Michael Collins NLP Lecture 7

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

课程网盘地址：

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

这一讲主要介绍了机器翻译。

Chapter 5 统计机器翻译：IBM模型1和2

1.介绍

接下来的几个课程讲座将侧重于机器翻译，特别是统计机器翻译（SMT）系统。在本讲义中，我们将重点介绍IBM翻译模型，这些模型可以追溯到20世纪80年代末/90年代初期。这些模型是开创性的，是当今使用的许多SMT模型的基础。

遵循惯例，我们将在整个讲义中假设任务是将法语（““源”语言）翻译成英语（“目标”语言）。一般来说，我们用$f$来表示法语句子：$f$是单词序列$f_1,f_2…f_m$，其中$m$是句子的长度，$f_j$表示句子中的第$j$个单词（$j\in \{1…m\}$）。我们用$e$来表示英文句子：$e$等于$e_1, e_2 …e_l$，其中$l$是英语句子的长度。

在SMT系统中，我们假设我们有一组样本翻译，$(f^{(k)},e^{(k)})$，$k=1…n$，其中$f^{(k)}$是训练样本中的第$k$个法语句子，$e^{(k)}$是第$k$个英语句子，并且$e^{(k)}$是$f^{(k)} $的翻译。每个$f^{(k)}$等于$f^{(k)}_1…f^{(k)}_{m_k}$，其中$m_k$是第$k$个法语句子的长度。每个$e^{(k)}$等于$e^{(k)}_1…e^{(k)}_{l_k}$，其中$l_k$是第$k$个英语句子的长度。我们将从这些训练样本中估计模型的参数。

那么我们从哪里获得训练样本？事实证明，很多语言对都有相当大的翻译样本。最初的IBM工作，实际上专注于从法语到英语的翻译，利用加拿大议会的会议记录（Hansards）：他们使用的语料库由数百万个翻译句子组成。 Europarl数据包括来自欧洲议会的会议记录，包括几种欧洲语言之间的翻译。其他语料库存在阿拉伯语——英语，中文——英文等翻译。

2.噪声通道方法

在几个讲座之前，我们介绍了生成模型，特别是噪声通道方法。IBM模型是噪声通道模型的实例，因此它们有两个组件：

一个语言模型，它用于为任何英语中的句子$e=e_1…e_l$指定概率$p(e)$。例如，我们将为模型的这一部分使用三元语言模型。可以从非常大量的英语数据中估计语言模型的参数。
一个翻译模型，它将条件概率$p(f|e)$分配给任何法语/英语句子。将根据翻译样本估计此模型的参数。该模型涉及两个选择，两个选择都以英语句子$e_1…e_l$为条件；首先选择法语句子的长度$m$；第二，选择$m$个单词$f_1…f_m$。

给定模型的这两个组件，遵循噪声通道方法中的常用方法，翻译模型对新法语句子$f$上的输出是：

$e^* =\arg \max_{e\in E} p(e) \times p(f|e)$

其中$E$是所有英语句子的集合。因此，可能的翻译$e$的得分是两个分数的乘积：第一，语言模型的分数$p(e)$，其给出了用英语表示句子的先验分布；第二，翻译模型的分数$p(f|e) $，表示我们将法语句子$f$视为$e$的翻译的可能性。

请注意，正如噪声通道模型中通常的那样，模型$p(f|e)$似乎也是“反向”（backwards）的：尽管我们正在构建从法语到英语的翻译模型，我们有一个$p(f|e)$模型。噪声通道方法使用了贝叶斯法则：

$p(e|f) =\frac{p(e)p(f|e)}{\sum_e p(e)p(f|e)}$

因此

$\begin{aligned} \arg\max_{e\in E} p(e|f) &=\arg\max_{e\in E} \frac{p(e)p(f|e)}{\sum_e p(e)p(f|e)}\\ &=\arg\max_{e\in E}p(e)p(f|e) \end{aligned}$

噪声通道方法的一个主要好处是它允许我们使用语言模型$p(e)$。这对于提高翻译模型输出的流畅性或语法性非常有用。

本讲义的其余部分将重点关注以下问题：

我们如何定义翻译模型$p(f|e)$？
如何从训练样本$(f^{(k)}, e^{(k)})$中估计的翻译模型的参数$(k=1…n)$？

我们将针对此问题描述IBM模型（特别是IBM模型1和2）。IBM模型是SMT的早期方法，现在没有被广泛用于翻译：改进的模型（我们将在下一讲中介绍）已经在最近的工作中得到。但是，它们（IBM模型）对我们非常有用，原因如下：

模型直接使用对齐（alignment）的概念，因此我们可以恢复训练数据中法语和英语单词之间的对齐。由此产生的对齐模型在现代SMT系统中至关重要。
将使用期望最大化（EM）算法估计IBM模型的参数。EM算法被广泛用于NLP和其他问题域的统计模型。我们将在课程后期深入研究它：我们使用此处描述的IBM模型作为该算法的第一个示例。

