Generating and Sampling Orbits for Lifted Probabilistic Inference
Steven Holtzen, Todd Millstein, Guy Van den Broeck
Abstract
A key goal in the design of probabilistic inference algorithms is identifying and exploit- ing 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.
BibTeX
@InProceedings{pmlr-v115-holtzen20a,
title = {Generating and Sampling Orbits for Lifted Probabilistic Inference},
author = {Holtzen, Steven and Millstein, Todd and {Van den Broeck}, Guy},
booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference},
pages = {985--994},
year = {2020},
editor = {Adams, Ryan P. and Gogate, Vibhav},
volume = {115},
series = {Proceedings of Machine Learning Research},
month = {22--25 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v115/holtzen20a/holtzen20a.pdf},
url = {https://proceedings.mlr.press/v115/holtzen20a.html},
abstract = {A key goal in the design of probabilistic inference algorithms is identifying and exploit- ing 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.}
}