统计机器翻译综述课件

NLP课题组例会报告 统计机器翻译简介刘群2002-12-6统计机器翻译简介刘群2002-12-6NLP课题组例会报告统计机器翻译方法的特点利用语料库作为知识来源l区别于规则方法：无需人工编写规则建立完整完整的统计模型l区别于实例方法或模板方法：必须为整个翻译过程建立统计模型2002-12-6统计机器翻译方法的特点利用语料库作为知识来源2002-12-NLP课题组例会报告统计机器翻译的分类基于平行概率语法的统计机器翻译模型基于信源信道思想的统计机器翻译模型lIBM的PeterBrown等人首先提出l目前影响最大l几乎成为统计机器翻译的同义词基于最大熵的统计机器翻译模型l源于基于特征的自然语言理解lOch提出，获ACL2002最佳论文2002-12-6统计机器翻译的分类基于平行概率语法的统计机器翻译模型2002NLP课题组例会报告统计机器翻译的优缺点优点l无需人工编写规则，利用语料库直接训练得到机器翻译系统；（但可以使用语言资源）l系统开发周期短；l鲁棒性好；l译文质量好；缺点l时空开销大；l数据稀疏问题严重；l对语料库依赖性强；l算法研究不成熟。2002-12-6统计机器翻译的优缺点优点2002-12-6NLP课题组例会报告基于平行概率语法的统计机器翻译模型基本思想l两种语言建立一套平行的语法规则，l规则一一对应l两套规则服从同样的概率分布l句法分析的过程决定了生成的过程主要模型lAlshawi的基于HeadTransducer的MT模型l吴德恺的InverseTransductionGrammar（ITG）lTakeda的Pattern-basedCFGforMT2002-12-6基于平行概率语法的统计机器翻译模型基本思想2002-12-6NLP课题组例会报告Head Transducer MT(1)HeadTransducer（中心词转录机）是一种DefiniteStateAutomata（有限状态自动机）与一般的有限状态识别器的区别：l每一条边上不仅有输入，而且有输出；l不是从左至右输入，而是从中心词往两边输入2002-12-6HeadTransducerMT(1)HeadTraNLP课题组例会报告Head Transducer MT(2)a:a 0:0 0:0 b:b a:a-1:+1 b:b-1:+1 例子：一个可以将任何a，b组成的串倒置的HeadTransducer2002-12-6HeadTransducerMT(2)a:a0:00NLP课题组例会报告Head Transducer MT(3)所有的语言知识（词典、规则）都表现为HeadTransducer；HeadTransducer可以嵌套：一个HeadTransducer的边是另一个的识别结果；纯统计的训练方法；对齐的结果是依存树：不使用词性和短语类标记；Chart句法分析器。2002-12-6HeadTransducerMT(3)所有的语言知识（词NLP课题组例会报告Inversion Transduction Grammar(1)比赛星期三开始。ThegamewillstartonWednesday。2002-12-6InversionTransductionGrammarNLP课题组例会报告Inversion Transduction Grammar(2)规则形式：lABClAlAx/y产生源语言和目标语言串分别为：lBCBC：词序相同lBCCB：词序交换lxy：词典2002-12-6InversionTransductionGrammarNLP课题组例会报告Pattern-based CFG for MT(1)每个翻译模板由一个源语言上下文无关规则和一个目标语言上下文无关规则（这两个规则称为翻译模板的骨架），以及对这两个规则的中心词约束和链接约束构成；举例：S:2 NP:1 岁:MP:2 了S:be NP:1 be year:NP:2 old2002-12-6Pattern-basedCFGforMT(1)每个NLP课题组例会报告Pattern-based CFG for MT(2)中心词约束：对于上下文无关语法规则中右部（子结点）的每个非终结符，可以指定其中心词；对于规则左部（父结点）的非终结符，可以直接指定其中心词，也可以通过使用相同的序号规定其中心词等于其右部的某个非终结符的中心词；链接约束：源语言骨架和目标语言骨架的非终结符子结点通过使用相同的序号建立对应关系，具有对应关系的非终结符互为翻译。2002-12-6Pattern-basedCFGforMT(2)中心NLP课题组例会报告信源信道模型假设目标语言文本T是由一段源语言文本S经过某种奇怪的编码得到的，那么翻译的目标就是要将T 还原成S，这也就是就是一个解码的过程。注意，源语言S是噪声信道的输入语言，目标语言T是噪声信道的输出语言，与整个机器翻译系统的源语言和目标语言刚好相反。P（S）P（TS）2002-12-6信源信道模型假设目标语言文本T是由一段源语言文本S经过某种NLP课题组例会报告统计机器翻译基本方程式P.Brown称上式为统计机器翻译基本方程式l语言模型：P(S)l翻译模型：P(T|S)语言模型反映“S像一个句子”的程度：流利度翻译模型反映“T像S”的程度：忠实度联合使用两个模型效果好于单独使用翻译模型，因为后者容易导致一些不好的译文。2002-12-6统计机器翻译基本方程式P.Brown称上式为统计机器翻译基本NLP课题组例会报告语言模型与翻译模型考虑汉语动词“打”的翻译：有几十种对应的英语词译文：打人，打饭，打鱼，打毛衣，打猎，打草稿，如果直接采用翻译模型，就需要根据上下文建立复杂的上下文条件概率模型如果采用信源信道思想，只要建立简单的翻译模型，可以同样达到目标词语选择的效果：l翻译模型：不考虑上下文，只考虑单词之间的翻译概率l语言模型：根据单词之间的同现选择最好的译文词2002-12-6语言模型与翻译模型考虑汉语动词“打”的翻译：有几十种对应的英NLP课题组例会报告统计机器翻译的三个问题三个问题：l语言模型P(S)的参数估计l翻译模型P(T|S)的参数估计l解码（搜索）算法2002-12-6统计机器翻译的三个问题三个问题：2002-12-6NLP课题组例会报告语言模型把一种语言理解成是产生一个句子的随机事件语言模型反映的是一个句子在一种语言中出现的概率语言模型lN元语法P(S)=p(s0)*p(s1|s0)*p(Sn|Sn-1Sn-N)l链语法：可以处理长距离依赖lPCFG（要使用句法标记）2002-12-6语言模型把一种语言理解成是产生一个句子的随机事件2002-1NLP课题组例会报告引入隐含变量：对齐A翻译模型与对齐P(T|S)的计算转化为P(T,A|S)的估计对齐：建立源语言句子和目标语言句子的词与词之间的对应关系2002-12-6引入隐含变量：对齐A翻译模型与对齐P(T|S)的计算转化为PNLP课题组例会报告IBM Model对P(T,A|S)的估计IBMModel1仅考虑词对词的互译概率IBMModel2加入了词的位置变化的概率IBMModel3加入了一个词翻译成多个词的概率IBMModel4IBMModel52002-12-6IBMModel对P(T,A|S)的估计2002-12-6NLP课题组例会报告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。最后，读出法语串，其概率为上述每一步概率的乘积。2002-12-6IBMModel3对于句子中每一个英语单词e，选择一个产NLP课题组例会报告翻译模型的参数训练ViterbiTraining（对比：EMTraining）1.给定初始参数；2.用已有的参数求最好（Viterbi）的对齐；3.用得到的对齐重新计算参数；4.回到第二步，直到收敛为止。IBMModel1：存在全局最优IBMModel25：不存在全局最优，初始值取上一个模型训练的结果2002-12-6翻译模型的参数训练ViterbiTraining（对比：ENLP课题组例会报告统计机器翻译的解码借鉴语音识别的搜索算法：堆栈搜索参数空间极大，搜索不能总是保证最优从错误类型看，只有两种：l模型错误：概率最大的句子不是正确的句子l搜索错误：没有找到概率最大的句子后一类错误只占总错误数的5%（IBM）搜索问题不是瓶颈2002-12-6统计机器翻译的解码借鉴语音识别的搜索算法：堆栈搜索2002-NLP课题组例会报告IBM公司的Candide系统 1基于统计的机器翻译方法分析转换生成l中间表示是线性的l分析和生成都是可逆的分析（预处理）：1.短语切分2.专名与数词检测3.大小写与拼写校正4.形态分析5.语言的归一化2002-12-6IBM公司的Candide系统1基于统计的机器翻译方法20NLP课题组例会报告IBM公司的Candide系统 2转换（解码）：基于统计的机器翻译解码分为两个阶段：l第一阶段：使用粗糙模型的堆栈搜索l输出140个评分最高的译文l语言模型：三元语法l翻译模型：EM算法l第二阶段：使用精细模型的扰动搜索l对第一阶段的输出结果先扩充，再重新评分l语言模型：链语法l翻译模型：最大熵方法2002-12-6IBM公司的Candide系统2转换（解码）：基于统计的机NLP课题组例会报告IBM公司的Candide系统 3ARPA的测试结果：FluencyFluencyAdequacyAdequacyTime RatioTime Ratio199219921993199319921992199319931992199219931993SystranSystran.466.466.540.540.686.686.743.743CandideCandide.511.511.580.580.575.575.670.670TransmanTransman.819.819.838.838.837.837.850.850.688.688.625.625ManualManual.833.833.840.8402002-12-6IBM公司的Candide系统3ARPA的测试结果：FNLP课题组例会报告JHU的1999年夏季研讨班由来lIBM的实验引起了广泛的兴趣lIBM的实验很难重复：工作量太大目的l构造一个统计机器翻译工具（EGYPT）并使它对于研究者来说是可用的（免费传播）；l在研讨班上用这个工具集构造一个捷克语英语的机器翻译系统；l进行基准评价：主观和客观；l通过使用形态和句法转录机改进基准测试的结果；l在研讨班最后，在一天之内构造一个新语对的翻译器。JHU夏季研讨班大大促进了统计机器翻译的研究2002-12-6JHU的1999年夏季研讨班由来2002-12-6NLP课题组例会报告EGYPT工具包EGYPT的模块1.GIZA：这个模块用于从双语语料库中抽取统计知识（参数训练）2.Decoder：解码器，用于执行具体的翻译过程（在信源信道模型中，“翻译”就是“解码”）3.Cairo：整个翻译系统的可视化界面，用于管理所有的参数、查看双语语料库对齐的过程和翻译模型的解码过程4.Whittle：语料库预处理工具EGYPT可在网上免费下载，成为SMT的基准2002-12-6EGYPT工具包EGYPT的模块2002-12-6NLP课题组例会报告EGYPT工具包的性能“当解码器的原形系统在研讨班上完成时，我们很高兴并惊异于其速度和性能。1990年代早期在IBM公司举行的DARPA机器翻译评价时，我们曾经预计只有很短（10个词左右）的句子才可以用统计方法进行解码，即使那样，每个句子的解码时间也可能是几个小时。在早期IBM的工作过去将近10年后，摩尔定律、更好的编译器以及更加充足的内存和硬盘空间帮助我们构造了一个能够在几秒钟之内对25个单词的句子进行解码的系统。为了确保成功，我们在搜索中使用了相当严格的阈值和约束，如下所述。但是,解码器相当有效这个事实为这个方向未来的工作预示了很好的前景，并肯定了IBM的工作的初衷，即强调概率模型比效率更重要。”引自JHU统计机器翻译研讨班的技术报告2002-12-6EGYPT工具包的性能“当解码器的原形系统在研NLP课题组例会报告对IBM方法的改进IBM方法的问题l不考虑结构：能否适用于句法结构差别较大的语言？l数据稀疏问题严重后续的改进工作l王野翊的改进lYamada和Knight的改进lOch等人的改进2002-12-6对IBM方法的改进IBM方法的问题2002-12-6NLP课题组例会报告王野翊的改进(1)背景：德英口语翻译系统l语法结构差异较大l数据稀疏（训练数据有限）改进：两个层次的对齐模型l粗对齐：短语之间的对齐l细对齐：短语内词的对齐2002-12-6王野翊的改进(1)背景：德英口语翻译系统2002-12-6NLP课题组例会报告王野翊的改进(2)文法推导l词语聚类：基于互信息的方法l短语归并l规则学习优点l机器翻译的正确率提高：错误率降低了11%l提高了整个系统的效率：搜索空间更小l缓解了因口语数据缺乏导致的数据稀疏问题2002-12-6王野翊的改进(2)文法推导2002-12-6NLP课题组例会报告Yamada和Knight的改进(1)基于语法的翻译模型（Syntax-basedTM）：l输入是源语言句法树l输出是目标语言句子翻译的过程：l每个内部结点的子结点随机地重新排列：排列概率l在每一个结点的左边或右边随机插入一个单词l左、右插入和不插入的概率取决于父结点和当前结点标记l插入哪个词的概率只与被插入词有关，与位置无关 l对于每一个叶结点进行翻译：词对词的翻译概率l输出译文句子2002-12-6Yamada和Knight的改进(1)基于语法的翻译模型（SNLP课题组例会报告Yamada和Knight的改进(2)2002-12-6Yamada和Knight的改进(2)2002-12-6NLP课题组例会报告Yamada和Knight的改进(3)2002-12-6Yamada和Knight的改进(3)2002-12-6NLP课题组例会报告Yamada和Knight的改进(4)2002-12-6Yamada和Knight的改进(4)2002-12-6NLP课题组例会报告Yamada和Knight的改进(5)训练l英日词典例句2121对，平均句长日9.7和英6.9l词汇量：英语3463，日语3983，大部分词只出现一次lBrillsPOSTagger和CollinsParserl用中心词词性标记取得短语标记l压扁句法树：中心词相同的句法子树合并lEM训练20遍迭代：IBMModel5用20遍迭代2002-12-6Yamada和Knight的改进(5)训练2002-12-6NLP课题组例会报告Yamada和Knight的改进(6)困惑度Perplexity：OurModel：15.70IBMModel：9.84(Over-fitting)Alignmentave.scorePerfectsentsOurModel0.58210IBMModel50.4310结果2002-12-6Yamada和Knight的改进(6)困惑度PerplexiNLP课题组例会报告Och等人的改进(1)著名语音翻译系统VerbMobil的一个模块对IBM方法的改进l基于类的模型：词语自动聚类：各400个类l语言模型：基于类的五元语法，回退法平滑l翻译模型：基于对齐模板的方法l短语层次对齐l词语层次对齐l短语划分：动态规划2002-12-6Och等人的改进(1)著名语音翻译系统VerbMobil的一NLP课题组例会报告Och等人的改进(2)对齐模板2002-12-6Och等人的改进(2)对齐模板2002-12-6NLP课题组例会报告基于最大熵的统计机器翻译模型(1)Och等人提出，思想来源于Papineni提出的基于特征的自然语言理解方法不使用信源信道思想，直接使用统计翻译模型，因此是一种直接翻译模型是一个比信源信道模型更具一般性的模型，信源信道模型是其一个特例与一般最大熵方法的区别：使用连续量作为特征2002-12-6基于最大熵的统计机器翻译模型(1)Och等人提出，思想来源NLP课题组例会报告基于最大熵的统计机器翻译模型(2)假设e、f是机器翻译的目标语言和源语言句子，h1(e,f),hM(e,f)分别是e、f上的M个特征，1,M是与这些特征分别对应的M个参数，那么直接翻译概率可以用以下公式模拟：2002-12-6基于最大熵的统计机器翻译模型(2)假设e、f是机器翻译的目NLP课题组例会报告基于最大熵的统计机器翻译模型(3)对于给定的f，其最佳译文e可以用以下公式表示：2002-12-6基于最大熵的统计机器翻译模型(3)对于给定的f，其最佳译文NLP课题组例会报告基于最大熵的统计机器翻译模型(4)取以下特征和参数时等价于信源信道模型：l仅使用两个特征lh1(e,f)=log p(e)lh2(e,f)=log p(f|e)l121 2002-12-6基于最大熵的统计机器翻译模型(4)取以下特征和参数时等价于NLP课题组例会报告基于最大熵的统计机器翻译模型(5)参数训练最优化后验概率准则：区别性训练这个判断准则是凸的，存在全局最优考虑多个参考译文：2002-12-6基于最大熵的统计机器翻译模型(5)参数训练最优化后验概率准NLP课题组例会报告基于最大熵的统计机器翻译模型(6)Och等人的实验(1)：方案l首先将信源信道模型中的翻译模型换成反向的翻译模型，简化了搜索算法，但翻译系统的性能并没有下降；l调整参数1和2，系统性能有了较大提高；l再依次引入其他一些特征，系统性能又有了更大的提高。2002-12-6基于最大熵的统计机器翻译模型(6)Och等人的实验(1)：NLP课题组例会报告基于最大熵的统计机器翻译模型(7)Och等人的实验(2)：其他特征l句子长度特征(WP)：对于产生的每一个目标语言单词进行惩罚；l附件的语言模型特征(CLM)：一个基于类的语言模型特征；l词典特征(MX)：计算给定的输入输出句子中有多少词典中存在的共现词对。2002-12-6基于最大熵的统计机器翻译模型(7)Och等人的实验(2)：NLP课题组例会报告基于最大熵的统计机器翻译模型(8)Och等人的实验(2)：实验结果2002-12-6基于最大熵的统计机器翻译模型(8)Och等人的实验(2)：NLP课题组例会报告基于最大熵的统计机器翻译模型(9)经典的信源信道模型只有在理想的情况下才能达到最优，对于简化的语言模型和翻译模型，取不同的参数值实际效果更好；最大熵方法大大扩充了统计机器翻译的思路；特征的选择更加灵活。2002-12-6基于最大熵的统计机器翻译模型(9)经典的信源信道模型只有NLP课题组例会报告统计机器翻译的应用传统机器翻译的应用领域跨语言检索l聂建云使用IBMModel1进行CLIR机器翻译系统的快速开发l针对未知语言l快速开发2002-12-6统计机器翻译的应用传统机器翻译的应用领域2002-12-6NLP课题组例会报告总结IBM当年的工作是有一定超前性的虽然很多人怀疑统计方法在机器翻译中能否取得成功，但现在这已不再是问题基于平行语法的机器翻译方法总体上不成功基于最大熵的方法为统计机器翻译方法开辟了一个新天地2002-12-6总结IBM当年的工作是有一定超前性的2002-12-6NLP课题组例会报告我的工作设想采用基于最大熵的统计机器翻译模型；提出基于模板的统计翻译模型：l句法树对齐l抽取翻译模板l基于模板翻译模型其它特征l汉语词法分析l汉语句法分析2002-12-6我的工作设想采用基于最大熵的统计机器翻译模型；2002-12NLP课题组例会报告参考文献(1)Al-Onaizan1999YaserAl-Onaizan,JanCurin,MichaelJahr,KevinKnight,JohnLafferty,DanMelamed,Franz-JosefOch,DavidPurdy,NoahA.SmithandDavidYarowsky(1999).Statistical Machine Translation:Final Report,Johns HopkinsUniversity1999SummerWorkshoponLanguageEngineering,CenterforSpeechandLanguageProcessing,Baltimore,MD.Alshawi1998Alshawi,H.,Bangalore,S.andDouglas,S.AutomaticAcquisitionof Hierarchical transduction models for machine translation,Proc.36th Conf.AssociationofComputationalLinguistics,Montreal,Canada,1998.Berger1994Berger,A.,P.Brown,S.DellaPietra,V.DellaPietra,J.Gillett,J.Lafferty,R.Mercer,H.Printz,LUres,TheCandideSystemforMachineTranslation,ProceedingsoftheDARPAWorkshoponHumanLanguageTechnology(HLT)Berger1996A.L.Berger,S.A.DellaPietra,andV.J.DellaPietra.Amaximumentropy approach to natural language processing.Computational Linguistics,22(1):39-72,March1996.Brown1990PeterF.Brown,JohnCocke,StephenA.DellaPietra,VincentJ.DellaPietra,Fredrick Jelinek,John D.Lafferty,Robert L.Mercer,Paul S.Roossin,AStatisticalApproachtoMachineTranslation,ComputationalLinguistics,19902002-12-6参考文献(1)Al-Onaizan1999YaserNLP课题组例会报告参考文献(2)Brown1993Peter.F.Brown,StephenA.DellaPietra,VincentJ.DellaPietra,RobertL.Mercer,TheMathematicsofStatisticalMachineTranslation:ParameterEstimation,ComputationalLinguistics,Vol19,No.2,1993 Ker 1997 Sue J.Ker,Jason S.Chang,A Class-based Approach to WordAlignment,ComputationalLinguistics,Vol.23,No.2,Page313-343,1997Knight1999KevinKnight,AStatisticalMachineTranslationTutorialWorkbook.unpublished,prepared in connection with the JHU summer workshop,August1999.(availableathttp:/www.clsp.jhu.edu/ws99/projects/mt/wkbk.rtf).Och 1998 Franz Josef Och and Hans Weber.Improving statistical naturallanguagetranslationwithcategoriesandrules.InProc.Ofthe35thAnnualConf.of the Association for Computational Linguistics and the 17th Int.Conf.onComputationalLinguistics,pages985-989,Montreal,Canada,August1998.Och1999F.J.Och,C.Tillmann,andH.Ney.Improvedalignmentmodelsforstatisticalmachinetranslation.InProc.oftheJointSIGDATConf.OnEmpiricalMethodsinNaturalLanguageProcessingandVeryLargeCorpora,pages20-28,UniversityofMaryland,CollegePark,MD,June1999.2002-12-6参考文献(2)Brown1993Peter.F.NLP课题组例会报告参考文献(3)Och2001FranzJosefOch,HermannNey.WhatCanMachineTranslationLearnfrom Speech Recognition?In:proceedings of MT 2001 Workshop:Towards aRoadMapforMT,pp.26-31,SantiagodeCompostela,Spain,September2001.Och2002FranzJosefOch,HermannNey,DiscriminativeTrainingandMaximumEntropyModelsforStatisticalMachineTranslation,ACL2002Papineni1997K.A.Papineni,S.Roukos,andR.T.Ward.1997.Feature-basedlanguage understanding.In European Conf.on Speech Communication andTechnology,pages1435-1438,Rhodes,Greece,September.Papineni 1998 K.A.Papineni,S.Roukos,and R.T.Ward.1998.Maximumlikelihoodanddiscriminativetrainingofdirecttranslationmodels.InProc.Int.Conf.onAcoustics,Speech,andSignalProcessing,pages189-192,Seattle,WA,May.Takeda1996KoichiTakeda,Pattern-BasedContext-FreeGrammarsforMachineTranslation,Proc.of34thACL,pp.144-151,June1996Wang 1998a Y.Wang and A.Waibel.Modeling with Structures in StatisticalMachineTranslation.InProceedingsofthe36thAnnualMeetingoftheAssociationforComputationalLinguisticsand17thInternationalConferenceonComputationalLinguisticsMontreal,Canada.August1998.2002-12-6参考文献(3)Och2001FranzJosefNLP课题组例会报告参考文献(4)Wang 1998b Ye-Yi Wang,Grammar Inference and Statistical MachineTranslation,Ph.DThesis,CarnegieMellonUniversity,1998Wu 1995 Dekai Wu.Stochastic Inversion Transduction Grammars,withApplicationtoSegmentation,Bracketing,andAlignmentofParallelCorpora.14thIntl.JointConf.OnAtificalIntelligence,pp1328-1335,Montreal,Aug,1995.IJCAI-95Wu1997DekaiWu,StochasticInversionTransductionGrammarsandBilingualParsingofParallelCorpora,ComputationalLinguisticsVol.23No.31997.Yamada2001K.YamadaandK.Knight,ASyntax-BasedStatisticalTranslationModel,inProc.oftheConferenceoftheAssociationforComputationalLinguistics(ACL),20012002-12-6参考文献(4)Wang1998bYe-YiWangNLP课题组例会报告谢谢2002-12-6谢谢2002-12-6