搜索
机器翻译原理与方法第三讲基于词的统计机器翻译方法中国科学院计算技术研究所2008-2009年度秋季课程刘群中国科学院计算技术研究所liuqun@ict.ac.cn机器翻译原理与方法讲义(02)机器翻译方法2内容提要•为翻译建立概率模型•IBM的信源信道模型•语言模型––n元语法模型•翻译模型––IBM模型1-5•词语对齐算法•解码算法•Candide系统•Egypt工具包与Giza++•机器翻译自动评价机器翻译原理与方法讲义(02)机器翻译方法3为翻译建立概率模型•假设任意一个英语句子e和一个法语句子f，我们定义f翻译成e的概率为：Pr(|)ef其归一化条件为：Pr(|)1=∑eef•于是将f翻译成e的问题就变成求解问题：ˆ=argmaxPr(|)eeef机器翻译原理与方法讲义(02)机器翻译方法4内容提要•为翻译建立概率模型•IBM的信源信道模型•语言模型––n元语法模型•翻译模型––IBM模型1-5•词语对齐算法•解码算法•Candide系统•Egypt工具包与Giza++•机器翻译自动评价机器翻译原理与方法讲义(02)机器翻译方法5信源信道模型(1)•信源信道模型又称噪声信道模型，是由IBM公司的PeterF.Brown等人于1990年提出来的：PeterF.Brown,JohnCocke,StephenA.DellaPietra,VincentJ.DellaPietra,FredrickJelinek,JohnD.Lafferty,RobertL.Mercer,PaulS.Roossin,AStatisticalApproachtoMachineTranslation,ComputationalLinguistics,1990机器翻译原理与方法讲义(02)机器翻译方法6信源信道模型(2)•假设我们看到的源语言文本F是由一段目标语言文本E经过某种奇怪的编码得到的，那么翻译的目标就是要将F还原成E，这也就是就是一个解码的过程。•注意，在信源信道模型中：–噪声信道的源语言是翻译的目标语言–噪声信道的目标语言是翻译的源语言这与整个机器翻译系统翻译方向的刚好相反EP（E）P（F｜E）F机器翻译原理与方法讲义(02)机器翻译方法7统计机器翻译基本方程式•P.Brown称上式为统计机器翻译基本方程式–语言模型：P(E)–翻译模型：P(F|E)•语言模型反映“E像一个句子”的程度：流利度•翻译模型反映“F像E”的程度：忠实度•联合使用两个模型效果好于单独使用翻译模型，因为后者容易导致一些不好的译文。)E|F()E(maxargEEPP=机器翻译原理与方法讲义(02)机器翻译方法8语言模型与翻译模型•考虑汉语动词“打”的翻译：有几十种对应的英语词译文：打人，打饭，打鱼，打毛衣，打猎，打草稿，……•如果直接采用翻译模型，就需要根据上下文建立复杂的上下文条件概率模型•如果采用信源－信道思想，只要建立简单的翻译模型，可以同样达到目标词语选择的效果：–翻译模型：不考虑上下文，只考虑单词之间的翻译概率–语言模型：根据单词之间的同现选择昀好的译文词机器翻译原理与方法讲义(02)机器翻译方法9统计机器翻译的三个问题•三个问题：–语言模型P(E)的建模和参数估计–翻译模型P(F|E)的建模和参数估计–解码（搜索）算法机器翻译原理与方法讲义(02)机器翻译方法10内容提要•为翻译建立概率模型•IBM的信源信道模型•语言模型––n元语法模型•翻译模型––IBM模型1-5•词语对齐算法•解码算法•Candide系统•Egypt工具包与Giza++•机器翻译自动评价机器翻译原理与方法讲义(02)机器翻译方法11语言模型•统计语言模型把一种语言理解成是产生一个句子的随机事件。在统计语言模型看来，对于一种语言，任何一个句子都是可以接受的，只是接受的可能性（概率）不同•语言模型给出任何一个句子的出现概率：Pr(E=e1e2…en)归一化条件：ΣEPr(E)=1•统计语言模型实际上就是一个概率分布，它给出了一种语言中所有可能的句子的出现概率机器翻译原理与方法讲义(02)机器翻译方法12语言模型的类型•理论上，单词串的任何一种概率分布，都是一个语言模型。•实际上，N元语法模型是昀简单也是昀常见的语言模型。•N元语法模型由于没有考虑任何语言内部的结构信息，显然不是理想的语言模型。•其他语言模型：–隐马尔科夫模型（HMM）（加入词性标记信息）–概率上下文无关语法（PCFG）（加入短语结构信息）–概率链语法（ProbabilisticLinkGrammar）（加入链语法的结构信息）•目前为止，其他形式的语言模型效果都不如N元语法模型•统计机器翻译研究中开始有人尝试基于句法的语言模型机器翻译原理与方法讲义(02)机器翻译方法13N元语法模型－概念辨析•N元语法模型：N-GramModel。•所谓N-Gram，指的是由N个词组成的串，可以称为“N元组”，或“N元词串”。•基于N-Gram建立的语言模型，称为“N元语法模型(N-GramModel)”。•Gram不是Grammar的简写。在英文中，并没有N-Grammar的说法。•在在汉语中，单独说“N元语法”的时候，有时指“N元组(N-Gram)”，有时指“N元语法模型(N-GramModel)”，请注意根据上下文加以辨别。机器翻译原理与方法讲义(02)机器翻译方法14N元语法模型－定义•N元语法模型（N-gramModel）∏∏=−+−+−=−≈=niiNiNiiniii)...|()...|()(•假设：单词wi出现的概率只与其前面的N-1个单词有关机器翻译原理与方法讲义(02)机器翻译方法15N元语法模型－举例•N=1时：一元语法模型–相当于词频表，给出所有词出现的频率•N=2时：二元语法模型–相当于一个转移矩阵，给出每一个词后面出现另一个词的概率•N=3时：三元语法模型–相当于一个三维转移矩阵，给出每一个词对儿后面出现另一个词的概率•在自然语言处理中，N元语法模型可以在汉字层面，也可以在单词层面，还可以在概念层面……机器翻译原理与方法讲义(02)机器翻译方法16二元语法模型－图示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机器翻译原理与方法讲义(02)机器翻译方法17袋子模型BagModel(1)•将一个英语句子中所有的单词放入一个袋子中•用N元语法模型试图将其还原–对于这些单词的任何一种排列顺序根据N元语法模型计算其出现概率–取概率昀大的排列方式机器翻译原理与方法讲义(02)机器翻译方法18袋子模型BagModel(2)•实验：取38个长度小于11个单词的英语句子，实验结果如下：机器翻译原理与方法讲义(02)机器翻译方法19内容提要•为翻译建立概率模型•IBM的信源信道模型•语言模型––n元语法模型•翻译模型––IBM模型1-5•词语对齐算法•解码算法•Candide系统•Egypt工具包与Giza++•机器翻译自动评价机器翻译原理与方法讲义(02)机器翻译方法20翻译模型•翻译模型P(F|E)反映的是一个源语言句子E翻译成一个目标语言句子F的概率•由于源语言句子和目标语言句子几乎不可能在语料库中出现过，因此这个概率无法直接从语料库统计得到，必须分解成词语翻译的概率和句子结构（或者顺序）翻译的概率机器翻译原理与方法讲义(02)机器翻译方法21•翻译模型的计算，需要引入隐含变量：对齐A：翻译模型与对齐∑=APP)E|A,F()E|F(•翻译概率P(F|E)的计算转化为对齐概率P(F,A|E)的估计•对齐：建立源语言句子和目标语言句子的词与词之间的对应关系和句子结构之间的对应关系机器翻译原理与方法讲义(02)机器翻译方法22词语对齐的表示(1)中国十四个边境开放城市经济建设成就显著China’s14openboardcitiesmarkedeconomicachievement1234567891,2335468997z图形表示9连线9矩阵（见下页）z数字表示9给每个目标语言单词标记其所有对应的源语言单词机器翻译原理与方法讲义(02)机器翻译方法23词语对齐的表示(2)achievementeconomicmarkedcitiesboardopen14‘sChina中国十四个边境开放城市经济建设成就显著机器翻译原理与方法讲义(02)机器翻译方法24IBMModel•对P(F,A|E)的估计•IBMModel1仅考虑词对词的互译概率•IBMModel2加入了词的位置变化的概率•IBMModel3加入了一个词翻译成多个词的概率•IBMModel4•IBMModel5机器翻译原理与方法讲义(02)机器翻译方法25IBMModel1&2推导方式(1)IBM模型1&2的推导过程：1.猜测目标语言句子长度；2.从左至右，对于每个目标语言单词：–首先猜测该单词由哪一个源语言单词翻译而来；–再猜测该单词应该翻译成什么目标语言词。am2I1我一a3student4学生个是源语言句子E：目标语言句子F：词语对齐A：12334机器翻译原理与方法讲义(02)机器翻译方法26IBMModel1&2推导方式(2))E,,,|Pr()E,,,|Pr()E|Pr()E|A,FPr(11111111mfafmfaamjjmjjjjj−=−−∏=注意：在IBMModel中，词语对齐只考虑了源语言到目标语言的单向一对多形式，不考虑多对一和多对多的形式。假设翻译的目标语言句子为:mmffff211F==假设翻译的源语言句子为:lleeee211E==假设词语对齐表示为:},,0{},,,1{,A211lamiaaaaimm∈∈∀==那么词语对齐的概率可以表示为:机器翻译原理与方法讲义(02)机器翻译方法27IBMModel1的推导(1)假设所有翻译长度都是等概率的：ε=)E|Pr(m假设词语对齐只与源语言长度有关，与其他因素无关：11)E,,,|Pr(1111+=−−lmfaajjj假设目标词语的选择只与其对应的源语言词语有关，与其他因素无关：)|()E,,,|Pr(111jajjjjeftmfaf=−机器翻译原理与方法讲义(02)机器翻译方法28IBMModel1的推导(2)∏=+=mjajmjeftl1)|()1()E|A,FPr(ε那么对齐概率可以表示为:对所有可能的对齐求和，那么翻译概率就可以表示为:∑∑∏∑===+==lalamjajmmjeftl111A1)|()1()E|AF,Pr()E|FPr(ε这就是IBMModel1的翻译模型公式。也就是说，给定参数t(f|e)，我们就可以计算出句子E翻译成句子F的概率。机器翻译原理与方法讲义(02)机器翻译方法29IBMModel1的参数求解(1)•在IBMModel1中，ε是个常数，无关紧要，起重要作用的就是单词翻译概率分布：)|(eft•这个单词翻译概率分布表现为一个翻译概率表，这个表给出了每一个源语言单词翻译成任何一个目标语言单词的概率，并且这个概率满足归一性约束条件：1)|(=∑feft机器翻译原理与方法讲义(02)机器翻译方法30IBMModel1的参数求解(2)•根据昀大似然估计，我们希望得到一组概率分布，使得我们的训练语料库出现的概率昀大。•也就是说，给定训练语料库E和F，我们要求解一个概率分布t(f|e)，使得翻译概率Pr(F|E)昀大。•这是一个受约束的极值问题，约束条件即是t(f|e)的归一性条件。•为了求解这个问题，我们需要引入拉格朗日乘子，构造一个辅助函数，将上述受约束的极值问题转换成一个不受约束的极值问题。机器翻译原理与方法讲义(02)机器翻译方法31IBMModel1的参数求解(3)•引入拉格朗日乘子λe，构造辅助函数如下：∑∑∑∑∏−−+≡===efelalamjajmefteftlthmj)1)|(()|()1(),(1111λελ•将上述函数对t(f|e)求导得到：1111(|)(,)(,)(,)(|)(1)t(|)kjmmkallkjaemaatf