3.IBM模型

3.1 对齐（Alignments）

我们现在转向为任何法语句子建立条件概率$p(f|e ) $的问题，其中法语句子$f=f_1…f_m$与英语句子$e=e_1…e_l$组成一对。
回想一下$p(f|e) $涉及两个选择：第一，选择法语句子的长度$m$；第二，选择单词$f_1…f_m$。我们将假设存在某个分布$p(m|l)$，该分布对法语句子长度关于英语句子长度的条件分布建模。从现在开始，我们将长度$m$固定，我们的重点将放在对如下分布的建模上

$p(f_1...f_m| e_1...e_l,m)$

即，单词$f_1…f_m$关于英语字符串$e_1…e_l$以及法语句子长度$m$的条件概率。

直接模拟$p(f_1…f_m| e_1…e_l,m)$是非常困难的。IBM模型的一个中心思想是为问题引入额外的对齐变量。我们将有对齐变量$a_1…a_m$——也就是说，为句子中每个法语单词指定一个对齐变量——其中每个对齐变量可以取$\{0,1,…,l\}$中的任何值。对齐变量将指定每个法语单词与英语句子中某个单词的对齐。

我们不是试图直接定义$p(f_1…f_m| e_1…e_l,m)$，而是关于法语句子$f_1…f_m$以及对其变量$a_1…a_m$定义一个条件分布

$p(f_1...f_m,a_l...a_m| e_1...e_l,m)$

定义了这个模型后，我们可以通过对齐变量求和来计算$p(f_1…f_m| e_1…e_l,m)$（“边缘化”对齐变量）：

$p(f_1...f_m| e_1...e_l,m) = \sum_{a_1=0}^ l \sum_{a_2=0}^ l \sum_{a_3=0}^ l... \sum_{a_m=0}^ l p(f_1...f_m,a_l...a_m| e_1...e_l,m)$

我们现在详细描述对齐变量。每个对齐变量$a_j$指定法语单词$f_j$与英语单词$e_{a_j}$对齐：我们将很快直观地看到，在概率模型中，单词$f_j$将从英语单词$e_{a_j}$生成。我们将$e_0$定义为一个特殊的单词$\text{NULL}$；所以$a_j =0$指定从单词$\text{NULL}$生成的单词$f_j $。我们将在描述概率模型时看到$\text{NULL}$符号所扮演的角色。

作为一个例子，考虑$l=6,m=7$以及

$\begin{aligned} e &=\text{And the programme has been implemented}\\ f&= \text{Le programme a ete mis en application} \end{aligned}$

在这种情况下，法语句子的长度$m$等于$7$；因此我们有对齐变量$a_1,a_2,…,a_7$。作为一个对齐（这是非常合理的），我们有

$a_1,a_2,...,a_7 = \langle 2,3,4,5,6,6,6 \rangle$

指定以下对齐方式：

$\begin{aligned} \text{Le} &\Rightarrow \text{the} \\ \text{Programme} &\Rightarrow \text{program} \\ \text{a} &\Rightarrow \text{has} \\ \text{ete} &\Rightarrow \text{been}\\ \text{mis} &\Rightarrow \text{implemented}\\ \text{en} &\Rightarrow \text{implemented}\\ \text{application} &\Rightarrow \text{implemented}\\ \end{aligned}$

请注意，每个法语单词都与一个英语单词对齐。对齐是多对一的：可以将多个法语单词与一个英语单词对齐（例如，mis，en和application都与implemented对齐）。某些英语单词可能不与法语单词对齐：例如单词And与此示例中的任何法语单词都不对齐。

还要注意，该模型是不对称的，因为没有约束条件规定每个英语单词恰好与一个法语单词对齐：每个英语单词可以与任何数字（零个或多个）法语单词对齐。我们稍后会回到这一点。

作为另一个对齐示例，我们有

$a_1,a_2,...,a_7 = \langle 1,1,1,1,1,1,1 \rangle$

指定以下对齐方式：

$\begin{aligned} \text{Le} &\Rightarrow \text{And} \\ \text{Programme} &\Rightarrow \text{And} \\ \text{a} &\Rightarrow \text{And} \\ \text{ete} &\Rightarrow \text{And}\\ \text{mis} &\Rightarrow \text{And}\\ \text{en} &\Rightarrow \text{And}\\ \text{application} &\Rightarrow \text{And}\\ \end{aligned}$

对于这个例子，这显然不是一个好的对齐方式。

3.2 对齐模型：IBM模型2

我们现在描述如下条件概率的模型

$p(f_1...f_m,a_l...a_m| e_1...e_l,m)$

我们描述的模型通常被称为IBM模型2：我们将使用IBM-M2作为此模型的简写。稍后我们将描述IBM模型1是IBM模型2的特例。模型的定义如下：

定义 1（IBM模型2）

