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

山东大学高性能计算与大数据处理学科组HighPerformanceComputingandBigDataProcessingGroup张庆科隐马尔可夫模型原理图解HiddenMarkovModels提纲HiddenMarkovModel隐马尔科夫模型的三个问题总结13概率计算问题路径预测问题2参数学习问题HiddenMarkovModel1马尔可夫模型马尔可夫模型是数学中具有马尔可夫性质的离散时间随机过程，是用于描述随机过程统计特征的概率模型。S2S3S1……SNS1t=1t=2t=3t=T-1t=T……………S1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN……………S1S2S3SN系统状态数目(N个)S2S3S1S1SN一条马尔可夫链状态序列=观测序列2.一阶马尔可夫模型概念t=1t=2t=3t=4t=5S1S2S3S1S2S3系统状态数目(N=3)一阶马尔可夫模型（MarkovModels）S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下时期状态只取决于当前时期状态和转移概率从某时刻状态到下时刻的状态按一定概率转移t-1时刻t时刻qt-1qtqt-1qt…q1q2q3t-1时刻t时刻晴阴雨T=1T=2T=33.隐马尔可夫模型t=1t=2t=3t=T-1t=T……………S1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN……………S1S2S3SN隐藏状态S2S3S1S1SNt=1t=2t=3t=T-1t=T…观测状态Q1Q2QM…Q1Q2QM…Q1Q2QM…Q1Q2QM…Q1Q2QM…Q1Q2隐藏状态序列观察状态序列Q1QMQ2QM…………HMM状态序列≠观测序列Q1QM一般随机过程马儿科夫过程t=1t=2t=3t=4t=5S1S2S3一阶隐马尔可夫模型（HiddenMarkovModels）图解S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下时期状态只取决于当前时期状态和转移概率从某时刻状态到下时刻的状态按一定概率转移t-1时刻t时刻qt-1qt4.隐马尔可夫模型(HiddenMarkovModels,HMM)Q3Q4Q1Q1O2I-隐藏状态转移概率生成概率b2(Q3)b3(Q4)b1(Q1)b1(Q1)b2(Q2)II-观察序列S2S3S1S1S2qt-1qt…q1q2q3t-1时刻t时刻T=1T=2T=3t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNS1S2SNS1S2SNO1O2O3OT-1S2SNS1S1S25.隐马尔可夫模型(HiddenMarkovModels,HMM)HMM模型五元组表示：λ

＝（N,M,π,A,B）用来描述HMM，或简写为λ=(π,A,B)一阶隐马尔可夫模型（HiddenMarkovModels）数学定义

………………OT………A转移概率矩阵OMOMOMOMOM……………B生成概率矩阵πNM提纲HiddenMarkovModel隐马尔科夫模型的三个问题总结13概率计算问题路径预测问题2参数学习问题概率计算问题t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNzS1S2SNS1S2SNa11a12a13a22a21a23aN1aNNaN2a11a12a22a21a23a33a32a11a12a22a21a23a33a32O1O2O3OT-1……………OT…A转移概率矩阵B生成概率矩阵问题1：给定观察序列O=O1,O2,…,OT,以及模型λ=(π,A,B),计算P(O|λ)？πa01a02a0N…Π：初始概率向量1.隐马尔可夫模型-全概率计算S2…问题本质：计算产生观测序列O的所有可能的状态序列对应的概率之和共NT个可能路径（指数级计算）N=5,T=100,=>计算量10^72t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05aT1aT2aT3aT4aT5O1O2O3O4前向算法后向算法问题1：给定观察序列O=O1,O2,…,OT,以及模型λ=(π,A,B),如何计算P(O|λ)？SkSkS1SNOt……S1……SNSkS1SN0t-1OT

tT0SkS1SN……1O1……………………………………初始化阶段(t=1)中间递归阶段（t=2,…,T）结束阶段2.概率计算问题：前向算法（ForwardAlgorithm）前进Ot-1前进N=5,T=100,=>计算量3000SkOt+1S1……SNSkS1SN0OT

tT0SkS1SN……1O1...……………问题1：给定观察序列O=O1,O2,…,OT,以及模型λ=(π,A,B),如何计算P(O|λ)？3.概率计算问题：后向算法（ForwardAlgorithm）OtSkS1SN……t+1……...…...……………后退后退初始化阶段(t=T)中间递归阶段（t=T-1,…,2,1）结束阶段提纲HiddenMarkovModel隐马尔科夫模型的三个问题总结13概率计算问题路径预测问题2参数学习问题路径预测问题1.隐马尔可夫模型-路径预测问题2：给定观察序列O=O1,O2,…,OT,以及模型λ,如何推测最可能的状态序列S?t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN1……………A转移概率矩阵B生成概率矩阵πa01a02a0N…Π：初始概率向量S2…问题本质：计算产生观测序列O的最可能的一条隐藏状态序列QO1O2O3OT-1OT…已知观察序列？解决方法：Viterbi算法S2SNS1S1S2viterbi算法t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05a1-0a2-0a3-0a4-0a5-0O1O2O3O42.隐马尔可夫状态路径预测：Viterbi算法t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05a1-0a2-0a3-0a4-0a5-0O1O2O3O4动画演示：由Viterbi算法计算产生观测序列O的最可能的一条隐藏状态序列QSkSkS1SNOt……S1……SNSkS1SN0t-1时刻OT

t时刻T时刻0SkS1SN……1时刻O1…………………………………初始化阶段(t=1)中间递归阶段（t=2,…,T）结束阶段Ot-1问题2：给定观察序列O=O1,O2,…,OT,以及模型λ,如何推测最可能的状态序列S?Max……S1SNSkS1S？S？S？S1……Max路径回溯向量3.预测隐马尔可夫状态路径：Viterbi算法表示t时刻，沿状态路径{q1,q2,…,qt},且qt=Sk时，产生已知的观察序列的前面t个子序列{o1,o2,…,ot}的最大概率值表示t时刻，到达隐状态sk，且其<dela概率*转移概率>乘积最大的那个状态对应的标记序号值。路径回溯提纲HiddenMarkovModel隐马尔科夫模型的三个问题总结13概率计算问题路径预测问题2参数训练问题参数训练问题1.隐马尔可夫模型-参数训练问题问题3：给定观察值序列O,如何调整模型参数λ=(π,A,B),使得P(O|λ)最大?t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN1……………A转移概率矩阵B生成概率矩阵πa01a02a0N…Π：初始概率向量S2…问题本质：参数λ=(π,A,B)的估值问题O1O2O3OT-1OT…已知观察序列O？？？情形1：路径已知时的参数估计

(监督学习方法)情形2：路径未知时的参数估计(非监督学习方法)问题3：给定观察值序列O,如何调整模型参数λ=(π,A,B),使得P(O|λ)最大?2.隐马尔可夫模型-参数训练问题即：由最大似然估计法对HMM的参数进行估计S2S3S1S5S2S2S3S1S5V1V3V2V2V1V4V3V4V1?????V1V3V2V2V1V4V3V4V1????Baum-Welch算法（EM算法特例）对HMM参数估计转移概率生成概率3.参数训练算法：Baum-Welch算法基础(将乘