Generalising the Interaction Rules in Probabilistic Logic

1 Introduction

The last two decades has seen the emergence of many different probabilistic logics, such as Markov logic [Richardson and Domingos, 2006], probabilistic Horn clause logic [Poole, 1993], and ProbLog [Kimmig et al., 2010], that use logical languages to specify, and sometimes reason, with probability distributions. Probabilistic logics are based on first-order logic, and they share the advantage of first-order logic in comparison to propositional logic in that they can be looked upon as more expressive knowledge-representation languages with considerable modelling power, which for probabilistic logics is extended to areas where uncertainty is encountered.

However, despite their generality, all of these languages are based on different semantic principles. Some of the principles, while taken for granted, should actually be considered as part of the design choices. When different choices would have been made, a different probabilistic logic would have emerged because of the close interaction between the logical aspects and probabilistic aspects of a probabilistic logic.

In the research described in the present paper, we introduce the theoretical foundation of a whole class of probabilistic logics, starting from a very general and unrestrictive probabilistic logic, the above-mentioned ProbLog, and show that it is possible to obtain a new, but related, probabilistic logic by changing the way probabilistic evidence is combined. We do this by redesigning the probabilistic and logical basis of the probabilistic logic hand in hand such that the resulting logic supports this double, logical and probabilistic, view. The resulting class of probabilistic logics has the advantage that it can be used to gear a logic to the problem at hand.

In the next section, we first review the basics of ProbLog, which is followed by the development of the main methods used in generalising probabilistic Boolean interaction, and, finally, default logic is briefly discussed. We will use probabilistic Boolean interaction as a sound and generic, algebraic way to combine uncertain evidence, whereas default logic will be used as our language to implement the interaction operators, again reflecting this double perspective on the probabilistic logic. The new probabilistic logical framework is described in Section 3 and compared to other approaches in Section 4. The achievements of this research are reflected upon in Section 5.

2 Preliminaries

In this section, probabilistic logic and a method for combining probabilistic evidence is described. We also briefly review concepts from default logic.

2.1 Probabilistic Logic: Syntax and Semantics

There are many different proposals in the scientific literature for probabilistic logics. In this paper we focus on the class of logics where probabilistic reasoning and logical reasoning go hand in hand. ProbLog is a typical example of such a language [Kimmig et al., 2010]. ProbLog was specifically designed as a basic language to which other probabilistic logical languages can be compiled [De Raedt et al., 2008]; thus, the results from this paper apply to a whole range of languages.

It is assumed that the reader is familiar with logic programming terminology, where a program consists of Horn clauses of the form

where B, Ai are atoms of the form p(t1, . . . , tm), with tk terms. If n = 0, then the Horn clause is called a fact, if B is ⊥ (false), then the clause is called a query; otherwise, the clause is called a rule.

The ProbLog language extends logic programming by allowing that probabilities are attached to facts, then called labelled facts. Let F denote the set of labelled facts, then each element of F has the form

also abbreviated to pf , where pf = P(f) ∈ [0, 1] has the meaning of a probability, and f conforms to the syntax of an atom. The meaning of an atom in terms of probability theory is that of a set of random variables. For example,

specifies the collection of random variables parent(X), for each ground instance of parent(X), obtained by applying substitutions Θ to parent(X). For example, parent(X)θ = parent(john) with θ = {john/X}, where θ ∈ Θ. The resulting ground atoms are called logical facts.

In addition to labelled facts, a ProbLog program consists of rules, constituting the background knowledge B of the program. Now, let T = F ∪ B be a ProbLog program and let Θf be the set of all possible substitutions associated with the logical fact f. Then, LT is defined as the subset-maximal set of logical facts that can be added to B applying the set of substitutions Θf to the fact f, for each f ∈ F. The ProbLog program then defines a joint probability distribution on the logical facts LT . Let L ⊆ LT , then:

Let q now be any query to the ProbLog program, then it holds that

where

and '⊨' indicates logical entailment. Each L with P(q | L) = 1 is called an explanation of q.

