Uncertainty Quantification for Causal Discovery¶

讲者: Samuel Wang
讨论人: Daniel Malinsky
来源: OCIS (Online Causal Inference Seminar)
日期: 2022-06-28
主题: 因果推断
视频: https://youtu.be/YxgG35kDbR4 · 幻灯片

本页据讲座录音的自动转写（ASR）生成。人名 / 术语 / 公式 / 具体的率与界可能被听错，关键处请对照视频或讲者论文核对。

一、这场报告在讲哪条工作线¶

这场报告属于因果发现中的不确定性量化（Uncertainty Quantification for Causal Discovery）这一子方向。该方向追问的核心问题是：当我们从观测数据中估计出单一因果结构（DAG 或因果顺序）时，对此“点估计”的信任程度如何？哪些其他结构未被数据排除？

主流路线与奠基工作： - 因果发现的识别（identification）与相合性（consistency）已有大量工作，例如 LiNGAM 模型（Shimizu et al., 2006）、加性噪声模型（Hoyer et al., 2008; Peters et al., 2014）在非高斯性或非线性假设下实现了 DAG 的唯一可识别。但该领域在相合性之后，长期缺少一套系统性的不确定性量化（UQ）框架，即 “估计出结构之后，怎么给它一个频域置信集？”。 - 近年的少量工作开始关注结构的不确定性：Janková & van de Geer (2019)、Li et al. (2019)、Shi et al. (2021) 等对已知或可相合恢复的因果顺序下的参数或特定边做检验与置信区间；Peters et al. (2016) 提出了“祖先关系保守集”的概念，但未有可操作的统计推断框架。 - 另一条线与模型选择后的推断（post-selection inference）相关，但主要针对单个回归系数，而非整个图的置信集。

这场报告站在什么位置： - 它提出了一套可操作的频域框架，为整个因果顺序（causal ordering）（而非单个边或参数）构造置信集（confidence set），并证明该置信集即使在因果顺序无法被相合恢复的条件下仍然渐近有效。 - 该方法的基础是：对每个候选顺序 θ 进行拟合优度检验（goodness-of-fit test），通过检验“回归残差与预测变量独立”这一核心可检验蕴含（testable implication），然后将所有未被拒绝的顺序的集合作为置信集。 - 关键词：Wang, Samuel (Cornell)，合作者 Mladen Kolar (U. Chicago) 与 Mathias Drton (TU Munich)。该工作与 Drton 的前期工作 Wang & Drton (2019) 在检验统计量上有继承关系，也与 Schultheiss et al. (2021)、Sen & Sen (2014)、Shah & Bühlmann (2018)、Berrett & Samworth (2019) 的残差独立性检验有技术关联。

小结：该工作核心方法是将模型选择问题反转为一系列拟合优度检验，将不确定性量化为未被排除的顺序集合。这一思路在统计学其他领域（如回归模型选择、子集选择）有先例（如所罗门·泰伯茨（Tippett）最小值 p 值法），但用于因果发现是新的。

二、最小内核 / 一个最简例子¶

符号与模型¶

我们考虑一个线性结构方程模型（Linear SEM）：

\[Y_v = \sum_{u \in \text{pa}(v)} \beta_{v,u} Y_u + \varepsilon_v, \quad v = 1, \dots, p.\]

可观测：独立同分布样本 \( Y^{(i)} = (Y_1^{(i)}, \dots, Y_p^{(i)})^\top, i = 1, \dots, n \)。

参数：所有边的系数 \(\beta_{v,u}\)、噪声分布。

潜在/不可观测：真实 DAG \(G\)；真实的因果顺序（所有与 \(G\) 相符的拓扑序）集合 \(\Theta(G)\)。

目标：构造置信集 \(\hat{\Theta}(Y, \alpha)\)，使得

\[\lim_{n \to \infty} P\bigl( \hat{\Theta}(Y, \alpha) \cap \Theta(G) \neq \emptyset \bigr) \ge 1 - \alpha.\]

最简特例：\(p = 2\)，二值因果方向¶

设 \(p=2\)，变量为 \(A, B\)。两个可能的顺序：\(\theta_1: A \to B\)，\(\theta_2: B \to A\)。真实 DAG 为 \(A \to B\)，\(\Theta(G) = \{\theta_1\}\)。

关键可检验蕴含（基于非高斯误差）： - 若 \(\theta_1\) 正确（\(A\) 是 parent，\(B\) 是 child），则回归 \(B\) 在 \(A\) 上的残差 \(\eta_{B|A} = Y_B - \beta_{B,A} Y_A\) 应与 \(Y_A\) 独立（因为在模型中 \(\varepsilon_B \perp Y_A\)）。 - 若 \(\theta_2\) 正确（\(B\) 是 parent），则回归 \(A\) 在 \(B\) 上的残差应与 \(Y_B\) 独立。

