《隐马尔可夫模型(有例子,具体易懂)》由会员分享，可在线阅读，更多相关《隐马尔可夫模型(有例子,具体易懂)（77页珍藏版）》请在金锄头文库上搜索。
1、隐马尔可夫模型隐马尔可夫模型 主要内容 n n 马尔可夫模型马尔可夫模型 n n 隐马尔可夫模型隐马尔可夫模型 n n 隐马尔可夫模型的三个基本问题隐马尔可夫模型的三个基本问题 n n 三个基本问题的求解算法三个基本问题的求解算法 1. 1.前向算法前向算法 2. 2.ViterbiViterbi算法算法 3. 3.向前向后算法向前向后算法 n n 隐马尔可夫模型的应用隐马尔可夫模型的应用 n n 隐马尔可夫模型的一些实际问题隐马尔可夫模型的一些实际问题 n n 隐马尔可夫模型总结隐马尔可夫模型总结 马尔可夫链 一个系统有一个系统有NN个状态个状态 S1S1，S2S2，SnSn，随着时间推移，
2、随着时间推移 ，系统从某一状态转移到另一状态，设，系统从某一状态转移到另一状态，设qtqt为时间为时间t t的状态，的状态， 系统在时间系统在时间t t处于状态处于状态Sj Sj 的概率取决于其在时间的概率取决于其在时间 1 1 ，2 2， ，t-1 t-1 的状态，该概率为：的状态，该概率为： 如果系统在如果系统在t t时间的状态只与其在时间时间的状态只与其在时间 t -1t -1的状态相关的状态相关 ，则该系统构成一个离散的一阶，则该系统构成一个离散的一阶马尔可夫链马尔可夫链( (马尔可夫过马尔可夫过 程程) )： 马尔可夫模型 如果只考虑独立于时间如果只考虑独立于时间t t的随机过程：的
3、随机过程： 其中状态转移概率其中状态转移概率 a aij ij 必须满足 必须满足 a a ij ij =0 , =0 , 且且 ，则该随机过程称为，则该随机过程称为马尔可夫模型马尔可夫模型。 例 假定一段时间的气象可由一个三状态的假定一段时间的气象可由一个三状态的 马尔可夫模型马尔可夫模型MM描述，描述，S1S1：雨，：雨，S2S2：多云，：多云， S3S3：晴，状态转移概率矩阵为：晴，状态转移概率矩阵为： 例（续） 如果第一天为晴天，根据这一模型，在今后七天中天如果第一天为晴天，根据这一模型，在今后七天中天 气为气为O=O=“ “晴晴雨雨晴云晴晴晴雨雨晴云晴” ”的概率为：的概率为： 隐马
4、尔可夫模型 （Hidden Markov Model, HMM） n n 在在MMMM中，每一个状态代表一个可观察的中，每一个状态代表一个可观察的 事件事件 n n 在在HMMHMM中观察到的事件是状态的随机函数中观察到的事件是状态的随机函数 ，因此该模型是一双重随机过程，其中状，因此该模型是一双重随机过程，其中状 态转移过程是不可观察（隐蔽）的态转移过程是不可观察（隐蔽）的( (马尔可马尔可 夫链夫链) )，而可观察的事件的随机过程是隐蔽，而可观察的事件的随机过程是隐蔽 的状态转换过程的随机函数的状态转换过程的随机函数( (一般随机过程一般随机过程) ) 。 HMM的三个假设 对于一个随机事
5、件，有一观察值序列：对于一个随机事件，有一观察值序列： O=OO=O 1 1 ,O,O 2 2 , ,OO T T 该事件隐含着一个状态序列：该事件隐含着一个状态序列： Q = qQ = q 1 1 ,q ,q 2 2 , ,q qT T。 。 假设假设1 1：马尔可夫性假设（状态构成一阶马尔可夫链）马尔可夫性假设（状态构成一阶马尔可夫链） P(qP(q i i |q|qi-1 i-1 q q 1 1 ) = P(q) = P(q i i |q|qi-1 i-1 ) ) 假设假设2 2：不动性假设（状态与具体时间无关）不动性假设（状态与具体时间无关） P(qP(qi+1 i+1|q |q i
6、i ) = P(q) = P(qj+1 j+1|q |q j j ) )，对任意对任意i i，j j成立成立 假设假设3 3：输出独立性假设（输出仅与当前状态有关）输出独立性假设（输出仅与当前状态有关） p(Op(O 1 1 ,.,O,.,OT T | q | q 1 1 ,.,q,.,q T T ) = ) = pp(O(O t t | q| q t t ) ) HMM定义 一个隐马尔可夫模型一个隐马尔可夫模型 ( (HMM) HMM) 是由一个五元组描述的：是由一个五元组描述的： （ NN，M M ，A A，B B， ） 其中：其中： N N = q = q 1 1 ,.q,.qN N ：
7、 ：状态的有限集合状态的有限集合 M M = v = v 1 1 ,.,v,.,vM M ： ：观察值的有限集合观察值的有限集合 A = a A = a ij ij ，a a ij ij = P(q = P(q t t = S = S j j |q |qt-1 t-1 = S = S i i ) )：状态转移概率矩阵状态转移概率矩阵 B = b B = b jk jk ， b b jk jk = P(O= P(O t t = v = v k k | q | q t t = S = S j j ) )：观察值概率分布矩阵观察值概率分布矩阵 = = i i ， i i = P(q = P(q 1
8、1 = S= S i i ) )：初始状态概率分布初始状态概率分布 观察序列产生步骤 n n 给定给定HMMHMM模型模型 = (A = (A， B B， ) ，则观察序列，则观察序列 O=OO=O 1 1 ,O,O 2 2 , ,OO T T 可由以下步骤产生：可由以下步骤产生： n n 1. 1.根据初始状态概率分布根据初始状态概率分布= = i i , ,选择一初始状态选择一初始状态 q q1 1 =S=S i i ； n n 2. 2.设设t=1t=1； n n 3. 3.根据状态根据状态 S S i i 的输出概率分布的输出概率分布 b bjk jk , ,输出输出OO t t =v
9、=v k k ； n n 4. 4.根据状态转移概率分布根据状态转移概率分布a a ij ij , ,转移到新状态转移到新状态q qt+1 t+1=S =S j j ； n n 5. 5.设设t=t+1,t=t+1,如果如果tTtT，重复步骤，重复步骤3 3、4 4，否则结束。，否则结束。 HMM的三个基本问题 令令 = = ，A A，B B 为给定为给定HMMHMM的参数，的参数， 令令 O O = O= O 1 1 ,.,O,.,OT T 为观察值序列，则有关于 为观察值序列，则有关于 隐马尔可夫模型（隐马尔可夫模型（HMMHMM）的三个基本问题：的三个基本问题： 1. 1.评估问题：评估
10、问题：对于给定模型，求某个观察值序列的对于给定模型，求某个观察值序列的 概率概率P(P(OO| | ) ) ； 2. 2.解码问题：解码问题：对于给定模型和观察值序列，求可能对于给定模型和观察值序列，求可能 性最大的状态序列性最大的状态序列maxmaxQ QP(Q|O, P(Q|O, )； 3. 3.学习问题：学习问题：对于给定的一个观察值序列对于给定的一个观察值序列OO，调整，调整 参数参数 ，使得观察值出现的概率使得观察值出现的概率P(P(OO| | ) )最大。最大。 例: 赌场的欺诈 某赌场在掷骰子根据点数决定胜负时 , 暗中 采取了如下作弊手段: 在连续多次掷骰子的过程中, 通常使用
11、公平骰 子 AB 0.9 0.1 A, 偶而混入一个灌铅骰子B. 0.8 0.2 公平骰子 灌铅骰子 骰子骰子A A骰子骰子B B 1 1点点1/61/6 0 0 2 2点点1/61/61/81/8 3 3点点1/61/61/81/8 4 4点点1/61/63/163/16 5 5点点1/61/63/163/16 6 6点点1/61/63/83/8 公平骰子A与灌铅骰子B的区别: 时间时间 1 1 2 2 3 3 4 4 5 5 6 6 7 7 骰子骰子 A A A A A A B B A A A A A A 掷出掷出 点数点数 3 3 3 3 4 4 5 5 1 1 6 6 2 2 一次连续
12、掷骰子的过程模拟 隐序列 明序列 查封赌场后, 调查人员发现了一些连续掷骰子的记录, 其中有一个骰子掷出的点数记录如下: 124552646214614613613666166466163661636616361651561511514612356234 问题 1 评估问题 给定 一个骰子掷出的点数记录 124552646214614613613666166466163661636616361651561511514612356234 问题 会出现这个点数记录的概率有多大? 求求P(O|P(O| ) ) 问题 2 解码问题 给定 一个骰子掷出的点数记录 12455264621461461361
13、3666166466163661636616361651561511514612356234 问题 点数序列中的哪些点数是用骰子B掷出的? 求求maxQP(Q|O,maxQP(Q|O, ) 问题 3 学习问题 给定 一个骰子掷出的点数记录 124552646214614613613666166466163661636616361651561511514612356234 问题 作弊骰子掷出各点数的概率是怎样的?公平骰子 掷出各点数的概率又是怎样的 ? 赌场是何时 换用骰子的 ? 骰子B 本例中HMM的定义 赌场的例子中: 隐状态集: S=骰子A, 骰子B 明字符集: V=1,2,3,4,5,6
14、 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将两个序列相联系起来： 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
