Beam Search（集束搜索）是一种启发式图搜索算法，通常用在图的解空间比较大的情况下，为了减少搜索所占用的空间和时间，在每一步深度扩展的时候，剪掉一些质量比较差的结点，保留下一些质量较高的结点。这样减少了空间消耗，并提高了时间效率，但缺点就是有可能存在潜在的最佳方案被丢弃，因此Beam Search算法是不完全的，一般用于解空间较大的系统中。
更准确的说，集束搜索是一种类似于迭代最佳改进（iterative best improvement）的方法。 在算法的每个阶段，它选择当前所有节点中的k个最佳节点（或者如果小于k则选择所有节点），在下一阶段在这k个节点中进行同样的操作，直到算法停止。
由于集束搜索能同时考虑多个节点，它对于存储器限制的情况很有用，其中k的取值可以根据内存确定。
随机集束搜索是集束搜索的替代方案，其不是选择最佳k个节点，而是随机选择k个节点，但质量更好的节点更有可能被选中。 这可以通过使用吉布斯分布或玻尔兹曼分布来确定概率分布。
因此，随机集束搜索倾向于允许k节点比集束搜索更多样化。 在生物学的进化方面，评价函数反映了节点的适应性； 对于节点而言，适应的越好的节点更有可能将其所包含的那部分搜索结果传递给下一代。 随机集束搜索就像无性繁殖; 每个人给出轻微变异的孩子，然后随机集束搜索进行，适者生存。
下图是一个集束搜索的剪枝示意图。可以看到每一步都有一些节点被丢弃，用红色叉号表示。这个过程一直持续直到整个搜索完成。
集束搜索主要用于机器翻译、语音识别等系统。这类系统虽然从理论来说，也就是个多分类系统，然而由于分类数等于词汇数，简单的套用softmax之类的多分类方案，明显是计算量过于巨大了。
PS：中文验证码识别估计也可以采用该技术。
[描述来源： Artificial Intelligence: Foundations of Computational Agents by David L. Poole and Alan K. Mackworth. //https://blog.csdn.net/antkillerfarm/article/details/78889594]
发展历史
早于1992年，H. Ney等人描述了对用于10000字连续语音识别任务的时间同步集束搜索策略的改进。 这些改进基于两个措施：发音词典的树组织和音素级别的技术，这两种技术都直接与音素模型的状态级别的详细搜索相互作用。实验结果显示使用该算法整体搜索工作量减少了17倍而没有损失识别准确度。
2003年，Philipp Koehn等人提出了一种新的基于短语的翻译模型和解码算法，能够评估和比较此前提出的几种基于短语的翻译模型。其中，为比较不同的基于短语的翻译模型，他们开发的基于短语的解码器采用了集束搜索算法。该算法中集束搜索的时间复杂度是句子长度的二次方，并且与集束大小成线性关系。
2013年，同年，Alex Graves，Abdel-rahman Mohamed和Geoffrey Hinton在训练递归神经网络（RNN）用于语音识别问题时也使用了集束搜索来作为解码器。实证结果显示深度长短期记忆RNN在TIMIT音素识别基准上达到了17.7％的测试集误差，达到了当时的最佳分数。
2014年前后出现的序列到序列（Sequence to Sequence，seq2seq）模型，特别是基于编码-解码（Encoder - Decoder）的架构，对机器翻译，机器理解等领域产生了重大影响。而seq2seq模型在测试时一般会使用集束搜索来提高输出准确率。
2017年，IBM Watson研究院发表论文，提出了一个新的算法SCST（Self-critical Sequence Training），借鉴基础的强化学习算法REINFORCE 来训练网络，直接优化了CIDEr评价标准（Consensus-based image description evaluation）。在测试阶段，该网络进行了改进，可直接用贪婪搜索产生图像描述，而不需要更费时的集束搜索。
同年，针对神经机器翻译（NMT）中使用的集束搜索从左到右逐字地生成目标语句的策略过于简单的问题，Markus Freitag 和Yaser Al-Onaizan使用更灵活的集束搜索策略来集中精力加速解码器，其候选大小可以根据候选分数在每个时间步长变化。对于德语 - 英语和中英文两种语言对为测试，他们将原始解码器的速度提高了43％，而不会降低任何翻译质量。
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1992 | H. Ney等人描述了对用于10000字连续语音识别任务的时间同步集束搜索策略的改进 | Ney, H.; Haeb-Umbach, R.; Tran, B. H. and Oerder, M. (1992). Improvements in beam search for 10000-word continuous speech recognition. InICASSP-92: 1992 IEEE International Conference on Acoustics, Speech, and Signal Processing. pp. 9-12. |
| 2003 | Philipp Koehn等人提出了一种新的基于短语的翻译模型和解码算法，他们开发的基于短语的解码器采用了集束搜索算法 | Koehn, P. et al. (2003). Statistical phrase-based translation. NAACL '03. 1: 48-54.//Bengio, Y.; Ducharme, R.; Vincent, P.; Jauvin, C. (2003). A Neural Probabilistic Language Model. JMLR. 3:1137-1155. |
| 2013 | Alex Graves，Abdel-rahman Mohamed和Geoffrey Hinton在训练递归神经网络（RNN）用于语音识别问题时也使用了集束搜索来作为解码器 | Graves, A.; Mohamed, A. R. and Hinton, G. (2013). Speech recognition with deep recurrent neural networks.2013 IEEE International Conference on Acoustics, Speech and Signal Processing. pp. 6645-6649. |
| 2014 | Google研究提出基于序列到序列（seq2seq）的机器翻译模型 | Sutskever, I., Vinyals, O., & Le, Q. (2014). "Sequence to Sequence Learning with Neural Networks", arXiv preprint arXiv:1409.3215v3, 2014. |
| 2017 | IBM Watson研究院发表论文，提出了一个新的算法SCST（Self-critical Sequence Training） | Rennie, S. J. et al. (2017).Self-critical Sequence Training for Image Captioning. CVPR. |
| 2017 | 针对神经机器翻译（NMT）中使用的集束搜索从左到右逐字地生成目标语句的策略过于简单的问题，Markus Freitag和Yaser Al-Onaizan使用更灵活的集束搜索策略来集中精力加速解码器 | Freitag, M.; Al-Onaizan, Y. (2017).Beam Search Strategies for Neural Machine Translation.arXiv:1702.01806. |
发展分析
瓶颈
集束搜索的第一个问题就是由它于在每一步深度扩展的时候都会丢掉一部分节点，最佳解决方案有可能也会被丢弃。另外超参数B（即束宽）的选择有些主观，过小的B可考虑的选择少，搜索结果不好，过大的B太过于费时。
未来发展方向
可以考虑通过结合其他方法来提高搜索质量，如seq2seq模型解码时引入惩罚因子影响排序结果，使得解码出的结果更具多样性。另外，使用AutoML来自动确定B的取值也许也是一个方向。
Contributor：Yuanyuan Li