如何构造置信集： 1. 对 \(\theta_1\)：用样本估计 \(\hat{\beta}_{B,A}\)，计算残差 \(\hat{\eta}_{B|A}\)。用条件自举法（residual bootstrap）检验 \(H_{0,\theta_1}: \hat{\eta}_{B|A} \perp Y_A\)，得到 p 值 \(\pi_{\theta_1}\)。 2. 对 \(\theta_2\) 同理得 \(\pi_{\theta_2}\)。 3. 置信集 \(\hat{\Theta} = \{ \theta : \pi_\theta \ge \alpha \}\)。

说明：当样本量足够时，正确的顺序 \(\theta_1\) 的 p 值应均匀分布（≥ α），错误的顺序 \(\theta_2\) 的 p 值应很小（< α），因此 \(\hat{\Theta}\) 以高概率包含 \(\theta_1\)。当信号弱（例如误差接近高斯、效应量小）时，\(\hat{\Theta}\) 可能同时包含两个顺序，从而如实反映了不确定性。

三、报告主体：讲者讲了什么¶

[0:00–0:03] 开场与背景¶

动机：Sachs et al. (2005) 的蛋白调控网络——该网络是生物学专家通过多年、大量实验得出的 consensus 网络，过程昂贵耗时。讲者指出这正是因果发现希望解决的场景：从观测数据中自动估计因果结构。
问题域划分：因果发现的三个层次——
识别（identification）：需要什么假设才能在总体层面唯一确定因果结构？
相合性（consistency）：如何从样本数据相合恢复结构？
不确定性量化（UQ）：点估计的可信度？哪些其他结构未被数据排除？
讲者强调经典文献到第2层基本结束，该工作填补第3层。

[0:03–0:10] 假设与识别基础¶

线性 SEM 假设：\(Y_v = \sum_{u\in\text{pa}(v)} \beta_{v,u} Y_u + \varepsilon_v\)，no unobserved confounding (\(\varepsilon_v \perp \varepsilon_u\))，非高斯误差保证唯一可识别（Shimizu et al., 2006）。非线性加性模型（Hoyer et al., 2008; Peters et al., 2014）也可处理，但报告基于线性简化。
bivariate 直观例子 [0:05–0:06]：两个变量 \(P \to C\)，真实机制 \(C = 0.5P + \varepsilon_C\)，误差为均匀分布。对比正确方向与反方向的散点图和残差图，展示正确方向的残差大约独立于 parent，而反方向虽 residual 零相关（OLS 一阶条件）但非独立（条件方差变化）。讲者承认该例子有简化（Q&A 部分指出异方差可能造成类似诊断）。

[0:10–0:17] 核心可检验蕴含：残差独立性¶

对任意节点 \(v\) 和预测变量集 \(U\)，定义总体残差 \(\eta_{v|U} = Y_v - d_{v,U}^\top Y_U\)。
关键命题（口语化陈述）：若 \(\text{pa}(v) \subseteq U \subseteq \text{nd}(v)\)（即 \(U\) 包含 \(v\) 的所有 parent 且不含 descendant），则 \(\eta_{v|U} \perp U\)；反之一般不成立。
注：讲者声明“this statement is not quite true” [0:16:23]，但有助于理解。

[0:17–0:27] 框架：拟合优度检验 + 反演¶

高层框架 [0:18–0:19]：对每个顺序 \(\theta\) 做拟合优度检验得 p 值 \(\pi_\theta\)；置信集 \(\hat{\Theta}(Y, \alpha) = \{\theta : \pi_\theta \ge \alpha\}\)。
为什么要关心这个集合 [0:19–0:21]：
若 \(\hat{\Theta}\) 为空 → 所有顺序都被拒绝 → 识别假设很可能不成立 → 应换方法。
若 \(\hat{\Theta}\) 很大 → 信号弱 → 点估计不可靠。
显式给出“未被数据排除的备选顺序”，辅助实验设计。
理论性质 [0:21–0:23]：若检验对任意真实顺序渐近有效，则

\[\lim_{n\to\infty} P(\hat{\Theta}(Y,\alpha) \cap \Theta(G) \neq \emptyset) \ge 1-\alpha。\]

