跳转至

Consistency guarantees for greedy permutation-based causal inference algorithms

作者: L Solus, Y Wang, C Uhler
主题: 因果推断
相关性: 7/10
链接: https://doi.org/10.1093/biomet/asaa104

一、领域脉络与小综述

这个方向是什么

这个子方向是因果结构学习（causal structure learning），核心问题是从观测数据中恢复有向无环图（DAG）所编码的因果结构。这是一个组合优化问题：给定 \(p\) 个节点，DAG 空间的大小是超指数级的（\(O(p! \cdot 2^{\binom{p}{2}})\)），且最大似然估计是 NP-hard 的。因此，主流方法不是精确求解，而是贪婪搜索——在某个离散空间（DAG 空间、马尔可夫等价类空间、或排列空间）上局部移动，优化一个评分函数（如 BIC、BDeu）。该方向的成熟度：理论上有大量一致性结果（在适当条件下，贪婪搜索可恢复真 DAG），但计算与统计的权衡仍是核心张力——搜索空间越大，统计一致性越强，但计算越昂贵；搜索空间越小，计算越快，但可能错过真 DAG。

发展脉络（history）

从 intro 引用的工作串成一条线：

  1. 奠基工作：Chickering (2002) 证明了 GES（Greedy Equivalence Search） 在马尔可夫等价类空间上的一致性——这是第一个在等价类空间上具有一致性保证的贪婪算法。它通过加边、删边、转向操作在等价类之间移动。留下的口子：等价类空间的大小仍远大于排列空间（\(p\) 个节点的等价类数约为 \(O(2^{p})\)），且 GES 的每一步需要评估大量候选操作。

  2. 主要进展——排列空间上的搜索：Teyssier & Koller (2005) 首次提出在排列空间上搜索——给定一个节点排序（ordering），最优 DAG 是每个节点只从排在它前面的节点中选择父集，这可通过独立子问题求解（每个节点的父选择是一个变量选择问题）。关键洞察：排列空间的大小是 \(p!\)，远小于 DAG 空间和等价类空间。但 Teyssier & Koller 的方法需要枚举所有排列（或随机采样），没有一致性保证。

  3. 当前 frontier——贪婪排列搜索：Solus, Wang & Uhler（本文）将排列空间上的贪婪搜索形式化为一个多面体边缘图上的单纯形类算法，并首次给出一致性和高维一致性保证。他们构造的 DAG associahedron 是一个排列多面体（permutohedron）的子多面体，其每个顶点对应一个 DAG（而非一个排列），且相邻顶点对应一个边翻转操作。本文的位置：填补了"排列空间上的贪婪搜索缺乏一致性理论"这一空白。

  4. 竞争路线：van de Geer & Bühlmann (2013) 给出了 \(\ell_0\)-惩罚似然估计的高维一致性（在 \(p > n\) 时），但需要求解一个 NP-hard 的优化问题，只能通过凸松弛近似。本文的贪婪搜索是多项式时间的（每步只需评估 \(O(p^2)\) 个候选），且在高维设定下也有理论保证。

子线索聚类

这些被引文献大致落在 3 条子线索上：

  • 线索 1：等价类空间上的贪婪搜索（Chickering 2002, Hauser & Bühlmann 2012）。核心：在马尔可夫等价类空间上搜索，一致性保证强，但搜索空间大、每步计算成本高。
  • 线索 2：排列空间上的搜索（Teyssier & Koller 2005, Solus et al. 本文）。核心：将问题分解为"找排序 + 选父集"，搜索空间小，但此前缺乏贪婪搜索的一致性理论。
  • 线索 3：惩罚似然与凸松弛（van de Geer & Bühlmann 2013, Loh & Bühlmann 2014）。核心：用 \(\ell_1\) 或 MCP 惩罚逼近 \(\ell_0\)，可处理高维，但解不一定对应 DAG（需后处理投影），且理论保证依赖于较强的条件（如 restricted eigenvalue）。

