Causal Discovery with Fewer Conditional Independence Tests

许多科学问题都围绕着理解因果关系这一基本问题。然而，大多数基于约束的因果发现算法，包括著名的 PC 算法，往往会产生指数级的条件独立性 (CI) 测试，从而在各种应用中存在限制。针对这一问题，我们的工作重点在于确定在减少 CI 测试数量的情况下可以学到什么关于潜在因果图的信息。我们展示了可以用多项式数量的测试学习到潜在因果图的更粗糙表示方法。这种更粗糙的表示方法被命名为因果一致划分图 (CCPG)，由顶点的一个划分和在其组件上定义的有向图组成。CCPG 满足方向的一致性和有利于更细的划分的附加约束。此外，当因果图可识别时，它会还原为底层的因果图。因此，我们的结果提供了第一个使用多项式数量的测试恢复真实因果图的有效算法，特别是在因果图可以通过观察数据和可能的附加干预完全识别的特殊情况下。

减少条件独立性测试的数量，探索如何使用多项式数量的测试学习潜在因果图的粗略表示。

提出了一种名为Causal Consistent Partition Graph（CCPG）的方法，它由顶点的分区和其组件上定义的有向图组成，满足方向一致性和其他约束条件，有助于更细的分区。当因果图是可识别的时，它会缩小到潜在因果图。

本文提供了第一个有效的算法，可以在多项式数量的测试中恢复真实的因果图，特别是在因果图通过观察数据和可能的干预完全可识别的特殊情况下。实验使用了合成数据和真实数据集，证明了CCPG方法的有效性。

相关研究包括因果发现算法，如PC算法和GIES算法，以及其他减少条件独立性测试数量的方法，如CFCI算法和RFCI算法。