An Algorithm for Fast Recovery of Sparse Causal Graphs

Abstract

Previous asymptotically correct algorithms for recovering causal structure from sample probabilities have been limited even in sparse causal graphs to a few variables. We describe an asymptotically correct algorithm whose complexity for fixed graph connectivity increases polynomially in the number of vertices, and may in practice recover sparse graphs with several hundred variables. From sample data with n = 20,000, an implementation of the algorithm on a DECStation 3100 recovers the edges in a linear version of the ALARM network with 37 vertices and 46 edges. Fewer than 8% of the undirected edges are incorrectly identified in the output. Without prior ordering information, the program also determines the direction of edges for the ALARM graph with an error rate of 14%. Processing time is less than 10 seconds. Keywords DAGS, Causal Modelling.

Get full access to this article

View all access options for this article.

References

Beinlich, l. , Suermondt, H. , Chavez, R. , & Cooper, G. (1989). The ALARM monitoring system. (Technical Report KSL 88-84 Stanford, CA Knowledge Systems Laboratory Medical Computer Science, Stanford University.

Duncan, O.D. (1975). Introduction to structural equation models. New York: Academic Press .

Fung, R. , & Crawford, S. (1990). Constructor: A system for the induction of probabilistic models In Proceedings of the American Association for Artificial Intelligence (pp. 762-769). Boston.

Herskovits, E. , & Cooper, G. (1990). Kutato An entropy-driven system for construction of probabilistic expert systems from databases In Proceedings of the Sixth Conference on Uncertainty in AI (pp. 54-62) Cambridge, MA.

James, L.R. , Mulaik, S.A. , & Brett, J. (1982). Causal analysis. Newbury Park, CA Sage.

Joreskog, K. , & Sorbom, D. (1984). LISREL VI User's guide Mooresville, IN: Scientific Software.

Loehlin, J. (1987). Latent variable models. Hillsdale, NJ: Lawrence Ehrlbaum Assoc.

Pearl, J. , & Verma, T. (1990, October). A formal theory of inductive causation. (Techmcal Report R-135 Cognitive Science Laboratory Department of Computer Science, University of California, Los Angeles.

Spirtes, P. , Glymour, C. , & Schemes, R. (1990). Causality from probability In J. Tiles, G. McKee, and G. Dean (Eds.), Evolving knowledge m the natural and behavioral sciences (pp. 181-199). London: Pitman.

10.

Verma, T. , & Pearl, J. (1990). Equivalence and synthesis of causal models In Proceedings of the Sixth Conference on Uncertainty in AI (pp. 220-227). Cambridge, MA.