Inference for a New Probabilistic Constraint Logic

1 Introduction

Probabilistic logics combine the power of logic to represent knowledge with the ability to deal with uncertainty. In earlier research (e.g. [Bacchus, 1990]), this concerned logics with formulas such as P > 0.5ϕ, meaning that the 'agent believes ϕ with probability strictly greater than 0.5'. While there has been significant work in this area, these types of logics are typically both computationally and conceptually complex. In recent years, powerful probabilistic logics have been developed that allow for efficient inference and learning (cf. [Getoor and Taskar, 2007] for an overview). Many of these languages are based on Sato's distribution semantics [Sato, 1995], which extends a joint probability distribution over the facts of a logic program to a distribution over the set of possible least models of the entire program. Examples of such languages are ProbLog [Raedt et al., 2007], PRISM [Sato and Kameya, 1997], ICL [Poole, 2008], and CP-logic [Vennekens et al., 2009].

∗This publication was supported by the Dutch national program COMMIT. The research work was carried out as part of the Metis project under the responsibility of the Embedded Systems Institute with Thales Nederland B.V. as the carrying industrial partner. We omitted all proofs in this paper due to lack of space. An extended version including the proofs will be made available.

Significant research has also been done to extend logic programming (LP) with constraints, which lead to constraint logic programming (CLP) [Jaffar and Lassez, 1987]. The general approach supports various constraint theories. For example, in CLP(FD) [Codognet and Diaz, 1996] constraints involving variables with a finite domain can be handled. Another example is CLP(R) [Jaffar et al., 1992], which introduces constraints on real numbers inside LP.

In this paper, we combine probabilistic with constraint logic programming, called probabilistic constraint logic programming (PCLP), by associating a set of constraints with a probability distribution. The idea of modeling probabilistic information using constraints was previously explored in CLP(BN) [Costa and Cussens, 2003] and an identically named language [Reizler, 1998], which both use the CLP mechanism to model a joint probability distribution on the models of a logic program. The key difference is that instead of modeling a single joint distribution, we use PCLP to define constraints on a distribution. Thus, PCLP supports imprecise probabilities, meaning that some of the probabilistic information is unknown, e.g., as in some of the earlier probabilistic logics, it is possible to specify that the probability of a fact being true is larger than 0.5.

This way of defining distributions allows PCLP to deal with continuous distributions in a powerful way. Although Hybrid ProbLog [Gutmann et al., 2010] extends ProbLog with continuously distributed facts, the logical language involving these distributions is heavily restricted, e.g., it is not possible to compare two random variables. Another approach is the work on distributional clauses, which extends the expressiveness of ProbLog further [Gutmann et al., 2011]. Although this language supports arbitrary parameterized distributions, inference is only feasible by sampling. In comparison, continuous distributions can be modeled in PCLP by providing probabilistic information about constraints in CLP(R), consistent with the actual distribution. The lower and upper bound of marginal probabilities can be derived using exact inference. The bounds can serve as approximation with desired precision, which depends on the amount of probabilistic information encoded by the constraints.

This paper is organized as follows. In the following section, PCLP is motivated by means of an example. In Section 3, we will formally introduce the syntax and semantics of PCLP. Section 4 introduces an inference procedure for PCLP, which we apply in Section 5 to the example. Finally, in Section 6, the achievements are summarized and we point out directions for future research.

2 Motivating Example

To illustrate the expressive power of the new language, we present an example on the likelihood consumers will buy a certain kind of fruit, based on [Binder et al., 1997]. Since we have a first-order formalism, this generalizes easily to an arbitrary number of kinds (in the example: apples and bananas).

Yield of fruit is clearly relevant for the price. We model the yield of fruit with normally distributed random variables X ∼ N (µ, σ2 ):

The price is also influenced by government support:

Support(apple) ∼ {0.3: yes, 0.7: no}

Support(banana) ∼ {0.5: yes, 0.5: no}

The basic price linearly depends on the yield:

basic price(apple,250 - 0.007 · Yield(apple)) basic price(banana,200 - 0.006 · Yield(banana))

In case the price is supported it is raised by a fixed amount:

price(Fruit , BPrice + 50) ←

basic price(Fruit , BPrice), Support(Fruit) = yes

price(Fruit , BPrice) ←

basic price(Fruit , BPrice), Support(Fruit) = no

At which maximum price customers still buy a certain fruit is modeled by a gamma distribution:

Max price(apple) ∼ Γ(10.0, 18.0) Max price(banana) ∼ Γ(12.0, 10.0)

Thus, a customer is willing to buy in case the price is equal to or is less than the maximum price, which can be expressed by the following first-order rule:

buy(Fruit ) ← price(Fruit , P ), P ≤ Max price(Fruit ) Based on these constraints, the following probability approx-

imations can be determined:

The actual probabilities are guaranteed to be within the computed maximum error determined by the constraints and used approximation scheme.

Besides using the language for approximations, it can also express imprecise probabilities. For instance, to express that the probability that the price of apples is supported is in the interval [0.3, 1], we can write:

Support(apple) ∼ {0.3: yes, 0.7: yes ∨ no}

The bounds on the probability that the consumer buys apples is now 0.222 ≤ P(buy(apple)) ≤ 0.493. These bounds represent both the underspecified distribution and the error in approximating the continuous distributions.

3 The PCLP Language

The probabilistic constraint logic program (PCLP) language L consists of a constraint language C, the language of rules R, and definitions of random variables V. Below, we assume the language to be fixed. Then, a PCLP T (a "theory") consists of random variable definitions VT , and a logical theory LT = CT ∪ RT , where CT is a constraint theory, related to the used constraints domains as discussed hereafter, and RT is a set of acyclic rules.

3.1 Syntax

Constraint Domains

In this paper, we use a language of constraints that is closed under conjunction and negation. We explore two constraint domains which are commonly used in constraint logic programming - discrete values (DV) and the real numbers (R) - to model constraints on discrete and continuous random variables, respectively.

In the constraint domain DV random variables take discrete values. The constraint language consists of equality (=) and inequality (̸=) as basic building blocks. In the example we used constants such as yes in the definitions as abbreviation for the constraint that a random variable equals that constant. The constraint domain is very similar to the finite constraint domain CLP(FD) [Hentenryck, 1989], with the difference that we do not require the domain to be defined explicitly. The domain of all variables is implicitly given by all atoms occurring in the program, but one can exclude values by not assigning any probability mass to them. Using DV, one can represent, for instance, Bayesian networks [Pearl, 1988], but also first-order formalisms such as CP-logic [Vennekens et al., 2009].

The R domain is basically the same as in CLP(R) [Jaffar et al., 1992]. Variables represent real numbers and constraints consist of linear equalities and inequalities using predicates such as {=, ̸=,<,>,≤,≥} and functions {+,-, ∗}. This theory can be used to approximate arbitrary continuous distributions for which the cumulative distribution function is known by associating probabilities to intervals of the domain of the distribution, defining a set of distributions including the actually intended one. To do that one can divide the probability space of a single variable in n intervals (l1, u1), · · · , (ln, un) and constrain its distribution as X ∼ {P(l1 < X < u1): l1 < X < u1, · · · , P(ln < X < un): ln < X < un}. The number of intervals determine the precision, i.e., the gap between the probability bounds one can compute.

Rule Language

Rules are (implicitly universally quantified) expressions of the form: h ← l1, . . . , ln where h is called the head and the conjunction l1, . . . , ln is called the body of the rule. The head h is an atom, i.e., an expression of the form p(t1, . . . , tm) with p a predicate, and l1, . . . , ln are either atoms or constraints (elements of C). Constants are denoted by lower-case letters (a, b, . . . ), while variables start with upper-case letters (e.g. X, Y , . . . ). As mentioned above, RT is defined as the set of rules of the PCLP theory T .

Random Variable Definitions

