A Fast Non-parametric Approach for Causal Structure Learning in Polytrees¶

讲者: Mona Azadkia
讨论人: Bryon Aragam
来源: OCIS (Online Causal Inference Seminar)
日期: 2022-06-07
主题: 因果推断
视频: https://youtu.be/ikHRbNLjYdc · 幻灯片

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

相关论文¶

2111.14969 （尚未精读 — talks read --id … --read-papers 可补）

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

子方向：局部因果结构学习（Local Causal Structure Learning）。
该方向追问的是：在仅观测数据、且对函数形式与噪声分布几乎不做假设的前提下，能否恢复一个特定目标节点（而非整张图）的父节点集。这与「全局结构学习」（恢复整个DAG）不同：全局目标通常需要更强的假设（如线性、加性噪声、非高斯性）或面临不可识别问题（Markov等价类）；局部目标则仅关心局部的因果机制，在生物网络、基因调控等「只关心少量目标变量」的场景下更实用。

奠基与主流路线： - 经典方法：PC算法、GES等依赖条件独立性检验，理论完整但检验本身在非参数设置下具有高难度（Robins et al., 2003 指出均匀一致性不可能，催生「强忠实性」条件）。 - 参数化/半参数路线：LiNGAM（线性非高斯）、加性噪声模型（ANM）、因果加性模型（CAM），各自对函数形式或噪声分布施加结构约束以识别整图。 - 非参数路线近十年兴起：如非参数PC（HSIC）、基于熵的方法（Aragam & Gao, 2021，本文讨论员），但有限样本理论往往薄弱。

当前前沿与这场报告的位置：
报告作者Mona Azadkia等所发展的 DAG-FOCI 属于非参数局部方法，站在两条汇合处： 1. Azadkia & Chatterjee (2021) 的CODEC非参数条件依赖度量：基于秩的简单估计量（$O(n \log n)$），自带[0,1]界与自然停止规则； 2. Markov边界 == 父 ∪ 子 ∪ 配偶这一结构化观测，将搜索空间从 $O(2^p)$ 压缩到仅Markov边界内的节点。

报告的关键创新在于跳出FOCI（只给出Markov边界）的局限，向更细粒度的父节点识别推进。其核心假设是「树邻域（tree-neighborhood）」：目标变量Y的Markov边界在原图骨架中的任何环上至多含一个节点。这一假设保证了δ-Markov Gap，也就保证了贪婪前向选择（FOCI）能正确恢复Markov边界，且后续通过无条件下的两两独立性检验就能区分父节点与子/配偶节点。

文献依据：幻灯片 / 论文摘要确认了 arXiv:2111.14969（Azadkia, Taeb, Bühlmann, 2021），讨论员Aragam也引用了自己的工作（Aragam & Gao, "Learning Markov boundaries ... does not appear to have much finite-sample work", 约 [0:53:00] 处）。转写中讲者说 "Peter Bühlmann" （[0:01:05]）但 ASR 记成 "Peter Bolman"——以幻灯片为准。

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

符号与模型：

可观测数据：$n$ 个 i.i.d. 样本，包含变量 $X_1,\dots,X_p,Y$（$Y$是目标）。底层有未知DAG $D=(V,E)$。
结构方程模型（SEM）：每个节点 $X_i = f_i(\text{pa}(X_i), \varepsilon_i)$，$\varepsilon_i$ 独立，$f_i$ 仅可测——无加性噪声假设，无线性假设。
感兴趣的 estimand：$\text{pa}(Y)$ —— $Y$ 的父节点集。
潜在不可观测量：噪声变量 $\varepsilon_i$、函数形式 $f_i$、整张图的结构（除包含 $Y$ 的局部之外）。

最简例子（$d=1$ 父节点，$p=3$，二值/高斯均可）：

考虑一个简单的树形DAG：

X1 → Y → X2

无配偶、无环。Markov边界 $\text{MB}(Y) = \{X1, X2\}$（父+子）。FOCI 算法： 1. 分别计算 $\hat T_n(Y, X_1)$ 与 $\hat T_n(Y, X_2)$。由于 $X_1$ 是父节点而 $X_2$ 是子节点，二者都应该大于0（$X_2$ 通过 $Y$ 与 $Y$ 相关）。但 FOCI 的第一次选择可能选 $X_1$ 或 $X_2$，取决于样本量及信号强度。 2. 关键点：如果按FOCI先选 $X_1$，第二步计算 $\hat T_n(Y, X_2 \mid X_1)$，近似为0（$X_2 \perp Y \mid X_1$），算法停止，输出 $\hat S = \{X_1\}$（恰为Markov边界？不对！本例中MB(Y)应该是 $\{X_1, X_2\}$，FOCI只选出了 $\{X_1\}$，不够完善！）

