HMM的中文分詞方法

520jefferson 2020-08-25

展開(kāi)全文

逐夢(mèng)程序猿們的思考、總結(jié)

前言

隱馬爾可夫模型

HMM分詞

代碼實(shí)現(xiàn)

前言

在談?wù)勚形姆衷~基本問(wèn)題我們討論過(guò)基于詞典的分詞和基于字的分詞兩大類(lèi)，在NLP中經(jīng)典的詞典分詞方法解析文中我們利用n-gram實(shí)現(xiàn)了基于詞典的分詞方法。其中，我們也討論了這種方法的缺陷，就是OOV的問(wèn)題，即對(duì)于未登錄詞會(huì)失效在，并簡(jiǎn)單介紹了如何基于字進(jìn)行分詞，本文著重闡述下如何利用HMM實(shí)現(xiàn)基于字的分詞方法。

隱馬爾可夫模型

首先，我們將簡(jiǎn)要地介紹HMM（Hidden Markov Model）。HMM包含如下的五元組：

狀態(tài)值集合Q={q1,q2,…,qN}，其中N為可能的狀態(tài)數(shù)；
觀測(cè)值集合V={v1,v2,…,vM}，其中M為可能的觀測(cè)數(shù)；
轉(zhuǎn)移概率矩陣A=[aij]，其中aij表示從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率；
發(fā)射概率矩陣（也稱之為觀測(cè)概率矩陣）B=[bj(k)]，其中bj(k)表示在狀態(tài)j的條件下生成觀測(cè)vk的概率；
初始狀態(tài)分布π.

一般地，將HMM表示為模型λ=(A,B,π)，狀態(tài)序列為I，對(duì)應(yīng)測(cè)觀測(cè)序列為O。對(duì)于這三個(gè)基本參數(shù)，HMM有三個(gè)基本問(wèn)題：

概率計(jì)算問(wèn)題，在模型λ下觀測(cè)序列O出現(xiàn)的概率；
學(xué)習(xí)問(wèn)題，已知觀測(cè)序列O，估計(jì)模型λ的參數(shù)，使得在該模型下觀測(cè)序列P(O|λ)最大；
解碼（decoding）問(wèn)題，已知模型λ與觀測(cè)序列O，求解條件概率P(I|O)最大的狀態(tài)序列I。

HMM分詞

在（1）中我們已經(jīng)討論過(guò)基于字分詞，是如何將分詞轉(zhuǎn)換為標(biāo)簽序列問(wèn)題，這里我們簡(jiǎn)單闡述下HMM用于分詞的相關(guān)概念。將狀態(tài)值集合Q置為{B,E,M,S}，分別表示詞的開(kāi)始、結(jié)束、中間（begin、end、middle）及字符獨(dú)立成詞（single）；觀測(cè)序列即為中文句子。比如，“今天天氣不錯(cuò)”通過(guò)HMM求解得到狀態(tài)序列“B E B E B E”，則分詞結(jié)果為“今天/天氣/不錯(cuò)”。
通過(guò)上面例子，我們發(fā)現(xiàn)中文分詞的任務(wù)對(duì)應(yīng)于解碼問(wèn)題：對(duì)于字符串C={c1,…,cn}，求解最大條件概率

其中，ti表示字符ci對(duì)應(yīng)的狀態(tài)。

兩個(gè)假設(shè)

在求條件概率

我們利用貝葉斯公式可得

類(lèi)似于n-gram的情況，我們需要作出兩個(gè)假設(shè)來(lái)減少稀疏問(wèn)題：

有限歷史性假設(shè): ti 只由 ti-1 決定
獨(dú)立輸出假設(shè)：第 i 時(shí)刻的接收信號(hào) ci 只由發(fā)送信號(hào) ti 決定

即如下：

這樣我們就可以將上面的式子轉(zhuǎn)化為：

而在我們的分詞問(wèn)題中狀態(tài)T只有四種即{B,E,M,S}，其中P(T)可以作為先驗(yàn)概率通過(guò)統(tǒng)計(jì)得到，而條件概率P(C|T)即漢語(yǔ)中的某個(gè)字在某一狀態(tài)的條件下出現(xiàn)的概率，可以通過(guò)統(tǒng)計(jì)訓(xùn)練語(yǔ)料庫(kù)中的頻率得出。

Viterbi算法

有了以上東東，我們應(yīng)如何求解最優(yōu)狀態(tài)序列呢？解決的辦法便是Viterbi算法；其實(shí)，Viterbi算法本質(zhì)上是一個(gè)動(dòng)態(tài)規(guī)劃算法，利用到了狀態(tài)序列的最優(yōu)路徑滿足這樣一個(gè)特性：最優(yōu)路徑的子路徑也一定是最優(yōu)的。定義在時(shí)刻t狀態(tài)為i的概率最大值為δt(i)，則有遞推公式：

其中，ot+1即為字符ct+1。

代碼實(shí)現(xiàn)

我們基于HMM實(shí)現(xiàn)一個(gè)簡(jiǎn)單的分詞器，這里我主要從jieba分詞中抽取了HMM的部分，具體邏輯如下：
prob_start.py定義初始狀態(tài)分布π：

1P={'B': -0.26268660809250016,
2 'E': -3.14e+100,
3 'M': -3.14e+100,
4 'S': -1.4652633398537678}

prob_trans.py轉(zhuǎn)移概率矩陣A：

