基于支持向量機(jī)方法的中文組織機(jī)構(gòu)名的識別

摘要:在應(yīng)用基本的支持向量機(jī)算法的基礎(chǔ)上，提出了一種分步遞增式學(xué)習(xí)的方法，利用主動學(xué)習(xí)的策略對訓(xùn)練樣本進(jìn)行選擇，逐步增大提交給學(xué)習(xí)器訓(xùn)練樣本的規(guī)模，以提高學(xué)習(xí)器的識別精度。實驗表明，采用主動學(xué)習(xí)策略的支持向量機(jī)算法是有效的，在實驗中，中文機(jī)構(gòu)名識別的正確率和召回率分別達(dá)到了81.7%和86.8%。

關(guān)鍵詞:機(jī)構(gòu)名識別; 支持向量機(jī); 主動學(xué)習(xí)

中圖分類號:TP301.6文獻(xiàn)標(biāo)志碼:A

文章編號:1001－3695(2008)02－0362－03

中文組織機(jī)構(gòu)名的識別是中文信息處理中的一個重要任務(wù)，也是命名實體識別(named entity recognition)研究的重點之一。命名實體包括人名#65380;地名#65380;機(jī)構(gòu)名和時間短語等。組織機(jī)構(gòu)名是其中非常重要的一部分。有統(tǒng)計數(shù)據(jù)顯示，中文組織機(jī)構(gòu)名在命名實體中的比例為20.2%[1]。機(jī)構(gòu)名泛指機(jī)關(guān)#65380;團(tuán)體或其他企事業(yè)單位，包括學(xué)校#65380;公司#65380;醫(yī)院#65380;研究所和政府機(jī)關(guān)等組織機(jī)構(gòu)的名稱。由于這類詞涉及廣泛#65380;種類繁多#65380;形態(tài)各異#65380;隨時間不斷變化，并且中文機(jī)構(gòu)名又不存在英文中那樣明確的形態(tài)標(biāo)記，其識別的難度較大。

目前中文機(jī)構(gòu)名的識別方法主要有基于規(guī)則和基于統(tǒng)計兩大類。研究較多的是基于統(tǒng)計的方法，所采用的方法包括隱馬爾科夫模型[2]#65380;最大熵模型[3，4]等，取得了一定的效果。采用統(tǒng)計方法的系統(tǒng)性能與所使用的標(biāo)注語料的領(lǐng)域和規(guī)模密切相關(guān)。機(jī)構(gòu)名的構(gòu)成很不穩(wěn)定，隨著領(lǐng)域和時間的不同會有很大的變化。語料的標(biāo)注耗時耗力，往往成為提高系統(tǒng)性能的關(guān)鍵性問題，也限制了系統(tǒng)在不同應(yīng)用領(lǐng)域之間的移植，難以滿足其真實應(yīng)用的需求。

在統(tǒng)計學(xué)習(xí)理論的基礎(chǔ)上發(fā)展起來支持向量機(jī)(support vector machine)是一種新的通用學(xué)習(xí)方法。與過去的一些統(tǒng)計學(xué)習(xí)方法相比，基于結(jié)構(gòu)風(fēng)險最小化原則的支持向量機(jī)已經(jīng)表現(xiàn)出一些優(yōu)越的性能。特別是在樣本集有限的情況下，它往往能取得優(yōu)于其他方法的結(jié)果。目前，支持向量機(jī)已經(jīng)應(yīng)用于自然語言處理的許多領(lǐng)域，如文本分類#65380;淺層句法分析#65380;專名識別等，都取得了不錯的效果。本文即是支持向量機(jī)在中文機(jī)構(gòu)名識別方面的一些嘗試性研究:用支持向量機(jī)對切分正確的語料中的中文機(jī)構(gòu)進(jìn)行識別，并在樣本選擇和模型訓(xùn)練時，結(jié)合主動學(xué)習(xí)的策略，提高學(xué)習(xí)器精度并減少人工樣本標(biāo)注的成本。

1支持向量機(jī)的基本原理

1.1最優(yōu)分類超平面

即支持向量機(jī)的標(biāo)準(zhǔn)形式[5]。

由于支持向量機(jī)基于結(jié)構(gòu)風(fēng)險最小化的原理，有效地控制了VC維，具有良好的泛化能力;通過把原問題轉(zhuǎn)換為對偶問題，計算的復(fù)雜度不再取決于空間維數(shù)，而是取決于樣本數(shù)，尤其是樣本中的支持向量數(shù)，具有良好的高維處理能力。

2主動學(xué)習(xí)策略

2.1統(tǒng)計學(xué)習(xí)中主動學(xué)習(xí)策略

主動學(xué)習(xí)是一種迭代地從未標(biāo)注樣本中選擇最富含有效信息的樣本，然后交由人工標(biāo)注的機(jī)器學(xué)習(xí)技術(shù)。由于學(xué)習(xí)器每次能夠從大量的未標(biāo)注文本中提取出一些最具有訓(xùn)練效用的樣本，減少了那些對提高學(xué)習(xí)器精度幫助不大的冗余樣本的標(biāo)注，因而學(xué)習(xí)器只需更少的樣本便能獲得相同精度。主動學(xué)習(xí)的理論依據(jù)在于，通過系統(tǒng)地降低統(tǒng)計學(xué)習(xí)器的期望錯誤率可以做到對訓(xùn)練數(shù)據(jù)的優(yōu)化選擇。

基于不確定性的樣本選擇(uncertainty－based sampling)[6]是一種主要的主動學(xué)習(xí)策略。它首先讓學(xué)習(xí)器對未標(biāo)注實例進(jìn)行標(biāo)注并給出學(xué)習(xí)器對該樣本標(biāo)注的置信度度量;然后依據(jù)置信度度量來進(jìn)行樣本的選擇。其依據(jù)就是那些學(xué)習(xí)器最不確定的樣本對提升學(xué)習(xí)器精度的幫助最大。這類主動學(xué)習(xí)算法的重點就是構(gòu)造一種合理的度量機(jī)制來評估學(xué)習(xí)器輸出的標(biāo)注序列的置信度。通常情況下，對輸出為概率值的學(xué)習(xí)器，往往用樣本不同標(biāo)注的概率分布的熵來作為置信度。

2.2支持向量機(jī)方法的主動學(xué)習(xí)策略

采用基于不確定性的樣本選擇的主動學(xué)習(xí)策略通常需要學(xué)習(xí)器輸出的是樣本標(biāo)注的概率值，而支持向量機(jī)的輸出不是概率。為了解決這個問題，需要構(gòu)造一種新的置信度的度量值。筆者知道基本的二分類的支持向量機(jī)輸出的是一個判定值，其絕對值就是樣本到最優(yōu)分類超平面的距離。因此，一種直觀的想法是將該距離作為學(xué)習(xí)器標(biāo)注的置信度。文獻(xiàn)[7]基于該想法提出了一種將支持向量機(jī)輸出映射為概率的方法:

其中:y是樣本標(biāo)注; f(x)是支持向量機(jī)輸出的判定值;A#65380;B是需要確定的參數(shù)值。可以證明，在A<0的情況下，該概率值與f(x)具有相同的單調(diào)性。事實上，由于并不需要知道確定的概率值而是它的度量，本文直接采用支持向量機(jī)的輸出判定值的絕對值作為置信度的度量。

3基于主動學(xué)習(xí)支持向量機(jī)的中文機(jī)構(gòu)名識別策略

3.1基于支持向量機(jī)的機(jī)構(gòu)名識別策略

中文組織機(jī)構(gòu)名識別任務(wù)可由下面的模型表示:設(shè)一個由n個詞組成的漢語句子為S=W1，W2，W3，…，Wn。Wi表示句子的第i個詞;Li為詞Wi的標(biāo)記。通常采用IOB標(biāo)注法對每個詞進(jìn)行標(biāo)注，即:B表示該詞為機(jī)構(gòu)名的起始詞;I表示機(jī)構(gòu)名的非起始詞，O表示機(jī)構(gòu)名之外的詞。例如:“逢博/O 以/O 優(yōu)異/O 成績/O 考取/O 了/O 上海/B 同濟(jì)/I 大學(xué)/I。/O”。因此，機(jī)構(gòu)名識別過程就變成了對句子的每一個詞進(jìn)行標(biāo)注的問題。進(jìn)一步地，可以表示成對一個詞為樣本單位的分類問題，而該分類問題可以由支持向量機(jī)來完成。實際上，可以將機(jī)構(gòu)名部分即I#65380;B標(biāo)注歸成一類，這樣就變成了一個最基本二分類問題。

對于樣本的特征選取，本文選擇一個詞及其上下文(前后兩個詞)的詞性，機(jī)構(gòu)名的標(biāo)注作為樣本特征。另外，考慮到中文機(jī)構(gòu)名的組成特征，本文還引入了機(jī)構(gòu)名稱呼詞置信度的特征。機(jī)構(gòu)稱呼詞是指出現(xiàn)在機(jī)構(gòu)名尾部，表示機(jī)構(gòu)名稱呼的詞(如公司#65380;協(xié)會#65380;委員會等)。機(jī)構(gòu)稱呼詞是機(jī)構(gòu)名組成的中心詞，在對機(jī)構(gòu)名的識別有重要作用。筆者計算其機(jī)構(gòu)稱呼詞置信度ph(huán)(w)為

其中:y是所有在機(jī)構(gòu)稱呼詞表中的詞;C(w)為該詞作為機(jī)構(gòu)名出現(xiàn)的次數(shù)。為了計算機(jī)構(gòu)名稱呼詞的置信度，還必須維護(hù)一個包含詞頻信息的機(jī)構(gòu)名稱呼詞表。由于開始時，并沒有這樣一個機(jī)構(gòu)名稱呼詞表，本文采取了以下的辦法:結(jié)合主動學(xué)習(xí)的訓(xùn)練過程，先從最開始的用于訓(xùn)練的標(biāo)注語料中統(tǒng)計出現(xiàn)的機(jī)構(gòu)名稱呼詞及其詞頻信息，構(gòu)建一個初始的機(jī)構(gòu)名稱呼詞表;然后，隨著每次新選擇的樣本的加入，更新詞表及詞頻信息。

這樣，最終的樣本特征確定為

3.2采用主動學(xué)習(xí)策略的支持向量機(jī)學(xué)習(xí)算法

為了能夠更好地利用大量的未標(biāo)注語料，減少人工標(biāo)注的成本，本文引入了主動學(xué)習(xí)的策略對樣本進(jìn)行選擇，以便在規(guī)模相同或較少的樣本訓(xùn)練集上，獲得較高的訓(xùn)練效果。前邊已經(jīng)介紹了基于不確定性的樣本選擇策略應(yīng)用于支持向量機(jī)的方法。由于本文對語料樣本的選擇是以句子為基本單位的，在詞的不確定性的基礎(chǔ)上定義句子的不確定度為Si=1/|W|∑wi∈Wconf(wi)。其中:W是該句中所有標(biāo)注為機(jī)構(gòu)名部分的詞的集合;conf(wi)是wi的不確定度。這樣，可以從一個已標(biāo)注的樣本集開始訓(xùn)練分類器，然后利用現(xiàn)有的分類器對未標(biāo)注的樣本進(jìn)行分類，從而計算每個句子的不確定性，從中選擇不確定性最大的m個句子加入樣本集。整個訓(xùn)練過程描述如下:

輸入:少量的標(biāo)注語料L和大量的未標(biāo)注語料U

輸出:由樣本集訓(xùn)練獲得的支持向量機(jī)M

a)從L開始訓(xùn)練并獲得支持向量機(jī)M0;

b)利用Mi(Mi是經(jīng)過次樣本選擇和重新訓(xùn)練后的支持向量機(jī))對U中的語料進(jìn)行分類標(biāo)注并計算每個句子的不確定度;

c)從U中選出Su值最大的m個句子提交給人工標(biāo)注，并將其從U中轉(zhuǎn)移到L中，同時更新機(jī)構(gòu)名稱呼詞表;

d)重新從步驟a)開始，并反復(fù)這一循環(huán)，直到達(dá)到指定的要求或者U中的樣本都已用盡為止。

4實驗

利用上述方法對系統(tǒng)進(jìn)行了開放性實驗，采用的語料來源于《人民日報》的切分標(biāo)注語料。首先將其中包含機(jī)構(gòu)名的部分近5萬字，包含機(jī)構(gòu)名2 013個的語料從切分標(biāo)注好的語料中提取出來，隨機(jī)分為三個部分。其中:約20%的語料作為測試集;另外約10%的語料作為最初的訓(xùn)練集L，這兩部分語料中的機(jī)構(gòu)名部分都已經(jīng)人工標(biāo)注好了;剩下的語料作為未標(biāo)注集U作為主動學(xué)習(xí)的訓(xùn)練語料集。

在本實驗中，總共進(jìn)行了三組實驗:前兩組實驗設(shè)定了不同的m值，分別為100和50，以對比不同粗細(xì)度的樣本選擇效果;第三組實驗沒有采用主動學(xué)習(xí)策略，每次隨機(jī)選擇樣本，以比較主動學(xué)習(xí)和非主動學(xué)習(xí)的差別。實驗中支持向量機(jī)的核函數(shù)采用了二次多項式。本文沒有采用其他不同的核函數(shù)(如徑向基核函數(shù)和多層感知機(jī))的SVM進(jìn)行比較實驗。原因是許多實驗表明，這幾種不同核函數(shù)的支持向量機(jī)在不同的分類問題上表現(xiàn)出十分相近的性能，錯誤率相差都在0.5%以內(nèi)[8，9]。

實驗中的性能指標(biāo)定義如下:

正確率(precision):P=N2/N1×100%

召回率(recall):R=N2/N3×100%

