Loading...
墨滴

cpgsmldl

2021/06/04  阅读:30  主题:橙心

Beam Search 算法小结

算法简介

Beam Search(集束搜索)是一种启发式图搜索算法,通常用在图的解空间比较大的情况下,为了减少搜索所占用的空间和时间,在每一步深度扩展的时候,剪掉一些质量比较差的结点,保留下一些质量较高的结点。这样减少了空间消耗,并提高了时间效率,但缺点就是有可能存在潜在的最佳方案被丢弃,因此Beam Search算法是不完全的,一般用于解空间较大的系统中。

Beam Search(集束搜索)使用广度优先策略建立搜索树,在树的每一层,按照启发代价对节点进行排序,然后仅留下预先确定的个数(Beam Width-集束宽度)的节点,仅这些节点在下一层次继续扩展,其他节点就被剪掉了。

Beam Search(集束搜索)多用在一些大型系统中,比如机器翻译系统,语音识别系统等,因为这些系统中的数据集可能非常大,而且结果也没有唯一正确的解,系统用最快的方式找到最接近正确的解才是系统的目标。

解码是seq2seq模型的常见问题,常用方法有贪心搜索(Greedy Search)集束搜索(Beam Search)。

贪心搜索(greedy search)

贪心搜索最为简单,每一个时间步都取出了条件概率最大一个结果。

集束搜索(beam search)

而beam search是对贪心策略一个改进。思路也很简单,就是稍微放宽一些考察的范围。在每一个时间步,不再只保留当前分数最高的1个输出,而是保留num_beams个。当num_beams=1时集束搜索就退化成了贪心搜索。

下图是一个实际的例子,每个时间步有A、B、C、D、E共5种可能的输出,图中的num_beams=2,也就是说每个时间步都会保留到当前步为止条件概率最优的2个序列。

  • 第 1 个时间步,A和C是最优的两个序列,因此得到了两个结果[A],[C],其他三个就被丢弃了;
  • 第 2 个时间步,得到10个候选[AA],[AB],[AC],[AD],[AE],[CA],[CB],[CC],[CD],[CE],对这10个序列进行统一排名,再保留最优的两个序列,即[AB][CE]
  • 第 3 个时间步,得到10个候选[ABA],[ABB],[ABC],[ABD],[ABE],[CEA],[CEB],[CEC],[CED],[CEE],对这10个序列进行统一排名,再保留最优的两个序列,即[ABD],[CED]

可以发现,beam search在每一步需要考察的候选人数量是贪心搜索的num_beams倍,因此是一种牺牲时间换性能的方法。

参考

cpgsmldl

2021/06/04  阅读:30  主题:橙心

作者介绍

cpgsmldl