隐马尔可夫模型（HMM）推导与维特比解码

小象实战讲义 · 自然语言处理

在上一节中，我们引入了隐马尔可夫模型（HMM）作为词性标注问题的概率框架。本节我们将深入HMM的数学核心，理解其如何从一个动态混合模型的视角进行形式化定义，并掌握其核心算法——维特比（Viterbi）算法，用于高效地解码出最可能的隐藏状态序列。学完本节，你将能够从概率图模型的角度理解HMM，并手动实现其关键参数估计和解码过程。

💡 核心导读

• HMM作为动态混合模型：理解HMM如何将简单的混合模型（如高斯混合模型）扩展到时序数据，其“动态”体现在隐藏状态间的马尔可夫链，“混合”体现在给定状态下的观测生成。
• HMM的三大核心问题与参数：明确HMM涉及的评估、解码和学习问题，并掌握其两个核心参数矩阵——状态转移矩阵和发射（释放）矩阵的数学定义与最大似然估计方法。
• 维特比算法原理：学习如何利用动态规划思想，高效地求解给定观测序列下最可能的隐藏状态序列（即解码问题），这是HMM应用于词性标注等任务的关键步骤。
• 从经典到现代的定位：了解HMM在NLP发展史上的重要地位及其当前适用场景，明确其与后续深度学习模型（如序列到序列模型）的承继关系。

从混合模型到动态混合模型

在概率建模中，我们常常从一个简单的生成视角出发。回顾之前学过的混合模型，例如高斯混合模型（GMM）。其核心思想是：我们观察到的数据点 $x$，并非直接来自一个单一的分布，而是源于多个潜在的“成分”（或状态）$z$。每个成分 $z=k$ 以一个先验概率 $\pi_k$ 被选中，然后数据 $x$ 从该成分对应的分布（如 $N(\mu_k, \sigma_k)$）中生成。模型的参数 $\theta = {\pi_k, \mu_k, \sigma_k}$ 可以通过期望最大化（EM）算法从观测数据 ${x_i}$ 中估计出来。

这个过程可以形式化为一个两层的概率图模型：

1. 选择一个隐含变量 $z \sim \text{Categorical}(\pi)$。
2. 给定 $z$，生成观测 $x \sim p(x|z; \theta_z)$。

隐马尔可夫模型（HMM） 可以看作是对混合模型的一个自然时序扩展，因此我们称其为动态混合模型。其“动态”性体现在：隐含状态 $z_t$ 不再是一个独立同分布的随机变量，而是构成了一条马尔可夫链。也就是说，当前时刻的隐藏状态 $z_t$ 的概率分布仅依赖于前一个时刻的隐藏状态 $z_{t-1}$。这种依赖关系由状态转移矩阵 $A$ 刻画，其中 $A_{ij} = p(z_t = j | z_{t-1} = i)$。

其“混合”性则保持不变：在每一个时刻 $t$，给定当前隐藏状态 $z_t$，观测变量 $x_t$ 从一个与状态相关的分布中独立生成，该分布由发射矩阵 $B$ 刻画，其中 $B_{j}(v) = p(x_t = v | z_t = j)$。

因此，HMM的生成过程可以描述为：

1. 初始化：根据初始状态分布 $\pi$ 选择第一个隐藏状态 $z_1$。
2. 对于每个时刻 $t = 1, 2, ..., T$： a. 根据当前状态 $z_t$ 的发射概率 $B_{z_t}$，生成观测 $x_t$。 b. 根据当前状态 $z_t$ 和转移矩阵 $A$，转移到下一个状态 $z_{t+1}$（对于 $t < T$）。

在词性标注任务中，隐藏状态 $z_t$ 对应词性标签（如NN, VB, JJ），观测 $x_t$ 对应单词本身。状态转移矩阵 $A$ 描述了词性序列的语法规律（例如，形容词JJ后接名词NN的概率较高），发射矩阵 $B$ 描述了某个词性生成特定单词的可能性（例如，给定词性NN，出现单词“table”的概率）。

HMM的形式化定义与参数估计

一个离散观测的HMM由以下五元组 $\lambda = (S, V, A, B, \pi)$ 定义：

• $S = {s_1, s_2, ..., s_N}$：所有可能的隐藏状态集合（如45种Penn Treebank词性标签）。
• $V = {v_1, v_2, ..., v_M}$：所有可能的观测集合（即词汇表）。
• $A = [a_{ij}]_{N \times N}$：状态转移概率矩阵，$a_{ij} = p(z_{t+1}=s_j | z_t = s_i)$。
• $B = [b_j(k)]_{N \times M}$：发射概率矩阵，$b_j(k) = p(x_t = v_k | z_t = s_j)$。
• $\pi = [\pi_i]_{N \times 1}$：初始状态概率分布，$\pi_i = p(z_1 = s_i)$。

