一戳晌、隱含馬爾可夫模型（Hidden Markov Model）
1奥秆、簡介
隱含馬爾可夫模型并不是俄羅斯數(shù)學家馬爾可夫發(fā)明的说庭，而是美國數(shù)學家鮑姆提出的玖像，隱含馬爾可夫模型的訓(xùn)練方法（鮑姆-韋爾奇算法）也是以他名字命名的钳垮。隱含馬爾可夫模型一直被認為是解決大多數(shù)自然語言處理問題最為快速惑淳、有效的方法。
2饺窿、馬爾可夫假設(shè)
隨機過程中各個狀態(tài)St的概率分布歧焦，只與它的前一個狀態(tài)St-1有關(guān)，即P(St|S1,S2,S3,…,St-1) = P(St|St-1)肚医。
比如绢馍，對于天氣預(yù)報，硬性假定今天的氣溫只與昨天有關(guān)而和前天無關(guān)肠套。當然這種假設(shè)未必適合所有的應(yīng)用舰涌，但是至少對以前很多不好解決的問題給出了近似解。
3你稚、馬爾可夫鏈
符合馬爾可夫假設(shè)的隨機過程稱為馬爾可夫過程瓷耙，也稱為馬爾可夫鏈。
圖：馬爾可夫鏈
在這個馬爾可夫鏈中刁赖，四個圈表示四個狀態(tài)搁痛，每條邊表示一個可能的狀態(tài)轉(zhuǎn)換，邊上的權(quán)值是轉(zhuǎn)移概率宇弛。隱含馬爾可夫鏈是上述馬爾可夫鏈的一個擴展：任一時刻t的狀態(tài)St是不可見的鸡典。所以觀察者沒法通過觀察到一個狀態(tài)序列S1,S2,S3,…,ST來推測轉(zhuǎn)移概率等參數(shù)。但是隱含馬爾可夫模型在每個時刻t會輸出一個符號Ot枪芒，而且Ot和St相關(guān)且僅和St相關(guān)彻况。這稱為獨立輸出假設(shè)谁尸。隱含馬爾可夫模型的結(jié)構(gòu)如下圖，其中隱含的狀態(tài)S1,S2,S3,…是一個典型的馬爾可夫鏈纽甘。鮑姆把這種模型稱為“隱含”馬爾可夫模型良蛮。
圖：隱含馬爾可夫模型
4、隱含馬爾可夫模型的三個基本問題
（1）給定一個模型悍赢，如何計算某個特定的輸出序列的概率背镇？?
Forward-Backward算法
（2）給定一個模型和某個特定的輸出序列，如何找到最可能產(chǎn)生這個輸出的狀態(tài)序列泽裳？
維特比算法
（3）給定足夠量的觀測數(shù)據(jù)，如何估計隱含馬爾可夫模型的參數(shù)破婆？
訓(xùn)練隱含馬爾可夫模型更實用的方式是僅僅通過大量觀測到的信號O1涮总，O2，O3祷舀，….就能推算模型參數(shù)的P(St|St-1)和P(Ot|St)的方法（無監(jiān)督訓(xùn)練算法）瀑梗，其中主要使用鮑姆-韋爾奇算法。
5裳扯、隱含馬爾可夫模型的五元組
HMM是一個五元組（O , Q , O0抛丽，A , B）:
O:{o1,o2,…,ot}是狀態(tài)集合，也稱為觀測序列饰豺。
Q:{q1,q2,…,qv}是一組輸出結(jié)果亿鲜，也稱為隱序列。
Aij?= P(qj|qi)：轉(zhuǎn)移概率分布
Bij?= P(oj|qi)：發(fā)射概率分布
O0是初始狀態(tài)冤吨，有些還有終止狀態(tài)蒿柳。
二、維特比算法（Viterbi）
1漩蟆、簡介
維特比算法是一個特殊但應(yīng)用最廣的動態(tài)規(guī)劃算法垒探，它是針對籬笆網(wǎng)絡(luò)的有向圖（Lattice）的最短路徑問題而提出的。凡是使用隱含馬爾可夫模型描述的問題都可以用維特比算法來解碼怠李，包括今天的數(shù)字通信圾叼、語音識別、機器翻譯捺癞、拼音轉(zhuǎn)漢字夷蚊、分詞等。
圖：籬笆網(wǎng)絡(luò)
2翘簇、維特比算法的基礎(chǔ)
（1）如果概率最大的路徑P（或叫最短路徑）經(jīng)過某個點撬码，比如下圖中的X22，那么這條路徑上從起始點S到X22的這一段子路徑Q版保，一定是S到X22之間的最短路徑呜笑。否則夫否，用S到X22的最短路徑R替代Q，便構(gòu)成了一條比P更短的路徑叫胁，這顯然是矛盾的凰慈。
（2）從S到E的路徑必定經(jīng)過第i時刻的某個狀態(tài)，假定第i時刻有k個狀態(tài)驼鹅，那么如果記錄了從S到第i個狀態(tài)的所有k個節(jié)點的最短路徑微谓，最終的最短路徑必經(jīng)過其中的一條。這樣输钩，在任何時刻豺型，只需要考慮非常有限條最短路徑即可。
（3）結(jié)合上述兩點买乃，假定當我們從狀態(tài)i進入狀態(tài)i+1時姻氨，從S到狀態(tài)i上各個節(jié)點的最短路徑已經(jīng)找到，并且記錄在這些節(jié)點上剪验，那么在計算從起點S到前一個狀態(tài)i所有的k個結(jié)點的最短路徑肴焊，以及從這k個節(jié)點到Xi+1，j的距離即可功戚。
3娶眷、維特比算法總結(jié)
（1）從點S出發(fā)，對于第一個狀態(tài)X1的各個節(jié)點啸臀，不妨假定有n1個届宠，計算出S到它們的距離d(S,X1i)，其中X1i代表任意狀態(tài)1的節(jié)點壳咕。因為只有一步席揽，所以這些距離都是S到它們各自的最短距離。
（2）對于第二個狀態(tài)X2的所有節(jié)點谓厘，要計算出從S到它們的最短距離幌羞。對于特點的節(jié)點X2i，從S到它的路徑可以經(jīng)過狀態(tài)1的n1中任何一個節(jié)點X1i竟稳，對應(yīng)的路徑長度就是d(S,X2i) = d(S,X1i) + d(X1i,X2i)属桦。由于j有n1種可能性，我們要一一計算他爸，找出最小值聂宾。即：
d(S,X2i) = minI=1，n1?d(S,X1i) + d(X1i,X2i)
這樣對于第二個狀態(tài)的每個節(jié)點诊笤，需要n1次乘法計算系谐。假定這個狀態(tài)有n2個節(jié)
點，把S這些節(jié)點的距離都算一遍，就有O(n1·n2)次計算纪他。
（3）接下來鄙煤，類似地按照上述方法從第二個狀態(tài)走到第三個狀態(tài)，一直走到最后一個狀態(tài)茶袒，就得到了整個網(wǎng)格從頭到尾的最短路徑梯刚。每一步計算的復(fù)雜度都和相鄰兩個狀態(tài)Si和Si+1各自的節(jié)點數(shù)目ni，ni+1的乘積成正比薪寓，即O(ni·ni+1)
（4）假設(shè)這個隱含馬爾可夫鏈中節(jié)點最多的狀態(tài)有D個節(jié)點亡资，也就是說整個網(wǎng)格的寬度為D，那么任何一步的復(fù)雜度不超過O(D2)向叉，由于網(wǎng)格長度是N锥腻，所以整個維特比算法的復(fù)雜度是O(N·D2)。
三母谎、HMM模型+維特比算法實例
1旷太、問題描述
假設(shè)連續(xù)觀察3天的海藻濕度為(Dry,Damp,Soggy),求這三天最可能的天氣情況。
2销睁、已知信息
①天氣只有三類(Sunny,Cloudy,Rainy)，海藻濕度有四類{Dry,Dryish, Damp,Soggy }存崖，而且海藻濕度和天氣有一定的關(guān)系冻记。
②隱藏的狀態(tài)：Sunny, Cloudy, Rainy;
③觀察狀態(tài)序列：{Dry, Damp, Soggy}
④初始狀態(tài)序列：
SunnyCloudyRainy
0.630.170.20
⑤狀態(tài)轉(zhuǎn)移矩陣：
?SunnyCloudyRainy
Sunny0.50.3750.125
Cloudy0.250.1250.625
Rainy0.250.3750.375
⑥發(fā)射矩陣：
?DryDryishDampSoggy
Sunny0.60.20.150.05
Cloudy0.250.250.250.25
Rainy0.050.100.350.5
3、分析
由一階HMM可知来惧，Day2的天氣僅取決于Day1冗栗；Day3的天氣又只取決于Day2的天氣。
4供搀、計算過程
（1）Day1由于是初始狀態(tài)隅居，我們分別求
P(Day1-Sunny)=0.63*0.6;
P(Day1-Cloudy)=0.17*0.25;
P(Day1-Rain)=0.20*0.05;
Choose max{ P(Day1-Sunny) , P(Day1-Cloudy),P(Day1-Rainy)}, 得到P(Day1-Sunny)最大，得出第1天Sunny的概率最大葛虐。
（2）Day2的天氣又取決于Day1的天氣狀況胎源，同時也受Day2觀察的海藻情況影響。
P(Day2-Sunny)= max{ P(Day1-Sunny)*0.5, P(Day1-Cloudy)*0.25,? P(Day1-Rainy)*0.25} *0.15;
P(Day2-Cloudy)= max{ P(Day1-Sunny)*0.375,? P(Day1-Cloudy)*0.125, P(Day1-Rainy)*0.625} *0.25;
P(Day2-Rainy)= max{ P(Day1-Sunny)*0.125,? P(Day1-Cloudy)*0.625 , P(Day1-Rainy)*0.375} *0.35;
Choosemax{ P(Day2-Sunny) , P(Day2-Cloudy), P(Day2-Rainy)},得到P(Day2-Rainy)最大屿脐，得出第2天Rainy的概率最大涕蚤。
故{Sunny,Rainy}是前兩天最大可能的天氣序列。
（3）Day3的天氣又取決于Day2的天氣狀況的诵，同時也受Day3觀察的海藻情況影響万栅。
P(Day3-Sunny)= max{ P(Day2-Sunny)*0.5, P(Day2-Cloudy)*0.25,? P(Day2-Rainy)*0.25} *0.05;
P(Day3-Cloudy)= max{ P(Day2-Sunny)*0.375,? P(Day2-Cloudy)*0.125, P(Day2-Rainy)*0.625} *0.25;
P(Day3-Rainy)= max{ P(Day2-Sunny)*0.125,? P(Day2-Cloudy)*0.625, P(Day2-Rainy)*0.375} *0. 05;
Choosemax{ P(Day3-Sunny) , P(Day3-Cloudy), P(Day3-Rainy)},得到P(Day3-Rainy)最大，得出第3天Rainy的概率最大西疤。故{Sunny,Rainy,Rainy}是這三天最可能的天氣序列烦粒。
原文地址：https://www.cnblogs.com/Denise-hzf/p/6612212.html
