解码隐马尔可夫模型——维特比算法

1. 问题背景与定位

我们已经学习了 HMM 的评估问题（计算一个观测序列的概率）和学习问题（估计模型参数）。现在，我们面临第三个，也是应用最广泛的问题之一：预测（或解码）问题。

预测问题描述：给定一个 HMM 模型 $\lambda =(A,B,\pi )$ 和一个观测序列 $O=(o_1,o_2,\dots ,o_T)$，我们的任务是找到一条最有可能的隐藏状态序列 $Q^{\ast }=(q_1^{\ast },q_2^{\ast },\dots ,q_T^{\ast })$，这条序列能够最好地解释我们所看到的观测序列。

用数学语言来说，我们的目标是求解：

$$Q^{\ast }=\underset{所有可能的Q}{\mathrm{argmax}}P(Q|O,\lambda )$$

与评估问题的关键区别：

• 评估问题 (前向算法) 计算的是所有可能的隐藏路径产生观测 $O$ 的概率之和，即 $P(O|\lambda )={\sum }_{Q}P(O,Q|\lambda )$。它回答的是“这个观测序列有多大概率发生？”。
• 预测问题 寻找的是那唯一的一条使后验概率 $P(Q|O,\lambda )$ 最大的隐藏路径 $Q$。它回答的是“最可能发生了什么内部状态变化，才导致了我看到的这个结果？”。

在实际应用中，比如词性标注，我们拿到一个句子（观测序列），我们想要的不是这个句子出现的概率，而是每个词最可能的词性（最可能的隐藏状态序列）。这正是解码问题的用武之地。

2. 近似算法

在深入维特比算法之前，让我们先思考一个最简单、最直观的方法，也就是“近似算法”。

2.1 算法思想

这个方法的想法是，我们可以独立地考察每一个时刻 $t$，找出在该时刻最有可能的隐藏状态是什么，然后把这些最可能的状态串起来，作为最终的预测路径。

我们如何计算在时刻 $t$ 最有可能的状态呢？这正是我们之前学习过的概率 ${\gamma }_t(i)$。

$${\gamma }_t(i)=P(q_t=s_i|O,\lambda )$$

这个概率表示，在观测到全部序列 $O$ 的前提下，时刻 $t$ 的状态是 $s_i$ 的概率。

所以，近似算法的步骤如下： 对每一个时刻 $t=1,2,\dots ,T$，都独立地求解：

$$q_t^{\ast }=\underset{1\le i\le N}{\mathrm{argmax}}[{\gamma }_t(i)]$$

最后，将这些 $q_t^{\ast }$ 拼接起来，得到最终的路径 $Q^{\ast }=(q_1^{\ast },q_2^{\ast },\dots ,q_T^{\ast })$。

2.2 为什么是“近似”且“有缺陷”的？

这种方法虽然简单直观，但它存在一个致命的缺陷：它只保证了每个时间点的局部最优，而完全忽略了状态之间的转移关系，因此无法保证全局最优。

更严重的是，它甚至可能产生一条非法路径！例如，在时刻 $t$ 算出的最优状态是 $q_t^{\ast }=s_i$，在时刻 $t+1$ 算出的最优状态是 $q_{t+1}^{\ast }=s_j$，但模型中的状态转移概率 $a_{ij}$ 可能为 0。这意味着从 $s_i$ 到 $s_j$ 的转移是根本不可能发生的。近似算法由于其“各自为政”的计算方式，无法避免这种情况。

因此，我们需要一个能够从全局视角考虑路径整体概率的算法。

2.3 例子分析

模型和数据: 与解决隐马尔科夫模型的学习问题相同，观测序列 $O=(\text{红, 白, 红})$。

• $\alpha$ 值（前向概率）和 $\beta$ 值（后向概率）已由前向-后向算法算出。
• 总概率 $P(O|\lambda )=0.130218$。

计算 ${\gamma }_t(i)=\frac{{\alpha }_t(i){\beta }_t(i)}{P(O|\lambda )}$:

• 时刻 t=1:

  • ${\gamma }_1(1)=\frac{{\alpha }_1(1){\beta }_1(1)}{P(O|\lambda )}=\frac{0.10\times 0.2451}{0.130218}\approx 0.1882$
  • ${\gamma }_1(2)=\frac{{\alpha }_1(2){\beta }_1(2)}{P(O|\lambda )}=\frac{0.16\times 0.2622}{0.130218}\approx 0.3217$
  • ${\gamma }_1(3)=\frac{{\alpha }_1(3){\beta }_1(3)}{P(O|\lambda )}=\frac{0.28\times 0.2277}{0.130218}\approx 0.4899$
  • 在时刻1，${\gamma }_1(3)$ 最大，所以 $q_1^{\ast }=\text{状态3}$。

• 时刻 t=2:

  • ${\gamma }_2(1)=\frac{{\alpha }_2(1){\beta }_2(1)}{P(O|\lambda )}=\frac{0.077\times 0.54}{0.130218}\approx 0.3193$
  • ${\gamma }_2(2)=\frac{{\alpha }_2(2){\beta }_2(2)}{P(O|\lambda )}=\frac{0.1104\times 0.49}{0.130218}\approx 0.4161$
  • ${\gamma }_2(3)=\frac{{\alpha }_2(3){\beta }_2(3)}{P(O|\lambda )}=\frac{0.0606\times 0.57}{0.130218}\approx 0.2655$
  • 在时刻2，${\gamma }_2(2)$ 最大，所以 $q_2^{\ast }=\text{状态2}$。

• 时刻 t=3:

  • ${\gamma }_3(1)=\frac{{\alpha }_3(1){\beta }_3(1)}{P(O|\lambda )}=\frac{0.04187\times 1}{0.130218}\approx 0.3215$
  • ${\gamma }_3(2)=\frac{{\alpha }_3(2){\beta }_3(2)}{P(O|\lambda )}=\frac{0.035512\times 1}{0.130218}\approx 0.2727$
  • ${\gamma }_3(3)=\frac{{\alpha }_3(3){\beta }_3(3)}{P(O|\lambda )}=\frac{0.052836\times 1}{0.130218}\approx 0.4058$
  • 在时刻3，${\gamma }_3(3)$ 最大，所以 $q_3^{\ast }=\text{状态3}$。

近似算法得到的最优路径为: $Q^{\ast }=(\text{状态3}\to \text{状态2}\to \text{状态3})$。

我们稍后会看到，这个结果与维特比算法得到的全局最优路径是不同的。

3. 维特比算法

维特比算法是解决 HMM 解码问题的标准答案。它同样运用了动态规划 (Dynamic Programming) 的思想，但目标与前向算法截然不同。

• 前向算法在递推时，将所有到达当前状态的路径概率进行求和。
• 维特比算法在递推时，只保留所有到达当前状态的路径中概率最大的那一条。

3.1 直观理解与核心定义

为了实现这个目标，维特比算法需要定义两个关键变量：

1. 最大概率变量 ${\delta }_t(i)$: 定义: 在时刻 $t$，所有以状态 $s_i$ 结尾的部分路径 $(q_1,\dots ,q_t=s_i)$ 中，能够生成观测子序列 $(o_1,\dots ,o_t)$ 的、概率最大的那条路径的概率值。

   $${\delta }_t(i)=\underset{q_1,\dots ,q_{t-1}}{\max }P(q_1,\dots ,q_t=s_i,o_1,\dots ,o_t|\lambda )$$

   这个 ${\delta }_t(i)$ 记录了到达“时刻 $t$、状态 $s_i$”这个节点的最优路径的“得分”。

2. 路径记忆变量 ${\psi }_t(i)$ (psi): 定义: 在时刻 $t$，使得 ${\delta }_t(i)$ 取得最大值的、那个在时刻 $t-1$ 的状态。

   $${\psi }_t(i)=\underset{1\le j\le N}{\mathrm{argmax}}[{\delta }_{t-1}(j)a_{ji}]$$

   这个 ${\psi }_t(i)$ 就像一个“路标”或“回溯指针”，它不记录概率值，而是记录路径本身。它告诉我们，要想到达“时刻 $t$、状态 $s_i$”这个最优节点，应该从“时刻 $t-1$”的哪个节点过来。

3.2 算法推导与步骤

维特比算法的流程可以分解为四个经典的动态规划步骤：

1. 初始化 (Initialization), $t=1$ 在初始时刻，到达状态 $s_i$ 的路径只有一条，就是直接从开始走到 $s_i$。

• 计算 ${\delta }_1(i)$:

  $${\delta }_1(i)={\pi }_i{b}_i(o_1),i=1,\dots ,N$$

  这表示在时刻1处于状态 $s_i$ 并观测到 $o_1$ 的路径的概率。

• 初始化 ${\psi }_1(i)$:

  $${\psi }_1(i)=0,i=1,\dots ,N$$

  因为时刻1之前没有状态，我们用0来表示起点。

