基于詞聚類的依存句法分析

袁里馳

(1. 江西財經大學 信息學院，江西 南昌，330013；2. 中南大學 信息科學與工程學院，湖南 長沙，410083)

句法分析[1]是指根據給定的語法，自動地識別出句子所包含的句法單位和這些句法單位之間的關系。句法分析是自然語言理解的一個關鍵組成部分，是對自然語言語義進行進一步分析的基礎。隨著自然語言應用的日益廣泛，特別是對文本處理需求的進一步增加，句法分析的作用愈加突出，它幾乎成為大多數(shù)自然語言處理應用的關鍵因素，如機器翻譯、信息抽取、問答系統(tǒng)、檢索系統(tǒng)等。句法分析的研究大體分為 2種途徑：基于規(guī)則的方法[2]和基于統(tǒng)計的方法[3]?；谝?guī)則的方法是以知識為主體的理性主義(Rationalism)方法，以語言學理論為基礎，強調語言學家對語言現(xiàn)象的認識，采用非歧義的規(guī)則形式描述或解釋歧義行為或歧義特性；基于統(tǒng)計的句法分析必須以某種方式對語言的形式和語法規(guī)則進行描述，而且這種描述必須可以通過對已知句法分析結果的訓練獲得，這便是句法分析模型?；跇鋷斓慕y(tǒng)計句法分析[4-10]是現(xiàn)代句法分析的主流技術。構建統(tǒng)計句法分析模型的目的是以概率的形式評價若干個可能的句法分析結果(通常表示為語法樹形式)并在這若干個可能的分析結果中直接選擇一個最可能的結果?；诮y(tǒng)計的句法分析模型其實質是一個評價句法分析結果的概率評價函數(shù)，即對于任意一個輸入句子s和它的句法分析結果t，給出一個條件概率 P(t|s)，并由此找出該句法分析模型認為概率最大的句法分析結果，即找到句法分析問題的樣本空間為S×T(其中S為所有句子的集合，T為所有句法分析結果的集合)。Collins[11]提出的中心詞驅動的句法分析模型是當前句法分析的主流模型，其基本思想是在上下文無關文法規(guī)則中引入詞匯化信息和短語的中心詞信息。這2種信息的引入增強了句法分析模型的消歧能力，然而，不可避免地帶來了嚴重的數(shù)據稀疏問題?；陬惖慕y(tǒng)計語言模型是解決統(tǒng)計模型數(shù)據稀疏問題的重要方法，本文利用互信息定義詞相似度，提出一種自下而上的分層聚類算法，以解決Collins模型引入詞匯信息所帶來的數(shù)據稀疏問題。在此，本文作者利用互信息給出基于鄰接關系、語義依存關系[12-13]的種詞相似度定義，在詞相似度的基礎上提出一種自下而上的分層聚類算法；對Collins模型的規(guī)則進行分解和修改，給出基于聚類和依存關系的句法分析模型。

1 基于詞相似度的分層聚類算法

1.1 基于鄰接關系的詞相似度

聚類算法[14]有很多種，可歸結為2種基本類型：層次聚類與非層次聚類。非層次聚類只包括每類的數(shù)量，類與類之間的關系不確定。層次聚類的每一個節(jié)點是其父節(jié)點的1個子類，葉節(jié)點對應的是類別中每個單獨的對象，常用算法有自下向上法與自上向下法(即凝聚法與分裂法)。

傳統(tǒng)的統(tǒng)計聚類方法通常基于貪婪原則，以語料的似然函數(shù)或困惑度作為判別函數(shù)。這種傳統(tǒng)方法的主要缺點是聚類速度慢，初值對結果影響大，易陷入局部最優(yōu)。而本文提出的分層聚類算法基于詞的相似度，因此，首先要找到一種可靠的、適于計算的詞與詞間相似度的定量標準?；谡Z料庫的統(tǒng)計方法通常認為一個詞的意義與其所處的上下文中出現(xiàn)的其他詞即語言環(huán)境有關。若2個詞在語料庫中所處的語言環(huán)境總是非常相似，則可以認為這2個詞彼此之間非常相似[15-16]。

