# 勤奋的凯尔森同学10000h刻意练习Day14：序列标注的生成式与判别式 —— 看不见的状态怎么倒推？从HMM到CRF

所属专栏: 凯尔森的10000h刻意练习
Slogan: 一个36岁程序员, 研究生(学硕)，前世界500强top20软件开发Java工程师，用10000小时深耕AI, 目标Top10 AI资深工程师, 全程日更记录。

只看到同事连续三天带没带伞,你能倒推出这三天是晴是雨吗?

Day7的逻辑回归和感知机处理的是"一个输入一个输出"的简单映射。但现实中很多任务的数据是序列——语音是一帧帧时间序列,文本是一个个词,基因是一段碱基串。序列数据的核心特点是当前状态和前后文有关:今天下雨,明天大概率还下雨;"开"后面大概率是"车"不是"水"。

处理序列标注(给序列每个位置打标签)有两条经典路线:生成式的隐马尔可夫模型(HMM)建模联合概率 $P (X, Y)$ ,假设状态如何生成观测;判别式的条件随机场(CRF)直接建模条件概率 $P (Y ∣ X)$ ,不关心观测怎么生成。这就像Day7逻辑回归和Day11朴素贝叶斯的关系——一个判别式,一个生成式。今天先用HMM把三个核心问题(评估/解码/学习)和三组算法(前向-后向/Viterbi/Baum-Welch)讲透,再看CRF如何放松HMM的两个强假设、把"概率"换成"分数"完成同样的事。

# 1.1 HMM的定义

先用一句话抓住HMM:用一条看不见的状态链解释我们看到的观测序列——状态随时间转移,每个状态又按一定概率产生观测。天气与伞的例子就是:天气看不见→天气会变化→天气决定带伞概率→我们只能看到伞→根据伞倒推天气。

q_{1} ↓ o_{1} \to q_{2} ↓ o_{2} \to \dots \dots \to q_{T} ↓ o_{T}

上面一行是隐藏状态链(真正关心却看不到),下面一行是观测链(实际能看到的数据)。HMM的全部参数都在描述两件事:状态之间怎么转移、状态如何产生观测。

# 1.1.1 两个假设

HMM用一组隐藏的状态序列 ${q_{1}, q_{2}, \dots, q_{T}}$ 和一组观测序列 ${o_{1}, o_{2}, \dots, o_{T}}$ 建模。它有两个核心假设:

假设一:马尔可夫性(一阶)

当前状态只依赖前一个状态,与更早的历史无关:

P (q_{t} ∣ q_{t - 1}, q_{t - 2}, \dots, q_{1}) = P (q_{t} ∣ q_{t - 1})

这是"今天只看昨天"的假设。它不是说世界真的只有昨天影响今天,而是为了让模型可计算:长度为T的状态序列共有 $N^{T}$ 条可能路径,直接枚举是指数级;一阶假设让状态转移只需用一个 $N \times N$ 矩阵A描述,再配合1.2节的动态规划,三个问题都能在 $O (N^{2} T)$ 的多项式复杂度内解决。代价是长程依赖无法表达——天气不只和昨天有关,可能和前一周有关。但实践证明,一阶马尔可夫在很多场景已经够用。

假设二:观测独立性

当前观测只依赖当前状态,与其他时刻的状态和此前的观测无关:

P (o_{t} ∣ q_{1}, \dots, q_{T}, o_{1}, \dots, o_{t - 1}) = P (o_{t} ∣ q_{t})

即看到什么只取决于当前处于什么状态。注意条件里只能放 $o_{1}, \dots, o_{t - 1}$ ——若把 $o_{t}$ 自己也放进条件,概率就恒等于1,假设就失去意义了。

# 1.1.2 三组参数(λ = (A, B, π))

参数	含义	维度
$π$	初始状态分布 $P (q_{1} = s_{i})$	$N$
$A$	状态转移矩阵 $a_{i j} = P (q_{t + 1} = s_{j} ∥ q_{t} = s_{i})$	$N \times N$
$B$	观测发射矩阵 $b_{j} (k) = P (o_{t} = v_{k} ∥ q_{t} = s_{j})$	$N \times M$

N是隐藏状态数,M是观测值种类数。这三组参数合记为 $λ = (π, A, B)$ 。

# 1.1.3 一个具体例子:天气与伞

经典小例子:天气有晴/雨两种状态(N=2),你只能看到同事带没带伞(M=2)。

A = [0.7 0.4 0.3 0.6], B = [0.1 0.8 0.9 0.2], π = (0.6, 0.4)

$A$ :晴→晴 0.7,晴→雨 0.3;雨→晴 0.4,雨→雨 0.6
$B$ :晴天带伞 0.1 不带 0.9;雨天带伞 0.8 不带 0.2
$π$ :第一天晴的概率 0.6,雨 0.4

