Ordering-Based Causal Structure Learning in the Presence of Latent Variables
We consider the task of learning a causal graph in the presence of latent confounders given i.i.d.samples from the model. While current algorithms for causal structure discovery in the presence of latent confounders are constraint-based, we here propose a hybrid approach. We prove that under assumpt...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
International Machine Learning Society
2021
|
| Online Access: | https://hdl.handle.net/1721.1/130442 |
| _version_ | 1811089283540320256 |
|---|---|
| author | Bernstein, Daniel Irving Saeed, Basil(Basil N.) Squires, Chandler(Chandler B.) Uhler, Caroline |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bernstein, Daniel Irving Saeed, Basil(Basil N.) Squires, Chandler(Chandler B.) Uhler, Caroline |
| author_sort | Bernstein, Daniel Irving |
| collection | MIT |
| description | We consider the task of learning a causal graph in the presence of latent confounders given i.i.d.samples from the model. While current algorithms for causal structure discovery in the presence of latent confounders are constraint-based, we here propose a hybrid approach. We prove that under assumptions weaker than faithfulness, any sparsest independence map (IMAP) of the distribution belongs to the Markov equivalence class of the true model. This motivates the Sparsest Poset formulation - that posets can be mapped to minimal IMAPs of the true model such that the sparsest of these IMAPs is Markov equivalent to the true model. Motivated by this result, we propose a greedy algorithm over the space of posets for causal structure discovery in the presence of latent confounders and compare its performance to the current state-of-the-art algorithms FCI and FCI+ on synthetic data. |
| first_indexed | 2024-09-23T14:16:45Z |
| format | Article |
| id | mit-1721.1/130442 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:16:45Z |
| publishDate | 2021 |
| publisher | International Machine Learning Society |
| record_format | dspace |
| spelling | mit-1721.1/1304422022-09-28T19:41:33Z Ordering-Based Causal Structure Learning in the Presence of Latent Variables Bernstein, Daniel Irving Saeed, Basil(Basil N.) Squires, Chandler(Chandler B.) Uhler, Caroline Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Institute for Data, Systems, and Society We consider the task of learning a causal graph in the presence of latent confounders given i.i.d.samples from the model. While current algorithms for causal structure discovery in the presence of latent confounders are constraint-based, we here propose a hybrid approach. We prove that under assumptions weaker than faithfulness, any sparsest independence map (IMAP) of the distribution belongs to the Markov equivalence class of the true model. This motivates the Sparsest Poset formulation - that posets can be mapped to minimal IMAPs of the true model such that the sparsest of these IMAPs is Markov equivalent to the true model. Motivated by this result, we propose a greedy algorithm over the space of posets for causal structure discovery in the presence of latent confounders and compare its performance to the current state-of-the-art algorithms FCI and FCI+ on synthetic data. National Science Foundation (U.S.). Math-ematical Sciences Postdoctoral Research Fellowship (DMS-1802902) National Science Foundation (U.S.) (Grant DMS-1651995) United States. Office of Naval Research (Grants N00014-17-1-2147 and N00014-18-1-2765) 2021-04-12T13:51:44Z 2021-04-12T13:51:44Z 2020-08 2021-04-05T14:33:47Z Article http://purl.org/eprint/type/ConferencePaper 2640-3498 https://hdl.handle.net/1721.1/130442 Bernstein, Daniel Irving et al. “Ordering-Based Causal Structure Learning in the Presence of Latent Variables.” Paper in the Proceedings of Machine Learning Research, 108, 23rdInternational Conference on Artificial Intelligence and Statistics (AISTATS) 2020, Online, August 26 - 28, 2020, International Machine Learning Society: 4098-4108 © 2020 The Author(s) en http://proceedings.mlr.press/v108/bernstein20a.html Proceedings of Machine Learning Research Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf International Machine Learning Society Proceedings of Machine Learning Research |
| spellingShingle | Bernstein, Daniel Irving Saeed, Basil(Basil N.) Squires, Chandler(Chandler B.) Uhler, Caroline Ordering-Based Causal Structure Learning in the Presence of Latent Variables |
| title | Ordering-Based Causal Structure Learning in the Presence of Latent Variables |
| title_full | Ordering-Based Causal Structure Learning in the Presence of Latent Variables |
| title_fullStr | Ordering-Based Causal Structure Learning in the Presence of Latent Variables |
| title_full_unstemmed | Ordering-Based Causal Structure Learning in the Presence of Latent Variables |
| title_short | Ordering-Based Causal Structure Learning in the Presence of Latent Variables |
| title_sort | ordering based causal structure learning in the presence of latent variables |
| url | https://hdl.handle.net/1721.1/130442 |
| work_keys_str_mv | AT bernsteindanielirving orderingbasedcausalstructurelearninginthepresenceoflatentvariables AT saeedbasilbasiln orderingbasedcausalstructurelearninginthepresenceoflatentvariables AT squireschandlerchandlerb orderingbasedcausalstructurelearninginthepresenceoflatentvariables AT uhlercaroline orderingbasedcausalstructurelearninginthepresenceoflatentvariables |