隐马尔可夫模型_刘秉权.pdf

《隐马尔可夫模型_刘秉权.pdf》由会员分享，可在线阅读，更多相关《隐马尔可夫模型_刘秉权.pdf（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、隐马尔可夫模型隐马尔可夫模型刘秉权哈工大智能技术与自然语言处理研究室2006年11月隐马尔可夫模型2主要内容?马尔可夫模型?隐马尔可夫模型?隐马尔可夫模型的三个基本问题?隐马尔可夫模型的基本算法?隐马尔可夫模型的应用隐马尔可夫模型3马尔可夫链一个系统有N个状态NSSS,21L，随着时间推移，系统从某一状态转移到另一状态，设tq为时间t的状态，系统在时间t处于状态jS的概率取决于其在时间1-t,1,2,L的状态，该概率为：),Sq,Sq|SP(qk2-ti1-tjtL=如果系统在t时间的状态只与其在时间1t的状态相关，则该系统构成一个离散的一阶马尔可夫链(马尔可夫过程)：)Sq|SP(q),Sq

2、,Sq|SP(qi1-tjtk2-ti1-tjt=L隐马尔可夫模型4马尔可夫模型(Markov Model)如果只考虑独立于时间t的随机过程：ji,i1-tjta)Sq|SP(q=,Nji,1 其中状态转移概率ji,a必须满足0aji,且1aN1jji,=，则该随机过程称为马尔可夫模型。隐马尔可夫模型5马尔可夫模型可视为随机有限状态自动机?该有限状态自动机的每一个状态转换都有一相应概率，表示自动机采用这一状态转换的可能性隐马尔可夫模型6例假定一段时间内的气象可由一三状态马尔可夫模型M描述：1S：雨，2S：多云，3S：晴，转移概率矩阵为：8.01.01.02.06.02.03.03.04.0=i

3、jaA 隐马尔可夫模型7例（续）如果第一天为晴天，根据这一模型，在今后七天中天气为晴晴雨雨晴云晴=O的概率为：4233213113133332332131131333333231133310536.1)2.0)(1.0)(3.0)(4.0)(1.0)(8.0)(8.0(1)|()|()|()|()|()|()|()()|,()|(=aaaaaaaSSPSSPSSPSSPSSPSSPSSPSPMSSSSSSSSPMOP隐马尔可夫模型8隐马尔可夫模型(Hidden Markov Model,HMM)?在MM中，每一个状态代表一个可观察的事件?在HMM中观察到的事件是状态的随机函数，因此该模型是一双

4、重随机过程，其中状态转移过程是不可观察（隐蔽）的(马尔可夫链)，而可观察的事件的随机过程是隐蔽的状态转换过程的随机函数(一般随机过程)。隐马尔可夫模型9实例一房间有N只瓮，每只瓮中有M种不同颜色的球。根据某一概率分布随机地选择一个初始瓮，根据不同颜色球的概率分布从中随机取出一个球，并报告球的颜色。然后根据某一概率分布随机地选择另一只瓮，再根据不同颜色球的概率分布从中随机取出一个球，并报告球的颜色，。对房间外的观察者，可观察的过程是不同颜色球的序列，而瓮的序列是不可观察的。这里每只瓮对应 HMM 模型中的状态，球的颜色对应于状态的输出符号，从一只瓮转向另一只瓮对应于状态转换，从一只瓮中取球对应于

5、从一状态输出观察符号。隐马尔可夫模型10实例（续）Observed Ball Observed Ball SequenceUrn 3SequenceUrn 3Urn 1Urn 2VeilUrn 1Urn 2Veil隐马尔可夫模型11实验中的几个要点?不能直接观察瓮间的转移?从瓮中所选取的球的颜色和瓮并不是一一对应的?每次选取哪个瓮由一组转移概率决定隐马尔可夫模型12HMM的组成五元组：),(BAMN=简记为：),(BA=N：状态数目 M：可能的观察值数目 A：与时间无关的状态转移概率矩阵 B：给定状态下，观察值概率分布：初始状态空间的概率分布 隐马尔可夫模型13状态转移概率矩阵ijaA=)|(

6、1itjtijSqSqPa=，Nji,1 0ija，11=Njija 隐马尔可夫模型14观察值概率分布矩阵从状态jS观察到符号kv的概率分布矩阵：)(kbBj=)|()(jtktjSqvOPkb=，Nj 1，Mk 1 0)(kbj，1)(1=Mkjkb 隐马尔可夫模型15初始状态概率分布i=)(1iiSqP=，Ni 1 0i，11=Nii 隐马尔可夫模型16观察序列产生步骤给定模型),(BA=，观察序列TOOOO,21L=可由以下步骤产生：1.根据初始状态概率分布i=选择一初始状态iSq=1；2.设1=t；3.根据状态iS的输出概率分布)(kbj，输出ktvO=；4.根据状态转移概率分布ija

7、，转移到新状态jtSq=+1；5.设1+=tt，如果Tt，重复步骤 3、4，否则结束。隐马尔可夫模型17HMM中的三个基本问题问题 1：给定观察序列TOOOO,21L=，以及模型),(BA=，如何计算)|(OP？问题 2：给定观察序列TOOOO,21L=及模型),(BA=，如何选择一个对应的状态序列TqqqS,21L=，使得S能够最为合理地解释观察序列O？问题 3：如何调整模型参数),(BA=，使得)|(OP最大？隐马尔可夫模型18解决问题1直接计算：=QQQOPQPQOPOP),|()|()|,()|(其中：TOOOO,21L=，TqqqQ,21L=TTqqqqqqqaaaQP132211)

8、|(=L)()()(),|(2121TqqqObObObQOPTL=困难：穷尽所有可能的状态序列，复杂度)(TNO，指数爆炸。有效方法：向前算法，动态规划，复杂性)(2TNO。隐马尔可夫模型19动态规划(Dynamic Programming)?也称为动态时间弯曲(Dynamic Time-Wraping)?常用于有序数字的最优求解问题，例如无向图中两点之间的最短距离问题或者语料库对齐中基于长度的对齐都采用了动态规划算法。隐马尔可夫模型20HMM的网格结构隐马尔可夫模型21向前算法思想：高效递归地计算向前变量，以求得最终结果 向前变量：)|,()(21itttSqOOOPi=L，Tt 1 算法

9、：1.出始化：)()(11Obiii=，Ni 1 2.递归：)()()(111+=+=tjNiijttObaij，11Tt,Nj 1 3.终结：=NiTiOP1)()|(隐马尔可夫模型22向前变量图示S1 S2 S3 Sj :SN t t+1)(it )(1jt+向前变量：)()()(111+=+=tjNiijttObaij 隐马尔可夫模型23向后算法思想：与向前算法类似，可用于解决问题1,3 向后变量：)|,()(21itTtttSqOOOPi=+L，11Tt算法：1.出始化：1)(=iT，Ni 1 2.递归：=+=NjttjijtjObai111)()()(，NiTt1,11 3.终结：=

10、NiiOP11)()|(隐马尔可夫模型24向后变量图示 S1 S2 Si S3 :SN t t+1)(it )(1jt+向前变量：=+=NjttjijtjObai111)()()(隐马尔可夫模型25解决问题2：Viterbi算法目标：给定一个观察序列和 HMM 模型，如何有效选择“最优”状态序列，以“最好地解释”观察序列？“最优”概率最大：),|(maxarg*OQPQQ=思想：利用动态规划求解，复杂性)(2TNO Viterbi 变量：)|,(max)(2121,121titqqqtOOOSqqqPitLLL=递归关系：)()(max)(11+=tiijtjtObaji 记忆变量：)(it纪

11、录概率最大路径上当前状态的前一个状态 隐马尔可夫模型26Viterbi算法初始化：)()(11Obiii=，0)(1=i，Ni 1 递归：)()(max)(11tjijtNitObaij=，NjTt1,2)()(maxarg)(11tjijtNitObaij=，NjTt1,2终结：)(max1*ipTNi=，)(maxarg1*iqTNiT=路径回溯：)(*11*+=tttqq，1,.,2,1=TTt 隐马尔可夫模型27解决问题3：HMM参数估计给定观察序列TOOOO,21L=作为训练数据，参数估计的目的是估计模型中的i，ija，)(kbj，使得观察序列O的概率)|(OP最大。隐马尔可夫模型2

12、8状态序列已知情况可以由最大似然估计来估计 HMM 的参数：),(1iiSq=+=1-T1it1-T1j1tit)S,(q)S,(q)S,(q)(ttiijiijqqQqqQa的次数本身包括转移到另一状态中从状态的次数转移到中从状态=T1jtT1ktjt)S,(q)v,(O)S,(q)(ttjkjjqQvqQkb的次数到达的次数输出中由状态 其中，=yxyxyx，01),(隐马尔可夫模型29EM(Expectation-Maximization)算法?由于HMM中的状态序列是观察不到的（隐变量），以上的最大似然估计不可行。EM算法可用于含有隐变量的统计模型的最大似然估计。?EM算法是一个由交替

13、进行的“期望(E过程)”和“极大似然估计(M过程)”两部分组成的迭代过程：?对于给定的不完全数据和当前的参数值，“E过程”从条件期望中相应地构造完全数据的似然函数值，“M过程”则利用参数的充分统计量，重新估计概率模型的参数，使得训练数据的对数似然最大。?EM算法的每一次迭代过程必定单调地增加训练数据的对数似然值，于是迭代过程渐进地收敛于一个局部最优值。隐马尔可夫模型30向前向后算法(Baum-Welch算法)1.初始化：随机地给i，ija，)(kbj赋值（满足概率条件），得到模型0，设0=i。2.EM 步骤：E 步骤：由i根据公式（1）和（2），计算期望值),(jit和)(it。M 步骤：用

14、E 步骤所得的期望值，根据公式（3）重新估计i，ija，)(kbj，得到模型1+i。3.循环设计：1+=ii；重复 EM 步骤，直至i，ija，)(kbj值收敛。隐马尔可夫模型31期望值(1)给定 HMM 和观察序列，在时间t位于状态i，时间1+t位于状态j的概率：=+=NiNjttjijtttjijtttjijtjtitjtittjObaijObaiOPjObaiOPOSqSqPOSqSqPji1111111111)()()()()()()|()()()()|()|,(),|,(),(隐马尔可夫模型32图示隐马尔可夫模型33期望值(2)给定 HMM 和观测序列，在时间t位于状态i的概率：=N

15、jttjii1),()(隐马尔可夫模型34重估公式(3)(S1i1iqi=的概率为=1-T1t1-T1t(i)j)(i,)(ttiijiijqqQqqQa的期望次数本身包括转移到另一状态中从状态的期望次数转移到中从状态=T1T1kt(j)v,(O(j)(ttttjkjjqQvqQkb的期望次数到达的期望次数输出中由状态 隐马尔可夫模型35HMM的应用领域?语音识别?语言处理?机器视觉?人脸检测?机器人足球?图像处理?图像去噪?图像识别?生物医学分析?DNA/蛋白质序列分析隐马尔可夫模型36在NLP中的应用?词性标注(POS Tagging)?基于类的N-gram模型?线性插值HMM语言模型?谢谢！