Michael Collins NLP Lecture 8

课程主页：http://www.cs.columbia.edu/~cs4705/

课程网盘地址：

链接：https://pan.baidu.com/s/1KijgO7yjL_MVCC9zKZ7Jdg
提取码：t1i3

这一讲主要介绍了基于短语的翻译模型。

Chapter 6 基于短语的翻译模型

1.介绍

在之前的讲座中，我们已经看到了IBM翻译模型1和2。在本讲义中，我们将描述基于短语的翻译模型。基于短语的翻译模型在IBM模型上提供了大大改进的翻译，并为许多语言对提供了最先进的翻译。
至关重要的是，基于短语的翻译模型允许在源语言或目标语言方面具有多个单词的词汇项：例如，我们可能有词汇项

$\text{(le chien, the dog)}$

该词汇项指定法语中的字符串$\text{le chien}$可以用英语翻译为$\text{ the dog}$。在源语言或目标语言方面使用多单词表达的选项与IBM模型1和2有很大不同，后者基本上是单词到单词的翻译模型（即，它们假设每个法语单词都是由单个英文单词生成）。多单词表达在翻译中非常有用；这是基于短语的翻译模型所带来改进的主要原因。

更正式地，基于短语的词库定义如下：

定义 1（基于短语的词库）

基于短语的词库$\mathcal L$是一组词汇项，其中每个词汇项是元组$(f,e,g)$，其中：

$f$是一个或多个外语单词的序列。
$e$是一个或多个英语单词的序列。
$g$是词汇项的得分。得分可以是实数中的任何值。

注意到没有限制要求词汇项中的外语单词和英语单词的数量应该相等。例如，允许以下项：

$(\text{au, to the, } 0.5)\\ (\text{au banque, to the bank, } 0.01) \\ (\text{allez au banque, go to the bank, }2.5)$

（类似的情况下，英语单词少于法语单词，也是允许的）。在词汇项的定义中的这种灵活性是重要的，因为在许多情况下，具有外语和英语单词的数量不相等的词汇项是非常有用的。

我们很快就会描述如何在翻译中使用短语词汇$\mathcal L$。然而，首先，我们将描述如何从一组翻译样本中学习短语词库。

2.从翻译样例中学习短语词汇

和以前一样，我们假设我们的训练数据包括英语句子$e^{(k)}=e^{(k)}_1…e^{(k)}_{l_k}$与配对的法语句子$f^{(k)}=f^{(k)}_1…f^{(k)}_{m_k}$，$k=1…n$。这里整数$l_k$是第$k$个英语句子的长度，$e^{(k)}_j$是第$k$个英语句子中的第$j$个单词。整数$m_k$是第$k$个法语句子的长度，$f^{(k)}_i$是第$k$个法语句子中的第$i$个单词。

除了句子本身之外，我们还假设每个训练样本都有一个对齐矩阵。第$k$个样本的对齐矩阵$A^{(k)}$形状为$l_k \times m_k$，其中

$A^{(k)}_{i,j}=\begin{cases} 1 & 如果法语中第i个单词和英语中第j个单词对齐\\ 0 & 其他 \end{cases}$

请注意，此表示形式比IBM模型1和2所考虑的对齐更为通用。在这些模型中，我们有对齐变量$a_i,i\in \{1…m_k\}$，指定了第$i$个法语单词所对应的英语单词。根据定义，在IBM模型1和2中，每个法语单词只能与单个英语单词对齐。利用对齐矩阵$A^{(k)}_{i,j}$，对齐可以是多对多的；例如，给定的法语单词可以与多于一个英语单词对齐（即，对于给定的$i$，我们可以有多个$j$满足$A^{(k)}_{i,j}=1$）。

关于如何导出对齐矩阵$A^{(k)}$，我们还不知道。在实际中，常见的方法类似于以下内容。首先，我们使用前一讲中描述的EM算法训练IBM模型2。其次，我们使用各种启发式方法从每个训练样本的IBM模型输出中提取对齐矩阵。具体来说，一个非常简单的方法如下（该方法太朴素，无法在实际中使用，仅作为示例）：

