隐隐MarkovMarkov模型及其模型及其NLPNLP应用应用网络智能信息技术研究所网络智能信息技术研究所孙越恒孙越恒主要内容主要内容Markov模型模型1隐隐Markov模型模型(HMM)2隐隐Markov模型模型的三个基本问题及其算法的三个基本问题及其算法34隐隐Markov模型的应用模型的应用5隐隐Markov模型总结模型总结一、Markov模型（1）v现实生活中的例子现实生活中的例子传染病感染人数变化的过程传染病感染人数变化的过程人口增长的过程人口增长的过程青蛙在荷叶上跳跃青蛙在荷叶上跳跃这这些些随随机机过过程程都都可可视视为为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.3Markov模型（4） Markov模型的实质模型的实质Markov模模型型可可视视为为随随机机有有限限状状态态自自动动机机，该该有有限限状状态态自自动动机机的的每每一一个个状状态态转转换换过过程程都都有有一一个个相相应应的的概概率率，表表示示自自动动机机采采用用这这一一状状态转换的可能性。态转换的可能性。表表示示成成状状态态图图的的Markov链链= = 转转移移弧弧上上有有概概率率的的非非确确定的有限状态自动机定的有限状态自动机二、隐Markov模型（1）放有彩色球的罐子，每个罐子都有编号，随机地从罐子中摸出彩球放有彩色球的罐子，每个罐子都有编号，随机地从罐子中摸出彩球可观察序列可观察序列猜测隐藏猜测隐藏在幕后的在幕后的罐子序列罐子序列罐子模型罐子模型隐Markov模型（2）v双重的随机过程双重的随机过程状态转移：从一个罐子转移到另一个罐子1可观察符号的输出：从某个罐子取出某种颜色的球2状状态态的的转转移移过过程程是是隐隐蔽蔽的的，而而可可观观察察符符号号的的输输出出过过程程是是状状态态转转移移过程的随机函数。过程的随机函数。罐子模型罐子模型q1.o1.观察序列观察序列O状态序列状态序列QHMM 隐Markov模型（3）q2q3q4qTo2o3o4oT罐子模型罐子模型隐Markov模型（4）v隐隐Markov模型的形式化描述模型的形式化描述1.1. 状态集合状态集合： ，以qt表示模型在t时刻的状态； 2.2. 输出符号集合输出符号集合： 3. 3. 状态转移矩阵状态转移矩阵：A =aij（aij是从状态Si转移到状态Sj的概率），其中：以不同以不同编号表编号表示的不示的不同罐子同罐子不同颜不同颜色的球色的球罐罐子子之之间间互互相相转转移移的的概率概率形式化描述形式化描述隐Markov模型（5）4. 可观察符号的概率分布矩阵可观察符号的概率分布矩阵：B = bj(k)，表示在状态j时输出符号vk的概率，其中：5. 初始状态概率分布初始状态概率分布：从从某某个个罐罐子子取取出出某某种种颜颜色色球球的概率的概率在在初初始始时时刻刻选选择择不不同同罐罐子子的的概率概率一般的，一个一般的，一个HMM可以表示为可以表示为 (S, O, A, B, )或或(A, B, )形式化描述形式化描述三、隐Markov模型的三个基本问题及其算法（1）v隐Markov模型涉及如下三个基本问题评估问题评估问题：给定一个观察序列 和模型，如何计算给定模型下观察序列O的概率P(O| )。1解码问题解码问题：给定一个观察序列 和模型，如何计算状态序列 ，使得该状态序列能“最好地解释”观察序列。2学学习习问问题题：给定一个观察序列 ，如何调节模型的参数，使得P (O| )最大。3隐Markov模型的三个基本问题及其算法（2）v问题问题1：评估问题：评估问题解决之道：解决之道：前向算法、后向算法、前向前向算法、后向算法、前向-后向算法后向算法v前向算法前向算法 前向变量：HMM在时间 t 输出序列O1Ot，并且位于状态 i 的概率： 则有：公式公式3.1公式公式3.2评估问题评估问题前向算法：前向算法：1.初始化初始化：2.递递归归：3.终终止止： 隐Markov模型的三个基本问题及其算法（3）评估问题评估问题t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=11.初始化初始化1(i)=ibi(O1)评估问题评估问题t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1评估问题评估问题t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1评估问题评估问题t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1评估问题评估问题t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=12. 递归评估问题评估问题t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1评估问题评估问题t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1评估问题评估问题t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1评估问题评估问题t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1评估问题评估问题前向算法过程演示i=Nt=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=N-1i=5i=4i=3i=2i=1评估问题评估问题前向算法过程演示t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=Ni=N-1i=5i=4i=3i=2i=1评估问题评估问题t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1评估问题评估问题t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1评估问题评估问题t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1评估问题评估问题前向算法过程演示t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7i=Ni=N-1i=5i=4i=3i=2i=13. 计算P(O|)评估问题评估问题t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1评估问题评估问题评估问题评估问题后向算法后向算法n与向前算法类似：定义向后变量n初始化：n递归：n终结：隐Markov模型的三个基本问题及其算法（4）隐Markov模型的三个基本问题及其算法（5）v问题问题2：解码问题：解码问题给定一个观察序列 和模型，如何计算状态序列 ，使得该状态序列能“最好地解释”观察序列。所求的所求的Q应当在某个准则下是应当在某个准则下是“最优最优”的的,因此也称因此也称Q 为最优路径为最优路径,解码问题即是确定最优路径的问题。解码问题即是确定最优路径的问题。该问题可形式化为：该问题可形式化为：公式公式3.3解码问题解码问题隐Markov模型的三个基本问题及其算法（6）假定有假定有N个个词性性标记，给定定词串中有串中有M个个词考考虑最坏的情况：每个最坏的情况：每个词都有都有N个可能的个可能的词性性标记，则可能的可能的状状态序列有序列有NM 个个随着随着M（词串串长度）的增加，需要度）的增加，需要计算的可能路径数算的可能路径数目以指数方式增目以指数方式增长，需要需要寻找更有效的算法找更有效的算法效率效率问题解码问题解码问题词性是状性是状态，词语是是观察符号察符号隐Markov模型的三个基本问题及其算法（7）vViterbi算法：算法：基于基于Viterbi变量的动态规划算法变量的动态规划算法Viterbi变量：变量：在时间在时间t 沿状态序列沿状态序列q1q2.qt且且qt=Si而产生出而产生出O1O2Ot的最大概率，即：的最大概率，即：公式公式3.4Viterbi变变量量说说明明的的是是，从从初初始始状状态态到到 t 时时刻刻的的状状态态 Si的的所所有有路路径径中中，必必有有一一条条路路径径，能能够够使使得得你你观观察察到到O1O2Ot序序列列的的概概率率最大，也即这条路径最好的解释了最大，也即这条路径最好的解释了O1O2Ot序列的出现。序列的出现。解码问题解码问题隐Markov模型的三个基本问题及其算法（8）vViterbi算法（续）算法（续）初始化：初始化：路径回溯：路径回溯：终终 结：结：递递 归：归：解码问题解码问题隐Markov模型的三个基本问题及其算法（9）o1o2o3ot-1otoT.观察序列观察序列s1s2s3sNsjsi.sj.1.初始化初始化2. 递推递推3. 终结终结.4.回溯回溯.解码问题解码问题假定有假定有N个个词性性标记，给定定词串中有串中有M个个词。考考虑最坏的情况，最坏的情况，扫描到每一个描到每一个词时，从前一个，从前一个词的各个的各个词性性标记（N个）到当前个）到当前词的各个的各个词性性标记（N个），有个），有NN=N2条路条路经，即，即N2次运算，次运算，扫描完整个描完整个词串（串（长度度为M），），计算算次数次数为M个个N2相加，即相加，即。对于确定的于确定的词性性标注系注系统而言，而言，N是确定的，因此，随着是确定的，因此，随着M长度的增加，度的增加，计算算时间以以线性方式增性方式增长。也就是。也就是说，Viterbi算算法的法的计算复算复杂度是度是线性的。性的。Viterbi算法的复算法的复杂度分析度分析隐Markov模型的三个基本问题及其算法（10）解码问题解码问题隐Markov模型的三个基本问题及其算法（11）v问题三：学习问题问题三：学习问题给定一个观察序列给定一个观察序列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 0 得到从某一状态转移到另一状态的期望次数，然后以期望次数代替公式中的次数，得到模型参数的新估计，由此得到新的模型 1;(3)从 1又可得到模型中隐变量的期望值，由此重新估计模型参数。循环这一过程，参数收敛于最大似然估计值。学习问题学习问题给定 HMM模型 和观察序列 O O1O2 OT ，那么， 在时间 t 位于状态 Si，时间 t+1位于状态 Sj 的概率：隐Markov模型的三个基本问题及其算法（15）公式公式3.8学习问题学习问题t (i) t (i, j)那么，给定模型 和观察序列 O O1O2 OT ，在时间 t 位于状态 Si 的概率为： Nj 1由此，模型 的参数可由下面的公式重新估计：(1)q1为为Si 的概率：的概率：i 1 (i)公式公式3.9公式公式3.10隐Markov模型的三个基本问题及其算法（16）学习问题学习问题(3)可观察符号的输出概率：可观察符号的输出概率：(2)转移概率：转移概率：公式公式3.11公式公式3.12隐Markov模型的三个基本问题及其算法（17）学习问题学习问题 ab (k) 1Baum-Welch算法 (前向后向算法):(1)初始化：初始化：随机地给 i , aij , bj (k)赋值，使得 1Ni 1iij 11 i NNj 1i1 i N由此得到模型 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）v 隐隐Markov模型具有广泛的应用，如：模型具有广泛的应用，如： 自然语言处理：中文分词、词性标注、音字转换、自然语言处理：中文分词、词性标注、音字转换、语音识别、机器翻译语音识别、机器翻译12行为识别、手写字符识别行为识别、手写字符识别3生物信息学：基因组分析生物信息学：基因组分析一般化：任何与线性序列相关的问题！一般化：任何与线性序列相关的问题！隐Markov模型的应用（2）v以词性标注为例：以词性标注为例：词性标注词性标注把把这这篇篇报道报道编辑编辑一一下下有多少种可能性？哪种可能性最大？有多少种可能性？哪种可能性最大？隐Markov模型的应用（3）v我们看到的是词汇序列词汇序列，记做W=w1w2wn（即观察符即观察符号序列号序列）。需要去猜测隐藏在幕后的词性标记序列词性标记序列，记做Tt1t2tn（即状态序列即状态序列）v问问题题抽抽象象：已已知知词词串串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 词性转移矩阵词性转移矩阵词性标注词性标注Tagcfmnpqrvc736700397143250925353777640148f900475456976972968278129026951m54714701750546001172213965330513778n551775057127918277181430234049769221776p472664141317825133631422724936807q7327845450652310245117676013288r205512251282043953112297681357253391v13715148437091422179644651322646697191967隐Markov模型的应用（7）词性词性频次频次c168350f110878m270381n1539367p269186q155374r214942v1193317表表2 词性频次表词性频次表词性标注词性标注由表由表1和表和表2得出词性得出词性的转移概率的转移概率 P(ti|ti-1)隐Markov模型的应用（8）词语词语词性词性频次频次词语词语词性词性频次频次把把p9877编辑编辑n243把把q290编辑编辑v100把把n2一一m20672把把v208一一c2229这这r21990下下f6313篇篇q706下下q161报道报道v4040下下v2271报道报道n420表表3 词语词语/词性频次表词性频次表词性标注词性标注由表由表2和表和表3得出在不同词性下的词语输出概率得出在不同词性下的词语输出概率 P(wi|ti)隐Markov模型的应用（9）词性标注词性标注把把这这篇篇报道报道编辑编辑一一下下五、隐Markov模型总结（1）v隐隐Markov模型可视为一个随机有限状态自动机，其中模型可视为一个随机有限状态自动机，其中包含两个随机过程：状态转移过程和观察符号的输出过包含两个随机过程：状态转移过程和观察符号的输出过程程v隐隐Markov模型涉及三个基本问题：评估问题、解码问模型涉及三个基本问题：评估问题、解码问题和学习问题题和学习问题v对任何应用，都要考虑如下问题：系统的状态和观察符对任何应用，都要考虑如下问题：系统的状态和观察符号是什么？各自的数目是多少？如何通过已有数据来获号是什么？各自的数目是多少？如何通过已有数据来获得模型参数？得模型参数？隐Markov模型总结（2）v应用中的问题应用中的问题小数溢出：小数溢出：Viterbi变量的连乘变量的连乘取对数取对数训练数据不足的问题训练数据不足的问题将两个模型整合将两个模型整合独立性假设：时间独立、上下文独立独立性假设：时间独立、上下文独立更高级的模型：条件随机场（更高级的模型：条件随机场（CRF）具体应用中的问题具体应用中的问题比如语音识别中说话人的影响比如语音识别中说话人的影响