Markov Chains on Orbits of Permutation Groups

By Mathias Niepert. 2012

64 citations recorded by the source corpus.

We present a novel approach to detecting and utilizing symmetries in probabilistic graphical models with two main contributions. First, we present a scalable approach to computing generating sets of permutation groups representing the symmetries of graphical models. Second, we introduce orbital Markov chains, a novel family of Markov chains leveraging model symmetries to reduce mixing times. We establish an insightful connection between model symmetries and rapid mixing of orbital Markov chains. Thus, we present the first lifted MCMC algorithm for probabilistic graphical models. Both analytical and empirical results demonstrate the effectiveness and efficiency of the approach.

Subfields: Artificial Intelligence, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

Equivariance Through Parameter-Sharing (2017, methodology): “In particular, many probabilistic inference techniques have been extended to graphical models with known symmetry groups (Raedt et al., 2016; Kersting et al., 2009; Bui et al., 2012; Niepert, 2012).”
Deep Symmetry Networks (2014, background): “Symmetries in graphical models [21] lead to effective lifted probabilistic inference algorithms.”
Automorphism Groups of Graphical Models and Lifted Variational Inference (2012, methodology): “ this MLN prescribes attractive potentials on the pairs (Smoke(x);Smoke(y)), thus MAP 5The ground graphical model of this MLN has tree-width equals to the domain size. 6Independent result reported in [13] seems to suggest better performance can be obtained using SAUCY, a more modern tool for ﬁnding ”