Information Theory Tools to Rank MCMC Algorithms on Probabilistic Graphical Models
Firas Hamze‚ Jean−Noel Rivasseau and Nando de Freitas
We propose efﬁcient MCMC tree samplers for random ﬁelds 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 ﬁrst. 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 efﬁcient 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.