隱馬爾可夫模型（Hidden Markov Model，HMM）是用來描述一個(gè)含有隱含未知參數(shù)的馬爾可夫過程难咕。
本文閱讀了2篇blog，理解其中的意思，附上自己的代碼宦言，共同學(xué)習(xí)。

一感憾、理解隱馬爾科夫

1.1 舉例理解

來源：< http://www.cnblogs.com/skyme/p/4651331.html >
假設(shè)我手里有三個(gè)不同的骰子。第一個(gè)骰子是我們平常見的骰子（稱這個(gè)骰子為D6）令花，6個(gè)面阻桅，每個(gè)面（1，2兼都，3嫂沉，4，5扮碧，6）出現(xiàn)的概率是1/6趟章。第二個(gè)骰子是個(gè)四面體（稱這個(gè)骰子為D4）杏糙，每個(gè)面（1，2蚓土，3宏侍，4）出現(xiàn)的概率是1/4。第三個(gè)骰子有八個(gè)面（稱這個(gè)骰子為D8）蜀漆，每個(gè)面（1谅河，2，3确丢，4绷耍，5，6鲜侥，7褂始，8）出現(xiàn)的概率是1/8。

image.png

當(dāng)我們無法觀測(cè)到時(shí)使用哪個(gè)骰子投擲描函，僅僅能看到投擲的結(jié)果的時(shí)候崎苗。例如我們得到一個(gè)序列值：1 6 3 5 2 7 3 5 2 4。
它其實(shí)包含了：1赘阀、隱含的狀態(tài)益缠，選擇了哪個(gè)骰子；2基公、可見狀態(tài)幅慌，使用該骰子投出數(shù)值。如下：

image.png

而假設(shè)轰豆，每個(gè)狀態(tài)間轉(zhuǎn)移的概率（選擇骰子的概率）是固定的（即為不因觀測(cè)值的數(shù)值而改變）胰伍。可以得到狀態(tài)轉(zhuǎn)移矩陣酸休。

image.png

那么我們得到觀測(cè)值序列（1 6 3 5 2 7 3 5 2 4）出現(xiàn)概率的計(jì)算公式：

image.png

舉前3個(gè)觀測(cè)值（1 6 3）的例子骂租，計(jì)算如下：

image.png

以上計(jì)算中，假設(shè)選擇3個(gè)骰子的概率是相同的斑司，都是1/3渗饮。

1.2 例子抽象

通過以上例子可以抽象一下，上面的例子中：

3種不同情況的骰子宿刮，即為：狀態(tài)值集合（StatusSet）
所有可能出現(xiàn)的結(jié)果值（1互站、2、3僵缺、4胡桃、5、6磕潮、7翠胰、8）：觀察值集合（ObservedSet）
選擇不同骰子之間的概率：轉(zhuǎn)移概率矩陣（TransProbMatrix ）容贝，狀態(tài)間轉(zhuǎn)移的概率
在拿到某個(gè)骰子，投出某個(gè)觀測(cè)值的概率：發(fā)射概率矩陣（EmitProbMatrix ）-即：拿到D6這個(gè)骰子之景，投出6的概率是1/6斤富。
最初一次的狀態(tài)：初始狀態(tài)概率分布（InitStatus ）

所以，很容易得到闺兢，計(jì)算概率的方法就是茂缚，初始狀態(tài)概率分布（InitStatus ）、發(fā)射概率矩陣（EmitProbMatrix ）屋谭、轉(zhuǎn)移概率矩陣（TransProbMatrix ）的乘積脚囊。
當(dāng)某個(gè)狀態(tài)序列的概率值最大，則該狀態(tài)序列即為桐磁，出現(xiàn)該觀測(cè)值的情況下悔耘，最可能出現(xiàn)的狀態(tài)序列。

二我擂、中文分詞

該篇文章講了怎么使用隱馬爾科夫鏈作分詞衬以，原理使用上面的作為理解。下文中提到的SBME4個(gè)狀態(tài)可以類比為上文提到的3個(gè)骰子校摩。中文文字即為上文提到的投出的數(shù)字看峻。

來源：< http://blog.csdn.net/taoyanqi8932/article/details/75312822 >

2.1 模型

HMM的典型模型是一個(gè)五元組:
StatusSet: 狀態(tài)值集合
ObservedSet: 觀察值集合
TransProbMatrix: 轉(zhuǎn)移概率矩陣
EmitProbMatrix: 發(fā)射概率矩陣
InitStatus: 初始狀態(tài)分布

