中文分詞交叉型歧義消解算法

甘 蓉

(陜西工業(yè)職業(yè)技術(shù)學(xué)院汽車工程學(xué)院， 陜西 咸陽 712000)

中文分詞是自然語言處理的基礎(chǔ)和關(guān)鍵[1]。中文分詞已經(jīng)有很多成熟的算法，但是歧義識(shí)別和未登錄詞識(shí)別仍是中文分詞的2大難點(diǎn)。其中，歧義識(shí)別又分為交叉型歧義和組合型歧義[2]。對(duì)于歧義，許多研究者做了大量的工作。目前常用的歧義消解算法主要分為2種：規(guī)則型歧義消解算法和概率型歧義消解算法。規(guī)則型歧義消解算法主要采用語義、語法、詞性等規(guī)則對(duì)歧義字段進(jìn)行消歧。概率型歧義消解算法通常需要統(tǒng)計(jì)上下文信息[3](例如使用互信息、N元統(tǒng)計(jì)模型、t-測(cè)試原理、HMM模型、字標(biāo)注統(tǒng)計(jì)等方法或模型[4]統(tǒng)計(jì)上下文信息)從而進(jìn)行歧義消解。文獻(xiàn)[4]提出了一種基于詞頻的中文分詞歧義消解方法，該方法主要適用于沒有上下文的歧義消解。文獻(xiàn)[5]提出了一種針對(duì)交叉型歧義無監(jiān)督的學(xué)習(xí)方法，并比較了卡方統(tǒng)計(jì)量、t-測(cè)試差在歧義處理中的效果。文獻(xiàn)[6]提出了針對(duì)組合型歧義的消解方法，該方法考慮了詞搭配的支持度，依據(jù)支持度度量因子進(jìn)行歧義消解。文獻(xiàn)[7]利用訓(xùn)練語料中歧義字段的上下文信息建立了規(guī)則庫(kù)，然后利用統(tǒng)計(jì)方法C-SVM模型進(jìn)行歧義消解。

本文提出了一種基于正向[8]、負(fù)向[9]最大匹配算法和passive aggressive(PA)算法[10-11]結(jié)合的交叉型歧義消解算法。該方法有3個(gè)優(yōu)點(diǎn)：1)由于正向、負(fù)向最大匹配算法是基于字符串匹配的，所以速度快；2)PA算法能靈活添加任意特征模板，使得分詞訓(xùn)練和解碼都能盡可能獲得多的信息；3)PA算法是一種在線學(xué)習(xí)算法[12]，可以增量學(xué)習(xí)[13]分詞模型，以利于自適應(yīng)領(lǐng)域分詞研究。

1 相關(guān)術(shù)語

1.1 歧義識(shí)別

歧義是指對(duì)于同一句話，可能有2種或者2種以上不同的切分方法[14]。例如句子“已結(jié)婚的和尚未結(jié)婚的青年都要實(shí)行計(jì)劃生育”可能被切分成“已/結(jié)婚/的/和/尚未/結(jié)婚/的/青年”或者“已/結(jié)婚/的/和尚/未/結(jié)婚/的/青年”，計(jì)算機(jī)到底應(yīng)該怎么選擇最佳的符合人類邏輯的切分結(jié)果呢？這就是所謂的分詞歧義問題。

歧義主要分為2種類型：交集型歧義和組合型歧義。假設(shè)漢字串AXB由漢字串A、X、B組成，同時(shí)AX和XB也分別能組成詞語，則稱漢字串AXB為交集型歧義字段。例如，句子“南京市長(zhǎng)江大橋”可以切分為“南京市/長(zhǎng)江大橋”和“南京/市長(zhǎng)/江大橋”，其中，“南京市長(zhǎng)江大橋”為交集型歧義字段。假設(shè)漢字串AB由漢字串A、B組成，同時(shí)A、B、AB都能組成詞語，則稱漢字串AB為組合型歧義字段。例如，句子“中華人民共和國(guó)”可以切分為“中華/人民/共/和/國(guó)”和“中華/人民/共和國(guó)”兩種，其中，“共和國(guó)”為組合型歧義字段。

1.2 正向、負(fù)向最大匹配算法

在中文分詞算法中，最大匹配算法[15]是一種基于字符串匹配的分詞方法，即按照一定的策略將自然語言中的漢字串與詞典中的詞條進(jìn)行匹配，如果在詞典中找到這個(gè)字符串，則匹配成功，即分出了一個(gè)詞，如果沒有找到這個(gè)字符串，則按照一定的策略繼續(xù)匹配。按照字符串匹配的方向，最大匹配算法可以細(xì)分為正向最大匹配法和負(fù)向最大匹配法。

