详细讲解隐马尔可夫模型配有实际例题ppt课件.ppt

《详细讲解隐马尔可夫模型配有实际例题ppt课件.ppt》由会员分享，可在线阅读，更多相关《详细讲解隐马尔可夫模型配有实际例题ppt课件.ppt（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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：晴，状态转移概率矩阵为：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例（续）如果第一天为晴天，根据这一模型，在今后七天中天如果第一天为晴天，根据这一模型，在今后七天中天气为气为O=“O=“晴晴雨雨晴云晴晴晴雨雨晴云晴”的概率为：的概率为：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用隐马尔可夫模型（HiddenMa

5、rkovModel,HMM）n n在MM中，每一个状态代表一个可观察的 事件n n在HMM中观察到的事件是状态的随机函数，因此该模型是一双重随机过程，其中状态转移过程是不可观察（隐蔽）的(马尔可夫链)，而可观察的事件的随机过程是隐蔽的状态转换过程的随机函数(一般随机过程)。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用HMM的三个假设 对于一个随机事件，有一观察值序列：对于一个随机事件，有一观察值序列：O=OO=O1 1,O,O2 2,O,OT T该事件隐含着一个状态序列：该事件隐含着一个状态序列：Q=qQ=q

6、1 1,q,q2 2,q,qT T。假设假设假设假设1 1：马尔可夫性假设（状态构成一阶马尔可夫链）马尔可夫性假设（状态构成一阶马尔可夫链）P(qP(qi i|q|qi-1i-1qq1 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

7、,.,q,.,qT T)=)=pp(O(Ot t|q|qt t)经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用HMM定义 一个隐马尔可夫模型一个隐马尔可夫模型(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)：状态

8、转移概率矩阵状态转移概率矩阵 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)：初始状态概率分布初始状态概率分布经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用观察序列产生步骤n n给定给定HMMHMM模型模型 =(A=(A，B B，)，则观察序列，则观察序列 O=OO=O1 1,O,O2 2,O,OT T 可由以下步骤产生：可由以下步骤产生：n n1.1.根

9、据初始状态概率分布根据初始状态概率分布=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，否则结束。，否则结束。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为

10、消费者购买商品的价款或接受服务的费用HMM的三个基本问题令令 =，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.学习问题：学习问题

11、：对于给定的一个观察值序列对于给定的一个观察值序列OO，调整，调整参数参数，使得观察值出现的概率使得观察值出现的概率P(P(O|)最大。最大。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例:赌场的欺诈 某赌场在掷骰子根据点数决定胜负时,暗中采取了如下作弊手段:在连续多次掷骰子的过程中,通常使用公平骰子AB0.90.1A,偶而混入一个灌铅骰子B.0.80.2公平骰子灌铅骰子经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用骰子骰子A

12、 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的区别:经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用时间时间1 12 23 34 45 56 67 7骰子骰子A AA AA AB BA AA AA A掷出掷出点数点数3 33 34 45 51 16 62 2一次连续掷骰子的过程模拟隐序列明序列查封赌场后,调查人员发

13、现了一些连续掷骰子的记录,其中有一个骰子掷出的点数记录如下:124552646214614613613666166466163661636616361651561511514612356234 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用问题1评估问题给定一个骰子掷出的点数记录124552646214614613613666166466163661636616361651561511514612356234问题会出现这个点数记录的概率有多大?求P(O|)经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求

14、增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用问题2解码问题给定一个骰子掷出的点数记录124552646214614613613666166466163661636616361651561511514612356234问题点数序列中的哪些点数是用骰子B掷出的?求maxQP(Q|O,)经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用问题3学习问题给定一个骰子掷出的点数记录12455264621461461361366616646616366163661636165156151151461

15、2356234问题 作弊骰子掷出各点数的概率是怎样的?公平骰子掷出各点数的概率又是怎样的?赌场是何时 换用骰子的?经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用骰子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.1a21=0.8,a22=0.2

16、初始状态明字符生成概率:b11=b12=b16=1/61.001:2:3:4:5:骰子A 6:0.11:2:3:4:5:6:0.80.90.2经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用HMM将两个序列相联系起来：1.由离散隐状态组成的状态序列(路径)Q=(q1,qT),每个qtS均是一个状态由初始状态概率及状态转移概率(,A)所决定2.由明字符组成的观察序列O=(o1,oT),每个otV均为一个离散明字符由状态序列及各状态的明字符生成概率(Q,B)所决定经营者提供商品或者服务有欺诈行为的，应当按照消费者的要

17、求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用赌场的例子中:隐状态明观察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 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用本例中三个基本问

18、题1.评估问题给定观察序列O和HMM =(,A,B),判断O是由产生出来的可能性有多大 计算骰子点数序列的确由“作弊”模型生成的可能性2.解码问题给定观察序列O和HMM=(,A,B),计算与序列O相对应的状态序列是什么在骰子点数序列中,判断哪些点数是用骰子B掷出的3.学习问题给定一系列观察序列样本,确定能够产生出这些序列的模型=(,A,B)如何从大量的点数序列样本中学习得出“作弊模型”的参数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用三个基本问题的求解算法n n评估问题：前向算法n n定义前向变量定义前向变量

19、n n采用动态规划算法，复杂度采用动态规划算法，复杂度O(NO(N2 2T)T)n n解码问题：韦特比（Viterbi）算法n n采用动态规划算法，复杂度采用动态规划算法，复杂度O(NO(N2 2T)T)n n学习问题：向前向后算法EMEM算法的一个特例，带隐变量的最大似然估计算法的一个特例，带隐变量的最大似然估计经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用解决问题一前向算法定义前向变量为：“在时间步t,得到t之前的所有明符号序列,且时间步t的状态是Si”这一事件的概率，记为(t,i)=P(o1,ot,qt=

20、Si|)则经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用算法过程经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用HMM的网格结构经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用前向算法过程演示t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=Ni=N-1i=5i=4i=3i=2i=1(t,i)经营者提供商品或者服务有欺诈行为的，应当按照消

21、费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=11.初始化2.(1,i)=(i)b(i,o1)经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者

22、购买商品的价款或接受服务的费用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前向算法过程

23、演示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经营者提供商品或者服务有欺诈行为的，应当按

24、照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用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=2

25、t=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=

26、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经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额

27、为消费者购买商品的价款或接受服务的费用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前向

28、算法过程演示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=7t=6t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1经营者提供商品或者服务有欺诈行为的，应当按

29、照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用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=7前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用前向算法过程

30、演示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 nHMM模型如下，试根据前向算法计算产生观察符号序列O=ABAB的概率

31、。状态集Q=S1,S2,S3观察序列集O=A,B经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例（续）n n初始概率矩阵=(1,0,0),即开始处于状态1。按照前向算法公式，我们依次递推解出 t(i)。解法如下：1.当 t=1时：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例（续）n n2.2.当当t=2t=2时：时：n n3.3.当当t=3t=3时：时：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的

32、损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例（续）n n4.当t=4时：n n所以最终有：P(O|)=4(1)+4(2)+4(3)=0.0717696 即观察序列O由HMM模型产生的概率经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例（续）n n最后将其计算过程示意图表示如下：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用问题2解码问题所求的 Q应当在某个准则下是“最优”的,因此也称 Q为最优路径,解码问题即是确

33、定最优路径的问题。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用qt=Si产生出 o1,ot的最大概率，即：解决问题二Viterbi算法Viterbi 算法也是类似于前向算法的一种网格结构经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用Viterbi算法（续）n n目标：给定一个观察序列和目标：给定一个观察序列和HMMHMM模型，如何有效选择模型，如何有效选择“最优最优”状态序列，以状态序列，以“最好地解释最好地解释”观察序列观察

34、序列n n“最优最优”概率最大：概率最大：n nViterbiViterbi变量：变量：n n递归关系：递归关系：n n记忆变量：记忆变量：记录概率最大路径上当前状态的前一个状记录概率最大路径上当前状态的前一个状态态经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用Viterbi算法（续）n n初始化：n n递归：n n终结：n n路径回溯：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例子（Viterbi算法应用）n nHMMHM

35、M模型如下，试根据模型如下，试根据ViterbiViterbi算法计算产生观察算法计算产生观察符号序列符号序列O=ABABO=ABAB的最优状态序列的最优状态序列QQ。状态集QS1,S2,S3观察序列集O=A,B经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例（续）n n初始概率矩阵=(1,0,0),即开始时处于状 态1。按照上面的公式，我们依次递推解出 ，以及 。解法如下：1.当t=1时：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服

36、务的费用例（续）n n2.当t=2时：n n3.当t=3时：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例（续）n n4.当t=4时：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例（续）n n其递推结果为：其递推结果为：n n可以看出，最有可能的状态序列是：可以看出，最有可能的状态序列是：S1S1，S2S2，S2S2，S2.S2.经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消

37、费者购买商品的价款或接受服务的费用例（续）n n其计算结果示意图如下所示：n n绿色的箭头表示最有可能的状态序列绿色的箭头表示最有可能的状态序列 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用问题3学习问题也称训练问题、参数估计问题化准则，使得观察序列的概率P(O|)最大。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用状态序列已知情况n n可以由最大似然估计来估计HMM的参数：经营者提供商品或者服务有欺诈行为的，应当按照消费者的

38、要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用EM(Expectation-Maximization)算法n n由于由于HMMHMM中的状态序列是观察不到的（隐变量），中的状态序列是观察不到的（隐变量），以上的最大似然估计不可行。以上的最大似然估计不可行。EMEM算法可算法可 用于含有隐变量的统计模型的最大似然估计。用于含有隐变量的统计模型的最大似然估计。n nEMEM算法是一个由交替进行的算法是一个由交替进行的“期望期望(E(E过程过程)”)”和和“极大似然估计极大似然估计(M(M过程过程)”)”两部分组成的迭代过程：两部分组成的迭代过程：对于给定的不完全数据

39、和当前的参数值，对于给定的不完全数据和当前的参数值，“E E过程过程”从条件期望中从条件期望中相相 应地构造完全数据的似然函数值，应地构造完全数据的似然函数值，“MM过程过程”则利用参数的则利用参数的充分统计充分统计 量，重新估计概率模型的参数，使得训练数据的对数似然最大。量，重新估计概率模型的参数，使得训练数据的对数似然最大。n nEMEM算法的每一次迭代过程必定单调地增加训练数算法的每一次迭代过程必定单调地增加训练数据的对数似然值，于是迭代过程渐进地收敛于一据的对数似然值，于是迭代过程渐进地收敛于一个局部最优值。个局部最优值。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿

40、其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用向前向后算法(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

41、，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 值收敛。值收敛。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用期望值(1)n n给定给定HMMHMM和观察序列，和观察序列，t t（i i，j j）为在时间）为在时间t t 位于状态位于状态i i，时间，时间 t+1 t+1 位于状态位于状态j j的概率：的概率：经营者提供商品或者服务有欺诈行为的，

42、应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图示经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用期望值(2)n n给定HMM和观测序列，在时间t位于状态i的概率：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用重估公式(3)经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用HMM的应用n n语音识别n n

43、音字转换n n词性标注（POS Tagging）n n基因识别问题 状态状态:编码区域与非编码区域编码区域与非编码区域 字符字符:ATCG:ATCGn n一般化：任何与线性序列相关的现象经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用HMM的一些实际问题n n初始概率分布的选择 1.随机选择 2.利用先验信息 3.来自多序列比对的结果经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用HMM的一些实际问题（续）n n数值计算中的防溢出处

44、理n n在前向算法、Viterbi算法以及Baum-Welch算法中，概率值的连续乘法运算很容易导致下溢现象。n n解决办法：1.1.前向算法中：每一个时间步的运算中都乘以一前向算法中：每一个时间步的运算中都乘以一 个比例因子个比例因子 2.Viterbi 2.Viterbi算法中：对概率值取对数后计算算法中：对概率值取对数后计算经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n nViterbiViterbi算法算法:连乘积连乘积对数求和对数求和n n前向算法前向算法:引入比例因子引入比例因子 其中其中,比例因子比例因子经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用HMM总结n nHMM模型可以看作一种特定的Bayes Netn nHMM模型等价于概率正规语法或概率有限状态自动机n nHMM模型可以用一种特定的神经网络模型来模拟n n优点：研究透彻，算法成熟，效率高，效果好，易于训练