第十章隐马尔可夫模型

\[\alpha_t(i) = P(o_1, o_2, \ldots, o_t, i_t = q_i | \lambda)$$ $$\beta_t(i) = P(o_{t+1}, o_{t+2}, \ldots, o_T | i_t = q_i, \lambda)$$ $$\delta_{t+1}(j) = \max_{i_1,\ldots,i_t} [\delta_t(i) a_{ij}] b_j(o_{t+1})\]

10.1 概述

隐马尔可夫模型（Hidden Markov Model，简称 HMM）是一种关于时序数据的概率模型，它在语音识别、自然语言处理、生物信息学、金融时间序列分析等领域有着广泛的应用。HMM 由马尔可夫链演变而来，但其核心特点在于：系统的实际状态是不可直接观测的隐藏状态，我们只能通过另一组可观测的输出来推断系统的内在状态。这种“双重随机性”——即隐藏状态的随机转移，以及给定隐藏状态后观测值的随机生成——使得 HMM 能够有效描述许多现实世界中的复杂现象。

从本质上讲，HMM 是一种生成式模型，它通过定义一个关于隐状态序列和观测序列的联合概率分布来建模。模型的核心思想可以概括为两点：第一，系统内部存在一条隐含的状态序列，这条序列满足马尔可夫性，即当前状态只与前一状态有关；第二，每一时刻的隐状态会对应产生一个可观测的输出，输出的分布由当前隐状态决定。正是这种“隐状态产生观测”的机制，使得 HMM 成为一种经典的序列建模工具。

10.2 HMM 的基本定义

10.2.1 模型参数

一个完整的隐马尔可夫模型由以下三个要素构成，我们将其记作参数三元组：

其中各个参数的含义如下：

状态转移概率矩阵 $A$：

其中 $N$ 表示可能的状态数，$q_i$ 和 $q_j$ 分别为时刻 $t$ 和 $t+1$ 的状态，$a_{ij}$ 表示从状态 $q_i$ 转移到状态 $q_j$ 的概率。显然，对任意 $i$ 有 $\sum_{j=1}^{N} a_{ij} = 1$，即每一行的转移概率之和为 $1$。

观测概率矩阵 $B$：

其中 $M$ 表示可能的观测值数目，$v_k$ 为第 $k$ 个可能的观测，$b_j(k)$ 表示在状态 $q_j$ 下观测到 $v_k$ 的概率。对任意 $j$ 有 $\sum_{k=1}^{M} b_j(k) = 1$。

初始状态概率向量 $\pi$：

表示时刻 $t=1$ 时系统处于状态 $q_i$ 的概率，且 $\sum_{i=1}^{N} \pi_i = 1$。

综上，给定 $\lambda = (A, B, \pi)$，HMM 就完全确定。我们用 $Q = \{q_1, q_2, \ldots, q_N\}$ 表示所有隐状态的集合，用 $V = \{v_1, v_2, \ldots, v_M\}$ 表示所有观测值的集合。

10.2.2 状态序列与观测序列

设 $I = (i_1, i_2, \ldots, i_T)$ 为长度为 $T$ 的隐状态序列（hidden state sequence），其中每个 $i_t \in Q$；设 $O = (o_1, o_2, \ldots, o_T)$ 为对应的观测序列（observation sequence），其中每个 $o_t \in V$。

HMM 产生观测序列的过程可以描述如下：首先根据初始分布 $\pi$ 选取初始隐状态 $i_1$；然后根据 $i_1$ 的观测分布 $b_{i_1}(\cdot)$ 产生第一个观测 $o_1$；接着根据状态转移分布 $A$ 由 $i_1$ 转移到 $i_2$，再由 $i_2$ 产生 $o_2$；依此类推，直到产生 $o_T$。整个过程的联合概率为：

10.2.3 HMM 的基本假设

HMM 基于以下两条基本假设：

齐次马尔可夫假设：假设隐藏的马尔可夫链在任意时刻 $t$ 的状态只依赖于前一时刻的状态，与其他时刻的状态无关，即：

观测独立性假设：假设在任意时刻 $t$ 的观测只依赖于当前时刻的隐状态，与其他时刻的观测和状态无关，即：

这两条假设使得 HMM 的概率计算和参数学习成为可能，同时也限制了模型的表达能力。在实际应用中，如果问题不满足这些假设，就需要考虑使用更复杂的模型，如条件随机场（CRF）等。

10.3 HMM 三个基本问题

在实际应用中，隐马尔可夫模型面临三类核心问题，分别对应不同的计算和推理需求。理解这三个问题对于正确应用 HMM 至关重要。

