數據驅動的依存句法分析方法研究

李正華　李渝勤　劉挺　車萬翔

1依存句法分析的定義

句法分析任務是對文本進行分析，將輸入句子從序列形式變為樹狀結構，從而刻畫句子內部詞語之間的組合或修飾關系。這是自然語言處理領域的核心研究課題，已經廣泛應用到其它自然語言處理任務中，如機器翻譯、自動問答、信息抽取等。和其他句法分析形式如短語結構句法分析相比，依存句法分析具有形式簡單、易于標注、便于學習、分析效率更高等優點[1，2]。另外，依存句法描述詞和詞之間的關系，因此更適合于表達非連續的、遠距離的結構，這對于一些語序相對自由的西方語言非常重要。依存語法歷史悠久，最早可能追溯到公元前幾世紀Panini提出的梵文語法。依存語法存在一個共同的基本假設：句法結構本質上包含詞和詞之間的關系。這種關系稱為依存關系（Dependency Relations）。一個依存關系連接兩個詞，分別是核心詞（Head）和修飾詞（Dependent）。依存關系可以細分為不同的類型，表示兩個詞之間的句法關系（Dependency Relation Types）。目前，依存語法標注體系已經為自然語言處理領域的許多專家和學者所采用，并應用于不同語言中，且對其不斷地發展和完善。研究者們提出并實現了多種不同的依存分析方法，達到了較好的準確率。近年來，依存句法分析多已廣泛用于統計機器翻譯[3]、自動問答[4]和信息抽取[5]等任務，并取得了良好的效果。

依存句法分析任務的輸入是一個已完成分詞的自然語言句子。形式化地，輸入句子可以表示為：x=W0W2…Wi…Wn，其中，wi表示輸入句子的第i個詞；W0表示一個偽詞，指向整個句子的核心詞，也就是根節點（ROOT）。圖1表示輸入句子“剛滿19歲的歐文現在效力利物浦隊。”的依存樹。

[JZ][HT5”H]圖1 依存樹示例[ST5”HZ][WT5”HZ][JZ]Fig.1[ST5”BZ] Example of a dependency parse

