一種處理結構化輸入輸出的中文句法分析方法

趙國榮,王文劍

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

?

一種處理結構化輸入輸出的中文句法分析方法

趙國榮,王文劍

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

中文句法結構復雜，特征維數較高，目前已知最好的漢語句法分析效果與其他西方語言相比還有一定的差距。為進一步提高中文句法分析的效率和精度，該文提出一種采用二階范數軟間隔優化的結構化支持向量機(Structural Support Vector Machines, Structural SVMs)方法對基于短語結構的中文句法進行分析，通過構造結構化特征函數ψ(x,y)，體現句法樹的輸入信息，并根據中文句子本身具有的強相關性，在所構造的ψ(x,y)中增加中文句法分析樹中父節點的信息，使ψ(x,y)包含了更加豐富的結構信息。在賓州中文樹庫PCTB上的實驗結果表明，該文方法與經典結構化支持向量機方法以及BerkeleyParser相比可取得較好的效果。

中文句法分析；加權上下文無關文法；結構化SVM；二階范數軟間隔優化

1 引言

句法分析是自然語言處理中一個重要的環節，句法分析的結果直接決定著信息檢索、信息抽取、機器翻譯和自動文摘等自然語言處理系統的最終性能，也是語用、語義等自然語言處理深層研究的基礎。所謂句法分析是根據給定的語法[1]，自動地推導出句子所包含的句法單位和這些句法單位之間的關系，即句子的語法結構。句法分析要遵循某一語法體系，根據該體系的語法確定語法樹的表示形式。目前，在句法分析中使用比較廣泛的有短語結構語法和依存語法，前者(特別是上下文無關語法)應用最為廣泛。

句法分析方法的研究大體分為兩種途徑： 基于規則的方法[2]和基于統計的方法[3-4]。前者從漢語句子最本質的特征出發，規則相對穩定且易于表達漢語句子成分的構成規律，方法也較成熟，但是規則的獲取過程十分繁瑣，句法分析的歧義問題很難解決，常會出現不穩定以及規則沖突等問題。基于統計的句法分析方法具有效率高、魯棒性好的優點，可以有效地消除語言現象中的各種歧義現象，但是在處理高維數據時效果不太理想。由Vapnik等人[5]提出的支持向量機(Support Vector Machine, SVM)具有簡潔的數學形式、成熟的求解方法和良好的泛化能力，尤其處理高維數據具有較強的優勢，在自然語言處理領域被廣泛應用。但是傳統的SVM訓練效率偏低，在處理結構復雜的數據時有一定局限性，對輸出的結果也不能從概率上進行解釋。

Hofmann和Joachims等人在2004年[6]針對實際應用中數據具有比較復雜的結構，而且數據本身存在相互依賴關系(如隊列結構、樹形結構或網狀結構等數據)，改進了傳統支持向量機，首次提出結構化支持向量機學習方法，并將其應用于英文句法分析中，取得了較好的效果。由于結構化支持向量機處理復雜結構這一特點，有望在未來10年在多個應用領域得到廣泛應用[7]。

中文句子結構復雜，詞類和句法成分之間的關系錯綜復雜，同一詞類可擔任多種句法成分并且無形態變化，還有兼類詞等問題，實現中文句法分析要更困難一些。文獻[8]直接引入經典的結構化支持向量機方法進行中文句法分析，結構特征函數的構造也僅僅是句法規則的抽取以及規則出現的頻次統計，但所取得的實驗結果說明了Structural SVMs進行中文句法分析的可行性和有效性。本文采用二階范數軟間隔優化形式的結構化支持向量機，同時由于中文句法結構具有較強相關性，在特征構造上引入短語結構樹中父節點的信息，使特征函數的構成信息更加豐富。在賓州中文樹庫PCTB上進行中文句法分析實驗，并和文獻[8]方法以及Berkeley Parser[9]的實驗結果進行了分析比較。

2 優化的結構化支持向量機學習模型

