基于词聚类的依存句法分析

袁里驰^{1, 2}

 (1. 江西财经大学 信息学院，江西 南昌，330013；

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

摘要：利用语义、语法等语言知识，对中心词驱动的句法分析模型规则进行分解和修改，结合分词、词性标注进行句法分析，提出一种可同时考虑多个语义依存关系的模型。利用互信息给出基于邻接关系、语义依存关系的2种词相似度定义，提出一种自下而上的分层聚类算法，以解决中心词驱动模型数据稀疏问题，用改进的句法分析模型进行句法分析实验。研究结果表明：模型精确率和召回率分别为88.14%和86.93%，综合指标比Collins头驱动句法分析模型的综合指标提高6.09%。

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

中图分类号：TP391.1          文献标志码：A         文章编号：1672-7207(2011)07-2023-05

Dependency language Parsing model based on word clustering

YUAN Li-chi^{1, 2}

(1. School of Information Technology, Jiangxi University of Finance & 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 model was constructed on cluster, and the problem of data sparseness was not serious. The model took advantage of a few semantic dependencies at the same time, and it was a parser based on lexicalized model. Experiments were conducted for the refined statistical parser. The results show that precision and recall are 88.14% and 86.93%, respectively, and comprehensive factor is improved by 6.09% compared with that of the head-driven parsing model.

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

句法分析^[1]是指根据给定的语法，自动地识别出句子所包含的句法单位和这些句法单位之间的关系。句法分析是自然语言理解的一个关键组成部分，是对自然语言语义进行进一步分析的基础。随着自然语言应用的日益广泛，特别是对文本处理需求的进一步增加，句法分析的作用愈加突出，它几乎成为大多数自然语言处理应用的关键因素，如机器翻译、信息抽取、问答系统、检索系统等。句法分析的研究大体分为2种途径：基于规则的方法^[2]和基于统计的方法^[3]。基于规则的方法是以知识为主体的理性主义(Rationalism)方法，以语言学理论为基础，强调语言学家对语言现象的认识，采用非歧义的规则形式描述或解释歧义行为或歧义特性；基于统计的句法分析必须以某种方式对语言的形式和语法规则进行描述，而且这种描述必须可以通过对已知句法分析结果的训练获得，这便是句法分析模型。基于树库的统计句法分析^[4-10]是现代句法分析的主流技术。构建统计句法分析模型的目的是以概率的形式评价若干个可能的句法分析结果(通常表示为语法树形式)并在这若干个可能的分析结果中直接选择一个最可能的结果。基于统计的句法分析模型其实质是一个评价句法分析结果的概率评价函数，即对于任意一个输入句子s和它的句法分析结果t，给出一个条件概率P(t|s)，并由此找出该句法分析模型认为概率最大的句法分析结果，即找到，句法分析问题的样本空间为S×T(其中S为所有句子的集合，T为所有句法分析结果的集合)。Collins^[11]提出的中心词驱动的句法分析模型是当前句法分析的主流模型，其基本思想是在上下文无关文法规则中引入词汇化信息和短语的中心词信息。这2种信息的引入增强了句法分析模型的消歧能力，然而，不可避免地带来了严重的数据稀疏问题。基于类的统计语言模型是解决统计模型数据稀疏问题的重要方法，本文利用互信息定义词相似度，提出一种自下而上的分层聚类算法，以解决Collins模型引入词汇信息所带来的数据稀疏问题。在此，本文作者利用互信息给出基于邻接关系、语义依存关系^[12-13]的种词相似度定义，在词相似度的基础上提出一种自下而上的分层聚类算法；对Collins模型的规则进行分解和修改，给出基于聚类和依存关系的句法分析模型。

1  基于词相似度的分层聚类算法

1.1   基于邻接关系的词相似度

聚类算法^[14]有很多种，可归结为2种基本类型：层次聚类与非层次聚类。非层次聚类只包括每类的数量，类与类之间的关系不确定。层次聚类的每一个节点是其父节点的1个子类，叶节点对应的是类别中每个单独的对象，常用算法有自下向上法与自上向下法(即凝聚法与分裂法)。

传统的统计聚类方法通常基于贪婪原则，以语料的似然函数或困惑度作为判别函数。这种传统方法的主要缺点是聚类速度慢，初值对结果影响大，易陷入局部最优。而本文提出的分层聚类算法基于词的相似度，因此，首先要找到一种可靠的、适于计算的词与词间相似度的定量标准。基于语料库的统计方法通常认为一个词的意义与其所处的上下文中出现的其他词即语言环境有关。若2个词在语料库中所处的语言环境总是非常相似，则可以认为这2个词彼此之间非常相似^[15-16]。

假定词w₁与词w₂相似，则可推断这2个词与其他词的互信息也是相似的。定义2个词w₁和w₂之间的相似度如下：

 (1)

其中：为相邻词对w_i和w_j之间的互信息，

            (2)

p(w_i)和p(w_j)分别为词w_i和w_j在训练语料中出现的概率；p(w_i, w_j)为联合概率。由式(1)可知：w₁和w₂与它们的左右近邻之间互信息差别越小，两词的相似度也越高，因此，这种定义是合理的。更进一步可以定义2个词w₁和w₂之间的左相似度sim_L(w₁, w₂)和右相似度sim_R(w₁, w₂)：

  (3)

  (4)

基于词相似度，词类C₁和C₂之间的相似度定义为：

    (5)

其中：C(w_i)和C(w_j) 分别表示词w_i与w_j 在语料中出现的数量。类似地，可以定义词类之间的左相似度和右相似度。

1.2   基于语义依存关系的词相似度

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

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

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

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

      (6)

其中：。

这里计算要用到的概率使用极大似然估计(Maximum likeihood estimation)的方法统计：

     (7a)

       (7b)

       (7c)

           (7d)

其中：“*”表示可能的词或依存关系，因而，有

  (8)

定义1  词对w₁和w₂在依存关系r_el下的相似度定义为：

(9)

定义2  词对w₁和w₂之间的相似度则定义为：

      (10)

1.3   聚类算法

整个算法的流程如下：(1) 计算词对之间的相似度；(2) 初始化，词表中的每个词各代表一类，共N类(N为词表中词的数量)；(3) 找出具有最大相似度的2个词类，将这2个词类合并成1个新的词类；(4) 计算刚合并词类与其他词类的相似度；(5) 检查是否达到结束条件(词类之间最大相似度小于某个预先决定的门槛值，或词类的数目达到要求)，若是，则程序结束；否则，转(3)。

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

2.1   中心词驱动模型的基本原理

中心词驱动模型是最具有代表性的词汇化模型。为了发挥词汇信息的作用，中心词驱动模型为文法规则中的每一个非终结符(none terminal)都引入核心词/词性信息。由于引入词汇信息，将不可避免地出现严重的稀疏问题。为了缓解这个问题，中心词驱动模型把每一条文法规则的右手侧分解为三大部分：1个中心成分；若干个在中心左边的修饰成分；若干个在中心右边的修饰成分。可以写成如下形式：

          (11)

其中：P为非终结符；H表示中心成分；L_i表示左边修饰成分；R_i表示右边修饰成分；H_w，l_w和r_w均为成分的核心词；h_t，l_t和r_t分别为它们的词性。进一步假设：首先由P产生核心成分H，然后，以H为中心分别独立地产生左、右两边的所有修饰成分。这样，形如(11)式的文法规则的概率为：

       (12)

其中：L_m+1和R_n+1分别为左、右两边的停止符号。

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

模型在进行概率计算时采取自上而下分层、自左至右的算法。设表示当前核心词h所依赖的上层核心词。每一条文法规则写成如下形式：

    (13)

形如式(13)的文法规则的概率为：

       (14)

其中：L_m+1和R_n+1分别为左、右两边的停止符号。式(14)中的概率 可分解为2个概率，即和

的乘积，由马尔可夫族模型^[16]的假定，有：

      (15)

   (16)

由于引入词汇信息，不可避免地将出现严重的数据稀疏问题，为了避免数据稀疏问题，可用基于类的模型代替基于词的模型。设C′(w)和C(w)分别表示w基于邻接关系和语义依存关系的聚类，则(16)式中的概率为：

可近似为：

 (17)

其中：0＜＜1。

句子Astronomers saw stars with telescopes具有2种含义，因此，具有2棵不同的句法树图(如图1和图2所示)。

2棵句法分析树和它们对应的驱动的规则如下：

Top→S(saw)             (18a)

S(saw) →NP(NNs,Astronomers)VP(V,saw) (18b)

VP(v,saw) →V(v,saw)NP(NNs,stars)   (18c)

NP(NNs,stars|saw)→

NP(NNs,stars|saw)PP(p,with)       (18d)

PP(p,with|stars) →

PP(p,with|stars)NP(NNs,telescopes)     (18e)

Top→S(saw)            (19a)

S(saw) →NP(NNs,Astronomers)VP(V,saw)  (19b)

VP(v,saw) →VP(v,saw)PP(p,with)     (19c)

VP(v,saw)→V(v,saw)NP(NNs,stars)    (19d)

PP(p,with|saw)→

p(p,with|saw)NP(NNs,telescopes)     (19e)

其中，规则(18e)和(19e)对应的概率分别为：

P(p,with|stars)?P(NNs, telescopes|(p,with),stars)  (20)

P(p,with|saw)?P(NNs, telescopes|(p,with),saw)   (21)

与Collins的头驱动句法分析模型相比较，通过概率(20)和(21)的计算，就能选出正确的句法分析树。

图1  句子分析树1

Fig.1  Parse tree Ⅰ of sentence

图2  句子分析树2

Fig.2  Parse tree Ⅱ of sentence

3  实验结果

本文的实验在宾州中文树库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)用来衡量句法分析系统分析出的所有正确成分在实际成分中的比例；综合指标。

实验中采用的句法分析Baseline系统是Bikel基于Collins模型实现的DBParser。Baseline系统和改进模型的句法分析实验结果见表1。

表1  句法分析实验结果

Table 1  Experimental results of language parsing

从表1可以看出：由于在词的聚类、规则的分解及概率计算中，多层次地利用了语法、语义依存关系等语言知识，改进模型的准确率P、召回率R、综合指标F与Collins的头驱动句法分析模型的相比明显 提高。

4   结论

(1) 语言特征知识的应用对统计句法分析有很大影响，表明可从语言学角度寻找更多的特征知识。

(2) 依存语法分析句子的方式是通过分析句子成分间的语法、语义依存关系，建立以句子成分为节点的依存语法树，以此表达句子的结构。所以，首先要确定依存语法中句子成分的种类和成分之间的依存关系类型。

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

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

参考文献：

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

[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] Joshua G. A bit of progress in language modeling[J]. Computer Speech and Language, 2001, 15(4): 403-434.

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

[5] Fung P, Ngai G, Yang Y S, 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] Ciprian C, Frederick J. Structured language modeling[J]. Computer Speech and Language, 2000, 14(4): 283-332.

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

