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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GA23-07299S" target="_blank" >GA23-07299S: Statistické relační učení v dynamických doménách</a><br>

Návaznosti

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

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název statě ve sborníku

Frontiers in Artificial Intelligence and Applications

ISBN

—

ISSN

0922-6389

e-ISSN

1879-8314

Počet stran výsledku

10

Strana od-do

3145-3154

Název nakladatele

IOS Press

Místo vydání

Oxford

Místo konání akce

Santiago de Compostela

Datum konání akce

19. 10. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—