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 = dec,
Year = {2010}
}