Title: Understanding the complexity of lifted inference and asymmetric weighted model counting
Authors: Gribkoff, Eric ×
Van den Broeck, Guy
Suciu, Dan #
Issue Date: Jul-2014
Host Document: Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence (UAI) pages:280-289
Conference: Conference on Uncertainty in Artificial Intelligence (UAI) edition:30 location:Quebec City, Quebec, Canada date:23-27 July 2014
Abstract: In this paper we study lifted inference for the Weighted First-Order Model Counting problem (WFOMC), which counts the assignments that satisfy a given sentence in first-order logic (FOL); it has applications in Statistical Relational Learning (SRL) and Probabilistic Databases (PDB). We present several results. First, we describe a lifted inference algorithm that generalizes prior approaches in SRL and PDB. Second, we provide a novel dichotomy result for a non-trivial fragment of FO CNF sentences, showing that for each sentence the WFOMC problem is either in PTIME or #P-hard in the size of the input domain; we prove that, in the first case our algorithm solves the WFOMC problem in PTIME, and in the second case it fails. Third, we present several properties of the algorithm. Finally, we discuss limitations of lifted inference for symmetric probabilistic databases (where the weights of ground literals depend only on the relation name, and not on the constants of the domain), and prove the impossibility of a dichotomy result for the complexity of probabilistic inference for the entire language FOL.
Description: 32% acceptance rate
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
gribkoff-uai14.pdfOA article Published 358KbAdobe PDFView/Open


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