周惠巍，黃德根，高 潔，楊元生

(大連理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，遼寧 大連 116024)

1 引言

依存關(guān)系解析是句法分析的一個重要方法，是自然語言處理的一個重要任務(wù)，近年來引起了人們的廣泛興趣。依存關(guān)系可以明確地表明中心詞之間的句法依存關(guān)系，并能方便地轉(zhuǎn)化為語義依存描述。英文依存關(guān)系解析[1-2]與日語依存關(guān)系解析[3]已經(jīng)取得了較好的研究成果。中文與英文等其他語言有著明顯區(qū)別，中文沒有嚴格意義上的形態(tài)變化，不同詞類之間的界限不十分明顯，這使得中文依存關(guān)系解析變得更為困難。

大規(guī)模語料庫的構(gòu)建，使得人們可以使用數(shù)據(jù)驅(qū)動的方法構(gòu)建依存關(guān)系解析器。數(shù)據(jù)驅(qū)動依存關(guān)系解析方法可以分為兩類：最大生成樹解析方法和決策式解析方法。最大生成樹解析方法將句子中的詞看作圖的頂點，將詞間依存關(guān)系連線看作圖的有向邊。機器學(xué)習獲得依存關(guān)系概率(有向邊權(quán)重)函數(shù)，基于概率函數(shù)計算有向邊的權(quán)重。從而將依存關(guān)系解析問題轉(zhuǎn)換為在完全有向圖中搜索最大生成樹(MST)問題。Eisner將最大生成樹應(yīng)用于英語等非交叉結(jié)構(gòu)語言的依存關(guān)系解析(O(n3))[4]，McDonald使用Chu-Liu-Edmonds最大生成樹解析算法[5]解析捷克語等交叉結(jié)構(gòu)語言的依存關(guān)系(O(n2))[6]。辛霄將MST算法應(yīng)用于中文依存關(guān)系解析，取得了很好的解析效果[7]。劉挺基于詞匯支配度構(gòu)建了漢語依存分析模型，找出一棵概率最大的依存樹[8]。決策式解析方法有效地利用了句子的中間解析結(jié)果特征，從一個解析狀態(tài)轉(zhuǎn)移至下一個解析狀態(tài)。解析采用貪婪算法，每一步轉(zhuǎn)移都尋求局部最優(yōu)轉(zhuǎn)移狀態(tài)，直至解析結(jié)束。代表性的決策式解析方法有面向英語的Nivre算法[1]、Yamada算法[2]，面向日語的組塊逐步應(yīng)用算法[3]。Cheng將Nivre算法[1]和Yamada算法[2]應(yīng)用于中文依存關(guān)系解析，基于最大熵和支持向量機(SVMs)進行確定性依存關(guān)系解析[9]。并使用全局特征和根節(jié)點解析器提高解析性能[10]。Xu基于SVMs構(gòu)建了中文短語依存關(guān)系解析器[11]。段湘煜提出了兩種模型對句法分析動作進行建模避免了原決策式依存分析方法的貪婪性[12]。Cheng的研究表明，基于SVMs的Nivre算法[1]更符合中文的語法特點[9]。

最大生成樹解析方法和決策式解析方法差別很大，本質(zhì)上是對立和互補的。最大生成樹解析方法采用全句的依存樹進行訓(xùn)練，解析時使用最大生成樹搜索整句的最優(yōu)依存樹，因此具有全局性和完備性。但是，因為不到最大生成樹搜索完畢，無法獲得任何中間解析結(jié)果，所以無法將解析的中間結(jié)果應(yīng)用于后續(xù)解析。而決策式解析方法基于狀態(tài)轉(zhuǎn)移過程進行訓(xùn)練，解析時搜索局部最優(yōu)轉(zhuǎn)移狀態(tài)，直至整句解析結(jié)束，因此具有局部性和貪婪性。但是，可以將句子解析的中間結(jié)果用于后續(xù)解析。兩種模型均被廣泛用于各種語言，取得了較高的依存關(guān)系正確率。Nivre和McDonald基于其互補關(guān)系[13]提出在訓(xùn)練時結(jié)合兩種模型的方法，將一種模型的解析結(jié)果作為指導(dǎo)特征引入另一種模型[14]。當兩種模型的解析正確率相差不大時，結(jié)合后的模型顯著地提高了原基本模型的依存關(guān)系正確率。

