基于概率上下文无关文法的句法分析方法研究-065871胡芊.doc

密级： 保密期限： 硕士研究生学位论文 题目：基于概率上下文无关文法的汉语句法分析方法研究 学 号： 065871 姓 名： 胡芊 专 业： 计算机科学与技术导 师： 杨正球 学 院： 计算机学院 2009年 2月 8 日54北京邮电大学硕士学位毕业论文独创性（或创新性）声明本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名： 日期： 关于论文使用授权的说明学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。（保密的学位论文在解密后遵守此规定）保密论文注释：本学位论文属于保密在 年解密后适用本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授权书。本人签名： 日期： 导师签名： 日期： 基于概率上下文无关文法的汉语句法分析方法研究摘 要句法分析是自然语言处理的一个基本问题。许多自然语言处理任务，比如机器翻译、信息获取、自动文摘等都要依赖句法分析的精确结果才能最终获得满意的解决。同时，句法分析中所使用的技术也有助于解决其他领域与句法分析相似的问题。另一方面，语言是人类思维的载体，对自然语言的研究有助于研究人类智慧的本质，在处理语言的过程中，句法分析也是人们所面临的一个基本问题。因此对自然语言句法分析的研究具有重要的理论价值和深刻的哲学意义。在基于统计的句法分析方法中，最关键的两个问题是句法分析歧义消解模型和句法分析算法的设计，他们决定着句法分析系统的分析正确率和效率。本文从事的工作则从这两方面入手，提出了一个基于PCFG的结合上下文信息的句法分析方法，主要研究工作如下：1 研究现有常用的统计句法分析模型和句法分析算法，并对其进行综合分析比较；2 在以上研究的基础上，提出一个引入上下文信息的句法歧义消解模型；3 对GLR分析算法进行概率化扩展，形成了本文的句法分析算法。4 用实验证明了本文句法分析方法的有效性。 本文的实验采用了1998年1月的人民日报语料库和中科院计算所机器翻译句法树库作为训练语料，根据树库总结出实验所用语法规则，进行了小规模的分组实验。实验证明，本文的句法分析方法具有较高的分析效率和正确率。关键词 句法分析 PCFG GLR算法 自然语言处理RESEARCHES ON PCFG-BASED PARSING METHOD FOR CHINESE LANGUAGE ABSTRACTParsing is a fundamental problem in natural language processing. Many natural language processing tasks, such as machine translation, information acquisition, automatic abstracting, have to depend on the precise parsing results to be finally resolved satisfactorily. At the same time, parsing techniques also help to solve problems similar with parsing in other areas. On the other hand, Parsing is also a basic problem in dealing with languages which are the carrier of the human mind, thus, research on parsing will be helpful for us to find the nature of human intelligence. Therefore, natural language parsing research has important theoretical value and profound philosophical meaning. In the Statistics-based parsing methods, the two most critical issues are the disambiguation model and parsing algorithms, they determine the accuracy and efficiency of parsing. This paper works from both sides, proceeds a PCFG-based parsing method combining context information, the main research work are as follows: 1. Study of existing commonly used statistical model of parsing and parsing algorithm, and comprehensively analyze and compare their performance; 2. Based upon above studies, we propose a disambiguation model including some context information;3. Proceeding our own parsing algorithm by expanding GLR algorithm;4. Demonstrating the effectiveness of our method by experiments. We adopt the Peoples Daily Corpus in January, 1998 and the machine translation Treebank produced by Institute of computing technology, the Chinese Academy of Sciences to be the training corpus, and summarized a series of grammar rules from the corpus for experiments. The small-scaled experiments we implemented proved that our parsing method is relatively efficient and accurate.KEY WORDS parsing PCFG GLR algorithm natural language processing目录第一章 绪论11.1 本文的研究目的和意义11.2 句法分析方法综述21.2.1 基于规则的方法21.2.2 基于统计的方法21.3 汉语句法分析研究现状71.3.1 汉语句法分析面临的问题71.3.2 汉语句法分析的发展趋势81.4 本文的主要研究内容8第二章统计句法分析模型和句法分析算法研究102.1 统计句法分析的基本理论102.1.1 语言模型、句法分析模型和句法分析算法102.1.2 句法分析模型的评价标准122.2 常用统计句法分析模型简介及比较122.2.1 概率上下文无关文法.132.2.2 基于历史的句法分析模型132.2.3 分层渐近式句法分析模型152.2.4 头驱动的统计句法分析模型152.2.5 四种模型的性能综合比较172.3常用句法分析算法概述和分类比较192.3.1句法分析算法概述192.3.2句法分析算法的分类与比较20第三章本文的句法分析方法233.1 概率模型233.2 语法规则概率的获取253.3 结构共现概率的计算方法263.4 分析算法273.4.1 分析表的构造273.4.2 分析算法描述293.4.3 用例子描述算法分析过程31第四章实验与实验结果分析39第五章总结与展望435.1总结435.2展望43参考文献44附录48致谢52作者攻读学位期间发表的学术论文目录53第一章 绪论1.1 本文的研究目的和意义要使计算机与人能够通过自然语言进行交流，就要使计算机能够理解和运用自然语言，自然语言处理技术就是几十年来人们在这个方向上不断努力的产物1。句法分析是自然语言处理的一个基本问题。许多自然语言处理任务，比如机器翻译、信息获取、自动文摘等都要依赖句法分析的精确结果才能最终获得满意的解决。随着信息社会的到来，人们对自然语言处理的需求日益迫切，因而对句法分析的研究具有重要的现实意义。同时，句法分析中所使用的技术也有助于解决生物信息识别等与句法分析相似的问题。另一方面，语言是人类思维的载体，对自活语言的研究有助于研究人类智慧的本质，在处理语言的过程中，句法分析也是人们所面临的一个基本问题。因此对自然语言句法分析的研究具有重要的理论价值和深刻的哲学意义2。自然语言句法分析的任务是利用语言知识自动识别句子的语法结构，即句子所包含的句法单位以及这些句法单位相互之间的关系。相对于计算机语言等人工语言，自然语言存在着很大的不确定性。这种不确定性造成了自然语言句法歧义现象的普遍存在，歧义消解问题成为句法分析的主要难题之一 3。因此，对于同一个语句，通常存在着多个语法上正确的分析结果(尽管很多结果在语义上是没有意义的)。在这种情况下，句法分析的任务就包括从多种分析结果中选出正确的一种。然而，即使对于一个简单的自然语言句子，也可能存在着上百万种不同的语法上正确的分析结果，这就使得无论从排歧方法、分析精度，还是从时间、空间复杂度上，自动句法分析都面临着巨大的挑战。因此，评价一个句法分析方法优劣的标准主要在于两方面：分析结果的正确率和分析的效率。而这两方面的性能是由句法歧义消解模型和句法分析算法所共同决定的。句法分析的相关研究工作则是从这些方面展开，以获得大覆盖度高效率高精度的鲁棒性句法分析方法为目标4。本文的目的是在研究常见的句法分析算法和常见的统计句法分析模型的基础上，提出一个基于PCFG的引入上下文信息的句法分析方法，该方法将前向共现概率和后向共现概率引入到PCFG模型中来解决局部的歧义消解问题，提出了综合前后共现概率来计算句法树概率的公式，该计算方法比较公平地考虑各方面影响句法树概率的因素，有助于消解由规则本身结构引起的局部歧义。此外，该方法将概率计算扩展到GLR算法中，用引入概率计算的GLR算法来实现句法分析过程，实验证明，该方法具有较高的分析正确率和效率。1.2 句法分析方法综述1.2.1 基于规则的方法20世纪50年代末乔姆斯基的文法理论的提出奠定了基于规则方法的基础。在此后30多年的时间里，出现了一些有影响力的基于规则的系统，例如早期的BaseBall系统、SIR系统、STUDENT系统以及后来的基于转移扩张网络法的系统等。在中文处理方面， Zhou Ming 5提出了一种典型的基于规则的句法分析方法。该文中采用了短语结构的局部分析和依存分析相结合的方法。在句法分析的过程中，首先通过短语分析来对句子进行适当地抽象，减少处理时句子结点数目，最后通过手工书写的规则来进行依存分析。他共定义了11类短语和17类依存关系，制定了1000多条短语识别规则和300多条依存分析规则。基于规则的方法主要通过人工组织语法规则、建立知识库，句法结构歧义的解决是通过一些条件约束和检查来实现的 6。这种基于规则的方法在某一限定领域应用是可行的。然而，这种方法本身存在着较大的缺陷，主要表现在：1.规则刻画的知识颗粒度过大，无法使用有限的规则来刻画几乎是无限的自然语言现象，而且很难处理自然语言结构的不确定性。2.不能保证各种自然语言规则间的相容性和一致性，随着系统中规则数量的增加，规则之间常常会发生矛盾和冲突。3.规则的获取是一个十分繁琐的过程，它完全依赖于制定规则的工程师的语言知识和经验，因此获取一套完整而详细的大规模语法规则非常艰难。基于上述原因，单纯使用规则方法无法解决处理大规模真实文本时自然语言的高度复杂性和歧义性。因此，进入20世纪90年代以后，句法分析的主流方法己从规则方法转向以统计方法为代表的经验主义方法4。1.2.2 基于统计的方法统计方法以数学模型和大规模语料库为基础，其核心思想是建立数学模型以表述某一种语言现象，然后在大规模语料库中对模型进行训练，使其满足己经获知的经验知识，然后用训练好的模型对未知的现象进行预测。几乎所有基于统计的方法都可以归结到上述框架中去。与传统的基于规则的方法相比，统计方法有下述优点4：1.它不依赖于人主观的先验知识，这也是本文认为统计方法最重要的优点。大规模语料库实际上和规则一样，都是一种知识的表示形式，不同的是语料库相比规则而言，有更强的独立性和客观性。2.统计方法将知识和算法分离。前面己提过，规则往往是由某方面的专家针对某一特定的应用所编写的指导原则，而同一个语料库可以为多种算法、多种应用服务，它是独立的知识库。这样语料库的建立和完善可以和算法的设计并行，不仅节省了人力物力，也给一些标准化测试提供了基础。另外这项优点给基于统计方法的系统的维护和更新带来了很大的方便。随着应用的扩展，我们往往要考虑到新的语言现象，这时基于统计方法的系统只需要用更大的语料库重新训练一下模型就可以了，而基于规则的方法则需要增加大量的规则，而如上文所述，这并非一件容易的事情。3.基于统计的方法通过语料库给每条语言规则加上概率值，使得语言规则的使用有了“柔性”，不再是“说一不二”、“非此即彼”。近十几年来，随着计算机硬件设备的飞速发展，其单位存储和计算成本大幅度降低，使一些基于大规模搜索和迭代的复杂算法能够在个人计算机上广泛地实现和应用；而随着行业信息化的普及和网络资源的迅猛膨胀，可用语料资源也大为丰富，这一切给基于大规模语料库的统计自然语言处理方法的实现提供了必要的硬件和软件环境。在这种条件下，大规模地收集语料并用计算机处理成为可能，语料库的建设和语料库语言学成为计算语言学新的分支而迅速崛起。作为统计句法分析基础的树库的建设也获得巨大的发展。在英语方面，以美国宾夕法尼亚大学开发的宾州树库（Penn treebank）较为著名，该树库从1991年第一版发布以来的十余年时间里，经过不断地维护和修正，目前己达到几百万字的规模，被公认为具有较高的一致性和标注准确性，是目前研究英语句法分析所公认的标注训练集和测试集。在汉语方面，中文的树库建设在近年来也到了广泛的重视和巨大的发展。如美国宾夕法尼亚大学的宾州中文树库，目前发布的树库规模为10万汉语词。台湾中研院的中文句结构树库，增加了对句子语义信息的描述，如句子的施事（Agent）和受事（Patient）等，目前发布的树库规模为约24万汉语词。由中文语言资源联盟（Chinese LDC）建设的树库（TCT 973）的规模为100万汉字，是到目前为止规模最大的中文句法树库之一（http：//）。大规模树库的建设和发展为统计句法分析提供了很好的知识获取来源和测试平台。当前，大多数成功的统计句法分析方法都是利用语料库来获得分析所需要的知识。其基本思想是：1、使用语料库作为唯一的信息源，所有的知识（除了统计模型的构造方法）都是从语料库中获得的。2、在统计意义上解释语言知识，所有的参变量都是通过统计处理从语料库中自动习得的 7。概率方法的广泛应用是统计方法的显著特点之一。概率方法的本质就是利用不同语言现象的统计分布来描述语言使用的一般模式，并由此选择输入句子的最可能的分析结果，更适合大规模文本的自然语言句法分析。根据采用信息的不同，可以把统计方法分为下面五类。1. 概率上下文无关文法概率上下文无关文法（PCFG）模型是最典型的一种基于结构的概率方法。20世纪80年代以来，国内外学者对PCFG进行了深入的研究，包括对PCFG参数的推导和学习以及分析算法的研究。国外的研究起步较早，研究得也比较广泛。Lari 8首先采用Inside-Outside算法自动估计PCFG参数； Black 9等人以自底向上的CKY算法总结出PCFG的各种算法，包括Inside-Outside算法、Viterbi算法等；Stolcke 10将Earley算法与PCFG结合，给出了概率化的Earley算法。此外， Corazza 11对如何利用PCFG进行句法分析和计算句子的概率进行了深入细致的研究。国内的很多学者对PCFG用于汉语句法分析也做了大量的工作。王挺和周强 13用Inside-Outside算法研究了汉语的PCFG自动推导，在匹配分析机制上实现了无指导的EM 迭代训练算法。朱胜火 14对原有的GLR分析表加以改造，利用分析过程的控制结构来计算有关的概率，实现了一种有效的概率上下文无关文法的分析算法。虽然PCFG具有形式简洁、参数空间小和分析效率高的优点，但是它忽略了消歧所需的上下文信息，因此其消歧能力有限。针对PCFG的问题，出现了下面几种模型：增加结构信息的概率模型，包含词汇依存关系的概率文法，引入语义信息的模型和依据历史的模型，我们将在下面几节详细介绍这些模型。2. 增加结构信息的模型实验表明，结构信息的引入有助于提高句法分析的结果。Briscoe 15将合一语法同概率广义LR表（Probailistic Generalized LR）算法结合，以增加PCFG的上下文描述能力。Simmons 16首次提出上下文依存文法（the Context-Dependent Grammars，CDGs），并基于CDG针对英语受限子集实现了一个英语句法获取和分析系统。Schabes 17提出了一种概率树邻接文法（Probabilistic Tree-Adjoining Grammars， PTAGs）。这种文法在上下文无关文法中的标准替换规则的基础上，增添了一种附加原则，以提高规则的上下文敏感性，并且还改进了Inside-Outside算法使之能无指导地估计PTAG概率。Su 18提出了一种基于简单上下文相关文法的LMRN模型，该模型将归约项目左边M个符号和右边N个符号作为规则的上下文，同时认为紧随移进的归约动作是高度相关的，而不考虑相邻动作的约束。面向数据的句法分析技术（DOP）由Bod 1920首先提出。该处理技术建立在包含大量语言现象的树库基础上。把经过标注的树库看作一个语法，从树库中抽取部分树并构造一个部分树的数据库。当处理新的语言现象时，通过重新组合这些部分树的方式来构造句法分析树。DOP方法与人们对句法分析的直觉相一致，但对给定的句子，其推导的搜索空间与句子长度成指数增长（这句话有点问题）。Bod应用MonteCarlo技术在多项式时间内找到最优的句法树，但实际的句法分析的时间消耗仍然很大。在国内，张浩 21研究了PCFG独立性假设的局限性，并在PCFG的基础上提出了三个逐层递进的与结构上下文相关的概率句法分析模型，它们考虑了分析树当中每个派生结点的结构上下文条件。孟遥 2设计了一个包含复杂特征的统计句法分析模型，综合考虑了上下文无关规则的结构特性、所处的上下文环境即复杂特征信息。3. 基于词汇的概率方法基于词汇的句法分析方法根据包含在句子中的词的特性来区分句子的不同句法分析候选。基于词汇的句法分析的一种思路是考虑词汇之间的搭配关系，某些词的某些特殊组合比各自的其它偶然出现的组合更容易出现在句子中，也就是说，这些词汇的同现概率比较高。同现概率越高的词汇，越容易出现在同一句法结构中。这种同现关系通常采用互信息进行量化。Magerman 22提出了一种基于广义互信息模型的短语自动划分算法。它依赖于下面的一个假设：给定句子中的短语成分边界可以通过分析句子中词类n-gram组合的互信息值加以确定。它的实验结果说明：这种方法对于短句的分析效果较好，而对并列结构以及长句子的分析则不够理想。然而，单纯依靠词性信息很难获得理想的句法分析结果。因此，将词汇语法理论和概率结合产生出词汇语法的概率模型是件很自然的事情。Alshawi 23提出了一种基于核心词的概率句法分析模型，他认为一棵句法分析树由核心词及它的左右修饰成分组成。Goodman 24在概率上下文无关文法中引入了复杂特征，他规定所有规则前项只有两个结点，即二分形式的规则。每个非终结结点由一组属性值对表示，允许表示词汇的合一关系，以及远距离的依赖关系。Collins和Chamiak 252627等人采用中心词驱动的概率模型方法，这一方法是近年来句法分析词汇化的典型代表。其基本思想是：句子是围绕着中心词来组织的，规则中的每一个非终结符结点与其核心词相联系，通过规则的概率体现核心词之间的依存关系。Collins于1999年得到的句法分析结果是目前公认的英语的最好结果之一。在汉语方面，Bikel 28在4000句宾州中文树库上实验了Collin的头驱动句法分析模型和概率TAG句法分析模型的汉语句法分析效果。付国宏 29结合汉语的特点，把语义信息引入到汉语句法分析中，提出了一个基于词义的概率上下文文法（LPCFG）的汉语句法分析模型，构造了一个以词义搭配模式为品质因数的Best-First线图算法。4. 基于历史的模型基于历史的文法最早由Black 9提出，其核心思想是把句法分析过程看作自顶而下、从左向右的非终结结点的扩展过程，非终结结点的扩展相当于一系列的产生式使用过程，产生式的概率依赖于句子中当前分析点的整个分析历史。Jelinek 30描述了一个相似的历史模型，不同在于Black采用的是手工书写的规则，而Jelinek采用的规则是从树库中自动提取的。Magerman的工作 3132是Jelinek工作的延续，他采用决策树方法使得系统性能得到了较大提高。Ratnaparkhi 33采用最大熵的方法构造了一个基于历史的模型。5. 语义辅助的句法分析模型语义辅助的模型把语义信息引入到句法分析模型当中。Sekine 34描述了一个由语义辅助的句法分析器，它分析的过程考虑由核心词、语法关系以及谓词论元所组成的三元组。Jones 35设计的句法分析器在扩展结点的过程中不仅计算了规则的句法概率，而且考虑了其语义概率，语义以谓词论元的形式表示。Alshawi 36描述的句法树由语法关系、属性以及语义搭配等组成，并给出了多个句法分析结果。综上所述，句法分析的研究表明句法结构歧义的消除必须依赖多种信息，句法分析过程中的上下文结构信息，词汇信息以及语义信息都有助于歧义结构的消除。但如何很好地综合利用这些信息，需要根据所处理的语言的特点以及资源情况而定。1.3 汉语句法分析研究现状1.3.1 汉语句法分析面临的问题汉语有一个显著特点，即较为灵活。有人把世界上的语言分成孤立语、曲折语、粘着语、复杂语四种类型，汉语是孤立语的代表，孤立语的主要特征是缺乏词形变化，语法规则较灵活。汉语灵活的特点增加了汉语语言处理的难度。汉语的书面形式是连续书写的，词与词之间没有自然的界限，对汉语的分析首先要解决单词的切分问题。汉语是一种分析型语言，语义在汉语分析中起着举足轻重的作用。与俄语和英语相比，汉语在句法分析中需要更多的语义知识帮助消歧。朱德熙先生认为，汉语的语法体系与印欧语法体系是不同的。印欧语法体系中从词到短语是组成关系，而从短语到句子则是一种实现关系。汉语的语法学界对短语和句子的分界较为模糊，不少著作认为，短语和句子有一套共同的结构规则，短语加上一定的语调就成为句子。汉语缺少从词到短语再到小句最后组成句子的这种清晰的层次结构，短语分析与整句分析同样困难2。目前己知最好的汉语句法分析效果同其他西方语言相比还有一定的差距。而造成这种差距的主要原因之一是汉语语言本身的特点增加了对其进行分析的难度。汉语句法分析的主要困难可以总结为如下几点4：1.汉语的词性兼类问题非常普遍。汉语是一种孤立型语言，缺少形态标识，汉语的句子组成通常依赖虚词和词序，而不靠形态变化。但是虚词在汉语句子中并没有实际的意义，常常被省略掉；而次序又相当灵活，使得汉语的词类与句子成分之间不存在简单的一一对应关系，相同意思的句子就会对应多个结构，也就是多个词序的句子。所以，汉语中的同一个语法成份可以由属于不同词类的词来构成，同一个词在句法结构中又可以作为不同的句子成份。因此，汉语的词性兼类问题更为突出且难于解决3738。2.汉语句法分析存在着一个特殊的分词问题。由于汉语句子的书写方式是以字为单位的，在汉语文本中，字与字之间除了标点、分段等特殊符号外，没有其它明显的界限标志。句法分析主要是以词为最小单元进行处理的，因此在分析汉语的句法结构之前，首要的任务就是对汉语文本进行自动分词处理，其切分的好坏必然影响句法分析的效果。3.汉语句法结构分析歧义产生的一个重要原因是单纯依靠词类信息无法解决一些固有的歧义问题。引入词汇信息、语义信息是解决汉语句法歧义的重要途径之一。4.大规模、包含多种信息的知识库的建立是汉语句法分析实现大规模开放应用的瓶颈之一。由于汉语的复杂性和需要更多的预处理，目前己经建立的并可以利用的语言资源与英语相比，相对比较匾乏。汉语语言资源中可计算的完备的机器词典，尤其是大规模的语义词典和熟语料的建立相对滞后，这在一定程度上阻碍了汉语句法分析的发展。1.3.2 汉语句法分析的发展趋势正如上述问题的存在，要彻底解决这些问题，并实现句法分析研究的最终目标还有很长的路要走。国内外学者们对此进行了不断的探索和研究，提出了在当前条件下解决上述问题的可能的方案和发展方向，主要可以归纳为如下几点4：1.统计方法己成为主流技术。英语研究方面出现的许多较为成熟的统计模型可以为汉语分析所借鉴，但研究人员在借鉴其优点的同时，还应该结合汉语特点进行特殊处理。2.实现多方法、多特征或多知识源相结合的混合模型。这是句法分析研究发展的必然，是为了更好地解决句法分析过程的歧义问题。大量的实验证明，单一方法、单一知识很难有效地解决句法分析歧义问题。PCFG模型在句法分析中得到广泛的研究，但是为了提高算法的分析能力，如何描述超出PCFG模型的上下文约束的概率模型是目前句法分析研究的热点之一。3.句法分析算法是实现句法分析模型的基础，模型的可行性，最终由分析算法决定。因此，如何提高分析算法的效率，这是决定句法分析能否实际应用的关键技术之一。4.汉语是一种分析型语言，汉语的分析过程是一个语法知识、语义知识和常识性知识共用的过程，充分利用所有可能的复杂知识，通过书写包含语义或者语言学常识的规则，将基于规则的方法和基于统计的方法相结合成为句法分析研究的必然。1.4 本文的主要研究内容本文对自然语言句法分析的理论和相关方法进行了研究，重点研究两方面内容：基于统计的句法分析模型和句法分析算法，并在此基础上提出自己的汉语句法分析方法。本文的篇章结构如下：第一章 绪论，介绍本文的研究目的及意义，并简要介绍各种句法分析方法及其特点；分析了汉语句法分析面临的问题和未来的发展趋势；简单介绍本文的主要研究内容及篇章安排。第二章 统计句法分析模型和句法分析算法研究，本章是全文的理论基础和理论依据，主要研究现有的常用的统计句法分析模型和常用的句法分析算法，对现有常用的句法分析模型进行了综合的性能比较，并对常用的句法分析算法进行分类与比较。第三章 本文的句法分析方法，本章是本文的核心内容，详细介绍了一个基于PCFG的引入上下文信息的句法分析方法，该方法有一个改进的句法分析的歧义消解模型，该模型在计算概率的时候将一定的上下文信息纳入考虑范围，并尽量公平地考虑各方面因素对句法分析的影响。此外，该方法的句法分析算法是对GLR算法的扩展，在GLR分析过程中计算句法树的概率，并选择概率最大的句法树作为句法分析的结果。第四章 实验结果分析， 本章主要的内容是对本文的句法分析方法的实验和对实验数据的分析。第五章 总结与展望，对本文的研究工作做一个总结，提出本文的不足之处以及可以改进的地方，指出下一步可以研究的方向。第二章 统计句法分析模型和句法分析算法研究一个句法分析系统的性能优劣主要取决于两个关键部分：分析模型和分析算法。首先，选定一个合适的句法分析模型，设计合理的句法分析算法，对给定句子在时间允许的情况下，找到满足分析模型要求的所有句法分析结果。其次，对这些结果，根据句法分析模型来评价，从而选出最优的句法分析树。后面一个过程，也可以看作一个歧义消解的过程。因此，句法分析模型和句法分析算法实际上是相互独立而又彼此关联的，它们共同决定着句法分析系统在效率和正确率两方面的性能。本章的内容就是在介绍统计句法分析的基础理论的基础上研究现有常用的统计句法分析模型和句法分析算法，为后面本文句法分析方法的提出提供充足的理论基础和重要依据。2.1 统计句法分析的基本理论2.1.1 语言模型、句法分析模型和句法分析算法语言是一种符号系统，任何符号系统都包含形式和意义两个方面39，而语言模型就是对语言的形式和意义的描述。语言模型又叫文法，最简单的语言模型就是列出该语言的所有句子，而高级语言模型可以描述语言的结构和意义。语言模型主要分为规则模型和统计模型两种。规则模型是指语言学家描述语言的语法，语言学家认为所有人类语言的构造都是有层次的，层次结构可以用规则的形式表示出来，而规则的集合就是语法。对于一个输入的文字串，根据语法可以推导出该文字串的语法结构，从而判断出该文字串是否符合文法。统计语言模型是用概率统计的方法来揭示语言单位内在的统计规律，它不是简单地判断该句子是否符合文法，而是估计出句子在语言中出现的可能性。统计语言模型关注的是一个文字串出现在该语言中的概率。对于一个字符串s，记做s=w1w2wn，其中每个wi为词典V中的一个词。令wji=wjwj+1wi。N元文法（N-Gram）模型下，句子概率为： (2-1)PCFG文法模型下，句子概率p(s)为： (2-2)其中t为s的句法分析结果。统计句法分析模型的目的是评价若干个可能的句法分析结果（通常表示为语法树形式）是当前句子的正确语法解释的概率或在这若干个可能的分析结果中直接选择一个可能的结果40。一个统计句法分析模型的数学意义为一个概率评价函数，设G为某一种语言的语法，s为一个句子，T为根据语法G对s的所有可能的分析结果组成的集合。对于任意tT，一个统计句法分析模型可以给出t的概率，即p(t|s,G)，且 (2-3)句法分析算法是句法分析模型的实现，它的作用是根据句法分析模型对句法分析结果进行概率评价，找出该句法分析模型认为概率最大的句法分析结果，即找到： (2-4) 选择一个好的句法分析模型就是选择一种能够合理评价句子句法分析结果的概率评价函数，设计句法分析器是指如何有效地计算句法分析结果的概率，找出概率最大的句法分析树。句法分析模型和句法分析算法是统计句法分析研究密不可分的两个问题，前者决定句法分析结果是否正确，后者决定是否能够在有效的时间内实际找到结果。概率语言模型可以直接转换为统计句法分析模型，由 (2-5)可知 (2-6)因此基于概率语言模型建立句法分析模型是统计句法分析中常用的方法。建立统计句法分析模型与建立概率语言模型并不等价，建立句法分析模型可以不依赖语言模型，比如当语法相对简单时可用枚举的方式对句子的句法分析结果进行概率评价，或根据语料库用统计的方法直接习得句法分析模型，另一方面概率语言模型也不只用于句法分析，它还用于语音识别及对语言本身的研究等多方面41。尽管建立一个句法分析模型可以完全根据语料库的统计结果，而不使用语言模型，但大量实验表明在句法分析建模时依据合适的语言模型可以提高句法分析的效果2542。因此在设计统计句法分析模型时仍将以概率语言模型为基础，句法分析过程中尽量包含语言模型对语言的描述。在统计句法分析研究中研究语言模型通常也是在研究句法分析模型2。2.1.2 句法分析模型的评价标准对句法分析模型的评价是句法分析研究的重要内容，它决定句法分析模型的选择和优化。评价一个句法分析模型优劣主要要看采用该模型的句法分析系统的性能优劣，或该句法分析系统应用于实际问题是否有效4243。对句法分析模型的评价方法有面向任务的评价、基于语料库的评价、基于经验风险最小化的评价和基于实际风险最小化的评价 2。目前比较常用的是属于基于语料库的评价的PASEVAL句法分析评价体系。就目前而言，PASEVAL句法分析评价体系被认为是一种粒度适中较为理想的评价方法，在句法分析系统中使用最为广泛。其评价体系主要由精确率（Precision）和召回率（Recall）组成44。在句法分析系统中对于一组需要分析的句子，设语料库中对这组句子标注的所有成分的集合为目标集，句法分析系统实际分析出的句子成分为分析集。分析集和目标集的交集为共有集。分析集是句法分析系统分析出的所有成分，共有集是分析正确的元素，其它部分是分析错误的元素。目标集是实际包含的所有成分，而目标集减去共有集则为句法分析系统没有分析出的成分。精确率用来衡量句法分析系统所分析的所有成分中正确的成分比例，即 (2-7)召回率用来衡量句法分析系统分析出的所有正确成分在实际成分中的比例，即 (2-8)精确率和召回率通常会相互制约，提高精确率可能会降低召回率，相反提高召回率也可能会降低精确率。2.1.3 数据稀疏问题在统计模型当中，数据稀疏问题是一个普遍存在的问题2。一方面，训练数据不足以覆盖模型的参数空间；另一方面，自然语言当中，大量的语言现象是以小概率事件出现的。目前主要有两种途径来解决数据稀疏问题：数据平滑技术和压缩模型方法。数据平滑技术是最早出现且用的最多的方法，其基本思想是采取某种适当的措施来调节最大似然估计所得到的概率，从而得到一个更为准确的模型参数的概率分布，避免数据稀疏时产生的零概率分布。比较有代表性的方法主要有：加法平滑、Good-Turing估计、线性插值方法(Linear Interpolation)、回退法(Back-off Procedure)等4546。在这些平滑方法当中，加法平滑性能最差，插值方法和回退方法性能稳定，是目前普遍采用的两种方法。插值法与回退法的中心思想都是：用低阶不稀疏的模型去估计高阶出现稀疏的模型。压缩模型的基本原理是采取某种方法压缩模型的参数空间，减少训练所需的数据，从而避免数据稀疏问题。例如，基于等价类的方法是一个典型的压缩模型方法，它把词集划分成等价类，利用类与类的同现概率近似估计为观察到的词语同现概率。这种方法通过压缩模型参数空间，从而增强模型的概括能力，来解决数据稀疏问题47。压缩模型方法虽然代表了解决数据稀疏问题的研究方向，但由于自动聚类方法和相似度方法还不够完善，而且方法本身也存在数据稀疏问题。而平滑方法虽然不够精确，但其本身简单实用，因此在本文中采用平滑方法来解决数据稀疏问题。2.2 常用统计句法分析模型简介及比较由于统计方法相对于规则方法的优越性，加上目前大规模资源库的建设和发展又给统计方法的发展提供了很好的基础和条件，因此，基于统计的句法分析和歧义消解模型得到了很大发展，成为一个比较热门的研究分支。本节的内容就是对常用的统计句法分析模型进行研究，并且简要分析对比了现有的句法分析模型。2.2.1 概率上下文无关文法概率上下文无关文法（Probabilistic Context Free Grammar or Stochastic Context Free Grammar）是最早也是最常用的句法分析模型，它是上下文无关文法（Context Free Grammar）的扩展，将CFG的每一条规则与概率组合，就构成PCFG。PCFG的分析过程与非概率型上下文无关文法相同，也是从非终结符S开始扩展，通过概率型上下文无关文法赋予每棵分析树一个概率，当句子具有结构歧义时，可以利用该概率来选择句子的分析结果，即 (2-9)分析树t的概率就是生成t所用到的所有产生式的条件概率的乘积： (2-10)其中，r是产生式，D(t)表示用于生成分析树t的有序产生式集合。PCFG给出了一种概率型的自然语言句法分析模型，具有一定的消歧能力，PCFG的最大特点是上下文无关，因此PCFG的文法规则容易推导，而且PCFG不考虑上下文，可以一定程度地避免数据稀疏问题，对于开放领域的自然语言分析来说具有较好的鲁棒性。但另一方面，上下文无关假设不可能很好地表示语言的特点，难以解决需要上下文信息才可以消解的句法歧义，而且它只考虑了词性信息而没有考虑词汇或语义信息，所以对语言的描述也是粗粒度的。另外，PCFG对句法结果的概率评价具有倾向性（Bias），由公式(2-10)可知，通常使用规则较少的句法分析结果其概率值大于使用规则较多的句法分析结果，因此PCFG的最优树通常倾向选择句法分析树中较矮的树作为最优结果。2.2.2 基于历史的句法分析模型基于历史的模型由E.Black最早提出，它是一种线性的句法分析模型，其实质类似于N元文法模型，只不过N元文法中的结点是词或词性符号，而基于历史的模型中结点可以是规则。基于历史的模型认为句法分析过程可以看作规则的有序重写过程，非终结结点的扩展相当于一系列的产生式使用过程，句子的句法分析结果由产生式序列产生，在当前分析阶段非终结结点如何扩展，由它前面的扩展过程（这里叫做历史）决定。例如：“努力工作是成功之路”，其句法分析结果如图2-1所示：SVPVPa/努力vg/工作vx/是NSAPa/成功usde/之ng/路wj/。图2-1 “努力工作是成功之路”的句法分析结果2如果以自顶向下，自左至右的顺序进行规则重写，则分析序列为：SVP VP wj，VPa vg，a努力，vg工作，VPvx NS，vx是，NSAP ng，APa usde，a成功，usde之，ng路，wj。设s为句子，t为句法分析结果，为自顶向下分析所用序列。 (2-11)则最好的句法分析结果： (2-12)历史是一个概括化的定义，在当前分析前出现的所有信息都可以作为历史，它可以包含前面使用的规则，扩展的结点的词性或词信息，基于历史的模型可以更抽象地定义为： (2-13)其中为历史的选择函数，对于历史特征的不同选择对应不同的句法分析模型。PCFG模型可以认为是基于历史的模型在不考虑历史信息时的一个特例，因此基于历史的模型的消歧能力强于PCFG，通过对历史函数的定义可以在句法分析模型中体现上下文信息、词汇信息及语言学知识，从而构造多种句法分析歧义消解方法。句法分析的历史序列与选择的句法分析过程相关，比如采用自顶向下、自左至右的分析过程与采用自底向上、自左至右的过程显然不同。已有的基于历史的模型中Black在Lancaster计算机手册语料上所做的句法分析器采用的是自顶向下、自左至右的分析过程，而D.Magerman的SPATTER系统所采用的则为自底向上的分析方法3148。2.2.3 分层渐近式句法分析模型PCFG和基于历史的方法都是一种全局最优的非确定性句法分析方法，需要在整个句法分析结束后才可以选出最优结果。当分析的句子和语法比较复杂时，全局最优需要较大的时间和空间开销。为此，Macus提出了一种确定性的句法分析算法，句法分析的每一步都不需要保留多个可能结果，而只给出一个不需要回溯的确定性结果49。完全确定性的句法分析方法虽然可以很大程度地节约空间和时间开销，但其显然不符合语言的分析规律，因为即使是人，在分析句子时也需要反复。近年来