这个方向在追问的核心问题

  1. 一致性：贪婪搜索在什么条件下（样本量、信噪比、稀疏性）能恢复真 DAG？
  2. 计算-统计权衡：搜索空间越小（排列 vs. 等价类 vs. DAG），一致性条件是否越强？能否在保持多项式时间的同时达到最优统计率？
  3. 高维一致性：当 \(p > n\) 时，贪婪搜索是否仍能一致？需要什么额外条件（如父集大小的上界）？
  4. 非参数扩展：能否将排列搜索扩展到非参数或半参数因果模型（如加性噪声模型、非线性 SEM）？

⚠️ 作者的 framing（必须明确标注成"这是作者的说法"）

作者把缺口 frame 成："尽管排列空间上的搜索在计算上更高效（空间大小为 \(p!\)，远小于 DAG 空间和等价类空间），但此前没有贪婪排列搜索的一致性保证。本文填补了这一空白。"（见 intro 第 2-3 段）。作者淡化了以下竞争路线： - GES 的一致性：Chickering (2002) 的 GES 在等价类空间上已有强一致性，但作者认为等价类空间太大，计算成本高。 - 惩罚似然方法：van de Geer & Bühlmann (2013) 的高维一致性是在 \(\ell_0\) 惩罚下证明的，但作者认为该优化是 NP-hard 的，而本文的贪婪搜索是多项式时间。

什么明显该被引 / 该存在、却没出现在 intro 里？ - Bühlmann et al. (2014) "CAM: Causal Additive Model"：该文在排列空间上使用高维变量选择（如 PC 算法 + 独立性检验）来学习排序，与本文的贪婪搜索形成对比。未引可能因为 CAM 不是贪婪搜索，而是基于条件独立性检验的两阶段方法。 - Scanagatta et al. (2015) "Learning Bayesian Networks with Thousands of Variables"：该文使用 A 搜索在排列空间上精确学习 DAG，与本文的贪婪搜索形成对比。未引可能因为 A 是精确算法（指数时间），而本文是贪婪（多项式时间）。 - Raskutti & Uhler (2018) "Learning Directed Acyclic Graphs from Observations and Interventions"：该文结合观测和干预数据学习 DAG，与本文的纯观测设定互补。未引可能因为本文聚焦纯观测设定。

值得研究者去查的问题：这些未引文献是否在排列搜索的一致性上已有隐含结果？例如，CAM 的排序学习是否隐含了某种一致性？A* 搜索的精确性是否意味着贪婪搜索的次优性？

张力

未见明显对立引用。所有被引工作都承认 DAG 学习是 NP-hard，且贪婪搜索是实用妥协。主要张力在于搜索空间的选择：等价类空间（Chickering）vs. 排列空间（本文）vs. DAG 空间（传统方法），但作者没有直接比较这些空间上贪婪搜索的一致性条件强弱。

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

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

符号： - \(G = (V, E)\)：一个有向无环图（DAG），其中 \(V = \{1, \dots, p\}\) 是节点集，\(E \subseteq V \times V\) 是有向边集。 - \(\prec\)：一个节点排序（permutation / ordering），即 \(V\) 上的一个全序。若 \(i \prec j\)，则 \(i\) 排在 \(j\) 之前。 - \(\Pi(G)\)：与 DAG \(G\) 一致的所有排序的集合——即若 \(G\) 中有边 \(i \to j\)，则必须有 \(i \prec j\)。 - \(X = (X_1, \dots, X_p)\)：观测数据，\(n\) 个 i.i.d. 样本，每个样本是 \(p\) 维随机向量。 - \(\hat{\Sigma}\)：样本协方差矩阵。 - \(\text{score}(G)\)：一个评分函数，衡量 DAG \(G\) 对数据的拟合程度（如 BIC、BDeu）。本文使用BIC 评分：\(\text{BIC}(G) = \log L(\hat{\theta}_G) - \frac{\text{dim}(G)}{2} \log n\)，其中 \(\hat{\theta}_G\) 是 MLE，\(\text{dim}(G)\) 是自由参数数（即边数）。 - \(\text{sparsity}(G)\)：DAG \(G\) 的稀疏性，通常用边数 \(|E|\) 的负值衡量（越少边越稀疏）。 - \(\text{DAG}_p\)：所有 \(p\) 节点 DAG 的集合。 - \(\mathcal{A}_p\)：DAG associahedron，一个 \(p-1\) 维多面体，其顶点对应 DAG（更准确地说，对应 DAG 的排序等价类——见下文）。

