Probabilistic Partial Evaluation: Exploiting Rule Structure in Probabilistic Inference

1 Introduction

Probabilistic inference IS Important for many applications in diagnosis, perception, and anywhere there is uncertainty about the state of the world from observations. Belief (Bayesian) networks [Pearl, 1988] are a representation of in­ dependence amongst random variables. They are of interest because the independence is useful in many domains, they al­ low for compact representations of problems of probabilistic inference, and there are algorithms to exploit the compact rep­ resentations.

Recently there has been work to extend belief networks by allowing more structured representations of the condi­ tional probability of a variable given its parents. This has been in terms of either causal independencies [Heckerman and Breese, 1994; Zhang and Poole, 1996] or by exploiting finer grained contextual independencies inherent in stating the con­ ditional probabilities in terms of rules [Poole, 1993] or trees

*This work was supported by Institute for Robotics and Intelli­ gent Systems, Project IC-7 and Natural Sciences and Engineering Research Council of Canada Research Grant OGP0044121 . Thanks to Holger Hoos and Mike Horsch for comments.

[Boutilieret al. , 1996]. In this paper we show how algorithms for efficient inference in belief networks can be extended to also exploit the structure of the rule-based representations.

In the next section we introduce belief networks, a rule­ based representation for conditional probabilities, and an al­ gorithm for belief networks that exploits the network struc­ ture. We then show how the algorithm can be extended to ex­ ploit the rule-based representation. We present an example in detail and show how it is more efficient than previous propos­ als for exploiting structure.

2 Background

2.1 Belief Networks

A belief network [Pearl, 1988] is a DAG, with nodes labelled by random variables. We use the terms node and random vari­ able interchangeably. Associated with a random variable x is its frame, val(x), which is the set of values the variable can take on. For a variable x, let rrx be the parents of x in the be­ lief network. Associated with the belief network is a set of probabilities of the form P( x lrrx ), the conditional probability of each variable given its parents (this includes the prior prob­ abilities of those variables with no parents).

A belief network represents a particular independence as­ sumption: each node is independent of its non-descendents given its parents. Suppose the variables in a belief network are x1 , ... , Xn where the variables are ordered so that the par­ ents of a node come before the node in the ordering. Then the independence of a belief network means that:

By the chain rule for conjunctions we have

This is often given as the formal definition of a beliefnetwork.

Example 2.1 Consider the belief network of Figure I. This represents a factorization of the joint probability distribution:

If the variables are binary, the first term, P( e labcd), requires the probability of e for all 16 cases of assignments of values to a, b, c, d.

2.2 Contextual Independence

Definition 2.2 Given a set of variables C, a context on Cis an assignment of one value to each variable in C. Usually Cis left implicit, and we simply talk about a context. Two contexts are incompatible if there exists a variable that is assigned dif­ ferent values in the contexts; otherwise they are compatible.

Boutilier et at. [ 1996] present a notion of contextually inde­ pendent that we simplify. We use this definition for a repre­ sentation that looks like a belief network, but with finer-grain independence that can be exploited.

Definition 2.3 [Boutilier et at., 1996] Suppose X, Y and C are disjoint sets of variables. X andY are contextually inde­ pendent given context c. E val(C) if P(XIY =y1 A C=c) = P(XIY=y2 A C=c) for all Y1,Y2 E val(Y) such that P(Y=y1 A C=c) > 0 and P(Y=y2 A C=c) > 0.

Definition 2.4 Suppose we have a total ordering of variables. Given variable x;, we say that c E val(C) where C ~ { x;_ 1 ... xi} is a parent context for x; if x; is contextually independent of {x;_1 ... xi}- C given c.

What is the relationship to a belief network? In a belief net­ work, the rows of a conditional probability table for a vari­ ables form a set of parent contexts for the variable. However, often there is a much smaller set of smaller parent contexts that covers all of the cases.

A minimal parent context for variable x; is a parent con­ text such that no subset is also a parent context.

Example 2.5 1 variable e are a, b, c, d, y, z. It could be the case that the set of minimal parent contexts for e are { {a , b} , {a , b}, {a, c }, {a, c, d, b }, {a, c, d, b}, {a, c, d} }. The proba­ bility of a given values for its predecessors can be reduced to the probability of a given a parent context. For example:

