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

1、,山东大学高性能计算与大数据处理学科组 High Performance Computing and Big Data Processing Group,张庆科,隐马尔可夫模型原理图解,Hidden Markov Models,提 纲,Hidden Markov Model,隐马尔科夫模型的三个问题,总结,1,3,2,Hidden Markov Model,1马尔可夫模型,马尔可夫模型是数学中具有马尔可夫性质的离散时间随机过程，是用于描述随机过程统计特征的概率模型。,t=1,t=2,t=3,t=T-1,t=T,S1,S2,S3,SN,S1,S2,S3,SN,S1,S2,S3,SN,S1,S2,

2、S3,SN,S1,S2,S3,SN,系统状态数目(N个),状态序列=观测序列,2. 一阶马尔可夫模型概念,t=1,t=2,t=3,t=4,t=5,S1,S2,S3,S1,S2,S3,系统状态数目(N=3),一阶马尔可夫模型（Markov Models）,S1,S2,S3,S1,S2,S3,S1,S2,S3,S1,S2,S3,a11,a12,a13,a22,a21,a23,a31,a33,a32,a11,a12,a22,a21,a23,a33,a32,a11,a12,a22,a21,a23,a33,a32,a11,a12,a22,a21,a23,a33,a32,下时期状态只取决于当前时期状态和转

3、移概率,从某时刻状态到下时刻的状态按一定概率转移,t-1时刻,t时刻,qt-1,qt,q1,q2,q3,t-1时刻,t 时刻,晴,阴,雨,T=1,T=2,T=3,3. 隐马尔可夫模型,t=1,t=2,t=3,t=T-1,t=T,S1,S2,S3,SN,S1,S2,S3,SN,S1,S2,S3,SN,S1,S2,S3,SN,S1,S2,S3,SN,S1,S2,S3,SN,隐藏状态,t=1,t=2,t=3,t=T-1,t=T,观测状态,隐藏状态序列,观察状态序列,HMM,状态序列观测序列,一般随机过程,马儿科夫过程,t=1,t=2,t=3,t=4,t=5,S1,S2,S3,一阶隐马尔可夫模型（Hi

4、dden Markov Models）图解,S1,S2,S3,S1,S2,S3,S1,S2,S3,S1,S2,S3,a11,a12,a13,a22,a21,a23,a31,a33,a32,a11,a12,a22,a21,a23,a33,a32,a11,a12,a22,a21,a23,a33,a32,a11,a12,a22,a21,a23,a33,a32,下时期状态只取决于当前时期状态和转移概率,从某时刻状态到下时刻的状态按一定概率转移,t-1时刻,t时刻,qt-1,qt,4. 隐马尔可夫模型(Hidden Markov Models,HMM),I-隐藏状态,转移概率,生成概率,b2(Q3),b

5、3(Q4),b1(Q1),b1(Q1),b2(Q2),II-观察序列,q1,q2,q3,t-1时刻,t 时刻,T=1,T=2,T=3,t=1,t=2,t=3,t=T-1,t=T,S1,S2,S3,S1,S2,SN,S1,S2,SN,S1,S2,SN,S1,S2,SN,OT-1,5. 隐马尔可夫模型(Hidden Markov Models,HMM),HMM模型五元组表示： （ N, M, , A, B）用来描述HMM，或简写为 =( , A, B),一阶隐马尔可夫模型（Hidden Markov Models）数学定义,OT,N,M,提 纲,Hidden Markov Model,隐马尔科夫模

6、型的三个问题,总结,1,3,2,t=1,t=2,t=3,t=T-1,t=T,S1,S2,S3,S1,S2,SN,S1,S2,SN,z,S1,S2,SN,S1,S2,SN,a11,a12,a13,a22,a21,a23,aN1,aNN,aN2,a11,a12,a22,a21,a23,a33,a32,a11,a12,a22,a21,a23,a33,a32,问题1：给定观察序列O=O1,O2, ,OT,以及模型=(,A,B),计算P(O|)？,a01,a02,a0N,：初始概率向量,1. 隐马尔可夫模型-全概率计算,S2,问题本质：计算产生观测序列O的所有可能的状态序列对应的概率之和,共 N T 个

