隱馬爾科夫模型HMM詳解

1、馬爾科夫過程馬爾科夫過程可以看做是一個(gè)自動(dòng)機(jī)，以一定的概率在各個(gè)狀態(tài)之間跳轉(zhuǎn)?？紤]一個(gè)系統(tǒng)，在每個(gè)時(shí)刻都可能處于N個(gè)狀態(tài)中的一個(gè)，N個(gè)狀態(tài)集合 是S1,S2,S3，SN。我們現(xiàn)在用q1，q2，q3,qn來表示系統(tǒng)在t=1,2,3，n時(shí)刻下的 狀態(tài)。在t=1時(shí)，系統(tǒng)所在的狀態(tài)q取決于一個(gè)初始概率分布PI，PI(SN)表示t=1 時(shí)系統(tǒng)狀態(tài)為SN的概率。馬爾科夫模型有兩個(gè)假設(shè)：.系統(tǒng)在時(shí)刻t的狀態(tài)只與時(shí)刻t-1處的狀態(tài)相關(guān)；(也稱為無后效性).狀態(tài)轉(zhuǎn)移概率與時(shí)間無關(guān)；(也稱為齊次性或時(shí)齊性)第一條具體可以用如下公式表示：P(qt=Sj%=Si,qt-2=Sk,尸胴=用%尸1)其中，t為大于1的任意