正向最大匹配法：從左到右將待分詞文本中的幾個(gè)連續(xù)字符與詞表匹配，如果匹配上，則切分出一個(gè)詞，但要做到最大匹配，并不是第一次匹配到就可以切分的，最大匹配出的詞必須保證下一個(gè)掃描不是詞表中的詞或詞的前綴才可以結(jié)束。

負(fù)向最大匹配算法：從右往左將待分詞文本中的幾個(gè)連續(xù)字符與詞表匹配。切分方向與正向最大匹配算法相反，但切分規(guī)則相同。

1.3 PA算法及基于PA算法的分詞

PA算法可看作對(duì)平均感知器[10]的改進(jìn)。平均感知器算法雖然最后收斂到一個(gè)線性分類面，但這個(gè)線性分類面到底有多好，卻沒有評(píng)判標(biāo)準(zhǔn)。在平均感知器中，每次調(diào)整參數(shù)總是移動(dòng)一個(gè)固定步長(zhǎng)，通常是1，在該算法中，移動(dòng)的步長(zhǎng)需要通過一個(gè)優(yōu)化準(zhǔn)則確定，即在滿足調(diào)整后參數(shù)能產(chǎn)生正確預(yù)測(cè)的前提下，相對(duì)于調(diào)整前的參數(shù)w′做出最小調(diào)整：

s.t.ξ+wTΦ(x,y′)≥wTΦ(x,y)+l(y′,y),ξ≥0。

PA算法將分詞任務(wù)建模為基于字的序列標(biāo)注問題。對(duì)于輸入句子的字序列，模型給句子中的每個(gè)字標(biāo)注一個(gè)標(biāo)識(shí)詞邊界的標(biāo)記，采用的標(biāo)記集如表1所示。

表1 標(biāo)記集

以“我愛自然語言處理”為例，標(biāo)注結(jié)果如表2所示。

表2 分詞序列標(biāo)注示例

對(duì)于分詞模型，使用3種特征：基本模型特征、字符疊字特征、基于字的詞典特征，如表3—5所示。在表3中，ch[0]表示當(dāng)前字，ch[-1]表示當(dāng)前字的前1個(gè)位置上的字，ch[-2]表示當(dāng)前字的前2個(gè)位置上的字，ch[1]表示當(dāng)前字后1個(gè)位置上的字，ch[2]表示當(dāng)前字后2個(gè)位置上的字，故ch[-2]-ch[-1]表示的是當(dāng)前字前2個(gè)位置上的字和前1個(gè)位置上的字的組合，ch[-1]-ch[0]表示當(dāng)前字與前1個(gè)位置上的字的組合，ch[0]-ch[1]表示當(dāng)前字與后1個(gè)位置上的字的組合，ch[1]-ch[2]表示當(dāng)前字的后1個(gè)位置上的字和后2個(gè)位置上的字的組合。表4中ch[-1]=ch[0]？表示判斷當(dāng)前字與前1個(gè)位置上的字是否相同，ch[-2]=ch[0]？表示判斷當(dāng)前字與前2個(gè)位置上的字是否相同。當(dāng)相同時(shí)，給出一個(gè)標(biāo)記，例如名詞形式的“T”；不同時(shí)，給出一個(gè)能區(qū)別于相同情況的標(biāo)記，例如“F”。表5描述了基于字的詞典特征，即這個(gè)字的位置在詞語的開始、中間還是結(jié)尾，也就是說，這個(gè)字是詞語的詞首、詞中還是詞尾。

表3 基本特征模板

表4 字符疊字特征

表5 基于字詞典特征

2 基于正向、負(fù)向最大匹配算法和PA算法結(jié)合的交叉型歧義消解方法

圖1描述了基于正向、負(fù)向最大匹配算法和PA算法結(jié)合進(jìn)行交叉型歧義消解的流程。由圖1可看出，基于正向、負(fù)向最大匹配算法和PA算法結(jié)合進(jìn)行交叉型歧義消解方法的主要步驟如下：1)基于PA算法在訓(xùn)練語料上訓(xùn)練分詞模型； 2)基于正向最大匹配算法和負(fù)向最大匹配算法檢測(cè)出存在交叉型歧義的部分； 3)把存在交叉型歧義的部分傳遞給分詞模型，進(jìn)行解碼； 4)拼接基于正向、負(fù)向最大匹配算法分詞結(jié)果中無歧義部分和解碼結(jié)果，合成最終的分詞結(jié)果。

