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)}\)拿书中的一个句子为例:

1
2
3
4
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)})} \] 算法如下:




评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×