其中:N1為標(biāo)準(zhǔn)結(jié)果中的機(jī)構(gòu)名個數(shù);N2為正確標(biāo)注的機(jī)構(gòu)名個數(shù);N3為標(biāo)注的機(jī)構(gòu)名總個數(shù)。

Fβ=[(β2+1)×P×R]/(β2×R+P)

其中β=1。這里的正確標(biāo)注是指機(jī)構(gòu)名的類別和邊界都被正確地識別出來。實驗結(jié)果如表1所示。

在完成了多次樣本選擇訓(xùn)練以后，原來未標(biāo)注集中的約60%樣本已經(jīng)被用于訓(xùn)練，最后的正確率和召回率已經(jīng)穩(wěn)定在82%和87%左右，F(xiàn)值也已經(jīng)穩(wěn)定在84%左右。從不同m值的對比實驗結(jié)果(圖1)看，每次選擇較少的樣本比每次選擇較多的樣本的結(jié)果要略好一些。這可能與樣本的多樣性有關(guān)。每次選擇較多的樣本也有可能包含較多相似的樣本，而減少每次提交的樣本數(shù)就會降低這種可能，但同時也會增加訓(xùn)練的時間。如何在樣本選擇時考慮樣本之間的相似性問題，是筆者進(jìn)一步要研究的問題。

另外，本文還將采用了主動學(xué)習(xí)策略的實驗結(jié)果和沒有采用主動學(xué)習(xí)策略(隨機(jī)選擇樣本)的實驗結(jié)果進(jìn)行了比較，如圖2所示。

從圖2的比較可以看出，在樣本數(shù)逐漸增大的情況下，采用了主動學(xué)習(xí)策略的方法要明顯優(yōu)于沒有采用主動學(xué)習(xí)策略的方法。最終結(jié)果，其F值要優(yōu)于隨機(jī)樣本選擇的方法3~4個百分點。這說明樣本選擇對提高學(xué)習(xí)器的學(xué)習(xí)精度起到了作用。從獲得相同F(xiàn)值時所用的樣本數(shù)方面來看: F值達(dá)到80%，采用主動學(xué)習(xí)的方法(m=50)和沒有采用主動學(xué)習(xí)的方法分別需要樣本數(shù)約為10 889和16 317(以詞為單位);F值達(dá)到75%，則分別為7 240和10 983。采用主動學(xué)習(xí)的方法都少用了近1/3的樣本，說明樣本選擇起到了減少冗余樣本的作用。

5結(jié)束語

本文研究了利用支持向量機(jī)結(jié)合主動學(xué)習(xí)策略的中文機(jī)構(gòu)名識別方法。支持向量機(jī)作為分類器較其他分類器具有較好的性能，尤其在小樣本情況下的泛化能力十分的優(yōu)秀。主動學(xué)習(xí)作為一種機(jī)器學(xué)習(xí)方法通過選擇最有價值的樣本提交給學(xué)習(xí)器能有效地提高學(xué)習(xí)器的學(xué)習(xí)效率和精度。實驗表明，這一方法取得了較好的結(jié)果。進(jìn)一步的工作是改進(jìn)主動學(xué)習(xí)樣本選擇的策略和SVM算法。例如，樣本選擇時考慮樣本密度以及多分類的SVM識別算法等，進(jìn)一步提高了算法分類能力。

參考文獻(xiàn):

[1]PALMER D， DAY D S. A statistical profile of the named entity task[C]//Proc of the 5th Conference on Applied Natural Language Processing. Washington D C:[s.n.]， 1997:191－192.

[2]VLACHOS A. Active learning with support vector machines[D]. MS: University of Edinburgh， 2004:12－14.

[3]BERGER A L， PIETRA S A D， DELLA－PIETRA V J. A maximum entropy approach to natural language processing[J]. Computational Linguistics， 1996，22(1):39－71.

[4]馮沖，陳肇雄，黃河燕，等.最大熵模型的樹—柵格最優(yōu)N解碼算法[J].計算機(jī)科學(xué)，2005，32(10):167－169.

[5]張學(xué)工.關(guān)于統(tǒng)計學(xué)習(xí)理論與支持向量機(jī)[C].自動化學(xué)報，2000，26(1):32－42.

[6]LEWIS D D， GALE W A. A sequential algorithm for training text classifiers[C]//Proc of the 17th ACM International Conference on Research and Development in Information Retrieval. 1994:3－12.

[7]PLATT J. Probabilistic outputs for support vector machines and comparison to regularized likelihood methods[C]//Advances in Large Margin Classifiers. 2000:61－74.

[8]VAPNIK V. The nature of statistical learning theory[M]. New York: Springer， 1995.

[9]JOACHIMS T. Text categorization with support vector machines:learning with many relevant features[C]//Proc of the European Conference on Machine Learning. 1998:137－142.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”