（计算机应用技术专业论文）依存文法在汉英统计机器翻译中的应用.pdf

摘要 摘要 基于句法的统计机器翻译模型近年来成为了统计机器翻译研究的热点，相对 于经典的短语模型，句法模型能够将更多的语言学知识融入翻译过程，更好的指 导翻译以及重排序。 本文以依存句法作为切入点，考察依存句法结构和语占知识标记在翻译过程 中所起的作用，提出- j 力n 入语法标记的泛化翻译模型，设计并实现了一个跨语言 的依存句法分析器和两个基于依存句法结构的机器翻译系统。 在依存句法分析方面，构建了一个基于动作序列预测的确定性依存句法分析 器；该分析器以移进归约( s h i f t r e d u c e ) 方法为基础，加入了基于统计信息的在 线错误修正和全局动作序列的选优工作，减小了错误动作的影响；在c o n l l 2 0 0 7 的评测集上，中文依存弧标记准确率为( l a s ) 7 6 3 6 ，英语l a s 为8 2 9 3 。 在机器翻译方面，本文在依存句法分析的基础上搭建了两个基于依存树到串 的统计机器翻译模型；其中模型l 采用的是完全词汇化的翻译模板，在源语言端 抽取依存子图( t r e e l e t ) ，并在目标语言中寻找与之对齐的连续词串信息；在实验 中，结合短语规则的系统成绩略低于经典的短语翻译系统；模型2 采用了泛化的 方法来对已经学习到的词汇化模板进行归纳，与之前的模型不同，本文提出使用 语法知识标记对泛化模板进行约束，使用了3 种泛化变量的形式，分别代表3 种类型的语法信息；具有语法标记的泛化模板加入了语法约束，因而可以更加有 效的指导译文的选择和调序；其实验结果超越了基于短语的翻译系统。 关键字：依存文法；句法分析；机器翻译 a b s t r a c t a b s t r a c t s y n t a x - b a s e dm o d e li sb e c o m i n ga l la c t i v ea r e ai nr e c e n ty e a r si nt h es t a t i s t i c a l m a c h i n et r a n s l a t i o nr e s e a r c h c o m p a r e dt ot h ec l a s s i cp h a s e b a s e dm o d e l ，s y n t a x m o d e lw o u l db em o r ea b l et oi n t e g r a t el i n g u i s t i ck n o w l e d g e ，a n dc o u l db eab e t t e r g u i d ei nt r a n s l a t i o ns e a r c h i n g , a sw e l la st r a n s l a t i o nr e o r d e r i n g i nt h i sp a p e r , w ef o c u so nt h ed e p e n d e n c yg r a m m a rt od i s c o v e rt h er o l eo fs y n t a x i nt h ep r o c e s so ft r a n s l a t i o n w ep r o p o s eag e n e r a l i z e dt r a n s l a t i o nm o d e l ，w h i c hi s l a b e l e db yg r a m m a rm a r k s ，a n dw ei m p l e m e n tam u l t i l a n g u a g ed e p e n d e n c yp a r s e r a n dt w od e p e n d e n c ys t r u c t u r eb a s e dm a c h i n et r a n s l a t i o ns y s t e m s f o rt h es y n t a c t i cp a r s i n g , w ep r e s e n ta na c t i o ns e q u e n c eb a s e dd e t e r m i n i s t i c p a r s e r w ea p p l yt h es t a t eo fa r ts h i f t r e d u c ea l g o r i t h m , a n du s et h es t a t i s t i c a l i n f o r m a t i o nb a s e do n l i n ee r r o r - c o r r e c t i o na n do v e r a l la c t i o ns e q u e n c eo p t i m i z a t i o nt o r e d u c et h em i s t a k ec a u s e db yd e t e r m i n i s t i ca c t i o n s w ea c h i e v e dd e p e n d e n c ea r c m a r k e ra c c u r a c yr a t e ( l a s ) 7 6 3 6 o nc h i n e s ea n d8 2 9 3 o nt h ee n g l i s ho nt h e b e n c h m a r ks e ti nc o n l l 2 0 0 7 f o rt h em a c h i n et r a n s l a t i o n ，w ep r e s e n tt w od e p e n d e n c ys t r u c t u r eb a s e ds t a t i s t i c a l m a c h i n et r a n s l a t i o nm o d e l s m o d e l1i sc o m p l e t e l yl e x i c a l i z e d ；w ee x t r a c tt h et r e e l e t s t r u c t u r ei nt h es o u r c el a n g u a g es i d e ，a n dt h ec o n t i n u o u sc o r r e s p o n d i n gs t r i n go f w o r d si nt h et a r g e tl a n g u a g es i d e b yc o m b i n i n gt h ep h r a s e b a s e dt e m p l a t ew e a c h i e v e dt h es a m el e v e lr e s u l t sa st h ec l a s s i cp h r a s e - b a s e ds y s t 啪m o d e l2a p p l i e s t h eg e n e r a l i z a t i o nt os u m m a r i z et h el e a r n e dl e x i c a lt e m p l a t e d i f f e r e n tf r o mt h e b e f o r es y s t e m s ，w ea p p l yg r a m m a rl a b e l st oc o n s t r a i nt h eg e n e r a l i z e dt e m p l a t e w e u s et h r e ek i n d so fv a r i a b l e si nt h ef o r mo fg e n e r a l i z a t i o n ，r e p r e s e n t i n gt h r e ed i f f e r e n t g r a m m a rc o n s t r a i n s t h eg r a m m a r - l a b e l e dg e n e r a l i z e dt e m p l a t e sc o u l db em o r e e f f e c t i v et og u i d et h ec h o i c eo ft r a n s l a t i o n t h ee x p e r i m e n tr e s u l to ft h i sm o d e l o u t p e r f o r m st h ec l a s s i cp h r a s e d - b a s e dm o d e l k e y w o r d s ：d e p e n d e n c yg r a m m a r ；s y n t a xp a r s i n g ；m a c h i n et r a n s l a t i o n 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。 本人在论文写作中参考的其他个人或集体的研究成果，均在文中以明 确方式标明。本人依法享有和承担由此论文产生的权利和责任。 c 酬黝哗 砂酣年厂月7e l 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电 子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学 校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索， 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适 用本规定。 本学位论文属于 1 保密() ，在年解密后适用本授权书。 2 不保密( ) ( 请在以上相应括号内打“寸) 第一章绪论 1 1 机器翻译 第一章绪论 机器翻译的研究已有半个多世纪的历史。在计算机发明之初，就有入想到利 用计算机来破解密码，当然也有人想到利用计算机来破解人与人之间沟通的密码 语言。所谓机器翻译，一般是指使用计算机把一种语言表达为另外一种语言 的转化过程。 早在1 9 4 9 年，人类设计制造出第一台计算机后不久，w e a v e r 发表的以翻 译为题的备忘录中就提出利用计算机进行翻译的设想，他提出：“当我阅读一 篇用俄语写的文章的时候，我可以说，这篇文章实际上是用英语写的，只不过它 是用另外一种奇怪的符号编了码而已，当我在阅读时，我是在进行解码。 这其 实是一种基于信源通道的翻译模型的思想。 然而，虽然1 9 4 9 年就提出了这样的想法，但实际中的进展却非常曲折和缓 慢。 1 9 5 4 年美国的乔治伦敦大学和i b m 公司合作，公开演示了世界上第一个m t 系统。直到2 0 世纪6 0 年代前期，欧美各国的机器翻译研究出现了不断上升的 趋势。1 9 6 4 年，美国科学院成立的语言自动处理咨询委员会( a u t o m a t i cl a n g u a g e p r o c e s s i n ga d v i s o r yc o m m i t t e e ) 经过两年的综合调查分析和测试，于1 9 6 6 年发 布了著名的a l p a c 报告宣称：“在近期和可以预见的未来，开发出实用的机器 翻译系统是没有指望的 。报告还指出，机器翻译研究遇到了难以克服的“语义 障碍 ( s e m a n t i cb a r r i e r ) ：这一报告给了正在蓬勃发展的机器翻译当头一棒，m t 研究陷入了近乎停滞的僵局。 在此之后的2 0 多年里，学者们主要通过句法、语法等理论知识来解释语言 中词汇的内部关联，希望能够跨越语言之间的语义障碍；进而还出现了描述世界 知识的知识库；一直到9 0 年代以前，机器翻译的主流方法一直是基于规则的方 法；其主要问题是一方面语言的表现形式是非常丰富的，构建知识库的规则需要 训练有素的语言学家来制定并维护；另一方面，语言并不是一个封闭的集合，规 第一章绪论 则之外还有新的规则，但新的规则如何不与旧的规则冲突也是一个难题。知识的 获取成为传统翻译方法的瓶颈。 在2 0 世纪8 0 年代中后期，一些研究人员提出基于语料库的机器翻译方法； 与基于规则方法不同的是，基于语料库的方法不对语言进行深层次的分析，而是 大规模收集互为译文的双语语料并基于这些对齐语料进行翻译。其中有两个主要 的分枝：一种称为基于实例的机器翻译方法，主张通过在双语语料库中查找最为 相似的翻译实例来获得语言的翻译；另一种称为基于统计的机器翻译方法，即统 计机器翻译，主张对翻译过程建立数学模型，利用对齐语料库估计模型参数，进 而根据数学统计模型及经过调整的参数来执行概率选优来生成译文。 1 9 9 3 年，i b m f l q b r o w n 首次提出基于单词的统计机器翻译模型1 1 ，其效果超 过了当时基于规则的最好系统s y s t r a n ，而其提出的基于信源信道的统计翻译 模型在研究者中引起了相当大的兴趣，该模型将源语言到目标语言的转化视作信 号在信道里面的传输过程，而翻译的任务就是通过观察信号的转变现象来重建逆 通道模型，并通过机器来自动的进行文本中的概率计算进而完成多个翻译结果； 从此，越来越多的学者从编制烦琐、细致的翻译规则的工作中投入到对新概率模 型的探索、语料库的分析、模型参数的选择等工作上来，取得一系列的重要突破， 沉寂多年的机器翻译研究重新活跃起来，并且进入了一个空前繁荣的时期。 基于词对齐( w o r d t o w o r d ) 模型应该说是最早的统计翻译模型，是一种纯 粹从单词到单词的转录方法，而对于上下文的信息没有加以利用，在目标语言的 上重排序就显得异常困难和复杂；而一般的习惯用语则很难通过单个词的翻译拼 接来完成较好的意义表达【2 】【3 1 。 鉴于词模型的限制，学者们的研究对象从单词扩展到短语( p h r a s e ) 上来， 这个短语并不是语言学意义上的短语，而是任意连续的词串；以短语为对象的翻 译系统其主要任务就转化为短语划分、短语重排序、短语片段的直接翻译这样几 个问题上来；基于短语的翻译系统扩展了上下文的空间，对于相邻的单词串经常 作为一个整体来操作，一方面降低了翻译和调序的任意性，模型的复杂性降低； 另一方面，对于源语言的分块操作也符合人类的语言直觉；虽然只是翻译单元的 粒度发生了变化( 在模型和解码器的设计方面，两者是一脉相承的) ，但是在翻 译性能上却是前进了一大步，尤其当语料库的容量达到一定程度的时候，就会表 2 第一章绪论 现出其健壮的特点；从2 0 0 2 年到2 0 0 5 年，由f r a n zj o e h 开发的基于短语对齐模 板的统计机器翻译系统【4 】【5 】【6 】连续在n i s t 评测中独占鳌头，而其他基于短语的系 统也都排在前列，标志着基于短语的翻译模型已成为统计机器翻译的主流技术。 然而翻译粒度的改变并没有从根本上解决短语翻译中全局信息缺失、远距离 重排序的弱点，近年来其性能的增长逐渐放缓，呈现平台期的趋势，在2 0 0 5 年 和2 0 0 6 年的n i s t 评测1 中并没有明显的进步。 在短语翻译中遇到的困难提示人们应该将更多的信息加入到翻译过程中，使 得机器能够使用到更多的上下文。2 0 0 1 年，y a m a d a 提出第一个基于句法的统计 机器翻译模型【刀，该模型延续了噪声通道模型的思路，通过分析目标语言句法树 结构到源语言串的转换概率来进行翻译；从此翻译的目标也开始朝着语言的深层 结构进行探究。其结构定义即可以是符合语言学标准的具体的句法结构，也可以 是形式化的模板规则。在句法结构的指引下，产生了许多基于句法结构的翻译模 型，如d i n g 利用概率化同步依存插入语法( p r o b a b i l i s t i cs y n c h r o n o u sd e p e n d e n c y i n s e r t i o ng r a m m a r ，简称p s d i g ) 和非同构性随机树到树转录机( s t o c h a s t i c t r e e - t o t r e et r a n s d u c e r ) 构建了一个基于句法的统计机器翻译系统【8 】；q u i r k 同样使 用依存分析提出了一种基于依存分析的树到树的翻译模型唧；c h i a n g 提出层次化 ( h i e r a r c h i c a l ) 基于短语的翻译模型；2 0 0 6 年，刘洋提出了基于源语言树到目 标语言串的翻译模型【l l 】；2 0 0 7 年熊德意提出的基于依存t r e e l e t s t r i n g 对应模型的 统计机器翻译【1 2 】等。 其中c l l i 锄g 的系统( h i e r o ) 在2 0 0 5 年和2 0 0 6 年的n i s t 评测中都取得了 极佳的成绩，超过了许多基于短语的系统，成为目前最好的基于句法的系统之一。 统计机器翻译的模型从最早的基于单词，到基于短语，基于模板，再到层次 化的短语模型，及目前正在研究的很多基于句法或句法和短语混合的模型，整个 发展脉络是非常清晰的。从机器翻译金字塔结构来说，这个发展方向就是塔底的 字词翻译向塔顶的中间语言理解这样一个自底向上的方向。统计机器翻译发展到 基于句法这个阶段，可以说既是借鉴了其它机器翻译方法( 基于规则的，基于实 例的) 的经验，同时又是与它们的紧密结合，形成了机器翻译研究中承前启后的 一个新的混合翻译模式。 3 第一章绪论 本文的思路就是将依存文法结构应用于机器翻译之中，通过学习依存句法结 构片段来建立翻译模板，并进行基于依存句法的翻译和重排序研究。 1 2 本文的工作 语言学意义上的结构，相对于形式化结构而言，具有更强的表达能力，能够 真正地将语言学知识运用到机器翻译过程中；而随着句法分析技术的日趋成熟， 源自于各种语言学句法结构的翻译系统也成为可能。依存文法作为一种完全词汇 化的文法形式，体现出语言内部的自然依赖关系，在翻译中所表现出来的语义内 涵具有很强的研究价值。 熊德意对基于依存树到串f 拘s m t 做了初步的尝试【1 2 1 ，我们认为在依存结构 以及泛化策略上基于依存结构的s m t 还有很多可以探讨的空间。 本文的主要研究对象是以依存文法为指导建立起一个以依存句法结构为基 本翻译粒度的翻译模型，和其他的泛化模型不同，我们将依存关系标记等语法标 记也加入到泛化模板中，对不同的语法信息在翻译中做起的作用也作了对比分 析。整个论文包含三个部分的工作： 1 ) 设计并改进了n i v r e 的基于移进归约的确定性依存句法分析器；在原有的确 定性分析的基础之上加入了概率化依存分析模型和全局动作序列预测的优选，使 分析器弥补一部分由确定性分析所带来的损失； 2 ) 设计了一个完全词汇化的依存树到串的翻译转录模型，基于该模型实现了一 个翻译原型系统，与熊德意的模型不同，我们在目标对齐语言一端并不采用间隔 ( g a p ) 这一定义，在对齐模板的抽取上严格遵循对齐一致性的假设；在n i s t 2 0 0 5 的测试集上的实验结果表明加入了短语模板的翻译模型可以得到更好的翻译效 果，其翻译成绩略低于经典的基于短语的模型； 3 ) 对词汇化的模型进行各种泛化策略和泛化规则的研究，包括针对依存关系、 词性的泛化方式的研究；在n i s t 2 0 0 5 和滨洲树库的封闭集合上作了对比试验，考 察不同的语法标记模板对于翻译所起的作用，实验结果表明以依存关系标记的语 法模板既可以拥有泛化模型的预测能力、而且有语法知识的约束能力，可以得到 更好的翻译结果；而泛化系统与短语模板的结合也取得了超过了经典的短语系统 的成绩。 4 第一章绪论 本文的组织结构如下： 第一章为绪论部分，主要简单介绍机器翻译的发展历史以及本文思想的来 由； 第二章介绍依存句法以及依存句法分析器的过程： 第三章主要描述重要的统计机器翻译模型的演化进程，分析其中具有代表性 的工作； 第四章介绍词汇化依存树到串的翻译转录模型； 第五章介绍采用3 种泛化模板的依存树到串的翻译转录模型； 第六章介绍翻译模型的实验结果； 第七章为对本文工作的总结，以及对今后工作的一些设想。 第_ 二章依存句法分析器 第二章依存句法分析器 2 1 依存文法简介 依存语法主要是通过分析句子内部核心词和从属词之间的依存和支配关系， 来表达语言的构成。虽然语法依存和动词中心论等概念存在已久，但一般认为现 代依存语法理论的是由法国语言学家t e s i e r e 于1 9 5 9 年结构句法基础一书【1 3 】 中提出的，他认为句子是一个“有组织的整体 ，其组织性则体现于构成句子的 词与词之间的不对称的“关系( 即“依存关系 ) ：动词作为一个句子的中心， 支配其他成分，而其本身不受任何其他成分的支配。 此后1 9 7 0 年，美国计算语言学家j 罗宾孙( j r o b i n s o n ) 提出了依存语法的4 条公理： 1 ) 一个句子只有一个成分是独立的； 2 ) 句子中的其它成分直接从属于某一成分； 3 ) 任何一个成分都不能从属于两个或两个以上的成分； 4 ) 如果成分a 直接从属于成分b ，而成分c 在句子中位于a 和b 之间，那么， 成分c 或者从属于a ，或者从属于b ，或者从属于a 和b 之间的某一成分。 这四条公理比较准确界定了一个依存树所要满足的条件，包括汉语在内的各 种语言都遵循这个语法体系【1 4 】，得到了依存语法研究者的普遍接受。 在依存结构中，每一个词至多只有一个支配词，称作该词的“头”( h e a d ) ， 这样整个依存结构可以表示为一个有向图，其中的节点为句子中的词，边则记录 着依存关系，由受支配词指向该词的头。 在文献”1 中，对一个良构( w e l l f o r m e d ) 的依存图做了如下的5 条约束： ， 1 ) 标记的唯一性( u n i q u e l a b e l ) ( w j _ w ， w j 寸w ，) j ，= r ， 2 ) 单个头节点( s i n g l eh e a d ) ( w - - 1 , w j w k 专w j ) jw = w k 3 ) 非环( a c y c l i c ) 1 ( w 专w j w j 寸w ) 4 ) 连通图( c o n n e c t e d ) wh w j 5 ) 可投影性( p r o j e c t i v e ) ( w 付w k w w j ) j ( w 一w j v w k 斗w j ) 6 第二章依存句法分析器 图2 1 1 就是一个良构的依存图结构： 是 s 弋 这样例 d e t - - 夕 一个 原句：这是一个样例 箭头从受支配词指向支配词 依存边上的依存关系解释为： s u b j ：主谓关系； p r d ：表语补足关系； d e t ：限定关系 图2 1 1 依存句法结构示例 严格来讲，依存语法并不是一种严格定义的文法形式【1 6 】，依存语法没有明 确定义的规则形式；而不同语言的依存结构都或多或少的不满足上述五个形式化 条件约束，尤其是可投影性质，在大部分语言中都存在不满足该限制的实例，尽 管如此，我们仍然可以通过文献【1 刀所提出的方法，将非可投影性质 ( n o n p r o j e c t i v e ) 的依存树改造成合法的句法树。本文所讨论的依存句法树均为 满足5 个限制条件的良构图结构。 相对于短语结构文法，依存结构的最大不同在于其句法结构表示形式中所有 节点都是句子中的词，没有非终结符，是天然的词汇化节点【1 8 】：另外，从分支 边上看，依存关系的父子节点反映支配词与被支配词之间的关系，而短语结构文 法的分支边表示子节点是父节点的组成部分；因而依存文法关心的是关系结构， 而短语结构文法侧重组成结构【1 9 1 。z h o um i n e 2 0 】提出：常用于英语并取得良好效 果的短语语法在有些情况下不能有效描述汉语句子中词与词之间的关系： 依存文法在自然语言处理中主要有一下几点的优势： 1 ) 表示简洁。依存语法不含非终结符，词数为n 的句子对应的依存树只有1 1 个节点； 2 ) 依存文法采用中心词为驱动，不过多强调固定词序，比较适应汉语词序 灵活的特点； 3 ) 依存文法的关系结构能在一定程度上体现深层次的语义表达，语义对于 自然语言处理起着重要的作用。 本章以依存句法分析为主要研究对象，初步实现了一个基于统计的确定性依 存句法分析器。 7 第二章依存句法分析器 2 2 基于统计的依存句法分析器系统 2 2 1 主流分析方法简介 基于统计的依存分析系统主要通过学习树库中的结构上下文，得到唯一的依 存结构，其关键在于模型的选择以及相应的学习方法。由于依存分析不同于标准 的p c f g 方法，针对依存结构曾提出过很多的解决方案，大致可以分为基于动态 规划和基于动作序列预测的两大门类。 基于动态规划的模型 这一类模型的主要想法是将原来适用于短语结构的句法分析方法施加较少 的改动来进行依存句法树的生成，如图2 2 2 所示，将原来线图中的每一个规则 改变为词汇化的规则，这样就可以利用c k y 算法进行自底向上的合并，形成文 法结构。直接利用这种方法的问题是从不同的方向进入子树，会形成不同的分析 结构，如果图2 2 1 中“一个 也有机会和“是 进行合并，不能保证生成的一 定是良构的依存树结构。 是 样例 户 一个 一厂弋 这是 是 图2 2 1 依存结构转化到类似的短语结构 。弋 样例 一个样例 e i s n e r l 2 1 1 1 2 2 1 1 2 3 】提出一种改进的c k y 算法，他定义了跨度( s p a n ) 的概念， 一个跨度是指子串上的闭区间，其中内部节点上的依存关系都指向s p a n 内部， 只有s p a n 两端的词是活跃的( a c t i v e ) ，两个s p a n 进行“合并 的条件是拥有重 叠的活跃词，整个依存树的形成就是求一个能覆盖整个语言串的s p a n 的合并序 列；如图2 2 2 所示，由于每一个二元结构都有左向、右向的两种可能( 如果没 有依存关系，两个方向的概率均为0 ) ，在算法中采用了左向概率和右向概率的 第二章依存句法分析器 两个方向的马尔可夫过程来进行概率的估算。其算法的优点是只处理活跃边，生 成的结构均是可投影的。 八厂沁 ( 是一个) + ( 一个样例) 匕冷( 是一个 样例) 八瓜八瓜八厂心八八 ( 这是)+ ( 是一个样例) 日( 这是 一个样例) 图2 2 2e i s n e r 算法演示 m c d o n a l d 将依存图的概率问题转化为求解最大概率生成树的问题【冽；如图 2 2 3 所示，句子中每一个词都可能和另外任何一个词有依存关系，每条依存弧 【f ，刀都赋以概率s c o r e ( i ，) = w f ( i ，j ) 其中w 表示依存弧上的权值，这样解码问 题就变化为求一棵得分最大的生成树的问题。如果依存弧上的权值是正确的，该 模型可以生成全局最优的树，而且该模型也完全适用于非可投影( n o n - p r o j e c t i v e ) 的结构。在c o n l l 2 0 0 6 的测试集上，该模型在多种语言的集合上都取得了较高 的成绩2 。 图2 2 3 最大生成树结构演示 基于多特征的确定性算法 删 m s t y 3 0 t t - 巴 j o h 、m a r y 这一类的模型从确定性分析的角度出发，将原来的概率问题变成了动作行为 的分类问题，最终依照动作序列构造出唯一的一颗依存分析树。 y a m a d a 2 5 1 首先提出移进归约的算法，算法的核心是确定了3 种动作，以动 作来驱动状态的转移。状态由三元组 组成，其中s 是栈，存储已经部 9 第一二章依存句法分析器 分处理过的节点，q 是待处理的剩余字符串，a 是( 当前) 依存关系的集合；定 义了：s h i f t 、l e f t 、r i g h t 的三种操作，其中每一个操作的定义为： 舶驴 谢 三妒 r i g h t ，w ，w a s 】q ，w a s 【 q h 一心 w ，w a s 【】q ，w a s qm 一 图2 2 4y a m a d a 算法定义 其中，一w ，表示两个单词之间存在依存关系。算法自底向上的搜寻 每一个词是向左还是向右的进行依存，当只剩下一个节点时则搜索结束。图2 2 5 显示了该算法在推导过程中可能出现的格局： 是样例 il 虚线框内为栈当前应当处理的前两个节点，i r r “l 垄焦丛丝塑垦丝翌些盟堇盛! l 这一个 图2 2 5y a m a d a 算法演示 n i w e 在y a m a d a 的基础上提出了一种增强的动作预测模型【1 7 1 ，他将依存关 系也作为新的特征加入到模型中，并且将l e f t 和r i g h t 操作划分在每一个依存关 系上，使得动作集合大大增加；另外，将原来的自底向上的方向改变为自左至右 的线性动作序列，针对方向的改变，增加了归约( r e d u c e ) 操作，具体的定义如 下( 我们要求箭头指向支配词，与n i w e 文稿中的箭头相反) ： l o 第二章依存句法分析器 图2 2 6n i v r e 确定性算法的有关定义 该算法的优点在于首先保证了生成结构一定是非环( a c y c l i c ) 、可投影 ( p r o j e c t i v e ) ：相比y a m a d a 的定义，将l e f t 和砌g l l t 动作均加上关系标记，是 一个依存弧和依存关系标注一体化的分析系统；另外，该算法是确定性的算法， 每次动作都会消耗队列中输入串，为线性时间复杂度。图2 2 7 给出了一个详细 的s h i f t r e d u c e 算法过程。 第二章依存句法分析器 这个被杨三郎称为孩子的书会 按照 进行状态转移： 初始状态： s t e p l ： 妫妒 s t e p 2 ： r o o t ，这个，被 ，【杨三郎书会】，n i 妫泸 s t e p 3 ： r i g h t s t e p 4 ： r e d u c e s t e p s & & 6 ： 坳& 嘲驴 s t e p 7 ： r i g h t s t e p 8 ： r e d u c e s t e p 9 & & l o ： l e f l & & s h i f l s t e p l l ： r o o t ，这个】， 书会】， 被一杨三郎，被一称为，称为一孩子，称为一的，的一 书会 z e f t s t e p l 2 ： r o o t ，【书会】， 被一杨三郎，被一称为，称为一孩子，称为一的，的一书会， 这个一书会) 坳 s t e p l 3 ： r o o t ， n i t ， 被一杨三郎，被一称为，称为一孩子，称为一的，的一书会， 这个一书会，r o o t 一书会 r i g h t 终止状态： 图2 2 7n i v r e 算法示例 本文在n i c 【1 7 1 的基础上了提出一种结构化依存概率模型，用于修正确定分 类器中错误的判断所导致的结构错误，系统在c o n l l 2 0 0 7 的评测集上做了测试， 中文依存弧标记准确率为( l a s ) 7 6 3 6 ，骨架依存弧( u a s ) 8 3 3 9 ， 英语l a s 8 2 9 3 ，u a s 为8 4 3 7 。 2 2 2 依存分析模型 2 2 2 1 回顾n i v r e 中的错误动作序列 n i v r e 算法的主要问题在于r e d u c e 动作的风险较大，如果r e d u c e 过早的发生， 1 2 第二章依存句法分析器 则在队列中的较后边的词就没有机会与被弹出的词发生关系，使得在这一词上的 结构发生错误，或者使该词没有父节点。如图2 2 - 8 所示，图中虚线部分是正确 的依存关系，但由于在某些步骤上选择了错误的动作，使得正确的依存弧没有在 分析中出现，产生了错误的非联通( n o n c o n n e c t i v e ) 的结构；其次，确定性的动作 选择是根据动态的子树结构的生成，如果一旦出现选择错误，则动态树结构的错 误会传播到后继动作尤其是长距离的依存关系的判断。 这个被杨三郎称为孩子的书会 s t e p 4 ： s t e p 5 ： r e d u c e s t e p s ： s t e p 9 ： r e d u c e s t e p l 2 ： r o o q ， m l 】， 被一杨三郎，称为一孩子，的一书会，这个一 会，r o o t 一书会) 终止状态： 图2 2 8n i v r e 算法错误的动作序列演示 j i i l 等【2 6 】采用了分层分析的方式来解决动作序列的歧义问题，但是其主要面 向的对象是中文和动词，对于其他词性发生的r e d u c e l h i 题，还是需要分别建模处 理。通过图2 2 8 中可以看出，这种错误不光存在动词与动词之间。 基于以上分析，我们分别建立了2 个模型来解决依存结构生成错误的问题。 2 2 2 2 模型1 采用结构概率修正动作序列 观察分析步骤，产生r e d u c e 错误的原因并不在于当前的出栈步骤( 如s t e p 5 、 s t e p 9 ) ，而在于之前没有对栈顶( t o p ) 的自由的节点执行正确的动作，如图2 2 8 中，“的 应该首先与“称为 进行l e f t 的归约，但由于队列中“书会 的出现， 使得分类器选择了首先与“书会 进行归约，这样，“的 从栈中弹出，失去了 第二章依存句法分析器 后继处理的可能。但同时，分析这种现象也给了我们修复原来错误结构的机会。 产生这种现象的特征在于： a c t i o n = r e d u c e & & t o p p a r e n t = n i l 从结构信息来分析，队列头只可能存在递归的左儿子群： t 0 p - lt 0 p n 了 譬：一，- ：j i t ni-一迥咖sexts o n s i n e x 【3 0 n s 根据依存树p r o j e c t i v e 性质的要求，t 0 p 只可能与t o p 一1 或者n e x t 的左子节点 序列有依存关系，我们将t o p 放置于每一个可能的位置，并通过依存树语言模型 来得到最终合法的结构。 由于t 0 p 在树林中可能的位置只能构成两颗退化了的树，相当于一个平面结 构，所以可以直接以类似n 元模型的方式进行概率估计，组合成的概率为： p ( t r e e ( t o p 一1 ，f 印) ) p ( t r e e ( n e x t ，n e x t s o n s ) ) 或者p ( 抛p ( 卸一1 ) ) p ( t r e e ( n e x t ，s o b ，卸，s o n ) ) 其中p ( t r e e ( w l w 2 ) ) 2p ( h i i ) p ( w 2i ) p ( ir o o t ) 当位置选定后，采用最大似然估计的方法估计依存关系标注的概率： 酬邺，= 黑鲁 其中表示依存关系标注，最终的概率由词性概率插值得到。 尸= a a + 五扔+ 五善 p l 为词汇概率，见为词性概率，亏为常数。通过训练树库，可以得到上述 的各个概率信息。 2 2 2 3 模型2 动作序列的全局优化 对于r e d u c e 弓l 起的错误，其根本原因还是在于确定性分析引起的局部最优所 1 4 第二章依存句法分析器 导致，如果将依存分析的动作序列看作是一个序列化标注的问题，则整个依存树 的生成过程可以看作是找到最可能出现的动作标注序列的标注问题。 a r g m a x p ( t r e e ( r o o t ) 1w ) a r g m a x p ( 4 ，4 ，4 ，4 - l ，以lw ) a r g m a x p ( a t ，4 ，4 ，以1 ，以) p ( 4 ，4 9o , 0 9 4 ，a n 小4 ，) = 兀p ( 44 一。) = 兀p ( 4 is , 一。) p ( 墨一。i4 一。) = 兀p ( 4l 墨一。) 其中，a i 为第i 个动作，s i 为a i 动作之后所生产的图结构。 我们对s v m 分类器做了概率输出的修改，使得每一步选择能够保留n - b e s t 的动作序列，这样就可以用动态规划算法得到概率最大的输出序列，从而得到对 应全局最优的依存树结构。 2 2 3 实验结果 我们采用的测试数据是c o n l l 2 0 0 7 评测提供的实验数据，测试结果是用主 办方提供的e v a l u a t e p l 脚本进行评测，其评测标准为： 依存弧准确率( l a b e l e da t t a c h m e n ts c o r e ) ：依存弧和弧上的依存关系均正确 的词的百分比； 骨架依存弧准确率( u n l a b e l e d a t t a c h m e n ts c o r c ) ：核心词标注正确的词的百 分比。 我们采用l i b s v m 2 刀包来进行动作的分类器选择，采用的特征同文献【1 7 1 。针 对除中文外其他语料库的n o n - p r o j e c t i v e 现象，使用n i v r e 所采用的伪可投影的方 法【2 8 】进行预处理和后处理，生成n o n - p r o j e c t i v e 的结构。 1 5 第二章依存句法分析器 c h i n e s e e n g l i s h a r a b i ct u d ( i s hg r e e ki t a l i a nc a t a l a n l a ss c o r e7 6 3 68 2 9 3 6 3 3 76 4 6 86 5 4 57 4 6 58 0 1 2 l a sa v g 7 6 5 98 0 9 56 8 3 47 0 0 67 0 2 27 8 0 67 9 8 5 u a ss c o r e8 3 3 98 4 3 7 7 4 27 5 9 67 5 6 58 2 3 69 0 8 3 u a s a v g 8 1 9 8 8 2 6 77 8 8 47 6 9 57 7 7 88 2 4 58 7 9 8 与n i r v e 的m a l t 系统所得到的结果对比 表格2 系统与m a l t 的结果比对 c h i n e s e e n g l i s h t h i ss y s t e m7 6 3 68 2 9 3 l a s m a l t7 5 8 288 1 l t h i ss y s t e m 8 3 3 98 4 3 7 u a s m a l t8 4 5 2 8 8 9 3 在中文的l a s 测试上好于m a l t ，说明我们所采用的修正过程对于依存关系标 记具有较好的矫正作用；而我们的系统在s v m 的参数调整上并没有做训练，所 以最后的结果与m a l t 有一定的距离。 系统在不同语言的数据集上得到的结果参差不齐，主要是由于针对于其他语 料中所出现给出的独特的语法特征我们并没有加以利用，对所有的语言所用的特 征是一致的。 对于中文而言错误率最大的几个词为： 的d e 、“、”c、在p、和c 、 舆c， 分析结果发现“在p 和连词在训练集的依存关系与从属词距离较远，其支 配词在远距离的情况下非常容易被中间的词进行归约，进而失去了与支配词依存 的机会。而对于“的d e 的错误，主要在于出现了没有子女的叶子节点，这对 于中文来说是个非法的结构，考察训练库，我们发现“的d e 的子女分布情况 1 6 第二章依存句法分析器 表格3 “的d e ”结构的分布 在结构特征相似的情况下，导致了s v m 分类器的不一致现象，对结果有较 大的影响。 同时应用模型2 在中文和英文的语料上做了测试，其结果为： 表格4 应用全局序列的成绩 c h i n e s e e n g l i s h n = 5n = 1 0n = 5n = 1 0 l a b7 7 5 47 7 8 58 3 9 38 4 2 5 u a b8 4 4 98 4 9 l8 6 2 5 8 6 9 6 我们看到采用了全局的动作序列能够从一定程度上弥补确定性分析所带来 的不确定因素，而我们所用的评价函数还仅仅是s v m 直接得出的评分值，如果 加入对添加更多的评价函数来进行n - b e s t 的操作应该还能提高效果。 2 3 小结 本章介绍了一种针对确定性依存分析的概率化改进方法。通过c o n l l 2 0 0 7 评测，在不同语言的数据集上进行了测试，考察了不同语言在依存分析上的差别， 在中文和英文的评测中都取得了较好的效果。我们可以看到依存文法的确是一种 能够跨越不同语种的通用结构，在相同的算法框架、甚至采用相同的特征下，都 可以生成可以接受的依存结构片段，我们有理由期望依存结构在更高的层次得到 较好的应用。 1 7 第三章统计机器翻译系统简介 第三章统计机器翻译系统简介 统计机器翻译( 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 ) 将翻译问题建 模为一个机器学习的问题。 假定源语言词汇集合为f ，目标语言词汇集合为e ，则一个源语言上的句子 ，可以表示成一个在f 集合上的序列彳石乃或者f ，同理目标语言上的句 子，可表示为q 吃一白或者弓e ；所谓翻译即为给定找到意义对等的序列 e l ，。 s m t 认为任何一个石j 都可以