We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

cs.AI
new | recent | 1807

Change to browse by:

cs

References & Citations

Computer Science > Artificial Intelligence

Title:Block-Value Symmetries in Probabilistic Graphical Models

Abstract: 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.
Comments: 11 pages, 3 figures, Accepted in UAI 2018 and StaR AI 2018
Subjects: Artificial Intelligence (cs.AI)
Cite as: arXiv:1807.00643 [cs.AI]
  (or arXiv:1807.00643v2 [cs.AI] for this version)

Submission history

From: Ankit Anand [view email]
[v1] Mon, 2 Jul 2018 13:03:22 UTC (454 KB)
[v2] Sun, 8 Jul 2018 06:09:06 UTC (3,721 KB)