Statistical Machine Translation IBM Models 1 and 2

IBM model是统计机器翻译(statistical machine translation, SMT)非常经典的模型,虽然到现在已经非常古老了,但是其中的一些核心idea到现在还在被使用与翻译系统中,比如alignment模型。之前上京都大学的自然语言处理的课程时就有接触过,最近研究中有个子问题可能可以借鉴IBM model的一些idea,所以又IBM model翻出来重新看了一遍,这里做一个记录和总结,主要参考Columbia University由Michael Collins主讲的课程COMS W4705: Natural Language Processing的notes。

Introduction

IBM model被提出时主要是用于解决翻译FrenchEnglish

$f = f_1, f_2…f_m $表示一个French句子,长度为$m$,$f_i$ for $j \in {1…m}$ 表示句子中第$i$个词。

同样的,定义$e = e_1, e_2…e_l$表示一个英语句子。

在SMT系统中,假设我们有一个训练数据集,也就是一些翻译的例子,每个例子也就是French句子以及对应的翻译的English句子,$(f^{(k)}, e^{(k)})$,表示第k个翻译例子。

$$\begin{aligned} f^{(k)} = f_{1}^{(k)}, f_{2}^{(k)}...f_{m_k}^{(k)} \\ e^{(k)} = e_{1}^{(k)}, e_{2}^{(k)}...e_{l_k}^{(k)} \end{aligned}$$

The Nosiy-Channel Approch(消息信道模型)

IBM model也是使用noisy-channel模型的一个例子,主要包括两个部分:

  1. A language model, 用于计算任何英语句子$e$存在的概率$p(e)$,比如我们可以用trigram language model来计算,或者最简单直接的unigram language model。一般language model可以通过大量的English corpus就能直接估计出来。
  2. A translation model,用于计算给定一个English句子$e$,对应的French句子是$f$的条件概率$p(f|e)$。这个概率的计算方法会在后面的内容介绍,一般是从给定的翻译例子的训练数据中估计出来。给定了English句子$e$后,$p(f|e)$主要由两个选择决定:first,the length of French sentence: $m$;second, a choice of the $m$ words $f_1…f_m$。

这里可能会有很多觉得奇怪,任务不是给定法语句子,要翻译为英语句子嘛,为什么前面的translation model是先给定英语句子,其对应法语句子为$f$的概率。下面会给出解释:

我们最直接的任务的表示是($E$表示所有的英语句子):

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

通过贝叶斯规则我们可以转换问题为:

$$\begin{aligned} arg \max_{e\in E} p(e|f) &= arg \max_{e\in E} \frac{p(e, f)}{p(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}$$

所以问题就转换为了求:

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

也就是前面定义的language model和translation model可以解决的问题。一个可能的翻译$e$的score分为两部分:first,the language-model score $p(e)$,给出一个先验概率用于估计这个句子是个合法的英语句子的概率。second,the translation-model score $p(f|e)$,也就是$f$是$e$的翻译的概率。

之所以把原来的问题转换为求:$e^{*} = arg \max_{e\in E} p(e)p(f|e)$(也就是noisy-channel approach),主要的一个好处是可以引入language model。可以有效的改进翻译结果的fluency和语法的合法程度。

只要解决了提到的两个model的参数估计,就可以得到问题的solution。language-model的score一般比较直接,通过分析大规模的English corpus生成的gram model就可以得到,比如trigram model,bigram model。

所以接下来主要要介绍的是:

  1. 如何定义translation model $p(f|e)$
  2. 如果从翻译例子集中估计出translation model的参数。

The IBM Models

Alignments

现在我们来解决modeling条件概率$p(f|e)$的问题,$f=f_1…f_m$以及$e=e_1…e_l$。

前面我们提到过,$p(f|e)$主要由两个选择决定:first,the length of French sentence: $m$;second, a choice of the $m$ words $f_1…f_m$。

为了简化问题,这里我们先假设我们已经有了$p(m|l)$的分布(后面会再次引入并介绍如何估计)。从这里开始,我们固定$m$,然后主要考虑modeling下面的分布:

$$\begin{aligned} p(f_1...f_m|e_1...e_l,m) \end{aligned}$$

也就是$e=e_1…e_m$并且Frence句子长度为$m$的条件下,翻译为$f=f_1…f_m$的条件概率。

直接model $p(f_1…f_m|e_1…e_l,m)$是非常难的。IBM model的一个核心idea是引入alignment variables。alignment variables用于将French句子中的每个位置(词)alignment到English sentence的一个位置,$a_1, a_2…a_m$,$a_1=2$表示关联French sentence的第一个位置关联到English sentence的第二个位置。每个alignment variable的取值范围即是English句子的所有位置,也就是$a\in {0,1,…,l}$。本质上alignment variables是用于为每个French word指定其对应的English sentence(可以多个French words可以关联到同一个English word)。

因为直接model $p(f_1…f_m|e_1…e_l,m)$是非常难的,所以我们先定义:

$$\begin{aligned} p(f_1...f_m,a_1...a_m \ |\ e_1...e_l,m) \end{aligned}$$

进一步我们可以得到:

$$\begin{aligned} 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_1...a_m|e_1...e_l) \end{aligned}$$