使用训练样本$e^{(k)},f^{(k)}$，$k=1…n$，使用前一讲中描述的EM算法训练IBM模型2。对于任何英语字符串$e$，法语字符串$f$和法语长度$m$，该模型给出条件概率$p(f,a|e,m)$。
对于每个训练样本，定义
$a^{(k)} =\arg \max_a p(f^{(k)},a|e^{(k)},m_k)$
也就是说，对于第$k$个样本，$a^{(k)}$是该模型下最可能的对齐（参见IBM模型1和2中有关如何计算它的注释）。
定义
$A^{(k)}_{i,j}=\begin{cases} 1 & a_i^{(k)}=j\\ 0 & 其他 \end{cases}$

例如对于句子

$\text{English: Mary did not slap the green witch}\\ \text{Spanish: Maria no daba una bofetada a la bruja verde}$

我们可以得到如下对齐矩阵：

该方法的问题是不是多对多。另一种方法如下（见PPT）

步骤1：为$p(f|e)$训练IBM模型2，并为每个$(e,f)$对提出最可能的对齐。
步骤2：为$p(e|f)$训练IBM模型2，并为每个$(e,f)$对提出最可能的对齐。

我们现在有两个对齐：将两个对齐的交点作为起点。

例如对于上例，得到两个对齐：

接下来以两者的交作为起点：

接下来启发式的算法如下：

仅探索$p(f|e)$和$p(e|f)$对齐的并。
一次添加一个对齐点。
仅添加当前没有对齐的单词。
一开始，将自己限制在当前对齐点的“邻居”（邻接或对角线）的对齐点。
稍后，考虑其他对齐点。

利用上述方法得到的对齐矩阵如下：

现在假设我们已经为每个训练样本导出了一个对齐矩阵，我们现在可以描述从一组翻译样本中提取基于短语的词库的方法。图1显示了用于此目的的简单算法。算法的输入是一组翻译样本，每个训练样本都有一个对齐矩阵。该算法迭代所有训练样本（$k=1…n$），并覆盖所有可能的短语对，其中短语对是一对$(s,t),(s’,t’)$，其中$(s,t)$是源语言句子中的子序列，并且$(s’,t’)$是目标语言句子中的子序列。例如，考虑包含以下句子的训练样本：

$f^{(k)} =\text{wir mussen auch diese kritik ernst nehmen} \\ e^{(k)} = \text{we must also take these criticisms seriously}$

那么$(s, t) = (1,2), (s’, t’) = (2, 5)$将对应潜在的词汇项

$\text{wir mussen, must also take these}$

对于每个可能的$(s,t),(s’,t’)$对，我们测试它是否与对齐矩阵$A^{(k)}$一致：函数$\text{consistent}(A^{(k)},(s,t),(s’,t’))$，如果可能的词汇项$(s,t),(s’,t’)$与训练样本的对齐矩阵一致，则返回true。有关$\text{consistent}$函数的定义，请参见图2。

对于那些一致的短语，我们将词条$(f,e)$添加到词库中，其中$f=f_s…f_t,e=e_{s’}…e_{t’}$。我们还增加计数$c(e,f)$和$c(e )$，对应于于在数据中看到词汇条目$(f,e)$的次数，$c(e )$对应于看到英语字符串$e$和任何外文短语$f$配对的次数。最后，在提取了语料库的所有词汇条目后，我们将任何短语$(f,e)$的分数定义为

$\log \frac{c(e,f)}{c(e)}$

这可以被解释为外语短语$f$关于给定英语短语$e$的对数条件概率的估计。

值得注意的是，这些概率在某种意义上是启发式的——即不清楚什么概率模型是整体模型的基础。但是，在使用模型进行翻译时，它们将非常有用。

3.基于短语的模型翻译

前面描述了如何从一组训练样本中导出基于短语的词库。在本节中，我们将描述如何使用基于短语的词库来定义给定输入句子的一组翻译；每个这样的翻译如何在模型下获得分数；最后，我们将介绍如何搜索输入句子的最高得分翻译，从而提供翻译算法。

3.1 短语和衍生词

基于短语的翻译模型的输入是具有$n$个单词的源语言句子，$x=x_1…x_n$。输出是目标语言中的句子。本节中的示例将使用德语作为源语言，使用英语作为目标语言。我们将使用德语句子