本文提出解析時結(jié)合兩種模型的方法?；贜ivre模型的解析結(jié)果和依存度(依存關(guān)系概率)，修正MST模型有向邊的權(quán)重，再基于Chu-Liu-Edmonds最大生成樹解析算法[6]搜索得到該句的依存樹。既有效地利用了Nivre解析模型的中間解析結(jié)果特征，又使用了具有全局性的最大生成樹搜索算法，避免了因為決策式解析算法貪婪性而引起的解析錯誤。

2 最大生成樹解析算法和決策式解析算法

最大生成樹解析算法將一個句子Sen={w1,w2,…,wn}的依存關(guān)系樹表示為一個有向圖T=(V,A)。其中V={0, 1,2,…,n}表示頂點集合(用詞在句子中的序號表示該詞)，0為虛擬根節(jié)點；A?[0:n]×[1:n]表示依存關(guān)系連線。若依存樹中有一條由頂點i指向頂點j的有向連線，則一對頂點i,j∈V間就有一條有向邊(i,j)∈A，j≠0。

最大生成樹解析算法基于訓(xùn)練語料通過機器學(xué)習方法獲得有向邊權(quán)重的定義函數(shù)score(i,j,y)，即j依存于i的概率。其中y為依存關(guān)系類型，本文只解析是否存在依存關(guān)系，此處y=1。一棵依存關(guān)系樹的權(quán)重即為這棵樹中有向邊權(quán)重的總和。這樣，依存關(guān)系解析問題轉(zhuǎn)變?yōu)樵谕耆邢驁DG=(V,E)中搜索最大生成樹問題：

(1)

其中E?[0∶n]×[1∶n]表示頂點間的全部有向連線，依存關(guān)系連線集合A為E的子集A?E?？紤]解析效率，本文基于Chu-Liu-Edmonds算法(O(n2))搜索最大生成樹。

將支持向量機(SVMs)用于計算MST解析模型中有向圖各邊依存概率。sigmoid函數(shù)可以將SVMs輸出的距離函數(shù)較好地近似為概率函數(shù)[15]。本文基于Chu-Liu-Edmonds算法搜索最大生成樹。解析兩個詞(i,j)依存關(guān)系的具體特征見表1。

表1 MST算法的特征向量

在Nivre算法中，解析器可以表示成一個三元組。其中S和I是堆棧，I中是待解析的輸入序列。A是一個集合，存放在解析過程中確定下來的依存關(guān)系項。假設(shè)給定一個輸入序列Sen，解析器首先被初始化成。解析器解析棧S的棧頂元素t和棧I的棧頂元素n的依存關(guān)系，然后采取相應(yīng)的動作，操作棧中的元素移動，算法迭代進行直至棧I為空。此時，解析器停止迭代，輸出集合A中的依存關(guān)系序列。Nivre算法一共定義了四個操作。

(1) Right。在當前三元組中，假如存在依存關(guān)系t→n，即t依存于n，則在集合A中添加項(t→n)，同時彈出S中的棧頂元素t，于是三元組變?yōu)?S,n|I,A∪{(t→n)}>。

(2) Left。在當前三元組中，假如存在依存關(guān)系n→t，則在集合A中添加項(n→t)，同時把元素n壓入棧S中，于是三元組變?yōu)?n|t|S,I,A∪{(n→t)}>。

如果n與t不存在依存關(guān)系，改進的Nivre算法對Reduce操作和Shift操作做了明確的定義。

(3) Reduce。假如兩棧頂元素n與t不存在依存關(guān)系，t有父親節(jié)點在其左側(cè)，并且該父親節(jié)點與n存在依存關(guān)系，解析器從棧S中彈出t，于是三元組變?yōu)?S,n|I,A>。

