Models and Algorithms for Probabilistic and Bayesian Logic

1 Introduction

Numerous models and algorithms have been proposed for reasoning under uncertainty in knowledge-based sys­ tems. Among these, models based on logic and the the­ ory of probabilities are, after a period of relative dis­ favor, attracting much attention again. These models differ according to the independence assumptions made about the events or logical sentences under consideration and the amount of information requested from the ex­ pert or decision maker. At one extreme of the spectrum, well illustrated by the frobabilistic loQic and probabilistic entailment models of Nilsson, 1986J, no independance assumptions are made and only the available informa­ tion is used. Moreover, this information may be vague, i.e., expressed by probability intervals instead of precise values. In probabilistic logic, the probabilities of being true of m logical sentences are given. It is asked whether these probabilities are consistent or not. In probabilis­ tic entailment an additional logical sentence is consid­ ered and it is asked to find best possible lower and up­ per bounds on its probability of being true. In both cases the joint probability distribution on the set of pos­ sible outcomes is only partially specified. At the other extreme of the spectrum, the Bayesian network mod­ els (e.g. , [Pearl, 1988], [Lauritzen et al., 1988]) usually make strong independence assumptions and request suf­ ficient information for the joint probability distribution to be entirely specified. When those requirements are satisfied the probability of any event ma.y be computed, often in moderate time. Moreover, evidence can be ef­ ficiently propagated through the network. Attempts to combine both methodologies have been made by [Van der Gaag, 1990] [Van der Gaag, 1991] and by [Andersen et al., 1994].

Brigitte J aumard

Ecole Polytechnique de Montreal C.P. 6079, Succ. Centre-Ville Montreal (Quebec) H3C 3A7, CDN

Marcus Poggi de Aragao

Univ. Estadual de Campinas, Brazil

The purpose of this paper is to present an overview, with new results, of mathematical models and algorithms for probabilistic logic, probabilistic entailment and their extensions. Motivation stems from the facts that both problems have a long history and are the object of re­ search dispersed among several literatures. This explains recent overly pessimistic statements as to the possibil­ ity of solving large instances. After stating the prob­ lems mathematically, analytical solution is studied. It is shown that one can use Fourier elimination or enu­ meration of vertices and extreme rays of polytopes. The latter approach leads to automated generation of theo­ rems in the theory of probabilities. Numerical solution of large instances is then discussed. The column generation approach of linear programming, combined with special­ ized nonlinear 0-1 programming techniques to solve aux­ iliary subproblems (computation of the most negative or positive reduced costs) leads to algorithms efficient in practice. Extensions are then examined, i.e., use of probability intervals, conditional probabilities, linear re­ lations between probabilities and qualitative probabili­ ties. Moreover, we show that (i) restoration of consis­ tency through minimal changes in the probability inter­ vals can be handled by the same type of models and (ii} elimination of inconsistency through minimal dele­ tion of logical sentences can be solved by combining col­ umn generation with branch-and-bound. The Bayesian logic model proposed by [Andersen et a/., 1994] is finally investigated: we show that while this model is one of nonlinear nonconvex programming, many cases to which it applies can in fact be expressed as linear programs.

2 Probabilistic Satisfiability

The probabilistic logic problem of [Nilsson, 1986] may be expressed mathematically as follows. Let S = { S1 , S2, ... , Sm} be a set of m logical sentences defined on a set X= {xl,X2, .. . ,xn} of n boolean variables with the usual operators V (disjunction), 1\ ( conjunc­ tion), and ...., (negation). Let 1r = (1r1, 1r2, ... , 7rm) be a vector of probabilities that these sentences are true. Are these sentences together with their probabilities consis­ tent ? To make this question precise, consider all 2" possible assignments xk of truth values to the variables of X and let Ak be a m-vector such that a;k = 1 if S; is true for Xk and a;k = 0 otherwise. Then the system of sentences and probabilities is consistent if and only if the linear system

where A = (Ak), has a solution. In other words, the system is consistent if and only if there is a probability distribution over the set of truth assignments such that, for each sentence the sum of probabilities of the truth assignments for which it is true is equal to its probability of being true.

