第14章：概率图模型 — 西瓜书学习笔记

本文是周志华《机器学习》（西瓜书）第14章 概率图模型（Probabilistic Graphical）的学习笔记，涵盖本章所有核心知识点，配有通俗类比与公式推导。

①. 基本概念与模型分类

有向图 vs. 无向图，概率图的两种范式

🗺️ 生活类比：家族族谱 vs. 朋友圈

**有向图（贝叶斯网络）**像家族族谱——你从父母到子女有明确的方向。”基因”沿有向边传递，父子关系带来因果依赖。**无向图（马尔可夫随机场）**像朋友圈——朋友之间没有方向，你们相互影响。”状态”通过无向连接相互约束。

📐 概率图模型 = 图结构 + 概率分布

一个概率图模型就是用图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$ 描述随机变量集合 $\boldsymbol{X}=\{X_1,\ldots,X_n\}$ 之间的依赖关系，用一套参数 $\boldsymbol{\Theta}$ 来量化这些关系。

🔷 有向图 (Bayesian Network)

联合分布分解为局部条件概率的乘积：

$P(X_1,\ldots,X_n) = \displaystyle\prod_{i=1}^{n} P(X_i \mid \pi_i)$

其中 $\pi_i$ 是 $X_i$ 的父节点集合。

🔶 无向图 (MRF)

联合分布分解为最大团势能函数的乘积：

$P(\boldsymbol{X}) = \dfrac{1}{Z}\displaystyle\prod_{Q\in\mathcal{C} } \psi_Q(\boldsymbol{X}_Q)$ $Z$ 是配分函数（partition function），$\mathcal{C}$ 是最大团集合。

🔗 三类条件独立性

在上面再加分连接（tail-to-tail），完整展示：

🟢 信息流被阻塞

• 顺连 (A→B→C)：给定B则A⊥C
• 分连 (A←B→C)：给定B则A⊥C
• 汇连 (A→B←C)：未给定B时A⊥C

🔴 信息流被激活

• 汇连 (A→B←C)：给定B后，A和C相互依赖（explaining away）
• 未给定中间节点时，顺连和分连都不阻塞

②. 隐马尔可夫模型（HMM）

有向图序列模型的经典代表

🎰 生活类比：猜骰子序列

你只能看到每次掷出的点数（观测），但不知道用的是哪种骰子（隐藏状态）——可能是公平骰子、也可能被暗中换成了灌铅骰子。HMM 要解决的问题就是：从观测序列反推出隐藏状态序列。

📐 HMM 五要素

要素	符号	含义
状态集合	$\mathcal{S}=\{s_1,...,s_N\}$	隐藏状态的有限集合
观测集合	$\mathcal{O}=\{o_1,...,o_M\}$	可观测输出的有限集合
初始状态概率	$\pi_i = P(y_1=s_i)$	初始时刻各状态的概率
状态转移矩阵	$A_{ij}=P(y_{t+1}=s_j|y_t=s_i)$	状态间的转移规律
发射概率矩阵	$B_{jk}=P(x_t=o_k|y_t=s_j)$	给定状态下产生某观测的概率

⚡ HMM 三大基本问题

1. 评估问题

给定模型 $\lambda$ 和观测序列 $x$，求 $P(x|\lambda)$

解法：前向-后向算法

给定模型和观测序列，求最可能的状态序列 $y^*$

解法：维特比算法（动态规划）

3. 学习问题

给定观测序列，估计模型参数 $\lambda^*$

解法：Baum-Welch / EM 算法

📐 前向算法（Forward Algorithm）

定义前向概率 $\alpha_t(i) = P(x_1,...,x_t, y_t=s_i|\lambda)$

递推公式：$\alpha_{t+1}(j) = \left[\sum_{i=1}^N \alpha_t(i) A_{ij}\right] \cdot B_j(x_{t+1})$

最终：$P(x|\lambda) = \sum_{i=1}^N \alpha_T(i)$，复杂度 $O(N^2T)$

📐 维特比算法（Viterbi）— 解码最优路径

定义 $\delta_t(i) = \max_{y_1,...,y_{t-1} } P(y_1,...,y_t=s_i, x_1,...,x_t)$

