Beam Search

Q: 什么是Beam Search? 它在NLP中的什么场景里会⽤到?

传统的广度优先策略能够找到最优的路径，但是在搜索空间非常大的情况下，内存占用是指数级增长，很容易造成内存溢出，因此提出了beam search的算法。

beam search尝试在广度优先基础上进行进行搜索空间的优化（类似于剪枝）达到减少内存消耗的目的。

在sequence2sequence模型中，beam search的方法只用在测试的情况，因为在训练过程中，每一个decoder的输出是有正确答案的，也就不需要beam search去加大输出的准确率。test的时候，假设词表大小为3，内容为a，b，c。beam size是decoder解码的时候：1： 生成第1个词的时候，选择概率最大的2个词，假设为a,c,那么当前序列就是a,c2：生成第2个词的时候，我们将当前序列a和c，分别与词表中的所有词进行组合，得到新的6个序列aa ab ac ca cb cc,然后从其中选择2个得分最高的，作为当前序列，假如为aa cb3：后面会不断重复这个过程，直到遇到结束符为止。最终输出2个得分最高的序列。

转自：https://www.jianshu.com/p/bc3beb101885