这正是报告的动机所在：FOCI 不保证给出Markov边界（只保证某个Markov blanket）。问题出在贪婪性——如果 $X_1$ 对 $Y$ 的依赖性远大于 $X_2$，$X_2$ 可能被忽略。只有在满足 $\delta$-Markov Gap 或树邻域结构时，FOCI 才保证得到完整的Markov边界。本例中图是树，树邻域成立，但FOCI仍有可能只选一个吗？答：如果 $Y$ 与 $X_2$ 之间的条件依赖性较弱，而 $X_1$ 对 $Y$ 的依赖性强，贪婪算法可能在第一步就选 $X_1$，然后第二步检查条件依赖时认为 $X_2$ 多余，从而输出 $\{X_1\}$ 而非 $\{X_1,X_2\}$。这正是报告第14页幻灯片举例的「贪婪糟糕」场景的简化版。树邻域保证了存在这样的 $\delta$ 使得来自 Markov 边界内的变量总是比边界外的变量给 $Q$ 带来至少 $\delta$ 的提升——但这里 $X_2$ 和 $X_1$ 都在边界内，贪婪性的问题不是加不加 $X_2$，而是 $X_2$ 是否被 $X_1$ 完全解释。若 $X_2$ 是子节点，则由局部马尔可夫性质，$Y$ 和 $X_2$ 在给定父节点 $X_1$ 后是条件独立的，所以 $ \hat T_n(Y, X_2 \mid X_1) \approx 0$。因此 FOCI 只会输出 $\{X_1\}$——不会输出完整的 Markov 边界。这是 FOCI 的一个已知缺陷（不保证 Markov boundary 的最优性）。

报告第二阶段的「区分父/子」算法就是专门为此设计：在获得 $\widehat{\text{MB}}(Y)$（可能是 $\{X_1\}$）后，进一步对 $\widehat{\text{MB}}(Y)$ 中的每个节点计算它们的 Markov 边界，构建无向图，再识别「所有边且内部节点两两独立」的连通分量作为父节点集合。本例中 $\widehat{\text{MB}}(Y) = \{X_1\}$，算法检查 $X_1$ 的 Markov 边界，发现 $Y \in \widehat{\text{MB}}(X_1)$，因此 $X_1$ 与 $Y$ 互在对方的 Markov 边界中。树邻域下，$\widehat{\text{MB}}(Y)$ 内部的「全连接且内部两两独立」的连通分量只有一个——$\{X_1\}$。算法输出 $\{X_1\}$ 作为父节点。成功的！ 输出恰为真实父节点。

总结：例子虽然简单，但揭示了报告的双阶段核心： - 第一阶段（FOCI）：找到某个 Markob blanket，不一定是 Markov 边界（但树邻域保证它边界准确）。 - 第二阶段：利用 Markov 边界的结构关系（父节点之间互为 Markov 边界，子/配偶则与父节点无 Markov 边界重叠）以及树邻域条件，仅在无条件两两独立性检验下重构出父节点集。

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

0:00–0:04 [寒暄/问题设置]
介绍问题：对于一个目标变量 $Y$，能否从观测数据找出其父节点集（红色节点）。指出「不是整图，只是局部」。

0:04–0:08 [定义与预备]
- SEM：$X_i = f_i(\text{pa}(X_i), \varepsilon_i)$，$f_i$ 仅可测，$\varepsilon_i$ i.i.d.（无添加性、无参数化假设）。 - 父/子/配偶的定义。 - Markov 等价类：两张 DAG 等价当且仅当骨架相同且 v-结构相同。性质：若 $Y$ 在某个等价类中有 $\ge 2$ 个父节点，则 $\mathcal{P}(Y)$（所有等价类中的父节点集构成的集合）只含一个集合（即唯一识别）；否则可能不唯一（如只有一个父节点时，方向可逆）。 - Markov 边界（MB）：最小充分集，且为 $\text{pa}(Y) \cup \text{ch}(Y) \cup \text{sp}(Y)$。

