Title: On the completeness of first-order knowledge compilation for lifted probabilistic inference
Authors: Van den Broeck, Guy # ×
Issue Date: 13-Dec-2011
Host Document: Advances in Neural Information Processing Systems 24 pages:1386-1394
Series Title: Advances in Neural Information Processing Systems
Conference: Annual Conference on Neural Information Processing Systems (NIPS) edition:25 location:Granada, Spain date:13-15 December 2011
Article number: 805
Abstract: Probabilistic logics are receiving a lot of attention today because of their expressive power for knowledge representation and learning. However, this expressivity is detrimental to the tractability of inference, when done at the propositional level.
To solve this problem, various lifted inference algorithms have been proposed that reason at the first-order level, about groups of objects as a whole. Despite the existence of various lifted inference approaches, there are currently no completeness results about these algorithms.
The key contribution of this paper is that we introduce a formal definition of lifted inference that allows us to reason about the completeness of lifted inference algorithms relative to a particular class of probabilistic models.
We then show how to obtain a completeness result using a first-order knowledge compilation approach for theories of formulae containing up to two logical variables.
Description: acceptance rate 21.8% for papers
acceptance rate 1.4% for oral presentation
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
guyvdb-nips11-paper.pdfMain article Published 293KbAdobe PDFView/Open
Completeness of FO KC.pdfPresentation Published 1019KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.