Generating and Sampling Orbits for Lifted Probabilistic Inference
This work enables efficient probabilistic inference for non-relational models by exploiting symmetry, addressing a key limitation in the field.
The authors tackled the problem of exact lifted inference for arbitrary discrete factor graphs, which previous methods could not handle, and introduced a lifted Markov-Chain Monte-Carlo algorithm that mixes rapidly based on symmetry.
A key goal in the design of probabilistic inference algorithms is identifying and exploiting properties of the distribution that make inference tractable. Lifted inference algorithms identify symmetry as a property that enables efficient inference and seek to scale with the degree of symmetry of a probability model. A limitation of existing exact lifted inference techniques is that they do not apply to non-relational representations like factor graphs. In this work we provide the first example of an exact lifted inference algorithm for arbitrary discrete factor graphs. In addition we describe a lifted Markov-Chain Monte-Carlo algorithm that provably mixes rapidly in the degree of symmetry of the distribution.