第3讲隐马尔可夫模型及其应用5.pptx

隐Markov模型及其NLP应用主要内容一、Markov模型（1）一个系统有N个状态S1S2···SN随着时间推移系统从某一状态转移到另一状态设qt为时间t的状态系统在时间t处于状态Sj的概率取决于其在时间12···t-1的状态该概率为：如果系统在t时间的状态只与其在时间t-1的状态相关则该系统构成一个一阶Markov过程：如果只考虑独立于时间t的随机过程：称为状态转移概率必须满足且则该随机过程称为Markov模型。Markov模型（4）二、隐Markov模型（1）隐Markov模型（2）q1隐Markov模型（4）隐Markov模型（5）三、隐Markov模型的三个基本问题及其算法（1）隐Markov模型的三个基本问题及其算法（2）前向算法：1.初始化：2.递归：3.终止：t=1t=1t=1t=1t=1t=1t=1t=1t=1前向算法过程演示i=N前向算法过程演示t=1t=1t=1前向算法过程演示t=1评估问题隐Markov模型的三个基本问题及其算法（5）隐Markov模型的三个基本问题及其算法（6）隐Markov模型的三个基本问题及其算法（7）隐Markov模型的三个基本问题及其算法（8）隐Markov模型的三个基本问题及其算法（9）假定有N个词性标记给定词串中有M个词。考虑最坏的情况扫描到每一个词时从前一个词的各个词性标记（N个）到当前词的各个词性标记（N个）有N×N=N2条路经即N2次运算扫描完整个词串（长度为M）计算次数为M个N2相加即。对于确定的词性标注系统而言N是确定的因此随着M长度的增加计算时间以线性方式增长。也就是说Viterbi算法的计算复杂度是线性的。隐Markov模型的三个基本问题及其算法（11）如果产生观察序列O的状态Q=q1q2…qT已知可以用最大似然估计来计算HMM的参数：其中vk是模型输出符号集中的第k个符号。期望值最大化算法(Expectation-MaximizationEM)基本思想：给定HMM模型和观察序列OO1O2…OT那么在时间t位于状态Si时间t+1位于状态Sj的概率：t(i)t(ij)(3)可观察符号的输出概率：(2)执行EM算法：E-步：由模型m根据公式(3.8)和(3.9)计算期望值t(ij)和t(i)M-步：用E-步中得到的期望值根据公式(3.10-3.12)重新估计iaijbj(k)得到模型m+1循环：m=m+1重复执行E-步和M-步直至iaijbj(k)的值收敛：|logP(O|m1)logP(O|m)|(3)结束算法获得相应的参数四、隐Markov模型的应用（1）隐Markov模型的应用（2）隐Markov模型的应用（3）隐Markov模型的应用（4）隐Markov模型的应用（5）隐Markov模型的应用（6）隐Markov模型的应用（7）隐Markov模型的应用（8）隐Markov模型的应用（9）五、隐Markov模型总结（1）隐Markov模型总结（2）ThankYou!ThankYou!内容总结