Processing math: 29%

Deep Learning Note: 5-10 Beam 搜索

1. Beam 搜索

  前面提到,对于机器翻译问题,我们希望得到具有最高概率的句子,Beam 搜索就是用于获取这样的句子的算法。

  仍以前面的从法语翻译为英语的任务为例,使用如下的法语句子作为输入:

Jane visite l’Afrique en septembre.

  Beam 搜索的第一步是使用如图 1 所示的网络来计算 P(y<1>|x)。在贪婪算法中,我们只是选择能使 P(y<1>|x) 最大的一个词,而在 Beam 搜索中,我们选择能使 P(y<1>|x) 最大的前 B 个词,B 是一个参数,称为 Beam 宽度。

图 1

图 1

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

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

图 2

图 2

  图 2 中网络的输出 ˆy<2> 为给定法语输入 x 和英文翻译第 1 个词 y<1>=in 时,英文翻译第 2 个词的概率,即 P(y<2>|x,y<1>),进而可以得到给定法语输入 x 时,英语翻译前两个词为 y<1>,y<2>|x 的概率为:

P(y<1>,y<2>|x)=P(y<1>|x)P(y<2>|x,y<1>)

  由图 2 所示的网络可以得到词汇表中每个词作为英文翻译的第 2 个词时的 y<1>,y<2>|x,共计 10000 个概率。

  对于从第一步得到的另两个词 jane 和 september,也使用同样的网络,如图 3 所示,得到给定法语输入 x 和英文翻译第 1 个词为 jane 或 september 时,英文翻译第 2 个词的概率 P(y<2>|x,y<1>),进而由式 (1) 得到英语翻译前两个词为 y<1>,y<2>|x 的概率,共计有 20000 个概率。

图 3

图 3

  由此得到了 30000 个 y<1>,y<2>|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<1>,y<2>,y<3>|x),保存 3 个具有最大概率的组合,假设为 (in september jane),(jane is visiting) 和 (jane visits africa)。

图 3

图 3

  不断重复上面的步骤,每一步都可以在英文翻译中添加一个词,直到得到 ,即句子结束的标记,则翻译结束。

  上面的例子中使用 B=3,即每一步保留三个可能的输出,而当使用 B=1 时,Beam 搜索算法即变为贪婪算法。通过选择如 B=3B=10 等大于 1 的值,Beam 搜索算法的效果要远好于贪婪算法。

2. 改善 Beam 搜索

2.1. 长度归一化

  长度归一化(Length Normalization)是对 Beam 搜索算法的一个小改进。Beam 搜索算法的优化目标是:

argmax

  式 (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 取值在 01 之间,如 0.7,则可以调整归一化的程度。\alpha 是一个经验参数,并没有严格的理论支持,可以作为一个超参数进行调优。

  在 Beam 搜索过程中,会得到各种长度的句子,假设句子最大长度为 30,则 T_y 可能为 1, 2, 3, … 30。对于每一个句子,使用式 (6) 计算得到一个分数,然后选出得分最高的句子,作为最终的输出。

2.2. 参数 B 的选择

  Beam 搜索中的 Beam 宽度参数 B 用于控制搜索的每一步中所要保留的候选数量,B 的值越大,保留的候选越多,越可能得到更好的结果,但相对应的,计算量也更大。反之,B 的值越小,保留的候选越少,得到的结果可能更差,但计算量会更小。

  在前面的例子中,使用了 B = 3,这是一个较小的取值。对于生产系统,通常会使用更大的取值,如使用 B = 10B = 100 对于生产系统来说是一个很大的取值,但对用于研究目的的系统,甚至会使用 B = 1000 甚至 B = 3000B 的取值取决于具体的应用和领域,可以尝试使用不同的取值,但如果取得太大,收益通常会递减。将 B1 提升到 10 可能会带来巨大的提升,而将 B1000 提升到 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,则可以使用前文介绍的方法对网络进行进一步的错误分析,判断应该增加正则化,还是获取更多训练数据,还是调整网络结构等等。