跳转至

Greedy Relaxations of the Sparsest Permutation Algorithm

讲者: Wayne Lam
讨论人: Alex Markham
来源: OCIS (Online Causal Inference Seminar)
日期: 2022-11-29
主题: 因果推断
视频: https://youtu.be/odV0jgcApi0 · 幻灯片

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

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

这场报告属于因果结构学习（Causal Discovery）中一条特定的工作线：基于“稀疏排列”（Sparsest Permutation, SP）的DAG（有向无环图）学习。

  • 这个方向追问什么：给定观测数据，能否在比经典“忠实性（Faithfulness）”更弱的假设下，恢复出数据生成机制的真实DAG（更准确说，是它的马尔可夫等价类 MEC）？忠实性假设要求分布中所有的条件独立关系都完全由DAG的 d-分离编码。但这个假设在实践中很容易被几乎违反（near-violations），因此人们想寻找更鲁棒（需要更弱假设）的算法。

  • 奠基与主流路线：

    • 主流方法（如 PC、GES）通常假设忠实性。GES（贪婪等价搜索）作为经典的贪心算法，通过在CPDAG空间中进行搜索来学习MEC。
    • Sparsest Permutation (SP) 算法 [Raskutti & Uhler, 2018]：这是该路线的基础。SP算法的核心思想是：遍历所有可能的变量排列（causal order），对每个排列 π 通过条件独立性检验构造一个DAG G_π（该DAG必定是SGS-最小的马尔可夫图），然后返回所有构造出的DAG中最稀疏的那个（边数最少）。SP算法在“唯一稀疏性（u-frugality）”假设下是渐近正确的，这个假设严格弱于忠实性。但SP需要枚举所有m!个排列，计算量是超级指数级的，实际中最多只能处理约10个变量。

  • 当前 Frontier 与这场报告的站位：

    • 上一阶段工作 [Solus et al., 2021]：为了将SP从超级指数变为可扩展，Solus等人提出了两种贪心版本的SP算法：Triangle SP (TSP) 和 Edge SP (ESP)。TSP在 Chickering 序列（一种通过逆转或删除覆盖边连接的DAG序列）上做贪心深度优先搜索。ESP在“DAG associahedron”（一个由相邻转置连接排列构成的图，并进一步将生成相同DAG的排列坍缩后得到的几何结构）上做贪心搜索。关键结论是 ESP条件比TSP条件（等同于忠实性）严格更弱，但ESP需要预先计算出整个DAG associahedron，这本身就不具备可扩展性，因此他们并未实现ESP。
    • 本场报告（讲者的工作）：解决了ESP的“不可实现性”问题，并提出了更强的贪心算法 GRaSP (Greedy Relaxations of the Sparsest Permutation)。核心贡献包括：
      1. 引入了一个叫 tuck 的排列操作，它能够高效地实现ESP的搜索（对应GRaSP1），而无需预先计算整个associahedron。
      2. 提出了GRaSP2，该操作不仅对“覆盖边”或“单一边”进行操作，而是对所有有向边应用tuck，因此能探索比ESP更大的搜索空间，其正确性所需的假设（GRaSP2条件）严格弱于ESP条件（GRaSP1条件），但比u-frugality更强。
      3. 在模拟中，GRaSP2在有限样本下性能极其出色，甚至在小样本（n=1000, p=60）和高密度的场景下也近乎完美，计算时间在2分钟以内。

点名关键工作（有把握的）： - Raskutti & Uhler, 2018: "Learning directed acyclic graph models based on sparsest permutations". Stat, 7. (SP算法奠基) - Uhler et al., 2013: "Geometry of the faithfulness assumption in causal inference". Annals of Statistics, 41. (指出忠实性假设在有限样本下的脆弱性) - Solus et al., 2021: "Consistency guarantees for greedy permutation-based causal inference algorithms". Biometrika, 108. (TSP和ESP的提出者) - Chickering, 2002: "Optimal structure identification with greedy search". Journal of Machine Learning Research, 3. (Chickering序列定理) - Zhang, 2013: "A comparison of three Occam's razors for Markovian causal models". British Journal for the Philosophy of Science, 64. (证明忠实性与唯一P-最小性是等价的)

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

核心问题：我们有m个观测变量V = {X₁, ..., X_m}。我们不知道它们的因果结构（DAG G），但我们能观测到它们的联合分布P。我们希望从P中恢复出G（或它的等价类MEC(G*)）。

