A new probabilistic constraint logic programming language based on a generalised distribution semantics

Steffen Michels*, Arjen Hommersom, Peter J. F. Lucas, Marina Velikova

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Probabilistic logics combine the expressive power of logic with the ability to reason with uncertainty. Several probabilistic logic languages have been proposed in the past, each of them with their own features. We focus on a class of probabilistic logic based on Sato's distribution semantics, which extends logic programming with probability distributions on binary random variables and guarantees a unique probability distribution. For many applications binary random variables are, however, not sufficient and one requires random variables with arbitrary ranges, e.g. real numbers. We tackle this problem by developing a generalised distribution semantics for a new probabilistic constraint logic programming language. In order to perform exact inference, imprecise probabilities are taken as a starting point, i.e. we deal with sets of probability distributions rather than a single one. It is shown that given any continuous distribution, conditional probabilities of events can be approximated arbitrarily close to the true probability. Furthermore, for this setting an inference algorithm that is a generalisation of weighted model counting is developed, making use of SMT solvers. We show that inference has similar complexity properties as precise probabilistic inference, unlike most imprecise methods for which inference is more complex. We also experimentally confirm that our algorithm is able to exploit local structure, such as determinism, which further reduces the computational complexity. (C) 2015 Elsevier B.V. All rights reserved.

Original languageEnglish
Pages (from-to)1-44
Number of pages44
JournalArtificial Intelligence
Volume228
Early online date4 Jul 2015
DOIs
Publication statusPublished - Nov 2015

Keywords

  • Probabilistic logic programming
  • Imprecise probabilities
  • Continuous probability distributions
  • Exact probabilistic inference
  • INFERENCE
  • NETWORKS
  • PROPAGATION
  • COMPLEXITY
  • VARIABLES
  • SYSTEM

Cite this