IBM-M2模型由英语单词的有限集合$\mathcal E$，法语单词集合$\mathcal F$，以及指定法语和英语句子的最大长度的整数$M$和$L$组成。该模型的参数如下：

$t(f|e)$，对任何$f\in \mathcal F,e \in \mathcal E \cup \{\text{NULL}\}$。参数$t(f|e)$可以解释为由英语单词$e$生成法语单词$f$的条件概率。
$q(j|i,l,m)$对于任何$l\in \{1…L\},m\in \{1…M\}, i \in \{1…m\},j \in \{0…l\}$。参数$q(j|i,l,m)$可以解释为给定英语和法语句子的长度$l$和$m$，对齐变量$a_i$取值$j$的概率。

给定这些定义，对于任何英语句子$e_1…e_l$，其中每个$e_j \in \mathcal E$，对于每个长度$m$，我们定义关于法语句子$f_1…f_m$以及对其变量$a_1…a_m$的条件概率为

$p(f_1...f_m,a_l...a_m| e_1...e_l,m) =\prod_{i=1}^m q(a_i|i,l,m)t(f_i|e_{a_i})$

这里我们定义$e_0$为单词$\text{NULL}$。

为了说明这个定义，考虑前面的例子，其中$l=6,m=7$以及

$\begin{aligned} e &=\text{And the programme has been implemented}\\ f&= \text{Le programme a ete mis en application} \end{aligned}$

对齐变量为

$a_1,a_2,...,a_7 = \langle 2,3,4,5,6,6,6 \rangle$

指定以下对齐方式：

在这个情形下，我们有

$\begin{aligned} &p(f_1...f_m,a_l...a_m| e_1...e_l,m) \\ =& q(2|1,6,7)\times t(\text{Le}|\text{the}) \\ &\times q(3|2,6,7)\times t(\text{programme}|\text{program})\\ &\times q(4|3,6,7)\times t(\text{a}|\text{has})\\ &\times q(5|4,6,7)\times t(\text{ete}|\text{been})\\ &\times q(6|5,6,7)\times t(\text{mis}|\text{implemented})\\ &\times q(6|6,6,7)\times t(\text{en}|\text{implemented})\\ &\times q(6|7,6,7)\times t(\text{application}|\text{implemented})\\ \end{aligned}$

因此，每个法语单词都有两个相关项：第一，选择对齐变量，指定单词与哪个英语单词对齐；第二，根据步骤1中选择的英语单词选择法语单词。例如，对于$f_5=\text{mis}$，我们首先选择$a_5 = 6$，概率为$q(6|5,6,7)$，然后选择单词$\text{mis}$，基于英语单词$e_6 =\text{implemented}$，概率为$t(\text{mis}|\text{implemented})$。
注意，对齐参数$q(j|i,l,m)$对每个三元组$i,j,m$指定不同的分布$\langle q(0|i,l,m) ,q(1|i,l,m)…q(l|i,l,m)\rangle$，其中$i$是法语句子中的位置，$l$是英语句子的长度，$m$是法语句子的长度。例如，这将使我们能够捕捉到接近法语句子开头的单词倾向于接近英语句子开头的单词的翻译。

这个模型当然相当简单和朴素。但是，它捕获了数据的一些重要方面。

3.3 IBM模型2中的独立假设

我们现在考虑IBM模型2的独立假设。将$L$作为与英语句子长度相对应的随机变量；$E_1…E_l$是与英语句子中的单词对应的随机变量序列；$M$是对应于法语句子长度的随机变量；$F_1…F_m$和$A_1…A_m$是法语m单词序列和对齐变量。我们的目标是建立一个模型

$P(F_1=f_1...F_m=f_m,A_1=a_1...A_m=a_m| E_1=e_1...E_l = e_l,L=l,M=m)$

作为第一步，我们可以使用概率的链式法则将其分解为两项：

$\begin{aligned} &P(F_1=f_1...F_m=f_m,A_1=a_1...A_m=a_m| E_1=e_1...E_l = e_l,L=l,M=m) \\ =& P(A_1=a_1...A_m=a_m| E_1=e_1...E_l = e_l,L=l,M=m) \\ &\times P(F_1=f_1...F_m=f_m|A_1=a_1...A_m=a_m, E_1=e_1...E_l = e_l,L=l,M=m) \end{aligned}$

我们现在将分别考虑这两项。
首先，我们做出以下独立假设：

$\begin{aligned} &P(A_1=a_1...A_m=a_m| E_1=e_1...E_l = e_l,L=l,M=m) \\ =&\prod_{i=1}^m P(A_i=a_i| A_1=a_1...A_{i-1}=a_{i-1},E_1=e_1...E_l = e_l,L=l,M=m) \\ =&\prod_{i=1}^m P(A_i =a_i|L=l,M=m) \end{aligned}$

