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

　　　　HMM模型的解码问题最常用的算法是维特比算法，当然也有其他的算法可以求解这个问题。同时维特比算法是一个通用的求序列最短路径的动态规划算法，也可以用于很多其他问题，比如之前讲到的文本挖掘的分词原理中我们讲到了单独用维特比算法来做分词。

　　　　本文关注于用维特比算法来解码HMM的的最可能隐藏状态序列。

1. HMM最可能隐藏状态序列求解概述

　　　　在HMM模型的解码问题中，给定模型$\lambda = (A, B, \Pi)$和观测序列$O =\{o_1,o_2,...o_T\}$，求给定观测序列O条件下，最可能出现的对应的状态序列$I^*= \{i_1^*,i_2^*,...i_T^*\},$即$P(I^*|O)$要最大化。

　　　　一个可能的近似解法是求出观测序列O在每个时刻t最可能的隐藏状态$i_t^*$然后得到一个近似的隐藏状态序列$I^*= \{i_1^*,i_2^*,...i_T^*\}$。要这样近似求解不难，利用隐马尔科夫模型HMM（二）前向后向算法评估观察序列概率中第五节的定义：在给定模型$\lambda$和观测序列O时，在时刻t处于状态$q_i$的概率是$\gamma_t(i)$，这个概率可以通过HMM的前向算法与后向算法计算。这样我们有：$i_t^* = arg \max_{1 \leq i \leq N}[\gamma_t(i)], \; t =1,2,...T$

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

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

2. 维特比算法概述

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

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

　　　　第一个局部状态是在时刻t隐藏状态为i所有可能的状态转移路径$i_1,i_2,...i_t$中的概率最大值。记为$\delta_t(i):\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$

　　　　由$\delta_t(i)$的定义可以得到$\delta$的递推表达式：$\begin{aligned} \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{aligned}$

　　　　第二个局部状态由第一个局部状态递推得到。我们定义在时刻t隐藏状态为i的所有单个状态转移路径$(i_1,i_2,...,i_{t-1},i)$中概率最大的转移路径中第t-1个节点的隐藏状态为$\Psi_t(i)$,其递推表达式可以表示为：$\Psi_t(i) = arg \; \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}]$

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

3. 维特比算法流程总结

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

　　　　输入：HMM模型$\lambda = (A, B, \Pi)$，观测序列$O=(o_1,o_2,...o_T)$

　　　　输出：最有可能的隐藏状态序列$I^*= \{i_1^*,i_2^*,...i_T^*\}$

　　　　1）初始化局部状态：$\delta_1(i) = \pi_ib_i(o_1),\;i=1,2...N\Psi_1(i)=0,\;i=1,2...N$

　　　　2) 进行动态规划递推时刻t=2,3,...T时刻的局部状态：$\delta_{t}(i) = \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}]b_i(0_{t}),\;i=1,2...N\Psi_t(i) = arg \; \max_{1 \leq j \leq N}\;[\delta_{t-1}(j)a_{ji}],\;i=1,2...N$

　　　　3) 计算时刻T最大的$\delta_{T}(i),$即为最可能隐藏状态序列出现的概率。计算时刻T最大的$\Psi_t(i),$即为时刻T最可能的隐藏状态。$P* = \max_{1 \leq j \leq N}\delta_{T}(i)i_T^* = arg \; \max_{1 \leq j \leq N}\;[\delta_{T}(i)]$

　　　　4) 利用局部状态$\Psi(i)$开始回溯。对于t=T-1,T-2,...,1：$i_t^* = \Psi_{t+1}(i_{t+1}^*)$

　　　　最终得到最有可能的隐藏状态序列$I^*= \{i_1^*,i_2^*,...i_T^*\}$

4. HMM维特比算法求解实例

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

　　　　我们的观察集合是:V={红，白}，M=2

　　　　我们的状态集合是：Q ={盒子1，盒子2，盒子3}， N=3

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

　　　　初始状态分布为：$\Pi = (0.2,0.4,0.4)^T$

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

$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)$

　　　　观测状态概率矩阵为：

$B = \left( \begin{array} {ccc}0.5 & 0.5 \\0.4 & 0.6 \\ 0.7 & 0.3 \end{array} \right)$

　　　　球的颜色的观测序列:O={红，白，红}

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

$\delta_1(1) = \pi_1b_1(o_1) = 0.2 \times 0.5 = 0.1$

$\delta_1(2) = \pi_2b_2(o_1) = 0.4 \times 0.4 = 0.16$

$\delta_1(3) = \pi_3b_3(o_1) = 0.4 \times 0.7 = 0.28$

$\Psi_1(1)=\Psi_1(2) =\Psi_1(3) =0$

　　　　现在开始递推三个隐藏状态在时刻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$

$\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$

$\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$

$\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$

$\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$

$\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$

$\Psi_3(3)=3$

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

　　　　由于$\Psi_3(3)=3$,所以$i_2^* =3$, 而又由于$\Psi_2(3)=3$,所以$i_1^* =3$。从而得到最终的最可能的隐藏状态序列为：(3,3,3)

5. HMM模型维特比算法总结

　　　　如果大家看过之前写的文本挖掘的分词原理中的维特比算法，就会发现这两篇之中的维特比算法稍有不同。主要原因是在中文分词时，我们没有观察状态和隐藏状态的区别，只有一种状态。但是维特比算法的核心是定义动态规划的局部状态与局部递推公式，这一点在中文分词维特比算法和HMM的维特比算法是相同的，也是维特比算法的精华所在。

　　　　维特比算法也是寻找序列最短路径的一个通用方法，和dijkstra算法有些类似，但是dijkstra算法并没有使用动态规划，而是贪心算法。同时维特比算法仅仅局限于求序列最短路径，而dijkstra算法是通用的求最短路径的方法。