第13章概率图模型：表示#

“The purpose of computing is insight, not numbers.” — Richard Hamming

“Graphical models are a marriage between probability theory and graph theory.” — Michael I. Jordan

13.1 引言：为什么需要概率图模型？#

13.1.1 高维联合概率分布的困境#

考虑 $n$ 个二值随机变量 $X_1, X_2, \ldots, X_n$。完整的联合概率分布 $P(X_1, X_2, \ldots, X_n)$ 需要存储 $2^n - 1$ 个参数（减1是因为概率和为1的约束）。

问题：

存储复杂度：随着变量数量指数增长，参数空间爆炸。
估计复杂度：从数据中估计如此多的参数需要海量样本。
推断复杂度：在高维空间中进行边缘化或条件化计算不可行。

解决方案：利用变量间的条件独立性来分解联合概率分布。

13.1.2 条件独立性的威力#

如果变量 $X$ 和 $Y$ 在给定 $Z$ 的条件下独立，记作 $X \perp Y \mid Z$，则：

$$ P(X, Y \mid Z) = P(X \mid Z) P(Y \mid Z) $$

这种独立性结构可以用图来表示：

节点代表随机变量。
边代表变量间的依赖关系。

概率图模型（Probabilistic Graphical Models, PGM）通过图结构编码条件独立性，将高维联合分布分解为低维因子的乘积。

13.1.3 图模型的两大家族#

贝叶斯网络（Bayesian Networks）：使用有向无环图（DAG）表示因果关系。
马尔可夫随机场（Markov Random Fields）：使用无向图表示对称的局部依赖关系。

13.2 贝叶斯网络（Bayesian Networks）#

13.2.1 定义与基本结构#

定义 13.1（贝叶斯网络） 贝叶斯网络是一个有向无环图 $G = (V, E)$，其中：

每个节点 $v_i \in V$ 对应随机变量 $X_i$。
每条有向边 $v_i \to v_j$ 表示 $X_i$ 对 $X_j$ 有直接影响。
联合概率分布分解为：

$$ P(X_1, X_2, \ldots, X_n) = \prod_{i=1}^{n} P(X_i \mid \text{Pa}(X_i)) $$

其中 $\text{Pa}(X_i)$ 是 $X_i$ 的父节点集合。

物理直觉：每个变量只依赖于其直接原因（父节点），这体现了局部马尔可夫性。

13.2.2 局部马尔可夫性#

定理 13.1（局部马尔可夫性） 在贝叶斯网络中，每个变量在给定其父节点的条件下，与其非后代节点条件独立：

$$ X_i \perp \text{NonDesc}(X_i) \mid \text{Pa}(X_i) $$

证明思路：由链式法则分解联合概率，观察到 $X_i$ 的条件概率只涉及 $\text{Pa}(X_i)$，与其他非后代节点无关。

13.2.3 D-分离（D-Separation）#

D-分离是判定贝叶斯网络中条件独立性的核心工具。

定义 13.2（D-分离） 给定节点集合 $Z$，如果所有从 $X$ 到 $Y$ 的路径都被 $Z$ “阻塞”（blocked），则称 $X$ 和 $Y$ 被 $Z$ D-分离，记作 $X \perp_d Y \mid Z$。

阻塞规则：路径被阻塞当且仅当路径上存在节点 $W$ 满足以下条件之一：

Head-to-Tail（串联）：$X \to W \to Y$
- 如果 $W \in Z$，路径被阻塞。
- 物理意义：观测到中间变量后，信息传递被切断。
Tail-to-Tail（分叉）：$X \leftarrow W \to Y$
- 如果 $W \in Z$，路径被阻塞。
- 物理意义：观测到共同原因后，结果变量独立。
Head-to-Head（碰撞）：$X \to W \leftarrow Y$
- 如果 $W \notin Z$ 且 $W$ 的后代都不在 $Z$ 中，路径被阻塞。
- 物理意义：未观测共同结果时，原因变量独立；观测后反而产生依赖（“解释效应”）。

定理 13.2（D-分离与条件独立） 在贝叶斯网络中，$X \perp_d Y \mid Z$ 当且仅当 $X \perp Y \mid Z$（对于任何满足该网络的概率分布）。

示例 13.1（解释效应） 考虑网络：$\text{雨} \to \text{地湿} \leftarrow \text{洒水器}$。

未观测地湿时：雨和洒水器独立。
观测到地湿后：知道下雨了，会降低洒水器开启的概率（解释了地湿）。

这是 Head-to-Head 结构的经典例子。

13.2.4 典型结构：朴素贝叶斯分类器#

结构：类别变量 $C$ 作为根节点，所有特征 $X_1, \ldots, X_d$ 作为子节点。

$$ P(C, X_1, \ldots, X_d) = P(C) \prod_{i=1}^{d} P(X_i \mid C) $$

