A polynomial time algorithm for determining Dag equivalence in the presence of latent variables and selection bias
Graduate studies at Western
|Abstract||if 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.|
|Keywords||No keywords specified (fix it)|
No categories specified
(categorize this paper)
|Through your library||Only published papers are available at libraries|
Similar books and articles
Clark Glymour & Richard Scheines, On the Number of Experiments Suﬃcient and in the Worst Case Necessary to Identify All Causal Relations Among N Variables.
Jiji Zhang & Peter Spirtes, A Transformational Characterization of Markov Equivalence Between DAGs with Latent Variables.
Peter Spirtes, Christopher Meek & Thomas Richardson, Causal Inference in the Presence of Latent Variables and Selection Bias.
Added to index2009-01-28
Total downloads10 ( #114,432 of 739,344 )
Recent downloads (6 months)1 ( #61,538 of 739,344 )
How can I increase my downloads?