递推：$\delta_{t+1}(j) = \max_i [\delta_t(i) \cdot A_{ij}] \cdot B_j(x_{t+1})$

回溯记录最优前驱 $\psi_t(j) = \arg\max_i \delta_{t-1}(i)A_{ij}$

③. 马尔可夫随机场（MRF）

无向图的概率建模：全局马尔可夫性与团分解

🧩 Hammersley-Clifford 定理

这是 MRF 的核心理论基石：一个严格正的分布满足无向图 $\mathcal{G}$ 的马尔可夫性，当且仅当它可以分解为最大团的势函数（potential function）乘积：

📐 吉布斯分布（Gibbs Distribution）

$$P(\boldsymbol{X}) = \frac{1}{Z} \prod_{Q \in \mathcal{C} } \psi_Q(\boldsymbol{X}_Q) = \frac{1}{Z} \exp\left(-\sum_{Q \in \mathcal{C} } E_Q(\boldsymbol{X}_Q)\right)$$

其中 $Z = \sum_{\boldsymbol{X} } \prod_{Q} \psi_Q(\boldsymbol{X}_Q)$ 是配分函数（归一化常数），$E_Q(\cdot)=-\ln\psi_Q(\cdot)$ 是能量函数。

三种马尔可夫性

1. 成对马尔可夫性：不相邻的两个变量在给定所有其他变量时条件独立
2. 局部马尔可夫性：给定邻居，该变量与其他所有变量独立
3. 全局马尔可夫性：给定分离集，被分离的变量集合条件独立

💡 势函数的物理直觉

将 $E(\boldsymbol{X}) = \sum_{Q} E_Q(\boldsymbol{X}_Q)$ 看作系统总能量。低能量配置概率高，高能量配置概率低——物理中的 Boltzmann 分布就是 MRF 的特例！

④. 条件随机场（CRF）

判别式序列建模：直接对条件概率建模

⚔️ HMM vs. CRF：生成式 vs. 判别式

HMM 是生成式模型，先学出数据的”生成规则”$P(x,y)$，再反推$P(y|x)$——相当于先学会掷骰子的完整物理过程。CRF 是判别式模型，直接上手学”怎么从观测判断状态”$P(y|x)$——省了一大圈。

📐 线性链 CRF 定义

对于序列标注任务（$x$ 观测序列，$y$ 标签序列），定义条件分布：

📐 CRF 条件概率

$$P(\boldsymbol{y} \mid \boldsymbol{x}) = \frac{1}{Z(\boldsymbol{x})} \exp\!\left( -\sum_{t=1}^{T} \left[ \sum_{k=1}^{K_1} \lambda_k t_k(y_t, y_{t-1}, \boldsymbol{x}, t) + \sum_{l=1}^{K_2} \mu_l s_l(y_t, \boldsymbol{x}, t) \right] \right)$$

其中 $t_k$ 是转移特征函数（刻画相邻标签关系），$s_l$ 是状态特征函数（刻画标签与观测的关系），$\lambda_k, \mu_l$ 是需要学习的权重。

✅ CRF 的优势

• 不受观测独立性假设约束（HMM 有这个强假设）
• 可灵活设计任意特征函数，引入领域知识
• 无局部归一化问题（全局归一化）
• 对不平衡标注不敏感

⚠️ CRF 的代价

• 训练更慢（需迭代计算梯度）
• 推断通常用维特比（链式CRF）
• 特征工程工作量大
• 配分函数 $Z(x)$ 计算开销大

⑤. 精确推断

变量消去与信念传播

🔍 变量消去（Variable Elimination）

核心思想：利用分配律对边缘概率计算中的求和与乘积进行交换，动态规划避免重复计算。

例如要计算 $P(A)$：

📐 消去变量 B, C

$$P(A) = \sum_B\sum_C P(A)P(B|A)P(C|B) = P(A)\sum_B P(B|A)\underbrace{\left[\sum_C P(C|B)\right]}_{\text{先算内层求和！} }$$

直觉：与其 $A \times B \times C$ 三种组合全枚举再求和，不如先”消去”最内层的 C，把中间结果缓存（这就是动态规划！），计算顺序决定复杂度。

