跳转至

Estimation of Gaussian directed acyclic graphs using partial ordering information with applications to DREAM3 networks and dairy cattle data

作者: Syed Rahman, Kshitij Khare, George Michailidis, Carlos Martínez, Juan Carulla
来源: Annals of Applied Statistics
主题: 因果推断
相关性: 8/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么

这个子方向要解决的根本问题是：如何在高维情形下从观测数据估计有向无环图的拓扑结构。在因果推断与图模型中，DAG 是刻画变量间因果结构的核心工具。当前该方向已相当成熟：从早期依赖条件独立性检验的约束方法（如 PC 算法），到高维情形下的惩罚似然与凸优化方法，再到利用先验信息（如节点序）降低计算复杂度与识别不确定性。本文处于"利用部分先验信息"这一中间地带，试图在"无任何先验"与"全序已知"之间架桥。

发展脉络

奠基工作（无序情形）： - Kalisch & Bühlmann (2007) [2]：证明了 PC 算法在高维稀疏 DAG 下的一致性，是约束方法的里程碑。但 PC 算法不利用节点序，搜索空间巨大，且依赖 faithfulness 假设。 - Shojaie & Michailidis (2009) [9]：在节点有自然序的前提下，将 DAG 估计转化为一系列回归问题，用 Lasso/Adaptive Lasso 实现高维变量选择一致性。这是"有序"情形的奠基工作。 - van de Geer & Bühlmann (2012) [10]：用 \(\ell_0\) 惩罚似然研究高维 DAG 估计，不依赖 faithfulness，给出了 Frobenius 范数收敛率。

主要进展（凸优化与无序搜索）： - Aragam & Zhou (2014) [1]：提出 concave penalized likelihood，在不限制搜索空间的前提下实现快速结构学习，且不要求 faithful DAG 表示。这是对传统 \(\ell_0\) 惩罚（如 BIC）的重要改进。 - Khare et al. (2017) [4]：提出基于 Cholesky 分解的凸优化框架，对协方差矩阵的 Cholesky 因子施加稀疏惩罚，保证正定性，且估计的稀疏模式对应一个 DAG。这是本文方法论的直接前身。

当前 Frontier（先验信息的利用）： - Cao et al. (2016) [11]：在贝叶斯框架下研究 DAG-Wishart 先验的后验收缩率与图选择一致性，给出了 \(p\) 随 \(n\) 指数增长的收敛结果。 - Champion et al. (2011) [13]：用遗传算法嵌套凸优化来同时学习拓扑结构与节点序，但计算成本高。

本文的位置： 本文填补了"无序"与"全序"之间的空白——当只有部分序（partition-based partial ordering）已知时，如何高效估计 DAG。作者指出，这种中间情形在实际应用中很常见（如农业生态系统中，某些变量组之间的因果方向已知，但组内顺序未知），但现有方法要么忽略先验（效率低），要么要求全序（不现实）。

子线索聚类

被引文献大致落在三条子线索上：

  1. 无序情形的结构学习：PC 算法 [2]、\(\ell_0\) 惩罚似然 [10]、concave penalized likelihood [1]。这一簇的核心挑战是 DAG 的非识别性（Markov 等价类）与 NP-hard 搜索空间。

  2. 有序情形的凸优化方法：Shojaie & Michailidis [9]、Khare et al. [4]、Cao et al. [11]。当节点序已知时，DAG 估计退化为一系列回归问题，可用 Lasso 等凸方法高效求解。这一簇的理论更完善，但依赖强假设。

  3. 应用驱动的网络推断：DREAM 挑战赛 [6, 8]、基因调控网络综述 [3]。这一簇关注方法在真实数据上的表现，强调基准测试与领域知识整合。

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

  1. 识别性：在无干预或无序信息时，DAG 只能识别到 Markov 等价类。如何利用先验信息（如部分序、干预数据）打破识别性瓶颈？
  2. 计算可行性：DAG 结构学习是 NP-hard。在高维情形下，如何设计多项式时间算法？凸松弛、贪婪搜索、先验约束各有什么 trade-off？
  3. 理论保证：在高维稀疏设定下，估计的一致性、收敛率、变量选择性质是什么？对正则化参数如何选择？
  4. 先验信息的整合：领域知识（如时间序、因果序）如何形式化并嵌入估计框架？部分序信息能带来多少增益？

当前主流方法与瓶颈： - 约束方法（PC 类）：依赖条件独立性检验，在高维时计算爆炸，且对 faithfulness 假设敏感。 - 惩罚似然方法：在有序情形下高效，但无序时需搜索所有排列，计算不可行。 - 贝叶斯方法：后验收缩率有理论保证，但 MCMC 在高维时收敛慢。

