依存句法分析方法綜述

楊振鵬

摘 要：近年來，自然語言處理發(fā)展迅速，依存句法分析作為自然語言處理的重要組成部分，成了句法分析研究的熱點問題。目前較為成熟的依存句法分析方法有4種：生成式句法分析模型、判別式句法分析模型、決策式句法分析模型和約束滿足句法分析模型。文章詳細介紹了4種句法分析模型的原理，并對模型算法進行了對比分析。

關鍵詞：依存句法分析；生成式句法分析模型；判別式句法分析模型；決策式句法分析模型；約束滿足句法分析模型

語法理論是任何一種句法分析的基礎?，F(xiàn)有的語法體系中，用兩個詞之間的依存關系來描述依存語法的語言結構。依存語法的結構將謂詞作為研究的中心，并且表層句法結構的條件及狀況由深層語義的結構來體現(xiàn)，謂詞的詞類由謂詞與體詞之間的同現(xiàn)關系來劃分。依存語法具有易于理解、便于詞性標注、形式簡潔清晰等優(yōu)勢，受到了許多學者的關注。目前，許多研究人員在自然語言處理領域中應用了依存語法，促進了依存句法分析方法的發(fā)展。

1 依存句法分析的研究現(xiàn)狀

1.1 英語依存句法分析現(xiàn)狀

短語結構的句法分析一直是英語的句法分析的主要工作，而依存句法的研究開展則相對滯后。Melchuk在1988年全面系統(tǒng)的研究了英語的依存語法理論，Eisner[1]在1997年最先提出了樹庫轉化的思想，依存樹庫通過短語樹庫轉化得到，并進行了相關的轉化實驗。Eisner在數(shù)據(jù)轉換時對含連詞的句子進行過濾，其余的句子使用規(guī)則進行自動轉換，得到了90.1%的依存正確率。

依存句法分析吸引了越來越多的研究者加入，他們對英語的依存體系進行了完善。在實踐方面，Yamada等[2]使用支持向量機的方法進行短語結構的轉換，主要是對Penn Treebank中的句子進行轉換，獲得了90.5%的正確率。在此基礎上，Nivre和McDonald進一步深入研究了英語的依存分析工作，促進了英語依存分析的發(fā)展。

近幾年，許多學者對聯(lián)合模型表現(xiàn)出了極大的興趣，并進行了相關聯(lián)合模型的研究。李正華等于2011年提出了漢語詞性標注與依存句法分析相結合的聯(lián)合模型，Jun等[3]等提出了分詞、詞性標注以及依存句法分析三者相結合的聯(lián)合模型。

1.2 漢語依存句法分析現(xiàn)狀

在漢語方面，最近幾年依存句法分析的工作逐漸受到關注。Zhou[4]很早就做過依存語法的相關研究，他根據(jù)制定的語法規(guī)則對句子進行分塊處理，找出那些關系固定的語塊，然后對整個句子進行依存分析。Ma等在漢語依存分析方面，利用無指導的方法做了有價值的研究。

隨著漢語應用的日益廣泛，國外的學者也開始了漢語依存分析的研究工作。Chen等分別在Chinese Penn Treebank（CTB）和CKIP樹庫上進行了依存分析的實驗。在基于CTB的實驗中，主要從特征和算法復雜度方面改進了Nivre算法，一方面擴大了全局特征，另一方面對算法進行優(yōu)化，在尋找根節(jié)點時，分別分析根節(jié)點兩側的句子，降低復雜度。實驗獲得了86.18%的依存關系正確率。在基于CKIP樹庫的實驗中，首先進行數(shù)庫的轉換，利用確定性搜索算法將短語結構樹庫自動轉化為依存結構樹庫。用CKIP樹庫中的部分數(shù)據(jù)作實驗數(shù)據(jù)，句子平均長度為5.7詞。根據(jù)篇章類型的不同分別進行測試，效果最好的是文學類，其正確率分別為：句子核心詞94%，整句71%，依存關系87%；效果最差的是新聞類，核心詞86.9%，整句50%，依存關系74%。

Jin等對Nivre和Yamada方法進行改進，新的移進—歸約算法采用雙階段方式進行漢語依存分析，第一階段的歸約由兩部分構成，一是歸約左邊的依存弧，二是歸約右邊的體詞性依存節(jié)點，第二階段則主要是對右邊的動詞性依存節(jié)點進行歸約。實驗時，先對CTB 4.0進行轉換，然后抽取轉換結果中部分句子作為實驗數(shù)據(jù)，依存正確率為84.52%。

2 主流的依存句法分析方法

目前主要的依存句法分析模型可大致歸為以下4類：生成式的句法分析模型、判別式的句法分析模型、決策式的句法分析模型和約束滿足的句法分析模型。

