基于主動(dòng)學(xué)習(xí)的中文依存句法分析

車(chē)萬(wàn)翔，張梅山，劉 挺

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院 社會(huì)計(jì)算與信息檢索研究中心,黑龍江 哈爾濱 150001)

1 引言

在統(tǒng)計(jì)學(xué)習(xí)的模型訓(xùn)練過(guò)程中，按照對(duì)訓(xùn)練實(shí)例的處理方式，可將學(xué)習(xí)過(guò)程分為兩類(lèi)： 主動(dòng)學(xué)習(xí)和被動(dòng)學(xué)習(xí)。被動(dòng)學(xué)習(xí)是隨機(jī)地選擇訓(xùn)練實(shí)例，被動(dòng)地接受這些樣本信息。主動(dòng)學(xué)習(xí)與被動(dòng)學(xué)習(xí)不同，它是迭代地從未標(biāo)注語(yǔ)料中優(yōu)先選擇最富含有效信息的實(shí)例(即當(dāng)前模型預(yù)測(cè)最不準(zhǔn)的)交由人工標(biāo)注，然后加入訓(xùn)練集重新訓(xùn)練。由于優(yōu)先選擇的是最具訓(xùn)練效用的樣本，所以減少了那些對(duì)提高學(xué)習(xí)器精度幫助不大的冗余樣本的標(biāo)注，因而學(xué)習(xí)器只需更少的樣本便能獲得相同精度[1-2]。

目前最廣泛使用的主動(dòng)學(xué)習(xí)方法有基于不確定性度量(Uncertainty-based Sampling)和基于委員會(huì)投票(Query-by-committee)兩種[1]。

基于不確定性度量的樣本選擇根據(jù)學(xué)習(xí)器對(duì)未標(biāo)注樣本的分類(lèi)置信度來(lái)進(jìn)行。樣本分類(lèi)置信度越低，說(shuō)明學(xué)習(xí)器尚不能很好區(qū)分此樣本，即學(xué)習(xí)器缺乏此樣本含有的信息。此時(shí)將該樣本進(jìn)行人工標(biāo)注并加入訓(xùn)練集會(huì)對(duì)學(xué)習(xí)器精度的提升有很大幫助。對(duì)于分類(lèi)置信度高的樣本，不再人工標(biāo)注，從而免除了在冗余樣本上耗費(fèi)人力。這類(lèi)學(xué)習(xí)算法的重點(diǎn)是構(gòu)造一種合理有效的不確定性度量機(jī)制，以此來(lái)指導(dǎo)樣本選擇。

基于委員會(huì)投票的樣本選擇需要構(gòu)建一組分類(lèi)器，這些分類(lèi)器可以是用不同的訓(xùn)練算法得到(SVM、MaxEnt等)，也可以是用同種訓(xùn)練算法對(duì)樣本從不同的特征角度訓(xùn)練得到(Multi-view active learning[3])?；谖瘑T會(huì)投票的方法優(yōu)先選擇各分類(lèi)器投票結(jié)果最不一致的樣本進(jìn)行人工標(biāo)注。投票熵(Vote Entropy，Dagan and Engelson, 1995)和相對(duì)熵(KL divergence to the mean，Pereira et al.，1993)是兩種最常用的度量投票結(jié)果差異的方法。熵值越高，說(shuō)明投票差異越大，該樣本越應(yīng)該加入到訓(xùn)練集[4]。