Each random variable definition is of the form: V (t1, . . . , tn) ∼ {p1 : c1, . . . , pm: cm} where each ti is a term, i.e., a constant or variable, ci ∈ C is a constraint, pi ∈ [0, 1] are probabilities such that ∑i pi ≤ 1. This makes sure that random variables are defined consistently, together with the requirement that left-hand sides of definitions are non-unifiable. Given a substitution θ that grounds {t1, . . . , tn}, this definition yields constraints on a random variable V (t1, . . . , tn)θ. The pair pi : ci means that the prior probability that the value of this random variable satisfies the constraint ci is at least pi. We define the realization of a random variable, which formally captures this notion.

Definition 1. Let V be a random variable in a PCLP theory, where V ∼ {p1 : c1, . . . , pm : cm}. Then, a random variable X is called the realization of V if for all ci, 1 ≤ i ≤ m, it holds that

where c[V/X] is the constraint c with V substituted by X.

Constraints are not necessarily mutually exclusive; e.g., it is possible to express that 20% of the balls in an urn are definitely blue and 80% are either blue or yellow. However, to ensure that all the probability mass can be assigned to the domain of random variable V we require that the constraints are satisfiable. To specify the constraints on random variables, each constraint domain contains at least the associated random variables, interpreted logically as constants. To make sure random variables are defined independently, a constant in a constraint of the definition of V is either V itself or it does not unify with any variable in V. For example, we may include the constraint Support(apple) = yes in the definition of Support(apple), but not refer to Support(banana).

3.2 Semantics

As the theory T specifies constraints on random variables, typically there is a class of distributions that satisfies the constraints. In fact, for a given ground atom q, the theory specifies an interval [Pmin(q), Pmax(q)] such that Pmin(q) ≤ P (q) ≤ Pmax(q).

Given a finite set of possible grounding substitutions {θ1, . . . , θn} for each variable V (t1, . . . , tm) from V, we first define a probability space over a choice function ϕ which selects for each element of V (t1, . . . , tm)θi either one of its probability-constraint pair p: cθi or it maps to (1 - ∑(pi:ci)∈V pi : true) which represents the remaining probability mass. We denote the set of grounded variables by VT , which represents all the random variables in T . A particular choice is then the set:

As each random variable is independent, the probability Pϕ attached to a choice ϕ is the product of all selected probabilities:

Each choice can be thought of as a possible world, although this world is described by constraints. In this world, it is possible that q is true, although this might depend on the actual values of the random variables involved. We say that s ∈ C is a solution for q given a particular choice ϕ, denoted by solution(s, q, ϕ) iff

Given a particular choice function ϕ, there are three possibilities: (i) the query is necessarily true in ϕ, i.e., solution(true, q, ϕ) holds, denoted by follows(q, ϕ), (ii) there are no solutions or (iii) there are some constraints which imply the query, i.e., ∃s: solution(s, q, ϕ), denoted by possible(q, ϕ).

Example 1. Consider the following program:

We denote the choice selecting the ith element in the definition of X and the jth element in the definition of Y as ϕij. Those choices can be represented in a two-dimensional probability space as depicted in Figure 1. Each rectangle represents an (independent) choice of a single constraint from the distribution of two random variables; the query q is represented by the area above the line. We have follows(q, ϕ11) since for the choice ϕ11 it always holds Y < 1.25, 0.25 ∗ X+Y < 1.375. In the light grey areas, there is a possible solution, i.e., possible(q, ϕij). For instance for the choice ϕ21, Y can be 0 and therefore less than 0.75. However, not all possible values consistent with the choice are a solution: Y can be 1 which is greater than 0.75, and 0.25 ∗ X + Y could be up to 1.5, which is larger than 1.375. Hence, it is possible to pick some additional consistent constraints on X and Y such that q does not follow, i.e., follows(q, ϕ21) does not hold.

We can use these notions to define the lower bound of the probability distribution, which is the probability mass of choices for which the query is certainly true. Formally, we say the lower bound of the probability for q is the sum of the probabilities of choices which imply q, i.e.,