$\text{wir mussen auch diese kritik ernst nehmen}$

作为一个例子。

基于短语的翻译模型的一个关键组成部分是基于短语的词库，它将源语言中的单词序列与目标语言中的单词序列配对，如本讲义前面部分所述。例如，与上面显示的德语句子相关的词汇项包括

$\begin{aligned} &(\text{wir mussen, we must})\\ &(\text{wir mussen auch, we must also})\\ &(\text{ernst, seriously}) \end{aligned}$

等等。每个短语项都有一个相关的分数，可以取任何正值或负值。如前所述，估计短语分数的一种非常简单的方法是定义

$\begin{eqnarray*} g(f,e) =\log \frac{c(e,f)}{c(e)} \tag 1 \end{eqnarray*}$

其中$f$是外语词汇序列，$e$是英语单词序列，$c(e,f)$和$c(e)$是从某些语料库中获取的计数。例如，我们有

$g(\text{wir mussen, we must})= \log \frac{c(\text{we must, wir mussen})}{c(\text{we must})}$

分数为外语短语$f$关于给定英语短语$e$的对数条件概率。

我们介绍以下符号。对于特定输入（源语言）句子$x_1…x_n$，短语是元组$(s,t,e)$，表示源语言句子中的子序列$x_s…x_t$可以翻译为目标语言字符串$e$，使用基于短语的词库中的项。例如，短语$(1,2,\text{we must})$将指定子字符串$x_1x_2$可以被翻译为$\text{we must}$。每个短语$p=(s,t,e)$在模型下接收得分$g(p) \in \mathbb R$。对于给定的短语$p$，我们将使用$s(p),t(p),e(p)$来指代其三个分量。我们将使用$\mathcal P$来代表输入句子$x$的所有可能短语的集合。

请注意，对于给定的输入句子$x_1…x_n$，计算可能的短语集合$\mathcal P$很简单。我们只考虑$x_1…x_n$的每个子字符串，并包括短语词库中所有以子字符串作为英语字符串的项。我们最终可能会有一个以上的短语项。

衍生词$y$则是有限的短语序列，$p_1,p_2,…,p_L$，其中每个$p_j$，$j\in \{1…L\}$是$\mathcal P$的成员。长度$L$可以是任何正整数值。对于任何衍生词$y$，我们使用$e(y)$来代表由$y$定义的基础翻译，其通过连接字符串$e(p_1),e(p_2),…,e(p_L)$而得到。例如，如果

$\begin{eqnarray*} y = \text{(1, 3, we must also), (7, 7, take), (4, 5, this criticism), (6, 6, seriously)} \tag 2 \end{eqnarray*}$

那么

$e(y) = \text{we must also take this criticism seriously}$

3.2 有效衍生词集

我们将使用$\mathcal Y(x)$来表示输入句子$x=x_1…x_n $的有效衍生词集。 $\mathcal Y(x)$是长度有限的短语序列$p_1…p_L$的结合，满足以下条件：

每个$p_k$，$k\in \{1…L\}$是$x_1…x_n$的短语$\mathcal P$的成员。（回想一下，每个$p_k$是三元组$(s,t,e)$。）
每个单词只翻译一次。更正式地说，对于衍生词$y=p_1…p_L$，我们定义
$\begin{eqnarray*} y(i)=\sum_{k=1}^ L [\![ s(p_k) \le i \le t(p_k)]\!] \end{eqnarray*}$
是单词$i$被翻译的次数（如果$\pi$是真，那么$[![ \pi ]!]$为$1$，否则为$0$），那么我们必须有
$y(i) =1$
对$i=1…n$
对$k\in \{1…L-1\}$，
$|t(p_k) + 1-s(p_{k+1})| \le d$
其中$d\ge 0$是模型的参数。另外，我们必须有
$|1-s(p_1)|\le d$

前两个条件应该是明确的。最后一个条件取决于参数$d$，值得更多解释。

参数$d$是连续短语彼此之间的距离的限制，并且通常被称为失真限制（distortion limit）。为了说明这一点，请考虑我们之前的示例衍生词：

