結合結構下文及詞匯信息的漢語句法分析方法

陳 功，羅森林，陳開江，馮 揚，潘麗敏

(北京理工大學 信息與電子學院信息安全與對抗技術實驗室，北京 100081)

1 引言

將自然語言的句法分析進行可計算化處理，需要兩個重要元素：語法模型和搜索算法[1]。無論是早期單純的理性主義和經驗主義還是如今的兩者結合，都需要建立一種語法模型，并且在分析過程中采取一種搜索算法得到分析結果。最早的語法模型就是簡單的上下文無關語法模型。概率上下文無關語法(PCFG)是把概率引入到上下文無關語法規(guī)則而形成的語法規(guī)則模型。但是，經典的PCFG實際上是建立在一些非常理想化的獨立性假設的基礎之上的，而這些假設并不符合實際，于是造成了PCFG的實際效果不理想。目前的概率上下文無關語法研究，主要集中在如何突破這些獨立性假設上。

中國科學院的張浩和劉群嘗試了祖先節(jié)點相關，父節(jié)點使用的規(guī)則相關等幾種結構上下文相關的策略，效果良好[2]。北京大學計算語言研究所的冀鐵亮等嘗試使用了動詞子語類框架[3]，利用了動詞的子語類框架的信息。北京大學的張耀中嘗試了融合語義和句型信息[4]。這些方法都對突破上下文無關語法研究中的獨立性假設的進行了嘗試。利用了結構上文，動詞詞匯及語義、句型等信息，對于PCFG模型的改進及分析很有參考價值，但是這些方法沒有嘗試與結構下文相關，本文的工作正是通過在概率上下文無關語法模型中加入結構下文，構成了結構下文相關的概率語法模型。

詞匯化的句法分析是目前自然語言處理研究的趨勢和熱點。概率上下文無關語法由于其獨立性的假設，脫離詞匯本身，這也是PCFG的一個重要缺陷?；诖?，本文在PCFG中引入了詞匯信息，構成了詞匯化的PCFG，彌補了詞匯信息的缺乏。同時，對于模型的分析算法，使用了基于左角分析的Earley改進算法，并引入分層的分析策略，進一步提高了分析效果。

2 結構下文及詞匯信息結合的語法概率模型

經典的PCFG基于獨立性的假設，對上下文信息利用不足，且沒有用到詞匯信息。基于此本文提出了結構下文相關的概率模型(S-PCFG)以及結合詞匯信息的概率模型(L-PCFG)，并在這兩個模型基礎上，提出了結構下文相關以及結合詞匯信息的概率模型(SL-PCFG)。

2.1 經典模型(PCFG)

一個 PCFG 的符號系統(tǒng)包括以下成分：

? 一個終結符的集合，{Wk},k=1,…,V

? 一個非終結符的集合，{Ni},i=1,…,n

? 一個開始符號，N1

? 一個規(guī)則的集合，{Ni→ζj}，(其中ζj是一個終結符和非終結符的序列)

概率方面，PCFG給出了由一個非終結符節(jié)點可能派生出的各種符號序列的概率分布(式(1))。

計算一棵分析樹t的概率P(t)，需要進行必要的獨立性假設。經典的 PCFG認為，施用每一條規(guī)則的概率獨立于上下文和祖先節(jié)點[5]。這樣，假設t當中的所有規(guī)則構成了一個規(guī)則的多重集R，那么[2]：

(2)

所得句法分析樹的概率P(t)是建立在PCFG的獨立性假設基礎上的，主要是以下三條假設：

(1)位置無關性假設：子節(jié)點概率與子節(jié)點管轄的字符串在句子中的位置無關；

(2)上下文無關性假設：子節(jié)點概率與不受子節(jié)點管轄的其他字符串無關；

(3)祖先結點無關性假設：子節(jié)點概率與導出該節(jié)點的所有祖先節(jié)點無關。

然而，實際生活中自然語言有著很強的上下文相關性，子節(jié)點的概率不僅與其祖先節(jié)點有關，還與它的兄弟節(jié)點，它所導出的子節(jié)點相關，面對這樣的歧義，PCFG模型便無法解決。此外，PCFG模型并沒有考慮詞匯的信息，對于詞匯相關的歧義，它也是無法解決。

