宗成庆-统计自然语言处理--第六章----隐马尔可夫模型

LOGO第6章隐马尔可夫模型邮件：[e-mail]参考课件：宗成庆：《自然语言理解》讲义LOGO6.1马尔可夫模型马尔可夫模型马尔可夫模型描述存在一类重要的随机过程：如果一个系统有N个状态S1,S2,…,SN,随着时间的推移，该系统从某一状态转移到另一状态。如果用qt表示系统在时间t的状态变量，那么，t时刻的状态取值为Sj(1jN)的概率取决于前t-1个时刻(1,2,…,t-1)的状态，该概率为：P(qtSj|qt1Si,qt2Sk,…)马尔可夫模型如果在特定情况下，系统在时间t的状态只与其在时间t-1的状态相关，则该系统构成一个离散的一阶马尔可夫链：P(qtSj|qt1Si,qt2Sk,…)P(qtSj|qt1Si)…(6.1)假设马尔可夫模型假设：如果只考虑公式(6.1)独立于时间t的随机过程，即所谓的不动性假设，状态与时间无关，那么：P(qtSj|qt1Si)aij,1i,jN…(6.2)该随机过程称为马尔可夫模型(MarkovModel)。a6.1马尔可夫模型在马尔可夫模型中，状态转移概率aij必须满足下列条件：aij0…(6.3)1ijNj1…(6.4)马尔可夫模型又可视为随机有限状态自动机，该有限状态自动机的每一个状态转换过程都有一个相应的概率，该概率表示自动机采用这一状态转换的可能性。马尔可夫模型马尔可夫链可以表示成状态图（转移弧上有概率的非确定的有限状态自动机）－零概率的转移弧省略。－每个节点上所有发出弧的概率之和等于1。1.0he1.0p00.66i0.41.00.6a00.33t00.440.30.4startP(S1)P(S2|S1)P(S3|S2)…P(ST|ST1)T1t1其中，i=P(q1=Si)，为初始状态的概率。S1aStSt16.1马尔可夫模型状态序列S1,…,ST的概率：P(S1,…,ST)P(S1)P(S2|S1)P(S3|S1,S2)…P(ST|S1,…,ST1)…(6.5)(t,i,p)P(S1t)P(S2i|S1t)P(S3p|S2i)=1.0×0.3×0.6=0.18LOGO6.2隐马尔可夫模型隐马尔可夫模型隐马尔可夫模型(HiddenMarkovModel,,HMM)描写：该模型是一个双重随机过程，我们不知道具体的状态序列，只知道状态转移的概率，即模型的状态转换过程是不可观察的（隐蔽的），而可观察事件的随机过程是隐蔽状态转换过程的随机函数。隐马尔可夫模型例如：N个袋子，每个袋子中有M种不同颜色的球。一实验员根据某一概率分布选择一个袋子，然后根据袋子中不同颜色球的概率分布随机取出一个球，并报告该球的颜色。对局外人：可观察的过程是不同颜色球的序列，而袋子的序列是不可观察的。每只袋子对应HMM中的一个状态；球的颜色对应于HMM中状态的输出。……12N……隐马尔可夫模型HMM的组成11.模型中的状态数为N(袋子的数量)2.从每一个状态可能输出的不同的符号数M(不同颜色球的数目)a6.2隐马尔可夫模型3.状态转移概率矩阵Aaij(aij为实验员从一只袋子(状态Si)转向另一只袋子(状态Sj)取球的概率)。其中,aijP(qt1Sj|qtSi),1i,jNaij0…(6.6)1ijNj1b6.2隐马尔可夫模型4.从状态Sj观察到某一特定符号vk的概率分布矩阵为：B=bj(k)其中，bj(k)为实验员从第j个袋子中取出第k种颜色的球的概率。那么，bj(k)P(Otvk|qtSj),1jN,1kM…((6.7))bj(k)0Mj(k)1k1…(6.8)6.2隐马尔可夫模型5.初始状态的概率分布为：=i，其中，iP(q1Si),1iNi01iNi1,,为了方便，一般将HMM记为：(A,B,)或者(S,OAB,)用以指出模型的参数集合。隐马尔可夫模型给定HMM求观察序列给定模型(A,B,)，产生观察序列O＝O1O2…OT:(1)令t=1;(2)根据初始状态分布i选择初始状态q1Si;(3)根据状态Si的输出概率分布bi(k)),输出Otvk;(4)根据状态转移概率aij，转移到新状态qt1Sj;(5)t=t+1,如果tT,重复步骤(3)(4),否则结束。隐马尔可夫模型HMM中的三个问题(1)在给定模型(A,B,)和观察序列O＝O1O2…OT的情况下，怎样快速计算概率P(O|)？(2)在给定模型(A,B,)和观察序列O＝O1O2…OT的情况下，如何选择在一定意义下“最优”的状态序列Q=q1q2…qT，使得该状态序列“最好地解释”观察序列？隐马尔可夫模型(3)给定一个观察序列OO1O2…OT，如何根据最大似然估计来求模型的参数值？即如何调节模型(A,B,)的参数，使得P(O|)最大？LOGO6.3前向算法前向算法问题1：快速计算观察序列概率P(O|)给定模型(A,B,)和观察序列O=O1O2…OT快速计算P(O|)：对于给定的状态序列Qq1q2…qT…(6.9)…(6.10)…(6.11)P(O|)P(O,Q|)P(Q|)P(O|Q,)QQP(Q|)q1aq1q2aq2q3…aqt1qTP(O|Q,)bq1(O1)bq2(O2)…bqT(OT)•困难：如果模型=(A,B,)有N个不同的状态，时间长度为T，那么有NT个可能的状态序列，搜索SN3T21路径成指数级组合爆炸。Time,t前向算法解决办法：动态规划前向算法(Theforwardprocedure)基本思想：定义前向变量t(i)：t(i)P(O1O2…Ot,qtSi|)…(6.12)如果可以高效地计算t(i)，就可以高效地求得P(O|)。T(i)6.3前向算法因为P(O|)是在到达状态qT时观察到序列O=O1O2…OT的概率(所有可能的概率之和)：P(O|)P(O1O2…OT,qTSi|)SiNi1…(6.13)t1(j)[t(i)aij]bj(Ot1)6.3前向算法动态规划计算t(i)：在时间t+1的前向变量可以根据时间t的前向变量t(1),…,t(N)的值递推计算：Ni1…(6.14)……t(1)1t(2)2S36.3前向算法OtOt+1a2ja3jSjj(t+1)SSt(3)SNt(N)tt(i)t+1t+1(j)…t1(j)[t(i)aij]bj(Ot1),P(O|)i1T(i)6.3前向算法算法6.1:前向算法(1)初始化：1(i)ibi(O1),1iN(2)循环计算：1tT1Ni1(3)结束，输出：N前向算法算法的时间复杂性：每计算一个t(i)必须考虑从t-1时的所有N个状态转移到状态Si的可能性，时间复杂性为O(N)，对应每个时刻t，要计算N个前向变量：t(1),t(2),…,t(N)，所以，时间复杂性为：O(N)×N=O(N2)。又因t=1,2,…,T，所以前向算法总的复杂性为：O(N2T)。LOGO6.4后向算法后向算法后向算法(Thebackwardprocedure)定义后向变量t(i)是在给定了模型(A,B,)和假定在时间t状态为Si的条件下，模型输出观察序列Ot1Ot2…OT的概率：t(i)P(Ot1Ot2…OT|qtSi,)…(6.15)后向算法与前向变量一样，运用动态规划计算后向量：(1)从时刻t到t+1，模型由状态Si转移到状态Sj，并从Sj输出Ot+1；(2)在时间t+1，状态为Sj的条件下，模型输出观察序列Ot1Ot2…OT。t(i)aijbj(Ot1)t1(j)6.4后向算法第一步的概率：aijbj(Ot1)第二步的概率按后向变量的定义为：t1(j)于是，有归纳关系：…(6.16)Nj1归纳顺序：T(x),T1(x),…,1(x)(x为HMM的状态)……6.4后向算法算法的图形解释：OtOt+1S1S2S3St…SNt+1t1(j)tt(i)t(i)aijbj(Ot1)t1(j),6.4后向算法算法6.2：后向算法(1)初始化：T(i)1,1iN(2)循环计算：T1t1,1iNNj1(2)输出结果：算法的时间复杂性：O(N2T)LOGO6.5Viterbi搜索算法搜索算法问题2－如何发现“最优”状态序列能够“最好地解释”观察序列解释不是唯一的，关键在于如何理解“最优”的状态序列？一种解释是：状态序列中的每个状态都单独地具有概率，即：对于每个时刻t(1tT)，寻找qt使得t(i)P(qtSi|O,)最大。(qtSi,O|)P(O|)t(i)P(qtSi|O,)…(6.17)HMM的输出序列O，并且在时间t到达状态i的概率。6.5Viterbi搜索算法分解过程：(1)HMM在时间t到达状态i,并且输出OO1O2…Ot。根据前向变量的定义，实现这一步的概率为t(i)。(2)从时间t，状态Si出发，HMM输