$y = \text{(1, 3, we must also), (7, 7, take), (4, 5, this criticism), (6, 6, seriously)}$

在这种情况下，$y=p_1p_2p_3 p_4$（即，短语的数量$L$等于$4$）。为了论证，假设失真参数$d$等于$4$。

我们现在将解决以下问题：这种衍生词是否满足条件

$\begin{eqnarray*} |t(p_k) + 1-s(p_{k+1})| \le d \tag 4 \end{eqnarray*}$

对$k=1…3$？首先考虑$k = 1$的情况。在这种情况下，我们有$t(p_1)= 3,s(p_2)= 7$。因此

$|t(p_1) + 1-s(p_2)| =|3+1-7| =3$

对于$k = 1$，满足公式$4$中的约束。可以看出，$|t(p_1) + 1-s(p_2)|$的值是短语$p_1$和$p_2$在句子中相互之间的距离的度量。失真限制指定连续短语必须彼此相对接近。

现在考虑$k = 2$的约束。在这种情况下我们有

$|t(p_2) + 1-s(p_3)| =|7+1-4| =4$

所以约束满足（回想一下，我们假设$d = 4$）。对于$k = 3$，我们有

$|t(p_3) + 1-s(p_4)| =|5+1-6| =0$

最后，我们需要检查约束

$|1-s(p_1)| \le d$

对于此示例，$s(p_1)=1$，所以满足约束。这个最终约束确保序列中的第一个短语$p_1$离句子的开头不太远。

作为一个因为不满足失真约束的无效的衍生的例子，考虑

$y = \text{(1, 2, we must), (7, 7, take), (3, 3, also), (4, 5, this criticism), (6, 6, seriously)}$

在这种情况下，可以验证

$|t(p_2) + 1-s(p_3)| =|7+1-3| =5$

大于失真限制$d=4$。

失真限制的动机是双重的：

它减少了模型中的搜索空间，使得模型的翻译更加高效。
根据经验，它经常被证明可以提高翻译效果。对于许多语言对，最好不要允许相互之间距离较长的连续短语，因为这会导致不好的翻译。

然而，应该注意的是，失真限制实际上是用于建模语言之间的词序差异的相当粗略的方法。在课程的后面，我们将看到试图改进这种方法的系统。

3.3 衍生词的得分

接下来的问题如下：我们如何评估衍生词的得分？也就是说，我们如何定义函数$f(y)$，它为句子的每个可能的衍生词分配一个分数？源语言句子$x$在该模型下的最佳翻译将是

$\arg \max_{y\in \mathcal Y(x)} f(y)$

在基于短语的系统中，任何衍生词$y$的得分按如下方式计算：

$\begin{eqnarray*} f(y) = h(e(y)) + \sum_{k=1}^L g(p_k) +\sum_{k=1}^{L-1}\eta \times |t(p_k) + 1-s(p_{k+1})| \tag 5 \end{eqnarray*}$

该分数的组成部分如下：

如前所述，$e(y)$是衍生词$y$的目标语言字符串。$h(e(y))$是三元语言模型下字符串$e(y)$的对数概率。因此，如果$e(y)=e_1…e_m$，那么
$h(e(y))= \log \prod_{i=1}^m q(e_i|e_{i-2},e_{i-1}) = \sum_{i=1}^m \log q(e_i|e_{i-2},e_{i-1})$
其中$q(e_i|e_{i-2},e_{i-1})$是三元语言模型下，单词$e_i$在二元组$e_{i-2},e_{i-1}$之后的概率。
如前所述，$g(p_k)$是短语$p_k$的得分（例如，公式$1$为一种可能的方法来定义$g(p)$）。
$\eta$是模型的“失真参数”。它通常可以是任何正值或负值，但在实际中它几乎总是负的。每一项
$|t(p_k) + 1-s(p_{k+1})|$
对应于短语$p_k$和$p_{k + 1}$相互远离的惩罚（假设$\eta $为负数）。因此，除了对连续短语之间的距离具有硬约束之外，我们还具有软约束（即，与该距离线性增加的惩罚）。

给定这些定义，源语言句子$x=x_1…x_n $在该模型下的最佳翻译是

$\arg \max_{y\in \mathcal Y(x)} f(y)$

