跳转至

Order-based structure learning without score equivalence

作者: Hyunwoong Chang, James J Cai, Quan Zhou
来源: Biometrika
主题: 因果推断
相关性: 8/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么
本文所在子方向是从观测数据中学习有向无环图（DAG）结构，重点是利用误差方差相等的假设来实现因果方向的可识别性。当前该方向的理论和方法已较成熟，但贝叶斯方法在计算可扩展性与理论保证（特别是异质方差下的选择一致性）方面仍存缺口。本文正是填补这一缺口的首个以等方差假设为基础的贝叶斯结构学习方法。

发展脉络（以本文 intro 和参考文献中的引用句定位）

  • 奠基工作：
  • Peters & Bühlmann (2014) 证明：在线性高斯 SEM 中，若所有误差方差相等，则 DAG 可从联合分布中完全识别（即不仅识别 Markov 等价类，还可识别方向）[文献[7]： “the directed acyclic graph can be recovered from the joint Gaussian distribution”]。

  • Shimizu et al. (2006) 等前作提出非高斯噪声下的识别，但等方差假设因其简洁性成为另一条主流。

  • 主要进展：

  • Chen et al. (2019) 和 Ghoshal & Honorio (2018) 提出确定性搜索算法，利用等方差假设来快速恢复 DAG。作者引用：“two deterministic search algorithms have been proposed recently for structure learning with equal error variances … shown to be advantageous in terms of computational cost and scale well to high-dimensional data”。但这类方法没有提供贝叶斯不确定性量化。
  • Lee et al. (2018) 和 Cao et al. (2019) 在高维贝叶斯 DAG 模型上建立了强选择一致性（strong selection consistency），但他们的方法依赖于“DAG-Wishart”先验，且要求误差方差相等或已知，不解决异质方差下的问题。
  • Zhou & Chang (2021) 研究了MCMC 在等价类空间上的混合行为，证明距离多项式的混合时间，但仅适用于无等方差假设的一般情景（等价类不可区分）。

  • Agrawal et al. (2018) 提出最小 I-MAP MCMC，通过条件独立性测试聚焦于高概率 DAG，但他们的方法不依赖等方差，且计算复杂度与最大入度指数相关。

  • 当前 Frontier：

  • 将等方差假设与贝叶斯框架结合以同时获得方向识别性和不确定性量化，并发展快速 MCMC 采样器（本文定位）。

  • 放松等方差假设仍保持选择一致性：本文第一个证明在异质方差下（即等方差假设被违反时）贝叶斯模型仍能一致选择真图（定理1）。

  • 本文的位置：作者在引言中明确：“we propose the first Bayesian method for structure learning under the equal variance assumption … but we also prove that strong selection consistency still holds when the error variances are heterogeneous”。这意味着作者将自身置于等方差贝叶斯方法的开创者位置，并提供了比现有确定性算法更高的灵活性（后验分布）。

子线索聚类（从被引文献看）

子线索 代表性文献 核心做法 留下的口子
1. 基于排序的贝叶斯方法 Friedman & Koller (2003), Agrawal et al. (2018), Kuipers et al. (2022) 在排序空间上做 MCMC，避免直接搜索 DAG 空间 通常要求结构性先验（如稀疏性），但无法利用等方差识别方向；Agrawal 等方法依赖于分数等价先验（score equivalent），因而不能区分等价类内的方向。
2. 基于等价类的搜索 Chickering (1996), Castelletti et al. (2018) 直接搜索 CPDAG 空间，避免在等价类内冗余移动 仍陷于分数等价先验的限制，且混合行为在理论上未获充分分析。
3. 等方差假设下的确定性算法 Chen et al. (2019), Ghoshal & Honorio (2018) 利用条件方差排序或优化目标进行非贝叶斯估计 缺乏不确定性量化，且在异质方差下表现未知。
4. 高维贝叶斯 DAG 一致性 Lee et al. (2018), Cao et al. (2019) 在给定排序下建立选择一致性，使用 DAG-Wishart 先验 假设误差方差相等或已知，且未提供 MCMC 采样器的混合理论。

