李正華，車萬翔，劉 挺

(哈爾濱工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院 信息檢索研究中心,黑龍江 哈爾濱 150001)

1 引言

依存分析是針對給定的句子x=w1w2…wn，遵循某種依存語法體系，建立句子對應(yīng)的依存樹y。依存語法相對于短語結(jié)構(gòu)語法而言，其優(yōu)點在于：(1)形式簡潔，不增加額外的非終結(jié)標(biāo)記，易于理解。(2)側(cè)重于反映語義關(guān)系，可以很容易地和語義分析結(jié)合。(3)適合表示交叉關(guān)系，因此適用于大多數(shù)語言。(4)有利于實現(xiàn)線性時間的搜索算法。因此，依存句法分析受到國內(nèi)外學(xué)者廣泛的關(guān)注。CoNLL 2006、2007年連續(xù)兩年評測多語依存分析任務(wù)。CoNLL 2008評測英語依存語義分析任務(wù)。CoNLL 2009評測多語依存語義分析任務(wù)。這些評測任務(wù)的開展，也促進了依存分析的發(fā)展。

本文內(nèi)容組織為：第2章介紹依存分析相關(guān)工作；第3章介紹基于柱搜索的高階依存分析方法；第4章為實驗；第5章給出結(jié)論及進一步工作。

2 相關(guān)工作

目前的依存分析的主流方法有兩種，第一種是基于轉(zhuǎn)移的方法，第二種是基于圖的方法?；谵D(zhuǎn)移的方法將依存樹的構(gòu)建分解為一個動作序列，由分類器根據(jù)當(dāng)前狀態(tài)來決定下一個動作。Covington[1], Yamada[2], Nivre[3]等人采用了這種方法。

基于圖的方法將依存分析看成在有向圖中求最大生成樹的問題。對于輸入的句子x=w1w2…wn，可以構(gòu)建一個有向圖G=(V,E)。V={0,1,…,n}為節(jié)點集合，對應(yīng)每一個詞，0為增加的偽節(jié)點，用以表示依存樹的根節(jié)點。E={(i,j,l}|0≤i≤n,1≤j≤n,l∈L}為有向邊集合。其中L表示依存關(guān)系集合，(i,j,l)表示一條從i指向j的有向邊，依存關(guān)系為l。有向圖G中每兩個節(jié)點之間可以有多個同方向的但是不同依存關(guān)系的有向邊。依存分析的目標(biāo)是從圖G中找到一顆分值最大的依存樹。Eisner設(shè)計出了基于span的算法，使得上述搜索過程可以在O(n3)時間內(nèi)完成[4]。McDonald提出了一階依存分析模型，假設(shè)依存樹中的弧相互獨立，依存樹的分值為所有弧分值的累加[5]。進而，McDonald又將一階模型擴展為二階模型，假設(shè)依存樹中一條弧的分值與它相鄰的兄弟弧(核心節(jié)點與其前一個兒子節(jié)點構(gòu)成的弧)相關(guān)[6]。Carreras擴展了二階模型，提出高階模型。高階模型假設(shè)一條弧的分值與其最左和最右的孫子弧(非核心節(jié)點與其兒子節(jié)點構(gòu)成的弧)相關(guān)[7]。

3 基于圖的依存分析方法

3.1 依存分析模型

本文擴展了Carreras的高階模型，假設(shè)一條弧的分值與其所有的孫子弧相關(guān)。模型如公式(1)所示。

(1)

S(x,y)表示輸入句子x對應(yīng)的依存樹y的分值，由三部分構(gòu)成：每一條依存弧的分值Ssingle(h,c,l)，兄弟節(jié)點互相影響的分值Ssibling(h,ci,ci+1)，以及祖孫節(jié)點互相影響的分值Sgrand(h,c,gc,l)。第二部分中，ci和ci+1表示相鄰的兄弟節(jié)點，注意在計算兄弟之間互相影響的分值時，模型沒有考慮依存關(guān)系。

3.2 解碼算法

3.2.1 依存關(guān)系標(biāo)注策略

