蔡海滨中山大学信息科学与技术的学院

蔡海滨 中山大学信息科学与技术学院,隐马尔可夫模型 Hidden Markov model,目录,HMM简介 马尔可夫（Markov）链 HMM的基本定义 HMM的三个基本问题及其算法,HMM简介,HMM（Hidden Markov Model隐马尔可夫模型）是一种用参数表示的用于描述随机过程统计特性的概率模型，是一个双重随机过程，由两部分组成：马尔可夫链和一般随机过程。其中马尔可夫链用来描述状态的转移，用转移概率描述。一般随机过程用来描述状态与观察序列间的关系，用观察值概率来描述。 对HMM模型，其转换过程是不可观察的，因而称之为“隐”马尔可夫模型,HMM的应用领域,HMM作为语音信号的一种统计模型，今天正在语言处理各个领域中获得广泛的应用。除此之外，HMM还可以应用于： 生物计算 计算机视觉 生物测定学（Biometrics） 手势识别 其他更多的领域,Markov链,如果一个过程的“将来”仅依赖“现在”而不依 赖“过去”，则此过程具有马尔可夫性,或称此 过程为马尔可夫过程 马尔可夫链是时间和状态参数都离散的马尔 可夫过程,Markov链的数学定义,随机序列Xn ,在任一时刻n，它可以处在状态S1,S2,SN,且它在m+k时刻所处的状态为qm+k的概率，只与它在m时刻的状态qm有关，而与m时刻以前它所处状态无关，即有： P(Xm+k=qm+k|Xm=qm,Xm-1=qm-1,X1=q1) =P(Xm+k=qm+k|Xm=qm) 则称Xn 为Markov链.,K步转移概率： Pij(m,m+k)=P(qm+k=Sj|qm=Si) 当Pij与m无关时，即Pij (m,m+k)=Pij(k)此 时这个Markov链称为齐次markov链。 当k=1时，Pij称为一步转移概率，简称转移 概率,阴天,下雨,晴天,转移概率矩阵,晴天 阴天 下雨 晴天 0.50 0.25 0.25 阴天 0.375 0.25 0.375 下雨 0.25 0.125 0.625,转移概率可以表示成一个转移概率矩阵,转移概率矩阵,其中，aij=Pij(1),初始概率矢量,概率转移矩阵还不足以描述一个markov链， 因此还需要引入一个初始概率矢量。,其中，,HMM的基本定义,HMM是在Markov链的基础上发展起来的。由于实际问题比Markov链模型所描述的更为复杂，观察到的时间并不是与状态一一对应的，而是通过一组概率分布相联系，这样的模型称为HMM。它是双重随机过程，其中之一是Markov链，这是基本随机过程，它描述状态的转移。另一个随机过程描述状态和观察值之间的统计对应关系。,这样，站在观察者的角度，只能看到观察值，不像Markov链模型中观察值和状态一一对应，因此，不能直接看到状态，而是通过一个随机过程去感知状态的存在及其特性。因而称之为“隐”Markov模型，即HMM。 通过“球和缸”实验，可以更好的理解HMM,球和缸实验,Observed Ball Sequence,球和缸实验的描述,设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下 根据初始概率分布，随机选择N个缸中的一个开始实验 根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为O1，并把球放回缸中 根据描述缸的转移的概率分布，随机选择下一口缸，重复以上步骤。 最后得到一个描述球的颜色的序列O1,O2,，称为观察值序列O。,HMM的定义,HMM可由如下五个元素定义： 状态的集合 观察值集合 初始概率矢量 状态转移矩阵 状态i观察的概率分布 以下将一一介绍,状态的集合,X代表一组状态的集合，其中 X=S1,S2,SN 状态数为N，并用qt表示t时刻的状态。虽然状态是隐藏的，但对于很多应用来说，有一些物理的意义和状态或者状态集相关，状态内部的联系就是一个状态可以到达其他状态,观察值的集合,O代表一组可观察符号的集合 O=V1,V2,vM M是从每一状态可能输出的不同观察值的数目,初始概率矢量,初始化状态分布 表示初始模型时，每一状态可取的概率,状态转移概率分布,状态转移概率分布A=aij,这里 aij=Pqt+1=Sj | qt=si 特殊情况下，每个状态都可以一步达到其他任何状态，这时对任意（i，j） ，有aij0。对于其他的HMM，可能aij=0（对于一对或多对i，j）,状态i观察概率分布,令B=bj(k),表示状态j输出相应观察值的概率，其中 bj(k)=P(Ot=Vk|qt=Sj), j:1,N,k:1:M,由以上可知，一个HMM可以表示成一个五元组U U=X,O, ,A,B 或简写成 U= ,A,B 上面所述HMM的三个关键元素实际可以分成两部分，其一为Markov链，由 和A描述，另一部分是一个随机过程，由B描述,HMM的三个基本问题及其算法,评估问题 解码问题 学习问题,评估问题,给定观察序列O=O1O2OT和模型U=(A,B, )计算P(O|U)。即给定模型和输出观察序列，如何计算从模型生成观察序列的概率。可以把它看作是评估一个模型和给定观察序列的匹配程度，由此可以用来在一些列候选对象中选取最佳匹配。,解决评估问题的两个算法,前向(forward)算法 后向(backward)算法,前向算法,如果希望计算给定模型参数情况下输出序列O=O1O2 OT的出现概率P(O|U),通常采用前向(后向)算法。其复杂度为O(K2L) 观察状态序列Q：Q=q1q2qT,其中q1表示初始状态在 状态序列出现的情况下观察序列O的概率。 定义前向变量： at(i)=P(O1O2Ot,qt=Si|U) 表示在给定的模型下，到时间t时输出观察序列为O1O2 Ot，并且时刻t的状态是Si的概率,前向算法流程,1) 初始化 F1(i)= bi(O1),1=i=N 2) 递推 Ft+1(j)=i=1toNFt(i)*aij*bj(Ot+1) 1=t=T-1,1=j=N 3) 终止 P(O|U)= i=1toNFT(i),后向算法,后向算法与前向算法性质是一样的，只是递推 的方向不同。定义后向变量： Ht(i)=P(Ot+1Ot+2OT|qt=Si,U) 表示给定模型参数，当时刻t状态为Si的时候， 从t+1到序列结束的输出观察序列为Ot+1Ot+2 OT的概率,后向算法流程,1) 初始化 HT(i)=1 1=i=N 2) 递推 Ht(j)= i=1toNaji*bi(Ot+1)*Ht+1(i) 1=j=N 3) 终止 P(O|U)= j=1toN *bj(O1) *H1(j),解码问题,给定观察序列O=O1O2OT和模型U=(A,B, ) 求在某种有意义的情况下最优的相关状态序列 Q=q1q2qT。这可以理解为对输出观察的最 佳“解释”，它试图揭示模型的隐藏部分，比如 说查找“正确”的状态序列，在应用中，通常都 使用一个优化策略来最大可能的解决这个问题。,Viterbi算法,Viterbi算法采用动态规划算法。算法复杂度 为O(K2L)。其中K和L分别为状态个数和序列长 度。定义 Wt(i)=maxPq1q2,qt=I,O1,O2,Ot,|U 我们所要找的，就是T时刻最大的WT(i)所代表 的状态序列。,Viterbi算法流程,初始化 W1(i)= bi(O1),1=i=N R1(i)=0, 1=i=N 递归 Wt(j)=max1=i=NWt-1(i)aijbj(Oi) Rt(j)=arg max1=i=NWt-1(i)aij 终结 P*=max1=i=NWT(i) qT*=arg max1=i=NWT(i) 求s序列 qt*=Rt+1(qt+1*),t=T-1,T-2,1,学习问题,如何调整模型参数U=(A,B, ),对于一个给定序 列O=O1O2OT，使得P(O|U)最大。它试图 优化模型的参数来最佳的描述一个给定的观察 序列是如何得来的。,Baum-Welch估计算法,到目前为止，对于隐马尔可夫模型的参数选 择和优化问题，目前使用较广的处理方法是 Baum-Welch估计算法。该算法是一种迭代算 法，初始时刻由用户给出各参数的经验估计值 ，通过不断迭代，使各个参数趋向更合理的较 优值。,Baum-Welch估计算法流程,初始化 =r1(i) 当t=1时处于Si的期望值，U=(A0,B0, ) 迭代计算 令 表示t时刻状态为Si以及t+1时刻状态为Sj的概率,t时刻处于状态Si的概率,整个过程中从状态Si转出的次数的预期,从Si跳转到Sj次数的预期,重估公式,终止条件,The End,