引言
在因果推断中,因果发现是一个重要的目标,它旨在通过观察数据来揭示潜在的因果结构,即真实的因果图。然而,在缺乏干预数据的情况下,真实的因果图只能在其图形分离的基础上部分恢复。因果发现方法通常分为基于评分的方法和基于约束的方法,后者是本文关注的重点。基于约束的方法假设概率依赖结构能够很好地代表真实因果图的图形结构。一个常见的假设是“信忠性”,即数据生成分布中的每个条件独立关系都被真实因果图准确表示。在信忠性假设下,大多数基于约束的学习方法(如 PC 和 SGS 算法)被证明能够返回真实的因果图,尽管存在图形分离。然而,简单的例子表明,信忠性假设往往在实践和理论中容易被违反,因此可能过于严格。
近年来,为了放宽信忠性假设,出现了一些新的方法。例如,Raskutti 和 Uhler 提出的“稀疏排列”(SP)算法,以及 Sadeghi 和 Soo 提出的自然结构学习算法,这些算法在比信忠性更弱的假设下也能证明返回真实因果图的图形分离。本文旨在提供一个通用框架,以涵盖所有基于约束的因果学习算法的条件,并给出任何算法的条件。
约束因果学习的背景
在约束因果学习中,真实的因果图 G0 是我们希望从观察分布 P 中部分恢复的目标。因果学习算法的目标是从输入分布 P 输出图 G(P),如果输出图 G(P) 与真实因果图 G0 是马尔可夫等价的,那么算法就是一致的。从 P 中,我们主要关注条件独立性 J(P),通过假设条件独立性 Oracle 的可用性,我们始终知道给定的条件独立关系是否在分布中成立。
约束因果学习中的假设
在因果学习文献中,通常假设真实因果图与其观察分布之间存在关系。这些关系的成功依赖于假设的成立。最基本的关系是马尔可夫性质。马尔可夫性质表明,如果 P 是 G 的马尔可夫分布,那么所有的条件独立性关系都在图 G 中得到体现。信忠性则是一个更强的假设,表示图 G 中的所有条件独立性都能够在分布 P 中找到对应。
通用框架的定义
在本节中,我们将介绍一个通用框架,该框架允许我们通过占位符属性来表示任何基于约束的因果学习算法。给定一类图 G 和一个分布 P,我们定义属性 A(P, G) = ⊤,表示分布 P 满足属性 A 相对于图 G。如果我们能够识别出一个属性 A,使得输出图 G(P) 和输入分布 P 之间存在关系,那么我们就可以获得该算法的一致性条件。
框架的核心定理
根据框架的定义,如果属性 A 是类属性,并且对应于算法,则我们可以得出以下定理:
定理1:给定图类 G,设 A 是一个属性。考虑一个基于约束的因果学习算法,它从分布 P 输出图 G(P) ∈ G,使得 A(P, G(P)) = ⊤。如果 G0 ∈ G 是真实的因果图,则 A(P, G0) = ⊤ 且 UA(P) = ⊤ ⇒ 算法是一致的。
这个定理表明,只要我们能够识别出属性 A,并且它与真实因果图 G0 之间存在一致性条件,那么算法就会返回正确的因果图。
框架中的应用与实例
在这个框架下,我们可以通过不同的属性 A 来具体化一致性条件。比如,考虑“信忠性”作为属性 A,我们可以得出属性 A 和 UA(P) 的结合相当于 P 在 G 中的信忠性。
PC 算法的具体一致性条件
在基于约束的学习中,PC 算法是一个经典算法。根据不同的计算实现,PC 算法的方向规则可能会略有不同。我们可以利用框架中的定理,得出 PC 算法在不同方向规则下的必要和充分一致性条件。
例如,设定方向规则为:
- 如果 ∀ C ⊆ V \ {i, j} 使得 i ⊥⊥ j | C,则 k ∈ C,则将 i ∼ k ∼ j 赋值为非碰撞点;否则赋值为碰撞点。
- 如果 ∀ C ⊆ V \ {i, j} 使得 i ⊥⊥ j | C,则 k ̸∈ C,则将 i ∼ k ∼ j 赋值为碰撞点;否则赋值为非碰撞点。
通过这些方向规则,我们能够导出相应的属性 Vn,c,进而利用框架的定理得出以下结论:
命题6:设 P 为真实因果图 G0 的分布,V1, V2, V3 为各个方向规则对应的性质,则 VI(P, G0) = ⊤ ⇐⇒ 使用方向规则 I 的 PC 算法一致。
这一命题提供了 PC 算法一致性的充分和必要条件,且这些条件在文献中是首次被明确描述。
结论与未来工作
本文提出的基于约束的因果学习的通用框架为因果学习算法的一致性条件提供了理论基础。通过识别出属性 A,我们能够得到算法一致性的条件,从而提升因果发现的准确性。
未来的研究方向包括如何从 J(P) 中获得 Pearl 最小图的过程,以及探索如何将函数优化中的图作为生成的算法属性。通过这些研究,我们希望进一步提高因果学习算法的有效性和适用性。
参考文献
- Teh, K. Z., Sadeghi, K., & Soo, T. (2024). A General Framework for Constraint-based Causal Learning. arXiv:2408.07575.
- Spirtes, P., & Glymour, C. (1991). An algorithm for fast recovery of sparse causal graphs.
- Raskutti, G., & Uhler, C. (2018). Sparse Permutation algorithms for causal inference.
- Pearl, J. (2009). Causality: Models, reasoning, and inference.
- Forster, J., et al. (2018). Minimality assumptions in causal inference.
以上是根据您提供的文档撰写的文章。希望这篇文章能满足您的需求!如果您有任何具体的修改建议或其他要求,请告诉我!