第一个等号是由概率的链式法则。第二个等号对应于一个非常强的独立性假设：即，随机变量$A_i$的分布仅取决于随机变量$L$和$M$的值（它独立于英语单词$E_1…E_l $，以及其他对齐变量）。最后，我们假设

$P(A_i =a_i|L=l,M=m) =q(a_i|i,l,m)$

其中每个$q(a_i|i,l,m)$是我们模型的参数。

接着，我们做出以下假设：

$\begin{aligned} &P(F_1=f_1...F_m=f_m|A_1=a_1...A_m=a_m, E_1=e_1...E_l = e_l,L=l,M=m) \\ =& \prod_{i=1}^m P(F_i=f_i|F_1=f_1...F_{i-1}=f_{i-1},A_1=a_1...A_m=a_m, E_1=e_1...E_l = e_l,L=l,M=m) \\ =&\prod_{i=1}^m P(F_i=f_i|E_{a_i} =e_{a_i}) \end{aligned}$

第一个等号是由概率的链式法则。在第二步中，我们假设$F_i$的值仅取决于$E_{a_i}$：即，取决于$F_i $对齐的英语单词的标识。最后，我们假设对于所有$i$，

$P(F_i=f_i|E_{a_i} =e_{a_i}) = t(f_i|e_{a_i})$

其中每个$ t(f_i|e_{a_i})$是我们模型的参数。

4.应用IBM模型2

下一节将介绍IBM模型2的参数估计算法。在此之前，我们首先考虑一个重要问题：IBM模型2什么有用？

最初的动机是完整的机器翻译问题。一旦我们从数据中估计了参数$q(j|i,l,m)$和$t(f|e)$，我们就得到了一个关于语法句子$f$，对齐序列$a$和英语句子$e$的分布

$p(f,a|e)$

从这里我们可以得到一个分布

$p(f|e) = \sum_{a}p(f,a|e)$

最后，假设我们有一个语言模型$p(e )$，我们可以定义任何法语句子$f$的翻译为

$\begin{eqnarray*} \arg \max_e p(e) p(f|e) \tag {1} \end{eqnarray*}$

其中$\arg\max$作用于所有可能的英语句子。在公式1中找到$\arg\max$的问题通常被称为解码问题。解决解码问题是计算上非常困难的问题，但是已经导出了各种近似方法。
但实际上，IBM模型2并不是一个特别好的翻译模型。在后面的讲座中，我们将看到远远更有效的模型。

然而，IBM模型在现代翻译系统中仍然至关重要，原因有两个：

词汇概率$t(f|e) $直接用于各种翻译系统。
最重要的是，使用IBM模型得出的对齐直接用于构建现代翻译系统。

让我们更详细地考虑第二点。假设我们已经从训练语料库中估计了我们的参数$t(f|e )$和$q(j|i,l,m)$（使用下一节中描述的参数估计算法）。给定任何由英语句子$e$与配对的法语句子$f$组成的训练样本，我们可以在模型下找到最可能的对齐：

$\begin{eqnarray*} \arg \max_{a_1...a_m} p(a_1...a_m|f_1...f_m, e_1...e_l,m) \tag 2 \end{eqnarray*}$

因为模型采用简单的形式，所以找到公式2的解很简单。事实上，一个简单的推导表明我们只是对$i=1…m$定义

$a_i =\arg \max_{j\in \{0...l\}} (q(j|i,l,m)\times t(f_i|e_j))$

因此，对于每个法语单词$i$，我们简单地将其与英语位置$j$对齐，这使得两项的乘积最大化：第一，对齐概率$q(j|i,l,m)$; 第二，翻译概率$t(f_i|e_j)$。

5.参数估计

本节描述了从翻译数据估计参数$t(f|e)$和$q(j|i,l,m)$的方法。我们考虑两种情况：第一种是用完全观察到的数据估计；第二种是用部分观察到的数据估计。第一种情况是不现实的，但在我们进入第二种更现实的情况之前，这将是一次有用的热身。

5.1 具有完全观测数据的参数估计

我们现在转向以下问题：我们如何估计模型的参数$t(f|e)$和$q(j|i,l,m)$？我们假设有一个训练语料库，其中翻译为$\{f^{(k)},e^{(k)}\}_{k=1}^n$。但请注意，此数据中缺少一条关键信息：我们不知道每个训练样本的潜在的对齐方式。在这个意义上，我们将说数据只是部分观察到的，因为缺少一些信息——即每个句子的对齐。因此，我们经常将对齐变量称为隐藏变量。尽管存在隐藏变量，我们将看到我们实际上可以估计模型的参数。
请注意，我们可能会雇佣人来给数据加上潜在的对齐（以类似的方式雇佣人来注释潜在的解析树，以形成树库资源）。但是，我们希望避免这种情况，因为对齐的手动注释将是一项昂贵的任务，合理大小的翻译语料库就需要花费大量时间来进行——而且，每次我们收集新的语料库时，我们都必须以这种方式对其进行注释。

