跳转至

A general framework on conditions for constraint‐based causal learning

作者: Kai Z. Teh, Kayvan Sadeghi, Terry Soo
来源: Scandinavian Journal of Statistics
主题: 因果推断
相关性: 7/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么： 约束型因果发现旨在从观测数据的条件独立（CI）集合中，逆向推断出生成这些数据的真实因果图。其根本统计与科学问题在于：给定一个概率分布 \(P\) 及其蕴含的 CI 关系集合，在何种假设（即 correctness condition）下，算法能唯一（或至多在 Markov 等价类内）恢复出真实因果图 \(G^*\) 的拓扑结构？当前该方向的成熟度表现为：经典算法（如 PC）的充分条件（faithfulness）已被广泛接受，但其过强且在几何上易被违反；近年来涌现了多种试图放松该条件的替代算法与假设（如 SP、frugality、SMR），但各假设之间的逻辑强弱偏序与必要/充分性长期缺乏统一、严格的刻画。

发展脉络： - 奠基工作：Spirtes et al. (2000) 与 Pearl (2000) 建立了以 Causal Markov Condition 与 Faithfulness 为双基石的约束型发现范式。Verma & Pearl (1990) 提出了 Markov 等价类概念，指出仅靠 CI 只能恢复到等价类层面，奠定了算法输出的目标上限。 - 主要进展（对 Faithfulness 的质疑与放松）：Uhler et al. (2013) 从几何与组合角度证明，强 faithfulness（\(\lambda\)-strong faithfulness, Zhang & Spirtes 2002）的违反集具有非零 Lebesgue 测度，且在稠密图下测度惊人地大，揭示了 PC 算法在高维设定下的根本局限。Ramsey et al. (2006) 拆解 faithfulness 为 Adjacency-Faithfulness 与 Orientation-Faithfulness，指出前者可保留而后者可放弃，由此提出 CPC 算法，这是对 PC 正确性条件的首次精细拆解。Raskutti & Uhler (2018) 提出 SP 算法与 SMR 假设，证明 SMR 严格弱于 faithfulness，并指出存在统计-计算权衡。Forster et al. (2018) 提出 frugality 原则（选择边最少的 DAG），将其与 minimality 联系。Sadeghi (2017) 引入 minimally Markovian assumption，从骨架角度定义极小性。 - 当前 frontier（统一框架与极弱条件）：Sadeghi & Soo (2022) 首次尝试形式化"自然结构学习算法"族，给出了一组可测试的、弱于 faithfulness 的正确性条件。Teh et al. (2024) 将其局部化为 LoNS 算法族，给出了必要且充分条件，并证明其严格弱于 restricted faithfulness。Lam et al. (2022) 证明 GRaSP 算法的一致性条件包含关系 \(\text{supp}(\mathcal{M}_3) \subseteq \text{supp}(\mathcal{M}_2)\)。 - 本文的位置：本文将前述零散的"某算法在某条件下正确"的命题，抽象为"算法 = property"的统一框架。在此框架下，不仅重新推导出 PC 的精确正确性条件，更从偏序结构上证明：对于输出 ancestral graph 或满足任意极小性的 DAG 的算法族，SMR 是最弱的可能正确性条件（即不可能再弱了）。

子线索聚类： 1. 算法驱动的条件放松线：PC → CPC (Ramsey 2006) → FCI (Spirtes 1995, 处理潜变量) → SP (Raskutti 2018) → GRaSP (Lam 2022)。这条线关注具体算法的运行逻辑，逐次剥离 faithfulness 中非必要的成分。 2. 原则驱动的极小性定义线：Pearl-minimality → Frugality (Forster 2018) → Minimally Markovian (Sadeghi 2017) → SMR。这条线从图论的极小性（边数最少、无法再删边等）出发，定义分布与图的匹配原则。 3. 几何与测度局限线：Uhler et al. (2013) 与 Zhang & Spirtes (2002)。这条线不构造新算法，而是量化 faithfulness 与 strong faithfulness 的违反概率与测度，揭示高维下的一致性瓶颈。

