隐马尔可夫模型 (HMM) 是一种概率图模型。
我们知道，机器学习模型可以从频率派和贝叶斯派两个方向考虑，
如图，概率图模型最基本的模型可以分为
在这些基本的模型上，如果样本之间存在关联，可以认为样本中附带了时序信息(不一定是时间，是一个表示先后的量即可），从而样本之间不独立全同分布的，这种模型就叫做动态模型，隐变量随着时间发生变化，于是观测变量也发生变化。
根据状态变量（隐变量）的特点，可以分为：
动态模型从横向看是一个时间序列，纵向看是一个混合模型：
下面的内容将分为以下三个部分进行叙述：
HMM 用概率图表示为：
| 符号 | 解释 |
|---|---|
| λ = ( π , A , B ) \lambda=(\pi,A,B) λ=(π,A,B) | 一个表示模型的参数 |
| π \pi π | 初始时刻的概率分布 |
| A A A | 状态转移矩阵 |
| B B B | 发射矩阵，观测概率矩阵 |
更进一步：
在 HMM 中，有两个基本假设：
齐次 Markov假设（当前状态仅与前一状态有关）：
p
(
i
t
+
1
∣
i
t
,
i
t
−
1
,
⋯
,
i
1
,
o
t
,
o
t
−
1
,
⋯
,
o
1
)
=
p
(
i
t
+
1
∣
i
t
)
(1)
p(i_{t+1}|i_t,i_{t-1},\cdots,i_1,o_t,o_{t-1},\cdots,o_1)=p(i_{t+1}|i_t) \tag{1}
p(it+1∣it,it−1,⋯,i1,ot,ot−1,⋯,o1)=p(it+1∣it)(1)
观测独立假设（当前的观测变量只与当前的状态变量有关）：
p
(
o
t
∣
i
t
,
i
t
−
1
,
⋯
,
i
1
,
o
t
−
1
,
⋯
,
o
1
)
=
p
(
o
t
∣
i
t
)
(2)
p(o_t|i_t,i_{t-1},\cdots,i_1,o_{t-1},\cdots,o_1)=p(o_t|i_t) \tag{2}
p(ot∣it,it−1,⋯,i1,ot−1,⋯,o1)=p(ot∣it)(2)
p ( O ∣ λ ) = ∑ I p ( I , O ∣ λ ) = ∑ I p ( O ∣ I , λ ) p ( I ∣ λ ) p(O|\lambda)=\sum\limits_{I}p(I,O|\lambda)=\sum\limits_{I}p(O|I,\lambda)p(I|\lambda) p(O∣λ)=I∑p(I,O∣λ)=I∑p(O∣I,λ)p(I∣λ)
p ( I ∣ λ ) = p ( i 1 , i 2 , ⋯ , i t ∣ λ ) = p ( i t ∣ i 1 , i 2 , ⋯ , i t − 1 , λ ) p ( i 1 , i 2 , ⋯ , i t − 1 ∣ λ ) p(I|\lambda)=p(i_1,i_2,\cdots,i_t|\lambda)=p(i_t|i_1,i_2,\cdots,i_{t-1},\lambda)p(i_1,i_2,\cdots,i_{t-1}|\lambda) p(I∣λ)=p(i1,i2,⋯,it∣λ)=p(it∣i1,i2,⋯,it−1,λ)p(i1,i2,⋯,it−1∣λ)
根据齐次 Markov 假设：
p
(
i
t
∣
i
1
,
i
2
,
⋯
,
i
t
−
1
,
λ
)
=
p
(
i
t
∣
i
t
−
1
)
=
a
i
t
−
1
i
t
p(i_t|i_1,i_2,\cdots,i_{t-1},\lambda)=p(i_t|i_{t-1})=a_{i_{t-1}i_t}
p(it∣i1,i2,⋯,it−1,λ)=p(it∣it−1)=ait−1it
所以：
p
(
I
∣
λ
)
=
π
1
∏
t
=
2
T
a
i
t
−
1
,
i
t
p(I|\lambda)=\pi_1\prod\limits_{t=2}^Ta_{i_{t-1},i_t}
p(I∣λ)=π1t=2∏Tait−1,it
又由于：
p
(
O
∣
I
,
λ
)
=
∏
t
=
1
T
b
i
t
(
o
t
)
p(O|I,\lambda)=\prod\limits_{t=1}^Tb_{i_t}(o_t)
p(O∣I,λ)=t=1∏Tbit(ot)
于是：
p
(
O
∣
λ
)
=
∑
I
π
i
1
∏
t
=
2
T
a
i
t
−
1
,
i
t
∏
t
=
1
T
b
i
t
(
o
t
)
p(O|\lambda)=\sum\limits_{I}\pi_{i_1}\prod\limits_{t=2}^Ta_{i_{t-1},i_t}\prod\limits_{t=1}^Tb_{i_t}(o_t)
p(O∣λ)=I∑πi1t=2∏Tait−1,itt=1∏Tbit(ot)
我们看到，上面的式子中的求和符号是对所有的观测变量求和，于是复杂度为
O
(
N
T
)
O(N^T)
O(NT)。
下面，记
α
t
(
i
)
=
p
(
o
1
,
o
2
,
⋯
,
o
t
,
i
t
=
q
i
∣
λ
)
\alpha_t(i)=p(o_1,o_2,\cdots,o_t,i_t=q_i|\lambda)
αt(i)=p(o1,o2,⋯,ot,it=qi∣λ)，所以，
α
T
(
i
)
=
p
(
O
,
i
T
=
q
i
∣
λ
)
\alpha_T(i)=p(O,i_T=q_i|\lambda)
αT(i)=p(O,iT=qi∣λ)。我们看到：
p
(
O
∣
λ
)
=
∑
i
=
1
N
p
(
O
,
i
T
=
q
i
∣
λ
)
=
∑
i
=
1
N
α
T
(
i
)
p(O|\lambda)=\sum\limits_{i=1}^Np(O,i_T=q_i|\lambda)=\sum\limits_{i=1}^N\alpha_T(i)
p(O∣λ)=i=1∑Np(O,iT=qi∣λ)=i=1∑NαT(i)
对
α
t
+
1
(
j
)
\alpha_{t+1}(j)
αt+1(j)：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲\alpha_{t+1}(j)…
利用观测独立假设：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲\alpha_{t+1}(j)…
上面利用了齐次 Markov 假设得到了一个递推公式，这个算法叫做前向算法。
还有一种算法叫做后向算法，定义
β
t
(
i
)
=
p
(
o
t
+
1
,
o
t
+
1
,
⋯
，
o
T
∣
i
t
=
i
,
λ
)
\beta_t(i)=p(o_{t+1},o_{t+1},\cdots，o_T|i_t=i,\lambda)
βt(i)=p(ot+1,ot+1,⋯，oT∣it=i,λ)：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲p(O|\lambda)&=p…
对于这个
β
1
(
i
)
\beta_1(i)
β1(i)：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲\beta_t(i)&=p(o…
于是后向地得到了第一项。
为了学习得到参数的最优值，在 MLE 中：
λ
M
L
E
=
a
r
g
m
a
x
λ
p
(
O
∣
λ
)
\lambda_{MLE}=\mathop{argmax}_\lambda p(O|\lambda)
λMLE=argmaxλp(O∣λ)
我们采用 EM 算法（在这里也叫 Baum Welch 算法），用上标表示迭代：
θ
t
+
1
=
a
r
g
m
a
x
θ
∫
z
log
p
(
X
,
Z
∣
θ
)
p
(
Z
∣
X
,
θ
t
)
d
z
\theta^{t+1}=\mathop{argmax}_{\theta}\int_z\log p(X,Z|\theta)p(Z|X,\theta^t)dz
θt+1=argmaxθ∫zlogp(X,Z∣θ)p(Z∣X,θt)dz
其中，
X
X
X 是观测变量，
Z
Z
Z 是隐变量序列。于是：
λ
t
+
1
=
a
r
g
m
a
x
λ
∑
I
log
p
(
O
,
I
∣
λ
)
p
(
I
∣
O
,
λ
t
)
=
a
r
g
m
a
x
λ
∑
I
log
p
(
O
,
I
∣
λ
)
p
(
O
,
I
∣
λ
t
)
\lambda^{t+1}=\mathop{argmax}_\lambda\sum\limits_I\log p(O,I|\lambda)p(I|O,\lambda^t)\\ =\mathop{argmax}_\lambda\sum\limits_I\log p(O,I|\lambda)p(O,I|\lambda^t)
λt+1=argmaxλI∑logp(O,I∣λ)p(I∣O,λt)=argmaxλI∑logp(O,I∣λ)p(O,I∣λt)
这里利用了
p
(
O
∣
λ
t
)
p(O|\lambda^t)
p(O∣λt) 和
λ
\lambda
λ 无关。将 Evaluation 中的式子代入：
∑
I
log
p
(
O
,
I
∣
λ
)
p
(
O
,
I
∣
λ
t
)
=
∑
I
[
log
π
i
1
+
∑
t
=
2
T
log
a
i
t
−
1
,
i
t
+
∑
t
=
1
T
log
b
i
t
(
o
t
)
]
p
(
O
,
I
∣
λ
t
)
\sum\limits_I\log p(O,I|\lambda)p(O,I|\lambda^t)=\sum\limits_I[\log \pi_{i_1}+\sum\limits_{t=2}^T\log a_{i_{t-1},i_t}+\sum\limits_{t=1}^T\log b_{i_t}(o_t)]p(O,I|\lambda^t)
I∑logp(O,I∣λ)p(O,I∣λt)=I∑[logπi1+t=2∑Tlogait−1,it+t=1∑Tlogbit(ot)]p(O,I∣λt)
对
π
t
+
1
\pi^{t+1}
πt+1：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲\pi^{t+1}&=\mat…
上面的式子中，对
i
2
,
i
2
,
⋯
,
i
T
i_2,i_2,\cdots,i_T
i2,i2,⋯,iT 求和可以将这些参数消掉：
π
t
+
1
=
a
r
g
m
a
x
π
∑
i
1
[
log
π
i
1
⋅
p
(
O
,
i
1
∣
λ
t
)
]
\pi^{t+1}=\mathop{argmax}_\pi\sum\limits_{i_1}[\log \pi_{i_1}\cdot p(O,i_1|\lambda^t)]
πt+1=argmaxπi1∑[logπi1⋅p(O,i1∣λt)]
上面的式子还有对
π
\pi
π 的约束
∑
i
π
i
=
1
\sum\limits_i\pi_i=1
i∑πi=1。定义 Lagrange 函数：
L
(
π
,
η
)
=
∑
i
=
1
N
log
π
i
⋅
p
(
O
,
i
1
=
q
i
∣
λ
t
)
+
η
(
∑
i
=
1
N
π
i
−
1
)
L(\pi,\eta)=\sum\limits_{i=1}^N\log \pi_i\cdot p(O,i_1=q_i|\lambda^t)+\eta(\sum\limits_{i=1}^N\pi_i-1)
L(π,η)=i=1∑Nlogπi⋅p(O,i1=qi∣λt)+η(i=1∑Nπi−1)
于是：
∂
L
∂
π
i
=
1
π
i
p
(
O
,
i
1
=
q
i
∣
λ
t
)
+
η
=
0
\frac{\partial L}{\partial\pi_i}=\frac{1}{\pi_i}p(O,i_1=q_i|\lambda^t)+\eta=0
∂πi∂L=πi1p(O,i1=qi∣λt)+η=0
对上式求和：
∑
i
=
1
N
p
(
O
,
i
1
=
q
i
∣
λ
t
)
+
π
i
η
=
0
⇒
η
=
−
p
(
O
∣
λ
t
)
\sum\limits_{i=1}^Np(O,i_1=q_i|\lambda^t)+\pi_i\eta=0\Rightarrow\eta=-p(O|\lambda^t)
i=1∑Np(O,i1=qi∣λt)+πiη=0⇒η=−p(O∣λt)
所以：
π
i
t
+
1
=
p
(
O
,
i
1
=
q
i
∣
λ
t
)
p
(
O
∣
λ
t
)
\pi_i^{t+1}=\frac{p(O,i_1=q_i|\lambda^t)}{p(O|\lambda^t)}
πit+1=p(O∣λt)p(O,i1=qi∣λt)
Decoding 问题表述为：
I
=
a
r
g
m
a
x
I
p
(
I
∣
O
,
λ
)
I=\mathop{argmax}\limits_{I}p(I|O,\lambda)
I=Iargmaxp(I∣O,λ)
我们需要找到一个序列，其概率最大，这个序列就是在参数空间中的一个路径，可以采用动态规划的思想。
定义：
δ
t
(
j
)
=
max
i
1
,
⋯
,
i
t
−
1
p
(
o
1
,
⋯
,
o
t
,
i
1
,
⋯
,
i
t
−
1
,
i
t
=
q
i
)
\delta_{t}(j)=\max\limits_{i_1,\cdots,i_{t-1}}p(o_1,\cdots,o_t,i_1,\cdots,i_{t-1},i_t=q_i)
δt(j)=i1,⋯,it−1maxp(o1,⋯,ot,i1,⋯,it−1,it=qi)
于是：
δ
t
+
1
(
j
)
=
max
1
≤
i
≤
N
δ
t
(
i
)
a
i
j
b
j
(
o
t
+
1
)
\delta_{t+1}(j)=\max\limits_{1\le i\le N}\delta_t(i)a_{ij}b_j(o_{t+1})
δt+1(j)=1≤i≤Nmaxδt(i)aijbj(ot+1)
这个式子就是从上一步到下一步的概率再求最大值。记这个路径为：
ψ
t
+
1
(
j
)
=
a
r
g
m
a
x
1
≤
i
≤
N
δ
t
(
i
)
a
i
j
\psi_{t+1}(j)=\mathop{argmax}\limits_{1\le i\le N}\delta_t(i)a_{ij}
ψt+1(j)=1≤i≤Nargmaxδt(i)aij
HMM 是一种动态模型，是由混合树形模型和时序结合起来的一种模型（类似 GMM + Time）。对于类似 HMM 的这种状态空间模型，普遍的除了学习任务（采用 EM ）外，还有推断任务，推断任务包括：
译码 Decoding： p ( z 1 , z 2 , ⋯ , z t ∣ x 1 , x 2 , ⋯ , x t ) p(z_1,z_2,\cdots,z_t|x_1,x_2,\cdots,x_t) p(z1,z2,⋯,zt∣x1,x2,⋯,xt)
似然概率： p ( X ∣ θ ) p(X|\theta) p(X∣θ)
滤波：
p
(
z
t
∣
x
1
,
⋯
,
x
t
)
p(z_t|x_1,\cdots,x_t)
p(zt∣x1,⋯,xt)，Online
p
(
z
t
∣
x
1
:
t
)
=
p
(
x
1
:
t
,
z
t
)
p
(
x
1
:
t
)
=
C
α
t
(
z
t
)
p(z_t|x_{1:t})=\frac{p(x_{1:t},z_t)}{p(x_{1:t})}=C\alpha_t(z_t)
p(zt∣x1:t)=p(x1:t)p(x1:t,zt)=Cαt(zt)
平滑：
p
(
z
t
∣
x
1
,
⋯
,
x
T
)
p(z_t|x_1,\cdots,x_T)
p(zt∣x1,⋯,xT)，Offline
p
(
z
t
∣
x
1
:
T
)
=
p
(
x
1
:
T
,
z
t
)
p
(
x
1
:
T
)
=
α
t
(
z
t
)
p
(
x
t
+
1
:
T
∣
x
1
:
t
,
z
t
)
p
(
x
1
:
T
)
p(z_t|x_{1:T})=\frac{p(x_{1:T},z_t)}{p(x_{1:T})}=\frac{\alpha_t(z_t)p(x_{t+1:T}|x_{1:t},z_t)}{p(x_{1:T})}
p(zt∣x1:T)=p(x1:T)p(x1:T,zt)=p(x1:T)αt(zt)p(xt+1:T∣x1:t,zt)
根据概率图的条件独立性，有：
p
(
z
t
∣
x
1
:
T
)
=
α
t
(
z
t
)
p
(
x
t
+
1
:
T
∣
z
t
)
p
(
x
1
:
T
)
=
C
α
t
(
z
t
)
β
t
(
z
t
)
p(z_t|x_{1:T})=\frac{\alpha_t(z_t)p(x_{t+1:T}|z_t)}{p(x_{1:T})}=C\alpha_t(z_t)\beta_t(z_t)
p(zt∣x1:T)=p(x1:T)αt(zt)p(xt+1:T∣zt)=Cαt(zt)βt(zt)
这个算法叫做前向后向算法。
预测：
p
(
z
t
+
1
,
z
t
+
2
∣
x
1
,
⋯
,
x
t
)
,
p
(
x
t
+
1
,
x
t
+
2
∣
x
1
,
⋯
,
x
t
)
p(z_{t+1},z_{t+2}|x_1,\cdots,x_t),p(x_{t+1},x_{t+2}|x_1,\cdots,x_t)
p(zt+1,zt+2∣x1,⋯,xt),p(xt+1,xt+2∣x1,⋯,xt)
p
(
z
t
+
1
∣
x
1
:
t
)
=
∑
z
t
p
(
z
t
+
1
,
z
t
∣
x
1
:
t
)
=
∑
z
t
p
(
z
t
+
1
∣
z
t
)
p
(
z
t
∣
x
1
:
t
)
p(z_{t+1}|x_{1:t})=\sum_{z_t}p(z_{t+1},z_t|x_{1:t})=\sum\limits_{z_t}p(z_{t+1}|z_t)p(z_t|x_{1:t})
p(zt+1∣x1:t)=zt∑p(zt+1,zt∣x1:t)=zt∑p(zt+1∣zt)p(zt∣x1:t)
p ( x t + 1 ∣ x 1 : t ) = ∑ z t + 1 p ( x t + 1 , z t + 1 ∣ x 1 : t ) = ∑ z t + 1 p ( x t + 1 ∣ z t + 1 ) p ( z t + 1 ∣ x 1 : t ) p(x_{t+1}|x_{1:t})=\sum\limits_{z_{t+1}}p(x_{t+1},z_{t+1}|x_{1:t})=\sum\limits_{z_{t+1}}p(x_{t+1}|z_{t+1})p(z_{t+1}|x_{1:t}) p(xt+1∣x1:t)=zt+1∑p(xt+1,zt+1∣x1:t)=zt+1∑p(xt+1∣zt+1)p(zt+1∣x1:t)
A. Markov的齐次性与阶数
