Metadata only
Date
2022-06-30Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
Given a first-order sentence Gamma and a domain size n, how can one sample a model of Gamma 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 for all x for all y : psi(x, y) for some quantifier-free formula psi(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. Show more
Publication status
publishedExternal links
Journal / series
Proceedings of the AAAI Conference on Artificial IntelligenceVolume
Pages / Article No.
Publisher
AAAIEvent
Subject
Reasoning Under Uncertainty (RU)More
Show all metadata
ETH Bibliography
yes
Altmetrics