Recently continuous relaxations have been proposed in order to learn Directed
Acyclic Graphs (DAGs) from data by backpropagation, instead of using
combinatorial optimization. However, a number of techniques for fully discrete
backpropagation could instead be applied. In this paper, we explore that
direction and propose DAG-DB, a framework for learning DAGs by Discrete
Backpropagation. Based on the architecture of Implicit Maximum Likelihood
Estimation [I-MLE, arXiv:2106.01798], DAG-DB adopts a probabilistic approach to
the problem, sampling binary adjacency matrices from an implicit probability
distribution. DAG-DB learns a parameter for the distribution from the loss
incurred by each sample, performing competitively using either of two fully
discrete backpropagation techniques, namely I-MLE and Straight-Through
Estimation.

本文提出 DAG-DB 框架，采用离散反向传播技术从数据中学习有向无环图，其使用了内在概率分布采样二元邻接矩阵，然后学习分布的参数。

通过反向传播学习离散有向无环图

Learning Discrete Directed Acyclic Graphs via Backpropagation

Dense conditional random fields (CRF) with Gaussian pairwise potentials have
emerged as a popular framework for several computer vision applications such as
stereo correspondence and semantic segmentation. By modeling long-range
interactions, dense CRFs provide a more detailed labelling compared to their
sparse counterparts. Variational inference in these dense models is performed
using a filtering-based mean-field algorithm in order to obtain a
fully-factorized distribution minimising the Kullback-Leibler divergence to the
true distribution. In contrast to the continuous relaxation-based energy
minimisation algorithms used for sparse CRFs, the mean-field algorithm fails to
provide strong theoretical guarantees on the quality of its solutions. To
address this deficiency, we show that it is possible to use the same filtering
approach to speed-up the optimisation of several continuous relaxations.
Specifically, we solve a convex quadratic programming (QP) relaxation using the
efficient Frank-Wolfe algorithm. This also allows us to solve
difference-of-convex relaxations via the iterative concave-convex procedure
where each iteration requires solving a convex QP. Finally, we develop a novel
divide-and-conquer method to compute the subgradients of a linear programming
relaxation that provides the best theoretical bounds for energy minimisation.
We demonstrate the advantage of continuous relaxations over the widely used
mean-field algorithm on publicly available datasets.

本研究论文提出了一种使用 Frank-Wolfe 算法来通过优化凸二次规划松弛问题的方法，此外还开发了一种分治方法来计算线性规划松弛的次梯度，以实现更好的能量最小化，与常用的均值场算法相比，本文研究表明连续松弛技术有更好的结果。