beam search是什么意思?

  算法/数据结构/数据库 计算复杂度    浏览次数:2413        分享
0

beam search是什么意思?

 

潇洒橙   2019-09-11 13:12



   1个回答 
5

beam search在nlp以及sequence modeling还是经常出现的。

假如我们要从上十万个元素中寻找4个元素$Y_1,\cdots,Y_4$使得$P(Y_1,Y_2,Y_3,Y_4|X)$最大,如果要找精确解,我们就要遍历所有的组合,也就是$\binom{10^6}{4}$,大概是$10^{15}$,天文数字,不可能去遍历的。

所以,我们通常找到一个$Y1$,使得$P(Y_1|X)$最大,然后根据

$$P(Y_1,Y_1|X)=P(Y_2|X,Y_1)P(Y_1|X)$$

再去寻找$Y_2$,使得$P(Y_2|X,Y_1)$最大。此次类推,按照这种贪婪算法,我们就能找到$Y_1,\cdots,Y_4$,搜寻次数只需要$4\times 10^6$。

但是显然这样的贪婪搜索不能保证最优性,甚至都无法达到较优。beam search就是对贪婪算法的改良。

beam就是带宽。当beam=3的时候,我们每次保留三个最佳候选然后再进行下一步迭代。

下图就是beam为3的一个搜索树,我们从左往右搜索,每次搜索的最佳的三个点用红色标注。


SofaSofa数据科学社区DS面试题库 DS面经

皮皮虾   2019-09-22 13:57



  相关讨论

NP-hard是什么意思

sql查询时count(*)、count(1)、count()哪个更快?

在python中获取模型运行的时间

kNN进行预测时计算复杂度是多少?

python里list的remove和pop方法的时间复杂度是多少?

朴素贝叶斯的训练/预测效率如何?快吗?

1000个瓶子和10个小白鼠的算法题

树的inorder traversal是什么意思?

如果让你付费提问一个IT问题,你会问什么?

GMM和KMeans哪个快一点?

  随便看看

修正R方(adjusted R square)是什么?

怎么从矩母函数(mgf)推导得到概率密度函数(pdf)?

python里的<<或者>>符号是什么意思?

如何检验两个样本是同分布的?

模型调参时常用到的Grid Search是什么意思?