×

Learning high-dimensional directed acyclic graphs with latent and selection variables. (English) Zbl 1246.62131

Summary: We consider the problem of learning causal information between random variables in directed acyclic graphs (DAGs) when allowing arbitrarily many latent and selection variables. The FCI (Fast Causal Inference) algorithm has been explicitly designed to infer conditional independence and causal information in such settings. However, FCI is computationally infeasible for large graphs. We therefore propose s new RFCI algorithm, which is much faster than FCI. In some situations the output of the RFCI is slightly less informative, in particular with respect to conditional independence information. However, we prove that any causal information in the output of RFCI is correct in the asymptotic limit. We also define a class of graphs on which the outputs of FCI and RFCI are identical. We prove consistency of FCI and RFCI in sparse high-dimensional settings, and demonstrate in simulations that the estimation performances of the algorithms are very similar. All software is implemented in the R-package pcalg.

MSC:

62G99 Nonparametric inference
05C20 Directed graphs (digraphs), tournaments
65C60 Computational problems in statistics (MSC2010)
62P99 Applications of statistics
05C90 Applications of graph theory

Software:

TETRAD; pcalg; R
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] Aho, A., Hopcroft, J. and Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms . Addison-Wesley, Boston, MA. · Zbl 0326.68005
[2] Ali, R. A., Richardson, T. S. and Spirtes, P. (2009). Markov equivalence for ancestral graphs. Ann. Statist. 37 2808-2837. · Zbl 1178.68574 · doi:10.1214/08-AOS626
[3] Andersson, S. A., Madigan, D. and Perlman, M. D. (1997). A characterization of Markov equivalence classes for acyclic digraphs. Ann. Statist. 25 505-541. · Zbl 0876.60095 · doi:10.1214/aos/1031833662
[4] Chickering, D. M. (2002). Learning equivalence classes of Bayesian-network structures. J. Mach. Learn. Res. 2 445-498. · Zbl 1007.68179 · doi:10.1162/153244302760200696
[5] Colombo, D., Maathuis, M. H., Kalisch, M. and Richardson, T. S. (2012). Supplement to “Learning high-dimensional directed acyclic graphs with latent and selection variables.” . · Zbl 1246.62131
[6] Cooper, G. (1995). Causal discovery from data in the presence of selection bias. In Preliminary Papers of the Fifth International Workshop on Artificial Intelligence and Statistics (D. Fisher, ed.) 140-150.
[7] Dawid, A. P. (1980). Conditional independence for statistical operations. Ann. Statist. 8 598-617. · Zbl 0434.62006 · doi:10.1214/aos/1176345011
[8] Kalisch, M. and Bühlmann, P. (2007). Estimating high-dimensional directed acyclic graphs with the PC-algorithm. J. Mach. Learn. Res. 8 613-636. · Zbl 1222.68229
[9] Kalisch, M., Mächler, M., Colombo, D., Maathuis, M. H. and Bühlmann, P. (2012). Causal inference using graphical models with the R package pcalg. J. Statist. Software .
[10] Maathuis, M. H., Colombo, D., Kalisch, M. and Bühlmann, P. (2010). Predicting causal effects in large-scale systems from observational data. Nat. Methods 7 247-248.
[11] Maathuis, M. H., Kalisch, M. and Bühlmann, P. (2009). Estimating high-dimensional intervention effects from observational data. Ann. Statist. 37 3133-3164. · Zbl 1191.62118 · doi:10.1214/09-AOS685
[12] Meinshausen, N. and Bühlmann, P. (2006). High-dimensional graphs and variable selection with the lasso. Ann. Statist. 34 1436-1462. · Zbl 1113.62082 · doi:10.1214/009053606000000281
[13] Pearl, J. (2000). Causality. Models , Reasoning , and Inference . Cambridge Univ. Press, Cambridge. · Zbl 0959.68116
[14] Pearl, J. (2009). Causal inference in statistics: An overview. Stat. Surv. 3 96-146. · Zbl 1300.62013 · doi:10.1214/09-SS057
[15] Ramsey, J., Zhang, J. and Spirtes, P. (2006). Adjacency-faithfulness and conservative causal inference. In Proceedings of the 22 nd Annual Conference on Uncertainty in Artificial Intelligence . AUAI Press, Arlington, VA.
[16] Richardson, T. and Spirtes, P. (2002). Ancestral graph Markov models. Ann. Statist. 30 962-1030. · Zbl 1033.60008 · doi:10.1214/aos/1031689015
[17] Richardson, T. S. and Spirtes, P. (2003). Causal inference via ancestral graph models. In Highly Structured Stochastic Systems. Oxford Statistical Science Series 27 83-113. Oxford Univ. Press, Oxford.
[18] Robins, J. M., Hernán, M. A. and Brumback, B. (2000). Marginal structural models and causal inference in epidemiology. Epidemiology 11 550-560.
[19] Spirtes, P. (2001). An anytime algorithm for causal inference. In Proc. of the Eighth International Workshop on Artificial Intelligence and Statistics 213-221. Morgan Kaufmann, San Francisco.
[20] Spirtes, P., Glymour, C. and Scheines, R. (2000). Causation , Prediction , and Search , 2nd ed. MIT Press, Cambridge, MA. · Zbl 0806.62001
[21] Spirtes, P., Meek, C. and Richardson, T. (1999). An algorithm for causal inference in the presence of latent variables and selection bias. In Computation , Causation , and Discovery 211-252. AAAI Press, Menlo Park, CA.
[22] Verma, T. and Pearl, J. (1990). Equivalence and synthesis of causal models. In Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence 255-270. Elsevier, New York.
[23] Zhang, J. (2008). Causal reasoning with ancestral graphs. J. Mach. Learn. Res. 9 1437-1474. · Zbl 1225.68254
[24] Zhang, J. (2008). On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence 172 1873-1896. · Zbl 1184.68434 · doi:10.1016/j.artint.2008.08.001
[25] Zhao, P. and Yu, B. (2006). On model selection consistency of Lasso. J. Mach. Learn. Res. 7 2541-2563. · Zbl 1222.62008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.