2.1 結構化支持向量機模型

結構化支持向量機是基于判別式的模型，結構化數據分析問題的目的是要構造出樣本的輸入與輸出對之間的一個映射函數f：X→Y，在句法分析中f給定輸入句子X到輸出短語結構樹Y的一個映射。構造函數f的一個重要任務是需要學習一個基于輸入/輸出對的判別式函數F:X×Y→，通過對輸出變量的最大化，實現對輸出結果的預測。設Structural SVMs的目標函數為[6,10]：

F是基于輸入/輸出組合特征表示ψ(x,y)的線性函數，如式 (2)所示。

這里，w是權向量，ψ(x,y)的形式取決于具體要解決問題。以句法分析為例，句子x的句法分析樹y中的每一個結點對應一個規則gj，相應的規則對應一個權值ωj。對于一個句子x的有效句法樹y，每一個結點的權值ωj的和作為這個句法樹的分值，計算分值的函數為F(x,y;w)=〈w,ψ(x,y)〉。 對于給定的句子x，通過CKY(Cocke-Younger-Kasami)算法[1]找出符合文法的句法分析樹集Y，從中找出分值最大的F(x,y,w),y∈Y，即為句子的語法樹。對于Structural SVMs，最關鍵的是特征函數ψ(x,y)的構造。

2.2 二階范數軟間隔優化

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

(3)式可以等價轉換為：

其中定義δΨi(y)≡Ψ(xi,yi)-Ψ(xi,y)。

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

在式(5)中引入松弛變量的軟間隔，以容忍部分噪聲和離群點，并兼顧更多的訓練點，而不只是靠近邊界的那些點。松弛變量軟間隔的形式可以是一階的，也可以是二階的，它的泛化性的好壞和實際數據有關，文獻[8]使用一階的形式，在本文使用二階范數軟間隔優化形式[11]：

(6)

?i,?y∈Yyi:〈w,δψi(y)〉≥1-ξi,s.t.?i,ξi≥0

這里常量C>0，用來平衡訓練錯誤最小化和間隔最大化。

在實際問題中常常把損失函數引入到約束條件中，因為偏離標準值大的點更應調整，即具有高損失的點更應受到懲罰。所以在式(6)的約束條件中引入了損失函數：

(7)

除了對松弛變量進行再調整外，還可針對間隔進行再調整，得到以下優化問題：

(8)

優化問題(6)、(7)、(8)可分別通過相對應的對偶形式進行求解。

在解決二次凸優化問題中，最大的困難就是遇到規模很大的約束條件，用常規的優化方法很難求解[12]。而對于句法分析，每個可能的句法分析樹y都會對應一個約束，因而會產生規模非常大的約束條件，甚至可能達到指數級數量的約束，但是考慮到大間隔問題的特殊結構，實際上在指數級數量的約束集合中只需要非常少的約束即可求解問題，依據這個特性可以將指數級的約束數量減少為多項式數量集。最大間隔方法通過構造初始優化問題的一個嵌套序列的不斷緊密的松弛，從而可保證產生一個足夠精確的近似解。

3 基于優化的結構化支持向量機中文句法分析方法

句法分析的任務是對于給定的輸入句子，生成一棵與之對應的句法樹。句法分析的過程主要有兩步： 首先判斷進行句法分析的句子在句法上是否正確，然后對于句法正確的句子，輸出其短語結構樹。

本文采用短語結構的句法分析，將文法限定為喬姆斯基范式的形式[1]，所有的語法規則為：nl[A→BC]或者nl[A→α]的形式，這里A、B、C是非終結符，α是終結符，并且每一條規則都對應相應的權值wl，并將其稱之為加權上下文無關文法。假定x為給定的句子，針對x的分析結果為若干個句法樹用Y表示，最佳分析樹設為h(x)，rules(y)代表每棵句法樹y中所有的語法規則的集合，加權上下文無關文法模型的形式如式(9)所示。