⚠️ 作者的 framing

作者将缺口 frame 为：现有方法要么假设无序（计算难、识别差），要么假设全序（假设太强），而实际中常见的"部分序"信息未被充分利用。本文的 Partition-DAG 方法被定位为"显然的下一步"——利用部分序约束搜索空间，既降低计算成本，又改善识别性。

被淡化或回避的竞争路线： - 干预数据与多环境数据：Shojaie et al. [12] 利用干预数据推断因果网络，这是另一条打破识别性的路径，但本文未深入比较。 - 非高斯假设：基于独立成分分析（ICA）的方法可在无序时识别 DAG，但本文局限于高斯假设。 - 连续优化方法（如 NOTEARS）：近年来用 acyclicity constraint 的连续优化方法发展迅速，但本文未引用或比较。

缺失的引用： - NOTEARS (Zheng et al., 2018)：将 DAG 学习转化为无约束优化，是近年热点，但本文未引用。 - GES (Greedy Equivalence Search)：经典得分方法，在有限样本表现稳健，但未在仿真中比较。

张力

未见明显对立引用。被引工作之间更多是互补关系：无序方法提供基准，有序方法提供理想情形的上界，本文填补中间地带。

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

第一步：符号、模型、可观测数据

符号： - \(p\)：变量维数（节点数）。 - \(n\)：样本量。 - \(X = (X_1, \ldots, X_p)^\top\)：\(p\) 维随机向量，服从高斯分布。 - \(\mathcal{G} = (V, E)\)：有向无环图，\(V = \{1, \ldots, p\}\) 为节点集，\(E \subset V \times V\) 为边集。 - \(\pi: V \to \{1, \ldots, p\}\)：节点的一个拓扑排序，若 \((i, j) \in E\)，则 \(\pi(i) < \pi(j)\)。 - \(\mathcal{O} = \{O_1, \ldots, O_K\}\)：节点的一个划分，每个 \(O_k\) 是 \(V\) 的子集，且互不相交、并集为 \(V\)。 - 部分序：已知若 \(k < l\)，则 \(O_k\) 中所有节点在 \(O_l\) 中所有节点之前。但 \(O_k\) 内部节点的顺序未知。 - \(\mathbf{X} \in \mathbb{R}^{n \times p}\)：观测数据矩阵，每行是一个独立样本。 - \(\Sigma\)：\(X\) 的协方差矩阵，\(\Omega = \Sigma^{-1}\) 为精度矩阵。 - \(L\)：\(\Omega\) 的 Cholesky 分解下三角因子，\(\Omega = L D L^\top\)，其中 \(D\) 为对角矩阵，\(L\) 为单位下三角矩阵。

模型： - 高斯 DAG 模型：\(X \sim \mathcal{N}(0, \Sigma)\)，且 \(\Sigma\) 对应的 DAG 为 \(\mathcal{G}\)。 - 结构方程模型（SEM）表示：\(X_j = \sum_{i \in \text{pa}(j)} \beta_{ij} X_i + \epsilon_j\)，其中 \(\text{pa}(j)\) 为 \(j\) 的父节点集，\(\epsilon_j \sim \mathcal{N}(0, \sigma_j^2)\) 独立。 - Cholesky 与 DAG 的对应：若节点按拓扑序排列，则 \(L\) 的非对角非零元对应 DAG 的边，\(L_{ij} \neq 0 \Leftrightarrow (i, j) \in E\)。

可观测数据： - 观测到 \(n\) 个独立同分布样本 \(\mathbf{X} = (x^{(1)}, \ldots, x^{(n)})^\top\)。 - 已知先验：划分 \(\mathcal{O} = \{O_1, \ldots, O_K\}\) 及其顺序（部分序）。 - 不可观测/待估计：完整的拓扑排序 \(\pi\)（需在部分序约束下推断）、DAG 结构 \(\mathcal{G}\)、参数 \(\beta_{ij}, \sigma_j^2\)。

第二步：最小内核

最简特例：\(K=2\) 情形（两个分区）

设 \(p=4\)，节点为 \(\{1, 2, 3, 4\}\)。已知部分序为 \(O_1 = \{1, 2\}\)，\(O_2 = \{3, 4\}\)，即 \(\{1, 2\}\) 中节点在 \(\{3, 4\}\) 中节点之前，但 \(\{1, 2\}\) 内部顺序未知，\(\{3, 4\}\) 内部顺序也未知。

目标：估计 DAG 结构，即哪些节点之间有边。