3.4 总结

定义 2 （基于短语的翻译模型）

基于短语的翻译模型是元组$(\mathcal L, h,d,\eta)$，其中：

$\mathcal L$是基于短语的词库。$\mathcal L$的每个成员是元组$(f,e,g)$，其中$f$是一个或多个外语单词的序列，$e$是一个或多个英语单词的序列，$g\in \mathbb R$是$(f,e)$的分数。
$h$是三元语言模型：也就是说，对于任何英文字符串$e_1…e_m$，
$h(e_1...e_m) =\sum_{i=1}^m \log q(e_i|e_{i-2},e_{i-1})$
其中$q$是模型的参数，我们假设
$e_{-1}= e_0 = *$
其中*是语言模型中的特殊起始符号。
$d$是非负整数，指定模型下的失真限制。
$\eta\in \mathbb R$是模型中的失真惩罚。

对于输入句子$x_1…x_n$，定义$\mathcal Y(x)$是模型$(\mathcal L, h,d,\eta)$下的有效衍生词集。解码问题是找到

$\arg \max_{y\in \mathcal Y(x)} f(y)$

其中，假设$y=p_1p_2…p_L$，

$f(y) = h(e(y)) + \sum_{k=1}^L g(p_k) +\sum_{k=1}^{L-1}\eta \times |t(p_k) + 1-s(p_{k+1})|$

4.使用基于短语的模型进行解码

我们现在描述基于短语的模型的解码算法：即，试图找到

$\begin{eqnarray*} \arg \max_{y\in \mathcal Y(x)} f(y) \tag 6 \end{eqnarray*}$

的算法。其中，假设$y=p_1p_2…p_L$，

$f(y) = h(e(y)) + \sum_{k=1}^L g(p_k) +\sum_{k=1}^{L-1}\eta \times |t(p_k) + 1-s(p_{k+1})|$

根据上述对$f(y)$的定义，公式$6$的问题是NP-hard；因此，我们描述的算法是一种近似算法，不能保证找到最优解。

算法中的第一个关键数据结构是状态。一个状态是一个元组

$(e_1,e_2,b,r,\alpha)$

其中$e_1,e_2$是英文单词，$b$是长度为$n$的位串（bit-string）（回想一下，$n$是源语言句子的长度），$r$是一个整数，指定状态中最后一个短语的终点位置，$\alpha$是状态的得分。

任何短语序列都可以映射到相应的状态。例如，序列

$y = \text{(1, 3, we must also), (7, 7, take), (4, 5, this criticism)}$

将被映射到状态

$(\text{this, criticism}, 1111101, 5, \alpha)$

状态记录了这一短语序列的翻译中的最后两个单词，即$\text{this}$和$\text{criticism}$。位串记录哪些单词已被翻译：如果第$i$个单词已被翻译，则位串中的第$i$位等于$1$，否则为$0$。在这种情况下，只有第$6$位是$0$，因为只有第$6$个单词没有被翻译。值$r = 5$表示序列中的最后一个短语$\text{(4, 5, this criticism)}$在第$5$位结束。最后，$\alpha $将是部分翻译的分数，计算如下：

$f(y) = h(e(y)) + \sum_{k=1}^L g(p_k) +\sum_{k=1}^{L-1}\eta \times |t(p_k) + 1-s(p_{k+1})|$

其中$L=3$，我们有

$e(y) =\text{we must also take this criticism}$

以及

$p_1 = (1, 3, \text{we must also}), p_2 = (7, 7, \text{take}), p_3 = (4, 5, \text{this criticism})$

请注意，状态仅记录衍生词中的最后两个单词：稍后将会看到，这是因为三元语言模型仅对序列中的最后两个单词敏感，因此状态仅需要记录最后两个单词。

我们将初始状态定义为

$q_0 = (*, *,0^n , 0,0)$

其中$0^n$是长度为$n$的位串，具有$n$个零。我们使用$\star$来引用语言模型中的特殊起始符号。初始状态没有单词被翻译（所有位都设置为$0$）；$r$的值为$0$；得分$\alpha $为$0$。