In Nilsson's probabilistic entailment problem an ad­ ditional sentence Sm+t is considered, a 2n row vector Am+t is defined by am+t ,k = 1 if Sm+t is true for Xk and am+t ,k = 0 otherwise. It is asked to find best possi­ ble lower and upper bounds on the probability that Sm+l is true. In other words, one seeks the optimal values of the linear programs

subject to constraints (1)-(3). Note that [Nilsson, 1986] briefly discusses how to use standard techniques to re­ duce problems of first-order probabilistic logic to the propositional case. Instead of the names probabilistic logic and probabilistic entailment, [Georgakopoulos et al. , 1988] propose to use the name probabilistic satisfia­ bility, in decision and optimization versions respectively. Indeed, [Nilsson, 1986] proposes useful models but not a logic, i.e., a system of axioms and a study of inference rules, for reasoning about logic and probabilities. Such a logic extending the results of [Nilsson, 1986] has been explored by [Fagin et al., 1990]. There are many other proposals in that area. Moreover, the name probabilistic satisfiability stresses the relationship of problem (1)-(3) with the classical satisfiability (SAT) problem of propo­ sitional logic (which corresponds to the case where 1r is equal to 1). From now on, we use the name probabilistic satisfiability (PSAT).

The (PSAT) problem has a long history. The earliest occurrence of both versions appears to be in the classi­ cal work of [Boole, 1854] on The Laws of Thought. They are called conditions of possible experience and general problem in the theory of probabilities respectively. Both problems also appear in the subjective approach to prob­ ability theory of [de Finetti , 1974]. De Finetti's funda­ mental theorem in the theory of probability ([de Finetti, 197 4], p. 112) is indeed very close to Boole's general problem. The work of [Boole, 1854] on probability at­ tracted little attention until it was revived in a seminal paper of [Hailperin , 1965] and discussed and extended in a subsequent book of the same author on Boole 's Logic and Probability [Hailperin, 1986] . Several independent rediscoveries of (PSAT) have been made (including that of [Nilsson, 1986]) .

3 Analytical Solution of PSAT

In his book of 1854 and in several contemporary and subsequent papers, [Boole, 1854] proposes procedures to solve (PSAT) approximately or exactly. The most effi­ cient one works a.'> follows : (i) express each sentence as a sum of products, each product involving all logical vari­ ables in direct or complemented form; {ii) associate un­ known probabilities to each of these products and iden­ tify the resulting sums to the given probabilities; {iii) eliminate in the equations so obtained and in the non­ negativity constraints on the probabilities the variables corresponding to the probabilities of the products.

More than a century later, [Hailperin, 1965] [Hailperin, 1986] discusses Boole's methods and shows that the above mentioned one is equivalent to Fourier elimination. Moreover , [Hailperin, 1965] expresses (PSAT) as the linear program (1)-(3) or (1)-(4) and shows that an analytical expression for the bounds on the prob­ ability 'lrm+l can be obtained by vertex enumeration of polytopes. To this effect, consider the dual Dmin (Dmax) of (1)-(4):

subject to:

As the optimal solution of a linear program occurs at one (or several) of its extreme points, one has:

Theorem 1 ({Hailperin, 1965]) The best lower (upper) bound for 'lrm+t is given by the following convex (con­ cave) piecewise linear function of the probability assign­ ment:

