王文劍,王亞貝

(1.山西大學(xué)計算智能與中文信息處理教育部重點實驗室,山西太原 030006;2.山西大學(xué)計算機與信息技術(shù)學(xué)院,山西太原 030006)

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

王文劍1,2＊,王亞貝2

(1.山西大學(xué)計算智能與中文信息處理教育部重點實驗室,山西太原 030006;2.山西大學(xué)計算機與信息技術(shù)學(xué)院,山西太原 030006)

通過構(gòu)造結(jié)構(gòu)化函數(shù)ψ(x,y),提出一種基于結(jié)構(gòu)化支持向量機(SVM-Struct)的中文句法分析方法.實驗結(jié)果表明,與經(jīng)典的概率上下文無關(guān)文法(PCFG)相比,文章提出的方法在中文句法分析方面是十分有效的.

支持向量機;結(jié)構(gòu)化SVM;中文句法分析

0 引言

句法分析是自然語言處理中的一個重要環(huán)節(jié),同時它也是公認(rèn)的研究難題.許多自然語言處理問題,如機器翻譯、信息獲取、自動文摘等都要依賴句法分析的精確結(jié)果才能最終獲得滿意的解決.隨著信息社會的到來,人們對自然語言處理的要求日益迫切,因而對句法分析的研究具有重要的實際意義.

句法分析的主要任務(wù)是給定一個輸入句子,以語言的語法特征為主要知識源生成一棵短語結(jié)構(gòu)樹,通過樹的形式指明句子各部分之間的關(guān)系.目前為止,句法分析的研究大體分為兩種途徑:基于規(guī)則的方法和基于統(tǒng)計的方法.相比傳統(tǒng)的基于規(guī)則的方法,基于統(tǒng)計的分析方法具有更好的靈活性,在處理歧義等不確定性問題方面都有較好的效果[1].

概率上下文無關(guān)文法(PCFG)是把統(tǒng)計方法引入到上下文無關(guān)語法而形成的語法規(guī)則系統(tǒng)[2],然而經(jīng)典的PCFG實際上是建立在一些非常理想化的獨立性假設(shè)基礎(chǔ)上,而這些假設(shè)對于實際問題往往不能滿足,因此PCFG的實際應(yīng)用效果并不理想.由Vapnik等人[3]提出的支持向量機(Support Vector Machine,SVM)具有完美的數(shù)學(xué)形式、直觀的幾何解釋和良好的泛化能力,是一個通用有效的學(xué)習(xí)方法,目前已成功運用在自然語言處理的任務(wù)中,如英語詞性標(biāo)注、英語專名識別和文本分類等方面,并在這些領(lǐng)域都取得了不錯的效果[4].然而中文句法分析要處理的數(shù)據(jù)具有復(fù)雜的結(jié)構(gòu),傳統(tǒng)的支持向量機已經(jīng)不適應(yīng)解決此類問題.

2004年Hofmann和Joachim s等針對實際應(yīng)用中大部分要處理的數(shù)據(jù)往往具有比較復(fù)雜且彼此之間存在相互依賴關(guān)系的復(fù)雜特性(如樹形結(jié)構(gòu)、隊列結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)等),對傳統(tǒng)支持向量機進行了改進,首次提出結(jié)構(gòu)化支持向量機(SVM-Struct)[5],該方法通過結(jié)構(gòu)化函數(shù)ψ(x,y),并結(jié)合分解、選塊思想來實現(xiàn)對大規(guī)模復(fù)雜數(shù)據(jù)的分析.Joachim s等人之后對結(jié)構(gòu)化支持向量機進行了改進,提出n-Slack Formulation等算法來提高SVM-Struct的速率[6].Thomas G.Detterich等人認(rèn)為結(jié)構(gòu)化支持向量機研究在未來十年都會有很好的發(fā)展及應(yīng)用前景[7].

由于中文句法分析的數(shù)據(jù)集具有豐富的內(nèi)部結(jié)構(gòu),同時結(jié)構(gòu)化支持向量機對處理復(fù)雜結(jié)構(gòu)數(shù)據(jù)的高效性,所以本文探索將結(jié)構(gòu)化支持向量機學(xué)習(xí)方法應(yīng)用于中文句法分析領(lǐng)域,仿真實驗獲得了較為滿意的結(jié)果.