由此可見，概率上下文無關語法在遇到結構依存和詞匯依存問題的時候就顯得無能為力了，因此有必要探索其他的途徑來進一步提升概率上下文無關語法的功能[6]。

2.2 結構下文相關的概率模型(S-PCFG)

PCFG對于上下文信息的利用是不足的，子樹的概率與子樹以外的節(jié)點無關。針對PCFG的這一點假設，模型認為，一個非終結符重寫出來的節(jié)點受其子規(guī)則約束，符合真實語料中二次重寫(子規(guī)則)統(tǒng)計規(guī)律的非終結符才能在一次重寫中應用。例如，dj=np+vp的重寫過程中(一次重寫)需要考察其中np和vp將會重寫成什么符號(二次重寫)，然后再考慮一次重寫是否能成立，這相當于在分析中借助了下文的信息來提前驗證上文的預測。這個模型的規(guī)則表示成非終結符Ni重寫為幾個一層子規(guī)則r式(2)的形式，而不是重寫為兩個非終結符(或終結符)，如式(3)所示。

Ni=rj+rk+…+rl

(3)

相應地，模型中包含了式(4)所示的概率分布。

(4)

采用這種改進的PCFG模型，增加了重寫規(guī)則的分辨率。在自底向上分析或者左角分析的過程中可以快速幫助分析器抉擇，減少不必要的子樹生成。每一個S-PCFG的規(guī)則概率可以理解為一個條件概率，類似于PCFG的規(guī)則概率，S-PCFG的規(guī)則概率計算式如式(5)所示。

需要說明的是，在重寫部分中若出現終結符(詞性標記)則不用二次重寫。

假設句法樹t當中的所有非終結符構成了一個非終結符的集合N，分析樹的概率計算公式如式(6)所示。

(6)

模型的規(guī)則中所有非終結符均采用節(jié)點附著子節(jié)點的形式表示，例如字符串形式表示為dj-np-vp=np-nr+vp-v-np(規(guī)則左邊為節(jié)點“dj”附著子節(jié)點“np”“vp”)，在葉子節(jié)點上依然是原來標記作為節(jié)點類型，一般是詞性標記，若結合下文L-PCFG的話可能是“詞匯/詞性”的形式。

圖1所示為由S-PCFG模型分析出的句法樹。

圖1 S-PCFG的分析樹表示方法

2.3 結合詞匯信息的概率模型(L-PCFG)

L-PCFG模型是將一些小集合詞性的詞匯關聯到規(guī)則中去，是一種部分詞匯化的PCFG，雖然將如名詞、動詞等詞匯考慮到句法分析中后勢必會造成數據稀疏，但是對于集合較小，在自然語言使用中更新較慢的詞匯則可以考慮到句法分析中去。經對《人民日報》1998年1月的語料進行統(tǒng)計之后，可以確定將詞性如表 1所示的詞匯作為預終結符(即介于非終結符和終結符之間的詞性符號)，直接考慮到句法分析中。

表1 詞語集有限的詞性標記統(tǒng)計

這些詞性的集合隨著語料增加的分布規(guī)律如圖2 所示(統(tǒng)計語料來源：《人民日報》1998年1月)。從圖 2中可以看出，表 1中所列的詞性對應的詞匯是一個收斂的集合，將這些詞性的具體詞匯關聯到語法規(guī)則中引起的數據稀疏問題并不是很嚴重，相反，會帶來良好的消歧能力。綜合考慮數據稀疏及消歧能力，將相應的詞匯信息關聯到語法規(guī)則中還是有利的。

圖2 部分詞性集合詞匯分布規(guī)律

為了使規(guī)則表示為“非終結符重寫為若干預終結符”的形式，以方便和其他概率語法模型使用相同的分析算法以及相同的訓練算法，設計L-PCFG將關聯詞匯的規(guī)則表示為在需要關聯到詞匯時的地方都將詞匯和詞性連在一起作為一個符號，這相當于擴展了詞性標記，示例如圖 3所示，規(guī)則表示為vbar=v+了/u。

圖3 與詞匯關聯的規(guī)則實例

經過上述方式擴展了規(guī)則集之后，可以繼續(xù)使用原來的分析算法進行分析，只是在輸入句子后首先要檢查句子中是否存在表 1中所列的詞性，若有則需進行預處理以方便使用該模型進行分析。