For the program given in Example 1 the lower bound is Pϕ11 = 0.01.

In contrast, in the upper bound we also include those choices which, only together with a particular solution, imply q, i.e.,

For the program given in Example 1 the upper bounds is Pϕ11 + Pϕ21 + Pϕ31 + Pϕ12 + Pϕ22 = 0.22.

We now introduce the concept of solution constraints to relate those intuitive definitions of the lower and upper bound to the possible realizations of all variables in a program.

Definition 2. Let a solution constraint SC(q) be a constraint such that COMP(RT ) ∪CT |= SC(q) ↔ q, where COMP(RT ) is Clark's completion [Clark, 1978] of RT , i.e., rules are interpreted as if and only if statements, so that q is completely characterized by SC(q).

Given the solution constraint, we can now formally define the probability of q given a realization of the random variables.

Definition 3. Given the solution constraint SC(q) having random variables V = {V1, . . . , Vn} and a set of independent random variables X = {X1, . . . ,Xn} such that Xi is a realization of Vi, the probability of q, P(q | X), is defined as P(SC(q)[V1/X1, . . . , Vn/Xn]), denoted by P (SC(q)[V/X]).

The definition of bounds actually corresponds to the probability given the realizations for which the probability is minimal and maximal.

Theorem 1. Given the solution constraint SC(q) and independent random variables X = {X1, . . . , Xn} such that Xi is a realization of Vi, where V = {V1, . . . , Vn} is the set of random variables which are in SC(q), it holds that Pmin(q) and Pmax(q) are the most tight bounds for P(q | X), i.e.:

In case the constraints only relate to a single value of the random variables, then the bounds collapse, as then follows(q, ϕ) ⇔ possible(q, ϕ). In this case, there is a simple mapping from this logic to, e.g., ProbLog.

Finally, we define negations and conjunctions of queries in a similar fashion, i.e., a conjunction of literals q is defined by the constraint SC(q). Note that it follows that Pmax(¬q) = 1 - Pmin(q) and vice versa.

We finally define what conditional probabilities mean in this setting. For each realization of VT conditional probabilities are defined in the obvious way. We then define the minimum and maximum conditional probability of a program as the probability given realizations for which this probability is minimal and maximal.

Definition 4. We define the probability bounds given evidence as:

Example 2. Recall the program introduced in Example 1 and consider an additional rule e ← X < 1.5. Suppose we would like to compute Pmax(q | e). To illustrate this probability, consider Figure 2, which is the probability space of Figure 1 with an additional constraint that implies the evidence e. Intuitively, to determine Pmax(q | e) we need to exclude choices inconsistent with e from the probability space and compute the probability of q in the remaining space. The choices ϕ31, ϕ32 and ϕ33 are certainly inconsistent with e and are therefore excluded. The choices ϕ21, ϕ22 and ϕ23 are possibly inconsistent with e. Since we want to maximize P(q | e), removing ϕ23 increases the resulting probability, because for all possible X it could only contribute to P(e | X) but not to P(q | X); hence, ϕ23 is also excluded. In contrast, removing ϕ21 and ϕ22 would decrease the maximal probability of q. In summary, we compute Pmax(q | e) = Pϕ11 +Pϕ21 +Pϕ12 +Pϕ22 Pϕ11 +Pϕ21 +Pϕ12 +Pϕ22 +Pϕ13 ≈ 0.73. Note that even though Pϕ23 would contribute to compute the upper bound of the evidence alone, it does not contribute to the partition function of Pmax(q | e).

To compute conditional probabilities in general we have the following proposition that relates the joint probability to the conditional probability.

Proposition 1. The probability bounds of a query q given evidence e, as defined by Definition 4, can be computed as follows:

4 Inference

The inference problem is solved in two steps. We first apply resolution and derive a proof constraint PC(q) for a query q, which can be seen as the operational equivalent of the solution constraint. Using this, we compute a probability for q by summing over all choices. The advantage of this two-step approach is that we only need to apply resolution once. After this, we discuss strategies to reduce the number of choices we need to sum over.

