依存句法分析方法综述

杨振鹏

摘 要：近年来，自然语言处理发展迅速，依存句法分析作为自然语言处理的重要组成部分，成了句法分析研究的热点问题。目前较为成熟的依存句法分析方法有4种：生成式句法分析模型、判别式句法分析模型、决策式句法分析模型和约束满足句法分析模型。文章详细介绍了4种句法分析模型的原理，并对模型算法进行了对比分析。

关键词：依存句法分析；生成式句法分析模型；判别式句法分析模型；决策式句法分析模型；约束满足句法分析模型

语法理论是任何一种句法分析的基础。现有的语法体系中，用两个词之间的依存关系来描述依存语法的语言结构。依存语法的结构将谓词作为研究的中心，并且表层句法结构的条件及状况由深层语义的结构来体现，谓词的词类由谓词与体词之间的同现关系来划分。依存语法具有易于理解、便于词性标注、形式简洁清晰等优势，受到了许多学者的关注。目前，许多研究人员在自然语言处理领域中应用了依存语法，促进了依存句法分析方法的发展。

1 依存句法分析的研究现状

1.1 英语依存句法分析现状

短语结构的句法分析一直是英语的句法分析的主要工作，而依存句法的研究开展则相对滞后。Melchuk在1988年全面系统的研究了英语的依存语法理论，Eisner[1]在1997年最先提出了树库转化的思想，依存树库通过短语树库转化得到，并进行了相关的转化实验。Eisner在数据转换时对含连词的句子进行过滤，其余的句子使用规则进行自动转换，得到了90.1%的依存正确率。

依存句法分析吸引了越来越多的研究者加入，他们对英语的依存体系进行了完善。在实践方面，Yamada等[2]使用支持向量机的方法进行短语结构的转换，主要是对Penn Treebank中的句子进行转换，获得了90.5%的正确率。在此基础上，Nivre和McDonald进一步深入研究了英语的依存分析工作，促进了英语依存分析的发展。

近几年，许多学者对联合模型表现出了极大的兴趣，并进行了相关联合模型的研究。李正华等于2011年提出了汉语词性标注与依存句法分析相结合的联合模型，Jun等[3]等提出了分词、词性标注以及依存句法分析三者相结合的联合模型。

1.2 汉语依存句法分析现状

在汉语方面，最近几年依存句法分析的工作逐渐受到关注。Zhou[4]很早就做过依存语法的相关研究，他根据制定的语法规则对句子进行分块处理，找出那些关系固定的语块，然后对整个句子进行依存分析。Ma等在汉语依存分析方面，利用无指导的方法做了有价值的研究。

随着汉语应用的日益广泛，国外的学者也开始了汉语依存分析的研究工作。Chen等分别在Chinese Penn Treebank（CTB）和CKIP树库上进行了依存分析的实验。在基于CTB的实验中，主要从特征和算法复杂度方面改进了Nivre算法，一方面扩大了全局特征，另一方面对算法进行优化，在寻找根节点时，分别分析根节点两侧的句子，降低复杂度。实验获得了86.18%的依存关系正确率。在基于CKIP树库的实验中，首先进行数库的转换，利用确定性搜索算法将短语结构树库自动转化为依存结构树库。用CKIP树库中的部分数据作实验数据，句子平均长度为5.7词。根据篇章类型的不同分别进行测试，效果最好的是文学类，其正确率分别为：句子核心词94%，整句71%，依存关系87%；效果最差的是新闻类，核心词86.9%，整句50%，依存关系74%。

Jin等对Nivre和Yamada方法进行改进，新的移进—归约算法采用双阶段方式进行汉语依存分析，第一阶段的归约由两部分构成，一是归约左边的依存弧，二是归约右边的体词性依存节点，第二阶段则主要是对右边的动词性依存节点进行归约。实验时，先对CTB 4.0进行转换，然后抽取转换结果中部分句子作为实验数据，依存正确率为84.52%。

2 主流的依存句法分析方法

目前主要的依存句法分析模型可大致歸为以下4类：生成式的句法分析模型、判别式的句法分析模型、决策式的句法分析模型和约束满足的句法分析模型。

2.1 生成式依存句法分析模型

