by Abhay Jha, Vibhav Gogate, Alexandra Meliou, Dan Suciu

Abstract:

Lifted Inference algorithms for representations that combine first-order logic and graphical models have been the focus of much recent research. All lifted algorithms developed to date are based on the same underlying idea: take a standard probabilistic inference algorithm (e.g., variable elimination, belief propagation etc.) and improve its efficiency by exploiting repeated structure in the first-order model. In this paper, we propose an approach from the other side in that we use techniques from logic for probabilistic inference. In particular, we define a set of rules that look only at the logical representation to identify models for which exact efficient inference is possible. Our rules yield new tractable classes that could not be solved efficiently by any of the existing techniques.

Citation:

Abhay Jha, Vibhav Gogate, Alexandra Meliou, and Dan Suciu, Lifted Inference Seen from the Other Side: The Tractable Features, in 24th Annual Conference on Neural Information Processing Systems (NIPS), 2010, pp. 973–981.

Bibtex:

@inproceedings{Jha:fk, Abstract = {Lifted Inference algorithms for representations that combine first-order logic and graphical models have been the focus of much recent research. All lifted algorithms developed to date are based on the same underlying idea: take a standard probabilistic inference algorithm (e.g., variable elimination, belief propagation etc.) and improve its efficiency by exploiting repeated structure in the first-order model. In this paper, we propose an approach from the other side in that we use techniques from logic for probabilistic inference. In particular, we define a set of rules that look only at the logical representation to identify models for which exact efficient inference is possible. Our rules yield new tractable classes that could not be solved efficiently by any of the existing techniques.}, Author = {Jha, Abhay and Gogate, Vibhav and Meliou, Alexandra and Suciu, Dan}, Booktitle = {24th Annual Conference on Neural Information Processing Systems (NIPS)}, pages = {973-981}, Title = {\href{http://people.cs.umass.edu/ameli/papers/NIPS2010.pdf}{Lifted Inference Seen from the Other Side: The Tractable Features}}, Venue = {NIPS}, address = {Vancouver, Canada}, month = {December}, Year = {2010} }