(4) Shift。當Right，Left，Reduce操作條件都不滿足時，將n壓入棧S中，三元組變?yōu)?n|t|S,I,A>。

基于SVMs構(gòu)建Nivre依存關(guān)系解析器。解析當前三元組的兩個棧頂元素(t,n)的依存關(guān)系時，選取表2所示特征。

表2 Nivre算法的特征向量

3 最大生成樹算法和決策式算法的結(jié)合

多分類器融合系統(tǒng)近年來受到越來越多的關(guān)注，并成為模式識別和自然語言處理等領(lǐng)域的研究熱點。將多個分類器的決策結(jié)果按一定規(guī)則融合在一起，可以得到比其中最優(yōu)分類器還要好的性能。按照分類器的輸出結(jié)果形式，可以將多分類器融合方法分為三個層次：抽象層(Abstract Level)、排序?qū)?Rank Level)和度量層(Measurement Level)[16]。抽象層也稱為符號層或決策層，每個分類器僅輸出該分類器所判斷輸出的類別標識；排序?qū)樱總€分類器按照待分類項屬于各類別的可能性大小輸出所有類別標識的排序；度量層，每個分類器的輸出是一個待分類項屬于各類別可能性的度量值。

MST解析模型和Nivre解析模型均為數(shù)據(jù)驅(qū)動模型，因此Nivre和McDonald提出一種在學(xué)習時進行結(jié)合的方法[14]。將其中一個模型的解析結(jié)果作為指導(dǎo)特征引入另一個模型，以此促進兩個模型的相互學(xué)習。Nivre和McDonald將一個模型稱為基本模型B，另一個稱為指導(dǎo)模型C?；谥笇?dǎo)模型C解析語料，然后將獲得的解析結(jié)果作為特征加入到基本模型B的訓(xùn)練中，學(xué)習獲得結(jié)合解析模型BC。這種結(jié)合方法僅利用了指導(dǎo)模型抽象層信息，簡單而且顯著提高了依存關(guān)系正確率。

提出在解析時融合最大生成樹算法和決策式算法的中文依存關(guān)系解析方法，利用一種模型(指導(dǎo)模型)的解析結(jié)果指導(dǎo)另一種模型(基本模型)，促進兩個模型的相互融合。結(jié)合時分別基于指導(dǎo)模型解析結(jié)果的抽象層信息和度量層信息，輔助基本模型進行中文依存關(guān)系解析。

3.1 基于指導(dǎo)模型抽象層信息的結(jié)合

基于指導(dǎo)模型抽象層信息的結(jié)合，以一種模型為基本模型，利用指導(dǎo)模型的解析結(jié)果修正基本模型的解析結(jié)果。

McDonald和Nivre基于13種語言的實驗表明，MST模型的解析正確率普遍高于Nivre模型，MST模型具有全局性[14]。我們以MST模型為基本模型，利用Nivre模型的解析結(jié)果修正MST模型完全有向圖的權(quán)重，再基于Chu-Liu-Edmonds算法搜索依存樹?；贜ivre模型的解析結(jié)果指導(dǎo)MST模型的結(jié)合方法僅利用了Nivre模型決策層的信息。每種算法均輸出1-best結(jié)果。

基于MST算法獲得MST依存關(guān)系樹；基于Nivre算法獲得Nivre依存關(guān)系樹。依據(jù)兩棵依存樹修正MST模型完全有向圖的權(quán)重score(i,j,y)∈R：

(1) 對于MST依存樹和Nivre依存樹中同時存在的邊，將MST模型完全有向圖的權(quán)重乘以一個權(quán)值a，獲得新的權(quán)重a·score(iMN,jMN,y)∈R。

(2) 對于在MST依存樹中存在、而在Nivre依存樹中不存在的邊，將MST模型完全有向圖的權(quán)重乘以一個權(quán)值b1，獲得新的權(quán)重b1·score(iM,jM,y)∈R。

(3) 對于在Nivre依存樹中存在、而在MST依存樹中不存在的邊，將MST模型完全有向圖的權(quán)重乘以一個權(quán)值b2，獲得新的權(quán)重b2·score(iN,jN,y)∈R。