國(guó)外學(xué)者已經(jīng)將主動(dòng)學(xué)習(xí)應(yīng)用到諸多自然語(yǔ)言處理相關(guān)的任務(wù)中，比如信息抽取(Thompson et al.，1999)、文本分類(lèi)(McCallum and Nigam，1998)和基于短語(yǔ)結(jié)構(gòu)的句法分析(Thompson et al.，1999；Hwa，2000)[5-6]等。在國(guó)內(nèi)，清華大學(xué)覃剛力、北京理工大學(xué)宋鑫穎等將主動(dòng)學(xué)習(xí)應(yīng)用到文本分類(lèi)上[7-8]；中國(guó)科技大學(xué)馮沖、上海交通大學(xué)陳霄分別用最大熵模型和支持向量機(jī)模型將主動(dòng)學(xué)習(xí)應(yīng)用到組織機(jī)構(gòu)名識(shí)別中，并取得了一定效果[9]。就作者所掌握的文獻(xiàn)，目前還沒(méi)有將主動(dòng)學(xué)習(xí)和中文依存句法的訓(xùn)練過(guò)程相結(jié)合的研究。在應(yīng)用最大熵或者支持向量機(jī)模型進(jìn)行預(yù)測(cè)的自然語(yǔ)言處理任務(wù)中，前者可以得到每個(gè)樣本屬于某一類(lèi)別的概率，后者可以得到每個(gè)樣本到分類(lèi)超平面的距離。這些預(yù)測(cè)任務(wù)的置信度比較容易獲得，比如基于SVM的文本分類(lèi)中距離分類(lèi)超平面最近的樣本置信度就比較低等?；诙陶Z(yǔ)結(jié)構(gòu)的句法分析可以根據(jù)每個(gè)產(chǎn)生式的概率計(jì)算最終生成的短語(yǔ)結(jié)構(gòu)樹(shù)的概率，并利用此概率值進(jìn)行各種可信度計(jì)算；而依存句法通過(guò)Online算法訓(xùn)練權(quán)值，最終求一棵權(quán)值最大的生成樹(shù)，很難得到生成樹(shù)的概率，原有的基于短語(yǔ)結(jié)構(gòu)的可信度度量方法也就不能直接應(yīng)用到依存分析上。因此，本文嘗試將主動(dòng)學(xué)習(xí)應(yīng)用到依存分析上，并嘗試了多種衡量依存句法模型預(yù)測(cè)可信度的準(zhǔn)則。

本文內(nèi)容組織為，第二部分介紹依存句法分析相關(guān)概念和基于圖的依存分析算法；第三部分介紹主動(dòng)學(xué)習(xí)的算法流程，其中詳細(xì)討論了如何衡量依存句法模型的預(yù)測(cè)可信度；第四部分是實(shí)驗(yàn)；第五部分給出結(jié)論和下一步工作。

2 中文依存句法分析

主動(dòng)學(xué)習(xí)需要事先在小數(shù)據(jù)集上訓(xùn)練一個(gè)依存句法分析器，用來(lái)對(duì)未知樣本進(jìn)行可信度預(yù)測(cè)。本文采用基于圖的依存分析算法來(lái)訓(xùn)練依存分析器，以下簡(jiǎn)要介紹基于圖的依存句法分析。

2.1 基于圖的中文依存句法分析

McDonald首先提出將依存分析問(wèn)題歸結(jié)為在一個(gè)有向圖中尋找最大生成樹(shù)(Maximum Spanning Tree)的問(wèn)題。邊權(quán)使用Online Learning算法學(xué)習(xí)獲得，解碼使用Eisner算法[11]。

Eisner算法以span為解碼的基本單位，span表示輸入句子的一個(gè)片段對(duì)應(yīng)的子樹(shù)。與組塊不同的是，span中的核心詞只能位于片段首或尾，即span只包括了這個(gè)詞左邊或者右邊的子孫節(jié)點(diǎn)。另外，除核心詞外的另外一個(gè)片段首或尾詞的修飾成分可以是不完整的，即span可以不包括這個(gè)詞左邊的子孫節(jié)點(diǎn)或者右邊的子孫節(jié)點(diǎn)。對(duì)于其他詞，span包括它們所有的子孫節(jié)點(diǎn)。span的這種特性使得解碼算法獨(dú)立地確定一個(gè)詞左邊的修飾成分和右邊的修飾成分，從而降低算法的復(fù)雜度[10]。

基于圖的依存分析算法是目前性能最高的依存分析方法之一。

3 基于主動(dòng)學(xué)習(xí)的中文依存句法分析

本文將主動(dòng)學(xué)習(xí)應(yīng)用到基于圖的依存句法訓(xùn)練過(guò)程中，具體的算法流程如下。

L： 人工標(biāo)注后的實(shí)例(句法依存樹(shù)庫(kù))

U： 未標(biāo)注的實(shí)例(已經(jīng)過(guò)分詞和詞性標(biāo)注的句子)

C： 當(dāng)前已標(biāo)注實(shí)例訓(xùn)練得到的模型(基于圖的依存分析器訓(xùn)練)

Φ： 衡量實(shí)例可信度的函數(shù)

Batch-Size： 每輪主動(dòng)學(xué)習(xí)挑選實(shí)例的個(gè)數(shù)