The semantics of ProbLog is called the distribution semantics; it has been borrowed from PRISM [Sato, 1995]. Basically, in the distribution semantics all facts are assumed to be mutually independent. However, this does not imply that it is impossible to encode probabilistic dependences: all dependences are defined at the logical level. This allows defining any joint probability distribution. The distribution semantics also has particular consequences for obtaining probabilistic interactions between facts, as illustrated by the following example.

Example 1. Consider the following (trivial) ProbLog program T that represents some causal, medical knowledge:

0.7 :: flu.

0.2 :: pneumonia.

fever ← flu.

fever ← pneumonia.

In this program flu and pneumonia are two independent random variables according to the distribution semantics. We now wish to compute the probability PT (fever). Note that fever can be explained from either flu, pneumonia, or both flu and pneumonia. Thus, according to Equation (1) we get:

As is well known, this probabilistic result is identical to what would have been obtained by one of the most popular ways to model the interaction of (conditionally) independent events: the so-called noisy-OR [Pearl, 1988]. With the noisy-OR one models an uncertain, disjunctive interaction between events.

As the noisy-OR is based on logical disjunction, just one of the 16 binary Boolean operators, one can imagine that there might be other, equally sound, ways to combine probabilistic evidence. However, in order to be able to combine such evidence, one needs an algebraic method to combine such information. A general, algebraic way to combine probabilistic information is available from basic probability theory although it is rarely used to model Boolean interaction. In the following, we briefly review the necessary basics from probability theory, with convolution as a special case, and then investigate how ideas from probabilistic logic, Boolean interaction and default logic can be merged to obtain a more expressive probabilistic logic, which we call probabilistic interaction logic, or ProbIL for short.

2.2 Probabilistic Boolean Interaction

In the following, a probability mass function of a random variable X is referred to by fX; P denotes the associated probability distribution. A classical result from probability theory that is useful when studying sums of variables is the following well-known theorem (cf. [Grimmett and Stirzaker, 2001]).

Theorem 1. Let f be a joint probability mass function of the random variables X and Y , such that X + Y = z. Then it holds that P (X + Y = z) = fX+Y (z) = ∑x f (x, z - x).

If X and Y are independent, then, in addition, the following corollary holds.

Corollary 1. Let X and Y be two independent random variables, then it holds that

The probability mass function fX+Y is in that case called the convolution of fX and fY , and it is commonly denoted as fX+Y = fX ∗fY . The convolution theorem is very useful, as sums of independent random variables occur very frequently in probability theory and statistics. It can also be applied recursively, i.e.,

as follows from the recursive application of Equation (2).

Theorem 1 does not only hold for the addition of two random variables, but also for Boolean functions of random variables. However, in contrast to the field of real numbers where a value of a random variable Y is uniquely determined by a real number x and z through Y = z - x, in Boolean algebra values of Boolean variables only constrain the values of other Boolean variables. These constraints may yield a set of values, rather than a single value, which is still compatible with the theorem. In the following, we use the notation b(i, J) = q for such constraints, where the Boolean values i and q constrain J to particular values. For example, for (i ∨ J) = q, where i, q stand for I = 1 (I has the value 'true') and Q = 1 (Q has the value 'true'), it holds that J ∈ {0, 1}. Thus, f(i, (i ∨ J) = q) is an abbreviation for f(i, j) + f(i, ¬j). The theorem can then be re-expressed as follows.

Theorem 2. Let f be a joint probability mass function of the random variables I and J such that b(I, J) = q, with b a Boolean function. Then, it holds that P(b(I, J) = q) = fb(I,J)(q) = ∑i f(i, b(i, J) = q).

Proof. The (I, J) space defined by b(I, J) = q can be decomposed as follows: ⋃i {I = i} ∩ {J = j | b(i, j) = q}, where the expression b(i, j) = q should be interpreted as a logical constraint on the Boolean values of the variable J. Since the individual sets {I = i} ∩ {J = j | b(i, j) = q} are mutually exclusive, the result follows.

The following corollary for convolution is obtained if I and J are independent.

