Sample efficient active learning of causal trees
Neural information processing systems foundation. All rights reserved. We consider the problem of experimental design for learning causal graphs that have a tree structure. We propose an adaptive framework that determines the next intervention based on a Bayesian prior updated with the outcomes of p...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Morgan Kaufmann Publishers
2021
|
| Online Access: | https://hdl.handle.net/1721.1/130081 |
| _version_ | 1811074331658158080 |
|---|---|
| author | Greenewald, Kristjan Katz, Dmitriy Shanmugam, Karthikeyan Magliacane, Sara Kocaoglu, Murat Boix-Adsera, Enric Bresler, Guy |
| author2 | MIT-IBM Watson AI Lab |
| author_facet | MIT-IBM Watson AI Lab Greenewald, Kristjan Katz, Dmitriy Shanmugam, Karthikeyan Magliacane, Sara Kocaoglu, Murat Boix-Adsera, Enric Bresler, Guy |
| author_sort | Greenewald, Kristjan |
| collection | MIT |
| description | Neural information processing systems foundation. All rights reserved. We consider the problem of experimental design for learning causal graphs that have a tree structure. We propose an adaptive framework that determines the next intervention based on a Bayesian prior updated with the outcomes of previous experiments, focusing on the setting where observational data is cheap (assumed infinite) and interventional data is expensive. While information greedy approaches are popular in active learning, we show that in this setting they can be exponentially suboptimal (in the number of interventions required), and instead propose an algorithm that exploits graph structure in the form of a centrality measure. If each intervention yields a very large data sample, we show that the algorithm requires a number of interventions less than or equal to a factor of 2 times the minimum achievable number. We show that the algorithm and the associated theory can be adapted to the setting where each performed intervention yields finitely many samples. Several extensions are also presented, to the case where a specified set of nodes cannot be intervened on, to the case where K interventions are scheduled at once, and to the fully adaptive case where each experiment yields only one sample. In the case of finite interventional data, through simulated experiments we show that our algorithms outperform different adaptive baseline algorithms. |
| first_indexed | 2024-09-23T09:47:23Z |
| format | Article |
| id | mit-1721.1/130081 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:47:23Z |
| publishDate | 2021 |
| publisher | Morgan Kaufmann Publishers |
| record_format | dspace |
| spelling | mit-1721.1/1300812022-09-30T16:51:21Z Sample efficient active learning of causal trees Greenewald, Kristjan Katz, Dmitriy Shanmugam, Karthikeyan Magliacane, Sara Kocaoglu, Murat Boix-Adsera, Enric Bresler, Guy MIT-IBM Watson AI Lab Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Neural information processing systems foundation. All rights reserved. We consider the problem of experimental design for learning causal graphs that have a tree structure. We propose an adaptive framework that determines the next intervention based on a Bayesian prior updated with the outcomes of previous experiments, focusing on the setting where observational data is cheap (assumed infinite) and interventional data is expensive. While information greedy approaches are popular in active learning, we show that in this setting they can be exponentially suboptimal (in the number of interventions required), and instead propose an algorithm that exploits graph structure in the form of a centrality measure. If each intervention yields a very large data sample, we show that the algorithm requires a number of interventions less than or equal to a factor of 2 times the minimum achievable number. We show that the algorithm and the associated theory can be adapted to the setting where each performed intervention yields finitely many samples. Several extensions are also presented, to the case where a specified set of nodes cannot be intervened on, to the case where K interventions are scheduled at once, and to the fully adaptive case where each experiment yields only one sample. In the case of finite interventional data, through simulated experiments we show that our algorithms outperform different adaptive baseline algorithms. 2021-03-04T15:48:45Z 2021-03-04T15:48:45Z 2019-12 2020-12-03T16:31:17Z Article http://purl.org/eprint/type/ConferencePaper 1049-5258 https://hdl.handle.net/1721.1/130081 Greenewald, Kristjan et al. “Sample efficient active learning of causal trees.” Paper in the Advances in Neural Information Processing Systems, 32, 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancourver Canada, Dec 8-14, 2019, Morgan Kaufmann © 2019 The Author(s) en https://papers.nips.cc/paper/2019/hash/5ee5605917626676f6a285fa4c10f7b0-Abstract.html Advances in Neural Information Processing Systems 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 Morgan Kaufmann Publishers Neural Information Processing Systems (NIPS) |
| spellingShingle | Greenewald, Kristjan Katz, Dmitriy Shanmugam, Karthikeyan Magliacane, Sara Kocaoglu, Murat Boix-Adsera, Enric Bresler, Guy Sample efficient active learning of causal trees |
| title | Sample efficient active learning of causal trees |
| title_full | Sample efficient active learning of causal trees |
| title_fullStr | Sample efficient active learning of causal trees |
| title_full_unstemmed | Sample efficient active learning of causal trees |
| title_short | Sample efficient active learning of causal trees |
| title_sort | sample efficient active learning of causal trees |
| url | https://hdl.handle.net/1721.1/130081 |
| work_keys_str_mv | AT greenewaldkristjan sampleefficientactivelearningofcausaltrees AT katzdmitriy sampleefficientactivelearningofcausaltrees AT shanmugamkarthikeyan sampleefficientactivelearningofcausaltrees AT magliacanesara sampleefficientactivelearningofcausaltrees AT kocaoglumurat sampleefficientactivelearningofcausaltrees AT boixadseraenric sampleefficientactivelearningofcausaltrees AT breslerguy sampleefficientactivelearningofcausaltrees |