ICML24麻省理工提出使用更少的条件独立性测试来发现因果关系新方法

【摘要】众多科学领域的核心问题围绕着理解因果关系这一基本问题。然而,大多数基于约束的因果发现算法,包括广受欢迎的PC算法,通常会进行指数级数量的条件独立性(CI)测试,在各种应用中造成局限。为解决这一问题,我们的工作重点是表征在减少CI测试数量的情况下,可以了解潜在因果图的哪些信息。我们证明,学习一个隐藏因果图的更粗糙表示只需多项式数量的测试。该更粗糙表示,称为因果一致分区图(CCPG),包括顶点的分区和在其组件上定义的有向图。CCPG满足方向的一致性以及倾向于更细分区的附加约束。此外,当因果图是可识别的时,它会退化为潜在的因果图。因此,我们的结果提供了第一个有效的算法,可在特殊情况下仅用多项式数量的测试恢复真实的因果图,其中因果图完全可通过观察数据识别,并可能包含额外的干预。

原文：Causal Discovery with Fewer Conditional Independence Tests
地址：未知
代码：https://github.com/uhlerlab/CCPG
出版：2024 ICML
机构: 布罗德研究所、麻省理工学院
欢迎关注“码农的科研笔记”公众号

1 研究问题

本文研究的核心问题是: 如何在减少条件独立性测试数量的情况下,还原隐藏的因果关系图结构。
::: block-1
在医疗健康领域,人们希望理解各种生物标志物、环境因素、治疗手段等之间的因果关系。传统方法如PC算法,虽然能够还原因果图,但需要进行海量的条件独立性测试,计算开销巨大。假设有1000个变量,即便平均每个变量只与其他10个变量有联系,PC算法也可能需要进行2^10量级的测试。这使得它在处理大规模因果发现问题时捉襟见肘。
:::
本文研究问题的特点和现有方法面临的挑战主要体现在以下几个方面:

条件独立性测试的数量通常随节点度数的增长呈指数爆炸,严重制约了现有因果发现算法的计算效率和可扩展性。
因果方向的确定往往需要借助额外的干预实验数据,进一步增加了算法的数据成本。仅利用观测数据通常只能得到马尔可夫等价类。
在样本量不足的情况下,条件独立性测试的结果容易出现偏差,导致因果图的学习产生错误。测试次数越多,总体的错误风险也就越高。

针对这些挑战,本文提出了一种高效且鲁棒的"因果一致分区图(CCPG)"思路:
::: block-1
CCPG通过适当放松学习目标,用多项式数量的测试还原一个因果图的粗粒度近似。它将变量划分为若干个不相交的组,并学习这些组之间的因果关系。组内部的因果结构则暂时忽略。这种做法就像先画出国家之间的关系图,而将省市内部的连接抽象掉。通过聚焦组层面的因果关系,CCPG 极大地减少了所需的条件独立性测试数量。同时,CCPG 中的每个组仍保留了一定的因果方向信息,避免完全退化为无向图。这些性质使得 CCPG 在计算效率和信息丰富性之间取得了很好的平衡。此外,当真实的因果图能够从观测数据中唯一确定时,CCPG 会自动退化为它,确保了结果的准确性。若再辅以适当的干预数据,CCPG 同样能用多项式数量的测试学得完整的因果图。CCPG 巧妙地利用因果图的稀疏性进行化简,同时又能充分利用干预数据的信息,为大规模因果结构学习开辟了一条新的道路。
:::

2 研究方法

本文提出了一种通过学习因果一致性划分图(Causally Consistent Partition Graph, CCPG)表示来揭示因果结构的方法。该方法能够在进行较少的条件独立性检验的情况下，有效地发现因果关系。下面将详细介绍构造CCPG表示的整个过程。

2.1 前缀顶点集的构造

要构造CCPG表示，首先需要找到图中的前缀顶点集。直观上，前缀顶点集是图中排在前面的一些节点的集合，这些节点不能被后面的节点所指向。形式化地，节点集 $S$ 是前缀顶点集，当且仅当对于任意 $v\in S$ ，都有 $\text{Anc}(v)\cap\overline{S}=\emptyset$ ，其中 $\overline{S}$ 表示节点集 $V\setminus S$ 。