1 In this and subsequent examples, we assume that variables are Boolean. If xis a variable, x =true is written as x and x = false is written as x.

In the belief network, the parents of e are a, b, c, d, and would, in the traditional representation, require 2 4 = 16 numbers in­ stead of the 6 needed above. Adding an extra variable as a parent to e doubles the size of the table representation, but if it is only relevant in a very restricted context it may only in­ crease the size of the rule based representation by one.

For each variable x; and for each assignment x;_ 1=v; _ 1 , ... , x1=v1 of values to its preceding vari­ ables, there is a parent context rr~:-' · v,. Given this, the probability of an assignment of a value to each variable is given by:

This looks like the definition of belief network, but which variables act as the parents depends on the values. The num­ bers required are the probability of each variable for each of its minimal parent contexts. There can be many fewer mini­ mal parent contexts that the number of assignments to parents in a belief network.

Before showing how the structure of parent contexts can be exploited in inference, there are a few properties to note:

The set of minimal parent contexts is covering, in the sense that for each assignment of values to the variables before x; in the ordering with non-zero probability, there is a minimal context that is a subset.

The minimal parent contexts are not necessarily pairwise incompatible: it is possible to have two minimal parent con­ texts whose conjunction is consistent. This can only occur when the probability of the variable given the compatible con­ texts is the same, in which case it doesn't matter which parent context is chosen in the above formula.

The minimal parent contexts can often, but not always, be represented as a decision tree [Boutilier et at., I 996] where the contexts correspond to the paths to the roots in the tree. The operations we perform don't necessarily preserve the tree structure. Section 4. I shows how we can do much better than the analogous tree-based formulation of the algorithm.

2.3 Rule-based representations

We write the probabilities in contexts as rules,

where x;, = v;, A ... A x;k =v;k forms a parent context of x; and 0 ::; p ::; 1 is a probability. '

This rule can be interpreted in at least two ways:

In the first, this rule simply means the conditional probabil­ ity assertion:

The second interpretation [Poole, 1993] is as a set of defi­ nite clauses, with "noise" terms in the body. The noise terms are atoms that are grouped into independent alternatives (dis­ joint sets) that correspond to random variables. In this inter­ pretation the above rule is interpreted as the clause:

where n_i~,, , ... ,v,k; is a noise term, such that, for each tuple of values (vi,, ... , Vik . ), the noise terms for different values for v are grouped into an alternative, and the different alternatives are independent. P( n_i~,, , ... ,v;k . ) = p. This interpretation may be helpful as the operation; we consider can be seen as instances of resolution on the logical formula. One ofthe main advantages of rules is that there is a natural first-order version, that allows for the use of logical variables.

Example 2.6 Consider the belief network of Figure I. Figure 2 gives a tree-based representations for the conditional prob­ ability of e given its parents. In this tree, nodes are labelled with parents of e in the belief network. The left hand child cor­ responds to the variable being true, and the right hand node to the variable being false. The leaves are labelled with the prob­ ability that e is true. For example P( e=t ia=t 1\ b= f) = 0.5, irrespectively of the value for cor d.

These trees can be translated into rules: 2

These trees can be translated into rules:	(2)
e +- a 1\ b : 0.55 b:
1\	(4)
e +-a 1\ 0.5 e +- a c : 0.08	(3)
e +- a 1\ c 1\ d 1\ b : 0.025	(5)
e +-a 1\ c 1\ d 1\ b: 0.5	(6)
e +- a 1\ c 1\ d : 0.85	(7)

Note that the parent contexts are exclusive and covering. Assume the corresponding rules for b are:

Definition 2. 7 Suppose R is a rule

andy is a context on Y such that {xi , Xi 1, .. . , Xik · } ~ Y ~ {XI, ... , Xn}. We say that R is applicable in co~text y if y assigns v to Xi and for each ij assigns Vij to Xij.

Lemma 2.8 If the bodies for the rules are exclusive the prob­ ability of any context on {XI, ... , Xn} is the product of the probabilities of the rules that are applicable in that context.

For each Xi, there is exactly one rule with Xi in the head that is applicable in the context. The lemma now follows from equa­ tion(]).