核心追问： 1. Faithfulness 中哪些子条件是算法必需的，哪些是冗余的？（如 Adjacency vs Orientation） 2. 是否存在严格弱于 faithfulness 且仍能保证某类算法正确性的条件？其最弱下界在哪？（SMR 是否是终点？） 3. 极小性原则（如 Pearl-minimality）与 faithfulness 的逻辑关系是什么？极小性本身能否替代 faithfulness？

⚠️ 作者的 framing： - 作者将缺口 frame 为：现有文献对正确性条件的讨论是"逐算法、逐条件"的碎片化比较，缺乏一个能统一生成、比较任意约束型算法正确性条件的抽象框架。这使得本文的 property 框架成为"显然的下一步"——先定条件，再设计算法。 - 被淡化或回避的路线：Score-based 方法（如 BIC/GES）及其对应的条件（如 BIC 一致性条件）在 intro 中几乎未出现；本文框架明确限定在 constraint-based 算法。此外，统计-计算权衡（SP 算法的指数时间复杂度）在 intro 中被提及，但本文的理论推导并未将计算复杂度纳入 property 框架的偏序比较中。 - 明显该被引但缺失的：高维因果发现中基于 penalized score 的方法（如 Chickering 2002 的 GES 算法）及其一致性条件，以及近期关于 high-dimensional consistency 的文献（如 van de Geer 型 Lasso consistency），这些与 constraint-based 条件有直接对峙，但未在 intro 中定位。

张力： 未见明显对立引用。各文献在"faithfulness 过强、需要放松"上是一致的；张力主要体现在放松的程度与代价上：SMR 放松到最弱，但代价是 SP 算法的指数时间；CPC 放松 Orientation-faithfulness，代价是部分边方向无法识别。本文在定理层面确认了这种张力：SMR 是最弱条件，但达成它的算法在计算上可能是不可行的。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据交代清楚

  • \(V\)：有限随机变量集，维数为 \(p\)。
  • \(P\)：\(V\) 上的概率分布（可观测的底层分布），假设 \(P\) 对应一个 CI 关系集合 \(\mathcal{I}(P)\)（即 \(P\) 满足的全体条件独立语句）。
  • \(G^*\)：真实因果图（DAG 或 ancestral graph），是我们要推断的 estimand。\(G^*\) 诱导一个图论分离集合 \(\mathcal{J}(G^*)\)（通过 \(d\)-分离或 \(m\)-分离定义）。
  • \(\mathcal{G}\)：算法考虑的图类（如全体 DAG、全体 ancestral graph）。
  • \(\mathcal{A}\)：一个约束型因果发现算法。输入为 \(\mathcal{I}(P)\)，输出为图 \(G \in \mathcal{G}\)。
  • \(\mathcal{P}\)：一个 property（性质），是定义在 \((P, G)\) 对上的布尔条件。记号：\((P, G) \in \mathcal{P}\) 表示分布 \(P\) 与图 \(G\) 满足该性质。
  • \(\mathcal{P}_\mathcal{A}\)：算法 \(\mathcal{A}\) 的 correctness condition（正确性条件）。定义为：若 \((P, G^*) \in \mathcal{P}_\mathcal{A}\)，则算法 \(\mathcal{A}\) 输入 \(\mathcal{I}(P)\) 后必输出 \(G\)，且 \(G\) 与 \(G^*\) Markov 等价（即 \(\mathcal{J}(G) = \mathcal{J}(G^*)\)）。
  • 可观测数据：研究者实际观测到的是 \(V\) 上的样本 \(X_1, \ldots, X_n \sim P\)。在理论层面，算法的输入被假设为完美的 CI 集合 \(\mathcal{I}(P)\)（即大样本极限下条件独立检验无误差）；在有限样本下，\(\mathcal{I}(P)\) 由统计检验近似，本文的理论不处理有限样本误差。
  • 不可观测 / 需假设识别的：\(G^*\) 本身不可观测；\(P\) 与 \(G^*\) 的对应关系（\(P\) 是否由 \(G^*\) 生成）不可观测，必须靠 Markov Condition + 正确性条件（如 faithfulness）来识别。

