概率图模型：图上的不确定性推理

前面的文章中，我们把图当作确定性结构：节点有或没有，边存在或不存在，最短路径要么是 5 要么是 7。但现实世界充满不确定性——看到草地是湿的，是下雨了还是洒水器开了？病人发烧加咳嗽，是感冒还是肺炎？传感器网络中，某个读数异常，是真的故障还是噪声？

这些问题的共同特点是：变量之间有依赖关系，但每个变量的值不确定。如果把每个变量看成图的一个节点，变量间的依赖看成边，我们就得到了一张概率图模型（Probabilistic Graphical Model, PGM）——用图结构来表示和利用概率中的条件独立性，从而让原本指数级复杂的联合概率推理变得可计算。

没有概率图模型，一个有 $n$ 个二值变量的系统需要存储 $2^n - 1$ 个参数来描述联合概率分布——20 个变量就超过百万。PGM 利用图结构的条件独立性，将参数量和推理复杂度从指数级降到多项式级。这正是图算法在概率世界中的核心贡献。

算法范式：消息传递（信念传播）、动态规划（树上精确推理 = 消除算法）

边界声明：本文聚焦图结构和图上的消息传递算法。概率推断的更深数学细节（MCMC、变分推断、参数学习）属于未来的概率/统计路径，本文仅点到为止。

核心思路：用图结构分解联合概率

在进入具体模型之前，先抓住 PGM 的核心直觉：

一个复杂系统的联合概率可以根据变量之间的条件独立关系，分解为若干”局部”因子的乘积。 图的节点表示随机变量，图的边（或边的缺失）编码了条件独立性。图越稀疏，条件独立性越多，推理越高效。

这个思想有两种主要实现：

• 有向图（贝叶斯网络）：边表示因果/条件方向，联合概率 = 各节点条件概率之积
• 无向图（马尔可夫随机场）：边表示对称关联，联合概率 = 各团势函数之积 / 归一化常数

两者可以统一在因子图框架下，而信念传播算法在因子图上自然地完成推理。

贝叶斯网络（Bayesian Network）

定义与直觉

贝叶斯网络（BN, Bayesian Network）是一个有向无环图（DAG），其中：

• 每个节点代表一个随机变量（如”是否下雨”、“草地是否湿”）
• 每条有向边 $X_i \to X_j$ 表示 $X_i$ 对 $X_j$ 有直接的概率影响
• 每个节点附带一个条件概率表（CPT, Conditional Probability Table）：$P(X_i \mid \text{Parents}(X_i))$

联合概率分解

贝叶斯网的核心数学性质是链式法则 + 条件独立：

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

逐项理解：

• $X_i$：第 $i$ 个随机变量（图中的节点）
• $\text{Pa}(X_i)$：节点 $X_i$ 的父节点集合（有向边指向 $X_i$ 的那些节点）
• $P(X_i \mid \text{Pa}(X_i))$：$X_i$ 的条件概率表——只依赖父节点，不依赖其他节点
• 乘积 $\prod$：联合概率分解为各节点局部条件概率的乘积

以”草地湿了”的例子为例：

$P(C, S, R, W) = P(C) \cdot P(S \mid C) \cdot P(R \mid C) \cdot P(W \mid S, R)$

这比存储完整的 $2^4 = 16$ 项联合概率表要紧凑得多——只需 $1 + 2 + 2 + 4 = 9$ 个参数。对于有 100 个节点、每个节点最多 3 个父节点的贝叶斯网，参数量从 $2^{100}$（天文数字）降到 $100 \times 2^3 = 800$。

数值例子：计算联合概率

用上图的 CPT 具体计算。假设 $C = \text{True}$（多云），$S = \text{False}$（洒水器关），$R = \text{True}$（下雨），$W = \text{True}$（草湿）：

$P(C{=}T, S{=}F, R{=}T, W{=}T) = P(C{=}T) \cdot P(S{=}F \mid C{=}T) \cdot P(R{=}T \mid C{=}T) \cdot P(W{=}T \mid S{=}F, R{=}T)$

查表代入：

$= 0.5 \times 0.9 \times 0.8 \times 0.8 = 0.288$

这个计算只涉及 4 次乘法，而非遍历所有 $2^4$ 种组合。

d-分离：读图判断条件独立性

贝叶斯网不仅能紧凑地表示联合概率，还能直接从图结构中读出哪些变量在给定证据后条件独立。这个判断规则叫 d-separation（有向分离）。

