李壽山，黃居仁

(香港理工大學(xué) 中文及雙語(yǔ)學(xué)系，香港)

1 引言

自動(dòng)分詞是中文計(jì)算機(jī)處理中的一個(gè)基本任務(wù)[1]。該技術(shù)是實(shí)現(xiàn)眾多中文應(yīng)用系統(tǒng)的前期基礎(chǔ)，例如：中英(英中)機(jī)器翻譯、信息檢索、文本自動(dòng)分類(lèi)等。由于中文詞邊界本身的歧義性，加上大量新詞的不斷涌現(xiàn)，中文自動(dòng)分詞一直是中文信息處理中的一個(gè)長(zhǎng)期且艱巨的任務(wù)。針對(duì)該任務(wù)，中文信息處理研究領(lǐng)域先后出現(xiàn)了大量的自動(dòng)分詞方法。

長(zhǎng)期以來(lái)，分詞的方法都是基于詞(或詞典)的[2]。例如基于規(guī)則的最大匹配方法[3]或者基于統(tǒng)計(jì)的詞的N元語(yǔ)法方法[4]。 在大規(guī)模詞典的幫助下，基于詞的分詞方法取得了比較好的效果。但是該方法在識(shí)別未登錄詞(OOV)時(shí)，結(jié)果并不理想，然而未登錄詞的識(shí)別在分詞系統(tǒng)的應(yīng)用中是不可避免的問(wèn)題。近幾年來(lái)，基于字的分詞方法漸漸得到相當(dāng)?shù)年P(guān)注，在這幾次的Sighan評(píng)測(cè)中占主導(dǎo)地位。該方法將分詞問(wèn)題轉(zhuǎn)化為字的分類(lèi)問(wèn)題，即判斷文本的字是否為某詞的開(kāi)始或者結(jié)束[5]。相對(duì)于基于詞的分詞方法，基于字的分詞方法的最大優(yōu)點(diǎn)就是能夠取得令人滿意的OOV識(shí)別率。盡管如此，由于基于字的分詞方法需要構(gòu)建高維的向量空間，而且分類(lèi)的樣本非常龐大，這使得該方法訓(xùn)練和測(cè)試的時(shí)間復(fù)雜度和空間復(fù)雜度都非常高。因此，該方法還不能滿足一些真正實(shí)用的實(shí)時(shí)分詞系統(tǒng)。我們認(rèn)為一個(gè)優(yōu)秀的實(shí)時(shí)分詞系統(tǒng)不僅僅需要快速對(duì)新樣本進(jìn)行分詞，還需要能夠迅速學(xué)習(xí)新的標(biāo)注樣本(該特性我們稱之為在線學(xué)習(xí)能力[6])。而目前基于字的分詞方法訓(xùn)練需要時(shí)間太長(zhǎng)，很難滿足以上的要求。

文獻(xiàn)[7]首先提出一種基于詞邊界分類(lèi)的分詞方法(Word Boundary Decision，以下簡(jiǎn)稱該方法為WBD)。該方法直接對(duì)分詞的任務(wù)建模，判斷字同字之間的邊界是否為詞的邊界。換言之，該方法視分詞為一個(gè)兩類(lèi)分類(lèi)問(wèn)題。相對(duì)于一般的基于字的分類(lèi)方法，類(lèi)別的數(shù)目有所減少，從而降低了分類(lèi)的復(fù)雜度。本文將介紹該分詞方法并進(jìn)一步完善該方法，使得它能夠獲得接近目前主流方法的分詞效果。在此基礎(chǔ)上，我們將提出一種基于WBD的在線學(xué)習(xí)分詞方法，能夠快速學(xué)習(xí)新標(biāo)注樣本。鑒于WBD方法的時(shí)間復(fù)雜度和空間復(fù)雜度遠(yuǎn)遠(yuǎn)小于基于字的分詞方法，我們能夠利用它構(gòu)建一個(gè)更實(shí)用的分詞系統(tǒng)。

