机器翻译原理与方法 第三讲 基于词的统计机器翻译方法 刘群 中国科学院计算技术研究所 liuqun@ict.ac.cn 中国科学院计算技术研究所2009年秋季课程

机器翻译原理与方法(03) 基于词的统计机器翻译方法 内容提要 为翻译建立概率模型 IBM的信源信道模型 语言模型 –– n元语法模型 翻译模型 –– IBM模型1-5 词语对齐算法 解码算法 Candide系统 Egypt工具包与Giza++ 机器翻译自动评价 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 为翻译建立概率模型 假设任意一个英语句子e和一个法语句子 f，我们定义f翻译成e的概率为： 其归一化条件为： 于是将 f 翻译成 e 的问题就变成求解问题： 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 内容提要 为翻译建立概率模型 IBM的信源信道模型 语言模型 –– n元语法模型 翻译模型 –– IBM模型1-5 词语对齐算法 解码算法 Candide系统 Egypt工具包与Giza++ 机器翻译自动评价 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 信源信道模型 (1) 信源信道模型又称噪声信道模型，是由IBM公司的Peter F. Brown等人于1990年提出来的： Peter F. Brown, John Cocke, Stephen A. Della Pietra, Vincent J. Della Pietra, Fredrick Jelinek, John D. Lafferty, Robert L. Mercer, Paul S. Roossin, A Statistical Approach to Machine Translation, Computational Linguistics,1990 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 信源信道模型 (2) E P（E） P（F｜E） F 假设我们看到的源语言文本F是由一段目标语言文本E经过某种奇怪的编码得到的，那么翻译的目标就是要将F还原成E，这也就是就是一个解码的过程。 注意，在信源信道模型中： 噪声信道的源语言是翻译的目标语言 噪声信道的目标语言是翻译的源语言 这与整个机器翻译系统翻译方向的刚好相反 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 统计机器翻译基本方程式 P.Brown称上式为统计机器翻译基本方程式 语言模型：P(E) 翻译模型：P(F|E) 语言模型反映“ E像一个句子”的程度：流利度 翻译模型反映“F像E”的程度：忠实度 联合使用两个模型效果好于单独使用翻译模型，因为后者容易导致一些不好的译文。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 语言模型与翻译模型 考虑汉语动词“打”的翻译：有几十种对应的英语词译文： 打人，打饭，打鱼，打毛衣，打猎，打草稿，…… 如果直接采用翻译模型，就需要根据上下文建立复杂的上下文条件概率模型 如果采用信源－信道思想，只要建立简单的翻译模型，可以同样达到目标词语选择的效果： 翻译模型：不考虑上下文，只考虑单词之间的翻译概率 语言模型：根据单词之间的同现选择最好的译文词 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 统计机器翻译的三个问题 三个问题： 语言模型P(E)的建模和参数估计 翻译模型P(F|E)的建模和参数估计 解码（搜索）算法 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 内容提要 为翻译建立概率模型 IBM的信源信道模型 语言模型 –– n元语法模型 翻译模型 –– IBM模型1-5 词语对齐算法 解码算法 Candide系统 Egypt工具包与Giza++ 机器翻译自动评价 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 语言模型 统计语言模型把一种语言理解成是产生一个句子的随机事件。在统计语言模型看来，对于一种语言，任何一个句子都是可以接受的，只是接受的可能性（概率）不同 语言模型给出任何一个句子的出现概率： Pr(E=e1e2…en) 归一化条件：ΣEPr(E)=1 统计语言模型实际上就是一个概率分布，它给出了一种语言中所有可能的句子的出现概率 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 语言模型的类型 理论上，单词串的任何一种概率分布，都是一个语言模型。 实际上，N元语法模型是最简单也是最常见的语言模型。 N元语法模型由于没有考虑任何语言内部的结构信息，显然不是理想的语言模型。 其他语言模型： 隐马尔科夫模型（HMM）（加入词性标记信息） 概率上下文无关语法（PCFG）（加入短语结构信息） 概率链语法（Probabilistic Link Grammar）（加入链语法的结构信息） 目前为止，其他形式的语言模型效果都不如N元语法模型 统计机器翻译研究中开始有人尝试基于句法的语言模型 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 N元语法模型－概念辨析 N元语法模型：N-Gram Model。 所谓N-Gram，指的是由N个词组成的串，可以称为“N元组”，或“N元词串”。 基于N-Gram建立的语言模型，称为“N元语法模型(N-Gram Model)”。 Gram不是Grammar的简写。在英文中，并没有N-Grammar的说法。 在在汉语中，单独说“N元语法”的时候，有时指“N元组(N-Gram)”，有时指“N元语法模型(N-Gram Model)”，请注意根据上下文加以辨别。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 N元语法模型－定义 N元语法模型（N-gram Model） 假设：单词wi出现的概率只与其前面的N-1个单词有关 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 N元语法模型－举例 N=1时：一元语法模型 相当于词频表，给出所有词出现的频率 N=2时：二元语法模型 相当于一个转移矩阵，给出每一个词后面出现另一个词的概率 N=3时：三元语法模型 相当于一个三维转移矩阵，给出每一个词对儿后面出现另一个词的概率 在自然语言处理中，N元语法模型可以在汉字层面，也可以在单词层面，还可以在概念层面…… 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 二元语法模型－图示 P(t-i-p) = P(X1 = t)P(X2 = i|X1 = t)P(X3 = p|X2 = i) = 1.0×0.3×0.6= 0.18 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 袋子模型 Bag Model (1) 将一个英语句子中所有的单词放入一个袋子中 用N元语法模型试图将其还原 对于这些单词的任何一种排列顺序根据N元语法模型计算其出现概率 取概率最大的排列方式 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 袋子模型 Bag Model (2) 实验：取38个长度小于11个单词的英语句子，实验结果如下： 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 语言模型的平滑算法 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 内容提要 为翻译建立概率模型 IBM的信源信道模型 语言模型 –– n元语法模型 翻译模型 –– IBM模型1-5 词语对齐算法 解码算法 Candide系统 Egypt工具包与Giza++ 机器翻译自动评价 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 翻译模型 翻译模型P(F|E)反映的是一个源语言句子E翻译成一个目标语言句子F的概率 由于源语言句子和目标语言句子几乎不可能在语料库中出现过，因此这个概率无法直接从语料库统计得到，必须分解成词语翻译的概率和句子结构（或者顺序）翻译的概率 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 翻译模型与对齐 翻译模型的计算，需要引入隐含变量： 对齐A： 翻译概率P(F|E)的计算转化为对齐概率P(F,A|E)的估计 对齐：建立源语言句子和目标语言句子的词与词之间的对应关系和句子结构之间的对应关系 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 词语对齐的表示 (1) 图形表示 连线 矩阵（见下页） 数字表示 给每个目标语言单词标记其所有对应的源语言单词 1 China 中国 1,2 2 ’s 十四 3 3 14 个 3 4 open 边境 5 5 board 开放 4 6 cities 城市 6 7 marked 经济 8 8 economic 建设 9 9 achievement 成就 9 显著 7 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 词语对齐的表示 (2) achievement economic marked cities board open 14 ‘s China 中国 十四 个 边境 开放 城市 经济 建设 成就 显著 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 对P(F,A|E)的估计 IBM Model 1仅考虑词对词的互译概率 IBM Model 2加入了词的位置变化的概率 IBM Model 3加入了一个词翻译成多个词的概率 IBM Model 4 IBM Model 5 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 & 2 推导方式 (1) 源语言句子E： I1 am2 a3 student4 目标语言句子F： 我 是 一 个 学生 词语对齐A： 1 2 3 3 4 IBM模型1&2的推导过程： 猜测目标语言句子长度； 从左至右，对于每个目标语言单词： 首先猜测该单词由哪一个源语言单词翻译而来； 再猜测该单词应该翻译成什么目标语言词。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 & 2 推导方式 (2) 假设翻译的目标语言句子为: 假设翻译的源语言句子为: 假设词语对齐表示为: 那么词语对齐的概率可以表示为: 注意：在IBM Model中，词语对齐只考虑了源语言到目标语言的单向一对多形式，不考虑多对一和多对多的形式。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 的推导 (1) 假设所有翻译长度都是等概率的： 假设词语对齐只与源语言长度有关，与其他因素无关： 假设目标词语的选择只与其对应的源语言词语有关，与其他因素无关： 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 的推导(2) 那么对齐概率可以表示为: 对所有可能的对齐求和，那么翻译概率就可以表示为: 这就是IBM Model 1的翻译模型公式。 也就是说，给定参数t(f|e)，我们就可以计算出句子E翻译成句子F的概率。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 的参数求解(1) 在IBM Model 1中，ε是个常数，无关紧要，起重要作用的就是单词翻译概率分布： 这个单词翻译概率分布表现为一个翻译概率表，这个表给出了每一个源语言单词翻译成任何一个目标语言单词的概率，并且这个概率满足归一性约束条件： 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 的参数求解(2) 根据最大似然估计，我们希望得到一组概率分布，使得我们的训练语料库出现的概率最大。 也就是说，给定训练语料库E和F，我们要求解一个概率分布t(f|e)，使得翻译概率Pr(F|E)最大。 这是一个受约束的极值问题，约束条件即是t(f|e)的归一性条件。 为了求解这个问题，我们需要引入拉格朗日乘子，构造一个辅助函数，将上述受约束的极值问题转换成一个不受约束的极值问题。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 的参数求解(3) 引入拉格朗日乘子λe，构造辅助函数如下： 将上述函数对t(f|e)求导得到： 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 的参数求解(4) 令上式为0，我们得到： 我们看到，这个公式的左边和右边都出现了t(f|e) 我们无法直接用这个公式从给定的语料库(F|E)中计算出t(f|e) 我们可以将这个公式看成是一个迭代公式，给定一个初值t(f|e)，利用这个公式反复迭代，最后可以收敛到一个稳定的t(f|e)值，这就是EM算法。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 的参数求解(5) 上述迭代公式代入IBM Model 1的翻译模型公式， 我们得到： 对齐A中e连接到f的次数 定义在E和F的所有可能的对齐A下e和f连接数的均值为： 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 的参数求解(6) 我们有： 将c(f|e;F,E)代入迭代公式，并将Pr(F|E)并入参数λe，我们得到新的迭代公式： 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 的参数求解(7) 这个新的迭代公式可以理解为： 一旦我们得到了一组参数t(f|e)，我们就可以计算所有的词语对齐的概率Pr(F,A|E)； 有了每个词语对齐的概率Pr(F,A|E)，我们就可以计算新的t(f|e)的值，就是所有的出现词语链接(e,f)的词语对齐概率之和，并对e进行归一化。 这个迭代算法就是一个经典的EM算法。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 的参数求解(8) 通常，训练语料库(F|E)是由一系列句子对组成的： 因此实际计算时我们采用以下公式： 这里λe仅仅起到一个归一化因子的作用。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 的化简(1) 前面IBM Model 1的翻译模型公式为： 其复杂度太高： 这个公式实际上可以进一步简化。 因为： 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1 的化简(2) 所以翻译模型公式就可以简化为: 其复杂度减少为： 而c(f|e;F,E)也可以简化为： c(f|e;F,E)的推导还需细化。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 2 的推导 (1) 假设词语对齐只与源语言长度、目标语言的长度和两个词的位置有关，与其他因素无关： 归一化条件为： 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 2 的推导 (2) 经过推导我们可以得到： 经过化简我们可以得到IBM Model 2翻译模型： 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 2 的参数求解 (1) 同样通过引入拉格朗日乘子推导可以得到： 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 2 的参数求解 (2) 考虑到训练语料库(F|E)是由一系列句子对组成的： 因此实际计算时我们采用以下公式： 这里λe和μjml仅仅起到归一化因子的作用。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 3 & 4 & 5 推导方式 (1) e1 e2 e3 e4 e5 e6 e7 繁殖概率 1 1 2 2 1 1 翻译概率 f11 f21 f31 f32 f41 f42 f61 f71 调序概率 f1 f2 f3 f4 f5 f6 f7 f8 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 3 & 4 & 5 推导方式 (2) 首先根据源语言词语的繁殖概率，确定每个源语言词翻译成多少个目标语言词； 根据每个源语言词语的目标语言词数，将每个源语言词复制若干次； 将复制后得到的每个源语言词，根据翻译概率，翻译成一个目标语言词； 根据调序概率，将翻译得到的目标语言词重新调整顺序，得到目标语言句子。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 3 的推导 对于句子中每一个英语单词e，选择一个产出率φ，其概率为n(φ|e)； 对于所有单词的产出率求和得到m-prime； 按照下面的方式构造一个新的英语单词串：删除产出率为0的单词，复制产出率为1的单词，复制两遍产出率为2的单词，依此类推； 在这m-prime个单词的每一个后面，决定是否插入一个空单词NULL，插入和不插入的概率分别为p1和p0； φ0为插入的空单词NULL的个数。 设m为目前的总单词数：m-prime+φ0； 根据概率表t(f|e)，将每一个单词e替换为外文单词f； 对于不是由空单词NULL产生的每一个外语单词，根据概率表d(j|i,l,m)，赋予一个位置。这里j是法语单词在法语串中的位置，i是产生当前这个法语单词的对应英语单词在英语句子中的位置，l是英语串的长度，m是法语串的长度； 如果任何一个目标语言位置被多重登录（含有一个以上单词），则返回失败； 给空单词NULL产生的单词赋予一个目标语言位置。这些位置必须是空位置（没有被占用）。任何一个赋值都被认为是等概率的，概率值为1/φ0。 最后，读出法语串，其概率为上述每一步概率的乘积。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM模型的参数训练(1)：EM算法 EM参数训练算法是经典的无指导学习的算法： 给定初始参数； E步骤：用已有的参数计算每一个句子对的所有可能的对齐的概率； M步骤：用得到的所有对齐的概率重新计算参数； 重复执行E步骤和M步骤，直到收敛。 由于EM算法的E步骤需要穷尽所有可能的对齐，通常这会带来极大的计算量，除非我们可以对计算公式进行化简（就像前面IBM Model 1所做的那样），否则这种计算量通常是不可承受的。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

