机器翻译原理与方法 第五讲 基于句法的统计机器翻译方法 刘群 中国科学院计算技术研究所 liuqun@ict.ac.cn 中国科学院计算技术研究所2009年秋季课程
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 内容提要 概述 同步语法概念 反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 概述 基于短语的统计翻译方法的问题 基于句法的统计翻译方法的分类 目前的进展（the state of the art） 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于短语的统计翻译方法的问题 泛化能力差 中国大使馆、美国大使馆 月球大使馆？ 产生的句子不符合语法 短语的简单组合，没有句法结构 无法表示不连续的短语搭配的翻译 召开了一次关于…的会议 hold a meeting on … 无法进行长距离的语序调整 解决办法：引入句法结构！ 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 统计机器翻译方法的金字塔 Syntax-based Phrase-based Semantic-based Interlingua Word-based Source Language Target Language This picture show different translation models. Maybe you are familiar with this picture. Since people often use a similar picture to introduce the types of transfer-based machine translations. The translation models can be classified in the same way. There are word-based models, phrase-based models, syntax-based models, and etc. Here we will introduce two different syntax-based models. 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
基于句法的统计机器翻译模型(1) linguistically syntax-based model tree-to-tree model linguisitcal syntax level syntax level string-to-tree model tree-to-string model formally syntax-based model formal syntax level Now we put our attention to syntax-based models. There are many different kinds of syntax-based models. Here we give a simple review. This picture is a portion of the triangle we have introduced. the bottom is the phrase level. The top is the syntax level. Actually there are two different syntax levels, which we call formal syntax level and linguistic syntax level. So we have formally syntax-based model and linguistically syntax-based model. And, we can further have tree kinds of linguistically syntax-based models: tree-to-string model, string-to-tree model, and tree-to-tree model. phrase-based model phrase level 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于句法的统计机器翻译模型(2) 形式上基于句法的模型 不使用任何语言学知识 所有句法结构直接从未标注的语料库中自动学习得到 语言学上基于句法的模型 使用语言学知识 语言通常要从句法树库训练得到 树到串模型：只在源语言端使用语言知识 串到树模型：只在目标语言端使用语言知识 树到树模型：在源语言端和目标语言端都使用语言知识 string-to-tree model: linguistic syntax level on target side tree-to-string model: linguistic syntax level on source side tree-to-tree model: linguistic syntax level on both side 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 形式上基于句法的模型 反向转录语法（ITG）和括号转录语法（BTG） Inversion (Bracketing) Transduction Grammar (ITG,BTG), Wu 1997 有限状态中心词转录机 Finite-State Head Transducer, Alshawi 2000 基于层次短语的翻译模型 Hierarchical Phrase-based Model, Chiang 2005 最大熵括号转录语法的翻译模型 Maximal Entropy Bracket Transduction Grammar (ME-BTG), Xiong 2006 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 语言学上基于句法的模型 串到树模型 String-to-Tree Model 美国南加州大学信息科学研究所（ISI/CSU）的工作 Yamada 2001, Galley 2006, Marcu 2006 树到串模型 Tree-to-String Model 中科院计算所的工作 Tree-to-string Alignment Template Model (TAT), Liu Yang 2006 微软研究院的工作（依存模型） Dependency Treelet Translation, Quirk 2005 树到树的模型 Tree-to-Tree Model 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 内容提要 概述 同步语法概念 反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步语法 (1) 定义：同步语法是一种形式语法，这种语法的每一次推导，都在两种或者两种以上语言中同步生成一个句子。 同步语法 我 我们 我们是中国人 中国是世界上人口 最多的国家 …… I We We are Chinese China is the country with the largest population in the world …… 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步语法 (2) 同步语法的具体形式： 同步上下文无关语法（SCFG） 反向转录语法(ITG)和括号转录语法(BTG) 同步树替换语法(STSG) 同步树粘接语法(STAG) 多文本语法(MTG) 同步语法的应用： 编译中的代码生成 自然语言的语义解释 自然语言的机器翻译 双语语料库的对齐 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步语法 (3) 同步语法与统计机器翻译 同步语法是很多基于句法的统计机器翻译模型的理论基础 理论上说，如果采用同步语法，在完成源语言句法分析的同时，目标语言就生成了，因此可以利用各种成熟的句法分析算法进行机器翻译，而无需另外设计专门的翻译算法 另一方面，采用同步语法对源语言进行句法分析时，要把目标语言的因素考虑进来，这不同于通常的句法分析 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 内容提要 概述 同步语法概念 反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 反向转录语法 Inversion Transduction Grammar：ITG 吴德凯(1997 onwards) ITG是一种形式最简单的同步语法，可以并行地生成两颗对齐的句法树 ITG的规则都是乔姆斯基范式形式的 规则的右部或者全部是终结符，或者全部是终结符 非终结符规则都是二分的 ITG的规则可以指定语序的变化：保序 或 逆序 ITG中两种语言的规则使用同一套非终结符 ITG中对规则的二分限制降低了搜索的复杂度 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 反向转录语法 ITG rules Source Target 非终结符规则 A [ B C ] ABC A < B C > A CB 终结符规则 A x/y Ax Ay target source straight inverted 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 反向转录语法 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于反向转录语法的统计机器翻译 (1) 训练：从词语对齐的语料库中自动抽取规则 解码：类似于一个概率化句法分析的过程 利用规则的源语言部分进行句法分析 存在源语言部分相同而目标语言部分不同的规则（保序或逆序），这是不同于传统句法分析的地方 句法分析时，对于源语言部分相同而目标语言部分不同的规则，需要通过概率计算进行评分，这相当于对译文语序进行选择 句法分析完成的同时也就生成了译文句法结构和译文句子 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于反向转录语法的统计机器翻译 (2) 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于反向转录语法的统计机器翻译 (3) 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 括号转录语法 Bracketing Transduction Grammar：BTG BTG是ITG的一个特例，其中只有唯一的一个非终结符X 可以这么理解：BTG仅仅给出了两种语言的句子结构结构之间的对应关系，没有任何句法标记信息（如NP、VP等等） 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 统计机器翻译中语序调整的方式 无约束（所有匹配都运行） 所有语序调整都是允许的 对于N个词（或短语），在IBM约束下，语序调整有N!种可能性，搜索空间随着句子长度呈指数级增长，因此其搜索问题是NP问题 IBM约束（IBM Constrains） 为了减少搜索空间，通常在从左到右的解码过程中都会采用IBM约束来限制语序调整的搜索空间，也就是说，每次只选择最左边若干个未被翻译的词语进行翻译（对Hypothesis进行扩展） IBM约束可以大大减少搜索空间，但依然存在大量非法语序调整 BTG约束（BTG Constrains） 只有能够满足某种BTG映射的语序调整才是允许的 BTG约束大大降低了搜索空间大小，确保搜索范围内的语序调整都满足语法约束，同时不在搜索范围内的约束都不满足语法约束 BTG约束搜索使得长距离语序调整成为可能 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 这里给出了四个词的所有可能的调序方案以及对应的BTG转换模式。 其中有两种方案在BTG约束下是不允许的（找不到对应的BTG转换模式） 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 BTG约束导致搜索空间大大压缩 word reordering which are not permitted in BTG 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 真实自然语言的翻译满足BTG约束吗？ 对于汉语和英语之间的翻译，几乎满足 一个例外（出处？）: 对于一些自由语序的语言，不一定满足 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 内容提要 概述 同步语法概念 反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于最大熵括号转录语法的翻译模型 基于最大熵括号转录语法的翻译模型 A Translation Model Based on Maximum Entropy Bracketing Transuction Grammar (ME-BTG) Deyi Xiong, Qun Liu, and Shouxun Lin. Maximum Entropy Based Phrase Reordering Model for Statistical Machine Translation. COLING-ACL 2006, Sydney, Australia, July 17-21. Deyi Xiong, Min Zhang, Ai Ti Aw, Haitao Mi, Qun Liu and Shouxun Lin, Refinements in BTG-based Statistical Machine Translation, IJCNLP 2008, Hyderabad, India, January 7-12 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 BTG的主要问题 两条主要合并规则 A ［ A A ］ 0.8 A 〈 A A 〉 0.2 如何使用这两条规则，stochastic BTG给每条规则赋以先验概率 先验概率是一种非常粗糙、简单的处理方法，不能有效地处理重排序问题 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 ME-BTG：基本思想 在BTG框架下，将重排序问题看作是一个2类分类问题： 条件：各种与重排序短语相关的特征 类别：相邻语块的顺序 {straight, inverted} 引入最大熵模型作为分类模型，根据实际上下文计算合并规则的概率 with them keep contact 与他们 保持联系 straight 0.05 inverted 0.95 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 ME-BTG模型 模型 特征 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 ME-BTG训练 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 抽取重排序实例 在双语语料库中抽取所有如下两类双语短语块： S1 S2 b1 T1 <b1; b2> STRAIGHT b2 T2 E.g. <今天 有 棒球 比赛|Are there any baseball games today; 吗 ？|?> STRAIGHT S3 S4 b4 b3 T3 <b3; b4> INVERTED E.g. <澳门 政府|the Macao government; 有关 部门|related departments of> INVERTED T4 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 重排序特征 单目特征：单个源/目标语言边界单词 双目特征： 两个源/目标语言边界单词的组合 <与 他们|with them; 保持联系|keep contact> INVERTED 特征选择 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 为什么使用边界单词作为特征？ feature IGR Phrases .02655 C1C2E1E2 .0263687 E1E2 .0239286 C1C2 .023363 C2E2 .0192932 C1E1 .0153117 C2 .011371 E2 .00994372 E1 .00899752 C1 .00758598 Source boundary words C1 C2 E1 E2 Target boundary words 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于ME-BTG的统计机器翻译系统 Bruin：基于ME-BTG的统计机器翻译系统 解码算法 基于CKY算法 自底向上，考虑每一个区间(i,j)，每个区间保留一个堆栈 对于每个区间(i,j)，考虑其每一个分割(i,k)*(k+1,j) 对于每一个分割，考虑其所有子节点的候选译文，以及“保序”和“逆序”两种情况，计算所有可能的候选译文 采用柱搜索（Beam Search）策略，对堆栈中的候选译文结点进行剪枝 对于堆栈中的候选译文结点进行归并（recombination）:如果结点的左右n-1个单词都相同，在归并为一个结点（假设这里采用n元语法模型） 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 CKY解码算法 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于ME-BTG模型的翻译过程 查短语表 原文f 他 将 于 ４月 １０日 访问 美国 。 译文e he will on April 10 visit America . 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于ME-BTG模型的翻译过程 利用边界词特征计算是否调序 原文边界词：“于” + “访问” 保序概率：0.05 译文边界词：“on” + “visit” 原文f 他 将 于 ４月 １０日 访问 美国 。 译文e he will on April 10 visit America . 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于ME-BTG模型的翻译过程 利用边界词特征计算是否调序 原文边界词：“于” + “访问” 逆序概率：0.95 译文边界词：“on” + “visit” 原文f 他 将 于 ４月 １０日 访问 美国 。 译文e he will on April 10 visit America . 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
在所有可能的结构变换中搜索概率最大的形式 基于ME-BTG模型的翻译过程 搜索 在所有可能的结构变换中搜索概率最大的形式 需要搜索所有可能的结构关系映射。 相对于不考虑结构关系的映射，这种做法大大减少了搜索空间（指数量级降为多项式量级），这项工作是吴德凯的BTG模型完成的。 我们的关键贡献就在于，对于任何一种二分的句法结构，给出了其对应的译文语序的概率计算方法，即最大熵方法。这样就可以在众多的结构中搜索到最好的结构。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于ME-BTG模型的翻译过程 得到结果 原文f 他 将 于 ４月 １０日 访问 美国 。 译文e he will visit America on April 10 . 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 ME-BTG：实验 Systems NIST MT 05 IWSLT 04 Bruin with monotone search 20.1 37.8 Bruin with distance-based reordering 20.9 38.8 Bruin with flat reordering 20.5 38.7 Pharaoh 20.8 38.9 Bruin with MEBTG (单目) 22.0 42.4 Bruin with MEBTG (单目 + 双目) 22.2 42.8 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 内容提要 概述 同步语法概念 反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文无关语法 David Chiang. An introduction to synchronous grammars. In Proc. of ACL Tutorial, 2006. 本部分讲义引自David Chiang的上述Tutorial中的内容，特此说明，并向原作者表示感谢。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文无关语法 (1) 英语的语法： 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文无关语法 (2) 日语的语法 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文无关语法 (3) 两种语法的一一对应关系： 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文无关语法 (4) 同步上下文无关语法： 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文无关语法 (5) 同步句法树： 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文无关语法 (6) 带概率的同步语法： 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文无关语法 (7) 同步句法树的概率： 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 类似的表示形式 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文关语法的层次(1) 乔姆斯基范式： 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文关语法的层次(2) 5阶 2阶 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文关语法的层次(3) 3阶 2阶： 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文关语法的层次(4) 4阶 2阶？ 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文关语法的层次(5) 4阶 2阶？ 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步上下文关语法的层次(5) 表达能力： 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 算法复杂度 机器翻译复杂度： 分析：O(n3) 转换：O(n) 生成：O(n) 同步句法分析复杂度： O(n10) 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 内容提要 概述 同步语法概念 反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 层次短语模型 (1) 层次化基于短语的翻译模型（蒋伟，UMD） A Hierarchical Phrase-Based Translation Model David Chiang. A Hierarchical Phrase-Based Model for Statistical Machine Translation. ACL2005. (Best Paper Award) 本讲义这一部分内容直接引用了以下讲义的部分内容，特此说明并向原作者表示感谢： David Chiang, Hiero: Finding Structure in Statistical Machine Translation, in National University of Singapore 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 层次短语模型 (2) 传统的基于短语的翻译模型中，短语是平面的，不能嵌套 在层次短语模型中，引入了嵌套的层次短语 采用平行上下文无关语法作为理论基础，但只使用唯一的非终结符标记 效果比传统的短语模型有很大提高 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 短语的层次性 可以观察到短语是有层次的，短语之间可以嵌套。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 用层次短语进行翻译 (1) 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 用层次短语进行翻译 (2) 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 用层次短语进行翻译 (3) 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 用同步语法表示层次短语 (1) 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 用同步语法表示层次短语 (2) 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 层次短语的抽取 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 约束：降低复杂度 用于抽取规则的短语长度 (≤7–20) 规则长度 (≤5–6) 规则中至少要有一个终结符 最多有两个不相邻的非终结符 句法约束? 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 非终结符标记 到目前未知只采用一个非终结符X 可能的扩展： 句法类型 其他信息，如命名实体标记（人名、地名等） 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 规则举例 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 粘合规则（Glue Rules） 找不到可用的规则时，引入粘合规则 粘合规则的作用在于将短语的译文从左到右依次顺序“粘合”成完整的译文： 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 特殊规则 实际的翻译系统中，通常需要一些特殊的翻译模块： 数词 时间词 人名、地名、机构名 新闻byline 将以上模块翻译的结果处理成一条规则： （X一百二十三，X123） 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 模型 直接利用同步上下文无关语法的概率模型 通过对数线性模型融合其他特征，如传统短语模型的各种特征 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 模型特征 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 模型特征 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 解码 类似于句法分析，在对源语言分析的同时，产生目标语言的结构。 算法复杂度O(n3) 为了减少搜索时间，只将抽取出来的规则用于比较短的串（如少于10-15个词），对于更长的串只使用粘合规则。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 小结 形式上基于句法的模型 性能明显超过基于短语的模型 完全兼容基于短语的模型 所有规则可以自动抽取 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 内容提要 概述 同步语法概念 反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 树到串翻译模型 树到串翻译模型指这样一类翻译模型： 在源语言端进行句法分析 在目标语言端不进行句法分析 从源语言端句法分析和词语对齐的语料库中抽取翻译规则并构造翻译模型 目前，树到串翻译模型的典型工作有： 基于树到串对齐模板的翻译模型 （刘洋，ACL2006、ACL2007） 基于依存树片的翻译模型 （Quirk Chris，ACL2005；熊德意，WMT2007） 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于树到串对齐模板的翻译模型 基于树到串对齐模板的翻译模型（刘洋，ICT） A Translation Model Based on Tree-to-String Alignment Template Yang Liu, Qun Liu, and Shouxun Lin. 2006. Tree-to-String Alignment Template for Statistical Machine Translation. COLING-ACL 2006, Sydney, Australia, July 17-21. Yang Liu, Yun Huang, Qun Liu and Shouxun Lin, Forest-to-String Statistical Translation Rules, ACL2007, Prague, Czech，June 2007 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 基于树到串对齐模板的翻译模型 基于树到串对齐模板（简称TAT）的统计翻译模型是一种在源语言进行句法分析的基于语言学句法结构的统计翻译模型 树到串对齐模板既可以生成终结符也可以生成非终结符，既可以执行局部重排序也可以执行全局重排序 从经过词语对齐和源语言句法分析的双语语料库上自底向上自动抽取TAT 自底向上的柱搜索算法 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 树到串对齐模板 NP LCP NP NP LC NR NN DNP NP NR CC NR 间 布什 总统 NP DEG 美国 和 President Bush between United States and 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 翻译过程 : Parsing 中国 的 经济 发展 parsing NP DNP NP NP DEG NN NN NR 的 经济 发展 中国 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 翻译过程: Detachment NP DNP NP NP DEG NN NN NR 的 经济 发展 中国 detachment NP NP NP NN NN DNP NP NR NN NN 经济 发展 NP DEG 中国 的 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 翻译过程: Production NP NP NP NN NN DNP NP NR NN NN 经济 发展 NP DEG 中国 的 economic development China of 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
翻译过程: Combination NP NP NP NN NN DNP NP NR NN NN 经济 发展 NP DEG 中国 的 economic development China of combination economic development of China 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 模型 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 模型特征 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 训练 数据：源语言句法分析和词语对齐的双语语料库 自底向上抽取 为避免抽取的TAT数量过大，需要对抽取过程施加一些约束： 树高度约束 height(T)<=h 子节点个数约束 number_of_chindren(T)<=c 目标语言的首尾词必须是对齐的 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 树到串对齐模板的抽取 (1) NP DNP NP NR NR DEG NN NN 中国 中国 的 经济 发展 China economic development of China 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 树到串对齐模板的抽取 (2) NP DNP NP DEG NR DEG NN NN 的 中国 的 经济 发展 of economic development of China 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 树到串对齐模板的抽取 (3) NP DNP NP NN NR DEG NN NN 经济 中国 的 经济 发展 economic economic development of China 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 树到串对齐模板的抽取 (4) NP DNP NP NN NR DEG NN NN 发展 中国 的 经济 发展 development economic development of China 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 树到串对齐模板的抽取 (5) DNP DNP NP NR DEG NR DEG DNP NP 中国 的 的 NR DEG NN NN of China of 中国 的 经济 发展 DNP DNP NR DEG NR DEG 中国 economic development of China China 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 树到串对齐模板的抽取 (6) NP NP NP NN NN NN NN DNP NP 经济 发展 发展 NR DEG NN NN economic development development 中国 的 经济 发展 NP NP NN NN NN NN 经济 economic development of China economic 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 树到串对齐模板的抽取 (7) NP DNP NP NP NR DEG NN NN DNP NP 中国 的 经济 发展 economic development of China 严格的约束条件：h=2, c=2 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 解码 自底向上 柱搜索（Beam Search） 对于每一棵子树，找到所有与其根节点匹配的TAT，计算其候选译文（Candidate） 候选译文（Candidate）的数据结构： TAT序列 部分翻译结果 累积的特征值 累积的概率值 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
解码：构造缺省TAT 如果匹配不到合适的TAT，就构造一个缺省的TAT： NR NR 中国 construct default TATs NP NP DNP NP construct default TATs DNP NP NP DEG NN NN NR 的 经济 发展 中国 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 解码（1） Usable TAT 8 NP NR 4 7 DNP NP 中国 5 6 NP 2 DEG 3 NN NN China NR 1 的 经济 发展 Derivation 中国 ( NR 中国 ) China 1:1 Suppose we are to translate a Chinese string mentioned before. Here is the parse tree. The nodes of the tree are indexed by a postorder transversal. The subtree marked with red line is the current tree to be translated. Suppose we have five TATs at hand. (Go to page 10 and go back to page 27). We find a TAT usable and the tree of the TAT matches the subtree. As a result, the target string “China” is the translation for subtree 1. This is the derivation. The candidate translation is pushed into stack 1. Translation China 1 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 解码（2） Usable TAT (default) 8 NP NP 4 7 DNP NP NR 5 6 NP 2 3 DEG NN NN NR 1 的 经济 发展 Derivation 中国 ( NP ( NR ) ) X 1:1 ( NR 中国 ) China The green stacks store translations for subtrees that have already been translated, which are marked in blue. For the subtree 2, we cannot find a usable TAT and have to construct a default TAT. Note that the tree of default TAT covers only a portion of the subtree and the uncovered portion has already been translated, marked in blue. So we can directly make use of the candidate translation in Stack 1. This is the derivation for subtree 2. The translation is “China”. Translation China 1 2 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 解码（3） Usable TAT (default) 8 NP DEG 4 7 DNP NP 的 5 6 NP 2 3 DEG NN NN 的 NR 1 的 经济 发展 Derivation 中国 ( DEG 的 ) 的 1:1 This is also a default TAT. Translation 的 1 2 3 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 解码（4） Usable TAT (default) 8 NP DNP 4 7 DNP NP NP DEG 5 6 NP 2 3 DEG NN NN NR 1 的 经济 发展 Derivation 中国 ( DNP ( NP ) ( DEG ) ) X1 | X2 1:1 2:2 ( NP ( NR 中国 ) ) China 1:1 ( DEG 的 ) 的 Subtree 4 also needs a default TAT Translation China 的 1 2 3 4 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 解码（5） Usable TAT 8 NP NN 4 7 DNP NP 经济 5 6 NP 2 3 DEG NN NN economic NR 1 的 经济 发展 Derivation 中国 ( NN 经济 ) economic 1:1 Subtree 5 Translation economic 1 2 3 4 5 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 解码（6） Usable TAT 8 NP NN 4 7 DNP NP 发展 5 6 NP 2 DEG 3 NN NN development NR 1 的 经济 发展 Derivation 中国 ( NN 发展 ) development 1:1 Subtree 6 Translation development 1 2 3 4 5 6 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 解码（7） Usable TAT 8 NP NP 4 7 DNP NP NN NN 5 6 NP 2 DEG 3 NN NN NR 1 的 经济 发展 Derivation 中国 ( NP ( NN ) ( NN ) ) X1 | X2 1:1 2:2 ( NN 经济 ) economic 1:1 ( DEG 发展 ) development Subtree 7 Translation development 1 2 3 4 5 6 7 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
解码（8） Usable TAT 8 NP 4 7 DNP NP 5 6 NP 2 3 DEG NN NN NR 1 的 经济 发展 of Derivation 中国 ( NP ( DNP ( NP ) ( DEG ( 的 ) ) ) ( NP ) ) X1 | of | X2 1:3 2:2 3:1 ( NP ( NR ) ) X 1:1 ( NR 中国 ) China 1:! ( NP ( NN ) ( NN ) ) X1 | X2 1:1 2:2 ( NN 经济 ) economic ( NN 发展 ) development Subtree 8 is the entire parse tree. The translation for this tree is what we actually need. We make use of the candidate translations from stack 2 and stack 7 to help derive the translation for subtree 8. And this is the best translation we think. Translation 1 2 3 4 5 6 7 8 economic development of China 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 剪枝策略 模板表剪枝 tatTable_limit tatTable_threshold 堆栈剪枝 stack_limit stack_thrshold 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
候选译文归并（Recombination） The economic development of China is very rapid . The economic develop of China is quite rapid . The economic developing of Chinese is rapid . The economic development of Chinese are quite rapid . 考虑采用英文的三元语法模型，为了保证动态规划算法所要求的单调性，对同一个堆栈中，首尾Bigram完全相同的候选译文（Candidate），可以合并成一个结点。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 实验 Baseline：Pharaoh (Koehn et al., 2004) 实验系统：Lynx 训练语料：31,149 句子对 含843K汉语词和949K英语词 开发集：2002 NIST汉英测试数据的一部分 (571 of 878 sentences) 测试集：2005 NIST汉英测试数据 (1,082 sentences) The baseline system we used for comparison was Pharaoh, a freely available decoder for phrase-based translation models. The training corpus consists of thirty thousand pair of sentences. The development set is 2002 NIST Chinese-to-English test set. The test set is 2005 NIST test set. 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 训练过程 句子对齐的双语语料库 双向GIZA++及合并 词语对齐的双语语料库 Pharaoh 训练工具 汉语句法分析 带汉语句法树及词语对齐的双语语料库 The name of our decoder is Lynx. This diagram demonstrates data process for Pharaoh and Lynx. They share the same word-aligned data. Lynx requires an additional parsing. Lynx 训练工具 双语短语表 TAT表 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 实验环境 评测工具: mteval-v11b.pl 语言模型工具: SRI Language Modeling Toolkits (Stolcke, 2002) 显著性测试工具: Zhang et al., 2004 汉语句法分析: Xiong et al., 2005 最小错误率训练工具: optimizeV5IBMBLEU.m (Venugopal and Vogel, 2005) These are some tools used for experiments: evaluation, language model, significance test, parser, and minimum error rate training. 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
实验结果 Comparison of Pharaoh and Lynx with different feature settings Here are evaluation results. Lynx achieves an absolute improvement of 0.9% (4.3% relative) in terms of BLEU score. This difference is statistically significant. Lynx achieves an absolute improvement of 0.9% (4.3% relative) over Pharaoh in terms of BLEU score. This difference is statistically significant (p < 0.01). 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 与短语的兼容性 TAT模型与短语模型是不兼容的 句法短语可以表示为TAT 非句法短语无法表示为TAT 实验表明，非句法短语对于提高系统性能有重要作用 即使对于句法短语，由于句法分析不可靠（对于同一个短语的分析有时正确有时错误），也会造成TAT概率估计上的不准确 设想：利用双语短语（BP）可以改进TAT模型的性能 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 利用句法短语修正TAT的概率 理由： 句法分析是不可靠的，对于同一个短语，可能有时分析正确，有时分析错误，这样会导致TAT概率估计上的不准确 做法： 把句法短语（SBP）的四个概率与相应的TAT的四个概率进行比较，用其中较大者取代TAT原来的概率 We use bilingual phrases to strengthen the TAT-based model. Why? Bilingual phrases are “cheaper” than TATs. In other words, they are easier to obtain from real-world data. Moreover, syntactic analysis is not reliable. We may have many bad TATs and the input tree structure may be totally wrong. Bilingual phrases have been proved to excellent knowledge sources. In addition, the TAT-based model may lose useful non-syntactic phrase pairs due to strict restriction. How to use bilingual phrases? We treat them as special TATs without tree over the source side 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 An Example NP TAT table NR NN 布什 总统 0.4 0.2 0.3 0.5 NP NR NN President Bush 布什 总统 BP table For example, for an input tree, we find a TAT from the TAT table and a bilingual phrase from BP table. Their translation probabilities are different. 布什 总统 0.3 0.6 0.2 0.4 President Bush 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 An Example NP TAT table NR NN 布什 总统 0.4 0.2 0.3 0.5 NP NR NN President Bush NP 布什 总统 BP table We can build a TAT for this bilingual phrase. Just add the tree over the source string. If the built TAT is the same with the one coming from TAT table, we prefer to higher probabilities. NR NN 布什 总统 0.3 0.6 0.2 0.4 President Bush 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 An Example NP NP NR NN NR NN 布什 总统 0.4 0.6 0.3 0.5 布什 总统 President Bush This is the final TAT 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
采用句法短语修正TAT概率的效果 Effect of Using Bilingual Phrases for Lynx Using bilingual phrases brings an absolute improvement of 0.6% in terms of BLEU score Using bilingual phrases brings an absolute improvement of 0.6% in terms of BLEU score. 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 利用非句法双语短语改进译文流利度 Problem with Lynx: 国际足联将严惩足球场上的欺骗行为 FIFA will severely punish cheat behaviour on the football field 国际足联执委会还宣布了一些改革措施。 international 足联 Executive Committee also announces that some reform measures. There are two translations from our decoder. We find that for the same source sub string, the two translations are quite different! How could this happen? How could this happen? 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Two Parse Trees NP-B NP-B NN NN NN NN NN 国际 足联 国际 足联 执委会 国际 足联 The reason is that a bilingual phrase can be treated as a TAT if and only if there is a tree over the source string. So, in the first sentence, the source sub string is properly translated by the TAT constructed from the bilingual phrase. In the second sentence, the source sub string is translated by default TATs. The lesson is that the strength of bilingual phrases is restricted. FIFA the strength of BPs is restricted! 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Solution When the search ends, refine the output by replacing strings with more fluent ones with the help of alignment. Use language model to measure fluency If there are more than one candidates, choose the one with highest score (take translation probabilities into account) To take the advantage of bilingual phrases as fully as possible, we use them to improve fluency. The idea is that when the search ends, refine the output by replacing strings with more fluent ones with the help of alignment. We use language model to measure fluency. If there are more than one candidates, we choose the one with highest score. 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 An Example IP NP-B VP PU 。 NN NN NN ADVP VP-B 国际 足联 执委会 AD VV AS NP 还 宣布 了 QP NP-B CD NN NN For example, when the search ends, we get a translation and an alignment between the input source tree and the translation. Then, we can replace strings with more fluent ones, with no regard to the tree structure any more. Suppose that we find two strings can be replaced to improve fluency. 一些 改革 措施 international 足联 Executive Committee also announces that some reform measures . 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
An Example IP NP-B VP PU 。 NN NN NN ADVP VP-B 国际 足联 执委会 AD VV AS NP 还 宣布 了 QP NP-B CD NN NN We replace the first string “international 足联” by “FIFA” 一些 改革 措施 FIFA Executive Committee also announces that some reform measures . 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
An Example IP NP-B VP PU 。 NN NN NN ADVP VP-B 国际 足联 执委会 AD VV AS NP 还 宣布 了 QP NP-B CD NN NN Then replace the second string “announces that some” by “announced some”. As we can see, the refined translation is more fluent than the original one. 一些 改革 措施 FIFA Executive Committee also announced some reform measures . 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 加大数据规模 Bilingual corpus (train BPs and TATs) 2.6M sentence pairs (68.1M Chinese words and 73.8M English words) Use all the data to obtain BPs and a portion of 800K pairs to obtain TATs Monolingual corpora (train LM) English side of the bilingual corpus (73.8M words) Xinhua portion of Gigaword corpus (181M words) The bilingual corpus contains over 2 million sentence pairs. We use all the data to obtain bilingual phrases and a portion of 800K pairs to obtain TATs. We use two corpora to train language models. One is the English side of the bilingual corpus. Another is the Xinhua portion of Gigaword corpus. 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 加大数据规模后的实验结果 Training Data (pairs) Language Model Improve Fluency BLEU4 TAT BP Data (words) Order 31K - 949K one 3-gram No 0.2178 0.2240 800K 73M 0.2431 2.6M 0.2692 73M | 181M two 3-gram 0.2934 two 4-gram 0.3047 Yes 0.3184 These are evaluation results of Lynx on 2005 NIST Chinese-to-English Test Set with various settings. The BLEU score 0.3184 is the best result Lynx achieves on the test set. We find that that scaling to large data brings about 2% absolute improvement two 3-gram LMs brings about 2% absolute improvement over one 3-gram LMs two 4-gram LMs brings about 1% absolute improvement over two 3-gram LMs using BPs to improve fluency brings about 1% absolute improvement Results of Lynx on test set with various settings. 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 小结 基于树到串对齐模板的翻译模型 一种树到串的模型 在源语言句法分析和词语对齐的双语语料库上抽取双语对齐模板（TAT），构建翻译模型 解码时先进行源语言句法分析，然后自底向上依次对树的每个结点构造候选译文 模型简洁直观，可以较好地利用句法信息进行重排序，性能超越了基于短语的模型 与短语模型结合后性能有更大幅度的提高 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 内容提要 概述 同步语法概念 反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 串到树翻译模型 串到树翻译模型指这样一类翻译模型： 在源语言端进行不句法分析 在目标语言端进行句法分析 从目标语言端句法分析和词语对齐的语料库中抽取翻译规则并构造翻译模型 目前，串到树翻译模型的典型工作是美国南加州大学信息科学研究所（USC/ISI）从2001年到2005年的系列工作 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 ISI的工作 Ulrich Germann, ACL2001 (Best Paper Award) Kenji Yamada, ACL2001, ACL2002 Yaser Al-Onaizan, ACL2002 Michel Galley, NAACL-HLT 2004 Jonathan Graehl, NAACL-HLT 2004 Kevin Knight, CICLing 2005 Michel Galley, COLING/ACL 2006 Daniel Marcu, COLING/ACL 2006 Hao Zhang, NAACL-HLT 2006 Liang Huang, AMTA 2006 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 ISI的工作 Scalable Inference and Training of Context-Rich Syntactic Models Michel Galley COLING/ACL 2006 SPMT: Statistical Machine Translation with Syntactified Target Language Phrases Daniel Marcu EMNLP 2006 Synchronous Binarization for Machine Translation Hao Zhang NAACL-HLT 2006 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步生成树、串和对齐 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步生成树、串和对齐 NP NP VP 的 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步生成树、串和对齐 NP NP VP NNS astronauts 的 宇航 员 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步生成树、串和对齐 NP NP VP NNS VBG PP astronauts coming IN NP from 来自 的 宇航 员 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 同步生成树、串和对齐 NP NP VP NNS VBG PP astronauts coming IN NP from NNP China 来自 中国 的 宇航 员 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 规则与推导 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 规则与推导 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 最小规则与组合规则 最小规则 定义： 不能再分解成更小规则的规则 例子： NP(x0:DT,CD(7),NNS(people)) -> x0, 7人 DT(these) -> 这 组合规则 由两个或者多个最小规则组合成的规则 NP(DT(these),CD(7),NNS(people)) -> 这, 7人 NP(x0:DT,CD(7),NNS(people)) -> x0, 7, 人 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 句法翻译概率表 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 翻译模型定义 Galley 条件概率模型：将给定的目标语言树转换成源语言词串的概率 Marcu 联合概率模型：同步生成源语言词串、目标语言树和对齐的概率 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 与短语模型的兼容性：非句法短语 NPB DT JJ NN the mutual understanding 这 相互 理解 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 非句法短语的处理办法 Marcu的办法 忽略非句法短语 损失：在汉语-英语双语语料库中提取的短语中，28%都是非句法短语 沿目标语言句法树向上找一个可以覆盖该短语并满足对齐约束的结点 问题：可能需要引入很大范围的上下文 为非句法短语构造新的规则： Compatible Rules 兼容规则 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 构造兼容规则 (1) *NPB*_NN DT JJ the mutual 这 相互 构造一条规则： 根结点是一个“伪”非终结符结点 覆盖若干棵目标语言句法子树及其对应的源语言词串 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 构造兼容规则 (2) NPB *NPB*_NN NN 构造另一条对应的规则：描述该“伪”结点如何与周围的“真”句法结点组合成 “真”句法树。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 构造兼容规则 (3) 兼容规则的引入，以比较小的代价实现了与短语模型的兼容性，提高了系统的性能 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 模型特征 Galley (1) EM-trained root-normalized SBTM Marcu (11) p_root(r) root normalized conditional probability of all rules p_cfg(r) CFG-like probability of non-lexicalized rules is_lexicalized(r) indicator 0/1 is_composed(r) indicator 0/1 is_lowcount(r) indicator count < 3 ? 1 : 0 lex_pef(r) direct phrase-based conditional probability lex_pfe(r) inverse phrase-based conditional probability m1(r) IBM model 1 probability m1inv(r) IBM model 1 inverse probability lm(e) language model wp(e) word penalty 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 训练 规则抽取 Input: word-aligned, target side parsed bilingual corpus Output: rules 概率估计 How to estimate the probability distribution of rules? 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Galley的规则抽取方法 首先计算边沿结点集合 自顶向下，以每一个边沿结点为根结点： 抽取最小规则，得到最小推导 或者： 对于该结点覆盖的未对齐源语言结点，考虑其不同的附着方式，抽取所有组合规则，得到推导森林 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 将树到串对齐表示为图 为了对规则抽取的过程进行形式化描述，我们将（树，串，对齐）三元组表示为一个有向图（边都是向下的），其中并不对树中的边和表示对齐关系的边加以区别。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Some Notions The span of a node n is defined by the indices of the first and last word in the source string that are reachable from n The complement span of a node n is the union of the spans of all nodes n’ in G that are neither descendants nor ancestors of n Nodes of G whose spans and complement spans are non-overlapping form the frontier set F∈G A frontier graph fragment is a graph fragment that root and all sinks are in the frontier set A minimal frontier graph fragment is the one that is a subgraph of every other frontier graph fragment with the same root. 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 一些概念定义 一个结点n的区间(span)是该结点所对应的第一个和最后一个源语言单词所指定的范围。 一个结点n的补区间(complement span)是图G中所有既非n的子孙结点也非n的祖先结点的那些结点n’的区间(span)所构成的并集 图G的边沿集合(frontier set)是由图G中那些其区间与补区间不重叠的结点所构成的集合F（F⊆G） 图G的一个边沿图片段(frontier graph fragment)是图G的一个片段，其根结点及其Sink结点都位于图G的边沿集合中 图G的一个最小边沿图片段(frontier graph fragment)是图G的一个边沿图片段，而且它是所有其他具有相同根结点的边沿图片段的子图 请注意以下概念：有向图、有向图的片段（fragment）、有向图片段的根结点和sink结点 sink结点在一些地方翻译成“漏”结点或者“汇”点，表示出度为零的结点。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 An Example 灰色结点构成边沿集合 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 抽取规则算法 Step 1: 计算图的边沿集合 Step 2: 对边沿集合中的每个结点，计算以其为根结点的最小边沿图片段 Step3: 从该最小边沿图片段中导出规则 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Extraction 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Extraction 抽取规则的时候，对于边沿集合外的子孙结点，必须全部包含进来 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Extraction 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Extraction 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Extraction 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Extraction 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Extraction 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Extraction 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Extraction 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Extraction 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Extraction 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Extraction 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
唯一最小推导 Unique Minimal Derivation 这样我们就得到了生成图G的唯一的一组最小规则 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 未对齐词导致的问题 真实双语语料库中，源语言和目标语言中都有一些未对齐的词，这些词会导致以下问题： 未对齐的目标语言词使得其祖先结点区间无法确定 未对齐的源语言词会导致抽取的规则数量组合爆炸 n7 n5 n6 n1 n2 n3 n4 w1 w2 w3 w4 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 未对齐词的处理办法 单边附着 将未对齐单词附着到覆盖它的区间最小的结点 多边附着 不做任何将未对齐词“正确”附着的先验性假设，而是返回所有与图G相容的推导 利用语料库的统计信息来优先选取与整个语料库一致性最好的未对齐附着方式 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 源语言未对齐词的多边附着 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 推导森林 多边附着导致可以采用多种推导方式图G，这些推导方式可以表示成一个压缩森林的形式，如上所示 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 新的规则抽取算法 与老算法类似, 新算法也是自顶向下遍历图G, 区别在于，对于每个结点n∈F 执行以下操作： 搜索所有以n为根结点的子树，找到对源语言未对齐单词进行附着的方式，并构造使用这些附着方式的图G的有效推导 比较 老算法 新算法 规则 最小 最小、组合 附着方式 单边 多边 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Marcu的规则抽取算法 对于每一个源语言短语： 首先抽取覆盖该短语的最小规则； 从最小规则的根结点，往上找到第一个带有多子节点的父节点，从该父结点开始抽取一个包含该短语的组合规则 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Marcu的规则抽取算法 最小规则 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Marcu的规则抽取算法 组合规则 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Marcu的规则抽取算法 最小规则 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Marcu的规则抽取算法 组合规则 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 估计规则概率 按规则左部完整树进行归一化： 按规则左部根结点进行归一化： 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example 假设左部的对齐出现了99次，右边的对齐仅出现了1次 按树归一化： p1 = 99/100 = 0.99 p2 = 1/100 = 0.01 p3 = 99/99 = 1.0 p4 = 99/99 = 1.0 按根结点归一化： p1 = 99/199 = 0.4975 p2 = 1/199 = 0.0050 p3 = 99/199 = 0.4976 p4 = 99/99 = 1.0 preferred by Liu preferred by Galley 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 EM训练算法 可以采用EM算法来训练上述模型，各规则的初始概率设置为均匀分布： 计算所有推导θi的概率，为推导过程所采用的所有规则概率的乘积； 对同一个句子的所有推导θi的概率进行归一化，使其概率之和为1； 对于每一条规则，对齐出现在的所有推导θi求和，作为该规则的新的概率pi 对pi进行归一化 重复上述步骤，语料库的似然率将逐步提高。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 高效的EM训练算法 由于不可能对大量的推导进行穷举，上述算法实际上是不可行的。 Graehl and Knight (2004)提出了一种高效的训练算法： 对于每个训练实例构造一个推导森林； 在该推导森林上运行EM算法，其复杂度是森林规模的多项式函数； 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 解码 采用自底向上的CKY形式的算法，在源语言句子的基础上，构造目标语言的短语结构句法树 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example 枪手 被 警方 击毙 。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example NNS gunmen 枪手 被 警方 击毙 。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example NP DT NNS The gunmen 枪手 被 警方 击毙 。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example NP DT NNS IN The gunmen by 枪手 被 警方 击毙 。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example NP DT NNS IN NN The gunmen by police 枪手 被 警方 击毙 。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example NP NP DT NNS IN DT NN the gunmen by the police 枪手 被 警方 击毙 。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example NP NP DT NNS IN DT NN VBN the gunmen by the police killed 枪手 被 警方 击毙 。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example NP NP DT NNS IN DT NN VBN . the gunmen by the police killed . 枪手 被 警方 击毙 。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example PP NP NP DT NNS IN DT NN VBN . the gunmen by the police killed . 枪手 被 警方 击毙 。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example VP-C PP NP NP DT NNS VBN IN DT NN . the gunmen killed by the police . 枪手 被 警方 击毙 。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example VP VP-C PP NP NP DT NNS VBD VBN IN DT NN . the gunmen were killed by the police . 枪手 被 警方 击毙 。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Example S VP VP-C PP NP NP DT NNS VBD VBN IN DT NN . the gunmen were killed by the police . 枪手 被 警方 击毙 。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
规则的二叉化（ Binarization） 现有规则不是二叉的：规则右部可以有多个结点； 多叉的规则导致解码器编程比较复杂； 解决办法：对规则进行二叉化。通过增加非终结符将所有规则变成二叉的规则。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
规则的二叉化（ Binarization） 不是所有规则都可以二叉化 有多大比例的规则可以二叉化？ 根据张浩的论文，在一个汉英双语语料库中提取的50,879,242条规则中，99.7%的规则是可以二叉化的，而且剩下的0.3%的规则，根据人类专家的判断，绝大部分都是对齐错误导致的 规则二叉化有什么作用？ 对翻译质量没有损失 简化解码器的编程复杂度 允许更有效的剪枝 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 线性的二叉化算法 一条规则通常有很多种二叉化的方法 张浩、黄亮等人提出了一种有效的二叉化算法 一种移进-规约算法 只需扫描一遍，在线性时间内找到一种规则二叉化等价形式 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Galley的实验：不同规则集 内部结点，应该是指frontier以外的结点 Cm：只抽取最小规则 C3：抽取最小规则和组合规则，规则最多包含三个内部结点 C4：抽取最小规则和组合规则，规则最多包含四个内部结点 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Galley所采用的特征 实验系统的解码器搜索过程中仅采用了一个经过EM训练的、Root归一化的基于句法的翻译模型（SBTM）特征，甚至没有采用语言模型 Och的基于对齐模板的系统AlTemp作为对比系统，该系统采用了两个基于短语（PBTM）的翻译模型特征和12个其他特征 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Marcu的实验：SPMT Models SPMT Model 1最小规则 SPMT Model 1 Composed 组合规则 SPMT Model 2 最小规则+兼容规则 SPMT Model 2 Composed 组合规则+兼容规则 抽取的时候，限制源语言端短语的长度不超过四个词 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 组合多个SPMT模型的输出结果 每一个SPMT模型对于开发集中的所有句子都生成一个nbest列表，并给出每一个候选译文的所有特征值 将同一个句子的所有候选译文合并，根据其特征值重新进行最小错误率训练，得到一组新的特征参数 用这组特征参数，对于测试集上生成的nbest输出进行重新评分（rerank） 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Marcu采用的特征 proot(ri)：对root归一化的概率 pcfg(ri)：类cfg概率 is_lexicalized(ri)：是否词汇化规则 is_composed(ri)：是否组合规则 is_lowcount(ri)：是否出现三次以下 lex_pef(ri)：短语翻译概率 lex_pfe(ri)：反向短语翻译概率 m1(ri)：IBM model 1 m1inv(ri)：反向IBM Model 1 lm(e)：语言模型 wp(e)：单词数惩罚 Marcu的论文没有对Pcfg多加解释。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Galley Vs. Och Och的对齐模板模型 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Marcu Vs. Och 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Marcu Vs. Och 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 Analysis Galley Good results with very poor feature functions Very promising It’s reasonable to find that C4 > C3 > Cm due to their difference in expressive power Marcu Outperform Och’s ! The results are really confusing. I suppose that: m2c > m2 > m1c > m1 Marcu suspect the decoder still makes many search errors 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 内容提要 概述 同步语法概念 反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 总结 同步语法 形式化基于句法的翻译模型 最大熵括号转录语法模型 层次化短语模型 语言学基于句法的翻译模型 树到串对齐模板模型 ISI的串到树模型 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
Views on String-to-Tree Vs. Tree-to-String Galley The target language (i.e. English) has syntactic resources (parsers and treebanks) that are considerably more available than for the source language There is less benefit in modeling the syntax of the source language, since the input sentence is fixed during decoding and is generally already grammatical Liu Source analysis may be important Ill-formed source trees make the Tree-to-String decoder difficult to seek the “true” translation. We can never expect good syntactically-motivated reordering under ill-formed source tree structures. In contrast, the input of String-to-Tree decoding is source string. The decoder may build a reasonable target tree with the help of language model even though the rules are learned from ill-formed target trees in training data. Tree-to-String decoding is useful for translating resource-rich languages (e.g. English) into resource-poor languages (e.g. Inuktitut) 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
ISI Vs. ICT ISI ICT model string-to-tree tree-to-string phrasal compatibility full partial features 11 7 extraction algorithm top-down bottom-up unaligned words attachment multiple single decoding algorithm bottom-up CKY bottom-up beam search rule binarization yes no nbest derivation generation nbest list generation treat BPs as special rules improve fluency using BPs 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
Comparison Chiang Galley Marcu Liu model formal syntax string-to-tree tree-to-string tree annotations single-level multi-level syntactically-motivated no yes phrasal compatibility enable discontinuous source phrases feature functions 8 1 11 7 Marcu的短语抽取方法是以每个短语为起点向上抽取的，短语左右的结点都抽象为变量，因此抽出来的规则是短语兼容的，而且没有不连续的短语。 机器翻译原理与方法(05) 基于句法的统计机器翻译方法
机器翻译原理与方法(05) 基于句法的统计机器翻译方法 讨论 机器翻译原理与方法(05) 基于句法的统计机器翻译方法