A polynomial time algorithm for determining Dag equivalence in the presence of latent variables and selection bias
Abstractif and only if for every W in V, W is independent of the set of all its non-descendants conditional on the set of its parents. One natural question that arises with respect to DAGs is when two DAGs are “statistically equivalent”. One interesting sense of “statistical equivalence” is “d-separation equivalence” (explained in more detail below.) In the case of DAGs, d-separation equivalence is also corresponds to a variety of other natural senses of statistical equivalence (such as representing the same set of distributions). Theorems characterizing d-separation equivalence for directed acyclic graphs and that can be used as the basis for polynomial time algorithms for checking d-separation equivalence were provided by Verma and Pearl (1990), and Frydenberg (1990). The question we will examine is how to extend these results to cases where a DAG may have latent (unmeasured) variables or selection bias (i.e. some of the variables in the DAG have been conditioned on.) D-separation equivalence is of interest in part because there are algorithms for constructing DAGs with latent variables and selection bias that are based on observed conditional independence relations. For this class of algorithms, it is impossible to determine which of two d-separation equivalent causal structures generated a given probability distribution, given only the set of conditional independence and dependence relations true of the observed distribution. We will describe a polynomial (in the number of vertices) time algorithm for determining when two DAGs which may have latent variables or selection bias are d-separation equivalent.
Similar books and articles
Causal inference in the presence of latent variables and selection bias.Peter Spirtes, Christopher Meek & Thomas Richardson - unknown
A Transformational Characterization of Markov Equivalence between DAGs with Latent Variables.Jiji Zhang & Peter Spirtes - unknown
On the Number of Experiments Suﬃcient and in the Worst Case Necessary to Identify All Causal Relations Among N Variables.Clark Glymour & Richard Scheines - unknown
Added to PP
Historical graph of downloads
Citations of this work
The Similarity of Causal Inference in Experimental and Non‐experimental Studies.Richard Scheines - 2005 - Philosophy of Science 72 (5):927-940.
Causal Reasoning with Ancestral Graphical Models.Jiji Zhang - 2008 - Journal of Machine Learning Research 9:1437-1474.
References found in this work
No references found.