加權上下文無關文法模型中引入結構化特征函數ψ(x,y)，則

其中ψ(x,y)表示規則及規則出現的次數，w表示統計學習中訓練得到的權值。

3.1 結構化特征函數ψ(x,y)的構造

在結構化支持向量機方法中，特征函數ψ(x,y)的構造是重點和難點，在實際應用中，ψ(x,y)構造的合適與否直接影響結構化支持向量機方法的有效性。

中文句子具有很強的上下文相關性,對于詞語的序列來說，出現在序列前或后的詞語都會對確定句子序列有所幫助。所以本文在構造特征函數時，加入了短語結構樹中父節點信息，以豐富特征函數的結構信息。圖1為中文句法分析的輸入輸出示例，圖2為本文增加父節點信息后針對中文句法分析構造的ψ(x,y)。

輸入x： 秘魯僑胞舉行新年晚會

f:x→y

輸出y：

圖1 句法分析輸入輸出示例圖

3.2 基于結構化輸入輸出的中文句法分析算法

首先使用求解結構化支持向量機中文句法分析任務的近似優化算法對訓練數據進行訓練，得到相應的權值。對于測試數據，首先使用CKY算法，對每一條輸入的句子分析出符合語法規則的句法樹集[13]，然后使用加權上下文無關文法摸型，將訓練得到的權值帶入式(9)，求出最佳分析樹。

基于結構化輸入輸出的中文句法分析算法的主要步驟如下：

step1： 輸入訓練樣本(x1,y1),…(xn,yn)，設置參數C,ε

step2： 初始化工作集Si為null，i=1,...,n.

4 實驗結果分析

4.1 評價指標

對句法分析模型的評價是句法分析研究的一項重要內容，在句法分析中，PARSEVAL句法分析評價體系被認為是一種粒度適中較為理想的評價方法，在句法分析系統中被廣泛使用[1]，它主要由精確率、召回率兩部分組成。

對于一組需要分析的句子，假設語料庫中對這組句子標注的所有成分的集合為目標集，句法分析系統實際分析出的句子成分為分析集，分析集和目標集的交集為共有集，即正確識別出的句子成分的數量。精確率是衡量句法分析系統分析的所有成分中正確的成分的比例，召回率是衡量句法分析系統分析的所有正確成分在實際成分中的比例，F1用來協調精確率和召回率。它們分別定義如式(11)～(13)所示。

4.2 實驗語料

本文使用PCTB賓州中文樹庫語料，從它的1 500個文檔中提取出2 000條(句長小于等于12詞)單句，其中的1 850句用來進行訓練，從訓練集中抽取150句用來進行封閉測試，除訓練集之外的150句用來進行開放測試，稱為語料1，進行簡單句的實驗；然后又提取300句復雜句(平均句長為26)，其中250句用來訓練，50句用來進行開放測試，稱為語料2，進行復雜句的對比實驗。本實驗采用線性核[14]k=u*v，其中懲罰參數C=1.0，參數ε=0.01。

4.3 對實驗語料的處理

在做本實驗時，本文將從賓州中文樹庫選出來的2 000個單句進行實驗處理，將句法樹上原有的空語類、指同索引和功能標記一概刪除[15]。

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

A

((IP-HLN (NP-SBJ (NP-PN (NR 秘魯))

(NP (NN 僑胞)))

(VP (VV 舉行)

(NP-OBJ (NT 新年)

(NN 晚會)))))

B

((S (NP (NR 秘魯)

(NN 僑胞))

(VP (VV 舉行)

(NP (NT 新年) (NN 晚會)))

))

4.4 兩種損失函數實驗結果的比較

采用語料1先進行簡單句的實驗，分別使用SVM2、ΔS_SVM2、ΔM_SVM2在加注父節點的情況下對中文句法進行分析，并選用0-1損失和F1損失進行實驗，實驗結果如表1與表2所示。

表1 采用0-1損失的三種方法的實驗結果比較

