Timezone: »
We consider the problem of learning causal structures with latent variables using interventions. Our objective is not only to learn the causal graph between the observed variables, but to locate unobserved variables that could confound the relationship between observables. Our approach is stage-wise: We first learn the observable graph, i.e., the induced graph between observable variables. Next we learn the existence and location of the latent variables given the observable graph. We propose an efficient randomized algorithm that can learn the observable graph using O(d\log^2 n) interventions where d is the degree of the graph. We further propose an efficient deterministic variant which uses O(log n + l) interventions, where l is the longest directed path in the graph. Next, we propose an algorithm that uses only O(d^2 log n) interventions that can learn the latents between both non-adjacent and adjacent variables. While a naive baseline approach would require O(n^2) interventions, our combined algorithm can learn the causal graph with latents using O(d log^2 n + d^2 log (n)) interventions.
Author Information
Murat Kocaoglu (MIT-IBM Watson AI Lab)
Karthikeyan Shanmugam (IBM Research, NY)
Elias Bareinboim (Purdue)
More from the Same Authors
-
2020 Poster: Active Structure Learning of Causal DAGs via Directed Clique Trees »
Chandler Squires · Sara Magliacane · Kristjan Greenewald · Dmitriy Katz · Murat Kocaoglu · Karthikeyan Shanmugam -
2020 Poster: Causal Discovery from Soft Interventions with Unknown Targets: Characterization and Learning »
Amin Jaber · Murat Kocaoglu · Karthikeyan Shanmugam · Elias Bareinboim -
2020 Poster: Applications of Common Entropy for Causal Inference »
Murat Kocaoglu · Sanjay Shakkottai · Alexandros Dimakis · Constantine Caramanis · Sriram Vishwanath -
2020 Poster: Entropic Causal Inference: Identifiability and Finite Sample Results »
Spencer Compton · Murat Kocaoglu · Kristjan Greenewald · Dmitriy Katz -
2019 Poster: Near-Optimal Reinforcement Learning in Dynamic Treatment Regimes »
Junzhe Zhang · Elias Bareinboim -
2019 Poster: Sample Efficient Active Learning of Causal Trees »
Kristjan Greenewald · Dmitriy Katz · Karthikeyan Shanmugam · Sara Magliacane · Murat Kocaoglu · Enric Boix Adsera · Guy Bresler -
2019 Poster: Efficient Identification in Linear Structural Causal Models with Instrumental Cutsets »
Daniel Kumor · Bryant Chen · Elias Bareinboim -
2019 Poster: Characterization and Learning of Causal Graphs with Latent Variables from Soft Interventions »
Murat Kocaoglu · Amin Jaber · Karthikeyan Shanmugam · Elias Bareinboim -
2019 Poster: Identification of Conditional Causal Effects under Markov Equivalence »
Amin Jaber · Jiji Zhang · Elias Bareinboim -
2019 Spotlight: Identification of Conditional Causal Effects under Markov Equivalence »
Amin Jaber · Jiji Zhang · Elias Bareinboim -
2018 Poster: Structural Causal Bandits: Where to Intervene? »
Sanghack Lee · Elias Bareinboim -
2018 Poster: Experimental Design for Cost-Aware Learning of Causal Graphs »
Erik Lindgren · Murat Kocaoglu · Alexandros Dimakis · Sriram Vishwanath -
2018 Poster: Equality of Opportunity in Classification: A Causal Approach »
Junzhe Zhang · Elias Bareinboim -
2017 Poster: Model-Powered Conditional Independence Test »
Rajat Sen · Ananda Theertha Suresh · Karthikeyan Shanmugam · Alexandros Dimakis · Sanjay Shakkottai -
2015 Poster: Learning Causal Graphs with Small Interventions »
Karthikeyan Shanmugam · Murat Kocaoglu · Alexandros Dimakis · Sriram Vishwanath -
2015 Poster: Bandits with Unobserved Confounders: A Causal Approach »
Elias Bareinboim · Andrew Forney · Judea Pearl -
2014 Poster: Transportability from Multiple Environments with Limited Experiments: Completeness Results »
Elias Bareinboim · Judea Pearl -
2014 Spotlight: Transportability from Multiple Environments with Limited Experiments: Completeness Results »
Elias Bareinboim · Judea Pearl -
2014 Poster: Sparse Polynomial Learning and Graph Sketching »
Murat Kocaoglu · Karthikeyan Shanmugam · Alexandros Dimakis · Adam Klivans -
2014 Oral: Sparse Polynomial Learning and Graph Sketching »
Murat Kocaoglu · Karthikeyan Shanmugam · Alexandros Dimakis · Adam Klivans -
2013 Poster: Transportability from Multiple Environments with Limited Experiments »
Elias Bareinboim · Sanghack Lee · Vasant Honavar · Judea Pearl -
2013 Tutorial: Causes and Counterfactuals: Concepts, Principles and Tools. »
Judea Pearl · Elias Bareinboim