隐马尔可夫模型有例子具体易懂.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,隐马尔可夫模型有例子具体易懂,主要内容,马尔可夫模型,隐马尔可夫模型,隐马尔可夫模型的三个基本问题,三个基本问题的求解算法,1.,前向算法,算法,3.,向前向后算法,隐马尔可夫模型的应用,隐马尔可夫模型的一些实际问题,隐马尔可夫模型总结,马尔可夫链,一个系统有,N,个状态,S1,，,S2,，,，,Sn,，随着时间推移，系统从某一状态转移到另一状态，设,qt,为时间,t,的状态，系统在时间,t,处于状态,Sj,的概率取决于其在时间,1,，,2,，,，,t-1,的状态，该概率为：,如果系统在,t,时间的状态只与其在时间,t-1,的状态相关，则该系统构成一个离散的一阶马尔可夫链,(,马尔可夫过程,),：,马尔可夫模型,如果只考虑独立于时间,t,的随机过程：,其中状态转移概率,a,ij,必须满足,a,ij,=0,且,，则该随机过程称为马尔可夫模型。,例,假定一段时间的气象可由一个三状态的马尔可夫模型,M,描述，,S1,：雨，,S2,：多云，,S3,：晴，状态转移概率矩阵为：,例（续）,如果第一天为晴天，根据这一模型，在今后七天中天气为,O=,“,晴晴雨雨晴云晴,”,的概率为：,隐马尔可夫模型（,Hidden Markov Model,HMM,）,在,MM,中，每一个状态代表一个可观察的,事件,在,HMM,中观察到的事件是状态的随机函数，因此该模型是一双重随机过程，其中状态转移过程是不可观察（隐蔽）的,(,马尔可夫链,),，而可观察的事件的随机过程是隐蔽的状态转换过程的随机函数,(,一般随机过程,),。,HMM,的三个假设,对于一个随机事件，有一观察值序列：,O=O,1,O,2,O,T,该事件隐含着一个状态序列：,Q=q,1,q,2,q,T,。,假设1：,马尔可夫性假设（状态构成一阶马尔可夫链）,P(q,i,|q,i-1,q,1,)=P(q,i,|q,i-1,),假设2：,不动性假设（状态与具体时间无关）,P(q,i+1,|q,i,)=P(q,j+1,|q,j,)，,对任意,i,，,j,成立,假设3：,输出独立性假设（输出仅与当前状态有关）,p(O,1,.,O,T,|q,1,.,q,T,)=,p,(O,t,|q,t,),HMM,定义,一个隐马尔可夫模型(,HMM),是由一个五元组描述的：,（,N,，,M,，,A,，,B,，,）,其中：,N,=q,1,.q,N,：,状态的有限集合,M,=v,1,.,v,M,：,观察值的有限集合,A=a,ij,，a,ij,=P(q,t,=S,j,|q,t-1,=S,i,)：,状态转移概率矩阵,B=b,jk,，,b,jk,=P(O,t,=v,k,|q,t,=S,j,)：,观察值概率分布矩阵,=,i,，,i,=P(q,1,=S,i,)：,初始状态概率分布,观察序列产生步骤,给定,HMM,模型,=(A,，,B,，,),，则观察序列,O=O,1,O,2,O,T,可由以下步骤产生：,1.,根据初始状态概率分布,=,i,选择一初始状态,q,1,=S,i,；,2.,设,t=1,；,3.,根据状态,S,i,的输出概率分布,b,jk,输出,O,t,=v,k,；,4.,根据状态转移概率分布,a,ij,转移到新状态,q,t+1,=S,j,；,5.,设,t=t+1,如果,t=0,且,可以看出，最有可能的状态序列是：,在前向算法、Viterbi算法以及Baum-Welch算法中，概率值的连续乘法运算很容易导致下溢现象。,目标：给定一个观察序列和HMM模型，如何有效选择“最优”状态序列，以“最好地解释”观察序列,给定一系列观察序列样本,确定能够产生出这些序列的模,由状态序列及各状态的明字符生成概率(Q,B)所决定,由离散隐状态组成的状态序列(路径),对于给定的不完全数据和当前的参数值，“E过程”从条件期望中相 应地构造完全数据的似然函数值，“M过程”则利用参数的充分统计,根据状态 Si的输出概率分布bjk,输出Ot=vk；,给定一系列观察序列样本,确定能够产生出这些序列的模,可以由最大似然估计来估计HMM的参数：,问题 1 评估问题,给定一系列观察序列样本,确定能够产生出这些序列的模,一个骰子掷出的点数记录,某赌场在掷骰子根据点数决定胜负时,暗中,三个基本问题的求解算法,可以看出，最有可能的状态序列是：,可以由最大似然估计来估计HMM的参数：,学习问题：对于给定的一个观察值序列O，调整参数，使得观察值出现的概率P(O|)最大。,三个基本问题的求解算法,数值计算中的防溢出处理,根据初始状态概率分布=i,选择一初始状态q1=Si；,HMM,的应用,语音识别,音字转换,词性标注（,POS Tagging）,基因识别问题,状态,:,编码区域与非编码区域,字符,:ATCG,一般化：任何与线性序列相关的现象,HMM,的一些实际问题,初始概率分布的选择,1.,随机选择,2.,利用先验信息,3.,来自多序列比对的结果,HMM,的一些实际问题（续）,数值计算中的防溢出处理,在前向算法、,Viterbi,算法以及,Baum-Welch,算法中，概率值的连续乘法运算很容易导致下溢现象。,解决办法：,1.,前向算法中：每一个时间步的运算中都乘以一 个比例因子,算法中：对概率值取对数后计算,Viterbi,算法,:,连乘积,对数求和,前向算法,:,引入比例因子,其中,比例因子,谢谢观看！,