Domain-Lifted Sampling for Universal Two-Variable Logic and Extensions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00359634" target="_blank" >RIV/68407700:21230/22:00359634 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1609/aaai.v36i9.21246" target="_blank" >https://doi.org/10.1609/aaai.v36i9.21246</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1609/aaai.v36i9.21246" target="_blank" >10.1609/aaai.v36i9.21246</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Domain-Lifted Sampling for Universal Two-Variable Logic and Extensions

Popis výsledku v původním jazyce

Given a first-order sentence ? and a domain size n, how can one sample a model of ? on the domain {1, . . . , n} efficiently as n scales? We consider two variants of this problem: the uniform sampling regime, in which the goal is to sample a model uniformly at random, and the symmetric weighted sampling regime, in which models are weighted according to the number of groundings of each predicate appearing in them. Solutions to this problem have applications to the scalable generation of combinatorial structures, as well as sampling in several statistical-relational models such as Markov logic networks and probabilistic logic programs. In this paper, we identify certain classes of sentences that are domain-liftable under sampling, in the sense that they admit a sampling algorithm that runs in time polynomial in n. In particular, we prove that every sentence of the form ∀x∀y: ?(x, y) for some quantifier-free formula ?(x,y) is domain-liftable under sampling. We then further show that this result continues to hold in the presence of one or more cardinality constraints as well as a single tree axiom constraint.

Název v anglickém jazyce

Domain-Lifted Sampling for Universal Two-Variable Logic and Extensions

Popis výsledku anglicky

Given a first-order sentence ? and a domain size n, how can one sample a model of ? on the domain {1, . . . , n} efficiently as n scales? We consider two variants of this problem: the uniform sampling regime, in which the goal is to sample a model uniformly at random, and the symmetric weighted sampling regime, in which models are weighted according to the number of groundings of each predicate appearing in them. Solutions to this problem have applications to the scalable generation of combinatorial structures, as well as sampling in several statistical-relational models such as Markov logic networks and probabilistic logic programs. In this paper, we identify certain classes of sentences that are domain-liftable under sampling, in the sense that they admit a sampling algorithm that runs in time polynomial in n. In particular, we prove that every sentence of the form ∀x∀y: ?(x, y) for some quantifier-free formula ?(x,y) is domain-liftable under sampling. We then further show that this result continues to hold in the presence of one or more cardinality constraints as well as a single tree axiom constraint.

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/GJ20-19104Y" target="_blank" >GJ20-19104Y: Generativní relační modely</a><br>

Návaznosti

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

Rok uplatnění

2022

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

Proceedings of the 36th AAAI Conference on Artificial Intelligence

ISBN

978-1-57735-876-3

ISSN

2159-5399

e-ISSN

2374-3468

Počet stran výsledku

10

Strana od-do

10070-10079

Název nakladatele

AAAI Press

Místo vydání

Menlo Park

Místo konání akce

- virtual

Datum konání akce

22. 2. 2022

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

WRD - Celosvětová akce

Kód UT WoS článku

000893639103010