基于詞聚類(lèi)的依存句法分析

袁里馳

(1. 江西財(cái)經(jīng)大學(xué) 信息學(xué)院，江西 南昌，330013；2. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙，410083)

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

1 基于詞相似度的分層聚類(lèi)算法

1.1 基于鄰接關(guān)系的詞相似度

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

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

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

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

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

基于詞相似度，詞類(lèi)C1和C2之間的相似度定義為：

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

1.2 基于語(yǔ)義依存關(guān)系的詞相似度

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

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

綜上所述，根據(jù)語(yǔ)義依存關(guān)系和語(yǔ)法特性對(duì)詞進(jìn)行分類(lèi)很為必要。當(dāng)然，這些分類(lèi)可以由語(yǔ)言學(xué)家依據(jù)語(yǔ)言知識(shí)進(jìn)行，但利用統(tǒng)計(jì)模型，結(jié)合語(yǔ)言學(xué)知識(shí)對(duì)詞自動(dòng)聚類(lèi)的方法可能更可取。

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

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

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

定義1 詞對(duì)w1和w2在依存關(guān)系rel下的相似度定義為：

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

1.3 聚類(lèi)算法

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

2 基于依存關(guān)系和聚類(lèi)的句法分析模型

2.1 中心詞驅(qū)動(dòng)模型的基本原理

中心詞驅(qū)動(dòng)模型是最具有代表性的詞匯化模型。為了發(fā)揮詞匯信息的作用，中心詞驅(qū)動(dòng)模型為文法規(guī)則中的每一個(gè)非終結(jié)符(none terminal)都引入核心詞/詞性信息。由于引入詞匯信息，將不可避免地出現(xiàn)嚴(yán)重的稀疏問(wèn)題。為了緩解這個(gè)問(wèn)題，中心詞驅(qū)動(dòng)模型把每一條文法規(guī)則的右手側(cè)分解為三大部分：1個(gè)中心成分；若干個(gè)在中心左邊的修飾成分；若干個(gè)在中心右邊的修飾成分。可以寫(xiě)成如下形式：

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

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

2.2 基于多個(gè)依存關(guān)系和聚類(lèi)的句法分析模型

模型在進(jìn)行概率計(jì)算時(shí)采取自上而下分層、自左至右的算法。設(shè))(hΦ表示當(dāng)前核心詞h所依賴(lài)的上層核心詞。每一條文法規(guī)則寫(xiě)成如下形式：

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

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

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

其中：0＜iwλ＜1。

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

2棵句法分析樹(shù)和它們對(duì)應(yīng)的驅(qū)動(dòng)的規(guī)則如下：

圖1 句子分析樹(shù)1Fig.1 Parse tree Ⅰ of sentence

圖2 句子分析樹(shù)2Fig.2 Parse tree Ⅱ of sentence

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

與Collins的頭驅(qū)動(dòng)句法分析模型相比較，通過(guò)概率(20)和(21)的計(jì)算，就能選出正確的句法分析樹(shù)。

3 實(shí)驗(yàn)結(jié)果

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

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

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

表1 句法分析實(shí)驗(yàn)結(jié)果Table 1 Experimental results of language parsing

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

4 結(jié)論

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

(2) 依存語(yǔ)法分析句子的方式是通過(guò)分析句子成分間的語(yǔ)法、語(yǔ)義依存關(guān)系，建立以句子成分為節(jié)點(diǎn)的依存語(yǔ)法樹(shù)，以此表達(dá)句子的結(jié)構(gòu)。所以，首先要確定依存語(yǔ)法中句子成分的種類(lèi)和成分之間的依存關(guān)系類(lèi)型。

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

(4) 在頭驅(qū)動(dòng)的句法分析模型中，解決數(shù)據(jù)稀疏問(wèn)題是提高句法分析性能的關(guān)鍵。利用依存關(guān)系、互信息對(duì)詞聚類(lèi)，數(shù)據(jù)稀疏問(wèn)題得到較好解決。

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

[2] 鐘義信. 關(guān)于“信息—知識(shí)—智能轉(zhuǎn)換規(guī)律”的研究[J]. 電子學(xué)報(bào), 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] 趙軍, 黃昌寧. 漢語(yǔ)基本名詞短語(yǔ)結(jié)構(gòu)分析模型[J]. 計(jì)算機(jī)學(xué)報(bào), 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] 劉水, 李生, 趙鐵軍, 等. 頭驅(qū)動(dòng)句法分析中的直接插值平滑算法[J]. 軟件學(xué)報(bào), 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] 李正華, 車(chē)萬(wàn)翔, 劉挺. 基于柱搜索的高階依存句法分析[J].中文信息學(xué)報(bào), 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ìn)的隱馬爾科夫模型的語(yǔ)音識(shí)別方法[J]. 中南大學(xué)學(xué)報(bào): 自然科學(xué)版, 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.