Integer Programming for Learning Directed Acyclic Graphs from Continuous Data

Hasan Manzour, Simge Küçükyavuz, Hao-Hsiang Wu, Ali Shojaie

    研究成果: Article同行評審

    摘要

    Learning directed acyclic graphs (DAGs) from data is a challenging task both in theory and in practice, because the number of possible DAGs scales superexponentially with the number of nodes. In this paper, we study the problem of learning an optimal DAG from continuous observational data. We cast this problem in the form of a mathematical programming model that can naturally incorporate a superstructure to reduce the set of possible candidate DAGs. We use a negative log-likelihood score function with both ℓ1 and ℓ0 penalties and propose a new mixed-integer quadratic program, referred to as a layered network (LN) formulation. The LN formulation is a compact model that enjoys as tight an optimal continuous relaxation value as the stronger but larger formulations under a mild condition. Computational results indicate that the proposed formulation outperforms existing mathematical formulations and scales better than available algorithms that can solve the same problem with only ℓ1 regularization. In particular, the LN formulation clearly outperforms existing methods in terms of computational time needed to find an optimal DAG in the presence of a sparse superstructure.
    原文American English
    頁(從 - 到)46-73
    頁數28
    期刊INFORMS Journal on Optimization
    3
    發行號1
    出版狀態Published - 1 一月 2021

    指紋

    深入研究「Integer Programming for Learning Directed Acyclic Graphs from Continuous Data」主題。共同形成了獨特的指紋。

    引用此