Statistical Machine Translation：IBM Models 1 and 2

Introduction

这部分讲机器翻译，尤其是在统计机器翻译（SMT）系统上，此部分关注IBM翻译模型。这里以翻译法语(源语言)为英语(目标语言)为例，用\(f\)表示法语句子，即\(f_1,f_2...f_m\)，其中m为句子的长度；用e表示英语句子，即\(e_1,e_2...e_l\)，其中l表示英语句子的长度。用\((f^{(k)},e^{k})\)表示第k个法语句子和英语句子。

The Noisy-Channel Approach

IBM模型是一个噪声通道模型的例子，给出两个参数，用\(p(e)\)表示任意一个句子\(e_1,e_2...e_l\)在英语中的概率，用\(p(f|e)\)表示出现法语/英语对的概率，那么对于该模型，给定一个新的法语句子，其输出的结果是（即对应的英语句子）： \[ e^{*}=arg \,\, \max_{e \in E} \,\,p(e)p(f|e) \] 这个前面的章节中有讲到为什么，这里就直接用了。此时的重点在于如何定义模型\(p(f|e)\)，以及如何从训练集\((f^{(k)},e^{(k)}) \,\,for\,\,k=1...n\)中评估模型的参数？

The IBM Models

直接求解\(p(f_1...f_m|e_1...e_l,m)\)比较难，将其条件概率细化为\(p(f_1...f_m,a_1...a_m|e_1...e_l,m)\)，其中变量\(a_1...a_m\)的\(a_i \in \{0,0,...,l\}\)表示法语的第i个单词对应英语的某个单词，这样再回到原条件概率： \[ p(f_1...f_m|e_1...e_l)=\sum_{a_1=0}^{l}\sum_{a_2=0}^{l}...\sum_{a_m=0}^{l}p(f_1...f_m,a_1...a_m|e_1...e_l) \]

IBM Model2

用一个有限集\(\varepsilon\)表示英语单词集，用\(F\)表示法语集，用\(M\)和\(L\)分别表示法语的最大长度和英语的最大长度，下面给出两个参数：

• 一个是\(t(f|e)\)，表示从英语单词e生成法语单词f的条件概率，其中\(f \in F , e \in \varepsilon \cup \{NULL\}\)
• 一个是\(q(j|i,l,m)\)，表示在法语句子和英语句子长度分别为m和l的条件下，对齐变量\(a_i\)值为j的概率，其中\(l \in\{1...L\}，m \in \{1...M\}，i \in \{1...m\}，j \in \{0...l\}\) 前面讲到的条件概率有如下等价： \[ p(f_1...f_m,a_1...a_m|e_1...e_l,m)=\prod_{i=1}^mq(a_i|i,l,m)t(f_i|e_{a_i}) \]

此处定义\(e_0\)为NULL。 上式为什么就等价呢，下面用随机变量来讲解： 定义\(E_1...E_l\)为对应英语句子中单词的随机变量序列，L为英语句子长度的随机变量，\(F_1...F_m\)为法语单词的随机变量序列，M为法语句子长度的随机变量，\(A_1...A_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) \] 上式用条件概率展开如下： \[ 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)\cdot \\ 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) \] 上面两部分分别做如下两个假设：

1、 \[ 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) \] 2、 \[ 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}) \] 第二行假设随机变量\(F_i\)仅仅依赖于\(E_{ai}\) 【【此处假设有点强，Fi竟然和其它的法语变量没关系…有点不太懂？？？】】

Applying IBM Model 2

前面讲到了IBM Model 2 中的参数\(q(j|i,l,m)\)和\(t(f|e)\)，即我们知道了分布\(p(f,a|e)\)，而我们需要知道对于任意的\(f,a,e\)，得出如下分布： \[ p(f|e)=\sum_ap(f,a|e) \] 最后，假定我们已经估计了语言模型\(p(e)\)，那么我们对任意一个法语句子f的翻译结果就是： \[ arg\,\, \max_ep(e)p(f|e) \] IBM模型并不是一个好的翻译系统，但是仍然是一个关键的算法 ，这里说道的两种原因：\(t(f|e)\)被用到各种翻译系统，现代的翻译模型都是建立在IBM模型上的。 继续接上面最后的公式，对于由英语句子和法语句子对组成的训练集中，我们可以分析出一组对齐变量，使得下面的概率最大，也就是最符合的对齐变量： \[ arg \,\, \max_{a_1...a_l}p(a_1...a_m|f_1...f_m,e_1...e_l,m) \] 继而求解如下子问题： \[ a_i=arg\,\, \max_{j \in (0...l)}(q(j|i,l,m)t(f_i|e_j)) \]