为了构造前缀顶点集，文中提出了一种启发式的方法。具体来说，就是先找到一个前缀顶点集 $S$ （初始时可以为空集），然后通过排除以下三类节点来得到一个更大的前缀顶点集 $S^{'}$ ：

$D_S$ ：通过条件独立性检验 $u\perp v|S$ 和 $u\not\perp v|S\cup\{w\}$ 可以推断 $v$ 不是 $w$ 的后代。 $D_S$ 就是所有这样的节点 $w$ 的集合。直观上， $D_S$ 中的节点有可能是 $\overline{S}$ 中某个节点的后代，因此将其排除。
$E_S$ ：类似地，通过条件独立性检验 $u\perp v'|S\cup\{v\}$ 和 $u\not\perp v'|S\cup\{v,w\}$ 可以推断 $w$ 在学习因果关系时可能引入错误。 $E_S$ 就是所有这样的节点 $w$ 的集合。
$F_S$ ：通过条件独立性检验 $u\not\perp v|S$ ， $u\perp w|S\cup\{v\}$ 和 $v\not\perp w|S$ 可以推断 $v$ 不是 $w$ 的后代。 $F_S$ 就是所有这样的节点 $w$ 的集合。排除 $F_S$ 是为了避免 $S^{'}$ 中包含太多节点。

通过排除上述三类节点，就可以得到一个更大的前缀顶点集 $S^{'}$ 。此外，文中还证明了 $S^{'}$ 中包含了 $\overline{S}$ 中所有的源节点（即入度为0的节点）。排除法这个可以借鉴。

2.2 CCPG表示的构造

有了前缀顶点集的构造方法，我们就可以进一步地构造CCPG表示了。CCPG表示由两部分组成：

将节点划分为若干个不相交的组件 $V_1,\dots,V_k$ ；
构造组件之间的有向无环图 $D$ ，其中 $D$ 中的边 $V_i\rightarrow V_j$ 表示 $V_i$ 中存在节点指向 $V_j$ 中某个节点。

构造CCPG表示的过程如下。首先，从空集开始，通过前缀顶点集的构造方法来不断扩大前缀顶点集，直到其为整个节点集 $V$ 。这样，我们就得到了一个前缀顶点集序列 $\emptyset\subsetneq S_1\subsetneq S_2\subsetneq \dots \subsetneq S_m=V$ 。

接下来，对于每个 $S_i\setminus S_{i-1}$ ，我们将其进一步划分为几个不相交的组件。直观上，如果 $S_i\setminus S_{i-1}$ 中的两个节点在给定 $S_1\cup\dots\cup S_{i-1}$ 的条件下不独立，那么它们就属于同一个组件。通过这种方式，我们就得到了节点的一个划分 $V_1,\dots,V_k$ 。可以证明，每个组件要么只包含一个节点，要么包含一条需要通过干预才能确定方向的边。

最后，我们再来构造组件之间的有向无环图 $D$ 。对于两个组件 $V_i$ 和 $V_j$ （ $i < j$ ），如果 $V_i\not\perp V_j|V_1\cup\dots\cup V_{j-1}$ ，那么我们就在 $D$ 中连一条边 $i\rightarrow j$ 。可以证明，通过这种方式构造出的 $D$ 是一个有向无环图，且与原图的因果关系是一致的。

综上，通过上述过程，我们就构造出了图 $G$ 的CCPG表示 $(V_1,\dots,V_k,D)$ 。

举个例子，假设有一个5个节点的有向无环图，其中节点1,2,3为源节点。通过前缀顶点集的构造过程，我们可以依次找到前缀顶点集 ${1\},\{1,2\},\{1,2,3\},\{1,2,3,4\},\{1,2,3,4,5\}$ 。然后我们对每个 $S_i\setminus S_{i-1}$ 进行划分，可以得到 ${\{1\},\{2\},\{3\},\{4\},\{5\}\}$ 。最后，通过条件独立性检验，我们得到 $D$ 中的边 $\{1,2,3\}\rightarrow 4$ 和 $\{1,2,3\}\rightarrow 5$ 。这就是该图的CCPG表示。

2.3 引入干预的扩展

上面介绍的方法都是在没有干预的情况下，即只根据观测数据来构造CCPG表示。而在引入干预的情况下，我们其实可以进一步细化CCPG表示。这是因为一个干预操作会切断某些因果边，使得一些原本不确定方向的边变得确定。（干预方法带来更好的因果发现）

为了将CCPG表示的构造方法扩展到引入干预的情况，文中对前缀顶点集的构造方法进行了一些改进。除了排除 $D_S,E_S,F_S$ 这三类节点外，文中还引入了第四类节点 $J_S^I$ 。直观上， $J_S^I$ 中的节点要么是干预集 $I$ 中节点的后代，要么虽然是 $I$ 中某个节点 $v$ 但存在某个不属于 $S$ 的节点 $u$ 使得 $u$ 和 $v$ 在给定 $V\setminus \text{Des}(I\setminus S)$ 的条件下不独立。通过排除这四类节点，我们就得到了引入干预情况下的前缀顶点集 $S^{'}$ 。

有了新的前缀顶点集构造方法，我们就可以类似地构造引入干预情况下的CCPG表示了，记为I-CCPG。与CCPG表示类似，I-CCPG表示也由节点的一个划分 $V_1,\dots,V_k$ 和组件之间的有向无环图 $D$ 组成，且满足每个组件要么只包含一个节点，要么包含一条不受干预影响的需要通过干预才能确定方向的边。此外，图 $D$ 也与原图的因果关系是一致的。

继续上面的例子，假设我们在节点4上进行干预。根据新的前缀顶点集构造方法，我们可以依次找到前缀顶点集 ${1\},\{1,2\},\{1,2,3\},\{1,2,3,4\},\{1,2,3,4,5\}$ 。与未引入干预的情形不同的是，节点5不再属于 $J_{\{1,2,3\}}^I$ ，因此 $S_4$ 为 ${1,2,3,5\}$ 。然后我们对每个 $S_i\setminus S_{i-1}$ 进行划分，可以得到 ${\{1\},\{2\},\{3\},\{5\},\{4\}\}$ 。最后在 $D$ 中连边，得到 $\{1,2,3\}\rightarrow\{5\},\{5\}\rightarrow\{4\},\{1,2,3\}\rightarrow\{4\}$ 。这就是引入干预情况下的I-CCPG表示，可以看到其比未引入干预情况下的CCPG表示更加精细。

以上就是本文提出的在较少条件独立性检验情况下构造CCPG表示的方法，以及将其扩展到引入干预情况下的I-CCPG表示的方法。通过CCPG表示，我们可以揭示原因果图的很多结构信息。当原因果图可以被观测数据或额外的干预完全确定时，所构造的CCPG表示将退化为原因果图本身。此外，所提出的构造方法的样本复杂度和计算复杂度都是原因果图规模的多项式，远低于已有的因果结构学习方法。

3 实验

3.1 实验场景介绍

该论文提出了一个高效的因果发现算法CCPG,可以用多项式数量级的条件独立性检验来恢复因果图的一个粗粒度表示。实验部分主要验证CCPG在合成和实际数据集上的运行效率和性能。

3.2 实验设置

Datasets:
- 合成数据:线性高斯加性噪声模型生成的可识别因果图,特别是星形DAG,节点数10到100
- 实际数据:6变量Airfoil数据集
Baseline: 基于条件独立性检验的因果发现方法PC、FCI、RFCI(约束)、GSP(混合)
Implementation details:
- PC、GSP用Python实现,FCI、RFCI用R和C++加速实现
- 合成数据上对比实验中,每个规模运行5次取平均
metric:
- 运行时间
- 恢复真实因果图所需的最少样本数

3.3 实验结果

3.3.1 实验一、不同图规模下运行时间对比

目的：评估CCPG在不同规模因果图上相比其他方法的计算效率优势
涉及图表：图6
实验细节概述：在节点数从20到100的星形DAG上,用10万样本对比CCPG与基线方法的运行时间
结果：

CCPG与混合方法GSP速度相当,远快于约束方法PC、FCI等
约束方法在节点数超过20时耗时剧增,难以应用于更大规模

3.3.2 实验二、样本复杂度对比

目的：评估CCPG恢复真实因果图所需的样本数与其他方法的优劣
涉及图表：图7
实验细节概述：在10节点星形DAG上,计算每个方法需要的最少样本数才能恢复出真实图,重复5次
结果：

CCPG所需样本数最少,约束方法次之,混合方法最多
CCPG在保证多项式数量级条件独立性检验的同时,样本复杂度和计算复杂度均优于其他方法

3.3.3 实验三、实际数据集上CCPG与PC学习因果图的对比

目的：在Airfoil实际数据集上对比CCPG学到的粗粒度因果表示与PC学到的更细粒度但不完整的因果图
涉及图表：图8、图9
实验细节概述：在6变量Airfoil数据集上运行CCPG和PC,并对比学到的因果图
结果：

尽管CCPG学到的是更粗粒度的因果表示,但更符合已知的部分因果关系
PC学到的因果图包含更多细节,但缺失了一些重要的因果边

4 总结后记

本论文针对因果结构学习中条件独立性测试开销过高的问题,提出了一种高效的算法,通过多项式数量级的条件独立性测试,学习一个因果图的粗粒度表示(CCPG)。该表示由顶点的一个划分以及定义在划分组件上的有向无环图组成,并满足一定的一致性和优先更细粒度划分的性质。论文证明了在特定情况下,所提算法能够通过多项式数量级的条件独立性测试准确恢复真实的因果图。
::: block-2
疑惑和想法：