McDonald的方法在解碼之前，利用一元特征為任意一條弧確定了唯一的依存關(guān)系，并且在解碼過程中，直接使用一元特征對應(yīng)的分值。這種做法雖然比較簡單地解決了依存關(guān)系標(biāo)注的問題，但是由于沒有利用豐富的依存關(guān)系特征，因此很大程度上影響了依存關(guān)系準(zhǔn)確率。為此，本文首先利用一元特征，為每一條弧確定K1個可能的依存關(guān)系L1(.)；然后利用二元特征，對這K1個依存關(guān)系進行重排序，得到K2個可能的依存關(guān)系L2(.)，進一步縮小依存關(guān)系的數(shù)量(K2?K1<|L|)。L表示訓(xùn)練語料中出現(xiàn)的依存關(guān)系類型集合。最后，在解碼過程中每條弧僅使用選出的K2個依存關(guān)系。整個過程如公式(2～3)所示，其中funi(.)表示一元特征集合，fbi(.)表示二元特征集合。整個過程的時間復(fù)雜度為O(n2|L|logK1+n2K1logK2)。

(2)

(3)

3.2.2 基于span的基本操作及分值計算

在Eisner提出基于span的算法之前，基于圖的依存分析一般以組塊(Constituent)為基本單位。組塊表示輸入句子的一個片斷ws...wt(0≤s≤t≤n)對應(yīng)的子樹，即包括一個核心詞，片斷中其他詞都是這個核心詞的子孫節(jié)點。組塊中核心詞的位置是任意的，可以是片段中的任意一個詞wi(s≤i≤t)。Eisner算法以span作為解碼的基本單位。Span也表示輸入句子的一個片斷對應(yīng)的子樹。與組塊不同的是，span的核心詞必須位于片段首或尾。Span的這種特性使得解碼算法獨立的確定一個詞左邊的修飾成分和右邊的修飾成分，從而降低算法的復(fù)雜度。

Span可以分為兩種，完整span和不完整span。完整span中除了核心詞外其他詞的所有修飾成分全部找到，使用←或→表示。不完整span除了核心詞外，另外一個位于片段首或尾的詞的修飾成分也沒有全部找到，使用|←或→|表示。圖1中包含了三個span，分別記作sps→r，spr+1←t和sps→|t。其中sps→r和spr+1←t表示了兩個完整span；而sps→|t表示一個不完整span。sps→r代表了以ws為核心詞的一顆子樹，其他詞ws+1,r都是ws的右修飾成分，并且sps→r包括了ws+1,r完整的修飾成分。spr+1←t則表示了以wt為核心詞的一顆子樹。sps→|t包括了ws的右子孫節(jié)點，但是不包括wt的右子孫節(jié)點。

解碼算法中包括兩類操作。第一是將兩個完整span合并為一個不完整span，如圖1所示。第二類操作將一個完整span和一個不完整span合并為一個完整span，如圖2所示。圖1和圖2中的操作得到新的span都是以最左邊的詞作為核心節(jié)點。得到以最右邊詞作為核心節(jié)點的span的操作是類似的。

圖1 兩個完整span合并為一個不完整span

圖2 一個完整span和一個不完整span合并為一個完整span

S(sps→|t)=S(sps→r)+S(spr+1←t)

+Sicp(s,r,t,l)

(4)

Sicp(s,r,t,l)=w·ficp(s,r,t,l)

(5)

ficp(s,r,t,l)=funi(s,t,l)∪fbi(s,t,l)∪fsib(s,sck,t)

(6)

圖2中sps→|r和spr→t合并為sps→t，這個操作不會增加弧。sps→t的分值由三部分構(gòu)成，如公式(7～9)所示。第三部分表示由r的右側(cè)兒子節(jié)點對應(yīng)的祖孫特征貢獻的分值，包括了所有t右側(cè)兒子節(jié)點對應(yīng)的祖孫特征。而Carreras的高階模型中僅考慮t最遠的兒子節(jié)點，此處指tck。

(7)

(8)

(9)