1 SVM-Struct學(xué)習(xí)方法簡介

支持向量機SVM(Support Vector Machine)是新型機器學(xué)習(xí)方法,具有完備的統(tǒng)計學(xué)理論基礎(chǔ),它采用結(jié)構(gòu)風(fēng)險最小化原則代替?zhèn)鹘y(tǒng)統(tǒng)計學(xué)的基于大樣本的風(fēng)險最小化原則,具有出色的學(xué)習(xí)和推廣能力.但在實際應(yīng)用中,大部分要處理的數(shù)據(jù)(如樹形結(jié)構(gòu)、隊列結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)等)都是比較復(fù)雜彼此之間存在相互依賴,具有特定結(jié)構(gòu)化關(guān)系的,而用傳統(tǒng)的支持向量機已經(jīng)很難去處理這些問題了,因此,結(jié)構(gòu)化支持向量機(SVM-Struct)根據(jù)數(shù)據(jù)內(nèi)部的結(jié)構(gòu)性提出結(jié)構(gòu)化函數(shù)ψ(x,y)對傳統(tǒng)的支持向量機進行了改進,能有效地處理結(jié)構(gòu)化數(shù)據(jù).

結(jié)構(gòu)化數(shù)據(jù)分析問題的目的是要找到樣本的輸入與輸出對之間的一個函數(shù)f:X→Y假定函數(shù)f的形式為:

其中F是判別函數(shù):F(x,y;w)=〈w,ψ(x,y)〉,w是權(quán)向量,ψ(x,y)是結(jié)合輸入與輸出數(shù)據(jù)特性提取出來的代表著輸入輸出彼此之間特性合并的一個向量.一般ψ(x,y)的形式取決于具體要解決的結(jié)構(gòu)化問題.

SVM-Struct通過訓(xùn)練得到w權(quán)向量,使:

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

班級也是一個社會的組織，班主任可以將大學(xué)生職業(yè)生涯規(guī)劃整合到班級建設(shè)中，例如：開展班級面試大賽、職業(yè)理想演講比賽、班級社會實踐，優(yōu)秀畢業(yè)生交流等班級建設(shè)活動，將職業(yè)生涯規(guī)劃融入到學(xué)生生活中，幫助學(xué)生畢業(yè)時能盡快適應(yīng)職場生活。

采用最大間隔法[8],引入松弛變量[9]的最優(yōu)化問題為:

由于實際問題中|y|往往很大,以上形式不適合解決此類問題,所以在約束條件中引入了損失函數(shù):

或者 ?i,?y∈Yyi:〈w,δΨi(y)〉≥Δ(yi,y)-ξ(5)

最優(yōu)化問題(3)的對偶形式為:

其中αiy是拉格朗日乘子.對于軟間隔,還另外有組約束條件:

在SVM-Struct方法中,其重點也是難點的是ψ(x,y)函數(shù)的構(gòu)造,對于實際應(yīng)用問題,ψ(x,y)構(gòu)造的合適與否將直接影響SVM-Struct方法的有效性.

2 基于SVM-Struct的中文句法分析

目前中文句法分析研究中常采用兩類方法,一類是淺層句法分析,也叫部分句法分析或語塊分析,主要任務(wù)是語塊的識別和分析.另一類是完全句法分析,通過一系列分析過程,最終得到句子的完整的語法樹.本文的研究方法屬于完全句法分析,它基于SVM-Struct方法,主要通過構(gòu)造結(jié)構(gòu)化函數(shù)ψ(x,y),對中文句法進行分析,最終得到句子的完整語法樹.

其中αi(i=1…n)指所對應(yīng)的語法規(guī)則出現(xiàn)的次數(shù),n指所涉及的語法規(guī)則的總個數(shù).一個句法分析示例及對應(yīng)的ψ(x,y)如圖1所示.

圖1 (a)中文句法分析示例;(b)對應(yīng)的ψ(x,y)Fig.1 (a)Illustration of Chinese parsing;(b)Correspondingψ(x,y)

