Clustering and Pruning in Causal Data Fusion¶
作者: Otto Tabell, Santtu Tikka, Juha Karvanen
来源: JMLR
主题: 因果推断
相关性: 8/10
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么¶
本文所处的子方向是因果数据融合(causal data fusion)中的识别问题。其根本科学问题是:当研究者手头有多个数据集(例如一个观测性研究、一个随机对照试验),且这些数据集覆盖的变量集合不完全相同、采集条件也不一致时,如何判断某个因果量(如 p(y|do(x)))能否被唯一确定,并给出相应的识别公式。该方向的成熟度处于"理论框架已建立、但计算与规模化工具不足"的阶段:do-calculus 提供了通用的判定框架,但直接应用在变量数较多时会遭遇组合爆炸。
发展脉络¶
- 奠基工作:Pearl (1995) 提出 do-calculus 的三条规则,为因果效应识别提供了公理化基础;Shpitser and Pearl (2006) 与 Huang and Valtorta (2006) 证明了 do-calculus 在单一观测数据源场景下的完备性,即"若一个因果效应能被识别,则存在一条 do-calculus 推导路径"。
- 主要进展(单一数据源简化):Tikka and Karvanen (2018) 提出"剪枝"(pruning)操作,在单一观测数据源下,给出了移除与目标因果效应无关的变量的充分条件,并证明剪枝不改变可识别性。Tikka et al. (2023) 进一步引入"transit cluster"(传递簇)概念,证明在特定条件下可将多个变量合并为一个簇变量而不改变可识别性,并给出了寻找所有 transit cluster 的高效算法。
- 主要进展(多数据源识别):Tikka et al. (2021) 提出 do-search 算法,将 do-calculus 推广到多数据源场景,能自动搜索识别路径;Kivva et al. (2022) 修正了 g-identifiability 的完备性证明,指出原算法在正性假设缺失时可能不 sound,并给出了修正版本;Lee et al. (2024) 提出了在系统性选择偏差下进行数据融合的通用识别算法。
- 当前 frontier:多数据源场景下 do-calculus 的完备性仍属未知(本文第 8 节明确承认这一点);同时,识别算法的计算复杂度随图规模增长迅速,缺乏系统性的图简化工具。
- 本文位置:本文是上述两条线索(剪枝/聚类与多数据源识别)的汇合——将 Tikka and Karvanen (2018) 的剪枝和 Tikka et al. (2023) 的 transit cluster 从单一数据源推广到多数据源场景,并给出识别公式的迁移定理。
子线索聚类¶
- 单一数据源下的图简化:Tikka and Karvanen (2018) 的剪枝、Tikka et al. (2023) 的 transit cluster 与结构鲁棒性。这条线索的核心问题是"哪些变量可以安全地删掉或合并"。
- 多数据源下的识别算法:Tikka et al. (2021) 的 do-search、Kivva et al. (2022) 的修正 g-identifiability、Lee et al. (2024) 的系统性选择偏差处理。这条线索的核心问题是"给定一组输入分布,目标因果量是否可识别"。
- 数据融合的应用场景:Bareinboim and Pearl (2016) 的传输性问题、Colnet et al. (2024) 关于 RCT 与观测数据结合的综述、Li et al. (2020) 的汇总统计量融合方法。这条线索更贴近实际数据分析,关注的是"哪些数据组合起来能回答什么问题"。
这个方向在追问的核心问题¶
- 完备性:多数据源场景下,do-calculus 是否完备?即"若一个因果效应在数学上可识别,是否总存在一条 do-calculus 推导路径"?(本文第 8 节明确说"尚不清楚")
- 计算可行性:如何降低识别算法的计算复杂度?本文的剪枝与聚类正是对此的回应——通过减少变量数来缩小搜索空间。
- 识别公式的迁移:在小图上得到的识别公式,如何"翻译"回原图?本文定理 20、21 给出了答案。
⚠️ 作者的 framing(这是作者的说法)¶
作者将缺口 frame 成:"虽然剪枝和聚类在单一数据源下已有理论保证,但多数据源场景下缺乏系统性的图简化工具,导致 do-search 等算法在大图上不可用。" 因此本文是"显然的下一步"。作者淡化的竞争路线包括:(1) 直接改进 do-search 的搜索策略而非预处理(本文未讨论);(2) 利用代数或数值方法近似判定可识别性(本文未涉及)。值得去查的问题:为什么作者没有讨论将剪枝/聚类嵌入 do-search 的搜索循环中,而只作为预处理步骤?这是否意味着存在"剪枝后图可识别但原图不可识别"的反例?
张力¶
未见明显对立引用。但注意 Kivva et al. (2022) 对 Lee et al. (2020b) 的 g-identifiability 算法提出了修正,这属于"同一问题上的算法修正"而非"结论冲突"。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据¶
- 因果图:
G(V ∪ U),其中V是内生变量(可观测),U是外生变量(不可观测,即误差项)。有向边表示直接因果作用。 - 目标量:
p(y|do(x))——对X施加干预do(x)后,Y的分布。这是** estimand**(要估计的目标),不是直接可观测的量。 - 输入分布:
I = { p(a_i | do(b_i), c_i) },其中a_i是测量变量,b_i是干预变量,c_i是条件变量。这些是可观测数据(或可由可观测数据估计的量)。注意:a_i, b_i, c_i三者互不相交,且a_i ∪ b_i ∪ c_i ⊆ V。 - 识别:
p(y|do(x))在(G, I)下可识别,当且仅当对任意两个与G兼容且产生相同输入分布I的模型M1, M2,都有p1(y|do(x)) = p2(y|do(x))。 - 剪枝:从
G中删除变量集W,得到G',同时将输入分布限制到剩余变量上。 - 聚类:将变量集
T合并为一个新变量T,得到G',同时将输入分布中所有T的成员替换为T。 - Transit cluster:满足特定条件的变量集
T,使得聚类后G'中T的父节点 = 原图中T的外部父节点,T的子节点 = 原图中T的外部子节点,且T内部没有"信息泄漏"(具体条件见定义 13)。 - 识别不变性:若聚类/剪枝操作是识别不变的,则
p(y|do(x))在(G, I)中可识别 ⟺ 在(G', I')中可识别。
第二步:最小内核¶
核心命题(本文定理 17 的简化版):假设 T 是 G 中的一个 transit cluster,且输入分布 I 与 T 兼容(即 T 的成员在 I 中总是作为一个整体出现,不被拆分到不同的 a_i, b_i, c_i 中)。那么,将 T 聚类为单个变量 T 后,p(y|do(x)) 的可识别性不变。
为什么成立(直觉):Transit cluster 的关键性质是"信息只能从接收者流入、从发射者流出"。聚类后,T 作为一个整体,其外部连接(父节点、子节点)与原图中 T 的外部连接完全一致。因此,任何在 G 中能区分两个模型的 do-calculus 推导,在 G' 中也能区分(只需将 T 替换为 T);反之亦然。证明的技术难点在于:需要处理 T 内部存在多条路径的情况,以及输入分布中 T 的成员可能出现在不同位置(如 a_i 和 c_i)的情况。作者通过定义 14 的"兼容性"条件排除了后一种情况,并通过引理 15、16 建立了 G 与 G' 之间 d-分离的等价性。
最小例子:考虑图 4a 中的结构。S = {R, S1, S2, E1, E2} 是一个 transit cluster(R 是接收者,E1, E2 是发射者)。假设输入分布为 p(x, s) 和 p(y, s),其中 s 表示 S 中所有变量的取值。聚类后得到图 4b,其中 S 是一个单一变量。定理 17 告诉我们:p(y|do(x)) 在原图中可识别 ⟺ 在聚类后的图中可识别。这个例子的要点:S 内部的复杂结构(S1, S2 之间的相互作用)对 p(y|do(x)) 的识别是无关紧要的,可以安全地"打包"成一个变量。
为什么这个内核是核心:它揭示了因果识别中的一个重要现象——识别性只取决于变量之间的"宏观连接"(谁是谁的父节点、谁是谁的子节点),而不取决于"微观结构"(变量内部的相互作用)。这为大规模因果图的简化提供了理论基础。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:在多数据源因果融合场景下,如何通过剪枝(删除无关变量)和聚类(合并 transit cluster)来缩小因果图规模,同时保持目标因果效应的可识别性不变。
- 核心工具/方法:将单一数据源下的剪枝定理(Tikka and Karvanen 2018)和 transit cluster 聚类定理(Tikka et al. 2023)推广到多数据源场景,并设计了验证算法 VerifyInputs(算法 1)来检查聚类操作是否识别不变。
- 主要结论:给出了剪枝和聚类在多数据源下保持识别不变性的充分条件(定理 7、8、9、17、18、19),证明了识别公式的可迁移性(定理 20、21),并通过模拟实验展示了图简化能显著降低 do-search 的运行时间。
关键设定与假设¶
- 因果图:有向无环图(DAG),包含可观测变量
V和不可观测变量U(误差项)。允许不可观测的混杂因子(通过U中的多父节点表示)。 - 输入分布:
I = { p(a_i | do(b_i), c_i) },其中a_i, b_i, c_i互不相交。这是比"整个观测分布 + 整个实验分布"更一般的设定,允许部分重叠的变量集合。 - 正性假设:
p(v) > 0(定义 4),确保所有条件分布和干预分布良定义。 - 兼容性假设(定义 14):聚类时,要求每个输入分布中,
T的成员要么全部出现在a_i中,要么全部出现在b_i中,要么全部出现在c_i中,但不能跨类别拆分。这个假设排除了"部分变量被干预、部分被观测"的复杂情况。 - 与已有文献的对比:相比 Tikka and Karvanen (2018) 的单一数据源剪枝,本文允许
b_i非空(即存在实验数据);相比 Tikka et al. (2023) 的 transit cluster,本文允许输入分布是条件分布或干预分布,而非必须是整个观测分布。
主要结果¶
定理 7(剪枝非祖先):如果输入分布中没有任何变量是 Y 的后代,且 b_i ∪ c_i 不包含非祖先变量,则可以删除所有非 Y 祖先的变量,识别性不变。
定理 8(干预后剪枝):在 G = G[an⁺_G(Y) ∪ Y] 的前提下,可以删除在干预 do(x) 后与 Y d-分离的变量,识别性不变。条件 (a) 确保被删变量不是 X 的后代,(b) 确保输入分布不涉及被删变量,(c) 确保 X 之间的混杂结构不被破坏。
定理 9(剪枝孤立变量):如果一个变量集合 Z 只通过单个变量 W 与图的其余部分相连,且 Z 不包含 X 或 Y,则可以删除 Z,识别性不变。
定理 17(聚类识别不变性——正向):如果 T 是 transit cluster,输入分布兼容,且 p(y|do(x)) 在聚类后的图 G' 中可识别,则在原图 G 中也可识别。
定理 18(聚类识别不变性——反向):如果 p(y|do(x)) 在聚类后的图 G' 中不可识别,且 VerifyInputs 返回 TRUE,则在原图 G 中也不可识别。注意:这里需要 VerifyInputs 的额外条件,说明反向方向比正向方向更微妙。
定理 19(特殊 transit cluster):如果 transit cluster 的接收者集合与发射者集合有交集,则聚类对任何因果效应都是识别不变的。
定理 20、21(识别公式迁移):在聚类/剪枝后得到的识别公式,只需将 T 替换回 T 的成员(或将被删变量视为求和变量),即可得到原图的识别公式。
证明路线与技术技巧¶
- 整体路线:作者采用"构造性证明"策略。对于正向方向(聚类后可识别 ⟹ 原图可识别),直接构造识别公式的迁移(定理 21)。对于反向方向(聚类后不可识别 ⟹ 原图不可识别),采用反证法:假设原图可识别,则存在一个 do-calculus 推导序列;利用引理 15、16 将推导序列"投影"到聚类后的图上,得到聚类后也可识别的矛盾。
- 关键跳跃点:引理 16 是核心,它建立了
G和G'之间 d-分离的等价性。证明的关键在于处理T内部路径的"压缩":原图中经过T内部多条节点的路径,在G'中被压缩为经过T的单条路径。作者需要仔细验证压缩后路径的"阻塞"性质不变。 - 技术技巧:
- d-分离的逐路径分析:作者没有使用代数判定准则,而是回到 d-分离的定义,逐条分析路径。
- 构造性反例:在附录 D 中,作者构造了 VerifyInputs 条件不满足时聚类破坏识别性的具体例子,说明这些条件不是多余的。
- 模拟实验设计:算法 2 详细描述了随机生成因果图和输入分布的流程,确保生成的实例具有代表性(包含至少一个 transit cluster 和一个非祖先变量)。
真实例子与应用¶
本文包含两个真实数据例子:
-
婴儿死亡率研究(Filippidis et al., 2017):研究香烟价格对婴儿死亡率的影响。作者使用两个数据源:一个观测数据集(包含价格、教育、母亲年龄等),一个实验数据集(关于控烟政策的随机干预)。通过剪枝和聚类,将原始大图简化为小图,从而能够应用 do-search 判定
p(s|do(r))的可识别性,并得到识别公式。 -
动脉粥样硬化研究(Camelo et al., 2015,即 ELSA-Brasil):研究生命历程社会经济地位对颈动脉内膜中层厚度的影响。作者将
B(基线变量)、H(健康行为)、M(代谢指标)作为 transit cluster 处理,展示了聚类操作如何帮助判断p(y|do(l))的可识别性。
这两个例子的作用是验证方法的实用性:它们展示了在真实规模的因果图中,剪枝和聚类能够将 do-search 从"不可用"变为"可用"。
🔎 结论是否比证明窄¶
- 定理 7 的陈述:定理 7 要求"输入分布中
b_i ∪ c_i不包含非祖先变量"。但作者在证明中实际使用了更弱的条件(只需b_i ∪ c_i中的非祖先变量在干预后与Yd-分离)。因此,定理的陈述比证明所支持的要窄。作者在附录 A 中承认了这一点,但为了陈述简洁而保留了较强的条件。 - 定理 18 的陈述:定理 18 要求 VerifyInputs 返回 TRUE,但作者在附录 D 中展示了 VerifyInputs 返回 FALSE 时聚类仍可能保持识别性的例子。因此,VerifyInputs 是充分条件而非必要条件。作者在正文中明确承认了这一点,但未给出更弱的充分条件。
- do-calculus 完备性:本文所有结果都依赖于 do-calculus 的推导。作者在第 8 节明确说"do-calculus 在多数据源场景下是否完备尚不清楚",因此所有识别不变性结果都是相对于 do-calculus 而言的,而非绝对的数学识别性。
四、开放问题¶
- do-calculus 在多数据源场景下的完备性(扎根于第 8 节:"It remains an open question whether do-calculus is complete for the general causal effect identification problem")。这是本文最根本的开放问题——如果 do-calculus 不完备,那么"聚类后不可识别 ⟹ 原图不可识别"的结论可能只对 do-calculus 框架成立,而非绝对的数学事实。
- VerifyInputs 的完备性(扎根于附录 D 和定理 18 的陈述)。作者证明了 VerifyInputs 是 sound 的,但未证明其完备性。是否存在更弱的充分条件?能否给出 VerifyInputs 返回 FALSE 但聚类仍保持识别性的完整刻画?
- 剪枝与聚类的交互:本文分别讨论了剪枝和聚类,但未讨论两者的最优组合策略。是否存在一种情况,先聚类再剪枝比先剪枝再聚类更有效?能否给出最优预处理顺序的刻画?
- 条件因果效应的识别不变性:本文只考虑了边际因果效应
p(y|do(x))。对于条件因果效应p(y|do(x), z),剪枝和聚类的识别不变性条件是否需要修改?
提示:要确认上述问题是否是真 gap,建议去读以下文献的近期引用(各约 5 篇): - Tikka et al. (2021) 的 do-search 后续工作——看是否已有改进搜索策略的算法; - Kivva et al. (2022) 的修正 g-identifiability 后续工作——看是否已有完备性证明; - Bareinboim and Pearl (2016) 的传输性问题后续工作——看是否已有针对部分重叠变量的更一般框架。
Maintained by 陈星宇 · Homepage · Source on GitHub