基于单词的统计翻译模型 IBM Model1

统计翻译模型的基本思想是对大量平行(parallel)语料进行统计分析。之前实习的时候有幸接触到一些简单的模型,而事实上这种简单的模型在大量数据训练的基础上,发挥还是挺不错的。

IBM的统计翻译模型从简单到繁琐,一共有Model1-Model5五个模型,全都是基于词的统计模型。

本文只对Model1作简单介绍,方便起见,文中以将法文(French)翻译为英文(English)为例。

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

模型假定源语言中的(法语)句子是由目标语言(英语)经过含有噪声的信道编码后得到的。寻找最佳的英文翻译结果等同于寻找\arg\max_{e}p(e|f)

根据贝叶斯公式,容易得到\arg\max_{e}p(e|f)=\arg\max_{e}\frac{p(f|e)p(e)}{p(f)},由于对于同一个法语单词来说,p(f)是一定的,因此上式等同于\arg\max_{e}p(f|e)p(e),其中

  • p(f|e)称为翻译模型,即给定信号源,观察到信号的概率;
  • p(e)称为语言模型,即信号源发生的概率;

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

词对齐(Alignment)

Word Alignment

我们假设要翻译的法语句子包含m个单词,即F=f_1, f_2, ..., f_m,翻译出来的英语句子包含l个单词,即E=e_1, e_2, ..., e_l,那么之前提到的翻译概率p(F|E)=p(f_1,f_2,...,f_m|e_1,e_2,...,e_l, m)其中包含了对句子长度服从这么个条件分布p(m|l)的假设。

然而这个概率是很难直接建模的,于是一帮聪明的人想出来一个方案:引入词对齐(word alignment):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),其中这个a就是词对齐,它是个隐变量,表示源语言(法语)中的某个单词是用目标语言(英语)翻译而来的。

具体可以看这个例子:

这个例子中,l=6, m=7,一个理想的对齐方式如下:

它对应的alignment标记可以表示为a_1,a_2,...,a_7=<2,3,4,5,6,6,6>

此外在英文中还有加入个特殊的NULL单词,它表示法语中那些对于英语翻译“无用”的词。

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

根据之前单词对齐的假设,我们可以把翻译任务进一步拆分成两部分:对齐和词到词的翻译,边际化参数A

p(F|E)=\sum_{A}p(F,A|E)=\sum_{A}p(A|E)p(F|E,A)

第一部分是对齐,在Model 1中做了一个最简单的假设:每个对齐都是等概率发生的。所以p(a|e)=\prod_{i=1}^{m}\frac{1}{l+1}

第二部分是词-词翻译,也是整个模型的核心部分,这里当然不能再精简了,否则就没有了…

P(F|E,A)=\prod_{j=1}^{m}tr(f_j|e_{A_{j}})

这里头的tr(.|.)就是单词到单词的翻译概率,也就是模型要学习的东西。

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

很显然,要学习到词-词翻译概率,就必须知道单词对齐;要学习单词对齐,就得知道翻译概率,这种鸡生蛋的问题就需要用EM来解。

定义一个参数\delta(k,i,j)表示第k组平行预料(训练集中法文-英文句子)里的第i个法文词,第j个英文词。如果是上帝模式,那\delta(k,i,j)=1/0分别表示这两个词之间应当/不应当对齐。然而目前无人能观测到这个隐变量,所以采用最大似然估计来估计这个东西,意思就是说翻译概率的大小决定了单词对齐的概率,即

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

注意上面这个式子是根据Model 1“句子中的对齐都是等概率”假定推导来的:q(j|i,l_k,m_k)=\frac{1}{l^{(k)}+1}

算法

输入:训练集(f^{(k)}, e^{(k)})其中k=1,...,n,其中f^{(k)}=f_1^{(k)}...f_m^{(k)}, e^{(k)}=e_1^{(k)}...e_l^{(k)}

初始化:初始化所有词-词翻译概率t(f|e)

步骤:关键部分我用绿色的字注释了

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

输出:tr(f|e)

 

参考文献

  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

Crowd-BT算法模型 Part III [在线学习]

转载请注明来自http://boweihe.me/?p=1524

本文内容源自

Chen, X., Bennett, P. N., Collins-Thompson, K., & Horvitz, E. (2013, February). Pairwise ranking aggregation in a crowdsourced setting. InProceedings of the sixth ACM international conference on Web search and data mining (pp. 193-202). ACM.

第二部分还在努力学习,先把第三部分贴上来…有部分理解不全我就假装没看到了(捂脸)

在线学习:这个方法似乎是借鉴了Crowd-BT模型,但是最后参数更新的方法用了另外一套东西,可以独立于Crowd-BT的最优化而计算。

QQ截图20150517212359 QQ截图20150517212419 QQ截图20150517212505

Crowd-BT算法模型 Part I [Bradley-Terry的延伸-模型基础]

转载请注明来自http://boweihe.me/?p=1524

本文内容源自

Chen, X., Bennett, P. N., Collins-Thompson, K., & Horvitz, E. (2013, February). Pairwise ranking aggregation in a crowdsourced setting. InProceedings of the sixth ACM international conference on Web search and data mining (pp. 193-202). ACM.

第一部分是对Crowd-BT中采用的模型的中文翻译及理解,不涉及后面的主动学习算法(因为暂时没看懂,哈哈)。

因为没弄懂Wordpress的公式插件,所以暂时用Word文档的截图了..

QQ截图20150515100316

 

QQ截图20150515100340

QQ截图20150515100406