第8章：图模型（Graphical Models）
一、导读
8.1 本章学习目标
第8章介绍了概率图模型——一种用图结构表示随机变量之间条件独立关系的强大框架。图模型将概率论和图论完美结合，为复杂的高维概率分布提供了紧凑的表示和高效的推断算法。从贝叶斯网络到马尔可夫随机场，从精确推断到近似推断，图模型是现代机器学习和人工智能的核心工具。
本章的核心学习目标包括：
- 理解有向图模型（贝叶斯网络）：如何用有向无环图表示变量之间的因果关系？条件独立的含义是什么？
- 掌握无向图模型（马尔可夫随机场）：无向图如何表示变量之间的相关性？团势函数的作用是什么？
- 掌握条件独立的三种关系：有向图中的tail-to-tail、head-to-tail、head-to-head分别对应什么条件独立关系？
- 理解因式分解定理：图结构如何决定概率分布的因式分解形式？
- 掌握精确推断算法：Sum-Product算法和Belief Propagation如何在图上进行高效推断？
- 理解d-分离：如何从图结构直接读出条件独立关系？
8.2 为什么本章如此重要
概率图模型是现代AI的核心基础设施。在自然语言处理中，隐马尔可夫模型和条件随机场是序列标注的基础；在计算机视觉中，马尔可夫随机场用于图像分割和去噪；在推荐系统中，矩阵分解可以理解为二部图模型；在因果推断中，贝叶斯网络是表达因果关系的标准工具。
更重要的是，图模型提供了一种模块化的建模方式：复杂系统可以分解为多个简单的局部模型，通过图结构组合在一起。这种模块化不仅使模型更容易设计和理解，也使得推断算法可以利用图结构实现高效计算。
8.3 核心问题引导
在阅读本章时，请带着以下问题思考：
有向图和无向图在表示概率分布时有什么本质区别？
什么是条件独立？为什么条件独立对于高效推断至关重要？
贝叶斯网络中的"因果"关系与统计相关性有什么区别？
马尔可夫随机场中的团势函数有什么物理含义？
Sum-Product算法的时间复杂度是多少？为什么它比朴素推断高效得多？
什么是道德图（Moral Graph）？为什么在有向图上进行推断需要先"道德化"？
二、核心概念详解
8.1 贝叶斯网络
8.1.1 定义
贝叶斯网络（Bayesian Network）是一个有向无环图（DAG），其中：
- 节点表示随机变量
- 边表示变量之间的直接依赖关系
- 条件概率表（CPT）：每个节点 $x_i$ 有一个条件概率分布 $p(x_i | \text{pa}(x_i))$，其中 $\text{pa}(x_i)$ 是 $x_i$ 的父节点集合
联合概率分布可以分解为：
$$p(\mathbf{x}) = \prod_{i=1}^{M} p(x_i | \text{pa}(x_i))$$
8.1.2 条件独立
贝叶斯网络的核心价值在于它隐含地编码了条件独立关系。三种基本的图结构：
Tail-to-Tail（$a \leftarrow c \rightarrow b$）：
- $a$ 和 $b$ 在给定 $c$ 时条件独立：$a \perp b | c$
- 直觉：$c$ 是 $a$ 和 $b$ 的共同原因
Head-to-Tail（$a \rightarrow c \rightarrow b$）：
- $a$ 和 $b$ 在给定 $c$ 时条件独立：$a \perp b | c$
- 直觉：$c$ 是 $a$ 影响 $b$ 的中间变量
Head-to-Head（$a \rightarrow c \leftarrow b$）：
- $a$ 和 $b$ 在无条件时独立：$a \perp b$
- $a$ 和 $b$ 在给定 $c$ 时不独立（解释效应）
- 直觉：$c$ 是 $a$ 和 $b$ 的共同结果
import numpy as np
import matplotlib.pyplot as plt
def demonstrate_conditional_independence():
"""演示条件独立的三种基本结构"""
np.random.seed(42)
N = 10000
# Tail-to-Tail: a <- c -> b
c = np.random.randn(N)
a = 0.8 * c + 0.2 * np.random.randn(N)
b = 0.8 * c + 0.2 * np.random.randn(N)
corr_ab = np.corrcoef(a, b)[0, 1]
# 给定c的条件下，a和b应该独立
# 按c的值分组计算条件相关
c_bins = np.percentile(c, [25, 50, 75])
conditional_corrs = []
for i in range(len(c_bins) + 1):
if i == 0:
mask = c <= c_bins[0]
elif i == len(c_bins):
mask = c > c_bins[-1]
else:
mask = (c > c_bins[i-1]) & (c <= c_bins[i])
if np.sum(mask) > 10:
corr = np.corrcoef(a[mask], b[mask])[0, 1]
conditional_corrs.append(corr)
print("Tail-to-Tail (a <- c -> b):")
print(f" 无条件相关: {corr_ab:.4f}")
print(f" 条件相关(给定c): {np.mean(conditional_corrs):.4f}")
print(f" → 给定c后，a和b近似独立\n")
# Head-to-Head: a -> c <- b (解释效应)
a2 = np.random.randn(N)
b2 = np.random.randn(N)
c2 = a2 + b2 + 0.1 * np.random.randn(N)
corr_ab2 = np.corrcoef(a2, b2)[0, 1]
# 给定c的条件下，a和b变得相关
c2_bins = np.percentile(c2, [25, 50, 75])
conditional_corrs2 = []
for i in range(len(c2_bins) + 1):
if i == 0:
mask = c2 <= c2_bins[0]
elif i == len(c2_bins):
mask = c2 > c2_bins[-1]
else:
mask = (c2 > c2_bins[i-1]) & (c2 <= c2_bins[i])
if np.sum(mask) > 10:
corr = np.corrcoef(a2[mask], b2[mask])[0, 1]
conditional_corrs2.append(corr)
print("Head-to-Head (a -> c <- b):")
print(f" 无条件相关: {corr_ab2:.4f}")
print(f" 条件相关(给定c): {np.mean(conditional_corrs2):.4f}")
print(f" → 给定c后，a和b变得相关（解释效应）")
demonstrate_conditional_independence()8.1.3 D-分离
D-分离（d-separation）是判断条件独立的图论准则。在贝叶斯网络中，给定观测变量集合 $Z$，两条路径被"阻断"当且仅当路径上存在某个节点 $w$ 满足以下条件之一：
Tail-to-Tail或Head-to-Tail：$w \in Z$（$w$ 被观测）
Head-to-Head：$w \notin Z$ 且 $w$ 的后代也不在 $Z$ 中
如果 $Z$ 阻断了 $a$ 和 $b$ 之间的所有路径，则 $a$ 和 $b$ 在给定 $Z$ 时条件独立。
8.1.4 经典贝叶斯网络
朴素贝叶斯：所有特征在给定类别时条件独立。
隐马尔可夫模型（HMM）：隐状态形成马尔可夫链，观测在给定隐状态时条件独立。
有向生成网络：层次化的生成模型，如变分自编码器（VAE）。
def naive_bayes_graphical_model():
"""朴素贝叶斯的图模型表示"""
# 朴素贝叶斯的图结构: y -> x1, y -> x2, ..., y -> xD
# 条件独立: xi ⊥ xj | y (i ≠ j)
# 联合分布: p(y, x1, ..., xD) = p(y) * prod_i p(xi|y)
print("朴素贝叶斯图模型:")
print(" 图结构: y → x₁, y → x₂, ..., y → x_D")
print(" 条件独立: xᵢ ⊥ xⱼ | y (i ≠ j)")
print(" 联合分布: p(y, x₁, ..., x_D) = p(y) · ∏ᵢ p(xᵢ|y)")
print(" 参数数量: O(K·D) 而非 O(2^D)")
# 参数效率
D = 100 # 特征数
K = 2 # 类别数
full_params = 2**D * K # 完整联合分布
nb_params = K + K * D * 10 # 朴素贝叶斯（每个特征10个参数）
print(f"\n D={D}, K={K}:")
print(f" 完整模型参数: {full_params:.2e}")
print(f" 朴素贝叶斯参数: {nb_params:.2e}")
print(f" 参数节省: {full_params/nb_params:.2e}x")
naive_bayes_graphical_model()8.2 马尔可夫随机场
8.2.1 定义
马尔可夫随机场（Markov Random Field, MRF）是无向图模型。联合概率分布通过团势函数（clique potentials）定义：
$$p(\mathbf{x}) = \frac{1}{Z} \prod_{C \in \mathcal{C}} \psi_C(\mathbf{x}_C)$$
其中 $\mathcal{C}$ 是所有极大团（maximal cliques）的集合，$\psi_C$ 是团 $C$ 的势函数，$Z$ 是配分函数（归一化常数）。
通常使用对数线性形式：
$$p(\mathbf{x}) = \frac{1}{Z} \exp\left\{-\sum_{C} E_C(\mathbf{x}_C)\right\}$$
其中 $E_C$ 是能量函数。
8.2.2 条件独立
在无向图中，条件独立的判断更简单：
如果从 $a$ 到 $b$ 的所有路径都经过 $Z$ 中的节点，则 $a \perp b | Z$。
等价地：移除 $Z$ 中的节点后，$a$ 和 $b$ 在不同的连通分量中。
8.2.3 经典MRF
伊辛模型（Ising Model）：
$$p(\mathbf{x}) = \frac{1}{Z} \exp\left\{\sum_{i} h_i x_i + \sum_{(i,j)} J_{ij} x_i x_j\right\}$$
其中 $x_i \in \{-1, +1\}$，$h_i$ 是外场，$J_{ij}$ 是耦合强度。
玻尔兹曼机：随机神经网络，是伊辛模型的推广。
def ising_model_sample():
"""伊辛模型的Gibbs采样"""
np.random.seed(42)
# 2D伊辛模型
L = 10
T = 2.0 # 温度
n_iter = 1000
# 初始化
spins = np.random.choice([-1, 1], size=(L, L))
# Gibbs采样
for iteration in range(n_iter):
for i in range(L):
for j in range(L):
# 计算翻转能量变化
neighbors = spins[(i-1)%L, j] + spins[(i+1)%L, j] + \
spins[i, (j-1)%L] + spins[i, (j+1)%L]
delta_E = 2 * spins[i, j] * neighbors
# Metropolis准则
if delta_E < 0 or np.random.random() < np.exp(-delta_E / T):
spins[i, j] *= -1
# 可视化
fig, ax = plt.subplots(figsize=(6, 6))
ax.imshow(spins, cmap='RdBu_r', vmin=-1, vmax=1)
ax.set_title(f'Ising Model (T={T}, L={L})')
ax.set_xticks([])
ax.set_yticks([])
plt.tight_layout()
plt.savefig('ising_model.png', dpi=150)
plt.close()
magnetization = np.mean(spins)
print(f"磁化强度: {magnetization:.4f}")
print(f"温度 T={T}: {'有序相' if abs(magnetization) > 0.3 else '无序相'}")
ising_model_sample()8.3 精确推断
8.3.1 推断任务
图模型中的推断任务主要包括：
边缘概率：$p(x_i) = \sum_{\mathbf{x} \setminus x_i} p(\mathbf{x})$
条件概率：$p(x_i | x_j = a)$
最大后验（MAP）：$\arg\max_{\mathbf{x}} p(\mathbf{x} | \text{evidence})$
朴素计算需要遍历所有可能的变量赋值，复杂度为指数级。图模型的优势在于利用条件独立结构实现高效推断。
8.3.2 链式传播（Sum-Product）
对于树结构的图模型，Sum-Product算法可以在 $O(N)$ 时间内完成精确推断。
消息传递规则：
从节点 $i$ 到节点 $j$ 的消息：
$$\mu_{i \to j}(x_j) = \sum_{x_i} \phi(x_i) \psi(x_i, x_j) \prod_{k \in \text{ne}(i) \setminus j} \mu_{k \to i}(x_i)$$
节点 $i$ 的边缘概率：
$$p(x_i) \propto \phi(x_i) \prod_{k \in \text{ne}(i)} \mu_{k \to i}(x_i)$$
def sum_product_chain():
"""链式图模型上的Sum-Product算法"""
np.random.seed(42)
# 链式图: x1 - x2 - x3 - x4 - x5
n_nodes = 5
n_states = 3
# 节点势（先验）
node_potentials = [np.ones(n_states) for _ in range(n_nodes)]
node_potentials[0] = np.array([0.5, 0.3, 0.2]) # x1的先验
# 边势（转移概率）
edge_potentials = []
for _ in range(n_nodes - 1):
# 随机转移矩阵
T = np.random.rand(n_states, n_states)
T /= T.sum(axis=1, keepdims=True)
edge_potentials.append(T)
# 前向消息传递
forward_messages = [None] * n_nodes
forward_messages[0] = node_potentials[0]
for i in range(1, n_nodes):
msg = forward_messages[i-1] @ edge_potentials[i-1]
msg *= node_potentials[i]
msg /= msg.sum()
forward_messages[i] = msg
# 后向消息传递
backward_messages = [None] * n_nodes
backward_messages[-1] = np.ones(n_states)
for i in range(n_nodes - 2, -1, -1):
msg = backward_messages[i+1] * node_potentials[i+1]
msg = edge_potentials[i] @ msg
msg /= msg.sum()
backward_messages[i] = msg
# 边缘概率
marginals = []
for i in range(n_nodes):
belief = forward_messages[i] * backward_messages[i]
belief /= belief.sum()
marginals.append(belief)
print("Sum-Product算法结果（链式图）:")
for i, m in enumerate(marginals):
print(f" p(x{i+1}) = {np.round(m, 3)}")
sum_product_chain()8.3.3 树宽与推断复杂度
对于一般图，精确推断的复杂度与图的树宽（treewidth）有关。树宽为 $k$ 的图，推断复杂度为 $O(N \cdot d^k)$，其中 $d$ 是每个变量的状态数。
对于树结构（树宽为1），推断复杂度为 $O(N \cdot d^2)$，是线性的。
8.4 因子图
8.4.1 定义
因子图（Factor Graph）是一种二部图，包含两类节点：
- 变量节点（圆形）：表示随机变量
- 因子节点（方形）：表示势函数
因子图提供了最细粒度的图表示，可以统一表示有向图和无向图。
8.4.2 因子图上的Sum-Product
因子图上的消息传递规则：
从变量 $x$ 到因子 $f$ 的消息：
$$\mu_{x \to f}(x) = \prod_{h \in \text{ne}(x) \setminus f} \mu_{h \to x}(x)$$
从因子 $f$ 到变量 $x$ 的消息：
$$\mu_{f \to x}(x) = \sum_{\mathbf{x} \setminus x} f(\mathbf{x}) \prod_{y \in \text{ne}(f) \setminus x} \mu_{y \to f}(y)$$
def factor_graph_example():
"""因子图示例"""
print("因子图表示示例:")
print()
print("朴素贝叶斯: p(y, x1, x2) = p(y) · p(x1|y) · p(x2|y)")
print()
print("因子图:")
print(" 变量节点: y, x1, x2")
print(" 因子节点: f_y, f_1, f_2")
print(" 边: y-f_y, y-f_1, x1-f_1, y-f_2, x2-f_2")
print()
print("HMM: p(z1,z2,z3,x1,x2,x3) = p(z1)p(z2|z1)p(z3|z2)p(x1|z1)p(x2|z2)p(x3|z3)")
print()
print("因子图:")
print(" 变量节点: z1, z2, z3, x1, x2, x3")
print(" 因子节点: f_prior, f_trans1, f_trans2, f_emit1, f_emit2, f_emit3")
factor_graph_example()8.5 条件独立与图结构
8.5.1 有向图的道德化
在有向图上进行推断时，通常需要先将其转换为无向图（道德图），然后应用无向图的推断算法。
道德化的步骤：
对于每个head-to-head结构（$a \rightarrow c \leftarrow b$），在 $a$ 和 $b$ 之间添加无向边（"结婚"）
将所有有向边替换为无向边（"道德"）
道德化后，可以使用无向图的推断方法。
def moralization_example():
"""道德化示例"""
print("道德化示例:")
print()
print("原始有向图: a → c ← b, c → d")
print(" Head-to-head: a → c ← b")
print()
print("道德化过程:")
print(" 1. 在a和b之间添加边（结婚）")
print(" 2. 去掉箭头方向")
print()
print("道德图: a - c - b, c - d, a - b")
print()
print("条件独立关系:")
print(" 原始图: a ⊥ b (无条件)")
print(" 道德图: a 和 b 直接相连 → 不再独立")
print(" 解释: 给定c时，a和b变得相关")
moralization_example()三、实战案例
8.1 隐马尔可夫模型
def hmm_forward_backward():
"""HMM的前向-后向算法"""
np.random.seed(42)
# HMM参数
n_states = 2 # 晴天/雨天
n_obs = 3 # 散步/购物/清洁
T = 10 # 时间步
# 转移概率
A = np.array([[0.7, 0.3], # 晴天→晴天/雨天
[0.4, 0.6]]) # 雨天→晴天/雨天
# 发射概率
B = np.array([[0.5, 0.4, 0.1], # 晴天: 散步/购物/清洁
[0.1, 0.3, 0.6]]) # 雨天: 散步/购物/清洁
# 初始概率
pi = np.array([0.6, 0.4])
# 观测序列
observations = [0, 1, 2, 1, 0, 0, 1, 2, 2, 1]
# 前向算法
alpha = np.zeros((T, n_states))
alpha[0] = pi * B[:, observations[0]]
for t in range(1, T):
alpha[t] = (alpha[t-1] @ A) * B[:, observations[t]]
# 后向算法
beta = np.zeros((T, n_states))
beta[-1] = 1.0
for t in range(T-2, -1, -1):
beta[t] = A @ (B[:, observations[t+1]] * beta[t+1])
# 平滑概率
gamma = alpha * beta
gamma /= gamma.sum(axis=1, keepdims=True)
print("HMM前向-后向算法:")
print(f"{'t':>3} {'观测':>6} {'P(晴天)':>10} {'P(雨天)':>10}")
print("-" * 35)
states = ['晴天', '雨天']
obs_names = ['散步', '购物', '清洁']
for t in range(T):
print(f"{t:3d} {obs_names[observations[t]]:>6} {gamma[t,0]:10.4f} {gamma[t,1]:10.4f}")
# 可视化
fig, ax = plt.subplots(figsize=(10, 5))
ax.plot(range(T), gamma[:, 0], 'o-', label='P(晴天|观测)', linewidth=2)
ax.plot(range(T), gamma[:, 1], 's-', label='P(雨天|观测)', linewidth=2)
ax.set_xlabel('时间步')
ax.set_ylabel('平滑概率')
ax.set_title('HMM前向-后向算法：状态推断')
ax.legend()
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('hmm_forward_backward.png', dpi=150)
plt.close()
hmm_forward_backward()8.2 马尔可夫随机场去噪
def mrf_denoising():
"""使用MRF进行图像去噪"""
np.random.seed(42)
# 创建简单图像
L = 20
clean_image = np.zeros((L, L))
clean_image[:L//2, :] = 1 # 上半部分为1
clean_image[L//2:, :] = -1 # 下半部分为-1
# 添加噪声
noisy_image = clean_image.copy()
noise_mask = np.random.random((L, L)) < 0.2
noisy_image[noise_mask] *= -1
# MRF去噪（迭代条件模式 ICM）
restored = noisy_image.copy()
beta = 1.0 # 平滑参数
eta = 0.5 # 数据保真参数
for iteration in range(20):
for i in range(L):
for j in range(L):
# 计算两种状态的能量
neighbors = []
if i > 0: neighbors.append(restored[i-1, j])
if i < L-1: neighbors.append(restored[i+1, j])
if j > 0: neighbors.append(restored[i, j-1])
if j < L-1: neighbors.append(restored[i, j+1])
for state in [-1, 1]:
E_data = eta * (state - noisy_image[i, j]) ** 2
E_smooth = -beta * state * sum(neighbors)
energy = E_data + E_smooth
if state == -1:
E_minus = energy
else:
E_plus = energy
restored[i, j] = 1 if E_plus < E_minus else -1
# 可视化
fig, axes = plt.subplots(1, 3, figsize=(15, 5))
axes[0].imshow(clean_image, cmap='RdBu_r', vmin=-1, vmax=1)
axes[0].set_title('Clean Image')
axes[0].set_xticks([])
axes[0].set_yticks([])
axes[1].imshow(noisy_image, cmap='RdBu_r', vmin=-1, vmax=1)
axes[1].set_title('Noisy Image (20% flipped)')
axes[1].set_xticks([])
axes[1].set_yticks([])
axes[2].imshow(restored, cmap='RdBu_r', vmin=-1, vmax=1)
axes[2].set_title('MRF Restored (ICM)')
axes[2].set_xticks([])
axes[2].set_yticks([])
plt.tight_layout()
plt.savefig('mrf_denoising.png', dpi=150)
plt.close()
error_before = np.mean(noisy_image != clean_image)
error_after = np.mean(restored != clean_image)
print(f"去噪前错误率: {error_before:.2%}")
print(f"去噪后错误率: {error_after:.2%}")
mrf_denoising()8.3 条件随机场
def crf_example():
"""条件随机场示例"""
np.random.seed(42)
print("条件随机场（CRF）:")
print(" CRF是判别式图模型，直接建模p(y|x)")
print(" 与MRF的区别: CRF以观测为条件，不需要对观测建模")
print()
# 序列标注示例
# 观测: 词性特征
# 标签: NNP(名词), VB(动词), JJ(形容词)
n_obs = 5 # 观测序列长度
n_labels = 3 # 标签数
# 特征函数（简化）
# f1: 当前词首字母大写 → NNP
# f2: 当前词以-ing结尾 → VB
# f3: 前一个标签是NNP且当前标签是VB → 转移特征
print(f"序列长度: {n_obs}")
print(f"标签数: {n_labels}")
print()
print("CRF的优势:")
print(" 1. 不需要对观测分布建模")
print(" 2. 可以使用任意特征")
print(" 3. 避免了生成模型的强假设")
print(" 4. 在序列标注任务中表现优异")
crf_example()四、本章小结
第8章系统介绍了概率图模型的理论和应用：
贝叶斯网络：用有向无环图表示变量之间的因果关系。联合分布分解为各节点条件概率的乘积。条件独立关系通过d-分离判断。
马尔可夫随机场：用无向图表示变量之间的相关性。联合分布通过团势函数定义。条件独立关系通过图的分离性质判断。
精确推断：Sum-Product算法在树结构上实现线性时间推断。对于一般图，推断复杂度与树宽有关。道德化将有向图转换为无向图以便推断。
因子图：提供了最细粒度的图表示，统一了有向图和无向图。因子图上的消息传递算法是最通用的推断框架。
经典模型：隐马尔可夫模型、条件随机场、伊辛模型等都是图模型的特例，在各自的应用领域取得了巨大成功。
图模型是现代AI的基础设施。它提供了模块化的建模方式、高效的推断算法和清晰的理论框架。后续的第9章混合模型和第10章近似推断都大量使用了图模型的工具。
五、思考与练习
思考题
有向图和无向图在表达能力上有什么区别？是否存在一个分布可以用有向图表示但不能用无向图表示？
解释效应（explaining away）在实际应用中有什么意义？请举一个具体的例子。
为什么树结构上的推断是高效的？树宽如何影响推断复杂度？
CRF相比HMM有什么优势？为什么在序列标注中CRF通常优于HMM？
道德化过程中添加的边有什么物理含义？
编程练习
HMM参数学习：实现Baum-Welch算法（EM在HMM中的应用），从观测序列中学习HMM的参数。
信念传播：在一般图上实现Loopy Belief Propagation，观察其与精确推断的差异。
MRF图像分割：使用MRF对灰度图像进行前景-背景分割，比较不同平滑参数的效果。