机器翻译原理与方法 第五讲 基于句法的统计机器翻译方法 刘群 中国科学院计算技术研究所 liuqun 中国科学院计算技术研究所 2009 年秋季课程 2机器翻译原理与方法 05 基于句法的机器翻译方法 内容提要 概述概述 同步语法概念 反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 3机器翻译原理与方法 05 基于句法的机器翻译方法 概述 基于短语的统计翻译方法的问题 基于句法的统计翻译方法的分类 目前的进展 4机器翻译原理与方法 05 基于句法的机器翻译方法 基于短语的统计翻译方法的问题 泛化能力差 中国大使馆 美国大使馆 月球大使馆 产生的句子不符合语法 短语的简单组合 没有句法结构 无法表示不连续的短语搭配的翻译 召开了一次关于 的会议 hold a meeting on 无法进行长距离的语序调整 解决办法 引入句法结构 5机器翻译原理与方法 05 基于句法的机器翻译方法 统计机器翻译方法的金字塔 Syntax based Phrase based Semantic based Interlingua Word based Source LanguageTarget Language 6机器翻译原理与方法 05 基于句法的机器翻译方法 基于句法的统计机器翻译模型 1 syntax level phrase level 7机器翻译原理与方法 05 基于句法的机器翻译方法 基于句法的统计机器翻译模型 1 linguistic syntax level formal syntax level phrase level 8机器翻译原理与方法 05 基于句法的机器翻译方法 基于句法的统计机器翻译模型 1 phrase based model formally syntax based model linguistically syntax based model string to tree model tree to string model tree to tree model 9机器翻译原理与方法 05 基于句法的机器翻译方法 基于句法的统计机器翻译模型 2 形式上基于句法的模型 不使用任何语言学知识 所有句法结构直接从未标注的语料库中自动学习得到 语言学上基于句法的模型 使用语言学知识 语言通常要从句法树库训练得到 树到串模型 只在源语言端使用语言知识 串到树模型 只在目标语言端使用语言知识 树到树模型 在源语言端和目标语言端都使用语言知识 10机器翻译原理与方法 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 11机器翻译原理与方法 05 基于句法的机器翻译方法 语言学上基于句法的模型 串到树模型 String to Tree Model 美国南加州大学信息科学研究所 ISI CSU 的工作 Yamada 2001 Galley 2006 Marcu 2006 树到串模型 Tree to String Model 中科院计算所的工作 Tree to string Alignment Template Model TAT Yang Liu ACL2006 微软研究院的工作 依存模型 Dependency Treelet Translation Quirk 2005 树到树的模型 Tree to Tree Model 12机器翻译原理与方法 05 基于句法的机器翻译方法 内容提要 概述 同步语法概念同步语法概念 反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 13机器翻译原理与方法 05 基于句法的机器翻译方法 同步语法 1 定义 同步语法是一种形式语法 这种语 法的每一次推导 都在两种或者两种以上 语言中同步生成一个句子 同步语法同步语法 I We We are Chinese China is the country with the largest population in the world 我 我们 我们是中国人 中国是世界上人口 最多的国家 14机器翻译原理与方法 05 基于句法的机器翻译方法 同步语法 2 同步语法的具体形式 同步上下文无关语法 SCFG 反向转录语法 ITG 和括号转录语法 BTG 同步树替换语法 STSG 同步树粘接语法 STAG 多文本语法 MTG 同步语法的应用 编译中的代码生成 自然语言的语义解释 自然语言的机器翻译 双语语料库的对齐 15机器翻译原理与方法 05 基于句法的机器翻译方法 同步语法 3 同步语法与统计机器翻译 同步语法是很多基于句法的统计机器翻译模型 的理论基础 理论上说 如果采用同步语法 在完成源语言 句法分析的同时 目标语言就生成了 因此可 以利用各种成熟的句法分析算法进行机器翻 译 而无需另外设计专门的翻译算法 另一方面 采用同步语法对源语言进行句法分 析时 要把目标语言的因素考虑进来 这不同 于通常的句法分析 16机器翻译原理与方法 05 基于句法的机器翻译方法 内容提要 概述 同步语法概念 反向转录语法和括号转录语法反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 17机器翻译原理与方法 05 基于句法的机器翻译方法 反向转录语法 Inversion Transduction Grammar ITG 吴德凯 1997 onwards ITG 是一种形式最简单的同步语法 可以并行地 生成两颗对齐的句法树 ITG 的规则都是乔姆斯基范式形式的 规则的右部或者全部是终结符 或者全部是终结符 非终结符规则都是二分的 ITG 的规则可以指定语序的变化 保序 或 逆序 ITG 中两种语言的规则使用同一套非终结符 ITG 中对规则的二分限制降低了搜索的复杂度 18机器翻译原理与方法 05 基于句法的机器翻译方法 反向转录语法 ITG rulesSourceTarget 终 结 符 规 则非符 A B C A BCA BC A A BCA CB 终 结规 则符 A x yA xA y 开始 BVP S S BNP PP VP The e game 比赛 will e start on e Wednesday星期三 target source straightinverted 19机器翻译原理与方法 05 基于句法的机器翻译方法 反向转录语法 20机器翻译原理与方法 05 基于句法的机器翻译方法 基于反向转录语法的统计机器翻译 1 训练 从词语对齐的语料库中自动抽取规则 解码 类似于一个概率化句法分析的过程 利用规则的源语言部分进行句法分析 存在源语言部分相同而目标语言部分不同的规则 保 序或逆序 这是不同于传统句法分析的地方 句法分析时 对于源语言部分相同而目标语言部分不 同的规则 需要通过概率计算进行评分 这相当于对 译文语序进行选择 句法分析完成的同时也就生成了译文句法结构和 译文句子 21机器翻译原理与方法 05 基于句法的机器翻译方法 基于反向转录语法的统计机器翻译 2 22机器翻译原理与方法 05 基于句法的机器翻译方法 基于反向转录语法的统计机器翻译 3 23机器翻译原理与方法 05 基于句法的机器翻译方法 括号转录语法 Bracketing Transduction Grammar BTG BTG 是 ITG 的一个特例 其中只有唯一的一个非 终结符 X 可以这么理解 BTG 仅仅给出了两种语言的句子 结构结构之间的对应关系 没有任何句法标记信 息 如 NP VP 等等 24机器翻译原理与方法 05 基于句法的机器翻译方法 统计机器翻译中语序调整的方式 无约束 所有匹配都运行 所有语序调整都是允许的 对于 N 个词 或短语 在 IBM 约束下 语序调整有 N 种可能 性 搜索空间随着句子长度呈指数级增长 因此其搜索问题是 NP 问题 IBM 约束 IBM Constrains 为了减少搜索空间 通常在从左到右的解码过程中都会采用 IBM 约束来限制语序调整的搜索空间 也就是说 每次只选择最左边 若干个未被翻译的词语进行翻译 对 Hypothesis 进行扩展 IBM 约束可以大大减少搜索空间 但依然存在大量非法语序调整 BTG 约束 BTG Constrains 只有能够满足某种 BTG 映射的语序调整才是允许的 BTG 约束大大降低了搜索空间大小 确保搜索范围内的语序调整 都满足语法约束 同时不在搜索范围内的约束都不满足语法约束 BTG 约束搜索使得长距离语序调整成为可能 25机器翻译原理与方法 05 基于句法的机器翻译方法 这里给出了四个词的所有可能的调序方案以及对应的 BTG 转换模式 其中有两种方案在 BTG 约束下是不允许的 找不到对应的 BTG 转换模式 26机器翻译原理与方法 05 基于句法的机器翻译方法 BTG 约束导致搜索空间大大压缩 word reordering which are not permitted in BTG 27机器翻译原理与方法 05 基于句法的机器翻译方法 真实自然语言的翻译满足 BTG 约束吗 对于汉语和英语之间的翻译 几乎满足 一个例外 出处 对于一些自由语序的语言 不一定满足 28机器翻译原理与方法 05 基于句法的机器翻译方法 内容提要 概述 同步语法概念 反向转录语法和括号转录语法 基于最大熵括号转录语法的翻译模型基于最大熵括号转录语法的翻译模型 同步上下文无关语法和同步树替换语法 层次短语模型 树到串翻译模型 串到树翻译模型 总结 29机器翻译原理与方法 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 30机器翻译原理与方法 05 基于句法的机器翻译方法 BTG 的主要问题 两条主要合并规则 A A A 0 8 A A A 0 2 如何使用这两条规则 stochastic BTG 给 每条规则赋以先验概率 先验概率是一种非常粗糙 简单的处理方 法 不能有效地处理重排序问题 31机器翻译原理与方法 05 基于句法的机器翻译方法 ME BTG 基本思想 在 BTG 框架下 将重排序问题看作是一个 2 类分 类问题 条件