融合多結構信息的中文句法分析方法*

趙國榮，王文劍

山西大學 計算機與信息技術學院，太原 030006

融合多結構信息的中文句法分析方法*

趙國榮，王文劍+

山西大學 計算機與信息技術學院，太原 030006

+Corresponding author:E-mail:w jwang@sxu.edu.cn

ZHAO Guorong，WANGWenjian.M ethod for Chinese parsing based on fusion of multiple structural information.Journalof Frontiersof Computer Scienceand Technology,2017,11(7)：1114-1121.

句法分析是自然語言理解的一項基礎技術，是邁向深層語言理解的基石。目前常用的句法分析方法的語法模型建立在上下文無關文法的假設上。事實上，短語結構樹的節點之間具有很強的上下文相關性，充分利用結構信息，可進一步提高句法分析的準確性。融合了句法結構樹中的多結構信息（在非終節點中增加父親節點及左、右姐妹節點等標記）以加強語法規則的上下文約束，并采用結構化支持向量機的方法對句法進行了分析。實驗表明，該融合多結構信息的句法分析方法可以消解結構歧義，提升句法分析精確率和F1值。

結構化支持向量機；上下文無關文法；結構上下文相關；中文句法分析

1 引言

句法分析是自然語言處理的關鍵性問題之一。對句法分析進行可計算化處理，句法分析算法和語法模型是兩個重要的元素，其中語法模型無論是使用統計的方法，還是使用單純的規則，在進行句法分析時都需要建立一種模型。最早的語法模型是簡單的上下文無關的語法模型（context-free grammar，CFG）[1]。但是CFG是在一些非常理想化的獨立性假設的基礎上建立的，它的規則的建立只和其孩子節點有關，因而這些假設忽略了句法樹中其他許多隱含的信息。為了得到更好的基于短語結構的句法分析效果，一些算法的研究集中在挖掘短語結構樹的上下文相關的信息上，通過增加豐富的結構信息和詞匯信息等來提升句法分析的效果。

最具代表性的研究就是在概率上下文無關文法[2]（probabilistic context-free grammar，PCFG）中增加結構上下文相關的策略。文獻[3]嘗試了祖先節點相關、父親節點相關等幾種結構上文相關的策略；文獻[4]嘗試了加入結構下文孩子節點相關的策略，構成結構下文相關的概率語法模型；文獻[5]加入了每個短語節點的父親節點和左、右姐妹節點的結構上下文信息，這些方法都對突破上下文無關語法研究中的獨立性假設進行了嘗試，都是對經典PCFG模型進行的優化。文獻[6]采用機器學習方法——結構化支持向量機（structural support vectormachine，SSVM）對基于短語結構的中文句法進行分析，語言模型采用的是上下文無關文法。本文的工作是嘗試融合句法分析樹中節點的結構信息，研究使用結構化支持向量機對中文句法進行分析時所產生的影響，實驗證明它可以提高句法分析系統的精確率和F1值。

2 結構化支持向量機方法簡介

在現實世界中，需要處理的大部分數據（如網狀結構數據、隊列結構或樹形結構等）都比較復雜，而且數據之間相互依賴，具有特定的結構化關系，傳統的支持向量機[7]已經不適合處理這些復雜的數據。為了解決傳統支持向量機在處理復雜數據時的難題，Hofmann和Joachims等人首次提出了結構化支持向量機[8-9]，它可以根據不同的應用領域設計不同的結構化特征函數去擬合數據，從而有效地處理結構化數據。

結構化支持向量機是一種基于判別式的學習模型，使用結構化支持向量機的關鍵是構造出樣本的輸入與輸出對之間的一個映射函數 f:x→y。當使用結構化支持向量機進行句法分析時，f:x→y中 f表示的意思是輸入句子X到輸出短語結構樹Y的一個映射。在構造函數 f時，關鍵任務是需要學習一個基于輸入/輸出對的判別式函數F:X×Y→?，通過使輸出變量最大化的方法，實現對輸出結果預測的目的。結構化支持向量機的目標函數[10-11]為：

F是基于輸入/輸出組合特征表示ψ(x,y)的線性函數：

式（1）中帶參數w的函數 f，假設它的經驗風險為0，可以寫成一個非線性約束的形式[8]：

式（3）可以等價轉換為：

采用最大間隔法可以將式（4）轉化為一個凸二次規劃形式的最優化問題[10]：

為了容忍部分噪聲和離群點，同時兼顧除靠近邊界之外更多的訓練點，在式（5）中引入松弛變量的軟間隔，本文采用一階范數ξ的形式[10]：