核心思路： 1. 搜索空间缩减：无序时需搜索所有 \(4! = 24\) 种排列。部分序约束下，只需搜索 \(O_1\) 内部 \(2! = 2\) 种排列与 \(O_2\) 内部 \(2! = 2\) 种排列的组合，共 \(2 \times 2 = 4\) 种排列。搜索空间从 \(O(p!)\) 降至 \(O(\prod_{k=1}^K |O_k|!)\)。

  1. 对每个候选排列，DAG 估计退化为回归：给定一个排列 \(\pi\)，将节点按 \(\pi\) 重排后，DAG 估计等价于对每个节点 \(j\)，用其前面的节点 \(\{i: \pi(i) < \pi(j)\}\) 做回归，用 Lasso 选择父节点。

  2. 选择最优排列：比较所有候选排列对应的惩罚似然值，取最优者。

数学问题：

\[\hat{\pi}, \hat{L} = \arg\min_{\pi \in \Pi_{\mathcal{O}}} \min_{L \in \mathcal{L}(\pi)} \left\{ -\ell(\mathbf{X}; L) + \lambda \|L\|_1 \right\}\]
其中 \(\Pi_{\mathcal{O}}\) 为满足部分序约束的排列集合，\(\mathcal{L}(\pi)\) 为对应排列 \(\pi\) 的 Cholesky 因子空间，\(\|L\|_1\) 为 \(L\) 的非对角元绝对值之和（稀疏惩罚）。

为什么成立： - 高斯似然可分解为各节点回归似然之和。 - 给定排列，每个节点的父节点选择是独立的 Lasso 问题，有高效解法。 - 部分序约束将排列搜索空间从阶乘级降至分区内部阶乘的乘积，在分区数 \(K\) 较小或分区大小较均衡时，搜索空间大幅缩减。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：在高斯 DAG 结构学习中，当只有部分序信息（基于划分的部分序）已知时，如何高效估计 DAG 结构。
  2. 核心工具/方法：提出 Partition-DAG 算法，在部分序约束下枚举候选排列，对每个排列用惩罚似然（基于 Cholesky 分解）估计 DAG，选择最优者。
  3. 主要结论：在 DREAM3 酵母网络仿真中，Partition-DAG 在速度和精度上均优于忽略顺序信息的 CCDr 和 PC 算法，接近全序已知方法（CSCS）的性能；在奶牛农业数据应用中，推断的因果结构与领域知识一致。

关键设定与假设

设定： - 部分序约束：已知划分 \(\mathcal{O} = \{O_1, \ldots, O_K\}\)，若 \(k < l\)，则 \(O_k\) 中节点在 \(O_l\) 中节点之前。这是本文的核心设定，介于"无序"与"全序"之间。 - 高斯假设：\(X \sim \mathcal{N}(0, \Sigma)\)，这是利用 Cholesky 分解与似然方法的前提。

假设： - 稀疏性：真实 DAG 的边数 \(|E|\) 远小于 \(p\)，即 \(|E| = o(p)\) 或 \(|E| = O(p^\alpha)\)，\(\alpha < 1\)。这是高维结构学习的标准假设。 - 部分序正确性：已知的部分序与真实 DAG 的拓扑序相容，即不存在违反部分序的边（从 \(O_l\) 指向 \(O_k\)，\(k < l\)）。这是识别性的关键假设。 - 正则化参数选择：用交叉验证或 BIC 选择惩罚参数 \(\lambda\)。

相比已有文献的放宽/强化： - 相比 Shojaie & Michailidis [9] 和 Khare et al. [4] 要求全序，本文放宽为部分序。 - 相比 Aragam & Zhou [1] 和 PC 算法 [2] 假设无序，本文利用先验信息，但假设更强（部分序正确性）。

主要结果

算法结果： - Partition-DAG 算法： 1. 枚举所有满足部分序约束的排列 \(\pi \in \Pi_{\mathcal{O}}\)。 2. 对每个排列 \(\pi\)，计算 Cholesky 分解的惩罚似然估计：

\[\hat{L}^{(\pi)} = \arg\min_{L \in \mathcal{L}(\pi)} \left\{ -\ell(\mathbf{X}; L) + \lambda \|L\|_1 \right\}\]
3. 选择使惩罚似然最小的排列：
\[\hat{\pi} = \arg\min_{\pi \in \Pi_{\mathcal{O}}} \left\{ -\ell(\mathbf{X}; \hat{L}^{(\pi)}) + \lambda \|\hat{L}^{(\pi)}\|_1 \right\}\]
4. 输出 \(\hat{\mathcal{G}}\) 对应的 DAG 结构。

