隐马尔科夫模型(原理图解)

1、山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组High Performance Computing and Big Data Processing Group张庆科张庆科隐马尔可夫模型原理图解隐马尔可夫模型原理图解Hidden Markov ModelsHidden Markov Models1提 纲Hidden Markov ModelHidden Markov Model隐马尔科夫模型的三个问题隐马尔科夫模型的三个问题总结总结13l概率计算概率计算问题问题l路径预测问题路径预测问题2l参数学习问题参数学习问题Hidden Hidden Markov Markov

2、ModelModel21 1马尔可夫模型马尔可夫模型是数学中是数学中具有马尔可夫性质的离散具有马尔可夫性质的离散时间时间随机过程随机过程，是，是用于用于描述随机描述随机过程统计特征的概率过程统计特征的概率模型。模型。S2S3S123a,1Na31aSNS1t=1t=2t=3t=T-1t=TS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN系统状态数目(N个)S2S3S1S1SN23a31a1Na一条一条马尔可夫链马尔可夫链状态序列状态序列= =观测序列观测序列32. 2. 一阶马尔可夫一阶马尔可夫模型概念模型概念t=1t=2t=3t=4t=5S1S

3、2S3S1S2S3系统状态数目(N=3)一阶马尔可夫一阶马尔可夫模型（模型（Markov ModelsMarkov Models）S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下时期状态只下时期状态只取决于取决于当前当前时期时期状态和转移概率状态和转移概率从某时刻状态到下从某时刻状态到下时刻时刻的的状态按一定概率转移状态按一定概率转移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隐藏状态S2S3S1S1SNt=1t=2t=3t=T-1t=T23a31a1Na观测状态观测状态Q1Q2QMQ1Q2QMQ1Q2QMQ1Q2QMQ1Q2QMQ1Q2隐藏状态序列隐藏状态序列观察观察状态序列状态序列Q1QMQ2QMH HMMMM状态状态序列序列观测序列观测序列Q1QM一般随机过程一般随机过程马儿科

5、夫过程马儿科夫过程5t=1t=2t=3t=4t=5S1S2S3一阶隐马尔可夫一阶隐马尔可夫模型模型（Hidden Markov Hidden Markov ModelsModels）图解图解S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下时期状态只下时期状态只取决于取决于当前当前时期时期状态和转移概率状态和转移概率从某时刻状态到下从某时刻状态到下时刻时刻的的状态按一定概率转移状态按一定概率转移1(|)ijtjtia

6、P qSqSt-1时刻t时刻qt-1qt121(|,)(|)tjtitktjtiP qSqS qSP qSqS4. 4. 隐马尔可夫模型隐马尔可夫模型(Hidden Markov Models(Hidden Markov Models, ,HMM)HMM)Q3Q4Q1Q1O2I- I-隐藏隐藏状态状态转移概率生成概率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）数学定义）数学定义 OTOMOMOMOMOMNM7提 纲Hidden Markov ModelHidden Markov Model隐马尔科夫模型的三个问题隐马尔科夫模型的三个问

8、题总结总结13l概率计算概率计算问题问题l路径预测问题路径预测问题2l参数学习问题参数学习问题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 路径路径路径问题本质：计算产生观测序列O的所有可能的状态序列对应的概率之和共 N T 个可能路径（指数级计算）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）结束阶段(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）结束阶段11提 纲Hidden Markov ModelHidden Mar

13、kov Model隐马尔科夫模型的三个问题隐马尔科夫模型的三个问题总结总结13l概率计算概率计算问题问题l路径预测问题路径预测问题2l参数学习问题参数学习问题l路径预测问题路径预测问题12 1. 1.隐马尔可夫模型隐马尔可夫模型- -路径预测路径预测n 问题2：给定观察序列O=O1,O2, ,OT,以及模型,如何推测最可能的状态序列S ? t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN101020 Naaaa01a02a0N：初始概率向量S2问题本质：计算产生观测序列O的最可能的一条隐藏状态序列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. 隐马尔可夫状态路径预测：隐马尔可夫状态路径预测：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算法计算产生观测序列O的最可能的一条隐藏状态序列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）结束阶段(N)TOt-1n 问题2：给定观察序列O=O1,O

17、2, ,OT,以及模型,如何推测最可能的状态序列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. 预测隐马尔可夫状态路径：预测隐马尔可夫状态路径：ViterbiViterbi算法算法1(s )0k(k)t表示表示t t时刻，沿状态路径时刻，沿状态路径q1, q2, ,q1, q2

18、, ,qt qt, ,且且q qt t=S=Sk k时，产生已知的观时，产生已知的观察序列的前面察序列的前面t t个子序列个子序列o1,o2,o1,o2,otot 的最大概率值的最大概率值(s )tk表示表示t t时刻，到达隐状态时刻，到达隐状态sksk，且其，且其 乘积最大乘积最大的那个状态对应的标记序号值。的那个状态对应的标记序号值。路径路径回溯回溯15提 纲Hidden Markov ModelHidden Markov Model隐马尔科夫模型的三个问题隐马尔科夫模型的三个问题总结总结13l概率计算概率计算问题问题l路径预测问题路径预测问题2l参数训练问题参数训练问题l参数训练问题参数

19、训练问题161 1. . 隐马尔可夫模型隐马尔可夫模型- -参数训练问题参数训练问题n 问题3：给定观察值序列O,如何调整模型参数=(,A,B),使得P(O|)最大 ?t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN101020 Naaaa01a02a0N：初始概率向量S2O1O2O3OT-1OT已知观察序列已知观察序列O O？17情形情形1 1：路径已知时的参数估计 (监督学习方法)情形情形2 2：路径未知时的参数估计 (非监督学习方法)n 问题3：给定观察值序列O,如何调整模型参数=(,A,B),使得P(O|)最大 ?2. 2. 隐马尔可

20、夫模型隐马尔可夫模型- -参数参数训练训练问题问题即：由最大似然估计法对即：由最大似然估计法对HMMHMM的参数进行估计的参数进行估计S2S3S1S5S2S2S3S1S5V1V3V2V2V1V4V3V4V1123451234 , ,svSs s s s sOv v v v123451234 , ,svSs s s s sOv v v v?V1V3V2V2V1V4V3V4V1?Baum-WelchBaum-Welch算法（算法（EMEM算法特例）对算法特例）对HMMHMM参数估参数估计计1 1()()ijijNijjf ssaf ssijisss状态转移的总次数状态转移任意状态的总次数1()(

21、)()ikiNikkg svb kg svikisvs从状态 生成观测字符 的次数从状态 生成任意字符的总次数Count( )engthisL=is状态 出现的次数序列的长度转移概率生成概率181111111( )()( )( )()( )(i, j)( , )(| )( )( )( )P(|, )( , )NtillttNNtijjttljjttttiiab oli a b ojP OP Oiiiqs OP O3. 3. 参数训练算法：参数训练算法：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前后向算法关系图前后向算法关系图194. 4. 参数训练算法：参数训练算法：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转移概率矩阵转移概率矩阵1112121222*M12MMNNNNMbbbbbbBbbb B生成生成概率矩阵概率矩阵01020 Naaa初始概率矩阵初始概率矩阵111111( ,q|)( )( )( )(|)( ,q|)iiNkkP OsiiiP OP Os201112121222*12NNN NNNNNaaaaaaAaaa A转移概率矩阵转移概率矩阵1112121222*M12MMNNNNMbbbbbbBbbb B生成生