基于迭代算法的新詞識(shí)別

趙小寶，張華平

(北京理工大學(xué)計(jì)算機(jī)學(xué)院，北京 100081)

1 概述

詞是最小的能夠獨(dú)立應(yīng)用的有意義的語言成分[1]，中文信息處理的特有問題即漢語分詞，漢語分詞是句法分析等深層處理的基礎(chǔ)，也是機(jī)器翻譯、信息檢索和信息抽取等應(yīng)用的重要環(huán)節(jié)[2]，但隨著語言的不斷發(fā)展和進(jìn)化，新詞開始大量出現(xiàn)。特別是隨著網(wǎng)絡(luò)技術(shù)的高速發(fā)展，新詞的產(chǎn)生變得更快更多，傳播也變得更快更廣，如“拼客”、“山寨”、“蟻?zhàn)濉?、“裸婚”、“神馬都是浮云”、“給力”、“屌絲”、“高富帥”等。如果在中文分詞過程中不考慮這些新詞，不實(shí)施新詞發(fā)現(xiàn)，必然影響中文分詞的質(zhì)量。

與英語不同，中文詞語與詞語之間沒有特定的分隔標(biāo)記，任何相鄰中文字符都可能構(gòu)成一個(gè)詞語；且書面語中沒有字符形態(tài)變化，這都給中文新詞自動(dòng)檢測(cè)帶來了巨大障礙[3]。國(guó)內(nèi)外大量科研院校和科研單位都相繼開展了新詞識(shí)別研究工作，并取得了一定的研究成果。在這些研究中，主要分為有監(jiān)督和無監(jiān)督的方法。大量研究實(shí)踐表明，在沒有大規(guī)模標(biāo)注語料的情況下，使用無監(jiān)督的方法獲得候選新詞具有對(duì)語料依賴程度小、適應(yīng)能力強(qiáng)、新詞識(shí)別效果好等特點(diǎn)，因此該方法也成為新詞識(shí)別領(lǐng)域比較流行的研究方法。本文介紹新詞發(fā)現(xiàn)研究的相關(guān)工作及衡量詞語內(nèi)聚性的特征，論述衡量詞語外部靈活性的特征，提出一種左鄰右平均熵和右鄰左平均熵的計(jì)算方法。

2 相關(guān)工作

眾多研究者從不同角度應(yīng)用不同的方法進(jìn)行了研究。利用遞增的N-Gram模型提取重復(fù)模式，在此基礎(chǔ)上使用手工編制的提取和過濾規(guī)則從互聯(lián)網(wǎng)語料中提取新詞[4]的方法，其主要思想是先統(tǒng)計(jì)所有二字串的頻次，然后逐步統(tǒng)計(jì)三字串，四字串，五字串，……，記CRF錄每一次擴(kuò)展的字串以及對(duì)應(yīng)頻次，到達(dá)句末或者是字串長(zhǎng)度達(dá)到閾值時(shí)停止擴(kuò)展。該方法的優(yōu)點(diǎn)是空間復(fù)雜度低，但時(shí)間復(fù)雜度較高。在此方法的基礎(chǔ)上，使用正則表達(dá)式來表示過濾規(guī)則[5]，可實(shí)現(xiàn)任意長(zhǎng)度新詞的檢測(cè)。另一種新詞檢測(cè)方法是采用形式化描述模型在框架下判斷是否是新詞[6]。其訓(xùn)練和解碼所選用的語言知識(shí)特征包括前綴、雙字前綴、后綴、雙字后綴、串長(zhǎng)、命名實(shí)體后綴、候選模式的出現(xiàn)頻率、互信息、色子系數(shù)和左、右熵等11項(xiàng)。結(jié)合LDCRF和semi-CRF的基于全局特征的判別模型[7]同樣被用來進(jìn)行新詞識(shí)別和詞性猜測(cè)。首先利用LDCRF識(shí)別新詞候選，然后利用semi-CRF對(duì)新詞候選的Nbest進(jìn)行剪枝和過濾，得到新詞。該方法加快訓(xùn)練速度，縮短了計(jì)算時(shí)間。以上2種方法的優(yōu)點(diǎn)是無監(jiān)督方式進(jìn)行新詞識(shí)別，不需要過多的人工干預(yù)，缺點(diǎn)是易受訓(xùn)練數(shù)據(jù)的影響，訓(xùn)練特征的選擇導(dǎo)致了人工工作量的增加。在分詞的過程中進(jìn)行新詞識(shí)別的方法[8]提出了一種快速的分詞訓(xùn)練法——ADF，利用該方法得到的模型即使在多維特征的數(shù)據(jù)集上依然能夠快速的進(jìn)行分詞和新詞識(shí)別。針對(duì)專業(yè)領(lǐng)域的新詞識(shí)別[9]，第1步是構(gòu)建專業(yè)領(lǐng)域詞典，第2步是利用該詞典尋找該專業(yè)的專家用戶，最后從專家用戶的輸入內(nèi)容中提取該領(lǐng)域的新詞，該方法只能識(shí)別某一領(lǐng)域內(nèi)的新詞，構(gòu)建專業(yè)領(lǐng)域詞典需要人工參與，而且專家用戶的選擇會(huì)直接影響到新詞識(shí)別的結(jié)果。另外還有一些研究者在位置成詞概率的基礎(chǔ)上，結(jié)合新詞內(nèi)部模式的特征，綜合互信息、鄰接類別等統(tǒng)計(jì)量對(duì)新詞進(jìn)行識(shí)別[10]。