符号与模型： - 可观测的：联合分布 P，以及从P中计算出的条件独立（CI）关系集合 I(P)。 - 不可观测的（潜在结构）：真实的DAG G*，以及它编码的d-分离关系集合 I(G*)。 - 假设： - （组成性）图可环（Graphoid）：分布P需满足一些正则性条件（如对称性、分解、收缩等），这是SP算法工作所需的基础。 - 因果马尔可夫（Causal Markov）：I(G*) ⊆ I(P)。（真实DAG的d-分离是分布中CI关系的子集，这是基本假设）。 - 唯一稀疏性（u-frugality，也称Sparsest Markov Representation）：在所有与P马尔可夫的DAG中，稀疏的DAG（边数最少的）都是同一个MEC的（即G是这个MEC中的一员）。这比忠实性弱。 - Estimand / 目标：MEC(G)。

一个最简例子（d=3个变量，读者可以想象为 1 → 2 → 3）： 1. 一个排列π是顶点集{v=1,2,3}的一个顺序，比如π = ⟨1, 2, 3⟩。这代表了一个可能的因果序（causal order）——即祖先必须在后代之前。 2. 如何从π和CI关系构建DAG G_π？规则RU（Verma & Pearl, 1988）： - 对于排列中的任意一对变量(j, k)，且j排在k之前： - 如果X_j ⊥/⊥ X_k | X_Pre(k,π) \ {j}（即j和k在控制了排在k前的所有其他变量后，仍然相关），则在G_π中添加有向边 j → k。 3. 举例（幻灯片第12页）： - 假设 I(P) = {⟨X₁, X₃ | ∅⟩} （只有X₁和X₃边缘独立）。 - 对于排列 π₁ = ⟨1, 2, 3⟩： - 检查 (1,2): X₁ ⊥/⊥ X₂ | ∅（是的，相关） → 加边 1→2。 - 检查 (1,3): X₁ ⊥/⊥ X₃ | {X₂}（在控制了X₂后，1和3的原因2被block掉了，所以条件独立） → 不加边 1→3。 - 检查 (2,3): X₂ ⊥/⊥ X₃ | {X₁}（在控制了X₁后，2和3可能仍有其他路径，所以相关） → 加边 2→3。 - 得到的G_π₁是 1 → 2 → 3。 - 对于排列 π₂ = ⟨1, 3, 2⟩： - 检查 (1,3): X₁ ⊥/⊥ X₃ | ∅（边缘独立） → 不加边 1→3。 - 检查 (1,2): X₁ ⊥/⊥ X₂ | {X₃}（在控制了X₃后，X₃作为“对撞子”会打开新的路径，所以可能相关） → 加边 1→2。 - 检查 (3,2): X₃ ⊥/⊥ X₂ | {X₁}（相关） → 加边 3→2。 - 得到的G_π₂是 3 → 2 ← 1（一个v-结构）。

  1. 核心思想：SP算法需要枚举所有6个排列，构造6个DAG，然后选出边数最少的。在这个例子里，G_π₁有2条边，G_π₂也有2条边，其他排列可能产生更多边。SP会返回这2个（如果唯一）或它们所属的MEC。

  2. tuck操作的直观想法：这个操作作用于一个排列π，并选择其中一对变量(j,k)，其中π中j在k之前，且G_π中有边j→k。它通过移动元素来产生一个新的排列π'，旨在让新排列π'诱导出的DAG G_π'比原来的DAG 更稀疏（边数更少）。报告用了一个生动的“塞衬衫”比喻：

    • γ（γ = k在G_π中的祖先）= 你的“内衣”，要先贴身塞好（移到k紧前面）。
    • k = “衬衫”，塞在“内衣”外面。
    • γ^c（k的非祖先）= “腰带”，压在“衬衫”上面（放在最外面）。
    • j = 你要操作的“扣子”，把它从k前面移到k后面，看看这样“塞”之后，是否能让“衬衫”（DAG）更平整（更稀疏）。

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

[0:00:06 - 0:07:18] 背景与动机 - 介绍：讲者Wayne Lam（CMU哲学系）感谢OCIS邀请，介绍合作者Bryan Andrews和Joseph Ramsey。概述报告内容：因果发现、SP算法及其不可扩展性、TSP/ESP的提出。 - 核心动机：SP算法在理论上很美好（在u-frugality下渐近正确，假设弱于faithfulness），但计算上超级指数（m!），无法用于超过10个变量。我们需要正确但贪心的 SP版本。 - GRaSP的引入：讲者提出GRaSP，包含三个层次（GRaSP0/1/2）。GRaSP2是他们的创新，性能极其出色。关键在于引入 tuck 操作，能够高效探索DAG空间。

