大规模因果结构学习的分布式方法

DCILP：大规模因果结构学习的分布式方法

DCILP: A Distributed Approach for Large-Scale Causal Structure Learning

https://arxiv.org/pdf/2406.10481?

摘要：

因果学习处理的是估计因果图这一计算要求很高的任务。本文介绍了一种用于因果图学习的新分治方法，称为DCILP。在分治阶段，识别每个变量Xi的马尔可夫毯MB(Xi)，并且与每个MB(Xi)相关的因果学习子问题被独立地并行处理。这种方法受益于所考虑的数据样本数与变量数之间更有利的比例。相对地，它可能会受到隐藏混杂因素存在的不利影响，因为MB(Xi)外部的变量可能会影响其中的变量。在分治阶段生成的局部因果图的对账是一个具有挑战性的组合优化问题，尤其是在大规模应用中。DCILP的主要新颖之处在于将该对账表述为一个整数线性规划（ILP）问题，这是一种原创性的表述，它可以被委托给ILP求解器并高效处理。通过在中等至大规模图上的实验，以及与最先进方法的比较，DCILP在计算复杂度方面表现出显著改进，同时在真实世界问题上保持了学习精度，并且在合成问题上最多只遭受轻微的精度损失。

代码——https://github.com/shuyu-d/dcilp-exp

扩展版本——https://arxiv.org/abs/2406.10481

1 引言

从观测数据中发现因果关系，作为人工智能的一个重要问题而出现，具有基础性和实践性的动机（Pearl 2000；Peters, Janzing, and Schölkopf 2017）。一个显著的原因是，因果模型支持一些推理模式，例如反事实推理和算法追索（Tsirtsis et al. 2021），这些超出了基于相关性的模型所能达到的范围（Peters, Bühlmann, and Meinshausen 2016；Arjovsky et al. 2019；Sauer and Geiger 2021）。在因果发现和贝叶斯网络学习的文献中，有两类主要方法，即基于约束的方法（Spirtes et al. 2000；Meek 1995）和基于评分函数的方法（Chickering 2002a；Loh and Bühlmann 2014）（更多内容见第5节）。根据具体方法的不同，学习大规模因果图的策略包括将有向图的搜索空间限制为稀疏图的搜索空间（Ramsey et al. 2017；Loh and Bühlmann 2014），或者将潜在的组合问题转化为连续优化问题（Zheng et al. 2018；Aragam, Amini, and Zhou 2019；Ng, Ghassami, and Zhang 2020；Ng et al. 2021；Lopez et al. 2022）。尽管这些策略在降低复杂度方面带来了显著改进，但当变量数量和/或所寻求因果图的度数很高时，它们的可扩展性仍然有限。

为了更好地应对学习大规模因果结构中的计算挑战，越来越多的研究考虑将大规模因果发现问题分解为从变量子集定义的更小问题，并采用分治策略。这些变量子集可以是增量构建和细化的（Gao, Fadnis, and Campbell 2017）；它们可以基于层次聚类（Gu and Zhou 2020）、基于条件独立性检验的递归分解（Zhang et al. 2020），或者通过每个变量相关联的马尔可夫毯（在第2节中定义）（Tsamardinos et al. 2003; Wu et al. 2020, 2022, 2023; Mokhtarian et al. 2021）。一个主要挑战在于征服步骤中，即对分治步骤中识别出的部分解进行融合或对账；大多数征服方法基于规则，这限制了它们的适用性。

在本文中，我们提出了原创的基于整数线性规划的因果建模分治法（DCILP），以解决因果发现中固有的可扩展性挑战。形式上，DCILP由三个阶段组成：

所提出的DCILP的原创性贡献有两方面。首先，阶段2在设计上可并行化；它能够处理与每个马尔可夫毯相关联的因果发现子问题，这使其能够扩展到数千个变量。因果不充分性问题通过仅保留涉及马尔可夫毯中心变量的因果关系而得到缓解。其次，也是最重要的，我们展示了阶段2中学习到的因果子图的对账可以被表述为一个整数线性规划（ILP）问题并被高效求解。定义二元ILP变量来表示因果关系（原因、结果、配偶和v结构）；定义逻辑约束以强制其一致性，ILP变量的优化旨在找到一个因果图，使其尽可能接近所有局部子图的拼接，同时受一致性约束的约束。该ILP问题的求解可以委托给高效的ILP求解器。

总体而言，DCILP定义了一个灵活的框架，其中每个阶段可以使用不同的算法组件：（i）对于阶段1中的马尔可夫毯发现任务，我们遵循（Loh and Bühlmann 2014）的设置，将自己限制在线性结构方程模型（第2节）；（ii）对于阶段2中的因果发现子问题，我们考虑GES（Chickering 2002b）和DAGMA（Bello, Aragam, and Ravikumar 2022），因为它们是因果建模的两种代表性且高效的先进算法；（iii）对于阶段3，我们使用Gurobi ILP求解器（Gurobi Optimization 2025）。

本文组织如下。在第2节中介绍形式化背景之后，我们在第3节中描述DCILP。第4节介绍DCILP的实验设置和结果。第5节讨论DCILP相对于相关工作所处的位置。第6节总结全文并提出一些进一步工作的展望。

2 形式化背景

3 DCILP概述

在描述了DCILP核心的分治策略之后，本节详细介绍了用于对账局部因果图的整数线性规划方法。在本文的剩余部分，我们假设马尔可夫性质和因果充分性。