IBM模型的参数训练(2)：Viterbi训练 给定初始参数； 用已有的参数求概率最大（Viterbi）的词语对齐； 用得到的概率最大的词语对齐重新计算参数； 回到第二步，直到收敛为止。 在对参数计算公式无法化简的情况下，采用Viterbi参数训练算法是一种可行的做法，这种算法通常可以迅速收敛到一个可以接受的结果。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM模型的参数训练 (3) IBM Model 1 任何初始值均可达到全局最优 IBM Model 2~5： 存在大量局部最优，任意给定的初值很容易导致局部最优，而无法到达全局最优的结果 IBM的训练策略： 依次训练IBM Model 1-5 对于与上一级模型相同的参数初始值，直接取上一个模型训练的结果； 对于新增加的参数，取任意初始值。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM模型的参数训练 (4) 由于IBM Model 1和2存在简化的迭代公式，实际上在EM算法迭代是并不用真的去计算所有的对齐，而是可以利用迭代公式直接计算下一次的参数； 由于IBM Model 3、4、5的翻译模型公式无法化简，理论上应该进行EM迭代。由于实际上由于计算所有词语对齐的代价太大，通常采用Viterbi训练，每次E步骤只生成最好的一个或者若干个对齐。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1的EM训练示例 (0) 我们用一个简单的例子来演示EM训练的过程 假设有两个句子对：(a b|x y) 和 (a y) 先假设所有词语翻译概率平均分布P(f|e)： Pr(a|x) 1/2 Pr(a|y) Pr(b|x) Pr(b|y) 我们这里为方便起见，对IBM Model 1做了简化： 只考虑词语一对一的情况，不考虑词语一对多或者对齐到空的情况； 对齐概率计算的时候，忽略了词语长度和词语对齐概率，仅考虑词语翻译概率。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1的EM训练示例(1E) 对所有可能的对齐 计算P(F,A|E) 对P(F,A|E)归一化 得到P(A|F,E) a b x y a b x y a y 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1的EM训练示例(1M) 计算c(f|e) 重新计算Pr(f|e) 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1的EM训练示例(2E) 对所有可能的对齐 计算P(F,A|E) 对P(F,A|E)归一化 得到P(A|F,E) a b x y a b x y a y 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1的EM训练示例(2M) 计算c(f|e) 重新计算Pr(f|e) 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM Model 1的EM训练示例(n) a b x y a b x y a y 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 统计机器翻译的解码 给定F，求E，使得P(E)*P(F|E)最大 解码问题实际上是一个搜索问题，搜索空间巨大，不能保证总能找到全局最优，但通常一些局部最优也是可以接受的 如果考虑所有的词语对齐可能性，那么这个问题是一个NP完全问题 [Knight 99] 经典的算法： 单调解码（不调整词序） 堆栈搜索 贪婪算法 …… 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 内容提要 为翻译建立概率模型 IBM的信源信道模型 语言模型 –– n元语法模型 翻译模型 –– IBM模型1-5 词语对齐算法（略） 解码算法 Candide系统 Egypt工具包与Giza++ 机器翻译自动评价 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 词语对齐算法 基于IBM模型的词语对齐方法 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 内容提要 为翻译建立概率模型 IBM的信源信道模型 语言模型 –– n元语法模型 翻译模型 –– IBM模型1-5 词语对齐算法 解码算法 Candide系统 Egypt工具包与Giza++ 机器翻译自动评价 机器翻译原理与方法(03) 基于词的统计机器翻译方法

