Huajishe Notes

0-PGM-概率图模型

24 min read

概率图模型（PGM）核心理论与算法推导

前置知识假设：读者已掌握概率论（条件概率、贝叶斯定理、全概率公式）、微积分（多元微分、矩阵运算）以及基本的信息论概念（熵、KL散度）。本文档目标是从底层数学逻辑构建对 PGM 的系统性理解。

一、表示理论 (Representation)

1.1 贝叶斯网络 (Bayesian Network / Directed Graphical Model)

1.1.1 因子分解公式

贝叶斯网络 又称有向图模型，其核心思想是利用有向无环图（DAG）编码随机变量之间的条件依赖关系。

设图 ，节点集合 ，每条边表示直接的因果影响。对于任意节点 ，令 表示其父节点集合，则联合分布可以因子分解为：

其中约定：当 （即无父节点）时，。

Bayes 定理在图模型中的作用：在因子分解中，每个条件概率分布 本质上是贝叶斯规则的局部应用——当我们有父节点的先验知识时，它定义了子节点的似然。

为什么分解是合理的？

根据链式法则，任何联合分布都满足：

若图结构规定只有 中的变量直接影响 ，则 以外的变量在条件中都可以边缘化掉，上式恰好化简为因子分解形式。

1.1.2 D-分离（D-separation）准则

核心问题：给定图结构，我们如何快速判断两组变量之间是否条件独立？

D-分离 提供了一套基于图结构的判定准则，是贝叶斯网络中最重要的工具性定理。

定义（迹 / Trail）：一条从节点 到节点 的迹（trail）指二者之间沿任意方向（顺向或逆向）的一条路径。路径经过的中间节点集合记为 。

D-分离的三条基本规则：

规则 1：顺序结构（Serial / Chain）

A → M → B

当中间节点 被观测（即 ）时， 与 条件独立。

直观理解： 作为”信息管道”，一旦我们知道 的值，从 到 的信息流就被阻断。

规则 2：发散结构（Diverging / Fork）

A ← M → B

当 被观测时， 与 条件独立。

直观理解： 是 和 的共同原因（common cause），一旦控制 ， 与 之间的伪相关（spurious correlation）消失。这正是”解释规避”（Explaining Away）现象的数学表述。

规则 3：收敛结构（Converging / Collider）

A → M ← B

收敛结构 （Collider）中：

  • 未观测 及其后代时：路径被阻断，（边缘独立）；
  • 一旦观测 或其任意后代：路径被打通，独立性消失， 与 变得相关。

解释规避（Explaining Away）实例：假设 = 草地湿， = 洒水车没来， = 下雨了。若我们观察到 （下雨），（草地湿）就被”解释”了，从而降低了对 （洒水车没来）的信念—— 与 在 条件下变得负相关。

D-分离的完整判定算法：

  1. 将需要判断条件独立性的两组节点集合记为 和 ，条件集为 。
  2. 在图上标记所有 中的节点为”已观测”（blocked/cut）。
  3. 在所有从 中任意节点到 中任意节点的迹上，检查是否存在有效阻断：
    • 对于顺序/发散结构：若中间节点被观测，则阻断。
    • 对于收敛结构：若中间节点及其所有后代均未被观测，则阻断；否则不阻断。
  4. 若所有迹均被阻断，则 （D-分离成立）。

定理（D-分离与条件独立的对应关系）：

给定一个贝叶斯网络 ，全局马尔可夫性（Global Markov Property）表明：若集合 与 在 中被 D-分离，则在实际的概率分布 中， 成立。

逆命题为忠实性（Faithfulness）：若 中 成立，则在 中 与 被 D-分离。

1.2 马尔可夫随机场（Markov Random Field / Undirected Graphical Model）

1.2.1 势函数与团分解

马尔可夫随机场（MRF） 使用无向图编码变量之间的对称依赖关系，适用于不存在明确因果方向的问题（如图像、蛋白质结构、社交网络）。

关键区别：无向图中不存在”父节点-子节点”的非对称关系，因此无法直接写出条件概率的贝叶斯链式分解。

团（Clique）定义：在无向图 中，节点的集合 被称为一个团，当且仅当 中的任意两个节点之间都有边相连（即 为一完全子图）。若无法再向其中加入节点而不破坏团性质，则称之为最大团（maximal clique）。

MRF 的联合分布分解：设 为图 的所有最大团集合， 为定义在最大团 上的势函数（potential function，非概率意义上的正函数），则联合分布可以分解为：

其中归一化常数：

称为配分函数（partition function）。

物理直觉：势函数可以理解为”局部配置的能量”的指数化（）。 的作用是确保概率归一化，这在统计物理中来自玻尔兹曼分布。

1.2.2 Hammersley-Clifford 定理（核心定理）

定理陈述：

