b11 = b12=…=b16=1/6 b21=0, b22=b23=1/8, b24=b25=3/16, b26=3/8
1.0 骰子A
1: 1/6
2: 1/6 3: 1/6 4: 1/6 5: 1/6 6: 1/6
0.1
0.8
骰子B
1: 0 2: 1/8
0
3: 1/8
4: 3/16
5: 3/16
6: 3/8
2021/2/2
34
前向算法过程演示
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
2021/2/2
35
前向算法过程演示
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
2021/2/2
42
前向算法过程演示
i=N
2021/2/2
40
前向算法过程演示
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
2021/2/2
41
前向算法过程演示
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
灌铅骰子
2021/2/2
12
公平骰子A与灌铅骰子B的区别:
1点 2点 3点 4点 5点 6点
2021/2/2
骰子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
13
一次连续掷骰子的过程模拟
时间 1 2 3 4 5 6 7 骰子 A A A B A A A 掷出 点数 3 3 4 5 1 6 2
2021/2/2
9
观察序列产生步骤
给定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，否则结束。
2021/2/2
38
前向算法过程演示
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
2021/2/2
39
前向算法过程演示
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
2021/2/2
19
观察序列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…
2. α(1,i)=π(i)b(i,o1)
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
2021/2/2
27
前向算法过程演示
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
2021/2/2
36
前向算法过程演示
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
2021/2/2
37
前向算法过程演示
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
问题
点数序列中的哪些点数是用骰子B掷出的?
求maxQ{P(Q|O,λ)}
2021/2/2
16
问题 3 – 学习问题
给定
一个骰子掷出的点数记录
124552646214614613613666166466163661636616361651561511514612356234
问题
作弊骰子掷出各点数的概率是怎样的?公平骰子 掷出各点数的概率又是怎样的 ? 赌场是何时
如果系统在t时间的状态只与其在时间 t -1的状态相关， 则该系统构成一个离散的一阶马尔可夫链(马尔可夫过程)：
2021/2/2
3
马尔可夫模型
如果只考虑独立于时间t的随机过程：
ai, j
其中状态转移概率 aij 必须满足 aij>=0 , 且 ，则该随机过程称为马尔可夫模型。
2021/2/2
4
例
隐序列 明序列
查封赌场后, 调查人员发现了一些连续掷骰子的记录, 其中有一个骰子掷出的点数记录如下:
… 124552646214614613613666166466163661636616361651561511514612356234
2021/2/2
14
问题 1 – 评估问题
给定
一个骰子掷出的点数记录
在MM中，每一个状态代表一个可观察的 事件
在HMM中观察到的事件是状态的随机函数， 因此该模型是一双重随机过程，其中状态 转移过程是不可观察（隐蔽）的(马尔可夫 链)，而可观察的事件的随机过程是隐蔽的 状态转换过程的随机函数(一般随机过程)。
2021/2/2
7
HMM的三个假设
对于一个随机事件，有一观察值序列： O=O1,O2,…OT
采用动态规划算法，复杂度O(N2T)
学习问题：向前向后算法
EM算法的一个特例，带隐变量的最大似然估计
2021/2/2
22
解决问题一—前向算法
定义前向变量为：
“在时间步t, 得到t之前的所有明符号序列, 且时间 步t的状态是Si”这一事件的概率，
记为 (t, i) = P(o1,…,ot, qt = Si|λ)
3.学习问题：对于给定的一个观察值序列O，调整
参数λ，使得观察值出现的概率P(O|λ)最大。
2021/2/2
11
例: 赌场的欺诈
某赌场在掷骰子根据点数决定胜负时 , 暗中 采取了如下作弊手段: 在连续多次掷骰子的过程中, 通常使用公平骰 子 A, 偶而混入一个灌铅骰子B.
0.8
0.9
A
B
0.2
0.1 公平骰子
2021/2/2
10
HMM的三个基本问题
令 λ = {π，A，B} 为给定HMM的参数，
令 O = O1,...,OT 为观察值序列，则有关于
隐马尔可夫模型（HMM）的三个基本问题： 1.评估问题：对于给定模型，求某个观察值序列的
概率P(O|λ) ；
2.解码问题：对于给定模型和观察值序列，求可能 性最大的状态序列maxQ{P(Q|O,λ)}；
124552646214614613613666166466163661636616361651561511514612356234
问题
会出现这个点数记录的概率有多大?
求P(O|λ)
2021/2/2
15
问题 2 – 解码问题
给定
一个骰子掷出的点数记录
124552646214614613613666166466163661636616361651561511514612356234
该事件隐含着一个状态序列： Q = q1,q2,…qT。
假设1：马尔可夫性假设（状态构成一阶马尔可夫链） P(qi|qi-1…q1) = P(qi|qi-1)
假设2：不动性假设（状态与具体时间无关） P(qi+1|qi) = P(qj+1|qj)，对任意i，j成立
假设3：输出独立性假设（输出仅与当前状态有关） p(O1,...,OT | q1,...,qT) = Πp(Ot | qt)
2021/2/2
8
HMM定义
一个隐马尔可夫模型 (HMM) 是由一个五元组描述的：
λ ＝（ N，M ，A，B， π ）
其中： N = {q1,...qN}：状态的有限集合 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)：初始状态概率分布
则
2021/2/2
23
算法过程
2021/2/2
24
HMM的网格结构
2021/2/2
25
前向算法过程演示