本文針對(duì)以上方法的優(yōu)缺點(diǎn)，考慮到詞語的結(jié)構(gòu)特性，把詞語內(nèi)部的凝聚程度(內(nèi)聚度)和外部的靈活程度(靈活度)作為識(shí)別新詞的特征，提出一種基于完全無監(jiān)督的新詞識(shí)別算法。該算法提出使用左鄰右平均熵和右鄰左平均熵作為表征詞語外部靈活性的特征，新詞發(fā)現(xiàn)的正確率得到一定程度的提升。

3 新詞識(shí)別

3.1 基本設(shè)計(jì)理念

在自然語言處理過程中，詞是最小的可以獨(dú)立應(yīng)用的語言單位。其中無監(jiān)督的分詞方法——ESA[11]綜合了頻率、長(zhǎng)度、左(右)信息熵等特征計(jì)算字符串的IV(AB)值和2個(gè)子串連接在一起時(shí)的CV(AB)值，判定字符(串)AB是獨(dú)立成詞還是子串A和B分別成詞，通過反復(fù)迭代，最終將一串字符進(jìn)行粗切分，并利用局部最優(yōu)化方法進(jìn)行最優(yōu)化，選出最優(yōu)序列作為最終分詞結(jié)果。新詞作為詞的有機(jī)組成部分，同樣也會(huì)擁有詞語的所有特性。在結(jié)構(gòu)上，新詞應(yīng)該具有較高的內(nèi)聚性和靈活性，這樣才能滿足獨(dú)立應(yīng)用的要求。

到目前為止，學(xué)術(shù)界對(duì)于新詞的定義仍然沒有達(dá)成共識(shí)。這里所說的新詞指的是自動(dòng)分詞工具未能正常切分且可以獨(dú)立表達(dá)完整意義的詞。這些詞或者是由已經(jīng)存在的多字詞組成(如：“中國(guó)特色社會(huì)主義”是由中國(guó)、特色、社會(huì)主義3個(gè)多字詞組成)，或者是由單字詞組成(如：“高富帥”是由高、富、帥3個(gè)單字詞組成，“白富美”是由白、富、美3個(gè)單字詞組成)。從這些詞的后驗(yàn)表現(xiàn)上看，這些新詞都有一個(gè)共同的特點(diǎn)：出現(xiàn)頻率高，內(nèi)部結(jié)合緊密(內(nèi)聚性高)，上下文語境靈活(靈活性高)。假設(shè)一個(gè)字串在語料中反復(fù)出現(xiàn)(高于一定的頻率閾值)、內(nèi)部結(jié)合緊密(高于一定的內(nèi)聚性特征閾值)、上下文語境靈活(高于一定的靈活性特征閾值)，可以認(rèn)定該字串是一個(gè)新詞。即使該字串不是新詞(某一靈活性特征未達(dá)到閾值，如：白富、富美)，它仍有可能是某一新詞的一個(gè)組成部分，可以反復(fù)迭代以解決類似問題。

