贝叶斯网络：结构学习

从数据中学习贝叶斯网络 (BN) 的结构是概率建模中一项基本但有难度的任务。与参数 (parameter)学习不同，参数学习假设条件依赖关系（图结构）已知，目标是估计条件概率分布 (CPD) 的参数；而结构学习则尝试直接从观测数据中发现这些依赖关系。这个过程旨在找到一个有向无环图 (DAG) $G$，它能最好地表示数据集 $D$ 中存在的依赖关系。

主要思想是确定哪些变量直接影响其他变量，从而形成图的定向边。这不同于仅仅寻找相关性；结构学习寻找的是条件独立性，这对于数据生成过程提供更多信息。然而，仅从观测数据推断因果关系通常是不可能的，除非有额外的假设或干预数据。结构学习通常识别出属于同一 马尔可夫等价类 的结构，即编码相同条件独立性集合的图。

为何学习结构？

在许多情况下，变量之间真正的依赖结构事先不为人知。领域专业知识可能提供一些先验信息，但数据驱动的结构发现可以：

1. 展现意料之外的关系： 自动识别专家可能不明显依赖关系。
2. 使模型适应数据： 构建根据数据集中观察到的特定模式定制的模型。
3. 提供洞察： 学习到的图结构本身可以是一个有价值的输出，提供对所建模系统的定性认识。

结构学习的挑战

找到最优图结构在计算上是困难的。可能的 DAG 数量随变量 $n$ 的数量呈超指数增长。具体来说，DAG 数量 $f(n)$ 满足以下递推关系：

$$f(n) = \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} 2^{k(n-k)} f(n-k)$$

这种组合爆炸使得除了最小的网络（例如，$n > 5$）之外，穷举搜索都不可行。因此，实际的结构学习依赖于启发式搜索策略或基于条件独立性检验的方法。

结构学习的主要方法

两种主要的算法家族在 BN 结构学习中占主导地位：

1. 基于约束的方法

这些方法通过对数据执行条件独立性 (CI) 统计检验来工作。它们尝试识别在给定一组其他变量 $S$ 的情况下独立的变量对 $(X, Y)$，表示为 $(X \perp Y | S)$。观察到的独立性模式限制了可能的图结构。

ACO 离散数据常用 CI 检验是卡方 ($\chi^2$) 检验或 G 检验（似然比检验）。对于假设高斯分布的连续数据，可以使用基于偏相关性的检验。

算法示例：PC 算法 (Peter-Clark)

PC 算法是一种知名的基于约束的方法。它从一个完全连接的无向图开始，并根据递增阶数（条件集大小）的 CI 检验迭代地移除边。

1. 初始化： 从连接所有变量的完整无向图开始。
2. 边移除：
   • 对于每对通过边连接的变量 $(X, Y)$，检验是否 $(X \perp Y)$。如果为真，则移除该边。
   • 对于每对仍连接的 $(X, Y)$，检验对于所有单个邻居 $Z$ 是否 $(X \perp Y | Z)$。如果对任何 $Z$ 为真，则移除该边。
   • 继续增加条件集 $S$ 的大小（例如，$|S|=2, 3, \dots$），并对相邻的 $X, Y$ 检验 $(X \perp Y | S)$。如果发现独立性，则移除该边。
3. 定向： 根据发现的分离集（使 $X, Y$ 独立的 $S$）对边进行定向，以避免创建新的 v-结构（$X \rightarrow Z \leftarrow Y$），除非独立性要求。应用其他定向规则以确保无环性和一致性。

局限性：

• 数据需求大： CI 检验需要大量数据才能可靠，特别是条件集较大时。
• 检验敏感性： 结果可能对 CI 检验的选择和使用的显著性阈值 ($\alpha$) 敏感。早期检验（小条件集）中的错误可能会传播。
• 忠实性假设： 这些方法假设真实分布对某个 DAG 是 忠实 的，这意味着所有观察到的独立性都由图结构隐含，反之亦然。

2. 基于评分的方法

这些方法将结构学习视为一个优化问题。定义一个评分函数 $Score(G, D)$，它衡量候选图结构 $G$ 与观测数据 $D$ 的拟合程度。目标是找到使该评分最大化的图 $G^*$。

$$G^* = \arg \max_{G \in \mathcal{G}} Score(G, D)$$

其中 $\mathcal{G}$ 是所有可能 DAG 的空间。由于穷举搜索不可行，采用启发式搜索算法：

• 贪婪爬山算法： 从初始图（例如，空图或随机图）开始。迭代地进行局部更改（添加、删除或反转一条边），以产生评分的最大增长，同时确保无环性。当没有任何局部更改能提高评分时停止。容易陷入局部最优。
• 禁忌搜索： 一种元启发式算法，通过维护一个最近访问过的结构或移动的“禁忌列表”来增强爬山算法，以避免循环并逃离局部最优。
• 模拟退火： 一种概率优化技术，允许以一定概率接受降低评分的移动，该概率随时间降低，有助于逃离局部最优。
• 遗传算法： 维护一个候选结构种群，使用交叉和变异等操作，使结构向高评分图演化。