0:08–0:12 [FOCI：Markov 边界探索]
- 使用 FOCI (Forward stepwise variable selection based on CODEC)。 - CODEC：非参数条件依赖测度 $T(Y,Z \mid X)$，取值 [0,1]，0=条件独立，1=$Y$ 是 $Z$ 的函数给定 $X$。 - 定义：$T(Y,Z \mid X) = \frac{\int \mathbb{E}[\text{Var}(\mathbb{P}(Y\ge t \mid Z,X) \mid X)] d\mu(t)}{\int \mathbb{E}[\text{Var}(\mathbf{1}_{Y\ge t} \mid X)] d\mu(t)}$。 - 关键性质：观察到 $T$ 可被简单的秩/近邻估计量 $T_n$ 估计，$O(n \log n)$ 时间。 - FOCI 步骤：从空集开始。每一步，在剩余变量中找最大化 $T_n(Y, X_k \mid \hat S)$ 的那个加入 $\hat S$。停止准则：对所有剩余 $k$，$T_n(Y, X_k \mid \hat S) \le 0$（负？应是非正）。效果：输出 $\hat S$ 是某个 Markov blanket（定理6.1, Azadkia & Chatterjee 2021），但不保证是最小（Markov boundary）。

0:12–0:15 [贪婪的缺陷]
- 举例（幻灯片14）：$X_3$ 是 $Y$ 的祖父节点（$X_3 \to X_1, X_2$; $X_1, X_2 \to Y$）；设定噪声极小时，$X_3$ 对 $Y$ 的依赖性大于 $X_1$ 或 $X_2$。FOCI 先选 $X_3$（不是 Markov 边界的一部分），之后因 $X_3$ 已经解释了大部分 $Y$ 的变异性，$X_1, X_2$ 不再有正的条件依赖性贡献，从而最终 $\hat S$ 包含 $X_3$——是 Markov blanket 的超集，不是边界。 - 解决方案：引入 $\delta$-Markov Gap：对任何 $S \subsetneq \text{MB}(Y)$，存在 $i\in \text{MB}(Y)\setminus S$ 使得对任何 $j\notin \text{MB}(Y)$ 有 $Q(S \cup \{i\}) - Q(S \cup \{j\}) \ge \delta$，其中 $Q(S) = \int \text{Var}(\mathbb{P}(Y\ge t \mid X_S)) d\mu(t)$（即 CODEC 的分子）。若此 gap 存在，FOCI 恢复 Markov 边界。 - 何时有 gap？→ 树邻域：原图骨架中任何环至多包含一个 $\text{MB}(Y)$ 成员。证明：树邻域 $\implies$ $\delta$-Markov Gap。

0:15–0:23 [第二阶段：从 Markov 边界到父节点]
- 关键观察： 1. 若 $X_i, X_j \in \text{pa}(Y)$，则 $i \in \text{MB}(X_j)$ 且 $j \in \text{MB}(X_i)$（总是）。 2. 若树邻域成立且 $i \in \text{MB}(Y)\setminus \text{pa}(Y)$（即子/配偶），则 $\text{MB}(X_i) \cap \text{pa}(Y) = \varnothing$（因 $Y$ 阻断）。 - 算法：计算 $\widehat{\text{MB}}(Y)$；对其中每个 $i$，也计算 $\widehat{\text{MB}}(X_i)$。构建无向图 $G_Y^*$： - 顶点集 = $\widehat{\text{MB}}(Y)$； - 边 $(i,j)$ 当且仅当 $i \in \widehat{\text{MB}}(X_j)$ 且 $j \in \widehat{\text{MB}}(X_i)$。 - 树邻域保证 $G_Y^*$ 分解为若干完全连通子图，至多一个子图中所有顶点两两独立。这一子图（若存在且大小>1）就是 $\text{pa}(Y)$；若所有子图都大小为1，则 $\widehat{\mathcal{P}}(Y)$ 包含所有可能父节点集（对应不可识别情形）。 - 理论保证（Theorem 1）：在光滑条件、尾部分布条件、$\delta$-Markov Gap 及树邻域下，$\mathcal{P}(Y) \subseteq \widehat{\mathcal{P}}_n(Y)$ 以高概率成立。 - 保守性保证（Theorem 2）：若不假设树邻域，但 $\mathcal{P}(Y)$ 是单集合且 $|\text{pa}(Y)|>1$，则 DAG-FOCI 输出不包含非父节点（即无假阳性），以高概率成立。