核心问题（方向内仍在追问的）：

  1. 如何在不做分数等价假定的前提下，进行贝叶斯结构学习？ 分数等价先验（如 BGe 先验 [Geiger & Heckerman, 2002]）导致所有 Markov 等价 DAG 获得相同后验，从而无法区分等价类内的方向。
  2. 等方差假设是否必要？若它被违反，贝叶斯方法能否仍实现选择一致性？ 现有理论大多假设误差方差相等以实现方向识别。
  3. 如何设计 MCMC 采样器在排序空间上的混合时间可控，且不受最大入度指数限制？
  4. 如何在高维设定下得到后验收缩或 MAP 一致性的最优条件？

⚠️ 作者的 framing（必须明确标注为作者说法）：

作者在引言中明确将缺口定位为：“第一个在等方差假设下的贝叶斯方法，并且证明即使异质误差方差仍有一致性”。他们淡化了其他竞争路线——比如直接搜索 CPDAG（等价类）的方法（Castelletti et al., 2018; Zhou & Chang, 2021）。作者声称：“most Bayesian structure learning methods used in practice are score equivalent, which implies that they cannot distinguish Markov equivalent DAGs”，但实际上一些方法（如 Zhou & Chang 2021）直接搜索 CPDAG 空间，已回避了分数等价问题——作者在引言中将此列为后续工作的替代思路，但未深入比较。此外，未被引用的工作：例如 BGe 先验的变体（Constantinou et al., 2021）或非参数贝叶斯方法（如基于 GP）——可能因为与线性高斯模型偏离较大而未提及。值得研究者去查的问题：是否存在其他不依赖分数等价且利用等方差假设的贝叶斯方法（如基于 NML 编码或 MDL）？本文的引用列表基本覆盖了 2010-2021 年的核心工作，未见明显的缺失（除个别纯频率学派的结构学习基准）。

张力：未见明显对立引用。各子线索在假设和工具上各有侧重，但对“等方差保证识别”这一事实没有异议。

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

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

设观测数据为 \(X \in \mathbb{R}^{n \times p}\)，每一行是一个独立同分布样本，每一列对应一个变量 \(j \in [p] = \{1,\dots,p\}\)。

  • 模型（线性高斯结构方程模型）：

    \[X_j = \sum_{i \in \mathrm{pa}_G(j)} \beta_{ji} X_i + \varepsilon_j, \quad \varepsilon_j \sim N(0, \sigma_j^2),\]
    其中 \(G\) 是一个 DAG，\(\mathrm{pa}_G(j)\) 是 \(j\) 的父节点集合，系数 \(\beta_{ji}\) 非零当且仅当 \(i\to j\) 在 \(G\) 中。误差 \(\varepsilon_1,\dots,\varepsilon_p\) 相互独立，且与所有父节点变量独立。在等方差假设下，\(\sigma_1^2 = \cdots = \sigma_p^2 = \sigma^2\) 未知。在异质方差设定下，\(\sigma_j^2\) 可以不同，但论文证明一致性仍成立。

  • 可观测数据：仅能观测到 \(X\) 矩阵，无法直接观测误差项或结构方程系数。潜在 / 不可观测的量：真实 DAG \(G_0\)、系数 \(\beta_{ji}\)、误差方差 \(\sigma_j^2\)、拓扑顺序 \(\pi\)。

  • 目标 estimand：DAG 的结构（即边集）或等价的拓扑顺序 \(\pi\)（因为给定顺序，DAG 完全由每个节点的父集决定）。

  • 参数与符号：

  • \(\pi\)：一个排列（顺序），表示节点的拓扑次序。若 \(\pi(i) < \pi(j)\)，则 \(X_i\) 在因果上先于 \(X_j\)。
  • 给定 \(\pi\)，每个节点 \(j\) 的父集仅能选自其前驱节点 \(\mathrm{pre}_\pi(j) = \{i: \pi(i) < \pi(j)\}\)。
  • \(G\)：DAG，其邻接矩阵 \(B\)（下三角化后）。
  • 模型似然：给定 \(G\) 和参数，数据满足高斯分布，协方差矩阵满足递归 Cholesky 分解。

第二步：最小内核（p=2 特例）