参数的最大似然估计（MLE）

当我们可以获得已标注的平行语料（即每个句子都标注了正确的词性序列）时，HMM的参数可以通过简单的计数和归一化来估计，这本质上是最大似然估计。

假设我们有一个已标注语料库，其中包含 $L$ 个句子，每个句子是一系列（单词，词性）对。

1. 估计转移矩阵 $A$： $$a_{ij} = p(z_{t+1}=s_j | z_t = s_i) = \frac{C(s_i \rightarrow s_j)}{\sum_{k=1}^{N} C(s_i \rightarrow s_k)}$$ 其中 $C(s_i \rightarrow s_j)$ 表示在整个训练语料中，从状态 $s_i$ 转移到状态 $s_j$ 的次数。

2. 估计发射矩阵 $B$： $$b_j(k) = p(x_t = v_k | z_t = s_j) = \frac{C(s_j, v_k)}{\sum_{w \in V} C(s_j, w)}$$ 其中 $C(s_j, v_k)$ 表示状态 $s_j$ 生成观测 $v_k$（即单词 $v_k$ 被标注为词性 $s_j$）的次数。

3. 估计初始分布 $\pi$： $$\pi_i = p(z_1 = s_i) = \frac{C_{\text{start}}(s_i)}{\sum_{k=1}^{N} C_{\text{start}}(s_k)}$$ 其中 $C_{\text{start}}(s_i)$ 表示在训练语料中，句子以状态 $s_i$ 开头的次数。

下面我们用一个极小的示例来演示这个过程。

# HMM参数的最大似然估计（MLE）示例
import numpy as np

# 极小化的已标注训练语料（句子列表，每个句子是(单词, 词性)对列表）
tagged_corpus = [
    [('the', 'DET'), ('cat', 'NN'), ('sat', 'VB')],
    [('a', 'DET'), ('dog', 'NN'), ('ran', 'VB')],
    [('the', 'DET'), ('dog', 'NN'), ('barks', 'VB')],
]

# 1. 收集所有状态和观测
states_set = set()
observations_set = set()
for sentence in tagged_corpus:
    for word, tag in sentence:
        states_set.add(tag)
        observations_set.add(word)

states = sorted(list(states_set))  # ['DET', 'NN', 'VB']
observations = sorted(list(observations_set)) # ['a', 'barks', 'cat', 'dog', 'ran', 'sat', 'the']

N = len(states)  # 3
M = len(observations) # 7

state_to_idx = {s: i for i, s in enumerate(states)}
obs_to_idx = {o: i for i, o in enumerate(observations)}

# 2. 初始化计数矩阵
trans_count = np.zeros((N, N))  # 转移计数
emit_count = np.zeros((N, M))   # 发射计数
start_count = np.zeros(N)       # 起始状态计数

# 3. 遍历语料进行计数
for sentence in tagged_corpus:
    # 计数起始状态
    first_tag = sentence[0][1]
    start_count[state_to_idx[first_tag]] += 1
    
    for i in range(len(sentence)):
        word, tag = sentence[i]
        tag_idx = state_to_idx[tag]
        word_idx = obs_to_idx[word]
        
        # 计数发射
        emit_count[tag_idx, word_idx] += 1
        
        # 计数转移 (如果不是最后一个词)
        if i < len(sentence) - 1:
            next_tag = sentence[i+1][1]
            next_tag_idx = state_to_idx[next_tag]
            trans_count[tag_idx, next_tag_idx] += 1

# 4. 归一化得到概率矩阵 (加1平滑，避免零概率)
# 转移概率 A
A = (trans_count + 1) / (trans_count.sum(axis=1, keepdims=True) + N)
# 发射概率 B
B = (emit_count + 1) / (emit_count.sum(axis=1, keepdims=True) + M)
# 初始概率 pi
pi = (start_count + 1) / (start_count.sum() + N)

print("状态集合:", states)
print("观测集合:", observations)
print("\n转移概率矩阵 A (行:当前状态, 列:下一状态):")
for i, s_i in enumerate(states):
    print(f"  {s_i}: {[round(A[i, j], 3) for j in range(N)]}")