2. 递推 (Recursion), for $t=2,\dots ,T$ 这是算法的核心。假设我们已经计算出了时刻 $t-1$ 所有的 ${\delta }_{t-1}(j)$，我们要计算时刻 $t$ 的 ${\delta }_t(i)$ 和 ${\psi }_t(i)$。

要想到达时刻 $t$ 的状态 $s_i$，必须从时刻 $t-1$ 的某个状态 $s_j$ 转移过来。对于每一个可能的 $j$，从开始到 $s_j$ 的最优路径概率是 ${\delta }_{t-1}(j)$，从 $s_j$ 转移到 $s_i$ 的概率是 $a_{ji}$。因此，经过 $(t-1,j)$ 再到 $(t,i)$ 的路径概率是 ${\delta }_{t-1}(j)a_{ji}$。

我们要在所有可能的上一步状态 $j$ 中，选择使得这个概率最大的那一个。

• 计算 ${\delta }_t(i)$:

  $${\delta }_t(i)=\underset{1\le j\le N}{\max }[{\delta }_{t-1}(j)a_{ji}]\cdot b_i(o_t)$$

• 计算 ${\psi }_t(i)$:

  $${\psi }_t(i)=\underset{1\le j\le N}{\mathrm{argmax}}[{\delta }_{t-1}(j)a_{ji}]$$

  这个 argmax 记录了是哪个 $j$ 使得上面的 max 成立。

3. 终止 (Termination) 当递推到最后时刻 $T$ 时，我们已经计算出了所有 ${\delta }_T(i)$。最终的最优路径的概率，就是这些值中的最大值。

• 最优路径概率 $P^{\ast }$:

  $$P^{\ast }=\underset{1\le i\le N}{\max }[{\delta }_T(i)]$$

• 最优路径的最后一个状态 $q_T^{\ast }$:

  $$q_T^{\ast }=\underset{1\le i\le N}{\mathrm{argmax}}[{\delta }_T(i)]$$

4. 路径回溯 (Path Backtracking) 现在我们知道了最优路径在时刻 $T$ 结束于 $q_T^{\ast }$。我们可以利用存储的 $\psi$ 指针，像多米诺骨牌一样，从后往前倒推出整条路径。 For $t=T-1,T-2,\dots ,1$:

$$q_t^{\ast }={\psi }_{t+1}(q_{t+1}^{\ast })$$

最终，我们便能得到完整的全局最优路径 $Q^{\ast }=(q_1^{\ast },q_2^{\ast },\dots ,q_T^{\ast })$。

3.3 走一遍维特比算法

我们使用之前文章中的盒子与球模型来完整地演算一遍。

• 模型参数:
  • $\pi =(0.2,0.4,0.4)$
  • $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}{cc}0.5& 0.5\\ 0.4& 0.6\\ 0.7& 0.3\end{array}\right)$ (红, 白)
• 观测序列 $O=(\text{红, 白, 红})$

1. 初始化 (t=1), 观测 $o_1=\text{红}$

• ${\delta }_1(1)={\pi }_1{b}_1(\text{红})=0.2\times 0.5=0.10$
• ${\delta }_1(2)={\pi }_2{b}_2(\text{红})=0.4\times 0.4=0.16$
• ${\delta }_1(3)={\pi }_3{b}_3(\text{红})=0.4\times 0.7=0.28$
• ${\psi }_1(1)=0,{\psi }_1(2)=0,{\psi }_1(3)=0$

2. 递推 (t=2), 观测 $o_2=\text{白}$

• 计算 ${\delta }_2(1)$ 和 ${\psi }_2(1)$:

  • ${\delta }_1(1)a_{11}=0.10\times 0.5=0.05$
  • ${\delta }_1(2)a_{21}=0.16\times 0.3=0.048$
  • ${\delta }_1(3)a_{31}=0.28\times 0.2=0.056\leftarrow \text{最大}$
  • ${\delta }_2(1)=0.056\times b_1(\text{白})=0.056\times 0.5=0.028$
  • ${\psi }_2(1)=3$ (因为最大值来自 ${\delta }_1(3)$)

• 计算 ${\delta }_2(2)$ 和 ${\psi }_2(2)$:

  • ${\delta }_1(1)a_{12}=0.10\times 0.2=0.02$
  • ${\delta }_1(2)a_{22}=0.16\times 0.5=0.08$
  • ${\delta }_1(3)a_{32}=0.28\times 0.3=0.084\leftarrow \text{最大}$
  • ${\delta }_2(2)=0.084\times b_2(\text{白})=0.084\times 0.6=0.0504$
  • ${\psi }_2(2)=3$ (因为最大值来自 ${\delta }_1(3)$)

