2025-11-20T18:07:15.632725

An Asymptotically Optimal Coordinate Descent Algorithm for Learning Bayesian Networks from Gaussian Models

Xu, Küçükyavuz, Shojaie et al.
This paper studies the problem of learning Bayesian networks from continuous observational data, generated according to a linear Gaussian structural equation model. We consider an $\ell_0$-penalized maximum likelihood estimator for this problem which is known to have favorable statistical properties but is computationally challenging to solve, especially for medium-sized Bayesian networks. We propose a new coordinate descent algorithm to approximate this estimator and prove several remarkable properties of our procedure: the algorithm converges to a coordinate-wise minimum, and despite the non-convexity of the loss function, as the sample size tends to infinity, the objective value of the coordinate descent solution converges to the optimal objective value of the $\ell_0$-penalized maximum likelihood estimator. Finite-sample statistical consistency guarantees are also established. To the best of our knowledge, our proposal is the first coordinate descent procedure endowed with optimality and statistical guarantees in the context of learning Bayesian networks. Numerical experiments on synthetic and real data demonstrate that our coordinate descent method can obtain near-optimal solutions while being scalable.
academic

An Asymptotically Optimal Coordinate Descent Algorithm for Learning Bayesian Networks from Gaussian Models

基本信息

  • 论文ID: 2408.11977
  • 标题: An Asymptotically Optimal Coordinate Descent Algorithm for Learning Bayesian Networks from Gaussian Models
  • 作者: Tong Xu (Northwestern University), Simge Küçükyavuz (Northwestern University), Ali Shojaie (University of Washington), Armeen Taeb (University of Washington)
  • 分类: stat.ML cs.LG
  • 发表时间: 2024年8月（arXiv预印本）
  • 论文链接: https://arxiv.org/abs/2408.11977

摘要

本文研究从连续观测数据学习贝叶斯网络的问题，数据根据线性高斯结构方程模型生成。作者考虑了该问题的ℓ₀惩罚最大似然估计器，该估计器具有良好的统计性质，但在计算上具有挑战性，特别是对于中等规模的贝叶斯网络。文章提出了一种新的坐标下降算法来近似该估计器，并证明了算法的几个显著性质：算法收敛到坐标最小值，尽管损失函数是非凸的，但随着样本量趋于无穷，坐标下降解的目标值收敛到ℓ₀惩罚最大似然估计器的最优目标值。据作者所知，这是第一个在学习贝叶斯网络背景下具有最优性保证的坐标下降算法。

研究背景与动机

问题定义

贝叶斯网络为建模随机变量集合之间的因果关系提供了强大的框架。通常用有向无环图（DAG）表示，其中随机变量编码为顶点，从节点i到节点j的有向边表示i导致j，图的无环性防止循环依赖的出现。

问题重要性

在基因调控网络等大型系统中，DAG结构通常是未知的，需要从数据中学习图结构。如果已知DAG，可以用来预测系统在操作或干预下的行为，这在科学发现和决策制定中具有重要意义。

现有方法的局限性

  1. 基于约束的方法：如PC算法，需要在强忠实性条件下才有统计一致性保证，在高维设置下该条件过于严格
  2. 基于评分的方法：虽然不需要强忠实性假设，但许多方法缺乏统计保证，求解确切解的计算复杂度很高
  3. 现有坐标下降方法：虽然在学习大规模贝叶斯网络方面表现出显著潜力，但缺乏收敛性和最优性保证

研究动机

作者旨在开发一种既具有理论保证又具有计算可扩展性的方法，填补现有坐标下降算法在理论分析方面的空白。

