Huajishe Notes

17 第十七章 无向图模型

17 min read

[逻辑架构图]

  • 基础协议层（图结构与马尔科夫性）：定义了变量间条件独立性的拓扑语义，等同于系统设计中的“依赖解耦协议”。

  • 连续数据流（高斯图模型 GGM）：处理连续变量，核心任务是将表象的协方差矩阵 转化为本质的精度矩阵 （稀疏化反演），以识别直接的控制链路。

  • 离散状态机（马尔科夫随机场 MRF）：处理组合状态，通过势函数和吉布斯分布评估系统“能量”，但陷入了配分函数 带来的 计算泥潭。

  • 工程化重构（BM 与 RBM）：为了解决离散图模型的算力瓶颈，模型演化出全连接的波尔兹曼机（试图逼近热平衡）和切断层内连接的受限波尔兹曼机（通过拓扑阉割换取极致的硬件并行亲和度）。

[深度整理正文]

一、 概率图模型的基础：三个“马尔科夫”与图的数学性质

这三个概念虽然都带有“马尔科夫”的名字，但它们在概率图模型（PGM）和强化学习中扮演的角色各不相同。我们可以从基础的图结构演进到动态决策过程。

1. 概念辨析：无向图、马尔科夫链与 MDP

  • 无向图模型 (Undirected Graphical Model / MRF)：关注变量间的空间相关性。没有因果或先后之分。其联合概率分布是通过最大团 (Max-cliques) 来定义的：

    其中 是非负势函数， 是配分函数（归一化因子）。

  • 马尔科夫链 (Markov Chain)：描述状态序列的随机模型。核心是无记忆性 (Memorylessness)：

  • 马尔科夫决策过程 (MDP)：引入智能体的决策。定义为五元组 ，在动态环境下寻找最优策略 ，使得长期累积奖励的期望值最大。

概念核心关注点是否有方向是否有动作/奖励
无向图 (MRF)变量间的空间相关性无否
马尔科夫链状态随时间演变的规律有否
MDP在动态环境下的最优行为选择有是

2. 马尔科夫图 (Markov Graphs) 及其性质

在无向图 中，马尔科夫性定义了变量间的条件独立性：

  • 全局马尔科夫性：如果集合 分隔了 和 ，则给定 时，。

  • 局部马尔科夫性：给定一个节点 的所有邻居 ，该节点独立于图中所有其他节点。

  • 成对马尔科夫性：任意两个不相邻的节点 ，给定其余所有节点时独立。

  • Hammersley-Clifford 定理：一个正概率分布 满足上述马尔科夫性质，当且仅当它可以被分解为图中最大团上的势函数乘积。

{ [深度扩充：计算解耦与内存局部性]

从 CSAPP 的视角来看，马尔科夫性本质上是数据依赖的“隔离屏障”。在多线程并发或分布式计算中， 意味着一旦节点 的状态被固化（缓存在 L1 Cache 或被 Read-Lock），对 和 的计算可以毫无数据竞争（Data Race）地在不同的 CPU 核心上并行执行。H-C 定理则为大规模联合概率的计算提供了理论基础：把全局的 复杂度，拆解为多个最大团内部的局部计算。这使得我们可以将大图切分成适配 CPU Cache Line 尺寸的子块（Chunking），极大提升了指令吞吐量。 }

3. 图结构的实际意义：复杂关系的化简器

如果系统里有 100 个变量，两两组合是爆炸性的。图结构告诉我们哪些联系是本质的：

  1. 识别直接原因（去噪）：剔除虚假相关。例如给定“气温”，则“冰激凌销量”与“溺水事故”条件独立。

  2. 极大地降低计算复杂度（推断优化）：20 个二值变量本需要 的巨大状态表。利用稀疏图的因子分解，只需处理局部表格。它是现代 AI 能够实时运行的基础。

  3. 实现自动推理：定义信息流动的路径。观测值沿着边传播，自动更新其他节点的概率。

  4. 揭示系统拓扑特性：例如寻找基因调控网络中的枢纽（Hub），或构建推荐系统中物品兴趣节点的网状结构。

二、 连续变量的无向图模型：高斯图模型 (GGM) 与核方法

1. 核心定义与公式推导：从 到

假设变量服从多元正态分布 ，其概率密度函数为：

设均值 ，将指数项内部展开（这里精度矩阵 ）：

结论：如果 ，概率密度函数中 和 之间没有乘积项，即 。

协方差 是表象（包含了因为第三方中转产生的虚假相关），精度矩阵 是本质（剔除虚假关联后的直接相互作用）。

2. 图结构与参数估计：Graphical Lasso 算法

给定 个样本的经验协方差矩阵 。

  • 目标函数：如果特征数 ， 不可逆。为了寻找稀疏的图结构，GLasso 在极大似然中引入 正则化，强行将微弱的偏相关系数压缩为 0：

  • 计算机制：采用逐列更新（坐标下降法），固定其他列，用 Lasso 回归解法更新当前列。本质上是用其他所有变量作为自变量，去回归当前变量。

  • 独立性哲学：没有边 彻底没关系。没有边 没有直连（影响必须通过中转站传递）。

