一種處理結(jié)構(gòu)化輸入輸出的中文句法分析方法

趙國榮,王文劍

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

?

一種處理結(jié)構(gòu)化輸入輸出的中文句法分析方法

趙國榮,王文劍

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

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

中文句法分析；加權(quán)上下文無關(guān)文法；結(jié)構(gòu)化SVM；二階范數(shù)軟間隔優(yōu)化

1 引言

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

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

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

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

2 優(yōu)化的結(jié)構(gòu)化支持向量機學習模型

2.1 結(jié)構(gòu)化支持向量機模型

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

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

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

2.2 二階范數(shù)軟間隔優(yōu)化

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

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

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

采用最大間隔法可以將式(4)轉(zhuǎn)化為一個凸二次規(guī)劃形式的最優(yōu)化問題：

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

(6)

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

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

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

(7)

除了對松弛變量進行再調(diào)整外，還可針對間隔進行再調(diào)整，得到以下優(yōu)化問題：

(8)

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

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

3 基于優(yōu)化的結(jié)構(gòu)化支持向量機中文句法分析方法

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

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

加權(quán)上下文無關(guān)文法模型中引入結(jié)構(gòu)化特征函數(shù)ψ(x,y)，則

其中ψ(x,y)表示規(guī)則及規(guī)則出現(xiàn)的次數(shù)，w表示統(tǒng)計學習中訓練得到的權(quán)值。

3.1 結(jié)構(gòu)化特征函數(shù)ψ(x,y)的構(gòu)造

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

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

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

f:x→y

輸出y：

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

3.2 基于結(jié)構(gòu)化輸入輸出的中文句法分析算法

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

基于結(jié)構(gòu)化輸入輸出的中文句法分析算法的主要步驟如下：

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

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

4 實驗結(jié)果分析

4.1 評價指標

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

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

4.2 實驗語料

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

4.3 對實驗語料的處理

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

例如，下面的例句A要刪除轉(zhuǎn)換成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 兩種損失函數(shù)實驗結(jié)果的比較

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

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

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

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

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

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

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

表3 采用0-1損失復(fù)雜句實驗結(jié)果比較

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

4.5 不同模型的實驗結(jié)果比較

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

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

表4 三種模型的實驗結(jié)果比較

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

5 結(jié)束語

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

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

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

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

[4] 吳偉成,周俊生, 曲維光. 基于統(tǒng)計學習模型的句法分析方法綜述[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] 王文劍,王亞貝. 基于結(jié)構(gòu)化支持向量機的中文句法分析[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].北京:電子工業(yè)出版社,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—)，博士研究生，講師，主要研究領(lǐng)域為自然語言處理、機器學習等。E?mail：zhaogr@sxu．edu．cn王文劍(1968—)，博士，教授、博士生導(dǎo)師，主要研究領(lǐng)域為神經(jīng)網(wǎng)絡(luò)、支持向量機、機器學習理論、環(huán)境計算等。E?mail：wjwang@sxu．edu．cn

1003-0077(2015)01-0139-07

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

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

TP

A