13 KiB
title, draft, tags
| title | draft | tags | |
|---|---|---|---|
| 17 第十七章 无向图模型 | false |
|
[逻辑架构图]
-
基础协议层（图结构与马尔科夫性）：定义了变量间条件独立性的拓扑语义，等同于系统设计中的“依赖解耦协议”。
-
连续数据流（高斯图模型 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}} \phi_C(x_C)其中
\phi_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 个变量，两两组合是爆炸性的。图结构告诉我们哪些联系是本质的：
-
识别直接原因（去噪）：剔除虚假相关。例如给定“气温”，则“冰激凌销量”与“溺水事故”条件独立。
-
极大地降低计算复杂度（推断优化）：20 个二值变量本需要
2^{20}的巨大状态表。利用稀疏图的因子分解，只需处理局部表格。它是现代 AI 能够实时运行的基础。 -
实现自动推理：定义信息流动的路径。观测值沿着边传播，自动更新其他节点的概率。
-
揭示系统拓扑特性：例如寻找基因调控网络中的枢纽（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 \neq 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 \|\Theta\|_1 \right) -
计算机制：采用逐列更新（坐标下降法），固定其他列，用 Lasso 回归解法更新当前列。本质上是用其他所有变量作为自变量，去回归当前变量。
-
独立性哲学：没有边
\neq彻底没关系。没有边=没有直连（影响必须通过中转站传递）。
{ [深度扩充：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 求解 $S v = \lambda v \implies \frac{1}{n} X^T X v = \lambda v$。当我们引入非线性映射
\phi(x)到高维空间时，通过核技巧K_{ij} = \langle \phi(x_i), \phi(x_j) \rangle隐式计算。如果你有协方差，说明关注线性相关；如果使用核方法，说明怀疑存在非线性的深层相关。
三、 离散变量的无向图：马尔科夫随机场 (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 \neq i} w_{ij} s_j + \theta_i \right)
-
梯度求导准则：
\frac{\partial \log L}{\partial w_{ij}} = \langle s_i s_j \rangle_{data} - \langle s_i s_j \rangle_{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）或锁机制。这直接铺平了大规模深度学习模型落地的物理基础。 }
[边界知识联动]
-
OS 调度机制与能量函数：MRF 中通过博弈寻找最低能量状态（最高概率），与操作系统中通过“优先级反转（Priority Inheritance）”和“动态时间片分配”算法让 CPU 调度系统达到最优吞吐量（全局能量最低点）有着极强的同构性。
-
网络路由协议（OSPF）与图推断：在已知图结构中计算边际概率的信念传播（Belief Propagation）算法，其底层信息交互逻辑与计算机网络中基于链路状态的 OSPF 路由协议几乎完全一致——节点不断向邻居广播自己的“信念”，直到全网状态收敛。
-
编译器常量折叠与条件独立：在静态分析中，如果编译器确定变量 A 和 B 在中间路径上被某常量赋值（屏障节点 C）所截断，编译器就会独立优化 A 和 B 的后续指令路线。这与无向图中的马尔科夫屏障
X_A \perp X_B \mid X_C在逻辑图理上是一模一样的。