隱馬爾科夫模型(原理圖解)

1、山東大學高性能計算與大數(shù)據(jù)處理學科組山東大學高性能計算與大數(shù)據(jù)處理學科組High Performance Computing and Big Data Processing Group張慶科張慶科隱馬爾可夫模型原理圖解隱馬爾可夫模型原理圖解Hidden Markov ModelsHidden Markov Models1提 綱Hidden Markov ModelHidden Markov Model隱馬爾科夫模型的三個問題隱馬爾科夫模型的三個問題總結(jié)總結(jié)13l概率計算概率計算問題問題l路徑預測問題路徑預測問題2l參數(shù)學習問題參數(shù)學習問題Hidden Hidden Markov Markov

2、ModelModel21 1馬爾可夫模型馬爾可夫模型是數(shù)學中是數(shù)學中具有馬爾可夫性質(zhì)的離散具有馬爾可夫性質(zhì)的離散時間時間隨機過程隨機過程，是，是用于用于描述隨機描述隨機過程統(tǒng)計特征的概率過程統(tǒng)計特征的概率模型。模型。S2S3S123a,1Na31aSNS1t=1t=2t=3t=T-1t=TS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN系統(tǒng)狀態(tài)數(shù)目(N個)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下時期狀態(tài)只下時期狀態(tài)只取決于取決于當前當前時期時期狀態(tài)和轉(zhuǎn)移概率狀態(tài)和轉(zhuǎn)移概率從某時刻狀態(tài)到下從某時刻狀態(tài)到下時刻時刻的的狀態(tài)按一定概率轉(zhuǎn)移狀態(tài)按一定概率轉(zhuǎn)移1(|)ijtjtiaP qSqSt-1時刻t時刻qt-1qt121(|,)(|)

4、tjtitktjtiP qSqS qSP qSqSqt-1qtq1q2q3t-1時刻t 時刻晴陰雨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一般隨機過程一般隨機過程馬兒科

5、夫過程馬兒科夫過程5t=1t=2t=3t=4t=5S1S2S3一階隱馬爾可夫一階隱馬爾可夫模型模型（Hidden Markov Hidden Markov ModelsModels）圖解圖解S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下時期狀態(tài)只下時期狀態(tài)只取決于取決于當前當前時期時期狀態(tài)和轉(zhuǎn)移概率狀態(tài)和轉(zhuǎn)移概率從某時刻狀態(tài)到下從某時刻狀態(tài)到下時刻時刻的的狀態(tài)按一定概率轉(zhuǎn)移狀態(tài)按一定概率轉(zhuǎn)移1(|)ijtjtia

6、P qSqSt-1時刻t時刻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時刻t 時刻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ù)學定義）數(shù)學定義 OTOMOMOMOMOMNM7提 綱Hidden Markov ModelHidden Markov Model隱馬爾科夫模型的三個問題隱馬爾科夫模型的三個問

8、題總結(jié)總結(jié)13l概率計算概率計算問題問題l路徑預測問題路徑預測問題2l參數(shù)學習問題參數(shù)學習問題l概率計算概率計算問題問題8t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNzS1S2SNS1S2SNa11a12a13a22a21a23aN1aNNaN2a11a12a22a21a23a33a32a11a12a22a21a23a33a32O1O2O3OT-1OTn 問題1：給定觀察序列O=O1,O2, ,OT,以及模型=(,A,B)=(,A,B),計算P(O|)？01020 Naaaa01a02a0N：初始概率向量1. 1. 隱馬爾可夫模型隱馬爾可夫模型- -全概率計算全概率計

9、算S212Q S(|)Pr( ,Q|)=Pr(O,Q | )+ Pr(O,Q | )+ Pr(O,Q| )TTNP OO 路徑路徑路徑問題本質(zhì)：計算產(chǎn)生觀測序列O的所有可能的狀態(tài)序列對應的概率之和共 N T 個可能路徑（指數(shù)級計算）N=5, T=100, = 計算量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),如何計算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. 概率概率計算計算問題：問題：前向算法（前向算法（Forward AlgorithmForward Algorithm）前進前進Ot-1P(| )O前進前進N=5, T=100, = 計算量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),如何計算P(O|)？

12、3. 3. 概率概率計算計算問題：后向問題：后向算法（算法（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隱馬爾科夫模型的三個問題隱馬爾科夫模型的三個問題總結(jié)總結(jié)13l概率計算概率計算問題問題l路徑預測問題路徑預測問題2l參數(shù)學習問題參數(shù)學習問題l路徑預測問題路徑預測問題12 1. 1.隱馬爾可夫模型隱馬爾可夫模型- -路徑預測路徑預測n 問題2：給定觀察序列O=O1,O2, ,OT,以及模型,如何推測最可能的狀態(tài)序列S ? t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN101020 Naaaa01a02a0N：初始概率向量S2問題本質(zhì)：計算產(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)路徑預測：隱馬爾可夫狀態(tài)路徑預測：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動畫演示：由Viterbi算法計算產(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時刻OT t時刻T時刻0SkS1SN1(N)1(1)1時刻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. 預測隱馬爾可夫狀態(tài)路徑：預測隱馬爾可夫狀態(tài)路徑：ViterbiViterbi算法算法1(s )0k(k)t表示表示t t時刻，沿狀態(tài)路徑時刻，沿狀態(tài)路徑q1, q2, ,q1, q2

18、, ,qt qt, ,且且q qt t=S=Sk k時，產(chǎn)生已知的觀時，產(chǎn)生已知的觀察序列的前面察序列的前面t t個子序列個子序列o1,o2,o1,o2,otot 的最大概率值的最大概率值(s )tk表示表示t t時刻，到達隱狀態(tài)時刻，到達隱狀態(tài)sksk，且其，且其 乘積最大乘積最大的那個狀態(tài)對應的標記序號值。的那個狀態(tài)對應的標記序號值。路徑路徑回溯回溯15提 綱Hidden Markov ModelHidden Markov Model隱馬爾科夫模型的三個問題隱馬爾科夫模型的三個問題總結(jié)總結(jié)13l概率計算概率計算問題問題l路徑預測問題路徑預測問題2l參數(shù)訓練問題參數(shù)訓練問題l參數(shù)訓練問題參數(shù)

19、訓練問題161 1. . 隱馬爾可夫模型隱馬爾可夫模型- -參數(shù)訓練問題參數(shù)訓練問題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ù)估計 (監(jiān)督學習方法)情形情形2 2：路徑未知時的參數(shù)估計 (非監(jiān)督學習方法)n 問題3：給定觀察值序列O,如何調(diào)整模型參數(shù)=(,A,B),使得P(O|)最大 ?2. 2. 隱馬爾可

20、夫模型隱馬爾可夫模型- -參數(shù)參數(shù)訓練訓練問題問題即：由最大似然估計法對即：由最大似然估計法對HMMHMM的參數(shù)進行估計的參數(shù)進行估計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ù)估計計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ù)訓練算法：參數(shù)訓練算法：Baum-WelchBaum-Welch算法基礎算法基礎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、前向算法向算法后向算法后向算法(將分子中的按其遞歸計算公式展開)( )( )( )(| )tttiiiP O令其為( )ti令其為( , )i j前后向算法關(guān)系圖前后向算法關(guān)系圖194. 4. 參數(shù)訓練算法：參數(shù)訓練算法：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但在實際應用中但在實際應用中, ,訓練一訓練一個個HMMHMM用用到的觀測值序列往往不止一個到的觀測值序列往往不止一個, ,那么那么, ,對于對于多多個個觀測值序列訓練時觀測值序列訓練時, ,要要對對BWBW算法算法的重估的重估公式進行修正公式進行修正. .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生成生