where llmax (yiminJ for all j represent the kmax {kmin) extreme points of {Dmax) {{Dmin)).

This result has recently been completed; the dual (D) of (1)-(3) is:

Then, from the duality theory of linear programming

Theorem 2 ({Hansen et al. , 1995]) (PSAT) is consistent if and only if the inequality

holds for all extreme rays r of {D).

Theorems (1) and (2) lead to complete analytical so­ lutions of instances of (PSAT) given in parametric form, i.e., with unspecified truth probabilities 1r; . Once such solutions are at hand it suffices, for given values of the 1r; to substitute in (11) to check consistency and in (7) and (8) to obtain best possible bounds.

As algorithms for enumeration of extreme points and rays of polytopes are readily available (e.g. , [Chen et a/., 1991], [Dyer, 1983]) it is possible to obtain analytical so­ lutions for given systems of sentences and probabilities in an entirely automated way. An example of such an automatically generated theorem in the theory of prob­ abilities is the following ([Hansen et al. , 1995]):

subject to:

Theorem 3 If logical sentences x1 and x 2 have prob­ ability 1r1 and 1r2 respectively and the inference rule ( x 1 V x2) ---+ X3 has probability 1r3 then 1r1 + 1r3 2: 1 and 1r2 + 1r3 2: 1 must hold and the probability for X3 to be true is between max{ 1r1 + 1r2 + 1r3 - 2, 0} and 1r3. Moreover, these bounds are best possible.

While results such as the above are easily obtained by direct reasoning, automation becomes useful when more sentences are considered as the numbers of conditions and of terms in the bounds increase rapidly.

4 Numerical Solution of PSAT

(PSAT) is NP-hard, as it is in NP and contains the NP­ hard problem (sAT) as a particular case ([Georgakopou­ los et a/., 1988]). Moreover, the problems (1)-(3) and ( 1 )-( 4) have a number of columns exponential in the size of the input when, as is usually the case, the size (or total number of variable occurrences) of the sentences S; is bounded by a constant. (Note that this restriction on size is natural, as otherwise reading the input would require time exponential in the number of variables). So writing (1)-(3) or (1)-(4) explicitly already requires ex­ ponential time. This has led [Van der Gaag, 1990] [Van der Gaag, 1991] to surmise that solution of (PSAT) re­ quires exponential time in general and not only in worst case. (In fact, many polynomial cases have been identi­ fied, see [Georgakopoulos et a/., 1988], [Kavvadias eta/., 1990], [Jaumard et a/. , 1991]) . [Nilsson, 1986] [Nilsson, 1993] stresses less formally, but as strongly, the diffi­ culty of solving instances of (PSAT) with many variables and suggests looking for heuristics. [Frisch et a/., 1994] propose under the name of anytime deduction a heuris­ tic approach to (PSAT) based on sequential application of rules giving smaller and smaller intervals. This has the advantage of allowing reasoning to be followed step by step but may not yield best possible bounds. How­ ever, the powerful column 15eneration technique of lin­ ear programming (see, e.g., lChvatal, 1983], chapter 18) can be brought to bear. This was proposed by lZemel , 1982] for an application of (PSAT) to reliability, then for the general case by [Georgakopoulos et a/., 1988], whose work is extended in [Jaumard et a/., 1991], and ([Hooker , 1988], see also [Andersen et a/., 1994]). When solv­ ing a linear program by column generation a compact tableau is kept; at each iteration the entering column is found by solving a combinatorial subproblem and the tableau is updated following the rules of the revised sim­ plex method. Finding the column with minimum (max­ imum) reduced cost at a current iteration is equivalent to minimization (maximization) of

where the u; are the dual variables associated with con­ straints (1) and (2) . Associating the values true with 1 and false with 0, (12) may be rewritten

which is a nonlinear expression in the variables Xj with the operators V, 1\ and-... These operators may be elimi­ nated as ...,x = 1-x, xl\y = xxy and xVy = x+y-xxy where x and yare logical variables. Minimization (max­ imization) of the resulting nonlinear function in 0-1 variables can be done approximately by variable-depth search ([Kavvadias et a/., 1990]) or tabu search ([Jau­ mard et a/., 1991]) and exactly by an algebraic method ([Jaumard et a/., 1991], [Crama et a/., 1990]) or by lin­ earization ([Hooker , 1988], [Andersen et a/., 1994]). As an exact solution is only required when no more column with a reduced cost of adequate sign can be found heuris­ tically, variable-depth and tabu search are useful even if one wants proved best possible bounds. Heuristics will be used as long as possible and followed by a usually more time-consuming exact method. The column gener­ ation technique has led to solve large instances of (PSAT), with up to 140 variables and 300 sentences ([Jaumard et a/., 1991]) in reasonable computing time. The number of columns generated is a very small proportion of the overall number in the instance (e.g., about 2100 columns for problems with 70 variables, and hence 2 70 columns, and 200 sentences).

