Notes/【笔记origin】ESL/17 origin.md

第十七章

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

---

1. 无向图模型 (Undirected Graphical Model)

无向图模型又被称为 马尔科夫随机场 (Markov Random Field, MRF)。与贝叶斯网络（有向图）不同，它使用无向边来表示变量之间的相关性。

核心特性

• 对称相关性：如果变量 A 和 B 之间有边，表示它们互相关联，没有因果或先后之分（例如：图像中相邻像素的颜色倾向于相似）。

• 因子分解：无向图的联合概率分布是通过最大团 (Max-cliques) 来定义的。

  P(x) = \frac{1}{Z} \prod_{C \in \mathcal{C}} \phi_C(x_C)

  • $\phi_C$：势函数（Potential Function），通常是非负的。

  • $Z$：配分函数（Partition Function），用于归一化，确保概率之和为 1（计算 Z 通常是无向图模型中最难的部分）。

马尔科夫性质

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

• 步离马尔科夫性 (Separation)：如果节点集 A 和 B 被节点集 C 隔开，那么在给定 C 的情况下，A 和 B 独立。

---

2. 马尔科夫链 (Markov Chain)

你提到的“马尔科夫图”在数学上通常指代马尔科夫链的状态转移图。它是描述状态序列的随机模型。

定义

马尔科夫链的核心是无记忆性 (Memorylessness)：下一时刻的状态仅取决于当前时刻，而与过去无关。

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

关键要素

• 状态空间：所有可能存在状态的集合。

• 转移概率矩阵 $P$：矩阵中的元素 P_{ij} 表示从状态 i 转移到状态 j 的概率。

• 平稳分布：如果马尔科夫链运行足够长的时间，某些条件下状态概率会趋于稳定。

---

3. 马尔科夫决策过程 (Markov Decision Process, MDP)

这是“马尔科夫链”在强化学习领域的扩展。它不再只是被动地观察状态演变，而是引入了智能体的决策。

五元组 (S, A, P, R, \gamma)

1. S (States)：环境状态的集合。

2. A (Actions)：智能体可以采取的动作集合。

