Block-Value Symmetries in Probabilistic Graphical Models
This work addresses a specific bottleneck in lifted inference for probabilistic graphical models, offering an incremental improvement over existing methods.
The paper tackles the problem of missing state symmetries in probabilistic graphical models by introducing block-value (BV) permutations, which generalize variable-value symmetries to compute more symmetries. The result is BV-MCMC, an extension of orbital MCMC that mixes much faster than vanilla and orbital MCMC in experiments.
One popular way for lifted inference in probabilistic graphical models is to first merge symmetric states into a single cluster (orbit) and then use these for downstream inference, via variations of orbital MCMC [Niepert, 2012]. These orbits are represented compactly using permutations over variables, and variable-value (VV) pairs, but they can miss several state symmetries in a domain. We define the notion of permutations over block-value (BV) pairs, where a block is a set of variables. BV strictly generalizes VV symmetries, and can compute many more symmetries for increasing block sizes. To operationalize use of BV permutations in lifted inference, we describe 1) an algorithm to compute BV permutations given a block partition of the variables, 2) BV-MCMC, an extension of orbital MCMC that can sample from BV orbits, and 3) a heuristic to suggest good block partitions. Our experiments show that BV-MCMC can mix much faster compared to vanilla MCMC and orbital MCMC.