3.2 基于指導(dǎo)模型度量層信息的結(jié)合

基于指導(dǎo)模型度量層信息的結(jié)合，以MST模型為基本模型，利用Nivre依存樹各邊的依存度修正基本模型的解析結(jié)果。

SVMs為二值分類器，而Nivre算法包含四個操作，為多值分類問題?？梢圆捎胮airwise法將二值分類器擴展為多值分類器。首先利用SVMs對(t,i)進行分類，將其分為Right、Left和不存在依存關(guān)系三類。再利用規(guī)則將不存在依存關(guān)系的情況分為Reduce操作和Shift操作。采用pairwise法需要構(gòu)建三個二值分類器，分別為{Left，Right}、{Right，不存在依存}和{Left，不存在依存}。最后，輸出獲票最多的類別。

當(t,i)存在依存關(guān)系，即解析結(jié)果為right和left操作時，本文選用分類器{Left，Right}輸出的距離，計算Nivre依存樹各邊的依存概率。同樣利用sigmoid函數(shù)將SVMs模型輸出的距離近似為依存關(guān)系概率值。

基于MST算法獲得MST依存關(guān)系樹；基于Nivre算法獲得Nivre依存關(guān)系樹。依據(jù)兩棵依存樹及Nivre 依存樹各邊的依存度pMN修正MST模型完全有向圖的權(quán)重score(i,j,y)∈R：

(1) 對于在MST依存樹中存在、而在Nivre依存樹中不存在的邊，將MST模型完全有向圖的權(quán)重乘以一個權(quán)值b，獲得新的權(quán)重b·score(iM,jM,y)∈R。

(2) 對于MST依存樹和Nivre依存樹中同時存在的邊，計算其在Nivre模型中的依存概率，并乘以一個權(quán)值a，添加到MST模型的完全有向圖中，獲得新的權(quán)重a·pMN+b·score(iMN,jMN,y)∈R。

4 實驗

4.1 實驗結(jié)果與評估

實驗采用賓州中文樹庫(Penn Chinese Treebank, CTB)5.0。由于該樹庫為短語結(jié)構(gòu)，沒有依存關(guān)系，我們首先基于中心子節(jié)點過濾表將短語結(jié)構(gòu)的賓州中文樹庫轉(zhuǎn)換為依存結(jié)構(gòu)樹庫。我們采用1～4 500句的語料做十折交叉驗證，語料包含118 703詞。因為很難制定逗號兩側(cè)的短語的依存規(guī)則，我們同Cheng一樣，將逗號和句號都作為句子的結(jié)束標記[10]。

表3顯示了四種模型的解析結(jié)果。實驗結(jié)果表明：在CTB語料庫上，MST模型的依存關(guān)系正確率遠遠高于改進的Nivre模型(2.5%)。結(jié)合模型NivreMST的依存關(guān)系正確率較基本模型(Nivre模型)提高了1.72%；而結(jié)合模型MSTNivre的依存關(guān)系正確率卻低于基本模型(MST模型)。由此可見，當指導(dǎo)模型的依存關(guān)系解析性能遠遠低于基本模型時，對基本模型沒有正確的指導(dǎo)作用。

表3 依存關(guān)系解析結(jié)果

表4 解析時基于指導(dǎo)模型抽象層信息結(jié)合的解析結(jié)果(a=1.2)

采用本文提出的解析時基于指導(dǎo)模型抽象層信息的結(jié)合方法，設(shè)權(quán)值a=1.2，調(diào)節(jié)權(quán)值b1、b2的比例關(guān)系，解析結(jié)果如表4所示。

表5 改變Nivre模型影響權(quán)值的解析結(jié)果

由表4的實驗數(shù)據(jù)可見，我們提出的解析時基于指導(dǎo)模型抽象層信息的結(jié)合方法好于文獻[14]學(xué)習時結(jié)合的解析效果。解析時結(jié)合的方法比學(xué)習時結(jié)合的方法獲得了更加穩(wěn)定的解析性能。同時發(fā)現(xiàn)，當b1和b2的比值為1∶1.2時，即a與b2的權(quán)值相同時，解析效果最好。可見，Nivre模型解析獲得的依存關(guān)系，無論其在MST模型解析結(jié)果中是否存在，影響權(quán)值一致時解析效果最好。

