条件随机场 · 机器学习 POD

概率无向图模型

上一篇讲的 HMM 是一个有向图模型：隐状态 $y_t$ "生成"观测 $x_t$ ，前一个隐状态 "生成" 下一个隐状态，箭头表示因果方向。这种建模方式天然地定义了联合概率 $P(x, y)$ 。

但换一个视角：如果不去建模"谁生成谁"，而是直接描述变量之间的关联呢？这就引出了概率无向图模型（Markov Random Field, MRF），也叫马尔可夫随机场。

无向图的因子分解

一个无向图 $G = (V, E)$ 中，节点代表随机变量，无向边表示两个变量之间的直接依赖关系。图中没有箭头——不再区分"谁影响谁"。

团（clique）：图中任意两个节点之间都有边的完全子图。最大团：不能再加入任何节点的团。

概率无向图模型的核心定理——Hammersley-Clifford 定理告诉我们：满足正则条件的概率分布 $P(Y)$ 可以分解为最大团上的势函数之积：

P(Y) = \frac{1}{Z} \prod_{c \in \mathcal{C}} \Psi_c(Y_c)

其中 $\mathcal{C}$ 是所有最大团的集合， $\Psi_c(Y_c) \geq 0$ 是定义在团 $c$ 上的势函数（potential function）， $Z$ 是归一化常数（配分函数）：

Z = \sum_Y \prod_{c \in \mathcal{C}} \Psi_c(Y_c)

和有向图的条件概率相乘不同，无向图用势函数相乘再归一化。势函数不需要是概率，只要非负即可。

马尔可夫性

概率无向图模型有三种等价的马尔可夫性：

成对马尔可夫性：没有边相连的两个节点，在给定其余所有节点后条件独立。
局部马尔可夫性：每个节点在给定其邻居节点后，与所有其他节点条件独立。
全局马尔可夫性：被节点集 $C$ 分隔的两个节点集 $A, B$ ，在给定 $C$ 后条件独立。

这些性质直观上就是"信息只能通过边传递"——如果两个节点之间的所有路径都被阻断了（条件化的节点挡住了），它们就独立了。

条件随机场定义

CRF 的核心想法很简单：不去建模 $P(x, y)$ ，而是直接建模 $P(y \mid x)$ 。

一般定义

设 $X$ 和 $Y$ 是随机变量， $P(Y \mid X)$ 由无向图 $G = (V, E)$ 表示。如果在给定 $X$ 的条件下， $Y$ 的分布满足马尔可夫性：

P(Y_v \mid X, Y_w, w \neq v) = P(Y_v \mid X, Y_w, w \sim v)

其中 $w \sim v$ 表示 $w$ 和 $v$ 在图中相邻，那么 $(X, Y)$ 构成一个条件随机场。

直觉：每个标签 $Y_v$ 的取值只直接依赖它在图中的邻居标签——但注意，它可以依赖整个输入序列 $X$ 。

线性链 CRF

在序列标注问题中， $G$ 是最简单的线性链结构： $Y_1 - Y_2 - \cdots - Y_n$ 。此时最大团是相邻两个标签 $(Y_{t-1}, Y_t)$ ，CRF 定义为：

P(y \mid x) = \frac{1}{Z(x)} \exp\left(\sum_{t=1}^{T} \sum_{k} \lambda_k f_k(y_{t-1}, y_t, x, t) \right)

其中归一化因子为：

Z(x) = \sum_y \exp\left(\sum_{t=1}^{T} \sum_{k} \lambda_k f_k(y_{t-1}, y_t, x, t) \right)

特征函数

这里的 $f_k$ 就是特征函数——CRF 最核心的设计。特征函数分两类：

转移特征 $t_k(y_{t-1}, y_t, x, t)$ ：刻画相邻标签之间的关系。

例如：

t_1(y_{t-1}, y_t, x, t) = \begin{cases} 1, & \text{如果 } y_{t-1} = \text{B}, \; y_t = \text{I} \\ 0, & \text{其他} \end{cases}

"B 标签后面跟 I 标签"——在命名实体识别中，实体的开始（B）后面通常跟着实体的延续（I），这个特征的权重 $\lambda_1$ 应该学出一个正值。

状态特征 $s_k(y_t, x, t)$ ：刻画标签与观测之间的关系。

例如：

s_1(y_t, x, t) = \begin{cases} 1, & \text{如果 } y_t = \text{B}, \; x_t = \text{"北京"} \\ 0, & \text{其他} \end{cases}

"当前词是'北京'且标签是 B"——地名很可能是实体的开头。

把两类统一写成 $f_k$ ，对应的权重统一记为 $\lambda_k$ 。线性链 CRF 的参数化可以简写为：

P(y \mid x) = \frac{1}{Z(x)} \exp\left(\sum_{k=1}^{K} \lambda_k F_k(y, x) \right)

其中 $F_k(y, x) = \sum_{t=1}^{T} f_k(y_{t-1}, y_t, x, t)$ 是特征 $k$ 在整个序列上的累加。

在下面的交互图中切换 HMM 和 CRF，直观感受有向图与无向图的结构差异。

生成式模型：P(x,y) = P(y) P(x|y)

HMM：有向图模型。箭头表示因果/生成关系——隐状态生成观测，前一个隐状态生成下一个。每个观测 x_t 只能看到当前隐状态 y_t（观测独立假设）。

HMM vs CRF 对比

HMM 和 CRF 都用来做序列标注，但它们的哲学截然不同。

	HMM	CRF
图结构	有向图	无向图
建模目标	联合概率 $P(x, y)$	条件概率 $P(y \mid x)$
模型类型	生成式模型	判别式模型
观测假设	$P(x_t \mid y_t)$ ，每个观测只看当前隐状态	$f_k(y_{t-1}, y_t, x, t)$ ，特征可以依赖整个 x
参数含义	转移概率 $a_{ij}$ ，发射概率 $b_i(k)$	特征函数权重 $\lambda_k$
独立假设	观测独立假设（强）	无观测独立假设（弱）
特征灵活性	受限——只能用离散观测	任意特征函数，包括上下文窗口、词形、前后缀
归一化	局部归一化（每个条件概率独立归一化）	全局归一化（整个序列一起归一化）

为什么 CRF 更强

1. 打破观测独立假设

HMM 假设 $x_t$ 只依赖 $y_t$ 。这意味着做词性标注时，当前词的标签不能参考前一个词是什么。但在真实语言中，"我 / 吃 / 了 / 苹果"——"苹果"是名词还是专有名词，很大程度上取决于前面是"吃"还是"买了个"。

CRF 的特征函数可以写成 $f(y_t, x_{t-2}, x_{t-1}, x_t, x_{t+1})$ ——随便看上下文。

2. 全局归一化避免标签偏置

HMM 在每一步独立归一化（ $\sum_j a_{ij} = 1$ ， $\sum_k b_i(k) = 1$ ）。这可能导致标签偏置问题（label bias problem）：转出边少的状态会把概率集中在少数几个后继上，不管观测是什么。

CRF 对整个序列做一次归一化，不存在这个问题。

3. HMM 是 CRF 的特例

可以证明：对任意 HMM，都存在一个参数等价的 CRF，使得两者定义相同的条件概率 $P(y \mid x)$ 。反之不成立——CRF 严格比 HMM 表达能力更强。

具体地，取 CRF 的特征函数为：

f_{ij}(y_{t-1}, y_t) = \mathbb{1}[y_{t-1} = i, y_t = j], \quad \lambda_{ij} = \log a_{ij}

f_{ik}(y_t, x_t) = \mathbb{1}[y_t = i, x_t = k], \quad \lambda_{ik} = \log b_i(k)

代入 CRF 公式就能还原 HMM 的条件概率。但 CRF 允许更丰富的特征，所以 HMM $\subset$ CRF。

学习算法

CRF 的学习目标很直接：给定训练数据 $\{(x^{(i)}, y^{(i)})\}_{i=1}^{N}$ ，最大化条件对数似然。

对数似然

\mathcal{L}(\lambda) = \sum_{i=1}^{N} \log P(y^{(i)} \mid x^{(i)}) = \sum_{i=1}^{N} \left[ \sum_{k} \lambda_k F_k(y^{(i)}, x^{(i)}) - \log Z(x^{(i)}) \right]

CRF 的对数似然是凸函数——这是判别式模型的一大优势，意味着不会有局部最优的问题。

梯度推导

对第 $k$ 个参数求梯度：

\frac{\partial \mathcal{L}}{\partial \lambda_k} = \sum_{i=1}^{N} \left[ F_k(y^{(i)}, x^{(i)}) - \mathbb{E}_{P(y \mid x^{(i)})}[F_k(y, x^{(i)})] \right]

这个梯度的结构非常漂亮：观测到的特征值 - 模型期望的特征值。

第一项是特征在真实标注序列上的值——直接数就行。
第二项是特征在当前模型下的期望——需要对所有可能的标签序列求和。

梯度为零时，模型的特征期望等于经验特征值——这正是最大熵原理的体现。

前向-后向算法算期望

第二项中的期望涉及对所有 $y$ 求和，直接枚举不可行（ $N^T$ 种序列）。和 HMM 一样，用前向-后向算法来高效计算。

定义矩阵形式。对每个位置 $t$ ，定义 $N \times N$ 矩阵 $M_t(x)$ ：

M_t(y_{t-1}, y_t \mid x) = \exp\left(\sum_k \lambda_k f_k(y_{t-1}, y_t, x, t)\right)

那么归一化因子可以写成矩阵连乘：

Z(x) = \mathbf{1}^\top \left(\prod_{t=1}^{T} M_t(x)\right) \mathbf{1}

前向向量 $\alpha_t$ 和后向向量 $\beta_t$ 的递推：

\alpha_t^\top = \alpha_{t-1}^\top M_t(x), \quad \alpha_0 = \mathbf{1}

