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

山东大学高性能计算与大数据处理学科组HighPerformanceComputingandBigDataProcessingGroup张庆科隐马尔可夫模型原理图解HiddenMarkovModels1山东大学高性能计算与大数据处理学科组提纲HiddenMarkovModel隐马尔科夫模型的三个问题总结13概率计算问题路径预测问题2参数学习问题HiddenMarkovModel2山东大学高性能计算与大数据处理学科组1马尔可夫模型马尔可夫模型是数学中具有马尔可夫性质的离散时间随机过程，是用于描述随机过程统计特征的概率模型。S2S3S1……23a,1Na31aSNS1t=1t=2t=3t=T-1t=T……………S1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN……………S1S2S3SN系统状态数目(N个)S2S3S1S1SN23a31a1Na一条马尔可夫链状态序列=观测序列3山东大学高性能计算与大数据处理学科组2.一阶马尔可夫模型概念t=1t=2t=3t=4t=5S1S2S3S1S2S3系统状态数目(N=3)一阶马尔可夫模型（MarkovModels）S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32•下时期状态只取决于当前时期状态和转移概率•从某时刻状态到下时刻的状态按一定概率转移1(|)ijtjtiaPqSqSt-1时刻t时刻qt-1qt121(|,,)(|)tjtitktjtiPqSqSqSPqSqSqt-1qt…q1q2q3t-1时刻t时刻晴阴雨T=1T=2T=34山东大学高性能计算与大数据处理学科组3.隐马尔可夫模型t=1t=2t=3t=T-1t=T……………S1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN……………S1S2S3SN隐藏状态S2S3S1S1SNt=1t=2t=3t=T-1t=T23a31a1Na…观测状态Q1Q2QM…Q1Q2QM…Q1Q2QM…Q1Q2QM…Q1Q2QM…Q1Q2隐藏状态序列观察状态序列Q1QMQ2QM…………HMM状态序列≠观测序列Q1QM一般随机过程马儿科夫过程5山东大学高性能计算与大数据处理学科组t=1t=2t=3t=4t=5S1S2S3一阶隐马尔可夫模型（HiddenMarkovModels）图解S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32•下时期状态只取决于当前时期状态和转移概率•从某时刻状态到下时刻的状态按一定概率转移1(|)ijtjtiaPqSqSt-1时刻t时刻qt-1qt121(|,,)(|)tjtitktjtiPqSqSqSPqSqS4.隐马尔可夫模型(HiddenMarkovModels,HMM)Q3Q4Q1Q1O2I-隐藏状态转移概率生成概率b2(Q3)b3(Q4)b1(Q1)b1(Q1)b2(Q2)II-观察序列S2S3S1S1S2qt-1qt…q1q2q3t-1时刻t时刻T=1T=2T=36山东大学高性能计算与大数据处理学科组t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNS1S2SNS1S2SNO1O2O3OT-1S2SNS1S1S25.隐马尔可夫模型(HiddenMarkovModels,HMM)HMM模型五元组表示：λ＝（N,M,π,A,B）用来描述HMM，或简写为λ=(π,A,B)一阶隐马尔可夫模型（HiddenMarkovModels）数学定义………………OT………1112121222*12NNNNNNNNaaaaaaAaaaA转移概率矩阵OMOMOMOMOM……………1112121222*M12MMNNNNMbbbbbbBbbbB生成概率矩阵πNM7山东大学高性能计算与大数据处理学科组提纲HiddenMarkovModel隐马尔科夫模型的三个问题总结13概率计算问题路径预测问题2参数学习问题概率计算问题8山东大学高性能计算与大数据处理学科组t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNzS1S2SNS1S2SNa11a12a13a22a21a23aN1aNNaN2a11a12a22a21a23a33a32a11a12a22a21a23a33a32O1O2O3OT-1……………OT…1112121222*12NNNNNNNNaaaaaaAaaaA转移概率矩阵1112121222*M12MMNNNNMbbbbbbBbbbB生成概率矩阵问题1：给定观察序列O=O1,O2,…,OT,以及模型λ=(π,A,B),计算P(O|λ)？π01020Naaaa01a02a0N…Π：初始概率向量1.隐马尔可夫模型-全概率计算S2…12QS(|)Pr(,Q|)=Pr(O,Q|)+Pr(O,Q|)++Pr(O,Q|)TTNPOO路径路径路径问题本质：计算产生观测序列O的所有可能的状态序列对应的概率之和共NT个可能路径（指数级计算）N=5,T=100,=计算量10^72t=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)Ta01a02a03a04a05aT1aT2aT3aT4aT5O1O2O3O4101()()kkkabo11()()()Nttlkktlklabo01P(|)(k)NTkkOa前向算法后向算法9山东大学高性能计算与大数据处理学科组问题1：给定观察序列O=O1,O2,…,OT,以及模型λ=(π,A,B),如何计算P(O|λ)？SkSkS1SNOt……()tk(1)t()ktboS1……SN1(N)t11()()Ntlkktllabo()tk1(1)t(N)t1kaNkakkaSkS1SN0(1)T10a0Na0kat-1OT01(k)NTkkaP(|)OtT0SkS1SN……1(N)1(1)11()k01()kkaboO11()k1()kbo01a0ka0Na……………………………………初始化阶段(t=1)中间递归阶段（t=2,…,T）结束阶段(N)T2.概率计算问题：前向算法（ForwardAlgorithm）前进Ot-1P(|)O前进N=5,T=100,=计算量300010山东大学高性能计算与大数据处理学科组SkOt+1()tk(1)tS1……SN(N)tSkS1SN0(1)T10a0Na0kaOTtT0SkS1SN……1(N)1(1)1O11()k01a0ka0Na...……………(N)T问题1：给定观察序列O=O1,O2,…,OT,以及模型λ=(π,A,B),如何计算P(O|λ)？3.概率计算问题：后向算法（ForwardAlgorithm）Ot()Tk0()kkTabo(k)TSkS1SN……+1(N)t+1(1)tt+1……+1()tk11()tbo1()ktbo1()Ntbo()tk111()()Nkllttlabol1kakkakNaP(|)O0111()()Nkkkabok11()bo1()kbo1()Nbo...…...……………后退后退初始化阶段(t=T)中间递归阶段（t=T-1,…,2,1）结束阶段11山东大学高性能计算与大数据处理学科组提纲HiddenMarkovModel隐马尔科夫模型的三个问题总结13概率计算问题路径预测问题2参数学习问题路径预测问题12山东大学高性能计算与大数据处理学科组1.隐马尔可夫模型-路径预测问题2：给定观察序列O=O1,O2,…,OT,以及模型λ,如何推测最可能的状态序列S?t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN1……………1112121222*12NNNNNNNNaaaaaaAaaaA转移概率矩阵1112121222*M12MMNNNNMbbbbbbBbbbB生成概率矩阵π01020Naaaa01a02a0N…Π：初始概率向量S2…问题本质：计算产生观测序列O的最可能的一条隐藏状态序列QO1O2O3OT-1OT…已知观察序列？解决方法：Viterbi算法S2SNS1S1S2viterbi算法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)Ta01a02a03a04a05a1-0a2-0a3-0a4-0a5-0O1O2O3O4101()()kkkabot-11t-12t-1(1)(2)()Max()(N)kktktNkaakboa01,..,Pr(Q|,)()MaxTllNOla1(S)Bk(S)tk(S)Tk13山东大学高性能计算与大数据处理学科组2.隐马尔可夫状态路径预测：Viterbi算法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)Ta01a02a03a04a05a1-0a2-0a3-0a4-0a5-0O1O2O3O4动画演示：由Viterbi算法计算产生观测序列O的最可能的一条隐藏状态序列Q101()()kkkabot-11t-12t-1(1)(2)()Max()(N)kktktNkaakboa01,..,Pr(Q|,)()MaxTllNOla1(S)Bk(S)tk(S)Tk14山东大学高性能计算与大数据处理学科组SkSkS1SNOt……()tk