Decomposition of two classes of structural models

Abstract

The conditional independence structure of a common probability measure is a structural model. In this paper, we solve an open problem posed by Studený [Probabilistic Conditional Independence Structures, Theme 9, p. 206]. A new approach is proposed to decompose a directed acyclic graph and its optimal properties are studied. We interpret this approach from the perspective of the decomposition of the corresponding conditional independence model and provide an algorithm for identifying the maximal prime subgraphs in a directed acyclic graph.

Keywords

Combinatorial imset / conditional independence model / decomposition / directed acyclic graph / undirected graph

References

[1] Asmussen S, Edwards D. Collapsibility and response variables in contingency tables. Biometrika, 1983, 70: 567-578

[2] Cowell R G, Dawid A P, Lauritzen S L, Spiegelhalter D G. Probabilistic Network and Expert System, 1999, New York: Springer-Verlag

[3] Cox D R, Wermuth N. Multivariate Dependencies: Models Analysis and Interpretation, 1993, London: Chapman & Hall

[4] Dawid A P. Conditional independence in statistical theory. J R Stat Soc Ser B Stat Methodol, 1979, 41: 1-31

[5] Edwards D. Introduction to Graphical Modelling, 2000 2nd ed. Berlin: Springer-Verlag

[6] Frydenberg M. Marginalization and collapsibility in graphical interaction models. Ann Statist, 1990, 18: 790-805

[7] Geiger D, Pearl J. Logical and algorithmic properties of conditional independence and graphical models. Ann Statist, 1993, 21: 2001-2021

[8] Lauritzen S L. Graphical Models, 1996, Oxford: Clarendon Press

[9] Lauritzen S L. Lectures on Contingency Tables, 2002 4th ed. Aalborg: Aalborg University

[10] Lauritzen S L, Dawid A P, Larsen B N, Leimer H G. Independence properties of directed Markov fields. Networks, 1990, 20: 491-505

[11] Lauritzen S L, Spiegelhalter D J. Local computations with probabilities on graphical structures and their application to expert systems (with discussion). J R Stat Soc Ser B Stat Methodol, 1988, 50: 157-224

[12] Leimer H G. Optimal decomposition by clique separators. Discrete Math, 1993, 113: 99-123

[13] Liu B H, Guo J H, Jing B Y. A note on minimal d-separation trees for structural learning. Artificial Intelligence, 2010, 174: 442-448

[14] Ma Z, Xie X, Geng Z. Structural learning of chain graph via decomposition. J Mach Learn Res, 2008, 9: 2847-2880

[15] Matúš F. On the maximum-entropy extensions of probability measures over undirected graphs. Proceedings of WUPES94, September 11–15, Trest, Czech Republic, 1994 181 198

[16] Matúš F. Conditional independence among four random variables III: Final conclusion. Combin Probab Comput, 1999, 8: 269-276

[17] Matúš F. Towards classification of semi-graphoids. Discrete Math, 2004, 277: 115-145

[18] Neapolitan R E. Learning Bayesian Networks, 2004, Upper Saddle River: Pearson Prentice Hall

[19] Olesen K G, Madsen A L. Maximal prime subgraph decomposition of Bayesian networks. IEEE Transactions on Systems, Man, and Cybernetics, 2002, 32: 21-31

[20] Pearl J. Probabilistic Reasoning in Intelligent Systems, 1988, Burlington: Morgan Kaufmann

[21] Pearl J, Paz A. Du Boulay B, Hogg D, Steels L. Graphoids, graph-based logic for reasoning about relevance relations. Advances in Artificial Intelligence II, 1987, Amsterdam: North-Holland 357 363

[22] Shenoy P P. Conditional independence in valuation-based systems. Int J Approximate Reasoning, 1994, 10: 203-234

[23] Studený M. Probabilistic Conditional Independence Structures, 2005, Berlin: Springer-Verlag

[24] Studený M. An algebraic approach to structural learning Bayesian networks. Proceedings of the 11th International Conference IPMU, 2006 2284 2291

[25] Studený M, Vomlel J, Hemmecke R. Geometric view on learning Bayesian network structures. Int J Approximate Reasoning, 2010, 51: 573-586

[26] Wang X F, Guo J H, He X. Finding the minimal set for collapsible graphical models. Proc Amer Math Soc, 2011, 139: 361-373

[27] Whittaker J. Graphical Models in Applied Multivariate Statistics, 1990, New York: Wiley

[28] Xie X, Geng Z. A recursive method for structural learning about directed acyclic graphs. J Mach Learn Res, 2008, 9: 459-483

[29] Xie X, Geng Z, Zhao Q. Decomposition of structural learning about directed acyclic graphs. Artificial Intelligence, 2006, 170: 422-439