前言

最近在重刷李航老師的《統(tǒng)計(jì)機(jī)器學(xué)習(xí)方法》嘗試將其與NLP結(jié)合，通過(guò)具體的NLP應(yīng)用場(chǎng)景，強(qiáng)化對(duì)書中公式的理解，最終形成「統(tǒng)計(jì)機(jī)器學(xué)習(xí)方法 for NLP」的系列。這篇將介紹隱馬爾可夫模型HMM（「絕對(duì)給你一次講明白」）并基于HMM完成一個(gè)中文詞性標(biāo)注的任務(wù)。

HMM是什么

「隱馬爾可夫模型（Hidden Markov Model, HMM)」 是做NLP的同學(xué)繞不過(guò)去的一個(gè)基礎(chǔ)模型, 是一個(gè)生成式模型, 通過(guò)訓(xùn)練數(shù)據(jù)學(xué)習(xí)隱變量 和觀測(cè)變量 的聯(lián)合概率分布 。

HMM具有「兩個(gè)基本假設(shè)」：

齊次馬爾可夫性假設(shè)： 時(shí)刻的隱變量 只跟前一個(gè)時(shí)刻的隱變量 有關(guān)

觀測(cè)獨(dú)立性: 任意時(shí)刻的觀測(cè)變量 只與該時(shí)刻的隱變量 有關(guān)。所以可以構(gòu)成下面一個(gè)有向圖, 從而 可以分解成圖上邊的概率乘積。

「訓(xùn)練階段」：通過(guò)對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行極大似然估計(jì), 得到HMM模型的參數(shù)：初始概率向量 (對(duì)應(yīng)圖中的 )，隱變量之間的轉(zhuǎn)移概率矩陣 (對(duì)應(yīng)圖中的 ，隱變量到觀測(cè)變量之前的轉(zhuǎn)移概率矩陣 ((對(duì)應(yīng)圖中的 。

「預(yù)測(cè)階段」: 給定觀測(cè)變量 ，解出使 概率最大的隱變量。因?yàn)镠MM是一個(gè)生成模型, 所以模型在預(yù)測(cè)階段需要從全部可能的隱變量 中找到使得 最大的那個(gè) 。然而假設(shè)步長(zhǎng)為 , 對(duì)于每一步 ，隱變量 可能的取值有 個(gè), 那么全部可能的隱變量 個(gè)數(shù)為 , 這是一個(gè)指數(shù)級(jí)的時(shí)間復(fù)雜度,窮 舉 肯 定 是 不 現(xiàn) 實(shí) 的 。 所 以 就 引 入 了 維 特 比 算 法(Viterbi algorithm)進(jìn)行剪枝。

維特比算法的簡(jiǎn)單的說(shuō)就是「提前終止了不可能路徑」。具體而言, 在每一步遍歷全部的 個(gè)節(jié)點(diǎn),對(duì)于每一個(gè)節(jié)點(diǎn)繼續(xù)遍歷可能來(lái)源于上一步的 個(gè)節(jié)點(diǎn), 只保留上一步 () 個(gè)節(jié)點(diǎn)中概率最大的路徑, 裁剪其余的 條路徑。所以時(shí)間復(fù)雜度降低到 , 相比指數(shù)級(jí)的暴力枚舉, 這是可接受的。

值得注意的是現(xiàn)在在深度學(xué)習(xí)在解碼階段基本不用「維特比算法」解碼而更多的是使用「beam search」解碼。這是因?yàn)椤妇S特比算法」需要一個(gè)很強(qiáng)的假設(shè)：當(dāng)前節(jié)點(diǎn)只與上一個(gè)點(diǎn)有關(guān), 這也正是齊次馬爾可夫性假設(shè), 所以路徑整體概率才可以表示成各個(gè)子路徑相乘的形式。但是深度學(xué)習(xí)時(shí)代的解碼則不滿足這個(gè)假設(shè), 即, 而需要整體考慮, 所以beam search始終保留「整體最優(yōu)」的個(gè)結(jié)果。

基于HMM的詞性標(biāo)注

詞性標(biāo)注是指給定一句話(已經(jīng)完成了分詞)，給這個(gè)句子中的每個(gè)詞標(biāo)記上詞性，例如名詞，動(dòng)詞，形容詞等。這是一項(xiàng)最基礎(chǔ)的NLP任務(wù)，可以給很多高級(jí)的NLP任務(wù)例如信息抽取，語(yǔ)音識(shí)別等提供有用的先驗(yàn)信息。

這個(gè)任務(wù)中我們認(rèn)為隱變量是詞性(名詞，動(dòng)詞等)，觀測(cè)變量是中文的詞語(yǔ)，需要進(jìn)行的建模。

下面將分為：「數(shù)據(jù)處理，模型訓(xùn)練，模型預(yù)測(cè)」 三個(gè)部分 來(lái)介紹如果利用HMM實(shí)現(xiàn)詞性標(biāo)注

數(shù)據(jù)處理

這里采用「1998人民日?qǐng)?bào)詞性標(biāo)注語(yǔ)料庫(kù)」進(jìn)行模型的訓(xùn)練，包括44個(gè)基本詞性以及19484個(gè)句子。具體可以參考這里：https://www.heywhale.com/mw/dataset/5ce7983cd10470002b334de3

