隐马尔可夫模型(有具体例子-方便理解).ppt

隐马尔可夫模型隐马尔可夫模型 1主要内容n n马尔可夫模型马尔可夫模型n n隐马尔可夫模型隐马尔可夫模型n n隐马尔可夫模型的三个基本问题隐马尔可夫模型的三个基本问题n n三个基本问题的求解算法三个基本问题的求解算法 1.1.前向算法前向算法 2.2.ViterbiViterbi算法算法 3.3.向前向后算法向前向后算法n n隐马尔可夫模型的应用隐马尔可夫模型的应用n n隐马尔可夫模型的一些实际问题隐马尔可夫模型的一些实际问题n n隐马尔可夫模型总结隐马尔可夫模型总结2马尔可夫链 一个系统有一个系统有NN个状态个状态 S1S1，S2S2，SnSn，随着时间推移，随着时间推移，系统从某一状态转移到另一状态，设系统从某一状态转移到另一状态，设qtqt为时间为时间t t的状态，系的状态，系统在时间统在时间t t处于状态处于状态Sj Sj 的概率取决于其在时间的概率取决于其在时间 1 1，2 2，t-1 t-1 的状态，该概率为：的状态，该概率为：如果系统在如果系统在t t时间的状态只与其在时间时间的状态只与其在时间 t-1t-1的状态相关，的状态相关，则该系统构成一个离散的一阶则该系统构成一个离散的一阶马尔可夫链马尔可夫链(马尔可夫过程马尔可夫过程)：3马尔可夫模型 如果只考虑独立于时间如果只考虑独立于时间t t的随机过程：的随机过程：其中状态转移概率其中状态转移概率 a aij ij 必须满足必须满足 a aij ij=0,=0,且且 ，则该随机过程称为，则该随机过程称为马尔可夫模型马尔可夫模型。4例 假定一段时间的气象可由一个三状态的马尔可夫模型M描述，S1：雨，S2：多云，S3：晴，状态转移概率矩阵为：5例（续）如果第一天为晴天，根据这一模型，在今后七天中天如果第一天为晴天，根据这一模型，在今后七天中天气为气为O=O=“晴晴雨雨晴云晴晴晴雨雨晴云晴”的概率为：的概率为：6隐马尔可夫模型（Hidden Markov Model,HMM）n n在MM中，每一个状态代表一个可观察的 事件n n在HMM中观察到的事件是状态的随机函数，因此该模型是一双重随机过程，其中状态转移过程是不可观察（隐蔽）的(马尔可夫链)，而可观察的事件的随机过程是隐蔽的状态转换过程的随机函数(一般随机过程)。7HMM的三个假设 对于一个随机事件，有一观察值序列：对于一个随机事件，有一观察值序列：O=OO=O1 1,O,O2 2,OOT T该事件隐含着一个状态序列：该事件隐含着一个状态序列：Q=qQ=q1 1,q,q2 2,q qT T。假设假设假设假设1 1：马尔可夫性假设（状态构成一阶马尔可夫链）马尔可夫性假设（状态构成一阶马尔可夫链）P(qP(qi i|q|qi-1i-1q q1 1)=P(q)=P(qi i|q|qi-1i-1)假设假设假设假设2 2：不动性假设（状态与具体时间无关）不动性假设（状态与具体时间无关）P(qP(qi+1i+1|q|qi i)=P(q)=P(qj+1j+1|q|qj j)，对任意对任意i i，j j成立成立假设假设假设假设3 3：输出独立性假设（输出仅与当前状态有关）输出独立性假设（输出仅与当前状态有关）p(Op(O1 1,.,O,.,OT T|q|q1 1,.,q,.,qT T)=)=pp(O(Ot t|q|qt t)8HMM定义 一个隐马尔可夫模型一个隐马尔可夫模型(HMM)HMM)是由一个五元组描述的：是由一个五元组描述的：（N，M，A，B，）其中：其中：N N=q=q1 1,.q,.qNN：状态的有限集合状态的有限集合 M M=v=v1 1,.,v,.,vMM：观察值的有限集合观察值的有限集合 A=a A=aij ij，a aij ij=P(q=P(qt t=S=Sj j|q|qt-1t-1=S=Si i)：状态转移概率矩阵状态转移概率矩阵 B=b B=bjk jk，b bjk jk =P(O=P(Ot t=v=vk k|q|qt t=S=Sj j)：观察值概率分布矩阵观察值概率分布矩阵 =i i，i i=P(q=P(q1 1=S=Si i)：初始状态概率分布初始状态概率分布9观察序列产生步骤n n给定给定HMMHMM模型模型 =(A=(A，B B，)，则观察序列，则观察序列 O=OO=O1 1,O,O2 2,OOT T 可由以下步骤产生：可由以下步骤产生：n n1.1.根据初始状态概率分布根据初始状态概率分布=i i,选择一初始状态选择一初始状态q q1 1=S=Si i；n n2.2.设设t=1t=1；n n3.3.根据状态根据状态 S Si i的输出概率分布的输出概率分布b bjk jk,输出输出OOt t=v=vk k；n n4.4.根据状态转移概率分布根据状态转移概率分布a aij ij,转移到新状态转移到新状态q qt+1t+1=S=Sj j；n n5.5.设设t=t+1,t=t+1,如果如果tTtT，重复步骤，重复步骤3 3、4 4，否则结束。，否则结束。10HMM的三个基本问题令令 =，A A，B B 为给定为给定HMMHMM的参数，的参数，令令 O=O=O1 1,.,O,.,OT T 为观察值序列，则有关于为观察值序列，则有关于隐马尔可夫模型（隐马尔可夫模型（HMMHMM）的三个基本问题：的三个基本问题：1.1.评估问题：评估问题：对于给定模型，求某个观察值序列的对于给定模型，求某个观察值序列的概率概率P(P(O|)；2.2.解码问题：解码问题：对于给定模型和观察值序列，求可能对于给定模型和观察值序列，求可能性最大的状态序列性最大的状态序列maxmaxQQP(Q|O,P(Q|O,)；3.3.学习问题：学习问题：对于给定的一个观察值序列对于给定的一个观察值序列OO，调整，调整参数参数，使得观察值出现的概率使得观察值出现的概率P(P(O|)最大。最大。11例:赌场的欺诈 某赌场在掷骰子根据点数决定胜负时,暗中采取了如下作弊手段:在连续多次掷骰子的过程中,通常使用公平骰子AB0.90.1A,偶而混入一个灌铅骰子B.0.80.2公平骰子灌铅骰子12骰子骰子A A骰子骰子B B1 1点点1/61/60 02 2点点1/61/61/81/83 3点点1/61/61/81/84 4点点1/61/63/163/165 5点点1/61/63/163/166 6点点1/61/63/83/8公平骰子A与灌铅骰子B的区别:13时间时间1 12 23 34 45 56 67 7骰子骰子A AA AA AB BA AA AA A掷出掷出点数点数3 33 34 45 51 16 62 2一次连续掷骰子的过程模拟隐序列明序列查封赌场后,调查人员发现了一些连续掷骰子的记录,其中有一个骰子掷出的点数记录如下:124552646214614613613666166466163661636616361651561511514612356234 14问题 1 评估问题给定一个骰子掷出的点数记录124552646214614613613666166466163661636616361651561511514612356234问题会出现这个点数记录的概率有多大?求P(O|)15问题 2 解码问题给定一个骰子掷出的点数记录124552646214614613613666166466163661636616361651561511514612356234问题点数序列中的哪些点数是用骰子B掷出的?求maxQP(Q|O,)16问题 3 学习问题给定一个骰子掷出的点数记录124552646214614613613666166466163661636616361651561511514612356234问题 作弊骰子掷出各点数的概率是怎样的?公平骰子掷出各点数的概率又是怎样的?赌场是何时 换用骰子的?17骰子B 本例中HMM的定义赌场的例子中:隐状态集:S=骰子A,骰子B明字符集:V=1,2,3,4,5,6b21=0,b22=b23=1/8,b24=b25=3/16,b26=3/81/61/61/61/61/61/601/81/83/163/163/8初始状态概率:1=1,2=0隐状态转移概率:a11=0.9,a12=0.1 a21=0.8,a22=0.2初始状态明字符生成概率:b11=b12=b16=1/61.001:2:3:4:5:骰子A 6:0.11:2:3:4:5:6:0.80.90.218HMM将两个序列相联系起来：1.由离散隐状态组成的状态序列(路径)Q=(q1,qT),每个qtS均是一个状态由初始状态概率及状态转移概率(,A)所决定2.由明字符组成的观察序列O=(o1,oT),每个otV均为一个离散明字符由状态序列及各状态的明字符生成概率(Q,B)所决定19赌场的例子中:隐状态明观察AAAABAAAAABAAAAAAAAAAAAAAAAAAAAAAABAABAAAAAAAAA3 3 4 5 4 1 4 1 5 5 3 6 6 3 4 4 1 1 3 4 6 2 5 4 4 5 3 3 4 2 2 3 3 3 2 1 2 4 2 2 5 6 3 1 3 4 1q1q2q3q4qT.o1o2o3o4oT.观察序列O状态序列QHMM 20本例中三个基本问题1.评估问题 给定观察序列O和HMM =(,A,B),判断O是由产生出来的可能性有多大 计算骰子点数序列的确由“作弊”模型生成的可能性2.解码问题 给定观察序列O和HMM =(,A,B),计算与序列O相对应的状态序列是什么 在骰子点数序列中,判断哪些点数是用骰子B掷出的3.学习问题 给定一系列观察序列样本,确定能够产生出这些序列的模型=(,A,B)如何从大量的点数序列样本中学习得出“作弊模型”的参数21三个基本问题的求解算法n n评估问题：前向算法n n定义前向变量定义前向变量n n采用动态规划算法，复杂度采用动态规划算法，复杂度O(NO(N2 2T)T)n n解码问题：韦特比（Viterbi）算法n n采用动态规划算法，复杂度采用动态规划算法，复杂度O(NO(N2 2T)T)n n学习问题：向前向后算法EMEM算法的一个特例，带隐变量的最大似然估计算法的一个特例，带隐变量的最大似然估计22解决问题一前向算法定义前向变量为：“在时间步t,得到t之前的所有明符号序列,且时间步t的状态是Si”这一事件的概率，记为(t,i)=P(o1,ot,qt=Si|)则23算法过程24HMM的网格结构25前向算法过程演示t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=Ni=N-1i=5i=4i=3i=2i=1(t,i)26t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=11.初始化(1,i)=(i)b(i,o1)27t=1t=2t=3t4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=128t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=129t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=130t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=131t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=12.递归32t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=133t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=134t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=135t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=136t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=137t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=138前向算法过程演示i=Nt=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=N-1i=5i=4i=3i=2i=139前向算法过程演示t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=Ni=N-1i=5i=4i=3i=2i=140t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=141t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示iNi=N-1i=5i=4i=3i=2i=142t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=143t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=144t=1t=2t=3t=4t=5t=Tt=7t=6t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=145t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=146t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=147前向算法过程演示t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7i=Ni=N-1i=5i=4i=3i=2i=13.计算P(O|)48t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=149例子（前向算法应用）n nHMM模型如下，试根据前向算法计算产生观察符号序列O=ABAB的概率。状态集Q=S1,S2,S3观察序列集O=A,B50例（续）n n初始概率矩阵=(1,0,0),即开始处于状态1。按照前向算法公式，我们依次递推解出 t(i)。解法如下：1当 t=1时：51例（续）n n2.2.当当t=2t=2时：时：n n3.3.当当t=3t=3时：时：52例（续）n n4.当t=4时：n n所以最终有：P(O|)=4(1)+4(2)+4(3)=0.0717696 即观察序列O由HMM模型产生的概率53例（续）n n最后将其计算过程示意图表示如下：54问题 2解码问题所求的 Q 应当在某个准则下是“最优”的,因此也称 Q 为最优路径,解码问题即是确定最优路径的问题。55qt=Si产生出 o1,ot的最大概率，即：解决问题二Viterbi算法Viterbi 算法也是类似于前向算法的一种网格结构56Viterbi算法（续）n n目标：给定一个观察序列和目标：给定一个观察序列和HMMHMM模型，如何有效选择模型，如何有效选择“最优最优”状态序列，以状态序列，以“最好地解释最好地解释”观察序列观察序列n n“最优最优”概率最大：概率最大：n nViterbiViterbi变量：变量：n n递归关系：递归关系：n n记忆变量：记忆变量：记录概率最大路径上当前状态的前一个状记录概率最大路径上当前状态的前一个状态态57Viterbi算法（续）n n初始化：n n递归：n n终结：n n路径回溯：58例子（Viterbi算法应用）n nHMMHMM模型如下，试根据模型如下，试根据ViterbiViterbi算法计算产生观察算法计算产生观察符号序列符号序列O=ABABO=ABAB的最优状态序列的最优状态序列QQ。状态集QS1,S2,S3观察序列集O=A,B59例（续）n n初始概率矩阵=(1,0,0),即开始时处于状 态1。按照上面的公式，我们依次递推解出 ，以及 。解法如下：1.当t=1时：60例（续）n n2.当t=2时：n n3.当t=3时：61例（续）n n4.当t=4时：62例（续）n n其递推结果为：其递推结果为：n n可以看出，最有可能的状态序列是：可以看出，最有可能的状态序列是：S1S1，S2S2，S2S2，S2.S2.63例（续）n n其计算结果示意图如下所示：n n绿色的箭头表示最有可能的状态序列绿色的箭头表示最有可能的状态序列 64问题3学习问题也称训练问题、参数估计问题化准则，使得观察序列的概率P(O|)最大。65状态序列已知情况n n可以由最大似然估计来估计HMM的参数：66EM(Expectation-Maximization)算法n n由于由于HMMHMM中的状态序列是观察不到的（隐变量），中的状态序列是观察不到的（隐变量），以上的最大似然估计不可行。以上的最大似然估计不可行。EMEM算法可算法可 用于含有隐变量的统计模型的最大似然估计。用于含有隐变量的统计模型的最大似然估计。n nEMEM算法是一个由交替进行的算法是一个由交替进行的“期望期望(E(E过程过程)”和和“极大似然估计极大似然估计M(M过程过程)”两部分组成的迭代过程：两部分组成的迭代过程：对于给定的不完全数据和当前的参数值，对于给定的不完全数据和当前的参数值，“E E过程过程”从条件期望中从条件期望中相相 应地构造完全数据的似然函数值，应地构造完全数据的似然函数值，“MM过程过程”则利用参数的则利用参数的充分统计充分统计 量，重新估计概率模型的参数，使得训练数据的对数似然最大。量，重新估计概率模型的参数，使得训练数据的对数似然最大。n nEMEM算法的每一次迭代过程必定单调地增加训练数算法的每一次迭代过程必定单调地增加训练数据的对数似然值，于是迭代过程渐进地收敛于一据的对数似然值，于是迭代过程渐进地收敛于一个局部最优值。个局部最优值。67向前向后算法(Baum-Welch算法)n n1.1.初始化：随机地给初始化：随机地给 i i ，a aij ij ，bjk bjk 赋值（满足概率赋值（满足概率条件），得到模型条件），得到模型 0 0，设，设 i=0 i=0；n n2.EM2.EM步骤：步骤：E E步骤：由步骤：由 i i根据公式（根据公式（1 1）和（）和（2 2），计算期望值），计算期望值 t t（i i，j j）和和 t t（i i）；）；MM步骤：用步骤：用E E步骤所得的期望值，根据公式（步骤所得的期望值，根据公式（3 3）重新估计重新估计 i i ，a aij ij ，bjk bjk，得到模型，得到模型 i+1i+1;n n3.3.循环设计：循环设计：i=i+1 i=i+1；重复；重复EMEM步骤，直至步骤，直至 i i ，a aij ij ，bjk bjk 值收敛。值收敛。68期望值(1)n n给定给定HMMHMM和观察序列，和观察序列，t t（i i，j j）为在时间）为在时间t t 位于状态位于状态i i，时间，时间 t+1 t+1 位于状态位于状态j j的概率：的概率：69图示70期望值(2)n n给定HMM和观测序列，在时间t位于状态i的概率：71重估公式(3)72HMM的应用n n语音识别n n音字转换n n词性标注（POS Tagging）n n基因识别问题 状态状态:编码区域与非编码区域编码区域与非编码区域 字符字符:ATCG:ATCGn n一般化：任何与线性序列相关的现象73HMM的一些实际问题n n初始概率分布的选择 1.随机选择 2.利用先验信息 3.来自多序列比对的结果74HMM的一些实际问题（续）n n数值计算中的防溢出处理n n在前向算法、Viterbi算法以及Baum-Welch算法中，概率值的连续乘法运算很容易导致下溢现象。n n解决办法：1.1.前向算法中：每一个时间步的运算中都乘以一前向算法中：每一个时间步的运算中都乘以一 个比例因子个比例因子 2.Viterbi 2.Viterbi算法中：对概率值取对数后计算算法中：对概率值取对数后计算75n nViterbiViterbi算法算法:连乘积连乘积对数求和对数求和n n前向算法前向算法:引入比例因子引入比例因子 其中其中,比例因子比例因子76HMM总结n nHMM模型可以看作一种特定的Bayes Netn nHMM模型等价于概率正规语法或概率有限状态自动机n nHMM模型可以用一种特定的神经网络模型来模拟n n优点：研究透彻，算法成熟，效率高，效果好，易于训练77