2.2 基本假設(shè)

HMM模型的三個(gè)基本假設(shè)如下：
有限歷史性假設(shè):
P(Status[i]|Status[i-1],Status[i-2],… Status[1]) = P(Status[i]|Status[i-1])
齊次性假設(shè)(狀態(tài)和當(dāng)前時(shí)刻無關(guān)):
P(Status[i]|Status[i-1]) = P(Status[j]|Status[j-1])
觀察值獨(dú)立性假設(shè)(觀察值只取決于當(dāng)前狀態(tài)值):
P(Observed[i]|Status[i],Status[i-1],…,Status[1]) = P(Observed[i]|Status[i])

2.3 五元組

2.3.1 狀態(tài)值集合（StatusSet）

為(B, M, E, S): {B:begin, M:middle, E:end, S:single}。分別代表每個(gè)狀態(tài)代表的是該字在詞語中的位置衙吩，B代表該字是詞語中的起始字互妓，M代表是詞語中的中間字，E代表是詞語中的結(jié)束字坤塞，S則代表是單字成詞冯勉。
如：

給你一個(gè)隱馬爾科夫鏈的例子。
可以標(biāo)注為：
給/S 你/S 一個(gè)/BE 隱馬爾科夫鏈/BMMMME 的/S 例子/BE 摹芙。/S

2.3.2 觀察值集合（ObservedSet）

為就是所有漢字(東南西北你我他…)灼狰，甚至包括標(biāo)點(diǎn)符號(hào)所組成的集合。
狀態(tài)值也就是我們要求的值浮禾，在HMM模型中文分詞中交胚，我們的輸入是一個(gè)句子(也就是觀察值序列)，輸出是這個(gè)句子中每個(gè)字的狀態(tài)值盈电。

2.3.3 初始狀態(tài)概率分布（InitStatus ）

如：

B  -0.26268660809250016
E  -3.14e+100
M  -3.14e+100
S  -1.4652633398537678

數(shù)值是對(duì)概率值取【對(duì)數(shù)】之后的結(jié)果(可以讓概率【相乘】的計(jì)算變成對(duì)數(shù)【相加】)蝴簇。其中-3.14e+100作為負(fù)無窮，也就是對(duì)應(yīng)的概率值是0挣轨。
也就是句子的第一個(gè)字屬于{B,E,M,S}這四種狀態(tài)的概率军熏。

2.3.4 轉(zhuǎn)移概率矩陣（TransProbMatrix ）

【有限歷史性假設(shè)】

轉(zhuǎn)移概率是馬爾科夫鏈轩猩。Status(i)只和Status(i-1)相關(guān)卷扮，這個(gè)假設(shè)能大大簡(jiǎn)化問題荡澎。所以，它其實(shí)就是一個(gè)4x4(4就是狀態(tài)值集合的大小)的二維矩陣晤锹。矩陣的橫坐標(biāo)和縱坐標(biāo)順序是BEMS x BEMS摩幔。(數(shù)值是概率求對(duì)數(shù)后的值）

2.3.5 發(fā)射概率矩陣（EmitProbMatrix ）

【觀察值獨(dú)立性假設(shè)】
P(Observed[i], Status[j]) = P(Status[j]) * P(Observed[i]|Status[j])
其中，P(Observed[i]|Status[j])這個(gè)值就是從EmitProbMatrix中獲取鞭铆。

2.4 使用Viterbi算法

這五元的關(guān)系是通過一個(gè)叫Viterbi的算法串接起來或衡，ObservedSet序列值是Viterbi的輸入，而StatusSet序列值是Viterbi的輸出车遂，輸入和輸出之間Viterbi算法還需要借助三個(gè)模型參數(shù)封断，分別是InitStatus, TransProbMatrix, EmitProbMatrix。

定義變量
二維數(shù)組 weight[4][15]舶担，4是狀態(tài)數(shù)(0:B,1:E,2:M,3:S)坡疼，15是輸入句子的字?jǐn)?shù)。比如 weight[0][2] 代表 狀態(tài)B的條件下衣陶，出現(xiàn)’碩’這個(gè)字的可能性柄瑰。