In general we allow conjunctions on the left of the arrow. These rules have the obvious interpretation. Section 3.2 ex­ plains where these rules arise.

2.4 Belief network inference

The aim of probabilistic inference is to determine the poste­ rior probability of a variable or variables given some obser­ vations. In this section we outline a simple algorithm for be­ lief net inference called VE [Zhang and Poole, 1996] or bucket elimination for belief assessment, BEBA [Dechter, 1996], that is based on the ideas of SPI [Shachter et al., 1990]. This is a query oriented algorithm that exploits network structure for efficient inference, similarly to clique tree propagation [Lau­ ritzen and Spiegelhalter, 1988; Jensen et al., 1990]. One dif­ ference is the factors represent conditional probabilities rather than the marginal probabilities the cliques represent.

Suppose we want to determine the probability of variable x given evidence e which is the conjunction of assignments to some variables ei, ... , e,, namely ei=oi 1\ ... 1\ e,=o,.

2 We only specify the positive rules on our examples. For each rule of the form:

at-b:p

we assume there is also a rule of the form

We maintain both as, when we have evidence(Section 3.3), they may no longer sum to one.

Then:

Here P(e1=o1 1\ ... 1\ e, =o,) is a normalizing factor. The problem of probabilistic inference can thus be reduced to the problem of computing the probability of conjunctions. Let { Yl , ... , yk} = { x 1 , ... , x n} - { x} - { e 1, .. . , e s}, and sup­ pose that the y; 's are ordered according to some elimination ordering. To compute the marginal distribution, we sum out they; 'sin order. Thus:

where the subscripted probabilities mean that the associated variables are assigned the corresponding values in the func­ tion.

Thus probabilistic inference reduces to the problem of sum­ ming out variables from a product of functions . To sum out a variable y; from a product, we distribute all of the factors that don't involve the variable out of the sum. Suppose h , ... , h are some functions ofthe variables that are multiplied together (initially these are the conditional probabilities), then

where h . .. fm are those functions that don't involve y;, and fm+l ... h are those that do involve y;. We explicitly con­ struct a representation for the new function Ly, fm+l ... fk, and continue summing out the remaining variables. After all they; 'shave been summed out, the result is a function on x that is proportional to x 's posterior distribution.

Unfortunately space precludes a more detailed description; see [Zhang and Poole, 1996; Dechter, 1996] for more details.

3 Probabilistic Partial Evaluation

Partial evaluation [Lloyd and Shepherdson, 1991] is a tech­ nique for removing atoms from a theory. In the simple case for non-recursive theories, we can, for example partially evaluate b, in the clauses:

by resolving on b resulting in the clause:

The general idea of the structured probabilistic inference algo­ rithm is to represent conditional probabilities in terms of rules, and use the VE algorithm with a form of partial evaluation to sum out a variable. This returns a new set of clauses. We have to ensure that the posterior probabilities can be extracted from the reduced rule set.

The units of manipulation are finer grained than the factors in VE or the buckets of BEBA; what is analogous to a factor or a bucket consists of sets of rules. Given a variable to elim­ inate, we can ignore (distribute out) all of the rules that don't involve this variable.

The input to the algorithm is: a set of rules representing a probability distribution, a query variable, a set of observa­ tions, and an elimination ordering on the remaining variables.

At each stage we maintain a set of rules with the following program invariant:

The probability of a context on the non-eliminated variables can be obtained by multiplying the prob­ abilities associated with rules that are applicable in that context. Moreover for each assignment, and for each non-eliminated variable there is only one ap­ plicable rule with that variable in the head.

The algorithm is made up of the following primitive opera­ tions that locally preserve this program invariant: 3

Variable partial evaluation (VPE). Suppose we are elim­ inating e, and have rules:

such that there are no other rules that contain e in the body whose context is compatible with b. For each rule fore :

where b and h are compatible contexts, we create the rule:

This is done for all pairs of rules with e in the head and body. The original rules that contain e are removed.

To see why this is correct, consider a context c that includes a, b, and h, but doesn't give a value for e. Then P(c) = P(c 1\ e) + P(c 1\ e). P(c 1\ e) = pP(alb 1\ e)P(eih) , for some product p of terms that don't include e. Similarly P(c 1\ e) = pP(alb 1\ e)P(eih), for the same value p. Thus we have P( c) = p(p1p3 + P2P4). Because of the structure of Rule (15), it is only chosen for contexts with a, b, and h true, and it is the only rule with head a in such contexts.