PFR語(yǔ)料庫(kù)是對(duì)人民日?qǐng)?bào)1998年上半年的純文本語(yǔ)料進(jìn)行了詞語(yǔ)切分和詞性標(biāo)注制作而成的，嚴(yán)格按照人民日?qǐng)?bào)的日期、版序、文章順序編排的。文章中的每個(gè)詞語(yǔ)都帶有詞性標(biāo)記。目前的標(biāo)記集里有26個(gè)基本詞類標(biāo)記（名詞n、時(shí)間詞t、處所詞s、方位詞f、數(shù)詞m、量詞q、區(qū)別詞b、代詞r、動(dòng)詞v、形容詞a、狀態(tài)詞z、副詞d、介詞p、連詞c、助詞u、語(yǔ)氣詞y、嘆詞e、擬聲詞o、成語(yǔ)i、習(xí)慣用語(yǔ)l、簡(jiǎn)稱j、前接成分h、后接成分k、語(yǔ)素g、非語(yǔ)素字x、標(biāo)點(diǎn)符號(hào)w）外，從語(yǔ)料庫(kù)應(yīng)用的角度，增加了專有名詞（人名nr、地名ns、機(jī)構(gòu)名稱nt、其他專有名詞nz）；從語(yǔ)言學(xué)角度也增加了一些標(biāo)記，總共使用了40多個(gè)個(gè)標(biāo)記。

2. 模型訓(xùn)練

根據(jù)數(shù)據(jù)估計(jì)HMM的模型參數(shù)：全部的詞性集合，全部的詞集合，初始概率向量，詞性到詞性的轉(zhuǎn)移矩陣 ?，詞性到詞的轉(zhuǎn)移矩陣。 這里直接采用頻率估計(jì)概率的方法，但是對(duì)于會(huì)存在大量的0，所以需要進(jìn)一步采用「拉普拉斯平滑處理」。

#?統(tǒng)計(jì)words和tags
words?=?set()
tags?=?set()
for?words_with_tag?in?sentences:
????for?word_with_tag?in?words_with_tag:
????????word,?tag?=?word_with_tag
????????words.add(word)
????????tags.add(tag)
words?=?list(words)
tags?=?list(tags)
#?統(tǒng)計(jì)?詞性到詞性轉(zhuǎn)移矩陣A?詞性到詞轉(zhuǎn)移矩陣B?初始向量pi
#?先初始化
A?=?{tag:?{tag:?0?for?tag?in?tags}?for?tag?in?tags}
B?=?{tag:?{word:?0?for?word?in?words}?for?tag?in?tags}
pi?=?{tag:?0?for?tag?in?tags}
#?統(tǒng)計(jì)A，B
for?words_with_tag?in?sentences:
????head_word,?head_tag?=?words_with_tag[0]
????pi[head_tag]?+=?1
????B[head_tag][head_word]?+=?1
????for?i?in?range(1,?len(words_with_tag)):
????????A[words_with_tag[i-1][1]][words_with_tag[i][1]]?+=?1
????????B[words_with_tag[i][1]][words_with_tag[i][0]]?+=?1
#?拉普拉斯平滑處理并轉(zhuǎn)換成概率
sum_pi_tag?=?sum(pi.values())
for?tag?in?tags:
????pi[tag]?=?(pi[tag]?+?1)?/?(sum_pi_tag?+?len(tags))
????sum_A_tag?=?sum(A[tag].values())
????sum_B_tag?=?sum(B[tag].values())
????for?next_tag?in?tags:
????????A[tag][next_tag]?=?(A[tag][next_tag]?+?1)?/?(sum_A_tag?+?len(tags))
????for?word?in?words:
????????B[tag][word]?=?(B[tag][word]?+?1)?/?(sum_B_tag?+?len(words))

