×
Andersson, Steen A.; Perlman, Michael D.

Characterizing Markov equivalence classes for AMP chain graph models. (English) Zbl 1096.62097

Ann. Stat. 34, No. 2, 939-972 (2006).
Summary: Chain graphs (CG) (= adicyclic graphs) use undirected and directed edges to represent both structural and associative dependences. Like acyclic directed graphs (ADGs), the CG associated with a statistical Markov model may not be unique, so CGs fall into Markov equivalence classes, which may be superexponentially large, leading to unidentifiability and computational inefficiency in model search and selection.
It is shown here that, under the S. A. Andersson, D. Madigan and M. D. Perlman (AMP) interpretation of a CG [Scand.J. Stat. 24, No. 1, 81–102 (1997; Zbl 0918.60050); Ann. Stat. 25, No. 2, 505–541 (1997; Zbl 0876.60095)], each Markov-equivalence class can be uniquely represented by a single distinguished CG, the AMP essential graph, that is itself simultaneously Markov equivalent to all CGs in the AMP Markov equivalence class. A complete characterization of AMP essential graphs is obtained. Like the essential graph previously introduced for ADGs, the AMP essential graph will play a fundamental role for inference and model search and selection for AMP CG models.

Cited in 10 Documents

MSC:

62M99 Inference from stochastic processes
05C90 Applications of graph theory
60J99 Markov processes
62M45 Neural nets and related approaches to inference from stochastic processes
60K99 Special processes
68R10 Graph theory (including graph drawing) in computer science
68T30 Knowledge representation

Keywords:

graphical model; chain graph; Markov equivalence; essential graph

Citations:

Zbl 0876.60095; Zbl 0918.60050
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Andersson, S. A., Madigan, D. and Perlman, M. D. (1996). An alternative Markov property for chain graphs. In Uncertainty in Artificial Intelligence : Proc. Twelfth Conference (F. Jensen and E. Horvitz, eds.) 40–48. Morgan Kaufmann, San Francisco.
[2] Andersson, S. A., Madigan, D. and Perlman, M. D. (1997). On the Markov equivalence of chain graphs, undirected graphs and acyclic digraphs. Scand. J. Statist. 24 81–102. · Zbl 0918.60050 · doi:10.1111/1467-9469.t01-1-00050
[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] Andersson, S. A., Madigan, D. and Perlman, M. D. (2001). Alternative Markov properties for chain graphs. Scand. J. Statist. 28 33–85. · Zbl 0972.60067 · doi:10.1111/1467-9469.00224
[5] Andersson, S. A. and Perlman, M. D. (2004). Characterizing Markov equivalence classes for AMP chain graph models. Technical Report 453, Dept. Statistics, Univ. Washington. Available at www.stat.washington.edu/www/research/reports/2004/tr453.pdf. · Zbl 1096.62097
[6] Andersson, S. A. and Perlman, M. D. (2005). On the structure of essential graphs for AMP chain graph models.
[7] Blair, J. R. S. and Peyton, B. (1993). An introduction to chordal graphs and clique trees. In Graph Theory and Sparse Matrix Computation (A. George, J. R. Gilbert and J. W. H. Liu, eds.) 1–29. Springer, New York. · Zbl 0803.68081
[8] Bouckaert, R. R. and Studený, M. (1995). Chain graphs: Semantics and expressiveness. Symbolic and Quantitative Approaches to Reasoning and Uncertainty . Lecture Notes in Artificial Intelligence 946 69–76. Springer, Berlin.
[9] Buntine, W. L. (1995). Chain graphs for learning. In Uncertainty in Artificial Intelligence : Proc. Eleventh Conference (P. Besnard and S. Hanks, eds.) 46–54. Morgan Kaufmann, San Francisco.
[10] Castelo, R. and Perlman, M. D. (2004). Learning essential graph Markov models from data. In Advances in Bayesian Networks (J. A. Gámez, S. Moral and A. Salmerón, eds.) 255–269. Springer, Berlin.
[11] Cowell, R. G., Dawid, A. P., Lauritzen, S. L. and Spiegelhalter, D. J. (1999). Probabilistic Networks and Expert Systems. Springer, New York. · Zbl 0937.68121 · doi:10.1007/b97670
[12] Cox, D. R. (1999). Graphical Markov models: Statistical motivation. Paper presented at the Workshop on Conditional Independence Structures and Graphical Models, Fields Institute for Research in Mathematical Sciences, Toronto, Canada.
[13] Cox, D. R. and Wermuth, N. (1996). Multivariate Dependencies : Models , Analysis and Interpretation . Chapman and Hall, London. · Zbl 0880.62124
[14] Drton, M. and Eichler, M. (2006). Maximum likelihood estimation in Gaussian chain graph models under the alternative Markov property. Scand. J. Statist. 33 247–258. · Zbl 1125.62086 · doi:10.1111/j.1467-9469.2006.00482.x
[15] Frydenberg, M. (1990). The chain graph Markov property. Scand. J. Statist. 17 333–353. · Zbl 0713.60013
[16] Gillispie, S. and Perlman, M. D. (2002). The size distribution for Markov equivalence classes of acyclic digraph models. Artificial Intelligence 141 137–155. · Zbl 1043.68096 · doi:10.1016/S0004-3702(02)00264-3
[17] Højsgaard, S. and Thiesson, B. (1995). BIFROST–Block recursive models induced from relevant knowledge, observations and statistical techniques. Comput. Statist. Data Anal. 19 155–175. · Zbl 0875.62566 · doi:10.1016/0167-9473(93)E0054-8
[18] Lauritzen, S. L. (1996). Graphical Models. Oxford Univ. Press. · Zbl 0907.62001
[19] Lauritzen, S. L. and Wermuth, N. (1989). Graphical models for associations between variables, some of which are qualitative and some quantitative. Ann. Statist. 17 31–57. · Zbl 0669.62045 · doi:10.1214/aos/1176347003
[20] Levitz, M., Perlman, M. D. and Madigan, D. (2001). Separation and completeness properties for AMP chain graph Markov models. Ann. Statist. 29 1751–1784. · Zbl 1043.62080 · doi:10.1214/aos/1015345961
[21] Madigan, D., Andersson, S. A., Perlman, M. D. and Volinsky, C. T. (1996). Bayesian model averaging and model selection for Markov equivalence classes of acyclic digraphs. Comm. Statist.—Theory Methods 25 2493–2519. · Zbl 0894.62032 · doi:10.1080/03610929608831853
[22] Roverato, A. (2005). A unified approach to the characterization of equivalence classes of DAGs, chain graphs with no flags and chain graphs. Scand. J. Statist. 32 295–312. · Zbl 1090.62066 · doi:10.1111/j.1467-9469.2005.00422.x
[23] Studený, M. (1996). On separation criterion and recovery algorithm for chain graphs. In Uncertainty in Artificial Intelligence : Proc. Twelfth Conference (F. Jensen and E. Horvitz, eds.) 509–516. Morgan Kaufmann, San Francisco.
[24] Studený, M. (1997). A recovery algorithm for chain graphs. Internat. J. Approx. Reason. 17 265–293. · Zbl 0939.68096 · doi:10.1016/S0888-613X(97)00018-2
[25] Studený, M. (1998). Bayesian networks from the point of view of chain graphs. In Uncertainty in Artificial Intelligence : Proc. Fourteenth Conference (G. F. Cooper and S. Moral, eds.) 496–503. Morgan Kaufmann, San Francisco.
[26] Studený, M. and Bouckaert, R. R. (1998). On chain graph models for description of conditional independence structure. Ann. Statist. 26 1434–1495. · Zbl 0930.62066 · doi:10.1214/aos/1024691250
[27] Volf, M. and Studený, M. (1999). A graphical characterization of the largest chain graphs. Internat. J. Approx. Reason. 20 209–236. · Zbl 0935.62063 · doi:10.1016/S0888-613X(99)00003-1
[28] Wermuth, N. and Lauritzen, S. L. (1990). On substantive research hypotheses, conditional independence graphs and graphical chain models (with discussion). J. Roy. Statist. Soc. Ser. B 52 21–72. JSTOR: · Zbl 0749.62004
[29] Whittaker, J. (1990). Graphical Models in Applied Multivariate Statistics . Wiley, Chi- chester. · Zbl 0732.62056
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.