一個句子樣本x通過函數(shù)f(x;w)=argy∈mYa xF(x,y;w)得出與之對應(yīng)的句法樹y,其中F(x,y;w)=〈w,ψ(x,y)〉.本文所用到的漢語詞類標(biāo)注及漢語短語標(biāo)注見表1[1]和表2[1].

表1 漢語詞類標(biāo)注Table 1 Chinese part of speech tagging

表2 漢語短語標(biāo)注Table 2 Chinese phrase tagging

句法樹y中的每個結(jié)點對應(yīng)著語法規(guī)則gj以及權(quán)值w j.句法樹y中所有結(jié)點對應(yīng)的w j的總和將代表著將樣本x分類為y的一個評價值.這個值可以通過函數(shù)F(x,y;w)=〈w,ψ(x,y)〉得到,其中ψ(x,y)列向量中的每個元素對應(yīng)著句法樹y中每個gj所出現(xiàn)的次數(shù).然后通過式(1)最大化函數(shù)F,就可以得到正確的y.

基于SVM-Struct的中文句法分析算法的主要步驟如下:

Step1:輸入訓(xùn)練樣本(x1,y1),…,(xn,yn),設(shè)置參數(shù)C,ε,并選定損失函數(shù)類型,即為Δ(yi,y).

Step2:初始化工作集Si為空集,i=1,(i=1,…,n).

Step3:按式(4)計算H(y)≡(1-〈δΨi(y),w〉)Δ(yi,y),其中w≡∑j∑y′∈Sjαiy′δΨj(y′).

Step4:計算出^y=arg maxy∈Y H(y).

Step5:計算得出ξi=max{0,maxy∈Si H(y)},如果H(^y)＞ξi+ε,那么Si←Si∪{^y},S= ∪i Si,在S上進行二次優(yōu)化更新αs,并繼續(xù)返回到Step3進行優(yōu)化,否則轉(zhuǎn)到Step6.

Step6:輸入測試數(shù)據(jù)集根據(jù)訓(xùn)練得出的權(quán)值進行分類測試并輸出測試結(jié)果.

3 實驗結(jié)果與分析

本文實驗所用數(shù)據(jù)來自北京大學(xué)計算語言學(xué)研究所公開的微型語料庫中的樹庫樣例(1434句),句長大約都在5-20個詞之間.本文首先按照SVM-Struct方法重寫訓(xùn)練句子.如句子“北京在黃河北面”的樹庫格式為:

由于本文重點在于驗證SVM-Struct算法在中文句法分析中的可行性,所以選取了其中一部分?jǐn)?shù)據(jù)作為實驗數(shù)據(jù).將50條句子作為訓(xùn)練數(shù)據(jù)集,并從樹庫中隨機抽取50條句子作為測試數(shù)據(jù)集來驗證結(jié)構(gòu)化支持向量機在中文句法分析上的可行性以及有效性.

實驗采用的評價準(zhǔn)則主要有準(zhǔn)確率(Accuracy)和F1[1],其定義分別為:其中,TP、TN、FP、TN指一個預(yù)測可能產(chǎn)生的四種結(jié)果,TP(Ture Positive)指正確的肯定;TN(Ture Negative)指正確的否定;FP(False Positive)指錯誤的肯定;FN(False Negative)指錯誤的否定.

實驗首先統(tǒng)計訓(xùn)練數(shù)據(jù)集中出現(xiàn)的語法規(guī)則以及出現(xiàn)的次數(shù),結(jié)果見表3.

表3 訓(xùn)練數(shù)據(jù)集中出現(xiàn)的語法規(guī)則及頻次Table 3 Grammatical rules and frequencies in training dataset

