《[计算机软件及应用]隐马尔可夫模型有具体例子_方便理解》由会员分享，可在线阅读，更多相关《[计算机软件及应用]隐马尔可夫模型有具体例子_方便理解（77页珍藏版）》请在金锄头文库上搜索。
1、隐马尔可夫模型,主要内容,马尔可夫模型 隐马尔可夫模型 隐马尔可夫模型的三个基本问题 三个基本问题的求解算法 1.前向算法 2.Viterbi算法 3.向前向后算法 隐马尔可夫模型的应用 隐马尔可夫模型的一些实际问题 隐马尔可夫模型总结,马尔可夫链,一个系统有N个状态 S1，S2，Sn，随着时间推移，系统从某一状态转移到另一状态，设qt为时间t的状态，系统在时间t处于状态Sj 的概率取决于其在时间 1 ，2，t-1 的状态，该概率为： 如果系统在t时间的状态只与其在时间 t -1的状态相关，则该系统构成一个离散的一阶马尔可夫链(马尔可夫过程)：,马尔可夫模型,如果只考虑独立于时间t的随机过程：
2、 其中状态转移概率 aij 必须满足 aij=0 , 且 ，则该随机过程称为马尔可夫模型。,例,假定一段时间的气象可由一个三状态的马尔可夫模型M描述，S1：雨，S2：多云，S3：晴，状态转移概率矩阵为：,例（续）,如果第一天为晴天，根据这一模型，在今后七天中天气为O=“晴晴雨雨晴云晴”的概率为：,隐马尔可夫模型 （Hidden Markov Model, HMM）,在MM中，每一个状态代表一个可观察的 事件 在HMM中观察到的事件是状态的随机函数，因此该模型是一双重随机过程，其中状态转移过程是不可观察（隐蔽）的(马尔可夫链)，而可观察的事件的随机过程是隐蔽的状态转换过程的随机函数(一般随机过程
3、)。,HMM的三个假设,对于一个随机事件，有一观察值序列： O=O1,O2,OT 该事件隐含着一个状态序列： Q = q1,q2,qT。 假设1：马尔可夫性假设（状态构成一阶马尔可夫链） P(qi|qi-1q1) = P(qi|qi-1) 假设2：不动性假设（状态与具体时间无关） P(qi+1|qi) = P(qj+1|qj)，对任意i，j成立 假设3：输出独立性假设（输出仅与当前状态有关） p(O1,.,OT | q1,.,qT) = p(Ot | qt),HMM定义,一个隐马尔可夫模型 (HMM) 是由一个五元组描述的： （ N，M ，A，B， ） 其中： N = q1,.qN：状态的有限
4、集合 M = v1,.,vM：观察值的有限集合 A = aij，aij = P(qt = Sj |qt-1 = Si)：状态转移概率矩阵 B = bjk， bjk = P(Ot = vk | qt = Sj)：观察值概率分布矩阵 = i，i = P(q1 = Si)：初始状态概率分布,观察序列产生步骤,给定HMM模型 = (A， B， ) ，则观察序列 O=O1,O2,OT 可由以下步骤产生： 1.根据初始状态概率分布= i,选择一初始状态q1=Si； 2.设t=1； 3.根据状态 Si的输出概率分布bjk,输出Ot=vk； 4.根据状态转移概率分布aij,转移到新状态qt+1=Sj； 5.设
5、t=t+1,如果tT，重复步骤3、4，否则结束。,HMM的三个基本问题,令 = ，A，B 为给定HMM的参数， 令 O = O1,.,OT 为观察值序列，则有关于 隐马尔可夫模型（HMM）的三个基本问题： 1.评估问题：对于给定模型，求某个观察值序列的概率P(O|) ； 2.解码问题：对于给定模型和观察值序列，求可能性最大的状态序列maxQP(Q|O,)； 3.学习问题：对于给定的一个观察值序列O，调整参数，使得观察值出现的概率P(O|)最大。,例: 赌场的欺诈,某赌场在掷骰子根据点数决定胜负时 , 暗中,采取了如下作弊手段:,在连续多次掷骰子的过程中, 通常使用公平骰 子,A,B,0.9,0
6、.1,A, 偶而混入一个灌铅骰子B. 0.8,0.2,公平骰子,灌铅骰子,公平骰子A与灌铅骰子B的区别:,一次连续掷骰子的过程模拟,隐序列 明序列 查封赌场后, 调查人员发现了一些连续掷骰子的记录, 其中有一个骰子掷出的点数记录如下: 124552646214614613613666166466163661636616361651561511514612356234 ,问题 1 评估问题,给定,一个骰子掷出的点数记录,124552646214614613613666166466163661636616361651561511514612356234,问题,会出现这个点数记录的概率有多大? 求P
7、(O|),问题 2 解码问题,给定,一个骰子掷出的点数记录,124552646214614613613666166466163661636616361651561511514612356234,问题,点数序列中的哪些点数是用骰子B掷出的? 求maxQP(Q|O,),问题 3 学习问题,给定,一个骰子掷出的点数记录,124552646214614613613666166466163661636616361651561511514612356234,问题,作弊骰子掷出各点数的概率是怎样的?公平骰子,掷出各点数的概率又是怎样的 ? 赌场是何时 换用骰子的 ?,骰子B,本例中HMM的定义 赌场的例子中
8、: 隐状态集: S=骰子A, 骰子B,明字符集: V=1,2,3,4,5,6,b21=0, b22=b23=1/8, b24=b25=3/16, b26=3/8,1/6 1/6 1/6 1/6 1/6 1/6 0 1/8 1/8 3/16 3/16 3/8,初始状态概率: 1=1, 2=0 隐状态转移概率 : a11=0.9, a12=0.1 a21=0.8, a22=0.2 初始状态 明字符生成概率 : b11 = b12=b16=1/6,1.0 0,1: 2: 3: 4: 5: 骰子A 6: 0.1 1: 2: 3: 4: 5: 6:,0.8,0.9,0.2,HMM将两个序列相联系起来：,
9、1. 由离散隐状态组成的状态序列(路径),Q = (q1,qT), 每个qtS均是一个状态,由初始状态概率及状态转移概率(, A)所决定,2. 由明字符组成的观察序列,O = (o1,oT), 每个otV均为一个离散明字符,由状态序列及各状态的明字符生成概率(Q,B)所决定,赌场的例子中:,隐状态 明观察,AAAABAAAAABAAAAAAAAAAAAAAAAAAAAAAABAABAAAAAAAAA 3 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 1,q1,q
10、2,q3,q4,qT,.,o1,o2,o3,o4,oT,.,观察序列O,状态序列Q,HMM ,本例中三个基本问题,1.评估问题, 给定观察序列O和HMM =(, A, B), 判断O是由产,生出来的可能性有多大, 计算骰子点数序列的确由“作弊”模型生成的可能性,2.解码问题, 给定观察序列O和HMM =(, A, B), 计算与序列O相,对应的状态序列是什么, 在骰子点数序列中, 判断哪些点数是用骰子B掷出的,3.学习问题, 给定一系列观察序列样本, 确定能够产生出这些序列的模,型=(, A, B), 如何从大量的点数序列样本中学习得出“作弊模型”的参数,三个基本问题的求解算法,评估问题：前向
11、算法 定义前向变量 采用动态规划算法，复杂度O(N2T) 解码问题：韦特比（Viterbi）算法 采用动态规划算法，复杂度O(N2T) 学习问题：向前向后算法 EM算法的一个特例，带隐变量的最大似然估计,解决问题一前向算法,定义前向变量为：,“在时间步t, 得到t之前的所有明符号序列, 且时间 步t的状态是Si”这一事件的概率， 记为 (t, i) = P(o1,ot, qt = Si|),则,算法过程,HMM的网格结构,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=N i=N-1 i=5 i=4 i=3 i=2 i=1,(t,i),t=1,
12、t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N,i=N-1 i=5 i=4 i=3 i=2 i=1,初始化 (1,i)=(i)b(i,o1),t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N i
13、=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N,i=N-1 i=5 i=4 i=3 i=2 i=1,2. 递归,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N,i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,
14、前向算法过程演示 i=N,i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N,i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N,i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N,i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=
15、7,t=T-1,前向算法过程演示 i=N,i=N-1 i=5 i=4 i=3 i=2 i=1,前向算法过程演示 i=N,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=N-1 i=5 i=4 i=3 i=2 i=1,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=N i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=
16、T,t=6,t=7,t=T-1,前向算法过程演示 i=N i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示 i=N i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=7,t=6,t=T-1,前向算法过程演示 i=N i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,前向算法过程演示 i=N i=N-1 i=5 i=4 i=3 i=2 i=1,t=1,
