Learning directed acyclic graphs based on sparsest permutations

G. Raskutti, C. Uhler, STAT 7 (2018) e183.


Journal Article | Published | English
Author
Raskutti, Garvesh; Uhler, CarolineIST Austria
Abstract
We consider the problem of learning a Bayesian network or directed acyclic graph model from observational data. A number of constraint‐based, score‐based and hybrid algorithms have been developed for this purpose. Statistical consistency guarantees of these algorithms rely on the faithfulness assumption, which has been shown to be restrictive especially for graphs with cycles in the skeleton. We here propose the sparsest permutation (SP) algorithm, showing that learning Bayesian networks is possible under strictly weaker assumptions than faithfulness. This comes at a computational price, thereby indicating a statistical‐computational trade‐off for causal inference algorithms. In the Gaussian noiseless setting, we prove that the SP algorithm boils down to finding the permutation of the variables with the sparsest Cholesky decomposition of the inverse covariance matrix, which is equivalent to ℓ0‐penalized maximum likelihood estimation. We end with a simulation study showing that in line with the proven stronger consistency guarantees, and the SP algorithm compares favourably to standard causal inference algorithms in terms of accuracy for a given sample size.
Publishing Year
Date Published
2018-04-17
Journal Title
STAT
Volume
7
Issue
1
Article Number
e183
IST-REx-ID

Cite this

Raskutti G, Uhler C. Learning directed acyclic graphs based on sparsest permutations. STAT. 2018;7(1):e183. doi:10.1002/sta4.183
Raskutti, G., & Uhler, C. (2018). Learning directed acyclic graphs based on sparsest permutations. STAT, 7(1), e183. https://doi.org/10.1002/sta4.183
Raskutti, Garvesh, and Caroline Uhler. “Learning Directed Acyclic Graphs Based on Sparsest Permutations.” STAT 7, no. 1 (2018): e183. https://doi.org/10.1002/sta4.183.
G. Raskutti and C. Uhler, “Learning directed acyclic graphs based on sparsest permutations,” STAT, vol. 7, no. 1, p. e183, 2018.
Raskutti G, Uhler C. 2018. Learning directed acyclic graphs based on sparsest permutations. STAT. 7(1), e183.
Raskutti, Garvesh, and Caroline Uhler. “Learning Directed Acyclic Graphs Based on Sparsest Permutations.” STAT, vol. 7, no. 1, Wiley, 2018, p. e183, doi:10.1002/sta4.183.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1307.0366

Search this title in

Google Scholar