5 Extensions of PSAT

In addition to uncertainty, expressed by probabilities, expert knowledge often suffers from vagueness. Indeed giving a single value for the truth probability of a sen­ tence is quite arbitrary in many situations. Vagueness may be expressed in (PSAT) by using probability inter­ vals [1!:i, 1f;] for the truth of sentences S; instead of single values. Then the expert is not forced to provide more in­ formation than he has. Generalizing (PSAT) in this way was already proposed by [Hailperin, 1965]. Constraints (2) are replaced by

The column generation technique for (PSAT) described above extends readily to this case, columns correspond­ ing to slack or surplus variables being treated separately. The increase in computing time when replacing single probability values by intervals is moderate ([Jaumard et a/., 1991]).

Expert knowledge may also be precise in some situa­ tions only, which is expressed by using conditional prob­ abilities 7rili = prob( S; lSi). Such conditional probabil­ ities can be integrated into (PSAT) in several ways. As prob( S; Sj) [ prob(S;jSj) = prob(Sj) , one can use Jaumard eta/.,

1991] the two constraints:

where Aa = (aa,k) with aa,k = 1 if S; 1\ Sj is true and 0 otherwise, A13 = ( afJk) with afJk = 1 if Sj is true for X" and 0 otherwise. A more compact expression, obtained by elimination of 7rj, is:

where A1' = ( a-yk) with a-yk = 1 - 7r;jj if S; 1\ Sj is true, -11';jj if Sj is true and S; is false, and a-yk = 0 otherwise. Using (1) to add 7r;jj to all columns, one can also write

~her~ A5 = (a5k) ~ith a5k = 1 if S; 1\ Sj is true, a5k = 0 If Sj IS true and S; IS false and a5k = 11'ijj otherwise. This corresponds to the three-valued definition of conditional probability of [de Finetti, 1974]. Consistency conditions using this last form are derived by [Gilio, 1973], among others. If best possible bounds are sought for a con­ ditional probability the objective function (4) must be replaced by:

and the p~oblem beco~es ~ hyperbolic (or fractional) programmmg one. [Hailpenn, 1986] observes that this problem can be reduced to a linear program with one more variable using a standard technique of [Charnes et al., 1962]: one minimizes AaP adding to the constraints A~p = 1 and multiplying right-hand sides by a scaling factor t; once the solution is found , the probabilities p; are divided by t . Alternately [Jaumard et al., 1991] one can apply the lemma of [Dinkelbach, 1967] for fractional programming and solve (1)-(3), (16) by a sequence of linear programs. Again column generation techniques apply and . computing time is not much lar~er than for standard (PSAT) problems of the same size lJaumard et al. , 1991]. Intervals for conditional probability values can be handled as for usual probabilities.

[Fagin et al., 1990] develop a logic for reasoning about probabilities which extends the results of [Nilsson, 1986]. In particular they consider linear expressions in the prob­ a_bilities 11"j. If some of these are unknown, such expres­ Sions can be handled within the column generation ap­ proach, again by keeping separate explicit columns.

A step further is made by [Coletti, 1994] who consid­ ers qualitative probabilities or conditional probabilities: their values are unknown but a partial order on them is assumed to be given. The resulting generalization of (PSAT) remains linear for probabilities but is a nonlin­ ear nonconvex problem for conditional probabilities and thus hard to solve. [Coletti, 1994] presents conditions of consistency for such problems.

If a system of sentences is not consistent, which easily happens after addition of rules by different experts, one may seek to restore consistency with minimal changes. A first criterion is to minimize the sum of increases of the probability intervals, possibly weighted to express the degree of confidence of the expert in his evaluations. This leads to the following linear program [J aumard et al., 1991]:

subject to:

~here f;(u;) in the decrease in the lower bound (increase m the upper bound) on the probability of S;, !Q; and w; are attenuation. factors for these changes.

Another criterion is to minimize the number of sen­ tences to remove in order to restore consistency. The resulting problem, called probabilistic maximum satisfi­ ability (PMAXSAT) as it generalizes the (MAXSAT) prob­ lem of propositional logic (e.g. , [Hansen et al. , 1990]) , is a mixed-integer programming one ([Hansen et al., 1992]) :

