前面简单介绍了
隐马尔科夫模型
，下面继续看看HMM的三个基本问题。
问题一、评估观察序列概率
问题描述：假设我们已知HMM模型的参数
λ
=
(
A
,
B
,
Π
)
\lambda = (A, B, \Pi)
λ
=
(
A
,
B
,
Π
)
，其中A是隐藏状态转移概率的矩阵，B是观测状态生成概率的矩阵，
Π
\Pi
Π
是隐藏状态的初始概率分布。同时给定一个观测序列
O
=
{
o
1
,
o
2
,
.
.
.
o
T
}
O =\{o_1,o_2,…o_T\}
O
=
{
o
1
,
o
2
,
.
.
.
o
T
}
，现在我们要求这个观测序列?在模型?下出现的条件概率
P
(
O
∣
λ
)
P(O|\lambda)
P
(
O
∣
λ
)
。
1. 暴力求解法
我们可以列举出所有可能出现的长度为T的隐藏序列
I
=
{
i
1
,
i
2
,
.
.
.
,
i
T
}
I = \{i_1,i_2,…,i_T\}
I
=
{
i
1
,
i
2
,
.
.
.
,
i
T
}
，分别求出这些隐藏序列与观测序列O的联合概率分布
P
(
O
,
I
∣
λ
)
P(O,I|\lambda)
P
(
O
,
I
∣
λ
)
，这样我们就可以很容易的求出边缘分布
P
(
O
∣
λ
)
P(O|\lambda)
P
(
O
∣
λ
)
了，也就是我们要求的观测序列
O
O
O
在模型
λ
\lambda
λ
下出现的条件概率
P
(
O
∣
λ
)
P(O|\lambda)
P
(
O
∣
λ
)
。
(1) 首先，任意一个隐藏序列
I
=
{
i
1
,
i
2
,
.
.
.
,
i
T
}
I = \{i_1,i_2,…,i_T\}
I
=
{
i
1
,
i
2
,
.
.
.
,
i
T
}
出现的概率是
P
(
I
∣
λ
)
P(I|\lambda)
P
(
I
∣
λ
)
(2) 对于固定的状态序列
I
I
I
，我们要求的观察序列
O
O
O
出现的概率是：
P
(
O
∣
I
,
λ
)
P(O|I, \lambda)
P
(
O
∣
I
,
λ
)
， 则
I
I
I
和
O
O
O
联合出现的概率是：
P
(
O
,
I
∣
λ
)
=
P
(
I
∣
λ
)
P
(
O
∣
I
,
λ
)
P(O,I|\lambda) = P(I|\lambda)P(O|I, \lambda)
P
(
O
,
I
∣
λ
)
=
P
(
I
∣
λ
)
P
(
O
∣
I
,
λ
)
(3) 然后求边缘概率分布，即可得到观测序列
O
O
O
在模型
λ
\lambda
λ
下出现的条件概率：
P
(
O
∣
λ
)
=
∑
I
P
(
O
,
I
∣
λ
)
P(O|\lambda) = \sum\limits_{I}P(O,I|\lambda)
P
(
O
∣
λ
)
=
I
∑
P
(
O
,
I
∣
λ
)
虽然上述方法有效，但是如果我们的隐藏状态数?非常多的那就麻烦了，此时我们预测状态有
N
T
N^T
N
T
种组合，算法的时间复杂度是
O
(
T
N
T
)
O(TN^T)
O
(
T
N
T
)
阶的。因此对于一些隐藏状态数极少的模型，我们可以用暴力求解法来得到观测序列出现的概率，但是如果隐藏状态多，则上述算法太耗时，我们需要寻找其他简洁的算法。
前向后向算法就是来帮助我们在较低的时间复杂度情况下求解这个问题的。
2. 前向算法
前向算法本质上属于动态规划的算法，也就是我们要通过找到局部状态递推的公式，这样一步步的
从子问题的最优解拓展到整个问题的最优解
。
在前向算法中，通过定义
“前向概率”
来定义动态规划的这个局部状态。什么是前向概率呢, 其实定义很简单：假定t时刻隐藏状态为
q
i
q_i
q
i
，且观测状态序列为
o
1
,
o
2
,
.
.
.
o
t
o_1,o_2,…o_t
o
1
,
o
2
,
.
.
.
o
t
的概率就是
前向概率
，并记为：
α
t
(
i
)
=
P
(
o
1
,
o
2
,
.
.
.
o
t
,
h
t
=
q
i
∣
λ
)
\alpha_t(i) = P(o_1,o_2,…o_t, h_t =q_i | \lambda)
α
t
(
i
)
=
P
(
o
1
,
o
2
,
.
.
.
o
t
,
h
t
=
q
i
∣
λ
)
。
递推关系式如下：
α
t
+
1
(
j
)
=
∑
i
=
1
N
α
t
(
i
)
a
i
j
b
j
(
o
t
+
1
)
\alpha_{t+1}(j) = \sum\limits_{i=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})
α
t
+
1
(
j
)
=
i
=
1
∑
N
α
t
(
i
)
a
i
j
b
j
(
o
t
+
1
)
我们的动态规划从时刻1开始，到时刻T结束，由于
α
T
(
i
)
\alpha_T(i)
α
T
(
i
)
表示在时刻 T 观测序列为
o
1
,
o
2
,
.
.
.
o
T
o_1,o_2,…o_T
o
1
,
o
2
,
.
.
.
o
T
并且时刻T隐藏状态
q
i
q_i
q
i
的概率。因此我们只要将所有隐藏状态对应的概率相加，即
∑
i
=
1
N
α
T
(
i
)
\sum\limits_{i=1}^N\alpha_T(i)
i
=
1
∑
N
α
T
(
i
)
就得到了在时刻T观测序列为
o
1
,
o
2
,
.
.
.
o
T
o_1,o_2,…o_T
o
1
,
o
2
,
.
.
.
o
T
的概率，也就是我们要求的这个观测序列
O
O
O
在模型
λ
\lambda
λ
下出现的条件概率
P
(
O
∣
λ
)
P(O|\lambda)
P
(
O
∣
λ
)
。
总结下
前向算法的全部过程
：
输入：HMM模型
λ
=
(
A
,
B
,
Π
)
\lambda=(A,B,\Pi)
λ
=
(
A
,
B
,
Π
)
，观测序列
o
1
,
o
2
,
.
.
.
o
T
o_1,o_2,…o_T
o
1
,
o
2
,
.
.
.
o
T
输出：观测序列概率
P
(
O
∣
λ
)
P(O|\lambda)
P
(
O
∣
λ
)
(1) 计算时刻1的
各个隐藏状态
前向概率：
α
1
(
i
)
=
π
i
b
i
(
o
1
)
,
i
=
1
,
2
,
.
.
.
N
\alpha_1(i) = \pi_ib_i(o_1),\; i=1,2,…N
α
1
(
i
)
=
π
i
b
i
(
o
1
)
,
i
=
1
,
2
,
.
.
.
N
，
π
i
\pi_i
π
i
是时刻时刻1隐藏状态为i的概率，
b
i
(
o
1
)
b_i(o_1)
b
i
(
o
1
)
是观测状态为
o
1
o_1
o
1
的概率，
α
1
(
i
)
\alpha_1(i)
α
1
(
i
)
是时刻1状态为i的前向概率。
其实就是i取1,2,...,N，要计算所有状态的前向概率
。
(2) 递推时刻2,3,…T时刻
各个隐藏状态
的前向概率：
α
t
+
1
(
i
)
=
∑
i
=
1
N
α
t
(
i
)
a
i
j
b
j
(
o
t
+
1
)
,
i
=
1
,
2
,
.
.
.
N
\alpha_{t+1}(i) = \sum\limits_{i=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1}),\; i=1,2,…N
α
t
+
1
(
i
)
=
i
=
1
∑
N
α
t
(
i
)
a
i
j
b
j
(
o
t
+
1
)
,
i
=
1
,
2
,
.
.
.
N
。
这里j也取1,2,...,N，也要计算所有状态的前向概率
。
(3) 计算最终结果：
P
(
O
∣
λ
)
=
∑
i
=
1
N
α
T
(
i
)
P(O|\lambda) = \sum\limits_{i=1}^N\alpha_T(i)
P
(
O
∣
λ
)
=
i
=
1
∑
N
α
T
(
i
)
，
这里相加的是T时刻各隐藏状态的前向概率
。
从递推公式可以看出，我们的算法时间复杂度是
O
(
T
N
2
)
O(TN^2)
O
(
T
N
2
)
，比暴力解法的时间复杂度
O
(
T
N
T
)
O(TN^T)
O
(
T
N
T
)
少了几个数量级。
3. 前向算法实例
以
隐马尔科夫模型简介
中的盒子与球的例子来显示前向概率的计算。
我们的观察集合是:V={红，白}，M=2，我们的状态集合是:Q ={盒子1，盒子2，盒子3}， N=3。而观察序列和状态序列的长度为3。
初始状态分布为：
Π
=
(
0.2
,
0.4
,
0.4
)
T
\Pi = (0.2,0.4,0.4)^T
Π
=
(
0
.
2
,
0
.
4
,
0
.
4
)
T
状态转移概率分布矩阵为：
A
=
(
0.5
0.2
0.3
0.3
0.5
0.2
0.2
0.3
0.5
)
A = \left( \begin{array} {ccc} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.3 &0.5 \end{array} \right)
A
=
⎝
⎛
0
.
5
0
.
3
0
.
2
0
.
2
0
.
5
0
.
3
0
.
3
0
.
2
0
.
5
⎠
⎞
观测状态概率矩阵为：
B
=
(
0.5
0.5
0.4
0.6
0.7
0.3
)
B = \left( \begin{array} {ccc} 0.5 & 0.5 \\ 0.4 & 0.6 \\ 0.7 & 0.3 \end{array} \right)
B
=
⎝
⎛
0
.
5
0
.
4
0
.
7
0
.
5
0
.
6
0
.
3
⎠
⎞
球的颜色的观测序列:O={红，白，红}
按照我们上一节的前向算法。首先计算时刻1三个状态的前向概率：
(1) 时刻1是红色球:
隐藏状态是盒子1的概率为：
α
1
(
1
)
=
π
1
b
1
(
o
1
)
=
0.2
×
0.5
=
0.1
\alpha_1(1) = \pi_1b_1(o_1) = 0.2 \times 0.5 = 0.1
α
1
(
1
)
=
π
1
b
1
(
o
1
)
=
0
.
2
×
0
.
5
=
0
.
1
隐藏状态是盒子2的概率为：
α
1
(
2
)
=
π
2
b
2
(
o
1
)
=
0.4
×
0.4
=
0.16
\alpha_1(2) = \pi_2b_2(o_1) = 0.4 \times 0.4 = 0.16
α
1
(
2
)
=
π
2
b
2
(
o
1
)
=
0
.
4
×
0
.
4
=
0
.
1
6
隐藏状态是盒子3的概率为：
α
1
(
3
)
=
π
3
b
3
(
o
1
)
=
0.4
×
0.7
=
0.28
\alpha_1(3) = \pi_3b_3(o_1) = 0.4 \times 0.7 = 0.28
α
1
(
3
)
=
π
3
b
3
(
o
1
)
=
0
.
4
×
0
.
7
=
0
.
2
8
(2) 现在我们可以开始递推了，首先递推时刻2三个状态的前向概率
时刻2是白色球:
隐藏状态是盒子1的概率为：
α
2
(
1
)
=
[
∑
i
=
1
3
α
1
(
i
)
a
i
1
]
b
1
(
o
2
)
=
[
0.1
∗
0.5
+
0.16
∗
0.3
+
0.28
∗
0.2
]
×
0.5
=
0.077
\alpha_2(1) = \Big[\sum\limits_{i=1}^3\alpha_1(i)a_{i1}\Big]b_1(o_2) = [0.1*0.5+0.16*0.3+0.28*0.2 ] \times 0.5 = 0.077
α
2
(
1
)
=
[
i
=
1
∑
3
α
1
(
i
)
a
i
1
]
b
1
(
o
2
)
=
[
0
.
1
∗
0
.
5
+
0
.
1
6
∗
0
.
3
+
0
.
2
8
∗
0
.
2
]
×
0
.
5
=
0
.
0
7
7
隐藏状态是盒子2的概率为：
α
2
(
2
)
=
[
∑
i
=
1
3
α
1
(
i
)
a
i
2
]
b
2
(
o
2
)
=
[
0.1
∗
0.2
+
0.16
∗
0.5
+
0.28
∗
0.3
]
×
0.6
=
0.1104
\alpha_2(2) = \Big[\sum\limits_{i=1}^3\alpha_1(i)a_{i2}\Big]b_2(o_2) = [0.1*0.2+0.16*0.5+0.28*0.3 ] \times 0.6 = 0.1104
α
2
(
2
)
=
[
i
=
1
∑
3
α
1
(
i
)
a
i
2
]
b
2
(
o
2
)
=
[
0
.
1
∗
0
.
2
+
0
.
1
6
∗
0
.
5
+
0
.
2
8
∗
0
.
3
]
×
0
.
6
=
0
.
1
1
0
4
隐藏状态是盒子3的概率为：
α
2
(
3
)
=
[
∑
i
=
1
3
α
1
(
i
)
a
i
3
]
b
3
(
o
2
)
=
[
0.1
∗
0.3
+
0.16
∗
0.2
+
0.28
∗
0.5
]
×
0.3
=
0.0606
\alpha_2(3) = \Big[\sum\limits_{i=1}^3\alpha_1(i)a_{i3}\Big]b_3(o_2) = [0.1*0.3+0.16*0.2+0.28*0.5 ] \times 0.3 = 0.0606
α
2
(
3
)
=
[
i
=
1
∑
3
α
1
(
i
)
a
i
3
]
b
3
(
o
2
)
=
[
0
.
1
∗
0
.
3
+
0
.
1
6
∗
0
.
2
+
0
.
2
8
∗
0
.
5
]
×
0
.
3
=
0
.
0
6
0
6
(3) 继续递推，现在我们递推时刻3三个状态的前向概率
时刻3是红色球:
隐藏状态是盒子1的概率为：
α
3
(
1
)
=
[
∑
i
=
1
3
α
2
(
i
)
a
i
1
]
b
1
(
o
3
)
=
[
0.077
∗
0.5
+
0.1104
∗
0.3
+
0.0606
∗
0.2
]
×
0.5
=
0.04187
\alpha_3(1) = \Big[\sum\limits_{i=1}^3\alpha_2(i)a_{i1}\Big]b_1(o_3) = [0.077*0.5+0.1104*0.3+0.0606*0.2 ] \times 0.5 = 0.04187
α
3
(
1
)
=
[
i
=
1
∑
3
α
2
(
i
)
a
i
1
]
b
1
(
o
3
)
=
[
0
.
0
7
7
∗
0
.
5
+
0
.
1
1
0
4
∗
0
.
3
+
0
.
0
6
0
6
∗
0
.
2
]
×
0
.
5
=
0
.
0
4
1
8
7
隐藏状态是盒子2的概率为：
α
3
(
2
)
=
[
∑
i
=
1
3
α
2
(
i
)
a
i
2
]
b
2
(
o
3
)
=
[
0.077
∗
0.2
+
0.1104
∗
0.5
+
0.0606
∗
0.3
]
×
0.4
=
0.03551
\alpha_3(2) = \Big[\sum\limits_{i=1}^3\alpha_2(i)a_{i2}\Big]b_2(o_3) = [0.077*0.2+0.1104*0.5+0.0606*0.3 ] \times 0.4 = 0.03551
α
3
(
2
)
=
[
i
=
1
∑
3
α
2
(
i
)
a
i
2
]
b
2
(
o
3
)
=
[
0
.
0
7
7
∗
0
.
2
+
0
.
1
1
0
4
∗
0
.
5
+
0
.
0
6
0
6
∗
0
.
3
]
×
0
.
4
=
0
.
0
3
5
5
1
隐藏状态是盒子3的概率为：
α
3
(
3
)
=
[
∑
i
=
1
3
α
3
(
i
)
a
i
3
]
b
3
(
o
3
)
=
[
0.077
∗
0.3
+
0.1104
∗
0.2
+
0.0606
∗
0.5
]
×
0.7
=
0.05284
\alpha_3(3) = \Big[\sum\limits_{i=1}^3\alpha_3(i)a_{i3}\Big]b_3(o_3) = [0.077*0.3+0.1104*0.2+0.0606*0.5 ] \times 0.7 = 0.05284
α
3
(
3
)
=
[
i
=
1
∑
3
α
3
(
i
)
a
i
3
]
b
3
(
o
3
)
=
[
0
.
0
7
7
∗
0
.
3
+
0
.
1
1
0
4
∗
0
.
2
+
0
.
0
6
0
6
∗
0
.
5
]
×
0
.
7
=
0
.
0
5
2
8
4
(4) 最终我们求出观测序列:O={红，白，红}的概率为：
P
(
O
∣
λ
)
=
∑
i
=
1
3
α
3
(
i
)
=
0.13022
P(O|\lambda) = \sum\limits_{i=1}^3\alpha_3(i) = 0.13022
P
(
O
∣
λ
)
=
i
=
1
∑
3
α
3
(
i
)
=
0
.
1
3
0
2
2
4. 后向算法
后向算法和前向算法非常类似，都是用的动态规划，唯一的区别是选择的局部状态不同，后向算法用的是“后向概率”，那么后向概率是如何定义的呢？
定义时刻t时隐藏状态为
q
i
q_i
q
i
, 从时刻t+1到最后时刻T的观测状态的序列为
o
t
+
1
,
o
t
+
2
,
.
.
.
o
T
o_{t+1},o_{t+2},…o_T
o
t
+
1
,
o
t
+
2
,
.
.
.
o
T
的概率为
后向概率
。记为：
β
t
(
i
)
=
P
(
o
t
+
1
,
o
t
+
2
,
.
.
.
o
T
∣
h
t
=
q
i
,
λ
)
\beta_t(i) = P(o_{t+1},o_{t+2},…o_T| h_t =q_i , \lambda)
β
t
(
i
)
=
P
(
o
t
+
1
,
o
t
+
2
,
.
.
.
o
T
∣
h
t
=
q
i
,
λ
)
后向概率的动态规划递推公式和前向概率是相反的:
-
现在我们假设我们已经找到了在时刻t+1时各个隐藏状态的后向概率。
βt
+
1
(
j
)
\beta_{t+1}(j)
β
t
+
1
(
j
)
，现在我们需要
递推出时刻t时各个隐藏状态的后向概率
。 -
如下图，我们可以计算出观测状态的序列为
ot
+
2
,
o
t
+
3
,
.
.
.
o
T
o_{t+2},o_{t+3},…o_T
o
t
+
2
,
o
t
+
3
,
.
.
.
o
T
， 且t时刻隐藏状态为
qi
q_i
q
i
, t+1时刻隐藏状态为
qj
q_j
q
j
的概率为
ai
j
β
t
+
1
(
j
)
a_{ij}\beta_{t+1}(j)
a
i
j
β
t
+
1
(
j
)
。 -
接着可以得到观测状态的序列为
ot
+
1
,
o
t
+
2
,
.
.
.
o
T
o_{t+1},o_{t+2},…o_T
o
t
+
1
,
o
t
+
2
,
.
.
.
o
T
， t时隐藏状态为
qi
q_i
q
i
, 时刻t+1隐藏状态为
qj
q_j
q
j
的概率为
ai
j
b
j
(
o
t
+
1
)
β
t
+
1
(
j
)
a_{ij}b_j(o_{t+1})\beta_{t+1}(j)
a
i
j
b
j
(
o
t
+
1
)
β
t
+
1
(
j
)
, 则把下面所有线对应的概率加起来，我们可以得到观测状态的序列为
ot
+
1
,
o
t
+
2
,
.
.
.
o
T
o_{t+1},o_{t+2},…o_T
o
t
+
1
,
o
t
+
2
,
.
.
.
o
T
， t时隐藏状态为
qi
q_i
q
i
的概率为
∑j
=
1
N
a
i
j
b
j
(
o
t
+
1
)
β
t
+
1
(
j
)
\sum\limits_{j=1}^{N}a_{ij}b_j(o_{t+1})\beta_{t+1}(j)
j
=
1
∑
N
a
i
j
b
j
(
o
t
+
1
)
β
t
+
1
(
j
)
，这个概率即为时刻t的后向概率。
这样我们得到了后向概率的递推关系式如下：
β
t
(
i
)
=
∑
j
=
1
N
a
i
j
b
j
(
o
t
+
1
)
β
t
+
1
(
j
)
\beta_{t}(i) = \sum\limits_{j=1}^{N}a_{ij}b_j(o_{t+1})\beta_{t+1}(j)
β
t
(
i
)
=
j
=
1
∑
N
a
i
j
b
j
(
o
t
+
1
)
β
t
+
1
(
j
)
现在我们总结下后向算法的流程,注意下和前向算法的相同点和不同点：
输入：HMM模型
λ
=
(
A
,
B
,
Π
)
\lambda=(A,B,\Pi)
λ
=
(
A
,
B
,
Π
)
，观测序列
O
=
(
o
1
,
o
2
,
.
.
.
o
T
)
O=(o_1,o_2,…o_T)
O
=
(
o
1
,
o
2
,
.
.
.
o
T
)
输出：观测序列概率
P
(
O
∣
λ
)
P(O|\lambda)
P
(
O
∣
λ
)
(1) 初始化时刻T的各个隐藏状态后向概率：
β
T
(
i
)
=
1
,
i
=
1
,
2
,
.
.
.
N
\beta_T(i) = 1,\; i=1,2,…N
β
T
(
i
)
=
1
,
i
=
1
,
2
,
.
.
.
N
。
注意这里所有状态的后向概率为1
。
(2) 递推时刻T−1,T−2,…1时刻的后向概率：
β
t
(
i
)
=
∑
j
=
1
N
a
i
j
b
j
(
o
t
+
1
)
β
t
+
1
(
j
)
,
i
=
1
,
2
,
.
.
.
N
\beta_{t}(i) = \sum\limits_{j=1}^{N}a_{ij}b_j(o_{t+1})\beta_{t+1}(j),\; i=1,2,…N
β
t
(
i
)
=
j
=
1
∑
N
a
i
j
b
j
(
o
t
+
1
)
β
t
+
1
(
j
)
,
i
=
1
,
2
,
.
.
.
N
(3) 计算最终结果：
P
(
O
∣
λ
)
=
∑
i
=
1
N
π
i
b
i
(
o
1
)
β
1
(
i
)
P(O|\lambda) = \sum\limits_{i=1}^N\pi_ib_i(o_1)\beta_1(i)
P
(
O
∣
λ
)
=
i
=
1
∑
N
π
i
b
i
(
o
1
)
β
1
(
i
)
此时我们的算法时间复杂度仍然是
O
(
T
N
2
)
O(TN^2)
O
(
T
N
2
)
。
5. HMM常用概率的计算
利用前向概率和后向概率，我们可以计算出HMM中单个状态和两个状态的概率公式。
(1) 给定模型
λ
\lambda
λ
和观测序列
O
O
O
,在时刻t处于状态
q
i
q_i
q
i
的概率记为:
γ
t
(
i
)
=
P
(
h
t
=
q
i
∣
O
,
λ
)
=
P
(
h
t
=
q
i
,
O
∣
λ
)
P
(
O
∣
λ
)
\gamma_t(i) = P(h_t = q_i | O,\lambda) = \frac{P(h_t = q_i ,O|\lambda)}{P(O|\lambda)}
γ
t
(
i
)
=
P
(
h
t
=
q
i
∣
O
,
λ
)
=
P
(
O
∣
λ
)
P
(
h
t
=
q
i
,
O
∣
λ
)
利用前向概率和后向概率的定义可知：
P
(
h
t
=
q
i
,
O
∣
λ
)
=
α
t
(
i
)
β
t
(
i
)
P(h_t = q_i ,O|\lambda) = \alpha_t(i)\beta_t(i)
P
(
h
t
=
q
i
,
O
∣
λ
)
=
α
t
(
i
)
β
t
(
i
)
于是我们得到：
γ
t
(
i
)
=
α
t
(
i
)
β
t
(
i
)
∑
j
=
1
N
α
t
(
j
)
β
t
(
j
)
\gamma_t(i) = \frac{ \alpha_t(i)\beta_t(i)}{\sum\limits_{j=1}^N \alpha_t(j)\beta_t(j)}
γ
t
(
i
)
=
j
=
1
∑
N
α
t
(
j
)
β
t
(
j
)
α
t
(
i
)
β
t
(
i
)
(2) 给定模型
λ
\lambda
λ
和观测序列
O
O
O
，在时刻t处于状态
q
i
q_i
q
i
，且时刻t+1处于状态
q
j
q_j
q
j
的概率记为:
ξ
t
(
i
,
j
)
=
P
(
h
t
=
q
i
,
h
t
+
1
=
q
j
∣
O
,
λ
)
=
P
(
h
t
=
q
i
,
h
t
+
1
=
q
j
,
O
∣
λ
)
P
(
O
∣
λ
)
\xi_t(i,j) = P(h_t = q_i, h_{t+1}=q_j | O,\lambda) = \frac{ P(h_t = q_i, h_{t+1}=q_j , O|\lambda)}{P(O|\lambda)}
ξ
t
(
i
,
j
)
=
P
(
h
t
=
q
i
,
h
t
+
1
=
q
j
∣
O
,
λ
)
=
P
(
O
∣
λ
)
P
(
h
t
=
q
i
,
h
t
+
1
=
q
j
,
O
∣
λ
)
而
P
(
h
t
=
q
i
,
h
t
+
1
=
q
j
,
O
∣
λ
)
P(h_t = q_i, h_{t+1}=q_j , O|\lambda)
P
(
h
t
=
q
i
,
h
t
+
1
=
q
j
,
O
∣
λ
)
可以由前向后向概率来表示为:
P
(
h
t
=
q
i
,
h
t
+
1
=
q
j
,
O
∣
λ
)
=
α
t
(
i
)
a
i
j
b
j
(
o
t
+
1
)
β
t
+
1
(
j
)
P(h_t = q_i, h_{t+1}=q_j , O|\lambda) = \alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)
P
(
h
t
=
q
i
,
h
t
+
1
=
q
j
,
O
∣
λ
)
=
α
t
(
i
)
a
i
j
b
j
(
o
t
+
1
)
β
t
+
1
(
j
)
从而最终我们得到
ξ
t
(
i
,
j
)
\xi_t(i,j)
ξ
t
(
i
,
j
)
的表达式如下：
ξ
t
(
i
,
j
)
=
α
t
(
i
)
a
i
j
b
j
(
o
t
+
1
)
β
t
+
1
(
j
)
∑
r
=
1
N
∑
s
=
1
N
α
t
(
r
)
a
r
s
b
s
(
o
t
+
1
)
β
t
+
1
(
s
)
\xi_t(i,j) = \frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum\limits_{r=1}^N\sum\limits_{s=1}^N\alpha_t(r)a_{rs}b_s(o_{t+1})\beta_{t+1}(s)}
ξ
t
(
i
,
j
)
=
r
=
1
∑
N
s
=
1
∑
N
α
t
(
r
)
a
r
s
b
s
(
o
t
+
1
)
β
t
+
1
(
s
)
α
t
(
i
)
a
i
j
b
j
(
o
t
+
1
)
β
t
+
1
(
j
)
(3) 将
γ
t
(
i
)
\gamma_t(i)
γ
t
(
i
)
和
ξ
t
(
i
,
j
)
\xi_t(i,j)
ξ
t
(
i
,
j
)
在各个时刻t求和，可以得到：
-
在观测序列O下状态 i 出现的期望值:
∑t
=
1
T
γ
t
(
i
)
\sum\limits_{t=1}^T\gamma_t(i)
t
=
1
∑
T
γ
t
(
i
)
-
在观测序列O下由状态 i 转移的期望值:
∑t
=
1
T
−
1
γ
t
(
i
)
\sum\limits_{t=1}^{T-1}\gamma_t(i)
t
=
1
∑
T
−
1
γ
t
(
i
)
-
在观测序列O下由状态 i 转移到状态 j 的期望值:
∑t
=
1
T
−
1
ξ
t
(
i
,
j
)
\sum\limits_{t=1}^{T-1}\xi_t(i,j)
t
=
1
∑
T
−
1
ξ
t
(
i
,
j
)
上面这些常用的概率值在求解HMM问题二，即求解HMM模型参数的时候需要用到。
问题二、最可能隐藏状态序列求解
问题描述：在HMM模型的解码问题中，给定模型
λ
=
(
A
,
B
,
Π
)
\lambda=(A,B,\Pi)
λ
=
(
A
,
B
,
Π
)
和观测序列
O
=
{
o
1
,
o
2
,
.
.
.
o
T
}
O =\{o_1,o_2,…o_T\}
O
=
{
o
1
,
o
2
,
.
.
.
o
T
}
，求给定观测序列O条件下，最可能出现的对应的状态序列
I
∗
=
{
i
1
∗
,
i
2
∗
,
.
.
.
i
T
∗
}
I^*= \{i_1^*,i_2^*,…i_T^*\}
I
∗
=
{
i
1
∗
,
i
2
∗
,
.
.
.
i
T
∗
}
,即
P
(
T
∗
∣
O
)
P(T^*|O)
P
(
T
∗
∣
O
)
要最大化。
一个可能的近似解法是求出观测序列O在每个时刻t最可能的隐藏状态
i
t
∗
i_t^*
i
t
∗
然后得到一个近似的隐藏状态序列
I
∗
=
{
i
1
∗
,
i
2
∗
,
.
.
.
i
T
∗
}
I^*= \{i_1^*,i_2^*,…i_T^*\}
I
∗
=
{
i
1
∗
,
i
2
∗
,
.
.
.
i
T
∗
}
。要这样近似求解不难，利用前一个问题的前向后向算法评估观察序列概率中第五节(HMM常用概率)的定义：在给定模型
λ
\lambda
λ
和观测序列O时，在时刻t处于状态
q
i
q_i
q
i
的概率是
γ
t
(
i
)
\gamma_t(i)
γ
t
(
i
)
，这个概率可以通过HMM的前向算法与后向算法计算。这样我们有：
i
t
∗
=
a
r
g
max
1
≤
i
≤
N
[
γ
t
(
i
)
]
,
t
=
1
,
2
,
.
.
.
T
i_t^* = arg \max_{1 \leq i \leq N}[\gamma_t(i)], \; t =1,2,…T
i
t
∗
=
a
r
g
1
≤
i
≤
N
max
[
γ
t
(
i
)
]
,
t
=
1
,
2
,
.
.
.
T
近似算法很简单，但是却不能保证预测的状态序列是整体是最可能的状态序列，因为预测的状态序列中某些相邻的隐藏状态可能存在转移概率为0的情况。
而维特比算法可以将HMM的状态序列作为一个整体来考虑，避免近似算法的问题，维特比算法是一个通用的求序列最短路径的动态规划算法，也可以用于很多其他问题。下面我们来看看维特比算法进行HMM解码的方法。
1. 维特比算法概述
维特比算法是一个通用的解码算法，是基于动态规划的求序列最短路径的方法。既然是动态规划算法，那么就需要找到合适的局部状态，以及局部状态的递推公式。在HMM中，维特比算法定义了两个局部状态用于递推。
(1) 第一个局部状态是在时刻t隐藏状态为i所有可能的状态转移路径
i
1
,
i
2
,
.
.
.
i
t
i_1,i_2,…i_t
i
1
,
i
2
,
.
.
.
i
t
（
i
→
i
t
i \rightarrow i_t
i
→
i
t
）中的
概率最大值
。记为
δ
t
(
i
)
\delta_t(i)
δ
t
(
i
)
:
δ
t
(
i
)
=
max
i
1
,
i
2
,
.
.
.
i
t
−
1
P
(
i
t
=
i
,
i
1
,
i
2
,
.
.
.
i
t
−
1
,
o
t
,
o
t
−
1
,
.
.
.
o
1
∣
λ
)
,
i
=
1
,
2
,
.
.
.
N
\delta_t(i) = \max_{i_1,i_2,…i_{t-1}}\;P(i_t=i, i_1,i_2,…i_{t-1},o_t,o_{t-1},…o_1|\lambda),\; i =1,2,…N
δ
t
(
i
)
=
i
1
,
i
2
,
.
.
.
i
t
−
1
max
P
(
i
t
=
i
,
i
1
,
i
2
,
.
.
.
i
t
−
1
,
o
t
,
o
t
−
1
,
.
.
.
o
1
∣
λ
)
,
i
=
1
,
2
,
.
.
.
N
由
δ
t
(
i
)
\delta_t(i)
δ
t
(
i
)
的定义可以得到?的递推表达式：
δ
t
+
1
(
i
)
=
max
i
1
,
i
2
,
.
.
.
i
t
P
(
i
t
+
1
=
i
,
i
1
,
i
2
,
.
.
.
i
t
,
o
t
+
1
,
o
t
,
.
.
.
o
1
∣
λ
)
=
max
1
≤
j
≤
N
[
δ
t
(
j
)
a
j
i
]
b
i
(
o
t
+
1
)
\begin{array}{ll} \delta_{t+1}(i) & = \max_{i_1,i_2,…i_{t}}\;P(i_{t+1}=i, i_1,i_2,…i_{t},o_{t+1},o_{t},…o_1|\lambda)\\ & = \max_{1 \leq j \leq N}\;[\delta_t(j)a_{ji}]b_i(o_{t+1})\\ \end{array}
δ
t
+
1
(
i
)
=
max
i
1
,
i
2
,
.
.
.
i
t
P
(
i
t
+
1
=
i
,
i
1
,
i
2
,
.
.
.
i
t
,
o
t
+
1
,
o
t
,
.
.
.
o
1
∣
λ
)
=
max
1
≤
j
≤
N
[
δ
t
(
j
)
a
j
i
]
b
i
(
o
t
+
1
)
(2)
第二个局部状态由第一个局部状态递推得到
。我们定义在时刻t隐藏状态为i的所有单个状态转移路径
(
i
1
,
i
2
,
.
.
.
,
i
t
−
1
,
i
)
(i_1,i_2,…,i_{t-1},i)
(
i
1
,
i
2
,
.
.
.
,
i
t
−
1
,
i
)
中概率最大的转移路径中第t−1个时刻的
隐藏状态
为
i
t
−
1
=
Ψ
t
(
i
t
)
i_{t-1}=\Psi_t(i_t)
i
t
−
1
=
Ψ
t
(
i
t
)
,其递推表达式可以表示为：
Ψ
t
(
i
t
)
=
a
r
g
max
1
≤
j
≤
N
[
δ
t
−
1
(
j
)
a
j
i
]
\Psi_t(i_t) = arg \; \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}]
Ψ
t
(
i
t
)
=
a
r
g
1
≤
j
≤
N
max
[
δ
t
−
1
(
j
)
a
j
i
]
有了这两个局部状态，我们就可以先从时刻0一直递推到时刻T，然后再利用
Ψ
t
(
i
t
)
\Psi_t(i_t)
Ψ
t
(
i
t
)
记录的前一个最可能的状态节点回溯，直到找到最优的隐藏状态序列。
2. 维特比算法的流程
输入：HMM模型
λ
=
(
A
,
B
,
Π
)
\lambda=(A,B,\Pi)
λ
=
(
A
,
B
,
Π
)
，观测序列
O
=
{
o
1
,
o
2
,
.
.
.
o
T
}
O =\{o_1,o_2,…o_T\}
O
=
{
o
1
,
o
2
,
.
.
.
o
T
}
输出：最有可能的隐藏状态序列
I
∗
=
{
i
1
∗
,
i
2
∗
,
.
.
.
i
T
∗
}
I^*= \{i_1^*,i_2^*,…i_T^*\}
I
∗
=
{
i
1
∗
,
i
2
∗
,
.
.
.
i
T
∗
}
(1) 初始化局部状态：
δ
1
(
i
)
=
π
i
b
i
(
o
1
)
,
i
=
1
,
2…
N
\delta_1(i) = \pi_ib_i(o_1),\;i=1,2…N
δ
1
(
i
)
=
π
i
b
i
(
o
1
)
,
i
=
1
,
2
.
.
.
N
Ψ
1
(
i
)
=
0
,
i
=
1
,
2…
N
\Psi_1(i)=0,\;i=1,2…N
Ψ
1
(
i
)
=
0
,
i
=
1
,
2
.
.
.
N
(2) 进行动态规划递推时刻t=2,3,…,T时刻的局部状态：
δ
t
(
i
)
=
max
1
≤
j
≤
N
[
δ
t
−
1
(
j
)
a
j
i
]
b
i
(
0
t
)
,
i
=
1
,
2…
N
\delta_{t}(i) = \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}]b_i(0_{t}),\;i=1,2…N
δ
t
(
i
)
=
max
1
≤
j
≤
N
[
δ
t
−
1
(
j
)
a
j
i
]
b
i
(
0
t
)
,
i
=
1
,
2
.
.
.
N
Ψ
t
(
i
)
=
a
r
g
max
1
≤
j
≤
N
[
δ
t
−
1
(
j
)
a
j
i
]
,
i
=
1
,
2…
N
\Psi_t(i) = arg \; \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}],\;i=1,2…N
Ψ
t
(
i
)
=
a
r
g
max
1
≤
j
≤
N
[
δ
t
−
1
(
j
)
a
j
i
]
,
i
=
1
,
2
.
.
.
N
(3) 如果t=1,2,…,T所有时刻的两个局部状态
δ
t
(
i
)
\delta_t(i)
δ
t
(
i
)
和
Ψ
t
(
i
)
\Psi_t(i)
Ψ
t
(
i
)
都已经计算完成
那就要从时刻T开始，计算该时刻最大的
δ
T
(
i
)
\delta_{T}(i)
δ
T
(
i
)
,即为最可能隐藏状态序列出现的概率。计算时刻T最大的
Ψ
t
(
i
)
\Psi_t(i)
Ψ
t
(
i
)
,即为
时刻T最可能的隐藏状态
i
T
∗
i_T^*
i
T
∗
。
δ
T
(
i
)
\delta_{T}(i)
δ
T
(
i
)
中的最大概率：
P
∗
=
max
1
≤
j
≤
N
δ
T
(
i
)
P^* = \max_{1 \leq j \leq N}\delta_{T}(i)
P
∗
=
max
1
≤
j
≤
N
δ
T
(
i
)
对应了T时刻最可能的隐藏状态：
i
T
∗
=
a
r
g
max
1
≤
j
≤
N
[
δ
T
(
i
)
]
i_T^* = arg \; \max_{1 \leq j \leq N}\;[\delta_{T}(i)]
i
T
∗
=
a
r
g
max
1
≤
j
≤
N
[
δ
T
(
i
)
]
(4) 利用局部状态
Ψ
(
i
)
\Psi(i)
Ψ
(
i
)
开始
回溯
。对于t=T−1,T−2,…,1：
i
t
∗
=
Ψ
t
+
1
(
i
t
+
1
∗
)
i_t^* = \Psi_{t+1}(i_{t+1}^*)
i
t
∗
=
Ψ
t
+
1
(
i
t
+
1
∗
)
也就是将t+1时刻的隐藏状态
i
t
+
1
∗
i_{t+1}^*
i
t
+
1
∗
代入到上面这个等式，从而求得t时刻的最可能隐藏状态
i
t
∗
i_t^*
i
t
∗
，最终得到最有可能的
隐藏状态序列
I
∗
=
{
i
1
∗
,
i
2
∗
,
.
.
.
i
T
∗
}
I^*= \{i_1^*,i_2^*,…i_T^*\}
I
∗
=
{
i
1
∗
,
i
2
∗
,
.
.
.
i
T
∗
}
。
3. HMM维特比算法求解实例
仍使用上面的盒子与球的例子来看看HMM维特比算法求解。
按照我们上一节的维特比算法:
(1) 首先需要得到
三个隐藏状态
在时刻1时对应的
各自两个局部状态
δ
1
(
i
)
\delta_1(i)
δ
1
(
i
)
和
Ψ
1
(
i
)
\Psi_1(i)
Ψ
1
(
i
)
，此时观测状态为1（红球）：
δ
1
(
1
)
=
π
1
b
1
(
o
1
)
=
0.2
×
0.5
=
0.1
\delta_1(1) = \pi_1b_1(o_1) = 0.2 \times 0.5 = 0.1
δ
1
(
1
)
=
π
1
b
1
(
o
1
)
=
0
.
2
×
0
.
5
=
0
.
1
δ
1
(
2
)
=
π
2
b
2
(
o
1
)
=
0.4
×
0.4
=
0.16
\delta_1(2) = \pi_2b_2(o_1) = 0.4 \times 0.4 = 0.16
δ
1
(
2
)
=
π
2
b
2
(
o
1
)
=
0
.
4
×
0
.
4
=
0
.
1
6
δ
1
(
3
)
=
π
3
b
3
(
o
1
)
=
0.4
×
0.7
=
0.28
\delta_1(3) = \pi_3b_3(o_1) = 0.4 \times 0.7 = 0.28
δ
1
(
3
)
=
π
3
b
3
(
o
1
)
=
0
.
4
×
0
.
7
=
0
.
2
8
Ψ
1
(
1
)
=
Ψ
1
(
2
)
=
Ψ
1
(
3
)
=
0
\Psi_1(1)=\Psi_1(2) =\Psi_1(3) =0
Ψ
1
(
1
)
=
Ψ
1
(
2
)
=
Ψ
1
(
3
)
=
0
(2) 现在开始递推三个隐藏状态在时刻2时对应的各自两个局部状态，此时观测状态为2（白球）：
δ
2
(
1
)
=
max
1
≤
j
≤
3
[
δ
1
(
j
)
a
j
1
]
b
1
(
o
2
)
=
max
1
≤
j
≤
3
[
0.1
×
0.5
,
0.16
×
0.3
,
0.28
×
0.2
]
×
0.5
=
0.028
\delta_2(1) = \max_{1\leq j \leq 3}[\delta_1(j)a_{j1}]b_1(o_2) = \max_{1\leq j \leq 3}[0.1 \times 0.5, 0.16 \times 0.3, 0.28\times 0.2] \times 0.5 = 0.028
δ
2
(
1
)
=
max
1
≤
j
≤
3
[
δ
1
(
j
)
a
j
1
]
b
1
(
o
2
)
=
max
1
≤
j
≤
3
[
0
.
1
×
0
.
5
,
0
.
1
6
×
0
.
3
,
0
.
2
8
×
0
.
2
]
×
0
.
5
=
0
.
0
2
8
Ψ
2
(
1
)
=
a
r
g
max
1
≤
j
≤
3
[
δ
1
(
j
)
a
j
1
]
=
a
r
g
max
1
≤
j
≤
3
[
0.1
×
0.5
,
0.16
×
0.3
,
0.28
×
0.2
]
=
3
\Psi_2(1)= arg\max_{1\leq j \leq 3}[\delta_1(j)a_{j1}]= arg\max_{1\leq j \leq 3}[0.1 \times 0.5, 0.16 \times 0.3, 0.28\times 0.2] = 3
Ψ
2
(
1
)
=
a
r
g
max
1
≤
j
≤
3
[
δ
1
(
j
)
a
j
1
]
=
a
r
g
max
1
≤
j
≤
3
[
0
.
1
×
0
.
5
,
0
.
1
6
×
0
.
3
,
0
.
2
8
×
0
.
2
]
=
3
δ
2
(
2
)
=
max
1
≤
j
≤
3
[
δ
1
(
j
)
a
j
2
]
b
2
(
o
2
)
=
max
1
≤
j
≤
3
[
0.1
×
0.2
,
0.16
×
0.5
,
0.28
×
0.3
]
×
0.6
=
0.0504
\delta_2(2) = \max_{1\leq j \leq 3}[\delta_1(j)a_{j2}]b_2(o_2) = \max_{1\leq j \leq 3}[0.1 \times 0.2, 0.16 \times 0.5, 0.28\times 0.3] \times 0.6 = 0.0504
δ
2
(
2
)
=
max
1
≤
j
≤
3
[
δ
1
(
j
)
a
j
2
]
b
2
(
o
2
)
=
max
1
≤
j
≤
3
[
0
.
1
×
0
.
2
,
0
.
1
6
×
0
.
5
,
0
.
2
8
×
0
.
3
]
×
0
.
6
=
0
.
0
5
0
4
Ψ
2
(
3
)
=
a
r
g
max
1
≤
j
≤
3
[
δ
1
(
j
)
a
j
2
]
=
a
r
g
max
1
≤
j
≤
3
[
0.1
×
0.2
,
0.16
×
0.5
,
0.28
×
0.3
]
=
3
\Psi_2(3)= arg\max_{1\leq j \leq 3}[\delta_1(j)a_{j2}] =arg \max_{1\leq j \leq 3}[0.1 \times 0.2, 0.16 \times 0.5, 0.28\times 0.3]= 3
Ψ
2
(
3
)
=
a
r
g
max
1
≤
j
≤
3
[
δ
1
(
j
)
a
j
2
]
=
a
r
g
max
1
≤
j
≤
3
[
0
.
1
×
0
.
2
,
0
.
1
6
×
0
.
5
,
0
.
2
8
×
0
.
3
]
=
3
δ
2
(
3
)
=
max
1
≤
j
≤
3
[
δ
1
(
j
)
a
j
3
]
b
3
(
o
2
)
=
max
1
≤
j
≤
3
[
0.1
×
0.3
,
0.16
×
0.2
,
0.28
×
0.5
]
×
0.3
=
0.042
\delta_2(3) = \max_{1\leq j \leq 3}[\delta_1(j)a_{j3}]b_3(o_2) = \max_{1\leq j \leq 3}[0.1 \times 0.3, 0.16 \times 0.2, 0.28\times 0.5] \times 0.3 = 0.042
δ
2
(
3
)
=
max
1
≤
j
≤
3
[
δ
1
(
j
)
a
j
3
]
b
3
(
o
2
)
=
max
1
≤
j
≤
3
[
0
.
1
×
0
.
3
,
0
.
1
6
×
0
.
2
,
0
.
2
8
×
0
.
5
]
×
0
.
3
=
0
.
0
4
2
Ψ
2
(
3
)
=
a
r
g
max
1
≤
j
≤
3
[
δ
1
(
j
)
a
j
3
]
=
a
r
g
max
1
≤
j
≤
3
[
0.1
×
0.3
,
0.16
×
0.2
,
0.28
×
0.5
]
=
3
\Psi_2(3) =arg\max_{1\leq j \leq 3}[\delta_1(j)a_{j3}]=arg \max_{1\leq j \leq 3}[0.1 \times 0.3, 0.16 \times 0.2, 0.28\times 0.5] = 3
Ψ
2
(
3
)
=
a
r
g
max
1
≤
j
≤
3
[
δ
1
(
j
)
a
j
3
]
=
a
r
g
max
1
≤
j
≤
3
[
0
.
1
×
0
.
3
,
0
.
1
6
×
0
.
2
,
0
.
2
8
×
0
.
5
]
=
3
(3) 继续递推三个隐藏状态在时刻3时对应的各自两个局部状态，此时观测状态为1（红球）：
δ
3
(
1
)
=
max
1
≤
j
≤
3
[
δ
2
(
j
)
a
j
1
]
b
1
(
o
3
)
=
max
1
≤
j
≤
3
[
0.028
×
0.5
,
0.0504
×
0.3
,
0.042
×
0.2
]
×
0.5
=
0.00756
\delta_3(1) = \max_{1\leq j \leq 3}[\delta_2(j)a_{j1}]b_1(o_3) = \max_{1\leq j \leq 3}[0.028 \times 0.5, 0.0504 \times 0.3, 0.042\times 0.2] \times 0.5 = 0.00756
δ
3
(
1
)
=
max
1
≤
j
≤
3
[
δ
2
(
j
)
a
j
1
]
b
1
(
o
3
)
=
max
1
≤
j
≤
3
[
0
.
0
2
8
×
0
.
5
,
0
.
0
5
0
4
×
0
.
3
,
0
.
0
4
2
×
0
.
2
]
×
0
.
5
=
0
.
0
0
7
5
6
Ψ
3
(
1
)
=
2
\Psi_3(1) =2
Ψ
3
(
1
)
=
2
δ
3
(
2
)
=
max
1
≤
j
≤
3
[
δ
2
(
j
)
a
j
2
]
b
2
(
o
3
)
=
max
1
≤
j
≤
3
[
0.028
×
0.2
,
0.0504
×
0.5
,
0.042
×
0.3
]
×
0.4
=
0.01008
\delta_3(2) = \max_{1\leq j \leq 3}[\delta_2(j)a_{j2}]b_2(o_3) = \max_{1\leq j \leq 3}[0.028 \times 0.2, 0.0504\times 0.5, 0.042\times 0.3] \times 0.4 = 0.01008
δ
3
(
2
)
=
max
1
≤
j
≤
3
[
δ
2
(
j
)
a
j
2
]
b
2
(
o
3
)
=
max
1
≤
j
≤
3
[
0
.
0
2
8
×
0
.
2
,
0
.
0
5
0
4
×
0
.
5
,
0
.
0
4
2
×
0
.
3
]
×
0
.
4
=
0
.
0
1
0
0
8
Ψ
3
(
2
)
=
2
\Psi_3(2) =2
Ψ
3
(
2
)
=
2
δ
3
(
3
)
=
max
1
≤
j
≤
3
[
δ
2
(
j
)
a
j
3
]
b
3
(
o
3
)
=
max
1
≤
j
≤
3
[
0.028
×
0.3
,
0.0504
×
0.2
,
0.042
×
0.5
]
×
0.7
=
0.0147
\delta_3(3) = \max_{1\leq j \leq 3}[\delta_2(j)a_{j3}]b_3(o_3) = \max_{1\leq j \leq 3}[0.028 \times 0.3, 0.0504 \times 0.2, 0.042\times 0.5] \times 0.7 = 0.0147
δ
3
(
3
)
=
max
1
≤
j
≤
3
[
δ
2
(
j
)
a
j
3
]
b
3
(
o
3
)
=
max
1
≤
j
≤
3
[
0
.
0
2
8
×
0
.
3
,
0
.
0
5
0
4
×
0
.
2
,
0
.
0
4
2
×
0
.
5
]
×
0
.
7
=
0
.
0
1
4
7
Ψ
3
(
3
)
=
3
\Psi_3(3) =3
Ψ
3
(
3
)
=
3
(4) 此时已经到最后的时刻，我们开始准备
回溯
。
此时最大概率为
P
∗
=
δ
3
(
3
)
P^*=\delta_3(3)
P
∗
=
δ
3
(
3
)
,从而得到
i
3
∗
=
3
i_3^*=3
i
3
∗
=
3
，也就是时刻3最可能的隐藏状态是盒子3。将
i
3
∗
=
3
i_3^*=3
i
3
∗
=
3
代入
i
2
∗
=
Ψ
3
(
i
3
∗
)
i_2^* = \Psi_{3}(i_{3}^*)
i
2
∗
=
Ψ
3
(
i
3
∗
)
，所以
i
2
∗
=
3
i_2^*=3
i
2
∗
=
3
。同样将
i
2
∗
=
3
i_2^*=3
i
2
∗
=
3
代入
i
1
∗
=
Ψ
2
(
i
2
∗
)
i_1^* = \Psi_{2}(i_{2}^*)
i
1
∗
=
Ψ
2
(
i
2
∗
)
，所以
i
1
∗
=
3
i_1^*=3
i
1
∗
=
3
。从而得到最终的最可能的隐藏状态序列为：(3,3,3)。
问题三、模型参数学习问题
HMM模型参数求解根据已知的条件可以分为两种情况。
1. 第一种情况
这种情况较为简单，就是我们已知D个长度为T的观测序列和对应的隐藏状态序列，即
{
(
O
1
,
I
1
)
,
(
O
2
,
I
2
)
,
.
.
.
(
O
D
,
I
D
)
}
\{(O_1, I_1), (O_2, I_2), …(O_D, I_D)\}
{
(
O
1
,
I
1
)
,
(
O
2
,
I
2
)
,
.
.
.
(
O
D
,
I
D
)
}
是已知的，此时我们可以很容易的用最大似然来求解模型参数。
-
假设样本从隐藏状态
qi
q_i
q
i
转移到
qj
q_j
q
j
的频率计数是
Ai
j
A_{ij}
A
i
j
,那么
状态转移矩阵A
求得为：
A=
[
a
i
j
]
,
其
中
a
i
j
=
A
i
j
∑
s
=
1
N
A
i
s
A = \Big[a_{ij}\Big], \;其中a_{ij} = \frac{A_{ij}}{\sum\limits_{s=1}^{N}A_{is}}
A
=
[
a
i
j
]
,
其
中
a
i
j
=
s
=
1
∑
N
A
i
s
A
i
j
-
假设样本隐藏状态为
qj
q_j
q
j
且观测状态为
vk
v_k
v
k
的频率计数是
Bj
k
B_{jk}
B
j
k
,那么
观测状态概率矩阵B
为：
B=
[
b
j
(
k
)
]
,
其
中
b
j
(
k
)
=
B
j
k
∑
s
=
1
M
B
j
s
B= \Big[b_{j}(k)\Big], \;其中b_{j}(k) = \frac{B_{jk}}{\sum\limits_{s=1}^{M}B_{js}}
B
=
[
b
j
(
k
)
]
,
其
中
b
j
(
k
)
=
s
=
1
∑
M
B
j
s
B
j
k
-
假设所有样本中初始隐藏状态为
qi
q_i
q
i
的频率计数为C(i),那么
初始概率分布Π
为：
Π=
π
(
i
)
=
C
(
i
)
∑
s
=
1
N
C
(
s
)
\Pi = \pi(i) = \frac{C(i)}{\sum\limits_{s=1}^{N}C(s)}
Π
=
π
(
i
)
=
s
=
1
∑
N
C
(
s
)
C
(
i
)
可见第一种情况下求解模型还是很简单的，其实就是基于统计计算模型参数。但是在很多时候，我们无法得到HMM样本观察序列对应的隐藏序列，只有D个长度为T的观测序列，即
{
(
O
1
)
,
(
O
2
)
,
.
.
.
(
O
D
)
}
\{(O_1), (O_2), …(O_D)\}
{
(
O
1
)
,
(
O
2
)
,
.
.
.
(
O
D
)
}
是已知的，那就属于第二种情况了。
2. 第二种情况
也是我们本文要讨论的重点。它的解法最常用的是鲍姆-韦尔奇（Baum-Welch）算法，其实就是基于EM算法的求解，只不过鲍姆-韦尔奇算法出现的时代，EM算法还没有被抽象出来，所以我们本文还是说鲍姆-韦尔奇算法。
假设给定训练数据中包含S个长度为T的观测序列
O
=
(
o
1
,
o
2
,
.
.
.
,
o
T
)
O=(o_1,o_2,…,o_T)
O
=
(
o
1
,
o
2
,
.
.
.
,
o
T
)
，而没有对应的隐藏状态序列，目标是学习隐马尔可夫模型
λ
=
(
A
,
B
,
π
)
\lambda= (A,B,\pi)
λ
=
(
A
,
B
,
π
)
的参数。我们将观测序列数据看作观测数据
O
O
O
，状态序列数据看作不可观测的隐数据
I
I
I
，那么隐马尔可夫模型事实上是一个含有隐变量的概率模型 :
P
(
O
∣
λ
)
=
∑
I
P
(
O
∣
I
,
λ
)
P
(
I
∣
λ
)
(3.2.1)
P(O|\lambda) = \sum_{I}P(O|I,\lambda)P(I|\lambda) \tag{3.2.1}
P
(
O
∣
λ
)
=
I
∑
P
(
O
∣
I
,
λ
)
P
(
I
∣
λ
)
(
3
.
2
.
1
)
(1) 确定完全数据的
对数似然函数
所有观测数据写成
O
=
(
o
1
,
o
2
,
.
.
.
,
o
T
)
O=(o_1,o_2,…,o_T)
O
=
(
o
1
,
o
2
,
.
.
.
,
o
T
)
，所有隐数据写成
I
=
(
i
1
,
i
2
,
.
.
.
,
i
T
)
I=(i_1,i_2,…,i_T)
I
=
(
i
1
,
i
2
,
.
.
.
,
i
T
)
，
完全数据
是
(
O
,
I
)
=
(
o
1
,
o
2
,
.
.
.
,
o
T
,
i
1
,
i
2
,
.
.
.
,
i
T
)
(O,I)=(o_1,o_2,…,o_T,i_1,i_2,…,i_T)
(
O
,
I
)
=
(
o
1
,
o
2
,
.
.
.
,
o
T
,
i
1
,
i
2
,
.
.
.
,
i
T
)
。
完全数据的对数似然函数
是
log
P
(
O
,
I
∣
λ
)
\log P(O,I|\lambda)
lo
g
P
(
O
,
I
∣
λ
)
（似然函数还是条件概率的形式，但是目的是求参数）。
(2) EM算法的E步：写出
Q函数
首先Q函数的定义：
Q
(
λ
,
λ
‾
)
=
E
I
[
l
o
g
P
(
O
,
I
∣
λ
)
∣
O
,
λ
‾
]
Q(\lambda,\overline{\lambda})=E_I[logP(O,I|\lambda)|O,\overline{\lambda}]
Q
(
λ
,
λ
)
=
E
I
[
l
o
g
P
(
O
,
I
∣
λ
)
∣
O
,
λ
]
。
Q函数是
完全数据的对数似然函数
关于
给定模型参数和观测变量的前提下
对
隐变量的条件概率分布
的
期望
。按照Q函数的定义在当前问题的具体形式如下：
Q
(
λ
,
λ
‾
)
=
∑
I
l
o
g
P
(
O
,
I
∣
λ
)
P
(
I
∣
O
,
λ
‾
)
(3.2.2)
Q(\lambda,\overline{\lambda})=\sum_IlogP(O,I|\lambda)P(I|O,\overline{\lambda})\tag{3.2.2}
Q
(
λ
,
λ
)
=
I
∑
l
o
g
P
(
O
,
I
∣
λ
)
P
(
I
∣
O
,
λ
)
(
3
.
2
.
2
)
这里仅仅取
P
(
O
,
I
∣
λ
)
P(O,I|\lambda)
P
(
O
,
I
∣
λ
)
的对数，
P
(
I
∣
O
,
λ
‾
)
P(I|O,\overline{\lambda})
P
(
I
∣
O
,
λ
)
是在对数的外面。其中，
λ
‾
\overline{\lambda}
λ
是隐马尔可夫模型参数的当前估计值，
λ
\lambda
λ
是要极大化的隐马尔可夫模型参数。
并且我们注意到Q函数的后部分，根据
条件联合分布
公式可得 ：
P
(
I
∣
O
,
λ
‾
)
=
P
(
O
,
I
∣
λ
‾
)
P
(
O
∣
λ
‾
)
P(I|O,\overline{\lambda})=\frac{P(O,I|\overline{\lambda})}{P(O|\overline{\lambda})}
P
(
I
∣
O
,
λ
)
=
P
(
O
∣
λ
)
P
(
O
,
I
∣
λ
)
。而这个
1
/
P
(
O
∣
λ
‾
)
1/P(O|\overline{\lambda})
1
/
P
(
O
∣
λ
)
其实是一个常数因子，可以省略，因此得到
Q
(
λ
,
λ
‾
)
Q (\lambda,\overline \lambda)
Q
(
λ
,
λ
)
为：
Q
(
λ
,
λ
‾
)
=
∑
I
log
P
(
O
,
I
∣
λ
)
P
(
O
,
I
∣
λ
‾
)
(3.2.3)
Q (\lambda,\overline \lambda) = \sum_I \log P(O,I|\lambda)P(O,I|\overline \lambda)\tag{3.2.3}
Q
(
λ
,
λ
)
=
I
∑
lo
g
P
(
O
,
I
∣
λ
)
P
(
O
,
I
∣
λ
)
(
3
.
2
.
3
)
又因为
P
(
O
,
I
∣
λ
)
=
π
i
1
b
i
1
(
o
1
)
a
i
1
i
2
b
i
2
(
o
2
)
⋯
a
i
T
−
1
i
T
b
i
T
(
o
T
)
P(O,I|\lambda) = \pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)\cdots a_{i_{T-1}i_T}b_{i_T}(o_T)
P
(
O
,
I
∣
λ
)
=
π
i
1
b
i
1
(
o
1
)
a
i
1
i
2
b
i
2
(
o
2
)
⋯
a
i
T
−
1
i
T
b
i
T
(
o
T
)
，所以
Q
(
λ
,
λ
‾
)
=
∑
I
l
o
g
π
i
1
P
(
O
,
I
∣
,
λ
‾
)
+
∑
I
(
∑
t
=
1
T
−
1
l
o
g
a
i
t
i
t
+
1
)
P
(
O
,
I
∣
,
λ
‾
)
+
∑
I
(
∑
t
=
1
T
l
o
g
b
i
t
(
o
t
)
)
P
(
O
,
I
∣
,
λ
‾
)
(3.2.4)
\begin{array}{ll} Q(\lambda,\overline{\lambda})= & \sum_Ilog\pi_{i_1}P(O,I|,\overline{\lambda})\\ &+\sum_I\left(\sum_{t=1}^{T-1}log\ a_{i_ti_{t+1}}\right)P(O,I|,\overline{\lambda}) \\ &+\sum_I\left(\sum_{t=1}^{T}log\ b_{i_t}(o_t)\right)P(O,I|,\overline{\lambda}) \\ \end{array} \tag{3.2.4}
Q
(
λ
,
λ
)
=
∑
I
l
o
g
π
i
1
P
(
O
,
I
∣
,
λ
)
+
∑
I
(
∑
t
=
1
T
−
1
l
o
g
a
i
t
i
t
+
1
)
P
(
O
,
I
∣
,
λ
)
+
∑
I
(
∑
t
=
1
T
l
o
g
b
i
t
(
o
t
)
)
P
(
O
,
I
∣
,
λ
)
(
3
.
2
.
4
)
此时我们看到待估计的参数刚好分别出现在三个项中，所以只需对各个项分别极大化。
(3) EM算法的M步：极大化Q函数（公式3.2.4）
第一项：
∑
I
l
o
g
π
i
1
P
(
O
,
I
∣
,
λ
‾
)
\sum_Ilog\pi_{i_1}P(O,I|,\overline{\lambda})
∑
I
l
o
g
π
i
1
P
(
O
,
I
∣
,
λ
)
=
∑
I
log
π
i
1
P
(
O
,
I
∣
λ
‾
)
=
∑
j
=
1
N
log
π
j
P
(
O
,
i
1
=
j
∣
λ
‾
)
\sum_I \log\pi_{i_1}P(O,I|\overline\lambda) = \sum_{j=1}^N \log \pi_jP(O,i_1=j|\overline\lambda)
∑
I
lo
g
π
i
1
P
(
O
,
I
∣
λ
)
=
∑
j
=
1
N
lo
g
π
j
P
(
O
,
i
1
=
j
∣
λ
)
注意到
π
j
\pi_j
π
j
满足约束条件
∑
j
=
1
N
π
j
=
1
\sum_{j=1}^N \pi_j =1
∑
j
=
1
N
π
j
=
1
，利用
拉格朗日乘子法
，写出拉格朗日函数：
f
1
=
∑
j
=
1
N
log
π
j
P
(
O
,
i
1
=
j
∣
λ
‾
)
+
θ
(
∑
j
=
1
N
π
j
−
1
)
f_1=\sum_{j=1}^N \log \pi_j P(O,i_1=j|\overline\lambda) +\theta(\sum_{j=1}^N \pi_j-1)
f
1
=
∑
j
=
1
N
lo
g
π
j
P
(
O
,
i
1
=
j
∣
λ
)
+
θ
(
∑
j
=
1
N
π
j
−
1
)
对其求偏导数并令结果为0：
∂
f
1
∂
π
j
=
∂
∂
π
j
[
∑
j
=
1
N
log
π
j
P
(
O
,
i
1
=
j
∣
λ
‾
)
+
θ
(
∑
j
=
1
N
π
j
−
1
)
]
=
0
\frac {\partial f_1}{\partial_{\pi_j}}=\frac {\partial}{\partial_{\pi_j}}[\sum_{j=1}^N \log \pi_j P(O,i_1=j|\overline\lambda) +\theta(\sum_{j=1}^N \pi_j-1)]=0
∂
π
j
∂
f
1
=
∂
π
j
∂
[
∑
j
=
1
N
lo
g
π
j
P
(
O
,
i
1
=
j
∣
λ
)
+
θ
(
∑
j
=
1
N
π
j
−
1
)
]
=
0
注意这里的
π
j
\pi_j
π
j
其实是个向量，所以后半部分
∂
∂
π
j
γ
(
∑
j
=
1
N
π
j
−
1
)
=
θ
π
j
\frac {\partial}{\partial \pi_j}\gamma(\sum_{j=1}^N \pi_j-1)=\theta \pi_j
∂
π
j
∂
γ
(
∑
j
=
1
N
π
j
−
1
)
=
θ
π
j
，于是得到：
P
(
O
,
i
1
=
j
∣
λ
‾
)
+
θ
π
j
=
0
P(O,i_1=j|\overline\lambda) +\theta\pi_j=0
P
(
O
,
i
1
=
j
∣
λ
)
+
θ
π
j
=
0
对j求和
得到
拉格朗日因子
：
θ
=
−
P
(
O
∣
λ
‾
)
\theta= – P(O|\overline\lambda)
θ
=
−
P
(
O
∣
λ
)
于是得：
π
j
=
P
(
O
,
i
1
=
j
∣
λ
‾
)
P
(
O
∣
λ
‾
)
\pi_j =\frac {P(O,i_1=j|\overline\lambda)}{P(O|\overline\lambda)}
π
j
=
P
(
O
∣
λ
)
P
(
O
,
i
1
=
j
∣
λ
)
根据上面常用概率的关于
γ
\gamma
γ
的定义
:
γ
t
(
i
)
=
P
(
h
t
=
q
i
∣
O
,
λ
)
=
P
(
h
t
=
q
i
,
O
∣
λ
)
P
(
O
∣
λ
)
:\gamma_t(i) = P(h_t = q_i | O,\lambda) = \frac{P(h_t = q_i ,O|\lambda)}{P(O|\lambda)}
:
γ
t
(
i
)
=
P
(
h
t
=
q
i
∣
O
,
λ
)
=
P
(
O
∣
λ
)
P
(
h
t
=
q
i
,
O
∣
λ
)
可得
初始状态概率
为：
π
j
=
γ
1
(
j
)
(3.2.5)
\pi_j=\gamma_1(j)\tag{3.2.5}
π
j
=
γ
1
(
j
)
(
3
.
2
.
5
)
第二项：
∑
I
(
∑
t
=
1
T
−
1
l
o
g
a
i
t
i
t
+
1
)
P
(
O
,
I
∣
,
λ
‾
)
\sum_I\left(\sum_{t=1}^{T-1}log\ a_{i_ti_{t+1}}\right)P(O,I|,\overline{\lambda})
∑
I
(
∑
t
=
1
T
−
1
l
o
g
a
i
t
i
t
+
1
)
P
(
O
,
I
∣
,
λ
)
=
∑
i
=
1
N
∑
j
=
1
N
∑
t
=
1
T
−
1
log
a
i
j
P
(
O
,
i
t
=
i
,
i
t
+
1
=
j
∣
λ
‾
)
\sum_{i=1}^N \sum_{j=1}^N \sum_{t=1}^{T-1} \log a_{ij} P(O,i_t=i,i_{t+1} =j|\overline\lambda)
∑
i
=
1
N
∑
j
=
1
N
∑
t
=
1
T
−
1
lo
g
a
i
j
P
(
O
,
i
t
=
i
,
i
t
+
1
=
j
∣
λ
)
类似第一项，应用具有约束条件
∑
j
=
1
N
a
i
j
=
1
\sum_{j=1}^{N}a_{ij}=1
∑
j
=
1
N
a
i
j
=
1
的拉格朗日乘子法可以求出：
a
i
j
=
∑
t
=
1
T
−
1
P
(
O
,
i
t
=
i
,
i
t
+
1
=
j
∣
λ
‾
)
∑
t
=
1
T
−
1
P
(
O
,
i
t
=
i
∣
λ
‾
)
a_{ij}=\frac {\sum_{t=1}^{T-1}P(O,i_t=i,i_{t+1} =j|\overline\lambda)}{\sum_{t=1}^{T-1}P(O,i_t=i|\overline\lambda)}
a
i
j
=
∑
t
=
1
T
−
1
P
(
O
,
i
t
=
i
∣
λ
)
∑
t
=
1
T
−
1
P
(
O
,
i
t
=
i
,
i
t
+
1
=
j
∣
λ
)
同样根据
γ
t
(
j
)
\gamma_t(j)
γ
t
(
j
)
定义以及
ξ
t
(
i
,
j
)
\xi_t(i,j)
ξ
t
(
i
,
j
)
的定义
ξ
t
(
i
,
j
)
=
P
(
h
t
=
q
i
,
h
t
+
1
=
q
j
∣
O
,
λ
)
=
P
(
h
t
=
q
i
,
h
t
+
1
=
q
j
,
O
∣
λ
)
P
(
O
∣
λ
)
\xi_t(i,j) = P(h_t = q_i, h_{t+1}=q_j | O,\lambda) = \frac{ P(h_t = q_i, h_{t+1}=q_j , O|\lambda)}{P(O|\lambda)}
ξ
t
(
i
,
j
)
=
P
(
h
t
=
q
i
,
h
t
+
1
=
q
j
∣
O
,
λ
)
=
P
(
O
∣
λ
)
P
(
h
t
=
q
i
,
h
t
+
1
=
q
j
,
O
∣
λ
)
可得
状态转移概率
为：
a
i
j
=
∑
t
=
1
T
−
1
ξ
t
(
i
,
j
)
∑
t
=
1
T
γ
t
(
j
)
(3.2.6)
a_{ij}=\frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T}\gamma_t(j)}\tag{3.2.6}
a
i
j
=
∑
t
=
1
T
γ
t
(
j
)
∑
t
=
1
T
−
1
ξ
t
(
i
,
j
)
(
3
.
2
.
6
)
第三项：
∑
I
(
∑
t
=
1
T
l
o
g
b
i
t
(
o
t
)
)
P
(
O
,
I
∣
,
λ
‾
)
\sum_I\left(\sum_{t=1}^{T}log\ b_{i_t}(o_t)\right)P(O,I|,\overline{\lambda})
∑
I
(
∑
t
=
1
T
l
o
g
b
i
t
(
o
t
)
)
P
(
O
,
I
∣
,
λ
)
=
∑
j
=
1
N
∑
t
=
1
T
log
b
j
(
o
t
)
P
(
O
,
i
t
=
j
∣
λ
‾
)
\sum_{j=1}^N\sum_{t=1}^T \log b_j(o_t)P(O,i_t=j|\overline\lambda)
∑
j
=
1
N
∑
t
=
1
T
lo
g
b
j
(
o
t
)
P
(
O
,
i
t
=
j
∣
λ
)
同样用拉格朗日乘子法，约束条件是
∑
k
=
1
M
b
j
(
k
)
=
1
\sum_{k=1}^Mb_j(k)=1
∑
k
=
1
M
b
j
(
k
)
=
1
。注意，只有在
o
t
=
v
k
o_t = v_k
o
t
=
v
k
时
b
j
(
o
t
)
b_j(o_t)
b
j
(
o
t
)
对
b
j
(
k
)
b_j(k)
b
j
(
k
)
的偏导数才不为0，以
I
(
o
t
=
v
k
)
I(o_t = v_k)
I
(
o
t
=
v
k
)
表示，求得：
b
j
(
k
)
=
∑
t
=
1
T
P
(
O
,
i
t
=
j
∣
λ
‾
)
I
(
o
t
=
v
k
)
∑
t
=
1
T
P
(
O
,
i
t
=
j
∣
λ
‾
)
b_j(k) =\frac {\sum_{t=1}^T P(O,i_t =j|\overline\lambda)I(o_t =v_k)}{\sum_{t=1}^T P(O,i_t =j|\overline\lambda)}
b
j
(
k
)
=
∑
t
=
1
T
P
(
O
,
i
t
=
j
∣
λ
)
∑
t
=
1
T
P
(
O
,
i
t
=
j
∣
λ
)
I
(
o
t
=
v
k
)
同样根据
γ
t
(
j
)
\gamma_t(j)
γ
t
(
j
)
定义可得
观测状态概率
为：
b
j
(
k
)
=
∑
t
=
1
,
o
t
=
v
k
T
γ
t
(
j
)
∑
t
=
1
T
γ
t
(
j
)
(3.2.7)
b_j(k)=\frac{\sum_{t=1,o_t=v_k}^{T}\gamma_t(j)}{\sum_{t=1}^{T}\gamma_t(j)}\tag{3.2.7}
b
j
(
k
)
=
∑
t
=
1
T
γ
t
(
j
)
∑
t
=
1
,
o
t
=
v
k
T
γ
t
(
j
)
(
3
.
2
.
7
)
3. 鲍姆-韦尔奇算法流程总结
输入：观测数据
O
=
(
o
1
,
o
2
,
.
.
.
,
o
T
)
O=(o_1,o_2,…,o_T)
O
=
(
o
1
,
o
2
,
.
.
.
,
o
T
)
输出：隐马尔可夫模型参数
(1) 初始化
对n=0，选取
a
i
j
(
0
)
,
b
j
(
k
)
(
0
)
,
π
i
(
0
)
a_{ij}^{(0)},b_j(k)^{(0)},\pi_i^{(0)}
a
i
j
(
0
)
,
b
j
(
k
)
(
0
)
,
π
i
(
0
)
，得到模型
λ
(
0
)
=
(
A
(
0
)
,
B
(
0
)
,
π
(
0
)
)
\lambda^{(0)} = (A^{(0)},B^{(0)},\pi^{(0)})
λ
(
0
)
=
(
A
(
0
)
,
B
(
0
)
,
π
(
0
)
)
(2) 递推，对n=1,2,…
a
i
j
(
n
+
1
)
=
∑
t
=
1
T
−
1
ξ
t
(
i
,
j
)
∑
t
=
1
T
−
1
γ
t
(
i
)
a_{ij}^{(n+1)} = \frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)}
a
i
j
(
n
+
1
)
=
∑
t
=
1
T
−
1
γ
t
(
i
)
∑
t
=
1
T
−
1
ξ
t
(
i
,
j
)
b
j
(
n
+
1
)
(
k
)
=
∑
t
=
1
,
o
t
=
v
k
T
γ
t
(
j
)
∑
t
=
1
T
γ
t
(
j
)
b_{j}^{(n+1)}(k) = \frac{\sum_{t=1,o_t=v_k}^{T}\gamma_t(j)}{\sum_{t=1}^{T}\gamma_t(j)}
b
j
(
n
+
1
)
(
k
)
=
∑
t
=
1
T
γ
t
(
j
)
∑
t
=
1
,
o
t
=
v
k
T
γ
t
(
j
)
π
i
(
n
+
1
)
=
γ
1
(
i
)
\pi_i^{(n+1)}=\gamma_1(i)
π
i
(
n
+
1
)
=
γ
1
(
i
)
(3) 模型收敛（满足条件）则终止递推，得到模型参数
λ
(
n
+
1
)
=
(
A
(
n
+
1
)
,
B
(
n
+
1
)
,
π
(
n
+
1
)
)
\lambda^{(n+1) } =(A^{(n+1)},B^{(n+1)},\pi^{(n+1)})
λ
(
n
+
1
)
=
(
A
(
n
+
1
)
,
B
(
n
+
1
)
,
π
(
n
+
1
)
)
参考：
-
隐马尔可夫模型之Baum-Welch算法详解
-
HMM的Baum-Welch算法和Viterbi算法公式推导细节
-
隐马尔科夫模型HMM（三）鲍姆-韦尔奇算法求解HMM参数
- 《统计学习方法（李航）- 第10章 隐马尔科可夫模型》
THE END.