beam search是什么意思?

  算法/数据结构/数据库 计算复杂度    浏览次数:454        分享
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是什么意思   1回答

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

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

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

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

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

python中defaultdict的用法   2回答

python的set进行append操作?   2回答

python中如何合并两个dict   2回答

怎么在python中复制指定路径下的文件?   1回答

python中怎么获取cpu的个数?   1回答

python中怎么对一组逻辑变量求“或”?   2回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!