集束搜索(beam search)和贪心搜索(greedy search)
最近读论文的时候看到文中经常用到集束搜索(beam search),可能很多人不懂这到底是个什么算法,其实很简单,顺便把贪心搜索(greedy search)也介绍一下。
贪心搜索(greedy search)
贪心搜索最为简单,直接选择每个输出的最大概率,直到出现终结符或最大句子长度。
集束搜索(beam search)
集束搜索是一种启发式图搜索算法,在图的解空间比较大的情况下,为了减少搜索所占用的空间和时间,在每一步深度扩展的时候,剪掉一些质量比较差的结点,保留下一些质量较高的结点。
具体过程为:使用广度优先策略在树的每一层建立搜索树,按照启发代价对节点进行排序,然后仅留下预先确定的个数(Beam Width-集束宽度)的节点,仅这些节点在下一层次继续扩展,其他节点就被剪掉了。(注意:如果集束宽度无穷大,那该搜索就是宽度优先搜索)
好处:减少了空间消耗,并提高了时间效率。
概念可能不好理解,下完下面的例子你就会发觉真的很简单。
假设字典为[a,b,c],beam size选择2,则如下图有:
- 在生成第1个词的时候,选择概率最大的2个词,那么当前序列就是a或b。
- 生成第2个词的时候,我们将当前序列a或b,分别与字典中的所有词进行组合,得到新的6个序列aa ab ac ba bb bc,然后从其中选择2个概率最高的,作为当前序列,即ab或bb。
- 不断重复这个过程,直到遇到结束符为止。最终输出2个概率最高的序列。
是不是很简单啊?