Dynamic Blocking and Collapsing for Gibbs Sampling

In this paper, we investigate combining block- ing and collapsing – two widely used strategies for improving the accuracy of Gibbs sampling – in the context of probabilistic graphical mod- els (PGMs). We show that combining them is not straight-forward because collapsing (or elim- inating variables) introduces new dependencies in the PGM and in computation-limited settings, this may adversely affect blocking. We there- fore propose a principled approach for tackling this problem. Specifically, we develop two scor- ing functions, one each for blocking and collaps- ing, and formulate the problem of partitioning the variables in the PGM into blocked and collapsed subsets as simultaneously maximizing both scor- ing functions (i.e., a multi-objective optimization problem). We propose a dynamic, greedy algo- rithm for approximately solving this intractable optimization problem. Our dynamic algorithm periodically updates the partitioning into blocked and collapsed variables by leveraging correla- tion statistics gathered from the generated sam- ples and enables rapid mixing by blocking to- gether and collapsing highly correlated variables. We demonstrate experimentally the clear benefit of our dynamic approach: as more samples are drawn, our dynamic approach significantly out- performs static graph-based approaches by an or- der of magnitude in terms of accuracy.