1、主要内容马尔可夫链马尔可夫模型jia,例例（续）隐马尔可夫模型（Hidden Markov Model,HMM）HMM的三个假设HMM定义观察序列产生步骤HMM的三个基本问题例:赌场的欺诈 某赌场在掷骰子根据点数决定胜负时,暗中采取了如下作弊手段:在连续多次掷骰子的过程中,通常使用公平骰子AB0.90.1A,偶而混入一个灌铅骰子B.0.80.2公平骰子灌铅骰子公平骰子A与灌铅骰子B的区别:一次连续掷骰子的过程模拟隐序列明序列查封赌场后,调查人员发现了一些连续掷骰子的记录,其中有一个骰子掷出的点数记录如下:124552646214614613613666166466163661636616361
2、651561511514612356234 问题 1 评估问题给定一个骰子掷出的点数记录124552646214614613613666166466163661636616361651561511514612356234问题会出现这个点数记录的概率有多大?问题 2 解码问题给定一个骰子掷出的点数记录124552646214614613613666166466163661636616361651561511514612356234问题点数序列中的哪些点数是用骰子B掷出的?问题 3 学习问题给定一个骰子掷出的点数记录12455264621461461361366616646616366163661
3、6361651561511514612356234问题 作弊骰子掷出各点数的概率是怎样的?公平骰子掷出各点数的概率又是怎样的?赌场是何时 换用骰子的?骰子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
4、:0.11:2:3:4:5:6:0.80.90.2HMM将两个序列相联系起来：1.由离散隐状态组成的状态序列(路径)Q=(q1,qT),每个qtS均是一个状态由初始状态概率及状态转移概率(,A)所决定2.由明字符组成的观察序列O=(o1,oT),每个otV均为一个离散明字符由状态序列及各状态的明字符生成概率(Q,B)所决定赌场的例子中:隐状态明观察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
5、2 5 6 3 1 3 4 1q1q2q3q4qT.o1o2o3o4oT.观察序列O状态序列QHMM 本例中三个基本问题1.评估问题 给定观察序列O和HMM =(,A,B),判断O是由产生出来的可能性有多大 计算骰子点数序列的确由“作弊”模型生成的可能性2.解码问题 给定观察序列O和HMM =(,A,B),计算与序列O相对应的状态序列是什么 在骰子点数序列中,判断哪些点数是用骰子B掷出的3.学习问题 给定一系列观察序列样本,确定能够产生出这些序列的模型=(,A,B)如何从大量的点数序列样本中学习得出“作弊模型”的参数三个基本问题的求解算法解决问题一前向算法定义前向变量为：“在时间步t,得到t之
6、前的所有明符号序列,且时间步t的状态是Si”这一事件的概率，记为(t,i)=P(o1,ot,qt=Si|)则算法过程HMM的网格结构前向算法过程演示t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=Ni=N-1i=5i=4i=3i=2i=1(t,i)t=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)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=1t=2t=3t=4t=5t=Tt=6t=7t=T-
7、1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=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=1t=1t=2t=3t=4t=5t=Tt=6t=7
8、t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=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
9、=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=1t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=1t=2t=3t=4t=5t=Tt=6t=7
10、t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=1t=2t=3t=4t=5t=Tt=7t=6t=T-1前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1t=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=5
11、t=Tt=T-1t=6t=7前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1例子（前向算法应用）状态集Q=S1,S2,S3观察序列集O=A,B例（续）t(i)1.当 t=1时：例（续）例（续）4(1)+4(2)+4(3)=0.0717696 即观察序列O由HMM模型产生的概率例（续）问题 2解码问题所求的 Q 应当在某个准则下是“最优”的,因此也称 Q 为最优路径,解码问题即是确定最优路径的问题。qt=Si产生出 o1,ot的最大概率，即：解决问题二Viterbi算法Viterbi 算法也是类似于前向算法的一种网格结构Viterbi算法（续）Viterbi算法（续）例子（Viterbi算法应用）状态集QS1,S2,S3观察序列集O=A,B例（续）例（续）例（续）例（续）例（续）问题3学习问题也称训练问题、参数估计问题化准则，使得观察序列的概率P(O|)最大。状态序列已知情况EM(Expectation-Maximization)算法向前向后算法(Baum-Welch算法)期望值(1)图示期望值(2)重估公式(3)HMM的应用HMM的一些实际问题HMM的一些实际问题（续）HMM总结
