本文关注于用维特比算法来解码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...NPsi_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...NPsi_t(i) = arg ; max_{1 leq j leq N};[delta_{t-1}(j)a_{ji}],;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_{1leq j leq 3}[delta_1(j)a_{j1}]b_1(o_2) = max_{1leq j leq 3}[0.1 times 0.5, 0.16 times 0.3, 0.28times 0.2] times 0.5 = 0.028$$

$$Psi_2(1)=3$$

$$delta_2(2) = max_{1leq j leq 3}[delta_1(j)a_{j2}]b_2(o_2) = max_{1leq j leq 3}[0.1 times 0.2, 0.16 times 0.5, 0.28times 0.3] times 0.6 = 0.0504$$

$$Psi_2(2)=3$$

$$delta_2(3) = max_{1leq j leq 3}[delta_1(j)a_{j3}]b_3(o_2) = max_{1leq j leq 3}[0.1 times 0.3, 0.16 times 0.2, 0.28times 0.5] times 0.3 = 0.042$$

$$Psi_2(3)=3$$

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

$$delta_3(1) = max_{1leq j leq 3}[delta_2(j)a_{j1}]b_1(o_3) = max_{1leq j leq 3}[0.028 times 0.5, 0.0504 times 0.3, 0.042times 0.2] times 0.5 = 0.00756$$

$$Psi_3(1)=2$$

$$delta_3(2) = max_{1leq j leq 3}[delta_2(j)a_{j2}]b_2(o_3) = max_{1leq j leq 3}[0.028times 0.2, 0.0504times 0.5, 0.042times 0.3] times 0.4 = 0.01008$$

$$Psi_3(2)=2$$

$$delta_3(3) = max_{1leq j leq 3}[delta_2(j)a_{j3}]b_3(o_3) = max_{1leq j leq 3}[0.028times 0.3, 0.0504 times 0.2, 0.042times 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算法是通用的求最短路径的方法。