看一下詞性轉(zhuǎn)移矩陣

3. 模型預(yù)測(cè)

在預(yù)測(cè)階段基于維特比算法進(jìn)行解碼

def?decode_by_viterbi(sentence):
????words?=?sentence.split()
????sen_length?=?len(words)
????T1?=?[{tag:?float('-inf')?for?tag?in?tags}?for?i?in?range(sen_length)]
????T2?=?[{tag:?None?for?tag?in?tags}?for?i?in?range(sen_length)]
????#?先進(jìn)行第一步
????for?tag?in?tags:
????????T1[0][tag]?=?math.log(pi[tag])?+?math.log(B[tag][words[0]])
????#?繼續(xù)后續(xù)解碼
????for?i?in?range(1,?sen_length):
????????for?tag?in?tags:
????????????for?pre_tag?in?tags:
????????????????current_prob?=?T1[i-1][pre_tag]?+?math.log(A[pre_tag][tag])?+?math.log(B[tag][words[i]])
????????????????if?current_prob?>?T1[i][tag]:
????????????????????T1[i][tag]?=?current_prob
????????????????????T2[i][tag]?=?pre_tag
????#?獲取最后一步的解碼結(jié)果
????last_step_result?=?[(tag,?prob)?for?tag,?prob?in?T1[sen_length-1].items()]
????last_step_result.sort(key=lambda?x:?-1*x[1])
????last_step_tag?=?last_step_result[0][0]
????#?向前解碼
????step?=?sen_length?-?1
????result?=?[last_step_tag]
????while?step?>?0:
????????last_step_tag?=?T2[step][last_step_tag]
????????result.append(last_step_tag)
????????step?-=?1
????result.reverse()
????return?list(zip(words,?result))

最后進(jìn)行簡(jiǎn)單的測(cè)試

decode_by_viterbi('我?和?我?的?祖國(guó)')
[('我',?'r/代詞'),?
?('和',?'c/連詞'),?
?('我',?'r'/代詞),?
?('的',?'u'/助詞),?
?('祖國(guó)',?'n'/名詞)]

decode_by_viterbi('中國(guó)?經(jīng)濟(jì)?迅速?發(fā)展?，?對(duì)?世界?經(jīng)濟(jì)?貢獻(xiàn)?很?大')?
[('中國(guó)',?'ns/地名'),
?('經(jīng)濟(jì)',?'n/名詞'),
?('迅速',?'ad/形容詞'),
?('發(fā)展',?'v/動(dòng)詞'),
?('，',?'w/其他'),
?('對(duì)',?'p/介詞'),
?('世界',?'n/名詞'),
?('經(jīng)濟(jì)',?'n/名詞'),
?('貢獻(xiàn)',?'n/名詞'),
?('很',?'d'/副詞),
?('大',?'a'/形容詞)]

可以看到基本都是正確的，根據(jù)文獻(xiàn)HMM一般中文詞性標(biāo)注的準(zhǔn)確率能夠達(dá)到85%以上 :)

當(dāng)然「HMM的缺陷也很明顯」，主要是兩個(gè)強(qiáng)假設(shè)在實(shí)際中是不成立的。因?yàn)殡[變量不僅僅跟前一個(gè)狀態(tài)的隱變量有關(guān)（跟之前全部的隱藏變量和觀測(cè)變量有關(guān)），同時(shí)當(dāng)前觀測(cè)變量也不僅僅跟當(dāng)前的隱變量有關(guān)（跟之前全部的隱藏變量和觀測(cè)變量有關(guān)），這也是后面深度學(xué)習(xí)中RNN等模型嘗試解決的問(wèn)題了。

編輯：黃飛