基于依存关系的句法分析统计模型

袁 里 驰^{1, 2}

(1. 江西财经大学 信息学院数据与知识工程江西省重点实验室，江西 南昌，330013；

2. 中南大学 信息科学与工程学院，湖南 长沙，410083)

摘  要：利用语义、语法等语言知识，建立一种基于依存关系的句法分析统计模型，并利用改进的句法分析模型进行句法分析实验。研究结果表明：利用依存关系、互信息对词聚类，能解决模型数据稀疏问题；模型可同时考虑几种语义依存关系；该模型是一个词汇化的句法分析模型，能结合分词、词性标注进行句法分析；概率上下文无关语法中由概率的上下文无关性假设和祖先结点无关性假设引起的问题在该模型中得到有效解决；精确率和召回率分别为86.96%和85.25%，其综合指标F与Collins的头驱动句法分析模型的F相比提高4.75%。

关键词：自然语言处理；词聚类；中心词驱动；句法分析统计模型

中图分类号：TP391.1          文献标志码：A         文章编号：1672-7207(2009)06-1630-06

Statistical language paring model based on dependency

YUAN Li-chi^{1, 2}

(1. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China;

2. School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: By incorporating linguistic features such as semantic dependency and syntactic relations, a novel statistical Parsing model was proposed. The experiments were conducted for the refined statistical parser. The results show that the model is constructed on word cluster, so the problem of data sparseness is not serious. The model can take advantage of a few semantic dependencies at the same time. The model is a parser based on lexicalized model, it is combined with segmentation and POS tagging model and thus a language parser is built. The questions caused by context-free hypothesis and ancestor-free hypothesis in probability context free grammar are solved well in this model. It achieves 86.96% precision and recall 85.25%, F value is improved by 4.75% compared with that of the head-driven parsing model introduced by Collins.

Key words: natural language processing; word clustering; head-driven parsing model; statistical parsing model

句法分析^[1]，就是指根据给定的语法，自动地识别出句子所包含的句法单位和这些句法单位之间的关系。句法分析是自然语言理解的一个关键组成部分，是对自然语言进行进一步语义分析的基础。随着自然语言应用的日益广泛，特别是对文本处理需求的进一步增加，句法分析的作用愈加突出，它几乎成为大多数自然语言处理应用的关键因素，如机器翻译、信息抽取、问答系统、检索系统等。句法分析的研究大体分为2种途径：基于规则的方法和基于统计的方法。基于规则的方法是以知识为主体的理性主义(Rationalism)方法^[2]，以语言学理论为基础，强调语言学家对语言现象的认识，采用非歧义的规则形式描述或解释歧义行为或歧义特性。基于统计的句法分析^{[1, 3]}必须以某种方式对语言的形式和语法规则进行描述，而且这种描述必须可以通过对已知句法分析结果进行训练获得，这便是句法分析模型。基于树库的统计句法分析^[4-6]是现代句法分析的主流技术。构建统计句法分析模型的目的是以概率的形式评价若干个可能的句法分析结果(通常表示为语法树形式)并在这若干个可能的分析结果中直接选择一个最可能的结果。基于统计的句法分析模型其实质是一个评价句法分析结果的概率评价函数,即对于任意一个输入句子s和它的句法分析结果t，给出一个条件概率P(t|s)，并由此找出该句法分析模型认为概率最大的句法分析结果，即找到,句法分析问题的样本空间为S×T(其中：S为所有句子的集合，T为所有句法分析结果的集合)。

统计句法分析面临的一个主要问题是如何发现和利用具有强消歧能力的语言特征知识^[7-9]，同时保证语言知识的应用不会使模型的参数急剧膨胀而导致严重的数据稀疏问题。本模型从3个方面来融合丰富语言特征知识：a. 利用依存关系、互信息对词聚类，解决了模型数据稀疏问题；b. 同时考虑几种语义依存关系；c. 将句法分析模型与分词、词性标注模型结合进行句法分析。

1   头驱动句法分析模型

Collins使用Penn tree bank实现的头驱动的英语句法分析器^[10]，是目前所知在相同的训练语料和测试集下获得的最好结果。Collins所提出的句法分析模型是一种词汇化模型，其基本思想是在上下文无关规则中引入每个短语的核心词信息。

Collins把分析树的概率分解为 BaseNPs(B) 概率和依存关系(D)概率的乘积：

。   (1)

式中：S为带有词性标记的待分析的长度为n 的英语句子。词性标记采取最大熵标注方法，在S中去掉标点符号，并把BaseNPs 用其中心词表示，形成，则待分析的句子成为 á 词, 词性标记 ? 对的系列。

á?，m≤n。

分析树到依存结构的映射是依存模型的核心，该系统采取了以下步骤计算。

步骤1  对于分析树中每个句法成分P→ áC₁, C₂, …, C_n?，确定P的中心词，中心词从分析树的叶节点向上传播。

步骤2  中心词-修饰关系的抽取，形成三元组，定义，它表示在中的第j个词是第个词的修饰词。它们之间具有关系，D定义为有依存关系的m元组。

；         (2)

。        (3)

模型中，非终结符形如X(x)。其中：x =áw, t?，w为短语对应核心词，t为核心词的词性标记，终结符形如t(w)。

。 (4)

式中：P为非终结符；h为核心结点所在短语的符号标记和词信息；L_i为核心成分的左边成分；R_i为核心成分右边成分。

由于引入词汇信息，不可避免将出现严重的数据稀疏问题。为了避免数据稀疏问题，Collins采取把规则分解的方法，即在训练语料中把每一条规则分解成若干个对应其头节点的依存规则。

已知规则： ，规则的概率由核心成分的概率、核心成分的左依存概率和右依存概率组成，即：

。         (5)

头驱动的句法分析模型与PCFG模型最主要的区别为如下2个方面：

a. 在规则中引入核心结点的词汇信息。

b. 对上下文无关规则进行分解,弱化了上下文无关规则的结构信息，结构信息通过当前结点在核心结点的左或右来体现。

引入词汇信息，无疑增强了句法分析的消歧能力。将上下文无关规则进行分解，一方面解决了引入词汇信息所带来的数据稀疏问题；另一方面，规则进行分解后可以重新组合出训练过程中未出现的上下文无关规则，也在一定程度地解决了上下文无关规则的数据稀疏问题。

但进一步的实验结果表明，句法分析时，规则的结构信息所具有的消歧能力强于词汇信息所起的作用。与PCFG的对比实验结果表明，使用式(5)所构建的句法分析器效果不如PCFG模型的效果。为此，Collins^[10]在模型中增加了一个距离函数来补偿结构信息的缺失。距离信息考虑了3种情况：a. 该成分前是否有成分。b. 该成分前是否出现动词。c. 该成分前是否出现标点符号。

最终规则的概率评价函数为：

头驱动句法分析模型加入词汇信息，提高了句法分析模型的歧义消解能力，但不可避免地又带来了数据稀疏问题，为此，Collins采用回退法对数据进行平滑。在头驱动的句法分析模型中，解决数据稀疏问题是提高句法分析性能的关键。

2   基于依存关系和互信息的词聚类 方法

在汉语的基本句型中，绝大多数句子的中心语是由动词(短语)担当，只有少数句子的中心语是由形容词或体词担当。同样，在汉语的基本句型中，绝大多数句子的主语和宾语都是由名词(短语)担当，只有少数句子主语和宾语是由形容词或动词(短语)担当。由于句子的中心语支配着句子中的其他成分(主语、宾语、状语和补语)，所以，有必要对动词、名词和形容词等各种词的语义知识进行分析并加以分类，进而从中总结出中心语与各被支配成分之间的语义关系。

动词对名词类别的选择决定了什么类的名词能添入什么样的槽内，作者称之为动词对名词的制约选择。从原则上说，动词的概念定义就决定了动词的制约选择。例如，依据作用动词的概念定义，动词的施事必然是能发出使感官直接感受到具体活动的义类名词，其受事则必然使能接受这种活动的义类名词。其余依此类推。

2.1  词的相似度定义

综上所述, 根据语义依存关系^[11]和语法特性对词进行分类很为必要。当然，这些分类可以由语言学家依据语言知识进行，但利用统计模型、结合语言学知识对词自动聚类^[12-13]的方法可能更可取。

设w₁和w₂是具有依存关系rel的词对，用三元组(w₁, rel, w₂)表示词对和它们之间的依存关系。则词对(w₁, w₂)在依存关系rel下的互信息定义为：

2.2  聚类算法

整个算法的流程如下所示：

a. 计算词对之间的相似度。

b. 初始化，词表中的每个词各代表一类，共N类(N为词表中词的数量)。

c. 找出具有最大相似度的2个词类，将这2个词类合并成1个新的词类。

d. 计算刚合并词类与其他词类的相似度。

e. 检查是否达到结束条件(词类之间最大相似度小于某个预先决定的门槛值，或是词类的数目达到了要求)，若是，则程序结束；否则，转步骤c。

3   基于依存关系和聚类的句法分析模型

在使用该模型前，先利用其他的句法分析方法进行句法分析，得到所有可能的句法树，再利用预先输入的词语信息对词语进行句法成分标注,以及归纳出它们之间的语法、语义依存关系，最后利用该模型对句法树进行选择。

该模型在进行概率计算时采取自上而下分层，自左至右的算法。设A表示当前词，T_A表示其词性，B, C, D, …表示在A上层和前面的词，T_B, T_C, T_D, …表示它们的词性。计算条件概率：

由马尔可夫族模型^[14]的假定可知，当前词的出现概率只与它的词性和其他词有关，而与其他词的词性无关。结合依存语法可以认为, 当前词的出现概率只与它的词性和其他与该词有语义依存关系的核心词有关。在1个句子中，与1个词有语义依存关系的核心词可能不止1个，如：

Astronomers saw stars with telescopes。

在该句子中，词telescopes在语义搭配上既与其直接的核心词with有关，又与整个句子的核心词saw有关。当然，依存强度可能有所区别。而与一个词有语法关系的核心词只能有1个，因在用概率上下文无关语法进行句法分析时，应用于每个词的产生式的祖先结点只有1个。

不妨设与词A有语法关系的核心词为B，语法关系为R，与其相邻的前面2个词为C和D，下面计算式(12)右边的第2个条件概率：

。          (13)

假定B，R，T_C，T_D相互独立，当然它们关于条件T_A也相互独立，则有：

。    (14)

再由贝叶斯公式，有：

；

。(15)

将式(15)代入式(14)，有：

。       (16)

条件概率相当于在上下文无关规则的概率计算中引入每个短语的核心词信息，如产生式VP→V NP 改进为：

VP (saw) →V(saw)NP(president)。

由于数据稀疏问题, 核心词可用核心词的语法类(有相同语法搭配关系的一类词)来代替。而  即为词性标注中常用的三元模型。因此，式(16)意义明确。

设与词A有语义依存关系的核心词为E和F， 依存关系为rel_E，rel_F，则式(12)右边的第一个条件概率为：

。     (17)

经与上面类似的计算可得：

。     (18)

为了减少参数较多引起的数据稀疏问题, 条件概率可使用插值方法计算：

为了进一步减少数据稀疏，可用词A，E和F归属的语义类W_A，W_E，W_F代替A，E和F。

综上所述，该模型的计算主要包括式(16)和式(18)这2个部分。该模型在将语言知识与统计方法融合方面得到成功应用，模型的概率意义也非常明确。

4  实验结果

本文的实验是在宾州中文树库Chinese Treebank (CTB)5.0上进行的。CTB是由语言数据联盟(LDC)公开发的一个语料库，为汉语句法分析研究提供了一个公共的训练和测试平台。该树库包含了507 222个词，824 983个汉字，18 782个句子，有890个数据文件。作者将文件301~325(353个句子，6 776个词) 作为调试集，将文件271~300(348个句子，7 980个词)作为测试集，其余文件作为训练集。本文的所有实验中，模型的参数都是从训练集中采用极大似然法估计出  来的。

对测试的结果采取常用的3个评测指标，即准确率P、召回率R、综合指标F。精确率(Precision)用来衡量句法分析系统所分析的所有成分中正确成分的比例；召回率(Recall)用来衡量句法分析系统分析出的所有正确成分在实际成分中的比例；综合指标。

实验1  本研究首先利用词汇化模型对测试集中的句子进行分词和词性标注，与最常用的隐马尔可夫词性标注模型(HMM)进行对比。表1所示为实验结果。可以看到，词汇化模型的词性标注效果要好于HMM的词性标注效果。

表 1  词性标注实验结果

Table 1  Experimental results of POS tagging

隐马尔可夫词性标注模型假定当前词类标记的出现概率只与它紧邻的前1个或几个词类标记有关；词汇化词性标注模型认为当前词类标记的出现概率不但与它紧邻的前面词类标记有关，而且与当前词本身的词类特性有关。从统计学的角度来说，与词汇化模型的假设相比，隐马尔可夫词性标注模型的假设是过强假设。实验1的结果也证明了词汇化模型更符合语言现象。

实验2  实验中作者采用的句法分析Baseline系统是Daniel M.Bikel基于Collins模型实现的DBParser。表2所示为Baseline系统和改进模型的句法分析实验结果。从表2可以看出：由于在词的聚类、句法成分标注中，多层次地利用了语法和语义依存关系等语言知识，改进模型的准确率P、召回率R和综合指标F与Collins的头驱动句法分析模型相比有明显提高。

表2  句法分析实验结果

Table 2  Experimental results of language parsing

5  结  论

a. 语言特征知识的应用对统计句法分析有很大的影响，这从一个侧面指出了汉语统计句法分析研究的一个方向，即从语言学角度寻找更多的特征知识。从统计句法分析的角度来看，一个好的计算模型加上丰富的语言特征知识才是最佳选择。

b. 依存语法分析句子的方式，是通过分析句子成分间的语法和语义依存关系，建立以句子成分为节点的依存语法树，以此表达句子的结构。所以，首先要解决的问题是，确定依存语法中句子成分的种类和成分之间的依存关系类型。通常在统计句法分析中融入语义知识的模型(即基于语义依存关系的句法分析  模型)。

c. 利用语义和语法等语言知识，建立了一种基于依存关系的句法分析统计模型，并结合分词和词性标注进行句法分析。在概率上下文无关语法中，由概率的上下文无关性假设和祖先结点无关性假设引起的问题在该模型中得到有效解决。与Collins的头驱动句法分析模型相比，由于在词的聚类和句法成分标注中,多层次地利用了语法和语义依存关系等语言知识，改进模型的性能有明显提高。

d. 在头驱动的句法分析模型中解决数据稀疏问题是提高句法分析性能的关键。利用依存关系、互信息对词聚类，较好地解决了数据稀疏问题。

参考文献：

[1] Manning C D, Schutze H. Foundations of statistical natural language processing[M]. London: The MIT Press, 1999.

[2] 钟义信. 关于“信息—知识—智能转换规律”的研究[J]. 电子学报, 2004, 32(4): 601-605.
ZHONG Yi-xin. A study on information—knowledge—intelligence transformation[J] Chinese Journal of Electronics, 2004, 32(4): 601-605.

[3] Chelba C, Jelinek F. Structured language modeling[J]. Computer Speech and Language, 2000, 14(4): 283-332.

[4] XUE Nian-wen, XIA Fei, CHIOU Fu-dong, et al. The Penn Chinese treebank: Phrase structure annotation of a large corpus[J]. Natural Language Engineering, 2005, 11(2): 207-208.

[5] Fung P, Ngai G, YANG Yong-sheng, et al. A maximum-entropy Chinese parser augmented by transformation-based learning[J]. ACM Trans on Asian Language Processing, 2004, 3(2): 159-168.

[6] Goodman J T. A bit of progress in language modeling[J]. Computer Speech and Language, 2001, 10: 403-434.

[7] 赵 军, 黄昌宁. 汉语基本名词短语结构分析模型[J]. 计算机学报, 1999, 22(2): 141-146.
ZHAO Jun, HUANG Chang-ning. The model for Chinese basenp structure analysis[J]. Chinese Journal of Computers, 1999, 22(2): 141-146.

[8] 孟 遥, 李 生, 赵铁军, 等. 四种基本统计句法分析模型在汉语句法分析中的性能比较[J]. 中文信息学报, 2003, 17(3): 1-8.
MENG Yao, LI Sheng, ZHAO Tie-jun, et al. A comparative study of four primary statistical models in Chinese parsing[J]. Journal of Chinese Information Processing, 2003, 17(3): 1-8.

[9] 杨开城. 一种基于句法语义特征的汉语句法分析器[J]. 中文信息学报, 2000, 14(3): 46-53.
YANG Kai-cheng. A syntax parser based on syntax-semantic properties[J]. Journal of Chinese Information Processing, 2000, 14(3): 46-53.

[10] Collins M. Head-driven statistical models for natural language parsing[D]. Pennsylvania: The University of Pennsylvania, 1999.

[11] Seo K J, Nam K C, Choi K S. A probalistic model of the dependency parse of the variable-word-order languages by using ascending dependency[J]. Computer Processing of Oriental Languages, 2000, 12(3): 309-322.

[12] Lee L. Similarity-based approaches to natural language processing[D]. Cambridge, MA: Harvard University, 1997.

[13] GAO Jian-feng, Goodman J, MIAO Jiang-bo. The use of clustering techniques for language model—Application to Asian language[J]. Computational Linguistics and Chinese Language Processing, 2001, 6(1): 27-60.

[14] 袁里驰. 基于改进的隐马尔科夫模型的语音识别方法[J]. 中南大学学报: 自然科学版, 2008, 39(6): 1303-1308.
YUAN Li-chi. A speech recognition method based on improved hidden Markov model[J]. Journal of Central South University: Science and Technology, 2008, 39(6): 1303-1308.

收稿日期：2009-03-23；修回日期：2009-06-12

基金项目：国家自然科学基金资助项目(60763001，60663007)；中南大学博士后科学基金资助项目(2007年)

通信作者：袁里驰(1973-), 男，湖南邵阳人，博士，副教授，从事自然语言处理与语音识别研究；电话：13576126095；E-mail: yuanlichi@sohu.com