模型： - 数据生成机制：假设数据来自一个线性高斯 DAG 模型：

\[X_j = \sum_{i \in \text{pa}(j)} \beta_{ij} X_i + \varepsilon_j, \quad \varepsilon_j \sim N(0, \sigma_j^2),\]
其中 \(\text{pa}(j)\) 是节点 \(j\) 在真 DAG \(G^*\) 中的父节点集。该模型等价于 \(X \sim N(0, \Sigma)\)，其中 \(\Sigma\) 满足有向无环图结构（即存在一个排序 \(\prec^*\) 使得 \(\Sigma\) 的 Cholesky 因子是下三角且稀疏）。 - 目标：从 \(n\) 个 i.i.d. 样本中恢复真 DAG \(G^*\)（或至少恢复其马尔可夫等价类）。 - 已知：真 DAG 是稀疏的（每个节点的父节点数 \(\leq s\)，\(s \ll p\)），且满足忠实性（faithfulness）条件——条件独立性关系完全由图结构决定。

可观测数据： - 研究者实际能观测到的是 \(n \times p\) 数据矩阵 \(\mathbf{X}\)，每行是一个样本，每列是一个节点。 - 想要但观测不到的是： - 真 DAG \(G^*\)（结构未知）。 - 真排序 \(\prec^*\)（未知，且不一定唯一——若 \(G^*\) 有多个拓扑排序）。 - 误差方差 \(\sigma_j^2\) 和系数 \(\beta_{ij}\)（需估计）。 - 识别依赖假设：忠实性 + 稀疏性 + 高斯性（或更一般的分布假设，但本文聚焦高斯）。

第二步：讲最小内核

最简特例：\(p = 3\) 个节点，真 DAG 是 \(1 \to 2 \to 3\)（链结构）。此时： - 真排序 \(\prec^*\)：\(1 \prec 2 \prec 3\)（唯一）。 - 所有可能的排序：\(3! = 6\) 个。 - 每个排序 \(\prec\) 对应一个最优 DAG：给定排序，每个节点 \(j\) 只从排在它前面的节点中选择父集，通过最小化 BIC 得到。例如，排序 \(1 \prec 2 \prec 3\) 下，节点 1 无父节点，节点 2 的父集从 \(\{1\}\) 中选，节点 3 的父集从 \(\{1, 2\}\) 中选。

贪婪排列搜索的核心思路： 1. 初始化：随机选一个排序 \(\prec^{(0)}\)。 2. 局部移动：在当前排序 \(\prec\) 中，考虑所有相邻交换（swap two adjacent nodes）。每次交换产生一个新排序 \(\prec'\)。 3. 评分：对每个新排序 \(\prec'\)，计算其对应的最优 DAG 的 BIC 评分（或稀疏性度量）。 4. 更新：如果存在一个相邻交换使评分改善（BIC 更大 / 更稀疏），则执行该交换，重复步骤 2-3；否则停止（达到局部最优）。

在这个特例下，要证的命题退化成什么？ - 一致性：当 \(n \to \infty\) 时，贪婪排列搜索以概率 1 收敛到真 DAG \(G^*\)（即 \(1 \to 2 \to 3\)）对应的排序（\(1 \prec 2 \prec 3\)）。 - 为什么成立：在 \(p=3\) 且真 DAG 是链时，BIC 评分在排序空间上是单峰的——真排序是全局最优，且从任何初始排序出发，通过相邻交换总能单调地到达真排序。例如： - 从排序 \(2 \prec 1 \prec 3\) 出发：交换 \(2\) 和 \(1\) 得到 \(1 \prec 2 \prec 3\)（BIC 改善），然后停止。 - 从排序 \(3 \prec 2 \prec 1\) 出发：交换 \(3\) 和 \(2\) 得到 \(2 \prec 3 \prec 1\)（BIC 改善），再交换 \(2\) 和 \(1\) 得到 \(1 \prec 2 \prec 3\)（BIC 改善），然后停止。 - 证明怎么走：需要证明 BIC 评分在排序空间上是严格凹的（或至少是单峰的），且相邻交换是局部改善的充分条件。这依赖于真 DAG 的忠实性和稀疏性。