观测序列:带伞、带伞、不带伞。问题:这三天最可能的天气是什么?

# 1.2 HMM的三个问题

HMM有三个经典问题,分别对应"评估""解码""学习"。用人话说就是:评估=算概率(这串观测有多大可能出现)、解码=找路径(最可能经历了什么状态序列)、学习=学参数(只有观测时,A、B、π该长什么样)。

# 1.2.1 评估:前向-后向算法

暴力法为什么不行:给定模型 $λ$ 和观测序列 $O$ ,求 $P (O ∣ λ)$ 。暴力法枚举所有可能的状态序列,每个算概率,加起来。状态序列有 $N^{T}$ 种,每个序列长度T,总复杂度 $O (N^{T})$ 。 $N = 5, T = 100$ 时就是 $5^{100} \approx 1 0^{70}$ ,宇宙年龄都算不完。

前向算法(动态规划):前向变量 $α_{t} (i) = P (o_{1}, o_{2}, \dots, o_{t}, q_{t} = s_{i} ∣ λ)$ ——到时刻t为止,观测到 $o_{1} \dots o_{t}$ 且此刻处于状态 $s_{i}$ 的联合概率。

初始化: $α_{1} (i) = π_{i} \cdot b_{i} (o_{1})$
递推: $α_{t + 1} (j) = [\sum_{i} α_{t} (i) \cdot a_{i j}] \cdot b_{j} (o_{t + 1})$
终止: $P (O ∣ λ) = \sum_{i} α_{T} (i)$

复杂度 $O (N^{2} T)$ ——指数变多项式,动态规划的威力。

递推式的关键在求和号:昨天可能处于任意状态,把所有"昨天→今天"的路径概率汇总到一起,再乘今天状态产生当前观测的概率。所以 $α_{t} (i)$ 也可以直接读成:"走到第t天且今天是状态 $s_{i}$ ,前t天观测全部出现"的所有路径概率之和——前向算法做的是加法。

手推前向:天气与伞,观测 = (带伞, 带伞, 不带伞),即 $o_{1} = 0, o_{2} = 0, o_{3} = 1$ 。

t=1(初始化):

α_{1} (晴) α_{1} (雨) = π_{晴} \cdot b_{晴} (带伞) = 0.6 \times 0.1 = 0.06 = π_{雨} \cdot b_{雨} (带伞) = 0.4 \times 0.8 = 0.32

t=2:观测到第二个"带伞":

α_{2} (晴) α_{2} (雨) = [α_{1} (晴) \cdot 0.7 + α_{1} (雨) \cdot 0.4] \times 0.1 = [0.042 + 0.128] \times 0.1 = 0.017 = [α_{1} (晴) \cdot 0.3 + α_{1} (雨) \cdot 0.6] \times 0.8 = [0.018 + 0.192] \times 0.8 = 0.168

t=3:观测到"不带伞":

α_{3} (晴) α_{3} (雨) = [α_{2} (晴) \cdot 0.7 + α_{2} (雨) \cdot 0.4] \times 0.9 = [0.0119 + 0.0672] \times 0.9 = 0.0712 = [α_{2} (晴) \cdot 0.3 + α_{2} (雨) \cdot 0.6] \times 0.2 = [0.0051 + 0.1008] \times 0.2 = 0.0212

P (O ∣ λ) = 0.0712 + 0.0212 = 0.0924

后向算法:后向变量 $β_{t} (i) = P (o_{t + 1}, o_{t + 2}, \dots, o_{T} ∣ q_{t} = s_{i}, λ)$ ——从时刻 $t + 1$ 到末尾的观测序列概率,给定此刻处于 $s_{i}$ 。

初始化: $β_{T} (i) = 1$
递推: $β_{t} (i) = \sum_{j} a_{i j} \cdot b_{j} (o_{t + 1}) \cdot β_{t + 1} (j)$
终止: $P (O ∣ λ) = \sum_{i} π_{i} \cdot b_{i} (o_{1}) \cdot β_{0} (i)$

前向和后向算出的 $P (O ∣ λ)$ 完全相等(验证:手推天气与伞的后向算法,结果也是0.0924),它们是同一概率的两种分解方向。那为什么还要学后向?因为它是Baum-Welch的必备零件:E步要把同一时刻的前向概率和后向概率相乘,才能算出"此刻处于某状态"的后验 $γ$ 。

# 1.2.2 解码:Viterbi算法

逐时刻贪心为什么不行:给定观测序列找最可能的状态序列,最朴素的思路是每个时刻只凭当前观测选一个最可能的状态——看到带伞就选雨。这种做法完全没用上转移矩阵 $P (q_{t} ∣ q_{t - 1})$ ,等于放弃了状态之间的连续性;即便把上一步纳入考虑,每步只留一条路径也可能因小失大:这一步局部占优的选择,可能让后续整体概率更低。