初始化：

從U中取出小部分未標(biāo)注實(shí)例，人工標(biāo)注，加入L；

C ← Train(L)；

重復(fù)：

U1 ←用C預(yù)測(cè)所有U；

N ← 根據(jù)函數(shù)Φ ，選擇不可信度最大的Batch-Siz個(gè)實(shí)例；

U ← U - N；

人工標(biāo)注N后，加入L；

C ← Train(L)；

直到：

以下三種停止準(zhǔn)則中至少滿(mǎn)足其一。

3.1 可信度度量

可信度度量是主動(dòng)學(xué)習(xí)選擇某一訓(xùn)練實(shí)例交由句法分析器訓(xùn)練的依據(jù)。由于依存句法中如何衡量預(yù)測(cè)結(jié)果的可信度并沒(méi)有現(xiàn)成方法可用，本文利用依存分析對(duì)每一句子輸出的K-Best預(yù)測(cè)結(jié)果來(lái)衡量可信度。該方法的思想： 一個(gè)句子的K-Best結(jié)果越相似，說(shuō)明其越容易混淆，相應(yīng)地該句的預(yù)測(cè)結(jié)果可信度應(yīng)越低。本文采用了基于不確定性和基于委員會(huì)投票兩大類(lèi)方法。

3.1.1 基于不確定性(Uncertainty-based Sampling)

該方法依據(jù)K-Best結(jié)果對(duì)每個(gè)句子預(yù)測(cè)結(jié)果的不確定性做出量化，排序后優(yōu)先選擇不確定性最大的，也即可信度最低的。不確定性度量Φ本文采用了以下三種。

a) Uncertainty-1. K-Best結(jié)果中任兩個(gè)不同結(jié)果的分值差的和的倒數(shù)，如公式(1)所示：

(1)

b) Uncertainty-2. K-Best結(jié)果中1-Best相對(duì)2-Best的增長(zhǎng)率的倒數(shù)，如公式(2)所示：

(2)

c) Uncertainty-3. K-Best結(jié)果的Sentence Entropy，如公式(3)所示：

其中

(3)

前兩種度量方法的思想是： 若K-Best不同結(jié)果的分值差異越顯著，說(shuō)明學(xué)習(xí)器對(duì)做出的選擇越有信心。第三種度量方法先對(duì)K-Best每棵樹(shù)的分值歸一化處理，然后通過(guò)K-Best結(jié)果計(jì)算熵。之所以要進(jìn)行歸一化處理，是由于基于圖的依存分析是判別模型，輸出的分值不是概率，也就無(wú)法計(jì)算熵。

3.1.2 委員會(huì)投票(Query-by-committee)

委員會(huì)方法需要構(gòu)造一組不同的學(xué)習(xí)器來(lái)進(jìn)行投票。基于圖的依存句法分析已在2.2節(jié)介紹過(guò)，這里介紹另一種基于轉(zhuǎn)移的依存分析方法?；谵D(zhuǎn)移的方法最早由J.Nivre提出[12]，他將依存樹(shù)的搜索過(guò)程建模為一個(gè)動(dòng)作序列，依存分析問(wèn)題轉(zhuǎn)化為尋找最優(yōu)動(dòng)作序列的問(wèn)題，每次需要根據(jù)歷史采取動(dòng)作時(shí)由一個(gè)分類(lèi)器給出，例如，支持向量機(jī)、最大熵分類(lèi)器等。

委員會(huì)投票優(yōu)先選擇基于圖和基于轉(zhuǎn)移兩種依存分析方法預(yù)測(cè)結(jié)果最不一致的句子。句法分析結(jié)果通常用LAS和UAS度量，本文得到兩種依存分析方法的自動(dòng)結(jié)果后，以基于圖的結(jié)果為準(zhǔn)則，以基于轉(zhuǎn)移的結(jié)果做測(cè)試結(jié)果，計(jì)算它們的LAS和UAS值作為投票的一致性評(píng)價(jià)指標(biāo)。本文分別記為QBC-LAS和QBC-UAS。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)來(lái)自HIT-CIR-CDT(哈爾濱工業(yè)大學(xué)信息檢索研究中心漢語(yǔ)依存樹(shù)庫(kù))，該樹(shù)庫(kù)共包含59 996個(gè)句子，每個(gè)句子均經(jīng)過(guò)人工標(biāo)注，全部來(lái)源于《人民日?qǐng)?bào)》。為了更好檢驗(yàn)主動(dòng)學(xué)習(xí)的作用，本文只篩選句長(zhǎng)在10～25個(gè)詞(不含標(biāo)點(diǎn))之間的句子，共約42 000句。