一般情形：\(p\) 个节点，真 DAG 可能有多个拓扑排序。此时，贪婪排列搜索可能收敛到任何一个与真 DAG 一致的排序（即 \(\Pi(G^*)\) 中的任意一个）。一致性意味着：搜索以概率 1 收敛到 \(\Pi(G^*)\) 中的某个排序（而非一个错误的排序）。

核心数学困难：BIC 评分在排序空间上不是全局凹的——存在多个局部最优（对应不同的 DAG）。本文的关键想法是：DAG associahedron 的边图结构保证了从任何初始顶点出发，通过贪婪移动（最大化稀疏性）总能到达一个与真 DAG 对应的顶点，只要样本量足够大。这类似于单纯形算法在线性规划中的路径性质——尽管目标函数不是全局凹的，但多面体的组合结构保证了贪婪路径的正确性。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：为排列空间上的贪婪搜索算法提供一致性和高维一致性保证，用于从观测数据中学习 DAG 结构。
  2. 核心工具 / 方法：将贪婪排列搜索形式化为一个DAG associahedron（排列多面体的子多面体）边缘图上的单纯形类算法，通过最大化关联 DAG 的稀疏性（等价于最小化 BIC）在顶点之间移动。
  3. 主要结论：在适当条件下（忠实性、稀疏性、高斯性），贪婪排列搜索以概率 1 收敛到真 DAG 的某个拓扑排序（一致性）；当 \(p\) 随 \(n\) 增长时，若每个节点的父节点数有界且信噪比足够大，则搜索以高概率恢复真 DAG（高维一致性）。

关键设定与假设

完整设定（在第二节最小记号的基础上补全）： - 数据：\(n\) 个 i.i.d. 样本来自线性高斯 DAG 模型，协方差矩阵 \(\Sigma\) 满足有向无环图结构。 - 真 DAG \(G^*\)：稀疏（每个节点的父节点数 \(\leq s\)，\(s\) 可能随 \(p\) 增长但 \(s = o(n)\)），且满足忠实性（faithfulness）——所有条件独立性关系完全由图结构编码。 - 评分函数：BIC 评分，等价于最小化描述长度——\(\text{BIC}(G) = \log L(\hat{\theta}_G) - \frac{|E|}{2} \log n\)，其中 \(|E|\) 是边数。 - 搜索空间：所有 \(p!\) 个排序，但算法只在相邻交换（swap two adjacent nodes in the ordering）之间移动。 - DAG associahedron \(\mathcal{A}_p\)：一个 \(p-1\) 维多面体，其顶点对应排序等价类——两个排序等价当且仅当它们对应同一个 DAG（即它们都在 \(\Pi(G)\) 中）。每个顶点关联一个 DAG \(G\)，且相邻顶点对应一个边翻转（flip an edge in the DAG）或排序交换（swap two adjacent nodes in the ordering）。

假设（相比已有文献放宽或强化了哪些）： - 相比 GES (Chickering 2002)：本文假设忠实性（GES 也需此假设），但搜索空间更小（排列 vs. 等价类），因此一致性条件可能更强（需真 DAG 的排序是唯一的？——见下文）。 - 相比 Teyssier & Koller (2005)：本文假设BIC 评分（而非 BDeu），且要求贪婪搜索（而非枚举或随机采样）。Teyssier & Koller 没有一致性保证。 - 相比 van de Geer & Bühlmann (2013)：本文假设父节点数有界（\(s = O(1)\) 或 \(s = o(n/\log p)\)），而 van de Geer & Bühlmann 允许 \(s = O(n/\log p)\) 但需要 restricted eigenvalue 条件。本文的贪婪搜索是多项式时间，而 \(\ell_0\) 惩罚是 NP-hard。