3 融合多結構信息的語法模型構造

文獻[6]使用結構化支持向量機進行中文句法分析時，將文法限定為喬姆斯基范式的形式[2]，其語法規則為：

這里A、B、C是非終結符，α是終結符。設x是需要進行句法分析的句子，Y是針對x分析出的若干個句法樹的集合。假設最佳分析樹為h(x)，每棵句法樹y中所有的語法規則的集合用rules(y)表示，每一個語法規則所對應的權值參數為wl，文獻[6]使用的上下文無關文法模型為：

但是，在實際生活中自然語言具有很強的上下文相關性，上下文無關語法表現能力有限，當遇到結構依存的問題時就顯得能力有限了。

上下文無關文法對句法樹中的結構以及詞匯等信息利用不足，無法描寫句法樹結構上隱藏的許多信息，如每個短語節點的父節點或（和）左、右姐妹節點的信息。文獻[5]成功地將上下文相關信息（即父節點或（和）左、右姐妹節點的信息）加注到每個短語節點（即非終節點）上，使用概率上下文無關文法進行句法分析，并取得很好的效果。故本文也嘗試將這些信息增加到使用結構化支持向量機進行句法分析的方法中，從而提升句法分析器的精度。假設將單純地增加“父親”、“左妹”或“右妹”信息稱為一階標注；那么增加“父親+左妹”、“父親+右妹”或“左妹+右妹”就是二階標注；增加“父親+左妹+右妹”為三階標注。因為只是在非終節點上增加上下文相關的結構信息，所以語法規則（7）（8）的形式要發生變化。以語法規則（7）的形式變化為例，在每一個非終節點后用括號注明相關結構信息范疇。

一階標注中增加父親信息后，規則（7）的形式變換為：

增加左妹信息后，規則（7）的形式變換為：

增加右妹信息后，規則（7）的形式變換為：

二階標注中增加父親+左妹信息后，規則（7）的形式變換為：

增加父親+右妹信息后，規則（7）的形式變換為：

增加左妹+右妹信息后，規則（7）的形式變換為：

三階標注增加父親+左妹+右妹信息后，規則（7）的形式變換為：

語法規則（8）和規則（7）箭頭左部的變化一樣，因為箭頭右邊是終結符，所以不發生變化。簡單地以增加父親節點信息為例，短語的結構受到上層短語的制約。比如做主語的NP短語（NP位于S之下）和做賓語的NP短語（NP位于VP之下）的內部結構明顯不同，這樣可以快速幫助分析器抉擇，減少不必要的子樹生成。

4 結構化支持向量機特征函數的構建

在結構化支持向量機中，關鍵任務是特征函數ψ(x,y)的構造，在不同的領域需要構造不同的特征函數，從而和實際數據達到較好的擬合。因而特征函數構造合適與否會直接影響結構化支持向量機方法的有效性。圖1是短語結構樹的輸入輸出示例，圖2為其在學習時構造的ψ(x,y)。

以在每個非終節點增加“父親”、“父親+左妹”和“父親+左妹+右妹”節點為例，短語結構樹以及構造的相對應的特征函數ψ(x,y)變換后的示例如圖3所示。

Fig.1 A sampleof inputand outputw ithout structural information圖1 未增加結構信息的輸入輸出示例

Fig.2 Structural feature functionψ(x,y)圖2 結構化特征函數ψ(x,y)

