楊振鵬

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 最大熵

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

2.2.2 支持向量機

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

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

2.2.3 決策樹

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

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

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

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

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

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

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

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

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

3 結(jié)語

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

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