主要结果

定理 1（一致性）：假设数据来自忠实、稀疏的线性高斯 DAG 模型，且真 DAG \(G^*\) 的排序是唯一的（即 \(G^*\) 只有一个拓扑排序）。则当 \(n \to \infty\) 时，贪婪排列搜索以概率 1 收敛到 \(G^*\) 对应的排序。 - 直觉：BIC 评分在排序空间上是渐近一致的——真排序的 BIC 严格大于任何其他排序的 BIC。贪婪搜索通过相邻交换单调地改善 BIC，最终到达真排序。 - 必要条件：排序唯一性——若 \(G^*\) 有多个拓扑排序（如 \(G^*\) 是空图或完全无向的 DAG），则搜索可能收敛到任意一个，但仍在 \(\Pi(G^*)\) 中。作者在推论中处理了非唯一情况。 - 解决的技术难点：证明 BIC 评分在排序空间上是局部单峰的——从任何初始排序出发，存在一条单调改善的路径到真排序。这需要分析 DAG associahedron 的边图结构，证明相邻交换的 BIC 差异与真 DAG 的边结构一致。

定理 2（高维一致性）：假设 \(p\) 随 \(n\) 增长，但每个节点的父节点数 \(s = O(1)\)（或 \(s = o(n/\log p)\)），且信噪比足够大（即非零系数 \(\beta_{ij}\) 的绝对值有下界）。则当 \(n \to \infty\) 时，贪婪排列搜索以概率 \(1 - o(1)\) 恢复真 DAG \(G^*\) 的某个拓扑排序。 - 直觉：在高维设定下，BIC 评分仍能一致地区分真排序和错误排序，只要稀疏性条件成立。关键是要控制假阳性（将无关节点选为父节点）和假阴性（遗漏真父节点）。 - 必要条件：父节点数有界 + 信噪比有下界。这比 van de Geer & Bühlmann (2013) 的 \(\ell_0\) 惩罚条件更强（后者允许 \(s = O(n/\log p)\)），但本文的算法是多项式时间。 - 解决的技术难点：证明在高维下，BIC 评分的排序一致性——即真排序的 BIC 以高概率大于任何错误排序的 BIC。这需要集中不等式（如 Bernstein 不等式）来控制估计误差，以及组合计数（错误排序的数量是 \(p!\)，但通过稀疏性假设可限制到多项式级）。

推论 1（非唯一排序）：若真 DAG \(G^*\) 有多个拓扑排序，则贪婪排列搜索以概率 1 收敛到 \(\Pi(G^*)\) 中的某个排序（即与 \(G^*\) 一致的排序）。此时，恢复的 DAG 是 \(G^*\) 的马尔可夫等价类（即与 \(G^*\) 有相同骨架和 v-结构的 DAG）。

证明路线与技术技巧

