HDP與互信息相結(jié)合的中文無指導(dǎo)分詞

曹自強(qiáng)，李素建

(北京大學(xué) 計(jì)算語(yǔ)言學(xué)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100871)

1 引言

分詞是中文、日文等沒有明確詞分隔符的亞洲語(yǔ)言文本處理的最初環(huán)節(jié)，效果直接影響后續(xù)步驟。當(dāng)前絕大多數(shù)的分詞方法是有指導(dǎo)的。相比無指導(dǎo)方法，有指導(dǎo)分詞往往能取得更高準(zhǔn)確率。但是，構(gòu)建訓(xùn)練語(yǔ)料的代價(jià)非常大，并且對(duì)新詞的識(shí)別沒有十分有效的辦法。而無指導(dǎo)分詞提供了一種近似語(yǔ)言無關(guān)的分詞方法，對(duì)一些我們不了解的語(yǔ)言尤為重要。

無指導(dǎo)分詞的最初研究主要來自互信息[1]。隨后，其他一些統(tǒng)計(jì)量，包括χ2值[2]，t-測(cè)試差[3]，直接串頻統(tǒng)計(jì)[4]等，也逐漸被引入。也有學(xué)者提出將這些統(tǒng)計(jì)量相結(jié)合的方法[5]。近期， 非參數(shù)貝葉斯模型在無指導(dǎo)分詞中的應(yīng)用越來越廣泛。例如，Pitman-YorProcess(PYP)[6]，Dirichlet Process(DP)與HDP[7-8]，Hierarchical PYP(HPYP)[9]，Hierarchical HPYP(HHPYP)[10]等等。

基于統(tǒng)計(jì)量和基于貝葉斯模型的分詞方法有其各自的優(yōu)缺點(diǎn)，如表1所示。

表1 兩種無指導(dǎo)分詞方法各自的特點(diǎn)

針對(duì)兩者優(yōu)缺點(diǎn)間的互補(bǔ)性，本文將這兩種方法結(jié)合。HDP的先驗(yàn)設(shè)定是個(gè)重要問題，會(huì)直接影響到后續(xù)實(shí)驗(yàn)的速度和性能，而統(tǒng)計(jì)量互信息是通過概率表示的，對(duì)語(yǔ)言現(xiàn)象給出了較好的描述，因此本文提出互信息與HDP相結(jié)合的分詞方法，用互信息表示HDP的先驗(yàn)。同時(shí)，本文改進(jìn)了HDP的采樣過程，使其能夠處理文獻(xiàn)[8]中容易出現(xiàn)的多錯(cuò)誤長(zhǎng)字符串問題。最后，利用本模型可以結(jié)合已標(biāo)注語(yǔ)料的特點(diǎn)，進(jìn)行了半指導(dǎo)分詞實(shí)驗(yàn)。

本文其他章節(jié)的內(nèi)容組織結(jié)構(gòu)如下： 第2節(jié)簡(jiǎn)單介紹了互信息和HDP的相關(guān)知識(shí)；第3節(jié)詳述了HDP與互信息的結(jié)合方法，并對(duì)采樣過程進(jìn)行了改進(jìn)；第4節(jié)是實(shí)驗(yàn)部分，包括改進(jìn)前后的無指導(dǎo)分詞和改進(jìn)后的半指導(dǎo)分詞；第5節(jié)是對(duì)全文的總結(jié)及進(jìn)一步工作。

2 背景知識(shí)介紹

2.1 互信息簡(jiǎn)介

互信息可以衡量?jī)蓚€(gè)對(duì)象的結(jié)合能力。假設(shè)給定兩個(gè)對(duì)象x,y，它們之間的互信息定義如式(1)所示。

mi(x,y)越大，x,y就越傾向于以一個(gè)整體的形式出現(xiàn)。

應(yīng)用于分詞過程，文獻(xiàn)[1]中x,y代表任意相鄰的兩個(gè)字符。通過設(shè)定閾值就能決定兩者間是否需要切分。為了與HDP相結(jié)合，本文將x,y擴(kuò)展為任意兩個(gè)相鄰字符串。

2.2 HDP簡(jiǎn)介

對(duì)于無監(jiān)督參數(shù)模型，類的總數(shù)確定往往是一項(xiàng)很艱巨的挑戰(zhàn)，極易造成過擬合或欠擬合。而HDP是一種非參數(shù)貝葉斯模型。其參數(shù)數(shù)目隨樣本數(shù)的增加而自適應(yīng)，因此用于聚類過程，不需要事先指定好類的總數(shù)。