d-separation 的三种基本结构：

1. 链（Chain）：$A \to B \to C$。如果 $B$ 被观测，$A$ 和 $C$ 条件独立。直觉：$B$ 是 $A$ 到 $C$ 的唯一信息通道，观测 $B$ 后截断了信息流。

2. 叉（Fork）：$A \leftarrow B \to C$。如果 $B$ 被观测，$A$ 和 $C$ 条件独立。直觉：$A$ 和 $C$ 的关联完全由共同原因 $B$ 解释，一旦知道 $B$，两者独立。

3. 对撞（Collider）：$A \to B \leftarrow C$。未观测 $B$ 时 $A \perp C$；观测 $B$ 后 $A$ 和 $C$ 反而变相关！这就是著名的 explaining away（解释竞争）效应。直觉：如果 $B$（草湿）被观测为 True，而你知道 $A$（洒水器开了），那 $C$（下雨）的概率就降低了——两个原因在”竞争解释”同一个结果。

一般规则：给定观测集 $Z$，若 $A$ 到 $C$ 的所有路径都被 d-separation 阻断，则 $A \perp C \mid Z$。

与 HMM 的联系

隐马尔可夫模型（HMM）是贝叶斯网的一个特例：状态变量 $S_1 \to S_2 \to \cdots \to S_T$ 形成链，每个状态 $S_t$ 生成一个观测 $O_t$。HMM 的 Forward-Backward 算法就是在这个链式贝叶斯网上运行的信念传播。

马尔可夫随机场（MRF）

定义与直觉

马尔可夫随机场（MRF, Markov Random Field），也叫无向图模型（Undirected Graphical Model），用无向图表示变量间的关系：

• 每个节点是一个随机变量
• 每条无向边表示两个变量之间的对称关联（没有方向性）
• 联合概率通过势函数（potential function）定义

联合概率分解

MRF 的联合概率定义为图中所有最大团（maximal clique）上势函数的乘积，再除以归一化常数：

$P(X_1, \ldots, X_n) = \frac{1}{Z} \prod_{c \in \mathcal{C}} \psi_c(X_c)$

逐项理解：

• $\mathcal{C}$：图中所有最大团的集合（团 = 两两相连的完全子图，参见 Art. 10）
• $\psi_c(X_c)$：团 $c$ 上的势函数——一个非负函数，衡量团内变量取某一组值时的”兼容程度”。$\psi$ 值越大，表示这组值越”合理”
• $Z = \sum_{X_1, \ldots, X_n} \prod_c \psi_c(X_c)$：配分函数（partition function），确保概率和为 1
• 关键区别：势函数 $\psi$ 不是条件概率，它可以是任意非负函数

配分函数 $Z$ 的计算困难

配分函数 $Z$ 需要对所有变量的所有取值组合求和——这通常是 NP-hard 的。这是 MRF 与贝叶斯网的一个重要区别：贝叶斯网的联合概率天然归一化（条件概率表的每行和为 1），不需要计算 $Z$。

MRF 的马尔可夫性质

MRF 的核心性质是局部马尔可夫性：

$P(X_i \mid X_{-i}) = P(X_i \mid \text{Neighbors}(X_i))$

即：每个节点在给定其所有邻居后，与图中其余节点条件独立。 这在图像处理中非常自然——一个像素的值只直接依赖于周围像素，而非整张图片。

贝叶斯网 vs MRF

特征	贝叶斯网（BN）	马尔可夫随机场（MRF）
图类型	有向无环图（DAG）	无向图
边的含义	因果/条件方向	对称关联
参数	条件概率表 $P(X \mid \text{Pa})$	势函数 $\psi(X_{\text{clique}})$
归一化	自动（CPT 行和 = 1）	需要配分函数 $Z$
适用场景	因果关系明确	对称约束（图像、空间）

两者并非完全对立——Hammersley-Clifford 定理建立了它们之间的等价条件：在正概率分布下，MRF 等价于 Gibbs 分布。

条件随机场（CRF）

条件随机场（CRF, Conditional Random Field, Lafferty et al., 2001）是 MRF 的一个重要特化，在自然语言处理中是序列标注的经典工具。

HMM vs CRF

CRF 与 HMM 有密切联系，但有一个关键区别：

• HMM 是生成式模型：建模联合概率 $P(X, Y) = P(Y_1) \prod P(Y_t \mid Y_{t-1}) \prod P(X_t \mid Y_t)$，然后用贝叶斯定理得 $P(Y \mid X)$
• CRF 是判别式模型：直接建模条件概率 $P(Y \mid X)$，不需要建模 $P(X)$