最一般地，一個依存句法樹由多個依存弧構成，表示為：d={（h，m，l）：0≤h≤n，0

依存句法分析的目標是給定輸入句子x，尋找分值（或概率）最大的依存樹d*，具體公式為：

因此，依存句法分析存在四個基本問題：

（1）如何定義Score（x，d），即采用哪種方式將依存樹的分值分解為一些子結構的分值。這是模型定義問題；

（2）采用哪些特征來表示每一部分子結構，即特征表示問題；

（3）如何獲取特征的權重，即模型訓練算法問題；

（4）給定模型參數，即已知特征的權重，如何搜索到分值最大的依存樹。這是解碼問題。

2依存句法分析的方法

數據驅動的依存句法分析方法主要有兩種主流的方法：基于圖（Graph-based）的分析方法和基于轉移（Transition-based）的分析方法。這兩種方法從不同的角度解決這個問題。CoNLL上的評測結果表明這兩種方法各有所長，并且存在一定的互補性[2，6]。下面對各類方法展開細致分析。

2.1基于圖的依存句法分析方法

基于圖的依存分析模型將依存句法分析問題看成從完全有向圖中尋找最大生成樹的問題。一棵依存樹的分值由構成依存樹的幾種子樹的分值累加得到。模型通過基于動態規劃的解碼算法從所有可能的依存樹中搜索出分值最高的依存樹。相關的研究工作主要包括：

（1）模型定義。根據依存樹分值中包含的子樹的復雜度，基于圖的依存分析模型可以簡單區分為一階、二階和三階模型。一階模型中，依存樹的分值由所有依存弧的分值累加得到，即依存弧之間相互獨立，互不影響[7]。二階模型中，依存樹的分值中融入了相鄰兄弟弧（Sibling）和祖孫弧（Parent-child-grandchild）的分值[8，9]。三階模型中，進一步增加了祖孫兄弟弧（Grandparent-parent-sibling）等三條依存弧構成的子樹信息[10]。

（2）特征表示。在上述模型定義的基礎上，研究人員也提出了相應的一階、二階、三階子樹特征[7-10]。每種子樹特征考慮句子中的詞語和詞性信息、依存弧的方向和距離信息等。隨著高階子樹特征的使用，依存句法分析模型的準確率也有較大幅度的提高。

（3）訓練算法。基于圖的依存分析方法通常采用在線訓練算法（Online Training），如平均感知器算法（Averaged Perceptron）[11]、被動進取算法（Passive-Aggressive）[12]和Margin Infused Relaxed算法（MIRA） [13]。在線學習算法以迭代的方式訓練特征的權重。一次迭代中遍歷整個訓練數據集合，每次根據一個訓練實例的分析結果對當前的權重向量進行調整。

（4）解碼算法。一階模型對應的解碼算法為Eisner算法[14]。Eisner算法的本質是動態規劃，不斷合并相鄰子串的分析結果，直到得到整個句子的結果，其時間復雜度為O（n3）。進而，McDonald和Pereira （2006）對Eisner算法進行擴展，增加了表示相鄰兄弟節點的數據類型，時間復雜度仍為O（n3）。Carreras （2007）同樣對Eisner算法進行擴展，得到面向二階模型的基于動態規劃的解碼算法，時間復雜度為O（n4）。Koo和Collins （2010）提出了面向三階模型的解碼算法，時間復雜度為O（n4）。一些研究者提出采用基于柱搜索的解碼算法，允許模型方便地融入更高階的解碼算法，同時保證較低的時間復雜度[15，16]。

2.2基于轉移的依存句法分析方法

基于轉移的依存分析模型將依存樹的搜索過程建模為一個動作序列，將依存分析問題轉化為尋找最優動作序列的問題。模型通過貪心搜索或者柱搜索的方式找到近似最優的依存樹。其優點在于可以充分利用已形成的子樹信息，從而形成豐富的特征，以指導模型決策下一個動作。相關的研究工作主要包括：

（1）模型定義。基于轉移的依存句法分析方法提出早期，研究者們使用局部分類器（如最大熵分類器）決定下一個動作，選擇概率最大的動作[17，18]。這樣，一個依存樹的概率由其對應的動作序列中每一個動作的概率累乘得到。近年來，研究者們采用線性全局模型來決定下一個動作，一個依存樹的分值為對應動作序列中每一個動作的分值的累加[19-21]。

（2）特征表示。基于轉移的依存句法分析方法的優勢在于可以充分使用已構成的子樹信息。Zhang和Nivre （2011）在前人工作的基礎上，提出了豐富的特征集合，如三階子樹特征，詞的配價信息等[21]。

（3）訓練算法。早期，研究者們在訓練語料上訓練出一個局部分類器，在解碼過程中重復使用，決定下一個動作。通常采用的分類器有基于記憶的分類器、支持向量機等。近年研究發現采用全局線性模型可以提高句法分析的準確率，通常采用平均感知器在線訓練算法。

（4）解碼算法。其任務是找到一個概率或分值最大的動作序列。早期采用貪心解碼算法，即每一步都根據當前狀態，選擇并執行概率最大的動作，進入到下一個狀態。如此反復直至達到接收狀態，形成一棵合法的依存樹[17，18]。進而，研究者們提出使用柱搜索的解碼方式擴大搜索空間，即同時保留多個分值最高的狀態，直到搜索結束時選擇最優的動作路徑[22，19]。Huang和Sagae （2010）提出在柱搜索中加入動態規劃，通過合并等價狀態進一步擴大搜索空間[20]。隨著搜索空間的增大，依存句法分析的準確率有顯著提高。

2.3模型融合的方法

基于圖的方法和基于轉移的方法從不同的角度解決問題，各有優勢。基于圖的模型進行全局搜索但只能利用有限的子樹特征，而基于轉移的模型搜索空間有限但可以充分利用已構成的子樹信息構成豐富的特征。McDonald和Nivre （2011）通過詳細比較發現，這兩種方法存在不同的錯誤分布。因此，研究者們使用不同的方法融合兩種模型的優勢，常見的方法有：stacked learning [2，23]；對多個模型的結果加權后重新解碼[24，25]；從訓練語料中多次抽樣訓練多個模型（Bagging）[26，27]。

2.4詞性標注和依存句法分析聯合模型

依存句法分析模型中，詞性是非常重要且有效的特征。如果只使用詞語特征，會導致嚴重的數據稀疏問題。自然語言處理中，詞性標注和依存句法分析這兩個問題通常被當成兩個獨立的任務，以級聯的方式實現。即對于一個輸入句子，假定其分詞結果已知，先對句子進行詞性標注，然后在詞性標注結果的基礎上進行依存句法分析。這種級聯的方法會導致錯誤蔓延。也就是說，詞性標注的錯誤會嚴重影響依存分析的準確率。由于漢語缺乏詞形變化信息（如英語中的詞后綴變化如-ing，-ed，-es，-ly等），因此漢語的詞性標注比其他語言如英語更具挑戰性。近年來，研究者們通過建立詞性標注和依存句法分析聯合模型，在同一個模型中解決這兩個緊密相關的任務，允許詞性信息和句法結構互相影響和幫助，取得了不錯的效果。一方面，聯合模型中，句法信息可以用來指導詞性標注，從而幫助解決一部分需要句法結構才能夠消解的詞性歧義。另一方面，更準確的詞性標注，也可以反過來幫助依存分析。Li等通過擴展基于圖的依存句法分析模型，首次提出漢語詞性標注和依存句法分析聯合模型[28]，并且提出了適用于聯合模型的訓練算法[29]，顯著提高了詞性標注和依存句法分析的準確率。進而，一些研究者們提出基于轉移的詞性標注和依存句法分析聯合模型[30，31]。Ma等（2012）嘗試了基于Easy-first的漢語詞性標注和依存句法分析聯合模型[32]。

2.5基于多樹庫融合的方法

對于統計的數據驅動的分析模型而言，標注數據的規模很大程度上影響著分析結果的準確率。依存句法分析是一種結構化分類問題，比二元分類和序列標注問題更具挑戰性，因此依存句法分析更容易受到數據稀疏問題的影響，樹庫規模對依存句法分析的準確率影響很大。然而，標注樹庫是一件艱巨的任務，通常需要耗費很大的人力和物力。目前的研究結果表明在一個樹庫上訓練出的句法分析的模型似乎很難進一步提高句法分析的準確率。然而，漢語存在多個樹庫。這些樹庫由不同的組織或機構標注，遵循不同的標注規范，面向不同的應用。盡管各個樹庫遵循不同的標注規范，但卻都是根據人們對漢語語法的理解而標注，因此包含很多共性的標注結構。同時，不一致的標注結果應該也是有規律可循的。所以，一些研究者們嘗試同時利用多個樹庫，幫助句法分析的準確率。李正華等（2008）曾嘗試統計和規則相結合的方法，將短語結構的源樹庫CTB轉化為符合CDT標注規范的依存結構，然后將轉化后的樹庫和CDT合并，提高訓練數據的規模，以提高依存句法分析準確率[33]。Niu等（2009）提出一種基于統計的樹庫轉化方法，將依存結構的CDT樹庫轉化為滿足CTB標注規范的短語結構樹庫，進而使用語料加權的方式增大訓練樹庫的規模，提高了短語結構句法分析的性能[34]。Li等（2012）提出一種基于準同步文法的多樹庫融合方法，不是直接將轉化后的樹庫作為額外的訓練數據，而是使用準同步文法特征增強依存句法分析模型，從而柔和地學習標注規范中規律性的不一致，提高依存句法分析的準確率[35]。

3依存句法分析面臨的挑戰

自從2006年開始，CoNLL國際評測一直關注依存句法分析，不但提供了多語言、高質量的樹庫，并通過對各種方法的比較分析，讓研究者們對依存分析問題的理解更加清晰，極大地促進了依存句法分析的發展。依存分析已經成為自然語言處理的一個熱點問題，方法也越來越成熟，并且在許多領域得到了應用。然而，目前依存句法分析還存在很多挑戰，這些挑戰也可能是未來依存分析發展的趨勢。具體分析如下：

（1）提高依存分析準確率。目前主流的兩種依存分析方法都存在一定的缺陷。基于圖的方法很難融入全局特征。而基于轉移的方法雖然原理上可以利用豐富的特征，但是實際使用的特征還是屬于局部特征，另外也還存在錯誤級聯的問題（柱搜索只能緩解這個問題）。融合不同依存分析模型的方法可以提高分析性能，但是提高幅度比較有限。研究可知，只有從新的角度理解這個問題本身，提出新的建模方法，或者應用新的機器學習方法，才有望大幅度提高依存分析性能。一些學者提出的利用未標注數據幫助依存分析模型是一個很好的思路，值得深入研究。

（2）提高依存分析效率。基于圖的依存分析方法融入高階特征可以提高性能，但是效率很低，無法適應實際應用的需求。在不明顯降低分析性能的前提下，如何提高依存分析效率也是一個很有實際價值的問題。

（3）領域移植問題。研究發現，當訓練數據領域與測試數據領域不相同時，即使差距不大，也會導致句法分析性能下降很大。以英語為例，從華爾街日報樹庫移植到Brown語料時，句法分析性能下降近8%。目前依存樹庫所覆蓋的領域、規模都很有限，而標注樹庫的代價很大。因此解決領域移植問題，對于依存分析的實際應用至關重要。

（4）語言相關的依存分析。目前最主流的兩種依存分析方法都是語言無關的，純粹依靠機器學習方法從數據中學習，加入人類知識只能限于特征選擇。然而，每種語言都有其特點。因此語言相關的依存分析研究，如針對每種語言的特點設計更有效的模型和算法，利用一些語言特有的資源等，也是很有必要的。近年來，國內學者已經在漢語依存句法分析上做出了很多成績，然而如何利用漢語的特點，提高漢語句法分析的準確率和效率，仍然是一個開放的問題。

4結束語

本文對數據驅動的依存句法分析方法進行深入調研和總結。主流的依存句法分析方法大致可以分為兩類。一類是基于圖的方法，另一類為基于轉移的方法。兩種方法從不同的角度解決依存句法分析問題，都取得了較好的效果。進而，研究者們提出各種融合方法，嘗試使得兩類方法揚長補短，各取優勢。另外，本文還探討了依存句法分析和底層詞性標注任務聯合求解，以及利用多個樹庫提高依存句法分析準確率的相關工作。最后，本文展望了依存句法分析的未來研究方向和可能的挑戰。