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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)中的性能指標(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)名個(gè)數(shù);N2為正確標(biāo)注的機(jī)構(gòu)名個(gè)數(shù);N3為標(biāo)注的機(jī)構(gòu)名總個(gè)數(shù)。

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

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

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

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

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

5結(jié)束語(yǔ)

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

參考文獻(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]馮沖，陳肇雄，黃河燕，等.最大熵模型的樹(shù)—柵格最優(yōu)N解碼算法[J].計(jì)算機(jī)科學(xué)，2005，32(10):167－169.

[5]張學(xué)工.關(guān)于統(tǒng)計(jì)學(xué)習(xí)理論與支持向量機(jī)[C].自動(dòng)化學(xué)報(bào)，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)容請(qǐng)以PDF格式閱讀原文”