提出一种从观测数据精确重构线性有向无环图的新算法。
BUILD with Precision: Bottom-Up Inference of Linear DAGs
- 自底向上逐层识别叶节点及其父节点，逐步剪枝重建图结构。
- 在真实精度矩阵下可完全还原因果图，合成数据上优于现有方法。
- 适合需要高精度因果推断的科研与工程场景。
从观测数据中学习有向无环图（DAG）结构是因果发现、统计信号处理和机器学习中的核心问题。在线性高斯结构方程模型（SEM）且噪声方差相等的假设下，该问题具有可识别性，我们证明了观测数据的集成精度矩阵具有独特结构，有助于促进DAG恢复。基于此性质，本文提出BUILD（Bottom-Up Inference of Linear DAGs），一种确定性的分步算法：先识别叶节点及其父节点，再通过移除关联边进行剪枝，从而从真实精度矩阵中精确重构出DAG。实际应用中，精度矩阵需从有限数据估计，而病态性可能导致误差累积。为此，我们周期性地重新估计精度矩阵（随着叶节点被移除，变量数减少），以牺牲运行时间换取更强鲁棒性。在具有挑战性的合成基准测试中，重现性结果表明BUILD相比当前最先进的DAG学习算法表现更优，同时提供对复杂度的显式控制。
原文摘要 · Abstract (English)
Learning the structure of directed acyclic graphs (DAGs) from observational data is a central problem in causal discovery, statistical signal processing, and machine learning. Under a linear Gaussian structural equation model (SEM) with equal noise variances, the problem is identifiable and we show that the ensemble precision matrix of the observations exhibits a distinctive structure that facilitates DAG recovery. Exploiting this property, we propose BUILD (Bottom-Up Inference of Linear DAGs), a deterministic stepwise algorithm that identifies leaf nodes and their parents, then prunes the leaves by removing incident edges to proceed to the next step, exactly reconstructing the DAG from the true precision matrix. In practice, precision matrices must be estimated from finite data, and ill-conditioning may lead to error accumulation across BUILD steps. As a mitigation strategy, we periodically re-estimate the precision matrix (with less variables as leaves are pruned), trading off runtime for enhanced robustness. Reproducible results on challenging synthetic benchmarks demonstrate that BUILD compares favorably to state-of-the-art DAG learning algorithms, while offering an explicit handle on complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。