🎭 02-机器学习 · 推导笔记 11:隐马尔可夫模型 HMM(手写全流程)¶
HMM 是序列数据最经典的生成式模型:词性标注、语音识别、生物序列分析的教科书模型,也是面试“概率图模型”板块的必考点。
💡 一句话类比:你隔着墙听到隔壁传来“乒乓、乒乓”的声音(观测),但看不见里面的状态——可能是“打乒乓球”或“装修敲墙”(隐藏状态)。你想根据一连串声音,推断隔壁今天大概在干嘛、甚至预测接下来会听到什么——HMM 就是干这个的数学模型。
💡 更经典的版本:你只看得到朋友每天发了什么动态(散步/购物/清洁),猜不到天气(晴/雨)——但你知道“晴天的动态分布”“天气怎么演变”,HMM 就是把这些知识组织起来做推断。
运行环境:Python 3.8+,仅依赖 numpy。
📊 图 5:HMM 图模型——上方隐藏状态链 q(晴/雨)只有转移 A,下方观测 o(散步/购物/清洁)由发射 B 生成;π 决定初始状态。
核心概念¶
(a) 🗂️ HMM:三要素两假设、前向/后向、Viterbi 与 Baum-Welch¶
HMM 是序列数据最经典的生成式模型:词性标注、语音识别、生物序列分析的教科书模型。本篇三要素、两个假设、三个基本问题全部手写。
flowchart TB
N1["🎭 模型三要素与两个假设"] --> N2["概率计算:前向算法"]
N1 --> N3["后向算法:配套"]
N1 --> N4["解码问题:Viterbi"]
N1 --> N5["学习问题:Baum-Welch"]
N2 --> N6["生成式模型的局限"]
N3 --> N6
N6 --> N7["引出 CRF:下篇预告"]
N7 --> N8["常见 bug 与边界"]
N8 --> N9["自测清单"]
- N1 · 三要素与两个假设:三要素:初始概率 π(开始是哪个隐状态)、转移矩阵 A(状态怎么变)、发射矩阵 B(状态怎么产生观测);两个假设:齐次马尔可夫(只看上一个状态)和观测独立(只看当前状态)。
- N2 · 概率计算:前向算法:问题一"算概率":给定模型和观测序列,算这个观测出现的概率。直接枚举所有状态路径是指数级的,前向算法用动态规划把复杂度降到 O(T·N²)。
- N3 · 后向算法:与前向对称:从序列尾部往前"倒着算"剩余部分的概率;前向 + 后向合起来还能算出"每个时刻处于某状态的概率",是学习问题的原料。
- N4 · 解码:Viterbi:问题二"找最可能的状态路径"用 Viterbi:动态规划记录每个时刻每个状态的最优分数 + 回溯指针,最后从终点回溯出整条路径。
- N5 · 学习:Baum-Welch:问题三"学习参数":不知道状态、只有观测时用 Baum-Welch(EM 的特例):E 步用前向后向算"状态转移的期望次数",M 步重新估计 π/A/B,迭代收敛。
- N6 · 生成式模型的局限:齐次马尔可夫假设和观测独立假设太强,且它是生成式模型(建模联合分布),对特征不好扩展——这正是引出 CRF 的理由。
- N7 · 引出 CRF:对比预告:CRF 是判别式、用特征函数、全局归一化,能克服 HMM 的假设限制——下一篇详细展开。
- N8 · 常见 bug 与边界:概率下溢(连乘太小,要用 log 或缩放)、Viterbi 回溯忘指针、Baum-Welch 的归一化顺序写反。
- N9 · 自测清单:能手写前向算法、能用手算小例子的 Viterbi、能讲清 EM 在 HMM 上做了什么。
📖 本章导读¶
这一章讲什么(全书第 12 章):带隐藏状态的序列模型——三要素 $(\pi, A, B)$ 与两个假设;三个基本问题分别用前向算法(算概率)、Viterbi(找最优路径)、Baum-Welch/EM(学参数)。
学完本章,你应该能:
- 写出前向递推 $\alpha_{t+1}(j)=\big[\sum_i\alpha_t(i)a_{ij}\big]b_j(o_{t+1})$ 与 $P(O)=\sum_i\alpha_T(i)$;
- 讲清 Viterbi 为什么是动态规划、与贪心的区别;
- 说清 Baum-Welch 的 E 步($\gamma/\xi$)与 M 步(频率重估);
- 说出 HMM 的软肋(生成式、特征受限)——为下一章 CRF 埋坑。
📌 全书第 12 章。阅读路径:本章导读 → 三要素 · 前向后向 · Viterbi · Baum-Welch → 自测清单 → 本章小结。
§1 模型三要素与两个假设¶
HMM 由三组参数完全决定,记 $\lambda = (\pi, A, B)$:
| 记号 | 名称 | 含义 | 形状 |
|---|---|---|---|
| $\pi_i$ | 初始概率 | 第一个状态是 $i$ 的概率 | $N$ 维向量 |
| $A_{ij}$ | 状态转移矩阵 | 状态 $i \to j$ 的概率 | $N \times N$ |
| $B_{jk}$ | 观测概率矩阵 | 状态 $j$ 下发出观测 $k$ 的概率 | $N \times M$ |
两个假设(面试必背):
- 齐次马尔可夫性:当前状态只依赖前一个状态(一阶):$P(q_t \mid q_{1:t-1}) = P(q_t \mid q_{t-1})$;
- 观测独立性:当前观测只依赖当前状态:$P(o_t \mid q_{1:T}, o_{1:T}) = P(o_t \mid q_t)$。
三个基本问题:
| 问题 | 目标 | 算法 |
|---|---|---|
| 概率计算 | $P(O \mid \lambda)$ 观测序列出现的概率 | 前向/后向算法($O(N^2 T)$) |
| 解码 | 最可能的状态序列 $Q^*$ | Viterbi 算法(动态规划) |
| 学习 | 从观测估计 $\lambda$ | Baum-Welch(EM 特例) |
§2 概率计算:前向算法(手推 + 手写)¶
暴力法枚举所有 $N^T$ 条状态路径,指数爆炸。前向算法用动态规划:定义前向概率
$$\alpha_t(i) = P(o_1, \dots, o_t, q_t = i \mid \lambda)$$
初始化:$\alpha_1(i) = \pi_i b_i(o_1)$
递推($t = 2, \dots, T$):
$$\alpha_t(j) = \left[ \sum_{i=1}^{N} \alpha_{t-1}(i) \, a_{ij} \right] \cdot b_j(o_t)$$
终止:$P(O \mid \lambda) = \sum_{i=1}^{N} \alpha_T(i)$
💡 通俗理解:第 $t$ 时刻在状态 $j$ “且看到当前观测”的概率 = 上一时刻所有可能状态的“账”($\alpha_{t-1}$)转移到 $j$ 的总和,再乘上在 $j$ 发出当前观测的概率。复杂度 $O(N^2 T)$,比 $O(N^T)$ 快无数倍。
# ---- 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
# 经典例子(李航《统计学习方法》例 10.2):天气晴/雨 -> 朋友动态 散步/购物/清洁
# 状态 0=晴, 1=雨;观测 0=散步, 1=购物, 2=清洁
pi = np.array([0.6, 0.4])
A = np.array([[0.5, 0.5],
[0.3, 0.7]])
B = np.array([[0.5, 0.4, 0.1], # 晴天:散步 0.5 购物 0.4 清洁 0.1
[0.1, 0.3, 0.6]]) # 雨天:散步 0.1 购物 0.3 清洁 0.6
O = np.array([0, 1, 2]) # 观测序列:散步、购物、清洁
def forward(pi, A, B, O):
"""前向算法,返回 alpha[t, i] 与观测概率"""
N, T = len(pi), len(O)
alpha = np.zeros((T, N))
alpha[0] = pi * B[:, O[0]]
for t in range(1, T):
alpha[t] = (alpha[t-1] @ A) * B[:, O[t]]
return alpha, alpha[-1].sum()
alpha, P = forward(pi, A, B, O)
print("前向概率矩阵 alpha[t, i]:")
print(alpha.round(5))
print(f"\nP(观测=散步购物清洁 | 模型) = {P:.5f} (书上答案 0.13022)")
def backward(pi, A, B, O):
"""后向算法:beta[t, i] = P(o_{t+1:T} | q_t = i, 模型)"""
N, T = len(pi), len(O)
beta = np.zeros((T, N))
beta[-1] = 1.0
for t in range(T - 2, -1, -1):
beta[t] = (A * B[:, O[t+1]]) @ beta[t+1]
P2 = (pi * B[:, O[0]]) @ beta[0]
return beta, P2
beta, P2 = backward(pi, A, B, O)
print(f"后向算法算出的 P(O) = {P2:.5f} (应与前向一致)")
print(f"一致性校验 |P_fwd - P_bwd| = {abs(P - P2):.2e}")
§3 解码问题:Viterbi 算法(手写)¶
目标:找最可能的状态序列 $Q^* = \arg\max_Q P(Q \mid O, \lambda)$。定义
$$\delta_t(i) = \max_{q_1, \dots, q_{t-1}} P(q_1 \dots q_{t-1}, q_t = i, o_1 \dots o_t \mid \lambda)$$
递推:$\delta_t(j) = \max_i \left[ \delta_{t-1}(i) \, a_{ij} \right] \cdot b_j(o_t)$,同时记录回溯指针 $\psi_t(j) = \arg\max_i \delta_{t-1}(i) a_{ij}$。
终止:$P^* = \max_i \delta_T(i)$,从 $q_T^*$ 沿 $\psi$ 回溯得到整条路径。
💡 通俗理解:Viterbi 就是“带剪枝的动态规划”——每一步只保留“到每个状态的最优路径”,丢掉次优的,最后从终点倒推回起点。复杂度 $O(N^2 T)$。
def viterbi(pi, A, B, O):
"""Viterbi 解码,返回最优状态序列"""
N, T = len(pi), len(O)
delta = np.zeros((T, N))
psi = np.zeros((T, N), dtype=int)
delta[0] = pi * B[:, O[0]]
for t in range(1, T):
for j in range(N):
cand = delta[t-1] * A[:, j]
delta[t, j] = cand.max() * B[j, O[t]]
psi[t, j] = cand.argmax()
# 回溯
path = [delta[-1].argmax()]
for t in range(T - 1, 0, -1):
path.append(psi[t, path[-1]])
return np.array(path[::-1]), delta[-1].max()
path, prob = viterbi(pi, A, B, O)
names = {0: "晴", 1: "雨"}
print(f"最优状态路径 = {[names[i] for i in path]} (书上答案:雨-雨-晴)")
print(f"该路径的概率 = {prob:.6f}")
§4 学习问题:Baum-Welch(EM 在 HMM 上的特例)¶
只有观测 $O$、不知道状态 $Q$——这就是含隐变量的最大似然问题,天然用 EM 算法(EM 全量推导见推导笔记 3 的 GMM 篇,思想完全一致)。
E 步:用当前参数算两个充分统计量(需要前向 + 后向):
$$\gamma_t(i) = P(q_t = i \mid O, \lambda) = \frac{\alpha_t(i)\beta_t(i)}{P(O \mid \lambda)}$$
$$\xi_t(i, j) = P(q_t = i, q_{t+1} = j \mid O, \lambda) = \frac{\alpha_t(i)\, a_{ij}\, b_j(o_{t+1})\, \beta_{t+1}(j)}{P(O \mid \lambda)}$$
M 步:用期望计数重估参数(分子=期望次数,分母=期望可发生次数):
$$\hat{\pi}_i = \gamma_1(i), \qquad \hat{a}_{ij} = \frac{\sum_{t=1}^{T-1} \xi_t(i,j)}{\sum_{t=1}^{T-1} \gamma_t(i)}, \qquad \hat{b}_j(k) = \frac{\sum_{t: o_t = k} \gamma_t(j)}{\sum_{t=1}^{T} \gamma_t(j)}$$
迭代直到似然不再上升。EM 保证单调不减(推导笔记 3 有收敛性说明)。
💡 通俗理解:把“猜状态”当隐形变量——先按当前参数猜每个时刻处于各状态的概率(E 步),再用这些“软计数”重新统计转移和发射频率(M 步),循环往复,越猜越准。
def baum_welch(O, N, M, max_iter=200, tol=1e-6, seed=0):
"""Baum-Welch:单观测序列学习 HMM 参数"""
rng = np.random.default_rng(seed)
T = len(O)
pi = rng.dirichlet(np.ones(N))
A = rng.dirichlet(np.ones(N), size=N)
B = rng.dirichlet(np.ones(M), size=N)
prev_ll = -np.inf
for it in range(max_iter):
# E 步:前向 + 后向
alpha = np.zeros((T, N))
alpha[0] = pi * B[:, O[0]]
for t in range(1, T):
alpha[t] = (alpha[t-1] @ A) * B[:, O[t]]
ll = np.log(alpha[-1].sum())
beta = np.zeros((T, N))
beta[-1] = 1.0
for t in range(T - 2, -1, -1):
beta[t] = (A * B[:, O[t+1]]) @ beta[t+1]
denom = alpha[-1].sum()
gamma = alpha * beta / denom
xi = np.zeros((T - 1, N, N))
for t in range(T - 1):
xi[t] = (alpha[t][:, None] * A) * B[:, O[t+1]] * beta[t+1] / denom
# M 步:重估
pi = gamma[0]
A = xi.sum(axis=0) / gamma[:-1].sum(axis=0)[:, None]
for j in range(N):
for k in range(M):
B[j, k] = gamma[O == k, j].sum() / gamma[:, j].sum()
if abs(ll - prev_ll) < tol:
break
prev_ll = ll
return pi, A, B, ll, it
# 用真实参数生成一条长观测序列,再让 Baum-Welch 反推
rng = np.random.default_rng(42)
A_true = np.array([[0.7, 0.3], [0.4, 0.6]])
B_true = np.array([[0.6, 0.3, 0.1], [0.1, 0.3, 0.6]])
pi_true = np.array([0.5, 0.5])
states = [rng.choice(2, p=pi_true)]
obs = [rng.choice(3, p=B_true[states[0]])]
for _ in range(1999):
s = rng.choice(2, p=A_true[states[-1]])
states.append(s)
obs.append(rng.choice(3, p=B_true[s]))
obs = np.array(obs)
pi_hat, A_hat, B_hat, ll, it = baum_welch(obs, N=2, M=3)
print(f"迭代 {it + 1} 轮后对数似然 = {ll:.3f}")
print("学习到的转移矩阵 A:"); print(A_hat.round(3))
print("真实转移矩阵 A:"); print(A_true)
print("学习到的发射矩阵 B:"); print(B_hat.round(3))
print("真实发射矩阵 B:"); print(B_true)
print("\n(状态编号可交换,需按列/行排列后对比——量级与模式应对得上)")
§5 HMM 的局限与改进方向(引出 CRF)¶
HMM 的两个假设太强:
- 观测独立性:观测之间无关(词性标注里“昨天/今天”这种词上下文相关性被忽略);
- 只能利用局部特征:发射概率 $b_j(o_t)$ 只看当前状态与当前观测,难以加入“词是首字母大写”“词在词典中”这类任意重叠特征。
改进路线:
- 判别式化:MEMM(最大熵马尔可夫模型)用 $P(q_t \mid q_{t-1}, o)$ 直接建模,但存在**标注偏置(label bias)**问题——状态出度少的分支会“抢概率”;
- 全局归一化:线性链 CRF(推导笔记 12)在整条序列上做归一化,彻底解决标注偏置,是当前序列标注的主力模型。
💡 面试一句话:HMM = 生成式 + 强假设;CRF = 判别式 + 全局归一化 + 任意特征函数。
§6 常见 bug 与边界(面试踩坑区)¶
- 概率下溢:长序列下 $\alpha_t$ 指数级变小,float64 也会变 0——工程上用对数空间(log-sum-exp 技巧);
- Baum-Welch 对初值敏感:EM 只保证局部最优,多跑几个随机初值取似然最高的;
- 状态编号可交换:学到 $\pi, A, B$ 后要和真实参数对齐(permutation)再比较,别直接比对矩阵元素;
- 观测序列太长:$T$ 巨大时内存 $O(TN)$ 也吃力,可用在线/切片技巧;
- Viterbi 与最优路径概率别混:Viterbi 返回的是“单条最优路径”,不等于 $P(O)$(后者是所有路径求和)。
§7 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(8 问)¶
- 1. 说出 HMM 三要素与两个假设
- 2. 三大问题的目标与对应算法
- 3. 写出前向递推公式
- 4. 写出 Viterbi 递推与回溯思想
- 5. 为什么暴力枚举不可行($N^T$)
- 6. Baum-Welch 是哪个算法的特例(EM)
- 7. HMM 是生成式还是判别式
- 8. 观测独立假设意味着什么
L2 进阶(6 问)¶
- 9. 前向/后向算法复杂度 $O(N^2T)$ 的由来
- 10. 写出 $\gamma_t(i)$、$\xi_t(i,j)$ 的定义
- 11. 长序列为什么需要 log 空间
- 12. EM 在 HMM 中 E 步/M 步分别做什么
- 13. HMM 三大应用场景举例(词性标注/语音/生物)
- 14. 解码与概率计算的区别
L3 挑战(4 问)¶
- 15. 手写前向 + Viterbi + Baum-Welch 三件套
- 16. 多观测序列的 Baum-Welch 重估公式
- 17. 推导 Baum-Welch 是 EM 的证明思路(Q 函数)
- 18. 从 HMM → MEMM → CRF 的演进逻辑
自测要点¶
- 15 分钟内盲写前向算法与 Viterbi
- 能口述 EM 在 HMM 上的 E/M 步分工
- 能说出 HMM 两个假设被 CRF 如何放松
🏁 本章小结¶
- 原理一句话:HMM 三问——前向算概率、Viterbi 找最优路径、Baum-Welch(EM) 学参数。
- 必会公式:$\alpha_{t+1}(j)=\big[\sum_i\alpha_t(i)a_{ij}\big]b_j(o_{t+1})$;$P(O)=\sum_i\alpha_T(i)$;Viterbi $\delta_t(j)=\max_i\delta_{t-1}(i)a_{ij}\cdot b_j(o_t)$。
- 面试怎么考:三个基本问题各用什么算法、复杂度 $O(TN^2)$;Viterbi vs 贪心;Baum-Welch 的 E 步($\gamma/\xi$)与 M 步(频率重估);HMM vs CRF。
- 易错点:发射矩阵方向 $P(o|q)$ 别记反;Viterbi 要回溯记录 argmax 路径;概率连乘下溢 → 用 log。
自测清单没把握的条目,回到对应小节重读后再打勾。