arXiv:2409.07880cs.LGeess.SP2024-09被引 7

通过非负权重约束,实现可保证收敛的有向无环图结构学习。

Non-negative Weighted DAG Structure Learning

  • 利用非负边权和对数行列式构造凸无环约束,简化优化问题。
  • 算法在无限样本下能精确恢复真实图结构,且保证全局最优解。
  • 适合需要理论保障与稳定性的因果推断研究者使用。

我们研究从节点观测数据中学习线性结构方程模型下的有向无环图(DAG)拓扑结构问题。现有方法将组合式的DAG学习转化为连续优化,但面临非凸优化的复杂性。本文假设潜在DAG仅含非负边权,据此提出基于邻接矩阵对数行列式的凸无环函数,有效刻画并防止环的存在。该凸性使得非负加权DAG学习可被建模为抽象凸优化问题。我们提出基于乘子法的DAG恢复算法,理论上保证返回全局最小值。进一步证明,在样本量趋于无穷时,该凸方法可确保真实图结构的完全恢复。我们在多个可复现的合成数据实验中验证了算法性能,结果表明其优于当前最优方法。

原文摘要 · Abstract (English)

We address the problem of learning the topology of directed acyclic graphs (DAGs) from nodal observations, which adhere to a linear structural equation model. Recent advances framed the combinatorial DAG structure learning task as a continuous optimization problem, yet existing methods must contend with the complexities of non-convex optimization. To overcome this limitation, we assume that the latent DAG contains only non-negative edge weights. Leveraging this additional structure, we argue that cycles can be effectively characterized (and prevented) using a convex acyclicity function based on the log-determinant of the adjacency matrix. This convexity allows us to relax the task of learning the non-negative weighted DAG as an abstract convex optimization problem. We propose a DAG recovery algorithm based on the method of multipliers, that is guaranteed to return a global minimizer. Furthermore, we prove that in the infinite sample size regime, the convexity of our approach ensures the recovery of the true DAG structure. We empirically validate the performance of our algorithm in several reproducible synthetic-data test cases, showing that it outperforms state-of-the-art alternatives.

图结构学习凸优化因果推断

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。