2.2.1 DP模型

回到DP，我們定義： 在一個(gè)劃分成K部分，每一部分Ti擁有先驗(yàn)概率H(Ti)的空間Θ中，如果一隨機(jī)過程G的概率分布滿足： (G(T1),G(T2),…,G(TK))～Dir(αH(T1),αH(T2),…,αH(TK))，則稱G滿足DP過程?？梢宰C明，對(duì)于給定的α,H，符合條件的G是唯一的，記為G～DP(α,H)，其中的α是集中參數(shù)，其大小反映了G與先驗(yàn)分布H的相似程度。

(3)

如果α=0，等式就變?yōu)樽畲笏迫还烙?jì)。因此，DP很大程度上可以理解為數(shù)據(jù)平滑[9]。

應(yīng)用于分詞過程， DP可以視為一元模型——文本中一個(gè)詞產(chǎn)生的概率只和它自身的性質(zhì)有關(guān)，與其所處的上下文環(huán)境無關(guān)。即式(4)：

(4)

p(wi+text)≈p1(wi|h)

其中p0(wi)表示由字符串c1c2,…,cK組成詞wi的先驗(yàn)概率，p1為一元模型對(duì)應(yīng)后驗(yàn)概率，h代表當(dāng)前切分狀況，twi表示切分出詞wi的數(shù)目，t表示總詞數(shù)，α0為集中參數(shù)。

2.2.2 HDP模型

HDP是對(duì)DP的改進(jìn)，它包含多層DP，前一層DP的結(jié)果作為后一層DP的先驗(yàn)。

應(yīng)用于分詞過程，兩層HDP可以被視為二元模型，它考慮了前一個(gè)詞的影響，具體概率計(jì)算公式如式(5)、式(6)所示。

(5)

p(wi|text)≈p2(wi|wi-1,h)

其中p2為二元模型對(duì)應(yīng)后驗(yàn)概率，nwi-1代表以wi-1開頭的二元組數(shù)目，n代表二元組的數(shù)目，α1為第二層DP參數(shù)的集中參數(shù)。

2.2.3 基于Gibbs Sampling的潛變量估計(jì)

Gibbs Sampling是蒙特卡洛方法。對(duì)應(yīng)于分詞任務(wù)，文獻(xiàn)[8]提出的Gibbs Sampling具體步驟為：

1. 對(duì)語(yǔ)料進(jìn)行隨機(jī)切分，求得式(4)、(5)兩式所需的各二元組數(shù)目；

2. 對(duì)語(yǔ)料中的每一句重新進(jìn)行切分。先扣除這一句本來切分的二元組數(shù)目，再考慮每個(gè)位置是切分還是合并。

假設(shè)當(dāng)前詞串為αwLw1wRwRRβ，α、β為運(yùn)算中不需要考慮的相同部分。對(duì)于w1是否需要分割成w2、w3，我們有兩個(gè)假設(shè)H1，H2，如式(6)、式(7)所示。

式中每個(gè)條件概率都通過式(5)求得。其中，字符串c1c2,…,cK成詞w的先驗(yàn)概率如式(8)所示。

p$表示產(chǎn)生切分符號(hào)的概率(常用一個(gè)自定義值表示)，p(ck)表示每個(gè)字符在文檔中出現(xiàn)的概率。

類似的，對(duì)于w1wR是否需要合并為w4，我們也有兩個(gè)假設(shè)H3,H4，如式(9)、式(10)所示。

H3(w1wR|h)

=p(w1|wL)×p(wR|w1)×p(wRR|wR)

(9)

H4(w4|h)=p(w4|wL)×p(wRR|wR)

(10)

根據(jù)兩個(gè)假設(shè)我們得到了切分和合并的概率比。然后用隨機(jī)數(shù)模擬的方式?jīng)Q定每個(gè)位置是否切分。

3 模型改進(jìn)

3.1 結(jié)合互信息的先驗(yàn)

式(8)給出的先驗(yàn)保證了高頻詞的具有較高的成詞概率，但是帶來了兩個(gè)問題。

1. 缺乏字符間的順序考量。對(duì)于給定文本，究竟有哪些潛在詞匯是固定的。例如，短語(yǔ)“我愛我家”，可以切分出的bigram只有“我愛”、“愛我”、“我家”。但按照式(9)，還統(tǒng)計(jì)了“愛家”、“家愛”、“家我”、“我我”這些不可能出現(xiàn)的bigram的概率。特別是“我我”計(jì)算出的概率還是最大的。這顯然不合理。

