机器翻译原理与方法讲义(05)基于句法的统计机器翻译方法

机器翻译原理与方法第五讲基于句法的统计机器翻译方法刘群中国科学院计算技术研究所[e-mail]中国科学院计算技术研究所2009年秋季课程2机器翻译原理与方法(05)基于句法的机器翻译方法内容提要•概述•同步语法概念•反向转录语法和括号转录语法•基于最大熵括号转录语法的翻译模型•同步上下文无关语法和同步树替换语法•层次短语模型•树到串翻译模型•串到树翻译模型•总结3机器翻译原理与方法(05)基于句法的机器翻译方法概述•基于短语的统计翻译方法的问题•基于句法的统计翻译方法的分类•目前的进展4机器翻译原理与方法(05)基于句法的机器翻译方法基于短语的统计翻译方法的问题•泛化能力差–中国大使馆、美国大使馆→月球大使馆？•产生的句子不符合语法–短语的简单组合，没有句法结构•无法表示不连续的短语搭配的翻译–召开了一次关于…的会议holdameetingon…•无法进行长距离的语序调整•解决办法：引入句法结构！5机器翻译原理与方法(05)基于句法的机器翻译方法统计机器翻译方法的金字塔Syntax-basedPhrase-basedSemantic-basedInterlinguaWord-basedSourceLanguageTargetLanguage6机器翻译原理与方法(05)基于句法的机器翻译方法基于句法的统计机器翻译模型(1)syntaxlevelphraselevel7机器翻译原理与方法(05)基于句法的机器翻译方法基于句法的统计机器翻译模型(1)linguisticsyntaxlevelformalsyntaxlevelphraselevel8机器翻译原理与方法(05)基于句法的机器翻译方法基于句法的统计机器翻译模型(1)phrase-basedmodelformallysyntax-basedmodellinguisticallysyntax-basedmodelstring-to-treemodeltree-to-stringmodeltree-to-treemodel9机器翻译原理与方法(05)基于句法的机器翻译方法基于句法的统计机器翻译模型(2)•形式上基于句法的模型–不使用任何语言学知识–所有句法结构直接从未标注的语料库中自动学习得到•语言学上基于句法的模型–使用语言学知识–语言通常要从句法树库训练得到•树到串模型：只在源语言端使用语言知识•串到树模型：只在目标语言端使用语言知识•树到树模型：在源语言端和目标语言端都使用语言知识10机器翻译原理与方法(05)基于句法的机器翻译方法形式上基于句法的模型•反向转录语法（ITG）和括号转录语法（BTG）Inversion(Bracketing)TransductionGrammar(ITG,BTG),Wu1997•有限状态中心词转录机Finite-StateHeadTransducer,Alshawi2000•基于层次短语的翻译模型HierarchicalPhrase-basedModel,Chiang2005•最大熵括号转录语法的翻译模型MaximalEntropyBracketTransductionGrammar(ME-BTG),Xiong200611机器翻译原理与方法(05)基于句法的机器翻译方法语言学上基于句法的模型•串到树模型String-to-TreeModel–美国南加州大学信息科学研究所（ISI/CSU）的工作Yamada2001,Galley2006,Marcu2006•树到串模型Tree-to-StringModel–中科院计算所的工作Tree-to-stringAlignmentTemplateModel(TAT),YangLiuACL2006–微软研究院的工作（依存模型）DependencyTreeletTranslation,Quirk2005•树到树的模型Tree-to-TreeModel12机器翻译原理与方法(05)基于句法的机器翻译方法内容提要•概述•同步语法概念•反向转录语法和括号转录语法•基于最大熵括号转录语法的翻译模型•同步上下文无关语法和同步树替换语法•层次短语模型•树到串翻译模型•串到树翻译模型•总结13机器翻译原理与方法(05)基于句法的机器翻译方法同步语法(1)•定义：同步语法是一种形式语法，这种语法的每一次推导，都在两种或者两种以上语言中同步生成一个句子。同步语法IWeWeareChineseChinaisthecountrywiththelargestpopulationintheworld……我我们我们是中国人中国是世界上人口最多的国家……14机器翻译原理与方法(05)基于句法的机器翻译方法同步语法(2)•同步语法的具体形式：–同步上下文无关语法（SCFG）•反向转录语法(ITG)和括号转录语法(BTG)–同步树替换语法(STSG)–同步树粘接语法(STAG)–多文本语法(MTG)•同步语法的应用：–编译中的代码生成–自然语言的语义解释–自然语言的机器翻译–双语语料库的对齐15机器翻译原理与方法(05)基于句法的机器翻译方法同步语法(3)•同步语法与统计机器翻译–同步语法是很多基于句法的统计机器翻译模型的理论基础–理论上说，如果采用同步语法，在完成源语言句法分析的同时，目标语言就生成了，因此可以利用各种成熟的句法分析算法进行机器翻译，而无需另外设计专门的翻译算法–另一方面，采用同步语法对源语言进行句法分析时，要把目标语言的因素考虑进来，这不同于通常的句法分析16机器翻译原理与方法(05)基于句法的机器翻译方法内容提要•概述•同步语法概念•反向转录语法和括号转录语法•基于最大熵括号转录语法的翻译模型•同步上下文无关语法和同步树替换语法•层次短语模型•树到串翻译模型•串到树翻译模型•总结17机器翻译原理与方法(05)基于句法的机器翻译方法反向转录语法•InversionTransductionGrammar(ITG)吴德凯(1997onwards)•ITG是一种形式最简单的同步语法，可以并行地生成两颗对齐的句法树–ITG的规则都是乔姆斯基范式形式的•规则的右部或者全部是终结符，或者全部是终结符•非终结符规则都是二分的–ITG的规则可以指定语序的变化：保序或逆序–ITG中两种语言的规则使用同一套非终结符•ITG中对规则的二分限制降低了搜索的复杂度18机器翻译原理与方法(05)基于句法的机器翻译方法反向转录语法ITGrulesSourceTarget终结符规则非符A→[BC]A→BCA→BCA→BCA→BCA→CB终结规则符A→x/yA→xA→y.开始BVPSSBNPPPVPThe/egame/比赛will/estart/on/e/Wednesday星期三./。targetsourcestraightinverted19机器翻译原理与方法(05)基于句法的机器翻译方法反向转录语法20机器翻译原理与方法(05)基于句法的机器翻译方法基于反向转录语法的统计机器翻译(1)•训练：从词语对齐的语料库中自动抽取规则•解码：类似于一个概率化句法分析的过程–利用规则的源语言部分进行句法分析•存在源语言部分相同而目标语言部分不同的规则（保序或逆序），这是不同于传统句法分析的地方•句法分析时，对于源语言部分相同而目标语言部分不同的规则，需要通过概率计算进行评分，这相当于对译文语序进行选择–句法分析完成的同时也就生成了译文句法结构和译文句子21机器翻译原理与方法(05)基于句法的机器翻译方法基于反向转录语法的统计机器翻译(2)22机器翻译原理与方法(05)基于句法的机器翻译方法基于反向转录语法的统计机器翻译(3)23机器翻译原理与方法(05)基于句法的机器翻译方法括号转录语法•BracketingTransductionGrammar：BTG•BTG是ITG的一个特例，其中只有唯一的一个非终结符X•可以这么理解：BTG仅仅给出了两种语言的句子结构结构之间的对应关系，没有任何句法标记信息（如NP、VP等等）24机器翻译原理与方法(05)基于句法的机器翻译方法统计机器翻译中语序调整的方式•无约束（所有匹配都运行）–所有语序调整都是允许的–对于N个词（或短语），在IBM约束下，语序调整有N!种可能性，搜索空间随着句子长度呈指数级增长，因此其搜索问题是NP问题•IBM约束（IBMConstrains）–为了减少搜索空间，通常在从左到右的解码过程中都会采用IBM约束来限制语序调整的搜索空间，也就是说，每次只选择最左边若干个未被翻译的词语进行翻译（对Hypothesis进行扩展）–IBM约束可以大大减少搜索空间，但依然存在大量非法语序调整•BTG约束（BTGConstrains）–只有能够满足某种BTG映射的语序调整才是允许的–BTG约束大大降低了搜索空间大小，确保搜索范围内的语序调整都满足语法约束，同时不在搜索范围内的约束都不满足语法约束–BTG约束搜索使得长距离语序调整成为可能25机器翻译原理与方法(05)基于句法的机器翻译方法这里给出了四个词的所有可能的调序方案以及对应的BTG转换模式。其中有两种方案在BTG约束下是不允许的（找不到对应的BTG转换模式）26机器翻译原理与方法(05)基于句法的机器翻译方法BTG约束导致搜索空间大大压缩wordreorderingwhicharenotpermittedinBTG27机器翻译原理与方法(05)基于句法的机器翻译方法真实自然语言的翻译满足BTG约束吗？对于汉语和英语之间的翻译，几乎满足一个例外（出处？）:对于一些自由语序的语言，不一定满足28机器翻译原理与方法(05)基于句法的机器翻译方法内容提要•概述•同步语法概念•反向转录语法和括号转录语法•基于最大熵括号转录语法的翻译模型•同步上下文无关语法和同步树替换语法•层次短语模型•树到串翻译模型•串到树翻译模型•总结29机器翻译原理与方法(05)基于句法的机器翻译方法基于最大熵括号转录语法的翻译模型•基于最大熵括号转录语法的翻译模型ATranslationModelBasedonMaximumEntropyBracketingTransuctionGrammar(ME-BTG)•DeyiXiong,QunLiu,andShouxunLin.MaximumEntropyBasedPhraseReorderingModelforStatisticalMachineTranslation.COLING-ACL2006,Sydney,Australia,July17-21.•DeyiXiong,MinZhang,AiTiAw,HaitaoMi,QunLiuandShouxunLin,RefinementsinBTG-basedStatisticalMachineTranslation,IJCNLP2008,Hyderabad,India,January7-1230机器翻译原理与方法(05)基于句法的机器翻译方法BTG的主要问题•两条主要合并规则A→［AA］0.8A→〈AA〉0.2•如何使用这两条规则，stochasticBTG给每条规则赋以先验概率•先验概率是一种非常粗糙、简单的处理方法，不能有效地处理重排序问题31机器翻译原理与方法(05)基于句法的机器翻译方法ME-BTG：基本思想•在BTG框架下，将重排序问题看作是一个2类分类问题：–条件：各种与重排序短语相关的特征–类别：相邻语块的顺序{straight,inverted}•引入最大熵模型作为分类模型，根据实际上下文计算合并规则的概率withthemkeepcontact与他们保持联系straight0.05keepcontactwiththem与他们保持联系inverted0.9532机器翻译原理与方法(05)基于句法的机器翻译方法ME-BTG模型•模型•特征=po∣A1,A2=∑iihio,A1,A2∑o'exp∑iihio',A1,A2hio,A1,A2={1iffA1,A2=T,o=O0otherwiseO∈{straight,inver