提出QWO方法，让因果发现计算速度提升数十倍
QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs
- 用新算法快速构建基于排列的因果图结构
- 相比最优方法提速O(n²)，n为变量数
- 适合大规模因果关系挖掘任务
因果发现对理解科学领域中变量间关系至关重要。本文聚焦线性高斯无环模型（LiGAMs）中的基于排列的方法，其中排列编码了变量的因果顺序。现有方法因计算复杂度过高而难以扩展，主要包含两个部分：(i) 对给定排列π，构建特定有向无环图（DAG）$\mathcal{G}^π$，该图是在满足π约束下，从数据中能学习到的最佳结构；(ii) 在所有排列空间中搜索，以最小化$\mathcal{G}^π$的边数。我们提出QWO，一种显著提升给定排列π下$\mathcal{G}^π$计算效率的新方法。相较于最先进的基于BIC的方法，其速度提升达到$O(n^2)$（n为变量数），具有高度可扩展性。我们证明了该方法在理论上是合理的，并可集成到现有搜索策略如GRASP和基于爬山法的方法中，从而提升整体性能。
原文摘要 · Abstract (English)
Causal discovery is essential for understanding relationships among variables of interest in many scientific domains. In this paper, we focus on permutation-based methods for learning causal graphs in Linear Gaussian Acyclic Models (LiGAMs), where the permutation encodes a causal ordering of the variables. Existing methods in this setting are not scalable due to their high computational complexity. These methods are comprised of two main components: (i) constructing a specific DAG, $\mathcal{G}^π$, for a given permutation $π$, which represents the best structure that can be learned from the available data while adhering to $π$, and (ii) searching over the space of permutations (i.e., causal orders) to minimize the number of edges in $\mathcal{G}^π$. We introduce QWO, a novel approach that significantly enhances the efficiency of computing $\mathcal{G}^π$ for a given permutation $π$. QWO has a speed-up of $O(n^2)$ ($n$ is the number of variables) compared to the state-of-the-art BIC-based method, making it highly scalable. We show that our method is theoretically sound and can be integrated into existing search strategies such as GRASP and hill-climbing-based methods to improve their performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。