机器学习数学推导（十六）：条件随机场

你将学到什么#

命名实体识别、词性标注、信息抽取——这些任务都要求给序列中的每个元素打上标签。HMM（第十五篇 ）采用生成式方法，通过建模联合分布 $P(\mathbf{X},\mathbf{Y})$ 来解决这一问题。但为了使联合分布可分解，它不得不付出高昂代价：每个观测值仅被允许依赖于其对应的隐状态标签。然而在真实文本中，“bank”究竟是名词还是动词，往往取决于前后文、词缀、大小写乃至词典查询结果——所有这些特征共同作用。

条件随机场（CRF） 则彻底放弃了生成式建模的野心，转而直接建模条件概率 $P(\mathbf{Y}\mid\mathbf{X})$ 。一旦不再需要为观测序列 $\mathbf{X}$ 构造生成过程，你就可以自由地引入任意多且相互重叠的 $\mathbf{X}$ 特征。

你将学到：

1. 为什么 CRF 的判别式建模在标注任务中优于 HMM 的生成式建模
2. 转移特征与状态特征如何共同定义 CRF 的评分机制
3. 前向-后向算法如何用于计算配分函数 $Z(\mathbf{X})$ 和边缘概率
4. 对数似然梯度为何可简化为 “经验特征计数减去模型期望特征计数”
5. 如何通过 Viterbi 解码找到得分最高的标签序列

前置知识： 概率论基础（条件概率、贝叶斯公式）、熟悉 HMM（第十五篇 ），以及对矩阵表示法的掌握。

从 HMM 到 CRF：生成式 vs 判别式#

HMM 强加的假设#

预测时需借助贝叶斯公式：$\mathbf{Y}^* = \arg\max_{\mathbf{Y}} P(\mathbf{Y}\mid\mathbf{X})$ 。该联合分布之所以可分解，依赖于两个关键但限制性强的假设：

• 观测独立性：$P(x_t \mid y_{1:T}, x_{\setminus t}) = P(x_t \mid y_t)$ ，即每个词元仅依赖于其自身标签。
• 一阶马尔可夫性：$P(y_t \mid y_{1:t-1}) = P(y_t \mid y_{t-1})$ ，即每个标签仅依赖于前一个标签。

马尔可夫假设通常尚可接受，但观测独立性假设才是真正的瓶颈：它禁止使用任何涉及邻近词元、词缀或基于当前标签的词典匹配等特征。

CRF 的核心思想：直接建模 $P(\mathbf{Y}\mid\mathbf{X})$ #

上图展示了结构差异。在 HMM（上图）中，每个 $x_t$ 是 $y_t$ 的子节点，模型必须解释观测；为保持联合分布可分解，每个 $x_t$ 只能依赖于 $y_t$ 。而在 CRF（下图）中，整个观测序列 $\mathbf{X}$ 被置于共享的“上下文带”中，每个团 $(y_{t-1}, y_t, \mathbf{X})$ 都可以访问 $\mathbf{X}$ 的任意函数。我们从不显式建模 $P(\mathbf{X})$ ，因此也无需对观测生成过程做任何假设。

你获得的优势：

• 任意且重叠的特征：词形、词缀、前缀、大小写、邻近词、词典匹配等可同时使用，无需担心重复计数惩罚。
• 灵活的特征工程：全局特征成为一等公民。
• 更强的实证性能：在标准序列标注基准上，CRF 通常比 HMM 高出 5–10 个 F1 分数。

你付出的代价： 配分函数 $Z(\mathbf{X})$ 需对全部 $L^T$ 条标签序列求和，且每次训练迭代都必须重新计算它及其梯度。所幸前向-后向算法可在 $O(TL^2)$ 时间内完成这一任务。

从 HMM 经 MEMM 到 CRF#

MEMM 已是判别式模型，且允许使用 $\mathbf{X}$ 的任意特征，但它在每个位置进行局部归一化。这导致了著名的标签偏置（label bias）问题：出边较少的状态会因局部 softmax 的候选更少而集中概率质量——即便观测并不支持该转移。

CRF 通过全局归一化解决了这一问题：分母中唯一的 $Z(\mathbf{X})$ 强制所有路径在同一基准下竞争。总结如下：

• HMM —— 生成式、局部归一化、观测独立。
• MEMM —— 判别式、局部归一化、存在标签偏置。
• CRF —— 判别式、全局归一化、无标签偏置。

更广视角下的生成式 vs 判别式#

