Wiki解释
Beam Search（集束搜索）是一种启发式图搜索算法，通常用在图的解空间比较大的情况下，为了减少搜索所占用的空间和时间，在每一步深度扩展的时候，剪掉一些质量比较差的结点，保留下一些质量较高的结点。这样减少了空间消耗，并提高了时间效率。
NLP中的应用
本人发现这个算法是在读NLP的相关论文时，下面从这个角度分析以下集束搜索。
在做文本生成时，每一个时间步可能的输出种类是词典的大小，在如此大的基数下，遍历整个生成空间是不现实的。
贪心策略
最容易想到的策略是贪心搜索，即每个时间步都取一个条件概率最大的输出，再将从开始到当前步的结果作为输入去获得下一个时间步的输出，直到模型给出生成结束的标志。例如下图，每一个时间步都取出了条件概率最大一个结果，生成了序列[A,B,C]。
很明显，这样做将原来指数级别的求解空间直接压缩到了与长度线性相关的大小。由于丢弃了绝大多数的可能解，这种关注当下的策略无法保证最终得到的序列概率是最优的。
Beam search
而beam search是对贪心策略一个改进。思路也很简单，就是稍微放宽一些考察的范围。在每一个时间步，不再只保留当前分数最高的1个输出，而是保留num_beams个。当num_beams=1时集束搜索就退化成了贪心搜索。
下图是一个实际的例子，每个时间步有ABCDE共5种可能的输出，即，图中的num_beams=2，也就是说每个时间步都会保留到当前步为止条件概率最优的2个序列。
Beam Search示意图
- 在第一个时间步，A和C是最优的两个，因此得到了两个结果
[A],[C]，其他三个就被抛弃了； - 第二步会基于这两个结果继续进行生成，在A这个分支可以得到5个候选人，
[AA],[AB],[AC],[AD],[AE]，C也同理得到5个，此时会对这10个进行统一排名，再保留最优的两个，即图中的[AB]和[CE]； - 第三步同理，也会从新的10个候选人里再保留最好的两个，最后得到了
[ABD],[CED]两个结果。
可以发现，beam search在每一步需要考察的候选人数量是贪心搜索的num_beams倍，因此相较于贪心算法，是一种牺牲时间换性能的方法。
集束搜索与维特比算法
但是集束搜索依然是一种贪心算法，可以认为是维特比算法的贪心形式，在维特比搜索中由于利用动态规划导致当字典较大时效率比较低，而集束搜索使用beam size参数来限制在每一步保留下来的可能性词的数量。
显然集束搜索属于贪心算法，不能保证一定能够找到全局最优解，因为考虑到搜索空间太大，而采用一个相对的较优解。而维特比算法在字典大小较小时能够快速找到全局最优解。