3.2.3 基于柱搜索的解碼算法

由于高階特征的引入，Eisner算法不再具有動態(tài)規(guī)劃算法要求的最優(yōu)子結(jié)構(gòu)特性。如圖2中的合并操作，sps→t的分值最大，并不意味著sps→|r和spr→t都分值最大，還取決于第三部分分值。而第三部分分值又和sps→|r與spr→t中包含的弧和依存關(guān)系相關(guān)。本文采用柱搜索的方法來獲得近似解。算法如下:

1 initialization:C[s][s][c]=0.0?0≤s≤n,c∈{cp,icp}# cp:complete; icp:incomplete

2 forj= 1..n

3 fors= 0..n

4t=s+j

5 ift>nthen break

10 end for

13 end for

線圖(chart)的每一個位置保留K個最優(yōu)的span，如C[s][t][icp]保存了sps→|t類型的K個最優(yōu)的span。算法第6行的含義是，遍歷s≤r

算法第6行和第7行的時間復(fù)雜度均為O(n2K2K2logK)，其中K2=|L2|。注意由于在獲取祖孫特征的時候，使用了所有的孫子節(jié)點，因此復(fù)雜度為O(n)。第8行和第9行復(fù)雜度為O(n2K2logK)。因此整個算法復(fù)雜度為O(n4K2K2logK)。由于K和K2一般很小且為常數(shù)，因此可以認(rèn)為整個算法復(fù)雜度是O(n4)。

4 實驗

在CoNLL 2009多語語義依存分析評測任務(wù)中，作者采取將依存分析和語義角色標(biāo)注級聯(lián)的策略。CoNLL 2009評測任務(wù)包括漢語、英語、日語、捷克語、德語、西班牙語、加泰羅尼亞語七種語言。其中英語、德語、捷克語還提供了跨領(lǐng)域(ood, out of domain)的測試語料，用以評價系統(tǒng)對不同領(lǐng)域語料的適應(yīng)能力。

4.1 含有交叉弧語言的處理

CoNLL 2009評測包含的七種語言中，捷克語、德語、英語都不同程度的含有交叉弧的依存樹。本文的模型和算法無法處理含有交叉弧的情況。對于這三種語言，作者使用了Nivre的pseudo-projective方法[8]，先將含有交叉弧的句子轉(zhuǎn)化為不含有交叉弧，用以訓(xùn)練本文的依存分析器。最后，將分析結(jié)果逆向轉(zhuǎn)化，恢復(fù)為含有交叉弧的依存樹。

4.2 特征集合

本文借鑒McDonald采用的一階和二階特征，以及Carreras采用的高階特征，對作者參加CoNLL 2008評測任務(wù)的系統(tǒng)使用的特征[9]進行了擴充。

4.3 實驗結(jié)果及分析

本文實驗的機器配置是2.5GHz Xeon CPU, 16G內(nèi)存。依存分析器內(nèi)存使用峰值為15G，訓(xùn)練時間最多約60個小時。由于CoNLL 2009年評測涉及語言比較多，并且本文的系統(tǒng)對內(nèi)存等資源要求很高，作者沒有進行細致的特征選擇和參數(shù)優(yōu)化。訓(xùn)練模型過程中，針對不同語言，參數(shù)設(shè)置為：依存關(guān)系數(shù)量K1=10,K2=2，最優(yōu)span數(shù)量K=10，迭代次數(shù)T=5～10。測試階段參數(shù)設(shè)置為：K1=20～50,K2=2～3，K=10。

本文將使用所有孫子節(jié)點構(gòu)成祖孫特征的擴展模型與Carreras的只使用最左和最右的孫子節(jié)點構(gòu)成祖孫特征的模型在開發(fā)數(shù)據(jù)集上作以對比，實驗結(jié)果如表1所示。其中LAS表示依存關(guān)系準(zhǔn)確率，UAS表示依存弧準(zhǔn)確率。擴展模型在加泰羅尼亞語和西班牙語上性能有明顯的提高，而在漢語、英語 (UAS)、捷克語 (UAS)上有明顯的下降，其他語言則影響不大。其原因還需要深入的實驗和分析。

