3.4 改进集束搜索（Refinements to Beam Search）

长度归一化（Length normalization）是对束搜索算法稍作调整的一种方式，使之得到更好的结果

束搜索就是最大化概率$P(y^{< 1 >}\ldots y^{< T_{y}>}|X)$，表示成:

$$P(y^{<1>}|X)P(y^{< 2 >}|X,y^{< 1 >})P(y^{< 3 >}|X,y^{< 1 >},y^{< 2>})\cdots P(y^{< T_{y} >}|X,y^{<1 >},y^{<2 >}\ldots y^{< T_{y} - 1 >})$$

即乘积概率（the product probabilities）：

$$arg\ max\prod_{t=1}^{T_y} P(\hat y^{<t>}|x,\hat y^{<1>},\cdots,\hat y^{<t-1>})$$

这些概率值通常都远小于1，会造成数值下溢（numerical underflow），即数值太小了，导致电脑的浮点表示不能精确地储存

因此在实践中,不会最大化这个乘积，而是取$log$值：

$$arg\ max \sum_{t=1}^{T_y}\log P(\hat y^{<t>}|x,\hat y^{<1>},\cdots,\hat y^{<t-1>})$$

会得到一个数值上更稳定的算法，不容易出现数值的舍入误差（rounding errors）或者说数值下溢（numerical underflow）

参照原来的目标函数（this original objective），如果有一个很长的句子，那么这个句子的概率会很低，因为乘了很多项小于1的数字来估计句子的概率，就会得到一个更小的概率值，所以可能不自然地倾向于简短的翻译结果，因为短句子的概率是由更少数量的小于1的数字乘积得到的，所以乘积不会那么小。概率的$log$值也有同样的问题

解决：可以把它归一化，通过除以翻译结果的单词数量。即取每个单词的概率对数值的平均，这样很明显地减少了对输出长的结果的惩罚：

$$arg\ max\ \frac{1}{T_y}\sum_{t=1}^{T_y}\log P(\hat y^{<t>}|x,\hat y^{<1>},\cdots,\hat y^{<t-1>})$$

在实践中，会用一个更柔和的方法（a softer approach），在$T_{y}$上加上指数$\alpha$：

$$arg\ max\ \frac{1}{T_y^{\alpha}}\sum_{t=1}^{T_y}\log P(\hat y^{<t>}|x,\hat y^{<1>},\cdots,\hat y^{<t-1>})$$

$\alpha$可以等于0.7。如果$\alpha$等于1，就相当于完全用长度来归一化，如果$\alpha$等于0，$T_{y}$的0次幂就是1，就相当于完全没有归一化，$\alpha$就是算法另一个超参数（hyper parameter）

总结一下如何运行束搜索算法：

当运行束搜索时，会看到很多长度分别等于1、2、3...的句子等等，针对这些所有的可能的输出句子，取概率最大的几个句子，然后对这些句子计算目标函数$arg\ max\ \frac{1}{T_y^{\alpha}}\sum_{t=1}^{T_y}\log P(\hat y^{<t>}|x,\hat y^{<1>},\cdots,\hat y^{<t-1>})$，最后从经过评估的这些句子中挑选出在归一化的$log$ 概率目标函数上得分最高的一个，也叫作归一化的对数似然目标函数（a normalized log likelihood objective）

如何选择束宽B：

• B越大，考虑的选择越多，找到的句子可能越好，但是算法的计算代价越大，因为要把很多的可能选择保存起来，内存占用增大

• 如果用小的束宽B，结果会没那么好，因为在算法运行中，保存的选择更少，但是算法运行的更快，内存占用也小

在产品中，经常可以看到把束宽设到10，当B很大的时候，性能提高会越来越少。对于很多应用来说，从束宽1，也就是贪心算法，到束宽为3、到10，会看到一个很大的改善。但是当束宽从1000增加到3000时，效果就没那么明显

相对广度优先搜索（BFS, Breadth First Search algorithms），深度优先搜索（DFS, Depth First Search）这些精确的搜索算法（exact search algorithms），束搜索运行的更快，但是不能保证一定能找到argmax的准确的最大值