print("\n发射概率矩阵 B (行:状态, 列:观测词) - 部分显示:")
for i, s_i in enumerate(states):
    # 只显示该状态下概率非零的观测
    non_zero_indices = np.where(B[i, :] > 1/(M+1))[0] # 加平滑后的阈值
    non_zero_obs = [(observations[idx], round(B[i, idx], 3)) for idx in non_zero_indices]
    print(f"  {s_i}: {non_zero_obs}")
print(f"\n初始状态概率 pi: {[round(p, 3) for p in pi]}")

状态集合: ['DET', 'NN', 'VB']
观测集合: ['a', 'barks', 'cat', 'dog', 'ran', 'sat', 'the']

转移概率矩阵 A (行:当前状态, 列:下一状态):
  DET: [np.float64(0.167), np.float64(0.667), np.float64(0.167)]
  NN: [np.float64(0.167), np.float64(0.167), np.float64(0.667)]
  VB: [np.float64(0.333), np.float64(0.333), np.float64(0.333)]

发射概率矩阵 B (行:状态, 列:观测词) - 部分显示:
  DET: [('a', np.float64(0.2)), ('the', np.float64(0.3))]
  NN: [('cat', np.float64(0.2)), ('dog', np.float64(0.3))]
  VB: [('barks', np.float64(0.2)), ('ran', np.float64(0.2)), ('sat', np.float64(0.2))]

初始状态概率 pi: [np.float64(0.667), np.float64(0.167), np.float64(0.167)]

这个例子展示了如何从一个微型标注语料中统计出HMM的参数。实际应用中，语料库规模巨大（如百万词级），参数矩阵也会非常稀疏，需要采用更复杂的平滑技术（如Good-Turing、Katz回退等）来处理未登录词和罕见转移。

解码问题与维特比算法

在词性标注中，我们面对的是HMM的解码问题：给定观测序列 $\mathbf{x} = (x_1, x_2, ..., x_T)$ 和模型参数 $\lambda$，找到最有可能产生该观测序列的隐藏状态序列 $\mathbf{z}^* = (z_1, z_2, ..., z_T)$。即： $$\mathbf{z}^* = \arg\max_{\mathbf{z}} p(\mathbf{z} | \mathbf{x}, \lambda) = \arg\max_{\mathbf{z}} p(\mathbf{z}, \mathbf{x} | \lambda)$$

根据HMM的生成假设，联合概率可以分解为： $$p(\mathbf{z}, \mathbf{x} | \lambda) = \pi_{z_1} \cdot b_{z_1}(x_1) \cdot \prod_{t=2}^{T} a_{z_{t-1}, z_t} \cdot b_{z_t}(x_t)$$

一个直观但低效的方法是枚举所有可能的 $\mathbf{z}$（共有 $N^T$ 种组合），计算其概率并取最大。这显然不可行。维特比算法利用动态规划，将时间复杂度降低到 $O(T \cdot N^2)$。

维特比算法原理

算法维护两个核心表格：

• 维特比概率 $\delta_t(i)$：在时刻 $t$，所有到达状态 $s_i$ 的部分路径中的最大概率。 $$\delta_t(i) = \max_{z_1, ..., z_{t-1}} p(z_1,...,z_{t-1}, z_t=s_i, x_1,...,x_t | \lambda)$$
• 回溯指针 $\psi_t(i)$：记录使 $\delta_t(i)$ 取得最大值的时刻 $t-1$ 的状态索引。

算法步骤：

1. 初始化（$t=1$）： $$\delta_1(i) = \pi_i \cdot b_i(x_1), \quad \psi_1(i) = 0, \quad \text{for } i=1,...,N$$
2. 递推（$t=2,...,T$）： 对于每个状态 $j$： $$\delta_t(j) = \max_{1 \le i \le N} [\delta_{t-1}(i) \cdot a_{ij}] \cdot b_j(x_t)$$ $$\psi_t(j) = \arg\max_{1 \le i \le N} [\delta_{t-1}(i) \cdot a_{ij}]$$
3. 终止： $$P^* = \max_{1 \le i \le N} \delta_T(i)$$ $$z_T^* = \arg\max_{1 \le i \le N} \delta_T(i)$$
4. 回溯（$t=T-1,...,1$）： $$z_t^* = \psi_{t+1}(z_{t+1}^*)$$

最终得到最优路径 $\mathbf{z}^* = (z_1^*, z_2^*, ..., z_T^*)$。

下面我们实现维特比算法，对一个新的句子进行词性标注。