1P={'B': {'E': -0.510825623765990, 'M': -0.916290731874155},
2 'E': {'B': -0.5897149736854513, 'S': -0.8085250474669937},
3 'M': {'E': -0.33344856811948514, 'M': -1.2603623820268226},
4 'S': {'B': -0.7211965654669841, 'S': -0.6658631448798212}}

prob_emit.py定義了發(fā)射概率矩陣B，比如，P('和'|M)表示狀態(tài)為M的情況下出現(xiàn)“和”這個(gè)字的概率（注：在實(shí)際的代碼中漢字都用unicode編碼表示）；

1P={'B': {'一': -3.6544978750449433,
2       '丁': -8.125041941842026,
3       '七': -7.817392401429855,
4    ...}
5 'S': {':': -15.828865681131282,
6       '一': -4.92368982120877,
7       ...}
8 ...}

關(guān)于模型的訓(xùn)練作者給出了解解釋?zhuān)骸皝?lái)源主要有兩個(gè)，一個(gè)是網(wǎng)上能下載到的1998人民日?qǐng)?bào)的切分語(yǔ)料還有一個(gè)msr的切分語(yǔ)料。另一個(gè)是我自己收集的一些txt小說(shuō)，用ictclas把他們切分（可能有一定誤差）。然后用python腳本統(tǒng)計(jì)詞頻。要統(tǒng)計(jì)的主要有三個(gè)概率表：1)位置轉(zhuǎn)換概率，即B（開(kāi)頭）,M（中間),E(結(jié)尾),S(獨(dú)立成詞）四種狀態(tài)的轉(zhuǎn)移概率；2）位置到單字的發(fā)射概率，比如P('和'|M)表示一個(gè)詞的中間出現(xiàn)”和'這個(gè)字的概率；3) 詞語(yǔ)以某種狀態(tài)開(kāi)頭的概率，其實(shí)只有兩種，要么是B，要么是S?！?/p>

在seg_hmm.py中viterbi函數(shù)如下：

 1PrevStatus = {
 2    'B': 'ES',
 3    'M': 'MB',
 4    'S': 'SE',
 5    'E': 'BM'
 6}
 7
 8def viterbi(obs, states, start_p, trans_p, emit_p):
 9    V = [{}]  # tabular
10    path = {}
11    for y in states:  # init
12        V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)
13        path[y] = [y]
14    for t in range(1, len(obs)):
15        V.append({})
16        newpath = {}
17        for y in states:
18            em_p = emit_p[y].get(obs[t], MIN_FLOAT)
19            (prob, state) = max(
20                [(V[t - 1][y0] + trans_p[y0].get(y, MIN_FLOAT) + em_p, y0) for y0 in PrevStatus[y]])
21            V[t][y] = prob
22            newpath[y] = path[state] + [y]
23        path = newpath
24
25    (prob, state) = max((V[len(obs) - 1][y], y) for y in 'ES')
26
27    return (prob, path[state])

為了適配中文分詞任務(wù)，Jieba對(duì)Viterbi算法做了如下的修改：

狀態(tài)轉(zhuǎn)移時(shí)應(yīng)滿足PrevStatus條件，即狀態(tài)B的前一狀態(tài)只能是E或者S，…
最后一個(gè)狀態(tài)只能是E或者S，表示詞的結(jié)尾。

與此同時(shí)，這里在實(shí)現(xiàn)地推公式時(shí)，對(duì)其求對(duì)數(shù)，將相乘轉(zhuǎn)化成了相加：

ln\delta_{t+1}(i)=max{ln\delta_t(j)+lna_{ji}+lnb_i(c_{t+1})}

這也就是概率矩陣中出現(xiàn)了負(fù)數(shù)，是因?yàn)閷?duì)其求了對(duì)數(shù)。

實(shí)現(xiàn)效果

我們寫(xiě)一個(gè)簡(jiǎn)單的自測(cè)函數(shù)：

 1if __name__ == '__main__':
 2    ifile = ''
 3    ofile = ''
 4    try:
 5        opts, args = getopt.getopt(sys.argv[1:], 'hi:o:', ['ifile=', 'ofile='])
 6    except getopt.GetoptError:
 7        print('seg_hmm.py -i <inputfile> -o <outputfile>')
 8        sys.exit(2)
 9    for opt, arg in opts:
10        if opt == '-h':
11            print('seg_hmm.py -i <inputfile> -o <outputfile>')
12            sys.exit()
13        elif opt in ('-i', '--ifile'):
14            ifile = arg
15        elif opt in ('-o', '--ofile'):
16            ofile = arg
17
18    with open(ifile, 'rb') as inf:
19        for line in inf:
20            rs = cut(line)
21            print(' '.join(rs))
22            with open(ofile, 'a') as outf:
23                outf.write(' '.join(rs) + '\n')

運(yùn)行如下：

完整代碼

我提煉了完整的代碼放到了github上，大家可以看看HMM分詞方法的語(yǔ)料到模型，再到最終分詞預(yù)測(cè)的整個(gè)流程：
https://github.com/xlturing/machine-learning-journey/tree/master/seg_hmm

看完，趕緊點(diǎn)個(gè)“好看”鴨

點(diǎn)鴨點(diǎn)鴨

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買(mǎi)等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自： 520jefferson > 《機(jī)器學(xué)習(xí)/深度學(xué)習(xí)/tensorflow》

舉報(bào)/認(rèn)領(lǐng)