4.1 實(shí)驗(yàn)結(jié)果及分析

主動(dòng)學(xué)習(xí)的效果往往通過(guò)一條學(xué)習(xí)曲線(xiàn)(Learning Curve)來(lái)評(píng)價(jià)[1]。 本文將主動(dòng)學(xué)習(xí)的批處理參數(shù)Batch-Size設(shè)置為1 000，初始采用1 000句訓(xùn)練基于圖的依存分析器，以后每次通過(guò)主動(dòng)學(xué)習(xí)的抽樣方法加入Batch-Size個(gè)句子，算法共迭代10次?；趫D的依存分析器K-Best結(jié)果設(shè)置為5。同時(shí)為了與主動(dòng)學(xué)習(xí)對(duì)比，本文用每次隨機(jī)選擇 1 000句的方法作為基準(zhǔn)測(cè)試。每次訓(xùn)練出的模型都在3 000句測(cè)試集上測(cè)試，結(jié)果如表1所示。

從表1看出，基于不確定性和委員會(huì)投票這兩類(lèi)主動(dòng)學(xué)習(xí)中的任一種方法在10次主動(dòng)學(xué)習(xí)的迭代過(guò)程中都取得了比隨機(jī)抽樣更好的性能。一方面，使用相同數(shù)目的訓(xùn)練實(shí)例，主動(dòng)學(xué)習(xí)能使句法分析取得更好的性能： 10次迭代結(jié)束時(shí)，Uncertainty-1比Random提高了0.78個(gè)百分點(diǎn)(其中在第7次迭代時(shí)達(dá)到最大，提高0.8個(gè)百分點(diǎn))；另一方面，主動(dòng)學(xué)習(xí)使句法分析取得同樣的性能只需人工標(biāo)注更少量的訓(xùn)練語(yǔ)料： Random第10次迭代，即使用10 000句訓(xùn)練達(dá)到79.09%的準(zhǔn)確率(LAS)，而Uncertainty-1在第7次迭代時(shí)，只使用7 200句，就達(dá)到同樣性能，減少了近30%的人工標(biāo)注量。

將以上表格繪制成折線(xiàn)圖，如圖1所示：

表1 10次迭代過(guò)程中各種主動(dòng)學(xué)習(xí)方法在測(cè)試集上的LAS和UAS/%

圖1 10次迭代過(guò)程中各種主動(dòng)學(xué)習(xí)方法在測(cè)試集上的LAS遞增曲線(xiàn)

圖2給出了測(cè)試集LAS達(dá)到79.09%時(shí)，基準(zhǔn)測(cè)試和主動(dòng)學(xué)習(xí)各方法所需訓(xùn)練實(shí)例數(shù)目的對(duì)比。

實(shí)驗(yàn)表明，在五種可信度度量方法中，Uncertainty-1的效果最明顯，減少了近30%標(biāo)注量，其次是Uncertainty-3，效果最低的是QBC的兩類(lèi)方法。分析原因?yàn)椋?與Uncertainty-2相比，Uncertainty-1和Uncertainty-3綜合考慮了所有K-Best結(jié)果的差異，而不僅僅是最高的前兩個(gè)，因此受噪聲影響的可能性最小，效果最好；QBC只減少了15%標(biāo)注量，很可能在于基于轉(zhuǎn)移的依存分析性能上與基于圖的方法仍存在不小差異，實(shí)驗(yàn)使用的基于轉(zhuǎn)移的依存分析器LAS為72.83%(8 000句訓(xùn)練，1 000句測(cè)試)，而同樣的訓(xùn)練和測(cè)試數(shù)據(jù)，基于圖的LAS達(dá)到78%以上。因此，基于轉(zhuǎn)移方法引入的噪聲很可能影響投票效果，導(dǎo)致QBC實(shí)驗(yàn)效果較低。在具體應(yīng)用時(shí)，應(yīng)優(yōu)先考慮Uncertainty-1的可信度度量方法。

4 結(jié)論及下一步工作

