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

王文劍,王亞貝

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一個(gè)句子樣本x通過函數(shù)f(x;w)=argy∈mYa xF(x,y;w)得出與之對(duì)應(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中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)著語法規(guī)則gj以及權(quán)值w j.句法樹y中所有結(jié)點(diǎn)對(duì)應(yīng)的w j的總和將代表著將樣本x分類為y的一個(gè)評(píng)價(jià)值.這個(gè)值可以通過函數(shù)F(x,y;w)=〈w,ψ(x,y)〉得到,其中ψ(x,y)列向量中的每個(gè)元素對(duì)應(yīng)著句法樹y中每個(gè)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)計(jì)算H(y)≡(1-〈δΨi(y),w〉)Δ(yi,y),其中w≡∑j∑y′∈Sjαiy′δΨj(y′).

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

實(shí)驗(yàn)首先統(tǒng)計(jì)訓(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í)驗(yàn)中,設(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進(jìn)行比較.三種方法訓(xùn)練和測試的結(jié)果見表4.

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

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

4 結(jié)論及展望

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

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

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

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

[4] 李珩,朱靖波,姚天順.基于SVM的中文組塊分析[J].中文信息學(xué)報(bào),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)語法的自動(dòng)句法分析方法[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);教育部博士點(diǎn)基金(20091401110003);教育部科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(208021);山西省自然科學(xué)基金(2009011017-2);山西省回國留學(xué)人員科研資助項(xiàng)目(2008-14)

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