3.3 集束搜索（Beam Search）

“Jane visite l'Afrique en Septembre.”翻译成英语"Jane is visiting Africa in September".，集束搜索算法首先做的就是挑选要输出的英语翻译中的第一个单词。这里列出了10,000个词的词汇表，忽略大小写，在集束搜索的第一步中用这个网络来评估第一个单词的概率值，给定输入序列$x$，即法语作为输入，第一个输出$y$的概率值是多少

集束搜索会考虑多个选择，集束搜索算法会有一个参数B，叫做集束宽（beam width）。这个例子中集束宽设成3，意味着集束搜索一次会考虑3个可能结果，比如对第一个单词有不同选择的可能性，最后找到in、jane、september，是英语输出的第一个单词的最可能的三个选项，然后集束搜索算法会把结果存到计算机内存里以便后面尝试用这三个词。为了执行集束搜索的第一步，需要输入法语句子到编码网络，然后解码这个网络，softmax层会输出10,000个概率值，然后取前三个存起来，概率表示为：

$$P(\hat y^{<1>} | x)$$

集束搜索算法的第二步：针对每个第一个单词考虑第二个单词是什么

为了评估第二个词的概率值，把$y^{<1>}$设为单词in（编号3），输出就是$y^{<2>}$（编号5），有了这个连接（编号6），这个网络就可以用来评估：在给定法语句子和翻译结果的第一个单词in的情况下第二个单词的概率

在第二步更关心的是要找到最可能的第一个和第二个单词对，所以不仅仅是第二个单词有最大的概率，而是第一个、第二个单词对有最大的概率（编号7）。可以表示成第一个单词的概率（编号8）乘以第二个单词的概率（编号9）：

$$P(\hat y^{<1>},\hat y^{<2>}|x)=P(\hat y^{<1>} | x)\cdot P(\hat y^{<2>}|x,\hat y^{<1>})$$

jane、september跟上面一样

注意，如果集束搜索找到了第一个和第二个单词对最可能的三个选择是“in September”或者“jane is”或者“jane visits”，就意味着去掉了september作为英语翻译结果的第一个单词的选择，第一个单词现在减少到了两个可能结果，但是集束宽是3，还是有$y^{<1>}$，$y^{<2>}$对的三个选择

接着，再预测第三个单词。分别以in september，jane is，jane visits为条件，计算每个词汇表单词作为预测第三个单词的概率。从中选择概率最大的3个作为第三个单词的预测值，得到：in september jane，jane is visiting，jane visits africa

概率表示为：

$$P(\hat y^{<3>}|x,\hat y^{<1>},\hat y^{<2>})$$

此时，得到的前三个单词的3种情况的概率为：

$$P(\hat y^{<1>},\hat y^{<2>},\hat y^{<3>}|x)=P(\hat y^{<1>} | x)\cdot P(\hat y^{<2>}|x,\hat y^{<1>})\cdot P(\hat y^{<3>}|x,\hat y^{<1>},\hat y^{<2>})$$

以此类推，每次都取概率最大的三种预测。最后，选择概率最大的那一组作为最终的翻译语句：

Jane is visiting Africa in September.

如果参数B=1，则就等同于greedy search。实际应用中，可以根据不同的需要设置B为不同的值。一般B越大，机器翻译越准确，但同时也会增加计算复杂度