通过先获得顺序置信集、再从每个顺序相合估计图，可得到图的置信集 [0:22–0:23]。
衍生效用 [0:23–0:26]：
保守的祖先关系集合 \(\hat{A} = \{(u,v): \theta(u)<\theta(v) \ \forall \theta \in \hat{\Theta}\}\)，以 \(1-\alpha\) 概率不含假阳性祖先关系。
联合使用 \(\hat{\Theta}\)（以 \(\alpha/2\)）与每个顺序下的参数置信区间（以 \(1-\alpha/2\)），通过取并集得到校正结构不确定性的效应置信区间（类似 Strieder et al., 2021 的思路）。

[0:27–0:37] 核心挑战：拟合优度检验（统计细节）¶

naïve 方案失败 [0:31–0:33]：先回归求残差 \(\hat{\eta}_{v|U}\)，再直接检验 \(\hat{\eta}_{v|U} \perp U\)——因为 \(\hat{\eta} = \varepsilon_v - (\hat{d} - d)^\top Y_U\)，即使零假设成立，估计残差仍包含 \(O_p(n^{-1/2})\) 的 \(Y_U\) 成分，导致任何对 \(n^{-1/2}\) 局部备择有检验力的独立性检验都会尺度失真（have improper size）。
已有方法 [0:33–0:36]：
Schultheiss et al. (2021)：用多项式型统计量 + 渐进正态分部，计算快但有限样本不准。
Sen & Sen (2014)：用 HSIC + residual bootstrap（joint over covariates and residuals），灵活但慢。
Shah & Bühlmann (2018)；Berrett & Samworth (2019)：用条件于 covariates 的 bootstrap，但实际中假设误差高斯。
讲者声称他们开发了新检验，兼具计算效率（多项式型统计量）与条件残差自举（获得较好有限样本性质且不假设高斯）——具体公式：\(\frac{1}{\sqrt{n}} \sum_i g(Y_{u,i})^\top \hat{\eta}_i\)，其中 \(g\) 是非线性函数（通常选多项式）。

[0:37–0:47] 检验策略与理论¶

结合 p 值 [0:37–0:38]：
对顺序 \(\theta\)，对每个 \(v=2,\dots,p\) 检验 \(H_{0,v}: \eta_{v|\text{pr}_\theta(v)} \perp \text{pr}_\theta(v)\)，得 p 值 \(\gamma_{\theta, v}\)。
聚合统计量：\(\gamma_\theta = \min_{v} \gamma_{\theta, v}\)。
关键：证明这些 p 值渐近独立（因果顺序使得不同层的信息正交）→ \(\gamma_\theta\) 在零假设下逼近 Beta(1, p-1) 分布 → 得到最终 p 值 \(\pi_\theta\)。
有效性定理（Theorem 1） [0:38–0:39]：
条件：(i) 误差独立且次指数 (sub-exponential)；(ii) \(p \log p / n \to 0\)。
结论：自举分布 Wasserstein 收敛到零分布；各层 p 值渐近独立；检验渐近有效 \(\lim P(\pi_\theta \le \alpha) \le \alpha\)。
非线性情形通过 sieve 估计控制近似偏差。
计算问题：分支定界 [0:40–0:45]：
利用 \(\gamma_\theta\) 是最小 p 值的性质：检验按顺序逐层进行，一旦某层 p 值 \(<\alpha/(p-1)\) 分位数，可立即拒绝该顺序（及其所有前缀相同的顺序）。
具体步骤：先测试所有 size-2 的部分顺序 → 保留未拒绝的 → 扩展至 size-3 → 直至完整顺序。
优化：不同顺序若共享相同的前驱集（ancestral set），同一层的检验仅需计算一次（只与集合、不必与排列），减少计算量。

[0:45–0:47] 模拟与数据例¶

模拟设置 [0:45]：\(p=8\)，\(n=500,1000,2500,5000\)；随机 DAG（边概率 1/3，仅允许 \(i<j\) 方向）；边权来自 \(\pm \text{Gamma}(n^{-1/8},1)\)（信号随 n 减弱）；误差分布含 Gamma, Laplace, Lognormal, Uniform, Weibull。
主要结果 [0:45–0:46]：
覆盖概率（coverage）接近名义水平 90%。
置信集大小（proportion of orderings retained）随 n 增大而减小；同时，LiNGAM 点估计的相合恢复率（dashed line）仅约 20%，说明置信集在无法相合恢复时依然工作。
祖先关系保守集 \(\hat{A}\) 的大小（sensitivity）亦随 n 增加。
计算时间：\(p=13\) 时单核约 1 小时；强调时间与信噪比强相关（信号强时分支定界剪枝更高效）。
数据例：Sachs 蛋白调控网络 [0:47]：\(p=11, n=853\)。线性假设下 \(\hat{\Theta}(\alpha=0.01)\) 为空 → 假设很可能被拒绝。改用三次样条（非线性），\(\hat{\Theta}(\alpha=0.1)\) 包含约 37% 的顺序，说明在允许非线性下 uncertainty 很大。