Corollary 2. Let f be a joint probability mass function of independent random, Boolean variables I and J and let b be a Boolean function defined on I and J, then it holds that

Theorem 2 now appears to be the key insight to generalise ProbLog.

Example 2. Reconsider Example 1, and the Boolean relation L∨P = F , where L stands for 'flu,' P for 'pneumonia', and F for 'fever'. We use the same probability distributions as in Example 1: P(l) = 0.7 and P(p) = 0.2. By applying Theorem 2 the following results:

where the term fP (p) + fP (¬p) results from the logical constraint that l ∨ P = f, i.e., P ∈ {0, 1}.

Thus, the example demonstrates that the noisy-OR can be described quite naturally by convolution. See [Lucas and Hommersom, 2010] for details.

The correspondence between the two approaches is as follows. The Boolean function b corresponds to the deterministic probability distribution P(q | L) of Equation (1). As P(q | L) is defined in terms of logical entailment of qθ from B ∪ L, the question addressed in this paper is whether there are ways to replace logical entailment by a reasoning method that incorporates probabilistic Boolean interaction as a method to express interaction between heads of rules. Since Boolean interaction can be looked upon as an inference rule, a natural way to extend ProbLog is by replacing standard logic by default logic.

2.3 Default Logic

In default logic [Reiter, 1980] one adds special inference rules, called defaults, to ordinary first-order predicate logic. The defaults have the following form:

where 'prerequisite' is a condition that, if it is true, then 'consequent' can be derived, however, only when the resulting theory together with the assumptions described by the 'justifications' is consistent. The resulting theory is denoted as T = (D,W), where in this paper W stands for a set of facts and rules in Horn-clause logic as in ProbLog, and D are defaults. Inference in default logic is done by computing the extensions of the theory, using a fixed point operator. We will write (D,W) |∼ϕ if ϕ ∈ E, where E is a default extension of (D,W).

The next section will develop the probabilistic interaction logic, ProbIL, by using defaults to represent Boolean interaction, which, when combined with probabilities yields probabilistic Boolean interaction as developed in Section 2.2.

3 Probabilistic Interaction Logic

3.1 General Idea

As Example 1 illustrates, probabilistic languages as ProbLog implicitly combine probabilistic evidence using logical disjunction, which corresponds to the noisy-OR operator. This choice gives rise to a particular probabilistic behaviour, that may not always be justified. The resulting probability when using the noisy-OR is always larger than its components, i.e., the probabilistic behaviour is monotonically increasing: pq + p(1 - q) + (1 - p)q ≥ p, q. Thus, it is not possible to model that particular events, when taken together, cancel each other out. In contrast, non-monotonic logics such as default logic can be used to implement such reasoning.

The general idea of Probabilistic Interaction Logic (ProbIL) is to replace the background theory by a default logic theory. This logic has the same benefits as default logic, namely that we can specify problem-dependent default behaviour without sacrificing ordinary logical deduction. In the context of ProbIL, defaults model valid interactions dependent of the generic problem-solving method that needs to be expressed or of the actual problem at hand.

Formally, the probability P(q | L) is adapted as follows. We assume we have a background theory consisting of a set of defaults D and a set of standard logical rules B. Then we have:

i.e., the monotonic logical entailment |= has been replaced by the default logic entailment |∼.

Example 3. The popular example from non-monotonic logics "birds typically fly" is modelled by the default set D = { Bird(x) : Flies(x) Flies(x) } and we add the standard logic rule ex-

pressing that Penguins do not fly, i.e., B = {Penguin(x) → ¬Flies(x)}. Further, we might know that in a pet store 30% of the animals are birds, i.e., 0.3 :: Bird(x). To compute whether Tweety (T) flies, we compute, P(Flies(T)) = P(Flies(T) | Bird(T))P (Bird(T)) = 0.3.

This has the same representational benefit as default logic in comparison to standard logic, i.e., the example could also be formalised by the ProbLog rule:

However, if, as in the example, we do not know whether Tweety flies and we do not have a distribution for Tweety being a penguin, then P(Flies(T)) = 0. This illustrates the interplay between non-monotonic and probabilistic reasoning, which is not available in many existing probabilistic logics.

In the following we use this mechanism to study types of interactions that can be modelled and ways to represent the resulting probability mass explicitly by using probabilistic Boolean interaction, and by a convolution operator in case of independence.

3.2 Boolean Interactions

Consider the following ProbLog clauses: {a ← c, a ← e}. In order to model the interaction between the probabilistic evidence contributing to the probability of a, we need to specify a combination function for these clauses, i.e., we wish to interpret these clauses as a ← b(c, e), with b a Boolean function. As we have seen, in the case of ProbLog, b(c, e) is always equal to c ∨ e. Default logic, as an expressive logical formalism, is used here to reason about these Boolean interactions. The following proposition expresses that all possible interpretations of Boolean interactions can indeed be modelled in default logic.

Proposition 1. For all Boolean functions b and a set of atoms H,B1, . . . ,Bn there is a default logic theory D, which does not contain b, such that:

iff

To illustrate this, we list a number of common binary Boolean functions in Figure 1 with their associated default logic theory. Hence, for a given set of interactions, we may replace the relevant rules by the corresponding theory where the interactions are modelled by default rules.

Of course, the converse of Proposition 1 also holds: extensions of a default theory can be characterised using a Boolean function. In the following, we assume that we have a Boolean function to model the interaction.

Example 4. People having headache often use over-thecounter pain medication to obtain pain relief (r). However, scientific evidence indicates that headache can actually be triggered by the overuse of common pain killers. Suppose we have two pain killers k1 and k2 which in combination are ineffective against headache. Also assume that pain killer k1 thins the blood (t). Finally assume we have two probabilistic facts d1 and d2 that model the probabilistic decision of whether or not to take k1 and k2. We can formalise this using the following ProbLog theory:

As k1 and k2 undermine each other effect on r, we would like to include an XOR interaction function for r. Thus, the probabilistic rules should be interpreted as the default theory:

together with a purely logical theory:

We are interested in hypotheses L ⊆ {d1, d2} such that:

with Q ⊆ {r, t}. For r, the only explanations are {d1} and {d2}, but not {d1, d2}. For t, on the other hand, the explanations are {d1} and {d1, d2}. Hence, the only common explanation for r and t is {d1}.

3.3 Probabilistic Boolean Interaction

Default logic provides a reasoning mechanism for Boolean interactions. In this section, we explore the complementary probabilistic perspective, by generalising results presented in Section 2.2. As mentioned, Theorem 2 can be used as a basis for probabilistic interaction logic.

Theorem 3. Let Q be an atom that appears in the theory T by a single rule:

For the probability mass function fQ of Q holds:

Proof.

Example 5. Reconsider Example 4. As the explanations of r are {d1} and {d2}, we have:

Using the standard semantics of ProbLog, note that f(k1, ¬k2) = P (k1 ∧ ¬k2) = p1(1 - p2) and f(¬k1, k2) = (1 - p1)p2. By applying Theorem 3, we obtain

and the results correspond. However, if we had used the standard (noisy-OR) semantics of ProbLog, we would have obtained P ∗ (r) = P (OR(k1, k2) = r) = p1p2 + (1 - p1)p2 + p1(1 - p2), which is larger than or equal to P(r).

An assumption that is often made in probabilistic logics (e.g., [Poole, 1993]), is that explanations are mutually exclusive, i.e., P(Li ∨ Lj) = P(Li) + P(Lj), with Li and Lj explanations. Without this assumption, the probability of the disjunction is computed by finding an equivalent disjunction for Li ∨Lj where the disjuncts are mutually exclusive (called the disjoint-sum problem). Similarly, if we assume that bodies of a head, say Bi and Bj, are independent of each other, no disjoint-sum problem has to be solved as then it holds that P(Bi ∨ Bj) = P(Bi) + P(Bj) - P(Bi)P(Bj). This can be seen as a somewhat 'weaker' requirement, as this does not restrict the structure of logical theories, but only the probability distribution that is generated. In the case of independent bodies for a query, convolution can be exploited.