正确做法是动态规划:每个时刻对每个状态都保留一条到达它的最优路径(共N条候选),走到终点再比较所有终态、回溯出全局最优。

Viterbi算法:Viterbi变量 $δ_{t} (i) = max_{q_{1} \dots q_{t - 1}} P (q_{1}, \dots, q_{t - 1}, q_{t} = s_{i}, o_{1}, \dots, o_{t} ∣ λ)$ ——到时刻t状态为 $s_{i}$ 的最优路径概率。

初始化: $δ_{1} (i) = π_{i} \cdot b_{i} (o_{1})$
递推: $δ_{t + 1} (j) = max_{i} [δ_{t} (i) \cdot a_{i j}] \cdot b_{j} (o_{t + 1})$
回溯: $ψ_{t} (j) = ar g max_{i} [δ_{t - 1} (i) \cdot a_{i j}]$ ——记住"从哪来"
终止: $max_{i} δ_{T} (i)$ 即最优路径概率

回溯从最后一个时刻开始,沿着 $ψ$ 表往前走,得到完整最优路径。

和前向递推对照看,两者只有一处不同:前向是 $\sum_{i}$ (所有路径加起来算总概率),Viterbi是 $max_{i}$ (每个状态只留概率最大的那一条)。 $ψ_{t} (j)$ 记录的就是"今天到达状态j,最佳上一站是谁"。前向做加法、Viterbi取最大,这是两个算法最核心的区别。

手推Viterbi:天气与伞,观测 = (带伞, 带伞, 不带伞)。

时刻	$δ_{t} (晴)$	$δ_{t} (雨)$	最佳上一站
t=1	$0.6 \times 0.1 = 0.06$	$0.4 \times 0.8 = 0.32$	—
t=2	$max (0.06 \times 0.7, 0.32 \times 0.4) \times 0.1 = 0.128 \times 0.1 = 0.0128$	$max (0.06 \times 0.3, 0.32 \times 0.6) \times 0.8 = 0.192 \times 0.8 = 0.1536$	晴←雨
t=3	$max (0.0128 \times 0.7, 0.1536 \times 0.4) \times 0.9 = 0.0614 \times 0.9 = 0.0553$	$max (0.0128 \times 0.3, 0.1536 \times 0.6) \times 0.2 = 0.0922 \times 0.2 = 0.0184$	晴←雨

最优路径:终态 $δ_{3} (晴) = 0.0553 > δ_{3} (雨) = 0.0184$ ,终态选晴;回溯 $ψ_{3} (晴) = 雨$ , $ψ_{2} (雨) = 雨$ 。

最优天气序列:雨 → 雨 → 晴。这和直觉吻合:前两天带伞大概率下雨,第三天不带伞大概率晴。

Viterbi对比贪心:逐时刻贪心完全不看状态转移,只比当天的发射概率:第1、2天看到带伞,雨天带伞0.8大于晴天带伞0.1,都选雨;第3天不带伞,晴天不带0.9大于雨天不带0.2,选晴——得到雨→雨→晴,这次碰巧和Viterbi一致。但换个数据它就会翻车:某个状态即使当天发射概率略占优,若转移到它的概率极低,整条路径可能反而更差,贪心看不到这种跨时刻的影响。Viterbi对每个状态都保留到达它的最优路径,到终点才终裁,保证全局最优。

# 1.2.3 学习:Baum-Welch算法

鸡生蛋问题(再次出现):如果已知参数 $λ = (A, B, π)$ ,前向/Viterbi就能评估和解码;如果已知状态序列,直接数数就能统计参数。但实际中参数和状态都未知,观测序列是唯一的输入——不知道状态就没法统计参数,不知道参数又没法判断状态,和Day10 GMM一模一样的困境。

Baum-Welch就是HMM上的EM,可以抓成一句话:**先用当前模型估计"每一天有多大概率是晴/雨",再把这些概率上的次数(软计数)拿来重新估计参数,如此反复。**E步负责软着色,M步负责重新数数。

E步:用当前参数 $λ^{o l d}$ 算每个时刻各状态的后验概率:

γ_{t} (i) = P (q_{t} = s_{i} ∣ O, λ) = \frac{α _{t} ( i ) \cdot β _{t} ( i )}{\sum _{j} α _{t} ( j ) \cdot β _{t} ( j )}

这个式子正好解释了为什么必须同时有前向和后向: $α_{t} (i)$ 管过去(从开头走到状态 $i$ 的概率), $β_{t} (i)$ 管未来(从状态 $i$ 出发、后面观测全部出现的概率),两者相乘就是"过去走得到、未来也解释得通"的联合概率 $P (O, q_{t} = s_{i} ∣ λ)$ ;除以所有状态之和 $P (O ∣ λ)$ 归一化,得到的就是后验 $P (q_{t} = s_{i} ∣ O, λ)$ 。