生成式模型将采用联合概率score（x，y|θ）（其中，已知序列为x，依存分析结构为y，模型的参数为θ）生成一系列依存句法树，并赋予其概率分值，然后采用相关搜索算法找到概率打分最高的分析结果作为最后输出。在句法分析中，已知序列输入的是句子；输出的是依存结构树T。生成式模型的最终目标是从训练模型中获取使联合概率P（T，S）取得最大值的参数θ，得分最高的依存结构树。为了便于计算联合概率P（T，S），可以对句法分析问题作出不同程度的假设，这将有效减少数据稀疏问题。

生成式的句法分析与短语结构树的分析方法关系密切，PCFG方法是生成式方法的基础。起初，生成式的句法分析模型所采用的算法与由短语结构句法分析算法相似，它也采用全局搜索，生成多棵依存树，每个句子对应一棵或多棵依存树，最后系统输出概率最高的那棵依存树，算法正确率较高，但复杂度也很高，一般为O（n3）或（n5）。

生成式依存句法分析主要有以下3种模型。

（1）二元词汇亲和模型，该模型加入了词汇信息，将词性和词形联合。一个标记序列由马尔柯夫过程产生，链接关系对词汇是敏感的，每一对词是否可以构成链接关系的决策依赖于词汇信息，最终生成词性、词形和链接关系的联合概率模型。

（2）选择偏好模型，该模型加入了词的选择偏好信息，不再穷举所有连接再根据约束进行剪裁，而是限制模型为每个词只选择一个父结点。

（3）递归生成模型，该模型中每个词的左子结点和右子结点分别由各自的马尔柯夫模型顺次产生：左子结点的产生方向是自右向左，右子结点的产生方向是自左向右的。每一个子结点的生成建立在支配词和它前一个子结点上，是自顶向下的递归生成式模型。

2.2 判别式依存句法分析模型

判别式模型为了得到正确的分类边界，从非单一样本的数据中抽取出共有的特征。判别式句法分析为了避开联合概率模型中所要求的独立性假设，分析方法中采用条件概率模型。其代表模型是宾西法尼亚大学的最大生成树句法分析器，这是真正意义上的依存句法分析器。但是，非投影问题对系统复杂度是一个很大的挑战，判别式依存句法的优势在于对非投影问题的处理分析，该方法更加注重算法复杂度的降低。判别式的句法分析方法和生成式的分析方法一样，都是进行整个句子内的全局搜索，所以算法复杂度是必须要考虑的问题。判别式方法的一个最大缺陷是它的训练方法繁琐，需要重复分析训练集来迭代参数。

判别式依存句法分析模型的基本思想是：采用条件概率模型score（x，y|θ），使目标函数取得最大值的θ作为模型的参数。

通常，采用对数线性模型来进行判别模型的参数估计，并在句法分析中常以分类器的形式体现。首先，将句法分析进行分解，随后的操作由分类器来选择。在句法分析中应用较多的判别模型有：最大熵模型、支持向量机模型、决策树模型等。

2.2.1 最大熵

在英语的句法分析中，Ratnaparkhi最早引入了最大熵的方法，他利用上下文特征，通过最大熵的方法来预测下一步要执行的操作。其上下文特征主要包括：成分的核心词，核心词的组合，非特定组合信息，以及部分已完成的子树信息。

2.2.2 支持向量机

支持向量机是一种基于统计学习原理的线性分类器，可以使构成的超平面分割训练数据时，能够获得最大的边缘。支持向量机具有良好的应用效果，在自然语言处理中应用较为广泛，常用于文本分类等问题。

支持向量机的主要缺点是其训练效率偏低，并且对于输出结果不能准确地给出各个输出结果的概率分布，这就限制了它在概率需求较强的任务中的应用，给一些利用概率结果的处理和应用带来了麻烦。

2.2.3 决策树

决策树是另外一种比较典型的判别学习方法。它是一种“问卷表”方式的做法，利用一系列的查询问答来判断和分类某一模式，它将全部问题集用一棵有向树表示，对非度量数据而言效果较好。在英语的句法分析中，决策树的方法在英语的P宾州树库上取得了83%以上的正确率。决策树学习方法也存在一些问题，例如，在高维问题的处理上效果就不够理想。