# —— 重新构建上文用到的微型数据（本节各代码块相互独立，可单独运行）
import numpy as np
tagged_corpus = [
    [('the', 'DET'), ('cat', 'NN'), ('sat', 'VB')],
    [('a', 'DET'), ('dog', 'NN'), ('ran', 'VB')],
    [('the', 'DET'), ('dog', 'NN'), ('barks', 'VB')],
]
states_set = set()
observations_set = set()
for sentence in tagged_corpus:
    for word, tag in sentence:
        states_set.add(tag)
        observations_set.add(word)
states = sorted(list(states_set))  # ['DET', 'NN', 'VB']
observations = sorted(list(observations_set)) # ['a', 'barks', 'cat', 'dog', 'ran', 'sat', 'the']
N = len(states)  # 3
M = len(observations) # 7
state_to_idx = {s: i for i, s in enumerate(states)}
obs_to_idx = {o: i for i, o in enumerate(observations)}
trans_count = np.zeros((N, N))  # 转移计数
emit_count = np.zeros((N, M))   # 发射计数
start_count = np.zeros(N)       # 起始状态计数
for sentence in tagged_corpus:
    # 计数起始状态
    first_tag = sentence[0][1]
    start_count[state_to_idx[first_tag]] += 1
    
    for i in range(len(sentence)):
        word, tag = sentence[i]
        tag_idx = state_to_idx[tag]
        word_idx = obs_to_idx[word]
        
        # 计数发射
        emit_count[tag_idx, word_idx] += 1
        
        # 计数转移 (如果不是最后一个词)
        if i < len(sentence) - 1:
            next_tag = sentence[i+1][1]
            next_tag_idx = state_to_idx[next_tag]
            trans_count[tag_idx, next_tag_idx] += 1
A = (trans_count + 1) / (trans_count.sum(axis=1, keepdims=True) + N)
B = (emit_count + 1) / (emit_count.sum(axis=1, keepdims=True) + M)
pi = (start_count + 1) / (start_count.sum() + N)

# 维特比算法实现
def viterbi_decode(obs_sequence, states, pi, A, B, obs_to_idx):
    """
    obs_sequence: 观测序列（单词列表）
    states: 状态列表
    pi, A, B: HMM参数
    obs_to_idx: 单词到索引的映射
    """
    T = len(obs_sequence)
    N = len(states)
    
    # 初始化 delta 和 psi
    delta = np.zeros((T, N))
    psi = np.zeros((T, N), dtype=int)
    
    # 第一步：初始化
    first_obs_idx = obs_to_idx.get(obs_sequence[0], -1)
    if first_obs_idx == -1:
        # 处理未登录词：假设所有状态发射该词的概率相等（一种简单平滑）
        b_first = np.ones(N) / N
    else:
        b_first = B[:, first_obs_idx]
    
    delta[0, :] = pi * b_first
    psi[0, :] = 0  # 第一列回溯指针无意义，可设为0
    
    # 第二步：递推
    for t in range(1, T):
        obs_idx = obs_to_idx.get(obs_sequence[t], -1)
        if obs_idx == -1:
            b_t = np.ones(N) / N  # 未登录词处理
        else:
            b_t = B[:, obs_idx]
        
        for j in range(N):
            # 计算 delta[t-1, i] * A[i, j] 的最大值
            trans_probs = delta[t-1, :] * A[:, j]
            max_val = trans_probs.max()
            max_idx = trans_probs.argmax()
            
            delta[t, j] = max_val * b_t[j]
            psi[t, j] = max_idx
    
    # 第三步：终止
    P_star = delta[T-1, :].max()
    z_T_star = delta[T-1, :].argmax()
    
    # 第四步：回溯
    best_path = [z_T_star]
    for t in range(T-1, 0, -1):
        prev_state = psi[t, best_path[-1]]
        best_path.append(prev_state)
    best_path.reverse()  # 反转得到从t=1到t=T的路径
    
    best_path_tags = [states[idx] for idx in best_path]
    return best_path_tags, P_star

# 使用前面估计的参数进行解码测试
test_sentence = ['the', 'dog', 'barks']
# 注意：我们的微型语料中'the','dog','barks'都是登录词
best_tags, prob = viterbi_decode(test_sentence, states, pi, A, B, obs_to_idx)
print(f"观测序列: {test_sentence}")
print(f"维特比解码得到的最优词性序列: {best_tags}")
print(f"该路径的联合概率: {prob:.6f}")

观测序列: ['the', 'dog', 'barks']
维特比解码得到的最优词性序列: ['DET', 'NN', 'VB']
该路径的联合概率: 0.005333

解码结果 ['DET', 'NN', 'VB'] 符合我们对“the dog barks”这个句子的语法直觉。维特比算法成功地找到了全局最优的标注序列。