3. P (Transition Probability)：状态转移模型 $P(s' | s, a)$，即在状态 s 采取动作 a 后，转移到 s' 的概率。

4. R (Reward)：奖励函数 $R(s, a)$，采取某个动作后获得的即时反馈。

5. \gamma (Discount Factor)：折扣因子（0 到 1 之间），平衡当前利益与长远利益。

目标：寻找最优策略 \pi^*

在马尔科夫链中，状态转移是自动的；在 MDP 中，我们需要找到一个策略 $\pi(a|s)$，使得长期累积奖励的期望值最大。

---

三者的直观对比

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

总结

• 如果你在处理图像分割或空间建模，你会用到无向图模型。

• 如果你在分析股市波动或文本生成的统计规律，你会用到马尔科夫链。

• 如果你在训练AI 玩德州扑克或控制机器人，你会用到马尔科夫决策过程。

---

在理解了基础概念后，我们深入探讨无向图模型的数学性质、连续变量的处理方式，以及在实际应用中如何“学习”出一个图模型。

---

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

在无向图中，马尔科夫性定义了变量间的条件独立性。假设 G=(V, E) 是一个无向图，对于节点集合 $A, B, C \subset V$：

• 全局马尔科夫性 (Global Markov Property)：如果集合 C 分隔了 A 和 $B$（即去掉 C 后，A, B 之间没有路径），则给定 X_C 时，$X_A \perp X_B | X_C$。

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

• 成对马尔科夫性 (Pairwise Markov Property)：对于图中任意两个不相邻的节点 $u, v$，给定其余所有节点时，u 和 v 独立。

Hammersley-Clifford 定理：

这是无向图的核心定理。它指出，一个正概率分布 P(x) > 0 满足上述马尔科夫性质，当且仅当它可以被分解为图中最大团 (Max-cliques) 上的势函数乘积。

---

2. 连续变量的无向图模型：高斯图模型 (GGM)

对于连续变量，最常用的模型是高斯马尔科夫随机场 (Gaussian Markov Random Field)，也叫 高斯图模型 (GGM)。

假设变量 $\mathbf{x} \sim N(\mu, \Sigma)$。在无向图中，我们关心的不是协方差矩阵 $\Sigma$，而是它的逆矩阵——精度矩阵 (Precision Matrix) $\Theta = \Sigma^{-1}$。

核心性质

在 GGM 中，精度矩阵 \Theta 的元素直接反映了图的结构：

• 如果 $\Theta_{ij} = 0$，则变量 X_i 和 X_j 在给定其他所有变量的情况下是条件独立的。

• 这意味着图中节点 i 和 j 之间没有边。

• 因此，学习连续变量的图结构等同于寻找精度矩阵中的零元素。

---

3. 图结构已知时的参数估计

如果图的结构（哪些边存在）已经确定，我们需要估计势函数或参数（如 GGM 中的 $\Theta$）。

离散情况 (Log-Linear Models)

通常使用 迭代比例拟合 (Iterative Proportional Fitting, IPF) 或梯度上升法（如 L-BFGS）来最大化似然函数。由于存在配分函数 $Z$，计算梯度时通常需要进行推断（Inference），如使用 MCMC 采样。

连续情况 (GGM)

给定样本协方差矩阵 $S$，目标是最大化对数似然函数：

\ell(\Theta) = \log \det \Theta - \text{tr}(S\Theta)

在已知边结构（即约束某些 $\Theta_{ij} = 0$）的情况下，这变成了一个有约束的凸优化问题。

---

4. 图结构的估计 (Structure Learning)

当连边情况未知时，我们需要从数据中学习图的拓扑结构。

离散变量：约束法与评分法

• 基于约束 (Constraint-based)：对每一对节点进行条件独立性检验（如 \chi^2 检验），根据结果删减边。

• 基于评分 (Score-based)：定义一个衡量图好坏的分数（如 BIC, AIC），在图空间中进行启发式搜索。

连续变量：稀疏学习 (Graphical Lasso)

在变量维度很高时（例如基因数据），我们假设图是稀疏的（大多数变量间没有直接联系）。

Graphical Lasso (GLasso) 是目前最主流的方法，它在似然函数中加入 L_1 正则化项来强制使 \Theta 中的许多元素变为 0：

\hat{\Theta} = \arg\max_{\Theta \succ 0} \left( \log \det \Theta - \text{tr}(S\Theta) - \lambda \|\Theta\|_1 \right)

• \lambda 越大，生成的图越稀疏。

• 这不仅估计了参数，还直接通过非零元素的位置确定了图的结构。

启发式方法：PC 算法

PC 算法（以其开发者 Spirtes 和 Glymour 命名）从完全图开始，通过逐级增加条件集合的阶数进行独立性检验，不断删减边。它对于处理大规模稀疏图非常高效。

---

总结

• 马尔科夫图通过图结构编码条件独立性。

• 连续变量主要看精度矩阵 $\Sigma^{-1}$，零元素即代表无边。

• 参数估计在已知结构下通过极大似然完成，但要对抗配分函数 Z 的计算开销。

• 结构估计在现代高维数据处理中，通常依赖于 GLasso 等稀疏正则化技术来实现“自动筛选”边。

---

这是一个非常务实的问题。在算法和公式背后，图结构本质上是“复杂关系的化简器”。如果一个系统里有 100 个变量，它们两两相关的可能组合是爆炸性的，而图结构告诉我们：“哪些联系是本质的，哪些只是表象。”

具体来说，图结构在实际应用中有以下四个核心作用：

---

1. 识别“直接原因”与“间接影响”（去噪）

这是图结构最强大的地方。在统计学中，相关不代表因果。

• 现象： 统计发现“冰激凌销量”和“溺水事故数”高度相关。

• 图结构的作用： 如果引入“气温”这个节点，你会发现给定“气温”时，前两者是条件独立的。

• 用途： 图结构能帮你剔除虚假相关。在金融分析或疾病诊断中，它能帮你找到引起问题的直接源头，而不是被一堆由于连锁反应产生的表面数据误导。

2. 极大地降低计算复杂度（推断优化）

假设你有 20 个二值变量（0 或 1）：

• 如果没有图结构： 你需要存储一个包含 $2^{20}$（约 100 万）个状态的巨大概率表。这在计算上是不可能的。

• 有了图结构： 如果图很稀疏（每个节点只连 3-4 个邻居），利用因子分解，你只需要处理几个小的局部表格。

• 用途： 它是通信解码（如 5G 信号纠错）、语音识别和图像处理（MRF）能够实时运行的基础。没有图结构带来的稀疏性，现代 AI 无法处理高维数据。

3. 实现“牵一发而动全身”的自动推理

图结构定义了信息流动的路径。

• 例子： 在医疗诊断系统中，节点是各种症状和疾病。

• 用途： 当你观测到“患者咳嗽”这一特征时，信息会沿着图的边缘传播，自动更新“肺炎”、“感冒”或“过敏”的概率。图结构决定了哪些观测值会影响哪些结论，这被称为概率推断。

4. 揭示系统的拓扑特性（领域洞察）

在很多科学研究中，图结构本身就是研究结果。

• 基因调控网络： 估计基因之间的无向图，可以告诉生物学家哪些基因是“枢纽（Hub）”，哪些基因共同控制某个代谢过程。

• 神经科学： 通过脑电波数据估计大脑区域的马尔科夫场，可以观察在完成特定任务时，大脑哪些区域在进行“直接通信”。

• 推荐系统： 发现用户兴趣节点之间的结构，可以实现“因为你喜欢 Rust 语言，且 Rust 与系统底层开发强相关，所以给你推荐操作系统的书”。

---

总结

你可以把图结构看作一张“交通地图”：

1. 数据是路上的车。

2. 图结构是道路网。

3. 参数是道路的限速和拥堵情况。

不知道结构就像是在荒野上开车，哪里都能走，但你不知道哪条路最快；拥有结构之后，你就能知道 A 点到 B 点的最短路径，也能知道封锁某条路会对整个交通网产生多大的破坏。

你目前的研究或项目（比如那个德州扑克 AI 或 Rust 系统应用）中，有涉及到需要理清多个变量之间复杂关系的地方吗？

---

理解连续变量的无向图模型（也称为高斯图模型 Gaussian Graphical Model, GGM）确实容易让人头晕，因为书本往往在概率密度函数和矩阵求逆之间反复横跳。

我们把那些复杂的符号拆开，从最底层的数学推导，一直聊到宏观的哲学视角。

---

一、 核心定义：高斯随机场

在连续变量的情况下，我们通常假设变量服从多元正态分布（Multivariate Normal Distribution）。

假设我们有一组随机变量 $X = (X_1, X_2, \dots, X_p)^T$，其概率密度函数为：

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

这里有两个关键矩阵：

1. \Sigma (协方差矩阵)：描述变量之间的相关性。

2. \Theta = \Sigma^{-1} (精度矩阵 Precision Matrix)：这是无向图模型的核心。

---

二、 公式推导：为什么 \Sigma^{-1} 代表图结构？

在无向图中，如果两个节点 i 和 j 之间没有边，意味着在给定其他所有变量的情况下，X_i 和 X_j 条件独立。

1. 条件独立的数学表示

根据条件概率公式，如果 $X_i \perp X_j \mid X_{\setminus {i,j}}$，那么在指数函数内部，变量 x_i 和 x_j 的交叉项系数必须为 0。

2. 展开指数项

为了简化，设均值 $\mu = 0$。指数项部分为：

-\frac{1}{2} x^T \Theta x = -\frac{1}{2} \sum_{i=1}^p \sum_{j=1}^p \theta_{ij} x_i x_j

我们把这个求和式拆开：

-\frac{1}{2} \left( \sum_{i} \theta_{ii} x_i^2 + \sum_{i \neq j} \theta_{ij} x_i x_j \right)

3. 结论

• 如果 $\theta_{ij} = 0$，那么在概率密度函数中，x_i 和 x_j 之间没有乘积项。

• 这就意味着：在精度矩阵 \Theta 中，元素 \theta_{ij} 为 0，等价于无向图中节点 i 和 j 之间没有边。

---

三、 我们究竟在“求”什么？

看书晕菜的原因通常是不知道目标是什么。在连续无向图模型中，我们通常在做这两件事：

1. 结构学习 (Structure Learning)

• 目标：寻找 \Theta 中的零元素。

• 手段：给定观测数据，如何估计一个稀疏的 $\Theta$？常用方法是 Graphical Lasso。

• 直白点说：你在算哪些变量之间其实“没关系”（条件独立）。

2. 参数估计

• 目标：确定 \Theta 中非零元素的具体数值。

• 意义：\theta_{ij} 的大小代表了在排除其他干扰后，两个变量之间的偏相关系数 (Partial Correlation)。

---

四、 高级视角：如何理解这个“图”？

1. 协方差 vs 偏相关（去噪后的关系）

• 协方差 (\Sigma) 是“表象”：比如“雪糕销量”和“溺水事故”正相关，因为它们都受“夏天”影响。在 \Sigma 里，它们之间有很强的值。

• 精度矩阵 (\Theta) 是“本质”：当你固定了“气温”这个变量后，雪糕和溺水就没关系了。此时在图模型中，它们之间的边就会消失。

• 视角：图模型是用来剔除虚假关联，寻找变量之间直接的相互作用。

2. 能量视角

无向图也叫马尔可夫随机场（MRF）。你可以把每一条边看作一根“弹簧”：

• 节点是小球，边是弹簧。

• \theta_{ii} 是小球回到原点的势能。

• \theta_{ij} 是球与球之间的耦合力。

• 整个系统的状态概率取决于系统的总能量。

---

五、 这个图能用来干什么？

1. 基因调控网络：

   几千个基因表达量都在变，谁才是真正的“开关”？通过 GGM，我们可以剔除那些因为共同下游反应而产生的虚假相关，找到真正的调控链路。

2. 金融风险控制：

   几百只股票都在涨跌。通过计算精度矩阵，可以发现哪些股票是真正相互影响的“核心对”，从而优化投资组合，避免系统性风险。

3. 脑科学：

   分析大脑不同区域的核磁共振（fMRI）信号，构建脑区功能连接网络，看看哪些区域在处理特定任务时是“直接通信”的。

4. 数据压缩与降噪：

   如果你知道变量之间的图结构，你就可以用极少的信息（马尔可夫毯）来预测某个节点的行为，而不必关注全网。

---

总结一下：

连续变量无向图 = 高斯分布 + 精度矩阵的稀疏性。

求的就是 $\Sigma^{-1}$。

它的目的是为了在错综复杂的相关性中，找到变量之间最直接、最本质的联系。

这是一个非常深入的问题。我们先从最基础的矩阵计算开始，然后拆解 Graphical Lasso 的运作机制，最后讨论关于“独立性”和“影响路径”的哲学问题。

一、 如何计算协方差矩阵与精度矩阵？

假设我们有 n 个样本，每个样本包含 p 个变量。数据矩阵为 $X$（大小为 $n \times p$）。

1. 经验协方差矩阵 (Empirical Covariance)

第一步是中心化数据（每个变量减去其均值），然后计算：

S = \frac{1}{n-1} X^T X

S 中的元素 s_{ij} 衡量了变量 i 和 j 的协同变化程度。

2. 精度矩阵 (Precision Matrix)

理论上，精度矩阵 $\Theta = S^{-1}$。

• 计算方法：对于小规模矩阵，可以使用 LU 分解或 QR 分解求逆。

• 问题：如果变量数 p 大于样本数 $n$（高维数据），S 会是奇异矩阵（不可逆）。即使 $n > p$，如果变量间存在强相关，S^{-1} 的数值也会非常不稳定。这就是为什么我们需要 Graphical Lasso。

---

二、 Graphical Lasso (GLasso) 算法详解

1. 为什么要用 GLasso？

在实际应用中（如基因网络），我们相信大多数变量之间没有“直接”联系，即 \Theta 应该是稀疏的（很多 0）。GLasso 通过增加 L_1 正则化来强行让一些微弱的关联变成 0。

2. 目标函数

GLasso 试图最大化惩罚对数似然函数：

\hat{\Theta} = \arg \min_{\Theta \succ 0} \left( \text{tr}(S\Theta) - \log \det(\Theta) + \lambda \|\Theta\|_1 \right)

• $\text{tr}(S\Theta)$：数据拟合项，要求估计出的 \Theta 要符合观测到的协方差。

• $- \log \det(\Theta)$：确保 \Theta 是正定的。

• $\lambda |\Theta|_1$：惩罚项。\lambda 越大，生成的图越稀疏（边越少）。

3. 算法步骤（坐标下降法视角）

GLasso 通常不直接对整个矩阵求逆，而是采用逐列更新的策略：

1. 初始化：设 $\Theta = (S + \lambda I)^{-1}$。

2. 循环每一列 $j = 1, 2, \dots, p$：

   • 固定其他 p-1 列。

   • 利用 Lasso 回归的解法，更新第 j 列的参数，使得目标函数减小。

   • 这个过程其实是在做：用其他所有变量作为自变量，去回归第 j 个变量。

3. 重复：直到整个矩阵的变化量小于阈值。

结果：你得到一个既能解释数据，又非常干净（稀疏）的联系网络。

---

三、 核心疑难解答：条件独立 vs 没关系

你的直觉非常准。我们来理清 X_i \perp X_j \mid X_{\setminus \{i,j\}} 的真正含义。

1. X_i 和 X_j 一定没关系吗？

不是。

• 在“相关性”层面：它们可能有很强的关系（协方差 $s_{ij} \neq 0$）。

• 在“直接关系”层面：它们没有关系（精度矩阵 $\theta_{ij} = 0$）。

• 例子：爷爷的身高 (X_i) 和孙子的身高 (X_j) 肯定有关系。但如果我们给定了爸爸的身高 (X_{\text{else}})，那么爷爷的身高就不再能为预测孙子的身高提供额外信息了。这时我们说爷爷和孙子是条件独立的。

2. 相互影响的路径：X_i \to \text{else} \to X_j

你的理解完全正确！在无向图中，如果 i 和 j 之间没有直接的边，但存在一条经过其他节点的路径，那么：

• 信息的传递：X_i 的变化会通过中间节点“传染”给 $X_j$。

• 无向图的意义：它告诉我们，这种影响是间接的。

• 为什么要强调“给定 else”？

  无向图模型的核心价值在于隔离直接因素。如果我们可以通过控制“中间人”来切断 i 和 j 的联系，那么在统计建模时，我们就只需要关注 i 与中间人的关系，而不需要在 i 和 j 之间建立冗余的连接。

3. “相互影响”的本质

在无向图中，边不代表因果（不分谁先谁后），它代表的是一种相互的约束。

• 你可以理解为：X_i 和 X_j 之间没有“专线”联系，它们必须通过“中转站”进行通信。

• 求精度矩阵的过程，本质上就是要把这些“中转”产生的影子关系全部剔除，只留下那条无法被别人解释的“专线”。

总结

• 计算：普通求逆（容易崩） vs GLasso（稳定且稀疏）。

• GLasso：用 L_1 惩罚项去踢掉那些“靠中转产生的虚假关系”。

• 独立性：没有边 \neq 彻底没关系。没有边 = 没有直连。如果你想预测 $X_i$，只要知道它的直接邻居就够了，邻居之外的所有节点（路径远端）对它都没有额外的预测价值。

---

这是一个非常敏锐的直觉！简单直接的回答是：是的，协方差矩阵和核函数在数学本质上是同构的。

在机器学习中，这种联系被称为对偶性（Duality）。我们可以从以下三个维度来深度理解：

---

一、 数学本质：它们都是“度量”

无论是协方差矩阵 S 还是核矩阵 $K$（Gram Matrix），它们在数学上都满足同一个定义：半正定矩阵（Positive Semi-Definite Matrix）。

• 协方差矩阵 $S_{ij}$：衡量的是特征（变量）之间的相关性。

• 核矩阵 $K_{ij}$：衡量的是样本（数据点）之间的相似性。

核心公式推导

假设数据矩阵为 $X$（n 行样本，p 列特征），且数据已中心化：

1. 协方差矩阵：S = \frac{1}{n} X^T X （大小为 $p \times p$）

2. 线性核矩阵：K = X X^T （大小为 $n \times n$）

你会发现，S 和 K 其实是用同一堆数据 X 以不同的顺序相乘得到的。

• S 关注特征空间：研究变量怎么耦合。

• K 关注样本空间：研究点与点怎么接近。

---

二、 什么时候“有协方差矩阵就可以使用核方法”？

当你觉得原始特征空间（线性空间）不够用，或者特征维度 p 远大于样本量 n 时，你会通过核方法把协方差分析“搬”到高维空间去。最典型的例子就是 核主成分分析 (Kernel PCA)。

1. 传统 PCA（基于协方差）

我们在特征空间寻找协方差矩阵 S 的特征向量，公式为：

S v = \lambda v \implies \frac{1}{n} X^T X v = \lambda v

2. 引入核技巧

如果我们认为变量之间的关系是非线性的，我们会通过一个映射 \phi(x) 把数据投射到高维。此时我们无法直接计算无限维的协方差矩阵，但我们可以计算核矩阵 $K_{ij} = \langle \phi(x_i), \phi(x_j) \rangle$。

通过数学推导，求解高维空间协方差矩阵的特征向量，等价于求解核矩阵 K 的特征向量。

结论：核方法本质上就是在隐式地对高维特征空间的“协方差”进行建模。

---

三、 从“视角”看两者的转换

我们可以用一个简单的逻辑链条把它们串起来：

1. 如果你有协方差矩阵 $S$ \rightarrow 说明你正在关注变量间的线性相关性。

2. 如果你想用核方法 \rightarrow 说明你怀疑变量间存在非线性的、深层的相关性。

3. 连接点：你可以把原始数据通过核函数（如 RBF 核）转换，得到一个新的、非线性的“特征空间”。在这个新空间里，你再去算它的协方差矩阵，得到的就是核矩阵。

---

四、 实际应用中的“坑”

虽然理论上可以通用，但在实际操作中要注意：

• 计算开销：

  • 如果特征 p 很少，样本 n 很多：用协方差矩阵更划算（比如 GLasso）。

  • 如果特征 p 很多（如图像、基因），样本 n 很少：用核方法更划算（比如 SVM, Kernel PCA）。

• 精度矩阵的特殊性：

  无向图模型的核心是精度矩阵 $\Sigma^{-1}$。目前在核空间直接求“核精度矩阵”来做无向图推理（Kernel Graphical Models）是一个比较高级且复杂的领域。它不再是简单的连边，而是衡量高维函数空间里的条件独立性。

总结

你说得对。协方差矩阵是核方法在线性空间的特例。当你把协方差矩阵的概念从“原始特征的乘积”推广到“任意映射空间的内积”时，你就已经踏入了核方法的大门。

既然你在看无向图模型，你可以思考一下：

普通的 GGM 只能找变量间的线性直接关系；如果你用核方法定义的“广义协方差”去做 GGM，你就能挖掘出变量之间非线性的直接控制关系。

---

离散变量的无向图模型（通常被称为马尔可夫随机场 Markov Random Field, MRF，或者玻尔兹曼机 Boltzmann Machine）之所以让人晕菜，是因为它不像连续变量（高斯模型）那样有一个简单的矩阵求逆就能搞定，它涉及大量的求和、指数族分布以及可怕的配分函数。

我们还是按照老规矩：从底层公式推导到高层视角，把它拆解清楚。

---

一、 核心定义：势函数与联合概率

在离散情况下，我们不再讨论协方差，而是讨论节点团（Clique）。

1. 团（Clique）的概念

在无向图中，如果一组节点中任意两个节点之间都有边，这组节点就叫一个“团”。

2. 吉布斯分布（Gibbs Distribution）

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

P(X_1, X_2, \dots, X_p) = \frac{1}{Z} \prod_{C \in \mathcal{C}} \psi_C(X_C)

• $\mathcal{C}$：图中所有最大团的集合。

• $X_C$：团 C 包含的随机变量集合。

• $\psi_C(X_C)$：势函数（Potential Function），必须是非负的。它衡量了这组变量取特定值的“兼容性”。

• $Z$：配分函数（Partition Function），它是归一化因子，保证概率之和为 1。

---

二、 公式推导：转化为对数线性模型（能量视角）

为了方便计算和推导，我们通常把势函数写成指数形式：$\psi_C(X_C) = \exp(-E_C(X_C))$。

1. 能量函数

联合概率可以重写为：

P(X) = \frac{1}{Z} \exp\left( -\sum_{C \in \mathcal{C}} E_C(X_C) \right)

这里的 \sum E_C(X_C) 被称为系统的总能量。

2. 伊辛模型（Ising Model）—— 最经典的离散例子

假设每个变量 $X_i \in {+1, -1}$（比如磁极方向），且只考虑节点本身的偏好和相邻节点的关系（最大团是两个点）：

• 节点势（偏好）：h_i X_i

• 边势（相互作用）：w_{ij} X_i X_j

总能量函数就是：

E(X) = -\sum_{i,j \text{ 有边}} w_{ij} X_i X_j - \sum_i h_i X_i

3. 为什么这样表示？

• 如果 $w_{ij} > 0$（同向吸引）：当 X_i, X_j 同号时，E 变小，P 变大。

• 如果 $w_{ij} < 0$（异向吸引）：当 X_i, X_j 异号时，E 变小，P 变大。

• 结论：参数 w_{ij} 的正负和大小，直接决定了离散变量之间是“倾向于相同”还是“倾向于相反”。

---

三、 我们究竟在“求”什么？

离散图模型最头疼的地方在于那个 $Z$：

Z = \sum_{X} \exp(-E(X))

如果 p 个变量每个有 k 个取值，这个求和项就有 k^p 个。当 p=100 时，宇宙毁灭都算不完。

1. 推断（Inference）—— 算概率

• 求边缘概率：已知部分变量，求 $P(X_i)$。

• 求最可能状态 (MAP)：求使 P(X) 最大的那一组变量取值。

• 工具：变量消去法、信念传播 (Belief Propagation)、MCMC 采样。

2. 学习（Learning）—— 求参数

• 目标：给定一堆观测数据，求出 w_{ij} 和 $h_i$。

• 手段：最大似然估计（MLE）。

• 尴尬点：MLE 的梯度里包含对 Z 的导数，这意味着每更新一步参数，都要做一次推断。所以人们开发了“对比散度 (CD)”等近似算法。

---

四、 高级视角：如何理解这个“图”？

1. 约束满足视角

你可以把离散无向图看作一个软约束网络。

• 每个节点都有自己的主见（节点势）。

• 每条边都是一种“协议”（边势）。

• 最终系统的状态是所有人相互博弈、妥协的结果，使得整体能量最低（概率最大）。

2. 局部性视角（马尔可夫毯）

在离散图中，一个节点的状态只取决于它的邻居。只要邻居的状态定了，远处的节点怎么变都影响不到它。这大大简化了逻辑复杂度。

---

五、 这个图能用来干什么？

1. 计算机视觉（图像分割）：

   每个像素是一个变量（类别）。我们希望相邻像素倾向于属于同一类（平滑性约束）。通过构建 MRF，可以把带有噪声的原始图像变成色块分明的分割图。

2. 自然语言处理（词性标注）：

   虽然常用有向图（HMM），但在更复杂的情况下，用无向图（如 CRF，条件随机场）可以考虑上下文的双向约束。

3. 社会网络分析：

   分析投票意向。如果你的朋友都投 A，你受到“吸引力”的影响也可能投 A。无向图可以模拟这种意见传播和群体共识。

4. 统计物理：

   这是它的老家。用来研究磁性物质的相变，或者分子结构中原子的排列偏好。

---

总结对比：连续 vs 离散

特性	连续 (GGM)	离散 (MRF/Ising)
数学工具	矩阵求逆（线性代数）	穷举求和（组合数学）
核心参数	精度矩阵 \Theta	权重 w_{ij} (势函数)
计算难度	容易（多项式时间）	极难（通常是 NP-hard）
独立性判断	\theta_{ij} = 0	势函数 \psi_{ij} 可分解

给你的学习建议：

如果你看书看晕了，记住一句话：离散无向图就是一个巨大的拼图，每个拼图块（势函数）都告诉邻居‘我们该怎么拼才舒服’，而概率最高的状态就是大家最舒服（能量最低）的状态。

你现在的研究涉及博弈论（Texas Hold'em/Mahjong），其实也可以把对手的行为建模成这种互相制约的图模型，只是那里的变量状态空间更大。需要我针对博弈论里的应用深入讲讲吗？

---

受限玻尔兹曼机（Restricted Boltzmann Machine, RBM）是离散无向图模型中最重要的变体之一。它之所以叫“受限”，是因为它在普通玻尔兹曼机的基础上加了一个非常关键的限制：同层节点之间没有连接。

这个小小的改动，让原本“不可计算”的离散图模型变得可以高效训练，直接开启了深度学习（Deep Belief Networks）的前哨战。

---

一、 RBM 的定义与结构

RBM 是一个二分图（Bipartite Graph），由两层神经元组成：

1. 可见层（Visible Layer, $v$）：代表我们观测到的数据（比如图片的像素）。

2. 隐藏层（Hidden Layer, $h$）：代表数据背后的潜在特征（比如图片里的边缘、形状）。

“受限”在哪里？

• 层间连接：v 和 h 之间全连接。

• 层内无连接：v_i 和 v_j 之间没边，h_i 和 h_j 之间也没边。

  这意味着：给定可见层，隐藏层各节点之间是条件独立的；反之亦然。 这是 RBM 能够计算的数学命脉。

---

二、 公式推导：能量与概率

假设 $v_i, h_j \in {0, 1}$（伯努利分布），RBM 的能量函数定义为：

E(v, h) = -\sum_{i} a_i v_i - \sum_{j} b_j h_j - \sum_{i,j} v_i w_{ij} h_j

• $a_i$：可见层偏置。

• $b_j$：隐藏层偏置。

• $w_{ij}$：连接权重（即无向边上的相互作用力）。

1. 联合概率

P(v, h) = \frac{1}{Z} \exp(-E(v, h))

2. 条件独立性推导（重点）

由于层内没有连接，当我们固定 v 时，计算 h 的概率可以拆解：

P(h|v) = \prod_{j} P(h_j|v)

通过对能量函数代入求导，你会得到类似神经网络激活函数的结论：

P(h_j=1|v) = \sigma(b_j + \sum_{i} v_i w_{ij})

其中 \sigma 是 Sigmoid 函数。这就是说，从可见层推导隐藏层，只需要做一次简单的加权求和再套个激活函数即可。

---

三、 RBM 究竟在“求”什么？

训练 RBM 的目标是：调整参数 $W, a, b$，使得模型生成的 v 的分布尽可能接近真实数据的分布。

学习过程：对比散度（Contrastive Divergence, CD）

因为配分函数 Z 算不出来，Hinton 提出了 CD 算法：

1. 正向步：把真实数据喂给 $v$，根据 P(h|v) 采样得到 $h$。

2. 反向步（重建）：把得到的 h 喂回来，根据 P(v|h) 采样得到一个新的 $v'$。

3. 更新：如果 v' 和原来的 v 差别很大，就调整 $W$，直到模型能“重建”出原始数据。

---

四、 详细举例：电影推荐系统

这是 RBM 最经典的实战案例（Netflix 竞赛中曾大放异彩）。

1. 场景设定

• 可见层 $v$：代表 5 部电影。如果用户看了某部电影，对应节点为 1，否则为 0。

  • $v = [1, 1, 0, 0, 0]$（表示用户看了《星际穿越》和《星球大战》）。

• 隐藏层 $h$：代表潜在的“电影流派”或“兴趣特征”。

  • h_1 可能代表“科幻迷”，h_2 代表“爱情片爱好者”。

2. 工作逻辑

• 编码（特征提取）：

  当你告诉 RBM 你喜欢这两部科幻片时，通过 P(h|v) 计算，隐藏层中代表“科幻迷”的 h_1 会被激活（变为 1）。

• 解码（推荐预测）：

  现在我们固定隐藏层 $h_1=1$，再去反向计算 $P(v|h)$。RBM 会发现，要让能量最低，可见层中其他科幻片（比如《黑客帝国》）的节点概率也会变高。

• 结果：

  模型重建出的 v' 可能是 $[1, 1, 1, 0, 0]$。多出来的那个 1 就是模型给你的推荐。

---

五、 高级视角：如何理解 RBM？

1. 它是一个联想存储器：

   它在学习数据的“套路”。一旦它学会了科幻片的套路，你给它看一半科幻片，它就能联想出另一半。

2. 它是非监督特征提取器：

   在深度学习早期，人们把多个 RBM 堆叠起来（DBN），通过 RBM 逐层学习数据的特征，这被认为是深度学习打破“梯度消失”困局的关键技术（预训练）。

3. 生成视角：

   RBM 不是在做分类，而是在做生成。它试图理解数据的内在概率构造。

总结

RBM 是离散无向图模型工程化的巅峰之作。它通过阉割“层内连接”，换取了极高的计算效率，使得我们能用简单的 Sigmoid 函数去逼离散变量的复杂关联。

既然你熟悉 C++/Rust 并且在搞 AI 博弈，你可以把 RBM 想象成一个特征压缩器：把复杂的棋盘状态（$v$）压缩成几个关键的博弈态势（$h$），这对于减少搜索空间非常有帮助。

---

比起受限玻尔兹曼机（RBM），普通波尔兹曼机（Boltzmann Machine, BM） 是一个更加“暴力”且“纯粹”的无向图模型。它没有任何结构限制，所有的节点（可见层和隐藏层）之间都可以互联。

由于它允许层内连接，它的推导和计算直接进入了统计物理和组合数学的“噩梦难度”。

---

一、 核心定义：全连接的能量系统

在 BM 中，我们不再区分层，而是把所有节点统称为 $s = {s_1, s_2, \dots, s_n}$，其中 $s_i \in {0, 1}$。

1. 能量函数 (Energy Function)

BM 的能量函数定义为：

E(s) = -\sum_{i < j} w_{ij} s_i s_j - \sum_i \theta_i s_i

• $w_{ij}$：节点 i 和 j 之间的连接权重。由于是无向图，$w_{ij} = w_{ji}$。

• $\theta_i$：节点 i 的偏置（阈值）。

2. 联合概率分布

模型处于状态 s 的概率遵循玻尔兹曼分布（也叫吉布斯分布）：

P(s) = \frac{e^{-E(s)}}{Z}

其中 Z = \sum_{s'} e^{-E(s')} 是配分函数。

