Faster Lifting for Two-variable Logic Using Cell Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F21%3A00354301" target="_blank" >RIV/68407700:21230/21:00354301 - isvavai.cz</a>
Result on the web
<a href="https://proceedings.mlr.press/v161/bremen21a/bremen21a.pdf" target="_blank" >https://proceedings.mlr.press/v161/bremen21a/bremen21a.pdf</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Faster Lifting for Two-variable Logic Using Cell Graphs
Original language description
We consider the weighted first-order model counting (WFOMC) task, a problem with important applications to inference and learning in structured graphical models. Bringing together earlier work [Van den Broeck et al., 2011, 2014], a formal proof was given by Beame et al. [2015] showing that the two-variable fragment of first-order logic, FO^2, is domain-liftable, meaning it admits an algorithm for WFOMC whose runtime is polynomial in the given domain size. However, applying this theoretical upper bound is often impractical for real-world problem instances. We show how to adapt their proof into a fast algorithm for lifted inference in FO^2, using only off-the-shelf tools for knowledge compilation, and several careful optimizations involving the cell graph of the input sentence, a novel construct we define that encodes the interactions between the cells of the sentence. Experimental results show that, despite our approach being largely orthogonal to that of Forclift [Van den Broeck et al., 2011], our algorithm often outperforms it, scaling to larger domain sizes on more complex input sentences.
Czech name
—
Czech description
—
Classification
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)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence
ISBN
—
ISSN
2640-3498
e-ISSN
—
Number of pages
10
Pages from-to
1393-1402
Publisher name
ML Research Press
Place of publication
—
Event location
Online
Event date
Jul 27, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—