本文其他部分安排如下：第2部分詳細(xì)介紹基于詞邊界分類(lèi)的分詞方法并提出我們的一些改進(jìn)；第3部分提出基于WBD的在線學(xué)習(xí)分詞方法；第4部分給出實(shí)驗(yàn)結(jié)果及分析；第5部分給出相關(guān)結(jié)論。

2 基于詞邊界分類(lèi)的分詞方法(WBD)

2.1 WBD方法

自動(dòng)分詞的基本任務(wù)是將一段由字串組成的文本切割成由詞組成的詞序列。舉例來(lái)說(shuō)，一段分詞前的字序列為“共同創(chuàng)造美好的新世紀(jì)”，而分詞后的詞序列為：“共同 創(chuàng)造 美好 的 新 世紀(jì)”。這樣做是便于計(jì)算機(jī)識(shí)別和處理比較完整的一些語(yǔ)義單位，如“創(chuàng)造”、“美好”等，從而有利于進(jìn)一步的文本處理，如自動(dòng)翻譯、信息檢索等。

WBD方法的目標(biāo)是判斷每?jī)蓚€(gè)字之間的邊界是否為詞邊界。我們形式化表示一段文本為：

c1I1c2I2,...,ciIi,...,cn-1In-1cn

其中ci表示一個(gè)中文字符，Ii表示任意兩個(gè)字之間的字邊界。在原始的中文文本中，這些字邊界沒(méi)有明顯的顯示出是否為詞邊界。我們?cè)O(shè)定如果該字邊界為詞邊界，則記為Ii=1，否則Ii=0。WBD的方法就是直接判斷某個(gè)字邊界是否為詞邊界。因此，在WBD中，分詞任務(wù)被轉(zhuǎn)化為一個(gè)兩類(lèi)分類(lèi)問(wèn)題。然而在基于字的分詞方法中，一般會(huì)把字的類(lèi)別數(shù)目定義為“開(kāi)始”、 “中間” 、“結(jié)束”和“單字”。在類(lèi)別數(shù)目上面來(lái)說(shuō)，WBD方法要比基于字的分詞方法更簡(jiǎn)單。

WBD方法大致分為兩個(gè)步驟：N-gram概率信息統(tǒng)計(jì)和邊界的向量表示。下面分別介紹這兩個(gè)步驟。

在第一個(gè)步驟中，該方法通過(guò)收集訓(xùn)練樣本中的詞邊界信息，即N-gram字串關(guān)于詞邊界的統(tǒng)計(jì)信息。文獻(xiàn)[7]中給出了5種不同的unigram和bigram特征的統(tǒng)計(jì)信息，它們分別為PCB、PBC、PCCB、PCBC和PBCC。這些統(tǒng)計(jì)信息具體是指N-gram字串相對(duì)于詞邊界的出現(xiàn)概率。其中PCB定義如下：

其中C(ci,Ii=1) 表示在訓(xùn)練語(yǔ)料中字符ci出現(xiàn)在詞邊界前面的次數(shù)。而C(ci)表示字符ci在訓(xùn)練語(yǔ)料中出現(xiàn)的總次數(shù)。

另外，PCCB的定義如下：

其中C(ci-1,ci,Ii=1)表示在訓(xùn)練語(yǔ)料中二元字符串ci-1,ci出現(xiàn)在詞邊界前面的次數(shù)。而C(ci-1,ci)是二元字符串ci-1,ci在訓(xùn)練語(yǔ)料中出現(xiàn)的總次數(shù)。

其他三個(gè)概率信息,PBC(Ii=1|ci+1)，PCBC(Ii=1|ci,ci+1)和PBCC(Ii=1|ci-2,ci-1) 具有類(lèi)似的定義。為了簡(jiǎn)單起見(jiàn)，下面我們分別用PCCB(Ii),PCBC(Ii),PBCC(Ii),PCB(Ii),PBC(Ii)表示這5個(gè)概率信息統(tǒng)計(jì)量。一旦獲得了所有N-gram字符串的概率信息，我們將這些數(shù)據(jù)保存在一個(gè)字典中，供以后構(gòu)建向量使用。我們命名這個(gè)包含統(tǒng)計(jì)信息的字典為“N-gram數(shù)據(jù)源”。