HMM的局限与现代发展

隐马尔可夫模型因其清晰的概率解释、高效的解码算法和较好的实践效果，在自然语言处理、语音识别、生物信息学等领域曾占据核心地位数十年。它完美地诠释了如何将领域知识（如词性的马尔可夫假设）融入概率模型。

然而，HMM也存在明显的局限性：

1. 一阶马尔可夫假设过强：HMM 假设当前状态只依赖前一个状态；但一个词的词性可能依赖更远的上下文或整句结构，这属于状态转移层面的长程依赖，违背的是一阶马尔可夫假设，而不是观测独立性假设。观测独立性（当前观测只依赖当前状态）是另一条需要单独审视的假设。
2. 本节离散观测的特征表示有限：本节讨论的离散观测 HMM 把观测当作词表中的符号（单词），难以融入形态、前缀后缀、大小写等丰富特征；HMM 模型族本身也可以使用连续值或向量发射（如高斯发射），只是需要换成相应形式的发射分布。
3. 数据稀疏问题：即使在大语料上，转移矩阵和发射矩阵仍非常稀疏，需要复杂的平滑策略。

随着深度学习的发展，基于神经网络的序列标注模型（如 BiLSTM-CRF）以及基于注意力机制、Transformer 架构的预训练模型逐渐成为主流。需要区分：Seq2Seq 是编码器—解码器的任务范式，BERT 式词元分类并不属于 Seq2Seq 变体。这些模型：

• 能够自动学习从输入序列到输出序列的复杂映射，无需手工设计状态空间和概率分布形式。
• 可以利用连续的词向量作为输入，捕获丰富的语义和语法信息。
• 通过注意力机制，可以灵活地关注输入序列的任何部分，打破了马尔可夫假设的局部性限制。

今天怎么做：对于词性标注这类任务，当前工业界和学术界通常采用基于Transformer架构的预训练模型（如BERT）进行微调，或者使用专门的序列标注模型（如BiLSTM-CRF）。这些方法在各大基准测试上准确率远超传统的HMM。然而，HMM所蕴含的生成模型思想、动态规划的解码技巧，以及其作为概率图模型的典范地位，仍然是理解更复杂模型的重要基础。在一些计算资源受限、可解释性要求高，或标注数据极少的场景下，HMM依然有其用武之地。

📝 动手练一练

1. 概念辨析：HMM被描述为“动态混合模型”。请分别解释“动态”和“混合”在这个语境下的具体含义，并与静态的高斯混合模型（GMM）进行对比。

2. 手算练习：假设一个极简的HMM，状态集S={A, B}，观测集V={红, 绿}。模型参数如下：

   • 初始分布: π = [0.6, 0.4] (对应状态A, B)
   • 转移矩阵A: 从A到A概率0.7，A到B概率0.3；从B到A概率0.4，B到B概率0.6。
   • 发射矩阵B: 状态A发射“红”概率0.9，发射“绿”概率0.1；状态B发射“红”概率0.2，发射“绿”概率0.8。 给定观测序列 [红, 绿, 红]，请手动使用维特比算法计算最可能的状态序列及其概率（建议保留4位小数）。

本章小结

本节我们深入探讨了隐马尔可夫模型（HMM）的核心机理。我们首先从概率图模型的视角，将HMM理解为一种“动态混合模型”，其动态性源于隐藏状态间的马尔可夫链，混合性则体现在给定状态下的观测生成过程。接着，我们形式化定义了HMM的五元组参数，并学习了如何在拥有标注数据时，通过计数和归一化进行最大似然估计。最后，我们重点讲解了HMM解码问题的解决方案——维特比算法，该算法利用动态规划，高效地找到了给定观测序列下最可能的隐藏状态序列，并提供了完整的代码实现示例。

HMM是连接传统统计方法与现代神经模型的重要桥梁。它简洁而强大，其蕴含的生成思想、概率计算和解码技术至今仍在许多领域发光发热。

📋 行动清单

• 理解HMM“动态混合模型”这一概念的双重含义，并能与静态混合模型（如GMM）清晰对比。
• 掌握HMM参数（A, B, π）的最大似然估计方法，并能对小规模示例数据进行手动或编程计算。
• 掌握维特比算法的四个步骤（初始化、递推、终止、回溯），能够对简单例子进行手算推演，并理解其动态规划的本质。
• 思考HMM的独立性假设在词性标注任务中可能带来的问题，并了解现代序列标注模型（如基于深度学习的模型）是如何尝试解决这些问题的。

—— 小象教研组