arXiv:2409.14593v1 公告类型: 交叉 摘要: 在观察数据中测试假设的因果模型是许多因果推断任务的关键前提。一种自然的方法是测试模型中假设的条件独立关系（CIs）是否在数据中成立。虽然一个模型可以假设关于变量数量的指数级多的CIs，但测试所有这些CIs既不切实际也不必要。因果图以多项式空间编码这些CIs，产生了局部马尔可夫性质，使得模型测试可以通过显著较小的CIs子集进行。基于局部性质的模型测试需要一种算法来列出相关的CIs。然而，在存在隐藏变量和非参数分布的现实设置中，现有算法即使在生成单个CI约束时也可能需要指数时间。在本文中，我们引入了带有隐藏变量的因果图的c-组件局部马尔可夫性质（C-LMP）。由于C-LMP仍然可以调用指数数量的CIs，我们开发了一种多项式延迟算法，以多项式时间间隔列出这些CIs。据我们所知，这是第一个能够在因果图中对隐藏变量进行多项式延迟测试CIs的算法，适用于任意数据分布。对真实世界和合成数据的实验证明了我们算法的实用性。