subject to:

Consistent problems with up to 185 sentences to which are added 15 to 25 more sentences, and which then be­ come inconsistent , are readily solved, with a small num­ ber of branchings.

6 . Bayesian Logic

In Bayesian networks, denoted G = (V, E) (e.g., [Pearl , 1988]), nodes Vj E V are associated with simple events (or logical variables x j , we assume here only two out­ c<;>mes are possible for each event, i.e., true or false) and duected arcs ( v; , Vj) are used to represent probabilistic dependence among events. Morover, these netwroks are acyclic. The probabilities of each node conditioned on the values of its immediate predecessors are given. Then the probability that a node is true, when conditioned on the truth values of all its non-successors, is equal to the probability that it is true, conditioned only on the truth values of its immediate predecessors.

Example. [Andersen et al. , 1994] consider a net­ work with six nodes and assume the following con­ ditional probabilities to be given: prob(x41x5x6) = 1, prob(x41(-.xs)x6) = 1, prob(x4lxs(-.x6)) = 1, prob(x41(-.xs)(-.x6)) = 0, prob(x2lx4) = 0.4, prob(x2!-.x4) = 0.05, prob(xalx4) = 0.2, prob(x3l-.x4) = 0.1 , prob(x1lx2xa) = 0.95, prob(xd( -.x2)xa) = 0.8, prob(xdx2(-.xa)) = 0.7, prob(xd(-.x2)(-.xa)) = 0.1, as well as the marginal probabilities prob(x5 ) = 0.25 and prob(x6) = 0.15. As x 5 and x6 are assumed to be in­ dependent, prob(x4) = prob(xs V x 6 ) = prob(x5x6)+ prob((-.xs)x6)+ prob(xs(-.x6)) = 0.3625.

Let Xj denote x j or -.x j. Then the probability of any truth assignment XI, x2 , ... 'Xn can be computed by the chain rule

and in view of the above mentioned independence as­ sumption this can be done using the specified conditional probabilities only.

Example (continued). Removing nodes v5 and v6 as prob( x4) is known, one has

prob(XIIX2XaX4)prob(X2iXaX4)Prob(XaiX4)Prob(X4) = prob(X1IX2Xa)prob(X2IX4)Prob(XaiX4)Prob(X4); for instance prob(xi(-.x2)(-.x3)(-.x4)) = 0.1 x 0.95 x 0.9 X 0. 7375 = 0.6306.

The probability of any sentence S; may be computed in a similar way. For other types of operations answer­ able by Bayesian networks and in particular for propa­ gation of evidence, see, e.g., [Pearl, 1988], [Andersen et a/. , 1994].

The Bayesian Logic proposed by [Andersen et a/., 1994] consists in using the (PSAT) model to interpret probability statements associated with Bayesian net­ works and then to study various generalizations. To this effect conditional independence statements are encoded as additional nonlinear constraints. These constraints have the general form

where A, B and C are sets of propositional variables, with IAI =a, IBI = b, ICI = c and Ao, Bo and Co are sets of fixed atomic propositions. [Andersen eta/. , 1994] show that there are (2a -1 )2b(2c -1) nonredundant constraints among those described by ( 17). From the definition of conditional probability, (17) is equal to

[Andersen et a/. , 1994] propose to solve the extended (PSAT) model with constraints (17) by generalized Ben­ ders decomposition. Following that approach the prob­ lem is split into a nonlinear master problem in the 1r variables and a linear subproblem in the p variables, of the (PSAT) type. The subproblem is used to generate from its dual, linear constraints in the 1r variables, called Benders cuts, as long as it is infeasible. These cuts are added to the master problem. The procedure stops af­ ter a finite number of steps when the master problem is infeasible or the subproblem is feasible. The master problem has the form of a signomial geometric program for which specialized algorithms exist . Such problems belong to global optimization and only instances with few variables can be solved in reasonable time. This ap­ parently limits the scope of Bayesian logic, even if the number of 1r variables is much smaller than the num­ ber of p variables. Fortunately, there are many cases in which one need only add linear constraints to (PSAT) to express the independence assumptions of Bayesian net­ works and generalizations of them.