最简特例：\(p=2\)，两个变量 \(X_1, X_2\)。等方差假设：\(\sigma_1^2 = \sigma_2^2 = \sigma^2\)。两种可能因果方向：
- 图 \(G_1: X_1 \to X_2\)，模型：\(X_1 = \varepsilon_1,\ X_2 = \beta X_1 + \varepsilon_2\)；
- 图 \(G_2: X_2 \to X_1\)，模型：\(X_2 = \varepsilon_2,\ X_1 = \beta' X_2 + \varepsilon_1\)。

识别性（Peters & Bühlmann, 2014）：等方差下，两个模型虽生成不同的联合分布，但无法从相关系数分辨？实际上，等方差保证了顺序可识别：比较条件方差 \(\mathrm{Var}(X_2 \mid X_1)\) 与 \(\mathrm{Var}(X_1 \mid X_2)\)——在真方向 \(G_1\) 下，\(\mathrm{Var}(X_2 \mid X_1) = \sigma^2\)，而 \(\mathrm{Var}(X_1 \mid X_2) = \sigma^2/(1+\beta^2) < \sigma^2\)，因此从数据可推断方向。

本文贝叶斯方法在 p=2 上的运作：
1. 枚举两个排序（顺序）：\(\pi_1 = (1,2)\)，\(\pi_2 = (2,1)\)。
2. 对每个排序 \(\pi\)，找出其最佳 DAG \(\widehat{G}(\pi)\)：即每个节点 \(j\) 将其父集选为其前驱节点中使边际似然最大的子集。在 p=2 时，给定 \(\pi_1\)，节点 2 的父集只能是 \(\{1\}\)（节点 1 无父集），因此唯一的候选 DAG 就是 \(G_1\)；同理 \(\pi_2\) 唯一候选为 \(G_2\)。
3. 利用经验贝叶斯边际似然计算每个排序的近似后验概率：

\[\widetilde{\mathrm{pr}}(\pi \mid X) \propto L(\widehat{G}(\pi) \mid X) \cdot \mathrm{prior}(\pi),\]
其中 \(L\) 是采用经验贝叶斯估计的边际似然（对参数积分得到，具体见 §2.2）。
4. 选择后验概率较大的排序，即输出的 DAG 为其对应的 \(\widehat{G}(\pi)\)。

为什么这个特例抓住了核心：本文的全部理论和方法可看作这一简单思想的推广：通过“用每个排序下的最佳 DAG 的边际似然来近似该排序的后验”，将大规模组合问题（\(2^{O(p^2)}\) 个 DAG）转化为排序空间（\(p!\) 个排列）上的搜索，且利用等方差假设使得最佳 DAG 的边际似然可解析计算（无需 MCMC 内的嵌套选择）。

数学困难：对一般 \(p\)，每个排序下的最佳 DAG 不再是唯一的，需要通过稀疏回归（如 Lasso 或贝叶斯模型选择）来确定父集。本文使用经验贝叶斯的 Cholesky 分解公式来完成这一步（见 §2.2）。异质方差下的强选择一致性证明（定理1）关键依赖于此近似不会误导。

三、这篇论文做了什么（重心，务必讲透）

三句话

  • 研究了什么问题：在等方差假设下，提出首个贝叶斯 DAG 结构学习框架，并证明该方法在异质误差方差下仍具有强选择一致性；同时设计了基于排序的 MCMC 采样器并理论分析其混合时间。
  • 核心工具/方法：经验贝叶斯公式（利用数据估计超参数），将每个排序的后验概率近似为其最佳 DAG的边际似然，从而将 DAG 模型选择问题转化为排序空间上的优化和 MCMC；配合一种新的迭代自顶向下算法（ITD）快速估计初始排序。
  • 主要结论：
  • 定理1：在高维设定下（\(p = o(n)\) 且对数增长），MAP 估计量以概率趋于 1 恢复真实 DAG，即使误差方差异质（只需每个 \(\sigma_j^2\) 有界）。
  • 定理2：提出的 order-MCMC 采样器（使用随机转置或 random-to-random 移动）的总变差混合时间为 \(O(p^3 \log p)\)（在温和正则条件下），首次为等方差贝叶斯方法提供混合性理论。
  • 模拟与真实数据（scREAD 单细胞RNA-seq）表明，本文方法在准确性和计算效率上优于多种现有算法（如 mmPC、CAM、BGe 等）。

关键设定与假设

  • 模型：线性高斯 SEM，式 (2)：\(X_j = \sum_{i \in \mathrm{pa}_G(j)} \beta_{ji} X_i + \varepsilon_j\)。
  • 等方差：所有 \(\varepsilon_j\) 方差相同（但定理1允许异质）；协变量与误差独立。
  • 假设条件（重点标注）：
  • (C1) 限制特征值条件：存在常数 \(\phi_{\min}, \phi_{\max} > 0\)，使得对所有稀疏子集 \(S\)，样本协方差矩阵的子矩阵满足受限特征值条件（restricted eigenvalue condition）。这与 Lee et al. (2018) 的假设一致。
  • (C2) 先验参数选择：经验贝叶斯先验中的参数选择“适当”（如满足 Lemma 3 中的条件）。
  • (C3) β-min 条件：真父集系数绝对值的最小值满足 \(\min_{i \in \mathrm{pa}_0(j)} |\beta_{ji}| \ge \gamma_n\)，其中 \(\gamma_n\) 衰减不能快于 \(\sqrt{\log p / n}\)。这是选择一致性的标准必要条件。
  • (C4) 稀疏性：每个节点的入度有界（\(d = O(1)\)），且总边数 \(s = O(p)\)。
  • 相比已有文献（如 Lee et al. 2018），放宽了等方差假设（定理1不要求方差相等），同时强化了条件（需要 β-min 和限制特征值）；而相比确定性算法（Chen et al. 2019），本文不需要“faithfulness”或“强忠诚”假设。

主要结果

定理1（强选择一致性，§3.1 中 Theorem 1）
令 \(\widehat{G}_{\text{MAP}}\) 为经验贝叶斯后验的 MAP DAG。在假设 (C1)-(C4) 以及 \(n \gtrsim (\log p)^3\) 条件下，有

\[\Pr(\widehat{G}_{\text{MAP}} = G_0) \to 1 \quad \text{当 } n,p\to\infty.\]

直觉：经验贝叶斯边际似然在真 DAG 附近呈指数级高，而任何错误 DAG 的边际似然至少指数级小。证明核心是控制 Cholesky 因子的估计误差与先验惩罚项。
关键难点：异质方差下，边际似然中每个节点的方差贡献不再可消去，需要更精细的勒贝格测度处理。作者利用“每个节点误差方差的有界性”与“校正因子”克服了这一障碍。

定理2（MCMC 混合时间，§4.2 中 Theorem 2）
考虑在排序空间 \(\mathcal{S}_p\) 上运行的 Metropolis-Hastings 算法，提议分布为随机转置或 random-to-random shuffle。若后验分布满足“近似对数凹性”（具体指 §4.1 中的“热导”条件），则总变差混合时间 \(\tau(\epsilon) = O(p^3 \log p / \epsilon^2)\)。
直觉：排序空间上的局部移动可构造“高概率路径”连接任意两个排序，且后验集中在少数排序周围，因此避免了遍历性问题。证明方法结合了谱间隙估计和路径耦合技术，并借鉴了 Bernstein & Nestoridi (2019) 关于 random-to-random shuffle 的“cutoff”结果。

证明路线与技术技巧

整体路线（以定理1为例，三步）： 1. 局部一致性：对每个排序 \(\pi\)，给定真结构，证明经验贝叶斯下的 Cholesky 估计量以高概率恢复真父集（Lemma 4-6）。这一步使用限制特征值条件和 β-min 条件，采用类似于高维回归的 Lasso 分析。
2. 边际似然比较：证明真排序 \(\pi_0\) 的边际似然远大于任何错误排序的边际似然（Lemma 7-8）。核心是分解边际似然为“拟合优度”项和“复杂度惩罚”项，并利用异质方差下的“常数移位”性质（参见 Lemma 3 的引理）。
3. 后验集中：通过以上两步，MAP 估计量高概率落在真排序的邻域内，结合贝叶斯模型平均的“Bayesian oracle inequality”推出整体一致性。

关键跳跃点： - 在异质方差下，边际似然中的惩罚项会随方差差异变化，导致传统惩罚似然路径失效。作者通过将每个节点的边际似然写为校正后的残差平方和，使得异质方差带来的额外项可被先验的“幂次调整”（raising likelihood to power \(\alpha\)）吸收。
- 命题1与推论1：给出了后验集中在真图上的一个充分条件，刻画了“任意两个异质方差模型之间的 KL 散度下界”，这是证明的核心技术引理。

技术技巧点名： - 经验贝叶斯 + 幂次似然（power likelihood）：在计算后验时，将似然提升到 \(\alpha \in (0,1)\) 次幂，以抵消经验先验带来的模糊性（见 §2.2 和 Martin et al. (2017) 的引用）。
- Cholesky 分解的稀疏性：将 DAG 建模为精度矩阵的 Cholesky 因子稀疏，从而将结构学习转化为 p 个独立的稀疏回归问题（给定排序时）。
- Rao-Blackwellized 边后验概率：式 (8) 用 MCMC 样本估计边包含概率，通过条件期望减少方差（引用 Robert & Roberts, 2021）。
- 随机转置 vs random-to-random shuffle：后者的混合时间理论更成熟（Bernstein & Nestoridi, 2019），作者据此导出混合界。

真实例子与应用

数据：scREAD 数据库（Jiang et al., 2020），包含阿尔茨海默病患者的单细胞 RNA-seq 数据。作者选择10 个基因（与突触功能相关），样本量约 2000 个细胞。
方法：将本文的 ITD 算法 + order MCMC 应用于对数转换的标准化基因表达数据，假设线性高斯 SEM（等方差）。由于真实因果图未知，用留一法交叉验证的预测似然和生物学合理性（已知的基因调控关系）评估。
结果：
- 与 BGe、mmPC、CAM、GDS 等算法比较，本文方法在预测似然上显著最优（图 4 的箱线图）。
- 学习到的 DAG 中，部分边（如 MEF2C→SYN1）与文献一致，而其它方法遗漏或方向错误。
说明：展示了方法在实际高维噪声数据中的实用性，尤其是等方差假设在此应用中看似合理（技术重复的测量误差方差类似）。

🔎 结论是否比证明窄

  • 定理1声称在异质方差下仍一致，但假设条件 (C3) 的 β-min 要求 \(\min |\beta|\) 不能太弱。在实际中，这难以验证。作者在 §5 的模拟中展示了当方差异质较大时，MAP 的恢复率下降（见表 2），这暗示理论条件可能是“窄”的——对于严重异质的方差，可能需要更强的信号。
  • 定理2的混合时间边界依赖于“后验集中在少数排序”这一性质，这在 β-min 条件满足时成立。但对于弱信号，后验可能发散，混合时间可能更差。作者未提供这种情景下的分析。
  • 作者在 §6 结论中写道：“We believe that the empirical Bayes formulation can be extended to non-Gaussian models”，但本文没有给出任何理论或实证证据，属于 conjecture。

四、开放问题（扎根具体语句，最多4条）

  1. 放松 β-min 条件：定理1需要 \(\min |\beta| \ge \gamma_n\) 且 \(\gamma_n \gg \sqrt{\log p/n}\)。能否在更弱的信号下（如 \(\gamma_n \to 0\) 更快）仍保持选择一致性，或只能得到部分恢复？本文 §3.1 的 Remark 2 提到“this condition is likely necessary for exact recovery”，但未见详细讨论。可参考 Gan et al. (2019) 在异质方差下的一致性问题。

  2. 扩展到非高斯误差：作者在 §6 展望中提到“extend to non-Gaussian models (e.g., heavy-tailed)”。当前证明强烈依赖 Gaussian 似然的对数形式和对数-线性边缘似然展开。对于 heavy-tailed 误差，经验贝叶斯边际似然可能不存在闭合形式，需要新的耦合或 Laplace 逼近。

  3. 更准确的混合时间率：定理2给出 \(O(p^3 \log p)\)，但模拟中（§5.2.1）观察到混合时间在高维下似乎接近 \(O(p^2)\)。能否缩小这一 gap？作者在 §4.3 的讨论中指出“our bound is likely loose”，并猜想改进的热导估计可得到更优的率（参见 §4.2 末尾的 Remark 5）。

  4. 处理潜在变量（latent confounders）：当前方法假设所有相关变量被观测。在单细胞数据中，可能存在未知的细胞类型亚群作为潜在混杂。能否将等方差假设与潜在变量模型（如 LV-DAG）结合？本文没有讨论，但单一细胞数据的一个自然扩展。

提醒：想确认上述 gap 是否为真 gap，可查阅近期（2022-2024）关于等方差 DAG 学习的论文（如 Ghoshal & Honorio 的后续工作，或 Strieder et al. 2021 的置信区间方法），看他们是否解决了类似问题。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论