2.4 結構下文相關以及結合詞匯信息的概率模型(SL-PCFG)

為實現對句子信息的充分利用來進行句法分析，SL-PCFG.對S-PCFG及L-PCFG模型進行了結合見圖4。模型的結合實質上是將各種限制條件疊加使用，疊加的限制條件越多，分析越精確，但是在樹庫資源有限的情況下，開集測試時召回率會有所下降。

圖4 S-PCFG的分析樹表示方法

利用以上四種模型對句法分析的效果參見第四節(jié)的實驗部分。

3 句法分析算法

句法分析算法原理如圖 5所示。對于不同的概率模型，采用同樣的分析算法，只需在規(guī)則提取時采用不同的規(guī)則即可，即分別采用PCFG、S-PCFG、L-PCFG或是SL-PCFG的規(guī)則。

圖5 句法分析算法原理

3.1 規(guī)則提取

規(guī)則施用概率的提取采用最大似然估計，不同的概率模型(PCFG、S-PCFG、L-PCFG、SL-PCFG)有著各自的語法規(guī)則，但對于規(guī)則施用概率提取本質上都是一樣的。

隨著基于統(tǒng)計的方法在句法分析中逐漸成為主流，語料庫的建設對于句法分析的研究來說是不可或缺的，從樹庫自動抽取語法規(guī)則并進行統(tǒng)計以用于模型的分析是有效易行的。對于以上各模型的語法規(guī)則及概率獲取是比較簡單的，一般做法是：首先統(tǒng)計訓練語料中出現的規(guī)則及其次數，然后利用最大似然估計從規(guī)則出現頻率估計出規(guī)則施用概率[7]如式(7)。

加入結構下文信息或小集合詞匯信息模型的規(guī)則施用概率的計算公式跟式(7)本質上是一樣的，只是將重寫規(guī)則Ni→ζj改寫為Ni→rj+rk…rl的形式，如式(5)所示；或將部分規(guī)則中需要關聯到詞匯時的地方都將詞匯和詞性連在一起作為一個符號。相應的分析樹中的節(jié)點標記或部分詞性標記也進行變換。

具體的標記變換如圖 6所示。

圖6 標記變換示例

這樣，四個模型的分析算法都是PCFG的分析算法，只要替換不同的規(guī)則集，就構造出了結構下文相關、結合詞匯信息、結構下文相關以及結合詞匯信息的分析器。

3.2 句法結構分析

根據獲得的概率規(guī)則庫，我們采用分層分析的算法對待分析的句子進行句法結構的自動分析。

分析算法對原有的Earley算法進行了改進，并引入了分層的分析策略。原有的Earley算法是一種典型的自頂向下、自左向右的分析算法。通過對Earley算法進行改進，使用自底向上的分析算法，有效地減少了自頂向下的預測過程。使用分層的分析算法，有效地解決了消歧性與魯棒性間的矛盾。

1)分層分析算法原理

句法分析的難點是歧義消解，歧義存在的原因在于當前模型下無法獲取更多的信息來供分析器判定，因此消歧能力越強的模型其語法規(guī)則的限制條件越多，進而造成數據的稀疏，使得精確性(準確率)提高的同時，分析的覆蓋面(召回率)有所下降。分層構建句法樹實質上是用不同的概率語法模型分析，并且不同層之間共享子樹，為了在魯棒性較好的模型中使用到消歧性較好的模型分析出的子樹，來達到魯棒性和消歧雙贏的目的。在不同層(使用不同模型)分析過程中，即使某一層未分析成功整個句法樹，但是在下一層分析時仍可共享這一層得到的子樹片段。

分層分析一共四層，四層模型的特點如圖 7所示。只要有一層分析成功，分層分析不再進行下去。分層分析的流程圖如圖 8所示。

圖7 四層模型特點

圖8 分層分析流程圖

2)分層分析沖突處理策略

由于分層分析時是將不同語言模型下產生的結果放在一起，因此在構建句法樹過程中遇到沖突時，采用PCFG模型的概率參數對沖突進行取舍。

采取如下方式：當同層分析時，遇到范圍相同、根節(jié)點相同的片段樹時，采用PCFG模型的參數計算每個片段樹的概率，保留較大概率的片段樹。當不同層分析得到相同范圍、根節(jié)點相同的片段樹時，先計算各自在PCFG模型下的概率，較低一層得到的句法樹概率大于較高一層分析得到的句法樹時選擇較低一層得到的樹，否則，優(yōu)先選擇較高一層得到的子樹。

