楊振鵬

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

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

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

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

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

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

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

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

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

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

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

Jin等對(duì)Nivre和Yamada方法進(jìn)行改進(jìn)，新的移進(jìn)—?dú)w約算法采用雙階段方式進(jìn)行漢語依存分析，第一階段的歸約由兩部分構(gòu)成，一是歸約左邊的依存弧，二是歸約右邊的體詞性依存節(jié)點(diǎn)，第二階段則主要是對(duì)右邊的動(dòng)詞性依存節(jié)點(diǎn)進(jìn)行歸約。實(shí)驗(yàn)時(shí)，先對(duì)CTB 4.0進(jìn)行轉(zhuǎn)換，然后抽取轉(zhuǎn)換結(jié)果中部分句子作為實(shí)驗(yàn)數(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。生成式模型的最終目標(biāo)是從訓(xùn)練模型中獲取使聯(lián)合概率P（T，S）取得最大值的參數(shù)θ，得分最高的依存結(jié)構(gòu)樹。為了便于計(jì)算聯(lián)合概率P（T，S），可以對(duì)句法分析問題作出不同程度的假設(shè)，這將有效減少數(shù)據(jù)稀疏問題。

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

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

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

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

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

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

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

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

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

2.2.1 最大熵

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

2.2.2 支持向量機(jī)

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

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

2.2.3 決策樹

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

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

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

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

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

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

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

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

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

3 結(jié)語

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

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

[參考文獻(xià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.