綜合上述思想，本文算法使用迭代方法，利用內(nèi)聚性(共現(xiàn)頻率、互信息)和靈活性(左熵、右熵、左鄰接右平均熵、右鄰接左平均熵)2個(gè)方面的6個(gè)特征對(duì)新詞進(jìn)行識(shí)別。

3.1.1 內(nèi)聚性

新詞作為一個(gè)有機(jī)的并且能夠獨(dú)立應(yīng)用的有意義的語言成分，新詞內(nèi)部各元素之間必然存在高耦合度。內(nèi)聚性作為詞語的內(nèi)部特征，有多種度量方法：共現(xiàn)頻率，色子矩陣，互信息等，本文利用共現(xiàn)頻率和互信息兩種方法度量詞語的內(nèi)聚性。

互信息(Mutual Information,MI)是信息論里一種有用的信息度量，它是用來度量2個(gè)事件集合之間的相關(guān)性，假設(shè)S是長(zhǎng)度為n的字符串，S=xy，其中，x,y為字符串S的2個(gè)子串，x=c1,c2,…,ck，y=ck+1,ck+2,…,cn，則x，y的互信息可由式(1)計(jì)算得到互信息：

其中，Pxy表示字符串S在待分析語料中出現(xiàn)的頻率；Px表示子串x在待分析語料中出現(xiàn)的概率；Py表示子串y在待分析語料中出現(xiàn)的概率。

3.1.2 靈活性

作為一個(gè)獨(dú)立的語言成分，新詞應(yīng)該比非獨(dú)立的語言成分具有更靈活的應(yīng)用場(chǎng)合。人們用熵來衡量對(duì)事物的不確定性，熵越大，表示人們對(duì)該事物認(rèn)知的不確定性越大，對(duì)應(yīng)的，該事物對(duì)于人們來說就具有很高的靈活性；反之，說明人們對(duì)該事物的認(rèn)知是確定的，此時(shí)該事物對(duì)于人們來說是確定的，失去了靈活性。左(右)熵是度量人們對(duì)于新詞左(右)鄰接的不確定性，即新詞的左(右)靈活性。左熵和右熵可以分別由式(2)、式(3)計(jì)算得到。受對(duì)偶原理的啟發(fā)，若一個(gè)字符串是新詞，其左鄰接應(yīng)該具有較高的右靈活性，同樣的，其右鄰接應(yīng)該具有較高的左靈活性。進(jìn)一步，該算法用左(右)鄰接右(左)平均熵作為左(右)鄰接右(左)靈活性的判定特征，可以分別由式(6)、式(7)計(jì)算得到。

3.2 算法流程

基于迭代算法的新詞識(shí)別算法流程如圖1所示，具體流程為：用中文自動(dòng)分詞工具對(duì)語料進(jìn)行中文分詞和詞性標(biāo)注；對(duì)分詞后的結(jié)果進(jìn)行詞頻統(tǒng)計(jì)，找出重復(fù)模式。統(tǒng)計(jì)過程中利用詞性進(jìn)行停用詞過濾。該過程利用兩遍掃描法進(jìn)行詞頻統(tǒng)計(jì)，有效地提高了程序運(yùn)行速度。第一遍掃描只統(tǒng)計(jì)單個(gè)詞語的詞頻，將低于一定閾值的詞加入到過濾詞表(因?yàn)槿绻粋€(gè)詞的詞頻低于該閾值，則包含該詞的字符串肯定不會(huì)大于該閾值)，第二遍掃描時(shí)，只統(tǒng)計(jì)不以排除詞表(過濾詞表和詞性過濾列表，其中詞性過濾列表由人工添加)中的詞作為子串的字符串；再次，找出重復(fù)模式，統(tǒng)計(jì)重復(fù)模式的左(右)鄰接信息，計(jì)算重復(fù)模式的互信息、左(右)熵、左(右)鄰接右(左)平均熵，利用這些特征信息進(jìn)行新詞識(shí)別，獲得新詞候選列表；最后，利用中文詞語搭配庫[12]對(duì)候選結(jié)果進(jìn)行最后過濾，得到最終的新詞列表。