核心贡献

  1. 提出了第一个具有最优性保证的坐标下降算法：在学习贝叶斯网络的背景下，算法收敛到坐标最小值，并在大样本极限下产生最优评分的DAG
  2. 建立了渐近最优性理论：证明了尽管问题的非凸性，坐标下降解的目标值在样本量趋于无穷时收敛到ℓ₀惩罚最大似然估计器的最优目标值
  3. 刻画了优化景观：在大样本情况下，所有局部最小值都达到接近全局最小值的目标值，在极限情况下完全匹配
  4. 提供了收敛率分析：将收敛率表征为样本量和节点数的函数
  5. 扩展了拓扑排序理论：改进了Chen等人的结果，允许在轻度异方差噪声条件下恢复有效的拓扑排序

方法详解

任务定义

给定n个独立同分布的观测样本，这些样本来自满足线性结构方程模型的随机向量X：

X = B⋆ᵀX + ε

其中B⋆是连接矩阵，ε～N(0,Ω⋆)是高斯噪声。目标是估计B⋆的稀疏模式，即学习潜在的DAG结构。

模型架构

1. ℓ₀惩罚最大似然估计

原始优化问题：

min_{B,D} ℓₙ((I-B)D(I-B)ᵀ) + λ/2‖B‖_{ℓ₀}
s.t. G(B) is a DAG

2. 等价变换

通过变量替换Γ ← (I-B)D^{1/2}，得到等价问题：

min_Γ f(Γ) s.t. G(Γ-diag(Γ)) is a DAG

其中f(Γ) = Σᵢ(-2log(Γᵢᵢ)) + tr(ΓΓᵀΣ̂) + λ/2‖Γ-diag(Γ)‖_{ℓ₀}

3. 坐标更新规则

命题3给出了单坐标优化的解析解：

  • 对于非对角元素Γᵤᵥ (u≠v)：