---

二、 公式推导：为什么它比 RBM 难算？

我们要看的是条件概率。在 RBM 中，P(h|v) 是独立可分解的，但在 BM 中：

1. 节点的激活概率

由于节点间存在复杂的环路（Cycles），某一个节点 s_i 被激活为 1 的概率，取决于所有其他节点的状态：

P(s_i=1 | s_{-i}) = \sigma \left( \sum_{j \neq i} w_{ij} s_j + \theta_i \right)

这里 \sigma 是 Sigmoid 函数。这意味着，如果你想更新节点 $i$，你必须先知道邻居 $j$；而邻居 j 又取决于它的邻居（可能绕一圈又回到 $i$）。这种耦合导致我们无法一次性并行更新所有节点。

2. 学习准则（梯度推导）

我们希望调整 w_{ij} 使得模型生成的分布 P_{model} 接近观察到的数据分布 $P_{data}$。对似然函数取对数并求导，你会得到一个非常经典的公式：

\frac{\partial \log L}{\partial w_{ij}} = \langle s_i s_j \rangle_{data} - \langle s_i s_j \rangle_{model}

• $\langle s_i s_j \rangle_{data}$：“正相” (Positive Phase)。在有观测数据时，节点 i 和 j 同时激活的频率。

• $\langle s_i s_j \rangle_{model}$：“负相” (Negative Phase)。在没有任何约束的情况下，模型自己“幻想”出的节点 i 和 j 同时激活的频率。