例如，在第四層未分析成功但是產生了部分片段樹的情況下，第三層分析結束后構建出一個片段樹T3，并檢查到已在上一層構建出相同根節(jié)點的片段樹T4，則在PCFG下分別計算P(T3)和P(T4)，若P(T3)> P(T4)則用T3替代T4，否則選擇T4。

4 實驗及結果分析

為了驗證各語法模型的分析效果及分層分析結果，進行了各語法模型的分析對比實驗及分層分析的實驗。

本文的算法研究采用BFS-CTC語料庫(Beijing Forest Studio-Chinese Tag Corpus)。其原始語料來源于新聞語料中的句子(如Sohu、Sina、人民日報等)，句法標注集采用北京大學計算語言學研究所規(guī)范[8]。目前語料庫中的句子以單句為主，其中的句子基本涵蓋了各種句型及常見語法現象。

實驗的訓練數據來自于BFS-CTC語料庫中的詞法、句法標注集，表 2所示為訓練集，共5 488句。閉集測試集是從訓練集中抽樣的句子，共549句，平均每句13詞；開集測試為對以上5 488句數據源的十字交叉驗證。

表2 訓練用句子句式分布表

句法分析模型的評測算法采用的是PARSEVAL句法分析評價體系[9]。主要由準確率(Precision，體現準確性)、召回率(Recall，體現全面性)兩部分組成。F1值(Precision與Recall的調和均值)是用來綜合評價準確性和全面性的指標。

實驗中，首先分別利用PCFG、L-PCFG、S-PCFG、SL-PCFG進行單模型的句法分析實驗，其結果如表 3所示；結合得到的PCFG、L-PCFG、S-PCFG、SL-PCFG四種模型的概率規(guī)則庫，采用分層分析算法針對相同數據進行實驗，其結果如表 4所示。

表3 各個語法模型對比實驗結果

表4 分層分析實驗結果

表3的結果表明：集合了S-PCFG和L-PCFG兩個模型的SL-PCFG的消歧能力最強，因此在閉集測試時能夠得到最好的效果。但是， 與此同時帶來了數據稀疏的問題；在開集測試時雖然準確率仍然很高，但是召回率已經銳減到0.272了，說明已經出現了大量分析不成功的句子。S-PCFG模型與PCFG模型相比，準確率與召回率在閉集測試時均有較大程度的提高，但是召回率在開集測試時也有所下降。L-PCFG模型與PCFG模型相比，準確率有了一定程度的提高，說明加入部分詞匯信息對于結構歧義的消除有一定效果，但對于句子分析成功與否的作用并不明顯。

表5列出了相關中文句法分析器在賓州中文樹庫測試集上的結果。其中分析效果比較顯著的有Jiang作業(yè)論文[15]將Collins模型移植成中文句法分析器，F1值達到了81.1％；中國科學院的米海濤[16]等(2008)利用多子模型句法分析系統(tǒng)將中心詞驅動模型和結構上下文模型按照對數線性模型融合在一起，形成多子模型句法分析器，F1值達到了82.5％的較高水準；Petrov & Klein[17](Berkeley Parser)在PCFG模型基礎上利用隱含特征(PCFG-LA),同時并行的采用EM算法進行訓練，得到了一個不依賴于特定語言的句法分析器，Mary P.Harper & Zhongqiang Huang[19]用此句法分析器在CTB上對漢語進行了句法分析，得到了82.7％的準確率及83.1％的召回率，一定程度上減小了中、英文在句法分析結果上的差距；哈爾濱工業(yè)大學的曹海龍等[18]以著名的中心驅動模型為基礎，結合中心成分決策表和基本名詞短語，采用CYK分析算法，在CTB公共測試集上得到了85.89％的準確率和85.61％的召回率，這是目前已知的中文句法分析的最好分析結果。

表5 漢語相關句法分析性能比較

表4所示為論文中所述漢語句法分析的分析結果。與表5所示各漢語句法分析器實驗結果相比，雖然結果較好，但由于采用的是實驗室自己的語料，可比性存在著一定的問題。因此，暫時只能跟傳統(tǒng)的PCFG模型進行比較，以體現結合結構下文信息，結合部分詞匯信息對PCFG模型描述能力的提高。同時，有力地說明了結合結構下文及部分詞匯信息的分層分析方法的有效性。

