Proceedings

Approximate Weighted First-Order Model Counting: Exploiting Fast Approximate Model Counters and Symmetry

Timothy van Bremen, Ondrej Kuzelka

Video Download BibTeX Cite

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. Main track. Pages 4252-4258.

https://doi.org/10.24963/ijcai.2020/587

Keywords

  • Uncertainty in AI: Statistical Relational AI
  • Constraints and SAT: SAT: Algorithms and Techniques
  • Uncertainty in AI: Approximate Probabilistic Inference

Abstract

We study the symmetric weighted first-order model counting task and present ApproxWFOMC, a novel anytime method for efficiently bounding the weighted first-order model count of a sentence given an unweighted first-order model counting oracle. The algorithm has applications to inference in a variety of first-order probabilistic representations, such as Markov logic networks and probabilistic logic programs. Crucially for many applications, no assumptions are made on the form of the input sentence. Instead, the algorithm makes use of the symmetry inherent in the problem by imposing cardinality constraints on the number of possible true groundings of a sentence's literals. Realising the first-order model counting oracle in practice using the approximate hashing-based model counter ApproxMC3, we show how our algorithm is competitive with existing approximate and exact techniques for inference in first-order probabilistic models. We additionally provide PAC guarantees on the accuracy of the bounds generated.

Timothy van Bremen, and Ondrej Kuzelka. 2020. Approximate Weighted First-Order Model Counting: Exploiting Fast Approximate Model Counters and Symmetry. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20. IJCAI, 4252–4258. https://doi.org/10.24963/ijcai.2020/587
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards