（模式识别与智能系统专业论文）基于短语统计机器翻译的柱搜索解码器的优化及实现.pdf

中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名： 、罗毅 o _ 7 年6 月 | 中固 ： 学技术人学坝 。学位论文 摘簋 摘要 基于短语的统计机器翻译方法是当前统计机器翻译研究的热点。在统计 机器翻译中解码器的作用就是根据学习到的模型信息寻找源语言句子中最 可能的目标译文。本文在柱搜索算法的基础上，设计并实现一个高效的基于 短语统计机器翻译的解码器。 本文首先介绍了解码器中加入的多个特征模型，包括基本的短语翻译模 型，目标语言模型以及附加的扭曲模型、词语惩罚模型、短语惩罚模型。解 码器以这些特征模型作为信息输入，对源语言句子进行解码搜索。 柱搜索算法采用启发式规则对搜索过程中的节点进行高效剪枝，在人工 智能领域中得到广泛的使用。本文采用柱搜索算法丌展解码器的研究工作， 其主要贡献是： l 、设计完成了整个解码系统，给出了系统构建中主要流程的一些算法。 主要包括翻译选项表的构建、将来概率表的计算，柱搜索解码，n b e s t 回溯 等算法。 2 、提出了改进的剪枝策略。动态剪枝策略提高栈大小剪枝精度，预剪枝 策略根据栈阂值进一步提高剪枝速度。 3 、提出了改进的位置重排限制方法。通过避免不完全路径和减少重复扩 展的设计思想，提出一种新的位置重排限制方法。实验表明，该方法不仅能 在扩展速度上比当前的位置重排限制提高一倍，而且扩展精度也得到提高。 4 、提出了领域术语翻译方法。针对领域术语翻译效果不理想的问题，提 出了利用术语词典对领域术语进行特殊处理的方法。 关键词：统计机器翻译；解码算法：柱搜索：动态剪枝；位置重排限制 中国科学技术大学硕士学位论文 英文摘要 a b s t r a c t p h r a s e b a s e ds t a t i s t i c a lm a c h i n et r a n s l a t i o ni st h eh o t s p o ti nt h ec u r r e n t s t a t i s t i c a lm a c h i n et r a n s l a t i o nr e s e a r c ha r e a t h ed e c o d e r sj o bi st of i n dt h e t r a n s l a t i o nt h a ti sm o s tl i k e l ya c c o r d i n gt os e to fp r e v i o u s l yl e a r n e dm o d e l i n f o r m a t i o ni nt h es t a t i s t i c a lm a c h i n et r a n s l a t i o n i nt h et h e s i sw ed e s i g na n d i m p l e m e n ta ne f f i c i e n tp l l r a s e b a s e ds t a t i s t i c a lm a c h i n e t r a n s l a t i o nd e c o d e rb a s e d o nt h eb e a ms e a r c ha l g o r i t h m i nt h et h e s i s ，w ef i r s t l yg i v ea ni n t r o d u c t i o no f t h em u l t if e a t u r e sw h i c h a d d e d i n t ot h ed e c o d i n gp r o c e s s t h e s em u l t if e a t u r e si n c l u d eb a s i cl a n g u a g em o d e l ， p h r a s eb a s et r a n s l a t i o nm o d e la n da d d i t i o n a ld i s t o r t i o nm o d e l ，w o r dp e n a l t y m o d e l ，p h r a s ep e n a l t ym o d e l t h e d e c o d e ru s e st h e s ef e a t u r e sa s i n p u t i n f o r m a t i o nt of i n dt h em o s tl i k e l yt r a n s l a t i o n t h eb e a ms e a r c ha l g o r i t h mu s e st h eh e u r i s t i cr u l et ot h es e a r c hp r o c e s sn o d e s b yt h eh i g h l ye f f e c t i v ep r u n i n g 。 t h i st h e s i sm a i n l yf o c u s e so nt h ed e s i g na n di m p l e m e n t a t i o no fd e c o d e r b a s e db e a ms e a r c ha l g o r i t h m ，a n dn e wc o n t r i b u t i o n so f t h et h e s i sa r e ： ( 1 ) t h ew h o l es y s t e mh a sb e e nd e s i g n e da n dc o m p l e t e d s o m ea r i t h m e t i co f t h ep r i m a r yf l o wi sg i v e n i tm a i n l yi n c l u d ec o n s t r u c to f t r a n s l a t i o no p t i o nt a b l e ， c o m p u t i n gf u t u r ec o s tt a b l e ，b e a ms e a r c hd e c o d i n ga n d n - b e s tt r a n s l a t i o nt r a c i n g ( 2 ) a ni m p r o v e dp r u n i n gs t r a t e g yp m p o s e d d y n a m i cp r u n i n gs t r a t e g yi s u s e dt oi m p r o v et h ea c c t l r a c yo fs t a c ks i z ep r u n i n g ；t h ep r e - p r u n i n gs t r a t e g y f u r t h e re n h a n c e st h ep r u n i n gs p e e da c c o r d i n gt ot h es t a c kt h r e s h o l dv a l u e ( 3 ) a ni m p r o v e dr e o r d e r i n gc o n s t r a i n s m e t h o di s p r o p o s e d b ya v o i d i n g i n c o m p l e t es e a r c hp a t ha n dt h er e d u c e dr e e x p a n s i o nd e s i g nt h o u 曲gan e w r e o r d e r i n gc o n s t r a i n sm e t h o di sp r o p o s e d e x p e r i m e n t ss h o wt h a tt h em e t h o dn o t o n l yh a st h ed o u b l ee x p i a t i o ns p e e dt h a nc u r r e n tr e o r d e r i n gc o n s t r a i nm e t h o db u t a l s og e tt h eh i g h e re x p i a t i o np r e c i s i o m ( 4 ) ad o m a i nt e r mt r a n s l a t i o nm e t h o di sa l s op r o p o s e d t h ee f f e c to f d o m a i n t e r mt r a n s l a t i o ni sn o ts a t i s f a c t o r y ；w ep r e s e n tas p e c i a lp r o c e s sa p p r o a c hw i t l l d o m a i nd i c t i o n a r ys u p p o r t e d k e y w o r d s ：s t a t i s t i c a lm a c h i n et r a n s l a t i o n ；d e c o d i n ga l g o r i t h m ；b e a ms e a r c h ； d y n a m i cp r u n i n g ；w o r dr e o r d e r i n gc o n s t r a i n 2 中国科学技术大学硕士学位论文绪论 1 1 引言 第一章绪论 自然语言处理( n a t u r a ll a n g u a g ep r o c e s s i u g , n l p ) 是计算机科学、语言学、心 理学、认知科学和数学等多学科交叉而成长起来的- - f - i 边缘学科，常常又被称为 计算语言学( c o m p u t a t i o n a ll i n g u i s t i c s ) 。由于自然语言处理的研究和处理对象是 人类自然形成的极其复杂的语言现象，所以极具艰巨性，事实上，自4 0 年代产 生以来，这门学科经历了十分曲折的发展历程。不过，随着信息社会的到来，由 于在机器翻译、信息检索、人机接口等信息处理领域有着广泛的应用前景，自然 语言处理又恢复了它应有的勃勃生机。 机器翻译( m a c h i r e t r a n s l a t i o n , m t ) 是自然语言处理的主要目标之一，是自 然语言处理的一项重要应用。机器翻译是利用计算机把一种自然语言转变成另一 种自然语言的过程。用以完成这一过程的软件叫做机器翻译系统。当今社会，随 着信息化程度的急剧提高，信息高速公路深入人心。但是目前国际互联网使用的 主要语言是英语，有8 0 的站点位于说英语的国家，语言障碍已经成为限制信息 化程度提高的主要因素之一。在这种环境下，机器翻译研究成为众多学者的研究 热点，并由于巨大的市场潜力而受到越来越多的关注。统计机器翻译方法由于其 数学推导严密、模型一致性好、可以自动学习、鲁棒性强等优点，越来越受到人 们的重视。 1 2 机器翻译的分类 机器翻译的研究自计算机的诞生之初就被提出来了。在近6 0 年的发展过程 中，经历了曲折道路，有成功和兴奋，但更多是挫折和困惑。机器翻译研究也如 人工智能的其他研究一样。困惑重重，对研究者提出了无数的挑战这正说明人 类对智能、对语言机制认识的长期性。l l 肛1 人类对机器翻译的研究可追述到二十世纪四十年代电子计算机问世之时。当 时的方法非常简单，以双语字典为基础进行直接翻译，因此效果无法令人满意。 8 0 年代初，随着计算语言学的发展，人们采用了一种间接的翻译方法，邸通过 较深层次的语言分析，将源语言文本转换成某种意义上的抽象表达，以生成一个 或多个目标语言。这也就是通常所说的基于规则的方法。 1 9 8 9 年以来，机器翻译的发展进入了一个新纪元其重要标志是引入了基 于语料库的各种翻译方法。基于语料库的方法又可以分为基于统计的方法和基于 中国科学技术大学硕士学位论文绪论 实例的方法。传统的基于规则的方法又可以称为理性主义方法，与之相对，基于 语料库的方法又可以称为经验主义方法。 中国是继美、荚、苏之后世界上第四个开展机器翻译研究工作的国家，早在 1 9 5 6 年，机器翻译就被列入我国科学研究的发展规划。1 9 5 7 年，当时的中国科 学院语言研究所和计算技术研究所合作，率先开展了俄汉机译研究，为此语言研 究所还正式成立了机器翻译研究组。我国m t 研究的全面开展是在上个世界8 0 年代中期以后。特别是9 0 年代以来，一批m t 系统先后问世，并且推出了商品 化系统。此外，我国各大学纷纷开展m 【t 研究，研制了英汉、汉英、俄汉、日汉、 德汉翻译实验系统，发表了许多成果。1 3 1 1 4 1 2 1 基于规则机器翻译方法 基于规则的机器翻译( r u l e - b a s e dm a c h i n et r a n s l a t i o n ) 技术是最成熟的，也是 到目前为止应用最广的，目前商用的机器翻译系统一般都是基于规则的。基于规 则的机器翻译系统主要是这样的过程：通过对语言现象的综合和认识，不断总结 其规律，形成自己的语法语义规则体系，包括单语的分析规则和双语转换规则。 系统利用这些规则来分析输入的语言。形成一种内部表示。 从总体模式上基于规则的机器翻译方法可以分为三类【，j ：直接翻译法、中间 语言法以及转换法。直接翻译法从源语言的表层句子出发，将单词或固定词组直 接里换成目标语言的对应成分。中间语言法把源语言经过分析转换成一种对所有 语言都适合的一种句法语义表示，从这种表示可以生成任何一种目标语言。 在设计多种语言互译的机器翻译系统时，这种方法在理论上是非常经济的。转换 方法采用两种内部表达并按三个阶段进行翻译，第一个阶段把源语言转换成源语 言的内部表达，第二阶段把源语言的内部表达转换成目标语言的内部表达，第三 阶段再根据目标语言的内部表达生成目标语言。根据这种内部表示和相应的转换 规则转换成相应的目标语言的内部示，并形成译文。基于规则的机器翻译发展到 今天，相对来说已比较成熟。 然而，语言往往是一个民族几千年经验的积累，通常是约定俗成而又动态发 展的。随着社会的不断发展，新的词汇和语言现象会不断的出现。现有的机器翻 译系统的规则再多，都只是特定语言现象的总结和概括。所以单纯采用基于规则 的自然语言处理系统难以应付现实世界中复杂多变的语言现象。并且由于专家描 述的规则性知识通常颗粒度较大，不利于处理大量的细节，因而在处理大规模的 开放语料时，往往会遇到难以克服的困难。 6 中国科学技术大学硕士学位论文绪论 1 2 2 基于实例的机器翻译方法 基于实例的机器翻译( e x a m p l e b a s e dm a c h i n et r a n s l a t i o n ) 的基本思想是由日 本著名机器翻译专家长尾真提出的。他于1 9 8 4 年发表的论文“a f r a m e w o r k o f a m e c h a n i c a lt r a n s l a t i o nb e t w e e nj a p a n e s ea n d e n g l i s hb ya n a l o g yp r i n c i p l e ”可视为 这一研究领域的起点。 长尾真主张 6 1 ，语言学数据是比语言学理论更可靠的知识源，因此也可以为 机器翻译系统奠定更坚实的基础。他建议使用无标注的实例数据库和一个等价词 对的集合作为系统的知识源( 动词例外，需要使用格框架表达) ，翻译引擎主要负 责计算输入句子和候选实例中词汇间语义的相似性。 这种方法实际上是模拟了人类翻译的过程：人类不通过做深层语言学分析翻 译句子：人类的翻译过程是首先正确分解输入句子，分解成短语碎片，接着，把 这些短语碎片译成其它语言短语，最后把这些短语合并成长句。每个短语碎片采 用类比的原则进行翻译。 这种方法能吸引很多研究人员注意的优点有：容易产生高质量的译文，一旦 输入能和实例精确匹配，译文的质量是基于规则的方法所不能比的。可以避免一 些传统的基于规则机器翻译必须进行的深层次语言学分析。系统维护容易，系统 中知识以翻译实例和语义词典等形式存在，可以很容易的利用增加实例和词汇的 方式扩充系统。 1 2 3 基于统计的机器翻译方法 随着计算机性能大幅度的提高，昔日大型计算机才能胜任的工作今日工作站 或个人计算机就能够完成，也有了大量的联机语料供统计使用，在自然语言处理 领域，统计方法又获得新生。统计方法己经成功地用来处理语音自动识别、词典 编纂、词法分析等问题。 基于统计( s t a t i s t i c a lm a c h i n et r a n s l a t i o n ，s m t ) 的机器翻译方法假设源语言的 每句话都有可能翻译成目标语言中的任何一句话，翻译的目标就是找出其中对应 概率最大的映射，模型中所用到的各种概率参数通过统计语料库获取。 基于统计的机器翻译方法最早是由i b m 的p b r o w h 等研究者提出来的。他 们受到语音识别研究的启发，应用了类似的方法。以大规模英法双语语料库( 3 百万句对) 为基础，对源语言和目标语言词语的对应关系进行统计，根据统计规 律输出译文。这种方法没有使用语言知识，却也取得4 8 的正确率。其主要特征 是概率统计与随机过程的方法成为了分析和生成过程中的唯一方法。应该说，基 7 中国科学技术大学硕士学位论文 于统计机器翻译方法的出现改变了机器翻译研究的面貌，从而开始了机器翻译研 究的新阶段。 基于统计的方法需要大规模双语语料，其翻译模型、语言模型参数的准确性 直接依赖于语料的多少，其翻译质量主要取决于概率模型的好坏和语料库的覆盖 能力。同时翻译模型、语言模型在简化过程中也带来一些缺陷，在简化和可行之 间存在一个权衡问题。基于统计的方法不需要大量知识的依赖，直接靠统计结果 进行歧义消解处理和译文的选择。避开了语言理解的诸多难题。统计机器翻译方 法由于其数学推导严密、模型一致性好、可以自动学习、鲁棒性强等优点，越来 越受到人们的重视。 1 3 统计机器翻译方法的演变 1 3 1 从信源信道模型到最大熵方法嗍 基于信源信道模型统计机器翻译 基于信源信道模型的统计机器翻译方法的基本思想把机器翻译看成是一个 信息传输的过程，如图l - l 所示： 目标语言t 源语言s 图l l 信源信道模型 假设一段目标语言文本t ，经过某一噪声信道后变成源语言s ，也就是说， 假设源语言文本s 是由一段目标语言文本t 经过某种奇怪的编码得到的，那么 翻译的目标就是要将s 还原成t ，这也就是一个解码的过程。 统计机器翻译认为翻译过程就是从给定源语言句子f j = f l f i 目的所有目标 语言句子e i = e l e i e i 中寻找概率最大的句子。作为最佳译文。最初的信道模 型【8 1 中将翻译过程表示为： 仑4 = a r g m a x p r ( e 。i ，。) 一 ( 1 1 ) p r ( ，。) 是目标语言e 出现的概率，称为语言模型。反映的是一个句子在目标 语言中出现的可能性，实际上就是该句子在句法语义等方面的合理程度； p r ( 。) 是由目标语言文本t 翻译成源语言文本s 的概率，称为翻译模型，体现 源语言句子到目标语言句子的互翻译可能性；a r g m a x 是搜索最大概率t7 的算予， 这个算子的搜索过程在统计机器翻译中又称为解码过程。 中国科学技术大学硬士学位论文 绪论 基于最大熵的统计机器翻译 o c h 等人在进行统计机器翻译实验时发现，把i b m 统计机器翻译基本方程式 中的翻译模型换成反向的翻译模型，总体的翻译正确率并没有降低，这用信源信 道理论是无法解释的。于是，他们借鉴了f 9 1 0 j 中统计自然语言理解的一种思路， 提出了基于最大熵的统计机器翻译方法【i l 】。这是一个比基于信源信道的统计机器 翻译方法更为一般化的一种方法，基于信源信道的方法可以看作是基于最大熵的 方法的一个特例。 最大熵，又称最大熵原理，或者最大熵方法，是一种通用的统计建模的方法。 对于一个随机事件，假设我们已经有了一组样例，我们希望建立一个统计模型， 来模拟这个随机事件的分布。 为此，我们就需要选择一组特征，使得我们得到的这个统计模型在这组特 征上，与样例中的分布完全一致，同时又保证这个模型尽可能的“均匀”( 也就 是使模型的熵值达到最大) ，以确保除了这一组特征之外，这个模型没有其他的 任何偏好。依据这个原则的统计建模方法就是最大熵方法。 假设e 、f 是机器翻译的目标语言和源语言句子，h ( 8 。，。) 为口。和，之间的 特征模型，屯为特征模型的权重因子。，那么直接翻译概率可以用以下公式模拟： ，i 厂- ，) ： 朋五m h m ( e i , f j p r ( e e x p ( x ；f ) ) z ( 厂，)i 厂。) =) ) z ( 厂。) 研 ( 1 2 ) 其中z ( f 。) 为一个标准常量，此时翻译过程又可以表示为： e 7 = a r g 哪( 笠锄( e 7 ，f j ) ) e 。 卅 ( 1 3 ) 而对于给定的f ，其最佳译文e 可以用以下公式表示： ；= a r g m a x p r ( e l d ) 丛 = a r g m a x 以( p ，) ) ”“ ( 1 - 4 ) 可以看到，如果我们将两个特征分别取为l o gp ( e ) 和l o gp ( f l e ) ，并取柚= x 2 = l ，那么这个模型就等价于信源信道模型。在统计机器翻译中最大熵方法建模 的统计机器翻译思想又称为对数线性模型思想。 与此同时，统计机器翻译的模型经历了从基于词的模型到基于短语的模型过 程。下面我们介绍下这个过程中的典型方法。 9 中国科学技术大学硕士学位论文 1 3 2 从基于词的模型到基于短语的模型 基于词的模型：i b m 模型1 5 【2 1 对于翻译模型p r ( f l e ) ，i b m 公司提出了5 种复杂程度递增的数学模型，简称 为i b m 模型1 5 。模型l 仅考虑词与词互译的概率t ( o l e i ) 。模型2 考虑了单词 在翻译过程中位置的变化，引入了参数p r ( a j l j ，m ，1 ) ，m 和1 分别是目标语和源语 句子的长度，j 是目标语单词的位置，匈是其对应的源语单词的位置。模型3 考 虑了个单词翻译成多个单词的情形，引入了产出概率由( n l e i ) ，表示单词e i 翻 译成n 个目标语单词的概率。模型4 在对齐时不仅仅考虑词的位置变化，同时考 虑了该位置上的单词( 基于类的模型，自动将源语言和目标语言单词划分到5 0 个类中) 。模型5 是对模型4 的修正，消除了模型4 中的缺陷，避免对一些不可 能出现的对齐给出非零的概率。 这些模型的主要区别在于计算源语言单词和目标语言单词之间的连接 ( c o n n e c t i o n ) 的概率的方式不同。模型l 最简单，只考虑词与词之间互译的概 率，不考虑词的位置信息，也就是说，与词序无关。好在模型l 的参数估计具 有全局最优的特点，也就是说最后总可以收敛于一个与初始值无关的点。模型2 到s 都只能收敛到局部最优，但在i b m 的实验中，每一种模型的参数估计都依 次把上一种模型得到的结果作为初始值，可以看到最后的结果实际上也是与初始 值无关的。 从理论上说，i b m 的模型只考虑了词与词之间的线性关系，没有考虑句子的 结构。这在两种语言的语序相差比较大时效果可能会不太好。如果在考虑语言模 型和翻译模型时将句法结构或语义结构考虑进来，应该会得到更好的结果。 基于短语的模型 i b m 模型的一个缺点就是不能考虑一个词语翻译多个目标词语的情况，虽然 这个问题可以通过在解码过程中插入零繁衍的词来解决，但是这样的插入不能考 虑插入位置的上下文关系，其效果也不是很好。为此很多学者开始研究了以短语 为基本单位的模型的研究。 基于短语的翻译可以被追溯到o c h 1 3 1 的对齐模板模型，这个对齐模板模型可 以经过重新设计而转化成短语翻译系统。其他的研究者，如y a m a d a 和k n i g h t t “l 在他们的基于句法的机器翻译系统中使用了短语翻译来增强他们的系统。 m a r c u 和w o n gl ”】引入了短语翻译的联合概率模型。此时，大部分有竞争力 的统计机器翻译系统都是使用短语翻译，例如c m ui t 6 和i b m 1 7 1 系统。基于 短语的系统已经在近来的国际机器翻译竞赛中走到了前台( d a r p at i d e s2 0 0 3 中英、阿拉伯英语评测) 。 中国科学技术大学碗士学位论文 绪论 不同的基于短语系统的区别在于短语翻译表创建的方式不同。比如，o c h 的 短语对齐模板在i b m 模型词语对齐的基础采用启发式的规则抽取短语，而m a r e u 和w o n g 则直接从语料库中训练对齐的短语对。 在使用基于短语的模型进行解码时，首先对源句子进行短语级的划分，在此 基础上进行搜索加入了局部上下文( 1 0 c a lc o n t e x t ) ，使目标语言的构建更为合理 和符合自然语言特征。对于短语间的位置关系可以通过加入短语位置重排方式结 合扭曲模型进行惩罚。 1 4 统计机器翻译解码算法 早在1 9 9 0 年，i b m 的b r o w n 等人提出统计机器翻译的时候，解码器就作为 与翻译模型、语言模型并列的三大基础问题进行研究，解码就被视为以语言模型、 翻译模型和源语言句子为输入查找最可能的译文的过程。对于统计机器翻译而 言，解码在最简单的i b m 翻译模型l 和一元语言模型下都是一个n p 问题【l s 】， 因为搜索空间一般都是随着源语言句子的大小呈指数增长的，要在多项式时间内 找到全局最优解是不可能的，研究的目的趋向于如何在可解的时间内找到接近全 局最优的次优解。 第一个面向解码问题的算法出现在语音识别领域的基于栈的搜索算法【1 9 1 ，在 统计机器翻译领域中针对这个问题提出过多个算法。最初i b m 采用受限的基于 栈的搜索算法1 2 0 懈决解码问题其时间复杂度为指数级，w a n g 和w a i b e l z i l 在这个 算法上进行改进提出了更快的搜索算法。在进行第一次解码问题时间复杂度的研 究时，k e v i nk n i g h t 认为解码问题可以近似的理解成著名的旅行商问题 ( t r a v e l i n gs a l e s m a np r o b l e m ) ，c h r i s t o p ht i l l m a n t 2 2 1 了h e l d - k a r p 用于t s p 的动 态规划算法，最初h e l d k a r p 用于t s p 的动态规划算法在调整到解码问题时的时 间复杂十分高，为o ( 1 3 m 2 2 m ) 。o “n 5 2 m ) ( 1 ，i n 分别为源和目标语言句子长度) 。 为此t i l l m a n 和n e y 【2 3 l 了加入重排位置限制的方法将h e l d k a r p 的时间负责度降 为o ( 1 3 m 4 ) 一o ( m t ) 。t i l l m a n 的快速贪婪算法【8 】使时间复杂度降到o ( m 6 ) 来提高 解码速度。o c h l 2 4 】了一个基于a 算法的解码器能够很好的进行短句子的翻译。 由于最优解很难在合理的少量的时间内进行搜索，大量的研究工作关注于搜索较 好的次优解上，g e r m a n ( 2 0 0 3 ) 提出了贪婪搜索算法将时闻复杂度从o ( m 6 ) 将为 o ( m 2 ) 而被评为当年a c l 上的最佳论文。贪婪算法以搜索精度的降低换来了速度 的提高，快速又有效的解码搜索算法还需要进行进一步的研究。 除了上面所说的贪婪算法外，其他的算法在搜索过程中都用到了翻译假设的 概念。翻译假设用于表示搜索过程的部分翻译信息。在翻译假设中，一些源语言 词语被翻译成目标词语，并以模型信息进行评分。在翻译的过程中，系统保留了 中霉科学技术大学硕士学位论文绪论 大量的翻译假设，每个翻译假设对应一个模型评分值。搜索过程没有翻译的初始 假设开始进行不断扩展，每次扩展翻译假设未翻译的单词生成多个不同的假设， 直至扩展完成搜索结束。搜索的结果为评分最高的的最终假设。根据对翻译假设 扩展方式不同，分出不同的搜索算法：a 算法使用最优优先的方式，栈搜索采 用深度优先方式，动态规划算法采用宽度优先的方式。 a 搜索是一种栈解码算法，解码过程中所有的假设被放在一个按评分进行 排序的优先队列中。这个算法得主要的缺点是，由于未翻译词语多的翻译假设评 分较高，因此这个算法趋向于先扩展未翻译词语多的翻译假设从而导致搜索十分 慢。为了解决这个问题，需要加入一个启发式函数估计假设的完全评分。 栈搜索根据源句子中己翻译的单词不同将假设保存到不同的栈中，因此它将 有达2 m 个栈。在搜索过程中可以扩展不同的翻译完成程度的翻译假设，在每次 扩展遍历所有栈的那些评分最好的假设。所以每遍历一次至少会产生一个完成的 翻译假设。 动态规划算法将翻译假设作为搜索树中的节点保存下来，树中的节点采用宽 度优先的方式扩展，每次扩展栈中所有的子节点。传统的动态编程算法的搜索空 间很大，结合启发式规则限定栈大小剪枝方式的b e a ms e a r c h ( 柱搜索) 算法可 以搜索能在性能和速度上取得很好的折中。 在实践中穷尽搜索假设空间是不可能的，启发式的b e a ms e a r c h ( 柱搜索) 便是找到最优或近似最优的解的合理选择。柱算法是一种在入工智能领域中广泛 使用的搜索算法，它采用宽度优先的方式构建搜索树，利用启发式觌则剪枝来选 取最优的前n 个状态进行扩展，避免了贪婪算法的陷入局部最优的风险，又能 在搜索速度和性能上取得很好的折中，在统计机器翻译中得到了广泛的重视。在 国内，2 0 0 6 年由第二届统计机器翻译研讨会上，由中科院计算所联合中科院自 动化所，厦门大学，中科院软件所和哈尔滨工业大学共五家研究单位完成了一个 基于短语的统计机器翻译系统使用的三个解码器“绿洲”、“商队”、“骆驼”采用 的也都是柱搜索算法。 1 5 本论文的提出 统计机器翻译不需要具有大规模的语言学知识，各种参数的训练是与具体的 语言对无关的。目前采用的基于短语的统计机器方法由于考虑了词语之间的上下 文信息，在原i b m 词对词翻译模型基础上作了重大的改进。该方法从词语翻译 的基础上抽驭语料库中的双语短语互译信息，避免了词语繁衍问题并减少了词语 间位置扭曲影响。 在统计机器翻译系统中，解码的目的就是从给定语言模型，翻译模型和其它 中国科学技术大学硕士学位论文绪论 模型的信息基础上根据输入的源语言句子找到最可能译文。无论模型如何解码过 程都将是一个求解离敌最优解的n p 问题l 。 本文采用对数线性模型的思想研究了n 元目标语言模型、短语翻译模型、短 语词典概率模型、扭曲模型、词语惩罚模型、短语惩罚模型。在这些模型的基础 上采用b e a ms e a r c h ( 柱搜索) 算法实现了基于短语的统计机器翻译解码器。在 进行解码器的设计与实现过程中，研究语言模型和短语翻译表的存储结构以便进 行快速访问；采用动态规划的思想构建翻译选项列表，研究了将来概率表构建算 法减少搜索过程中的重复计算；对于搜索过程中产生的大量翻译假设信息采用对 象池技术进行管理；由于在柱搜索过程中可以保留了搜索的路径信息，在此基础 上研究了还n - b e s t 回溯算法获取n 个最佳译文的以便进行重评分。 由于传统的柱搜索算法在搜索状态扩展过程翻译速度不能很好的满足实时 性要求，对限定领域中术语的翻译的效果也比较差。本文基于这样的考虑在的柱 搜索算法上，从剪枝策略、位置重排限制以及术语翻译方面进行深入的研究。 在柱搜索的解码过程中生成的新状态的个数变化比较大，原先的固定n 大小 方法对这种搜索状态不能进行合理的反映从而加大陷入局部最优的风险。为此我 们有必要研究一种动态的剪枝策略，提商柱搜索剪枝的精度。 在柱搜索扩展时我们需要查找模型信息计算状态的模型评分，下一步扩展前 再根据状态的评分值对进行搜索树的剪枝删除比较差的状态。在柱搜索解码时， 生成的很多比较差的状态最终会被剪枝掉，这样的开销大大降低搜索的性能。因 此，寻求一种合适的剪枝策略来减少这种搜索性能浪费将大大提高搜索速度。 源短语的位置重排反映了源，目标语言之间的语法差异。若对位置重排没有任 何限制搜索变成n p 问题【1 8 】，通过位置重排的限制【1 4 1 可以减少搜索空间。当前使 用最多的位置重排限制方法有三种：受限的自由排序、i t g 限制、m m 限制。受 限的自由排序允许任何源短语在所限制的重排范围内都可以跟在任何其他短语 后。这种重排限制保证指定范围内重排位置的完全性，但是它会导致很多扩展的 浪费。i t g 限制可以限制交叉重排情况的但扩展速度比受限的自由排序慢很多。 i b m 限制的扩展比i t g 快，但限制的重排范围越大包含的重排情况也越多，其 扩展速度也会随之下降。为了提高位置重排限制下的扩展效率，我们计划研究一 种新的位置重排限制策略提高解码速度。 此外领域术语翻译具有唯一性的特点，而短语翻译模型反映的是通用领域的 短语翻译信息。为了提高对限定领域中的术语翻译效果，需要针对领域术语翻译 特殊处理以提高限定领域术语的翻译效果。 中国科学技术大学硕士学位论文绪论 1 6 本论文的结构框架 全文共分为6 章，安排如下： 第l 章绪论 旨在介绍本论文的研究背景、意义、国内外同类技术的发展与现状、以及本 课题的研究意义和主要工作，大致概括了本论文的结构框架。 第2 章基于短语统计机器翻译的模型研究 旨在对基于短语统计机器翻译中的各种模型的基本理论和相关训练方法进 行探讨，讨论了确定本课题解码器所用的模型。 第3 章柱搜索解码器的设计与实现 本章主要介绍了在设计与实现解码器时的关键算法。主要包括对模型存储结 构、翻译选项计算、将来概率计算、b e a ms e a r c h 算法、n - b e s t 回溯的算法的研究 与实现。 第4 章柱搜索解码器优化方法的研究 主要针对上章设计的解码器加入新的优化技术，提出改进的剪枝策略、位置 重排限制策略、以及对象池技术和术语翻译以提高解码效率。 第5 章试验与分析 本章在第3 章及第4 章的工作基础上，对解码器的关键算法进行测试和对比 分析。 第6 章结论与展望 本章回顾总结了全文的工作，并讨论了今后课题发展的进一步研究方向。 中国科学技术大学硕士学位论文基于短语统计机器翻译的模型研究 第二章基于短语统计机器翻译的模型研究 本文根据对数线性模型的思想，在解码过程中结合多个模型进行评分以提高 译文质量。本章我们主要介绍下解码器中所采用的模型。我们以语言模型和翻译 模型作为基本的模型，同时还加入了扭曲模型、词语惩罚模型和短语惩罚。 语言模型采用n - g r a m 的统计语言模型，由目标语言语料库训练而来；翻译 模型采用基于短语的方法构建，由双语对齐的语料库进行训练得到短语翻译表。 解码器结合多个模型作为信息输入对源语言句子进行解码翻译。系统流程如下图 2 1 所示： 图2 1 系统流程图 由上可知，解码器以模型信息为驱动，以最大可能的目标句子为搜索结果输 出。下面我们对这些模型进行分别讨论。 2 i 统计语言模型 语言模型是自然语言的数学模型，它主要描述自然语言的统计和结构方面的 内在规律。计算机主要依据语言模型对自然语言进行理解。 中国科学技术大学硕士学位论文基于短语统计机器翻译的模型研究 语言模型就其研究方面而言，一般分为两类。一类是基于语言学知识的规则 文法，另一类是基于统计的语言模型。研究发现，单纯依靠规则的语言模型几乎 不可能完成对大规模真实文本的处理，只能处理受限文本。目前，以语料库为基 础的统计语言建模方法成为潮流，它通过对语料库进行深层加工、统计和学习， 获取大规模真实语料中的语言知识。 统计语言模型是指用统计的方法分析和模拟自然语言的规律特性，并用概率 量化的方式决定一个词串的接受程度。统计语言模型很早以前就出现了，最先由 a n d r e im a r k o v 在2 0 世纪初应用到俄国文献的字母序列建模。另一个著名的语言 模型的应用是c l a u d es h a n n o n 的字母序列和单词序列模型，他用来解释译码的含 义和信息理论。后来，统计语言模型被发展成一种自然语言处理( n l p ) t 具。2 0 世纪7 0 年代末，语言模型第一次成功应用到自动语音识别领域的研究中。 2 1 1n - g r a m 统计语言模型 n - g r a m 统计语言模型是统计语言模型的一种。它主要根据历史n 1 个词，来 决定第n 个词可能出现的概率。n g r a m 语言模型的概率表示通常由最大相似度 ( m a x i m u ml i k e l i h o o de s t i m a t i o n ，m l e ) 来估计。第n 个词出现的概率只与前 面n 1 个词相关联，而与其它任何词不相关，整句的概率就是各个出现概率的乘 积，这个概率可以直接从语料库中同时出现n 个词的次数得到。n - g r a m 的句子 概率的数学表示公式2 - l 如下所示； p ( 聊= p ( w l ，w 2 ，w ，) = p “) p ( w ：1 w z ) p ( w 3 1 w 2 ，几p ( w 1 w , 心，w j ，k j j ( 2 1 ) = f i p ( w a w + w 2 ，w ) i j 语料库语言学的研究表明，许多词前面的词对于该词的出现具有很强的预测 能力，n - g r a m 模型的优点在于它包含了前n 1 个词所能提供的全部信息，这些 信息对于当前词的出现具有很强的约束力。它的缺点在于需要相当规模的训练文 本来确定模型的参数。当n 较大时，模型的参数空间过大。 自从十几年前在大词表语音识别系统中首次使用3 = g r a m 语言模型以来，直 到现在，3 - g r a m 统计语言模型仍旧是在世纪应用中表现最佳的语言模型，并且 成为许多其他语言模型的重要组成部件。本文采用统计机器翻译领域公认的成熟 开源语言模型训练工具s r i l m 进行n g r a m 语言模型的训练啪1 。 1 6 中国科学技术大学硕士学位论文基于短语统计机器旧译的模型研究 2 1 2 数据平滑技术 由于语言模型的训练文本t 的规模及其分布存在着一定的局限性和片面性。 许多合理的语言搭配现象没有出现在t 中。例如，一个词串吐。没有出现在t 中，根据公式： p ( h = w i d = 尸( 一= w l w i 一- i + 1 ) ( 2 2 ) 该词串对应的上下文条件概率p ( w = ，1 w i - 。i ) = o ，从而导致该词串所在的语 句s 出现的概率p ( s ) = o 。这种情况通常称作数据稀疏问题( d a t as p a r s e n e s s ) 或 零概率问题。对于一个给定的词典v ，基于此的n - g r a m 模型的模型参数空间为 i v j w 。显然，随着n - g r a m 模型的元数( n 值) 的增长，该模型的参数空间呈指 数性增长，其面临的数据稀疏问题越来越严重，极大地影响了模型的语言描述能 力。单纯的扩大训练问题t 的规模，不仅受到计算机时空复杂性的限制，而且 对于数据稀疏问题所引起的作用也十分有限。平滑算法就是用于解决数据稀疏问 题，而成为统计模型的研究热点。 数据平滑，就是通过调整最大似然估计( m a x i m u ml i k e l i h o o de s t i m a t i o n , m l e ) 的过程，使所得的概率值更贴近未见事件的真实情况。需要指出的是，所有参数 平滑算法都基于实际统计的数据之上，是对实际统计数据的平滑，大多数情况下 我们采用极大似然估计来统计实际数据，对数据的平滑自然是在此数据基础上进 行的。 下面我们介绍下常用的数据平滑方法【2 7 l ： 1 加法平滑 加法平滑算法是由l i d s t o n e ，j o h n s o n 和j e f f r e y s 等提出的一种简单易行的一 种平滑方法。它的基本思想是：为了避免零概率问题，将n g r a m 模型中每个n 元对的出现次数上加上一个常数艿( 0 o 口( 一1 w i ) p ( 岣1w 一1 ) ，e l s e f f c ( w l l ) o ( 2 1 0 ) a ( w i ) e ( w d o t h e r , v i s e 参数口的估算一般使用如下公式： ( n 一- i + 1 ) = l 一p ( i n - - i + 1 ) ：“w 。n 一“) o 1 9 ( 2 - 1 1 ) 中国科学技术大学硕士学位论文基于短语统计帆器翻译的模型研究 烈喝+1)2一n-i ：， 协 l 。吣( 嗉+ i ) o p ( i 嵋二k + 2 ) 1 w ( 。) 。p + ( h 1w 洲n - i + 2 ) 5k n e s e r - n e y 平滑 k n e s e r 和n e y 于1 9 9 5 年在绝对折扣平