CRF 的优势在于：

1. 可以使用重叠特征：$f(y_t, y_{t-1}, X, t)$ 可以依赖整个输入序列 $X$，而非只依赖当前观测 $X_t$
2. 不需要独立性假设：HMM 要求 $P(X_t \mid Y_t)$ 只依赖当前状态，CRF 没有这个限制
3. 在序列标注任务上通常优于 HMM

线性链 CRF 的条件概率形式为：

$P(Y \mid X) = \frac{1}{Z(X)} \exp\left(\sum_{t=1}^{T} \sum_{k} \lambda_k f_k(y_t, y_{t-1}, X, t)\right)$

其中 $f_k$ 是特征函数，$\lambda_k$ 是待学习的权重，$Z(X) = \sum_Y \exp(\cdots)$ 是配分函数。

因子图：统一表示

因子图（Factor Graph）是统一贝叶斯网和 MRF 的通用表示框架。信念传播算法在因子图上的定义最为自然。

定义

因子图是一个二部图，包含两种节点：

1. 变量节点（圆形）：对应随机变量
2. 因子节点（方形）：对应局部函数（条件概率或势函数）

变量节点和因子节点之间有边当且仅当该变量出现在该因子的参数中。

联合概率在因子图上表示为：

$P(X_1, \ldots, X_n) = \frac{1}{Z} \prod_{a} f_a(X_{N(a)})$

其中 $f_a$ 是第 $a$ 个因子，$X_{N(a)}$ 是与因子 $a$ 相连的变量集合。

转换规则

• 贝叶斯网 → 因子图：每个 CPT $P(X_i \mid \text{Pa}(X_i))$ 变成一个因子节点，连接到 $X_i$ 和 $\text{Pa}(X_i)$
• MRF → 因子图：每个团势函数 $\psi_c(X_c)$ 变成一个因子节点，连接到团内所有变量

因子图的优势：

• 统一了有向/无向模型
• 信念传播算法在因子图上定义最清晰
• 可以表示更细粒度的分解（一个 MRF 团可以拆成多个因子）

信念传播（Belief Propagation）

信念传播（BP, Belief Propagation），也叫 sum-product 算法，是概率图模型上最核心的推理算法。它的直觉极其简洁：每个节点向邻居发送”我认为你应该是什么状态”的消息，反复交换消息后，每个节点汇总收到的消息得到自己的信念。

消息传递公式

在因子图上，信念传播定义了两种消息：

变量→因子消息：变量 $x$ 发给因子 $f$ 的消息等于 $x$ 从其他所有因子收到的消息之积：

$\mu_{x \to f}(x) = \prod_{g \in N(x) \setminus f} \mu_{g \to x}(x)$

因子→变量消息：因子 $f$ 发给变量 $x$ 的消息等于 $f$ 对其他变量的边缘化：

$\mu_{f \to x}(x) = \sum_{X_{N(f) \setminus x}} f(X_{N(f)}) \prod_{y \in N(f) \setminus x} \mu_{y \to f}(y)$

逐项理解后一个公式：

• $f(X_{N(f)})$：因子 $f$ 的值（条件概率或势函数）
• $\sum_{X_{N(f) \setminus x}}$：对除 $x$ 外的所有变量求和（边缘化）
• $\prod_{y \in N(f) \setminus x} \mu_{y \to f}(y)$：其他变量发来的消息
• 直觉：因子 $f$ 综合自己的”知识”和从其他变量收到的消息，告诉 $x$“我认为你应该是什么状态”

最终信念：每个变量的信念（近似边缘概率）等于它收到的所有消息之积（归一化后）：

$b(x) \propto \prod_{f \in N(x)} \mu_{f \to x}(x)$

树上精确推理

当图是树结构（无环）时，信念传播保证给出精确的边缘概率。算法分两步：

1. 收集阶段（Collect / Upward Pass）：选择任意节点为根，从叶节点向根传递消息
2. 分发阶段（Distribute / Downward Pass）：从根向叶节点传递消息

两次传递后，每个节点都收到了来自图中所有方向的信息，计算出的信念就是精确的边缘概率。

复杂度：对于树结构，$n$ 个节点、每个变量 $k$ 个状态，信念传播的时间复杂度为 $O(n \cdot k^2)$——每条边发送一条消息，每条消息的计算需要 $O(k^2)$（对发送方的 $k$ 个状态求和）。