表2 采用F1損失的三種方法的實驗結果比較

從表1與2可以看出，采用0-1損失的SVM2、ΔS_SVM2、ΔM_SVM2三種方法的訓練時間均比使用F1損失的三種方法耗費的時間少，而且在0-1損失下SVM2訓練時間是最少的。由于測試數據需要的時間非常短，消耗的時間基本差不多，所以沒有對三種方法的測試時間進行對比。

在封閉測試中，三種方法各自相比均是采用0-1損失的效果好。在開放測試中，SVM2和ΔM_SVM2方法采用0-1損失的開放測試的結果比使用F1損失的效果好，ΔS_SVM2方法是采用F1損失的開放測試結果比使用0-1損失的效果好。總體來看，使用三種方法對中文句法進行分析，即是采用0-1損失比采用F1損失總的效果要好。

在表1采用0-1損失的方法比較中，SVM2方法在封閉測試和開放測試中F1值均排在第二，使用的訓練時間是最少的；ΔS_SVM2方法封閉測試中F1值排在第一，開放測試中F1值卻排在第三，但是和SVM2方法開放測試的F1值非常接近，然而使用的訓練時間最多；ΔM_SVM2方法是F1值在封閉測試排在第三，開放測試的F1值排在第一，使用訓練時間在其它兩種方法之間。所以綜合來看，使用SVM2方法測試的效果居中，比較穩定，訓練時間用時最短。

采用語料2進行復雜句的實驗，從對表1～2的分析中可以看到采用0-1損失比采用F1損失的實驗效果好，故針對復雜句的實驗采用0-1損失，SVM2、ΔS_SVM2、ΔM_SVM2三種方法的結果比較如表3所示。

表3 采用0-1損失復雜句實驗結果比較

相對于簡單句而言，復雜句不僅是句子的長度增加了，而且句子的結構也變得更加復雜，句法分析樹的深度也相應增加。即使采用結構化支持向量機的方法對復雜句進行句法分析，效果也不太理想。但僅是對SVM2、ΔS_SVM2、ΔM_SVM2三種方法進行比較的話，在對復雜句的分析中，SVM2方法的實驗結果更好一些。當針對復雜句時，約束條件越少，反而效果更好一些。

4.5 不同模型的實驗結果比較

文獻[8]采用的是經典的結構化支持向量機方法對中文句法進行分析，特征函數的構造也較簡單。BerkeleyParser是一個純粹的基于PCFG[16]方法的句法分析器，目前比較成熟，應用也比較廣泛，而且PCFG方法可以看成加權上下文無關文法的一個特例。所以將這兩個模型與本文提出的方法進行比較，以驗證本文所提方法的有效性。實驗語料采用的是語料1。

在0-1損失的情況下，BerkeleyParser、文獻[8]方法與SVM2(增加了父節點信息)模型實驗結果比較如表3所示。

表4 三種模型的實驗結果比較

從表4可以看出，SVM2(增加了父節點信息)方法在封閉測試上的F1值略低于Berkeley Parser，但是在開放測試F1值又比Berkeley Parser略好。文獻[8]在三個指標上的值均比較差，其原因是它的特征函數的構造比較簡單，ε的值采用的是絕對值的形式，而本文SVM2方法在特征函數的構造上增加了父節點的信息，ε值采用平方項的形式更適合中文句法分析應用。但是從表中可以看到本文和文獻[8]所使用的訓練時間比Berkeley Parser少很多。

5 結束語

句法分析在信息處理中處于重要地位，它的效果的好壞，直接影響機器翻譯、自動文摘、信息獲取等的處理效果，因而對句法分析的研究有很重要的意義。本文采用結構化支持向量機的方法對中文句法進行分析，主要針對單句進行了實驗分析，也對復雜的句子進行簡單的實驗分析，從結果上看，取得了令人滿意的效果，也驗證了使用結構化支持向量機對中文句法進行分析的可行性。由于結構化支持向量機在中文信息處理中應用還處于探索階段，很多問題還需要繼續進行深入的探討和研究。