本文提出一種基于主動(dòng)學(xué)習(xí)的中文依存句法分析方法。該方法從大量未標(biāo)注語(yǔ)料中優(yōu)先選擇不確定性最大，也即當(dāng)前句法模型預(yù)測(cè)可信度最低的句子交由人工標(biāo)注，隨后加入訓(xùn)練集迭代訓(xùn)練，如此往復(fù)，直到滿(mǎn)足停止準(zhǔn)則。其中，主動(dòng)學(xué)習(xí)使用了不確定性度量和委員會(huì)投票兩種最經(jīng)典的方法。實(shí)驗(yàn)證明，一方面，使用相同數(shù)目的訓(xùn)練實(shí)例，主動(dòng)學(xué)習(xí)使LAS最高提升0.8個(gè)百分點(diǎn)；另一方面，主動(dòng)學(xué)習(xí)使得只需標(biāo)注更少量的句子就可達(dá)到相同的依存分析準(zhǔn)確率，人工標(biāo)注量最多可減少30%，從而大大降低了樹(shù)庫(kù)標(biāo)注的人力成本。

圖2 測(cè)試集LAS達(dá)到79.09%時(shí)，基準(zhǔn)測(cè)試和主動(dòng)學(xué)習(xí)各方法需要的訓(xùn)練實(shí)例數(shù)目

下一步工作主要是探索主動(dòng)學(xué)習(xí)的其他有效方法，比如從訓(xùn)練語(yǔ)料的多樣性出發(fā)，可以先聚類(lèi)再?gòu)拿總€(gè)簇抽樣；或者優(yōu)先選取訓(xùn)練語(yǔ)料中最具代表性的實(shí)例，因?yàn)樽罹叽硇缘膶?shí)例可以覆蓋到更多的實(shí)例信息，它本身是噪聲點(diǎn)的可能性也往往最低，難點(diǎn)在于最具代表性的度量，這可以通過(guò)計(jì)算相對(duì)熵得到。另外，可以嘗試將主動(dòng)學(xué)習(xí)應(yīng)用到句法分析的領(lǐng)域移植上，以減少獲取新標(biāo)注語(yǔ)料時(shí)的壓力。

[1] Olsson Fredrik. A literature survey of active machine learning in the context of natural language processing[R]. Swedish Institute of Computer Science.2009.

[2] Min Tang, Xiaoqiang Luo, Salim Roukos. Active Learning for Statistical Natural Language Parsing[C]//Proceedings of the 40th ACL. 2002:120-127.

[3] Ion Muslea, Steven Minton, Craig A. Knoblock. Active Learning with Multiple Views[J]. Journal of Artificial Intelligence Research. 2006, 27:203-233.

[4] Yoav Freund, H.Sebastian Seung. Selective Sampling Using the Query by Committee Algorithm[J]. Machine Learning. 1997, 28:133-168.

[5] Cynthia A. Thompson, Mary Elaine Califf, Raymond J. Mooney. Active Learning for Natural Language Parsing and Information Extraction[C]//Proceedings of the Sixteenth International Conference on Machine Learning. 1999:406-414.

[6] Rebecca Hwa. Sample Selecting for Statistical Parsing[J]. Computational Linguistics. 2004, 30(3):253-276.

[7] 覃剛力,黃科等. 基于主動(dòng)學(xué)習(xí)的文檔分類(lèi)[J]. 計(jì)算機(jī)科學(xué). 2003, 30(10):45-48.

[8] 宋鑫穎,周志逵. 一種基于SVM的主動(dòng)學(xué)習(xí)文本分類(lèi)方法[J]. 計(jì)算機(jī)科學(xué). 2006, 33(11):288-290.

[9] 陳霄. 基于支持向量機(jī)的中文組織機(jī)構(gòu)名識(shí)別[D]. 碩士學(xué)位論文, 上海交通大學(xué). 2007.

[10] 李正華. 依存句法分析統(tǒng)計(jì)模型及樹(shù)庫(kù)轉(zhuǎn)化研究[D]. 碩士學(xué)位論文, 哈爾濱工業(yè)大學(xué). 2008.

[11] R.McDonald, K.Crammer， F.Pereira. Online Large-margin Training of Dependency Parsers[C]//Proceedings of ACL. 2005:91-98.

[12] J.Nivre. Algorithms for Deterministic Incremental Dependency Parsing[J]. Computational Linguistics. 2008, 34(4):513-553.