Tag: 统计

统计翻译模型的基本思想是对大量平行(parallel)语料进行统计分析。之前实习的时候有幸接触到一些简单的模型，而事实上这种简单的模型在大量数据训练的基础上，发挥还是挺不错的。
IBM的统计翻译模型从简单到繁琐，一共有Model1-Model5五个模型，全都是基于词的统计模型。
本文只对Model1作简单介绍，方便起见，文中以将法文(French)翻译为英文(English)为例。

噪声信道模型。机器翻译=翻译模型+语言模型

模型假定源语言中的（法语）句子是由目标语言（英语）经过含有噪声的信道编码后得到的。寻找最佳的英文翻译结果等同于寻找[latex]\arg\max_{e}p(e|f)[/latex]。
根据贝叶斯公式，容易得到[latex]\arg\max_{e}p(e|f)=\arg\max_{e}\frac{p(f|e)p(e)}{p(f)}[/latex]，由于对于同一个法语单词来说，[latex]p(f)[/latex]是一定的，因此上式等同于[latex]\arg\max_{e}p(f|e)p(e)[/latex],其中

• [latex]p(f|e)[/latex]称为翻译模型，即给定信号源，观察到信号的概率；
• [latex]p(e)[/latex]称为语言模型，即信号源发生的概率；

机器翻译的任务就被拆解成这两个模型的任务了。本文只负责翻译模型:)

词对齐(Alignment)

我们假设要翻译的法语句子包含m个单词，即[latex]F=f_1, f_2, …, f_m[/latex]，翻译出来的英语句子包含l个单词，即[latex]E=e_1, e_2, …, e_l[/latex]，那么之前提到的翻译概率[latex]p(F|E)=p(f_1,f_2,…,f_m|e_1,e_2,…,e_l, m)[/latex]其中包含了对句子长度服从这么个条件分布[latex]p(m|l)[/latex]的假设。
然而这个概率是很难直接建模的，于是一帮聪明的人想出来一个方案：引入词对齐(word alignment):[latex]p(F|E)=p(F,A|E)=p(f_1,f_2,…,f_m,a_1,a_2,…,a_m|e_1,e_2,…,e_l, m)[/latex]，其中这个a就是词对齐，它是个隐变量，表示源语言(法语)中的某个单词是用目标语言(英语)翻译而来的。
具体可以看这个例子：

e = And the program has been implemented
     1   2     3     4   5       6
f = Le programme a ete mis en application
     1   2       3  4   5   6      7

这个例子中，[latex]l=6, m=7[/latex]，一个理想的对齐方式如下：

Le => the
Programme => program
a => has
ate => been
mis => implemented
en => implemented
application => implemented

它对应的alignment标记可以表示为[latex]a_1,a_2,…,a_7=<2,3,4,5,6,6,6>[/latex]
此外在英文中还有加入个特殊的NULL单词，它表示法语中那些对于英语翻译“无用”的词。

IBM Model 1：翻译模型=对齐+词-词翻译

根据之前单词对齐的假设，我们可以把翻译任务进一步拆分成两部分：对齐和词到词的翻译，边际化参数A
[latex]p(F|E)=\sum_{A}p(F,A|E)=\sum_{A}p(A|E)p(F|E,A)[/latex]
第一部分是对齐，在Model 1中做了一个最简单的假设：每个对齐都是等概率发生的。所以[latex]p(a|e)=\prod_{i=1}^{m}\frac{1}{l+1}[/latex]。
第二部分是词-词翻译，也是整个模型的核心部分，这里当然不能再精简了，否则就没有了…
[latex]P(F|E,A)=\prod_{j=1}^{m}tr(f_j|e_{A_{j}})[/latex]
这里头的[latex]tr(.|.)[/latex]就是单词到单词的翻译概率，也就是模型要学习的东西。

模型训练：期望最大化(EM)

很显然，要学习到词-词翻译概率，就必须知道单词对齐；要学习单词对齐，就得知道翻译概率，这种鸡生蛋的问题就需要用EM来解。
定义一个参数[latex]\delta(k,i,j)[/latex]表示第k组平行预料（训练集中法文-英文句子）里的第i个法文词，第j个英文词。如果是上帝模式，那[latex]\delta(k,i,j)=1/0[/latex]分别表示这两个词之间应当/不应当对齐。然而目前无人能观测到这个隐变量，所以采用最大似然估计来估计这个东西，意思就是说翻译概率的大小决定了单词对齐的概率，即
[latex]\delta(k,i,j)=\frac{q(j|i,l_k,m_k)tr(f_i^{(k)}|e_j^{(k)})}{\sum_{j=0}^{l_k}q(j|i,l_k,m_k)tr(f_i^{(k)}|e_j^{(k)})}=\frac{tr(f_i^{(k)}|e_j^{(k)})}{\sum_{j=0}^{l_k}tr(f_i^{(k)}|e_j^{(k)})}[/latex]
注意上面这个式子是根据Model 1“句子中的对齐都是等概率”假定推导来的：[latex]q(j|i,l_k,m_k)=\frac{1}{l^{(k)}+1}[/latex]

算法

输入：训练集[latex](f^{(k)}, e^{(k)})[/latex]其中[latex]k=1,…,n[/latex]，其中[latex]f^{(k)}=f_1^{(k)}…f_m^{(k)}, e^{(k)}=e_1^{(k)}…e_l^{(k)}[/latex]
初始化：初始化所有词-词翻译概率[latex]t(f|e)[/latex]
步骤：关键部分我用绿色的字注释了

• for t=1…T
  • Set all counts [latex]c=0[/latex]
  • for [latex]k=1…N[/latex]
    • for [latex]i=1…m_k[/latex]
      • for [latex]j=1…l_k[/latex]
        • // word(i,j) in parallel corpus line k
        • [latex]\delta(k,i,j)=\frac{tr(f_i^{(k)}|e_j^{(k)}}{\sum_{j=0}^{l_k}tr(f_i^{(k)}|e_j^{(k)})}[/latex] //estimate alignment
        • [latex]c(e_j^{(k)},f_i^{(k)})+=\delta(k,i,j)[/latex] //update co-occurence count for word-word pair
        • [latex]c(e_j^{(k)})+=\delta(k,i,j)[/latex]
  • [latex]tr(f|e)=\frac{c(e,f)}{c(e)}[/latex] //update word-word pair translation probabilities

输出：[latex]tr(f|e)[/latex]
 

参考文献

1. http://www.cs.columbia.edu/~mcollins/courses/nlp2011/notes/ibm12.pdf
2. http://cpmarkchang.logdown.com/posts/245418-mt-ibm-model-1
3. https://zh.wikipedia.org/wiki/%E7%BB%9F%E8%AE%A1%E6%9C%BA%E5%99%A8%E7%BF%BB%E8%AF%91