From Fields to Trees
This work addresses efficiency improvements in probabilistic inference for researchers in machine learning and statistics, though it is incremental as it builds on existing MCMC and partitioning techniques.
The paper tackles the problem of computing posterior distributions in undirected graphical models by introducing new MCMC algorithms that partition Markov Random Fields into non-overlapping trees, showing empirically that tree sampling is more efficient than existing methods like Gibbs sampling and loopy belief propagation, with proven lower variance.
We present new MCMC algorithms for computing the posterior distributions and expectations of the unknown variables in undirected graphical models with regular structure. For demonstration purposes, we focus on Markov Random Fields (MRFs). By partitioning the MRFs into non-overlapping trees, it is possible to compute the posterior distribution of a particular tree exactly by conditioning on the remaining tree. These exact solutions allow us to construct efficient blocked and Rao-Blackwellised MCMC algorithms. We show empirically that tree sampling is considerably more efficient than other partitioned sampling schemes and the naive Gibbs sampler, even in cases where loopy belief propagation fails to converge. We prove that tree sampling exhibits lower variance than the naive Gibbs sampler and other naive partitioning schemes using the theoretical measure of maximal correlation. We also construct new information theory tools for comparing different MCMC schemes and show that, under these, tree sampling is more efficient.