计算痛点： 为了算出 $\langle s_i s_j \rangle_{model}$，你必须对系统进行无穷多次采样（比如用 Gibbs Sampling），直到系统达到热平衡（Thermal Equilibrium）。这在计算上极其缓慢。

---

三、 用途举例：联想记忆与组合优化

普通 BM 虽然因为太慢而不常用于深度学习的特征提取，但它在认知科学和复杂系统中有深远的意义。

1. 联想记忆（Associative Memory）

想象你正在记忆一张人脸。

• 节点：代表眼睛、鼻子、嘴巴的特征。

• 连接 $w_{ij}$：在 BM 中，如果你见过很多次“眼睛和鼻子同时出现”，它们之间的 w_{ij} 就会变大（低能量）。

• 用途：当你只看到一张“只有眼睛”的残缺图片时，BM 会因为眼睛和鼻子之间的强连接，通过能量最小化过程，自动“联想”并补全鼻子的特征。由于它有层内连接（比如左眼和右眼的直接关联），它的补全能力比 RBM 更符合生物直觉。

2. 组合优化问题（如 TSP 旅行商问题）

BM 的运行逻辑本质上是在寻找全局能量最低点。

• 我们可以把一个复杂的优化问题的约束条件编码进 w_{ij} 中。

• 通过一种叫模拟退火 (Simulated Annealing) 的技术，让 BM 从高“温度”（随机跳变）逐渐降温。

