Generating and Sampling Orbits for Lifted Probabilistic Inference

Conference on Uncertainty in Artificial Intelligence (UAI 2019), Tel Aviv, Israel, July 22-25, 2019.
Oral Presentation
Steven Holtzen, Todd Millstein, Guy Van den Broeck
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.