Theorem 4 Computing the probability of a sentence S; in a Bayesian network can be expressed as a (PSAT) prob­ lem with conditional probabilities.

Proof. Conditional probabilities for nodes given the truth value of their immediate predecessors can be ex­ pressed by (15) and marginal probabilities by (2). For independence conditions, let Bj denote the set of atomic propositions associated with immediate predecessors of Vj and Aj a similar set for non immediate predecessors of Vj. Then the condition

is equivalent to the expression

which is linear as the right-hand side of (18) is given. Finally, independence of sets A of nodes without pre­ decessors is expressed by identifying prob(A) with the product of the corresponding marginal probabilities 7r. · Example (continued). Assume one seeks the value of prob(x2lx1x3). Associate the probabilities P1, p2, ... , P16 to the truth assignements as follows:

Using the technique of [Charnes et a/., 1962], the objec­ tive function is expressed by

subject to:

the conditional probabilities, using (15), by

the marginal probability by

P1 + Pa + Ps + P7 + P9 + Pll + P13 + P15- 0.3625t = 0; the normalizing constraint by

the independence constraints prob(X2IXaX4) prob(XziX4) by

and the independence constraints prob(X1IX2XaX4) = prob(XdXzXa) by

The optimal value is 0.26863.

Clearly the number of sets of non-immediate prede­ cessors of a node may be exponential. However, not all corresponding constraints need be written. [Lau­ ritzen et a/., 1988] explain how to represent indepen­ dence relations by an undirected graph G' in which all pairs of immediate predecessors are joined and edges are added until the graph is triangulated. Then the joint probability distribution can be expressed as a product of marginal probability distributions on the maximal cliques of G', adequately scaled. [Van der Gaag, 1990] [Van der Gaag, 1991] proposes to use this property in a decomposition method for (PSAT) , discussed in a com­ panion paper ([Douanya et a/., 1995]). It is shown there that the usual (PSAT) model gives the same bounds as the decomposition-based version. Consequently (PSAT) takes implicitly into account in the computation of the bounds the conditional independence constraints (18) in­ volving variables which do not all belong to the same maximal clique.

Example (continued). A graph G' associated with the example after deletion of v5 and v6 is composed of triangles on v1 , v2, v3 and on v2 , v3 , v4. This shows that when computing bounds on prob(x2lxtxa) one neeed not take explicitly into account the constraints prob(XdX2XaX4) = prob(Xt!X2Xa), i.e. , the four last ones listed above.

[Andersen et a/., 1994] also explore cases where the number of independence constraints is limited. The main interest of Bayesian logic is not , however, to propose an alternate method for the computation made in Bayesian networks, but to consider more general assumptions.

Example (continued). Assume as done by [Andersen et a/., 1994] that the atomic propositions x5 and x6 are not independent . Then, 0.25 ~ prob(x4) ~ 0.40. Replacing the line giving the marginal probability of x4 by

minimizing and maximizing yields bounds of 0.21786 and 0.28358. Note that when using Benders decomposition the computation of the lower bound required 57 itera­ tions, i.e., solution of 57 (PSAT) and 57 signomial geo­ metric programming problems.

As discussed in [Andersen et a/. , 1994], many other ex­ tensions of Bayesian networks can be considered within the (PSAT) framework : one can replace single proba­ bility values by intervals, add constraints of different types than the conditional implications, allow for net­ works with cycles, etc. Not all extensions will remain linear. For instance, if in the example, the marginal probabilities for x5 and x 6 are replaced by intervals and the independence assumption is kept a quadratic con­ straint

arises. The resulting quadratic programs can be solved in many ways using global optimization techniques. Finding which are most efficient is an open problem.

To conclude, (PSAT) appears to be a flexible and com­ putationnally tractable model for reasoning under un­ certainty. It has already been extended in many ways, while remaining linear. Further exploration of the prob­ lems which may be so expressed and of solution methods for the nonlinear case are attractive topics for future re­ search.