Rule Splitting. If we have a rule

We can replace it by its split on variable d, forming rules:

3 To make this presentation more readable we assume that each variable is Boolean. The extension to the multi-valued case is straightforward. Our implementation uses multi-valued variables.

Combining Heads. If we have two rules:

such that a and b refer to different variables, we can combine them producing:

Thus in the context with a, b, and c all true, the latter rule can be used instead of the first two. We show why we may need to do this in Section 3.2.

In order to see the algorithm, let's step through some exam­ ples to show what's needed and why.

Example 3.1 Suppose we want to sum out b given the rules in Example 2.6. b has one child e in the belief network, and so b only appears in the body of rules for e. Of the six rules for e, two don't contain b (rules (4) and (7)), and so remain. The first two rules that contain b can be treated separately from the other two as they are true in different contexts. VPE of rules (2) and (3) with rule (8), results in:

Summing out b results in the following representation for the probability of e. (You can ignore these numbers, it is the struc­ ture of the probability tables that is important.)

Thus we need 16 rules (including rules for the negations) to represent how e depends on its parents once b is summed out. This should be contrasted with the table of size 64 that is cre­ ated for VE or in clique tree propagation.

3.1 Compatible Contexts

The partial evaluation needs to be more sophisticated to han­ dle more complicated cases than summing out b, which only appears at the root of the decision tree and has only one child in the belief network.

Example 3.2 Suppose, instead of summing out b, we were to sum out d where the rules ford were of the form:

The first three rules fore (rules (2)-(4)) don't involved, and remain as they were. Variable partial elimination is not di­ rectly applicable to the last three rules for e (rules (5)-(7)) as they don't contain identical contexts apart from the vari­ able being eliminated. It is simple to make the variable par­ tial elimination applicable by splitting rule (7) on b resulting in the two rules:

Rules (25) can be used with rule (5) in a variable partial eval­ uation, and (26) can be used with rule (6). The two rules cor­ responding variable partial evaluation with rule (22) are:

Four other rules are created by combining with the other rules for d.

In general, you have to split rules with complementary liter­ als and otherwise compatible, but not identical, contexts. You may need to split the rules multiple times on different atoms. For every pair of such rules, you create the number of rules equal to the size of the union of the literals in the two rules minus the number of literals in the intersection.

3.2 Multiple Children

One problem remains: when summing out a variable with multiple children in the belief network, using the technique above, we can't guarantee to maintain the loop invariant. Consider the belief network of Figure I . If you were to sum out y, the variables a, b, c, and d become mutually dependent. Using the partial evaluation presented so far, the dependence is lost, but it is crucial for correctness.

To overcome this, we allow multiple variables in the head of clauses. The rules imply different combinations of the truth of the variables in the heads of clauses.

Example 3.3 Consider a belief network with a and b are the only children of y, andy is their only parent, andy has a single parent z . Suppose we have the following rules involving a, b, andy:

We could imagine variable partial elimination on the rules for a with rule (31 ), and the rules forb with rule (31 ), resulting in:

However, this fails to represent the dependency between a and b that is induced by eliminating y.

We can, however, combine rules (27) and (29) resulting in the four rules:

Similarly, we can combine rules (28) and (30), resulting in four rules including:

which can be combined with rule (32) giving

Note that the rules with multiple elements in the head follow the same definition as other rules.

3.3 Evidence

We can set the values of all evidence variables before sum­ ming out the remaining non-query variables (as in VE). Sup­ pose e 1 =o1 1\ . .. 1\ e, =o, is observed. There are three cases:

• Remove any rule that contains e;=o;, where o; f. o; in the head or the body.
• Remove any term e;=o; in the body of a rule.
• Replace any e; =o; in the head of a rule by true.

Rules with true in the head are treated as any other rules, but we never resolve on true . When combining heads containing true, we can use the equivalence: true 1\ a = a.

Example 3.4 Supposed is observed. The rules fore become:

The rules (22)-(24) ford become:

d doesn't appear in the resulting theory.

3.4 Extracting the answer

