Beam Search 算法

我们经常需要预测一个句子，预测时第 2 个词依赖于前 1 个词，预测第 3 个词时依赖于前面的 2 个词，当预测第 n 个词时依赖于前 n-1 个词，我们需要找到一个这样的词的序列，使得概率值最大，或者至少能够被人接受。

我们马上就可以想到可以使用穷举的方法，把所有可能的序列都罗列出来，从里面选个概率最大的就可以了。这样可以吗? 我们写下它的过程（假设：词典有1024个词）：

1. 输入起始词，得到 1024 个词预测结果
2. 接下来，将 1024 个词逐个输入模型，进行预测，此时每个词对应了 1024 个预测结果，共有 1024*1024 待候选的结果
3. 如果要预测的句子有 3 个词组成，那么还需要将 1024 * 1024 个词再次输入模型，每个词再对应 1024 个预测结果，即：需要计算 1024*1024*1024 个不同词序列的概率值，从中选择概率值最大的词序列

从上面的过程可以看到，穷举法能够找到全局最优解，但是计算量太大了，加入：词典再大一些、预测词的数量再多一些…. 计算量过于巨大了…

我们可以使用贪心搜索思想，它和穷举思想可不同，计算量很小，它的搜索过程如下：

1. 输入起始词，得到 1024 个预测结果，只取概率值最大的结果
2. 接下来，将上次得到的概率值最大的预测结果送入模型，预测出 1024 个词，仍然取概率值最大的词作为本时间步的预测词
3. 以此类推… 直到预测出指定长度的句子

贪心搜索很明显计算量比穷举法下降是指数级的，但是其解无法保证全局最优解、甚至是不错的局部最优都有些困难。

Beam Search 则是介于穷举搜索、贪心搜索之间的一种搜索算法，其算法过程如下：

1. 初始化 beam width 为 3
2. 输入起始词得到 1024 个预测结果，选择概率最大的前 3 个词作为候选词
3. 将 3 个分别输入模型，每个词预测出 1024 个词，取概率值最大的前 3 个词序列作为候选词，共有 9 个序列
4. 以此类推… 直到预测出指定长度的词序列

从这个过程，可以看到 Beam Search 似乎也并不能保证找到一个全局最优解，但通过 beam width 设置可能找到一个局部不错的解，对于工程中，可能也是能接受的一个结果。另外，我们也发现 beam search 的计算量没有穷举大，但是比贪心算法要大一些。

这三个的区别总结如下：

1. 贪心搜索每一步优化中，搜索的空间只有 1，只考虑当前可能性最高的候选，作为当前步骤的决策。
2. 束搜索每一步优化中，搜索的空间是 beam width 个概率最高的候选，作为当前步骤的决策。当 beam width 等于 1 时，此时等价于贪心搜索了。
3. 穷举搜索每一步优化中，搜索的空间是 n（所有词），作为当前步骤的决策。
4. 束搜索像是平衡了贪心搜索、穷举搜索的一种搜索算法。这个思想有点像，mini batch 梯度下降介于全批量梯度下降和随机梯度下降之间的一种算法。在我们很多 NLP 任务的预测阶段，经常使用 beam search 来生成最后的预测序列。