TY - GEN
T1 - Minimum intervention cover of a causal graph
AU - Kandasamy, Saravanan
AU - Bhattacharyya, Arnab
AU - Honavar, Vasant G.
N1 - Funding Information:
Saravanan Kandasamy was supported in part by the DRDO Frontiers Project DRDO0687, and by Ramanujan grant SB/S2/RJN-020/2017 of DST India at the Tata Institute of Fundamental Research. Arnab Bhattacharyya was supported at IISc by Ramanujan grant DSTO1358 and the DRDO Frontiers Project DRDO0687 and at NUS by an AcRF Tier 1 grant on “Inference and Testing of Sparse Models in High Dimensions”. Vasant G Honavar was supported in part by the National Center for Advancing Translational Sciences, NIH through the grant UL1 TR000127 and TR002014, by the NSF, USA, through the grants 1518732, 1640834, and 1636795, the Pennsylvania State University’s Institute for Cyberscience and the Center for Big Data Analytics and Discovery Informatics, the Edward Frymoyer Endowed Professorship in Information Sciences and Technology at Pennsylvania State University and the Sudha Murty Distinguished Visiting Chair in Neurocomputing and Data Science funded by the Pratiksha Trust at the Indian Institute of Science.The content is solely the responsibility of the authors and does not necessarily represent the official views of the sponsors.
Publisher Copyright:
© 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org).
PY - 2019
Y1 - 2019
N2 - Eliciting causal effects from interventions and observations is one of the central concerns of science, and increasingly, artificial intelligence. We provide an algorithm that, given a causal graph G, determines MIC(G), a minimum intervention cover of G, i.e., a minimum set of interventions that suffices for identifying every causal effect that is identifiable in a causal model characterized by G. We establish the completeness of do-calculus for computing MIC(G). MIC(G) effectively offers an efficient compilation of all of the information obtainable from all possible interventions in a causal model characterized by G. Minimum intervention cover finds applications in a variety of contexts including counterfactual inference, and generalizing causal effects across experimental settings. We analyze the computational complexity of minimum intervention cover and identify some special cases of practical interest in which MIC(G) can be computed in time that is polynomial in the size of G.
AB - Eliciting causal effects from interventions and observations is one of the central concerns of science, and increasingly, artificial intelligence. We provide an algorithm that, given a causal graph G, determines MIC(G), a minimum intervention cover of G, i.e., a minimum set of interventions that suffices for identifying every causal effect that is identifiable in a causal model characterized by G. We establish the completeness of do-calculus for computing MIC(G). MIC(G) effectively offers an efficient compilation of all of the information obtainable from all possible interventions in a causal model characterized by G. Minimum intervention cover finds applications in a variety of contexts including counterfactual inference, and generalizing causal effects across experimental settings. We analyze the computational complexity of minimum intervention cover and identify some special cases of practical interest in which MIC(G) can be computed in time that is polynomial in the size of G.
UR - http://www.scopus.com/inward/record.url?scp=85090807470&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090807470&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85090807470
T3 - 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019
SP - 2876
EP - 2885
BT - 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019
PB - AAAI press
T2 - 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Annual Conference on Innovative Applications of Artificial Intelligence, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019
Y2 - 27 January 2019 through 1 February 2019
ER -