设 为定义在无向图 上的随机向量。（严格为正）对所有状态成立的条件下，以下三个命题等价：

  1. 满足局部马尔可夫性（Local Markov Property）：任意节点 ，给定其邻居 ，有 ；
  2. 满足成对马尔可夫性（Pairwise Markov Property）：任意无直接边的节点对 ，给定所有其他节点， 与 条件独立；
  3. 可以表示为最大团势函数的乘积形式：，其中 为最大团集合。

证明思路（概述）：

方向 (3) (1)：这是直接的——若联合分布可以写成最大团势函数的乘积，则任意无直接边的节点 不可能同时出现在同一个最大团中（否则它们之间必有边）。因此影响 和 的唯一途径必须经过其他节点，条件独立性由乘积结构直接给出。

方向 (1) (3)（核心证明）：

从 MRF 的正性假设 出发：

  1. 引入势函数的构造：对于任意最大团 ，定义

    其中 表示在子集 上的边际分布。这个构造源自容斥原理（Inclusion-Exclusion）。

  2. 验证该势函数的乘积确实等于 ：通过归纳最大团的覆盖顺序，可以证明

    其中 确保归一化。

  3. 正性假设的关键作用：若 对某些状态成立，则无法定义对数势函数，定理失效。这正是为什么 Hammersley-Clifford 定理要求 为严格正（strictly positive）的原因。

推论（条件随机场 / CRF）：当 MRF 应用于序列标注等结构化预测问题时，每个位置的标签作为观测变量的条件分布，即 。这直接催生了条件随机场（Conditional Random Field），是序列标注的标准方法。

二、推断算法（Inference）的数学本质

2.1 精确推断

2.1.1 变量消去法（Variable Elimination）

变量消去法是精确推断的基石，其核心思想是边缘化求解时，按适当顺序将变量逐一积分消去，避免直接计算联合分布的指数级复杂度。

目标：计算边缘概率 ，其中 表示除 以外的所有变量。

基本步骤：

设变量集合 ，因子分解后的因子集合 。

  1. 选择消除顺序（elimination order）；
  2. 对于每个待消除的变量 ，收集所有包含 的因子，构造message： 其中 表示当前尚未消除的变量集合（不含 ）；
  3. 将该 message 作为一个新的因子加入因子集，移除所有已用因子；
  4. 重复直到仅剩目标变量。

复杂度分析：若图结构中每个因子涉及的变量最多为 ，则时间复杂度为 ，其中 为每个变量的状态数。树状结构可达到 。

示例：对于链状 CRF：

计算 时，从 开始逐步消除：

2.1.2 信念传播算法（Belief Propagation / Sum-Product Algorithm）

核心问题：变量消去法虽然正确，但无法重用中间计算（每次查询都需要重新消除）。当需要计算多个边缘分布时，效率极低。

信念传播 通过消息传递（message passing）框架解决这个问题——它将变量消去的过程转化为图上邻居之间的信息交互，使得中间结果可以被复用。

消息传递公式推导：

考虑节点 向邻居 传递的消息。设 为从邻居 传递给 的消息（关于 的函数），则节点 汇总所有来自除 以外邻居的消息，生成向 的消息：

其中 为节点 的所有邻居集合。

解释：

  • ：节点 的势函数（如果 是最大团的一部分）
  • ：边 的势函数
  • ：从所有其他邻居收到的消息的乘积

边际概率的估计（Belief）：当消息传递收敛后，节点 的边际概率估计为：

对于边 的边际：

树状图上的收敛性证明：

定理（树状图信念传播的精确性）：若图结构为树（无环），则信念传播算法在消息传递有限次（最多 轮）后收敛，且得到的边际概率 精确等于 真实的边缘分布 。

证明思路：

  1. 在树上，存在唯一的从任意节点到任意其他节点的路径；
  2. 变量消除的顺序等价于从叶子到根的消息传递；
  3. 由于无环，不存在消息的”冲突”或”循环依赖”；
  4. 每条消息的计算恰好对应一次完整的变量消除；
  5. 收敛性由消息更新规则的有限步收敛性保证（树深度有限）。

注：对于带环图（loopy graph），标准 Sum-Product 信念传播直接迭代称为循环信念传播（Loopy Belief Propagation, LBP）——它本质上是 BP 在环图上的直接应用，无收敛与精确性保证。工程上常有效但缺乏理论保证。

2.2 近似推断

精确推断在大多数实际场景下不可行——联合状态空间随变量数指数增长（）。近似推断方法分为随机方法（蒙特卡洛采样）和确定性方法（变分推断）。以下重点讲解变分推断。

2.2.1 变分推断的核心框架

问题设定：给定观测数据 和隐变量 ，目标是计算后验分布 。然而配分函数 的计算通常 intractable（指数复杂度）。

变分推断的核心思想：将推断问题转化为优化问题——用一个简单的参数化分布 去近似真实后验 ，通过优化两者之间的差距来获得好的近似。

2.2.2 证据下界（Evidence Lower Bound, ELBO）的数学推导