在使用結構化支持向量機進行句法分析時，在學習過程中要從樹庫自動抽取語法規則并進行統計，從而對模型進行分析。rj表示句子x的句法分析樹y中每一個節點所對應的規則，aj表示規則rj出現的次數，wj表示每條規則相對應的權值。x表示一個句子，y表示其對應的有效句法樹，wj表示每一個節點的權值，其和作為這個句法樹的分值，F(x,為計算分值的函數。特征函數ψ(x,y)的構造就是由樹庫中出現的規則及其次數組成。對于給定的句子x，通過喬姆斯基算法[2]（Cocke-Younger-Kasam i，CKY）找出符合文法的句法分析樹集Y，再從句法分析樹集中找出分值最大的F(x,y,w),y∈Y，即為所求句子的語法樹。

Fig.3 Structural feature function afteradding structural information in non-terminalnode圖3 在每個非終節點增加結構信息后的結構化特征函數

5 實驗及分析

本文為了測試結構化支持向量機在融合多結構特征后對中文句法分析精度的影響，進行了一組對比實驗，并對結果進行了分析。

5.1 語料的預處理

5.1.1 語料1預處理

本文的實驗語料1來自北京大學計算語言學研究所公開的北大微型樹庫的A語料[12]。該語料來自漢英機器翻譯研究的測試題庫，它句型多樣，句子較短，不同短語組合的分布也很廣，便于進行自動分析處理。

該語料一共有1 434句，表1是對實驗語料集的情況統計[12]，表2為實驗語料舉例。

選取表2中887句單句作為實驗語料1，句長最長為19，最短為3，其平均句長為7.01；抽取其中787句作為訓練語料，100句用作開放測試的語料。

在進行實驗之前，需要對北大樹庫語料進行改寫，比如：

[dj廠長/n[vp[vbar宣布/v了/u][np委員/n名單/n]]]

改寫后格式為：

5.1.2 語料2預處理

本文的實驗語料2采用文獻[6]的語料，該語料來自PCTB賓州中文樹庫語料，從1 500個文檔中提取2 000條（句長小于等于12詞）單句，其中的1 850句用來進行訓練，剩下的150句用來進行開放測試。

在進行本實驗前，同樣需要對從賓州中文樹庫選出來的2 000個單句進行預處理[13-14]，將句法樹上原有的空語類、指同索引和功能標記一概刪除[5]。

例如，下面例句A轉換成B的形式：

5.2 評價指標

本文使用PARSEVAL評價體系[2]作為句法分析模型的評價指標，選取其中的精確率（Precision，Pre）、召回率（Recall，Rec）以及F1值（Pre和Rec的調和平均值）對結果進行評價。

Table1 Statisticsofexperimentaldata表1 實驗語料情況統計

Table 2 Samplesof experimentaldata表2實驗語料句型舉例

精確率表示所有句法分析結果中所有正確的成分比例；召回率表示句法分析結果中正確的成分占所有句法實際成分的比例；F1=2×Pre×Rec/(Pre+Rec)。

5.3 實驗分析

實驗使用的句法分析器是從網上公開下載的SVMstruct-cfg（http://www.cs.cornell.edu/tj/svm-light/svm_struct.htm）。使用經典結構化支持向量機SVM1方法，并與文獻[6]中SVM2方法以及經典的概率上下文無關文法PCFG[2]在語料1和語料2上進行了實驗對比分析。這里的PCFG采用和文獻[5]相同的算法，即規則的概率估計采用最簡單的相對頻率法。結構化支持向量機選取的核函數為線性核，其中懲罰參數C=1.0，參數ε=0.01。在文獻[6]中，在采用SVM2方法進行句法分析時，曾對選取F1損失函數和0-1損失函數進行實驗對比，從實驗結果中發現采用0-1損失函數要比F1損失函數的效果好，故本文在進行結構化支持向量機的實驗時，都選取的是0-1損失函數。實驗結果只采用開放測試的結果，結構化支持向量機的測試時間極短，可以忽略不計，故只對訓練時間進行對比。對比實驗結果如表3、表4所示。其中，Time表示模型在當前語料下的訓練時間。

從表3、表4開放測試的實驗結果可以看出：一階標注、二階標注、三階標注的F1值均高于未進行標注的模型。它們之間在精確率上是三階標注高于二階標注，二階標注高于一階標注。在召回率上有高有低，出現了三階標注的F1值低于二階標注的情況。這是因為產生了數據稀疏的問題，當增加的結構信息越多時，句法分析的性能反而有下降的情況。同時，從表3、表4中可以看到，當增加一階標注時，F1值有明顯的升高，但是增加為二階標注和三階標注，F1值的增加就不太明顯。另外，隨著結構信息的增加F1值會提高，但是需要的訓練時間也在不斷增加，而且語料規模越大，訓練消耗的時間也越來越多。從F1值的對比來看，總的情況是SVM2方法＞SVM1方法＞PCFG方法，但其中也有SVM1方法＞SVM2方法的情況；從語料的訓練時間對比來說，PCFG方法＜SVM1方法＜SVM2方法；因而從算法的F1值和訓練時間雙重考慮的話，增加了一階、二階、三階標注后，SVM1方法要好于SVM2方法和PCFG方法。

Table3 Comparison of experimental resultsofadding structural information in Corpus1表3 北大微型樹庫（語料1）上增加各種結構信息的對比實驗結果

Table4 Comparison of experimental resultsofadding structural information in Corpus2表4 賓州中文樹庫（語料2）上增加各種結構信息的對比實驗結果

6 結束語

中文句法相比較西文來說其結構更加復雜，具有較強的上下文相關性，在進行句法分析時難度更大。本文使用結構化支持向量機的方法并融合多結構信息對中文句法進行分析，豐富了結構化特征函數的形式。同時，本文使用了兩種語料，并對3種句法分析方法在這兩種語料庫上的實驗進行了對比分析，說明增加了結構信息可以在一定程度上提高句法分析的精度。由于對結構化支持向量機在中文信息處理中應用的研究還比較粗淺，在以后很多問題處理中還需要繼續進行深入的探討。

[1]Charniak E.Statistical parsing w ith a context-free grammar and word statistics[C]//Proceedings of the 14th National Conference on Artificial Intelligence and 9th Conference on Innovative Applications of Artificial Intelligence,Providence,USA,Jul27-31,1997.Menlo Park,USA:AAAI,1997:598-603.

[2]Mallning CD,Schutze H.Foundationsof statisticalnaturallanguage processing[M].Cambridge,USA:M ITPress,1999.

[3]Zhang Hao,Liu Qun,BaiShuo.Structural contextconditioned probabilistic parsing of chinese[C]//Proceedings of the 1st Students'Workshop on Computational Linguistics,Beijing,Aug 20-23,2002.Beijing:Chinese Information Processing Society of China,2002:46-51.

[4]Chen Gong,Luo Senlin,Chen Kaijiang,et al.Method for layered Chinese parsing based on subsidiary context and lexical information[J].Journalof Chinese Information Processing,2012,26(1):9-15.

[5]Huang Changning,LiYumei,Zhou Qiang.Implicit information of treebank[J].Journal of Chinese Linguistics,2012(15):149-160.

[6]Zhao Guorong,WangWenjian.AChinese parsingmethod based on interdependent and structured input and output spaes[J].Journal of Chinese Information Processing,2015,29(1):139-145.

[7]Vapnik V.Statictical learning theory[M].New York:John Wiley&Sons,Inc,1998.

[8]Joachims T,Finley T,Yu C N J.Cutting-plane training of structural SVMs[J].Machine Learning,2009,77(1):27-59.

[9]Tsochantaridis I,Hofmann T,Joachims T,etal.Supportvector machine learning for interdependent and structured output spaces[C]//Proceedings of the 21st International Conference on Machine Learning,Banff,Canada,Jul 4-8,2004.New York:ACM,2004:104-112.

[10]Tsochantaridis I,Joachims T,Hofmann T,etal.Largemargin methods for structured and interdependent output variables[J].Journal of Machine Learning Research,2005,6(2):1453-1484.

[11]Joachims T,Hofmann T,Yue Yisong,etal.Predicting structured objectsw ith support vectormachines[J].Communicationsof theACM,2009,52(11):97-104.

[12]Zhou Qiang,Zhang Wei,Yu Shiwen.Building a chinese treebank[J].Journal of Chinese Information Processing,1997,11(4):42-51.

[13]Johnson M.PCFG models of linguistic tree representations[J].Computational Linguistics,2002,24(4):613-632.

[14]CollinsM J.A new statistical parser based on bigram lexical dependencies[C]//Proceedings of the 34th Annual Meeting on Association for Computational Linguistics,Santa Cruz,USA,Jun 24-27,1996.Stroudsburg,USA:ACL,1996:184-191.

附中文參考文獻:

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

[4]陳功,羅森林,陳開江,等.結合結構下文及詞匯信息的漢語句法分析方法[J].中文信息學報,2012,26(1):9-15.

[5]黃昌寧,李玉梅,周強.樹庫的隱含信息[J].中國語言學報,2012(15):149-160.

[6]趙國榮,王文劍.一種處理結構化輸入輸出的中文句法分析方法[J].中文信息學報,2015,29(1):139-145.

[12]周強,張偉,俞士汶.漢語樹庫的構建[J].中文信息學報,1997,11(4):42-51.

ZHAO Guorong was born in 1979.She is a Ph.D.candidate and associate professor at ShanxiUniversity.Her research interests include Chinese information processing andmachine learning,etc.

趙國榮（1979—），女，山西大同人，山西大學博士研究生、副研究員，主要研究領域為中文信息處理，機器學習等。

王文劍（1968—），女，山西太原人，2004年于西安交通大學獲得博士學位，現為山西大學計算機與信息技術學院教授、博士生導師，CCF高級會員，主要研究領域為數據挖掘，機器學習等。

《計算機工程與應用》投稿須知

中國科學引文數據庫（CSCD）來源期刊、北大中文核心期刊、中國科技核心期刊、RCCSE中國核心學術期刊、《中國學術期刊文摘》首批收錄源期刊、《中國學術期刊綜合評價數據庫》來源期刊，被收錄在《中國期刊網》、《中國學術期刊（光盤版）》、英國《科學文摘》（SA/INSPEC）、俄羅斯《文摘雜志》（AJ）、美國《劍橋科學文摘》（CSA）、美國《烏利希期刊指南》（Ulrich’s PD）、《日本科學技術振興機構中國文獻數據庫》（JST）、波蘭《哥白尼索引》（IC），中國計算機學會會刊

《計算機工程與應用》是由中華人民共和國中國電子科技集團公司主管，華北計算技術研究所主辦的面向計算機全行業的綜合性學術刊物。

辦刊方針 堅持走學術與實踐相結合的道路，注重理論的先進性和實用技術的廣泛性，在促進學術交流的同時，推進科技成果的轉化。覆蓋面寬、信息量大、報道及時是本刊的服務宗旨。

報導范圍 行業最新研究成果與學術領域最新發展動態；具有先進性和推廣價值的工程方案；有獨立和創新見解的學術報告；先進、廣泛、實用的開發成果。

主要欄目 理論與研發，大數據與云計算，網絡、通信與安全，模式識別與人工智能，圖形圖像處理，工程與應用，以及其他熱門專欄。

注意事項 為保護知識產權和國家機密，在校學生投稿必須事先征得導師的同意，所有稿件應保證不涉及侵犯他人知識產權和泄密問題，否則由此引起的一切后果應由作者本人負責。

論文要求 學術研究：報道最新研究成果，以及國家重點攻關項目和基礎理論研究報告。要求觀點新穎，創新明確，論據充實。技術報告：有獨立和創新學術見解的學術報告或先進實用的開發成果，要求有方法、觀點、比較和實驗分析。工程應用：方案采用的技術應具有先進性和推廣價值，對科研成果轉化為生產力有較大的推動作用。

投稿格式 1.采用學術論文標準格式書寫，要求文筆簡練、流暢，文章結構嚴謹完整、層次清晰（包括標題、作者、單位（含電子信箱）、摘要、關鍵詞、基金資助情況、所有作者簡介、中圖分類號、正文、參考文獻等，其中前6項應有中、英文）。中文標題必須限制在20字內（可采用副標題形式）。正文中的圖、表必須附有圖題、表題，公式要求用MathType編排。論文字數根據論文內容需要，不做嚴格限制，對于一般論文建議7 500字以上為宜。2.請通過網站（http://www.ceaj.org）“作者投稿系統”一欄投稿（首次投稿須注冊）。

M ethod for Chinese Parsing Based on Fusion ofM ultip le Structural Information*

ZHAOGuorong,WANGWenjian+
Schoolof Computerand Information Technology,ShanxiUniversity,Taiyuan 030006,China

Syntactic parsing is a basic technology of natural language understanding,and it is the cornerstone of deep language understanding.Atpresent,the parsingmethod is based on the hypothesisof context free grammar.In fact,the contexthasa strong correlation in phrase structure trees.If the structural information can be used,itcan further improve the accuracy of the parser.This paper combines themultiple structural information in syntactic structure trees,the structural information(such as father node or leftand rightsister nodes)in the non-term inalnode can strengthen grammar rules of context constraints.And then this paper uses themethod of structural support vector machines(SSVMs)for Chinese parsing.The experimental results show that themethod ofmultiple structural information fusion can resolve the structuralambiguity and improve theaccuracy and F1 value.

structuralsupportvectormachines;context-free grammar;structure contextcorrelation;Chinese parsing

an was born in 1968.She

the Ph.D.degree from Institute for Information and System Science,Xi'an Jiaotong University in 2004.Now she isa professorand Ph.D.supervisoratSchoolof Computerand Information Technology,ShanxiUniversity,and the seniormemberof CCF.Her research interests include datam ining and machine learning theory,etc.

A

：TP391

*The National Natural Science Foundation of China under GrantNos.61273291,61503229(國家自然科學基金);the Natural Science Foundation of Shanxi Province under GrantNo.2015021096(山西省自然科學基金);the Science and Technology Innovation Project of ShanxiProvinceunderGrantNo.2015110(山西省高等學校科技創新項目).

Received 2016-04,Accepted 2016-06.

CNKI網絡優先出版:2016-06-23,http://www.cnki.net/kcms/detail/11.5602.TP.20160623.1139.004.htm l