隐马尔科夫模型原理图解.pptx

山山东大学高性能大学高性能计算与大数据算与大数据处理学科理学科组High Performance Computing and Big Data Processing Group张庆科科隐马尔可夫模型原理可夫模型原理图解解Hidden Markov Models1山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组提纲Hidden Markov Model隐马尔科夫模型的三个科夫模型的三个问题总结13l概率计算概率计算问题问题l路径预测问题路径预测问题2l参数学习问题参数学习问题Hidden Markov Model2山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组1马尔可夫模型可夫模型马尔马尔可可可可夫夫夫夫模型模型模型模型是数学中是数学中具有具有马尔可夫性可夫性质的离散的离散时间随机随机过程程，是用于，是用于描述随机描述随机过程程统计特征的概率特征的概率模型。模型。S2S3S1SNS1t=1t=2t=3t=T-1t=TS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN系统状态数目(N个)S2S3S1S1SN一条一条马尔可夫链马尔可夫链状状态序列序列=观测序列序列3山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组2.一一阶马尔可夫可夫模型概念模型概念t=1t=2t=3t4t=5S1S2S3S1S2S3系统状态数目(N=3)一一阶马尔可夫可夫模型（模型（Markov Models）S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下下时期状期状态只只取决于取决于当前当前时期期状状态和和转移概率移概率从某从某时刻状刻状态到下到下时刻刻的的状状态按一定概率按一定概率转移移t-1时刻t时刻qt-1qtqt-1qtq1q2q3t-1时刻t 时刻晴阴雨T=1T=2T=34山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组3.隐马尔可夫模型可夫模型t=1t=2t=3t=T-1t=TS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN隐藏状态S2S3S1S1SNt=1t=2t=3t=T-1t=T观测状状态Q1Q2QMQ1Q2QMQ1Q2QMQ1Q2QMQ1Q2QMQ1Q2隐藏状藏状态序列序列观察察状状态序列序列Q1QMQ2QMHMM状状态序列序列观测序列序列Q1QM一般随机一般随机过程程马儿科夫儿科夫过程程5山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组t=1t=2t=3t=4t=5S1S2S3一一阶隐马尔可夫可夫模型模型（Hidden Markov Models）图解解S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下下时期状期状态只只取决于取决于当前当前时期期状状态和和转移概率移概率从某从某时刻状刻状态到下到下时刻刻的的状状态按一定概率按一定概率转移移t-1时刻t时刻qt-1qt4.隐马尔可夫模型可夫模型(Hidden Markov Models,HMM)Q3Q4Q1Q1O2I-隐藏藏状状态转移概率生成概率b2(Q3)b3(Q4)b1(Q1)b1(Q1)b2(Q2)II-观察察序列序列S2S3S1S1S2qt-1qtq1q2q3t-1时刻t 时刻T=1T=2T=36山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNS1S2SNS1S2SNO1O2O3OT-1S2SNS1S1S25.隐马尔可夫模型可夫模型(Hidden Markov Models,HMM)HMM模型模型五五元元组表示：表示：（N,M,A,B）用来描述用来描述HMM，或，或简写写为 =(,A,B)一一阶隐马尔可夫可夫模型模型（Hidden Markov Models）数学）数学定定义 OTA转移概率矩阵OMOMOMOMOMB生成概率矩阵NM7山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组提纲Hidden Markov Model隐马尔科夫模型的三个科夫模型的三个问题总结13l概率计算概率计算问题问题l路径预测问题路径预测问题2l参数学习问题参数学习问题l概率计算概率计算问题问题8山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNzS1S2SNS1S2SNa11a12a13a22a21a23aN1aNNaN2a11a12a22a21a23a33a32a11a12a22a21a23a33a32O1O2O3OT-1OTA转移概率矩阵B生成概率矩阵n问题1：给定观察序列O=O1,O2,OT,以及模型=(,A,B),计算P(O|)？a01a02a0N：初始概率向量1.隐马尔可夫模型可夫模型-全概率全概率计算算S2问题本质：计算产生观测序列O的所有可能的状态序列对应的概率之和共N T 个可能路径（指数级计算）N=5,T=100,=计算量1072t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05aT1aT2aT3aT4aT5O1O2O3O4前前向向算算法法后后向向算算法法9山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组n问题1：给定观察序列O=O1,O2,OT,以及模型=(,A,B),如何计算P(O|)？SkSkS1SNOtS1SNSkS1SN0t-1OT tT0SkS1SN1O1初始化阶段(t=1)中间递归阶段（t=2,T）结束阶段2.概率概率计算算问题：前向算法（前向算法（Forward Algorithm）前前进Ot-1前前进N=5,T=100,=计算量300010山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组SkOt+1S1SNSkS1SN0OT tT0SkS1SN1O1.n问题1：给定观察序列O=O1,O2,OT,以及模型=(,A,B),如何计算P(O|)？3.概率概率计算算问题：后向：后向算法（算法（Forward Algorithm）OtSkS1SNt+1.后退后退后退后退初始化阶段(t=T)中间递归阶段（t=T-1,2,1）结束阶段11山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组提纲Hidden Markov Model隐马尔科夫模型的三个科夫模型的三个问题总结13l概率计算概率计算问题问题l路径预测问题路径预测问题2l参数学习问题参数学习问题l路径预测问题路径预测问题122024/5/21 周二1213山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组 1.隐马尔可夫模型可夫模型-路径路径预测n问题2：给定观察序列O=O1,O2,OT,以及模型,如何推测最可能的状态序列S?t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN1A转移概率矩阵B生成概率矩阵a01a02a0N：初始概率向量S2问题本质：计算产生观测序列O的最可能的一条隐藏状态序列QO1O2O3OT-1OT已知已知观察序列察序列？解决方法：Viterbi算法S2SNS1S1S2viterbi算法算法t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05a1-0a2-0a3-0a4-0a5-0O1O2O3O414山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组2.隐马尔可夫状可夫状态路径路径预测：Viterbi算法算法t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05a1-0a2-0a3-0a4-0a5-0O1O2O3O4动画演示：由Viterbi算法计算产生观测序列O的最可能的一条隐藏状态序列Q15山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组SkSkS1SNOtS1SNSkS1SN0t-1时刻OT t时刻T时刻0SkS1SN1时刻O1初始化阶段(t=1)中间递归阶段（t=2,T）结束阶段Ot-1n问题2：给定观察序列O=O1,O2,OT,以及模型,如何推测最可能的状态序列S?MaxS1SNSkS1S？S？S？S1Max路径路径回溯回溯向量向量3.预测隐马尔可夫状可夫状态路径：路径：Viterbi算法算法表示表示t t时刻，沿状态路径时刻，沿状态路径q1,q2,qt,q1,q2,qt,且且q qt t=S=Sk k时，产生已知的观时，产生已知的观察序列的前面察序列的前面t t个子序列个子序列o1,o2,oto1,o2,ot的最大概率值的最大概率值表示表示t t时刻，到达隐状态时刻，到达隐状态sksk，且其，且其dela 乘积最大乘积最大的那个状态对应的标记序号值。的那个状态对应的标记序号值。路径路径回溯回溯16山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组提纲Hidden Markov Model隐马尔科夫模型的三个科夫模型的三个问题总结13l概率计算概率计算问题问题l路径预测问题路径预测问题2l参数训练问题参数训练问题l参数训练问题参数训练问题17山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组1.隐马尔可夫模型可夫模型-参数参数训练问题n问题3：给定观察值序列O,如何调整模型参数=(,A,B),使得P(O|)最大?t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN1A转移概率矩阵B生成概率矩阵a01a02a0N：初始概率向量S2问题本质：参数=(,A,B)的估值问题O1O2O3OT-1OT已知已知观察序列察序列O？18山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组情形情形1：路径已知时的参数估计(监督学习方法)情形情形2：路径未知时的参数估计(非监督学习方法)n问题3：给定观察值序列O,如何调整模型参数=(,A,B),使得P(O|)最大?2.隐马尔可夫模型可夫模型-参数参数训练问题即：由最大似然估即：由最大似然估计法法对HMMHMM的参数的参数进行估行估计S2S3S1S5S2S2S3S1S5V1V3V2V2V1V4V3V4V1?V1V3V2V2V1V4V3V4V1?Baum-Welch算法（算法（EM算法特例）算法特例）对HMM参参数估数估计转移概率生成概率19山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组3.参数参数训练算法：算法：Baum-Welch算法基算法基础(将乘积因子按定义展开)前前向算法向算法后向算法后向算法(将分子中的按其递归计算公式展开)令其为令其为前后向算法关系前后向算法关系图20山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组4.参数参数训练算法：算法：Baum-Welch算法（算法（单观测序列）序列）但在但在实际应用中用中,训练一一个个HMM用用到的到的观测值序列往往不止一个序列往往不止一个,那么那么,对于于多多个个观测值序列序列训练时,要要对BW算法算法的重估的重估公式公式进行修行修正正.A转移概率矩移概率矩阵B生成生成概率矩概率矩阵初始概率矩初始概率矩阵21山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组A转移概率矩移概率矩阵B生成生成概率矩概率矩阵0-初始概率矩初始概率矩阵5.参数参数训练算法：算法：Baum-Welch算法算法（多（多观测序列序列这种多种多观测序列正好适用于蛋白序列正好适用于蛋白质家族序列中相关家族序列中相关问题的解决：如多序列比的解决：如多序列比对22山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组情形情形1：路径已知时的参数估计(监督学习方法)情形情形2：路径未知时的参数估计(非监督学习方法)6.参数参数训练算法：算法：Baum-Welch算法算法过程程纵览S2S3S1S5S2S2S3S1S5V1V3V2V2V1V4V3V4V1?V1V3V2V2V1V4V3V4V1?Baum-Welch算法算法转移概率生成概率初始概率极大似然极大似然统计法法转移概率生成概率初始概率23山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组山东大学高性能计算与大数据处理学科组Email:Thank you!242024/5/21 周二24