2.1 生成式依存句法分析模型

生成式模型將采用聯(lián)合概率score（x，y|θ）（其中，已知序列為x，依存分析結構為y，模型的參數(shù)為θ）生成一系列依存句法樹，并賦予其概率分值，然后采用相關搜索算法找到概率打分最高的分析結果作為最后輸出。在句法分析中，已知序列輸入的是句子；輸出的是依存結構樹T。生成式模型的最終目標是從訓練模型中獲取使聯(lián)合概率P（T，S）取得最大值的參數(shù)θ，得分最高的依存結構樹。為了便于計算聯(lián)合概率P（T，S），可以對句法分析問題作出不同程度的假設，這將有效減少數(shù)據(jù)稀疏問題。

生成式的句法分析與短語結構樹的分析方法關系密切，PCFG方法是生成式方法的基礎。起初，生成式的句法分析模型所采用的算法與由短語結構句法分析算法相似，它也采用全局搜索，生成多棵依存樹，每個句子對應一棵或多棵依存樹，最后系統(tǒng)輸出概率最高的那棵依存樹，算法正確率較高，但復雜度也很高，一般為O（n3）或（n5）。

生成式依存句法分析主要有以下3種模型。

（1）二元詞匯親和模型，該模型加入了詞匯信息，將詞性和詞形聯(lián)合。一個標記序列由馬爾柯夫過程產生，鏈接關系對詞匯是敏感的，每一對詞是否可以構成鏈接關系的決策依賴于詞匯信息，最終生成詞性、詞形和鏈接關系的聯(lián)合概率模型。

（2）選擇偏好模型，該模型加入了詞的選擇偏好信息，不再窮舉所有連接再根據(jù)約束進行剪裁，而是限制模型為每個詞只選擇一個父結點。

（3）遞歸生成模型，該模型中每個詞的左子結點和右子結點分別由各自的馬爾柯夫模型順次產生：左子結點的產生方向是自右向左，右子結點的產生方向是自左向右的。每一個子結點的生成建立在支配詞和它前一個子結點上，是自頂向下的遞歸生成式模型。

2.2 判別式依存句法分析模型

判別式模型為了得到正確的分類邊界，從非單一樣本的數(shù)據(jù)中抽取出共有的特征。判別式句法分析為了避開聯(lián)合概率模型中所要求的獨立性假設，分析方法中采用條件概率模型。其代表模型是賓西法尼亞大學的最大生成樹句法分析器，這是真正意義上的依存句法分析器。但是，非投影問題對系統(tǒng)復雜度是一個很大的挑戰(zhàn)，判別式依存句法的優(yōu)勢在于對非投影問題的處理分析，該方法更加注重算法復雜度的降低。判別式的句法分析方法和生成式的分析方法一樣，都是進行整個句子內的全局搜索，所以算法復雜度是必須要考慮的問題。判別式方法的一個最大缺陷是它的訓練方法繁瑣，需要重復分析訓練集來迭代參數(shù)。

判別式依存句法分析模型的基本思想是：采用條件概率模型score（x，y|θ），使目標函數(shù)取得最大值的θ作為模型的參數(shù)。

通常，采用對數(shù)線性模型來進行判別模型的參數(shù)估計，并在句法分析中常以分類器的形式體現(xiàn)。首先，將句法分析進行分解，隨后的操作由分類器來選擇。在句法分析中應用較多的判別模型有：最大熵模型、支持向量機模型、決策樹模型等。

2.2.1 最大熵

在英語的句法分析中，Ratnaparkhi最早引入了最大熵的方法，他利用上下文特征，通過最大熵的方法來預測下一步要執(zhí)行的操作。其上下文特征主要包括：成分的核心詞，核心詞的組合，非特定組合信息，以及部分已完成的子樹信息。

2.2.2 支持向量機

支持向量機是一種基于統(tǒng)計學習原理的線性分類器，可以使構成的超平面分割訓練數(shù)據(jù)時，能夠獲得最大的邊緣。支持向量機具有良好的應用效果，在自然語言處理中應用較為廣泛，常用于文本分類等問題。

支持向量機的主要缺點是其訓練效率偏低，并且對于輸出結果不能準確地給出各個輸出結果的概率分布，這就限制了它在概率需求較強的任務中的應用，給一些利用概率結果的處理和應用帶來了麻煩。

2.2.3 決策樹

決策樹是另外一種比較典型的判別學習方法。它是一種“問卷表”方式的做法，利用一系列的查詢問答來判斷和分類某一模式，它將全部問題集用一棵有向樹表示，對非度量數(shù)據(jù)而言效果較好。在英語的句法分析中，決策樹的方法在英語的P賓州樹庫上取得了83%以上的正確率。決策樹學習方法也存在一些問題，例如，在高維問題的處理上效果就不夠理想。