4.1 PCLP as a satisfiability problem

The collection of a proof constraint is similar to how it is done in constraint logic programming [Jaffar et al., 1998] and ProbLog [Raedt et al., 2007]. In brief, the idea is to apply SLD resolution on the query q, in which the constraints encountered are collected. In the end, for each proof i, we obtain a conjunction of constraints PCi(q) that proves q, i.e., RT ∪{PCi(q)} ⊢ q. Then, the complete proof constraint for q is simply the disjunction of constraints:

Since RT is acyclic, there are a finite number of these proofs, though this could be generalized to cyclic theories [Mantadelis and Janssens, 2010].

Example 3. Consider again the program from Example 1. The proof constraint for query q is:

Using PC(q) we compute the bounds on the probability distribution by applying a satisfiability solver. We start with the probability of a single positive query atom q, which can be computed by checking the satisfiability of the proof constraint with possible choices. We denote sat (C) for CT ∪{C} ̸⊢ ⊥.

Lemma 1. For all PCLP theories T , given a positive query q, it holds that:

From this lemma, the bounds on negations and conjunctions of queries can be easily derived.

Corollary 1.

Example 4. To compute Pmin(q) we make use of the fact that Pmin(q) = 1 - Pmax(¬q) and Corollary 1. It holds that:

For all ϕ it holds that sat(¬PC(q) ∧ CHϕ), except for ϕ11. Therefore, Pmin(q) = 1 - (1 - Pϕ11 ) = 0.01.

4.2 Exact inference for PCLP

Because of the duality of Pmin and Pmax, we will focus here on computing maximum probabilities. Clearly, by naively applying Lemma 1, it is necessary to consider all possible choices, which is exponential in the number of random variables. However, it is possible that a partial choice CH′ϕ ⊂ CHϕ is not consistent with or implies the proof constraint PC(q), which can be exploited during inference. To illustrate,

Algorithm 1: MAXPROB

• Input: proof constraint PC(q) and partial choice CHϕ Result: Pmax(q | CHϕ) 1 if ¬SAT( PC(q) ∧CHϕ) then return 0 2 if ¬SAT(¬PC(q) ∧CHϕ) then return 1 3 if there is some random variable V in PC(q), for which there is no choice in CHϕ then 4 return ∑ ϕ(V )=(p : c)p · MAXPROB(PC(q), CHϕ ∪ {c}) 5 else return 1

Algorithm 2: MAXPROBDECOMP

Input: proof constraint PC(q) Result: Pmax(q) 1 simplify PC(q) 2 if exists independent subconstraint C in PC(q) then 3 p = MAXPROBDECOMP(C) L| C = MAXPROBDECOMP(PC(q)[C ↦→ true]) L|¬C = MAXPROBDECOMP(PC(q)[C ↦→ false]) return p · L|C + (1 - p) · L|¬C 4 else return MAXPROB(PC(q),∅)

let ΦV be the possible choice functions for the random variable V ∈ VT only. Then, for a proof constraint such as X > 0∧X+Y > 0, we naively examine |ΦX||ΦY| choices. However, assuming only half of the choices for X are consistent with X > 0, we can reduce this to only |ΦX|/2+|ΦX||ΦY|/2 examinations, if we consider the choices for X first. This effectively prunes a part of the choice space.

A basic algorithm that exploits this idea is presented in Algorithm 1. Pruning takes place at lines 1 and 2. The efficiency of the algorithm depends on the order variables are selected on line 4. As MAXPROB terminates in case an inconsistency can be found, a simple heuristic is to order random variables such that Vi < Vj if Vi occurs in an (in)equality constraint with less variables on average than Vj. For example, in the constraint X > 0 ∧ X + Y > 0 we first select choices for X as some of these choices might make the whole constraint inconsistent.