二維數(shù)組 path[4][15]，4是狀態(tài)數(shù)(0:B,1:E,2:M,3:S)剪况，15是輸入句子的字?jǐn)?shù)教沾。比如 path[0][2] 代表 weight[0][2]取到最大時(shí)，前一個(gè)字的狀態(tài)译断，比如 path[0][2] = 1, 則代表 weight[0][2]取到最大時(shí)授翻，前一個(gè)字(也就是明)的狀態(tài)是E。記錄前一個(gè)字的狀態(tài)是為了使用viterbi算法計(jì)算完整個(gè) weight[4][15] 之后镐作，能對(duì)輸入句子從右向左地回溯回來藏姐，找出對(duì)應(yīng)的狀態(tài)序列。

B:-0.26268660809250016
E:-3.14e+100
M:-3.14e+100
S:-1.4652633398537678

且由EmitProbMatrix可以得出

Status(B) -> Observed(小)  :  -5.79545
Status(E) -> Observed(小)  :  -7.36797
Status(M) -> Observed(小)  :  -5.09518
Status(S) -> Observed(小)  :  -6.2475

所以可以初始化 weight[i][0] 的值如下：

weight[0][0] = -0.26268660809250016 + -5.79545 = -6.05814
weight[1][0] = -3.14e+100 + -7.36797 = -3.14e+100
weight[2][0] = -3.14e+100 + -5.09518 = -3.14e+100
weight[3][0] = -1.4652633398537678 + -6.2475 = -7.71276

注意上式計(jì)算的時(shí)候是相加而不是相乘该贾，因?yàn)橹叭∵^對(duì)數(shù)的原因羔杨。

//遍歷句子，下標(biāo)i從1開始是因?yàn)閯偛懦跏蓟臅r(shí)候已經(jīng)對(duì)0初始化結(jié)束了
for(size_t i = 1; i < 15; i++)
{
    // 遍歷可能的狀態(tài)
    for(size_t j = 0; j < 4; j++) 
    {
        weight[j][i] = MIN_DOUBLE;
        path[j][i] = -1;
        //遍歷前一個(gè)字可能的狀態(tài)
        for(size_t k = 0; k < 4; k++)
        {
            double tmp = weight[k][i-1] + _transProb[k][j] + _emitProb[j][sentence[i]];
            if(tmp > weight[j][i]) // 找出最大的weight[j][i]值
            {
                weight[j][i] = tmp;
                path[j][i] = k;
            }
        }
    }
}

確定邊界條件和路徑回溯
邊界條件如下：
對(duì)于每個(gè)句子杨蛋，最后一個(gè)字的狀態(tài)只可能是 E 或者 S兜材，不可能是 M 或者 B。
所以在本文的例子中我們只需要比較 weight[1(E)][14] 和 weight[3(S)][14] 的大小即可逞力。

在本例中：
weight[1][14] = -102.492;
weight[3][14] = -101.632;
所以 S > E曙寡，也就是對(duì)于路徑回溯的起點(diǎn)是 path[3][14]。

回溯的路徑是:
SEBEMBEBEMBEBEB
倒序一下就是:
BE/BE/BME/BE/BME/BE/S
所以切詞結(jié)果就是:
小明/碩士/畢業(yè)于/中國(guó)/科學(xué)院/計(jì)算/所

三寇荧、練習(xí)與實(shí)例

這里可以通過理解上文提到的所有举庶，進(jìn)行分詞。
給出我的github練習(xí)源碼：https://github.com/longgb246/pythonstudy/blob/master/longgb/Algorithm/TextMining/NLP/HMM/HMM.py
以及數(shù)據(jù)：https://github.com/longgb246/pythonstudy/tree/master/longgb/Algorithm/TextMining/Data

3.1 預(yù)料信息

首先揩抡，需要一個(gè)完整的預(yù)料信息户侥，該預(yù)料庫(kù)需要特征：
1镀琉、覆蓋范圍廣，理論上需要覆蓋你所有可能會(huì)被分詞的文字蕊唐，否則發(fā)射矩陣為出現(xiàn)極端情況屋摔，無法分詞。
2替梨、需要文本標(biāo)注正確钓试，如一些專有名詞，"太平洋保險(xiǎn)"等等副瀑，需要被分為一個(gè)詞弓熏，因?yàn)樗且粋€(gè)公司名稱，而不應(yīng)該被分為"太平洋/保險(xiǎn)"糠睡。
提取該語料庫(kù)硝烂，可能需要人工干預(yù)。
將分詞的結(jié)果進(jìn)行標(biāo)注铜幽，按照上文提到的信息，打上SBME的標(biāo)注：