第一步：引入辅助分布与 KL 散度

对于任意辅助分布 （又称变分分布），利用概率论的基本恒等式（全概率公式 + 对数分解）：

对 取期望：

第二项恰好是 KL 散度 的定义：

第二步：重排得到 ELBO

由于 KL 散度非负，故：

这就是 证据下界（ELBO）——它给出了 的下界。

第三步：ELBO 的等价形式

ELBO 还有两种等价的表达，便于不同角度的理解：

  1. 能量-熵形式：

    其中 为 的熵。第一项可以理解为”重构似然”（让 集中于高联合概率区域），第二项鼓励 保持高熵（避免过度自信）。

  2. 交叉熵形式：

    其中 为隐变量的先验分布。这揭示了 VAE 中”重构项 + 正则化项”的理论基础。

第三步：变分推断的优化目标

由于 ，且 为常数（不依赖 ），最大化 ELBO 等价于最小化 ，即让变分分布 尽可能接近真实后验 。

Jensen 不等式的视角：。这里用到的是 的凹性（即 Jensen 不等式 对凹函数 成立）。ELBO 正是从 Jensen 不等式推导出的下界。

三、学习理论（Learning）

3.1 参数学习：MLE vs MAP

给定数据集 ，假设数据由参数 控制的分布生成。

极大似然估计（MLE）：

MLE 的核心思想是：寻找使观测数据出现概率最大的参数值。

最大后验估计（MAP）：

MAP 引入参数先验 ，本质上是对 MLE 施加正则化——当数据稀疏时，先验防止模型过度自信。

贝叶斯估计 vs 点估计：MLE 和 MAP 都是点估计（point estimation）。贝叶斯方法保留参数的后验分布 ，对参数进行积分（边际化），但这通常计算代价更高。

3.2 EM 算法（Expectation-Maximization）

3.2.1 问题的提出：隐变量模型

当数据中包含隐变量（latent variable） 时，直接 MLE 不可行：

问题在于： 无法拆分为可求和的项（对数无法穿过求和符号）。

3.2.2 Jensen 不等式推导 EM 迭代

E 步（Expectation）：固定当前参数 ，计算隐变量的后验分布 ，并在此基础上计算当前 ELBO：

其中 。

关键洞察：当 时，ELBO 取到紧（tight）值——此时 ，ELBO 等于真实对数似然 。

M 步（Maximization）：固定 （即固定 E 步的结果），更新参数 ：

即最大化完整数据对数似然在隐变量后验分布下的期望。

3.2.3 单调收敛性的严格证明

定理（EM 算法的单调性）：在每一步迭代中，EM 算法保证 。

证明：

从 ELBO 的定义出发，对任意 和 ：

固定 ，选择 ，则 ，故：

M 步最大化 ，故 。

E 步更新 ，令 ，此时 ，故：

综合两步：

得证。

EM 的几何直觉：EM 算法在参数空间和变分分布空间之间交替爬山。每次 E 步找到当前参数下最紧的 ELBO 下界（提升对数似然到相同值），每次 M 步在该下界上寻找新的峰值（提升参数），如此循环直到收敛。

四、总结与直觉

4.1 图结构与概率统计的统一

概率图模型的核心贡献在于建立了图论与概率论之间的精确对应：

图论概念概率论解释
节点随机变量
边（无向）变量间的对称依赖关系
边（有向）因果 / 条件依赖方向
路径阻断（D-分离）条件独立性的判定准则
最大团联合势函数的作用范围
因子分解联合分布的乘法结构

4.2 表示、推断与学习的统一框架

表示(Representation)          推断(Inference)           学习(Learning)
      │                            │                          │
      ▼                            ▼                          ▼
  图结构编码独立性             后验概率计算               参数估计（MLE/MAP）
  因子分解简化计算            ELBO / 消息传递            EM算法迭代优化
  • 表示解决”如何用图编码先验知识”的问题；
  • 推断解决”给定观测数据，如何计算目标概率”的问题；
  • 学习解决”如何从数据中学习图结构和参数”的问题。

4.3 与生成式模型的深层联系

理解 PGM 对掌握现代生成式模型至关重要：

  • VAE 是 EM 算法 + 变分推断的典型应用；
  • 扩散模型 的前向过程（加噪）和反向过程（去噪）本质上是隐变量层级上的推断；
  • Flow Models 利用可逆变换和变量替换公式（change of variables）实现精确的对数似然计算；
  • 能量模型（EBM） 本质上是 MRF 的无归一化形式；
  • GPT/Transformer 的注意力机制可以理解为一种软性的消息传递——这正是 Belief Propagation 的连续推广。

一句话总结：概率图模型提供了一套统一语言——它让我们能够精确地回答”什么信息需要被传递”、“信息如何被归约”以及”我们如何从数据中学习这些传递规则”。这套语言渗透在现代深度生成模型的每一个角落。

Graph View