在本节中，作为部分观测数据情况的预热，我们将考虑完全观测数据的情况，其中每个训练样本实际上确实包含三元组$(f^{(k)},e^{(k)},a^{(k)})$，其中$f^{(k)}=f^{(k)}_1….f^{(k)}_{m_k}$是法语句子，$e^{(k)}=e^{(k)}_1…e^{(k)}_{l_k}$是英语句子，$a^{(k)}=a^{(k)}_1…a^{(k)}_{m_k}$是对齐变量。解决这种情况将有助于开发部分观测数据的算法。

完全观测到的数据的估计很容易推导出来。将$c(e,f)$定义为单词$e$与训练数据中的单词$f$对齐的次数，$c(e)$是$e$与任何法语单词对齐的次数。另外，将$c(j|i,l,m)$定义为我们同时看到长度为$l$的英语句子以及长度为$m$的法语句子的次数，其中法语中的单词$i$与英语中的单词$j$对齐。最后，将$c(i,l,m)$定义为我们同时看到长度为$l$的英语句子和长度为$m$的法语句子的次数。那么最大似然估计是

$\begin{aligned} t_{ML}(f|e) &=\frac{c(e,f)}{c(e)} \\ q_{ML}(j|i,l,m)& = \frac{c(j|i,l,m)}{c(i,l,m)} \end{aligned}$

因此，为了估计参数，我们只需从训练语料库中统计计数，然后获取这些计数的比值。
图1显示了使用完全观测到的数据进行参数估计的算法。部分观测数据的算法将是该算法的直接修改。算法考虑语料库中所有可能对齐的法语/英语单词对：即所有可能的$(k,i,j)$元组，其中$k\in \{1…n\},i\in \{1…m_k\},j\in\{0…l_k\}$。对于每对单词，如果两个单词对齐，我们有$a_i^{(k)}=j$。在这种情况下，我们增加相关的计数$c(e,f),c(e),c(j|i,l,m),c(i,l,m)$。如果$a_i^{(k)}\neq j$，那么这两个单词不对齐，计数不增加。

5.2 部分观测数据的参数估计

我们现在考虑部分观测数据的情况，其中在训练语料库中没有观察到对齐变量$a^{(k)}$。这种情况的算法如图2所示。该算法与图1中的算法有两个重要区别：

该算法是迭代的。我们从参数$t$和$q$的一些初始值开始：例如，我们可以将它们初始化为随机值。在每次迭代时，我们首先根据数据和我们当前的参数估计值计算一些“计数”$c(e,f),c(e),c(j|i,l,m),c(i,l,m)$。然后我们使用这些计数重新估计参数，并迭代。
使用与图1中相似的定义计算计数，但有一个关键的区别：不是定义
$\delta(k,i,j)=\begin{cases} 1 & a_i^{(k)}=j\\ 0& 其他 \end{cases}$
我们使用如下定义
$\delta(k,i,j) =\frac{q(j|i,l_k,m_k)t(f_i^{(k)}|e_j^{(k)})} {\sum_{j=0}^{l_k}q(j|i,l_k,m_k)t(f_i^{(k)}|e_j^{(k)})}$
其中$q$和$t$是我们当前的参数估计值。

让我们更详细地考虑这个最后的定义。事实上，我们可以得到如下等式：

$P(A_i=j|e_1...e_l, f_1...f_m,m)=\frac{q(j|i,l_k,m_k)t(f_i|e_j)} {\sum_{j=0}^{l_k}q(j|i,l_k,m_k)t(f_i|e_j)}$

其中$P(A_i=j|e_1…e_l, f_1…f_m,m)$是在当前模型参数下对齐变量$a_i$取值$j$的条件概率。因此，我们使用当前的参数估计有效地填充了对齐变量。这与完全观测到的情况形成对比，其中我们可以简单地定义$\delta(k,i,j) 1=$如果$a_i^{(k)}=j$，否则为$0$。

作为一个例子，其中$l=6,m=7$以及

$\begin{aligned} e &=\text{And the programme has been implemented}\\ f&= \text{Le programme a ete mis en application} \end{aligned}$

此例子中$\delta(k,5,6)$的值将是当前模型对单词$f_5$与单词$e_6$对齐的概率的估计。它的计算方法是

$\frac{q(6|5,6,7)t(\text{mis}|\text{implemented})} {\sum_{j=0}^{6}q(j|5,6,7)t(\text{mis}|e_j)}$

因此，分子将翻译参数$t(\text{mis}|\text{implemented}) $与对齐参数$q(6|5,6,7)$一起考虑在内; 分母为关于每个英语单词求和。

图2中的算法是期望最大化（EM）算法的实例。在部分观测数据的情况下，EM算法被广泛用于参数估计。 $c(e),c(e,f)$计数等被称为期望计数，因为它们是由如下分布定义的有效期望计数

$p(a_1...a_m|f_1...f_m, e_1...e_l,m)$