假设：特征在给定类别条件下独立（朴素假设）。

$$ P(C \mid X_1, \ldots, X_d) \propto P(C) \prod_{i=1}^{d} P(X_i \mid C) $$

优点：

参数数量从 $O(2^d)$ 降至 $O(d)$。
计算高效，对小样本鲁棒。

局限：朴素假设往往不成立，但实践中效果依然良好（为什么？后续章节讨论）。

13.2.5 典型结构：隐马尔可夫模型（HMM）#

结构：

隐状态序列 $Z_1 \to Z_2 \to \cdots \to Z_T$（马尔可夫链）。
观测序列 $X_1, X_2, \ldots, X_T$，每个 $X_t$ 依赖于 $Z_t$。

$$ P(Z_{1:T}, X_{1:T}) = P(Z_1) \prod_{t=2}^{T} P(Z_t \mid Z_{t-1}) \prod_{t=1}^{T} P(X_t \mid Z_t) $$

应用：语音识别、自然语言处理、基因序列分析。

13.3 马尔可夫随机场（Markov Random Fields）#

13.3.1 定义与基本概念#

定义 13.3（马尔可夫随机场） 马尔可夫随机场是一个无向图 $G = (V, E)$，其中：

每个节点 $v_i \in V$ 对应随机变量 $X_i$。
边 ${v_i, v_j} \in E$ 表示 $X_i$ 和 $X_j$ 直接相关。

全局马尔可夫性：给定邻居节点，每个节点与其他节点条件独立。

$$ X_i \perp X_{V \setminus {i} \cup \text{Ne}(i)} \mid X_{\text{Ne}(i)} $$

其中 $\text{Ne}(i)$ 是 $i$ 的邻居节点。

成对马尔可夫性：如果两个节点不相邻，则在给定其他所有节点条件下独立。

$$ X_i \perp X_j \mid X_{V \setminus {i, j}} \quad \text{if } {i, j} \notin E $$

13.3.2 团与最大团#

定义 13.4（团） 图 $G$ 的一个团（Clique）是节点的子集 $C \subseteq V$，其中任意两个节点都相邻。

定义 13.5（最大团） 最大团（Maximal Clique）是不能再添加任何节点的团。

示例：在三角形图（3个全连接节点）中，整个图是唯一的最大团。

13.3.3 Hammersley-Clifford 定理#

定理 13.3（Hammersley-Clifford 定理） 如果概率分布 $P(X)$ 严格为正，则 $P(X)$ 满足马尔可夫随机场 $G$ 当且仅当它可以分解为最大团上的势函数乘积：

$$ P(X) = \frac{1}{Z} \prod_{C \in \mathcal{C}} \psi_C(X_C) $$

其中：

$\mathcal{C}$ 是所有最大团的集合。
$\psi_C(X_C)$ 是定义在团 $C$ 上的势函数（非负函数）。
$Z = \sum_{X} \prod_{C \in \mathcal{C}} \psi_C(X_C)$ 是配分函数（归一化常数）。

物理意义：

势函数编码局部偏好（类比物理系统中的能量）。
配分函数确保概率归一化（类比统计物理中的配分函数）。

证明思路：

必要性：由局部马尔可夫性推导因子分解。
充分性：由因子分解验证条件独立性。

13.3.4 Gibbs 分布与能量函数#

势函数通常写为指数形式：

$$ \psi_C(X_C) = \exp(-E_C(X_C)) $$

其中 $E_C(X_C)$ 是能量函数。联合分布变为：

$$ P(X) = \frac{1}{Z} \exp\left(-\sum_{C \in \mathcal{C}} E_C(X_C)\right) $$

这称为Gibbs 分布。物理直觉：低能量状态概率高（类比玻尔兹曼分布）。

13.3.5 典型结构：Ising 模型#

定义：二值变量 $X_i \in {-1, +1}$ 排列在网格上，只有相邻节点有边。

$$ P(X) = \frac{1}{Z} \exp\left(\sum_{{i,j} \in E} \theta_{ij} X_i X_j + \sum_{i \in V} \theta_i X_i\right) $$

参数：

$\theta_{ij}$：耦合强度（相邻节点倾向于相同符号）。
$\theta_i$：外部场（节点的先验偏好）。

应用：

统计物理（铁磁性）。
计算机视觉（图像分割、去噪）。

13.3.6 典型应用：图像去噪#

建模：

观测像素 $Y_{ij}$（带噪声）。
真实像素 $X_{ij}$（待恢复）。

能量函数：

$$ E(X, Y) = \sum_{i,j} (X_{ij} - Y_{ij})^2 + \lambda \sum_{\text{neighbors}} (X_{ij} - X_{kl})^2 $$

