beam search是什么意思？

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的一个搜索树，我们从左往右搜索，每次搜索的最佳的三个点用红色标注。