Approximate Counting of Graphical Models Via MCMC Revisited
2015 (English)In: International Journal of Intelligent Systems, ISSN 0884-8173, E-ISSN 1098-111X, Vol. 30, no 3, 384-420 p.Article in journal (Refereed) Published
We apply MCMC sampling to approximately calculate some quantities, and discuss their implications for learning directed and acyclic graphs (DAGs) from data. Specifically, we calculate the approximate ratio of essential graphs (EGs) to DAGs for up to 31 nodes. Our ratios suggest that the average Markov equivalence class is small. We show that a large majority of the classes seem to have a size that is close to the average size. This suggests that one should not expect more than a moderate gain in efficiency when searching the space of EGs instead of the space of DAGs. We also calculate the approximate ratio of connected EGs to connected DAGs, of connected EGs to EGs, and of connected DAGs to DAGs. These new ratios are interesting because, as we will see, they suggest that some conjectures that appear in the literature do not hold. Furthermore, we prove that the latter ratio is asymptotically 1.
Finally, we calculate the approximate ratio of EGs to largest chain graphs for up to 25 nodes. Our ratios suggest that Lauritzen-Wermuth-Frydenberg chain graphs are considerably more expressive than DAGs. We also report similar approximate ratios and conclusions for multivariate regression chain graphs.
Place, publisher, year, edition, pages
Wiley-Blackwell, 2015. Vol. 30, no 3, 384-420 p.
MCMC sampling, Bayesian networks, Chain graphs, Lauritzen-Wermuth-Frydenberg interpretation, Multivariate regression interpretation
Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-105815DOI: 10.1002/int.21704ISI: 000348308600008OAI: oai:DiVA.org:liu-105815DiVA: diva2:710829
This work is funded by the Center for Industrial Information Technology (CENIIT) and a so-called career contract at Linkoping University, by the Swedish Research Council (ref. 2010-4808), and by FEDER funds and the Spanish Government (MICINN) through the projects TIN2010-20900-C04-03 and TIN2010-20900-C04-01.2014-04-082014-04-082016-03-29Bibliographically approved