隐马尔科夫模型(原理图解)
隐马尔可夫模型原理图解
Hidden Markov Models
张庆科
山东大学高性能计算与大数据处理学科组
High Performance Computing and Big Data Processing Group
提 纲
1 2
Markov Model Model Hidden Markov
隐马尔科夫模型的三个问题
t=1 系统状态数目(N=3)
t=2
t=3
t=4
t=5
S1
a11 a13 a12
S1
a11 a12
S1
a11 a12
S1
a11 a12
S1
S1 S2 S3
晴
阴
a21 S2 a22 a23 a31
S3
a21 S2 a22 a23
a21 S2 a22 a23
a21 S2 a22 a23
S2
雨
a32 a33
a1N a2 N aNN
E
法
a0N
aN1 aN2 (4) a 1 04 SN S3 aNN S 4 a05
1 (5)
O1 S5 O 2
a32 2 (4) SN a33
S4
3 (4)
SN
a32T (4) a33 S SN
4
aT4
aT5
BN *M
2 (5)
S5 O 3
3 (5)
S5 OT-1
T (5)
S5 OT
b11 12 1M b b b2 M 21 22 bN 1 bN 2 bNM
…S 2…S 3Leabharlann S4a12T (2)
S2
aT1
AN *N
aT2 a21 z S 3 (3) S2 a22 T (3) S 2 2 aT3 a23
S3
a11 a12 a a 21 22 aN 1 aN 2
A转移概率矩阵
…
S1 1
S1
N
π
S2 2
S2
AN *N
a11 a12 a aS2 21 22 aN 1 aN 2
A转移概率矩阵
a1N … S2 a2 N aNN
S2 2
a23
S3 S3
a31
… …
Q1
观 测 状 态
Q2
QM QM
t=1
…
SN
aN 1
Q Q1 1 Q2
…
SN
Q1 Q2
…
SN
状态序列≠观测序列
Q1 Q2
…
SN
…
SN
…
SN
H M M
… … … …
Q Q1 1 Q2
Q1 Q2 一般随机过程 观察状态序列
…
…
QM
t=2
…
QM
t=3
…
QM
t=T-1
…
QM
t=T
后 向 算 B生成概率矩阵 法 b b
P(O | )
1 (k ) a0k bk (o1 )
8
…
问题本质:计算产生观测序列O的所有可能的状态序列对应的概率之和
QST
…
…
…
…
…
Pr(O,Q | )= Pr(O, 路径Q |)+Pr(O, 路径Q |)+
t=1 t=2
aN1 a04
1 (3)
2 (3)
S S3 2
3 (3)
S3 S2
T (3)
S3
S S3 2
z S S 2 2
a3-0 a4-0
a11 a12 a a 21 22 aN 1 aN 2
E
A转移概率矩阵
qt
t时刻
q1
T=1
q2
T=2
q3
T=3
…
qt-1
t-1时刻
qt
t 时刻
3
山东大学高性能计算与大数据处理学科组
3. 隐马尔可夫模型
t=1 t=2 t=3 t=T-1 t=T
S1
隐 藏 状 态
S1 S2
S1 S2
S1 S2 S3
… …
S1 S2 S3
S1 S1 2 S3 马儿科夫过程 隐藏状态序列
S2 S3
1 (N)
SN
t 1 (N)
SN
t (N)
……
bk (ot )
a N 0
SN T (N)
O1
Ot-1
Ot
……
OT
P(O| ) T (k) ak 0
k 1 N
前进
N t (k ) t 1 (l ) alk bk (ot ) l 1
St=T-1 1
S1t=T
S1
a01 a02
1 (2) S
S2
1
2 (2)
S2
S1
3 (2)
a01
…
…
S2
S1 1
T (2) S
S2
1
a1-0 a2-0
AN *N
a01 a π 02 viterbi 算法 a0 N
a02
B
S2
a03
概率计算问题
路径预测问题
参数学习问题
3
总结
1
山东大学高性能计算与大数据处理学科组
1马尔可夫模型
马尔可夫模型是数学中具有马尔可夫性质的离散时间随机过程,是用于描述随机
过程统计特征的概率模型。
t=1 t=2 t=3 t=T-1 t=T
S1 S1 S2 S2 S3 S3 S2 S1 S1 S2 S3
b2(Q2) O2
II-观察序列
Q3
•
从某时刻状态到下时刻的状态按一定概率转移
•
下时期状态只取决于当前时期状态和转移概率
aij P(qt S j | qt 1 Si )
qt-1
t-1时刻
5
P(qt S j | qt 1 Si , qt 2 Sk , ) P(qt S j | qt 1 Si )
a10
S1
1 (1)
…… ……
S1
t 1 (1)
a1k ak k
S1
t (1)
…… ……
S1
a01
0
…
Sk
…
…
t (k )
a0k
a0 N
1 (k )
Sk
Sk
Sk
ak 0
0
P(O | )
…
1 (k ) a0k bk (o1 )
…
SN
…
……
bk (o1 )
aN k
B生成概率矩阵
…
…
…
…
SN
SN
OT
…
HMM模型五元组表示:λ =( N, M, π , A, B)用来描述HMM,或简写为 λ =(π , A, B)
6
…
…
…
…
OM
…
山东大学高性能计算与大数据处理学科组
提 纲
1 2
Hidden Markov Model 隐马尔科夫模型的三个问题
概率计算问题
路径预测问题
T (N)
Ot
后退
N
Ot+1
OT
t (k ) ak l bl (ot 1 ) t 1 (l )
l 1
T (k ) ak 0 bk (oT )
10
山东大学高性能计算与大数据处理学科组
提 纲
1 2
Hidden Markov Model 隐马尔科夫模型的三个问题
概率计算问题
参数学习问题
3
总结
7
山东大学高性能计算与大数据处理学科组
1. 隐马尔可夫模型-全概率计算 问题1:给定观察序列O=O1,O2, …,OT,以及模型λ=(π,A,B),计算P(O|λ)?
t=1
Π:初始概率向 量
1 (1)
t=2
2 (1)
t=3
3 (1)
S1
t=T-1
T (1)
t=T
…
4
山东大学高性能计算与大数据处理学科组
4. 隐马尔可夫模型(Hidden Markov Models,HMM)
一阶隐马尔可夫模型(Hidden Markov Models)图解
t=1
转移概率
t=2
t=3
t=4
t=5
S1
a11 a13 a12
S1
a11 a12
S S1 1
a11 a12
S1 1
a11 a12
山东大学高性能计算与大数据处理学科组
2. 概率计算问题:前向算法(Forward Algorithm) 问题1:给定观察序列O=O1,O2, …,OT,以及模型λ=(π,A,B),如何计算P(O|λ)? 初始化阶段(t = 1)
1
中间递归阶段(t = 2,…,T)
t-1 t T
结束阶段
T (1)
前进
N=5, T=100, => 计算量3000
9
山东大学高性能计算与大数据处理学科组
3. 概率计算问题:后向算法(Forward Algorithm) 问题1:给定观察序列O=O1,O2, …,OT,以及模型λ=(π,A,B),如何计算P(O|λ)? 结束阶段
1
中间递归阶段(t = T-1,…, 2,1)