Once evidence has been incorporated into the rule-base, the program invariant becomes:

The probability of the evidence conjoined with a context con the non-eliminated variables can be ob­ tained by multiplying the probabilities associated . with rules that are applicable in context c.

Suppose x is the query variable. After setting the evidence variables, and summing out the remaining variables, we end up with rules of the form:

The probability of x 1\ e is obtained by multiplying the rules of the first two forms. The probability ofx 1\ e is obtained by multiplying the rules of the last two forms. Then

3.5 The Algorithm

We have now seen all of the components of the algorithm. It remains to put them together. We maintain the loop invariant of Section 3.4.

The top-level algorithm is the same as VE:

To compute P(xi e1=o1 1\ . .. 1\ e,=o,) given elimination ordering y1 , ... , Yk:

1. Set the evidence variables as in Section 3.3.
2. Sum out Y1 , ... , Yk in turn.
3. Compute posterior probability as in Section 3.4

The only tricky part is in summing out variables.

To sum out variable y;:

1. {Rule splitting for combining heads}

for each pair of rules h1 ~ b1 : PI and h2 ~ b2 : P2

such that b1 and b2 both contain y;

and h1 1\ b1 and h2 1\ b2 are compatible,

but not identical

split each rule on variables in body of the other rule. {Following 1, all rules with Yi in the body that are applicable in the same context have identical bodies.}

1. {Combining heads}

for each pair of rules h1 ~ b : PI and h2 ~ b : P2

such that b contains y;

and h1 and h2 are compatible

replace them by the rule ht 1\ h2 .~ b: PIP2

{Following 2, for every context, there is a single rule with Yi in the body that is applicable in that context.}

3. {Rule splitting for variable partial evaluation}

for every pair of rule of the form h ~ Yi =v; 1\ b1 : PI

and b1 and b2 are comparable and not identical

split each rule on atoms in body of the other rule.

{Following 3, all rules with complementary values for the y;, but otherwise compatible bodies have otherwise identical. bodies and identical heads}

4. {Variable partial evaluation}

for each set of rules: h ~ Yi =vk 1\ b : Pk

where the Vk are all of the values for y;

such that h 1\ b and h2 1\ b2 are compatible

create the rule h 1\ h2 ~ b 1\ b2 : Lk PkQk·

1. {Clean up}

Remove all rules containing y;.

4 Comparison with other proposals

In this section we compare standard belief network algo­ rithms, other structured algorithms and the new probabilistic partial evaluation algorithm. Example 2.6 is particularly illu­ minating because other algorithms do very badly on it.

Under the elimination ordering b, d, c, a, y, z, to find the prior one, the most complicated rule set created is the rule set for e given in Example 3.1 with 16 rules (including the rules for the negations). After summing out d there are also 16 rules for e. After summing out c there are 14 rules fore, and after summing out a there are 8 rules for e. Observations simplify the algorithm as they mean fewer partial evaluations.

In contrast, VE requires a functor with table size 64 after b is summed out. Clique tree propagation constructs two cliques, one containing y, z, a, b, c, d of size 2 6 = 64, and the other containing a, b, c, d, e of size 32. Neither takes the structure of the conditional probabilities into account.

Note however, that VE and clique tree propagation manip­ ulate tables which can be indexed much faster than we can manipulate rules. There are cases where the rule-base expo­ nentially is smaller than the tables (where added variables are only relevant in narrow contexts). There are other cases where we require as many rules as there are entries in the table (we never require more), in which case the overhead for manipu­ lating rules will not make us competitive with the table-based methods. Where real problems lie in this spectrum is still an open question.

Boutilier et al. [ 1996] present two algorithms to exploit structure. For the network transformation and clustering method, Example 2.6 is the worst case; no structure can be ex­ ploited after triangulation of the resulting graph. (The tree for e in Example 2.6 is structurally identical to the tree for X ( 1) in Figure 2 of [Boutilier et al., 1996]). The structured cutset conditioning algorithm does well on this example. However, if the example is changed so that there are multiple (discon­ nected) copies of the same graph, the cutset conditioning al­ gorithm is exponential in the number of copies, whereas the probabilistic partial evaluation algorithm is linear.

This algorithm is most closely related to the tree-based al­ gorithms for solving MDPs [Boutilier et al., 1995], but these work with much more restricted networks and with stringent assumptions on what is observable.