2. 本先驗(yàn)并不能提供是否需要?jiǎng)澐趾驮谑裁次恢们蟹值囊罁?jù)。僅考慮先驗(yàn)，我們有詞w需要切分為w1,w2的概率比是一個(gè)固定值，和劃分位置無關(guān)。大大弱化了先驗(yàn)的作用，如式(11)所示。

利用互信息的思想，本文直接計(jì)算字符串出現(xiàn)的概率表示該字符串成詞的先驗(yàn)概率如式(12)所示。

則w是否要切分成w1,w2的先驗(yàn)決策就取決于比例如式(13)所示。

恰好是互信息的等價(jià)形式，可以較好指導(dǎo)分詞。

同時(shí)，本文還考慮了漢語(yǔ)中的詞長(zhǎng)分布特性。長(zhǎng)度為1或2的詞遠(yuǎn)多于其他，因此在先驗(yàn)中引入一個(gè)詞長(zhǎng)概率分布p(length=w.length)。為簡(jiǎn)單起見，本文假設(shè)漢語(yǔ)的詞長(zhǎng)滿足泊松分布。所以，最終的先驗(yàn)概率計(jì)算公式如式(14)所示。

3.2 采樣的改進(jìn)

文獻(xiàn)[8]的采樣過程中僅考慮當(dāng)前切分的字符串w1是否需要二分為w2、w3，這是帶有缺陷的。例如，w1=“學(xué)習(xí)和掌握”，是由3個(gè)詞組成，不論如何二分，w2、w3，中最多有一個(gè)劃分正確。不妨令w2=“學(xué)習(xí)”、w3=“和掌握”。由于切分有誤的詞匯在語(yǔ)料中一般很少出現(xiàn)，我們有：

p(w1|wL),p(wR|w1),p(w3|w2),p(wR|w3)≈0
0?p(w2|wL)<1

計(jì)算(6)(7)兩式之比:

即不切分的概率反而高于要切分，即使w2是正確的。

經(jīng)過實(shí)驗(yàn)統(tǒng)計(jì)，絕大多數(shù)的錯(cuò)誤就來源此類需要三分的問題。本文決定在二分完畢后，再對(duì)每個(gè)詞長(zhǎng)超過一定閾值(設(shè)為3)且H1接近0的w1考察是否需要三分為w2、w3、w4。即新假設(shè)如式(15)所示。

為了計(jì)算快捷，僅將最大的H5與H1比較，衡量是否需要三分。

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

本文準(zhǔn)備了兩份語(yǔ)料——A： 2000年12月《人民日?qǐng)?bào)》部分(總詞數(shù)： 88 435)；B： 1998年1月《人民日?qǐng)?bào)》(以A為參照，已登錄詞數(shù)： 785 056，未登錄詞數(shù)： 163 387)。A和B的分詞效果差異用于衡量文本大小對(duì)無指導(dǎo)分詞的影響。A還在半指導(dǎo)分詞實(shí)驗(yàn)中作為已標(biāo)注訓(xùn)練集。

在4.1節(jié)中進(jìn)行了3種實(shí)驗(yàn)：

一、進(jìn)行文獻(xiàn)[8]的HDP無指導(dǎo)分詞作為baseline；

二、進(jìn)行3.1和3.2節(jié)的改進(jìn)后的HDP無指導(dǎo)分詞；

三、改進(jìn)后的HDP半指導(dǎo)分詞，并與常用有指導(dǎo)分詞對(duì)比。

實(shí)驗(yàn)三的有指導(dǎo)分詞基于開源工具CRF++，并直接使用工具包內(nèi)示例的分詞模板。

由于標(biāo)點(diǎn)符號(hào)必然需要切分，并且可以輕易識(shí)別，本文決定在評(píng)價(jià)時(shí)刪除標(biāo)點(diǎn)。用準(zhǔn)確率、召回率和F值衡量分詞效果，計(jì)算公式分別如下。

實(shí)驗(yàn)結(jié)果表明經(jīng)過改進(jìn)后的HDP無指導(dǎo)分詞在執(zhí)行時(shí)間以及F值上相比原方法均有明顯改善。加入較小訓(xùn)練語(yǔ)料后對(duì)已登錄詞的識(shí)別還有很大提升。

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

4.1.1 原方法