整体路线（3-5 步逻辑主干）：

  1. 步骤 1：将贪婪排列搜索映射到 DAG associahedron 的边图。证明每个排序 \(\prec\) 对应 DAG associahedron \(\mathcal{A}_p\) 的一个顶点，且相邻交换对应一条边。因此，贪婪搜索是在 \(\mathcal{A}_p\) 的边图上行走，每一步移动到使 BIC 最大的相邻顶点。

  2. 步骤 2：证明 BIC 评分在 \(\mathcal{A}_p\) 的顶点上是渐近一致的**。即，当 \(n \to \infty\) 时，真 DAG \(G^*\) 对应的顶点（即 \(\Pi(G^*)\) 中的排序）的 BIC 严格大于任何其他顶点的 BIC。这需要：

  3. 对每个排序 \(\prec\)，计算其最优 DAG 的 BIC 与真 DAG 的 BIC 之差。
  4. 证明该差是负的（真 DAG 的 BIC 更大），除非 \(\prec \in \Pi(G^*)\)。

  5. 关键引理：BIC 差可分解为每个节点的贡献，且每个节点的贡献依赖于其父集选择的正确性。

  6. 步骤 3：证明 \(\mathcal{A}_p\) 的边图是连通的**，且从任何顶点出发，存在一条单调改善的路径到真顶点。这依赖于 \(\mathcal{A}_p\) 的组合性质：

  7. \(\mathcal{A}_p\) 是单纯形（simplex）的推广——它是一个多面体，其面结构对应 DAG 的子图关系。

  8. 关键引理：若一个顶点 \(v\) 对应的 DAG \(G\) 不是真 DAG \(G^*\)，则存在一条边从 \(v\) 到一个 BIC 更大的顶点 \(v'\)（即 \(G'\) 比 \(G\) 更接近 \(G^*\)）。这条边对应一个边翻转或排序交换，使 \(G'\) 的边集更接近 \(G^*\) 的边集。

  9. 步骤 4：结合步骤 2 和 3。由于 BIC 是渐近一致的，且 \(\mathcal{A}_p\) 的边图保证存在单调改善路径，贪婪搜索（每一步选 BIC 最大的相邻顶点）必然收敛到真顶点。这类似于梯度上升在凸函数上的收敛性，但这里的目标函数（BIC）不是凸的，而是多面体上的拟凹函数。

  10. 步骤 5（高维情况）：用集中不等式证明 BIC 的有限样本一致性。关键是要控制：

  11. 估计误差：\(\hat{\Sigma}\) 与 \(\Sigma\) 的偏差，用 Bai-Silverstein 定理（随机矩阵理论）或 Bernstein 不等式控制。
  12. 组合复杂度：错误排序的数量是 \(p!\)，但通过稀疏性假设（父节点数 \(\leq s\)），可证明只有 \(O(p^{s+1})\) 个排序需要比较（因为每个节点的父集大小有限）。
  13. 信噪比条件：非零系数 \(\beta_{ij}\) 的绝对值必须大于某个阈值，以确保 BIC 能区分真父集和假父集。

关键跳跃点： - 最吃功夫的引理：引理 3（论文中编号可能不同）——证明 \(\mathcal{A}_p\) 的边图是BIC 单调的：若一个顶点 \(v\) 不是真顶点，则存在一条边到 BIC 更大的顶点。这需要分析 DAG 的边翻转操作如何影响 BIC，以及如何保证翻转方向总是改善的。难点在于：边翻转可能同时改变多个节点的父集，导致 BIC 变化不是单调的。作者通过忠实性假设保证：若 \(G\) 不是 \(G^*\)，则存在一条边 \(i \to j\) 在 \(G\) 中但不在 \(G^*\) 中（或反之），翻转该边可改善 BIC。 - 作者用什么办法绕过去：利用 DAG associahedron 的凸性——\(\mathcal{A}_p\) 是排列多面体（permutohedron）的子多面体，其面结构由排序的偏序决定。因此，边翻转对应排序中的相邻交换，而 BIC 的变化可分解为两个节点的贡献，从而简化分析。

技术技巧点名： - DAG associahedron 的组合结构：将 DAG 学习问题映射到多面体几何，利用多面体的边图性质保证贪婪路径的存在性。这是本文的核心创新——之前的工作（如 Chickering 2002）没有使用多面体框架。 - BIC 评分的分解：将 BIC 分解为每个节点的局部评分之和，使得相邻交换只影响两个节点的局部评分。这类似于坐标下降中的可分性。 - 集中不等式：在高维证明中使用 Bernstein 不等式和 Loeve 不等式控制估计误差。具体地，对每个候选父集 \(S \subseteq \{1, \dots, p\}\)，需要控制 \(\hat{\beta}_S\)（回归系数估计）与真值的偏差。 - 组合计数：通过稀疏性假设将错误排序的数量从 \(p!\) 降低到 \(O(p^{s+1})\)，使得 union bound 可行。

真实例子与应用

本文包含模拟实验和真实数据实验：

  • 模拟实验：
  • 数据：从随机 DAG（Erdős–Rényi 模型，边概率 \(2/p\)）生成线性高斯数据，\(p = 10, 20, 50\)，\(n = 100, 500, 1000\)。
  • 方法对比：将贪婪排列搜索（GPS）与 GES（Chickering 2002）、PC 算法（Spirtes et al. 2000）、MMHC（Tsamardinos et al. 2006）对比。
  • 结果：GPS 在结构汉明距离（SHD，即错误边数）上与其他方法相当或更优，尤其在 \(p=50\) 时。GPS 的计算时间远小于 GES（因为搜索空间更小）。

  • 这个例子想说明什么：验证理论——GPS 在有限样本下也能恢复真 DAG，且计算效率高。

  • 真实数据实验：

  • 数据：Saccharomyces cerevisiae（酵母）基因表达数据（\(p = 11\) 个基因，\(n = 100\) 个样本），来自 Sachs et al. (2005) 的经典因果推断数据集。
  • 方法：用 GPS 学习 DAG，与已知的共识网络（consensus network）对比。
  • 结果：GPS 恢复的 DAG 与共识网络在骨架（无向边）上高度一致（约 80% 的边匹配），且 GPS 找到的 v-结构与共识网络一致。
  • 这个例子想说明什么：展示 GPS 在真实数据上的实用性——尽管 \(p\) 很小，但 GPS 能恢复有生物学意义的因果结构。

🔎 结论是否比证明窄

  • 窄结论 1：定理 1 假设真 DAG 的排序唯一。但许多 DAG（如空图、完全无向的 DAG）有多个拓扑排序。作者在推论 1 中处理了非唯一情况，但推论只保证收敛到 \(\Pi(G^*)\) 中的某个排序，而非唯一恢复 \(G^*\)。论文中 claim "一致性" 时，有时隐含了排序唯一性，但未明确说明（见 intro 第 4 段："we provide the first consistency guarantees"——未限定唯一性）。
  • 窄结论 2：高维一致性（定理 2）要求父节点数有界（\(s = O(1)\)）。但许多实际 DAG 的父节点数可能随 \(p\) 增长（如 \(s = O(\log p)\)）。作者在讨论中承认这一限制，但未给出更宽松条件的证明。
  • 窄结论 3：所有结果假设线性高斯模型。作者在结论中提到"扩展到非线性模型是未来工作"，但未给出任何线索。因此，本文的结论不能直接推广到非参数或离散数据。

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

  1. 非唯一排序下的精确恢复：当真 DAG 有多个拓扑排序时，贪婪搜索只能保证收敛到 \(\Pi(G^*)\) 中的某个排序，但无法唯一恢复 \(G^*\)。能否通过后处理（如检查 v-结构）从 \(\Pi(G^*)\) 中恢复 \(G^*\) 的马尔可夫等价类？扎根：推论 1 的陈述——"converges to a permutation in \(\Pi(G^*)\)"（论文第 5 页）。

  2. 高维下的父节点数增长：定理 2 要求 \(s = O(1)\)。能否放宽到 \(s = O(\log p)\) 或 \(s = o(n/\log p)\)？这需要更强的集中不等式或不同的证明策略。扎根：定理 2 的假设——"the maximum in-degree \(s\) is bounded"（论文第 6 页）。

  3. 非线性模型扩展：本文的证明强烈依赖线性高斯假设（BIC 的分解形式、集中不等式）。能否扩展到加性噪声模型或非参数 SEM？这可能需要用核方法或样条来估计条件期望，并重新分析 BIC 的渐近性质。扎根：结论部分——"extending our results to nonlinear models is an important direction for future work"（论文第 8 页）。

  4. 计算-统计权衡的量化：本文的贪婪搜索是多项式时间（每步 \(O(p^2)\)），但一致性条件（排序唯一性、父节点数有界）比 GES 更强。能否量化这种权衡——即，搜索空间越小，需要多强的统计条件才能保持一致性？扎根：intro 第 3 段——"the space of permutations is much smaller than the space of DAGs and Markov equivalence classes"（论文第 2 页），但未给出定量比较。

提醒：要确认第 1 条是否是真 gap，去读 Chickering (2002) 的 GES 论文——GES 在等价类空间上搜索，自然处理了非唯一排序。GPS 能否通过类似的后处理达到相同效果？

Maintained by 陈星宇 · Homepage · Source on GitHub

评论