基于柱搜索的高階依存句法分析

李正華，車萬翔，劉 挺

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

1 引言

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

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

2 相關工作

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

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

3 基于圖的依存分析方法

3.1 依存分析模型

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

(1)

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

3.2 解碼算法

3.2.1 依存關系標注策略

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

(2)

(3)

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

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

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的右子孫節點，但是不包括wt的右子孫節點。

解碼算法中包括兩類操作。第一是將兩個完整span合并為一個不完整span，如圖1所示。第二類操作將一個完整span和一個不完整span合并為一個完整span，如圖2所示。圖1和圖2中的操作得到新的span都是以最左邊的詞作為核心節點。得到以最右邊詞作為核心節點的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的分值由三部分構成，如公式(7～9)所示。第三部分表示由r的右側兒子節點對應的祖孫特征貢獻的分值，包括了所有t右側兒子節點對應的祖孫特征。而Carreras的高階模型中僅考慮t最遠的兒子節點，此處指tck。

(7)

(8)

(9)

3.2.3 基于柱搜索的解碼算法

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

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個最優的span，如C[s][t][icp]保存了sps→|t類型的K個最優的span。算法第6行的含義是，遍歷s≤r

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

4 實驗

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

4.1 含有交叉弧語言的處理

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

4.2 特征集合

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

4.3 實驗結果及分析

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

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

表1 本文擴展模型與Carreras模型在develop數據集上的對比

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

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

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

5 結論及下一步工作

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

下一步工作包括：細致的特征選擇和參數優化，從理論和實驗上分析對比擴展模型和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.