在第二個(gè)步驟中，WBD方法將所有的字邊界表示為下面的向量：

WBD的訓(xùn)練過(guò)程和測(cè)試過(guò)程都會(huì)將所有字邊界表示為這種向量。剩下的就是一個(gè)典型的模式分類(lèi)問(wèn)題。我們可以采用各種不同的統(tǒng)計(jì)分類(lèi)方法去訓(xùn)練和測(cè)試。由于該向量的維度很低，僅僅需要幾千個(gè)樣本就足夠訓(xùn)練出一個(gè)比較好的分類(lèi)器[8]。這一點(diǎn)與基于字的分詞方法不同，基于字的分詞方法需要訓(xùn)練大量的樣本向量。因此，WBD方法大大降低了訓(xùn)練時(shí)間。為了更清晰的了解WBD方法，我們給出文本“共I1同I2創(chuàng)I3造I4美I5好”中每個(gè)字邊界的向量實(shí)例，如表1所示。其中，在N-gram數(shù)據(jù)源中未出現(xiàn)的字串概率一律賦值為0.50。

表1 一段字串的字邊界向量實(shí)例

2.2 WBD方法的進(jìn)一步完善

在已有的WBD方法的框架基礎(chǔ)上，我們提出一系列進(jìn)一步完善的措施，包括概率估計(jì)的平滑、新N-gram的引入和數(shù)字英文字符的預(yù)處理。

在估計(jì)概率的時(shí)候，往往會(huì)出現(xiàn)某些字符在語(yǔ)料中出現(xiàn)次數(shù)很少的情況，利用上面的統(tǒng)計(jì)公式統(tǒng)計(jì)概率會(huì)帶來(lái)很大的誤差。為了減小這些誤差給分類(lèi)帶來(lái)的影響，我們盡量使頻率出現(xiàn)很少的概率趨向于0.5。以PCB為例，我們改寫(xiě)概率估計(jì)函數(shù)如下：

另外，上面介紹的WBD方法僅僅考慮到了unigram和bigram字符串的統(tǒng)計(jì)信息。在實(shí)際分詞任務(wù)中，為了捕捉更遠(yuǎn)的分詞信息，從而更好地識(shí)別多字符的詞，我們引入trigram字符串的統(tǒng)計(jì)信息。trigram字符串包括CCCB、CCBC、CBCC和BCCC，對(duì)應(yīng)的概率值分別為PCCCB(Ii)、PCCBC(Ii)、PCBCC(Ii)和PBCCC(Ii)。我們將在實(shí)驗(yàn)部分測(cè)試這些新特征對(duì)分詞效果的影響。

為了進(jìn)一步提高WBD方法的分詞效果，我們?cè)谶M(jìn)行統(tǒng)計(jì)N-gram字符串概率之前利用正則表達(dá)式進(jìn)行所有數(shù)字和英文字符的識(shí)別和替換。

3 基于WBD方法的在線學(xué)習(xí)分詞方法

優(yōu)秀的實(shí)時(shí)分詞系統(tǒng)不僅僅需要快速對(duì)新樣本進(jìn)行分詞，還需要能夠迅速學(xué)習(xí)新的標(biāo)注樣本，只有這樣，才能讓系統(tǒng)能夠快速引入不斷涌現(xiàn)的新詞。換言之，系統(tǒng)應(yīng)該具備在線學(xué)習(xí)的能力。在線學(xué)習(xí)(Online Learning)是指系統(tǒng)在輸入新的標(biāo)注樣本后，不需要重新學(xué)習(xí)原始的訓(xùn)練樣本，只是針對(duì)新來(lái)的標(biāo)注樣本學(xué)習(xí)就可以了。目前，在線學(xué)習(xí)本身作為機(jī)器學(xué)習(xí)的一個(gè)重要的研究問(wèn)題，備受模式識(shí)別，機(jī)器學(xué)習(xí)，自然語(yǔ)言處理等學(xué)術(shù)屆的重視。