Γ̂ᵤᵥ = {-Aᵤᵥ/(2Σ̂ᵤᵤ), if λ/2 ≤ A²ᵤᵥ/(4Σ̂ᵤᵤ)
        {0,              otherwise
  • 对于对角元素Γᵤᵤ：
Γ̂ᵤᵤ = (-Aᵤᵤ + √(A²ᵤᵤ + 16Σ̂ᵤᵤ))/(4Σ̂ᵤᵤ)

算法设计

算法1：循环坐标下降算法

  1. 输入：样本协方差Σ̂，正则化参数λ，超结构E^{super}，拓扑排序O
  2. 主循环：按拓扑排序依次更新坐标
  3. 无环性检查：使用广度优先搜索检查DAG约束
  4. 间隔步骤：当支撑集出现次数达到阈值时，执行间隔步骤稳定算法行为

技术创新点

  1. 理论突破：首次为贝叶斯网络学习的坐标下降算法提供收敛性和最优性保证
  2. 算法设计：巧妙结合解析坐标更新、无环性检查和间隔步骤
  3. 拓扑排序：扩展现有理论处理异方差噪声情况
  4. 优化景观分析：深入刻画非凸问题的局部最小值性质

实验设置

数据集

  1. 合成数据：基于12个公开网络生成，节点数从6到413不等
  2. 真实数据：使用因果室（causal chambers）收集的物理系统数据，包含20个变量

评价指标

  • dcpdag：估计的完全部分有向无环图（CPDAG）与真实CPDAG之间的不同边数
  • 目标函数值：与最优解的相对差异
  • 计算时间：算法运行时间

对比方法

  • MICODAG：混合整数凸规划方法
  • CCDr-MCP：使用minimax凹惩罚的坐标下降
  • GES：贪婪等价搜索算法
  • NOTEARS：基于连续优化的方法
  • TD：自顶向下方法

实现细节

  • 超结构使用图lasso估计道德图
  • 正则化参数通过oracle调参选择最优值
  • 间隔步骤阈值C=5
  • 默认初始化Γ^{init} = I

实验结果

主要结果

1. 渐近最优性验证

对于10节点网络，随着样本量从100增加到3200：

  • CD-ℓ₀的目标值与最优解的相对差异趋于0
  • GES无法达到最优目标值
  • CD-ℓ₀在约0.1%的计算时间内获得近最优解

2. 基准比较（轻度异方差情况）

在噪声方差从{0.6,1,1.2}采样的设置下：

  • 小图(m≤20)：CD-ℓ₀与MICODAG性能相似，但速度快得多
  • 中等图(m>20)：MICODAG无法在时间限制内求解，CD-ℓ₀获得更准确的模型
  • 大图(m>100)：CD-ℓ₀在可扩展性方面表现优异

3. 具体性能数据

以Insurance(27)网络为例：

  • CD-ℓ₀: dcpdag=18.3±1.9, 时间≤1秒
  • MICODAG: dcpdag=18.5±8.5, 时间≥1350秒, RGAP=0.272
  • GES: dcpdag=24.2±7.9

消融实验

验证了不同随机排序对算法收敛性的影响，证实了理论结果的robustness。

实验发现

  1. ℓ₀惩罚的优势：相比MCP惩罚，确保等价DAG具有相同评分
  2. 拓扑排序的重要性：良好的初始排序显著提升性能
  3. 异方差鲁棒性：在轻度异方差条件下表现良好，但严重异方差时性能下降

相关工作

主要研究方向

  1. 基于约束的方法：PC算法及其扩展
  2. 基于评分的方法：动态规划、混合整数规划
  3. 混合方法：结合约束和评分方法
  4. 梯度方法：NOTEARS等连续优化方法

本文优势

  1. 相比约束方法：无需强忠实性假设
  2. 相比精确方法：计算效率高，可扩展性好
  3. 相比现有坐标下降：提供理论保证
  4. 相比梯度方法：收敛性和最优性保证更强

结论与讨论

主要结论

  1. 提出了首个具有最优性保证的贝叶斯网络学习坐标下降算法
  2. 证明了算法收敛到坐标最小值，且渐近达到最优目标值
  3. 实验验证了方法的可扩展性和高质量解

局限性

  1. 异方差敏感性：在严重异方差条件下，拓扑排序恢复困难，影响性能
  2. 排序依赖性：不同排序可能导致不同的马尔可夫等价类
  3. 样本复杂度：理论保证需要相当大的样本量

未来方向

  1. 收敛速度：刻画算法的收敛速度
  2. 块坐标更新：通过更新变量块提高计算效率
  3. 统计一致性：建立算法的统计一致性保证
  4. 改进样本复杂度：降低样本量要求和收敛率

深度评价

优点

  1. 理论贡献显著：首次为该问题的坐标下降算法提供严格的理论分析
  2. 方法设计巧妙：有效结合解析更新、约束检查和稳定化技术
  3. 实验充分：涵盖合成和真实数据，对比方法全面
  4. 写作清晰：数学推导严谨，算法描述详细

不足

  1. 实用性限制：对拓扑排序质量的依赖可能限制实际应用
  2. 假设条件：近似同方差噪声的假设在实践中可能不满足
  3. 计算复杂度：未提供详细的计算复杂度分析
  4. 统计保证：缺乏有限样本的统计一致性保证

影响力

  1. 理论价值：为非凸优化在结构学习中的应用提供新视角
  2. 实用价值：可作为现有混合整数规划方法的warm start
  3. 可复现性：提供开源实现，便于验证和扩展

适用场景

  1. 中大规模网络：特别适合节点数在20-400范围的网络
  2. 高斯数据：适用于连续观测数据
  3. 计算资源受限：当精确方法计算成本过高时的替代方案

参考文献

本文主要参考了以下重要工作：

  1. van de Geer & Bühlmann (2013): ℓ₀惩罚最大似然的统计性质
  2. Hazimeh & Mazumder (2020): 坐标下降的收敛性分析框架
  3. Chen et al. (2019): 拓扑排序恢复算法
  4. Xu et al. (2024): 混合整数规划方法

总体评价：这是一篇高质量的理论与应用并重的论文，在贝叶斯网络学习领域做出了重要贡献。理论分析严谨，实验验证充分，为该领域的进一步发展奠定了坚实基础。