注意这是软分配,和Viterbi的硬选择有本质区别:Viterbi最终拍板"第一天=雨、第二天=雨、第三天=晴",每个时刻只选一个状态;Baum-Welch不急着选,而是保留"第一天晴40%雨60%、第二天晴15%雨85%"这样的软概率,交给M步当分数用。

更新转移矩阵A还需要知道"第t天从 $i$ 转到 $j$ "的后验,于是还有相邻时刻的转移后验:

ξ_{t} (i, j) = \frac{α _{t} ( i ) \cdot a _{i j} \cdot b _{j} ( o _{t + 1} ) \cdot β _{t + 1} ( j )}{\sum _{i^{'}, j^{'}} α _{t} ( i ^{'} ) \cdot a _{i^{'} j^{'}} \cdot b _{j^{'}} ( o _{t + 1} ) \cdot β _{t + 1} ( j ^{'} )}

分子按顺序读就是过去 × 转移 × 当前观测 × 未来:走到 $i$ (过去)、 $i \to j$ 的转移、在 $j$ 产生观测 $o_{t + 1}$ 、从 $j$ 继续解释剩余观测(未来),即整条序列经过" $i \to j$ 这一步"的联合概率;分母对所有可能的 $(i^{'}, j^{'})$ 求和做归一化。 $γ$ 看的是点(某时刻在某状态的概率), $ξ$ 看的是边(某步发生某转移的概率)——这就是HMM比GMM多出来的量,因为状态之间有马尔可夫依赖,转移矩阵A必须靠边的信息来学。

M步:把E步的软计数当成真实计数,重新统计三组参数:

\overset{π}{^}_{i} = γ_{1} (i)

\overset{a}{^}_{i j} = \frac{\sum _{t = 1}^{T - 1} ξ _{t} ( i , j )}{\sum _{t = 1}^{T - 1} γ _{t} ( i )}

\hat{b}_{j} (k) = \frac{\sum _{t : o_{t} = v_{k}} γ _{t} ( j )}{\sum _{t = 1}^{T} γ _{t} ( j )}

参数	软计数含义
$π_{i}$	第一时刻处于 $s_{i}$ 的软计数 $γ_{1} (i)$
$a_{i j}$	走 $i \to j$ 的期望次数 / 从 $i$ 出发的期望次数
$b_{j} (k)$	状态 $j$ 产生观测 $v_{k}$ 的期望次数 / 状态 $j$ 出现的期望次数

后两个公式就是概率最朴素的定义 $P (j ∣ i) =$ "同时发生 $i \to j$ 的次数 ÷ 发生 $i$ 的次数",只不过真实次数换成了期望次数。

收敛性:标准EM理论保证每轮正确更新后观测似然不降,即 $P (O ∣ λ^{n e w}) \geq P (O ∣ λ^{o l d})$ ;但 $P (O ∣ λ)$ 一般非凸,不保证找到全局最优,不同初始化可能收敛到不同局部解——和GMM的EM完全一样,实践中常以多组初始化选最好的结果。每轮迭代用前向-后向扫一遍序列,复杂度 $O (N^{2} T)$ 。

与Day10 GMM的对应关系:两者EM思想一致——E步算隐变量后验,M步用后验更新参数;区别在于HMM的隐变量有时间上的马尔可夫依赖,所以E步除了单时刻后验 $γ_{t} (i)$ ,还必须算相邻转移的后验 $ξ_{t} (i, j)$ 来更新A。

	GMM	HMM
隐变量	每个样本属于哪个分量	每个时刻处于哪个状态
E步	算样本对分量的责任度 $γ_{i k}$	算点后验 $γ_{t} (i)$ 和边后验 $ξ_{t} (i, j)$
M步	更新 $π_{k}, μ_{k}, Σ_{k}$	更新 $π_{i}, a_{i j}, b_{j} (k)$
样本关系	样本独立,无转移	相邻状态有马尔可夫依赖,需学习A
似然单调性	保证	保证
收敛性	局部最优	局部最优

# 1.3 NumPy实战:HMM天气与伞

公式和手推统一用1-based时间索引(t=1,2,3);代码里数组遵循Python惯例从0索引,alpha[0]对应公式里的t=1,阅读时注意错开一位。

import numpy as np

# A：状态转移矩阵
# 0 = 晴
# 1 = 雨
A = np.array([[0.7, 0.3],
              [0.4, 0.6]])
# B：观测发射矩阵
# 0 = 带伞
# 1 = 不带伞
B = np.array([[0.1, 0.9],
              [0.8, 0.2]])
pi = np.array([0.6, 0.4])
# obs：观测序列
# 0 = 带伞
# 1 = 不带伞
obs = [0, 0, 1]  # 带伞, 带伞, 不带伞

states = ['晴', '雨']

T = len(obs)
N = 2

# === 前向算法 ===
alpha = np.zeros((T, N))
# Forward 初始化
for i in range(N):
    alpha[0, i] = pi[i] * B[i, obs[0]]
# Forward 递推    
for t in range(1, T):
    for j in range(N):
        alpha[t, j] = B[j, obs[t]] * sum(alpha[t-1, i] * A[i, j] for i in range(N))
print("前向 alpha:", np.round(alpha, 4))
print("P(O|lambda) =", round(alpha[-1].sum(), 4))

# === 后向算法 ===
beta = np.zeros((T, N))
# 最后一天全部设置成1，已经到了最后一天，后面没有观测了，所以“未来观测出现的概率”就是1
beta[-1] = 1.0
# Backward 递推
for t in range(T-2, -1, -1):
    for i in range(N):
        beta[t, i] = sum(A[i, j] * B[j, obs[t+1]] * beta[t+1, j] for j in range(N))
print("\n后向 beta:", np.round(beta, 4))
print("P(O|lambda) backward =", round(sum(pi[i] * B[i, obs[0]] * beta[0, i] for i in range(N)), 4))

# === Viterbi ===
delta = np.zeros((T, N))
# 当前最优路径是从哪个前一个状态来的
psi = np.zeros((T, N), dtype=int)
# Viterbi 初始化
for i in range(N):
    delta[0, i] = pi[i] * B[i, obs[0]]
# Viterbi 递推    
for t in range(1, T):
    for j in range(N):
        vals = [delta[t-1, i] * A[i, j] for i in range(N)]
        psi[t, j] = np.argmax(vals)
        delta[t, j] = max(vals) * B[j, obs[t]]
path = [np.argmax(delta[-1])]
for t in range(T-2, -1, -1):
    path.append(psi[t+1, path[-1]])
path.reverse()
print("\nViterbi 最优路径:", [states[s] for s in path])

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

前向 alpha: [[0.06   0.32  ]
 [0.017  0.168 ]
 [0.0712 0.0212]]
P(O|lambda) = 0.0924

后向 beta: [[0.1635 0.258 ]
 [0.69   0.48  ]
 [1.     1.    ]]
P(O|lambda) backward = 0.0924

Viterbi 最优路径: ['雨', '雨', '晴']

1
2
3
4
5
6
7
8
9
10
11

前向=后向=0.0924,验证了两种算法的一致性;Viterbi给出雨→雨→晴,与手推一致。

# 1.4 CRF:从生成式到判别式

# 1.4.1 生成式与判别式

HMM是生成式模型——建模 $P (X, Y) = P (Y) P (X ∣ Y)$ ,需要假设状态如何生成观测。但很多时候我们只关心 $P (Y ∣ X)$ :给定句子,直接预测词性标签,不需要知道"名词怎么生成词"。**条件随机场(CRF)**就是直接建模 $P (Y ∣ X)$ 的判别式序列模型。

	生成式	判别式
建模目标	$P (X, Y) = P (Y) P (X ∥ Y)$	$P (Y ∥ X)$
典型模型	朴素贝叶斯、HMM、GMM	逻辑回归、CRF、SVM
需要建模	数据怎么"生成"的(观测的分布)	直接建模决策边界/后验
优点	可生成样本,处理缺失数据	不浪费精力建模观测分布,通常准确率更高
缺点	假设强(如朴素贝叶斯的条件独立),可能不准	不能生成样本

HMM"多做的那件事"具体在哪?它的 $P (X ∣ Y) = \prod_{t} P (o_{t} ∣ q_{t})$ 要求对每个状态建模观测的分布,而词性标注里我们根本不关心"名词生成某个词的概率",只关心"给定词,它最可能是什么词性"。这部分建模不仅多余,还被观测独立性假设捆住了手脚。CRF的思路就是砍掉它——不再规定"X如何生成",但仍然保留标签之间的链式结构 $y_{t - 1} \to y_{t}$ ,真正放宽的是允许特征函数自由依赖整个输入X。

# 1.4.2 CRF的定义与线性链形式

CRF直接建模条件概率:

P (Y ∣ X) = \frac{1}{Z ( X )} exp (t = 1 \sum T k \sum λ_{k} f_{k} (y_{t - 1}, y_{t}, X, t))

这个公式第一次看会发懵,其实可以先定义一个路径分数:

Score (X, Y) = t = 1 \sum T k \sum λ_{k} f_{k} (y_{t - 1}, y_{t}, X, t)

CRF就简化成:

P (Y ∣ X) = \frac{e ^{Score (X, Y)}}{Z ( X )}

直觉是:CRF不是直接写"概率是多少",而是对每条候选标签序列不断叠加特征分数(合法转移+2.5、当前词大写+1.8、不合理转移-2.7...),最后 $e^{Score}$ 把分数变成正数权重,再除以 $Z (X)$ 归一化成概率。

$f_{k} (y_{t - 1}, y_{t}, X, t)$ 是特征函数:可以看当前标签 $y_{t}$ 、前一个标签 $y_{t - 1}$ 、整个输入X、位置t——能看全局信息
$λ_{k}$ 是特征权重(模型参数,可正可负)
$Z (X) = \sum_{Y} e^{Score (X, Y)}$ 是配分函数,对所有可能的标签序列求和——可以理解成"给所有候选路径做一次全局softmax"

关键区别:HMM的 $P (Y)$ 和 $P (X ∣ Y)$ 是分开的概率;CRF的所有信息都编码在特征函数和权重里,不需要拆分。

一般CRF对任意图结构有效,但实践中最常用的是线性链CRF——标签序列是一条链, $y_{t}$ 只和 $y_{t - 1}$ 相邻:

P (Y ∣ X) = \frac{1}{Z ( X )} exp (t \sum [λ_{k} f_{k} (y_{t - 1}, y_{t}, X, t) + μ_{l} g_{l} (y_{t}, X, t)])

这里把特征函数分成两类:

转移特征 $f_{k} (y_{t - 1}, y_{t})$ :依赖相邻标签对,类似HMM的 $a_{i j}$ ——线性链CRF依然保留这种相邻标签的链式结构
状态特征 $g_{l} (y_{t}, X, t)$ :依赖当前标签和输入,类似HMM的 $b_{j} (o_{t})$ ——但能看整个输入X,不再受观测独立假设约束

# 1.4.3 特征函数:CRF灵活的关键

词性标注里的特征函数通常就是0/1指示函数,满足条件取1、否则取0,例如:

f1:前一个标签是B-ORG且当前是I-ORG时取1(实体名内部,B-ORG后面合法接I-ORG)
f2:当前词首字母大写且标签是B-ORG时取1
f3:前一个词是"开"且当前标签是B-ORG时取1

注意f2能看当前词的拼写、f3能看前一个词——它们都能读整个句子X和位置t。HMM的发射概率 $b_{j} (o_{t})$ 只能看当前观测 $o_{t}$ ,CRF的状态特征没有这个限制,这就是CRF比HMM强的关键所在。

# 1.4.4 CRF就是序列版逻辑回归

Day7讲过:逻辑回归就是最大熵模型。CRF的形式和最大熵完全一致——都是在约束下最大化条件熵,解都是softmax(指数族)形式。差别只是:

逻辑回归:输入一个x,输出一个y
CRF:输入一个序列X,输出一个序列Y

逻辑回归假设每个位置的标签独立;CRF通过转移特征 $f_{k} (y_{t - 1}, y_{t})$ 显式建模相邻标签的依赖关系。

# 1.4.5 HMM是CRF的特例

当CRF的特征函数只取"当前观测等于某个值"的指示函数、且权重取对数概率形式时,CRF退化为HMM。具体地:

转移特征 $f_{i j} (y_{t - 1} = i, y_{t} = j) = 1$ ,权重 $λ_{i j} = lo g a_{i j}$
状态特征 $g_{j k} (y_{t} = j, o_{t} = v_{k}) = 1$ ,权重 $μ_{j k} = lo g b_{j} (k)$

代入CRF公式,指数展开后恰好是HMM的 $P (Y) \cdot P (X ∣ Y)$ 。严格地说,是HMM所诱导的条件分布 $P (Y ∣ X)$ 可以表示为一个具有特定局部特征形式的线性链CRF——这样表述比"HMM是CRF的特例"更严谨,因为HMM本身是联合分布模型,CRF是条件分布模型。直觉上,可以把HMM的固定概率参数看成CRF特征权重的一种特殊情况。

场景	HMM	CRF
用"下一个词是动词"做特征	受观测独立假设限制,无法直接使用	直接写特征函数
用"当前词是大写"做特征	需离散化进发射概率	任意特征函数
标签间依赖	固定一阶	可任意阶(实践中一阶最常见)
灵活性	受观测独立假设约束	可利用丰富输入特征,在许多序列标注任务中更灵活(实际效果取决于特征设计、数据规模和具体任务)

# 1.5 CRF的推断与学习

# 1.5.1 推断:与HMM同构(概率换分数)

线性链CRF的推断和HMM几乎一样,只是把概率换成"分数"(exp后的权重):

前向(未归一化):

α_{1} (j) = exp (k \sum λ_{k} f_{k} (START, y_{1} = j, X, 1))

α_{t} (j) = i \sum α_{t - 1} (i) \cdot exp (k \sum λ_{k} f_{k} (y_{t - 1} = i, y_{t} = j, X, t))

后向、Viterbi的结构和HMM完全一样。定义局部因子:

ψ_{t} (i, j) = exp (k \sum λ_{k} f_{k} (y_{t - 1} = i, y_{t} = j, X, t))

那么HMM里的 $a_{i j} \cdot b_{j} (o_{t})$ 在CRF里就被替换成 $ψ_{t} (i, j)$ ——两者结构完全同构,只是"乘概率"变成"乘势能"。所以学完HMM的三组算法,CRF的推断基本免费——同一套动态规划框架,生成式算概率,判别式算分数。

解码时还有一个关键简化:由于 $Z (X)$ 对给定X是固定的,与具体候选路径无关,所以:

ar g Y max P (Y ∣ X) = ar g Y max Score (X, Y)

预测时根本不需要算配分函数,只要找得分最高的那条路径即可——还是Viterbi。

# 1.5.2 学习:梯度上升对比Baum-Welch(EM)

CRF的参数学习就是最大化带L2正则的条件对数似然:

L (λ) = n \sum ln P (Y^{(n)} ∣ X^{(n)}) - \frac{1}{2 σ ^{2}} k \sum λ_{k}^{2}

由于配分函数 $Z (X)$ 的存在,对数似然没有解析解,需要用梯度上升(或L-BFGS)迭代求解。梯度:

\frac{\partial L}{\partial λ _{k}} = 经验期望 n \sum t \sum f_{k} (y_{t - 1}^{(n)}, y_{t}^{(n)}, X^{(n)}, t) - 模型期望 n \sum t \sum E_{P (Y ∣ X^{(n)})} [f_{k}] - \frac{λ _{k}}{σ ^{2}}

直觉:梯度 = "数据里特征实际出现的次数" - "模型预测下特征出现的期望次数" - "正则项"。如果某个特征在真实数据里出现得比模型想象的更多(经验期望>模型期望),梯度为正,梯度上升就会提高它的权重;反过来就降低。当经验期望等于模型期望时(忽略正则),梯度为零,模型收敛。这和Day7最大熵的约束条件完全对应——梯度为零意味着经验期望等于模型期望。

模型期望怎么算?它需要对所有标签路径求期望 $E_{P (Y ∣ X)} [f_{k}] = \sum_{Y} P (Y ∣ X) f_{k} (X, Y)$ ,理论上是指数级枚举。但线性链结构告诉我们:只要用前向-后向算出每个位置和每条边的后验 $γ_{t} (i)$ 、 $ξ_{t} (i, j)$ ,就能高效汇总特征期望——这就是Forward-Backward在CRF里再次出现的原因,和HMM的学习形成闭环。

对比HMM的Baum-Welch:CRF用梯度上升(判别式,直接最大化条件对数似然 $lo g P (Y ∣ X)$ ),HMM用EM(生成式,优化观测对数似然 $lo g P (O ∣ λ)$ ,隐状态用后验估计)。两者都用前向-后向算期望,只是目标函数不同——一个是"软计数重新统计参数",一个是"让模型期望逼近经验期望"。

# 1.6 NumPy实战:CRF对比逐标签逻辑回归

下面用一个长度为2的序列对比两种解码:CRF的Viterbi对整条序列联合打分,逐标签逻辑回归只看每个位置独立的最大值。代码里T、E直接存0~1的势函数分数(对应公式里 $exp (\sum_{k} λ_{k} f_{k})$ 那一项),Viterbi在分数上做max-乘积;等价地换到log空间,就是max-求和。

import numpy as np

# 2个标签：B=0，I=1；序列长度=2
# T：转移势函数，E：状态势函数
T = np.array([[0.1, 0.2],
              [0.1, 1.0]])

E = np.array([[0.8, 0.7],
              [0.6, 0.9]])


# CRF：Viterbi 全局最优
delta = np.zeros((2, 2))
psi = np.zeros((2, 2), dtype=int)

# 第一个位置
delta[0] = E[0]

# 动态规划
for t in range(1, 2):
    for j in range(2):
        vals = delta[t - 1] * T[:, j]
        psi[t, j] = np.argmax(vals)
        delta[t, j] = np.max(vals) * E[t, j]

# 回溯最优路径
last = np.argmax(delta[1])
path_crf = [int(last), int(psi[1, last])]
path_crf.reverse()

print("CRF (Viterbi) 最优路径:", path_crf)


# 枚举所有路径，验证 Viterbi 结果
best_score = -1
best_path = None

print("\nCRF 各路径权重:")

for i in range(2):
    for j in range(2):
        score = E[0, i] * T[i, j] * E[1, j]
        print(f"  {i}->{j}: {score:.4f}")

        if score > best_score:
            best_score = score
            best_path = [i, j]

print("全局最优路径:", best_path)
print(f"全局最优权重: {best_score:.4f}")
print(f"Viterbi结果正确? {path_crf == best_path}")


# 逐标签逻辑回归：局部最优
# 每个位置独立选择状态势函数最大的标签，不考虑标签转移
lr_path = [int(np.argmax(E[0])), int(np.argmax(E[1]))]

lr_score = (
    E[0, lr_path[0]]
    * T[lr_path[0], lr_path[1]]
    * E[1, lr_path[1]]
)

print("\n逐标签 LR 路径:", lr_path)
print(f"LR 路径权重: {lr_score:.4f}")


# 对比
print("\n对比:")
print("LR  ：独立选择每个位置的局部最优标签")
print("CRF ：结合标签转移关系，寻找整条序列的全局最优路径")
print(f"LR 与 CRF 路径是否相同? {lr_path == path_crf}")

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

CRF (Viterbi) 最优路径: [1, 1]

CRF 各路径权重:
  0->0: 0.0480
  0->1: 0.1440
  1->0: 0.0420
  1->1: 0.6300
全局最优路径: [1, 1]
全局最优权重: 0.6300
Viterbi结果正确? True

逐标签 LR 路径: [0, 1]
LR 路径权重: 0.1440

对比:
LR  ：独立选择每个位置的局部最优标签
CRF ：结合标签转移关系，寻找整条序列的全局最优路径
LR 与 CRF 路径是否相同? False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这个例子恰好展示了CRF的核心优势。逐标签逻辑回归在每个位置只看状态势函数E的最大值:位置0选B(E[0,0]=0.8 > E[0,1]=0.7)、位置1选I(E[1,1]=0.9 > E[1,0]=0.6),得到路径(B, I)权重0.144。但CRF的Viterbi发现:虽然位置0选I的势能(0.7)略低于选B(0.8),但I→I的转移势能T[1,1]=1.0远大于B→I的T[0,1]=0.2,整条路径(I, I)的权重0.63是(B, I)的4倍多。CRF考虑了标签间的转移关系,而逐标签LR完全看不到这一点——这就是全局解码对比局部选择的价值。

# 1.7 HMM的典型应用与局限

# 1.7.1 典型应用

语音识别:声学特征是观测,音素是隐藏状态;Viterbi找最优音素序列
词性标注:词是观测,词性(名词/动词/...)是状态;转移矩阵编码语法规则
生物信息:DNA碱基是观测,基因编码区/非编码区是状态

# 1.7.2 局限与CRF的改进

一阶假设太强:长程依赖无法表达(CRF通过任意阶特征缓解)
生成式模型:建模 $P (X, Y) = P (X ∣ Y) P (Y)$ ,需要建模观测的生成过程;如果任务只关心 $P (Y ∣ X)$ ,生成式模型"多做了事"(CRF直接建模 $P (Y ∣ X)$ )
状态数预设:N要人工指定,不像GMM可以用BIC/轮廓系数选

# 小结

问题	算法	复杂度	核心思想
评估 $P (O ∥ λ)$	前向/后向	$O (N^{2} T)$	动态规划,指数→多项式
解码 $ar g max_{Q} P (Q ∥ O, λ)$	Viterbi	$O (N^{2} T)$	动态规划+回溯,全局最优
学习 $\hat{λ}$	Baum-Welch	每轮迭代 $O (N^{2} T)$	EM:E步软着色算后验,M步按软计数更新参数

维度	HMM(生成式)	CRF(判别式)
建模	$P (X, Y) = P (Y) P (X ∥ Y)$	$P (Y ∥ X)$
特征	受马尔可夫+观测独立假设约束	任意特征函数,可看全局
参数	$π, A, B$ (概率)	$λ_{k}$ (权重,可为负)
推断	前向-后向、Viterbi	结构相同,概率换分数
学习	Baum-Welch(EM)	梯度上升/L-BFGS
关系	CRF的特例(特定特征下)	HMM的一般化
对应	朴素贝叶斯(序列版)	逻辑回归(序列版)

# 今天的认知升级:同一套动态规划,两种建模哲学

HMM和CRF看似是两个模型,其实共享同一套"评估-解码-学习"的算法骨架:前向做加法把所有路径汇总、Viterbi取最大只留最优路径,EM或梯度上升学参数。差别只在建模目标——HMM建模联合概率 $P (X, Y)$ ,要假设观测怎么生成;CRF建模条件概率 $P (Y ∣ X)$ ,把生成过程交给特征函数。这就像Day7逻辑回归和Day11朴素贝叶斯的关系:判别式不做"多余的事",在许多序列标注任务中更灵活;生成式能处理缺失数据、能生成样本,各有适用场景。

CRF是传统机器学习时代序列标注的王者(NLP、生物信息)。深度学习时代,BiLSTM-CRF、BERT-CRF将神经网络的特征提取能力和CRF的结构化预测能力结合,依然是序列标注的主流方案。理解了CRF的"全局打分+配分函数"框架,后续阅读Energy-Based Model、Structured SVM都会触类旁通。

← 10000h·Day13 10000h·Day15 →