假定詞w1與詞w2相似，則可推斷這2個詞與其他詞的互信息也是相似的。定義2個詞w1和w2之間的相似度如下：

其中： ),(jiwwI 為相鄰詞對wi和wj之間的互信息，

p(wi)和 p(wj)分別為詞wi和 wj在訓練語料中出現(xiàn)的概率；p(wi, wj)為聯(lián)合概率。由式(1)可知：w1和w2與它們的左右近鄰之間互信息差別越小，兩詞的相似度也越高，因此，這種定義是合理的。更進一步可以定義2個詞w1和w2之間的左相似度simL(w1, w2)和右相似度simR(w1, w2)：

基于詞相似度，詞類C1和C2之間的相似度定義為：

其中：C(wi)和C(wj) 分別表示詞wi與wj在語料中出現(xiàn)的數(shù)量。類似地，可以定義詞類之間的左相似度和右相似度。

1.2 基于語義依存關系的詞相似度

在漢語的基本句型中，絕大多數(shù)句子的中心語是由動詞(短語)擔當?shù)模挥猩贁?shù)句子其中心語是由形容詞或體詞擔當?shù)?。同樣，在漢語的基本句型中，絕大多數(shù)句子的主語和賓語都是由名詞(短語)擔當?shù)?，只有少?shù)句子其主語和賓語由形容詞或動詞(短語)擔當。由于句子的中心語支配著句子中的其他成分(主語、賓語、狀語、補語)，所以，有必要對動詞、名詞和形容詞等各種詞的語義知識進行分析并加以分類，進而能從中總結出中心語與各被支配成分之間的語義關系。

動詞對名詞類別的選擇決定了什么類的名詞能添入什么樣的槽內，稱為動詞對名詞的制約選擇。原則上，動詞的概念定義決定了動詞的制約選擇。例如，依據作用動詞的概念定義，動詞的施事必然是能發(fā)出使感官直接感受到具體活動的義類名詞，其受事則必然是能接受這種活動的義類名詞。其余類推。

綜上所述，根據語義依存關系和語法特性對詞進行分類很為必要。當然，這些分類可以由語言學家依據語言知識進行，但利用統(tǒng)計模型，結合語言學知識對詞自動聚類的方法可能更可取。

設w1和w2是具有依存關系rel的詞對，用三元組(w1, rel, w2)表示詞對和它們之間的依存關系，則詞對(w1, w2)在依存關系rel下的互信息定義為：

這里計算要用到的概率使用極大似然估計(Maximum likeihood estimation)的方法統(tǒng)計：

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

定義1 詞對w1和w2在依存關系rel下的相似度定義為：

定義2 詞對w1和w2之間的相似度則定義為：

1.3 聚類算法

整個算法的流程如下：(1) 計算詞對之間的相似度；(2) 初始化，詞表中的每個詞各代表一類，共 N類(N為詞表中詞的數(shù)量)；(3) 找出具有最大相似度的2個詞類，將這2個詞類合并成1個新的詞類；(4) 計算剛合并詞類與其他詞類的相似度；(5) 檢查是否達到結束條件(詞類之間最大相似度小于某個預先決定的門檻值，或詞類的數(shù)目達到要求)，若是，則程序結束；否則，轉(3)。

2 基于依存關系和聚類的句法分析模型

2.1 中心詞驅動模型的基本原理

中心詞驅動模型是最具有代表性的詞匯化模型。為了發(fā)揮詞匯信息的作用，中心詞驅動模型為文法規(guī)則中的每一個非終結符(none terminal)都引入核心詞/詞性信息。由于引入詞匯信息，將不可避免地出現(xiàn)嚴重的稀疏問題。為了緩解這個問題，中心詞驅動模型把每一條文法規(guī)則的右手側分解為三大部分：1個中心成分；若干個在中心左邊的修飾成分；若干個在中心右邊的修飾成分?？梢詫懗扇缦滦问剑?/p>

其中：P為非終結符；H表示中心成分；Li表示左邊修飾成分；Ri表示右邊修飾成分；Hw，lw和rw均為成分的核心詞；ht，lt和rt分別為它們的詞性。進一步假設：首先由P產生核心成分H，然后，以H為中心分別獨立地產生左、右兩邊的所有修飾成分。這樣，形如(11)式的文法規(guī)則的概率為：