結合表 3、表 4可以看出，分層分析在開集和閉集測試都能得到良好的效果。分層分析中依靠消歧能力較強的SL-PCFG和S-PCFG提高分析的準確率，依靠魯棒性較好的L-PCFG和PCFG來提高分析的全面性，從而得到準確率與全面性的共同提高。開集測試的結果尤為明顯。

5 結論

PCFG模型上下文無關的假設是必須要進行突破的，同時詞匯信息的引入也是必不可少的[2]。本文基于以上的兩點考慮，首先在PCFG結構獨立性假設基礎上引入了結構下文信息；然后在PCFG中引入了詞匯化。實驗結果表明，基于以上兩點所做的改進很大程度上增強了句法分析的消歧能力。同時，針對由于S-PCFG及SL-PCFG引入了較多的規(guī)則條件，而出現數據稀疏的問題，本文采用了分層分析算法。利用SL-PCFG和S-PCFG消歧能力較強的特點，利用L-PCFG和PCFG魯棒性較好的特點，結合不同模型的優(yōu)點，兼顧了句法分析的準確性以及全面性。

[1]苗奪謙,衛(wèi)志華.中文文本信息處理的原理與應用[M].北京:清華大學出版社,2007.

[2]張浩,劉群,白碩.結構上下文相關的概率句法分析[C]//第一屆學生計算語言學研討會.北京,2002,46-51.

[3]冀鐵亮,穗志方.詞匯化句法分析與子語類框架獲取的互動方法[J].中文信息學報.2007(01):120-126.

[4]張耀中.融合語義和句型信息的中文句法分析方法研究與實現[D].北京大學,2009.

[5]Manning,C.,Schütze,H.Foundations of Statistical Natural Language Processing[M].Massachusetts:MIT Press,1999.

[6]馮志偉,自然語言處理中的概率語法[J].當代語言學.2005(2).

[7]Charniak,E.Treebank Grammars[R].Providence:Department of Computer Science,Brown University,1996.

[8]周強.漢語語料庫的短語自動劃分和標注研究[D].北京:北京大學,2002.

[9]Charniak,E.1997.Statistical Parsing with a Context-free Grammar and Word Statistics[C]//Proceedings of National Conference on Artificial Intelligence(NCAI)-1997,598-603.

[10]Daniel M.Bikel,David Chiang.Two statistical parsing models applied to the Chinese Treebank[C]//Proceedings of ACL 2nd Chinese Language Processing Workshop,2000.1.

[11]Roger Levy,Christopher D.Manning.Is it harder to parse Chinese,or the Chinese Treebank[C]//Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics,2003.439.

[12]Deyi Xiong,Shuanglong Li,QunLiu,Shouxun Lin,and Yueliang Qian.Parsing the Penn Chinese Treebank with semantic knowledge[C]//Proceedings of IJCNLP’05,2005.

[13]Daniel M.Bikel On the Parameter Space of Generative Lexicalized Statistical Parsing Models[D].Pennsylvania:Thesis of University of Pennsylvania,2004.

[14]David Chiang,Daniel M.Bikel.Recovering latent information in treebanks[C]//COLING ’02 Proceedings of the 19th international conference on Computational linguistics-Volume 1,2002.

[15]Zhengping Jiang Statistical Chinese parsing[D].Singapore:National University of Singapore,2004.

[16]米海濤,熊德意,劉群.中文詞法分析與句法分析融合策略研究[J].中文信息學報.2008,22(2):10-17.

[16]Slav Petrov,Dan Klein.Improved inference for unlexicalized parsing[C]//Human Language Technologies 2007:The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference.Rochester,New York,2007:404-411.

[18]曹海龍,趙鐵軍,李生.基于中心驅動模型的賓州中文樹庫(CTB)句法分析[J].高技術通訊.2007,17(1):15-20.

[19]MaryP.Harper,Zhongqiang Huang.Chinese Statistical Parsing[C]//Joseph Olive,John McCary,and Caitlin Christianson (eds).Handbook of Natural Language Processing and Machine Translation.Defense Advanced Research Projects Agency,Reston Virginia,2011:90-102.