Learning directed acyclic graph models based on sparsest permutations
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 assump...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021
|
| Online Access: | https://hdl.handle.net/1721.1/130118 |
| _version_ | 1826212152649711616 |
|---|---|
| author | Raskutti, Garvesh Uhler, Caroline |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Raskutti, Garvesh Uhler, Caroline |
| author_sort | Raskutti, Garvesh |
| collection | MIT |
| description | 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 l 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. |
| first_indexed | 2024-09-23T15:17:12Z |
| format | Article |
| id | mit-1721.1/130118 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:17:12Z |
| publishDate | 2021 |
| publisher | Wiley |
| record_format | dspace |
| spelling | mit-1721.1/1301182022-09-29T13:55:11Z Learning directed acyclic graph models based on sparsest permutations Raskutti, Garvesh Uhler, Caroline Massachusetts Institute of Technology. Laboratory for Information and Decision Systems 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 l 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. 2021-03-11T20:03:38Z 2021-03-11T20:03:38Z 2018-04 2018-01 2021-03-05T16:22:33Z Article http://purl.org/eprint/type/JournalArticle 2049-1573 https://hdl.handle.net/1721.1/130118 Raskutti, Garvesh and Caroline Uhler. "Learning directed acyclic graph models based on sparsest permutations." Stat 7, 1 (April 2018): e183. © 2018 John Wiley & Sons Ltd en http://dx.doi.org/10.1002/sta4.183 Stat Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Wiley Prof. Uhler via Phoebe Ayers |
| spellingShingle | Raskutti, Garvesh Uhler, Caroline Learning directed acyclic graph models based on sparsest permutations |
| title | Learning directed acyclic graph models based on sparsest permutations |
| title_full | Learning directed acyclic graph models based on sparsest permutations |
| title_fullStr | Learning directed acyclic graph models based on sparsest permutations |
| title_full_unstemmed | Learning directed acyclic graph models based on sparsest permutations |
| title_short | Learning directed acyclic graph models based on sparsest permutations |
| title_sort | learning directed acyclic graph models based on sparsest permutations |
| url | https://hdl.handle.net/1721.1/130118 |
| work_keys_str_mv | AT raskuttigarvesh learningdirectedacyclicgraphmodelsbasedonsparsestpermutations AT uhlercaroline learningdirectedacyclicgraphmodelsbasedonsparsestpermutations |