第二步：最小内核——PC 算法的精确正确性条件

剥掉所有一般性框架的抽象定义，本文的核心数学内核在于：把一个具体的算法（PC）拆解为一系列子步骤，每个子步骤对应一个子 property，然后证明这些子 property 的合取就是 PC 的精确正确性条件，且严格弱于 faithfulness。

最简特例（\(p=3\) 的 DAG，无潜变量）： 设 \(V = \{X_1, X_2, X_3\}\)，真实图 \(G^*\) 为 \(X_1 \rightarrow X_2 \rightarrow X_3\)（链结构）。\(P\) 由 \(G^*\) 生成且满足 Markov Condition，即 \(\mathcal{J}(G^*) = \{X_1 \perp X_3 \mid X_2\}\)。

  • Faithfulness 要求：\(\mathcal{I}(P) = \mathcal{J}(G^*)\)，即 \(P\) 中只有由 \(d\)-分离蕴含的条件独立，没有任何"额外"的独立。在 \(p=3\) 链结构下，faithfulness 意味着 \(X_1 \not\perp X_2\), \(X_2 \not\perp X_3\), \(X_1 \not\perp X_3\)（除给定 \(X_2\) 外）。
  • PC 算法的运行：
  • 骨架阶段：从完全图开始，检验零阶独立（\(X_i \perp X_j\)）。若 faithfulness 成立，\(X_1 \not\perp X_2\) 且 \(X_2 \not\perp X_3\)，故骨架保留边 \(X_1-X_2\) 与 \(X_2-X_3\)；检验一阶独立（\(X_1 \perp X_3 \mid X_2\)），发现成立，删去 \(X_1-X_3\)。骨架正确。
  • 方向阶段：在骨架 \(X_1-X_2-X_3\) 上，寻找 unshielded triple（\(X_1-X_2-X_3\)）。因 \(X_1 \perp X_3 \mid X_2\)，该 triple 不是 collider，故不定向为 \(X_1 \rightarrow X_2 \leftarrow X_3\)；后续规则将其定向为 \(X_1 \rightarrow X_2 \rightarrow X_3\)。
  • PC 的精确正确性条件（本文结论的退化）：在 \(p=3\) 链结构下，PC 只需要：
  • Adjacency-Faithfulness：若 \(X_i\) 与 \(X_j\) 在 \(G^*\) 中相邻，则 \(X_i \not\perp X_j\)（对任意条件集）。这保证骨架阶段不会误删真实边。
  • Orientation-Faithfulness 的弱化版：对于 unshielded triple \(X_i - X_k - X_j\)，若 \(X_k\) 不是 \(X_i, X_j\) 的 collider，则 \(X_i \perp X_j \mid X_k\)；若 \(X_k\) 是 collider，则 \(X_i \not\perp X_j \mid X_k\)。这保证方向阶段不会误定向。 这两条合取，即 \(\mathcal{P}_{\text{PC}}\)，在 \(p=3\) 链结构下严格弱于 faithfulness：因为 faithfulness 还要求"非相邻且非 \(d\)-分离的变量必须依赖"，而 PC 根本不检验这类独立，因此即使 \(P\) 中存在额外的独立（违反 faithfulness），只要不破坏上述两条，PC 仍能正确输出。

最小问题：给定算法 \(\mathcal{A}\)，其 correctness condition \(\mathcal{P}_\mathcal{A}\) 的最弱可能形式是什么？本文证明：对于输出满足极小性的 DAG 或 ancestral graph 的算法族，SMR 是最弱可能条件。SMR 定义为：\(G^*\) 是所有与 \(P\) Markov 匹配（即 \(\mathcal{J}(G) \subseteq \mathcal{I}(P)\)）的图中边数最少的图。这个条件的核心困难在于：它要求在全体图类 \(\mathcal{G}\) 上做 \(\ell_0\) 极小化（找最少边数的图），这是一个组合优化问题，计算上极难（对应 SP 算法的指数时间），但在逻辑上它确实是"最弱"的——任何更弱的条件都将无法区分边数不同的 Markov 等价图，导致因果学习失去意义。