2、數(shù)值，Sk為任意狀態(tài)第二個(gè)假設(shè)則可以用如下公式表示：P(qt=Sj|qt-1=S尸 P(qk=Sj|qk-1=Si)其中，k為任意時(shí)刻。下圖是一個(gè)馬爾科夫過程的樣例圖：可以把狀態(tài)轉(zhuǎn)移概率用矩陣A表示，矩陣的行列長度均為狀態(tài)數(shù)目，2弓表 示 P(SilSi-1)隱馬爾科夫過程與馬爾科夫相比，隱馬爾科夫模型則是雙重隨機(jī)過程，不僅狀態(tài)轉(zhuǎn)移之間是 個(gè)隨機(jī)事件，狀態(tài)和輸出之間也是一個(gè)隨機(jī)過程，如下圖所示：一狀態(tài)轉(zhuǎn)移觀察值輸出此圖是從別處找來的，可能符號與我之前描述馬爾科夫時(shí)不同，相信大 家也能理解。該圖分為上下兩行，上面那行就是一個(gè)馬爾科夫轉(zhuǎn)移過程，下面這一行則是 輸出，即我們可以觀察到的值，現(xiàn)在，我們

3、將上面那行的馬爾科夫轉(zhuǎn)移過程中的 狀態(tài)稱為隱藏狀態(tài)，下面的觀察到的值稱為觀察狀態(tài)，觀察狀態(tài)的集合表示為 O=O1,O2,O3，0M。相應(yīng)的，隱馬爾科夫也比馬爾科夫多了一個(gè)假設(shè)，即輸出僅與當(dāng)前狀態(tài)有關(guān)， 可以用如下公式表示：P(O1,O2，,0tIS1S2,S尸P(O1IS1)*P(O21s2)*.*P(OtISt)其中，O1,O2,0t為從時(shí)刻1到時(shí)刻t的觀測狀態(tài)序列，S1,S2,St則為隱 藏狀態(tài)序列。另外，該假設(shè)又稱為輸出獨(dú)立性假設(shè)。舉個(gè)例子舉個(gè)常見的例子來引出下文，同時(shí)方便大家理解！比如我在不同天氣狀態(tài)下 去做一些事情的概率不同，天氣狀態(tài)集合為下雨，陰天，晴天，事情集合為宅 著，自習(xí)，游

4、玩。假如我們已經(jīng)有了轉(zhuǎn)移概率和輸出概率，即P(天氣AI天氣 B)和P(事情al天氣A)的概率都已知道，那么則有幾個(gè)問題要問(注意，假設(shè)一 天我那幾件事情中的一件)，.假如一周內(nèi)的天氣變化是下雨。晴天。陰天。下雨。陰天。晴天-陰天，那么我這一周自習(xí)。宅著。游玩- 自習(xí)。游玩。宅著- 自習(xí)的概率是多 大？.假如我這一周做事序列是自習(xí)。宅著。游玩- 自習(xí)。游玩。宅著- 自習(xí)，不知道天氣狀態(tài)的情況下這個(gè)做事序列的概率是多大？.假如一周內(nèi)的天氣變化是下雨。晴天。陰天。下雨。陰天。晴天- 陰天， 那我們這一周最有可能的做事序列是什么？.假如我這一周做事序列是自習(xí)。宅著。游玩- 自習(xí)。游玩。宅著- 自習(xí)，

5、那么這一周的天氣變化序列最有可能是什么？對于第一個(gè)問題，我想大家應(yīng)該都能很快知道怎么算。（啥？不知道，答案 在本文最后）隱馬模型基本要素及基本三問題綜上所述，我們可以得到隱馬爾科夫的基本要素，即一個(gè)五元組S,N,A,B,PI； S：隱藏狀態(tài)集合；N：觀察狀態(tài)集合；A：隱藏狀態(tài)間的轉(zhuǎn)移概率矩陣；B：輸出矩陣（即隱藏狀態(tài)到輸出狀態(tài)的概率）；PI：初始概率分布（隱藏狀態(tài)的初始概率分布）；其中，A、B、PI稱為隱馬爾科夫的參數(shù)，用X表示。由上述問題可以引出隱馬爾科夫的三個(gè)基本問題的其中兩個(gè)，下文中為了簡 便，將隱馬爾科夫模型簡稱為HMM（Hiden Markov Model）。HMM的三個(gè)基本問題是：

6、給定模型（五元組），求某個(gè)觀察序列O的概率（樣例問題2）（即已知模型參數(shù)，計(jì)算某一特定輸出序列的概率.通常使用forward算 法解決.）給定模型和觀察序列O,求可能性最大的隱藏狀態(tài)序列（樣例問題4）。 （即已知模型參數(shù)，尋找最可能的能產(chǎn)生某一特定輸出序列的隱含狀態(tài) 的序列.通常使用Viterbi算法解決.）對于給定的觀察序列O,調(diào)整HMM的參數(shù)，使觀察序列出現(xiàn)的概率 最大。（即已知輸出序列，尋找最可能的狀態(tài)轉(zhuǎn)移以及輸出概率.通常 使用Baum-Welch算法以及Reversed Viterbi算法解決.）前向算法對于第一個(gè)基本問題，計(jì)算公式為：p（o|x） = W 尸。SM = W 尸6 團(tuán)

7、SS即對于觀察序列O,我們需要找出所有可能的隱藏狀態(tài)序列S，計(jì)算出在給 定模型下S輸出為O的概率（就是樣例問題一?。?，然后計(jì)算概率之和。直觀上看，假如序列O的長度為T，模型的隱藏狀態(tài)集合大小為N，那么一 共有NT個(gè)可能的隱藏狀態(tài)序列，計(jì)算復(fù)雜度極高O（NT），暴力算法太慢了。解決方案就是動(dòng)態(tài)規(guī)劃(Dynamic Programming )。假設(shè)觀察序列為O1,O2,O3,0t在時(shí)刻i (1i=t)時(shí)，定義C為產(chǎn)生序列 O1,O2，,0i且Si=Sk的概率：C(if5；) = Ptfil, 02,.f Qi, Si = Skg)其中，sk為任意一個(gè)隱藏狀態(tài)值。則C(i+1,Sr)的計(jì)算公式為:N

8、c(i + lfSr)=幺。&耳乂帚印口k= 1其中，Sr為任意一個(gè)隱藏狀態(tài)值。A為轉(zhuǎn)移概率。B為隱藏狀態(tài)到觀察狀態(tài) 的概率。為了便于理解，還是看圖：E.臼刁土宅卷f丸游玩- -f也自習(xí)C(3,下雨)考慮了 t=1和t=2的所有組合情況，同時(shí)也是C(4,下雨陰天I晴天) 的子問題。C(3,陰天)和C(3,晴天)也是如此計(jì)算，而C(i+1,Sr)計(jì)算公式則可以表由圖知：C（4,陰天）=C（3,下雨）*A（下雨，陰天）+C（3,陰天）*A（陰天，陰天）+C（3, 晴天）*A（晴天，陰天）廣B（陰天,自習(xí)）。通過圖片，大家應(yīng)該能直觀的理解該算法了，該算法又稱為前向算法，那還 有后向算法？是的，后向算

9、法就是這個(gè)算法倒過來嘛，也是動(dòng)態(tài)規(guī)劃，這里就不 贅述了，有興趣的看參考文獻(xiàn)。另外，這里沒有講解如何初始化概率，也可以去 參考文獻(xiàn)里查證。維特比算法現(xiàn)在，HMM的第一個(gè)基本問題解決了，下面開始解決第二個(gè)問題，第二個(gè) 問題又稱為解碼問題，同樣的，暴力算法是計(jì)算所有可能性的概率，然后找出擁 有最大概率值的隱藏狀態(tài)序列。與問題一的暴力解決方案類似，復(fù)雜度為O（NT）。那應(yīng)該用什么方案呢？毫無疑問，還是動(dòng)態(tài)規(guī)劃啊！假設(shè)觀察序列為O1,O2,O3,0t.在時(shí)刻i（1i=2 時(shí)，節(jié)點(diǎn)中保存著一些小節(jié)點(diǎn)，這些小節(jié)點(diǎn)的數(shù)目即為上一個(gè)狀態(tài)的狀態(tài)數(shù)目， 小節(jié)點(diǎn)的值意義為到達(dá)該時(shí)刻狀態(tài)為Sr且前一時(shí)刻狀態(tài)為Sk時(shí)能夠產(chǎn)生狀態(tài)序 列的最大概率。比如背景為綠色的小節(jié)點(diǎn)的值的意義為時(shí)刻3為下雨，時(shí)刻2 為下雨時(shí)去自習(xí)。宅著。游玩的最大概率。（注意，節(jié)點(diǎn)表示時(shí)刻i時(shí)某個(gè)狀態(tài)， 小節(jié)點(diǎn)表示節(jié)點(diǎn)中保存的前一狀態(tài)的節(jié)點(diǎn)，比如綠色的那個(gè)節(jié)點(diǎn)）。對于時(shí)刻i（i2），每個(gè)小節(jié)點(diǎn)的概率為DR,St,SQ = m改0LQ2，- 1） = S/燈那么對于時(shí)刻i+1,小節(jié)點(diǎn)的概率為：D（i 十 L$wSq）=* 山（工及用） * %馬以然后，從時(shí)刻t中尋找最大的小節(jié)點(diǎn)回溯即可。樣例問題一答案上面樣例問題中第一問的答案是：概率：P=P（下雨）*P（晴天下雨）*P（陰天|晴天）*自習(xí)下雨）*P（宅著|晴