Learning Causal Graphs with Latent Variables
Murat Kocaoglu, Karthikeyan Shanmugam, Elias Bareinboim · Neural Information Processing Systems · 2017
Causality is one of the central notions that allows us to decompose reality in meaningful components, construct cohesive stories (explanations) about complex aspects of this reality, and then understand the world around us and make principled decisions in intricate situations. The challenge of learning cause-and-effect relationships from non-experimental data was studied in different settings in the literature of causal structural learning, which includes delineating the boundary conditions such that causal relations can be learned from passive data (Pearl, 2000; SGS, 2001). In this paper, we consider the problem of learning causal structures in the presence of latent variables aided by the use of interventions. It is known that a naive approach to this problem would require O(n2) interventions for a causal graph with n observed variables, which due to costs, technical, or ethical considerations, is rarely feasible to perform in practice. We propose an efficient randomized algorithm to try to ameliorate this problem that can learn the causal graph (including the existence and location of latent variables) using O(log2 n) interventions, for graphs with a constant degree. We further propose an efficient deterministic variant of this procedure that is useful for different classes of graphs, including common cases such as bipartite, time-series, and relational type of systems.