3.1 分治策略

如图1所示，DCILP是一个三阶段过程：

3.2 因果子图之间的冲突

在阶段2中发现的因果效应关系的朴素拼接，给出为：

3.3 通过ILP对账因果子图

3.4 改进ILP公式

3.5 讨论

4 实验

本节报告DCILP的实验验证，更多细节和补充结果请参考扩展版本（Dong et al. 2025）。

4.1 实验设置

目标。实验的主要目标是根据因果学习的标准SHD、TPR、FDR和FPR指标，以及其计算效率，来评估DCILP的性能。

第二个目标是评估DCILP阶段2中使用的因果学习器如何影响整体性能。我们报告DCILP-ges（分别地，DCILP-dagma）的性能，对应于在阶段2中使用GES（分别地，DAGMA）的DCILP。选择GES（Chickering 2002b）和DAGMA（Bello, Aragam, and Ravikumar 2022），后者被称为NOTEARS（Zheng et al. 2018）的显著改进，是因为它们是使用不同技术的两种代表性先进因果学习方法：GES是一种贪婪搜索方法（在大样本极限下最优），用于寻找CPDAG，而DAGMA是一种用于学习因果DAG的高效连续优化方法。DCILP-ges和DCILP-dagma针对GES和DAGMA基线进行评估；GOLEM（Ng, Ghassami, and Zhang 2020）和DAS（Montagna et al. 2023）也用于比较。我们还通过考虑DCILP（MB*）变体来检验阶段1性能对整体结果的影响，其中将真实马尔可夫毯提供给阶段2。

4.2 合成图上的结果

我们观察到，DAGMA几乎精确地恢复了潜在的DAG，TPR和FDR分别接近1和0。DCILP-dagma在所有问题维度 d d上相对于DAGMA在运行时间上取得了显著提升，同时在学习准确率上有适度损失（在SF3数据上中位TPR约0.9；中位FDR约0.2，在ER1数据上低于0.1）。然而，在非等噪声方差（NV）设置（Reisach, Seiler, and Weichwald 2021）中的补充结果表明，DCILP-ges在NV情况下比DAGMA稳健得多（图5）。更多细节见扩展版本（Dong et al. 2025）。

4.3 真实世界图上的结果

在MUNIN上（图6），DCILP-dagma和DCILP-ges与DAGMA相比（加速约270倍）以及与GES相比（加速约25倍）实现了运行时间的显著减少。同时，它们的学习准确率与DAGMA相当，并且显著优于GES；DCILP-dagma和DCILP-ges的SHD与DAGMA一起排名第一或第二；DAGMA、GES和DCILP-dagma的TPR相似，而DCILP-ges在均匀噪声下略逊一筹。

对于其他 n / d 比例和噪声类型，也观察到类似趋势（详情见Dong et al. 2025, Appendix D.6）。

4.4 阶段3中ILP的影响

5 相对于相关工作的定位

最相关的工作是（Gu and Zhou 2020）提出的分治策略，定义了划分、估计和融合（PEF）方法。划分步骤作为层次聚类算法进行。估计步骤包括估计与每个聚类相关联的DAG或CPDAG。PEF与DCILP的第一个区别在于划分阶段：在PEF中，变量被划分，而DCILP考虑重叠的马尔可夫毯。注意到两种方法都面临因果不充分性问题，DCILP阶段2中涉及的冗余可能带来更好的稳健性。PEF与DCILP的第二个也是最重要的区别在于征服阶段。PEF处理一个组合优化问题，在子图之间定义并选择最佳边，而DCILP依赖ILP求解来确保从局部因果图构建的全局因果图的一致性。

（Zhang et al. 2020）提出的一种自顶向下策略，针对CPDAG，通过递归地将变量集分裂为更小的子集来进行。相反，自底向上策略是（Gao, Fadnis, and Campbell 2017）提出的图增长结构学习（GGSL），针对贝叶斯网络。在这些方法中，一个主要目标是减少为引出整体因果结构所需的条件独立性检验的数量。另一个相关工作，尽管程度较小，是（Mokhtarian et al. 2021）提出的名为MARVEL的递归变量消除方法。与DCILP一样，MARVEL算法依赖于马尔可夫毯的识别，使用例如Grow-Shrink（GS）（Margaritis and Thrun 1999）、IAMB（Tsamardinos et al. 2003）或基于精度矩阵的方法（例如，Loh and Bühlmann 2014）。实践中的主要问题是，递归过程没有为从潜在早期错误中恢复提供空间。

6 结论

该方法的一个主要局限来自阶段1和阶段2中马尔可夫毯和局部因果关系的学习准确率，这需要足够的样本与变量比。

未来研究的一个途径是以更集成的方式考虑这三个阶段，例如，在阶段3的ILP目标中考虑阶段2中识别出的因果边的强度（而不是仅考虑这些边的存在性）。

另一个视角是利用阶段3中ILP求解器发现的多个解。例如，在多个ILP解中保留的因果关系可以用于定义期望因果图的骨干，从而以集成学习的精神扩展DCILP。一个更长期的视角是使用双线性函数来近似经过充分研究的因果评分（Loh and Bühlmann 2014），以便将阶段3从整数线性规划扩展到二次规划。

原文链接：https://arxiv.org/pdf/2406.10481?