Lifted Inference Seen from the Other Side: The Tractable Features
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}
}