4.1 Why not trees?

It may be thought that the use of rules is a peculiarity of the author and that one may as well just use a tree-based repre­ sentation. In this section I explain why the rule-based version presented here can be much more efficient than a tree-based representation.

Figure 3 shows an exemplar for summing out a variable with multiple children. The ancestors of c, d, f , g, and h are not shown. They can be multiply connected. Similarly the de­ scendents of a and b are not shown.

Suppose we were to sum out e. Once e is eliminated, a and b become dependent. In VE and bucket elimination we form a factor containing all the remaining variables. This factor represents P(a, bl c, d, f , g , h). One could imagine a version of VE that builds a tree-based representation for this factor. We show here how the rule-based version is exploiting more structure than this.

Suppose e is only relevant to a when dis true, and e is only relevant to b when f is true. In this case, the only time we need to consider the dependence between a and b is when both d and f are true. For all of the other contexts, we can treat a and b as independent. The algorithm does this automatically. Consider the following rules for a:

Consider the rules forb :

Consider the rules for e:

The first thing to note is that the rules that don't mention e are not affected by eliminating e. Thus rules ( 4 7), ( 48), (51), and (52) remain intact after eliminating e.

Rules ( 45) and ( 49) are both applicable in a context with a, d, e, b and f true. So we need to split them, according to the first step of the algorithm, creating:

We can combine rules (55) and (57) forming:

Note also that rules (56) and (58), don't need to be combined with other rules. This reflects the fact that we only need to consider the combination of a and b for the case where both f and d are true.

Similarly we can split rules ( 46) and (50), and combine the compatible rules, giving rules for the combination of a and b in the context d 1\ e 1\ f, rules for a in the context d 1\ e 1\ 1 and rules forb in the context d 1\ f 1\ e .

Finally we can now safely replace e by its rules; all of the dependencies have been eliminated. The resultant rules en­ code the probabilities of {a, b} in the contexts d 1\ f 1\ h and d 1\ f 1\ h, (8 rules). For all other contexts we can consider a and b separately. There are rules for a in the contexts d 1\ c (rule (47)), d 1\ c (rule ( 48)), d 1\ fl\ h, and d 1\ fl\ h, with the last two resulting from combining rule (56), and an analogous rule created by splitting rule (46), with rules (53) and (54) for e). Similarly there are rules forb in the contexts /A g, fl\ g, d 1\ f 1\ h, and d 1\ f 1\ h. The total number of rules (including rules for the negations) is 24.

One could imagine using VE or BEBA with tree-structures probability tables. This would mean that, once e is eliminated, we need a tree representing the probability on both a and b. This would entail multiplying out the rules that were not com­ bined in the rule representation, for example the distribution on a and b the contexts d 1\ c 1\ fl\ g. This results in a tree with 72 probabilities at leaves. Without any structure, VE or BEBA needs a table with 2 7 = 128 values.

Unlike VE or BEBA, we need the combined effect on a and b only for the contexts where e is relevant to both a and b. For all other contexts, we don't need to combine the rules for a and b. This is important as combining the rules is the pri­ mary source of combinatorial explosion. By avoiding com­ bining rules, we can have a huge saving when the variable to be summed out appears in few contexts.

5 Conclusion

This paper has presented a method for computing the poste­ rior probability in belief networks with structured probability tables given as rules. This algorithm lets us maintain the rule structure structure, only combining contexts when necessary.

The main open problem is in finding good heuristics for elimination orderings. Finding a good elimination ordering is related to finding good triangulations in building compact junction trees, for which there are good heuristics [Kja:rulff, 1990; Becker and Geiger, 1996]. These are not directly appli­ cable to probabilistic partial evaluation, as an important crite­ ria in this case is the exact form of the rules, and not just the graphical structure of the belief network.

The two main extensions to this algorithm are to multi­ valued random variables and to allow logical variables in the rules. Both extensions are straightforward.

One of the main potential benefits of this algorithm is in approximation algorithms, where the rule bases allows fine­ grained control over distinctions. Complementary rules with similar probabilities can be collapsed into a simpler rule. This can lead to more compact rule bases, and reasonable posterior ranges [Poole, 1997].