Lifted Inference with Linear Order Axiom

Authors

  • Jan Tóth Czech Technical University in Prague
  • Ondřej Kuželka Czech Technical University in Prague

DOI:

https://doi.org/10.1609/aaai.v37i10.26449

Keywords:

RU: Relational Probabilistic Models

Abstract

We consider the task of weighted first-order model counting (WFOMC) used for probabilistic inference in the area of statistical relational learning. Given a formula φ, domain size n and a pair of weight functions, what is the weighted sum of all models of φ over a domain of size n? It was shown that computing WFOMC of any logical sentence with at most two logical variables can be done in time polynomial in n. However, it was also shown that the task is #P1-complete once we add the third variable, which inspired the search for extensions of the two-variable fragment that would still permit a running time polynomial in n. One of such extension is the two-variable fragment with counting quantifiers. In this paper, we prove that adding a linear order axiom (which forces one of the predicates in φ to introduce a linear ordering of the domain elements in each model of φ) on top of the counting quantifiers still permits a computation time polynomial in the domain size. We present a new dynamic programming-based algorithm which can compute WFOMC with linear order in time polynomial in n, thus proving our primary claim.

Downloads

Published

2023-06-26

How to Cite

Tóth, J., & Kuželka, O. (2023). Lifted Inference with Linear Order Axiom. Proceedings of the AAAI Conference on Artificial Intelligence, 37(10), 12295-12304. https://doi.org/10.1609/aaai.v37i10.26449

Issue

Section

AAAI Technical Track on Reasoning Under Uncertainty