（计算机应用技术专业论文）基于图和转移算法相结合的中文依存关系解析.pdf

大连理工大学硕士学位论文 摘要 句法分析是自然语言处理的重要任务之一，近年来得到广泛重视，在机器翻译、信 息检索、自动文摘等领域有着直接的应用。依存关系解析是句法分析的一个重要方法， 依存关系可以明确地表明词与词之间的句法依存关系，并方便地转化为语意依存描述。 词是句子结构中的最小元素，词与词之间的依存关系解析可以表示词间的深层联系，本 文在基于词的基础上进行依存关系解析。 目前，英文依存关系解析与日语依存关系解析已经取得了较好的研究成果。中文的 语法结构不同于其他语言，依存关系解析较复杂。目前的中文的依存解析方法主要分为 两种：基于转移的方法和基于图的方法，基于转移的方法的主要代表方法是n i v r e 算法， 而基于图的主要代表方法是最大生成树解析算法。 n i v r e 算法是一种确定性的解析方法，基于待解析词对的周边特征进行解析，采用 贪婪算法，在每一步都寻求局部最优解，中间结果可以用于随后的解析。最大生成树解 析算法是基于整句的依存关系树进行解析，搜索的是全局最优解，最大生成树未解析完 毕，不能确定任何中间结果。本文根据n i v r e 算法和最大生成树解析算法的互补关系提 出了两种结合方法。一种是以最大生成树算法为基础，通过n i v r e 算法结果的存在性修 正最大生成树边值的算法，称为基于存在性影响因子的中文依存关系解析；另一个结合 方法是以最大生成树算法为基础，通过n i v r e 算法结果的依存度修正最大生成树边值的 算法，称为基于依存度影响因子的中文依存关系解析。 实验采用宾州中文树库5 0 ，实验结果表明，本文提出的两种结合方法均好于原单 一算法。基于依存度影响因子的算法的解析效果晟好，精确率达到8 6 8 7 。 关键词：中文依存关系解析；最大生成树算法；支持向量机；n i v r e 算法 大连理工大学硕士学位论文 i n t e g r a t i n gg r a p h - b a s e da n dt r a n s i t i o n - b a s e dc h i n e s ed e p e n d e n c yp a r s e r a bs t r a c t s y n t a xp a r s i n gi so n eo ft h em o s ti m p o r t a n tt a s k so fn a t u r a ll a n g u a g ep r o c e s s i n g ， d e p e n d e n c ya n a l y s i si sw i d e l y u s e di nm a c h i n et r a n s l a t i o n ，i n f o r m a t i o nr e t r i e v a la n da u t o m a t i c a b s t r a c t 。d e p e n d e n c yr e l a t i o n sp r e s e n tr e l a t i o n sb e t w e e nw o r d s ，a n da r ee a s yt ob ec o n v e r t e d i n t os e m a n t i cd e p e n d e n c y w o r di st h es m a l l e s te l e m e n to fs e n t e n c e ，a n dt h ed e p e n d e n c yb a s e d o nw o r d sa n a l y s i sc a r l r e p r e s e n td e e ps y n t a xr e l a t i o n ，t h i st h e s i sr e s e a r c h e s c h i n e s e d e p e n d e n c yb e t w e e n w o r d s a tp r e s e n t ，n i v r e sa l g o r i t h mh a sb e e nu s e df o re n g l i s ha n dj a p a n e s ed e p e n d e n c ya n a l y s i s ， a n dh a sa c h i e v e dg o o dr e s e a r c hr e s u l t s t h eg r a m m a t i c a ls t r u c t u r eo fc h i n e s ei sf a rd i f f e r e n t f r o mo t h e rl a n g u a g e sa n dd e p e n d e n c ya n a l y s i si sv e r yc o m p l e x c u r r e n t l yt h em e t h o d so f c h i n e s ed e p e n d e n c yp a r s i n gc a l lb ed i v i d e di n t ot r a n s i t i o n b a s e da p p r o a c ha n dg r a p h - b a s e d a p p r o a c h ，t h em a i nr e p r e s e n t a t i v eo ft r a n s i t i o n b a s e da p p r o a c hi sn i v r e sa l g o r i t h ma n dt h e m a i nr e p r e s e n t a t i v eo ft r a n s i t i o n b a s e da p p r o a c hi sm a x i m u ms p a n n i n gt r e e ( m s t ) a l g o r i t h m n i v r e sa l g o r i t h mb e l o n g st od e t e r m i n i s t i cd e p e n d e n c yp a r s i n ga n dp a r s e sd e p e n d e n c y r e l a t i o nw i t l lt h ef e a t u r e sa r o u n dt h ew o r d s i tp e r f o r m sp a r s i n gb yg r e e d i l yt a k i n gt h e h i g h e s t - s c o r i n g t r a n s i t i o no u to fe v e r yp a r s e rs t a t ea n dt h ep a r s i n gh i s t o r yc a nb eu s e di nn e x t p a r s i n gu n t i lw eh a v ed e r i v e dac o m p l e t ed e p e n d e n c yg r a p h m s ta l g o r i t h mg e ta m o d e lf o r s c o r i n gp o s s i b l ed e p e n d e n c yg r a p h sf o rag i v e ns e n t e n c e ，p e r f o r mp a r s i n gb ys e a r c h i n gf o rt h e h i g h e s t - s c o r i n gg r a p h w ec a n tg e tt h ep a r tp a r s i n gr e s u l tu n t i lt h es e n t e n c ei sp a r s e do v e r i i l t h i sp a p e r ，w ep r o p o s et w ok i n d so fi n t e g r a t i n gm e t h o d sa c c o r d i n gt ot h ec o m p l e m e n t a r y r e l a t i o n s h i po fn i v r e sa l g o r i t h ma n dm a x i m u ms p a n n i n gt r e ea l g o r i t h m o n em e t h o di sb a s e d o nt h ei m p a c tf a c t o r so fe x i s t e n c et h a tm a x i m u ms p a n n i n gt r e ea l g o r i t h ma c ta st h eb a s i c a l g o r i t h mm o d i f i e db yt h ee x i s t e n c eo ft h er e s u l t so fn i v r ea l g o r i t h m t h eo t h e rm e t h o di s b a s e do nt h ei m p a c tf a c t o r so f d e p e n d e n c ed e g r e et h a tm a x i m u m s p a n n i n gt r e ea l g o r i t h ma c ta s t h eb a s i ca l g o r i t h mm o d i f i e db yt h ed e p e n d e n c yd e g r e eo f t h er e s u l t so f n i v r ea l g o r i t h m e x p e r i m e n t su s i n gp e n nc h i n e s et r e e b a n k 5 0s h o wt h a tt h ep r o p o s e dt w oc o m b i n a t i o n m e t h o d sa r eb e t t e rt h a nt h eo r i g i n a ls i n g l ea l g o r i t h ma n dt h em o d e lb a s e do nt h ei m p a c tf a c t o r s o fd e p e n d e n c ed e g r e er e a c h e st h eh i g h e s ta c c u r a c yw h i c hi s8 6 8 7 k e yw o r d s ：c h i n e s ed e p e n d e n c ya n a l y s i s ；m a x i m u ms p a n n i n gt r e ea l g o r i t h m ； s u p p o r tv e c t o rm a c h i n e ( s v m ) ；n i v r e 7 sa l g o r i t h m i i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：墨盘塑型魁纷互搁鱼垒鱼至鱼继抛 作者签名：匐盔盆 日期：递呈年生月上日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：驺园型丝醴纽堕塑丝丝! 拯丝鬓塑蛰 作者签名：a 盔红日期：型年。丝月厶日 导师签名： 当塑兰互乙 日期：型2年垃月j 上日 大连理工大学硕士学位论文 1 绪论 1 1研究背景 随着人类社会信息化程度的发展和计算机软硬件水平的提高，自然语言处理 ( n a t u r a ll a n g u a g ep r o c e s s i n g ，简称n l p ) 技术逐渐成为计算机应用和人工智能研究的 热点，在海量信息的处理中，如文本挖掘、文本分类、信息抽取、跨语言检索和机器翻 译等，随着这些海量信息处理应用的迫切需求的增长，自然语言处理的研究范围和应用 领域也在迅速的扩展，自然语言处理在我们生活中的地位越来越重要。 自然语言处理可以理解为使用计算机对人类特有的书面形式或口头形式的语言信 息进行各种处理和加工的研究。自然语言处理的主要任务是对字、词、句、篇章的语音 形式和书面等各种形式进行输入、输出、统计、检索、识别、分析、理解和生成，涉及 的范围主要包括语言学、数学和计算机科学等学科的交叉领域。自然语言处理过程通常 包括以下几个步骤【l 】：词法分析、句法分析、语义分析和语用分析，在这四个步骤中以 词法分析和句法分析为主。而句法分析方法大体上又可分为基于规则的方法和基于统计 的方法【2 ，3 】。 中文信息处理技术主要包括分词、词性标注、句法分析、语义分析和语用分析这几 个阶段。在目前的中文信息处理中，词法分析的技术相对来说已经比较成熟，从目前的 研究来看大部分词性标注工具对真实文本的标注准确率已达到实用的阶段，相比较而言 句法分析的研究还不够，可以说目前句法分析已经成为中文信息处理过程中的重点。 在句法分析过程中，依存关系解析是一个重要的方法。依存关系能够明确地表明中 心词之间的句法依存关系，并能方便地转化为语意依存描述。在1 9 7 0 年美国计算语言 学家j r o b i n s o n 在论文依存结构和转换规则中，提出依存关系的四条公理，这为依 存语法的形式化描述和其在计算语言学中的应用提供了一定的依据和理论基础，这四条 公理是： ( 1 ) 一个句子中只有一个成分是独立的。 ( 2 ) 一个句子中任何一个成分都不能依存于两个或两个以上的成分。 ( 3 ) 一个句子中其他成分直接依存于某一成分。 ( 4 ) 如果句子中b 成分直接依存于e 成分，而m 成分在句子中位于b 和m 之间，那 么m 或者直接依存于b ，或者直接依存于e ，或者直接依存于b 和e 之间的某一成分。 自此之后，依存关系的研究越来越受到重视，其中a n d e r s o n ，j a h u d s o n ，r a 和 m e l c u k 。i a 相继发表了多篇论文，使得依存关系逐步走向实用。进入九十年代，我国学 基于图和转移算法相结合的中文依存关系解析 者开始将依存语法引入中文语言学研究中，并结合中文的语法情况，提出了依存关系的 第五条公理： ( 5 ) 以句子的中心成分为中心，其左右两边的其它成分相互之间不发生依存关系。 根据研究，英文依存关系解析与日语依存关系解析已经取得了较好的研究成果。日 语依存关系解析是解析旬中各文节间之间的依存关系，旬中各文节( 句末文节除外) 能 且仅能依存于其后方的某个文节。中文与英文依存关系解析是解析句中各词间的依存关 系，句中各词依存于其前方或后方的某个词。近年来，机器学习的发展极为迅速，应用 亦日益广泛，有很多优秀的学习算法，基本上可以分为基于符号学习和基于非符号学习 ( 连接学习) 【4 ，5 】。其中基于符号学习比较好的方法有机械式学习、指导式学习、示例学 习、类比学习、基于解释的学习等。大规模语料库的创建使人们开始使用基于机器学习 的方法构建中文依存关系解析器。 1 2 研究意义 自然语言处理是计算机科学领域与人工智能领域中的一个重要方向1 6 】。它是能够 实现人与计算机之间用自然语言进行有效通信的各种理论和方法 g a o l 的一项研究。自然 语言处理的研究，也称为计算语言学，已成为计算机科学界的热门课题之一。自然语言 处理包括众多子领域，中文依存关系解析属于句法分析这个子领域。 中文依存关系解析在中文句法分析中的地位是无可取代的，在自然语言处理中旬法 分析又是一项特别关键的技术。词法分析的主要任务就是找出词汇的各个语素，从中获 取语言学信息，以便能够进行单词切分( 如中文、日语) ，或完成单词形态分析( 如英 语、法语) 。语义分析可以理解为是根据语义学的理论得到语句的意义并把这种意义形 式化表达出来，使得计算机能在此基础上进行推理。 中文依存关系能够确定句子中词之间的依存关系，属于基于中文依存文法。中文依 存关系可以明确地表明中心词之间的句法依存关系，并能方便地转化为语义依存描述。 词是句子结构中的最小元素，词与词之间的依存关系解析能够表示词间的深层联系，所 以本文在基于词的基础上进行依存关系解析。 中文依存关系解析以分词和词为基础，主要分析词与词之间的依存关系，是得到语 法树之前所需要的准备。如果依存关系的解析能够获得个很好的精度，将对语法树的 生成和译文的取舍有很大的帮助，并有利于进行句子中各层的分析。 大连理工大学硕士学位论文 1 3 研究现状 目前，国内外很多学者已经开始建立中文依存语法体系，归纳出不同的中文依存关 系集，并用依存关系语法来分析和表示中文句子的内部结构。分析方法可以归为三大类， 分别是：基于规则的方法，基于统计的方法，基于规则和统计相结合的方法。 周明与黄昌宁等人在1 9 9 4 年提出了一种统计与规则相结合的分析方法【1 1 , 1 2 】，它的 思想和词性标注的思想相同，其思想是首先从标注好的语料库中抽取标注知识，然后使 用抽取的知识来标注新的汉语句子，形成依存关系网，最后用语料库中的统计信息和某 些规则进行剪枝。微软亚洲研究院的周明于2 0 0 0 年提出一种基于规则的短语级依存关 系分析方法【1 3 】，郭艳华与周昌乐也在2 0 0 0 年提出一种基于规则的多级分析方法【1 4 】，首 先确定句子的谓语中心词和句子的主干，然后识别出句子中其他词的依存关系。随着各 种数学工具研究的不断深入，尤其是统计相关工具的研究有一定的进展，人们把统计工 具应用到依存关系解析上，取得了纯粹利用规则解析而无法得到的精度。目前使用的统 计方法主要有最大熵、s v m 等。 在依存关系解析方法中，主要方法有全依存对( a 1 1 p m r s ) 的方法和步进式( s t e p w i s e ) ， 其中全依存对方法又称基于图的方法，是将依存树分解成各个依存对。步进式的方法又 称基于转移的方法，将分析过程分解为各个分析动作。基于图的方法主要代表方法是最 大生成树算法，e i s n e r 1 5 】将最大生成树算法应用于英语等影射型语言的依存关系解析 ( o ( n 3 ) ) ，其搜索算法能够在所有的映射树中搜索得到最大生成树。m c d o n a l d 1 6 】使用 c h u l i u e d m o n d s 最大生成树解析算法【l7 】解析捷克语等非影射型语言的依存关系 ( o ( n 2 ) ) 。基于转移的解析方法有效地利用了句子解析至现在的中间解析结果特征，从一 个解析状态转移至下一个解析状态。解析采用贪婪算法，每一步转移都寻求局部最优转 移状态直至解析结束。比较有代表性的转移解析方法有面向英语的n i v r e 算法1 1 引， y a m a d a 算法【1 9 】，面向日语的组块逐步应用算法【2 0 】。段湘煜和赵军等人在2 0 0 7 年又提 出了基于动作建模的中文依存句法分析【2 l 】，该方法是对贪婪算法中每个分析步骤只选取 最有可能的分析动作而丢失了对整句话依存分析的全局视角方面进行了改进。郑育昌将 n i v r e 算法和y a m a d a 算法应用于中文依存关系解析，基于最大熵和支持向量机( s v m s ) 进行确定性依存关系解析【2 2 1 。并使用全局特征和根节点解析器提高解析性能 2 3 】。许云构 建了中文短语依存关系解析器f 2 4 】。郑育昌的研究表明【2 2 】，基于s v m s 的n i v r e 算法【1 8 】 更符合中文的语法特点。 基于图的方法和基于转移的方法差别很大，但本质上是对立和互补的。基于图的方 法利用全句的依存关系图进行训练，并使用最大生成树搜索算法进行解析，因此具有全 基于图和转移算法相结合的中文依存关系解析 局性和完备性。但是，因为不到最大生成树搜索完毕，无法获得任何中间解析结果，所 以无法将解析的中间结果应用于后续解析。而基于转移的方法利用每一步的状态转移进 行训练，解析时搜索局部最优转移状态直至整句解析结束，因此具有局部性和贪婪性。 但可以将句子解析的中间结果用于后续解析。两种模型均被广泛应用于各种语言，取得 了较高的依存关系正确率。m c d o n a l d 和n i v r e 对两种模型进行了详细的分析，揭示了 其错误分布的重要不同【2 5 1 。两种模型从推断算法至解析结果，可以称为是对立和互补的， 并且都有难以克服的不足。n i v r e 和m c d o n a l d 提出在训练时结合两种模型的方法【2 6 1 ， 将一种模型的解析结果作为指导特征引入另一种模型。实验表明结合后的模型显著地提 高了原基本模型的依存关系正确率，并有效地克服了原基本模型的不足。 近年来，国内外的许多院校、公司、科研机构也都展开了中文依存关系解析的研究， 并出现了一些解析效果较好的依存分析器，这些依存分析的研究成果使中文句法分析水 平有了很大的提高。 1 4中文依存关系解析的特点和难点 在中文依存语法中，可以将依存关系用三元组表示，即 ，其中占和e 分 别代表句子中的词语，r 代表b 与e 之间的关系。天是个有向弧，它由e ( 支配者) 指 向雪( 被支配者) ，即词语b 和f 的依存关系为月。 基于词的依存语法分析与短语结构语法相比较而言没有词组这个层次，在依存语法 分析中每一个结点都与句子中的某个单词相对应，它能直接处理句子中词与词之间的关 系，同时减少了很多结点数目。对语料库文本的自动标注过程中，依存于法分析比短语 结构使用方便。在对英语等语法进行分析时会用到短语结构语法，这样能够清楚地表示 出英语的句子结构。但是由于中文与英语有很大的不同之处，在中文韵句子结构分析中 短语结构语法却不能够很好地表示出中文句子的结构信息。 图1 1 短语结构树 f i g 1 1 p h r a s es t r u c t u r et r e e 大连理工大学硕士学位论文 采用树的结构进行说明一个兼语句，“老师安排小明打扫卫生”这个句子，如果用 短语结构语法来表示，其结构是一个短语结构树，其短语结构树如图1 1 所示，这是一个 典型的兼语句，名词“小明”既作动词“安排”的宾语，又作其后的动词“打扫”的主 语，而在短语结构树中却不能够表达出这种语法信息。但是在依存关系树中却可以清楚 地表示这种语法信息，如图1 2 所示。 图1 ，2 依存关系树 f i g 1 2d e p e n d e n c yt r e e 依存关系树的结构比短语结构树简洁，层次和结点数相对来说比较少。所以依存关 系结构要比短语结构更适合表示中文句子的内部结构。从近几年的研究成果和句法分析 的正确率来看，英语句法分析系统要比中文的句法系统好。其中造成中文自动分析困难 的原因主要有： ( 1 ) 中文同一词类可以担任多种句法成分而没有形态变化。 ( 2 )中文存在普遍的递归性，并且短语担任不同句法成分时也无形态变化。 ( 3 )中文的语序比较灵活。 在日语依存关系解析中旬中各文节( 句末文节除外) 能且仅能依存于其后方的某个 文节，且依存关系紧凑大多发生在相邻文节之间。英语的词类与句法成分之间对应关系 简单，而中文的词类和句法成分之间的关系错综复杂。中文是解析句中各词间的依存关 系，句中各词依存于其前方或后方的某个词。中文依存关系的解析存在着以下难点： ( 1 ) 在一个句子中，多数词语大多存在一个依存对象。示例如图1 3 所示。 ： 他在学校工作，待遇还不错。 ：， 图1 3 依存关系例句 f i g 1 3d e p e n d e n c ya n a l y s i se x a m p l e 基于图和转移算法相结合的中文依存关系解析 “他、“在、“不错”这三个词存在一个相同的依存对象“工作，这种情况 在中文依存关系解析中出现的频率相当高。当该词为句子的谓语中心词时，这种情况出 现频率会更高，那么如何将多个依存关系正确地分析出来，这是解析过程的一个难点。 ( 2 ) 长句子的解析精度较低。 在中文一句话中，两个发生依存关系的词可能跨度( 它们跨越的词数量) 很大，例 如：“其中n n 包括v v 工程n n 施工n n 招投标n n 管理n n 办法n n 、p u 拆迁 n n 工作n n 若干c d 规定n n 、p u 整治v v 违章j j 建筑n n 实施n n 办法n n、p u 通信n n 设施n n 及c c 管线n n 配套n n 建设n n 意见 n n、p u 建设n n 工地n n 施工n n 环境n n 管理n n 暂行j j 办法n n 等 e t c ”根据本文定义的依存关系类型，在这个含有3 5 个词语的句子中 存在3 1 个依存关系，依存关系发生跨度超过4 的词有l o 对。 类似的长句子对依存关系解析有如下影响： 首先，随着句子的长度的增加，句子的依存关系就会变得越来越复杂，消除歧义的 工作也越来越困难，正确选择依存对象将会很难，将会大大影响句子的解析精确度。 其次，随着句子的长度的增加，一对具有依存关系的词之间的跨度可能会变大，为 了判断这对依存关系，需要的工作量就相应变大，出现错误的可能性也随之增大，从而 影响句子的解析精确度。 考虑到中文句子的特点和难点以及现有的两个基本算法即n i v r e 算法和m s t 算法， 根据两个算法的互补关系，本文提出两个解析时结合两种基本算法的方法。首先训练获 得最大生成树解析模型和n i v r e 解析模型，然后利用n i v r e 解析模型解析中文句子，获 得解析结果；利用最大生成树解析模型的依存关系得分函数，计算获得完全有向图。两 个结合方法的不同之处就是影响因子的不同，根据最后基于n i v r e 的解析结果得到不同 的影响因子即存在性影响因子和依存度影响因子，用以修正完全有向图的边值，并基于 c h u l i u e d m o n d s 最大生成树解析算法【1 7 】搜索得到该句的依存关系解析图。这两种结合 方法分别称为基于存在性影响因子解析和基于依存度影响因子解析，此两种解析结合方 法，既利用了n i v r e 解析模型的中间解析结果特征，又使用了具有全局性的最大生成树 搜索算法，避免了因为确定性解析算法的贪婪性而引起的解析错误。 1 5 本文的主要工作 本文的工作是基于词解析中文依存关系，实验采用中文树库( c h t b ) 5 0 版，是已 经标注好的依存树库。此树库为短语结构，并且没有给出每个短语的中心子节点。首先 基于中心子节点过滤表将短语结构的宾州中文树库转换为依存结构树库。因为很难制定 大连理工大学硕士学位论文 逗号两侧的短语的依存规则，所以本文也和郑育昌【捌一样将逗号和句号均作为句子结束 标记。本文的主要工作如下： ( 1 ) 根据s v m 模型和依存关系解析算法总结s v m 模型需要的向量特征。并对 语料进行预处理，按照一定的格式重新排列，初步提取出一些s v m 模型需要的特征， 以便以后的解析。 ( 2 ) 应用确定性n i v r e 算法进行中文依存关系解析，从已标注语料中提取出供 s v m 训练的样本集( 向量的集合) 并进行支持向量机的学习，得到实验结果并进行分 析。 ( 3 ) 应用最大生成树算法进行中文依存关系解析，从己标注语料中选取并提取出 适合最大生成树算法的特征，得到供s v m 训练的样本集( 向量的集合) 并进行支持向 量机的学习，得到实验结果并进行分析。 ( 4 ) 把n i v r e 算法的模型和最大生成树的模型进行结合，利用支持向量机进行学 习，在学习过程中n i v r e 算法和最大生成树算法相互进行指导，即由n i v r e 算法模型指 导最大生成树算法模型进行学习，得到实验结果并进行分析：由最大生成树算法模型指 导n i v r e 算法模型进行学习，得到实验结果并进行分析。 ( 5 ) 在解析时进行结合，利用n i v r e 算法的解析结果作为影响因子( 存在性影响 因子) ，利用m s t 算法模型计算得到句子的一个完全图，然后利用存在性影响因子对 得到的图进行修正，并在修正后的图上利用m s t 算法来得到依存树，从而得到实验结 果。 ( 6 ) 在解析时进行结合，先利用n i v r e 算法进行解析，从n i v r e 算法解析结果中 的依存度作为影响因子( 依存度影响因子) ，先利用m s t 算法模型计算得到句子的一 个完全图，然后通过依存度影响因子修正图的边值，再利用m s t 算法得到依存树， ! 导 到实验结果。 本文通过上述工作，不仅实现了中文依存关系解析，并且详细介绍了n i v r e 算法和 最大生成树算法，不仅实现了这两个方法，还根据n i v r e 算法和最大生成树算法的优缺 点，提出新的结合方法来解析句子的依存关系。进一步提高了依存关系解析精度，基本 可以满足实际应用的需要。 本文包括绪论和六个章节的内容，结构如下： 第一章介绍中文依存关系的研究背景和研究意义，并介绍国内外中文依存关系的研 究现状，以及国内外进行中文依存关系解析时所采用的方法，并分析了中文依存关系的 特点和难点，以及本文工作所使用的方法和涵盖的范围。 第二章介绍了机器学习系统的结构和支持向量机( s v m ) 模型。 基于图和转移算法相结合的中文依存关系解析 第三章介绍了基于s v m 的确定性算法n i v r e 算法的中文依存关系解析模型，及基 于s v m 的图类方法m s t 算法的中文依存关系解析模型。 第四章介绍了n i v r e 算法和m s t 算法在基于s v m 学习时相互指导的模型。 第五章介绍了利用n i v r e 算法的解析结果，根据不同的影响因子来修正m s t 算法 的依存图。 第六章介绍了进行的实验，分析了实验的结果。 最后给出本文的结论和今后工作的展望。 一8 一 大连理工大学硕士学位论文 2 支持向量机简介 支持向量分类的目的是开发计算有效的途径，从而能在高维特征空间中学习“好 的分类超平面。支持向量机( s v m ，s u p p p o r tv e c t o rm a c h i n e ) 其泛化能力强而著称，并 因此得到了人们的青睐。它仅仅考虑类的边界情况，用较少的向量( 支持向量) 来分类。 一方面，它要使得边界之间的宽度最大( 分类边界将居于两类分界的正中间) ；另一方 面，它还要使得错分的代价不要太高。由v a p n i k 和他的合作者提出了一个在高维特征 空间使用线形函数假设空间的学习系统，它由一个来自最优化理论的学习方法训练，该 算法实现了一个由统计学习理论导出的学习偏置。是一个准则性的并且强有力的方法 【2 7 2 8 1 。在它提出后的若干年来，在广大范围的应用中，s v m 的性能超过大多数的学习 系统。 2 1分类超平面的基本概念 支持向量机用于分类问题其实就是寻找一个最优分类超平面，把此平面作为分类决 策面。在将低维空间向量映射到高维空间向量时会带来的“维数灾难”问题，支持向量 机通过引进核函数巧妙地解决了这个问题。 函数f ( x ) = w 7 o ) + 6 = 0 定义了一个超平面h 。其中将w 和b 成为权值向量和偏置， 这主要是从神经网络文献引用过来的。w 是超平面h 的法向量，决定超平面的方向；b 决定超平面的位置。在分类问题中，通常f ( x ) 表示分类平面，对样本x 来说，如果把样 本x 分成两类，那么：f ( x ) 0 表示其中一类；f ( x ) 一 o 【 仃 j ( 3 ) s i g m o i dk e m e l 函数：t a n h ( a ( x x 。) + f ) ，口、f 是常数，t a n h 是s i g m o i d 函数 大连理工大学硕士学位论文 3 中文依存关系解析的两个基本模型 两个基本模型分别是基于s v m 的n i v r e 中文依存关系解析模型和基于s v m 的m s t 中文依存关系解析模型，下面详细介绍这两种方法。 3 1 基于s v m 的n i v r e 中文依存关系解析模型 n i v r e 算法属于基于转移的方法，是一种确定性的解析方法，基于待解析词对的周 边特征进行解析，采用贪婪算法，每一步都寻求局部最优解。 3 1 1niv r e 算法 最先提出的依存关系解析的n i v r e 确定性算法是应用到日语 3 2 】、英语和挪威语【3 3 】 中，现在将它应用到中文依存关系中，利用n i v r e 算法构建一个中文依存关系解析器。 在n i v r e 算法【1 8 , 3 4 】中，其解析器可以由表达式 来表示。其中s 和i 都代表堆栈， i 代表将要解析的输入句子中的词序列。彳代表一个集合，存放在解析过程中确定下来 的依存关系项。给定一个序列w ，解析器最初的表达式是 。解析器将解 析栈s 的栈顶元素t 和栈i 的栈顶元素1 3 的依存关系，根据s v m 的分类结果采取相应 的动作，( 相应有四种动作，下面会详细介绍) 操作栈中的元素移动，算法迭代进行直 到栈歹为空。当栈歹为空时，解析器将停止迭代，并输出保存在集合彳中的依存关系序 列。 详细介绍n i v r e 解析时的四种动作，分别是r i g h t 操作、l e f t 操作、r e d u c e 操作和 s h i f t 操作。 r i g h t ：在当前三元组 中，如果存在依存关系f 嘲，即f 依存于以， 那么在依存关系集合a 中添加依存项( f 嘲) ，同时弹出栈s 中的栈顶元素r ，三元组 变为 。 l e f t ：在三元组 中，如果存在依存关系拧叫，即终依存于f ，则在 集合彳中添加依存项( 玎- - t ) ，并把元素”压入栈s 中，于是三元组 变为 。 在当前三元组 中，如果甩与f 相互之间不存在依存关系，解析器根 据不同情况执行下列操作。 r e d u c e ：如果歹中不存在任何元素玎7 ( 玎7 e ) 依存于f ，并且t 有父亲节点在其左侧， 解析器从栈s 中弹出，三元组变为 。 s h i f t ：当均不满足上述三种情况时，将，2 压入栈s 中，于是三元组 变为 。 基于图和转移算法相结合的中文依存关系解析 在n i v r e 算法中，r i g h t 操作和l e f t 操作都比较容易理解，只要单纯的判断两个栈 顶元素即可，但是在n i v r e 算法中r e d u c e 操作的条件是栈，中不存在任何节点依存于f ， 在依存关系的解析过程中很难判别是否满足这一条件。因此在实际的依存关系解析器中 一般应用确定性n i v r e 算法一只要栈，的栈顶元素n 不依存于元素f ，并且元素f 有父亲 节点在它的左面，此时则要执行r e d u c e 操作。根据确定性n i v r e 算法在依存关系解析过 程中，如果输入句长为m ，最多只需2 m 个动作既可完成解析，也就是说解析的时间复 杂度为o ( 2 m ) 。 n i v r e 算法的流程图如图3 1 所示： s = n i l ；l = w ：a = 咖 y 令譬韩 f 从栈s 中弹出，压入栈s 中 f 从栈s 中弹出 n 压入栈s 中 f 嘲加入集锄，- - * t 力 1 入集锄 f i i， 输出4 r 结束 图3 1 确定性n i v r e 算法流程图 f i g 3 1 t h ef l o wc h a r to fd e t e r m i n i s t i cn i v r e sa l g o r i t h m 下面举例详细说明n i v r e 算法的流程，以“小明报效祖国的壮志雄心。为例，句 子的n i v r e 算法的四种操作将在本例句中看到，对于不同的情况根据四种操作的条件选 择不同的操作，其操作过程如图3 2 所示 大连理工大学硕士学位论文 s t - 1t nn + l t - 1t 网 1 _ j a 小明报效) 靶 报效祖国报效 a 小明报效) n + l 团圈 报效祖国报蔽) i a 小明+ 报效祖国坝效) t 一1 t nn + l t 一1 tnn + l 圈 田圈 a 小e j 卜报效祖国 圈田 圈圈 i a 小明报效祖国+ 报效) + 图3 2n i v r e 算法的四个操作 f i g 3 2 f o u ro p e r a t i o n so fn i v r e sa l g o r i t h m 虽然对于一个句子中的大部分的词都是依存于其周围的词，但也有很多词和其依存 的词距离较远，也就是有很多词的孩子节点和词本身比较远，而对于n i v r e 算法的r e d u c e 操作不能保证这个条件总是成立。如果没有判断节点f 不存在孩子节点，不应该从栈s 中弹出节点t ，而是应该执行s h i f t 操作，将玎压入栈s 中，同时保留节点t 。如若不然， 如果在节点t 被弹出时还有孩子节点这样由于将不再被解析会得到一些错误的依存关系 结果。针对这类问题，杨洋提出了考虑远距离依存关系的确定性n i v r e 算法【3 5 1 ，其主要 思想是：在原有n i v r e 算法的基础上，根据中文语法特点适当增加对远距离依存关系的 判断。同时为了不增加n i v r e 算法本身的复杂性，同样定义了四种操作，r i g h t 操作与 尘圈n 面 基丁图和转移算法相结合的中文依存关系解析 l e f t 操作的定义与确定性n i v r e 算法中的定义完全相同，只是对r e d u c e 操作和s h i f t 操 作进行进一步明确的划分，改进后的r e d u c e 操作和s h i f t 操作如下： 在当前三元组 中，如果门与t 相互之间没有依存关系，解析器根据 不同情况执行下列操作。 r e d u c e ：假如栈歹的栈顶元素嚣不依存于元素，并且t 还有父亲节点在节点f 的左 面，并且父亲节点与以存在依存关系，那么解析器从栈s 中弹出，于是三元组变为 。 s h i f t ：当以上三种条件都不满足时将n 压入栈s 中，于是三元组变为 。 图3 1 3 给出了该算法中r e d u c e 和s h i f t 操作的流程图。 图3 3 考虑远距离依存关系的确定性n i v r e 算法部分流程图 f i g 3 3 t h ep a r tf l o wc h a r to fn i v r e sa l g o r i t h mw i t hc o n s i d e r a t i o no fl o n g - d i s t a n c ed e p e n d e n c y 根据依存关系的不交叉的依存公理，在句子中如果节点艿直接依存于节点e ，而m 节点在句子中位于b 和e 之间，那么m 或者直接依存于b ，或者直接依存于e ，或者直 接依存于b 和e 之间的某一成分，r e d u c e 操作的定义即使利用了这个定理。假如，的 栈顶元素 不依存于f ，并且t 的左侧的父亲节点与玎存在依存关系，则，中一定不存在 任何元素依存于f 。解析器从栈s 中弹出，根据不交叉公理不会影响随后的解析。 3 1 2n i v r e 算法特征的选取和分类 在机器学习时，学习模型的建立是通过样本集得到，学习模型的作用类似于记忆能 力能够对学过的对象有识别和推广能力。因为要建立学习模型，所以在机器学习领域特 大连理工大学硕士学位论文 征选取成为一个首要的问题。一个学习算法必须在确定好所需要的特征之后才能通过训 练样本对未知样本进行预测。由于特征是觉得学习算法得到的学习模型好坏的关键所 在，所以进行正确并有效的特征选择是一项重要的任务，这有利于减小时间复杂度提高 分类准确率，已经得到更精确、简单并容易理解的算法模型。那么在选择特征时，有一 种方法要注意每个特征的代表意义以及对分类结果的影响，还要考虑对回归的影响。这 样特征的选择就需要人们对所要建立的学习模型的专业领域有一定的了解，并具有主观 判断的经验。还有一种方法是利用数学知识和人工智能的方法在原始输入特征集合中自 动得到最优特征集合，无需人的干预。 本部分利用s v m 进行机器学习，对特征选取采用的方法是基于第一种方法，根据每 个特征所代表的具体意义来选择特征。在解析过程中，特征的选取在分类问题中对分类 的结果与否起决定性作用，对于考虑远距离依存关系的确定性n i v r e 算法中，解析器解 析当前三元组的两个栈顶元素( r ，门) 的依存关系。本部分选取f 节点及其前两个节点，行 节点及其后两个节点，以及它们的孩子节点的特征，解析( f ，n ) 的依存关系。根据依存 分析算法的解析过程，孩子节点是动态出现的过程。具体特征见表3 1 。 表3 1n i v r e 算法的特征向量 t a b 3 1f e a t u r e si nn i v r e sa l g o r i t h m 特征向量 节点f 幺t - 1 ，t 的词 节点t - 2 ，t - 1 ，t 的词性 节点c 幺t - 1 ，t 的孩子节点的词 节点幺t - 1 ，t 的孩子节点的词性 节点1 7 ，刀吖，刀理的词 节点刀，n