Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting
Abstract
We highlight our work on lifted inference for the asymmetric Weighted First-Order Model Counting problem (WFOMC), which counts the assignments that satisfy a given sentence in first-order logic. This work is at the intersection of probabilistic databases and statistical relational learning. First, we discuss how adding negation can lower the query complexity, and describe the essential element (resolution) necessary to extend a previous algorithm for positive queries to handle queries with negation. Second, we describe our novel dichotomy result for a non-trivial fragment of first-order CNF sentences with negation. Finally, we discuss directions for future work.
Cite
Text
Gribkoff et al. "Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting." Conference on Uncertainty in Artificial Intelligence, 2014.Markdown
[Gribkoff et al. "Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting." Conference on Uncertainty in Artificial Intelligence, 2014.](https://mlanthology.org/uai/2014/gribkoff2014uai-understanding/)BibTeX
@inproceedings{gribkoff2014uai-understanding,
title = {{Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting}},
author = {Gribkoff, Eric and Van den Broeck, Guy and Suciu, Dan},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {2014},
pages = {280-289},
url = {https://mlanthology.org/uai/2014/gribkoff2014uai-understanding/}
}