10.3.1 概率计算问题

问题描述：给定模型参数 $\lambda = (A, B, \pi)$ 和观测序列 $O = (o_1, o_2, \ldots, o_T)$，计算 $P(O \mid \lambda)$，即该观测序列出现的概率。

这是评估问题（evaluation problem），其核心在于如何高效地计算观测序列的概率。直接利用定义进行穷举的时间复杂度为 $O(N^T)$，因为所有可能的状态序列共有 $N^T$ 种，这在实际中是不可行的。解决这个问题的主要方法是前向-后向算法（Forward-Backward Algorithm），它利用动态规划将复杂度降低到 $O(N^2 T)$。

概率计算问题的应用场景包括：评估多个候选模型中哪个更有可能产生观测到的序列；在语音识别中评估不同词序列对应的模型概率；以及在后续的参数学习算法中作为中间计算步骤。

10.3.2 参数学习问题

问题描述：给定观测序列 $O = (o_1, o_2, \ldots, o_T)$，如何调整模型参数 $\lambda = (A, B, \pi)$ 使得 $P(O \mid \lambda)$ 最大？

这是学习问题（learning problem），即根据观测数据来估计模型参数。如果训练数据中同时包含观测序列和对应的状态序列（即有标注数据），则可以直接通过统计频率来估计参数，这属于有监督学习；如果只有观测序列而没有状态序列标注，则需要使用无监督学习方法，此时 Baum-Welch 算法（即隐状态版 EM 算法）是标准解决方案。

参数学习是 HMM 应用于实际问题的关键步骤，因为通常我们并不知道模型的参数值，需要从数据中学习得到。

10.3.3 状态预测问题

问题描述：给定模型参数 $\lambda = (A, B, \pi)$ 和观测序列 $O = (o_1, o_2, \ldots, o_T)$，如何找到最可能产生的该观测序列的隐状态序列 $I^* = (i_1^*, i_2^*, \ldots, i_T^*)$？

这是解码问题（decoding problem），其目标是求取最优的隐状态序列。解决这个问题最著名的算法是 Viterbi 算法，它也是一种动态规划算法，能够在 $O(N^2 T)$ 的时间内找到概率最大的隐状态序列。

状态预测问题在许多实际应用中有重要意义，例如：在语音识别中找到最可能对应的词序列；在基因序列分析中找到最可能的编码区段；在金融分析中推断市场状态的转换等。

10.4 前向-后向算法

前向-后向算法是解决概率计算问题的核心方法，通过引入前向变量和后向变量，利用动态规划思想高效计算 $P(O \mid \lambda)$。

10.4.1 前向算法

前向变量 $\alpha_t(i)$ 定义为到时刻 $t$ 为止、观测为 $o_1, o_2, \ldots, o_t$ 且时刻 $t$ 处于状态 $q_i$ 的联合概率：

初始化（$t = 1$）：

递推（对 $t = 2, 3, \ldots, T$）：

终止：

上述递推的直观理解是：$\alpha_{t-1}(j)$ 记录了到 $t-1$ 时刻且状态为 $q_j$ 的“前向概率”，将其乘以从 $q_j$ 到 $q_i$ 的转移概率并对所有 $j$ 求和，就得到到 $t$ 时刻且状态为 $q_i$ 的“未经观测 $o_t$ 加权”的概率，再乘以 $b_i(o_t)$ 即可得到加上 $o_t$ 后的前向概率。前向算法的时间复杂度为 $O(N^2 T)$，相比暴力枚举的 $O(N^T)$ 有本质性的改进。

10.4.2 后向算法

后向变量 $\beta_t(i)$ 定义为在时刻 $t$ 处于状态 $q_i$ 的条件下，从 $t+1$ 到 $T$ 的观测序列的条件概率：

初始化（$t = T$）：

递推（对 $t = T-1, T-2, \ldots, 1$）：

终止：

可以验证前向算法与后向算法得到的 $P(O \mid \lambda)$ 结果一致，它们从两个方向对同一概率进行分解。前向-后向算法不仅能计算总体概率，还可以进一步用于参数学习中的 E 步计算。

10.4.3 一些有用的一步概率

在 EM 算法的 E 步中，我们需要计算在给定观测序列和模型参数条件下，系统处于特定状态的概率。定义单步状态概率：

$\gamma_t(i)$ 表示在时刻 $t$ 处于状态 $q_i$ 的概率。

进一步，定义双步状态概率（用于计算状态转移的期望）：

$\xi_t(i, j)$ 表示在时刻 $t$ 处于状态 $q_i$ 且在时刻 $t+1$ 处于状态 $q_j$ 的联合概率。

