改进因果发现算法，更快更准识别变量间关系。
Extremely Greedy Equivalence Search
- 新算法XGES优先删边而非加边，避免陷入局部最优。
- 在模拟数据上准确率超传统方法，速度提升10倍。
- 适合需要高效可靠因果推断的研究者使用。
因果发现的目标是从数据中学习有向无环图。经典方法贪心等价搜索（GES）通过增量贪婪地添加或删除边来最大化模型选择准则，在无限数据下具有理论保证，但在有限数据下常失效。本文分析了GES失败原因，发现其易陷入局部最优，尤其在密集图中。为此提出xGES，采用新启发式策略：早期优先删除边，降低陷入局部最优风险，同时保持原有理论性质。还给出了XGES和GES的高效算法实现。在已知真实结构的模拟数据集上测试，XGES在恢复正确图结构方面持续优于GES，且速度提升10倍。Python与C++实现代码已开源。
原文摘要 · Abstract (English)
The goal of causal discovery is to learn a directed acyclic graph from data. One of the most well-known methods for this problem is Greedy Equivalence Search (GES). GES searches for the graph by incrementally and greedily adding or removing edges to maximize a model selection criterion. It has strong theoretical guarantees on infinite data but can fail in practice on finite data. In this paper, we first identify some of the causes of GES's failure, finding that it can get blocked in local optima, especially in denser graphs. We then propose eXtremely Greedy Equivalent Search (XGES), which involves a new heuristic to improve the search strategy of GES while retaining its theoretical guarantees. In particular, XGES favors deleting edges early in the search over inserting edges, which reduces the possibility of the search ending in local optima. A further contribution of this work is an efficient algorithmic formulation of XGES (and GES). We benchmark XGES on simulated datasets with known ground truth. We find that XGES consistently outperforms GES in recovering the correct graphs, and it is 10 times faster. XGES implementations in Python and C++ are available at https://github.com/ANazaret/XGES.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。