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

@article{f00eeeef4df8419ba858587a8774d45d,
title = "A new probabilistic constraint logic programming language based on a generalised distribution semantics",
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.",
keywords = "Probabilistic logic programming, Imprecise probabilities, Continuous probability distributions, Exact probabilistic inference, INFERENCE, NETWORKS, PROPAGATION, COMPLEXITY, VARIABLES, SYSTEM",
author = "Steffen Michels and Arjen Hommersom and Lucas, {Peter J. F.} and Marina Velikova",
year = "2015",
month = "11",
doi = "10.1016/j.artint.2015.06.008",
language = "English",
volume = "228",
pages = "1--44",
journal = "Artificial Intelligence",
issn = "0004-3702",
publisher = "ELSEVIER SCIENCE BV",

}

A new probabilistic constraint logic programming language based on a generalised distribution semantics. / Michels, Steffen; Hommersom, Arjen; Lucas, Peter J. F.; Velikova, Marina.

In: Artificial Intelligence, Vol. 228, 11.2015, p. 1-44.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Michels, Steffen

AU - Hommersom, Arjen

AU - Lucas, Peter J. F.

AU - Velikova, Marina

PY - 2015/11

Y1 - 2015/11

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

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

KW - Probabilistic logic programming

KW - Imprecise probabilities

KW - Continuous probability distributions

KW - Exact probabilistic inference

KW - INFERENCE

KW - NETWORKS

KW - PROPAGATION

KW - COMPLEXITY

KW - VARIABLES

KW - SYSTEM

U2 - 10.1016/j.artint.2015.06.008

DO - 10.1016/j.artint.2015.06.008

M3 - Article

VL - 228

SP - 1

EP - 44

JO - Artificial Intelligence

JF - Artificial Intelligence

SN - 0004-3702

ER -