隱馬爾科夫模型原理圖解

1、山東大學(xué)高性能計(jì)算與大數(shù)據(jù)處理學(xué)科組山東大學(xué)高性能計(jì)算與大數(shù)據(jù)處理學(xué)科組high performance computing and big data processing group張慶科張慶科隱馬爾可夫模型原理圖解隱馬爾可夫模型原理圖解hidden markov modelshidden markov models1提 綱hidden markov modelhidden markov model隱馬爾科夫模型的三個(gè)問題隱馬爾科夫模型的三個(gè)問題總結(jié)總結(jié)13l概率計(jì)算概率計(jì)算問題問題l路徑預(yù)測問題路徑預(yù)測問題2l參數(shù)學(xué)習(xí)問題參數(shù)學(xué)習(xí)問題hidden hidden markov markov

2、modelmodel21 1馬爾可夫模型馬爾可夫模型是數(shù)學(xué)中是數(shù)學(xué)中具有馬爾可夫性質(zhì)的離散具有馬爾可夫性質(zhì)的離散時(shí)間時(shí)間隨機(jī)過程隨機(jī)過程，是，是用于用于描述隨機(jī)描述隨機(jī)過程統(tǒng)計(jì)特征的概率過程統(tǒng)計(jì)特征的概率模型。模型。s2s3s123a,1na31asns1t=1t=2t=3t=t-1t=ts1s2s3sns1s2s3sns1s2s3sns1s2s3sns1s2s3sns1s2s3sn系統(tǒng)狀態(tài)數(shù)目(n個(gè))s2s3s1s1sn23a31a1na一條一條馬爾可夫鏈馬爾可夫鏈狀態(tài)序列狀態(tài)序列= =觀測序列觀測序列32. 2. 一階馬爾可夫一階馬爾可夫模型概念模型概念t=1t=2t=3t=4t=5s1s

3、2s3s1s2s3系統(tǒng)狀態(tài)數(shù)目(n=3)一階馬爾可夫一階馬爾可夫模型（模型（markov modelsmarkov models）s1s2s3s1s2s3s1s2s3s1s2s3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下時(shí)期狀態(tài)只下時(shí)期狀態(tài)只取決于取決于當(dāng)前當(dāng)前時(shí)期時(shí)期狀態(tài)和轉(zhuǎn)移概率狀態(tài)和轉(zhuǎn)移概率從某時(shí)刻狀態(tài)到下從某時(shí)刻狀態(tài)到下時(shí)刻時(shí)刻的的狀態(tài)按一定概率轉(zhuǎn)移狀態(tài)按一定概率轉(zhuǎn)移1(|)ijtjtiap qsqst-1時(shí)刻t時(shí)刻qt-1qt121(|,)(|)

4、tjtitktjtip qsqs qsp qsqsqt-1qtq1q2q3t-1時(shí)刻t 時(shí)刻晴陰雨t=1t=2t=343. 3. 隱馬爾可夫模型隱馬爾可夫模型t=1t=2t=3t=t-1t=ts1s2s3sns1s2s3sns1s2s3sns1s2s3sns1s2s3sns1s2s3sn隱藏狀態(tài)s2s3s1s1snt=1t=2t=3t=t-1t=t23a31a1na觀測狀態(tài)觀測狀態(tài)q1q2qmq1q2qmq1q2qmq1q2qmq1q2qmq1q2隱藏狀態(tài)序列隱藏狀態(tài)序列觀察觀察狀態(tài)序列狀態(tài)序列q1qmq2qmh hmmmm狀態(tài)狀態(tài)序列序列觀測序列觀測序列q1qm一般隨機(jī)過程一般隨機(jī)過程馬兒科