三、这篇论文做了什么

三句话： ① 研究了约束型因果发现算法的正确性条件（correctness conditions）的统一生成、比较与最弱性刻画问题。 ② 核心工具是引入 property（算法的抽象表示）与 class property（等价类上的不变性质），构建算法-条件偏序框架。 ③ 主要结论：给出了 PC 算法的精确正确性条件并证明其弱于 faithfulness；证明了对输出极小性 DAG/ancestral graph 的算法，SMR 是最弱可能正确性条件；论证了 Pearl-minimality 是有意义因果学习的必要条件但不足以放松 faithfulness。

关键设定与假设： 在第二节记号基础上补全： - Property \(\mathcal{P}\) 的形式化：\(\mathcal{P}\) 是 \(\mathcal{G} \times \mathfrak{P}\)（图类 × 分布类）上的子集。\((G, P) \in \mathcal{P}\) 表示 \(P\) 与 \(G\) 满足该性质。算法 \(\mathcal{A}\) 的 correctness condition \(\mathcal{P}_\mathcal{A}\) 定义为：\(\forall P, G^*\)，若 \((G^*, P) \in \mathcal{P}_\mathcal{A}\)，则 \(\mathcal{A}(\mathcal{I}(P))\) 输出 \(G\) 且 \(\mathcal{J}(G) = \mathcal{J}(G^*)\)。 - Class property：若 \(\mathcal{P}\) 在 Markov 等价类上不变（即 \(G_1 \equiv G_2 \Rightarrow (G_1, P) \in \mathcal{P} \Leftrightarrow (G_2, P) \in \mathcal{P}\)），则称 \(\mathcal{P}\) 为 class property。本文证明：faithfulness、SMR、Pearl-minimality、frugality 均为 class property；Adjacency-faithfulness 不是 class property（它依赖于具体图的边，而非等价类的骨架）。 - Minimality 假设族： - Pearl-minimality：\(P\) 对 \(G\) Markov，且对 \(G\) 的任何真子图 \(G'\)，\(P\) 不对 \(G'\) Markov（即删去任何一条边都会引入新的依赖）。 - SMR (Sparsest Markov Representation)：\(G\) 是所有与 \(P\) Markov 匹配的图中边数最少的图（\(\ell_0\) 极小化）。 - Frugality：\(G\) 是所有与 \(P\) 匹配的 DAG 中边数最少的 DAG。 - 假设的统计含义：Pearl-minimality 禁止了"冗余边"（即删边不改变分离集的边），这是因果图有意义的最低要求；SMR 进一步要求全局边数最少，这排除了所有"等价但更稠密"的图。相比已有文献，本文将 faithfulness 拆解为子 property，并明确指出了 Pearl-minimality 在偏序中的位置：它弱于 faithfulness，但不足以作为任何输出 DAG 的算法的正确性条件。