[1] Manning C D, Schutze H. Foundations of statistical natural language processing [M]. London: the MIT Press, 1999.

[2] 馮志偉.基于短語結構語法的自動句法分析方法[J].當代語言學，2000, 2(2): 84-98.

[3] 馬金山. 基于統計方法的漢語依存句法分析研究[D].哈爾濱:哈爾濱工業大學,2007.

[4] 吳偉成,周俊生, 曲維光. 基于統計學習模型的句法分析方法綜述[J].中文信息學報.2013,27(3):9-19.

[5] Vapnik V. Statictical Learning Theory [M].New York: Wiley, 1998.

[6] Tsochantaridis I, Hofmann T, Joachims T, et al. Support Vector Machine Learning for Interdependent and Structured Output Spaces[C]//Proceedings of the twenty-first International Conference on Machine Learning, 2004:104-112.

[7] Dietterich G H, Domingos P, Getoor L. Structured Machine Learning: the next ten years [J], Machine Learning, 2008, 73(1):3-23.

[8] 王文劍,王亞貝. 基于結構化支持向量機的中文句法分析[J].山西大學學報(自然科學版). 2011, 1: 66-72.

[9] http://code.google.com/p/berkeleyparser/

[10] T Joachims, T Hofmann, Yisong Yue, et al. Predicting Structured Objects with Support Vector Machines[J], Communications of the ACM, Research Highlight, November, 2009，52(11):97-104.

[11] Tsochantaridis I, Joachims T, Hofmann T, et al. Large Margin Methods for Structured and Interdependent Output Variables [J]. Journal of Machine Learning Research, 2005, 9: 1453-1484.

[12] Joachims T, Finley T, Chun-Nam Yu. Cutting-Plane Training of Structural SVMs [J]. Machine Learning, 2009, 77(1):27-59.

[13] Eugene C, Mark J. Coarse-to-fine n-best parsing and MaxEnt Discriminative reranking[C]//Proceedings of the 43rd Annual Meeting of the ACL, 2005:173-180.

[14] Nello C, John S T. An Introduction to SVM and Other Kernel-based Learning Methods [M].北京:電子工業出版社,2004.

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

[16] Collins M J．A new statistical parser based on bigram lexical Dependencies [C]//Proceedings of ACL, 1996: 184-191．

A Chinese Parsing Method Based on Interdependent and Structured Input and Output Spaces

ZHAO Guorong，WANG Wenjian

(School of Computer and Information Technology, Shanxi University, Taiyuan, Shanxi 030006, China)

Chinese syntax has complex structure and high dimension features, and the best known Chinese parsing performance is still inferior to that of other western languages. In order to improve the efficiency and accuracy of Chinese parsing，we propose a L2-norm soft margin optimization structural support vector machines (structural SVMs) approach. By constructing the structural functionψ(x,y),theinputinformationofsyntactictreecanbemappedwell.SinceChinesesyntaxhasastrongcorrelation,weusefathernodeofphrasestructuretreestoenrichthestructureinformationofψ(x,y).TheexperimentresultsonthebenchmarkdatasetofPCTBdemonstratethattheproposedapproachiseffectiveandefficientcomparedwithclassicalStructuralSVMsandBerkeleyParsersystem.

Chinese parsing; weighted context-free grammars; Structural SVMs; L2-norm soft margin optimization

趙國榮(1979—)，博士研究生，講師，主要研究領域為自然語言處理、機器學習等。E?mail：zhaogr@sxu．edu．cn王文劍(1968—)，博士，教授、博士生導師，主要研究領域為神經網絡、支持向量機、機器學習理論、環境計算等。E?mail：wjwang@sxu．edu．cn

1003-0077(2015)01-0139-07

2013-05-06 定稿日期： 2014-07-23

國家自然科學基金(60975035，61273291)；山西省回國留學人員科研資助項目(2012-008)

TP

A