0:23–0:33 [模拟与比较]
- 模拟图（幻灯片25）含16个节点，含非线性、非加性噪声关系（如 $X_5 = X_1 - \arctan(X_2) + \varepsilon_5$, $X_{11} = X_6 (X_{12} - X_8) + \varepsilon_{11}$）。 - 评估指标：Jaccard Index。样本量从2000至10000，Jaccard 从0.72/0.57升至0.92/0.93（$X_6$ / $X_{11}$）。精确恢复率升至~85%。 - 与 PC(partial correlation / HSIC)、Hill-climbing、CAM、GES 比较：在 $X_6$（关系近线性）时 PC(HSIC) 最优（Jaccard=1），DAG-FOCI 第二（0.92）；在 $X_{11}$（强非线性非加性）时 DAG-FOCI 最优（Jaccard=0.93），PC(HSIC) 降为0.60。 - 讨论员 Aragam（[0:43:00–1:00:00]）提供了更加宽广的学科史背景： - 非参数结构学习的有限样本理论历史悠久但薄弱；PC 算法本质非参但依赖条件独立检验，而非参 CI 检验本身很困难。 - Markov 边界学习 方面，现有算法（如 IAMB、GS）缺少有限样本保证；Aragam & Gao (2021) 曾给出有限样本保证，条件正是 $\delta$-Markov Gap。 - 树邻域假设的合理性：与 Chow-Liu 算法（寻找最优树近似）的联系是一个开放问题（Azadkia 回答「不清楚」）。 - 计算复杂度：DAG-FOCI 共需运行 FOCI $(|\widehat{\text{MB}}(Y)|+1)$ 次（[0:59:30] ~ 60万行声明，可能记错；ASR 文本[0:59:36] 是 "mark of boundary plus one times foci" 即 $|\text{MB}(Y)|+1$ 次）。若 Markov 边界尺寸大，时间可能较高（但 $O(n\log n)$ 每轮的累积仍可接受）。

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

对应论文：
- 标题：A Fast Non-parametric Approach for Local Causal Structure Learning
- 作者：Mona Azadkia, Armeen Taeb, Peter Bühlmann
- arXiv：2111.14969
- 幻灯片中参考文献也给出了 Azadkia & Chatterjee (2021) The Annals of Statistics——即 CODEC 的原论文。
- 讨论员 Aragam 的工作：Aragam & Gao (2021) 也给出了 Markov 边界学习的有限样本保证（研究者在阅读时建议交叉对比）。

开放问题（源于转写 & 讨论）：

无 $\delta$-Markov Gap 时的智能剪枝（转写 [0:42:20–0:43:01]）：当分布不满足 $\delta$-Markov Gap 或树邻域时，能否设计后向剪枝步骤（如 IAMB 风格）以有限样本保证地恢复 Markov 边界？
潜在混淆（转写 [0:43:08]）：数据中有未被观测的混淆变量时，DAG-FOCI 的保守性保证是否仍然成立？如何推广？
与 Chow-Liu 算法的潜在联系（讨论员提问 [0:57:05–0:57:20]）：第二阶段中仅用无条件独立性检验来区分父节点集的步骤，在假设树状邻域等价于局部树近似时，是否存在算法层面的等价性或可替代性？
整体计算复杂度的精确刻画（讨论员 [0:58:58–0:59:30]）：DAG-FOCI 若按最坏情况（$\widehat{\text{MB}}(Y)$ 较大）将运行 FOCI 多次。是否存在更高效的稀疏结构利用方案？
条件独立性检验的整合（转写 [0:42:50–0:43:05]）：当前算法避免条件独立检验（只用无条件的直接点），但若能整合高效的非参数条件独立检验（如基于核或基于分位数的快速方法），是否能在不破坏树邻域假设的前提下提升对非父节点的识别精度？

注意事项：上述问题均根植于转写中讲者或讨论员的明确语句，未作判断性评估（如「是否可行」「是否重要」）。研究者可自行核实对应时间点。

Maintained by 陈星宇 · Homepage · Source on GitHub