The combinatorial problem of learning directed acyclic graphs (DAGs) from
data was recently framed as a purely continuous optimization problem by
leveraging a differentiable acyclicity characterization of DAGs based on the
trace of a matrix exponential function. Existing acyclicity characterizations
are based on the idea that powers of an adjacency matrix contain information
about walks and cycles. In this work, we propose a new acyclicity
characterization based on the log-determinant (log-det) function, which
leverages the nilpotency property of DAGs. To deal with the inherent
asymmetries of a DAG, we relate the domain of our log-det characterization to
the set of $\textit{M-matrices}$, which is a key difference to the classical
log-det function defined over the cone of positive definite matrices. Similar
to acyclicity functions previously proposed, our characterization is also exact
and differentiable. However, when compared to existing characterizations, our
log-det function: (1) Is better at detecting large cycles; (2) Has
better-behaved gradients; and (3) Its runtime is in practice about an order of
magnitude faster. From the optimization side, we drop the typically used
augmented Lagrangian scheme and propose DAGMA ($\textit{DAGs via M-matrices for
Acyclicity}$), a method that resembles the central path for barrier methods.
Each point in the central path of DAGMA is a solution to an unconstrained
problem regularized by our log-det function, then we show that at the limit of
the central path the solution is guaranteed to be a DAG. Finally, we provide
extensive experiments for $\textit{linear}$ and $\textit{nonlinear}$ SEMs and
show that our approach can reach large speed-ups and smaller structural Hamming
distances against state-of-the-art methods. Code implementing the proposed
method is open-source and publicly available at
this https URL

该研究提出了一种基于对数行列式函数的新型有向无环图（DAG）的无环性描述，该描述利用 DAG 的幂零属性将其与正定矩阵锥定义的经典对数行列式函数进行了区分。该方法与现有技术相比，对于检测大型循环性更好，在梯度方面更好，并且实际运行时间大约快一个数量级。在数值实验中表明，该方法能够获得较大的速度提升和较小的结构 Hamming 距离。

DAGMA: 基于 M 矩阵和对数行列式无环特征学习 DAGs

DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity  Characterization

Nonnegative matrix factorization (NMF) has become a very popular technique in
machine learning because it automatically extracts meaningful features through
a sparse and part-based representation. However, NMF has the drawback of being
highly ill-posed, that is, there typically exist many different but equivalent
factorizations. In this paper, we introduce a completely new way to obtaining
more well-posed NMF problems whose solutions are sparser. Our technique is
based on the preprocessing of the nonnegative input data matrix, and relies on
the theory of M-matrices and the geometric interpretation of NMF. This approach
provably leads to optimal and sparse solutions under the separability
assumption of Donoho and Stodden (NIPS, 2003), and, for rank-three matrices,
makes the number of exact factorizations finite. We illustrate the
effectiveness of our technique on several image datasets.

本文介绍了一种基于 M 矩阵理论和非负矩阵分解的几何解释，通过对非负输入数据矩阵的预处理实现更为适合求解的 NMF 问题，其解具有更好的稀疏性和优化性，适用于多种图像数据集。