圖1 基于迭代算法的新詞識(shí)別算法流程

3.3 新詞識(shí)別過程描述

新詞識(shí)別是一個(gè)層疊迭代的過程，如圖2所示，其中實(shí)線表示算法流程，虛線表示迭代層級(jí)。該算法主要包括一個(gè)核心過程和2個(gè)子過程，首先介紹2個(gè)子過程。描述中常用符號(hào)說明見表1。

圖2 新詞識(shí)別過程示意圖

表1 符號(hào)說明

子過程1主要通過2次掃描獲得重復(fù)模式列表：第1次掃描進(jìn)行詞頻統(tǒng)計(jì)，根據(jù)設(shè)置閾值獲得過濾詞表，第2次掃描基于過濾詞表和詞性過濾列表獲得重復(fù)模式列表。

假設(shè)語料中的用詞個(gè)數(shù)為n，第1遍掃描的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。如果重復(fù)模式平均由m個(gè)詞構(gòu)成，第2遍掃描的時(shí)間復(fù)雜度為O(nm)，空間復(fù)雜度為O(n)。該子過程的時(shí)間復(fù)雜度為O(n+mn)，該算法所占用的空間主要為O(n)。

子過程2是整個(gè)算法中的核心子過程，計(jì)算給定重復(fù)模式的內(nèi)聚性和靈活性特征的值。

該過程是整個(gè)算法中時(shí)間復(fù)雜度和空間復(fù)雜度最高的部分。由式(1)、式(2)、式(3)、式(6)、式(7)計(jì)算5項(xiàng)特征的值，時(shí)間復(fù)雜度主要取決于后4項(xiàng)特征值的計(jì)算時(shí)間，假設(shè)平均每一個(gè)重復(fù)模式包含ml個(gè)左鄰接和mr右鄰接，每一個(gè)左鄰接的平均右鄰接個(gè)數(shù)為mlr，每一個(gè)右鄰接的平均左鄰接個(gè)數(shù)為mrl，則該過程的時(shí)間復(fù)雜度為O(mlmlr+mrmrl)，空間復(fù)雜度為5個(gè)特征值的空間，即O(1)。

核心過程負(fù)責(zé)2個(gè)子過程的執(zhí)行和判定重復(fù)模式是否為新詞，是從原始語料識(shí)別新詞、得到新詞列表的過程。

該過程的時(shí)間和空間復(fù)雜度主要取決于子過程1和子過程2，假設(shè)總共有m個(gè)重復(fù)模式，時(shí)間復(fù)雜度為：O(mn+m×(mlmlr+mrmrl))；空間復(fù)雜度為：O(n+m)。

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

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)在普通的PC單機(jī)上進(jìn)行，采用Windows操作系統(tǒng)，CPU為2.4 GHz×2，內(nèi)存為3 GB，算法的實(shí)現(xiàn)代碼采用C/C++語言實(shí)現(xiàn)。

4.2 測(cè)試對(duì)象的選取

實(shí)驗(yàn)主要分兩部分進(jìn)行，實(shí)驗(yàn)1取中國(guó)共產(chǎn)黨第十八次全國(guó)代表大會(huì)報(bào)告(以下稱十八大報(bào)告)；實(shí)驗(yàn)2取北京大學(xué)提供的98年1月的《人民日?qǐng)?bào)》手工標(biāo)注語料(以下簡(jiǎn)稱北大語料)，手工標(biāo)注后進(jìn)行實(shí)驗(yàn)。表2為語料的詳細(xì)說明。

表2 語料的詳細(xì)說明

4.3 實(shí)驗(yàn)條件設(shè)置

