公众号关注 “ML_NLP
设为 “星标”,重磅干货,第一时间送达!
来自 | 知乎
地址 | https://zhuanlan.zhihu.com/p/58526617
作者 | 恒仔
编辑 | 机器学习算法与自然语言处理公众号
本文仅作学术分享,若侵权,请联系后台删文处理
Beam Search 是一种启发式搜索算法,其使用广度优先搜索来构建搜索树,可降低内存需求,但不一定到全局最优解(without consuming too much memory)。

因为考虑到seq2seq的inference阶段的搜索空间过大而导致的搜索效率降低,所以即使是一个相对的局部优解在工程上也是可接受的。

PS:本文仅作学习过程中的记录,供讨论交流
在机器翻译(Machine Translation)里是这样的:在当前级别的状态下计算所有可能性,并按照递增顺序对他们进行排序,但只保留一定数量的可能结果(依据Beam Width决定数量),接着根据这些可能结果进行扩展,迭代以上的动作直到搜索结束并返回最佳解(具有最高概率的那个)
Andrew Ng讲得蛮清楚的,可以先看一下,为了方便我就直接下载传到知乎啦,相关链接在参考资料[4]。
https://link.zhihu.com/?target=https%3A//www.youtube.com/watch%3Fv%3DRLWuzLLSIgw
AndrewNg-Beam Search
这边综合一下 @萧瑟的回答,在Phased-Based Machine Translation做Test的时候(训练的时候知道正确答案,不需要再进行这个搜索):
假设词表大小为3,包含[A, B, C],Beam Width为2
  1. 1. 生成第1个词的时候,对P(A)、P(B)、P(C)进行排序,选取概率最大的两个,假设为A,C
  2. 2. 生成第2个词的时候,将当前序列A,C分别和词表中的所有词进行组合,得到新的6个序列为AA、AB、AC,CA、CB、CC,然后同样取概率最大的两个作为当前序列,假设为AA、CC
  3. 3. 重复以上的过程,直到遇到结束符为止,最终输出2个得分最高的序列
更新:刚刚发现一个不错的介绍10.10. 束搜索 - 《动手学深度学习》 文档,来保存一下。

PS:最近在Meeting的时候,发现Lab同学好几个已经开始在做Machine Translation了,一年半前刚进Lab的时候,全体还是以Data Mining尤其是Text Mining为主,现在都转向Deep Learning了。另外,最近也需要快一些实现一遍Sequence to Sequence,把相关的概念认真梳理一遍。
参考资料:
[1]:习翔宇:Seq2Seq中的beam search算法
[2]:谁能解释下seq2seq中的beam search算法过程?
[3]:谁能解释下seq2seq中的beam search算法过程?
[4]:C5W3L03 Beam Search
[5]:Beam search - Wikipedia
[6]:ADLxMLDS Lecture 5: Gated RNN and Sequence Generation (17/10/30)
重磅!忆臻自然语言处理-学术微信交流群已成立
可以扫描下方二维码,小助手将会邀请您入群交流,
注意:请大家添加时修改备注为 [学校/公司 + 姓名 + 方向]
例如 —— 哈工大+张三+对话系统。
号主,微商请自觉绕道。谢谢!
继续阅读
阅读原文