2.3 決策式依存句法分析模型

決策式的句法分析方法，是以特定的方向逐步取一個待分析的詞，為每次輸入的詞產生一個單一的分析結果，每讀入一個詞，都要根據(jù)當前狀態(tài)作出決策。分析過程可以看作是一步步作用于輸入句子之上的分析動作的序列。

決策式句法分析模型的典型代表是移近—歸約狀態(tài)轉移模型。移近—歸約狀態(tài)轉移模型在分析過程中維護一個堆棧和一個隊列，堆棧用以存儲到目前為止所有的依存子樹，隊列存儲尚未被分析到的詞。堆棧頂端和隊列的頭部確定了當前分析器的狀態(tài)，依據(jù)該狀態(tài)決定進行移進、規(guī)約或者建立棧頂元素與隊首元素的依存關系的操作，從而轉入新的狀態(tài)。

Sagae等[5]依照單純的移進—歸約的思想實現(xiàn)了一個確定性的句法分析器，解碼采用貪心策略，該文實驗中采用支持向量機分類器和基于存儲的分類器，支持向量機分類器實驗結果為：召回率80.2%，準確率為80.0%；基于存儲分類器實驗結果為：召回率87.6%，準確率87.5%。同時，也從理論上證明了句法分析的時間復雜度為O（n），其中n值是句子的長度。

Zhang等[6]對Sagae進行了改進，使用線性模型對決策序列進行預測，從全局的角度對決策進行了考量，采用泛化的感知器算法對模型的參數(shù)進行訓練，模型解碼時，不再像Sagae使用確定性方式，而是引入BeamSearch策略，實驗中討論了Beam-size和訓練數(shù)據(jù)集的大小對實驗結果的影響，可惜的是此文只給出了在CTB上的實驗結果。

2.4 約束滿足依存句法分析模型

約束滿足的依存句法分析模型采用約束依存語法，將依存句法分析看作可以用約束滿足的問題來描述的有限構造問題。它是根據(jù)已規(guī)定好的約束進行剪裁，把不符合約束的分析去掉，規(guī)定好的約束進行剪裁，把不符合約束的分析去掉，直到留下一棵合法的依存樹。

約束滿足的依存句法分析模型也存在一些問題：可能不存在能滿足所有約束的分析樹，也可能有多個樹滿足所有約束，無法消歧。

3 結語

依存句法分析成為當今句法學研究的前沿和熱點問題之一，隨著研究的深入，依存句法分析模型也日趨成熟。通過對目前主流依存句法分析模型的分析，現(xiàn)有的模型大多是通過經(jīng)典模型的改進而來，漢語依存句法分析明顯落后于英語依存句法分析。

對于目前漢語依存的發(fā)展，研究要結合漢語自身的特點。就目前而言，統(tǒng)計方法已成為主流技術，盡管英語方面出現(xiàn)許多較為成熟的統(tǒng)計模型，可以為漢語分析所借鑒，但漢語的語言特點使得研究人員在借鑒其優(yōu)點的同時，還應該結合漢語特點進行特殊處理，比如漢語中特殊語法結構（排比句、疊詞等）的處理。利用語法、語義等方面知識構建聯(lián)合模型來提高依存分析的正確率，構建的詞義、詞性標注和依存分析的聯(lián)合模型。聯(lián)合模型開辟了一種新的思路，可以成為我們研究的一種方向。

[參考文獻]

[1]EISNER J.Bilexical grammars and a cubic-time probabilistic parser[J].Proceedings of the International Workshop on Parsing Technologies，1997（20）：54-65.

[2]YAMADA H，MATSUMOTO Y.Statistical dependency analysis with support vector machines[C].Vancouver：Proceeding of the 8th International Workshop on Parsing Technologies，2003：195-206.

[3]JUN H，TAKUYA M，YUSUKE M，et al.Incremental joint approach to word segmentation，pos tagging，and dependency parsing in Chinese[C].Beijing：Proceedings of the 5th International Joint Conference on Natural Language Processing，2011：1225-1234.

[4]ZHOU M.A block-based dependency parser for unrestricted Chinese text[C].Hong Kong：Proceeding of the 2nd Chinese Language Processing Workshop Attached to ACL-2000，2000：78-84.

[5]SAGAE K，ALON L.A classifier-based parser with linear run-time complexity[C].Hirosaki：Proceeding of IWPT，2005：125-132.

[6]ZHANG Y，STEPHEN C.Syntactic processing using the generalized perceptron and beam search[J].Computational Linguistics，2011（1）：105-151.