在每次迭代的第一步中，我们计算模型下的期望计数。在第二步中，我们使用这些预期计数来重新估计参数$t$和$q$。我们迭代这个两步，直到参数收敛（这通常几次迭代后就会发生）。

6. 有关EM算法的更多信息：最大似然估计

很快我们将在一些简单数据上跟踪EM算法的运行。但首先，我们将考虑以下问题：我们如何证明算法的合理性？它的正式保证是什么，它优化的函数是什么？
在本节中，我们将描述EM算法如何尝试查找数据的最大似然估计。为此，我们需要引入一些符号，特别是，我们需要仔细指定IBM模型2的最大似然估计的确切含义。
首先，考虑模型的参数。有两种类型的参数：翻译参数$t(f|e)$和对齐参数$q(j|i,l,m)$。我们将使用$t$来代表翻译参数的向量，

$t=\{t(f|e): f\in F,e\in E\bigcup \{\text{NULL}\}\}$

$q$代表对齐参数的向量

$q=\{q(j|i,l,m): l\in \{1...L\}, m\in \{1...M\}, j\in \{0...l\}, i\in \{1...m\} \}$

我们将使用$\mathcal T$来代表翻译参数的参数空间——即翻译参数的有效集合，定义如下：

$\mathcal T = \{ t:\forall e,t, t(f|e)\ge 0; \forall e\in E\bigcup \{\text{NULL}\}, \sum_{f\in F} t(f|e)=1 \}$

我们将使用$\mathcal Q$来代表对齐参数的参数空间，

$\mathcal Q=\{ q:\forall j,i,l,m,q(j|i,l,m)\ge 0; \forall i,l,m,\sum_{j=0}^l q(j|i,l,m)=1 \}$

接下来，考虑模型的概率分布。这取决于参数集$t$和$q$。我们将引入使这种依赖显式化的符号。我们将

$p(f,a|e,m;t,q) = \prod_{i=1}^m q(a_i |i,l,m)t(f_i|e_{a_i})$

作为法语句子$f_1…f_m $，带有对齐变量$a_1…a_m $，关于英语句子$e_1…e_l $和法语句子长度$m$的条件概率。函数$p(f,a|e,m;t,q)$随着参数向量$t$和$q$的变化而变化，并且我们通过在该表达式中的“;”之后包括$t$和$q$来明确这种依赖性。

如前所述，我们还有以下分布：

$p(f|e,m;t,q) =\sum_{a\in \mathcal A(l,m)} p(f,a|e,m;t,q)$

其中$\mathcal A(l,m)$是对齐变量的所有可能的集合，假设英语句子的长度为$l$，而法语句子的长度为$m$：

$\mathcal A(l,m) = \{ (a_1...a_m); a_j \in \{0...l\},j=1...m \}$

所以$p(f|e,m;t,q)$是法语句子$f$关于以$e$和$m$的条件概率，其中参数为$t$和$q$。

现在考虑参数估计问题。我们有以下假定：

参数估计算法的输入是一组训练样本，$(f^{(k)},e^{(k)}),k=1…n$。
参数估计算法的输出是一对参数向量$t\in \mathcal T,q\in \mathcal Q$。

那么我们应该如何选择参数$t$和$q$？我们首先考虑单个训练样本，$(f^{(k)},e^{(k)})$，对于某个$k\in \{1…n\}$。对于任何参数$t$和$q$，我们可以考虑如下概率

$p(f^{(k)} |e^{(k)},m_k;t,q)$

当我们改变参数$t$和$q$时，这个概率会变化。直观地说，一个好的模型会使这个概率尽可能高。

现在考虑整个训练样本。对于任何参数$t,q$，我们可以计算整个训练样本的概率，如下：

$\prod_{k=1}^n p(f^{(k)} |e^{(k)},m_k;t,q)$

同样，这个概率随着参数$t$和$q$的变化而变化；直觉上，我们想选择参数$t$和$q$，使这个概率尽可能高。这导致以下定义：

定义 2 （IBM模型2的最大似然估计（ML））

IBM模型2的最大似然估计为

$(t_{ML},q_{ML}) = \arg \max_{t\in \mathcal T, q\in \mathcal Q} L(t,q)$

其中

$\begin{aligned} L(t,q) & = \log \Big( \prod_{k=1}^n p(f^{(k)} |e^{(k)},m_k;t,q)\Big)\\ &=\sum_{k=1}^n \log p(f^{(k)} |e^{(k)},m_k;t,q)\\ &=\sum_{k=1}^n \log \sum_{a\in \mathcal A(l_k,m_k)} p(f^{(k)},a |e^{(k)},m_k;t,q) \end{aligned}$

我们将函数$L(t,q)$称为对数似然函数。

根据这个定义，ML估计被定义为最大化函数的量

$\log \Big( \prod_{k=1}^n p(f^{(k)} |e^{(k)},m_k;t,q)\Big)$

注意到这等价于最大化