堆栈搜索解码算法 (1) [Brown et al US Patent #5,477,451] 1st English word 2nd English word 3rd English word 4th English word start end all source words covered Each partial translation hypothesis contains: - Last English word chosen + source words covered by it - Next-to-last English word chosen - Entire coverage vector (so far) of source sentence - Language model and translation model scores (so far) [Jelinek 69; Och, Ueffing, and Ney, 01] 机器翻译原理与方法(03) 基于词的统计机器翻译方法

堆栈搜索解码算法 (2) [Brown et al US Patent #5,477,451] 1st English word 2nd English word 3rd English word 4th English word best predecessor link start end all source words covered Each partial translation hypothesis contains: - Last English word chosen + source words covered by it - Next-to-last English word chosen - Entire coverage vector (so far) of source sentence - Language model and translation model scores (so far) [Jelinek 69; Och, Ueffing, and Ney, 01] 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(1/13) 待翻译句子： 翻译概率表： 我 的 书 我 I 0.4 me 0.3 my 0.2 mine 0.1 的 of 0.5  书 book the book 不考虑扭曲概率（IBM模型1） 语言模型（略） Beam Width=3 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(2/13) 第一个译文词由“我”翻译过来， 得到四个翻译假设(hypothesis) 译文 原文位置 翻译模型 语言模型 I 0.4 p(I|<s>) me 0.3 p(me|<s>) my 0.2 p(my|<s>) mine 0.1 p(mine|<s>) <s> 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(3/13) 加上其他翻译假设(hypothesis) I 0.4 p(I|<s>) me 0.3 p(me|<s>) my 0.2 p(my|<s>) mine 0.1 p(mine|<s>) of 0.5 p(of|<s>) book p(book|<s>) the book p(the book|<s>) <s> 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(4/13) 剪枝(prune) I 0.4 p(I|<s>) me 0.3 p(me|<s>) my 0.2 p(my|<s>) mine 0.1 p(mine|<s>) of 0.5 p(of|<s>) book p(book|<s>) the book p(the book|<s>) <s> 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(5/13) 剪枝(prune)后的结果 I 0.4 p(I|<s>) my 0.2 p(my|<s>) the book 0.5 p(the book|<s>) <s> 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(6/13) 对每个翻译假设进行扩展，生成第二个译文词 I of I book I the book my of my book the book I …… the book of I my the book <s> 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(7/13) 剪枝(prune) I of I book I the book my of my book the book I …… the book of I my the book <s> 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(8/13) 剪枝(prune)后的结果 I my the book my book the book I the book of <s> 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(9/13) 如果剩下的词都可以翻译到空，该假设可以不再扩展 对每个翻译假设进行扩展，生成第二个译文词 my book of the book I of the book of I the book of me the book of my the book of mine I my the book my book the book I the book of <s> </s> 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(10/13) 剪枝(prune) my book of the book I of the book of I the book of me the book of my the book of mine I my the book my book the book I the book of <s> </s> 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(11/13) 剪枝(prune)后的结果 I my the book my book the book I the book of my book of the book of my the book of mine <s> </s> 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(12/13) 所有源文词都已经翻译，不再对假设进行扩展 I my the book my book the book I the book of my book of the book of my the book of mine <s> </s> 在这里加上句尾标记</s>， 重新计算完整句子的语言模 型分数，并选择最优译文。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 堆栈搜索解码算法 – 例子(13/13) 最优译文 I my the book my book the book I the book of my book of the book of my the book of mine <s> </s> 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 内容提要 为翻译建立概率模型 IBM的信源信道模型 语言模型 –– n元语法模型 翻译模型 –– IBM模型1-5 词语对齐算法 解码算法 Candide系统 Egypt工具包与Giza++ 机器翻译自动评价 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM公司的Candide系统(1) 基于统计的机器翻译方法 分析－转换－生成 中间表示是线性的 分析和生成都是可逆的 分析（预处理）： 1.短语切分 2.专名与数词检测 3.大小写与拼写校正 4.形态分析 5.语言的归一化 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM公司的Candide系统(2) 转换（解码）：基于统计的机器翻译 解码分为两个阶段： 第一阶段：使用粗糙模型的堆栈搜索 输出140个评分最高的译文 语言模型：三元语法 翻译模型：EM Trained IBM Model 5 第二阶段：使用精细模型的扰动搜索 对第一阶段的输出结果先扩充，再重新评分 语言模型：链语法 翻译模型：最大熵翻译模型（选择译文词） 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 IBM公司的Candide系统(3) ARPA的测试结果 ：   Fluency Adequacy Time Ratio 1992 1993 Systran .466 .540 .686 .743 Candide .511 .580 .575 .670 Transman .819 .838 .837 .850 .688 .625 Manual .833 .840 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 内容提要 为翻译建立概率模型 IBM的信源信道模型 语言模型 –– n元语法模型 翻译模型 –– IBM模型1-5 词语对齐算法 解码算法 Candide系统 Egypt工具包与Giza++ 机器翻译自动评价 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 JHU的1999年夏季研讨班 由来 IBM的实验引起了广泛的兴趣 IBM的实验很难重复：工作量太大 目的 构造一个统计机器翻译工具（EGYPT）并使它对于研究者来说是可用的（免费传播）； 在研讨班上用这个工具集构造一个捷克语—英语的机器翻译系统； 进行基准评价：主观和客观； 通过使用形态和句法转录机改进基准测试的结果； 在研讨班最后，在一天之内构造一个新语对的翻译器。 JHU夏季研讨班大大促进了统计机器翻译的研究 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 EGYPT工具包 EGYPT的模块 GIZA：这个模块用于从双语语料库中抽取统计知识（参数训练） Decoder：解码器，用于执行具体的翻译过程（在信源信道模型中，“翻译”就是“解码”） Cairo：整个翻译系统的可视化界面，用于管理所有的参数、查看双语语料库对齐的过程和翻译模型的解码过程 Whittle：语料库预处理工具 EGYPT可在网上免费下载，成为SMT的基准 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 EGYPT工具包的性能 “当解码器的原形系统在研讨班上完成时，我们很高兴并惊异于其速度和性能。1990年代早期在IBM公司举行的DARPA机器翻译评价时，我们曾经预计只有很短（10个词左右）的句子才可以用统计方法进行解码，即使那样，每个句子的解码时间也可能是几个小时。在早期IBM的工作过去将近10年后，摩尔定律、更好的编译器以及更加充足的内存和硬盘空间帮助我们构造了一个能够在几秒钟之内对25个单词的句子进行解码的系统。为了确保成功，我们在搜索中使用了相当严格的阈值和约束，如下所述。但是,解码器相当有效这个事实为这个方向未来的工作预示了很好的前景，并肯定了IBM的工作的初衷，即强调概率模型比效率更重要。” ——引自JHU统计机器翻译研讨班的技术报告 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 内容提要 为翻译建立概率模型 IBM的信源信道模型 语言模型 –– n元语法模型 翻译模型 –– IBM模型1-5 词语对齐算法 解码算法 Candide系统 Egypt工具包与Giza++ 机器翻译自动评价 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 机器翻译的评价 常见的人工评价指标 忠实度和流利度 可理解率 …… 自动评价的重要意义 反复使用无需成本 为通过频繁的实验提高系统性能提供了基本的保证 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 基于测试点的机器翻译自动评价 北大俞士汶于1990年代初期提出 模仿人类的标准化考试的方法，对每个题目（源文句子）设置若干个测试点 每个测试点只考察一个问题（比如汉语分词、词语译文选择等） 判断测试点是否被正确翻译，完全通过字符串匹配，每个测试点可以有多种候选的正确答案 是国际上最早出现的机器翻译自动评价方法之一 缺点是题库的构造成本很高，需要对机器翻译有相当了解的专家 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 基于编辑距离的机器翻译自动评价 编辑距离：Edit distance，又称Levenshtein Distance，用于计算两个字符串之间的距离 编辑距离的含义，是指通过插入、删除、替换等编辑操作，将一个字符串变成另外一个字符串时，所需要的编辑操作的次数 常见的基于编辑距离的评价指标： WER，PER，mWER，mPER 缺点：对词序问题没有好的处理方法 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 基于N元语法的机器翻译自动评价 基本思想 对于每个源文句子，由多位翻译人员提供人工翻译的结果 将机器翻译的结果与这多个人工翻译的结果进行比较，越相似的句子，评价越高 这种比较按照一元语法、二元语法、三元语法、……分别进行，然后进行评价 常见的评价指标 BLEU：各层语法的结果进行几何平均 NIST：各层语法的结果进行算术平均，同时考虑信息增益 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 机器翻译自动评价：例子 考虑例子： Candidate 1: It is a guide to action which ensures that the military always obeys the command of the party Candidate 2: It is to insure the troops forever hearing the activity guidebook that party direct Reference 1: It is a guide to action that ensures that the military will forever heed party commands Reference 2: It is the guiding principle which guarantees the military forces always being under the command of the party Reference 3: It is the practical guide for the army to heed the directions of the party 候选译文更好？ 这是一个例子。 这里有两个译文。由三个参考答案。 看看哪一个译文比较好？ 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 简单计数方法 计算候选译文中n-gram在参考译文中出现的次数，除以该候选译文n-gram总数，也就是n-gram的正确率。 举例来说，对于unigram，也就是计算候选译文中的所有词语中，在参考译文中出现的词语数，除以候选译文的词语总数，就是unigram的正确率。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 改进的计数方法 (1) 考虑例子： Candidate: the the the the the the the Reference 1: the cat is on the mat. Reference 2: there is a cat on the mat. 在这个例子中，如果采用简单计数方法，候选译文的unigram正确率将是100%，显然是不合理的 改进的计数方法：对于同一个词的多次出现，其匹配次数最多只能等于在同一个参考译文中该词出现最多的次数 跟进改进的计数方法，这个例子中the在参考译文的同一个句子中最多出现两次，因此候选译文的unigram正确率只有2/7。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 改进的计数方法 (2) 再看前面的例子： Candidate 1: It is a guide to action which ensures that the military always obeys the command of the party Candidate 2: It is to insure the troops forever hearing the activity guidebook that party direct Reference 1: It is a guide to action that ensures that the military will forever heed party commands Reference 2: It is the guiding principle which guarantees the military forces always being under the command of the party Reference 3: It is the practical guide for the army to heed the directions of the party 这是一个例子。 这里有两个译文。由三个参考答案。 看看哪一个译文比较好？ Candidate 1的Bigram正确率达到了10/17 而Candidate 2的Bigram正确率只有 1/13. 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 与忠实度和流利度的关系 修改后的n-gram正确率可以认为在一定程度上反映了译文质量的两个重要方面： 一元语法unigram正确率主要体现了词语是否翻译正确，这反映了译文忠实度 二元语法bigram以上的ngram正确率主要体现了词语的排列顺序是否正确，这反映了译文的流利度 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 N-Gram正确率的计算公式 Count(n-gram)是n-gram在某个候选译文中的出现次数 Countclip(n-gram)是n-gram在某个候选译文中出现的次数，按照同一个参考译文中出现最多次数剪切后的次数 因此整个句子的翻译精度可以用这样一个公式来表示。他代表有多少个n-gram在参考译文中可以找到，然后除以总长度。 要翻译的文章有多少个句子，都按照这样一个办法累计。就可以得到整个文本的翻译精度。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 新问题：召回率问题 (1) 考虑这个例子： Candidate1:of the Reference1: It is a guide to action that ensures that the military will forever heed party commands Reference2: It is the guiding principle which guarantees the military forces always being under the command of the party Reference3: It is the practical guide for the army to heed the directions of the party 按照上面公式计算的bigram正确率将是100%，不合理 是召回率太低引起的吗？ ??? 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 新问题：召回率问题 (2) 再考虑一个例子： Candidate1: I always invariably perpetually do. Candidate2: I always do. Reference1: I always do. Reference2: I invariably do. Reference3: I perpetually do. Candidate 1的召回率高于Candidate 2，但实际上译文质量不如Candidate 2 解决办法：不考虑召回率，而是简单地对太短的译文进行惩罚 ??? 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 BLEU Metric r/c corpus level r/c sentence level Bilingual evaluation understudy 因此，译文句子的相对于参考译文的长短，对翻译的精确率有很大的影响。 由于长的句子，在计算bigram匹配的时候，因为匹配是一次性匹配，也就是匹配上一次，便拿掉。因此，句子越长，匹配不上的可能性越大，因此自然又惩罚。 因此主要要考虑句子短的句子。 IBM的公式是这样的。 首先他搞一个系数。当句子长度大于参考译文的长度时，惩罚系数伟1，意味着不惩罚。 当局资长度小雨参考译文的长度时，惩罚系数是， BLEU指就是指翻译的评价指， 是unigram, bigram, trigram, N-gram 平价值的几何平均值。然后加上一个根句长有关的惩罚系数。 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 BLEU: An Example 此投影片引自微软亚洲研究院周明博士的一个报告，特此声明并感谢！ Candidate 1: the book is on the desk Reference 1: there is a book on the desk Reference 2: the book is on the table unigram: bigram: trigram: 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 实验：人工译文和机器译文的比较 Compare a human translator and a standard translation system. For 127 sentences, each sentences have 4 references It appears that single n-gram precision score can distinguish between good translation and a bad translation. 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 实验：多个人工译文和机器译文的比较 Compare 2 human translators and 3 standard translation systems. Distinguish better human translators from bad human translations; Distinguish better machine translations from bad machine translations; For 127 sentences, each sentences have 4 references Same rank order assigned to these systems by human judges. 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 BLEU与人工评测的一致性 Consistency表示一致性。具体来讲是与人的评价之间的一致性关系。 第一个试验，看单语专家打分和ｂｌｅｕ打分的一致性检验。用现行回归方法，可以看出两者的现行相关度很高。 第二个试验，看双语专家打分和ｂｌｅｕ打分的一性性检验。同样，可以看出两者的现行相关度很高。 结论：ｂｌｅｕ方法与专家的评价比较一致。 一元线性回归：从一个变量取得的值去估计另一个变量的取值 预测问题：在给定的置信度下，估计处当x取某一定值时，随即变量y的取值情况 The high of 0.99 indicates that BLEU tracks human judgment well. The correlation coefficient of bilingual is 0.96 The overall quality of the fit is then parameterized in terms of a quantity known as the correlation coefficient 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 N元语法方法的优缺点 优点 构造成本比较低，只需要普通翻译人员即可 在译文质量普遍不高的情况下，与人工评价的结果具有较好的拟合度 缺点 在译文质量较好的情况下，与人工评价的结果拟合度较差，因而这种方法不宜用于评价人工翻译的结果 就目前而言，用于进行机器翻译的系统评价还是适合的，而且起到了非常好的作用 机器翻译原理与方法(03) 基于词的统计机器翻译方法

机器翻译原理与方法(03) 基于词的统计机器翻译方法 讨论 在实际的双语语料库上运行Giza++进行句子对齐，并获得统计翻译模型参数 利用北京大学的切分标注语料库和SRI语言模型工具实现一个汉语语言模型 利用上述翻译模型和语言模型尝试编写一个基于词的解码算法，可以采用贪心算法或者堆栈搜索算法 机器翻译原理与方法(03) 基于词的统计机器翻译方法