實(shí)驗(yàn)均采用如下設(shè)置：MI0表示互信息大于0，作為基準(zhǔn)實(shí)驗(yàn)(baseline)，LE0表示左鄰接熵大于0，RE0表示左鄰接熵大于0，LRAE0表示左鄰接右平均熵大于0，RLAE0表示右鄰接左平均熵大于0，F(xiàn)ilter表示經(jīng)過中文詞語搭配庫過濾，NoFilter表示未經(jīng)過中文詞語搭配庫過濾。

4.4 實(shí)驗(yàn)評(píng)測(cè)

在不同的條件下，新詞列表按照互信息由高到低進(jìn)行排序，取P@N作為實(shí)驗(yàn)結(jié)果的評(píng)測(cè)指標(biāo)。

正確率計(jì)算公式：

其中，p表示正確率；Nq表示正確的新詞個(gè)數(shù)；Nc表示新詞總數(shù)。

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

表3為實(shí)驗(yàn)1中不同參數(shù)下的結(jié)果比較。實(shí)驗(yàn)結(jié)果顯示，正確率均高于72%，利用互信息這一單一特征，N=100的正確率達(dá)到了72%，經(jīng)過詞語固定搭配的過濾，準(zhǔn)確率提升到78%。經(jīng)過全部5項(xiàng)特征的過濾，N=100的正確率達(dá)到83%，經(jīng)過詞語固定搭配詞典的過濾，新詞的正確率能夠達(dá)到85%。

表4為實(shí)驗(yàn)2中不同參數(shù)下的結(jié)果比較。實(shí)驗(yàn)結(jié)果顯示，正確率均高于76%，利用互信息這一單一特征，N=100的正確率達(dá)到了76%，經(jīng)過詞語固定搭配的過濾，準(zhǔn)確率提升到78%。經(jīng)過全部5項(xiàng)特征的過濾，N=100的正確率達(dá)到88%，經(jīng)過詞語固定搭配詞典的過濾，新詞的正確率能夠達(dá)到90%。

圖3、圖4分別為實(shí)驗(yàn)1和實(shí)驗(yàn)2中的部分新詞列表。

表3 實(shí)驗(yàn)1中不同參數(shù)下的結(jié)果比較%

表4 實(shí)驗(yàn)2中不同參數(shù)下的結(jié)果比較%

圖3 實(shí)驗(yàn)1中部分新詞列表

圖4 實(shí)驗(yàn)2中部分新詞列表

以上數(shù)據(jù)表明：N=10時(shí)，均有很高的正確率。隨著N的增加，正確率有一定程度的下降是因?yàn)榛バ畔⑹窃撍惴ǖ闹饕卣?，互信息的變化?duì)新詞識(shí)別的準(zhǔn)確率有直接的影響。隨著特征的逐一加入，新詞識(shí)別的正確數(shù)和正確率均呈現(xiàn)不斷上升的趨勢(shì)，證明各項(xiàng)特征均起到了提高正確率的效果。在同一實(shí)驗(yàn)條件下，固定詞語搭配詞典的過濾可以不同程度的提高正確率。當(dāng)語料的規(guī)模較小時(shí)，新詞發(fā)現(xiàn)的正確率略低，而語料規(guī)模較大時(shí)，新詞發(fā)現(xiàn)的正確率會(huì)升高，這是因?yàn)樵撍惴ㄍ耆诮y(tǒng)計(jì)方法，語料規(guī)模的越大，各項(xiàng)統(tǒng)計(jì)信息越接近真實(shí)情況。另外，左鄰接右平均熵和右鄰接左平均熵可以在一定程度上提高新詞識(shí)別的正確率，如果對(duì)新詞識(shí)別的正確率要求不高，可酌情刪除這2個(gè)特征，提高算法的執(zhí)行效率。

另外從2個(gè)實(shí)驗(yàn)的執(zhí)行時(shí)間來看，算法的執(zhí)行效率不是很高，主要有以下3個(gè)方面的原因：

(1)共現(xiàn)頻率閾值設(shè)置太小(為保證召回率)，導(dǎo)致重復(fù)模式過多，計(jì)算量增加；

(2)靈活度的4個(gè)特征值，尤其是左(右)鄰接右(左)平均熵計(jì)算復(fù)雜度過高；

