A More Practical Algorithm for Weighted First-Order Model Counting with Linear Order Axiom

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00378126" target="_blank" >RIV/68407700:21230/24:00378126 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.3233/FAIA240858" target="_blank" >https://doi.org/10.3233/FAIA240858</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3233/FAIA240858" target="_blank" >10.3233/FAIA240858</a>

Result language

angličtina

Original language name

A More Practical Algorithm for Weighted First-Order Model Counting with Linear Order Axiom

Original language description

We consider the task of weighted first-order model counting (WFOMC), a fundamental problem of probabilistic inference in statistical relational learning. The goal of WFOMC is to compute the weighted sum of models of a given first-order logic sentence over a finite domain, where each model is assigned a weight by a pair of weighting functions. Past work has shown that WFOMC can be solved in polynomial time in the domain size if the sentence is in the two-variable fragment of first-order logic (FO2). This result is later extended to the case where the sentence is in FO2with the linear order axiom, which requires a binary predicate in the sentence to introduce a linear ordering of the domain elements. However, despite its polynomial theoretical complexity, the existing domain-liftable algorithm for WFOMC with the linear order often suffers from inefficiencies when applied to real-world problems. This paper introduces a novel domain-lifted algorithm for WFOMC with the linear order axiom. Compared to the existing approach, our proposed algorithm exploits the inherent symmetries within first-order logic sentences and weighting functions to minimize redundant computations. Experimental results verify the efficiency of our approach, demonstrating a significant speedup over the existing approach.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA23-07299S" target="_blank" >GA23-07299S: Statistical Relational Learning in Dynamic Domains</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Frontiers in Artificial Intelligence and Applications

ISBN

—

ISSN

0922-6389

e-ISSN

1879-8314

Number of pages

10

Pages from-to

3145-3154

Publisher name

IOS Press

Place of publication

Oxford

Event location

Santiago de Compostela

Event date

Oct 19, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—