其中：Lm+1和Rn+1分別為左、右兩邊的停止符號。

2.2 基于多個依存關系和聚類的句法分析模型

模型在進行概率計算時采取自上而下分層、自左至右的算法。設)(hΦ表示當前核心詞h所依賴的上層核心詞。每一條文法規(guī)則寫成如下形式：

形如式(13)的文法規(guī)則的概率為：

其中：Lm+1和Rn+1分別為左、右兩邊的停止符號。式

由于引入詞匯信息，不可避免地將出現(xiàn)嚴重的數(shù)據稀疏問題，為了避免數(shù)據稀疏問題，可用基于類的模型代替基于詞的模型。設 C′(w)和 C(w)分別表示 w基于鄰接關系和語義依存關系的聚類，則(16)式中的概率為：

其中：0＜iwλ＜1。

句子Astronomers saw stars with telescopes具有2種含義，因此，具有2棵不同的句法樹圖(如圖1和圖2 所示)。

2棵句法分析樹和它們對應的驅動的規(guī)則如下：

圖1 句子分析樹1Fig.1 Parse tree Ⅰ of sentence

圖2 句子分析樹2Fig.2 Parse tree Ⅱ of sentence

其中，規(guī)則(18e)和(19e)對應的概率分別為：

與Collins的頭驅動句法分析模型相比較，通過概率(20)和(21)的計算，就能選出正確的句法分析樹。

3 實驗結果

本文的實驗在賓州中文樹庫 Chinese Treebank(CTB)5.0上進行。CTB是由語言數(shù)據聯(lián)盟(LDC)公開發(fā)布的一個語料庫，為漢語句法分析研究提供了一個公共的訓練、測試平臺。該樹庫包含了507 222個詞，824 983個漢字，18 782個句子，有890個數(shù)據文件。將文件301～325(353個句子，6 776個詞) 作為調試集，將文件271～300(348個句子，7 980個詞)作為測試集，其余文件作為訓練集。本文的所有實驗中，模型的參數(shù)都是從訓練集中采用極大似然法估計出來的。

測試結果采取常用的3個評測指標即準確率P、召回率R和綜合指標F體現(xiàn)。精確率(Precision)用來衡量句法分析系統(tǒng)所分析的所有成分中正確成分的比例；召回率(Recall)用來衡量句法分析系統(tǒng)分析出的所有正確成分在實際成分中的比例；綜合指標F=(P×R ×2)/(P+R)。

實驗中采用的句法分析Baseline系統(tǒng)是Bikel基于Collins模型實現(xiàn)的DBParser。Baseline系統(tǒng)和改進模型的句法分析實驗結果見表1。

表1 句法分析實驗結果Table 1 Experimental results of language parsing

從表1可以看出：由于在詞的聚類、規(guī)則的分解及概率計算中，多層次地利用了語法、語義依存關系等語言知識，改進模型的準確率 P、召回率 R、綜合指標F與Collins的頭驅動句法分析模型的相比明顯提高。

4 結論

(1) 語言特征知識的應用對統(tǒng)計句法分析有很大影響，表明可從語言學角度尋找更多的特征知識。

(2) 依存語法分析句子的方式是通過分析句子成分間的語法、語義依存關系，建立以句子成分為節(jié)點的依存語法樹，以此表達句子的結構。所以，首先要確定依存語法中句子成分的種類和成分之間的依存關系類型。

(3) 利用語義、語法等語言知識，建立了一種基于依存關系的句法分析統(tǒng)計模型，概率上下文無關語法中由概率的上下文無關性假設和祖先結點無關性假設引起的問題在該模型中得到有效解決。與 Collins的頭驅動句法分析模型相比較，由于改進模型在詞的聚類、規(guī)則的分解及概率計算中，多層次地利用了語法、語義依存關系等語言知識，其性能明顯提高。

(4) 在頭驅動的句法分析模型中，解決數(shù)據稀疏問題是提高句法分析性能的關鍵。利用依存關系、互信息對詞聚類，數(shù)據稀疏問題得到較好解決。

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

[2] 鐘義信. 關于“信息—知識—智能轉換規(guī)律”的研究[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.