注意 $\gamma_t(i) = \sum_{j=1}^{N} \xi_t(i, j)$，而 $\sum_{i=1}^{N} \gamma_t(i) = 1$。这些概率在 Baum-Welch 算法的参数重估公式中起到关键作用。

10.5 Viterbi 算法

Viterbi 算法用于解决状态预测问题，即给定观测序列 $O$ 和模型 $\lambda$，求取最可能对应的隐状态序列 $I^*$。该算法采用动态规划的思想，本质上是求取一条最优路径。

10.5.1 算法描述

定义最优路径变量 $\delta_t(i)$ 为在时刻 $t$ 到达状态 $q_i$ 并产生观测序列 $o_1, o_2, \ldots, o_t$ 的所有路径中概率最大的那一条对应的概率：

初始化（$t = 1$）：

其中 $\psi_t(i)$ 用于记录使得 $\delta_t(i)$ 最大化的前一状态索引。

递推（对 $t = 2, 3, \ldots, T$）：

终止：

回溯（对 $t = T-1, T-2, \ldots, 1$）：

由此得到最优隐状态序列 $I^* = (i_1^*, i_2^*, \ldots, i_T^*)$。

10.5.2 与前向算法的区别

Viterbi 算法与前向算法在递推形式上非常相似，但本质不同。前向算法对所有到达状态 $q_i$ 的路径概率进行求和，得到边缘概率 $P(o_1, \ldots, o_t, i_t = q_i \mid \lambda)$；而 Viterbi 算法只取所有路径概率的最大值，得到最优路径的概率。体现在公式上，前向递推中的 $\sum_{j=1}^{N} \alpha_{t-1}(j) a_{ji}$ 在 Viterbi 中被替换为 $\max_{1 \le j \le N} [\delta_{t-1}(j) a_{ji}]$。

这一区别使得 Viterbi 能找到“单个”最优路径而非所有路径的加权求和。在实际应用中，如果需要的不只是最优路径，而是所有路径的概率分布（用于计算后验概率等），则应使用前向算法。

10.6 Baum-Welch 算法（EM 形式参数估计）

当训练数据只有观测序列而没有对应的状态序列标注时，参数学习需要采用无监督学习方法。Baum-Welch 算法是 HMM 参数估计的标准方法，本质上是 EM 算法（Expectation-Maximization algorithm）在隐马尔可夫模型中的具体应用。

10.6.1 EM 算法的基本框架

EM 算法用于处理含隐变量的概率模型的参数估计问题。在 HMM 中，隐变量就是不可观测的状态序列 $I$。EM 算法通过交替执行两步来迭代优化参数：

E 步（Expectation）：计算在当前参数 $\lambda^{(\text{old})}$ 下，观测序列 $O$ 关于隐变量 $I$ 的期望（即计算隐状态概率的期望）；

M 步（Maximization）：利用 E 步得到的期望，重新估计参数 $\lambda^{(\text{new})} = (A, B, \pi)$，使得 $Q$ 函数（即完全数据的对数似然期望）最大化。

10.6.2 E 步

完全数据的对数似然为 $\log P(O, I \mid \lambda)$，则 EM 算法中的 $Q$ 函数定义为：

将 $P(O, I \mid \lambda)$ 的展开式代入并整理，$Q$ 函数可以分解为三项，分别仅涉及 $\pi$、$A$ 和 $B$。利用前面定义的前向-后向概率 $\gamma_t(i)$ 和 $\xi_t(i, j)$，我们有：

10.6.3 M 步

在 M 步中，我们需要对 $Q$ 函数分别对 $\pi$、$A$ 和 $B$ 求最大化（约束为各概率和为 $1$），这可以使用拉格朗日乘数法来求解。得到的重估公式如下：

初始状态概率：

状态转移概率：

观测概率：

上述重估公式的直观理解是：$a_{ij}^{\text{new}}$ 是从状态 $q_i$ 转移到 $q_j$ 的期望次数（加权求和）除以从状态 $q_i$ 出发的总期望次数；$b_j(k)^{\text{new}}$ 是在状态 $q_j$ 下观测到 $v_k$ 的期望次数除以到达状态 $q_j$ 的总期望次数。

10.6.4 算法流程

Baum-Welch 算法的完整流程如下：

1。 初始化：随机选取或用启发式方法选取初始参数 $\lambda^{(0)} = (A^{(0)}, B^{(0)}, \pi^{(0)})$；

