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

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,隐马尔可夫模型,1,主要内容,马尔可夫模型,隐马尔可夫模型,隐马尔可夫模型的三个基本问题,三个基本问题的求解算法,1.,前向算法,2.,Viterbi,算法,3.,向前向后算法,隐马尔可夫模型的应用,隐马尔可夫模型的一些实际问题,隐马尔可夫模型总结,2,马尔可夫链,一个系统有,N,个状态,S1,，,S2,，,，,Sn,，随着时间推移，系统从某一状态转移到另一状态，设,qt,为时间,t,的状态，系统在时间,t,处于状态,Sj,的概率取决于其在时间,1,，,2,，,，,t-1,的状态，该概率为：,如果系统在,t,时间的状态只与其在时间,t-1,的状态相关，则该系统构成一个离散的一阶,马尔可夫链,(,马尔可夫过程,),：,3,马尔可夫模型,如果只考虑独立于时间,t,的随机过程：,其中状态转移概率,a,ij,必须满足,a,ij,=0,且,，则该随机过程称为,马尔可夫模型,。,4,例,假定一段时间的气象可由一个三状态的马尔可夫模型,M,描述，,S1,：雨，,S2,：多云，,S3,：晴，状态转移概率矩阵为：,5,例（续）,如果第一天为晴天，根据这一模型，在今后七天中天气为,O=,“,晴晴雨雨晴云晴,”,的概率为：,6,隐马尔可夫模型（,Hidden Markov Model,HMM,）,在,MM,中，每一个状态代表一个可观察的,事件,在,HMM,中观察到的事件是状态的随机函数，因此该模型是一双重随机过程，其中状态转移过程是不可观察（隐蔽）的,(,马尔可夫链,),，而可观察的事件的随机过程是隐蔽的状态转换过程的随机函数,(,一般随机过程,),。,7,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,),8,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,)：,初始状态概率分布,9,观察序列产生步骤,给定,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,如果,tT,，重复步骤,3,、,4,，否则结束。,10,HMM,的三个基本问题,令,=,，,A,，,B,为给定,HMM,的参数，,令,O,=O,1,.,O,T,为观察值序列，则有关于,隐马尔可夫模型（,HMM）,的三个基本问题：,1.,评估问题：,对于给定模型，求某个观察值序列的概率,P(,O,|,),；,2.,解码问题：,对于给定模型和观察值序列，求可能性最大的状态序列,max,Q,P(Q|O,),；,3.,学习问题：,对于给定的一个观察值序列,O,，调整参数,，,使得观察值出现的概率,P(,O,|,),最大。,11,例,:,赌场的欺诈,某赌场在掷骰子根据点数决定胜负时,暗中,采取了如下作弊手段,:,在连续多次掷骰子的过程中,通常使用公平骰,子,A,B,0.9,0.1,A,偶而,混入一个灌铅骰子,B.,0.8,0.2,公平骰子,灌铅骰子,12,骰子,A,骰子,B,1,点,1/6,0,2,点,1/6,1/8,3,点,1/6,1/8,4,点,1/6,3/16,5,点,1/6,3/16,6,点,1/6,3/8,公平骰子,A,与灌铅骰子,B,的区别,:,13,时间,1,2,3,4,5,6,7,骰子,A,A,A,B,A,A,A,掷出,点数,3,3,4,5,1,6,2,一次连续掷骰子的过程模拟,隐,序列,明,序列,查封赌场后,调查人员发现了一些连续掷骰子的记录,其中有一个骰子掷出的点数记录如下,:,124552646214614613613666166466163661636616361651561511514612356234,14,问题,1,评估问题,给定,一个骰子掷出的点数记录,124552,6,4,6,214,6,14,6,13,6,13,666,1,66,4,66,1,6,3,66,1,6,3,66,1,6,3,6,1,6,515,6,1511514,6,1235,6,234,问题,会出现这个点数记录的概率有多大,?,求,P(O|,),15,问题,2,解码问题,给定,一个骰子掷出的点数记录,124552,6,4,6,214,6,14,6,13,6,13,666,1,66,4,66,1,6,3,66,1,6,3,66,1,6,3,6,1,6,515,6,1511514,6,1235,6,234,问题,点数序列中的哪些点数是用骰子,B,掷出的,?,求,maxQP(Q|O,),16,问题,3,学习问题,给定,一个骰子掷出的点数记录,124552,6,4,6,214,6,14,6,13,6,13,666,1,66,4,66,1,6,3,66,1,6,3,66,1,6,3,6,1,6,515,6,1511514,6,1235,6,234,问题,作弊骰子掷出各点数的概率是怎样的,?,公平骰子,掷出各点数的概率又是怎样的,?,赌场是何时,换用骰子的,?,17,骰子,B,本例中,HMM,的定义,赌场的例子中,:,隐状态集,:S=,骰子,A,骰子,B,明字符集,:V=1,2,3,4,5,6,b,21,=0,b,22,=b,23,=1/8,b,24,=b,25,=3/16,b,26,=3/8,1/6,1/6,1/6,1/6,1/6,1/6,0,1/8,1/8,3/16,3/16,3/8,初始状态概率,:,1,=1,2,=0,隐状态转移概率,:,a,11,=0.9,a,12,=0.1,a,21,=0.8,a,22,=0.2,初始状态,明字符生成概率,:,b,11,=b,12,=b,16,=1/6,1.0,0,1:,2:,3:,4:,5:,骰子,A,6:,0.1,1:,2:,3:,4:,5:,6:,0.8,0.9,0.2,18,HMM,将两个序列相联系起来：,1.,由离散,隐,状态组成的,状态序列,(,路径,),Q=(q,1,q,T,),每个,q,t,S,均是一个状态,由初始状态概率及状态转移概率,(,A),所决定,2.,由,明,字符组成的,观察序列,O=(o,1,o,T,),每个,o,t,V,均为一个离散明字符,由状态序列及各状态的明字符生成概率,(Q,B),所决定,19,赌场的例子中,:,隐,状态,明,观察,AAAA,B,AAAAA,B,AAAAAAAAAAAAAAAAAAAAAAABAA,B,AAAAAAAAA,3 3 4 5 4 1 4 1 5 5 3 6 6 3 4 4 1 1 3 4 6 2 5 4 4 5 3 3 4 2 2 3 3 3 2 1 2 4 2 2 5 6 3 1 3 4 1,q,1,q,2,q,3,q,4,q,T,.,o,1,o,2,o,3,o,4,o,T,.,观察序列,O,状态序列,Q,HMM,20,本例中三个基本问题,1.,评估问题,给定观察序列,O,和,HMM,=(,A,B),判断,O,是由,产,生出来的可能性有多大,计算骰子点数序列的确由,“,作弊,”,模型生成的可能性,2.,解码问题,给定观察序列,O,和,HMM,=(,A,B),计算与序列,O,相,对应的状态序列是什么,在骰子点数序列中,判断哪些点数是用骰子,B,掷出的,3.,学习问题,给定一系列观察序列样本,确定能够产生出这些序列的模,型,=(,A,B),如何从大量的点数序列样本中学习得出,“,作弊模型,”,的参数,21,三个基本问题的求解算法,评估问题：前向算法,定义前向变量,采用动态规划算法，复杂度,O(N,2,T),解码问题：韦特比（,Viterbi）,算法,采用动态规划算法，复杂度,O(N,2,T),学习问题：向前向后算法,EM,算法的一个特例，带隐变量的最大似然估计,22,解决问题一,前向算法,定义,前向变量,为：,“,在时间步,t,得到,t,之前的所有明符号序列,且时间,步,t,的状态是,S,i,”,这一事件的概率，,记为,(,t,i,)=,P(o,1,o,t,q,t,=S,i,|,),则,23,算法过程,24,HMM,的网格结构,25,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,(,t,i),26,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,初始化,(1,i)=(i)b(i,o1),27,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,28,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,29,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,30,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,31,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,2.,递归,32,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,33,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,34,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,35,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,36,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,37,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,38,前向算法过程演示,i=N,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=N-1,i=5,i=4,i=3,i=2,i=1,39,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,40,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,41,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,42,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,43,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,44,t=1,t=2,t=3,t=4,t=5,t=T,t=7,t=6,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,45,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,46,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,47,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,3.,计算,P(O|,),48,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,49,例子（前向算法应用）,HMM,模型如下，试根据前向算法计算产生观察符号序列,O=ABAB,的概率。,状态集,Q=S1,S2,S3,观察序列集,O=A,B,50,例（续）,初始概率矩阵,=(1,0,0),即开始处于状态,1,。按照前向算法公式，我们依次递推解出,t,(i),。解法如下：,1.,当,t=1,时：,51,例（续）,2.,当,t=2,时：,3.,当,t=3,时：,52,例（续）,4.,当,t=4,时：,所以最终有：,P(O|,)=,4,(1)+,4,(2)+,4,(3)=0.0717696,即观察序列,O,由,HMM,模型,产生的概率,53,例（续）,最后将其计算过程示意图表示如下：,54,问题,2,解码问题,所求的,Q,应当在某个准则下是,“,最优,”,的,因此也称,Q,为最优路径,解码问题即是确定,最优路径的问题。,55,q,t,=S,i,产生出,o,1,o,t,的最大概率，即：,解决问题二,Viterbi,算法,Viterbi,算法也是类似于前向算法的一种网格结构,56,Viterbi,算法（续）,目标：给定一个观察序列和,HMM,模型，如何有效选择“最优”状态序列，以“最好地解释”观察序列,“最优”概率最大：,Viterbi,变量：,递归关系：,记忆变量：记录概率最大路径上当前状态的前一个状态,57,Viterbi,算法（续）,初始化：,递归：,终结：,路径回溯：,58,例子（,Viterbi,算法应用）,HMM,模型如下，试根据,Viterbi,算法计算产生观察符号序列,O=ABAB,的最优状态序列,Q,。,状态集,Q,S1,S2,S3,观察序列集,O=A,B,59,例（续）,初始概率矩阵,=(1,0,0),即开始时处于状,态,1,。按照上面的公式，我们依次递推解出,，以及 。解法如下：,1.,当,t=1,时：,60,例（续）,2.,当,t=2,时：,3.,当,t=3,时：,61,例（续）,4.,当,t=4,时：,62,例（续）,其递推结果为：,可以看出，最有可能的状态序列是：,S1,，,S2,，,S2,，,S2.,63,例（续）,其计算结果示意图如下所示：,绿色的箭头表示最有可能的状态序列,64,问题,3,学习问题,也称训练问题、参数估计问题,化准则，使得观察序列的概率,P(O|,),最大。,65,状态序列已知情况,可以由最大似然估计来估计,HMM,的参数：,66,EM(Expectation-Maximization),算法,由于,HMM,中的状态序列是观察不到的（隐变量），以上的最大似然估计不可行。,EM,算法可,用于含有隐变量的统计模型的最大似然估计。,EM,算法是一个由交替进行的,“,期望,(E,过程,),”,和,“,极大似然估计,(M,过程,),”,两部分组成的迭代过程：,对于给定的不完全数据和当前的参数值，“,E,过程”从条件期望中相 应地构造完全数据的似然函数值，“,M,过程”则利用参数的充分统计,量，重新估计概率模型的参数，使得训练数据的对数似然最大。,EM,算法的每一次迭代过程必定单调地增加训练数据的对数似然值，于是迭代过程渐进地收敛于一个局部最优值。,67,向前向后算法,(Baum-Welch,算法,),1.,初始化：随机地给,i,，,a,ij,，,bjk,赋值（满足概率条件），得到模型,0,，设,i=0,；,2.EM,步骤：,E,步骤：由,i,根据公式（,1,）和（,2,），计算期望值,t,（,i,，,j,）和,t,（,i,）；,M,步骤：用,E,步骤所得的期望值，根据公式（,3,）重新估计,i,，,a,ij,，,bjk,，得到模型,i+1,;,3.,循环设计：,i=i+1,；重复,EM,步骤，直至,i,，,a,ij,，,bjk,值收敛。,68,期望值,(1),给定,HMM,和观察序列，,t,（,i,，,j,）为在时间,t,位于状态,i,，时间,t+1,位于状态,j,的概率：,69,图示,70,期望值,(2),给定,HMM,和观测序列，在时间,t,位于状态,i,的概率：,71,重估公式,(3),72,HMM,的应用,语音识别,音字转换,词性标注（,POS Tagging）,基因识别问题,状态,:,编码区域与非编码区域,字符,:ATCG,一般化：任何与线性序列相关的现象,73,HMM,的一些实际问题,初始概率分布的选择,1.,随机选择,2.,利用先验信息,3.,来自多序列比对的结果,74,HMM,的一些实际问题（续）,数值计算中的防溢出处理,在前向算法、,Viterbi,算法以及,Baum-Welch,算法中，概率值的连续乘法运算很容易导致下溢现象。,解决办法：,1.,前向算法中：每一个时间步的运算中都乘以一 个比例因子,2.Viterbi,算法中：对概率值取对数后计算,75,Viterbi,算法,:,连乘积,对数求和,前向算法,:,引入比例因子,其中,比例因子,76,HMM,总结,HMM,模型可以看作一种特定的,Bayes Net,HMM,模型等价于概率正规语法或概率有限状态自动机,HMM,模型可以用一种特定的神经网络模型来模拟,优点：研究透彻，算法成熟，效率高，效果好，易于训练,77,