5、夫過程馬兒科夫過程5t=1t=2t=3t=4t=5s1s2s3一階隱馬爾可夫一階隱馬爾可夫模型模型（hidden markov hidden markov modelsmodels）圖解圖解s1s2s3s1s2s3s1s2s3s1s2s3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下時(shí)期狀態(tài)只下時(shí)期狀態(tài)只取決于取決于當(dāng)前當(dāng)前時(shí)期時(shí)期狀態(tài)和轉(zhuǎn)移概率狀態(tài)和轉(zhuǎn)移概率從某時(shí)刻狀態(tài)到下從某時(shí)刻狀態(tài)到下時(shí)刻時(shí)刻的的狀態(tài)按一定概率轉(zhuǎn)移狀態(tài)按一定概率轉(zhuǎn)移1(|)ijtjtia

6、p qsqst-1時(shí)刻t時(shí)刻qt-1qt121(|,)(|)tjtitktjtip qsqs qsp qsqs4. 4. 隱馬爾可夫模型隱馬爾可夫模型(hidden markov models(hidden markov models, ,hmm)hmm)q3q4q1q1o2i- i-隱藏隱藏狀態(tài)狀態(tài)轉(zhuǎn)移概率生成概率b2(q3)b3(q4)b1(q1)b1(q1)b2(q2)ii-ii-觀察觀察序列序列s2s3s1s1s2qt-1qtq1q2q3t-1時(shí)刻t 時(shí)刻t=1t=2t=36t=1t=2t=3t=t-1t=ts1s2s3s1s2sns1s2sns1s2sns1s2sno1o2o3ot-

7、1s2sns1s1s25. 5. 隱馬爾可夫模型隱馬爾可夫模型(hidden markov models(hidden markov models, ,hmm)hmm)hmm模型模型五五元組表示：元組表示： （ n, m, , a, b）用來描述用來描述hmm，或簡寫為，或簡寫為 =( , a, b)一階隱馬爾可夫一階隱馬爾可夫模型模型（hidden markov hidden markov modelsmodels）數(shù)學(xué)定義）數(shù)學(xué)定義 otomomomomomnm7提 綱hidden markov modelhidden markov model隱馬爾科夫模型的三個(gè)問題隱馬爾科夫模型的三個(gè)問

8、題總結(jié)總結(jié)13l概率計(jì)算概率計(jì)算問題問題l路徑預(yù)測問題路徑預(yù)測問題2l參數(shù)學(xué)習(xí)問題參數(shù)學(xué)習(xí)問題l概率計(jì)算概率計(jì)算問題問題8t=1t=2t=3t=t-1t=ts1s2s3s1s2sns1s2snzs1s2sns1s2sna11a12a13a22a21a23an1annan2a11a12a22a21a23a33a32a11a12a22a21a23a33a32o1o2o3ot-1otn 問題1：給定觀察序列o=o1,o2, ,ot,以及模型=(,a,b)=(,a,b),計(jì)算p(o|)？01020 naaaa01a02a0n：初始概率向量1. 1. 隱馬爾可夫模型隱馬爾可夫模型- -全概率計(jì)算全概率計(jì)

9、算s212q s(|)pr( ,q|)=pr(o,q | )+ pr(o,q | )+ pr(o,q| )ttnp oo 路徑路徑路徑問題本質(zhì)：計(jì)算產(chǎn)生觀測序列o的所有可能的狀態(tài)序列對應(yīng)的概率之和共 n t 個(gè)可能路徑（指數(shù)級(jí)計(jì)算）n=5, t=100, = 計(jì)算量1072t=1t=2t=3s1s2s1s2s1s2bes4s4s4s5s5s5s3s3s3t=4s1s2s4s5s31(1)1(2)1(3)1(4)1(5)2(1)2(2)2(3)2(4)2(5)3(1)3(2)3(3)3(4)3(5)(1)t(2)t(3)t(4)t(5)ta01a02a03a04a05at1at2at3at4at

