束搜索.md

贪心搜索(greedy search)

贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。 贪心搜索最为简单，直接选择每个输出的最大概率，直到出现终结符或最大句子长度。 虽然贪心搜索效率很高，但是不能保证找到最优解，例如:

在这个例子中，贪心算法选择每个时间步最大概率对应的单词结果为:ABC。 但是，每一步的最优解不一定是整个句子的最优解。

在这个例子中，第二个时间步没有选择局部最优的B而是选择了C，导致之后的时间步计算的概率也不一样，最终结果为:ACB。 两个句子的概率分别为

$0.5 \times 0.4\times0.4\times0.6=0.048$

和

$0.5\times 0.3\times 0.6\times 0.6=0.054$

第二个解明显更优。 但是想要找到最优解就需要使用穷举法，这计算量是巨大的，所有可以使用折中的方法束搜索。

束搜索(beam search)

beam search是对greedy search的一个改进算法。相对greedy search扩大了搜索空间，但远远不及穷举搜索指数级的搜索空间，是二者的一个折中方案。 beam search有一个超参数beam size（束宽），设为 k 。第一个时间步长，选取当前条件概率最大的 k个词，当做候选输出序列的第一个词。之后的每个时间步长，基于上个步长的输出序列，挑选出所有组合中条件概率最大的 k 个，作为该时间步长下的候选输出序列。始终保持 k 个候选。最后从 k 个候选中挑出最优的。 例如，当k等于2的时候，上面的例子为： 过程详解:

1. 最开始选择了概率最大的两个词元分别是A和C。
2. 再从两个词元的扩展中选择最大的两个情况分别是AB和CE。
3. 循环扩展、选择词元的过程，知道搜索结束。
4. 选择最后结果中概率最大的句子。

候选分数

对于每个候选的词元，不能简单的计算概率，因为每个词元的概率都是小于1的值，长句子的概率乘积更有可能小于短句子，所以这个使用候选分数来选择词元。 每个候选的最终分数是：

$\frac{1}{L^\alpha} \log P(y_1, \ldots, y_{L}\mid \mathbf{c}) = \frac{1}{L^\alpha} \sum_{t'=1}^L \log P(y_{t'} \mid y_1, \ldots, y_{t'-1}, \mathbf{c})$

其中 $L$ 是最终候选序列的长度，  $\alpha$ 通常设置为 $0.75$ 。 因为一个较长的序列在求和中会有更多的对数项， 因此分母中的 $L^\alpha$ 用于惩罚长序列。

总结

beam search不保证全局最优，但是比greedy search搜索空间更大，一般结果比greedy search要好。 greedy search 可以看做是 beam size = 1时的 beam search。 穷举法可以看作是beam size = n时的 beam search。 主要用于[[Seq2Seq]]模型选择最优解。