【Beam Search】波束搜索的直观解释
原题：An intuitive explanation of Beam Search
原文：HTML
作者：Renu Khandelwal
在本文中，将详细介绍神经机器翻译是如何使用序列到序列（sequence to sequence）算法来为目标语言找到句子中最相关的单词的。
What is Beam search?
为了理解波束搜索（Beam search），我们将以序列到序列的神经机器翻译为例来说明。
序列到序列模型使用具有长短时记忆(LSTM)或门控循环单元(GRU)的编码器和解码器框架作为基本块。
编码器（Encoder）映射源序列（source sequence），对源信息进行编码，并将其传递给解码器。解码器将来自编码器的编码数据作为输入，同时将字符串起始符 <START> 作为初始输入，以产生输出序列。
这个源序列（源语句）是印地语的一个句子，目标序列是用英语生成的。希望为翻译选择最合适、最有可能与印地语句子意思相匹配的单词。
如何为目标序列选择最佳和最有可能的单词？
一个简单的方法是用目标语言建立词汇库，比如10000个单词，然后根据源序列，得到10000个目标单词的概率。源语句在目标语言中可能有多种可能的翻译。
应该随机选择任何翻译吗？
我们的目标是选出最好最有可能翻译的词，所以我们根据源句选择概率最大的目标词。
应该只挑一个最好的翻译吗？
贪婪搜索（Greedy Search）算法为每个时间步长选择一个最佳候选作为输入序列。只选择一个最佳候选可能适合当前的时间步，但当我们构建完整的句子时，它可能是一个次优选择。
波束搜索（Beam Search）算法基于条件概率在每个时间步长为输入序列选择多个备选方案。多个备选方案的数量取决于一个称为波束宽度（Beam Width）的参数 B B B。在每个时间步，波束搜索选择 B B B 个具有最高概率的最佳备选方案作为该时间步最可能的选择。
让我们举个例子来理解这一点。
我们将选择 beam width=3；英语词汇有10000个。
第一步：给定输入句子，找出概率最高的前3个单词。最可能的单词数量基于波束宽度。
- 将编码后的输入句子输入到解码器；解码器将对词汇表中的所有10000个单词应用softmax函数。
- 从10000个概率得分中，选出概率最高的前3个单词。
- 考虑翻译单词的3个最可能的选择，因为波束宽度设置为3。如果波束宽度设置为10，则选择概率最高的前10个单词。
- 把最重要的三个字：I，My，We 储存在内存中。
Step 1:Find three words with the highest probability based on the input sentence
贪婪搜索总是只考虑一个最好的选择。
第二步：根据条件概率找到第一个和第二个单词的三个最佳配对。
Step 2: Find the top 3 pair of words for the first and second word of the translated sentence
- 将第一步中选择的前三个单词（I, My, We）作为第二步的输入。
- 将softmax函数应用于词汇表中的所有10000个单词，为第二个单词找到三个最佳选项（上图中为：am，parent，will）。在这样做的同时，我们将使用条件概率找出最有可能形成一对的第一个和第二个单词的组合。
- 为了找到第一个和第二个单词的3个最佳对，我们首先取第一个单词
“I”，对词汇表中的所有10000个单词应用softmax函数。对第一个单词中的候选“My”和“We”做同样的操作。 - 以上操作需要与运行30000个不同的组合，选出第一个和第二个单词的前3个词对。结果为：
“I am”,“My parents”,“I will”。 - 删除第一个单词
“We”，因为没有找到任何带有“We”的词对，而第一个单词和第二个单词的条件概率很高。 - 在每一步，都实例化（instantiate）编码器-解码器网络的三个副本，以评估这些部分语句片段和输出。网络的副本数与波束宽度的大小相同。
第三步：根据输入的句子和选择的第一个和第二个单词，找出第一个、第二个和第三个单词的三个最佳配对。
Step 3: find the most likely choice of the first three words in the translated sentence
- 连同输入句子和上一步得出的前3个第一和第二个单词组成的单词对：
“I am”、“My parents”和“I will”，找到条件概率最高的第三个单词组成的单词对。 - 以上操作需要再次运行30000个组合来选择第一个、第二个和第三个单词的最佳和最可能的组合，并实例化seq2seq、编码器-解码器模型的三个副本。
- 前2个第一、第二和第三个单词组成的单词对是：
“I am visiting”、“I will visit”和“l am going”。 - 删除
“My parents”组合，因为我们在前三个单词组成的单词对中没有找到与之相关的单词对。
继续这个过程，选出3个概率最高的句子。这3个句子的长度可以不同，也可以相同。
Three output sentences with the highest conditional probabilities and different lengths
我们最终选择解码器的输出作为概率最高的句子。
波束宽度（beam width）的值越高，翻译效果会越好吗？
较高的光束宽度将提供更好的翻译结果，但会使用大量的内存和计算能力。
当波束宽度为3，词汇表为10000时，需要在每个时间步评估30000种组合，创建3个编码器-解码器实例，最大句子长度为9。创建编码器-解码器的多个副本并在每个时间步计算30000个单词的条件概率需要大量内存和计算能力。
较低的波束宽度将导致较差的翻译结果，但却减少了内存占用和运算资源。
Conclusion
波束搜索是序列到序列（sequence to sequence）深度自然语言处理算法中最流行的搜索策略，如神经机器翻译、图像字幕、聊天机器人等。
波束搜索使用条件概率，基于波束宽度考虑多个最佳选项，优于次优的贪婪搜索算法。