改进因果发现算法，更快更准还支持先验知识
Less Greedy Equivalence Search
- 不盲目贪心，只在必要时添加边，提升搜索效率
- 实测速度提升10倍，结构误差显著降低
- 可融合先验知识并自动纠正错误，适合真实数据
贪心等价搜索（GES）是经典的基于评分的因果发现算法，在样本极限下能恢复描述数据的马尔可夫等价类。但实际应用中面临计算成本高和有限样本精度低的问题。本文提出少贪心等价搜索（LGES），在保持理论保证的同时部分解决上述问题。LGES修改贪心步骤：仅当得分不暗示条件独立时才插入边，使搜索更精准。该方法实现最高10倍的速度提升，结构误差显著减少。此外，LGES可利用先验知识引导搜索，并在数据矛盾时自动修正；还能使用干预数据优化观测等价类。我们证明了在样本极限下，即使先验知识错误，LGES仍能恢复真实等价类。实验表明，LGES在速度、准确性和对错误先验的鲁棒性上均优于GES及其他基线。代码已开源：https://github.com/CausalAILab/lges。
原文摘要 · Abstract (English)
Greedy Equivalence Search (GES) is a classic score-based algorithm for causal discovery from observational data. In the sample limit, it recovers the Markov equivalence class of graphs that describe the data. Still, it faces two challenges in practice: computational cost and finite-sample accuracy. In this paper, we develop Less Greedy Equivalence Search (LGES), a variant of GES that retains its theoretical guarantees while partially addressing these limitations. LGES modifies the greedy step; rather than always applying the highest-scoring insertion, it avoids edge insertions between variables for which the score implies some conditional independence. This more targeted search yields up to a \(10\)-fold speed-up and a substantial reduction in structural error relative to GES. Moreover, LGES can guide the search using prior knowledge, and can correct this knowledge when contradicted by data. Finally, LGES can use interventional data to refine the learned observational equivalence class. We prove that LGES recovers the true equivalence class in the sample limit, even with misspecified knowledge. Experiments demonstrate that LGES outperforms GES and other baselines in speed, accuracy, and robustness to misspecified knowledge. Our code is available at https://github.com/CausalAILab/lges.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。