Dynamic Blocking and Collapsing for Gibbs Sampling
This work addresses a computational bottleneck in Bayesian inference for researchers using Gibbs sampling, offering a significant but incremental improvement in efficiency for probabilistic graphical models.
The paper tackles the challenge of combining blocking and collapsing strategies in Gibbs sampling for probabilistic graphical models, where collapsing introduces new dependencies that can hinder blocking. The authors propose a dynamic, greedy algorithm that periodically updates variable partitions based on sample correlations, achieving an order of magnitude improvement in accuracy over static methods.
In this paper, we investigate combining blocking and collapsing -- two widely used strategies for improving the accuracy of Gibbs sampling -- in the context of probabilistic graphical models (PGMs). We show that combining them is not straight-forward because collapsing (or eliminating variables) introduces new dependencies in the PGM and in computation-limited settings, this may adversely affect blocking. We therefore propose a principled approach for tackling this problem. Specifically, we develop two scoring functions, one each for blocking and collapsing, and formulate the problem of partitioning the variables in the PGM into blocked and collapsed subsets as simultaneously maximizing both scoring functions (i.e., a multi-objective optimization problem). We propose a dynamic, greedy algorithm for approximately solving this intractable optimization problem. Our dynamic algorithm periodically updates the partitioning into blocked and collapsed variables by leveraging correlation statistics gathered from the generated samples and enables rapid mixing by blocking together and collapsing highly correlated variables. We demonstrate experimentally the clear benefit of our dynamic approach: as more samples are drawn, our dynamic approach significantly outperforms static graph-based approaches by an order of magnitude in terms of accuracy.