2.1 基于PA算法訓(xùn)練分詞模型

基于PA算法訓(xùn)練分詞模型的整體流程主要包括以下步驟。

第1步，建立內(nèi)部詞典，把訓(xùn)練語料中的每個(gè)詞按詞頻降序排序，從前到后依次添加到詞典中，詞典中的詞只包括2字及以上的詞，并且這些詞的詞頻和小于等于總詞頻的90%。

圖1 基于正向、負(fù)向最大匹配算法和PA算法 結(jié)合進(jìn)行交叉型歧義消解的流程圖

第2步，根據(jù)內(nèi)部詞典，利用正向最大匹配法給每個(gè)字加詞典特征(詞首？詞中？詞尾？)，其中匹配的最大長(zhǎng)度為5。

第3步，按照特征模板建立特征空間feature_space。

第4步，迭代學(xué)習(xí)，每輪對(duì)每個(gè)句子執(zhí)行：

1)按照特征模板抽取特征，句子中每個(gè)字均有N個(gè)特征(N為模板個(gè)數(shù))，從特征空間中獲取每個(gè)特征的索引idx;

2)根據(jù)_W[標(biāo)簽數(shù)*標(biāo)簽數(shù)+標(biāo)簽數(shù)*特征總數(shù)]計(jì)算發(fā)射概率矩陣和轉(zhuǎn)移概率矩陣，其中，W初始化為0；

3)解碼，得到預(yù)測(cè)的標(biāo)簽序列predict_tags；

4)收集特征，將正確的標(biāo)簽序列correct_features 和預(yù)測(cè)的標(biāo)簽序列predict_features分別轉(zhuǎn)化成2個(gè)特征向量,即根據(jù)每個(gè)特征的索引idx給對(duì)應(yīng)的vec[idx]加1，其中，vec[idx]初始化為0；

5)整合特征，把correct_features 和predict_features對(duì)應(yīng)的向量整合到update_features中,即correct_features乘1，ctx.predict_features乘 (-1)，然后相加;

6)利用PA算法學(xué)習(xí)新參數(shù)W, 更新方法為

idx=update_features.idx

elapsed=now-time[idx]

upd=scale*update_features.value

cur_val=W[idx]

W[idx]=cur_val+upd

sum[idx] += elapsed*cur_val+upd

time[idx]=now

其中，“*”表示乘法運(yùn)算，update_features.idx表示待更新特征的索引idx， update_features.value表示整合特征后特征idx對(duì)應(yīng)的值，now表示當(dāng)前迭代的次數(shù)，time記錄每個(gè)特征更新的次數(shù)，scale是更新的步長(zhǎng)，在1.3節(jié)中給出了定義，sum記錄每個(gè)特征所有更新的權(quán)重之和，W記錄每個(gè)特征的權(quán)重。

2.2 交叉型歧義檢測(cè)

正向、負(fù)向最大匹配算法分詞都是根據(jù)詞典進(jìn)行切分，故正向和負(fù)向最大匹配算法切分出來的詞一定是詞典中的詞；因此，本文認(rèn)為正向和負(fù)向最大匹配算法分詞結(jié)果一致的部分為正確切分結(jié)果，不一致的地方即產(chǎn)生歧義的位置。

2.3 解碼

解碼的整體流程主要包括以下步驟：

第1步，讀取基于PA算法已經(jīng)訓(xùn)練好的分詞模型；

第2步，讀取測(cè)試語料；

第3步，基于正向、負(fù)向最大匹配算法進(jìn)行歧義檢測(cè)；

第4步，根據(jù)訓(xùn)練階段的模板抽取歧義部分的特征；

第5步，基于Viterbi算法[16]進(jìn)行解碼。Viterbi算法是一個(gè)成熟且有大量資料的算法，故此處不再贅述。

由于PA算法是考慮上下文特征的，因此檢測(cè)出歧義部分后，把歧義部分及歧義的上下文傳遞給PA算法訓(xùn)練出來的分詞模型進(jìn)行解碼。

2.4 合成分詞結(jié)果

合成分詞結(jié)果是指把基于正向、負(fù)向最大匹配算法切分結(jié)果和解碼結(jié)果進(jìn)行拼接生成最終分詞結(jié)果。拼接的方法是把歧義部分的解碼結(jié)果和正向、負(fù)向最大匹配算法切分一致部分進(jìn)行拼接，形成最后的分詞結(jié)果。

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

