前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
2. 递归
前向算法过程演示
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=6 t=7 t=T-1 t=T
HMM的三个基本问题
令 λ = {π，A，B} 为给定HMM的参数，
令 O = O1,...,OT 为观察值序列，则有关于 隐马尔可夫模型（HMM）的三个基本问题： 1.评估问题：对于给定模型，求某个观察值序列的 概率P(O|λ) ；
2.解码问题：对于给定模型和观察值序列，求可能 性最大的状态序列maxQ{P(Q|O,λ)}； 3.学习问题：对于给定的一个观察值序列O，调整 参数λ，使得观察值出现的概率P(O|λ)最大。
观察序列产生步骤



给定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.设t=t+1,如果t<T，重复步骤3、4，否则结束。
…
问题 1 – 评估问题
给定 一个骰子掷出的点数记录
124552646214614613613666166466163661636616361651561511514612356234
问题 会出现这个点数记录的概率有多大?
求P(O|λ)
问题 2 – 解码问题
给定 一个骰子掷出的点数记录
124552646214614613613666166466163661636616361651561511514612356234
本例中三个基本问题
1.评估问题
• 给定观察序列O和HMM =(π, A, B), 判断O是由产 生出来的可能性有多大
• 计算骰子点数序列的确由“作弊”模型生成的可能性
2.解码问题
• 给定观察序列O和HMM λ =(π, A, B), 计算与序列O相 对应的状态序列是什么 • 在骰子点数序列中, 判断哪些点数是用骰子B掷出的
问题 点数序列中的哪些点数是用骰子B掷出的?
求maxQ{P(Q|O,λ)}
问题 3 – 学习问题
给定 一个骰子掷出的点数记录
124552646214614613613666166466163661636616361651561511514612356234
问题 作弊骰子掷出各点数的概率是怎样的?公平骰子 掷出各点数的概率又是怎样的 ? 赌场是何时 换用骰子的 ?
3.学习问题
• 给定一系列观察序列样本, 确定能够产生出这些序列的模 型=(π, A, B) • 如何从大量的点数序列样本中学习得出“作弊模型”的参数
三个基本问题的求解算法

评估问题：前向算法
定义前向变量 采用动态规划算法，复杂度O(N2T)


解码问题：韦特比（Viterbi）算法

采用动态规划算法，复杂度O(N2T)
1点 2点 3点 4点 5点 6点
一次连续掷骰子的过程模拟
时间 骰子 掷出 点数
1 A 3 2 A 3 3 A 4 4 B 5 5 A 1 6 A 6 7 A 2 明序列 隐序列
查封赌场后, 调查人员发现了一些连续掷骰子的记录, 其中有一个骰子掷出的点数记录如下:
124552646214614613613666166466163661636616361651561511514612356234
0.9
0.8
明字符生成概率 :
b11 = b12=…=b16=1/6
0 骰子B
b21=0, b22=b23=1/8, b24=b25=3/16, b26=3/8
0.2
HMM将两个序列相联系起来：
1. 由离散隐状态组成的状态序列(路径)
Q = (q1,…,qT), 每个qt∈S均是一个状态 由初始状态概率及状态转移概率(π, A)所决定
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
2. 由明字符组成的观察序列
O = (o1,…,oT), 每个ot∈V均为一个离散明字符 由状态序列及各状态的明字符生成概率(Q,B)所决定
观察序列O
o1
o2
o3
o4
...
oT
HMM λ
状态序列Q
q1
q2
q3
q4
...
qT
赌场的例子中:
隐状态 AAAABAAAAABAAAAAAAAAAAAAAAAAAAAAAABAA BAAAAAAAAA… 明观察 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…
本例中HMM的定义
赌场的例子中:
隐状态集: S={骰子A, 骰子B} 明字符集: V={1,2,3,4,5,6} 初始状态概率: π1=1, π2=0 隐状态转移概率 :
a11=0.9, a12=0.1 a21=0.8, a22=0.2
初始状态
1.0 骰子A 0.1
1: 0 2: 1/8 3: 1/8 4: 3/16 5: 3/16 6: 3/8 1: 1/6 2: 1/6 3: 1/6 4: 1/6 5: 1/6 6: 1/6
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
例: 赌场的欺诈
某赌场在掷骰子根据点数决定胜负时 , 暗中 采取了如下作弊手段: 在连续多次掷骰子的过程中, 通常使用公平骰 子A, 偶而混入一个灌铅骰子B.
0.8 0.9 A 0.1 公平骰子 灌铅骰子 B 0.2
公平骰子A与灌铅骰子B的区别:
骰子A 1/6 1/6 1/6 1/6 1/6 1/6 骰子B 0 1/8 1/8 3/16 3/16 3/8
前向算法过程演示
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=6 t=7 t=T-1 t=T
前向算法过程演示
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=6 t=7 t=T-1 t=T
例（续）
如果第一天为晴天，根据这一模型，在今后七天中天 气为O=“晴晴雨雨晴云晴”的概率为：
隐马尔可夫模型 （Hidden Markov Model, HMM）
在MM中，每一个状态代表一个可观察的 事件 在HMM中观察到的事件是状态的随机函数， 因此该模型是一双重随机过程，其中状态 转移过程是不可观察（隐蔽）的(马尔可夫 链)，而可观察的事件的随机过程是隐蔽的 状态转换过程的随机函数(一般随机过程)。

HMM的三个假设
对于一个随机事件，有一观察值序列： O=O1,O2,…OT 该事件隐含着一个状态序列： Q = q1,q2,…qT。 假设1：马尔可夫性假设（状态构成一阶马尔可夫链） P(qi|qi-1…q1) = P(qi|qi-1)