即使跳出序列建模，这一权衡依然普适。生成式模型将参数用于建模 $P(\mathbf{X})$ ——如左图中平滑的紫色密度——若你只关心决策边界，这部分容量实属浪费。而判别式模型则将所有参数直接用于条件决策边界——如右图中锐利的对角等高线。朴素贝叶斯 vs 逻辑回归、HMM vs CRF，本质上是同一权衡在不同尺度上的体现。

线性链 CRF 的数学框架#

基本定义#

输入：观测序列 $\mathbf{X} = (x_1, x_2, \dots, x_T)$ 。 输出：标签序列 $\mathbf{Y} = (y_1, y_2, \dots, y_T)$ ，其中每个 $y_t \in \mathcal{Y} = \{1, 2, \dots, L\}$ 。

其中：

• $\Psi_t(y_{t-1}, y_t, \mathbf{X}) > 0$ 是位置 $t$ 的势函数，
• $Z(\mathbf{X}) = \sum_{\mathbf{Y}'} \prod_{t} \Psi_t(y'_{t-1}, y'_t, \mathbf{X})$ 是对所有标签序列归一化的配分函数。

按惯例，$y_0$ 是一个特殊的 START 符号，以确保首个转移有明确定义。

特征函数分解#

CRF 通过两类特征函数对势函数进行参数化：

示例：$t_1 = \mathbb{1}[y_{t-1}=\text{B-PER},\, y_t=\text{I-PER}]$ —— “人名延续”。

示例：$s_1 = \mathbb{1}[y_t=\text{B-LOC},\, x_t \text{ 首字母大写}]$ 。

上图以句子 “Barack Obama visited New York” 在位置 $t=4$ （“New” → B-LOC）为例展示。状态特征面板收集了在该位置激活 B-LOC 标签时 $\mathbf{X}$ 的所有相关属性（如首字母大写、下一词为 “York”、后缀为 ew），而转移特征面板则记录了所有与该决策一致的（前标签，当前标签）组合。关键在于，这些特征可自由重叠。

统一参数化#

矩阵形式#

这恰好是 $T$ 次 $L\times L$ 矩阵相乘，复杂度为 $O(TL^2)$ ，与前向-后向算法一致。

CRF 的前向-后向算法#

前向递推#

定义前向变量 $\alpha_t(j)$ 为所有在位置 $t$ 以标签 $j$ 结尾的部分路径的未归一化总得分。

直观上，$\alpha_t(j)$ 累积了所有长度为 $t$ 且终点为标签 $j$ 的部分序列的（未归一化）得分。递推式表明：要在时刻 $t$ 到达 $j$ ，必须从时刻 $t-1$ 的某个标签 $i$ 转移而来。

复杂度： $O(TL^2)$ —— 每步需对 $L \times L$ 个转移求和。相比暴力枚举的 $O(L^T)$ ，这是从不可行到可行的关键。

后向递推#

对称地，$\beta_t(i)$ 表示从位置 $t$ 标签 $i$ 开始至序列末尾的所有部分路径的未归一化总得分。递推从 $t = T$ 反向至 $t = 1$ ，同样耗时 $O(TL^2)$ 。

利用 $\alpha$ 和 $\beta$ 计算边缘概率#

完成前后向两遍计算后，边缘概率可直接得出：

格点图展示了其几何意义：每个单元 $(t, j)$ 接收来自左侧的前向箭头（蓝色）和右侧的后向箭头（紫色）。二者乘积经 $Z(\mathbf{X})$ 归一化后，即为后续梯度计算所需的逐位置边缘概率。

数值稳定性：对数空间#

这与 softmax 中常用的数值稳定技巧相同。

参数学习：极大似然估计#

目标函数#

第一项关于 $\mathbf{w}$ 是线性的，计算简单；难点全在 $\log Z$ 上。

梯度：经验减期望#

这与所有最大熵模型的梯度形式一致：特征在数据中实际出现的频次，减去当前模型预期的频次。训练过程推动模型期望向经验频次靠拢；收敛时二者完全匹配（即最大熵条件）。

在 $O(TL^2)$ 内计算期望#

右侧的标签对边缘概率正是 (5) 式所计算的内容，耗时 $O(TL^2)$ 。因此，一次前向-后向遍历即可同时获得 $\log Z$ 和全部梯度分量。

优化：L-BFGS#

目标函数是凹的（加入 L2 后严格凹），任意一阶方法均可收敛至全局最优。实践中，L-BFGS 是 CRF 训练的标准选择：

• 属拟牛顿法，近似逆 Hessian 矩阵，收敛速度接近二阶方法。
• “有限内存”版本仅存储最近 $m$ 次梯度差，即使特征维度超百万亦可高效处理。
• 通常 50–200 次迭代即可收敛，每次迭代对每条训练序列执行一次前向-后向计算。

标准实现：scipy.optimize.fmin_l_bfgs_b。

Viterbi 解码#

解码问题#

由于分母 $Z(\mathbf{X})$ 与 $\mathbf{Y}$ 无关，解码时无需计算它。

动态规划#

到达位置 $T$ 后，取 $y_T^* = \arg\max_j \delta_T(j)$ ，再通过 $y_{t-1}^* = \psi_t(y_t^*)$ 回溯，即可恢复完整最优序列。

上图直观展示了该过程：浅灰色箭头代表所有候选转移；橙色箭头标记每步保留的最大值路径；高亮节点构成回溯轨迹，将句子 “He left New York yesterday .” 解码为 O O B-LOC I-LOC O O。复杂度仍为 $O(TL^2)$ 。

深度学习时代的 CRF：BiLSTM-CRF#

• BiLSTM（或 Transformer 编码器）学习每个词元的上下文表示，以可学习特征取代手工设计的状态特征。
• CRF 层维护一个可学习的标签转移矩阵 $A_{ij}$ 。这至关重要，因为“I-PER 必须紧跟 B-PER，不能接 O”等约束是序列级的，逐词 softmax 无法表达，而 CRF 的转移矩阵可自然学习此类规则。
• 训练通过相同的负对数似然目标端到端优化整个模型。
• 推理仍使用 Viterbi 算法。

PyTorch 最小实现框架如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import torch
import torch.nn as nn

class BiLSTM_CRF(nn.Module):
    def __init__(self, vocab_size, tag_size, embed_dim, hidden_dim):
        super().__init__()
        self.embedding = nn.Embedding(vocab_size, embed_dim)
        self.lstm = nn.LSTM(embed_dim, hidden_dim // 2,
                            bidirectional=True, batch_first=True)
        self.hidden2tag = nn.Linear(hidden_dim, tag_size)
        # CRF 转移矩阵：transitions[i, j] 表示从 j 转移到 i 的得分
        self.transitions = nn.Parameter(torch.randn(tag_size, tag_size))

    def forward_score(self, emissions):
        """通过前向算法在 log 空间中计算 log Z(X)。"""
        T, L = emissions.shape
        alpha = emissions[0]  # (L,)
        for t in range(1, T):
            scores = (alpha.unsqueeze(0)
                      + self.transitions
                      + emissions[t].unsqueeze(1))
            alpha = torch.logsumexp(scores, dim=1)
        return torch.logsumexp(alpha, dim=0)

    def gold_score(self, emissions, tags):
        """计算真实标签序列的得分。"""
        score = emissions[0, tags[0]]
        for t in range(1, len(tags)):
            score += (self.transitions[tags[t], tags[t - 1]]
                      + emissions[t, tags[t]])
        return score

    def neg_log_likelihood(self, sentence, tags):
        emissions = self.hidden2tag(
            self.lstm(self.embedding(sentence))[0].squeeze(0)
        )
        return self.forward_score(emissions) - self.gold_score(emissions, tags)

损失函数即为 $\log Z(\mathbf{X}) - \text{score}(\mathbf{Y}_{\text{gold}}, \mathbf{X})$ ，也就是单样本下公式 (6) 的负值。反向传播通过前向算法自动计算出相同的“经验减期望”梯度——链式法则自然重现了公式 (7)。

端到端 NER 与置信度#

上图展示了训练好的 CRF 在句子 “Apple CEO Tim Cook visited Beijing last week” 上的推理输出：

• 上半部分：Viterbi 解码的 BIO 标签。三组连续的 B/I 被识别为实体跨度（ORG、PER、LOC），虚线框标出的即为传递给下游的实体范围。
• 下半部分：由前向-后向算法计算的逐词元边缘概率 $P(y_t \mid \mathbf{X})$ ，可作为校准良好的置信度分数。注意，这些边缘概率与解码路径概率不同——它们是逐位置独立计算的，适用于主动学习、拒答策略或下游贝叶斯聚合。

练习题#

练习 1：CRF 与 HMM 的特征能力对比。 在词性标注任务中，解释为何 CRF 可使用“下一个词是动词”作为特征，而 HMM 不行。

解答： HMM 的观测独立性假设要求 $P(x_t \mid y_t)$ 仅能查看 $x_t$ 本身。CRF 无此限制——其特征函数 $\mathbf{f}(y_{t-1}, y_t, \mathbf{X}, t)$ 以整个观测序列 $\mathbf{X}$ 为输入，因此“$x_{t+1}$ 是动词”这类特征完全合法。

练习 2：设计特征模板： 为命名实体识别设计三个特征函数。

解答： （1）转移特征：$\mathbb{1}[y_{t-1} = \text{B-ORG},\, y_t = \text{I-ORG}]$ （机构名延续）。 （2）状态特征（大小写）：$\mathbb{1}[y_t = \text{B-LOC},\, x_t \text{ 首字母大写}]$ 。 （3）上下文特征：$\mathbb{1}[y_t = \text{B-PER},\, x_{t-1} = \text{Mr.}]$ （前词为称谓）。

练习 3：前向算法复杂度： CRF 的 $T = 100$ 、$L = 50$ ，前向算法需多少次操作？与暴力法比较。

解答： 每个位置计算 $L$ 个前向值，每个值对 $L$ 个前驱求和：$O(TL^2) = O(100 \cdot 50^2) = O(2.5 \times 10^5)$ 。暴力法需枚举所有路径：$O(L^T) = O(50^{100}) \approx 10^{170}$ 。动态规划比暴力法快约 165 个数量级。

练习 4：梯度的含义： 用文字说明 $\nabla_\mathbf{w}\ell = \mathbf{F}_{\text{empirical}} - \mathbb{E}_{\text{model}}[\mathbf{F}]$ 的意义及收敛条件。

解答： 若某特征在训练数据中出现频次高于模型预期，其权重被调高；若模型高估该特征，则权重被调低。收敛时（梯度为零），经验与期望特征计数完全匹配。这就是最大熵条件：在所有满足经验特征均值的分布中，CRF 选择熵最大的那个。

练习 5：CRF Viterbi 与 HMM Viterbi 的区别。 两者均用 Viterbi，本质差异是什么？

解答： 格点结构与 $O(TL^2)$ 的 DP 递推完全相同。差异仅在于边得分：HMM 使用局部概率 $\log P(x_t \mid y_t) + \log P(y_t \mid y_{t-1})$ ；CRF 使用内积 $\mathbf{w}^\top \mathbf{f}(y_{t-1}, y_t, \mathbf{X}, t)$ ，其中特征向量可访问整个 $\mathbf{X}$ 的任意函数。

练习 6：为何 MEMM 有标签偏置而 CRF 没有。 用两状态小例说明局部归一化为何忽略观测，并解释全局归一化如何避免。

解答： 设状态 $A$ 仅有一条出边（至 $B$ ），而状态 $C$ 有 50 条。局部 softmax 后，$A \to B$ 概率为 1——因模型在 $A$ 处无不确定性，完全忽略观测。CRF 的分母 $Z(\mathbf{X})$ 对整条路径求和，故经 $A$ 的高分路径必须胜过所有经 $C$ 的路径——观测证据正通过此比较被纳入。

下一步#

到这里，监督学习（含序列）整条线我已经走完了。下一章起转入无监督表示学习，从最经典的降维方法——主成分分析（PCA）——开始。

PCA 看似只是“找方差最大的方向”，但它背后有四种等价视角：最大方差投影、最小重构误差、协方差矩阵的特征分解、数据矩阵的 SVD。这四个视角在不同问题里各自更顺手，一起构成了现代降维方法的语义骨架——核 PCA 是“换内积空间的 PCA”，概率 PCA 是“加高斯噪声的 PCA”，t-SNE / UMAP 是“换相似度度量的 PCA”。理解 PCA 的四视角等价，比单独学任何一个非线性降维方法都重要——它是这一整片方法族的母体。

参考文献#

[1] Lafferty, J., McCallum, A., & Pereira, F. C. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. ICML.

[2] Sutton, C., & McCallum, A. (2012). An introduction to conditional random fields. Foundations and Trends in Machine Learning, 4(4), 267-373.

[3] Huang, Z., Xu, W., & Yu, K. (2015). Bidirectional LSTM-CRF models for sequence tagging. arXiv:1508.01991 ↗ .

[4] Lample, G., Ballesteros, M., Subramanian, S., Kawakami, K., & Dyer, C. (2016). Neural architectures for named entity recognition. NAACL-HLT.

[5] Ma, X., & Hovy, E. (2016). End-to-end sequence labeling via bi-directional LSTM-CNNs-CRF. ACL.

本文是 ML Mathematical Derivations 系列的第 16 章。下一章：第 17 章：降维与主成分分析 。上一章：第 15 章：隐马尔可夫模型 。