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

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

[![](https://github.com/fengdu78/deeplearning_ai_books/raw/master/images/725eec5b76123bf45c9495e1231b6584.png)](https://github.com/fengdu78/deeplearning_ai_books/blob/master/images/725eec5b76123bf45c9495e1231b6584.png)

**束搜索**就是最大化概率$$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：**

[![](https://github.com/fengdu78/deeplearning_ai_books/raw/master/images/96e50aec6e1d7287e5bac70a0c4d92f4.png)](https://github.com/fengdu78/deeplearning_ai_books/blob/master/images/96e50aec6e1d7287e5bac70a0c4d92f4.png)

* **B**越大，考虑的选择越多，找到的句子可能越好，但是算法的计算代价越大，因为要把很多的可能选择保存起来，内存占用增大
* 如果用小的束宽**B**，结果会没那么好，因为在算法运行中，保存的选择更少，但是算法运行的更快，内存占用也小

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

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