Probabilistic Finite Domains: A Brief Overview

We propose a new way of extending Logic Programming (LP) for reasoning with uncertainty. Probabilistic finite domains (Pfd) capitalise on ideas introduced by Constraint LP, on how to extend the reasoning capabilities of the LP engine. Unlike other approaches to the field, Pfd syntax can be intuitively related to the axioms defining Probability and to the underlying concepts of Probability Theory, (PT) such as sample space, events, and probability function.

Probabilistic variables are core computational units and have two parts. Firstly, a finite domain, which at each stage holds the collection of possible values that can be assigned to the variable, and secondly a probabilistic function that can be used to assign probabilities to the elements of the domain. The two constituents are kept in isolation from each other. There are two benefits in such an approach. Firstly, that propagation techniques from finite domains research are retained, since a domain’s representation is not altered. Thus, a probabilistic variable continues to behave as a finite domain variable. Secondly, that the probabilistic function captures the probabilistic behaviour of the variable in a manner which is, to a large extent, independent of the particular domain values. The notion of events as used in PT can be captured by LP predicates containing probabilistic variables and the derives operator (⊢) as defined in LP. Pfd stores hold conditional constraints which are a computationally useful restriction of conditional probability from PT. Conditional constraints are defined by D ₁: π ₁⊕...⊕D _n: π _n | Q ₁ ∧...∧ Q_m where, D_i and Q_j are predicates and each π_i is a probability measure (0 ≤ π_i ≤ 1, 1 ≤ i ≤ n, 1 ≤ j ≤ m). The conjuction of Q _j’s qualifies probabilistic knowledge about D _i. In particular, the constraint is evidence that the probability of D _i in the qualified cases (i.e. when ⊢ Q ₁,..., Q _m) is equal to π _i. On the other hand a conditional provides no evidence for the cases where ⊬ Q ₁, ..., Q _m.

Pfd has been used to model a well known example, the Monty Hall problem, which is often used to caution about the counter-intuitive results when reasoning with probabilities. Analysis of the computations over this model, has shown that Pfd emulates extensional methods that are used in statistics.

The main benefits of our approach are (i) minimal changes of the core LP paradigm, and (ii) clear and intuitive way for arriving at probabilistic statements. Intuitiveness of probabilistic computations is facilitated by, (a) separation of the finite domain and the probability assigning function of a variable, and (b) using predicates to represent composite events.

Authors and Affiliations

1. Department of Computing, Imperial College, London, SW7 2BZ, UK

   Nicos Angelopoulos

Editors and Affiliations

1. Department of Computer Science and Software Engineering, University of Melbourne, 221 Bouverie St., Carlton, 3053, Australia

   Peter J. Stuckey

Reprints and permissions

© 2002 Springer-Verlag Berlin Heidelberg

Policies and ethics