207 lines
13 KiB
Markdown
207 lines
13 KiB
Markdown
---
|
||
title: 17 第十七章 无向图模型
|
||
draft: false
|
||
tags:
|
||
- ESL
|
||
---
|
||
### [逻辑架构图]
|
||
|
||
- **基础协议层（图结构与马尔科夫性）**：定义了变量间条件独立性的拓扑语义，等同于系统设计中的“依赖解耦协议”。
|
||
|
||
- **连续数据流（高斯图模型 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 个变量，两两组合是爆炸性的。图结构告诉我们哪些联系是本质的：
|
||
|
||
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 \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）或锁机制。这直接铺平了大规模深度学习模型落地的物理基础。 }
|
||
|
||
---
|
||
|
||
### [边界知识联动]
|
||
|
||
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$ 在逻辑图理上是一模一样的。 |