$\prod_{k=1}^n p(f^{(k)} |e^{(k)},m_k;t,q)$

我们现在考虑正在优化的函数$L(t,q) $。这实际上是一个难以处理的函数：首先，该优化问题没有解析解

$\begin{eqnarray*} (t,q) =\arg \max_{t\in \mathcal T, q\in \mathcal Q} L(t,q) \tag 3 \end{eqnarray*}$

通过解析解，我们指的是一种简单的封闭形式的解。作为解析解的一个例子，在语言建模中，我们发现三元参数的最大似然估计是

$q_{ML}(w|u,v) =\frac{\text{Count}(u,v,w)}{\text{Count}(u,v)}$

遗憾的是，最大化公式3的参数没有类似的简单表达式。

第二个困难是$L(t,q)$不是凸函数。图3展示了$x$是标量值（与向量相对）的函数$f(x)$的简单情况下凸函数和非凸函数的示例，其中。凸函数具有单一的全局最优，并且直观地，简单的爬山算法将爬到这一点。相比之下，图3中的第二个函数具有多个“局部”最优，并且直观地，爬山过程可能陷入局部最优，这不是全局最优。

凸函数和非凸函数的正式定义超出了本讲义的范围。然而，简而言之，有许多结果表明凸函数“易于”优化（即，我们可以设计找到$\arg\max$的有效算法），而非凸函数通常更难处理（即，我们可以经常表明，找到$\arg\max$在计算上很难，例如它通常是NP难的）。在许多情况下，我们所希望的最好情形的是优化方法找到非凸函数的局部最优。
实际上，这正是模型2的EM算法的情况。它具有以下保证：

定理 1 （IBM模型2的EM算法的收敛性）

我们使用$t^{(s)}$和$q^{(s)}$来指代EM算法的$s$次迭代之后的参数估计，并且$t^{(0)}$和$q^{(0)}$来指代初始参数估计。那么对于任何$s\ge 1$，我们都有

$\begin{eqnarray*} L(t^{(s)},q^{(s)})\ge L(t^{(s-1)},q^{(s-1)}) \tag 4 \end{eqnarray*}$

此外，在温和的条件下，当$s\to \infty$，参数估计$(t^{(s)},q^{(s)})$收敛于对数似然函数的局部最优值。

在本课程的后面部分，我们将更详细地考虑EM算法：我们将展示它可以应用于NLP中的各种模型，我们将更详细地描述它的理论属性。目前，这种收敛定理是算法最重要的属性。
公式4指出对数似然是严格不递减的：在EM算法的每次迭代中，它不会减少。然而，这并不排除相当无趣的情况，例如对所有$s$

$L(t^{(s)},q^{(s)})= L(t^{(s-1)},q^{(s-1)})$

第二个条件表明该方法实际上收敛于对数似然函数的局部最优。
该结论的一个重要结果如下：IBM模型2的EM算法可以收敛到不同的参数估计，这取决于初始参数值$t^{(0)}$和$q^{(0)}$。这是因为算法可以根据其初始点收敛到不同的局部最优值。实际上，这意味着在初始化中经常需要注意（即，选择初始参数值）。

7.使用IBM Model 1进行初始化

如前一节所述，IBM模型2的EM算法可能对初始值敏感：根据初始值，它可能会收敛到对数似然函数的不同局部最优值。
因此，在实际中，选择良好的参数初始化是很重要的。一种非常常见的方法是使用IBM模型1。我们将在本节中描述IBM模型1和基于IBM模型1的初始化方法。
回想一下，在IBM模型2中，我们有参数

$q(j|i,l,m)$

这被解释为法语单词$f_i$与英语单词$e_j$对齐的条件概率，给定法语长度$m$和英语长度$l$。在IBM模型1中，我们简单地假设对于所有$i,j,l,m$，

$q(j|i,l,m) =\frac 1 {l+1}$

因此，在所有$l + 1$个可能的英语单词上存在均匀概率分布（回想起英语句子是$e_1…e_l$，并且还有可能$j=0$，表明法语单词与$e_0 =\text{NULL}$对齐）。这导致以下定义：

定义 3（IBM模型1）

IBM-M1模型由英语单词的有限集合$\mathcal E$，法语单词集合$\mathcal F$，以及指定法语和英语句子的最大长度的整数$M$和$L$组成。该模型的参数如下：

$t(f|e)$，对任何$f\in \mathcal F,e \in \mathcal E \cup \{\text{NULL}\}$。参数$t(f|e)$可以解释为由英语单词$e$生成法语单词$f$的条件概率。

$p(f_1...f_m,a_l...a_m| e_1...e_l,m) =\prod_{i=1}^m \frac 1 {(l+1)}t(f_i|e_{a_i}) =\frac 1 {(l+1)^m }\prod_{i=1}^m t(f_i|e_{a_i})$

这里我们定义$e_0$为单词$\text{NULL}$。

