In Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence, Portland, Oregon, 1996. E.Horvitz and F.Jensen (eds.), Morgan Kaufmann, San Francisco, CA
| PS File (1.2M) | PDF File (458K) |
Directed acyclic graphs have been used fruitfully to represent causal structures (see Pearl (1988)). However, in the social sciences and elsewhere models are often used which correspond both causally and statistically to cyclic graphs (Spirtes(1995)). Pearl has discussed predicting the effects of intervention in models of this kind, so-called linear simultaneous structural equation models. This raises the question of whether it is possible to make inferences about cyclic causal structure, from sample data. In particular do there exist general, informative, feasible and reliable procedures for inferring causal structure from conditional independence relations among variables in a sample generated by an unknown causal structure?
In this paper I present a discovery algorithm that is correct in the large sample limit, given commonly (but implicitly) made plausible assumptions, and which provides information about the existence or non-existence of causal pathways from one variable to another. The algorithm is polynomial on sparse graphs. I include a proof that the algorithm is correct. I have also shown that the algorithm is d-separation complete.
Keywords: