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

图 1

  这里取 $B = 3$,假设字典中有 10000 个单词,且不考虑大小写,则将前面的法语句子输入图 1 所示的网络后,可以得到字典中每个词出现在英文翻译第一个单词位置上的概率,假设具有最大概率的三个词为 in、jane 和 september,Beam 算法会将这三个词保存起来,用于下一步。

  在 Beam 搜索的第二步中,使用第一步得到的 in 作为英文翻译的第一个词,输入如图 2 所示的网络。

图 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

图 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

图 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,则可以使用前文介绍的方法对网络进行进一步的错误分析,判断应该增加正则化,还是获取更多训练数据,还是调整网络结构等等。