需要強(qiáng)調(diào)的是WBD方法的核心部分是N-gram數(shù)據(jù)源，如果加入新的標(biāo)注樣本，只需要更新N-gram數(shù)據(jù)源，就相當(dāng)于更新了訓(xùn)練數(shù)據(jù)。以其中一個(gè)概率PCCB(Ii)為例，更新的概率公式如下：

其中C(ci-1,ci,Ii=1)和C(ci-1,ci)是N-gram數(shù)據(jù)源里面字符串ci-1ci的詞頻信息。這些數(shù)據(jù)都是已經(jīng)有的，不需要重新學(xué)習(xí)。Cnew(ci-1,ci,Ii=1)和Cnew(ci-1,ci)則是新標(biāo)注樣本里面字串ci-1ci的統(tǒng)計(jì)信息。Cnew(ci-1,ci,I=1)表示在新訓(xùn)練語(yǔ)料中二元字符串ci-1,ci出現(xiàn)在詞邊界前面的次數(shù)，而Cnew(ci-1,ci) 是二元字符串ci-1,ci在新訓(xùn)練語(yǔ)料中出現(xiàn)的總次數(shù)。其他幾種N-gram的更新公式同上式類(lèi)似。在實(shí)際應(yīng)用中，如果待測(cè)樣本和新標(biāo)注樣本比較接近的話，可以通過(guò)提高新樣本里面統(tǒng)計(jì)詞頻的權(quán)重來(lái)加重新標(biāo)注樣本對(duì)后期分詞的影響。

除了更新N-gram數(shù)據(jù)源之外，訓(xùn)練階段不需要任何其他的操作。因此，基于WBD的在線學(xué)習(xí)方法，需要再學(xué)習(xí)的代價(jià)非常小，可以滿足實(shí)時(shí)系統(tǒng)中的分詞需要。

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

在本實(shí)驗(yàn)中，我們將首先詳細(xì)給出WBD的分詞效果，其次，我們將測(cè)試上面提出的基于WBD的在線學(xué)習(xí)方法。

我們使用第二屆國(guó)際分詞競(jìng)賽(Bakeoff-2005)中的四組語(yǔ)料對(duì)WBD分詞方法進(jìn)行測(cè)試。每組語(yǔ)料中的訓(xùn)練語(yǔ)料用于生成各自的N-gram數(shù)據(jù)源，并隨機(jī)生成訓(xùn)練樣本中的1 000個(gè)字邊界的向量訓(xùn)練一個(gè)SVM(Support Vector Machine)分類(lèi)器。在測(cè)試過(guò)程中，測(cè)試語(yǔ)料中的所有字邊界由該組的N-gram數(shù)據(jù)源生成向量。然后用訓(xùn)練好的SVM分類(lèi)器進(jìn)行測(cè)試。

我們使用基于詞的F值作為評(píng)估標(biāo)準(zhǔn)，它是準(zhǔn)確率P和召回率R的調(diào)和平均值：F=2RP/(R+P)。為了和相關(guān)工作比較，我們也列出了未登錄詞的召回率(OOV recall)。表2～表5分別給出了WBD方法及其一些改進(jìn)方法在四組測(cè)試語(yǔ)料上面的分詞結(jié)果。其中，基準(zhǔn)的實(shí)現(xiàn)過(guò)程完全按照文獻(xiàn)[7]里面的描述，只用了5個(gè)N-gram的字符串特征。

表2 WBD及其改進(jìn)方法在Pku語(yǔ)料測(cè)試語(yǔ)料上的結(jié)果

表3 WBD及其改進(jìn)方法在Cityu語(yǔ)料測(cè)試語(yǔ)料上的結(jié)果

表4 WBD及其改進(jìn)方法在Msr語(yǔ)料測(cè)試語(yǔ)料上的結(jié)果

