Premium
Approximate Counting of Graphical Models via MCMC Revisited
Author(s) -
Sonntag Dag,
Peña Jose M.,
GómezOlmedo Manuel
Publication year - 2015
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/int.21704
Subject(s) - markov chain monte carlo , directed acyclic graph , markov chain , graphical model , chain (unit) , combinatorics , equivalence (formal languages) , mathematics , computer science , discrete mathematics , monte carlo method , statistics , physics , astronomy
We apply Markov chain Monte Carlo (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, the DAG or EG learnt from some given data is likely to be connected. 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.