主要结果：

  1. 定理：PC 算法的精确正确性条件 \(\mathcal{P}_{\text{PC}}\)
  2. 陈述：\(\mathcal{P}_{\text{PC}}\) 是 Adjacency-faithfulness 与 Orientation-faithfulness（具体形式为 Proposition 2 中的 \(\mathcal{V}_1, \mathcal{V}_3\)）的合取。即：若真实图 \(G^*\) 与分布 \(P\) 满足"相邻变量必依赖"且"unshielded triple 的 collider/非 collider 状态与 CI 一致"，则 PC 输出正确。
  3. 直觉：PC 算法只检验两类 CI：相邻变量的 CI（决定骨架）与 unshielded triple 上的 CI（决定方向）。因此，只有这两类 CI 需要与图结构一致，其余 CI 的违反不影响 PC。
  4. 必要条件：Adjacency-faithfulness 是必要的——若某相邻变量在 \(P\) 中独立，PC 必在骨架阶段删去该边，无法恢复。Orientation 条件也是必要的——若 collider triple 在 \(P\) 中给定中间变量后独立，PC 必误定向为非 collider。

  5. 解决的技术难点：以往文献（Ramsey 2006）给出了 CPC 的充分条件，但未给出 PC 的精确（必要且充分）条件。本文通过 property 框架，将 PC 的每一步操作映射到一个子 property，从而精确拼出 \(\mathcal{P}_{\text{PC}}\)。

  6. 定理：SMR 是最弱可能正确性条件

  7. 陈述：对于输出 ancestral graph 或满足任何极小性定义（Pearl-minimality, frugality, minimally Markovian）的 DAG 的算法族，SMR 是最弱的 class property 正确性条件。即：若 \(\mathcal{P}\) 是一个 class property 且是某输出极小性 DAG 的算法的正确性条件，则 \(\mathcal{P} \Rightarrow \text{SMR}\)（逻辑蕴含）。
  8. 直觉：SMR 要求"边数最少"，这已经是最弱的图论约束——任何更弱的条件都将允许边数更多的图通过，而极小性算法会选择边数少的图，导致输出与真实图不一致。
  9. 必要条件：算法必须输出极小性图（否则 SMR 不必要，如算法可能输出稠密图）。

  10. 解决的技术难点：证明"最弱"需要构造偏序：设 \(\mathcal{P}\) 是正确性条件，则 \(\mathcal{P}\) 必蕴含 SMR。本文通过反证法：若 \(\mathcal{P}\) 不蕴含 SMR，则存在 \((G^*, P) \in \mathcal{P}\) 但 \(G^*\) 不是最稀疏的；此时存在更稀疏的 \(G'\) 与 \(P\) Markov 匹配，极小性算法将输出 \(G'\) 而非 \(G^*\)，违反正确性。

  11. 命题：Pearl-minimality 的位置

  12. 陈述：Pearl-minimality 是有意义因果学习的必要条件（若不满足，则存在冗余边，因果图不可解释），但不是任何输出 DAG 的算法的充分正确性条件，且不能用来放松 faithfulness（因为 faithfulness 蕴含 Pearl-minimality，但反之不成立；且存在满足 Pearl-minimality 但违反 SMR 的分布，导致极小性算法输出错误）。
  13. 直觉：Pearl-minimality 只禁止"删边不改变分离集"的冗余边，但允许"删边改变分离集但引入额外独立"的伪稀疏图。SMR 则禁止所有伪稀疏图。

证明路线与技术技巧：

  • 整体路线：
  • 定义 property 与 class property，建立算法-条件的映射 \(\mathcal{A} \mapsto \mathcal{P}_\mathcal{A}\)。
  • 将具体算法（PC）拆解为子步骤，每个子步骤对应一个子 property，合取得到 \(\mathcal{P}_{\text{PC}}\)。
  • 建立 class property 的偏序：\(\text{Faithfulness} \Rightarrow \text{SMR} \Rightarrow \text{Pearl-minimality}\)（蕴含链）。
  • 证明 SMR 是最弱：对任意 class property \(\mathcal{P}\) 作为极小性算法的正确性条件，证明 \(\mathcal{P} \Rightarrow \text{SMR}\)。

  • 分析 Pearl-minimality 的不足：构造反例，展示满足 Pearl-minimality 但违反 SMR 的分布。

  • 关键跳跃点：

  • Lemma：PC 的子 property 拆解。难点在于：PC 的方向阶段涉及多个定向规则（Meek 规则），如何将每条规则的正确性映射为独立的 property？本文通过分析 PC 的定向逻辑，将 Orientation-faithfulness 拆解为 \(\mathcal{V}_3\)（unshielded collider 的 CI 一致性），而 Meek 规则的正确性被证明为 \(\mathcal{V}_3\) 的推论。

  • Theorem：SMR 最弱性的反证构造。难点在于：如何构造一个"满足 \(\mathcal{P}\) 但不满足 SMR"的 \((G^*, P)\) 对，使得极小性算法必然输出错误？本文利用了极小性定义的 \(\ell_0\) 性质：若 \(G^*\) 不是最稀疏的，则存在更稀疏的 \(G'\)，算法必选 \(G'\)。

  • 技术技巧点名：

  • Property 框架（抽象表示）：将算法抽象为从 CI 集合到图类的映射，将正确性条件抽象为 \((P, G)\) 上的子集。这允许在不涉及算法具体实现的情况下，比较不同算法的条件强弱。
  • Class property 不变性：利用 Markov 等价类的性质，证明 faithfulness、SMR 等是 class property，而 Adjacency-faithfulness 不是。这是偏序比较的基础——class property 之间可以按逻辑蕴含排序。
  • 蕴含链构造（Forster et al. 2018 的推广）：本文将 Forster et al. (2018) 给出的 DAG 上的蕴含链（Faithfulness \(\Rightarrow\) Frugality \(\Rightarrow\) Pearl-minimality）推广到 ancestral graph 与更一般的极小性定义，并插入 SMR 作为最弱节点。
  • 反例构造（Pearl-minimality 的不足）：构造满足 Pearl-minimality 但不满足 SMR 的分布，证明 Pearl-minimality 不能作为正确性条件。