改變Nivre模型的影響權(quán)值，實驗結(jié)果如表5所示。通過實驗結(jié)果發(fā)現(xiàn)，當Nivre模型的影響權(quán)值為1.3時，結(jié)合模型的解析效果最好。

采用本文提出的基于指導(dǎo)模型度量層信息的結(jié)合方法，設(shè)權(quán)值b=1，調(diào)節(jié)權(quán)值a、b的比例關(guān)系，解析結(jié)果如表6所示。由解析結(jié)果可以看出，解析時有效利用指導(dǎo)模型度量層信息可以取得比僅利用指導(dǎo)模型抽象層信息更好的解析效果。其中，當a和b的比值為0.15∶1時，解析效果最好，依存關(guān)系正確率達到86.49%?？梢?，利用Nivre模型度量層信息能夠進一步提高結(jié)合系統(tǒng)的解析性能。

表6 解析時基于指導(dǎo)模型度量層信息結(jié)合的解析結(jié)果

圖1顯示了四種模型依存關(guān)系正確率和句子長度(句長間隔為2：1-2，3-4，等)的關(guān)系。

圖1 依存關(guān)系正確率與句子長度的關(guān)系

實驗結(jié)果表明：在短句子中MST模型和Nivre模型的解析性能相差不大。但是隨著句子長度的增大，Nivre模型的解析性能明顯低于MST模型，這主要是由于Nivre算法貪婪性解析錯誤逐步擴散引起的?；贜ivre模型抽象層信息的結(jié)合模型的解析性能好于Nivre模型和MST模型?；贜ivre模型度量層信息的結(jié)合模型的解析性能表現(xiàn)更優(yōu)。這表明，隨著句子長度的增大，解析時結(jié)合的方法不僅保留了MST算法的全局搜索優(yōu)勢，又有效地利用了Nivre算法的中間解析結(jié)果特征，使得其解析性能比MST模型有很明顯的提高。而且，利用Nivre模型度量層信息的結(jié)合方法比單純利用Nivre模型的抽象層信息取得了更好的解析性能。

4.2 與以往方法的比較

辛霄采用CoNLL 2008 共享任務(wù)語料，比較了決策式解析方法和MST解析方法。結(jié)果表明，MST算法取得了最好的解析效果，在WSJ測試語料庫上的依存關(guān)系正確率達到87.42%[7]。基于CTB語料，我們再現(xiàn)了MST算法，解析結(jié)果如表3所示。劉挺使用哈爾濱工業(yè)大學(xué)漢語依存樹庫，將樹庫中的40 000 句作為訓(xùn)練集，在4 000 句的測試集上，獲得了約74%的依存關(guān)系正確率[8]。Cheng采用Nivre算法，并使用全局特征和根節(jié)點解析器提高解析性能。實驗采用CTB語料庫，訓(xùn)練語料為377 408詞，測試語料為63 886詞。依存關(guān)系解析正確率達到86.18%，句子正確率達到61.33%[10]。Xu構(gòu)建了基于短語的中文依存關(guān)系解析器，采用CTB語料庫，訓(xùn)練語料為4 000句，任意另取100句作為測試語料，依存關(guān)系解析正確率為77.3%[11]。段湘煜基于動作建模的依存句法分析器優(yōu)于原始決策式分析器。實驗采用CTB語料庫，訓(xùn)練語料為434 936詞，測試語料為50 319詞，依存關(guān)系解析正確率達到84.05%[12]。McDonald和Nivre采用CoNLL-X共享任務(wù)語料庫，依存關(guān)系解析正確率達到88.43%[14]。我們基于CTB語料，再現(xiàn)了他們學(xué)習時結(jié)合的方法，解析結(jié)果見表3。

5 結(jié)論

