Learning Bayesian Networks through Birkhoff Polytope: A Relaxation Method

We establish a novel framework for learning a directed acyclic graph (DAG)\nwhen data are generated from a Gaussian, linear structural equation model. It\nconsists of two parts: (1) introduce a permutation matrix as a new parameter\nwithin a regularized Gaussian log-likelihood to represent variable ordering;\nand (2) given the ordering, estimate the DAG structure through sparse Cholesky\nfactor of the inverse covariance matrix. For permutation matrix estimation, we\npropose a relaxation technique that avoids the NP-hard combinatorial problem of\norder estimation. Given an ordering, a sparse Cholesky factor is estimated\nusing a cyclic coordinatewise descent algorithm which decouples row-wise. Our\nframework recovers DAGs without the need for an expensive verification of the\nacyclicity constraint or enumeration of possible parent sets. We establish\nnumerical convergence of the algorithm, and consistency of the Cholesky factor\nestimator when the order of variables is known. Through several simulated and\nmacro-economic datasets, we study the scope and performance of the proposed\nmethodology.\n