image.png

我這里的練習(xí)為了方便狮杨，直接使用jieba分詞的結(jié)果橄教，僅僅作為練習(xí)喘漏。

3.2 計(jì)算初始狀態(tài)概率分布（InitStatus ）

初始狀態(tài)即為第一次選擇的狀態(tài)的概率翩迈。
這里選擇的是語料庫(kù)中，每個(gè)句子的第一個(gè)字的狀態(tài)堤魁，統(tǒng)計(jì)該狀態(tài)的頻率返十，計(jì)算出該狀態(tài)的概率洞坑。當(dāng)然，為了確保不會(huì)出現(xiàn)一些問題瓢剿，默認(rèn)悠轩，ME是不會(huì)出現(xiàn)在句首火架，即將其概率設(shè)置為0何鸡，在矩陣中為：-3.14e+100（取了log值牛欢，方便轉(zhuǎn)化為加法計(jì)算）傍睹。
偽代碼：

content = f.readlines()
content_str = ''.join(content)            # 1拾稳、將換行拼接在一起。
content_list = content.split(split_list)   # 2龙亲、按照斷句拆分鳄炉。split_list為拂盯。＜敲摇簸呈？等斷句的符號(hào)
initStatus.append(firstStatus(content_list))    # 將每一句話的第一個(gè)字的狀態(tài)記錄下來蜕便，語料庫(kù)中，觀測(cè)與狀態(tài)按照/劃分開两嘴。
statusCount(initStatus)                   # 統(tǒng)計(jì)出現(xiàn)狀態(tài)的概率

3.3 計(jì)算轉(zhuǎn)移概率矩陣（TransProbMatrix ）

轉(zhuǎn)移概率矩陣是一個(gè)SBEMSBEM的44的矩陣憔辫，但是其中有一些是不可能轉(zhuǎn)移的信息贰您，如：B->S，E->M等等舶替，將這些情況的概率的log值設(shè)置為-3.14e+100顾瞪。其他的按照詞前后的狀態(tài)序列統(tǒng)計(jì)抛蚁，統(tǒng)計(jì)前后之間的關(guān)系，這里已知假設(shè)孵延，當(dāng)前狀態(tài)僅與前一狀態(tài)有關(guān)尘应，與更前面的狀態(tài)無關(guān)犬钢。所以玷犹，思路：

內(nèi)容按照/拆分 -> 取出狀態(tài)序列 -> 分拆為2元組 -> 統(tǒng)計(jì)前一狀態(tài)出現(xiàn)后一狀態(tài)的概率

3.4 計(jì)算發(fā)射概率矩陣（EmitProbMatrix ）

回想一下上面舉的例子洒疚，發(fā)射概率矩陣是在某狀態(tài)下油湖，出現(xiàn)某個(gè)觀測(cè)值的概率乏德，所以有吠昭，在某狀態(tài)下，所有該狀態(tài)下觀測(cè)值的概率之和為1【該處理解對(duì)于計(jì)算發(fā)射矩陣很重要府喳，即钝满，當(dāng)矩陣的列為SBEM舱沧，行為觀測(cè)值時(shí)候熟吏，某一行的概率和為1牵寺，而不是某一列的概率和為1帽氓。根據(jù)隱馬爾科夫鏈的計(jì)算公式俩块，不理解的看看本文第一部分】玉凯。
所以漫仆，統(tǒng)計(jì)方法：

內(nèi)容按照/拆分 -> 取出狀態(tài):觀測(cè)的key:value -> 統(tǒng)計(jì)某狀態(tài)下，某觀測(cè)出現(xiàn)的次數(shù)署照，即為概率值 

3.5 使用Viterbi算法

第二部分給出了建芙，Viterbi算法的方法岁钓，可以根據(jù)初始狀態(tài)概率分布（InitStatus ）品嚣、轉(zhuǎn)移概率矩陣（TransProbMatrix ）翰撑、發(fā)射概率矩陣（EmitProbMatrix ）以及觀測(cè)值眶诈，得出一個(gè)最有可能的狀態(tài)序列逝撬。按照該狀態(tài)序列宪潮，將文本劃分出來即可狡相。