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

这一篇要讲什么

命名实体识别、词性标注、信息抽取——这一类任务都要给序列里的每一个元素打标签。HMM（第十五篇 ）用生成式思路硬刚：建模联合分布 $P(\mathbf{X},\mathbf{Y})$，但代价是必须假设每个观测只依赖自己的隐状态。可现实里，bank 是名词还是动词，依赖于前一个词、后一个词、词缀、大小写、词典命中——这些重叠特征 HMM 全都用不了。

条件随机场（Conditional Random Field, CRF） 干脆放弃了对 $\mathbf{X}$ 建模的野心，直接建模 $P(\mathbf{Y}\mid\mathbf{X})$。一旦不再需要给观测序列讲一个生成故事，你就可以把任意多的、相互重叠的观测特征都堆进来。

这篇你会学到：

1. CRF 的判别式建模为什么在标注任务上打过 HMM 的生成式建模
2. 转移特征和状态特征如何共同定义 CRF 的打分机制
3. 前向后向算法在 CRF 里的新角色——计算 $Z(\mathbf{X})$ 和边缘概率
4. 对数似然的梯度为什么恰好等于"经验特征计数 − 模型期望特征计数"
5. Viterbi 解码：找出得分最高的标签序列

前置知识： 概率论基础（条件概率、贝叶斯）、HMM（第十五篇 ）、矩阵表示。

1. 从 HMM 到 CRF：从生成式到判别式

1.1 HMM 强加给你的两个假设

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})$，每个标签只看上一个标签。

马尔可夫假设大体可以接受，真正难受的是观测独立性——它直接堵死了"看后一个词"“看后缀"“查词典"这一类自然且高效的特征。

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

线性链 CRF 这样定义：

上图把两者的结构差异画了出来。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)$。

1.3 从 HMM 经 MEMM 到 CRF

最大熵马尔可夫模型（MEMM） 是从 HMM 到 CRF 之间的自然过渡：

MEMM 已经是判别式的，也允许任意 $\mathbf{X}$ 特征，但它在每个位置局部归一化。这带来了著名的**标注偏置（label bias）**问题：转移选项少的状态，因为局部 softmax 的"竞争对手"少，会不顾观测就独占概率。

CRF 用全局归一化根治了这个问题：分母里那个唯一的 $Z(\mathbf{X})$ 强制所有路径在同一个分母下竞争。一句话总结：

• HMM——生成式，局部归一化，观测独立。
• MEMM——判别式，局部归一化，有标注偏置。
• CRF——判别式，全局归一化，无标注偏置。

1.4 生成式 vs 判别式的更广视角

跳出序列模型，这套权衡是普适的。生成式模型把参数花在 $P(\mathbf{X})$ 上——左图那张平滑的紫色密度——如果你只关心决策边界，这部分预算其实是浪费的。判别式模型直接把所有参数压在条件决策边界上——右图那条锐利的对角等高线。朴素贝叶斯 vs 逻辑回归、HMM vs CRF，是同一组权衡的不同尺度版本。

2. 线性链 CRF 的数学框架

2.1 基本定义

输入：观测序列 $\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 符号，让第一个转移有定义。

2.2 特征函数分解

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）；转移特征面板列出的是与该位置决策一致的所有 (前标签, 当前标签) 配置。这些特征完全可以重叠——这正是 CRF 相对 HMM 真正释放出的表达能力。

势函数把这些特征带权求和、再取指数：

2.3 统一参数化

把所有特征函数堆成向量 $\mathbf{f}$，所有权重堆成 $\mathbf{w}$：

势函数变成一个干净的对数线性形式：

全局特征向量就是把所有位置加起来：

整个 CRF 就是一个序列层面的对数线性模型：

2.4 矩阵形式

为每个位置 $t$ 定义一个 $L \times L$ 的得分矩阵：

那么未归一化的路径得分恰好是矩阵连乘，配分函数也有简洁形式：

成本就是 $T$ 次 $L\times L$ 矩阵乘法，$O(TL^2)$，与前向后向算法同阶。

3. 前向后向：CRF 版本

3.1 前向递推

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

初始化（$t = 1$）：

递推（$t = 2, \dots, T$）：

终止：

直观上，$\alpha_t(j)$ 累积了所有"长度为 $t$、终点是标签 $j$“的路径质量。递推的意思是：要在 $t$ 时刻落到 $j$，必然是从 $t-1$ 时刻的某个 $i$ 转过来的。

复杂度：$O(TL^2)$。对比暴力 $O(L^T)$，这是"可行"和"不可能"之间的距离。

3.2 后向递推

对称地，$\beta_t(i)$ 是"从位置 $t$ 标签 $i$ 出发到达序列末端"的所有部分路径的得分和。从 $t = T$ 反向递推到 $t = 1$，同样 $O(TL^2)$。