常用评分函数：

• 贝叶斯信息准则 (BIC)： 一个惩罚似然评分，权衡模型拟合度和复杂度。 $$Score_{BIC}(G, D) = \log P(D | \hat{\theta}_G, G) - \frac{\text{dim}(G)}{2} \log N$$ 其中 $\hat{\theta}_G$ 是图 $G$ 的最大似然参数 (parameter)，$\text{dim}(G)$ 是模型中独立参数的数量，$N$ 是数据点的数量。BIC 计算效率高且一致（渐近地找到真实结构）。
• 赤池信息准则 (AIC)： 与 BIC 类似，但惩罚项不同。 $$Score_{AIC}(G, D) = \log P(D | \hat{\theta}_G, G) - \text{dim}(G)$$
• 贝叶斯评分（例如，BDeu - 贝叶斯狄利克雷等价均匀）： 这些评分计算边缘似然 $P(D | G) = \int P(D | \theta_G, G) P(\theta_G | G) d\theta_G$，积分消除参数 $\theta_G$。这自然地包含对复杂度的惩罚，并与贝叶斯框架很好地吻合。如果使用共轭先验（如多项式变量的狄利克雷先验），计算边缘似然通常是可行的。BDeu 评分对先验参数等价性和均匀性做出假设。

示例：贪婪爬山算法的可视化

设想搜索空间，其中高度代表评分。爬山算法从一点开始，总是向上移动。

贪婪爬山算法搜索的示意。从初始图（红色圆圈）开始，算法沿着评分的改进（蓝色虚线箭头）前进，直到达到局部最优（红色实心圆圈），在此没有任何单一边更改能提高评分。全局最优（绿色双圆圈）可能会被错过。

优点与缺点：

• 灵活性： 可以通过初始图或评分惩罚轻松加入先验知识。
• 整体视角： 评分评估整个图结构。
• 局部最优： 启发式搜索方法可能陷入次优解。
• 计算成本： 评估评分和搜索空间仍然可能计算量大，但对于密集图通常比基于约束的方法更具可扩展性。

3. 混合方法

这些方法结合了基于约束和基于评分的技术，以利用它们各自的优势。例如，可以首先使用基于约束的方法来修剪搜索空间，通过识别确定的独立性（移除边），然后在受限空间内进行基于评分的搜索。

贝叶斯结构学习

纯贝叶斯方法将图结构 $G$ 本身视为一个随机变量，带有先验分布 $P(G)$。目标是计算给定数据下的结构后验分布：

$$P(G | D) = \frac{P(D | G) P(G)}{P(D)} = \frac{P(D | G) P(G)}{\sum_{G' \in \mathcal{G}} P(D | G') P(G')}$$

这里，$P(D | G)$ 是基于评分方法中使用的边缘似然（通常是贝叶斯评分）。$P(G)$ 允许编码关于结构的先验信念（例如，惩罚密集图）。

计算完整的后验 $P(G | D)$ 通常不可行，由于归一化 (normalization)常数 $P(D)$，这需要对所有可能的 DAG 求和。常用策略包括：

• 寻找最大后验 (MAP) 结构： $G_{MAP} = \arg \max_G P(G | D)$，这等同于最大化 $P(D | G) P(G)$。这通常使用基于评分的搜索启发式方法来处理。
• 贝叶斯模型平均： 不选择单一的最佳图，而是在多个高评分图上平均预测，并按其后验概率加权。这可以通过 MCMC 方法（例如在结构上的马尔可夫链蒙特卡洛）来近似，以从后验 $P(G | D)$ 中采样图。

实际考量

• 等价结构： 仅凭观测数据无法区分同一马尔可夫等价类中的图。例如，$X \rightarrow Y$ 和 $X \leftarrow Y$ 在没有进一步信息的情况下统计上是无法区分的。学习到的结构通常代表等价类。
• 潜在变量： 未观测（潜在）变量的存在可能在观测变量之间引起虚假依赖关系，使结构学习复杂化。
• 数据质量： 缺失数据和噪声明显影响学习结构的可靠性。
• 评估： 评估学习到的结构质量并非易事。指标包括与已知真实情况（在模拟中）比较、评估保留数据的似然性，或评估与参考图的结构差异（例如，结构汉明距离）。

结构学习仍然是一个活跃的研究领域，特别是在可伸缩性、处理混合数据类型、纳入因果假设以及处理潜在变量方面。尽管有挑战，从数据中学习网络结构的能力提供了一个强大的工具，用于理解复杂系统和构建自适应概率模型。