束搜索
目录
束搜索是权衡贪心和穷举的一种搜索方式
贪心搜索
贪心搜索的方式是每一个时间步都选择概率最大的那一个token，这样其实并不一定能找到最优解，因为前一个时间步的选择会影响后面的概率分布
例如这幅图展示了，如果在第二步选择了0.3，后续会变成0.6，这样总体概率累成起来反而变大了
穷举搜索
穷举搜索是一定能找到最优解的，毕竟考虑了所有情况，但是它通常是不可计算的。例如：10000个词的字典，预测10个时间步，则需要计算 $10^{40}$ 次，太大啦
束搜索
束搜索则综合了这两种方法
- 保存最好的$k$个候选
- 在每个时刻，对每个候选新加一项（n种可能），在$kn$个选项中选出最好的$k$个
时间复杂度： $knT$
分数：
$$ \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}),$$
$\alpha$通常设置为$0.75$。
解释：束搜索的结果长度不一致，如果不除以$L^\alpha$，那肯定会选择最短的那个预测
小结
- 序列搜索策略包括贪心搜索、穷举搜索和束搜索。
- 贪心搜索所选取序列的计算量最小，但精度相对较低。
- 穷举搜索所选取序列的精度最高，但计算量最大。
- 束搜索通过灵活选择束宽，在正确率和计算代价之间进行权衡。