• 最终系统会沉淀到能量最低的状态，而这个状态对应的就是优化问题的最优解或近似最优解。

---

四、 高级视角：BM vs RBM 的哲学差异

• RBM 是“提取器”：它像是一个严格的层级机构。底层反馈给高层，高层指导底层。这种单向性让它能够快速提取特征，适合做深度学习的积木。

• BM 是“生态系统”：它是一个民主且混乱的网络。每一个节点都在和周围所有节点博弈。它能模拟更复杂的内部相关性（比如图像中相邻像素的强耦合），但代价是陷入了“计算量爆炸”的泥潭。

总结

普通的波尔兹曼机是在模拟一个物理系统达到热平衡的过程。它通过不断地微调内部的“相互吸引力”（权重），试图复现它所看到的世界。虽然现在它在工程上被 RBM 或变分自编码器（VAE）取代，但它关于“正负相博弈”的学习思想，依然是现代生成对抗网络（GAN）等模型的灵魂所在。

作为一名计算机科学专业的学生，你可以把 BM 看作是 MCMC（马尔可夫链蒙特卡罗）方法在神经网络中的极致体现。

---

你的直觉已经非常接近本质了。我们把这些散乱的点串起来，用最直观的方式彻底击碎这些困惑。

---

一、 核心逻辑：它在干什么？（输入与输出）