7、可能路径（指数级计算）,N=5, T=100, = 计算量1072,t=1,t=2,t=3,B,E,t=4,a01,a02,a03,a04,a05,aT1,aT2,aT3,aT4,aT5,前向算法,后向算法,问题1：给定观察序列O=O1,O2, ,OT,以及模型=(,A,B),如何计算P(O|)？,Sk,Sk,S1,SN,S1,SN,Sk,S1,SN,0,t-1,t,T,0,Sk,S1,SN,1,初始化阶段(t = 1),中间递归阶段（t = 2,T）,结束阶段,2. 概率计算问题：前向算法（Forward Algorithm）,前进,前进,N=5, T=100, = 计算量3000,Sk,S

8、1,SN,Sk,S1,SN,0,t,T,0,Sk,S1,SN,1,.,问题1：给定观察序列O=O1,O2, ,OT,以及模型=(,A,B),如何计算P(O|)？,3. 概率计算问题：后向算法（Forward Algorithm）,Sk,S1,SN,t+1,.,.,后退,后退,初始化阶段(t = T),中间递归阶段（t = T-1, 2,1）,结束阶段,提 纲,Hidden Markov Model,隐马尔科夫模型的三个问题,总结,1,3,2,1.隐马尔可夫模型-路径预测,t=1,t=2,t=3,t=T-1,t=T,S1,S2,SN,S1,S2,SN,S1,S2,SN,z,S1,S2,SN,S1

9、,S2,SN,aN1,a01,a02,a0N,：初始概率向量,S2,问题本质：计算产生观测序列O的最可能的一条隐藏状态序列Q,已知观察序列,解决方法：Viterbi算法,viterbi算法,t=1,t=2,t=3,B,E,t=4,a01,a02,a03,a04,a05,a1-0,a2-0,a3-0,a4-0,a5-0,2. 隐马尔可夫状态路径预测：Viterbi算法,t=1,t=2,t=3,S1,S2,S1,S2,S1,S2,B,E,S4,S4,S4,S5,S5,S5,S3,S3,S3,t=4,S1,S2,S4,S5,S3,a01,a02,a03,a04,a05,a1-0,a2-0,a3-0,

10、a4-0,a5-0,O1,O2,O3,O4,动画演示：由Viterbi算法计算产生观测序列O的最可能的一条隐藏状态序列Q,Sk,Sk,S1,SN,S1,SN,Sk,S1,SN,0,t-1时刻,t时刻,T时刻,0,Sk,S1,SN,1时刻,初始化阶段(t = 1),中间递归阶段（t = 2,T）,结束阶段,路径回溯,向量,3. 预测隐马尔可夫状态路径：Viterbi算法,路径回溯,提 纲,Hidden Markov Model,隐马尔科夫模型的三个问题,总结,1,3,2,1. 隐马尔可夫模型-参数训练问题,问题3：给定观察值序列O,如何调整模型参数=(,A,B),使得P(O|)最大 ?,t=1,

11、t=2,t=3,t=T-1,t=T,S1,S2,SN,S1,S2,SN,S1,S2,SN,z,S1,S2,SN,S1,S2,SN,aN1,a01,a02,a0N,：初始概率向量,S2,问题本质：参数=(,A,B)的估值问题,已知观察序列O,情形1：路径已知时的参数估计 (监督学习方法),情形2：路径未知时的参数估计 (非监督学习方法),问题3：给定观察值序列O,如何调整模型参数=(,A,B),使得P(O|)最大 ?,2. 隐马尔可夫模型-参数训练问题,即：由最大似然估计法对HMM的参数进行估计,S2,S3,S1,S5,S2,S2,S3,S1,S5,?,?,?,?,?,?,?,?,?,Baum-

12、Welch算法（EM算法特例）对HMM参数估计,转移概率,生成概率,3. 参数训练算法：Baum-Welch算法基础,(将乘积因子按定义展开),前向算法,后向算法,(将分子中的按其递归计算公式展开),前后向算法关系图,4. 参数训练算法：Baum-Welch算法（单观测序列）,但在实际应用中,训练一个HMM用到的观测值序列往往不止一个,那么,对于多个观测值序列训练时,要对BW算法的重估公式进行修正.,A转移概率矩阵,B生成概率矩阵,初始概率矩阵,A转移概率矩阵,B生成概率矩阵,0-初始概率矩阵,5. 参数训练算法：Baum-Welch算法（多观测序列）,这种多观测序列正好适用于蛋白质家族序列中相关问题的解决：如多