\beta_t = M_{t+1}(x) \beta_{t+1}, \quad \beta_{T+1} = \mathbf{1}

利用前向-后向向量，可以得到位置 $t$ 上标签对 $(y_{t-1}, y_t)$ 的边缘概率：

P(y_{t-1}, y_t \mid x) = \frac{\alpha_{t-1}(y_{t-1}) \cdot M_t(y_{t-1}, y_t \mid x) \cdot \beta_t(y_t)}{Z(x)}

特征 $f_k$ 的期望就可以用这些边缘概率高效计算：

\mathbb{E}[F_k(y, x)] = \sum_{t=1}^{T} \sum_{y_{t-1}, y_t} P(y_{t-1}, y_t \mid x) \cdot f_k(y_{t-1}, y_t, x, t)

整个前向-后向过程的时间复杂度是 $O(N^2 T)$ ，和 HMM 一样。

优化方法

有了梯度之后，可以用各种优化算法。实践中常用的是拟牛顿法（L-BFGS），因为 CRF 的参数空间通常很大（几万甚至几十万个特征），L-BFGS 只需要存储最近几步的梯度信息就能近似二阶信息，比普通梯度下降收敛快得多。

也可以加正则化防止过拟合。 $L_2$ 正则化等价于给参数加高斯先验：

\mathcal{L}_{\text{reg}}(\lambda) = \mathcal{L}(\lambda) - \frac{1}{2\sigma^2} \sum_k \lambda_k^2

$L_1$ 正则化可以产生稀疏解——让大多数特征权重为零，相当于自动做特征选择。

预测：维特比算法

训练好 CRF 后，对新的输入序列 $x$ ，要找最优标签序列：

y^* = \arg\max_y P(y \mid x) = \arg\max_y \sum_{t=1}^{T} \sum_k \lambda_k f_k(y_{t-1}, y_t, x, t)

因为 $\exp$ 是单调函数，最大化概率等价于最大化指数上的线性得分——不需要算 $Z(x)$ 。

这个问题的结构和 HMM 的解码问题完全一样：在一个格（trellis）上找一条得分最高的路径。解法就是维特比算法。

递推公式

定义：

\delta_t(j) = \max_{y_1, \dots, y_{t-1}} \sum_{\tau=1}^{t} \sum_k \lambda_k f_k(y_{\tau-1}, y_\tau, x, \tau), \quad \text{s.t. } y_t = j

递推：

\delta_t(j) = \max_{i} \left[\delta_{t-1}(i) + \sum_k \lambda_k f_k(i, j, x, t)\right]

\psi_t(j) = \arg\max_{i} \left[\delta_{t-1}(i) + \sum_k \lambda_k f_k(i, j, x, t)\right]

终止和回溯：

y_T^* = \arg\max_j \delta_T(j)

y_t^* = \psi_{t+1}(y_{t+1}^*), \quad t = T-1, \dots, 1

和 HMM 维特比的对比

	HMM 维特比	CRF 维特比
操作空间	概率（乘法）	得分（加法）
递推	$\delta_t(j) = \max_i [\delta_{t-1}(i) \cdot a_{ij}] \cdot b_j(o_t)$	$\delta_t(j) = \max_i [\delta_{t-1}(i) + \text{score}(i, j, x, t)]$
需要 $Z$	不需要（找 max 不受归一化影响）	不需要
复杂度	$O(N^2 T)$	$O(N^2 T)$

本质上是同一个算法，只是 HMM 在概率域做乘法（或者取对数后变成加法），CRF 直接在得分域做加法。如果把 HMM 的 $\log a_{ij} + \log b_j(o_t)$ 看作 CRF 的特征得分，两者完全等价。

这个想法在前沿里

CRF 作为序列标注的经典框架，在深度学习时代不但没有消失，反而以"最后一层"的角色继续发挥作用：

BiLSTM-CRF —— 2015 年 Lample 等人提出的 BiLSTM-CRF 架构至今仍是命名实体识别（NER）的强基线。BiLSTM 负责编码上下文，输出每个位置上各标签的"发射分数"；CRF 层学习标签之间的转移约束（比如"I-PER 不能跟在 B-LOC 后面"），在全局上保证输出序列的合法性。单靠 softmax 逐位置分类做不到这一点。
CRF Loss 在 Transformer 中 —— 即使用了 BERT 或其他预训练模型做 NER，在最后加一个 CRF 层仍然能带来 1-2 个 F1 点的提升。原因很简单：Transformer 的自注意力虽然能看到全局上下文，但 softmax 输出层还是独立地为每个位置选标签，不保证相邻标签的一致性。CRF 层补上了这一环。
结构化预测的回归 —— 近年来"能量模型（Energy-Based Models）"和"结构化预测"的思想正在回归。CRF 本质上就是一个对数线性能量模型： $P(y \mid x) \propto \exp(-E(y, x))$ ，其中 $E = -\sum_k \lambda_k F_k$ 。扩散模型、对比学习中的很多想法，都和这个能量函数框架有深刻联系。