實驗中,設(shè)置懲罰參數(shù)C=1.0及參數(shù)ε=0.01,并選用兩種損失函數(shù)的SVM-Struct算法即SVM1和SVM(其中SVM1采用0——1損失;SVM采用F1損失,F1的定義式見式(11),其中Δ(yi,y)=(1-F1(yi,y)).與傳統(tǒng)的概率上下文無關(guān)文法PCFG進行比較.三種方法訓(xùn)練和測試的結(jié)果見表4.

表4 采用三種方法進行句法分析的實驗結(jié)果Table 4 Experiment results by three Chinese parsing approaches

從實驗結(jié)果可以看出,選用SVM-Struct算法進行的句法分析無論從準(zhǔn)確率Accuracy還是F1測量值都要優(yōu)于PCFG分析方法,盡管運行時間比PCFG方法稍慢但也是在我們可以接受范圍內(nèi)的,由此可以得出,在中文句法分析問題中SVM-Struct能夠有效地利用傳統(tǒng)SVM高泛化性能的優(yōu)勢.另外SVM1在準(zhǔn)確率Accuracy上較高于SVMΔs1,但從F1測量值來看,SVMΔs1要優(yōu)于其他兩種算法.因此,在結(jié)構(gòu)化支持向量機中,損失函數(shù)將會影響F1測量值.在實際問題中,我們可以根據(jù)特定的處理對象來選擇合適的損失函數(shù)及SVM的核函數(shù)與參數(shù),從而進一步得到更為優(yōu)秀的學(xué)習(xí)模型.

4 結(jié)論及展望

本文基于SVM-Struct,通過分析結(jié)構(gòu)化輸入數(shù)據(jù)與輸出數(shù)據(jù)的特征對應(yīng)關(guān)系,構(gòu)造結(jié)構(gòu)化函數(shù)ψ(x,y),將結(jié)構(gòu)化支持向量機算法應(yīng)用在自然語言處理中的中文句法分析.本文通過選用不同的損失函數(shù)對數(shù)據(jù)進行測試,實驗結(jié)果表明結(jié)構(gòu)化支持向量機算法在中文句法分析中的可行性及有效性.盡管SVM-Struct對結(jié)構(gòu)化數(shù)據(jù)具有較好的學(xué)習(xí)性能及應(yīng)用性,但本文基于SVM-Struct的中文句法分析的研究是初步的,另外由于目前中文樹庫資源還非常稀少,因此我們的實驗結(jié)果可能存在一定片面性.今后如何通過增大實驗數(shù)據(jù)以及增加評價指標(biāo)使其中文句法分析更深入還有待于進一步研究.

[1] Christopher D.Manning,Hinrich Schutze,Foundations of Statistical Natural Language Processing[M].Cambridge,M IT Press,1999.

[2] 林穎,史曉東,郭峰.一種基于概率上下文無關(guān)文法的漢語句法分析[J].中文信息學(xué)報,2006,20(2):1-7:32.

[3] Vapnik V.Statictical Learning Theory[M].New York:Wiley,1998:11-23.

[4] 李珩,朱靖波,姚天順.基于SVM的中文組塊分析[J].中文信息學(xué)報,2004,18(2):1-7.

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

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

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

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

[9] Crammer K,Singer Y.On the Algorithmic Implementation of Multi-Class Kernel-Based Vector Machines[J].Journal of Machine Learning Research,2001,2:265-292.

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

Chinese Parsing Based on Structural Support Vector Machine

WANG Wen-jian1,2,WANG Ya-bei2
(1.Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education,Taiyuan030006,China;
2.School of Computer and Information Technology,Shanxi University,Taiyuan030006,China)

A structural support vector machine(SVM-Struct)approach for Chinese parsing was introduced by constructing structural functionψ(x,y).Comparing with the traditional probabilistic context free grammar(PCFG),the experiment results demonstrate that the proposed SVM-Struct approach is effective for Chinese parsing.

support vector machine;SVM-Struct;Chinese parsing

TP181

A

0253-2395(2011)01-0066-05＊

2010-07-28;

2010-10-18

國家自然科學(xué)基金(60975035);教育部博士點基金(20091401110003);教育部科學(xué)技術(shù)研究重點項目(208021);山西省自然科學(xué)基金(2009011017-2);山西省回國留學(xué)人員科研資助項目(2008-14)

王文劍(1968-),女,山西太原人,博士,教授,博士生導(dǎo)師,主要從事機器學(xué)習(xí)、計算智能等的研究.E-mail:w jwang@sxu.edu.cn