10、5o1o2o3o4101( )( )kkkab o11( )( )( )nttlkktlkl ab o01p( | )(k)ntkkoa前前向算法向算法后向算法后向算法9n 問題1：給定觀察序列o=o1,o2, ,ot,以及模型=(,a,b)=(,a,b),如何計(jì)算p(o|)？sksks1snot( )tk(1)t( )ktb os1sn1(n)t11( )( )ntlkktll ab o( )tk1(1)t(n)t1kankakkasks1sn0(1)t10a0na0kat-1ot01(k)ntkkap( | )o tt0sks1sn1(n)1(1)11( )k01( )kkab oo11(

11、 )k1( )kb o01a0ka0na初始化階段(t = 1)中間遞歸階段（t = 2,t）結(jié)束階段(n)t2. 2. 概率概率計(jì)算計(jì)算問題：問題：前向算法（前向算法（forward algorithmforward algorithm）前進(jìn)前進(jìn)ot-1p(| )o前進(jìn)前進(jìn)n=5, t=100, = 計(jì)算量300010skot+1( )tk(1)ts1sn(n)tsks1sn0(1)t10a0na0kaot tt0sks1sn1(n)1(1)1o11( )k01a0ka0na.(n)tn 問題1：給定觀察序列o=o1,o2, ,ot,以及模型=(,a,b)=(,a,b),如何計(jì)算p(o|)？

12、3. 3. 概率概率計(jì)算計(jì)算問題：后向問題：后向算法（算法（forward algorithmforward algorithm）ot( )tk0( )kktab o(k)tsks1sn+1(n)t+1(1)tt+1+1( )tk11()tb o1()ktb o1()ntbo( )tk111()( )nkllttlab ol1kakkaknap( | )o0111( )( )nkkkab ok11()b o1( )kb o1( )nb o.后退后退后退后退初始化階段(t = t)中間遞歸階段（t = t-1, 2,1）結(jié)束階段11提 綱hidden markov modelhidden mar

13、kov model隱馬爾科夫模型的三個(gè)問題隱馬爾科夫模型的三個(gè)問題總結(jié)總結(jié)13l概率計(jì)算概率計(jì)算問題問題l路徑預(yù)測問題路徑預(yù)測問題2l參數(shù)學(xué)習(xí)問題參數(shù)學(xué)習(xí)問題l路徑預(yù)測問題路徑預(yù)測問題12 1. 1.隱馬爾可夫模型隱馬爾可夫模型- -路徑預(yù)測路徑預(yù)測n 問題2：給定觀察序列o=o1,o2, ,ot,以及模型,如何推測最可能的狀態(tài)序列s ? t=1t=2t=3t=t-1t=ts1s2sns1s2sns1s2snzs1s2sns1s2snan101020 naaaa01a02a0n：初始概率向量s2問題本質(zhì)：計(jì)算產(chǎn)生觀測序列o的最可能的一條隱藏狀態(tài)序列qo1o2o3ot-1ot已知觀察序列已知觀察

14、序列？解決方法：viterbi算法s2sns1s1s2viterbiviterbi算法算法t=1t=2t=3s1s2s1s2s1s2bes4s4s4s5s5s5s3s3s3t=4s1s2s4s5s31(1)1(2)1(3)1(4)1(5)2(1)2(2)2(3)2(4)2(5)3(1)3(2)3(3)3(4)3(5)(1)t(2)t(3)t(4)t(5)ta01a02a03a04a05a1-0a2-0a3-0a4-0a5-0o1o2o3o4101( )( )kkkab ot-11t-12t-1(1)(2)( )max( )(n)kktktnkaakb oa01,.,pr(q |, )( )ma