分別對(duì)語(yǔ)料A、B進(jìn)行文獻(xiàn)[8]的HDP分詞。實(shí)驗(yàn)結(jié)果如表2所示。

表2 原方法Gibbs Sampling收斂結(jié)果表

語(yǔ)料B收斂總耗時(shí)超過30h，說明本Gibbs Sampling的自相關(guān)作用(autocorrelation)很大，并不是一種高效的算法。

4.1.2 改進(jìn)后的無指導(dǎo)和半指導(dǎo)方法

進(jìn)行3.1和3.2節(jié)的改進(jìn)后的實(shí)驗(yàn)結(jié)果如表3所示。其中“A+B”代表以A為已標(biāo)注語(yǔ)料對(duì)B進(jìn)行的半指導(dǎo)分詞，用于同無指導(dǎo)分詞對(duì)比。

表3 改進(jìn)方法Gibbs Sampling收斂結(jié)果表

可見，通過改進(jìn)，分詞的F值和切分速度均有明顯改進(jìn)。語(yǔ)料B收斂總耗時(shí)10h，僅為原來三分之一。加入較小的已標(biāo)注語(yǔ)料后，總體分詞效果還有較大提升。

用A作為訓(xùn)練語(yǔ)料，對(duì)B測(cè)試的CRF分詞結(jié)果如表4所示。

表4 CRF有指導(dǎo)分詞結(jié)果表

同半指導(dǎo)的HDP不同，CRF的時(shí)間主要消耗在訓(xùn)練模型上，在測(cè)試時(shí)不需要自舉迭代。由于本實(shí)驗(yàn)訓(xùn)練語(yǔ)料規(guī)模遠(yuǎn)小于測(cè)試語(yǔ)料，因而CRF的耗時(shí)自然遠(yuǎn)小于HDP。但也正因?yàn)橛?xùn)練語(yǔ)料的不足，純有指導(dǎo)分詞又無法利用測(cè)試語(yǔ)料的信息，CRF分詞結(jié)果不如HDP。

分析半指導(dǎo)分詞的數(shù)據(jù)，結(jié)果如表5所示。

表5 半指導(dǎo)分詞結(jié)果分析表

從表中可知，雖然A的語(yǔ)料規(guī)模不到B的10%，但B相對(duì)于A的未登錄詞僅有17%，說明兩個(gè)文檔相似程度很高，半指導(dǎo)方法的優(yōu)越性并未很好體現(xiàn)。從無指導(dǎo)結(jié)果看，這些已登錄詞大部分也是高頻詞，能夠被正確識(shí)別。對(duì)比無指導(dǎo)和半指導(dǎo)結(jié)果。我們發(fā)現(xiàn)： 已登錄詞數(shù)之差≈已登錄正確數(shù)之差。F值的差別就體現(xiàn)在這6.6萬個(gè)被正確識(shí)別切分的已登錄詞。數(shù)據(jù)顯示半指導(dǎo)分詞對(duì)未登錄詞的切分改進(jìn)效果有限。

4.2 誤差分析

實(shí)驗(yàn)求得的無指導(dǎo)分詞F值0.741與半指導(dǎo)分詞F值0.809均不是特別高。造成誤差的可能原因有以下三點(diǎn)。

(1) 分詞的規(guī)則。人工分詞的結(jié)果和機(jī)器分詞的結(jié)果有一些內(nèi)在的不同。人往往會(huì)考慮詞性的區(qū)分，例如，“了的”必然不會(huì)劃分成一個(gè)詞。而機(jī)器只看統(tǒng)計(jì)結(jié)果，由于“了的”往往共同出現(xiàn)，因此易認(rèn)為是一個(gè)詞。這類情況普遍存在，例如，人名。標(biāo)準(zhǔn)答案中人名姓和名是分開的但對(duì)機(jī)器而言常見人名被分成一個(gè)詞的概率很高。

(2) 長(zhǎng)詞的切分錯(cuò)誤。式(14)的詞長(zhǎng)先驗(yàn)分布和式(15)的三分假設(shè)都基于“漢語(yǔ)傾向于生成長(zhǎng)度為1或2的詞”該假設(shè)。從實(shí)際統(tǒng)計(jì)看，該假設(shè)是合理的。不考慮標(biāo)點(diǎn)，兩者之和能占總詞數(shù)的90%。但這兩點(diǎn)必然造成分詞程序輸出長(zhǎng)詞的概率大大降低。語(yǔ)料B標(biāo)準(zhǔn)答案、無指導(dǎo)分詞、半指導(dǎo)分詞的具體詞長(zhǎng)分布情況如圖1所示。

