- 1. 基本思想
- 2. 三个基本问题与求解
- 2.1 似然计算
- 2.2 最可能序列
- 2.3 EM问题
隐马尔可夫模型是一种常用于处理时间序列的概率图模型，其概率图如下图所示，其中
s
I
s_I
sI是隐状态，
y
i
y_i
yi是观测变量；
p
(
s
i
∣
s
i
−
1
)
p(s_i|s_{i-1})
p(si∣si−1)是概率转移，
p
(
y
i
∣
s
i
)
p(y_i|s_i)
p(yi∣si)是观测概率。
根据概率图的计算公式，很容易得出两组变量的联合分布：
2. 三个基本问题与求解 2.1 似然计算
问题：给定参数集
θ
theta
θ和观测序列{
y
1
,
y
2
,
.
.
.
,
y
m
y_1,y_2,...,y_m
y1,y2,...,ym}，如何高效计算似然
p
(
Y
∣
θ
)
p(Y|theta)
p(Y∣θ)的概率？
分析：如果采用扩充法扩充出所有变量地联合概率，复杂度是
O
(
∣
S
∣
n
)
O(|S|^n)
O(∣S∣n)，计算复杂度较高。考虑采用递推法将复杂度降为
O
(
n
∣
S
∣
)
O(n|S|)
O(n∣S∣)
得到如下的递推式
问题：给定参数
θ
theta
θ和观测集
Y
Y
Y，求最可能的状态序列
X
X
X
分析：即
a
r
g
m
a
x
X
argmax_X
argmaxX
p
(
X
∣
Y
,
θ
)
p(X|Y,theta)
p(X∣Y,θ),
只要将上面的递推式的求和号改为argmax即可，这就是维特比算法
寻找最好的
θ
theta
θ使得
p
(
Y
∣
θ
)
p(Y|theta)
p(Y∣θ)最大，由于隐变量X未知所以采用EM算法
EM算法分为E步和M步
1）E步：计算概率
p
(
X
∣
Y
,
θ
i
−
1
)
p(X|Y,theta^{i-1})
p(X∣Y,θi−1)
2) M步:
max
θ
Q
(
θ
)
max_theta {Q(theta)}
maxθQ(θ),
Q
(
θ
)
=
∑
y
∑
x
p
(
x
∣
y
,
θ
i
−
1
)
l
o
g
p
(
y
,
x
,
θ
i
)
Q(theta)=sum_ysum_xp(x|y,theta^{i-1})logp(y,x,theta^i)
Q(θ)=∑y∑xp(x∣y,θi−1)logp(y,x,θi)