[0:07:19 - 0:18:36] 形式化定义与SP算法回顾 - [0:07:43] 定义了DAG G、顶点集、有向边、d-分离。定义了条件独立 I(P) 和d-分离 I(G)。 - [0:11:09] 回顾了因果马尔可夫（CMC）（I(G) ⊆ I(P)）和因果忠实性（CFC）（I(G) = I(P)）。说明算法通常目标输出是马尔可夫等价类（MEC）。忠实性虽好，但在有限样本下容易被几乎违反。 - [0:12:35] 幻灯片展示了假设强度的谱系：Faithfulness < u-frugality (u-frugality) < Markov。 - [0:15:50] 定义了稀疏性（Frugality）和唯一稀疏性（u-frugality）（又称Sparsest Markov Representation）。指出SP算法在唯一稀疏性下正确。 - [0:16:59] 回顾SP：枚举排列π，用规则RU (j→k) in G_π ⇔ j∈Pre(k,π) ∧ X_j ⊥/⊥ X_k | X_Pre(k,π) \{j} 构造DAG G_π，返回最稀疏的。

[0:18:37 - 0:30:22] TSP、ESP及其极限 - [0:18:37] 介绍基于排列的方法：π是因果序等价于生成DAG G_π。由UU构造的DAG G_π总是SGS-最小的（其任何子图都不能再与P马尔可夫）。 - [0:20:58] TSP (Triangle SP): 使用Chickering序列定理在DAG空间进行贪心深度优先搜索。每次操作可以反转或删除一条覆盖边。TSP保证输出P-最小的DAG。 - [0:21:06] 讲者指出核心理论问题：Solus等人（2021）声称TSP的条件比faithfulness弱，但这是错误的。Wayne等人证明 Faithfulness = u-P-minimality = TSP-condition。这意味着TSP的正确性仍然需要faithfulness，没有达到Weaken Faithfulness的目标。 - [0:26:53] ESP (Edge SP): 将搜索空间转换为排列hedron（permutohedron，通过相邻转置连接的排列图），然后压缩成DAG associahedron（将生成相同DAG的排列坍缩为一个点）。 - [0:28:37] ESP在这个associahedron上进行弱递减步长的贪心深度优先搜索。Solus等人（2021）证明 ESP-condition 严格弱于 TSP-condition (faithfulness)。 - [0:29:43] ESP的致命缺陷：需要预先完整地计算出整个DAG associahedron。这本身就不具备可扩展性，因此他们没有实现ESP。 - [0:30:11] 核心问题：是否存在一种高效的方式来实现ESP，使其可扩展？

[0:30:23 - 0:38:56] GRaSP：我们的工作 - [0:30:23] GRaSP的引入：提出GRaSP，通过一个核心操作 tuck，解决了ESP的效率问题，并延伸出性能更强的GRaSP2。 - [0:30:46] GRaSP的三层结构：t∈{0,1,2} 定义了tier。t=0只操作覆盖边（等价于TSP）；t=1只操作单一边（singular edges，即没有其他路径的可达边，等价于ESP但更高效）；t=2操作所有边（GRaSP2）。层级从低到高应用，且更高层级需要更弱的正确性假设。 - [0:31:40] tuck操作详解：给定排列π中一对(j,k)（j在k前且G_π中有j→k），tuck(π, j, k) 产生一个新排列。它把k在G_π中的所有祖先（γ） 放在k前面，然后移动j到k后面，再将非祖先部分（γ^c）放在j后面。这个操作旨在寻找更稀疏的DAG。 - [0:32:34] tuck的直观理解（衬衫比喻）：γ（祖先）是内衣→先塞好；k是衬衫→塞在内衣外；γ^c（非祖先）是腰带→压住衬衫；j是扣子→从衬衫内移到衬衫外。目的是让整体更平整（更少边）。 - [0:34:58] GRaSP的伪代码：给定P、初始π、tier t和DFS深度d，它递归地尝试对所有边应用tuck，如果新排列诱导的DAG得分（负边数或BIC）不下降，则继续深入探索，否则返回得分更好的DAG。 - [0:37:44] 理论保证： - GRaSP0（无界深度）= TSP。 - GRaSP1（无界深度）= ESP，但GRaSP1是高效的，因为它只需要通过tuck操作（作用于singular edges）来探索邻居，而无需预先计算整个associahedron。 - URG_aSP2 的正确性条件严格弱于 GRaSP1 条件 (ESP)，但严格强于 u-frugality。它不能完全在唯一稀疏性下工作，但比忠实性宽松。幻灯片32页的因果剃刀谱系图清晰展示了这一包含关系。 - [0:38:56] 一个重要结论：u-frugality 对 GRaSP2 的正确性是必要但不充分的，存在反例。

