Deep Learning Note: 5-10 Beam 搜索
1. Beam 搜索
前面提到，对于机器翻译问题，我们希望得到具有最高概率的句子，Beam 搜索就是用于获取这样的句子的算法。
仍以前面的从法语翻译为英语的任务为例，使用如下的法语句子作为输入：
Jane visite l’Afrique en septembre.
Beam 搜索的第一步是使用如图 1 所示的网络来计算 $P(y^{\lt 1 \gt}|x)$。在贪婪算法中，我们只是选择能使 $P(y^{\lt 1 \gt}|x)$ 最大的一个词，而在 Beam 搜索中，我们选择能使 $P(y^{\lt 1 \gt}|x)$ 最大的前 $B$ 个词，$B$ 是一个参数，称为 Beam 宽度。
图 1
这里取 $B = 3$，假设字典中有 10000 个单词，且不考虑大小写，则将前面的法语句子输入图 1 所示的网络后，可以得到字典中每个词出现在英文翻译第一个单词位置上的概率，假设具有最大概率的三个词为 in、jane 和 september，Beam 算法会将这三个词保存起来，用于下一步。
在 Beam 搜索的第二步中，使用第一步得到的 in 作为英文翻译的第一个词，输入如图 2 所示的网络。
图 2
图 2 中网络的输出 $\hat{y}^{\lt 2 \gt}$ 为给定法语输入 $x$ 和英文翻译第 1 个词 $y^{\lt 1 \gt} = in$ 时，英文翻译第 2 个词的概率，即 $P(y^{\lt 2 \gt}|x, y^{\lt 1 \gt})$，进而可以得到给定法语输入 $x$ 时，英语翻译前两个词为 $y^{\lt 1 \gt}, y^{\lt 2 \gt}|x$ 的概率为：
\begin{equation}
P(y^{\lt 1 \gt}, y^{\lt 2 \gt}|x) = P(y^{\lt 1 \gt}|x)P(y^{\lt 2 \gt}|x, y^{\lt 1 \gt}) \tag{1}
\end{equation}
由图 2 所示的网络可以得到词汇表中每个词作为英文翻译的第 2 个词时的 $y^{\lt 1 \gt}, y^{\lt 2 \gt}|x$，共计 10000 个概率。
对于从第一步得到的另两个词 jane 和 september，也使用同样的网络，如图 3 所示，得到给定法语输入 $x$ 和英文翻译第 1 个词为 jane 或 september 时，英文翻译第 2 个词的概率 $P(y^{\lt 2 \gt}|x, y^{\lt 1 \gt})$，进而由式 (1) 得到英语翻译前两个词为 $y^{\lt 1 \gt}, y^{\lt 2 \gt}|x$ 的概率，共计有 20000 个概率。
图 3
由此得到了 30000 个 $y^{\lt 1 \gt}, y^{\lt 2 \gt}|x$ 的概率，从中选出概率最高的 3 个保存起来，即得到了 3 组最可能出现在句子前两个词的组合。假设得到 3 组概率最高的前两个词为 (in september)，(jane is) 和 (jane visits)，此时 Beam 搜索拒绝了 september 出现在句子第一个词的机会，但仍保留了 3 个选择。
需要注意的是，由于 Beam 宽度参数 $B = 3$，在实现中会创建 3 个如图 2 所示的网络实例，每个网络实例计算 10000 个概率。不会使用 30000 个网络来并行计算。
类似地，在第三步中，对于上一步得到的 3 个组合 (in september)，(jane is) 和 (jane visits)，使用如图 3 所示的网络，计算给定法语输入 $x$ 时，英文翻译的前三个词的概率 $P(y^{\lt 1 \gt}, y^{\lt 2 \gt}, y^{\lt 3 \gt}|x)$，保存 3 个具有最大概率的组合，假设为 (in september jane)，(jane is visiting) 和 (jane visits africa)。
图 3
不断重复上面的步骤，每一步都可以在英文翻译中添加一个词，直到得到
上面的例子中使用 $B = 3$，即每一步保留三个可能的输出，而当使用 $B = 1$ 时，Beam 搜索算法即变为贪婪算法。通过选择如 $B = 3$ 或 $B = 10$ 等大于 1 的值，Beam 搜索算法的效果要远好于贪婪算法。
2. 改善 Beam 搜索
2.1. 长度归一化
长度归一化（Length Normalization）是对 Beam 搜索算法的一个小改进。Beam 搜索算法的优化目标是：
\begin{equation}
\arg \underset{y}{\max} \prod_{t=1}^{T_y} P(y^{\lt t \gt}|x, y^{\lt 1 \gt},…,y^{\lt t-1 \gt}) \tag{2}
\end{equation}
式 (2) 中的 $\prod_{t=1}^{T_y} P(y^{\lt t \gt}|x, y^{\lt 1 \gt},…,y^{\lt t-1 \gt})$ 实际上就是 $P(y^{\lt 1 \gt},…,y^{\lt T_y \gt}|x)$，因为：
\begin{equation}
P(y^{\lt 1 \gt},…,y^{\lt T_y \gt}|x) = P(y^{\lt 1 \gt}|x) \cdot P(y^{\lt 2 \gt}|x, y^{\lt 1 \gt}) \cdot … \cdot P(y^{\lt T_y \gt}|x, y^{\lt 1 \gt},…,y^{\lt T_y \gt}) \tag{3}
\end{equation}
式 (2) 中的概率 $P(y^{\lt t \gt}|x, y^{\lt 1 \gt},…,y^{\lt t-1 \gt})$ 通常远小于 $1$，将这些概率相乘，得到的结果会非常小，会导致数值下溢（Numerical Underflow），使得计算机使用的的浮点数无法足够准确地表示这么小的数值。所以实际中，我们会取这些概率乘积的对数，又因为：
\begin{equation}
\log \prod_{t=1}^{T_y} P(y^{\lt t \gt}|x, y^{\lt 1 \gt},…,y^{\lt t-1 \gt}) = \sum_{t=1}^{T_y} \log P(y^{\lt t \gt}|x, y^{\lt 1 \gt},…,y^{\lt t-1 \gt}) \tag{4}
\end{equation}
故最大化概率乘积的对数相当于最大化概率的对数的和：
\begin{equation}
\arg \underset{y}{\max} \sum_{t=1}^{T_y} \log P(y^{\lt t \gt}|x, y^{\lt 1 \gt},…,y^{\lt t-1 \gt}) \tag{5}
\end{equation}
对数函数是一个单调递增的函数，使用式 (5) 可以得到和式 (2) 相同的结果，且数值更加稳定。
式 (2) 的另一个问题是句子越长，相乘的概率项越多，相乘的结果就越小。因此使用式 (2) 作为优化目标会导致模型偏向于输出更短的句子。式 (5) 也存在同样的问题，因为概率都小于 1，对于小于 1 数值，其对数都是负数；句子越长，概率项越多，它们的对数相加起来就越小。为了避免这个问题，可以对式 (5) 中的求和进行归一化：
\begin{equation}
\frac{1}{T_y^\alpha}\sum_{t=1}^{T_y} \log P(y^{\lt t \gt}|x, y^{\lt 1 \gt},…,y^{\lt t-1 \gt}) \tag{6}
\end{equation}
此时的优化目标为：
\begin{equation}
\arg \underset{y}{\max} \frac{1}{T_y^\alpha}\sum_{t=1}^{T_y} \log P(y^{\lt t \gt}|x, y^{\lt 1 \gt},…,y^{\lt t-1 \gt}) \tag{7}
\end{equation}
式 (7) 中，在求和符号前加入了 $\frac{1}{T_y^\alpha}$ 一项，用于对求和进行归一化。这里的 $\alpha$ 是一个用于控制归一化程度的参数，如果取 $\alpha = 1$，则相当于完全归一化整个求和；如果取 $\alpha = 0$，则相当于没有进行归一化；如果 $\alpha$ 取值在 $0$ 和 $1$ 之间，如 $0.7$，则可以调整归一化的程度。$\alpha$ 是一个经验参数，并没有严格的理论支持，可以作为一个超参数进行调优。
在 Beam 搜索过程中，会得到各种长度的句子，假设句子最大长度为 30，则 $T_y$ 可能为 $1, 2, 3, … 30$。对于每一个句子，使用式 (6) 计算得到一个分数，然后选出得分最高的句子，作为最终的输出。
2.2. 参数 B 的选择
Beam 搜索中的 Beam 宽度参数 $B$ 用于控制搜索的每一步中所要保留的候选数量，$B$ 的值越大，保留的候选越多，越可能得到更好的结果，但相对应的，计算量也更大。反之，$B$ 的值越小，保留的候选越少，得到的结果可能更差，但计算量会更小。
在前面的例子中，使用了 $B = 3$，这是一个较小的取值。对于生产系统，通常会使用更大的取值，如使用 $B = 10$。$B = 100$ 对于生产系统来说是一个很大的取值，但对用于研究目的的系统，甚至会使用 $B = 1000$ 甚至 $B = 3000$。$B$ 的取值取决于具体的应用和领域，可以尝试使用不同的取值，但如果取得太大，收益通常会递减。将 $B$ 从 $1$ 提升到 $10$ 可能会带来巨大的提升，而将 $B$ 从 $1000$ 提升到 $3000$ 所带来的提升也许就没那么大了。
相比与广度优先搜索（Breadth First Search，BFS）和深度优先搜索（Depth First Search，DFS），Beam 搜索运行得更快，但不保证一定能找到 $\arg \underset{y}{\max} P(y|x)$ 的最大值。
3. Beam 搜索的错误分析
Beam 搜索并不能保证一定找到最佳结果，在算法给出了错误的预测时，通过错误分析，可以判断错误来自 Beam 搜索还是 RNN。
仍以从法语翻译到英语的任务为例，假设开发集中有如下这句法语句子：
Jane visite l’Afrique en septembre.
人类给出的翻译是（以下记为 $y^\ast$）：
Jane visits Africa in September.
算法给出的翻译是（以下记为 $\hat{y}$）：
Jane visited Africa last September.
这里算法给出的翻译并不好，改变了原句的意思。
如前所述的机器翻译算法包含两个组成部分，一个是 RNN，一个是 Beam 搜索。对于算法给出的错误翻译，我们希望知道这个错误是来自 RNN 还是来自 Beam 搜索，以找到进一步修正和优化的方向。
RNN 计算的是给定法语输入 $x$ 的情况下，网络输出特定句子 $y$ 的概率，即 $P(y|x)$。可以通过分别计算网络输出人类翻译的句子 $y^\ast $ 的概率 $P(y^\ast|x)$ ，以及网络输出算法翻译的句子 $\hat{y}$ 的概率 $P(\hat{y}|x)$，并比较二者的大小，来判断错误出在 RNN 还是 Beam 搜索：
- 如果 $P(y^\ast|x) > P(\hat{y}|x)$，可见 Beam 搜索选择了 $\hat{y}$，但是 $P(y^\ast|x)$ 具有更高的概率，说明错误出在 Beam 搜索上，Beam 搜索没有能找到使得 $P(y|x)$ 具有最大概率的句子 $y$。
- 如果 $P(y^\ast|x) \leq P(\hat{y}|x)$，可见虽然事实上 $y^\ast$ 的翻译比 $\hat{y}$ 更好，但 RNN 预测 $P(\hat{y}|x)$ 具有更大的概率，说明错误出在 RNN 上。
需要注意的是，如果使用了长度归一化，则使用以上方法进行错误分析时，需要比较带有长度归一化的优化目标。
错误分析的步骤可以整理为表 1 的形式。
| Human | Algorithm | $P(y^\ast|x)$ | $P(\hat{y}|x)$ | At Fault? |
|---|---|---|---|---|
| Jane visits Africa in September. | Jane visited Africa last September. | $2 \times 10^{-10}$ | $1 \times 10^{-10}$ | Beam Search |
| … | … | … | … | … |
通过对算法在开发集中给出很差翻译的句子进行分析，可以得到在所有的开发集错误中，来自 RNN 和来自 Beam 搜索的错误各占有多大比例。如果发现大部分错误都来自 Beam 搜索，则可以增加 Beam 宽度 $B$ 的取值；如果发现大部分错误都来自 RNN，则可以使用前文介绍的方法对网络进行进一步的错误分析，判断应该增加正则化，还是获取更多训练数据，还是调整网络结构等等。