Lifted Probabilistic Inference by First-Order Knowledge Compilation

Van den Broeck, Guy; Taghipour, Nima; Meert, Wannes; Davis, Jesse; de Raedt, Luc

doi:10.5591/978-1-57735-516-8/IJCAI11-363

Lifted Probabilistic Inference by First-Order Knowledge Compilation

Guy Van den Broeck, Nima Taghipour, Wannes Meert, Jesse Davis, Luc De Raedt

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2178-2184.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-363

Abstract

Probabilistic logical languages provide powerful formalisms forknowledge representation and learning. Yet performing inference inthese languages is extremely costly, especially if it is done at thepropositional level. Lifted inference algorithms, which avoid repeatedcomputation by treating indistinguishable groups of objects as one, helpmitigate this cost. Seeking inspiration from logical inference, wherelifted inference (e.g., resolution) is commonly performed, we developa model theoretic approach to probabilistic lifted inference. Our algorithmcompiles a first-order probabilistic theory into a first-orderdeterministic decomposable negation normal form (d-DNNF) circuit.Compilation offers the advantage that inference is polynomial in thesize of the circuit. Furthermore, by borrowing techniques from theknowledge compilation literature our algorithm effectively exploitsthe logical structure (e.g., context-specific independencies) withinthe first-order model, which allows more computation to be done at the lifted level.An empirical comparison demonstrates the utility of the proposed approach.

Guy Van den Broeck, Nima Taghipour, Wannes Meert, Jesse Davis, and Luc de Raedt. 2011. Lifted Probabilistic Inference by First-Order Knowledge Compilation. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2178–2184. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-363

@inproceedings{ijcai2011p363,
  title     = {Lifted Probabilistic Inference by First-Order Knowledge Compilation},
  author    = {Van den Broeck, Guy and Taghipour, Nima and Meert, Wannes and Davis, Jesse and de Raedt, Luc},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2178--2184},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-363},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-363},
}

TY  - CPAPER
TI  - Lifted Probabilistic Inference by First-Order Knowledge Compilation
AU  - Van den Broeck, Guy
AU  - Taghipour, Nima
AU  - Meert, Wannes
AU  - Davis, Jesse
AU  - de Raedt, Luc
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2178
EP  - 2184
DO  - 10.5591/978-1-57735-516-8/IJCAI11-363
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-363
ER  -