表5 WBD及其改進(jìn)方法在As語(yǔ)料測(cè)試語(yǔ)料上的結(jié)果

在改進(jìn)的方法中，我們只報(bào)告了CCBC和CBCC的結(jié)果，這是因?yàn)镃CCB和BCCC字串的加入對(duì)結(jié)果基本沒(méi)有影響。從這些表中可以看出，平滑在兩個(gè)語(yǔ)料上都有較好的表現(xiàn)，在另外兩個(gè)語(yǔ)料中基本保持原來(lái)的分詞效果。其他兩個(gè)改進(jìn)在所有的語(yǔ)料中都有不同程度的提高。

為了便于比較WBD同基于字的分詞方法，我們利用Porket CRF[9]工具實(shí)現(xiàn)了基于字的分詞方法，實(shí)驗(yàn)使用了字符的四種標(biāo)識(shí)類(lèi)別[10]。表6中給出該方法在Pku和Msr兩個(gè)語(yǔ)料上面的封閉測(cè)試結(jié)果(沒(méi)有用到數(shù)字英文字符識(shí)別)。相對(duì)于CRF實(shí)現(xiàn)的基于字的分詞方法，雖然WBD的分詞效果要稍微差一點(diǎn)，但是WBD所需要的訓(xùn)練時(shí)間(包括N-gram字符串概率的搜集和SVM分類(lèi)器的訓(xùn)練)要遠(yuǎn)遠(yuǎn)小于CRF的訓(xùn)練時(shí)間(我們用python實(shí)現(xiàn)的WBD方法)。

在實(shí)際分詞系統(tǒng)的應(yīng)用中，訓(xùn)練樣本和測(cè)試樣本并不能像分詞競(jìng)賽那樣限制為來(lái)自相同來(lái)源。為了模擬實(shí)際分詞無(wú)法預(yù)知測(cè)試語(yǔ)料來(lái)源的狀況，我們交換了Pku和Msr的測(cè)試語(yǔ)料。也就是說(shuō)，我們讓CRF和WBD在Pku的訓(xùn)練語(yǔ)料上面訓(xùn)練，但是在Msr的測(cè)試語(yǔ)料上面測(cè)試，這樣分詞的F值結(jié)果會(huì)大大減低到0.856和0.850(Pku→Msr)。在這個(gè)時(shí)候，CRF和WBD方法的差異已經(jīng)小到?jīng)]有統(tǒng)計(jì)上的相關(guān)性了。

表6 WBD與CRF實(shí)現(xiàn)的基于字標(biāo)注的分詞方法的比較結(jié)果

最后，我們利用WBD方法構(gòu)建一個(gè)真正實(shí)用的分詞系統(tǒng)，該系統(tǒng)使用Sinica研究院平衡語(yǔ)料產(chǎn)生N-gram數(shù)據(jù)源。該語(yǔ)料是來(lái)自中國(guó)臺(tái)灣研究員的繁體語(yǔ)料，由于Sinica語(yǔ)料在各個(gè)領(lǐng)域的分布比較均勻，我們認(rèn)為該語(yǔ)料庫(kù)能夠比較好的反映各種字符串同詞邊界的關(guān)系[11]。為了測(cè)試我們系統(tǒng)的效果以及上面提到的基于WBD的在線學(xué)習(xí)方法，我們使用部分Cityu的訓(xùn)練樣本用作我們系統(tǒng)新的標(biāo)注樣本。圖1給出了我們系統(tǒng)在Cityu測(cè)試語(yǔ)料上面的F值結(jié)果，橫坐標(biāo)表示加入新樣本的規(guī)模。從圖中可以看出，在不使用任何Cityu訓(xùn)練樣本的情況下，我們的系統(tǒng)已經(jīng)取得了近88%的F值。如果利用我們的在線學(xué)習(xí)方法，漸漸融入少量Cityu的訓(xùn)練樣本，系統(tǒng)的表現(xiàn)會(huì)越來(lái)越好。