[8] 刘水, 李生, 赵铁军, 等. 头驱动句法分析中的直接插值平滑算法[J]. 软件学报, 2009, 20(11): 2915-2924.
LIU Shui, LI Sheng, ZHAO Tie-jun, et al. Directly smooth interpolation algorithm in head-driven parsing[J]. Journal of Software, 2009, 20(11): 2915-2924.

[9] Aviran S, Siegel P H, Wolf J K. Optimal parsing trees for run-length coding of biased data[J]. IEEE Transaction on Information Theory, 2008, 54(2): 841-849.

[10] ZHOU De-yu, HE Yu-lan. Discriminative training of the hidden vectors state model for semantic parsing[J]. IEEE Transaction on Knowledge and Data Engineering, 2009, 21(1): 66-77.

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

[12] 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.

[13] 李正华, 车万翔, 刘挺. 基于柱搜索的高阶依存句法分析[J]. 中文信息学报, 2010, 24(1): 37-41.
LI Zheng-hua, CHE Wan-xiang, LIU Ting. Beam-search based high-order dependency parser[J]. Journal of Chinese Information Processing, 2010, 24(1): 37-41.

[14] 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.

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

[16] 袁里驰. 基于改进的隐马尔科夫模型的语音识别方法[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.

(编辑 陈灿华)

收稿日期：2010-07-11；修回日期：2010-10-08

基金项目：国家自然科学基金资助项目(60763001)；江西省自然科学基金资助项目(2009GZS0027，2010GZS0072)；全国教育科学“十一五”规划课题(ECA080292)

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