• 计算 ${\delta }_2(3)$ 和 ${\psi }_2(3)$:

  • ${\delta }_1(1)a_{13}=0.10\times 0.3=0.03$
  • ${\delta }_1(2)a_{23}=0.16\times 0.2=0.032$
  • ${\delta }_1(3)a_{33}=0.28\times 0.5=0.14\leftarrow \text{最大}$
  • ${\delta }_2(3)=0.14\times b_3(\text{白})=0.14\times 0.3=0.042$
  • ${\psi }_2(3)=3$ (因为最大值来自 ${\delta }_1(3)$)

3. 递推 (t=3), 观测 $o_3=\text{红}$

• 计算 ${\delta }_3(1)$ 和 ${\psi }_3(1)$:

  • ${\delta }_2(1)a_{11}=0.028\times 0.5=0.014$
  • ${\delta }_2(2)a_{21}=0.0504\times 0.3=0.01512\leftarrow \text{最大}$
  • ${\delta }_2(3)a_{31}=0.042\times 0.2=0.0084$
  • ${\delta }_3(1)=0.01512\times b_1(\text{红})=0.01512\times 0.5=0.00756$
  • ${\psi }_3(1)=2$

• 计算 ${\delta }_3(2)$ 和 ${\psi }_3(2)$:

  • ${\delta }_2(1)a_{12}=0.028\times 0.2=0.0056$
  • ${\delta }_2(2)a_{22}=0.0504\times 0.5=0.0252\leftarrow \text{最大}$
  • ${\delta }_2(3)a_{32}=0.042\times 0.3=0.0126$
  • ${\delta }_3(2)=0.0252\times b_2(\text{红})=0.0252\times 0.4=0.01008$
  • ${\psi }_3(2)=2$

• 计算 ${\delta }_3(3)$ 和 ${\psi }_3(3)$:

  • ${\delta }_2(1)a_{13}=0.028\times 0.3=0.0084$
  • ${\delta }_2(2)a_{23}=0.0504\times 0.2=0.01008$
  • ${\delta }_2(3)a_{33}=0.042\times 0.5=0.021\leftarrow \text{最大}$
  • ${\delta }_3(3)=0.021\times b_3(\text{红})=0.021\times 0.7=0.0147$
  • ${\psi }_3(3)=3$

4. 终止与回溯

• 比较 ${\delta }_3(1)=0.00756,{\delta }_3(2)=0.01008,{\delta }_3(3)=0.0147$。

• 最大值是 ${\delta }_3(3)=0.0147$。所以最优路径的概率是 $P^{\ast }=0.0147$。

• 最优路径的最后一个状态是 $q_3^{\ast }=3$。

• 开始回溯:

  • $q_3^{\ast }=3$
  • $q_2^{\ast }={\psi }_3(q_3^{\ast })={\psi }_3(3)=3$
  • $q_1^{\ast }={\psi }_2(q_2^{\ast })={\psi }_2(3)=3$

维特比算法得到的全局最优路径为: $Q^{\ast }=(\text{状态3}\to \text{状态3}\to \text{状态3})$。

对比结论:

• 近似算法结果: (状态3 $\to$ 状态2 $\to$ 状态3)
• 维特比算法结果: (状态3 $\to$ 状态3 $\to$ 状态3)

两者结果不同。维特比算法的结果是真正意义上的全局最优解，它考虑了路径上每一步转移的代价，而近似算法没有。

4. 总结与展望

本次，我们成功攻克了 HMM 的解码问题。

• 问题核心: 寻找给定观测序列下，概率最大的那一条隐藏状态序列。
• 近似方法: 通过独立最大化每个时间点的 ${\gamma }_t(i)$ 来确定状态，此方法简单但有缺陷，可能产生非法或非最优的路径。
• 维特比算法: 作为解决解码问题的标准动态规划方法，它通过巧妙地定义最大概率变量 ${\delta }_t(i)$ 和路径记忆变量 ${\psi }_t(i)$，高效地找到了全局最优路径。
• 关键区别: 前向算法的核心是求和，而维特比算法的核心是取最大值。这微小但本质的差别，决定了它们解决的是完全不同的问题。

至此，我们已经系统地学习了隐马尔可夫模型的三个基本问题：评估（前向算法）、学习（鲍姆-韦尔奇算法）和解码（维特比算法）。