# 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的准确的最大值


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://baozoulin.gitbook.io/neural-networks-and-deep-learning/di-wu-men-ke-xu-lie-mo-xing-sequence-models/di-wu-men-kexulie-mo-578b28-sequence-models/di-san-zhou-xu-lie-mo-xing-he-zhu-yi-li-ji-zhi-ff08-sequence-models-and-attention-mechanism/34-gai-jin-ji-shu-sou-suo-ff08-refinements-to-beam-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.