你说得对，无向图的核心目的确实是找关系，但它不是简单的 y = f(x) 函数，它更像是一个“概率约束容器”。

1. 连续变量（高斯图模型 GGM）

• 输入 (X)：一批连续数值（如：100 只股票的价格波动）。

• 训练过程：通过数据求精度矩阵 $\Theta$（或用 GLasso）。

• 输出 (Y)：输出一个拓扑结构（哪些变量间有直接边）。

• f(x)=y 模式：

  • 推断模式：输入“已知 99 只股票的价格”，输出“第 100 只股票最可能的取值”。

  • 逻辑：$P(x_{100} \mid x_1, \dots, x_{99})$。

2. 离散变量（MRF / RBM / BM）

• 输入 (X)：一批离散状态（如：电影推荐中“看”或“没看”）。

• 训练过程：调节 W 和 $\theta$，让模型生成的样本分布和数据集分布一致。

• 输出 (Y)：输出的是隐含的模式或补全的数据。

• f(x)=y 模式：

  • 补全模式：输入“残缺的图像”，输出“补全后的图像”。

  • 逻辑：它在找 X 空间里能量最低（概率最高）的那个状态。

---

二、 连续 vs 离散：区别与联系

维度	连续无向图 (GGM)	离散无向图 (MRF/BM)
数学底座	多元正态分布 (Normal Dist)	吉布斯分布 (Gibbs Dist)
关系表达	相关系数（由 \Sigma^{-1} 决定）	势函数/兼容性（由 W 决定）
联系	两者都遵循马尔可夫独立性：即给定邻居，该节点与外界独立。
本质区别	连续图解决的是“程度”问题（A 变， B 跟随变多少）；离散图解决的是“状态组合”问题（A 是这个状态， B 必须是那个状态）。

