viterb-hmm.md

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

---

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

本文关注于用维特比算法来解码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（二）前向后向算法评估观察序列概率](/ml/hmm/hmm-forward-backward.md)中第五节的定义：在给定模型$$\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$$

$$\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模型维特比算法总结

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

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

[^1]: Enter footnote here.