信念传播走查

下面的交互组件展示信念传播在一个 4 节点链 A-B-C-D 上的完整过程。设定证据 $D = 1$，势函数鼓励相邻节点取相同值 $\psi(\text{same}) = 0.9, \psi(\text{diff}) = 0.1$。观察证据如何沿链传播。

信念传播走查链图 A-B-C-D · 二值变量 · 证据 D=1

步骤 1/10: 初始状态：4 个二值节点 A-B-C-D 组成链。每对相邻节点的势函数 ψ 鼓励取相同值：ψ(相同)=0.9, ψ(不同)=0.1。

重置

1 / 10上一步下一步

走查中的关键观察：

• 证据衰减：$D = 1$ 的证据沿链传播，越远影响越弱——$P(C{=}1) = 0.90$，$P(B{=}1) = 0.82$，$P(A{=}1) = 0.76$。这是因为每经过一个势函数，“确信度”都会被稀释
• 双向传递：Pass 1（D→A）携带证据，Pass 2（A→D）从另一端传递信息。A 没有额外信息，所以 Pass 2 的消息都是均匀的
• 精确性：在树/链上，BP 给出的就是精确的边缘概率，无需近似

与标签传播的联系

信念传播和 Art. 8 中的标签传播算法有深刻联系：

• 标签传播：每个节点采纳邻居中最多数的标签 → 这是”硬”消息传递（每个消息是一个确定的标签）
• 信念传播：每个节点向邻居发送概率分布 → 这是”软”消息传递（每个消息是一个分布）

标签传播可以看作信念传播的极度简化版——将连续概率替换为硬标签，将概率乘法替换为多数投票。

Loopy 信念传播

当图有环时，信念传播不保证给出精确结果，也不保证收敛。但在实践中，人们仍然在有环图上运行 BP——称为 Loopy BP：

• 初始化所有消息为均匀分布
• 反复按某种调度更新所有消息
• 如果收敛，输出的信念作为边缘概率的近似

Loopy BP 在许多实际问题中表现出色（如纠错码解码、图像分割），但理论上：

• 可能不收敛（消息在环中振荡）
• 即使收敛，信念也只是近似值（环使信息被”重复计数”）

缓解方法：消息衰减（damping）——新消息 = $\alpha \cdot$ 旧消息 + $(1-\alpha) \cdot$ 计算得到的消息，$\alpha \in (0, 1)$。

变量消除算法

变量消除（Variable Elimination）是另一种精确推理算法，从动态规划的角度理解 PGM 推理。

核心思想

要计算某个变量的边缘概率 $P(X_q)$，我们需要对所有其他变量求和：

$P(X_q) = \sum_{X_1} \sum_{X_2} \cdots \sum_{X_{n-1}} P(X_1, \ldots, X_n)$

朴素地计算需要遍历所有 $k^n$ 种组合。但联合概率已经被分解为局部因子的乘积——变量消除利用求和的乘法分配律，将求和”推入”乘积中：

$\sum_{X_1} \sum_{X_2} f(X_1, X_2) \cdot g(X_2, X_3) = \sum_{X_2} g(X_2, X_3) \cdot \left[\sum_{X_1} f(X_1, X_2)\right]$

先对 $X_1$ 求和（消除 $X_1$），得到一个关于 $X_2$ 的新因子；然后再消除 $X_2$，以此类推。

复杂度与树宽

变量消除的复杂度取决于消除顺序。最优消除顺序使得中间因子的最大大小最小化，这个最小值与图的树宽（treewidth）$w$ 密切相关：

• 时间复杂度：$O(n \cdot k^{w+1})$
• 空间复杂度：$O(k^{w+1})$

树宽 $w$ 衡量图”离树有多远”：

• 树的树宽 $w = 1$ → $O(n \cdot k^2)$，与 BP 一致
• 链的树宽 $w = 1$
• 网格的树宽 $w = \sqrt{n}$ → $O(n \cdot k^{\sqrt{n}})$，仍然是指数级
• 完全图的树宽 $w = n - 1$ → 退化为暴力枚举

找最优消除顺序本身是 NP-hard 的，但有好的启发式（如最小度数、最小填充）。

复杂度对比表

算法	精确/近似	时间复杂度	适用图结构	核心思想
信念传播（树）	精确	$O(n \cdot k^2)$	树/链	消息传递
Loopy BP	近似	$O(n \cdot k^2)$ 每轮	一般图	迭代消息传递
变量消除	精确	$O(n \cdot k^{w+1})$	任意（取决于树宽）	动态规划
联结树算法	精确	$O(n \cdot k^{w+1})$	任意	树分解 + BP
MCMC 采样	近似	依赖收敛	任意	随机采样
变分推断	近似	依赖模型	任意	优化近似分布

其中 $n$ = 变量数，$k$ = 每个变量的状态数，$w$ = 树宽。

关键洞察：树宽是决定精确推理是否可行的关键参数。树宽小（如链、树）→ 精确推理高效；树宽大（如密集图）→ 只能用近似方法。

应用场景

医疗诊断系统

最早的 PGM 应用之一。QMR-DT（Quick Medical Reference）系统用一个大型贝叶斯网连接 600 种疾病和 4000 个症状。医生输入观察到的症状，系统利用信念传播推理最可能的疾病。关键优势：能处理多种疾病同时存在的情况，且推理过程透明（可以解释”因为观察到 X 和 Y 症状，所以疾病 Z 的概率升高”）。

NLP 序列标注

CRF 在词性标注（POS tagging）和命名实体识别（NER）中是经典工具。线性链 CRF 捕捉标签间的转移模式（如”形容词后面通常跟名词”）和观测特征（如”以大写字母开头的词更可能是专有名词”）。虽然近年来被 Transformer 架构替代，但 CRF 层仍然常作为 BERT 等模型的输出层，用于保证标签序列的一致性。

图像分割与去噪

MRF 天然适合图像处理——像素网格就是一个 MRF，相邻像素的标签（物体类别/去噪后的值）应该一致。势函数鼓励相邻像素取相同标签（空间平滑），同时考虑观测值（像素亮度）。信念传播或 graph cut 算法用于高效推理。

因果推断

贝叶斯网的有向边可以赋予因果解释。Pearl 的 do-calculus 在 DAG 上定义了”干预”操作 $P(Y \mid do(X = x))$，回答”如果我主动将 $X$ 设为 $x$，$Y$ 会怎样”这类因果问题。这与 Art. 19 案例集 中的因果推断案例直接相关。

总结

本文围绕”当节点有不确定性时，如何利用图结构高效推理”这个核心问题，建立了概率图模型的完整框架：

• 贝叶斯网络（有向 DAG）：联合概率 = $\prod P(X_i \mid \text{Pa}(X_i))$。d-separation 规则让你直接从图中读出条件独立性。
• 马尔可夫随机场（无向图）：联合概率 = $(1/Z) \prod \psi_c(X_c)$。势函数表示对称关联，但配分函数 $Z$ 通常难算。
• CRF：MRF 的判别式版本，直接建模 $P(Y \mid X)$，是序列标注的经典工具。
• 因子图：统一有向/无向模型的二部图表示。
• 信念传播：消息传递算法，树上精确、一般图上近似（Loopy BP）。核心公式：每个节点汇总邻居消息计算自己的信念。
• 变量消除：动态规划视角的精确推理，复杂度取决于树宽。

图结构是连接”概率”和”计算效率”的桥梁——稀疏的图意味着更多的条件独立性，意味着更高效的推理。这正是图算法在概率世界的核心价值。

下一篇 Art. 18: 图嵌入与 GNN 将从概率推理转向表示学习——用神经网络在图上学习节点和图的向量表示。而概率图模型在真实问题中的具体应用（如因果推断、诊断系统构建）将在 Art. 19: 案例集 中展开。

实现指引

工具	库	用法
贝叶斯网构建	pgmpy	BayesianNetwork([('C','S'),('C','R'),...])
贝叶斯网推理	pgmpy	VariableElimination(model).query(['W'], evidence={'R':1})
MRF 构建	pgmpy	MarkovNetwork([('X1','X2'),('X2','X3')])
信念传播	pgmpy	BeliefPropagation(model).query(['X'], evidence={...})
CRF 序列标注	sklearn-crfsuite	CRF(algorithm='lbfgs').fit(X_train, y_train)
CRF 层	pytorch-crf	CRF(num_tags).forward(emissions, tags)
贝叶斯网学习	pomegranate	BayesianNetwork.from_samples(data)
概率编程	PyMC	pm.Model() + pm.sample()
概率编程	Stan / PyStan	StanModel(model_code=...).sampling(data=...)
因果推断	DoWhy	CausalModel(data, treatment, outcome, graph)