圖1 系統(tǒng)在Cityu測(cè)試語(yǔ)料上面的F值

圖2 系統(tǒng)在Cityu測(cè)試語(yǔ)料上面的OOV Recall值

圖2給出系統(tǒng)在引入新語(yǔ)料后的OOV Recall值的變化曲線。從該圖可以看出，系統(tǒng)性能提高的一個(gè)重要原因就是新的語(yǔ)料給系統(tǒng)帶來(lái)了許多新詞，例如：“海陸空”、“社工”等詞，使得系統(tǒng)能夠更好的分好這些新詞。通過(guò)對(duì)比在線學(xué)習(xí)前后的分詞結(jié)果，我們還發(fā)現(xiàn)另外一個(gè)提高系統(tǒng)性能的重要原因：Cityu測(cè)試語(yǔ)料和Sinica語(yǔ)料的分詞標(biāo)準(zhǔn)在某些詞方面不一致，而加入Cityu的少量訓(xùn)練語(yǔ)料，能夠有效的校正不同的分詞標(biāo)準(zhǔn)。例如：在Sinica訓(xùn)練語(yǔ)料里面，“有 些”被認(rèn)為是兩個(gè)詞，而在Cityu里面“有些”被認(rèn)為是一個(gè)詞。另一個(gè)出現(xiàn)比較多的例子是，在Sinica訓(xùn)練語(yǔ)料里面，“x月x日”分詞為“x月 x 日”(其中“x”代表數(shù)字，“x”和“日”是分開(kāi)的)，而在Cityu里面被分為“x月 x日”(“x”和“日”是不分開(kāi)的)。

5 結(jié)論

本文研究了一種基于詞邊界分類(lèi)的分詞方法并提出改進(jìn)方法。在此基礎(chǔ)上， 我們實(shí)現(xiàn)了一種在線學(xué)習(xí)的分詞方法。實(shí)驗(yàn)結(jié)果表明，這種新的分詞方法能夠獲得接近目前主流方法的分詞效果，但只需要很少的訓(xùn)練時(shí)間。同時(shí)，我們利用提出的在線學(xué)習(xí)分詞方法和Sinica研究院平衡語(yǔ)料庫(kù)構(gòu)建了我們的分詞系統(tǒng)，該系統(tǒng)能夠在來(lái)自不同地方的語(yǔ)料中獲得比較滿意的分詞效果，并且能夠很迅速地學(xué)習(xí)新的樣本，使我們的系統(tǒng)具備很好的更新能力。

[1] 黃昌寧. 中文信息處理的分詞問(wèn)題[J]. 語(yǔ)言文字應(yīng)用, 1997, 11(1):72-78.

[2] 黃昌寧, 趙海. 中文分詞十年回顧[J]. 中文信息學(xué)報(bào), 2007, 21(3):8-20.

[3] 駱正清, 陳增武, 胡上序. 一種改進(jìn)的MM分詞方法的算法設(shè)計(jì)[J]. 中文信息學(xué)報(bào), 1996，10(3): 30-36.

[4] 吳春穎, 王士同. 基于二元語(yǔ)法的N-最大概率中文粗分模型[J]. 計(jì)算機(jī)應(yīng)用, 2007, 27(12): 332-339.

[5] Xue N. and L. Shen. Chinese word segmentation as LMR tagging[C]//Proceedings of the Second SIGHAN Workshop on Chinese Language Processing. 2003.

[6] Crammer K., O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. 2006. Online passive-aggressive algorithms[J]. Journal of Machine Learning Research, 2006(7): 551-585.

[9] http://sourceforge.net/project/showfiles.php?group_id=201943[OL].

[10] Ng H. and J. Low. Chinese part-of-speech tagging: one-at-a-time or all-at-once? Word-based or character-based?[C]//Proceedings of EMNLP. 2004.

[11] CKIP. Academia Sinica Balanced Corpus of Modern Chinese[OL]. http://www.sinica.edu.tw/SinicaCorpus/. 2001.