第五章_隐马尔可夫模型

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 隐马尔可夫模型,(,H,idden,M,arkov,M,odel),王 侠,徐州师范大学物理与电子工程学院,2008,年,5,月,18,日,一、,HMM,的由来,二、马尔可夫性和马尔可夫链,三、,HMM,实例,四、,HMM,的三个基本算法,1,、马尔可夫链,2,、马尔可夫模型,1870,年，俄国有机化学家,Vladimir V.,Markovnikov,3,、隐马尔可夫模型,60,年代末,70,年代初,Baum,等人建立的,一、,HMM,的由来,二、马尔可夫性和马尔可夫链,三、,HMM,实例,四、,HMM,的三个基本算法,马尔可夫性,如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有,马尔可夫性,或称此过程为,马尔可夫过程,X(t+1)=f(,X(t,),马尔科夫链,时间,和,状态,都离散的马尔科夫过程称为马尔科夫链,记作,X,n,=X(n),n=0,1,2,在时间集,T,1,=0,1,2,上对离散状态的过程相继观察的结果,链的状态空间记做,I=a,1,a,2,a,i,R,.,条件概率,P,ij,(,m,m+n,),=,PX,m+n,=,a,j,|X,m,=,a,i,为马氏链在时刻,m,处于状态,a,i,条件下，在时刻,m+n,转移到状态,a,j,的,转移概率,。,转移概率矩阵,阴天,晴天,下雨,晴天 阴天 下雨,晴天,0.50 0.25,0.25,阴天,0.375 0.25 0.375,下雨,0.25 0.125 0.625,转移概率矩阵,(,续,),由于链在时刻,m,从任何一个状态,a,i,出发，到另一时刻,m+n,，,必然转移到,a,1,，,a,2,，,诸状态中的某一个，所以有,当,P,ij,(m,m+n,),与,m,无关时，称马尔科夫链为,齐次马尔科夫链,，通常说的马尔科夫链都是指齐次马尔科夫链。,HMM,的由来,马尔可夫性和马尔可夫链,HMM,实例,HMM,的三个基本算法,HMM,是一个输出符号序列的统计模型，具有个状态,S,1,S,2,S,N,它按一定的周期从一个状态转移到另一个状态，每次转移时，输出一个符号转移到哪一个状态，转移时输出什么符号，分别由转移概率和转移时的输出概率来决定,S,1,S,2,S,3,a,11,0.3,a,b,0.80.2,a,22,0.4,a,b,0.30.7,a,12,0.5,a,b,1,0,a,23,0.6,a,b,0.50.5,a,13,0.2,a,b,0,1,例一,S,1,S,2,S,3,a,11,0.3,a,b,0.80.2,a,12,0.5,a,b,1,0,a,23,0.6,a,b,0.50.5,a,13,0.2,a,b,0,1,S,1,S,1,S,2,S,3,0.3*0.8*0.5*1.0*0.6*0.5=0.036,a,22,0.4,a,b,0.30.7,S,1,S,2,S,3,a,11,0.3,a,b,0.80.2,a,12,0.5,a,b,1,0,a,23,0.6,a,b,0.50.5,a,13,0.2,a,b,0,1,S,1,S,2,S,2,S,3,0.5*1.0*0.4*0.3*0.6*0.5=0.018,a,22,0.4,a,b,0.30.7,S,1,S,2,S,3,a,11,0.3,a,b,0.80.2,a,12,0.5,a,b,1,0,a,23,0.6,a,b,0.50.5,a,13,0.2,a,b,0,1,S,1,S,1,S,1,S,3,0.3*0.8*0.3*0.8*0.2*1.0=0.01152,所以输出,aab,的总概率是：,0.036+0.018+0.01152=0.06552,a,22,0.4,a,b,0.30.7,Observed Ball Sequence,Urn 3,Urn 1,Urn 2,Veil,例二,设有,N,个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下,根据初始概率分布，随机选择,N,个缸中的一个开始实验,根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为,O,1,，并把球放回缸中,根据描述缸的转移的概率分布，随机选择下一口缸，重复以上步骤。,最后得到一个描述球的颜色的序列,O,1,O,2,，,称为观察值序列,O,。,在上述实验中，有几个要点需要注意：,不能被直接观察缸间的转移,从缸中所选取的球的颜色和缸并不是,一一对应的,每次选取哪个缸由一组转移概率决定,HMM,概念,HMM,的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来,观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系,HMM,是一个双重随机过程，两个组成部分：,马尔可夫链,：描述状态的转移，用,转移概率,描述。,一般随机过程,：描述状态与观察序列间的关系，用,观察值概率,描述。,Markov,链,（,A,）,随机过程,（,B,）,状态序列,观察值序列,q,1,q,2,.,q,T,o,1,o,2,.,o,T,HMM,的组成示意图,HMM,的组成,HMM,的基本要素,用模型五元组 （,S,O,，,A,，,B,）用来描述,HMM,，或简写为,=(,，,A,，,B),参数,含义,实例,S,模型中状态的有限集合,缸,O,每个状态可能的观察值数目,彩球颜色数目,A,与,时间无关的状态转移概率矩阵,在,选定某个缸的情况下，选择另一个缸的概率,B,给定状态下，观察值概率分布,每个缸中的颜色分布,p,初始状态空间的概率分布,初始时选择某口缸的概率,HMM,可解决的问题,问题,1,：给定观察序列,O=O,1,O,2,O,T,以及模型,如何计算,P(O|M),？,问题,2,：给定观察序列,O=O,1,O,2,O,T,以及模型,M,如何选择一个对应的状态序列,S=S,1,S,2,S,T,，,使得,S,能够最为合理的解释观察序列,O,？,问题,3,：如何调整模型参数,使得,P(O|M),最大？,解决问题,1,前向方法,输出的观察符号序列,首先明确下列定义：,给定模型入时，输出符号序列,O,的概率,从状态,S,i,到状态,S,j,的转移概率,从状态,Si,到状态,Sj,发生转移时输出,o,t,的概率,输出部分符号序列,并且达到状态,S,j,的概率前向概率,解决问题,1,前向法,定义前向变量,初始化：,递归：,终结：,计算步骤如下,:,(1),给每个状态准备一个数组变量 初始化时令初始状态,S,1,的数组变量 为,1,其他状态数组变量 为,0,(2),根据,t,时刻输出的观察符号,o,t,计算,:,当状态,S,i,到,S,j,没有转移时,=0,(3),当,tT,时,转移到,(2),否则执行,(4),(4),把这时的终了状态的数组变量 内的值取出,则,:,前向法示意图,1 .t-1 t .,a,1j,a,t,1,q,N,.,q,i,.,q,j,.,.,.,q,1,a,t,N,a,t,i,a,Nj,a,ij,N=5,M=100,=,计算量,3000,计算量,:,乘法,N(N+1)(T-1)+N,加法,N(N-1)(T-1),状态,1,状态,2,状态,3,a,1,(1)=0.24,a,1,(2)=0.5,a,1,(3)=0,a,2,(1)=0.00576,a,2,(2)=0.18,a,2,(3)=0.15,a,3,(3)=0.0655,a,a,b,0.5,0.5,0.2,0,0.12,0.24,0.24,0.3,0.3,输出的观察符号序列,首先明确下列定义：,给定模型入时，输出符号序列,O,的概率,从状态,S,i,到状态,S,j,的转移概率,从状态,Si,到状态,Sj,发生转移时输出,o,t,的概率,从状态,Si,开始到状态,SN,结束时输出部分符号序列 的概率,即后向概率,解决问题,1,后向法,与前向法类似,初始化：,递推公式：,最后结果：,后向算法的计算量大约在,N2T,数量级,根据前向和后向概率,:,Viterbi,算法,目的：,给定观察序列,O,以及模型,如何选择一个对应的状态序列,S,，使得,S,能够最为合理的解释观察序列,O,？,Viterbi,算法叙述,:,(1),初始化,(2),递推公式,(3),最后结果,Viterbi,算法(续),Viterbi,算法求取最佳状态序列的步骤,(1),给每个状态准备一个数组变量 ，初始化时令初始状态,S,1,的数组变 量为,1,，其他数组状态的数组变量 为,0,；,(2),根据,t,时刻输出的观察符号,o,t,计算,:,(3),当,tT,时，转移到,(2),否则执行,(4),(4),把这时的终了状态寄存器内的值取出，则：,按照前向,在,t,时刻从状态,S,i,Baum-Welch,算法,:,给定一个观察值序列,以及一个初始模型,后向算法,对于符号序列,概率为,则,可表示如下,:,同时对于符号序列,在,t,时,Markov,链处于状态,Si,的概率为,:,转移到状态,S,j,的转移,状态,Si,转移到状态,Sj,的转移次数的,这样对于符号序列,而从状态,Si,转移出去的次数的期望值为,由此可以推导出,Baum-Welch,算法中的重估公式,:,期望值为,:,用,Bauum,-Welch,算法训练,HMM,的步骤,:,(1),适当的选择,的初始值,A:,给予从状态,i,转移出去的每条弧相等的转移概率,B:,给予每个输出观察符号相等的输出概率初始值,并且每条弧上,(2),给定一个,(,训练,),观察值符号序列,由初始模型计算,由重估公式计算,和,给予相同的输出概率矩阵,(3),再给定一个,(,训练,),观察值符号序列,把前一次的,和,作为初始模型计算,由重估公式重新计算,和,如此反复,直到,和,收敛为止,说明,:,语音识别一般采用从左到右型,HMM,所以初始状态概率,不需要估计,总是设定为,:,几种典型形状的,HMM,a.,全连接的模型,(A,矩阵没有零值,),b.A,矩阵有零值的模型,c.,有跨越的从左向右模型,d.,无跨越的从左向右模型,HMM,的一些实际问题,1,、下溢问题,在每步递归运算时乘以一个定标因子,2,、参数初始化问题,手工统计,采用分段,K,均值算法,3,、训练数据不足的问题,将两个模型整合,4,、说话人的影响,修正重估公式,5,、提高,HMM,描述语音动态特性的能力,利用语音的相关信息,