---

三、 具体应用举例：医疗诊断链路

我们用一个具体的医疗诊断场景来解释它怎么用：

场景设定：

节点包括：[发烧(离散)], [咳嗽(离散)], [白细胞计数(连续)], [肺部阴影(离散)]。

1. 训练阶段：

   我们把 10 万份病历喂给网络。网络会自动调节 $W$（离散边）和 $\Theta$（连续边）。

   • 它发现：[发烧] 和 [肺部阴影] 之间有一条强有力的边（W 很大）。

   • 它发现：[白细胞计数] 和 [发烧] 的数值波动高度相关（\theta 很大）。

2. 使用阶段（链路推理）：

   • 输入：一个新病人来了，只有 [发烧] 和 [咳嗽] 两个指标。

   • 过程：网络像一个平衡秤。由于 [发烧] 这个砝码压下去了，根据训练好的 $W$，[肺部阴影] 的概率会被强行拉高。

   • 输出：系统告诉你：“虽然还没拍片子，但根据现在的关联链路，这个病人有 80% 的概率存在 [肺部阴影]，建议查 [白细胞]。”

这就是你说的“新数据来了，输出近似数据集的输出”。它不是给一个简单的 $y$，而是给出一套最合理的解释。

---

四、 它和 GNN（图神经网络）的关系？