3.3 用 $\alpha$ 和 $\beta$ 算边缘概率

跑完两轮，边缘概率几乎是免费的：

单标签边缘：

相邻标签对边缘：

trellis 图把几何意义画了出来：每个格点 $(t, j)$ 接收来自左侧的前向蓝色箭头与来自右侧的后向紫色箭头，两者乘积再除以 $Z(\mathbf{X})$，就是该位置的边缘概率。下一节梯度公式里要用的就是它。

3.4 数值稳定：log 空间

把许多正数连乘很快就会下溢，所以前向后向全程在 log 空间用 logsumexp 实现：

和让 softmax 稳定的技巧是同一个。

4. 参数学习：极大似然

4.1 目标函数

给定训练集 $\mathcal{D} = \{(\mathbf{X}^{(n)}, \mathbf{Y}^{(n)})\}_{n=1}^N$，最大化对数似然：

第一项关于 $\mathbf{w}$ 线性，没什么难度；难度全集中在 $\log Z$ 上。

实践中加 L2 正则——它不仅防过拟合，更重要的是让目标函数严格凹，保证全局最优唯一：

4.2 梯度：经验减期望

对 (6) 求导，得到对数线性模型的标准形式：

这就是所有最大熵模型梯度共有的形态：特征在数据里实际点亮了多少次，减去当前模型认为它该点亮多少次。训练过程把模型期望往经验期望上推；收敛时两者相等（最大熵条件）。

4.3 把期望降到 $O(TL^2)$

(7) 里的期望乍看不可处理——它是对 $L^T$ 条序列求和。但靠线性化和链结构可以拆开：把 $\mathbf{F}$ 按位置拆成局部和，期望与求和交换：

右侧的 pair-marginal 正是 (5) 算过的那一组，$O(TL^2)$。所以一次前向后向就同时给出 $\log Z$ 和所有梯度分量。

4.4 优化：L-BFGS

目标函数是凹的（加 L2 后严格凹），任何一阶方法都收敛到全局最优。工程上 L-BFGS 是 CRF 训练的标准选择：

• 拟牛顿方法，近似逆 Hessian，收敛接近二阶。
• “limited-memory” 版本只保留最近 $m$ 步梯度差，特征空间上百万维时仍然吃得消。
• 通常 50–200 次迭代收敛，每次迭代对每条训练序列跑一次前向后向。

参考实现：scipy.optimize.fmin_l_bfgs_b。

5. Viterbi 解码

5.1 解码问题

给定训练好的 CRF 和一条新的 $\mathbf{X}$，要找：

注意 $Z(\mathbf{X})$ 与 $\mathbf{Y}$ 无关，解码时根本不需要算它。

5.2 动态规划

定义 $\delta_t(j)$ 为"以位置 $t$ 标签 $j$ 结束的最优部分路径"的得分。把前向算法的 $\sum$ 改成 $\max$ 即可：

同时记录回溯指针：

到达 $T$ 后取 $y_T^* = \arg\max_j\delta_T(j)$，沿 $y_{t-1}^* = \psi_t(y_t^*)$ 回溯，就得到完整最优序列。

trellis 图把它直观化了：浅灰箭头是所有候选转移；橙色箭头是每一步胜出的 max；高亮节点串起来就是回溯路径。例句 “He left New York yesterday .” 被解码成 O O B-LOC I-LOC O O。复杂度依旧是 $O(TL^2)$。

6. 深度学习时代：BiLSTM-CRF

现代序列标注几乎都是"神经特征器 + CRF 输出层"的组合：

• BiLSTM（或 Transformer encoder）学每个 token 的上下文表示，相当于把人工设计的状态特征替换成可学的。
• CRF 层保留一个可学的标签转移矩阵 $A_{ij}$。这个非常关键：像"I-PER 必须跟在 B-PER 后面"这种约束是序列级的，单 token 的 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
38

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 Z(X)：log 空间下的前向算法。"""
        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），虚线框就是要喂给下游消费者的 span。
• 下半：每个 token 的边缘概率 $P(y_t\mid\mathbf{X})$（由前向后向算出），可以当作校准良好的置信度使用。注意它和 Viterbi 路径概率不是一回事——边缘概率是逐位置独立计算的，常用于主动学习、拒答策略、下游贝叶斯聚合。

7. 练习题

练习 1：CRF vs 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，唯一的本质差别是什么？

解答： trellis 和 $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$ 的整条路径——观测证据就在这一比较里被引入。

参考文献

[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.

系列导航

• 上一篇：第十五篇 —— 隐马尔可夫模型
• 下一篇：第十七篇 —— 降维与主成分分析
• 查看本系列全部 20 篇文章