In the spirit of the well-known RelSAT algorithm [Bayardo and Pehoushek, 2000] for weighted model counting, we can also observe that in many cases the problem can be decomposed into subconstraints which do not share any random variables. For example, consider the proof constraint X > 0 ∧ Y > 0. In this case Pmax(X > 0 ∧ Y > 0) = Pmax(X > 0) · Pmax(Y > 0) which can be computed by examining |ΦX| + |ΦY| choices only. Also for more complex queries, independent subconstraints can be found, e.g.,

which requires examining |Φy|+2|Φx| choices. An algorithm that uses this idea is presented in Algorithm 2. Because of the substitutions, we initially perform some basic simplifications, e.g., in the previous example (X > 0 ∧ false) ∨ X < -3 is simplified to X < -3.

Theorem 2. Given a query atom q and its proof constraint PC(q), then

i.e., MAXPROBDECOMP computes the upper bound of q.

5 Experiments

In this section, we provide some insight into the behavior of the proposed algorithm. In particular, we investigate the proposed heuristics and provide some experiments with respect to scalability. In the implementation we make use of the satisfiability modulo theories (SMT) solver YICES [Dutertre and Moura, 2006], which supports linear arithmetic.

5.1 Heuristics

Continuing the example of Section 2, we will first present some experiments in the computation of P(buy(apple) ∨ buy(banana) | Max price(apple) < 90). We compare four algorithms: (i) the naive algorithm where we sum over all choices, (ii) the pruning algorithm (Algorithm 1), (iii) an algorithm that includes the decomposition of constraints (Algorithm 1), but without pruning, and (iv) the complete algorithm proposed in this paper.

Assuming we give a point prediction as the average of {Pmin(q), Pmin(q)} then the maximum error we make is (Pmax(q) - Pmin(q))/2. We varied the number of intervals into which the continuous variables were discretized and plotted the relationship between the inference time and the maximum error (cf. Figure 3a).

The result shows that the proposed heuristics improve inference time significantly. In this case, identifying the independent constraints has more effect on the inference time than the pruning heuristic, as several independences could be exploited. However, we also see that the pruning of choices reduces inference time, although the effect was limited in this case: only the choices inconsistent withMax price(apple) < 90 were pruned.

5.2 Scalability

To explore how scalable our inference algorithm is we add n kinds of fruit to the program, for simplicity with the same characteristics as banana and determine approximations for P(buy(fruit1) ∨ · · · ∨ buy(fruitn)). The result is shown in Figure 3b where we show again the relationship between inference time and maximum error.

The result shows an interesting non-monotonic behavior: while for small n, the maximum error is higher if there are more fruits, the reverse holds for large n, e.g., if n = 20, then the error is smaller than for n = 10 given the same inference time. The first behavior occurs because the maximum error increases with the number of fruits, given the same total number of choices (see Figure 3c). So without any heuristics, the maximum error is always higher with larger n given the same inference time. However, by using the heuristics the inference time for the choice space is sub-exponential, in particular because subconstraints are independent. Therefore, the size of the choice space starts to dominate and the error can even decrease given the same inference time.

6 Conclusions &FutureWork

We introduced a new probabilistic constraint logic programs framework that combines CLP with probabilistic inference. Although there are already several approaches where probabilistic information is combined with logic programming, many approaches are either restricted in their capabilities to representation (e.g., only to discrete distributions) or to inference (e.g., using sampling). PCLP overcomes these issues by using a constraint representation where exact inference is feasible. In general, the language allows for specifying partially unknown probability distributions.

In this paper, we also introduced an inference algorithm exploiting state-of-the-art SMT solvers, proved its correctness with respect to the semantics, introduced several heuristics, and experimentally evaluated the implementation of the inference algorithm. We obtained encouraging results indicating that inference in our language is feasible for solving challenging problems.

In future research, we aim to improve the inference further by lifting (in [Gogate and Domingos, 2011] the closely related RelSAT algorithm is lifted) and dynamically discretizing the distribution of continuous random variables [Neil et al., 2007]. Finally, we aim to develop learning methods for this new language.