4.5 维特比算法解码隐藏状态序列

学习目标

在本篇我们会讨论维特比算法解码隐藏状态序列，即给定模型和观测序列，求给定观测序列条件下，最可能出现的对应的隐藏状态序列。

HMM模型的解码问题最常用的算法是维特比算法，当然也有其他的算法可以求解这个问题。

同时维特比算法是一个通用的求序列最短路径的动态规划算法，也可以用于很多其他问题。

HMM模型的解码问题即：

给定模型 $\lambda=(A,B,\Pi)$ 和观测序列 $O={o_1,o_2,...o_T}$ ，求给定观测序列O条件下，最可能出现的对应的状态序列 $I^\ast ={i^\ast _1,i^\ast _2,...i^\ast _T}$ ,即 $P(I^\ast |O)$ 的最大化。

一个可能的近似解法是求出观测序列O在每个时刻t最可能的隐藏状态 $i^\ast _t$ 然后得到一个近似的隐藏状态序列 $I^\ast ={i^\ast _1,i^\ast _2,...i^\ast _T}$ 。要这样近似求解不难，利用前向后向算法评估观察序列概率的定义：

在给定模型 $\lambda$ 和观测序列O时，在时刻t处于状态 $q_i$ 的概率是 $\gamma _t(i)$ ，这个概率可以通过HMM的前向算法与后向算法计算。这样我们有：

近似算法很简单，但是却不能保证预测的状态序列整体是最可能的状态序列，因为预测的状态序列中某些相邻的隐藏状态可能存在转移概率为0的情况。

而维特比算法可以将HMM的状态序列作为一个整体来考虑，避免近似算法的问题，下面我们来看看维特比算法进行HMM解码的方法。

维特比算法是一个通用的解码算法，是基于动态规划的求序列最短路径的方法。

既然是动态规划算法，那么就需要找到合适的局部状态，以及局部状态的递推公式。在HMM中，维特比算法定义了两个局部状态用于递推。

1) 第一个局部状态是在时刻t隐藏状态为 $i$ 所有可能的状态转移路径 $i_1,i_2,...i_t$ 中的概率最大值。

由 $\delta _t(i)$ 的定义可以得到 $\delta$ 的递推表达式：

2) 第二个局部状态由第一个局部状态递推得到。

我们定义在时刻t隐藏状态为i的所有单个状态转移路径 $(i_1,i_2,...,i_{t-1},i)$ 中概率最大的转移路径中第t-1个节点的隐藏状态为 $\psi _t(i)$ ,
其递推表达式可以表示为：

有了这两个局部状态，我们就可以从时刻0一直递推到时刻T，然后利用 $\psi _t(i)$ 记录的前一个最可能的状态节点回溯，直到找到最优的隐藏状态序列。

现在我们来总结下维特比算法的流程：

流程如下：

3) 计算时刻T最大的 $\delta _T(i)$ ,即为最可能隐藏状态序列出现的概率。计算时刻T最大的 $\psi _t(i)$ ,即为时刻T最可能的隐藏状态。

最终得到最有可能的隐藏状态序列 $I^\ast ={i^\ast _1,i^\ast _2,...i^\ast _T}$

下面我们仍然用盒子与球的例子来看看HMM维特比算法求解。我们的观察集合是:

我们的状态集合是：

而观察序列和状态序列的长度为3.

初始状态分布为：

状态转移概率分布矩阵为：

观测状态概率矩阵为：

球的颜色的观测序列:

按照我们前面的维特比算法，首先需要得到三个隐藏状态在时刻1时对应的各自两个局部状态，此时观测状态为1：

现在开始递推三个隐藏状态在时刻2时对应的各自两个局部状态，此时观测状态为2：

$\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 \leq j \leq 3 } [δ^{ 1 } (j) a^{ j 1 }] 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$
- $\Psi_2(1)=3$
$\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 \leq j \leq 3 } [δ^{ 1 } (j) a^{ j 2 }] 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$
- $\Psi_2(2)=3$
$\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 \leq j \leq 3 } [δ^{ 1 } (j) a^{ j 3 }] 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$
- $\Psi_2(3)=3$

继续递推三个隐藏状态在时刻3时对应的各自两个局部状态，此时观测状态为1：

$\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 \leq j \leq 3 } [δ^{ 2 } (j) a^{ j 1 }] 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$
- $\Psi_3(1)=2$
$\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 \leq j \leq 3 } [δ^{ 2 } (j) a^{ j 2 }] 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$
- $\Psi_3(2)=2$
$\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 \leq j \leq 3 } [δ^{ 2 } (j) a^{ j 3 }] 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$
- $\Psi_3(3)=3$

此时已经到最后的时刻，我们开始准备回溯。此时最大概率为 $\delta _3(3)$ ,从而得到 $i^\ast _3=3$

由于 $\psi _3(3)=3$ ,所以 $i^\ast _2=3$ , 而又由于 $\psi _2(3)=3$ ,所以 $i^\ast _1=3$ 。从而得到最终的最可能的隐藏状态序列为：(3,3,3)。