15、xtllnol a1(s )bk(s )tk(s )tk132. 2. 隱馬爾可夫狀態(tài)路徑預(yù)測：隱馬爾可夫狀態(tài)路徑預(yù)測：viterbiviterbi算法算法t=1t=2t=3s1s2s1s2s1s2bes4s4s4s5s5s5s3s3s3t=4s1s2s4s5s31(1)1(2)1(3)1(4)1(5)2(1)2(2)2(3)2(4)2(5)3(1)3(2)3(3)3(4)3(5)(1)t(2)t(3)t(4)t(5)ta01a02a03a04a05a1-0a2-0a3-0a4-0a5-0o1o2o3o4動(dòng)畫演示：由viterbi算法計(jì)算產(chǎn)生觀測序列o的最可能的一條隱藏狀態(tài)序列q101( )(

16、 )kkkab ot-11t-12t-1(1)(2)( )max( )(n)kktktnkaakb oa01,.,pr(q |, )( )maxtllnol a1(s )bk(s )tk(s )tk14sksks1snot( )tk(1)t( )ktb os1sn1(n)t1(1)t(n)t1kankakkasks1sn0(1)t10a0nat-1時(shí)刻ot t時(shí)刻t時(shí)刻0sks1sn1(n)1(1)1時(shí)刻1( )k01()kkab oo11( )k1( )kb o01a0ka0na初始化階段(t = 1)中間遞歸階段（t = 2,t）結(jié)束階段(n)tot-1n 問題2：給定觀察序列o=o1,o

17、2, ,ot,以及模型,如何推測最可能的狀態(tài)序列s ? t-11t-12t-1(1)(2)max( )(n)kkktnkaab oa( )tkmax01,.,pr(q |, )( )maxtllnol as1snsks1s？s？s？s1(1)(t 1)(t) tmax路徑路徑回溯回溯1(s )t(s )n1(s )t(s )tk(s )tn-11(s )t-1(s )tn(s )tk(s )tk向量向量3. 3. 預(yù)測隱馬爾可夫狀態(tài)路徑：預(yù)測隱馬爾可夫狀態(tài)路徑：viterbiviterbi算法算法1(s )0k(k)t表示表示t t時(shí)刻，沿狀態(tài)路徑時(shí)刻，沿狀態(tài)路徑q1, q2, ,q1, q2

18、, ,qt qt, ,且且q qt t=s=sk k時(shí)，產(chǎn)生已知的觀時(shí)，產(chǎn)生已知的觀察序列的前面察序列的前面t t個(gè)子序列個(gè)子序列o1,o2,o1,o2,otot 的最大概率值的最大概率值(s )tk表示表示t t時(shí)刻，到達(dá)隱狀態(tài)時(shí)刻，到達(dá)隱狀態(tài)sksk，且其，且其 乘積最大乘積最大的那個(gè)狀態(tài)對應(yīng)的標(biāo)記序號(hào)值。的那個(gè)狀態(tài)對應(yīng)的標(biāo)記序號(hào)值。路徑路徑回溯回溯15提 綱hidden markov modelhidden markov model隱馬爾科夫模型的三個(gè)問題隱馬爾科夫模型的三個(gè)問題總結(jié)總結(jié)13l概率計(jì)算概率計(jì)算問題問題l路徑預(yù)測問題路徑預(yù)測問題2l參數(shù)訓(xùn)練問題參數(shù)訓(xùn)練問題l參數(shù)訓(xùn)練問題參數(shù)

19、訓(xùn)練問題161 1. . 隱馬爾可夫模型隱馬爾可夫模型- -參數(shù)訓(xùn)練問題參數(shù)訓(xùn)練問題n 問題3：給定觀察值序列o,如何調(diào)整模型參數(shù)=(,a,b),使得p(o|)最大 ?t=1t=2t=3t=t-1t=ts1s2sns1s2sns1s2snzs1s2sns1s2snan101020 naaaa01a02a0n：初始概率向量s2o1o2o3ot-1ot已知觀察序列已知觀察序列o o？17情形情形1 1：路徑已知時(shí)的參數(shù)估計(jì) (監(jiān)督學(xué)習(xí)方法)情形情形2 2：路徑未知時(shí)的參數(shù)估計(jì) (非監(jiān)督學(xué)習(xí)方法)n 問題3：給定觀察值序列o,如何調(diào)整模型參數(shù)=(,a,b),使得p(o|)最大 ?2. 2. 隱馬爾可

