17 第十七章 无向图模型

[逻辑架构图]

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

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

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

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

---

[深度整理正文]

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

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

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

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

  $P(x)=\frac{1}{Z}{\prod }_{C\in \mathcal{C}}{\varphi }_C(x_C)$

  其中 ${\varphi }_C$ 是非负势函数，$Z$ 是配分函数（归一化因子）。

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

  $P(X_{t+1}|X_t,X_{t-1},\dots ,X_0)=P(X_{t+1}|X_t)$

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

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

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

在无向图 $G=(V,E)$ 中，马尔科夫性定义了变量间的条件独立性：

• 全局马尔科夫性：如果集合 $C$ 分隔了 $A$ 和 $B$，则给定 $X_C$ 时，$X_A\perp X_B\mid X_C$。

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

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

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

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

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

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

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

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

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

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

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

---

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

1. 核心定义与公式推导：从 $\Sigma$ 到 ${\Sigma }^{-1}$

假设变量服从多元正态分布 $\mathbf{x}\sim N(\mu ,\Sigma )$，其概率密度函数为：

$f(x)=\frac{1}{(2\pi {)}^{p/2}|\Sigma {|}^{1/2}}\exp \left(-\frac{1}{2}(x-\mu {)}^T{\Sigma }^{-1}(x-\mu )\right)$

设均值 $\mu =0$，将指数项内部展开（这里精度矩阵 $\Theta ={\Sigma }^{-1}$）：

$-\frac{1}{2}{x}^T\Theta x=-\frac{1}{2}\left({\sum }_i{\theta }_{ii}{x}_i^2+{\sum }_{i\ne j}{\theta }_{ij}{x}_i{x}_j\right)$

结论：如果 ${\theta }_{ij}=0$，概率密度函数中 $x_i$ 和 $x_j$ 之间没有乘积项，即 $X_i\perp X_j\mid X_{\setminus \{i,j\}}$。

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

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

给定 $n$ 个样本的经验协方差矩阵 $S=\frac{1}{n-1}{X}^{T}X$。

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

  $\hat{\Theta }=\arg {\max }_{\Theta \succ 0}\left(\log \det \Theta -\text{tr}(S\Theta )-\lambda \Vert \Theta {\Vert }_1\right)$

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

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

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

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

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

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

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

• 协方差矩阵 $S=\frac{1}{n}{X}^{T}X$（大小 $p\times p$）：关注特征空间的耦合。

• 核矩阵 $K=X{X}^T$（大小 $n\times n$）：关注样本空间的接近。

  传统 PCA 求解 $Sv=\lambda v⟹\frac{1}{n}{X}^{T}Xv=\lambda v$。当我们引入非线性映射 $\varphi (x)$ 到高维空间时，通过核技巧 $K_{ij}=⟨\varphi (x_i),\varphi (x_j)⟩$ 隐式计算。如果你有协方差，说明关注线性相关；如果使用核方法，说明怀疑存在非线性的深层相关。

---

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

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

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

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

$P(X_1,X_2,\dots ,X_p)=\frac{1}{Z}{\prod }_{C\in \mathcal{C}}{\psi }_C(X_C)=\frac{1}{Z}\exp \left(-{\sum }_{C\in \mathcal{C}}{E}_C(X_C)\right)$

其中 ${\psi }_C$ 是势函数，$E_C$ 是能量。以二值变量的伊辛模型为例，总能量函数为：

$E(X)=-{\sum }_{i,j\text{ 有边}}{w}_{ij}{X}_i{X}_j-{\sum }_i{h}_i{X}_i$

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

2. 配分函数 $Z$ 的计算灾难

$Z={\sum }_X\exp (-E(X))$

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

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

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

---

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

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

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

BM 没有任何结构限制，变量状态 $s_i\in \{0,1\}$，能量函数为：

$E(s)=-{\sum }_{i<j}{w}_{ij}{s}_i{s}_j-{\sum }_i{\theta }_i{s}_i$

其联合概率为 $P(s)=\frac{e^{-E(s)}}{Z}$。

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

$P(s_i=1|s_{-i})=\sigma \left({\sum }_{j\ne i}{w}_{ij}{s}_j+{\theta }_i\right)$

• 梯度求导准则：$\frac{\partial \log L}{\partial w_{ij}}=⟨s_i{s}_j{⟩}_{data}-⟨s_i{s}_j{⟩}_{model}$

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

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

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

能量函数变为：

$E(v,h)=-{\sum }_i{a}_i{v}_i-{\sum }_j{b}_j{h}_j-{\sum }_{i,j}{v}_i{w}_{ij}{h}_j$

• 致命优势：条件独立性：当固定可见层 $v$ 时，隐藏层各节点互不干扰，概率可以分解：$P(h|v)={\prod }_{j}P(h_j|v)$。

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

  $P(h_j=1|v)=\sigma \left(b_j+{\sum }_i{v}_i{w}_{ij}\right)$

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

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

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

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

---

[边界知识联动]

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

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

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