{ [深度扩充：ESL 统计视角与数值线性代数]

在《The Elements of Statistical Learning》中， 惩罚项由于其梯度的非平滑性（在零点不可导），能够产生绝对的稀疏解（Sparse Solutions），而 只能产生小数值但非零的解。

从系统底层来看，GLasso 的输出 是一个极其稀疏的矩阵。这意味着在后续的图推断系统中，我们完全不需要分配 的连续内存。我们可以直接使用 CSR（Compressed Sparse Row）数据结构。由于消除了大量的零元素乘法，稀疏矩阵向量乘（SpMV）可以完美契合现代 CPU 的 AVX 指令集和 GPU 的 Tensor Cores，将内存带宽利用率从不到 10% 提升至理论上限。 }

3. 对偶性延伸：协方差矩阵与核矩阵 (Kernel Matrix)

协方差矩阵 和核矩阵 在数学上都是半正定矩阵。

  • 协方差矩阵 （大小 ）：关注特征空间的耦合。

  • 核矩阵 （大小 ）：关注样本空间的接近。

    传统 PCA 求解 。当我们引入非线性映射 到高维空间时，通过核技巧 隐式计算。如果你有协方差，说明关注线性相关；如果使用核方法，说明怀疑存在非线性的深层相关。

三、 离散变量的无向图：马尔科夫随机场 (MRF)

离散图模型不像连续变量能通过矩阵求逆解决，它涉及组合数学中的海量求和。

1. 吉布斯分布与伊辛模型 (Ising Model)

离散无向图的联合概率分布定义为：

其中 是势函数， 是能量。以二值变量的伊辛模型为例，总能量函数为：

有边

参数 的正负和大小，直接决定了节点间是“同向吸引”还是“异向吸引”。系统概率最高的状态，就是所有人相互妥协后总能量最低的状态。

2. 配分函数 的计算灾难

如果 个变量各有 个取值，求和项有 个（典型的 NP-hard 问题）。在参数学习阶段，最大似然估计的梯度里包含对 的导数，意味着每次迭代都要做一次全局推断。

{ [深度扩充：状态爆炸与 MCMC 寻址抖动]

从 CSAPP 视角看， 的计算不仅是 CPU 算力不足的问题，更是灾难性的内存访问模式问题。 的状态空间在物理内存中呈现出离散的、毫无规律可言的分布。当 MCMC（如 Gibbs Sampling）试图在这些状态中进行转移采样时，每一次采样几乎都会导致 Cache Miss 和深度的 TLB Miss（页表未命中）。因为下一状态的地址是随机计算出来的，现代 CPU 的硬件预取器（Hardware Prefetcher）彻底失效，流水线被迫停顿等待内存响应。这也是为什么离散图模型的原生精确解法在工程上几乎被判了死刑。 }

四、 工程化突围：普通波尔兹曼机 (BM) 与受限波尔兹曼机 (RBM)

为了在真实的神经网络中应用离散图模型，必须解决复杂的环路推断问题。

1. 普通波尔兹曼机 (BM)：纯粹但暴力的全连接系统

BM 没有任何结构限制，变量状态 ，能量函数为：

其联合概率为 。

由于存在层内连接，单个节点的激活概率深度耦合于所有其他节点：

  • 梯度求导准则：

    梯度由正相（数据观测共现）和负相（模型幻想共现）决定。计算模型自发共现需要将系统模拟至热平衡，计算极其缓慢。

2. 受限玻尔兹曼机 (RBM)：阉割拓扑换取效率

RBM 强制将结构变为二分图（Bipartite Graph）：可见层 和隐藏层 之间全连接，但层内绝对无连接。

能量函数变为：

  • 致命优势：条件独立性：当固定可见层 时，隐藏层各节点互不干扰，概率可以分解：。

    推导出的激活概率变成了极其友好的前向计算：

  • CD算法 (Contrastive Divergence)：利用一轮正向步（ 采样）和一轮反向重建步（ 采样）代替漫长的热平衡，迅速更新权重。

{ [深度扩充：数据依赖图的剪枝与 SIMD 向量化并行]

BM 为什么慢？因为环形的数据依赖图（Data Dependency Graph）引发了经典的 Read-After-Write (RAW) 数据冒险（Data Hazard）。在计算节点 时必须等待节点 的结果，导致 CPU/GPU 只能串行化执行指令。

Hinton 发明 RBM 的伟大之处，不仅在数学上，更在计算机体系结构上：“层内无连接”在硬件层面上等价于“彻底消除了同一循环层内的 RAW 冒险”。计算 变成了一个纯粹的密集矩阵向量乘法操作。成千上万个 的计算可以完美映射到 GPU 的数千个流处理器（CUDA Cores）上，利用 SIMD（单指令多数据流）并行完成，期间无需任何线程间同步（Thread Barrier）或锁机制。这直接铺平了大规模深度学习模型落地的物理基础。 }

[边界知识联动]

  1. OS 调度机制与能量函数：MRF 中通过博弈寻找最低能量状态（最高概率），与操作系统中通过“优先级反转（Priority Inheritance）”和“动态时间片分配”算法让 CPU 调度系统达到最优吞吐量（全局能量最低点）有着极强的同构性。

  2. 网络路由协议（OSPF）与图推断：在已知图结构中计算边际概率的信念传播（Belief Propagation）算法，其底层信息交互逻辑与计算机网络中基于链路状态的 OSPF 路由协议几乎完全一致——节点不断向邻居广播自己的“信念”，直到全网状态收敛。

  3. 编译器常量折叠与条件独立：在静态分析中，如果编译器确定变量 A 和 B 在中间路径上被某常量赋值（屏障节点 C）所截断，编译器就会独立优化 A 和 B 的后续指令路线。这与无向图中的马尔科夫屏障 在逻辑图理上是一模一样的。

Graph View