20、夫模型隱馬爾可夫模型- -參數(shù)參數(shù)訓(xùn)練訓(xùn)練問題問題即：由最大似然估計(jì)法對即：由最大似然估計(jì)法對hmmhmm的參數(shù)進(jìn)行估計(jì)的參數(shù)進(jìn)行估計(jì)s2s3s1s5s2s2s3s1s5v1v3v2v2v1v4v3v4v1123451234 , ,svss s s s sov v v v123451234 , ,svss s s s sov v v v?v1v3v2v2v1v4v3v4v1?baum-welchbaum-welch算法（算法（emem算法特例）對算法特例）對hmmhmm參數(shù)估參數(shù)估計(jì)計(jì)1 1()()ijijnijjf ssaf ssijisss狀態(tài)轉(zhuǎn)移的總次數(shù)狀態(tài)轉(zhuǎn)移任意狀態(tài)的總次數(shù)1()(

21、)()ikinikkg svb kg svikisvs從狀態(tài) 生成觀測字符 的次數(shù)從狀態(tài) 生成任意字符的總次數(shù)count( )engthisl=is狀態(tài) 出現(xiàn)的次數(shù)序列的長度轉(zhuǎn)移概率生成概率181111111( )()( )( )()( )(i, j)( , )(| )( )( )( )p(|, )( , )ntillttnntijjttljjttttiiab oli a b ojp op oiiiqs op o3. 3. 參數(shù)訓(xùn)練算法：參數(shù)訓(xùn)練算法：baum-welchbaum-welch算法基礎(chǔ)算法基礎(chǔ)11( )( )( )nttlkktlkl ab o111( )()( )ntklltt

22、lkab ol1212121212121212( )( )p( ,|) p(,|, )p( ,|) p(,|, )p( ,|) p(,|, )p(,|)p(,|)p(ttitittttittittttittittttittittitiio oo qsoooqso oo qsoooqso oo qsoooqs o ooqs o ooqs oqs|, ) p(|)ioo( )( )( )(| )tttiiip o(將乘積因子按定義展開)( )( )ttii1( )( )( )( , )(| )ntttjiiii jp o11( )()( )( , )(|)tijjtti a b oji jp o前

23、前向算法向算法后向算法后向算法(將分子中的按其遞歸計(jì)算公式展開)( )( )( )(| )tttiiip o令其為( )ti令其為( , )i j前后向算法關(guān)系圖前后向算法關(guān)系圖194. 4. 參數(shù)訓(xùn)練算法：參數(shù)訓(xùn)練算法：baum-welchbaum-welch算法（單觀測序列）算法（單觀測序列）1111111111111111111( , )( )()( )(|)( )( )( )( )(|)( )( )()( ,| )( ,| )ttttijjttijjttttttttttttttttttijtttijtiti jijp oijiiip oiiop o qs qsp o qsa b oa

24、ba11tttttt1,1,1,1,tttt1111p( ,|)( )( )( ) p(|)( )( )( )=p( ,|)( )( )( ) p(|)( )( )tktktktktttttjttostostostosttttjtjttttto qsjjjojjko qsjjjojjb但在實(shí)際應(yīng)用中但在實(shí)際應(yīng)用中, ,訓(xùn)練一訓(xùn)練一個(gè)個(gè)hmmhmm用用到的觀測值序列往往不止一個(gè)到的觀測值序列往往不止一個(gè), ,那么那么, ,對于對于多多個(gè)個(gè)觀測值序列訓(xùn)練時(shí)觀測值序列訓(xùn)練時(shí), ,要要對對bwbw算法算法的重估的重估公式進(jìn)行修正公式進(jìn)行修正. .1112121222*12nnn nnnnnaaaaaaaaaa a轉(zhuǎn)移概率矩陣轉(zhuǎn)移概率矩陣1112121222*m12mmnnnnmbbbbbbbbbb b生成生成概率矩陣概率矩陣01020 naaa初始概率矩陣初始概率矩陣111111( ,q|)( )( )( )(|)( ,q|)iinkkp osiiip op os201112121222*12nnn nnnnnaaaaaaaaaa a轉(zhuǎn)移概率矩陣轉(zhuǎn)移概率矩陣1112121222*m12mmnnnnmbbbbbbbbbb b生成生