On Expressiveness of the AMP Chain Graph Interpretation
2014 (English)In: Probabilistic Graphical Models: 7th European Workshop, PGM 2014, Utrecht, The Netherlands, September 17-19, 2014. Proceedings, Springer, 2014, 458-470 p.Conference paper (Refereed)
In this paper we study the expressiveness of the Andersson-Madigan-Perlman interpretation of chain graphs. It is well known that all independence models that can be represented by Bayesian networks also can be perfectly represented by chain graphs of the Andersson-Madigan-Perlman interpretation but it has so far not been studied how much more expressive this second class of models is. In this paper we calculate the exact number of representable independence models for the two classes, and the ratio between them, for up to five nodes. For more than five nodes the explosive growth of chain graph models does however make such enumeration infeasible. Hence we instead present, and prove the correctness of, a Markov chain Monte Carlo approach for sampling chain graph models uniformly for the Andersson-Madigan-Perlman interpretation. This allows us to approximate the ratio between the numbers of independence models representable by the two classes as well as the average number of chain graphs per chain graph model for up to 20 nodes. The results show that the ratio between the numbers of representable independence models for the two classes grows exponentially as the number of nodes increases. This indicates that only a very small fraction of all independence models representable by chain graphs of the Andersson-Madigan-Perlman interpretation also can be represented by Bayesian networks.
Place, publisher, year, edition, pages
Springer, 2014. 458-470 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 8754
Chain graphs, Andersson-Madigan-Perlman interpretation, MCMC sampling
IdentifiersURN: urn:nbn:se:liu:diva-111786DOI: 10.1007/978-3-319-11433-0_30ISI: 000358253800030ScopusID: 2-s2.0-84921764539ISBN: 978-3-319-11432-3ISBN: 978-3-319-11433-0OAI: oai:DiVA.org:liu-111786DiVA: diva2:760241
7th European Workshop, PGM 2014, Utrecht, The Netherlands, September 17-19, 2014
FunderSwedish Research Council, 2010-4808