真实例子与应用： 本文为纯理论论文，无真实数据例子或模拟实验。所有结论均在"完美 CI 输入"的理想假设下证明，不处理有限样本下的条件独立检验误差。

🔎 结论是否比证明窄： - 作者在讨论 SMR 最弱性时，明确限定了算法族为"输出极小性 DAG 或 ancestral graph 的算法"。对于不输出极小性图的算法（如某些 score-based 算法可能输出非极小性图），SMR 不一定是最弱条件。作者在文中未对这类算法做 claim，但 intro 中提到"meaningful causal learning"时，隐含地将极小性作为因果学习的自然要求，这是一个未经严格证明的哲学判断，而非数学结论。 - 作者 claim "Pearl-minimality has to be strengthened, such as by including background knowledge, for causal learning beyond faithfulness"，但"background knowledge"的引入并未在本文框架内形式化证明，这是一个方向性建议，而非定理。

四、开放问题（点到为止，扎根具体语句）

  1. 有限样本下的正确性条件：本文所有定理假设输入为完美 CI 集合 \(\mathcal{I}(P)\)。有限样本下，CI 检验有误差（假阳性/假阴性），此时 \(\mathcal{P}_{\text{PC}}\) 的样本版本是什么？如何定义"有限样本正确性条件"？（扎根：文中未提及有限样本，但 Uhler et al. (2013) 与 Zhang & Spirtes (2002) 的 strong faithfulness 正是针对此问题，本文框架未覆盖。）

  2. 计算复杂度与最弱条件的权衡形式化：本文证明 SMR 是最弱条件，但 SP 算法（达成 SMR 的算法）是指数时间。能否在 property 框架内引入"多项式时间可计算"的约束，刻画"多项式时间算法的最弱可能正确性条件"？这将直接对应统计-计算权衡。（扎根：intro 提及 "computational price"，但框架与定理未将复杂度纳入偏序。）

  3. Score-based 算法的正确性条件偏序：本文框架限定在 constraint-based 算法。能否将 score-based 算法（如 GES）的 BIC 一致性条件纳入类似的 property 偏序，与 \(\mathcal{P}_{\text{PC}}\)、SMR 比较？（扎根：intro 未提及 score-based 方法，但 Raskutti & Uhler (2018) 指出 SP 在高斯下等价于 \(\ell_0\)-penalized MLE，这暗示 score-based 与 constraint-based 的条件可能有深层联系。）

  4. Background knowledge 的形式化与最弱条件：作者建议将 Pearl-minimality 结合 background knowledge 强化，但未形式化。能否在 property 框架内定义"background knowledge property"（如 Meek 1995 的边约束），并刻画"Pearl-minimality + background knowledge"的最弱正确性条件？（扎根：文中 Meek (1995) 被引为例，但未展开定理。）

要确认某条是不是真 gap，去读同子领域近期约 5 篇的 intro——都指向它 = 共识（真 gap），互相打架 = 机会。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论