仿真结果（DREAM3 酵母网络）： - 数据：DREAM3 挑战赛 [8] 的酵母基因调控网络，节点数 \(p=100\)，样本量 \(n=100\)。 - 部分序构造：将节点随机分为 \(K\) 个分区，\(K \in \{2, 5, 10, 20\}\)，模拟不同程度的先验信息。 - 比较方法： - CCDr [1]：无序情形的 concave penalized 方法。 - PC 算法 [2]：约束方法，无序。 - CSCS [4]：全序已知的 Cholesky 稀疏方法。 - Partition-DAG：本文方法，部分序已知。 - 评价指标：F1-score、精确率、召回率、计算时间。 - 结果： - Partition-DAG 的 F1-score 随分区数 \(K\) 增加而提高，接近 CSCS（全序上界）。 - 计算时间显著低于 CCDr 和 PC，因为搜索空间缩减。 - 当 \(K=2\)（最弱先验）时，Partition-DAG 仍优于 CCDr 和 PC。

真实数据应用（奶牛农业生态系统）： - 数据：奶牛养殖数据，\(p=12\) 个变量（饲料、产奶量、环境指标等），\(n=200\)。 - 部分序来源：领域知识（如饲料影响产奶量，产奶量影响经济效益）。 - 结果：推断的 DAG 与领域专家的因果假设一致，如"饲料量 → 产奶量 → 经济效益"。

证明路线与技术技巧

本文为应用/方法型论文，理论证明相对简洁，主要依赖已有结果。

理论保证： - 命题 1（排列选择一致性）：在部分序正确、稀疏性、正则化参数适当选择的条件下，真实排列 \(\pi^*\) 的惩罚似然值以高概率小于其他候选排列。 - 直觉：真实排列对应的 Cholesky 因子更稀疏，惩罚似然更小。 - 证明思路：沿用 Khare et al. [4] 的 Cholesky 估计一致性结果，结合排列枚举的有限性（部分序约束下）。

技术技巧： - Cholesky 分解与 DAG 的对应：利用高斯 DAG 模型下，精度矩阵的 Cholesky 因子稀疏模式对应 DAG 的边，将图结构学习转化为稀疏矩阵估计问题。 - 惩罚似然凸优化：对每个固定排列，优化问题是凸的（\(\ell_1\) 惩罚），可用坐标下降等高效求解。 - 排列枚举的缩减：部分序约束将排列空间从 \(O(p!)\) 降至 \(O(\prod_{k=1}^K |O_k|!)\)，在分区数 \(K\) 较小或分区大小较均衡时，计算可行。

真实例子与应用

DREAM3 酵母网络仿真： - 目的：验证 Partition-DAG 在标准基准数据上的性能。 - 数据：DREAM3 挑战赛的酵母网络，\(p=100\)，真实网络结构已知（用于评估）。 - 部分序构造：将节点按真实拓扑序排序后，随机分为 \(K\) 个分区，模拟不同程度的先验信息。 - 结果：Partition-DAG 在 F1-score 上优于 CCDr 和 PC，接近 CSCS；计算时间随 \(K\) 增加而减少。

奶牛农业数据应用： - 目的：展示方法在真实数据上的实用性。 - 数据：奶牛养殖数据，\(p=12\) 个变量，包括饲料量、产奶量、环境指标、经济效益等。 - 部分序来源：领域专家提供的因果层级（如饲料 → 产奶 → 经济）。 - 结果：推断的 DAG 与领域知识一致，如"饲料量 → 产奶量"、"产奶量 → 经济效益"等边被正确识别。

🔎 结论是否比证明窄

  • 排列枚举的计算可行性：作者声称 Partition-DAG 在部分序约束下"高效"，但当分区大小不均衡时（如某个分区接近 \(p\)），排列空间仍可能很大。文中未给出计算复杂度的严格界，仅在仿真中展示 \(p=100\) 时可行。
  • 部分序正确性假设：理论结果假设部分序与真实 DAG 相容，但实际中部分序可能来自专家知识，存在错误。文中未讨论部分序错误时的稳健性。

四、开放问题

  1. 部分序错误时的稳健性：若部分序与真实 DAG 不相容（存在违反部分序的边），Partition-DAG 的表现如何？是否有检测或纠正机制？（扎根于假设部分序正确性，实际应用中可能不满足）
  2. 非高斯情形的推广：本文局限于高斯 DAG 模型，如何推广到非高斯或半参数情形？（扎根于高斯假设，限制了应用范围）
  3. 计算复杂度的严格界：在分区大小不均衡时，排列枚举的计算成本如何？是否有更高效的搜索策略（如分支定界）？（扎根于仿真仅展示 \(p=100\)，未给出复杂度分析）
  4. 与其他先验信息的整合：部分序与其他先验（如干预数据、非高斯假设）如何结合？（扎根于引言提到部分序是"中间情形"，但未讨论与其他先验的协同）

Maintained by 陈星宇 · Homepage · Source on GitHub

评论