2。迭代：对 $l = 0, 1, 2, \ldots$ 执行： - E 步：根据当前参数 $\lambda^{(l)}$ 计算 $\alpha_t(i)$、$\beta_t(i)$，进而计算 $\gamma_t(i)$ 和 $\xi_t(i, j)$； - M 步：根据 E 步的结果利用上述重估公式更新参数得到 $\lambda^{(l+1)}$；

3。终止：当 $\| \lambda^{(l+1)} - \lambda^{(l)} \|$ 或 $P(O \mid \lambda^{(l+1)}) - P(O \mid \lambda^{(l)})$ 的变化小于预设阈值时停止迭代。

Baum-Welch 算法保证对数似然函数单调递增，因此最终会收敛到局部最优解。由于初始值对最终结果有较大影响，实际应用中常采用多组随机初始化并取最优结果的方式。

10.7 有监督学习与无监督学习总结

在 HMM 的参数估计中，根据训练数据的不同形式，可以采用有监督学习或无监督学习两种策略。

10.7.1 有监督学习

适用场景：训练数据同时包含观测序列和对应的真实状态序列，即 $\{(O^{(1)}, I^{(1)}), (O^{(2)}, I^{(2)}), \ldots, (O^{(S)}), I^{(S)})\}$。

方法：直接通过统计频率来估计模型参数，这是一种最大似然估计（MLE）的直接应用。

具体而言，对于参数 $a_{ij}$、$b_j(k)$ 和 $\pi_i$，有：

其中 $\mathbf{1}(\cdot)$ 是指示函数。

有监督学习的优点是参数估计简单直接，且在标注数据充足时能够获得较为准确的参数估计。其缺点在于实际应用中标注数据往往难以获取，而手工标注状态序列本身的成本就非常高。

10.7.2 无监督学习

适用场景：训练数据仅包含观测序列，没有对应的状态序列标注，即 $\{O^{(1)}, O^{(2)}, \ldots, O^{(S)}\}$。

方法：采用 Baum-Welch 算法（EM 方法）。由于状态序列不可观测，直接的最大似然估计不可行，必须通过 EM 算法迭代地“猜测”隐状态序列并更新参数。

无监督学习的优势在于可以利用大量无标注数据，这是实际应用中的主要场景。然而，由于 EM 算法只能保证收敛到局部最优解，且对初始值敏感，最终模型的质量高度依赖于初始化策略。此外，当训练数据规模很大时，EM 迭代的收敛速度也可能成为瓶颈。

10.7.3 两者的比较与总结

有监督学习和无监督学习各有优缺点，在实际应用中需要根据具体问题选择合适的方法。

比较维度	有监督学习	无监督学习（Baum-Welch）
数据需求	需要标注的状态序列	只需观测序列
估计方法	频率计数（直接MLE）	EM迭代算法
计算复杂度	低（一次统计）	高（多次迭代）
解的质量	全局最优（标注正确时）	局部最优
标注成本	高	低
对未登录观测的处理	无法处理	需要平滑或回退机制

在实际应用中，如果条件允许（有足够的标注数据），有监督学习通常能提供更可靠的参数估计。但大多数情况下，研究者不得不依赖无监督的 Baum-Welch 算法。一种常见的折中方案是：先用少量标注数据通过有监督学习得到一个较好的初始参数，再用大量无标注数据通过 Baum-Welch 进行微调，这种“半监督”的策略往往能取得比单纯使用任何一种方法更好的效果。

公式汇总表

编号	公式名称	所属部分
(10.1)	HMM参数定义	§10.2.1
(10.2)	状态转移概率	§10.2.1
(10.3)	观测概率	§10.2.1
(10.4)	初始状态概率	§10.2.1
(10.5)	联合概率	§10.2.2
(10.6)	前向变量定义	§10.4.1
(10.7)	前向初始化	§10.4.1
(10.8)	前向递推	§10.4.1
(10.9)	前向终止	§10.4.1
(10.10)	后向变量定义	§10.4.2
(10.11)	后向初始化	§10.4.2
(10.12)	后向递推	§10.4.2
(10.13)	后向终止	§10.4.2
(10.14)	单步状态概率	§10.4.3
(10.15)	双步状态概率	§10.4.3
(10.16)	Viterbi初始化	§10.5.1
(10.17)	Viterbi递推	§10.5.1
(10.18)	Viterbi回溯	§10.5.1
(10.19)	Q函数定义	§10.6.2
(10.20)	Q函数展开	§10.6.2
(10.21)	π重估公式	§10.6.3
(10.22)	A重估公式	§10.6.3
(10.23)	B重估公式	§10.6.3

第十章 隐马尔可夫模型