【NeurIPS2021】存在潜在变量和选择偏差的递归因果结构学习

我们考虑了在存在潜在混淆变量和选择偏差的情况下，从观测数据中学习系统的因果MAG(Maximal Ancestral Graph)的问题。基于约束的方法是解决这一问题的主要方法之一，但现有方法在处理大型图时要么计算代价太高，要么缺乏完整性保证。我们提出了一种新的计算有效的递归约束方法，是健全和完整的。我们方法的关键思想是，在每次迭代中标识和删除特定类型的变量。这使我们能够高效地递归地学习结构，因为这种技术既减少了所需的条件独立(CI)测试的数量，又减少了条件集的大小。前者大大降低了计算复杂度，而后者产生了更可靠的CI测试。我们提供了最坏情况下所需CI测试数量的上限。据我们所知，这是文献中最紧的上界。我们进一步提供了任何基于约束的方法所需的CI测试数量的下界。在最坏的情况下，我们所提出的方法的上界和下界最多相差一个等于变量数的因子。我们也通过模拟与真实实验对提出的方法与当前最优算法进行了比较。

https://arxiv.org/abs/2110.12036