第3讲隐马尔可夫模型及其应用ppt课件

.,隐Markov模型及其NLP应用,网络智能信息技术研究所孙越恒,.,主要内容,Markov模型,1,隐Markov模型(HMM),2,隐Markov模型的三个基本问题及其算法,3,4,隐Markov模型的应用,5,隐Markov模型总结,.,一、Markov模型（1）,现实生活中的例子传染病感染人数变化的过程人口增长的过程青蛙在荷叶上跳跃,这些随机过程都可视为Markov过程！,.,一个系统有N个状态S1，S2，SN，随着时间推移，系统从某一状态转移到另一状态，设qt为时间t的状态，系统在时间t处于状态Sj的概率取决于其在时间1，2，t-1的状态，该概率为：如果系统在t时间的状态只与其在时间t-1的状态相关，则该系统构成一个一阶Markov过程：,Markov模型（2）,公式1.1,公式1.2,.,如果只考虑独立于时间t的随机过程：称为状态转移概率，必须满足,且,则该随机过程称为Markov模型。,Markov模型（3）,公式1.3,.,Markov模型（4）,Markov模型的实质,Markov模型可视为随机有限状态自动机，该有限状态自动机的每一个状态转换过程都有一个相应的概率，表示自动机采用这一状态转换的可能性。,表示成状态图的Markov链=转移弧上有概率的非确定的有限状态自动机,.,二、隐Markov模型（1）,放有彩色球的罐子，每个罐子都有编号，随机地从罐子中摸出彩球,可观察序列,猜测隐藏在幕后的罐子序列,罐子模型,.,隐Markov模型（2）,双重的随机过程,状态的转移过程是隐蔽的，而可观察符号的输出过程是状态转移过程的随机函数。,罐子模型,.,q1,.,o1,.,观察序列O,状态序列Q,HMM,隐Markov模型（3）,q2,q3,q4,qT,o2,o3,o4,oT,罐子模型,.,隐Markov模型（4）,隐Markov模型的形式化描述,1.状态集合：，以qt表示模型在t时刻的状态；2.输出符号集合：3.状态转移矩阵：A=aij（aij是从状态Si转移到状态Sj的概率），其中：,以不同编号表示的不同罐子,不同颜色的球,罐子之间互相转移的概率,形式化描述,.,隐Markov模型（5）,4.可观察符号的概率分布矩阵：B=bj(k)，表示在状态j时输出符号vk的概率，其中：5.初始状态概率分布：,从某个罐子取出某种颜色球的概率,在初始时刻选择不同罐子的概率,一般的，一个HMM可以表示为(S,O,A,B,)或(A,B,),形式化描述,.,三、隐Markov模型的三个基本问题及其算法（1）,隐Markov模型涉及如下三个基本问题,评估问题：给定一个观察序列和模型，如何计算给定模型下观察序列O的概率P(O|)。,1,解码问题：给定一个观察序列和模型，如何计算状态序列，使得该状态序列能“最好地解释”观察序列。,2,学习问题：给定一个观察序列，如何调节模型的参数，使得P(O|)最大。,3,.,隐Markov模型的三个基本问题及其算法（2）,问题1：评估问题解决之道：前向算法、后向算法、前向-后向算法前向算法前向变量：HMM在时间t输出序列O1Ot，并且位于状态i的概率：则有：,公式3.1,公式3.2,评估问题,.,前向算法：1.初始化：2.递归：3.终止：,隐Markov模型的三个基本问题及其算法（3）,评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,初始化1(i)=ibi(O1),评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,2.递归,评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,评估问题,.,前向算法过程演示i=N,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=N-1i=5i=4i=3i=2i=1,评估问题,.,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=Ni=N-1i=5i=4i=3i=2i=1,评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,评估问题,.,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,i=Ni=N-1i=5i=4i=3i=2i=1,3.计算P(O|),评估问题,.,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,评估问题,.,评估问题,后向算法与向前算法类似：定义向后变量初始化：递归：终结：,隐Markov模型的三个基本问题及其算法（4）,.,隐Markov模型的三个基本问题及其算法（5）,问题2：解码问题,给定一个观察序列和模型，如何计算状态序列，使得该状态序列能“最好地解释”观察序列。,所求的Q应当在某个准则下是“最优”的,因此也称Q为最优路径,解码问题即是确定最优路径的问题。,该问题可形式化为：,公式3.3,解码问题,.,隐Markov模型的三个基本问题及其算法（6）,假定有N个词性标记，给定词串中有M个词考虑最坏的情况：每个词都有N个可能的词性标记，则可能的状态序列有NM个随着M（词串长度）的增加，需要计算的可能路径数目以指数方式增长，需要寻找更有效的算法,效率问题,解码问题,词性是状态，词语是观察符号,.,隐Markov模型的三个基本问题及其算法（7）,Viterbi算法：基于Viterbi变量的动态规划算法,Viterbi变量：在时间t沿状态序列q1q2.qt且qt=Si而产生出O1O2Ot的最大概率，即：,公式3.4,Viterbi变量说明的是，从初始状态到t时刻的状态Si的所有路径中，必有一条路径，能够使得你观察到O1O2Ot序列的概率最大，也即这条路径最好的解释了O1O2Ot序列的出现。,解码问题,.,隐Markov模型的三个基本问题及其算法（8）,Viterbi算法（续）,初始化：,路径回溯：,终结：,递归：,解码问题,.,隐Markov模型的三个基本问题及其算法（9）,o1,o2,o3,ot-1,ot,oT,.,.,观察序列,1.初始化,2.递推,3.终结,.,4.回溯,.,解码问题,.,假定有N个词性标记，给定词串中有M个词。考虑最坏的情况，扫描到每一个词时，从前一个词的各个词性标记（N个）到当前词的各个词性标记（N个），有NN=N2条路经，即N2次运算，扫描完整个词串（长度为M），计算次数为M个N2相加，即。对于确定的词性标注系统而言，N是确定的，因此，随着M长度的增加，计算时间以线性方式增长。也就是说，Viterbi算法的计算复杂度是线性的。,Viterbi算法的复杂度分析,隐Markov模型的三个基本问题及其算法（10）,解码问题,.,隐Markov模型的三个基本问题及其算法（11）,问题三：学习问题给定一个观察序列O1O2OT，如何调节模型的参数，使得P(O|)最大。也称训练问题、参数估计问题,学习问题,.,如果产生观察序列O的状态Q=q1q2qT已知，可以用最大似然估计来计算HMM的参数：,其中，(x,y)为克罗奈克(Kronecker)函数，当x=y时,(x,y)=1,否则(x,y)=0。,隐Markov模型的三个基本问题及其算法（12）,公式3.5,公式3.6,学习问题,.,其中，vk是模型输出符号集中的第k个符号。,类似地，,隐Markov模型的三个基本问题及其算法（13）,公式3.7,学习问题,.,期望值最大化算法(Expectation-Maximization,EM)基本思想：,隐Markov模型的三个基本问题及其算法（14）,(1)初始化时随机地给模型的参数赋值(遵循限制规则，如：从某一状态出发的转移概率总和为1)，得到模型0;(2)从0得到从某一状态转移到另一状态的期望次数，然后以期望次数代替公式中的次数，得到模型参数的新估计，由此得到新的模型1;(3)从1又可得到模型中隐变量的期望值，由此重新估计模型参数。循环这一过程，参数收敛于最大似然估计值。,学习问题,.,给定HMM模型和观察序列OO1O2OT，那么，在时间t位于状态Si，时间t+1位于状态Sj的概率：,隐Markov模型的三个基本问题及其算法（15）,公式3.8,学习问题,.,t(i)t(i,j),那么，给定模型和观察序列OO1O2OT，在时间t位于状态Si的概率为：,Nj1,由此，模型的参数可由下面的公式重新估计：(1)q1为Si的概率：,i1(i),公式3.9,公式3.10,隐Markov模型的三个基本问题及其算法（16）,学习问题,.,(3)可观察符号的输出概率：,(2)转移概率：,公式3.11,公式3.12,隐Markov模型的三个基本问题及其算法（17）,学习问题,.,a,b(k)1,Baum-Welch算法(前向后向算法):(1)初始化：随机地给i,aij,bj(k)赋值，,使得,1,Ni1,i,ij,1,1iN,Nj1,i,1iN,由此得到模型0，令m=0。,Mk1,隐Markov模型的三个基本问题及其算法（18）,学习问题,.,(2)执行EM算法：E-步：由模型m根据公式(3.8)和(3.9)计算期望值t(i,j)和t(i)M-步：用E-步中得到的期望值，根据公式(3.10-3.12)重新估计i,aij,bj(k)，得到模型m+1循环：m=m+1，重复执行E-步和M-步，直至i,aij,bj(k)的值收敛：|logP(O|m1)logP(O|m)|(3)结束算法，获得相应的参数,隐Markov模型的三个基本问题及其算法（19）,学习问题,.,四、隐Markov模型的应用（1）,隐Markov模型具有广泛的应用，如：,自然语言处理：中文分词、词性标注、音字转换、语音识别、机器翻译,1,2,行为识别、手写字符识别,3,生物信息学：基因组分析,一般化：任何与线性序列相关的问题！,.,隐Markov模型的应用（2）,以词性标注为例：,词性标注,把,这,篇,报道,编辑,一,下,有多少种可能性？哪种可能性最大？,.,隐Markov模型的应用（3）,我们看到的是词汇序列，记做W=w1w2wn（即观察符号序列）。需要去猜测隐藏在幕后的词性标记序列，记做Tt1t2tn（即状态序列）问题抽象：已知词串W（观察序列）和模型的情况下，求使得条件概率P(T|W,)值最大的那个T,一般记做：,公式4.1,词性标注,.,隐Markov模型的应用（4）,根据贝叶斯定理，公式4.1可转换为：,公式4.2,公式4.2的分母可视为常数，因为是求最大值，由4.2得到：,公式4.3,其中：,公式4.4,词性之间的转移概率可以从语料库中估算得到：,公式4.5,词性标注,.,隐Markov模型的应用（5）,公式4.6,公式4.7,词性标注,.,隐Markov模型的应用（6）,表1词性转移矩阵,词性标注,.,隐Markov模型的应用（7）,表2词性频次表,词性标注,由表1和表2得出词性的转移概率P(ti|ti-1),.,隐Markov模型的应用（8）,表3词语/词性频次表,词性标注,由表2和表3得出在不同词性下的词语输出概率P(wi|ti),.,隐Markov模型的应用（9）,词性标注,把,这,篇,报道,编辑,一,下,.,五、隐Markov模