$a_j$用于指定$f_j$ is aligned to $e_i, i=a_j$,直观上也就是$f_j$是由$e_i, i=a_j$翻译而来的。注意$e_0$指定的是特殊的$NULL$ word。

Alignment Models: IBM Model 2

这里我们开始具体介绍如何model上面定义的带有隐含变量(hidden variables)的条件分布:

$$\begin{aligned} p(f_1...f_m|e_1...e_l,m) \end{aligned}$$

如何model这个条件分布决定了IBM Model 1和2的不同,IBM Model 1其实是IBM Model 2的一个特例。所以首先我们介绍IBM Model 2。

$E$是一个English words的集合
$F$是一个French words的集合
$X$和$Y$分别用于表示French句子的最大可能长度和English句子的最大可能长度。

  • $t(f|e)\text{ for any }f\in F, e\in E\cup{NULL}$,也就是也就是$f$是从$e$生成的条件概率。
  • $q(j|i,l,m)\text{ for any }l\in {1…X}, m\in{1…Y}, i\in {1…m}$。$q(j|i,l,m)$可以理解为在English sentence长度为$l$, French句子长度为$m$的条件下,alignment variable $a_i$取值为$j$的条件概率。

这里先给出最终的model,根据IBM Model 2的一些假设(后面会介绍),我们可以得到:

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

Independence Assumptions in IBM Model 2

$L$为一个随机变量,对应着English sentence的长度。
$M$为一个随机变量,对应着French sentence的长度。
$F_1…F_m$是French句子的words。
$A_1…A_m$是French句子的alignment variables。

我们要model的是:

$$\begin{aligned} p(f_1...f_m,a_1...a_m|e_1...e_l,m) \end{aligned}$$

也就是:

$$\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) \end{aligned}$$

根据概率chain rule,可以转换为:

$$\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}$$

进一步的,如果我们假设各个word的alignment是独立的,也就是只依赖于$M$和$L$,
,则可以有:

$$\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}$$ $$\begin{aligned} \prod_{i=1}^{m} P(A_i=a_i|L=l,M=m)= q(a_i|i,l,m) \end{aligned}$$

如果我们假设$F_i$的值只依赖于$E_j, j={a_i}$,那么我们有;

$$\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}$$ $$\begin{aligned} P(F_i=f_i|E_{a_i}=e_{a_i}) = t(f_i|e_{a_i}) \end{aligned}$$

这样我们就完成了对前面$p(f_1…f_m,a_1…a_m|e_1…e_l,m)$的model(基于IBM Model 2的一些假设),得到:

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

剩下的问题就是我们如何从翻译例子训练集中估计出参数$q(a_i|i,l,m)$和$t(fi|e{a_i})$。

Applying IBM Model 2

前面我们以及介绍了IBM Model 2,在进一步介绍如何估计参数之前,我们回顾一下我们将如何应用IBM Model 2用于机器翻译问题。

在第一节我们推导过,我们最终的目标是:

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

$p(e)$也就是language model,可以简单的通过分析英语语料库的gram model得到。
$p(f|e)$是translation model,也就是我们前面一直在介绍的如何定义和计算这个model。

通过引入alignment model,我们得到:

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

进一步我们需要model $p(f,a|e)$的分布以及计算方式,也就是我们上一节介绍的,我们根据IBM Model 2的假设最终得到:

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

当然,下面的问题是NP hard的,但是有多种估计方法:

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

除了上面的翻译问题,我们还可以利用IBM Model 2用于找到最有可能的alignment。假设我们已经估计得到参数$t(f|e)$和$q(j|i,l,m)$,给定一个新的翻译例子,我们可以利用前面得到的参数估计最有可能的alignment:

$$\begin{aligned} arg \max{a_1...a_m} p(a1_1...a_m|f_1...f_m,e_1...e_l,m) \end{aligned}$$

IBM Model 2的idependent假设使得我们可以很直接的计算的到最有可能的alignment,也就是对于每个alignment variable:

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

Parameter Estimation