63 束搜索【动手学深度学习v2】
束搜索（beam search）
贪心搜索（greedy search）
在 seq2seq 中使用了贪心搜索来预测序列（对于输出序列的每一时间步，将当前时刻具有最高条件概率的词元输出，作为下一个序列，一旦输出序列包含了“<eos>”或者达到最大长度，则输出完成）
但是贪心搜索的结果可能不是最优的，举例如下
- 上图中将两次选择各部分的概率分别进行相乘，会发现虽然右边并没有选择最优，但是最终生成 sequence 的概率比贪心搜索所得到的概率更高（因为当前步所选择的最优的词从整个句子来看的话不一定是最优的，所以贪心搜索可能是效率最高的，但是不一定是最优的）
穷举搜索（exhaustive search）
如果目标是获取最优序列，可以考虑使用穷举搜索：穷举地列出所有可能的输出序列及其条件概率，然后计算输出条件概率最高的一个（遍历所有的序列，将所有的序列的概率计算出来，最后选出最好的那个序列一定是最优的，也就是将所有的序列都使用模型评估一下）
如果输出字典大小为 n ，序列最长为 T ，那么需要考察 n ^ T 个序列
- n = 10000 , T = 10 : n^T = 10^4
- 计算上不可行，现有的计算机几乎不可能计算它
- 贪心搜索是最快的，但不是最好的；穷举搜索是最好的，但是计算量巨大，计算起来比较困难
束搜索（beam search）
- 如果只看重精度的话，显然穷举搜索算法是最优的；如果更注重计算成本的话，则贪心搜索算法是最优的；束搜索的实际应用介于这两个极端之间
- 在每个时刻，保存最好的 k 个候选序列，对每个候选新加一项（ n 种可能），在 kn 个选项中选出最好的 k 个
举例：
- 束搜索是贪心搜索的改进版本，它和贪心算法的区别在于，贪心算法每次都选择最好的一个词元来组成序列，而束搜索每次选择 k 个作为候选
- k 是超参数，称为束宽（beam size），在时间步 1 ，算法所选择的是具有条件概率最高的 k 个词元，这 k 个词元将分别是 k 个候选输出序列的第一个词元；在随后的每个时间步，基于上一时间步的 k 个候选输出序列，将继续挑出具有最高条件概率的 k 个候选输出序列
时间复杂度： O(knT)
- 对于每一个时刻 T 都需要做 kn 次搜索
- k = 5 , n = 10000 , T = 10 : knT = 5 x 10^5
- 束搜索的计算量介于贪心搜索和穷举搜索之间
- 贪心搜索可以看作是一种束宽为 1 的特殊类型的束搜索
- 通过灵活地选择束宽，束搜索可以在正确率和计算代价之间进行权衡
每个候选的最终分数是
- 最后不仅能够得到 k 个选择，还能够将搜索过程中得到的子序列也保存下来，基于这些序列获得最终候选输出序列集合，然后按照上述公式挑选其中条件概率乘积最高的序列作为输出序列
- 在计算概率的时候会发现，长句子的概率会低于短句子的概率（因为是各部分概率的乘积，而概率的值都是小于 1 的，所以句子越长，概率就越低，所以一个句子的概率会低于它的子句的概率），所以这里引入了一个 1 / (L ^ α)，等价于提高最终长句子所得到的分数，否则模型会倾向于学习长度较短的句子
- L 是最终候选序列的长度
- 通常 α = 0.75
总结
1、序列搜索策略包括贪心搜索、穷举搜索和束搜索
- 贪心搜索所选取序列的计算量最小，但是精度相对较低
- 穷举搜索所选取序列的精度最高，但是计算量最大
- 束搜索通过灵活选择带宽，在正确率和计算代价之间进行权衡
2、束搜索在每次搜索时保存 k 个最好的候选
- k = 1 时是贪心搜索，每一步总是选择最好的词元作为候选
- 束搜索的 k 一般取 5 或者 10 ，通常来说 k 的值选的越大，所选择的范围也就越大，但是可能最后实施的效果也就越差（在做语音特别是实时翻译的时候，k 的取值不能太大，如果取值比较大的话，会大大降低模型的实时性）
----end----
其他参考
1、《动手学深度学习》，课程安排，https://courses.d2l.ai/zh-v2/assets/pdfs/part-3_10.pdf