表1 本文擴展模型與Carreras模型在develop數(shù)據(jù)集上的對比

另外，雖然擴展模型理論上時間復(fù)雜度更高，作者在實驗中發(fā)現(xiàn)，兩個模型的運行效率基本相當(dāng)，原因可能是解碼過程中，每個節(jié)點的兒子節(jié)點數(shù)目比較少，因此使用所有孫子節(jié)點不會產(chǎn)生很大的時間消耗。

作者參加了CoNLL 2009評測，七種語言上均使用擴展模型，評測結(jié)果如表2所示。在這次評測中，作者在聯(lián)合任務(wù)中總成績排名第一，依存分析總成績排名第三。表中還給出了本文的系統(tǒng)和前兩名系統(tǒng)的性能比較。其中帶*表示對應(yīng)項在整個評測中為第一名。在跨領(lǐng)域語料上測試時，依存分析性能下降比較大(4%～10%)，因此如何增強依存分析模型領(lǐng)域適應(yīng)性是一個很有意義的研究點。

表2 CoNLL 2009評測依存分析依存關(guān)系準(zhǔn)確率(LAS)比較) %

5 結(jié)論及下一步工作

本文提出了一種基于柱搜索，融合高階特征的依存分析方法。這種高階依存模型使用所有的孫子節(jié)點構(gòu)成祖孫特征，擴展了Carreras的只利用最左或者最右孫子節(jié)點的模型。實驗證明這種擴展能夠提高加泰羅尼亞語和西班牙語的性能，卻會導(dǎo)致漢語、英語 (UAS)、捷克語 (UAS)性能下降，對其他語言則影響不大。另外，不同于以前的依存關(guān)系策略，本文以較小的時間復(fù)雜度為代價，使用了豐富的依存關(guān)系特征，并且允許模型在解碼的過程中進行依存關(guān)系選擇。作者參加了CoNLL 2009年多語語義依存分析國際評測，語義分析和句法分析聯(lián)合任務(wù)總成績第一名，依存分析總成績第三名。

下一步工作包括：細致的特征選擇和參數(shù)優(yōu)化，從理論和實驗上分析對比擴展模型和Carreras的模型。

[1] Michael A. Covington. A fundamental algorithm for dependency parsing [C]//Proceedings of the 39th Annual ACM Southeast Conference,2001.

[2] Hiroyasu Yamada, Yuji Matsumoto. Statistical dependency analysis with support vector machines [C]//Proceedings of 8thInternational Workshop on Parsing Technologies. 2003:195-206.

[3] Joakim Nivre, Mario Scholz. Deterministic Dependency Parsing of English Text [C]//Proceedings of COLING. 2004:64-70.

[4] Jason Eisner. Bilexical grammars and a cubic-time probabilistic parser [C]//Proceedings of the International Workshop on Parsing Technologies, MIT. 1997: 54-65.

[5] Ryan McDonald, Koby Crammer and Fernando Pereira. Online Large-Margin Training of Dependency Parsers [C]//Association for Computational Linguistics (ACL). 2005.

[6] Ryan McDonald and Fernando Pereira. Online Learning of Approximate Dependency Parsing Algorithms [C]//European Association for Computational Linguistics (EACL). 2006.

[7] Xavier Carreras. Experiments with a high-order projective dependency parser [C]//Proceedings of the CoNLL 2007 Shared Task Session of EMNLP-CoNLL. 2007:957-961.

[8] Joakim Nivre and J. Nilsson. Pseudo-Projective Dependency Parsing [C]//Proc. of the 43rd Annual Meeting of the ACL. 2005: 99-106.

[9] Wanxiang Che, Zhenghua Li, Yuxuan Hu, Yongqiang Li, Bing Qin, Ting Liu, Sheng Li. A Cascaded Syntactic and Semantic Dependency Parsing System [C]//CoNLL 2008: Proceedings of the 12th Conference on Computational Natural Language Learning, 2008: 238-242.