可以使用EM算法估计IBM模型1的参数，该算法与IBM模型2的算法非常相似。算法如图4所示。对IBM模型2算法的唯一变化来自更换

$\delta(k,i,j) =\frac{q(j|i,l_k,m_k)t(f_i^{(k)}|e_j^{(k)})} {\sum_{j=0}^{l_k}q(j|i,l_k,m_k)t(f_i^{(k)}|e_j^{(k)})}$

为

$\delta(k,i,j) =\frac{\frac 1{(l^{(k)}+1)}t(f_i^{(k)}|e_j^{(k)})} {\sum_{j=0}^{l_k}\frac 1{(l^{(k)}+1)}t(f_i^{(k)}|e_j^{(k)})} = \frac{t(f_i^{(k)}|e_j^{(k)})} {\sum_{j=0}^{l_k}t(f_i^{(k)}|e_j^{(k)})}$

反映了我们在模型1中有

$q(j|i,l_k,m_k) =\frac 1{(l^{(k)}+1)}$

IBM模型1的一个关键性质如下：

命题 1

在温和的条件下，图4中的EM算法收敛于IBM模型1下的对数似然函数的全局最优解。

因此，对于IBM模型1，我们可以保证收敛到对数似然函数的全局最优解。因此，无论如何初始化，EM算法都会收敛到相同的值。这表明了以下用于训练IBM模型2参数的过程：

使用图4中的算法，使用IBM模型1的EM算法估算参数$t$。
使用图2中的算法估算IBM模型2的参数。要初始化此模型，请使用：
- 1）在IBM模型1中步骤1中估计的参数$t(f|e)$来初始化参数$t$。
- 2）随机值来初始化$q(j|i,l,m)$。

直观地说，如果IBM模型1得到对参数$t$的合理估计，则该方法通常应该对IBM模型2执行得更好。实际上通常就是这种情况。

本讲测验题

Coursera部分

1.

因为

$l = 5,m=3$

所以结果为

$(l+1)^m=6^3$

选c

2.

注意

$l=3,m=3$

所以由公式可得

$p(a | e, m)=\frac{1}{(l+1)^{m}}=\frac 1 {64}$

3.

注意公式

$p(f | a, e, m)=\prod_{j=1}^{m} t\left(f_{j} | e_{a_{j}}\right)$

所以

$\begin{aligned} p(f | a, e, m) &=t(\text { abarks } | \text { barks }) \times t(\operatorname{adog} | \operatorname{dog}) \times t(\text { athe } | \text { the })\\ &=0.1\times 0.2\times 0.5\\ &=0.01 \end{aligned}$

4.

$\begin{aligned} p(a | e, m) &=\prod_{j=1}^{m} q\left(a_{j} | j, l, m\right)\\ &= q\left(3 | 1, 3, 3\right) \times q\left(2 | 2, 3, 3\right) \times \times q\left(1 | 3, 3, 3\right)\\ &=0.6\times 0.9\times 0.2\\ &=0.108 \end{aligned}$

5.

$\begin{aligned} q(0 | 1,3,3) \times t\left(f_{1} | e_{0}\right)&=0.1\times 0.1=0.01\\ q(1 | 1,3,3) \times t\left(f_{1} | e_{1}\right)&=0.4\times 0.2=0.08\\ q(2 | 1,3,3) \times t\left(f_{1} | e_{2}\right)&=0.2\times 0.5=0.1\\ q(3 | 1,3,3) \times t\left(f_{1} | e_{3}\right)&=0.3\times 0.2=0.06 \end{aligned}$

所以

$a_{1}^{*}=2$

6.

$\begin{aligned} t_{\mathrm{ML}}(\mathrm{Le} | \text {the})&=\frac{1}{1}=1 \\ t_{\mathrm{ML}}(\mathrm{Le} | \mathrm{And})&=\frac 0 1 = 0 \\ t_{\mathrm{ML}}(\text {mis } | \text { implemented})&=\frac {1}{3}=0.333 \\ t_{\mathrm{ML}}(\mathrm{en} | \text { implemented})&= \frac 13 =0.333\\ t_{\mathrm{ML}}(\text {application } | \text { implemented})&=\frac 1 3 =0.333\\ t_{\mathrm{ML}}(\text {application } | \mathrm{NULL})&=\frac 0 1 =0 \end{aligned}$

7.

$\begin{aligned} \delta(1, 1, 3)&=\frac{q\left(3 | 1, l_{1}, m_{1}\right) t\left(f_{1}^{(1)} | e_{3}^{(1)}\right)}{\sum_{j=0}^{l_{k}} q\left(j | i, l_{k}, m_{k}\right) t\left(f_{i}^{(k)} | e_{j}^{(k)}\right)}\\ &=\frac{0.1\times 0.3}{0.1\times 0.2+0.4\times 0.1 + 0.4\times 0.4+0.1\times 0.3}\\ &=0.12 \end{aligned}$