Approximate Counting of Graphical Models via MCMC Revisited. Issue 3 (24th December 2014)

• Record Type: Journal Article
• Authors: Sonntag, Dag; Peña, Jose M.; Gómez‐Olmedo, Manuel; Bielza, Concha; Moral, Serafín; Salmerón, Antonio
• Is Part Of: International journal of intelligent systems. Volume 30:Issue 3(2015:Mar.)
• Page Start: 384
• Page End: 420
• Publication Date: 2014-12-24
• Subjects: Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; 006.3
• DOI: 10.1002/int.21704
• Languages: English
• ISSNs: 0884-8173

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>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.</p> </abstract>