[0:39:00 - 0:44:15] 模拟与应用 - [0:39:00] 讲者简要介绍了如何在有限样本下用Grow-Shrink算法识别马尔可夫边界来构造DAG（使用BIC评分替代条件独立检验）。 - [0:41:08] 模拟设置：线性高斯模型，BIC惩罚系数=2，GRaSP深度 d=3（覆盖边）/ d=2（非覆盖边），结果与真实CPDAG（MEC的图表示）比较。 - [0:42:36] 模拟结果： - 改变平均度数（p=60, n=1000）：GRaSP2（方形点）的准确率极高，几乎不受图密度影响，远超GES、PC，也明显优于GRaSP0/1。 - 改变变量数（n=1000, 固定稀疏度）：GRaSP2的性能同样卓越，即使在p=100时仍保持很高准确率。 - 运行时间（p=60）：GRaSP2仅需不到2分钟，具有很好的可扩展性。相比，ESP需要预先计算associahedron，是不可行的。

[0:44:16 - 0:46:43] 未来工作 - 评分准则：是使用负边数还是BIC？在非参数模型中，最稀疏模型可能不是参数最少模型。也许应该假设唯一参数最小性（unique-parameter-minimality） 而非u-frugality。 - 减少贪心：当前只允许得分不下降的移动。是否可以允许一些暂时的得分下降，以跳出局部最优？ - 潜变量：GRaSP如何扩展到存在潜变量的情况（如结合FCI算法）？ - 更广泛比较：与更多算法、在离散和混合分布、真实数据上进行比较。

四、对应论文与开放问题

对应论文： - 本报告对应的论文很可能是： Lam, W., Andrews, B., & Ramsey, J. (2023). "Greedy Relaxations of the Sparsest Permutation Algorithm". 该论文可在 arXiv 上获取（具体链接可查），其内容与报告的幻灯片结构和理论结果高度吻合。合作者、机构（CMU哲学系）、年份都匹配。

开放问题（每条扎根于转写/幻灯片）：

  1. 评分准则的唯一性理论 (幻灯片第38页，转写 [0:44:18])： > “The sparsest model may not have the fewest parameters… assume unique-parameter-minimality instead of u-frugality?” 问题：对于非高斯或非参数模型，参数个数与边数并不一致。是否存在一个比u-frugality（基于边数）更合理的“唯一稀疏性”概念，如“唯一参数最小性”？GRaSP2正确性所需的理论假设能否向这个方向更新？

  2. GRaSP2的几何/组合解释 (讨论者Alex Markham在 [0:58:27 - 0:59:41]，以及讲者在 [1:01:07-1:02:14] 的回应)： > Alex: “GRaSP2 doesn’t just walk along the edges… it’s able to jump between points… can we give GRaSP2 a geometric interpretation like ESP?” > Wayne: “That is true. Because one edge you can have two different tuck operations… That is a difficulty of understanding what GRaSP2 is doing.” 问题：tuck操作对于同一个DAG中的同一条边可能产生多个不同的新排列（因为γ和γ^c的划分可能不唯一），这导致GRaSP2的搜索空间不再是一个标准的“DAG associahedron”。能否定义一个更广义的、包含这种非确定性邻接关系的组合结构（如多面体或单纯复形的某种推广）来描述GRaSP2的搜索空间？ 这个问题直接关系到对算法行为的理论理解。

  3. GRaSP2的“弱贪心”与跳出局部最优 (幻灯片第38页，转写 [0:45:00])： > “Tolerate some score declines in the DFS procedure?” 问题：GRaSP1/2的贪心性质可能导致它陷入局部最优解。如果允许在搜索过程中短暂接受得分下降（例如模拟退火或束搜索），能否在理论上证明其可以在更弱的假设（如u-frugality）下正确？或者能否设计一个只需要简单假设但保证不陷入严重次优解的“温和贪心”版本？

  4. 扩展到含潜变量场景 (幻灯片第38页，转写 [0:45:31])： > “GRaSP with latent variables: GRaSP + FCI...” 问题：GRaSP基于“无混淆（因果充分性）”假设（无潜变量）。如何将GRaSP的tuck操作与FCI（Fast Causal Inference）或其变体结合，使得能在允许潜变量和选择偏差的情况下进行可扩展的因果发现？这可能涉及定义一个新的“偏序”或“潜变量适应”的tuck操作。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论