🔗 02-机器学习 · 推导笔记 12:CRF 与最大熵模型(手写全流程)¶
最大熵模型(MaxEnt)是“不瞎猜”的建模哲学,线性链 CRF 是当前序列标注(词性标注、命名实体识别)的经典主力。面试常考:最大熵思想、CRF 与 HMM 的区别、标注偏置。
💡 一句话类比(最大熵):老师只告诉你“这个班平均身高 170cm”,让你猜每个人的身高——你会猜全班都差不多 170 附近(尽量均匀),而不是瞎编“有人 2 米、有人 1 米”。在满足已知约束的前提下,选最不确定(熵最大)的分布,这就是最大熵原理。
💡 一句话类比(CRF):词性标注就像猜一串词的词性——既要看每个词自己长啥样(“苹果”更像名词),又要看前后搭配(“吃苹果”里苹果是宾语名词,不是动词)。CRF 把“局部长相”和“前后搭配”都写成特征,在整句话上统一打分。
运行环境:Python 3.8+,仅依赖 numpy。
核心概念¶
(a) 🗂️ CRF 与最大熵:最大熵原理、指数族与线性链 CRF¶
最大熵模型是"不瞎猜"的建模哲学,线性链 CRF 是序列标注(词性标注、命名实体识别)的经典主力。本篇从最大熵推出指数族,再讲清 CRF 三个问题与对比表。
flowchart TB
N1["🔗 最大熵原理(不瞎猜)"] --> N2["从约束到指数族:与 LR 的关系"]
N2 --> N3["HMM 的两个痛点"]
N3 --> N4["线性链 CRF:定义与特征函数"]
N4 --> N5["概率计算:前向-后向"]
N4 --> N6["解码与学习:Viterbi + 梯度"]
N5 --> N7["三大序列模型对比表"]
N6 --> N8["常见 bug 与边界"]
N8 --> N9["自测清单"]
- N1 · 最大熵原理:在满足已知约束(比如"平均身高 170cm")的前提下,选择熵最大(最均匀、最不瞎猜)的分布——不给自己加没根据的假设。
- N2 · 从约束到指数族:把"期望与经验特征匹配"作为约束,用拉格朗日乘子求解,解出来是一族指数分布 p ∝ exp(Σλᵢfᵢ)。逻辑回归就是它单特征的特例——一个统一视角。
- N3 · HMM 的两个痛点:① 强假设(齐次马尔可夫 + 观测独立),难加任意特征;② 生成式建模 P(x,y),而判别式直接建模 P(y|x) 更直接;MEMM 还有标注偏置问题,于是要 CRF。
- N4 · 线性链 CRF 定义:对整条状态序列 y 打分 = 节点特征 + 边特征(转移特征)加权求和,再做全局归一化——特征函数可以任意设计,这是它比 HMM 灵活的本质。
- N5 · 概率计算:前向-后向:对应 HMM 的前向后向:CRF 的配分函数 Z(x) 用前向-后向算法算,复杂度同样是 O(T·N²),只是"矩阵"换成了特征加权。
- N6 · 解码与学习:解码用 Viterbi(找使打分最大的路径),学习用梯度上升/拟牛顿法迭代特征权重 λ——三个问题与 HMM 一一对应,只是枚举换成了特征打分。
- N7 · 三大序列模型对比表:HMM(生成式、强假设)、MEMM(判别式但有标注偏置)、CRF(判别式 + 全局归一化,无偏置)——这张表是面试必备。
- N8 · 常见 bug 与边界:特征函数没归一化导致数值爆炸、全局归一化忘记算 Z(x)、把 CRF 的边特征和 HMM 的转移矩阵混淆。
- N9 · 自测清单:能解释最大熵原理、能说清 CRF 与 HMM 三个问题的对应、能背出三大序列模型对比表。
📖 本章导读¶
这一章讲什么(全书第 13 章):从「最大熵原理」出发推出指数族分布(LR 是特例);再讲判别式的线性链 CRF——对整条序列指数打分 + 全局归一化,根治 HMM/MEMM 的标注偏置。
学完本章,你应该能:
- 从「约束下熵最大」推出 $P(y|x)\propto\exp(\sum_k\lambda_k f_k)$;
- 写出线性链 CRF 的 $P(Y|O)=\frac{\exp(\sum_t\sum_k\lambda_k f_k)}{Z(O)}$ 与归一化因子;
- 讲清「标注偏置」为什么来自局部归一化、全局归一化怎么救;
- 对比 HMM / MEMM / CRF 三兄弟(生成 vs 判别、局部 vs 全局)。
📌 全书第 13 章。阅读路径:本章导读 → 最大熵 · 特征函数 · 对比 → 自测清单 → 本章小结。
§1 最大熵原理(先建立直觉)¶
熵 $H(p) = -\sum_x p(x) \ln p(x)$ 度量分布的不确定程度。最大熵原理:在所有满足已知约束的分布中,选熵最大的那个——因为它在不违背事实的前提下最不武断。
经典例子:一个六面骰子,只知道两个约束:
- $\sum_i p_i = 1$(概率归一)
- $\sum_i i \cdot p_i = \mu$(平均点数已知,比如 $\mu = 4.5$)
拉格朗日乘子法:最大化 $H(p) + \lambda_0(1 - \sum p_i) + \lambda_1(\mu - \sum i p_i)$,求导得
$$p_i \propto e^{\lambda_1 i}$$
指数族形式:$\mu = 3.5$(均匀骰子)时 $\lambda_1 = 0$,退回均匀分布;$\mu = 4.5$ 时 $\lambda_1 > 0$,分布偏向大点数。
💡 直觉:约束是“事实”,熵是“谦虚”——最大熵 = 在事实约束下最谦虚的猜测。
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
import numpy as np
def maxent_dice(mu, faces=6, tol=1e-12):
"""数值求 lambda:p_i ∝ exp(lambda * i) 且均值 = mu(二分搜索)"""
lo, hi = -20.0, 20.0
for _ in range(200):
lam = (lo + hi) / 2
i = np.arange(1, faces + 1, dtype=float)
p = np.exp(lam * i); p = p / p.sum()
if (i * p).sum() < mu:
lo = lam
else:
hi = lam
return p
for mu in [3.5, 4.5, 5.5]:
p = maxent_dice(mu)
print(f"平均点数 = {mu} 最大熵分布 p = " + " ".join(f"{v:.3f}" for v in p))
print("\n解释:只知道平均点数,最大熵自动给出「最不武断」的分布(指数族)")
§2 最大熵模型:从约束到指数族(与 LR 的关系)¶
分类场景:输入 $x$、输出 $y$。定义特征函数 $f_k(x, y)$(如“词尾是‘ing’ 且 y=动词”)。经验约束:特征在数据上的期望要与模型期望一致:
$$E_{\tilde{p}}[f_k] = E_p[f_k]$$
在“满足全部约束 + 归一化”条件下最大化条件熵 $H(y \mid x)$,拉格朗日推导得到指数族/softmax 形式(这是重点结论):
$$p(y \mid x) = \frac{1}{Z(x)} \exp\left( \sum_{k} w_k f_k(x, y) \right), \qquad Z(x) = \sum_{y} \exp\left( \sum_k w_k f_k(x, y) \right)$$
与逻辑回归的关系(面试加分):当特征取 $f_k(x,y) = x_k \cdot \mathbb{1}[y=c]$(只用当前样本特征、每个类一套权重)时,上式退化为 softmax 回归:
$$p(y=c \mid x) = \frac{e^{w_c^{\top} x}}{\sum_{c'} e^{w_{c'}^{\top} x}}$$
所以 LR/softmax 是最大熵模型的特例;最大熵模型 = 更一般的“任意特征函数 + 指数族”。参数学习用最大似然 + 梯度上升(对偶问题等价于最大熵问题,这里不展开)。
📊 图 6:序列标注三件套对比——HMM(有向/生成式/局部归一化)vs 线性链 CRF(无向/判别式/全局归一化 Z(O)),后者天然规避标注偏置。
§3 为什么需要 CRF:HMM 的两个痛点¶
痛点 1:观测独立假设太强。HMM 假设 $o_t$ 只依赖 $q_t$,无法利用“前后词”这种重叠特征(如“前面是‘不’”、“词首大写”)。
痛点 2(更致命):局部归一化 → 标注偏置(label bias)。HMM 每一步概率 $P(q_t | q_{t-1}) \cdot P(o_t | q_t)$ 都是局部分开的。当某个状态“出度少”(能转移到的状态很少)时,它天然聚集更多概率,导致转移概率被路径长度/分支数稀释——解码偏向“少分支”路径。
💡 通俗例子:一条路有三个岔口,另一条路只有一个岔口。局部归一化会让“岔口少的路”看起来概率大(因为没得选),但实际走的人可能很少——局部归一化把“没得选”错当成了“更可能”。
CRF 的解法:全局归一化。整条序列一次性打分并归一化,概率不会被“出度少”偷走:
$$P(Y \mid O) = \frac{\exp\big(\text{score}(O, Y)\big)}{\sum_{Y'} \exp\big(\text{score}(O, Y')\big)}$$
§4 线性链 CRF:定义与特征函数¶
线性链 CRF:$O = (o_1, \dots, o_T)$ 观测序列,$Y = (y_1, \dots, y_T)$ 标注序列,$y_t \in \{1,\dots,N\}$。条件概率:
$$P(Y \mid O) = \frac{1}{Z(O)} \exp\left( \sum_{t=1}^{T} \sum_{k} \lambda_k f_k(y_{t-1}, y_t, O, t) \right)$$
特征函数分两类:
| 类型 | 形式 | 通俗含义 |
|---|---|---|
| 状态特征(发射) | $s_k(y_t, O, t)$ | “当前词是 X 且标签是 Y”(局部长相) |
| 转移特征 | $t_k(y_{t-1}, y_t, O, t)$ | “上一个标签是 A 且当前是 B”(前后搭配) |
特征值一般是 0/1 指示函数(也可以是实数值)。
归一化:$Z(O) = \sum_{Y} \exp\left(\sum_{t,k} \lambda_k f_k(y_{t-1}, y_t, O, t)\right)$ —— 对所有 $N^T$ 条路径求和,用前向算法高效计算($O(TN^2)$)。
💡 与 HMM 的对应:HMM 的 $\ln a_{ij}$ 对应转移特征权重,$\ln b_j(o_t)$ 对应发射特征权重——CRF 把这些“对数概率”泛化成了可学习的任意特征权重。
✍️ §4.1 手算 CRF:4 条路径的全局打分、Z(O) 与「标注偏置」数值对比¶
§3 说"局部归一化有标注偏置、CRF 全局归一化治它"——这里用 2 时刻、2 状态的 4 条路径,一笔一笔算出两种归一化的差异。
设定:时刻 $T=2$,状态 $y_t\in\{A,B\}$;发射分 $\lambda_E(A)=1.0,\ \lambda_E(B)=0.5$;转移分 $A{\to}A:0.3,\ A{\to}B:0.1,\ B{\to}A:0.1,\ B{\to}B:0.3$(对称,只演示归一化机制差异)。
第 1 步:4 条路径的全局分数(CRF 打分 = 两个发射 + 一个转移)
| 路径 | score = $\lambda_E(y_1)+\lambda_E(y_2)+\lambda_T(y_1,y_2)$ | $e^{\text{score}}$ |
|---|---|---|
| AA | $1.0+1.0+0.3=2.3$ | 9.974 |
| AB | $1.0+0.5+0.1=1.6$ | 4.953 |
| BA | $0.5+1.0+0.1=1.6$ | 4.953 |
| BB | $0.5+0.5+0.3=1.3$ | 3.669 |
第 2 步:CRF 全局归一化
$$Z(O)=9.974+4.953+4.953+3.669=23.550$$
$$P(AA\mid O)=\frac{9.974}{23.550}=0.424,\quad P(AB)=P(BA)=0.210,\quad P(BB)=0.156$$
第 3 步:HMM 式局部归一化(每步先归一化发射、再归一化转移)
$$P(AA)= \frac{e^{1.0}}{e^{1.0}+e^{0.5}}\times\frac{e^{0.3}}{e^{0.3}+e^{0.1}}=0.622\times0.550=0.342$$
$$P(AB)=0.622\times0.450=0.280,\quad P(BA)=0.378\times0.450=0.170,\quad P(BB)=0.378\times0.550=0.208$$
第 4 步:对比
| 路径 | CRF(全局) | HMM(局部) | 差异原因 |
|---|---|---|---|
| AA | 0.424 | 0.342 | AA 真实分最高,局部归一化把它"压低" |
| AB | 0.210 | 0.280 | A→B 转移占比 45%,局部归一化高估 |
| BB | 0.156 | 0.208 | 同理被局部归一化高估 |
手算收获:
- 全局归一化按整条路径总分竞争:AA 总分 2.3 最高 → 概率最高,公正反映"这条路径本身好不好"
- 局部归一化按每步比例竞争:A→B 是 A 状态仅有的两个出口之一(占 45%),被算成"很常见"——但 A→B 转移分只有 0.1,远低于 A→A 的 0.3,局部归一化把"没得选"误当成"更可能"
- 这就是标注偏置的数值原型:CRF 一个 $Z(O)$ 全局归一化直接根治
下面 numpy 复算。
# ---- §4.1 验证:numpy 复算 CRF 全局 vs 局部归一化 ----
import numpy as np
lamE = {'A': 1.0, 'B': 0.5}
lamT = {('A', 'A'): 0.3, ('A', 'B'): 0.1, ('B', 'A'): 0.1, ('B', 'B'): 0.3}
paths = ['AA', 'AB', 'BA', 'BB']
# CRF 全局
scores = {p: lamE[p[0]] + lamE[p[1]] + lamT[(p[0], p[1])] for p in paths}
expS = {p: np.exp(s) for p, s in scores.items()}
Z = sum(expS.values())
print('CRF 全局归一化:')
for p in paths:
print(f' {p}: score={scores[p]:.2f} exp={expS[p]:.4f} P={expS[p]/Z:.4f}')
assert abs(Z - 23.55) < 0.01
# HMM 局部
emis = {'A': np.exp(lamE['A']), 'B': np.exp(lamE['B'])}
Ze = emis['A'] + emis['B']
print('\nHMM 局部归一化:')
for p in paths:
p1 = emis[p[0]] / Ze
p2 = np.exp(lamT[(p[0], p[1])]) / (np.exp(lamT[(p[0], 'A')]) + np.exp(lamT[(p[0], 'B')]))
pp = p1 * p2
print(f' {p}: P={pp:.4f} (第1步 {p1:.3f} × 第2步 {p2:.3f})')
print('\n✓ 与手算一致:CRF 全局归一化 (AA=0.424) vs HMM 局部 (AA=0.342)')
# ---- 手写极简线性链 CRF:2 状态、2 观测、梯度上升学习特征权重 ----
def feature_counts(O, Y):
"""统计一条 (O, Y) 的特征计数:发射 cntE[状态, 观测] + 转移 cntT[状态, 状态]"""
T = len(O)
cntE = np.zeros((2, 2))
cntT = np.zeros((2, 2))
for t in range(T):
cntE[Y[t], O[t]] += 1
if t < T - 1:
cntT[Y[t], Y[t + 1]] += 1
return cntE, cntT
def forward_logZ(O, wE, wT):
"""前向算法求 log Z(对数空间,防下溢)"""
T = len(O)
def logsumexp(a):
m = a.max()
return m + np.log(np.exp(a - m).sum())
alpha = np.zeros((T, 2))
alpha[0] = wE[:, O[0]]
for t in range(1, T):
for j in range(2):
alpha[t, j] = wE[j, O[t]] + logsumexp(alpha[t-1] + wT[:, j])
return alpha, logsumexp(alpha[-1])
def crf_gradient(O, Y, wE, wT):
"""对数似然梯度 = 真实特征计数 - 模型期望(前向-后向求期望)"""
T = len(O)
alpha, logZ = forward_logZ(O, wE, wT)
Z = np.exp(logZ)
beta = np.zeros((T, 2))
beta[-1] = 1.0
for t in range(T - 2, -1, -1):
for i in range(2):
beta[t, i] = np.exp(wE[:, O[t+1]] + wT[i, :]).dot(beta[t+1])
gamma = alpha * beta / Z # gamma[t, j] = P(y_t = j | O)
xi = np.zeros((T - 1, 2, 2))
for t in range(T - 1):
for i in range(2):
for j in range(2):
xi[t, i, j] = (alpha[t, i] * np.exp(wT[i, j] + wE[j, O[t+1]]) * beta[t+1, j]) / Z
cntE, cntT = feature_counts(O, Y)
# 梯度 = 真实特征计数 - 模型特征期望(逐特征累加)
gE = cntE.copy()
for j in range(2):
for k in range(2):
gE[j, k] -= gamma[O == k, j].sum()
gT = cntT - xi.sum(axis=0)
return gE, gT, logZ
# 合成训练数据:由“真参数”生成 (O, Y) 对
rng = np.random.default_rng(0)
wE_true = np.array([[1.5, 0.0], [0.0, 1.5]]) # 状态0偏爱观测0,状态1偏爱观测1
wT_true = np.array([[1.0, -1.0], [-1.0, 1.0]]) # 倾向于保持原状态
def sample_seq(T=8):
Y, O = [], []
y = rng.choice(2)
for t in range(T):
Y.append(y)
# 简化采样:状态 y 以 0.8 概率发出观测 y(状态0→观测0,状态1→观测1)
o = y if rng.random() < 0.8 else 1 - y
O.append(o)
if t < T - 1:
# 简化采样:以 0.8 概率保持原状态
y = y if rng.random() < 0.8 else 1 - y
return np.array(O), np.array(Y)
data = [sample_seq() for _ in range(200)]
# 梯度上升训练
wE = np.zeros((2, 2)); wT = np.zeros((2, 2))
lr, epochs = 0.1, 50
for ep in range(epochs):
gE = np.zeros((2, 2)); gT = np.zeros((2, 2)); ll = 0.0
for O, Y in data:
ge, gt, logZ = crf_gradient(O, Y, wE, wT)
cntE, cntT = feature_counts(O, Y)
ll += (wE * cntE).sum() + (wT * cntT).sum() - logZ
gE += ge; gT += gt
wE += lr * gE / len(data); wT += lr * gT / len(data)
if ep % 10 == 0 or ep == epochs - 1:
print(f"epoch {ep:3d} 平均对数似然 = {ll / len(data):.3f}")
print("\n学习到的发射权重 wE(期望 状态0→观测0 大、状态1→观测1 大):")
print(wE.round(2))
print("学习到的转移权重 wT(期望 对角线大 = 倾向保持状态):")
print(wT.round(2))
§5 CRF 的三个问题(与 HMM 一一对应)¶
| 问题 | 目标 | 算法 | 与 HMM 对应 |
|---|---|---|---|
| 概率计算 | $P(Y \mid O)$ | 前向-后向(全局归一化) | HMM 前向-后向(但归一化在整条序列) |
| 解码 | $\arg\max_Y P(Y \mid O)$ | Viterbi(把边权换成 $\lambda_k f_k$ 的和) | HMM Viterbi |
| 学习 | 估计 $\lambda$ | 最大似然 + 梯度上升(梯度 = 真实计数 − 特征期望) | Baum-Welch(EM) |
学习的关键公式(§4 代码实现的就是它):对数似然对特征权重 $\lambda_k$ 的梯度是
$$\frac{\partial \ell}{\partial \lambda_k} = \sum_{(O,Y)} \Big[ \text{count}_k(O, Y) - E_{P_\lambda(Y \mid O)}[\text{count}_k] \Big]$$
“真实数据里出现了多少次”减去“模型认为应该出现多少次”——像不像把 LR 的梯度推广到了结构化输出?正是如此。工程上用 L-BFGS / 拟牛顿加速(sklearn 的 LogisticRegression 同款思路)。
§6 三大序列模型对比(必背表)¶
| 对比项 | HMM | MEMM | 线性链 CRF |
|---|---|---|---|
| 生成/判别 | 生成式(对 $P(O,Y)$ 建模) | 判别式 | 判别式(对 $P(Y\mid O)$ 建模) |
| 归一化 | 局部(每步) | 局部 → 标注偏置 | 全局(整条序列) |
| 特征 | 只有转移/发射(参数少) | 可加任意特征 | 可加任意重叠特征 |
| 假设 | 观测独立、一阶马尔可夫 | 一阶马尔可夫 | 线性链结构 |
| 数据量需求 | 小数据可用 | 中 | 较大(参数多) |
| 典型应用 | 语音、古早 POS | 早期 NER | 现代 POS/NER/分词 |
💡 记忆口诀:HMM 老实但天真(假设强),MEMM 聪明但偏心(局部归一化),CRF 聪明又公道(全局归一化)。
§7 常见 bug 与边界(面试踩坑区)¶
- 归一化对象搞错:CRF 归一化在整条序列上($Z(O)$ 对所有 $Y$ 求和),不是每步——这正是它和 HMM/MEMM 的本质区别;
- log 空间:$Z(O)$ 是 $N^T$ 项求和,直接算必下溢,必须 log-sum-exp 或前向算法;
- 特征退化:特征全为 0(或全为常数)→ 梯度为 0 学不动;特征太相关 → 权重不稳定,可加 L2 正则;
- 训练/解码标签域不一致:解码时用 Viterbi 必须保证特征函数与训练时完全一致;
- 收敛判据:看对数似然增量,别只看权重变化。
§8 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(8 问)¶
- 1. 口述最大熵原理(约束下熵最大)
- 2. 写出最大熵模型的指数族形式 $p(y\mid x) \propto e^{\sum w_k f_k}$
- 3. LR 是最大熵模型特例的理由
- 4. 什么是标注偏置,哪类模型有这个问题
- 5. CRF 与 HMM 的归一化区别(局部 vs 全局)
- 6. 状态特征与转移特征各是什么
- 7. CRF 是生成式还是判别式
- 8. CRF 解码用什么算法
L2 进阶(6 问)¶
- 9. 写出 CRF 的 $P(Y\mid O)$ 公式与 $Z(O)$ 定义
- 10. CRF 参数学习的梯度公式(真实计数 − 模型期望)
- 11. 为什么 $Z(O)$ 要用前向算法算
- 12. 特征函数为什么能是“重叠”的
- 13. MEMM 与 CRF 的差别
- 14. 词性标注 / NER 场景下 CRF 为什么比 HMM 好
L3 挑战(4 问)¶
- 15. 手写前向-后向求 $Z(O)$ 与特征期望
- 16. 推导 CRF 对数似然梯度(从 $\ell = \log P$ 开始)
- 17. 最大熵模型的对偶问题与 IIS/梯度方法的等价性
- 18. 从线性链推广到一般图 CRF 的难点
自测要点¶
- 15 分钟内写出 CRF 模型公式与梯度公式
- 能画图说明“局部归一化偷概率”的例子
- 能对比 HMM / MEMM / CRF 三行差异
🏁 本章小结¶
- 原理一句话:最大熵原理 → 指数族分布;线性链 CRF = 对整条序列指数打分 + 全局归一化。
- 必会公式:$P(Y|O)=\frac{\exp(\sum_t\sum_k\lambda_k f_k(y_{t-1},y_t,O,t))}{Z(O)}$;梯度 = 真实特征计数 − 模型期望计数(前向后向算)。
- 面试怎么考:最大熵为什么给指数族;LR/softmax 是最大熵特例;标注偏置的成因与解药;HMM/MEMM/CRF 三对比。
- 易错点:$Z(O)$ 要对所有可能标注序列求和(指数级,用前向后向);把 CRF 误当生成式模型。
自测清单没把握的条目,回到对应小节重读后再打勾。