實(shí)驗(yàn)包括3部分： 1)實(shí)驗(yàn)數(shù)據(jù)； 2)評(píng)測(cè)標(biāo)準(zhǔn)； 3)實(shí)驗(yàn)結(jié)果及分析。

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)分為訓(xùn)練語料和測(cè)試語料，其中，訓(xùn)練語料為2014年2—12月份人民日?qǐng)?bào)數(shù)據(jù)，共86 M，測(cè)試語料為2014年1月份人民日?qǐng)?bào)數(shù)據(jù)，共8 M。

3.2 評(píng)測(cè)標(biāo)準(zhǔn)

本文選用的評(píng)測(cè)指標(biāo)為準(zhǔn)確率(P)、召回率(R)和綜合評(píng)價(jià)指標(biāo)F-score值。具體定義為：

3.3 實(shí)驗(yàn)及分析

圖2描述了基于正向、負(fù)向最大匹配算法和PA算法結(jié)合進(jìn)行交叉型歧義消解的實(shí)驗(yàn)流程。

第1步，基于訓(xùn)練語料和PA算法訓(xùn)練出分詞模型。

第2步，基于正、負(fù)向最大匹配算法對(duì)測(cè)試語料進(jìn)行分詞，檢測(cè)出測(cè)試語料中的歧義部分和無歧義部分。

第3步，基于分詞模型對(duì)第2步中的歧義部分進(jìn)行分詞，得到分詞結(jié)果。

第4步，將第3步的分詞結(jié)果和無歧義部分組合形成最終分詞結(jié)果。

圖2 基于正向、負(fù)向最大匹配算法和PA算法 結(jié)合進(jìn)行交叉型歧義消解的實(shí)驗(yàn)流程

為驗(yàn)證本文提出的算法性能，進(jìn)行了4種實(shí)驗(yàn)：第1種，基于正向最大匹配算法分詞；第2種，基于負(fù)向最大匹配算法分詞；第3種，基于PA算法分詞；第4種，基于正向、負(fù)向最大匹配算法與PA算法結(jié)合分詞。分別統(tǒng)計(jì)這4種分詞結(jié)果中交叉型歧義的準(zhǔn)確率、召回率和F-score值，結(jié)果如表6所示。

表6 交叉型歧義結(jié)果統(tǒng)計(jì)

從分詞算法大類上講，第1種和第2種分詞方法屬于基于字符串匹配的分詞方法，第3種屬于基于統(tǒng)計(jì)的分詞方法，第4種是基于字符串匹配和統(tǒng)計(jì)結(jié)合的分詞方法。從表6可以看出，相較于前3種方法，第4種方法的結(jié)果是最優(yōu)的。其原因可以從分詞方法的特點(diǎn)解釋：基于字符串匹配的分詞方法的優(yōu)點(diǎn)是對(duì)于沒有歧義的語句分詞準(zhǔn)確性高，缺點(diǎn)是沒有歧義識(shí)別能力；基于統(tǒng)計(jì)的分詞方法優(yōu)點(diǎn)是有歧義識(shí)別能力，缺點(diǎn)是準(zhǔn)確率不高；第4種方法結(jié)合基于字符串匹配和統(tǒng)計(jì)方法，既發(fā)揮了基于字符串匹配分詞方法對(duì)于沒有歧義的語句分詞準(zhǔn)確性高的優(yōu)點(diǎn)，又利用了基于統(tǒng)計(jì)方法有歧義識(shí)別能力的特點(diǎn)。

從表6可以看出：第4種方法相比于第1種方法，準(zhǔn)確率P、召回率R和F-score值分別提高了2.06%、2.26%和2.16%；第4種方法相比于第2種方法，準(zhǔn)確率P、召回率R和F-score值分別提高了1.57%、1.17%和1.37%；第4種方法相比于第3種方法，準(zhǔn)確率P、召回率R和F-score值分別提高了1.19%、1.13%和1.16%。該結(jié)果表明，基于正向、負(fù)向最大匹配算法與PA算法結(jié)合分詞能在一定程度上解決交叉型歧義。

4 結(jié)論

本文提出一種基于正向、負(fù)向最大匹配算法和PA算法結(jié)合的交叉型歧義消解算法。該方法有3個(gè)優(yōu)點(diǎn)：處理速度快；能靈活添加任意特征模板，使分詞訓(xùn)練和解碼都能盡可能多地獲得更多的信息；可增量學(xué)習(xí)分詞模型，可用于自適應(yīng)領(lǐng)域的分詞研究。實(shí)驗(yàn)證明了該方法在一定程度上解決了交叉型歧義。下一步工作將繼續(xù)深入研究交叉型歧義的解決方法。另外，針對(duì)不同的分詞要求，也將研究解決組合型歧義的方法。