第一项：数据项，鼓励 $X$ 接近观测 $Y$。
第二项：平滑项，鼓励相邻像素相似（去噪）。
$\lambda$：平衡参数。

推断：通过最大后验（MAP）或边缘化求解最优 $X$。

13.4 因子图（Factor Graphs）#

13.4.1 动机：统一表示#

贝叶斯网络和马尔可夫随机场各有优势：

贝叶斯网络：有向图，清晰编码因果关系。
马尔可夫随机场：无向图，对称编码局部依赖。

问题：如何统一表示两者？

答案：因子图（Factor Graph）。

13.4.2 定义#

定义 13.6（因子图） 因子图是一个二部图 $G = (V \cup F, E)$，包含：

变量节点 $V$：对应随机变量 $X_i$。
因子节点 $F$：对应因子函数 $f_a(X_a)$。
边 $E$：连接因子和其涉及的变量。

联合概率分布分解为：

$$ P(X) = \frac{1}{Z} \prod_{a \in F} f_a(X_a) $$

其中 $X_a$ 是因子 $f_a$ 涉及的变量子集。

13.4.3 与其他图模型的关系#

从贝叶斯网络到因子图：每个条件概率 $P(X_i \mid \text{Pa}(X_i))$ 对应一个因子。
从马尔可夫随机场到因子图：每个势函数 $\psi_C(X_C)$ 对应一个因子。

优势：

显式表示因子，便于推断算法（如 Belief Propagation）。
避免有向图和无向图的转换歧义。

13.4.4 示例：HMM 的因子图表示#

对于 HMM：

$$ P(Z_{1:T}, X_{1:T}) = f_0(Z_1) \prod_{t=2}^{T} f_t(Z_{t-1}, Z_t) \prod_{t=1}^{T} g_t(Z_t, X_t) $$

因子图包含：

变量节点：$Z_1, \ldots, Z_T, X_1, \ldots, X_T$。
因子节点：$f_0, f_2, \ldots, f_T, g_1, \ldots, g_T$。

13.5 有向图与无向图的转换#

13.5.1 道德图（Moralization）#

将有向图转换为无向图的过程称为道德化：

为每个节点的父节点之间添加无向边（“结婚”）。
移除所有边的方向。

结果：道德图是一个无向图，但可能引入额外的边（丢失部分独立性信息）。

13.5.2 三角化（Triangulation）#

为确保无向图可以高效推断，需要进行三角化：在每个长度 $\geq 4$ 的环中添加弦，使得图中没有无弦环。

目的：简化推断算法（如变量消除）。

13.6 表示能力的比较#

定理 13.4（I-map 与 P-map）

I-map（Independence Map）：图 $G$ 蕴含的独立性都在分布 $P$ 中成立。
P-map（Perfect Map）：图 $G$ 蕴含的独立性恰好是 $P$ 中的独立性。

观察：

有向图和无向图各有所长，但表示能力不同。
某些分布只能用有向图完美表示（如 Head-to-Head 结构）。
某些分布只能用无向图完美表示（如循环依赖）。

13.7 小结#

本章介绍了概率图模型的表示理论：

贝叶斯网络：
- 有向无环图，编码因果关系。
- 局部马尔可夫性与 D-分离规则。
- 典型应用：朴素贝叶斯、HMM。
马尔可夫随机场：
- 无向图，编码对称依赖。
- Hammersley-Clifford 定理：分解为势函数乘积。
- 典型应用：Ising 模型、图像去噪。
因子图：
- 统一表示框架，显式因子节点。
- 为推断算法提供便利。
表示能力：
- 有向图与无向图表达不同的独立性结构。
- 道德化和三角化用于图转换。

下一章预告：我们将探讨如何在这些图模型上进行推断（Inference），包括精确推断（变量消除、信念传播）和近似推断（MCMC、变分推断）。

练习题#

13.1 证明局部马尔可夫性：在贝叶斯网络中，$X_i \perp \text{NonDesc}(X_i) \mid \text{Pa}(X_i)$。

13.2 给定贝叶斯网络：$A \to B \to C \leftarrow D$，判断以下独立性是否成立：

(a) $A \perp D$
(b) $A \perp D \mid B$
(c) $A \perp D \mid C$

13.3 推导 Ising 模型的配分函数 $Z$（提示：在小规模网格上枚举所有状态）。

13.4 绘制朴素贝叶斯分类器的因子图表示。

13.5 将以下马尔可夫随机场转换为道德图：一个环形图 $X_1 - X_2 - X_3 - X_4 - X_1$。

参考文献#

Koller, D., & Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques. MIT Press.
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. (Chapter 8)
Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann.
Wainwright, M. J., & Jordan, M. I. (2008). Graphical Models, Exponential Families, and Variational Inference. Foundations and Trends in Machine Learning.

第13章 概率图模型：表示#