Corollary 3. Let Q be an atom that appears in theory T as a single rule:

where I and J independent. Then the probability mass function fQ of Q:

Example 6. Reconsider again Example 4. It is not difficult to see that f(k1) = p1 and f(k2) = p2. So, we may use the convolution as follows:

which yields again the same result as before. However, in this case the computation of f(k1) is independent of f(k2).

3.4 Representation

In case the independence assumption does not hold, a disjoint-sum problem has to be solved, e.g., using binary decision diagrams (BDDs) [Kimmig et al., 2010]. However, it cannot be determined beforehand when this problem has to be solved, so a representation of such independence can avoid the overhead of BDDs and improve the inference in practice.

Syntactically, we introduce a labelling ri of rules, and use this to denote a Boolean interaction between rules with the same head. For example:

In this specification b(r1, r2) expresses that

where b denotes convolution using Boolean operator b. This operator is useful for algebraic manipulation of models with complex interactions between formulae, as the algebraic properties of the Boolean operator b carry over to the b operator. Moreover, it directly simplifies inference as it prevents the overhead of solving the disjoint-sum problem for a. Finally, the representation is generic for both discrete models, continuous models, and mixtures of these [Lucas and Hommersom, 2010], so the results generalise to probabilistic logical models with continuous distributions, such as proposed in [Gutmann et al., 2010].

4 RelatedWork

It is well-known that default logic can be embedded in a logic programming language with negation as failure [Kakas, 1994]. A probabilistic variant of such a logic programming language with such negations is ICL [Poole, 1997]. Another approach is the language of P-log [Baral et al., 2009], which extends the Answer Set Programming (ASP) framework with probabilistic facts. Both approach are closely related to ProbIL in the sense that they both are probabilistic non-monotonic logics. The goal of this paper, however, is complementary as we are not focused on non-monotonic theories per se, but rather, theories with different types of interactions between bodies. In fact, it holds for both ICL and P-log that the interactions between bodies follow a noisy-OR interaction. In contrast, this paper has showed that interactions can be faithfully represented in a non-monotonic logic and can sometimes be decomposed using a type of convolution operator. ProbIL is used as a basic language to give insight to the former goal as it very intuitively can represent causes that cancel each other out. From a more practical point of view, other systems could be used to actually represent and compute these probabilities.

5 Conclusions

In this paper, we proposed a new mechanism for modelling interactions in probabilistic logics. As suggested in [Poole, 1990], abduction can be seen as formalism for explaining observations, whereas default logic is used to make predictions. While languages such as ProbLog use a non-monotonic approach (abduction) for explaining a possible query, predictions are completely monotonic. We have used default reasoning in this context of prediction as a method for modelling interactions between probabilistic facts.

Default reasoning is difficult in general; in its full generality, default abduction is intractable [Eiter et al., 1997]. Nonetheless, algorithms for solving this problem for propositional default theories have been developed that use efficient quantified Boolean formula solvers [Tompits, 2003]. Moreover, we have shown that for many classes of problems, the probabilistic interactions can be decomposed and effectively represented by a convolution operator. This may significantly improve the computational complexity of reasoning in a way similar to the use of causal independence models in Bayesian networks [Zhang and Poole, 1996]. Although we have not presented a practical implementation of ProbIL in this paper -ProbIL is rather acting as a general language for representing interactions - it could be implemented using some of the existing approaches in probabilistic logics based on logic programming. Actually developing such implementations is future research.

Important in this work is that we have incorporated different methods of reasoning into a flexible probabilistic logic, while still maintaining the overall design aim of providing logical and probabilistic reasoning hand in hand. We believe that this can be of help for modelling and reasoning about a wide range of actual problems.

Acknowledgments

Arjen Hommersom was supported by VENI Grant 639.021.918 from The Netherlands Organization of Scientific Research. We thank the reviewers for their constructive comments which have significantly improved this paper.