(3)程序設(shè)計(jì)不盡合理，代碼執(zhí)行效率偏低。

5 結(jié)束語

本文基于迭代算法，提出了運(yùn)用左(右)鄰右(左)平均熵作為判斷重復(fù)模式是否為新詞的外部靈活度特征，采用內(nèi)聚性和靈活度等6項(xiàng)特征判斷重復(fù)模式是否為新詞，通過十八大報(bào)告和北大語料的實(shí)驗(yàn)測(cè)試，結(jié)果表明，該算法能夠有效提取新詞。通過對(duì)2組實(shí)驗(yàn)進(jìn)行對(duì)比分析發(fā)現(xiàn)，無論語料規(guī)模的大小，各項(xiàng)特征均起到提高正確率的效果。此外，語料規(guī)模對(duì)新詞發(fā)現(xiàn)的正確率也有一定的影響。語料規(guī)模越大，新詞發(fā)現(xiàn)的正確率就越高，這是因?yàn)樵摲椒ㄊ腔诮y(tǒng)計(jì)的方法，數(shù)據(jù)量越大，統(tǒng)計(jì)數(shù)據(jù)的可靠性也越高，正確率也就越大，表明使用非監(jiān)督的統(tǒng)計(jì)方法整合有效特征是一種非常有前途的新詞識(shí)別研究方法。

下一步工作是充分挖掘有效的新詞檢測(cè)特征并將其放入統(tǒng)計(jì)框架中，以進(jìn)一步改進(jìn)新詞檢測(cè)效果與算法的執(zhí)行效率，利用機(jī)器學(xué)習(xí)的方法學(xué)習(xí)各個(gè)特征的閾值，減少人工干預(yù)，以便將該方法整合到中文分詞技術(shù)中，提高中文分詞效果。

[1]朱德熙.語法講義[M].北京:商務(wù)印書館,2004.

[2]劉 群,張華平,俞鴻魁,等.基于層疊隱馬模型的漢語詞法分析[J].計(jì)算機(jī)研究與發(fā)展,2004,41(8):1421-1429.

[3]李 鈍,屠 衛(wèi),石 磊,等.基于上下文感知的中文新詞識(shí)別算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(10):4022-4027.

[4]鄭家恒,李文花.基于構(gòu)詞法的網(wǎng)絡(luò)新詞自動(dòng)識(shí)別初探[J].山西大學(xué)學(xué)報(bào):自然科學(xué)版,2002,25(2):115-119.

[5]鄒 剛,劉 群.面向Internet的中文新詞語檢測(cè)[J].中文信息學(xué)報(bào),2004,18(6):1-9.

[6]張海軍,欒 靜,李 勇,等.基于統(tǒng)計(jì)學(xué)習(xí)框架的中文新詞檢查方法[J].計(jì)算機(jī)科學(xué),2012,39(2):232-235.

[7]Sun Xiao,Huang Degen,Song Haiyu.Chinese New Word Identification:A Latent Discriminative Model with Global Features[J].Journal of Computer Science and Technology,2011,26(1):14-24.

[8]Sun Xu,Wang Houfeng,Li Wenjie.Association for Computational Linguistics[C]//Proc.of the 50th Annual Meeting of the Association for Computational Linguistics.[S.1.]:Association for Computational Linguistics,2012:123-128.

[9]Liu Zhiyuan,Zheng Yabin,Xie Lixing,et al.User Behaviors in Related Word Retrieval and New Word Detection:A Collaborative Perspective[J].ACM Transactions on Asian Language Information Processing,2011,10(4):20-27.

[10]林自芳,蔣秀鳳.基于改進(jìn)位置成詞概率的新詞識(shí)別[J].福州大學(xué)學(xué)報(bào):自然科學(xué)版,2011,39(1):43-48.

[11]Wang Hanshi,Zhu Jian,Tang Shiping,et al.A New Unsupervised Approach to Word Segmentation[J].Computational Linguistics,2011,37(3):421-454.

[12]搜狗實(shí)驗(yàn)室.搜狗中文詞語搭配庫[EB/OL].(2009-01-20).http://www.sogou.com/labs/resources.htm.