2.3 决策式依存句法分析模型

决策式的句法分析方法，是以特定的方向逐步取一个待分析的词，为每次输入的词产生一个单一的分析结果，每读入一个词，都要根据当前状态作出决策。分析过程可以看作是一步步作用于输入句子之上的分析动作的序列。

决策式句法分析模型的典型代表是移近—归约状态转移模型。移近—归约状态转移模型在分析过程中维护一个堆栈和一个队列，堆栈用以存储到目前为止所有的依存子树，队列存储尚未被分析到的词。堆栈顶端和队列的头部确定了当前分析器的状态，依据该状态决定进行移进、规约或者建立栈顶元素与队首元素的依存关系的操作，从而转入新的状态。

Sagae等[5]依照单纯的移进—归约的思想实现了一个确定性的句法分析器，解码采用贪心策略，该文实验中采用支持向量机分类器和基于存储的分类器，支持向量机分类器实验结果为：召回率80.2%，准确率为80.0%；基于存储分类器实验结果为：召回率87.6%，准确率87.5%。同时，也从理论上证明了句法分析的时间复杂度为O（n），其中n值是句子的长度。

Zhang等[6]对Sagae进行了改进，使用线性模型对决策序列进行预测，从全局的角度对决策进行了考量，采用泛化的感知器算法对模型的参数进行训练，模型解码时，不再像Sagae使用确定性方式，而是引入BeamSearch策略，实验中讨论了Beam-size和训练数据集的大小对实验结果的影响，可惜的是此文只给出了在CTB上的实验结果。

2.4 约束满足依存句法分析模型

约束满足的依存句法分析模型采用约束依存语法，将依存句法分析看作可以用约束满足的问题来描述的有限构造问题。它是根据已规定好的约束进行剪裁，把不符合约束的分析去掉，规定好的约束进行剪裁，把不符合约束的分析去掉，直到留下一棵合法的依存树。

约束满足的依存句法分析模型也存在一些问题：可能不存在能满足所有约束的分析树，也可能有多个树满足所有约束，无法消歧。

3 结语

依存句法分析成为当今句法学研究的前沿和热点问题之一，随着研究的深入，依存句法分析模型也日趋成熟。通过对目前主流依存句法分析模型的分析，现有的模型大多是通过经典模型的改进而来，汉语依存句法分析明显落后于英语依存句法分析。

对于目前汉语依存的发展，研究要结合汉语自身的特点。就目前而言，统计方法已成为主流技术，尽管英语方面出现许多较为成熟的统计模型，可以为汉语分析所借鉴，但汉语的语言特点使得研究人员在借鉴其优点的同时，还应该结合汉语特点进行特殊处理，比如汉语中特殊语法结构（排比句、叠词等）的处理。利用语法、语义等方面知識构建联合模型来提高依存分析的正确率，构建的词义、词性标注和依存分析的联合模型。联合模型开辟了一种新的思路，可以成为我们研究的一种方向。

[参考文献]

[1]EISNER J.Bilexical grammars and a cubic-time probabilistic parser[J].Proceedings of the International Workshop on Parsing Technologies，1997（20）：54-65.

[2]YAMADA H，MATSUMOTO Y.Statistical dependency analysis with support vector machines[C].Vancouver：Proceeding of the 8th International Workshop on Parsing Technologies，2003：195-206.

[3]JUN H，TAKUYA M，YUSUKE M，et al.Incremental joint approach to word segmentation，pos tagging，and dependency parsing in Chinese[C].Beijing：Proceedings of the 5th International Joint Conference on Natural Language Processing，2011：1225-1234.

[4]ZHOU M.A block-based dependency parser for unrestricted Chinese text[C].Hong Kong：Proceeding of the 2nd Chinese Language Processing Workshop Attached to ACL-2000，2000：78-84.

[5]SAGAE K，ALON L.A classifier-based parser with linear run-time complexity[C].Hirosaki：Proceeding of IWPT，2005：125-132.

[6]ZHANG Y，STEPHEN C.Syntactic processing using the generalized perceptron and beam search[J].Computational Linguistics，2011（1）：105-151.