本文利用MST算法和Nivre算法的互補關(guān)系，提出了解析時結(jié)合兩種模型的中文依存關(guān)系解析方法，分別基于Nivre模型解析結(jié)果的抽象層信息和度量層信息指導(dǎo)MST模型。實驗結(jié)果表明，基于Nivre模型抽象層信息的結(jié)合方法取得了86.14%的依存關(guān)系正確率，基于Nivre模型度量層信息的結(jié)合方法取得了86.49%的依存關(guān)系正確率。本文提出的兩種結(jié)合方法，均比單獨的每種算法以及學(xué)習時結(jié)合的方法具有更好的解析效果，并且基于Nivre模型度量層信息的結(jié)合方法比基于Nivre模型抽象層信息的結(jié)合方法取得了更好的解析性能。

下一步工作主要包括兩個方面：一方面是探索指導(dǎo)模型權(quán)重的自動設(shè)置方法，一種可行的方法是采用感知機算法，基于訓(xùn)練語料通過迭代，自動獲得指導(dǎo)模型的權(quán)重；另一方面是減小MST模型訓(xùn)練語料正負樣例的比例不均衡，提高MST模型的訓(xùn)練效率，可以通過采用其他機器學(xué)習方法或合理刪減負例的方法解決訓(xùn)練消耗問題。

[1] Joakim Nivre， Mario Scholz. Deterministic Dependency Parsing of English Text[C]//Proceedings of COLING'04, Geneva, Switzerland. 2004: 64-70.

[2] Hiroyasu Yamada， Yuji Matsumoto. Statistical dependency Analysis with Support Vector Machines[C]//Proceedings of the 8th International Workshop on Parsing Technologies, Nancy, France. 2003: 195-206.

[3] Taku Kuto， Yuji Matsumoto. Japanese dependency analysis using cascaded chunking[C]//Proceeding of CoNLL, Taipei, Taiwan, 2002: 63-69.

[4] Jason M. Eisner. Three new probabilistic models for dependency parsing: An exploration[C]//Proceedings of COLING, 1996: 340-345.

[5] Y.J. Chu， T.H. Liu. On the shortest arborescence of a directed graph [J]. Science Sinica, 1965, 14: 1396-1400.

[6] Ryan McDonald, Koby Crammer， Fernando Pereira. Online large-margin training of dependency parsers[C]//Proceedings of ACL, Ann Arbor, 2005：91-98.

[7] 辛霄,范士喜,王軒,等.基于最大熵的依存句法分析[J].中文信息學(xué)報，2009，23(2)：18-22.

[8] 劉挺,馬金山,李生.基于詞匯支配度的漢語依存分析模型[J].軟件學(xué)報,2006,17(9):1876-1883.

[9] Yuchang Cheng. Machine Learning-based Dependency Analyzer for Chinese[C]//Proceedings of the International Conference on Chinese Computing, Singapore. 2005：66-73.

[10] Yuchang Cheng, Masayuki Asahara， Yuji Matsumoto. Chinese deterministic dependency analyzer: Examining effects of global features and root node finder[C]//Proceedings of the Fourth SIGHAN Workshop on Chinese Language Processing, Juje, Korea, 2005：17-24.

[11] Yun Xu, Feng Zhang. Using SVM to construct a Chinese dependency parser [J]. Journal of Zhejiang University SCIENCE A, 2006, 7(2):199-203.

[12] 段湘煜,趙軍,徐波.基于動作建模的中文依存句法分析[J].中文信息學(xué)報，2007,21(5):31-35.

[13] Ryan McDonald， Joakim Nivre. Characterizing the errors of data-driven dependency parsing models[C]//Proceedings of EMNLP-CoNLL, 2007：122-131.

[14] Joakim Nivre， Ryan McDonald. Integrating Graph-Based and Transition-Based Dependency Parsers[C]//Proceedings of ACL-08: HLT, Columbus, Ohio, USA, 2008：950-958

[15] John C. Platt. Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods[M]. Advances in Large Margin Classifiers. MIT Press. 1999.

[16] 米愛中,郝紅衛(wèi),鄭雪峰,等. 一種自整定權(quán)值的多分類器融合方法[J].電子學(xué)報，2009,37(11):2604-2609.