接下来，我们定义一个函数$\text{ph}(q)$，它将状态$q$映射到可以附加到$q$的短语集。对于$\text{ph}(q)$的短语成员$p$，其中$q=(e_1,e_2,b,r,\alpha)$，必须满足以下条件：

$p$不得与位串$b$重叠。即，对于$i\in \{ s(p)…t(p)\}$，我们必须具有$b_i =0$。
不得违反失真限制。更具体地说，我们必须拥有
$|r+1 -s(p)|\le d$
其中$d$是失真限制。

另外，对于任何状态$q$，对于任何短语$p\in \text{ph}(q)$，我们定义

$\text{next}(p, q)$

为通过将状态$q$与短语$p$组合形成的状态。形式上，如果$q=(e_1,e_2,b,r,\alpha)$，并且$p=(s,t,\epsilon_1…\epsilon_M)$，那么$\text{next}(p, q)$是状态$q’=(e’_1,e’_2,b’,r’,\alpha’)$，定义如下：

首先，为方便起见，定义$\epsilon_{-1}= e_1,\epsilon_0 = e_2$。
定义$e_1’=\epsilon_{M-1},e_2’ =\epsilon_M$。
对$i\in \{s…t\}$，定义$b_i’=1$。对$i\not\in \{s…t\}$，定义$b_i’ =b_i$。
定义$r’=t$。
定义
$\alpha' =\alpha+ g(p) + \sum_{i=1}^M \log q(\epsilon_{i}|\epsilon_{i-2},\epsilon_{i-1}) +\eta\times |r+1-s|$

因此，更新$e_1’$和$e_2’$被更新为记录将短语$p$附加到状态$q$而形成的翻译中的最后两个单词; $b’$是一个更新的位串，它被修改为记录单词$s…t$哪些已经翻译；$r’$简单地设置为$t$，即短语$p$的结束点；$\alpha’$是通过添加短语得分$g(p)$，语言模型对于单词$\epsilon_1…\epsilon_ M$的得分和失真项$\eta\times |r+1-s|$来计算的。

我们解码算法所需的最终函数是一个非常简单的函数，它测试两个状态的是否相等。函数

$\text{eq}(q,q')$

返回真或假。假设$q=(e_1,e_2,b,r,\alpha)$，并且$q’=(e’_1,e’_2,b’,r’,\alpha’)$，当且仅当$e_1=e_1’,e_2=e_2’,b=b’,r=’r$时$\text{eq}(q,q’)$为真。

定义了$\text{ph}$，$\text{next}$和$\text{eq}$函数后，我们现在准备提供完整的解码算法。图3给出了基本的解码算法。该算法对$i=0…n$操纵集合$Q_i$。每个集合$Q_i$包含一组与长度为$i$的翻译相对应的状态（状态$q$的长度是$q$的位串中的$1$的个数——即，该状态下被翻译的单词数量）。最初，我们将$Q_0$设置为包含单个状态，即初始状态$q_0$。我们设置所有其他集合$Q_i $为空集（$i=1…n $）。然后我们迭代：对于每个$i\in \{1,2…n\}$，我们考虑每个$q\in \text{beam}(Q_i)$（$\text{beam}(Q_i)$是$Q_i$的一个子集，只包含$Q_i$的最高得分元素：我们将很快给出一个正式的定义）。对于每个$q\in \text{beam}(Q_i)$，我们首先计算集合$\text{ph}(q )$；然后对于每个$p\in \text{ph}(q )$，我们计算下一个状态$q’=\text{next}(p, q)$。我们将这个新状态添加到集合$Q_j$，其中$j$是状态$q’$的长度。请注意，我们总是有$j>i$，因此我们总是将元素添加到比我们当前正在考虑的集合$Q_i $更先进的状态（即长度更长）。

图$4$给出了函数$\text{Add}(Q,q’,q,p)$的定义。函数首先检查$Q$中是否存在状态$q’’$，使得$\text{eq}(q’’,q’)$为真。如果是这种情况，那么如果$q’$的分数高于$q’’$，那么$q’$将替换$q’’$；否则$q’$不会被添加到$Q$。因此，状态$q’$和$q’’$中的只有一个保留在$Q$中。如果没有这样的状态$q’’$，则将$q’$简单地添加到$Q$。