Information Theory Tools to Rank MCMC Algorithms on Probabilistic Graphical Models

Abstract

We propose efficient MCMC tree samplers for random fields and factor graphs. Our tree sampling approach combines elements of Monte Carlo simulation as well as exact belief propagation. It requires that the graph be partitioned into trees first. The partition can be generated by hand or automatically using a greedy graph algorithm. The tree partitions allow us to perform exact inference on each tree. This enables us to implement efficient Rao-Blackwellised blocked Gibbs samplers, where each tree is sampled by conditioning on the other trees. We use information theory tools to rank MCMC algorithms corresponding to different partitioning schemes.