×
Ali, R. Ayesha; Richardson, Thomas S.; Spirtes, Peter

Markov equivalence for ancestral graphs. (English) Zbl 1178.68574

Ann. Stat. 37, No. 5B, 2808-2837 (2009).
Summary: Ancestral graphs can encode conditional independence relations that arise in Directed Acyclic Graph (DAG) models with latent and selection variables. However, for any ancestral graph, there may be several other graphs to which it is Markov equivalent. We state and prove conditions under which two maximal ancestral graphs are Markov equivalent to each other, thereby extending analogous results for DAGs given by other authors. These conditions lead to an algorithm for determining Markov equivalence that runs in time that is polynomial in the number of vertices in the graph.

Cited in 17 Documents

MSC:

68T30 Knowledge representation
05C75 Structural characterization of families of graphs
68T37 Reasoning under uncertainty in the context of artificial intelligence

Keywords:

directed acyclic graphs; discriminating path; inducing path; Markov equivalence; polynomial-time algorithm

Software:

TETRAD
PDF BibTeX XML Cite
\textit{R. A. Ali} et al., Ann. Stat. 37, No. 5B, 2808--2837 (2009; Zbl 1178.68574)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat

References:

[1] Ali, R. A., Richardson, T. and Spirtes, P. (2009). Supplementary material for “Markov equivalence for ancestral graphs.” Available at http://arxiv.org/abs/0905.1540v1. · Zbl 1178.68574
[2] 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
[3] Chickering, D. (1995). A transformational characterization of equivalent Bayesian network. In Uncertainty in Artificial Intelligence : Proceedings of the 11th Conference (P. Besnard and S. Hanks, eds.) 87-98. Morgan Kaufmann, San Francisco.
[4] Cooper, G. F. (1995). Causal discovery from data in the presence of selection bias. In Preliminary Papers , Fifth International Workshop on AI and Statistics (D. Fisher, ed.) 140-150. Ft. Lauderdale, FL.
[5] Cox, D. R. and Wermuth, N. (1996). Multivariate Dependencies : Models , Analysis and Interpretation . Chapman and Hall, London. · Zbl 0880.62124
[6] Dawid, A. (1980). Conditional independence for statistical operations. Ann. Statist. 8 598-617. · Zbl 0434.62006
[7] Drton, M., Andersson, S. A. and Perlman, M. D. (2006). Conditional independence models for seemingly unrelated regressions with incomplete data. J. Multivariate Anal. 97 385-411. · Zbl 1085.62056
[8] Drton, M. and Richardson, T. S. (2004). Multimodality of the likelihood in the bivariate seemingly unrelated regressions model. Biometrika 91 383-392. · Zbl 1079.62060
[9] Frydenberg, M. (1990). The chain graph Markov property. Scand. J. Statist. 17 333-353. · Zbl 0713.60013
[10] Koster, J. T. A. (1999). Linear Structural Equations and Graphical Models . The Fields Institute, Toronto.
[11] Koster, J. T. A. (2002). Marginalizing and conditioning in graphical models. Bernoulli 8 817-840. · Zbl 1011.60026
[12] Lauritzen, S. (1996). Graphical Models. Oxford Statistical Science Series 17 . Clarendon, Oxford, UK. · Zbl 0907.62001
[13] Meek, C. (1995). Causal inference and causal explanation with background knowledge. In Uncertainty in Artificial Intelligence : Proceedings of the 11th Conference (P. Besnard and S. Hanks, eds.) 403-410. Morgan Kaufmann, San Francisco.
[14] Pearl, J. (2000). Causality : Models , Reasoning and Inference . Cambridge Univ. Press, Cambridge, UK. · Zbl 0959.68116
[15] Richardson, T. S. and Spirtes, P. (2002). Ancestral graph Markov models. Ann. Statist. 30 962-1030. · Zbl 1033.60008
[16] Richardson, T. S. and Spirtes, P. (2003). Causal inference via ancestral graph models. In Highly Structured Stochastic Systems (P. Green, N. Hjort and S. Richardson, eds.). Oxford Univ. Press, Oxford. · Zbl 1033.60008
[17] Robins, J. (1997). Causal inference from complex longitudinal data. In Latent Variable Modeling and Applications to Causality ( Los Angeles , CA , 1994 ). Lecture Notes in Statistics 120 (M. Berkane, ed.) 69-117. Springer, New York. · Zbl 0969.62072
[18] Spirtes, P., Glymour, C. and Scheines, R. (1993). Causation , Prediction and Search. Lecture Notes in Statistics 81 . Springer. · Zbl 0806.62001
[19] Spirtes, P. and Richardson, T. S. (1997). A polynomial-time algorithm for determining DAG equivalence in the presence of latent variables and selection bias. In Preliminary Papers , Sixth International Workshop on AI and Statistics (D. Madigan and P. Smyth, eds.) 489-501. Ft. Lauderdale, FL.
[20] Studeny, M. (2004). Probabilistic Conditional Independence Structures . Springer, Santa Clara, CA, USA.
[21] Verma, T. and Pearl, J. (1990). Equivalence and synthesis of causal models. In Uncertainty in Artificial Intelligence : Proceedings of the Sixth Conference (M. Henrion, R. Shachter, L. Kanal and J. Lemmer, eds.) 220-227. Association for Uncertainty in AI, Mountain View, CA.
[22] Verma, T. and Pearl, J. (1991). Equivalence and synthesis of causal models. Technical Report R-150, Cognitive Systems Laboratory, UCLA. · Zbl 0765.68177
[23] Zellner, A. (1962). An efficient method of estimating seemingly unrelated regression equations and tests for aggregation bias. J. Amer. Statist. Assoc. 57 348-368. JSTOR: · Zbl 0113.34902
[24] Zhao, H., Zheng, Z. and Liu, B. (2005). On the Markov equivalence of maximal ancestral graphs. Sci. China Ser. A 48 548-562. · Zbl 1092.05066
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.