圖1 語(yǔ)料B的詞長(zhǎng)分布圖。左： 標(biāo)準(zhǔn)答案 中： 無指導(dǎo) 右： 半指導(dǎo)

從圖1可以看出，由于3.2節(jié)設(shè)閾值為3，采樣過程中長(zhǎng)度大于3的詞基本完全被切分為較短的詞。雖然有利于整體F值的提升，但長(zhǎng)詞錯(cuò)誤率增大了不少。可能需要更加合理的權(quán)衡方法。

(3) 低頻詞。由于本實(shí)驗(yàn)是無監(jiān)督的，字串的切分與否完全取決于兩種狀態(tài)的出現(xiàn)概率比。但低頻詞成為一個(gè)詞的概率很低，因此會(huì)傾向于劃分成單字。語(yǔ)料A的分詞結(jié)果，一元詞比例比答案多了12%，二元詞比例比答案少了11%。可以看到由于A的語(yǔ)料規(guī)模遠(yuǎn)小于B，其中的低頻詞比例要高得多。相當(dāng)部分的二元詞被錯(cuò)誤切分成一元詞，影響了準(zhǔn)確率。因此，要使無指導(dǎo)分詞準(zhǔn)確，語(yǔ)料規(guī)模必須足夠大。

5 結(jié)論與進(jìn)一步工作

本文提出了HDP與互信息相結(jié)合的分詞方法，并改進(jìn)了采樣算法。實(shí)驗(yàn)表明： 本方法的切分速度、切分準(zhǔn)確率同baseline的HDP相比均有較大改進(jìn)。加入較小的訓(xùn)練語(yǔ)料后，總體F值還有較大提升。

我們的下一步工作是引入演化的HDP模型[11-12]，同時(shí)實(shí)現(xiàn)不同日期不同領(lǐng)域文本的新詞、領(lǐng)域詞與新搭配發(fā)現(xiàn)。

[1] Sproat, Richard, Shih C. A statistical method for finding word boundaries in Chinese text [J]. Computer Processing of Chinese and Oriental Languages, 1990, 4: 336-51.

[2] 黃萱菁, 吳立德. 基于機(jī)器學(xué)習(xí)的無需人工編制詞典的切詞系統(tǒng) [J]. 模式識(shí)別與人工智能, 1996, 9(4): 297-303.

[3] Maosong S, Dayang S, Tsou B K. Chinese word segmentation without using lexicon and hand-crafted training data[C]//Proceedings of the 17th International Conference on Computational linguistics-Volume 2, F, 1998.

[4] 劉挺, 吳巖, 王開鑄. 串頻統(tǒng)計(jì)和詞形匹配相結(jié)合的漢語(yǔ)自動(dòng)分詞系統(tǒng)[J]. 中文信息學(xué)報(bào)，1998, 12(1)：17-25.

[5] 孫茂松, 肖明, 鄒嘉彥. 基于無指導(dǎo)學(xué)習(xí)策略的無詞表?xiàng)l件下的漢語(yǔ)自動(dòng)分詞 [J]. 計(jì)算機(jī)學(xué)報(bào), 2004, 27(6): 736-42.

[6] Pitman J, Yor M. The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator [J]. The Annals of Probability, 1997, 25(2): 855-900.

[7] Goldwater S, Griffiths T L, Johnson M. Contextual dependencies in unsupervised word segmentation[C]//Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics, F, 2006.

[8] Goldwater S, Griffiths T L, Johnson M. A Bayesian framework for word segmentation: Exploring the effects of context [J]. Cognition, 2009, 112(1): 21-54.

[9] TEH Y W. A hierarchical Bayesian language model based on Pitman-Yor processes [C]//Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics, F, 2006.

[10] Wood F, Teh Y W. A hierarchical, hierarchical Pitman-Yor process language model[C]//Proceedings of the ICML 2008 Workshop on Nonparametric Bayes, F, 2008.

[11] Xu T, Zhang Z, Yu P S, et al. Evolutionary clustering by hierarchical dirichlet process with hidden markov state[C]//Proceedings of the Data Mining, ICDM’08 Eighth IEEE International Conference on, F, 2008. IEEE.

[12] Zhang J, Song Y, Zhang C, et al. Evolutionary hierarchical dirichlet processes for multiple correlated time-varying corpora[C]//Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining, F, 2010.