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

×