[0:47–0:49] 讨论与 Q&A¶

讲者承认的局限性：
置信集可能为空（即使 misspecification 轻微、点估计仍然好）→ 用户不能区分“严重 misspecified”与“轻微 misspecified”。讲者认为“至少知道假设不成立”是有价值信息。
计算负担大，虽可并行但仍是瓶颈。
未来方向：扩展到不同模型类；考虑其他类型的置信集（讨论嘉宾 Malinsky 提出若干建设性问题：更高维度、更少参数类、局部不确定性等）。

四、对应论文与开放问题¶

(a) 对应论文¶

论文标题（从报告推测）：“Confidence Sets for Causal Discovery” 或类似名称，联合作者为 Mladen Kolar（University of Chicago）与 Mathias Drton（TU Munich, old spelling may be “Mathias Drton” 或 “Mathias Drt…”，转写中为“Matthias stern”，待与视频核实）。
arXiv 状态：报告中未提及链接或 arXiv ID。讲者提到项目已进行 3-4 年，推测可能已投稿或有一篇 working paper。
相关前期工作：
检验统计量：Wang & Drton (2019) 的高阶相关检验。
条件自举：Sen & Sen (2014) 的 HSIC-based 自举法；Shah & Bühlmann (2018) 的 parametric bootstrap。
顺序搜索：Raskutti & Uhler (2018)；Solus et al. (2021) 的置换方法。

(b) 开放问题（每条扎根于报告转写）¶

扩展到不假设加性噪声模型的非参数 DAG 等价类（讨论嘉宾 Malinsky [0:50–0:55]）：加性噪声模型类对边际化不封闭，实际数据几乎不可能精确满足。能否基于 Markov 性质（而非残差独立性）构造检验，得到等价类（如 CPDAG）的置信集？
（转写来源：Malinsky 讨论 [0:51–0:55]，讲者回应 [0:56–0:58]：“Yes, definitely… very computationally difficult…”）
与后验局部不确定性 UQ 框架的关系（Malinsky [0:52–0:53]）：Strobl et al. (2019) 对每一条边给出 p 值。讲者的全局与 Strobl 的局部 UQ 各有何适用场景？能否结合？
（转写来源：Malinsky [0:52–0:54] 提到“Strobl… assign p-value to a single edge”；讲者未直接回答，但提到 Schultheiss et al. 的近期工作。）
在强假设被拒绝时的补救：置信集为空时，用户如何判断“轻微 misspecification”还是“完全错误”？能否设计一个层次化决策流程（先检验线性性、再检验因果顺序）？
（转写来源：讲者 [0:47–0:48] 承认局限性，但自身未提供解决方案。）
扩展到更高维 p 和更大规模图的可扩展性：报告中最大 p=13 且计算约 1 小时。分支定界在最坏情形（弱信号）下退化为全枚举，指数复杂度。能否利用更先进的剪枝策略、图分解或近似搜索（如 MCMC）来突破？
（转写来源：讲者 [0:46] 展示计算时间，但强调信号依赖性。Malinsky [0:51] 提出“starting from a consistent point estimate and testing nearby models”可能稀释计算量；讲者 [0:55] 表示考虑过但未采用。）
模型误设下的稳健置信集：讲者的检验同时检验了“因果顺序正确”与“模型类正确（线性、加性噪声、无混淆）”。若模型类正确但顺序错误，或顺序正确但模型类轻微误设，检验的行为能否分离？这对应 Malinsky 的“additive noise model class not closed under marginalization”批评 [0:52–0:54] 以及讲者 [0:57] 承认的“误设轻微时检验仍可能拒绝”。一个潜在的解决方向是构造“对非参数偏离稳健的顺序检验”，但报告未涉及。
统计-计算权衡（与用户兴趣“information-computation gap”的交汇点）：报告中的分支定界法本质上是一个确定性剪枝算法。在弱信号区域（信噪比低），剪枝失效，计算成本高。是否存在一个计算阈值——低于某 SNR 时任何多项式时间算法都无法获得非平凡置信集？这直接与用户的“polynomial-time possibility / low-degree barrier”兴趣对齐，但报告未触及。

Maintained by 陈星宇 · Homepage · Source on GitHub