📨 信念传播（Belief Propagation）

变量消去每次只能算一个边缘概率，需要重复很多计算。信念传播把所有节点的边缘概率一次性算出来，相当于在树上做”消息传递”。

📐 消息传递方程

$$m_{i \to j}(x_j) = \sum_{x_i} \psi(x_i, x_j) \prod_{k \in \mathcal{N}(i)\setminus\{j\} } m_{k \to i}(x_i)$$

节点 $i$ 发往 $j$ 的消息 = 含 $i$ 自己的局部信息 + 所有其他邻居传来的消息。

🌲 树结构上

BP 是精确算法，两轮传播（先到根，再来回）即收敛，复杂度与节点数线性。

🔄 含环图上

Loopy BP 是近似算法，不能保证收敛，但在实践中（如 Turbo 码、LDPC 码）效果惊人地好。

⑥. 近似推断

采样法（MCMC）与变分推断

🎲 MCMC 采样

当精确推断不可行时，用采样方法来近似推断：

Gibbs 采样

Algorithm: Gibbs Sampling
初始化: 随机给所有变量赋值 x⁽⁰⁾
for t = 1 to T:
for each variable X_i:
// 固定其他变量，从条件分布中采样 X_i
x_i⁽ᵗ⁾ ~ P(X_i | x₁⁽ᵗ⁾,…,x_{i-1}⁽ᵗ⁾, x_{i+1}⁽ᵗ⁻¹⁾,…,xₙ⁽ᵗ⁻¹⁾)
// 丢弃 burn-in 样本后，用剩余样本的均值/众数做推断

直观理解：每次只翻一张牌，其他牌不变，翻到哪张由条件概率决定。翻足够多次后，翻出的牌面分布就逼近真实联合分布。

📐 变分推断（Variational Inference）

不想采样？那就优化：找一个简单分布 $q(\boldsymbol{Z})$ 去逼近复杂的后验 $P(\boldsymbol{Z}|\boldsymbol{X})$，最小化它们的 KL 散度：

📐 ELBO（证据下界）

$$\ln P(\boldsymbol{X}) \geq \mathbb{E}_{q(\boldsymbol{Z})}[\ln P(\boldsymbol{X},\boldsymbol{Z})] - \mathbb{E}_{q(\boldsymbol{Z})}[\ln q(\boldsymbol{Z})] \triangleq \text{ELBO}(q)$$

最大化 ELBO = 最小化 $\text{KL}(q\|P)$。把不可解的推断问题变成可优化的问题。

⑦. 学习方法与模型对比总结

生成式 vs. 判别式，有向 vs. 无向

模型	图类型	概率建模	典型推断	典型应用	优点	缺点
HMM	有向	生成式 $P(x,y)$	维特比 / 前向-后向	语音识别、词性标注	简单、效率高	观测独立性假设太强
MRF	无向	生成式 $P(X)$	Gibbs 采样 / BP	图像去噪、分割	无方向偏好，灵活	难学习、推断贵
CRF	无向	判别式 $P(y|x)$	维特比 / BP	序列标注（NER、分词）	无观测独立性假设	训练慢、特征工程繁琐
贝叶斯网络	有向	生成式 $P(X)$	变量消去 / BP	专家系统、因果推断	可解释性强	需领域知识建图

📐 学习算法一览

场景	方法	核心思想	适用条件
完全观测	极大似然估计 (MLE)	最大化 $\prod_i P(x_i, y_i|\theta)$	所有变量值已知
部分变量隐藏	EM 算法	E步推算后验，M步更新参数	有隐变量但结构已知
结构未知	结构学习 (Structure Learning)	从数据中同时学图和参数	极其困难，通常用 score-based 搜索

🧠 本章一句话总结

概率图模型的核心是 H-C 定理：概率分布的马尔可夫性质 ⇔ 团分解形式。有向图适合因果推理（贝叶斯网），无向图适合对称约束（MRF），CRF 则是把无向图用于条件判别——三者共享”图结构 + 局部因子”的思想，只是在生成/判别、有向/无向的不同维度上做了不同的取舍。