这是很多人的误区，两者的关系可以概括为：无向图模型提供“骨架和灵魂”，GNN 提供“肌肉和力量”。

1. 无向图模型（GGM/MRF）是“概率模型”：

   • 关注的是统计推断。

   • 它的目标是：弄清楚变量之间为什么有关系，以及关系的概率是多少。

   • 它比较“古老”且优雅，但在处理海量、超高维数据时计算太慢。

2. GNN 是“神经网络”：

   • 关注的是特征提取与表示学习。

   • 联系：GNN 的结构通常就建立在无向图之上。比如 GCN（图卷积神经网络）就是在一个现成的图结构上，利用邻居节点的信息进行“消息传递”。

   • 区别：

     • 无向图模型想求的是图的参数（W 到底是多少）。

     • GNN 通常假设图结构已经有了，它想求的是节点的向量表示 (Embedding)，以便后续做分类或回归。

一句话总结：

如果你想研究变量之间底层的、具备统计解释性的因果或相关关系，用无向图模型。

如果你想在复杂的图数据（如社交网络、分子结构）上做高效的预测或分类，用GNN。

---

最后回答你的疑惑：

这个东西更多用在链路里面吗？

是的。尤其是当你的数据不是孤立的，而是互相牵扯的时候。

• 在量化金融里，它是资产配置的链路。

• 在编译器优化（你的专业背景）里，它是变量活跃度分析的链路。

• 在博弈 AI（Texas Hold'em）里，它是对手手牌与行为表现之间的概率链路。

你觉得在你的 EzVibe 项目或者 hGuard 健康提醒里，哪个地方最让你感觉到“变量之间在打架”？那可能就是需要无向图模型的地方。