Parameter Estimation

定义\(c(e,f)\)表示在训练集中单词e和单词l对齐的次数，\(c(e)\)表示e和任意一个法语单词对齐的次数，\(c(j|i,l,m)\)表示在看到长度为l的英语句子和长度为m的法语句子，且在看到单词i对应的是单词j的次数(就是\(a_i=j\)的次数)，\(c(i,l,m)\)表示长度为l的英语句子和长度为m的法语句子下标为i的个数。 上面的含义有点乱，而且下面给出的算法我也是看了好一会才理解什么意思，如下分别对全部语料库和部分语料库给出的算法，这里先分析对全部语料库的算法：

接上面定义的变量的含义，这里当\(a_i^{(k)}=j\)时，有\(\delta(k,i,j)=1\)，否则为0；算法中每次都会一起加1，看着值一样，其实是有区别的，这里我举个例子： 训练集中的数据为\(f^{(k)},e^{(k)},a^{(k)}\)拿书中的一个句子为例：

l=6,m=7
e= And the programma has been implemented
f= Le programme a ete mis en application
a={2,3,4,5,6,6,6}

这里\(c(e)\)就没什么好说的，就是统计如\(c(And),c(the)\)的个数，\(c(e,f)\)就是统计如\(c(the,Le)\)的个数，\(c(j|i,l,m)\)作如下解释，比如f中第一个单词Le对应e中第二个单词the，那么就将\(c(2|1,6,7)\)的值增加1，当然，对于\(c(the),c(the,Le),c(1,6,7)\)都会增加1，也就是说如果还有这样一个样本l=6，m=7，同时f中的第一个单词对应着e中第二个单词，那么\(c(2|1,6,7),c(1,6,7)\)也会增加1，但是\(c(the),c(the,Le)\)就不会增加了，这样就理解上面的算法了吧。接着看下面的算法：

观察两个算法的区别，主要在于\(\delta(k,i,j)=1\)计算不同，\(\delta(k,i,j)=1\)表示第k组平行预料（训练集中法文-英文句子）里的第i个法文词，第j个英文词。如果是上帝模式，那\(\delta(k,i,j)=1/0\)分别表示这两个词之间应当/不应当对齐，其问题在于我们不可能有全部语料库，也就是说等于1或者0，没有人能够知道，所以采用最大似然估计来估计（EM算法），于是就采用如下公式： \[ \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)})} \]

More on the EM Algorithm: Maximum-likelihood Estimation

这部分好像没什么用额，功力不够，就不写了

Initialzation using IBM Model 1

EM算法对IBM模型2的初始化敏感，依赖初始值(随机数)，这里使用IBM模型1，主要区别在于将模型2开始对\(q(j|i,l,m)\)的概率设为定值： \[ q(j|i,l,m)=\frac{1}{l+1} \] 注意这里的分母\(l+1\)表示的是j全部的取值个数，\(j \in \{0,1,...,l\}\)，这样做的意思就是说，在长度分别为l和m的英语句子和法语句子中，\(a_i\)对应j的关系是同概率的，没有什么相关性。 那么句子预测结果的概条件率公式可重写如下： \[ p(f_1...f_m,a_1...a_m|e_1...e_l,m)=\prod \frac{1}{l+1}t(f_i|e_{a_i})=\frac{1}{(1+l)^m}\prod_{i=1}^{m}t(f_i|e_{a_i}) \] EM算法重写如下： \[ \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)})} =\frac{t(f_i^{(k)}|e_j^{(k)}}{\sum_{j=0}^{l_k}t(f_i^{(k)}|e_j^{(k)})} \] 算法如下：