An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation
This addresses the foundational issue in causal inference of verifying the existence of causal models from data, which is incremental as it builds on prior work by Pearl and Verma.
The paper tackles the problem of determining whether a set of observed conditional independencies has a causal explanation, presenting an algorithm that tests for and produces a directed acyclic graph consistent with all given dependencies and independencies.
In a previous paper [Pearl and Verma, 1991] we presented an algorithm for extracting causal influences from independence information, where a causal influence was defined as the existence of a directed arc in all minimal causal models consistent with the data. In this paper we address the question of deciding whether there exists a causal model that explains ALL the observed dependencies and independencies. Formally, given a list M of conditional independence statements, it is required to decide whether there exists a directed acyclic graph (dag) D that is perfectly consistent with M, namely, every statement in M, and no other, is reflected via dseparation in D. We present and analyze an effective algorithm that tests for the existence of such a day, and produces one, if it exists.