Maximum Entropy in Nilsson's Probabilistic Logic

1. Introduction

A recent trend in reasoning with uncertainty has been to move away from representing the uncertainty of a sentence with a point probability, towards more complex mechanisms. Most notably with Probabilistic Logic

[Nilsson 1986a, Grosof1986a, Guggenheimerl987 a], Incidence Calculus [Bundyl986a, Bundyl986b], and stochastic simulation [Pearl1987a]. All of these systems involve explicit knowledge of possible world scenarios. In Incidence Calculus, the probability of a sentence is based on a sample space of points. Each of these points can be regarded as a possible world. In Pearl's stochastic simulation probabilities of events are computed by recording the fraction of time that events occur in a random series of scenarios generated from some causal model. Probabilistic Logic is a generalisation of the ordinary true-false semantics for logical sentences to a semantics that allows sentences to be uncertain, and consequently to have more than one possible state.

The consequences of their set-theoretic nature leaves these systems prey to complexity problems in space and time. Bundy's Legal assignment finder, which finds all the legal specialisations of an initial probability assignment is at least exponential. The number of runs it takes to approximate correct probability values in the stochastic simulator is of the same order, as is entailment inside probabilistic logic. Nilsson reports that implementation of the full procedure for probabilistic entailment would usually be impracticable.

The maximum entropy [Levinel979a, Bardl982a] principle also needs knowledge of all the possible states of uncertain information, and in this respect it is related to the possible world listed above, and shares the same complexity problems.

In this case, the distribution with maximum entropy is Dl. The reduction in entropy from Dl to D4 demonstrates the effect of having more information about the change in probabilistic likelihood of one of the coins over the others. D4 represents the case where there is no uncertainty as to which coin is counterfeit.

Information is embodied in each of the distributions, and we can see that the distribution which says least about the identity of the counterfeit coin is Dl. This equation of information with entropy leads to the maximum entropy principle: Of all probability distributions which satisfy the constraints imposed by the known aggregate probabilities, choose the one which has the maximum entropy or, equivalently, contains the least information.

3. Probabilistic Entailment and Context

Nilsson defines probabilistic entailment as an analogue of logical entailment in classical logic. The rule of modus ponens allows us to use the set (A 1o A 1=>B) to deduce (B). When we have uncertainty about whether or not A 1 or A1=>B is true, the real world, which has the real value of B, becomes a random variable, and can be one of a number of possible states. These states (possible worlds) can be produced mechanically by an exhaustive theorem prover [Changl973a], and the collected group represented called a semantic tree. In conventional set theoretic terms, this set of all possibilities is the universal set. In statistical terms, this set is called the sample space or possibility space.

As an example, Nilsson uses the set (A 1o A 1=>B) to estimate the probability of logically entailed sentence B. A complete interpretation table for the worlds which form the base set for the inference is:

The possible worlds are labelled with small letters a, b and c. Each possible world must eventually be assigned a non-zero probability such that if the probability of a sentence S is 1ts, and S is true in worlds a and b, then p(a) + p(b) = 1ts . The tautology t is true in all possible worlds and is included in the set to ensure that all the probabilities sum to 1.

Structurally, world c in this example is the world which causes concern. Nilsson presented the states for the semantic tree as:

The reasoning behind this being that in worlds a and b, B can only assume one logical value, 1 and 0 respectively. But in world c, B can logically assume either of the values 1 or 0. Hence, in figure 3, c represents the world where B is false, and d represents the world where B is true.

However, in the semantic tree for figure 3 there is no way of distinguishing between the worlds c and d, because they are the same world: i.e. where A 1 is false and the rule A 1 => B is true. Figure 3 also imposes an unnecessary condition on the relationship between the possible worlds (-.A1,A 1=>B, B) and (-.A 1,A1=>B, -.B), namely that they have the same probability. In this sense, figure 3 incorporates information into our reasoning process which is not necessarily true.

In appendix B we show that 2"+1 possible worlds are created from the tree in figure 2, where n is the number of propositions in the antecedent list of the rule. Effectively, we are left with n equations and 2" possible worlds to solve for. One way to remove the additional degrees of freedom is to maximise the entropy of the system. Bard [Bardl982a ,Bardl980a] presents examples which employs the notion of a semantic tree, and which illustrates the following solution methods with clear examples.

Each possible world is rewritten in terms of a multiplication of factors [Bardl982a ,Cheesemanl983a ,Nilssonl986a], where an unknown factor is associated with each of the sentences in the database. We shall use the following notation, with a~ representing the factor for the tautology; and the factors ai being associated with proposition j; and factor aR being associated with the rule. We include the factor in the multiplication list for a possible world only if the world has a one in the corresponding row of the ~emantic tree. So, in figure 2, we have:

a=a~IaR

c=a~R

In the case of figure 2 the equations are:

1. a~ 1aR+a~1+a~R =
2. a~ 1aR+a~ 1 = 1tJ
3. a~ 1aR+a~R = Equations 2 1tz

Wheras the equations which need to be solved from figure 3 are:

1. a~1aR+a~1+2a~R =

2.

3.

a~IaR+2a~R = 1tz

Equations 3: M.E. Probabilistic Equations for Fig. 3.

An attractive aspect of the distribution shown in figure 3 is that because of the assumption of equal probabilities between worlds c and d, once the relevant equations are solved, the probability of Q is

a~1aR+a~1 = 1t1

simply a.,a 1aR+a.,aR . However, in the case of figure 2, the probability of Q is a.,a 1aR+xa.,aR, where xis some real number between 0 and 1, which indicates how likely it is that Q will be true in the context of P being false, and P=>Q being true.

It may be that the expert feels that when P is false, there is little chance of Q being true, and may therefore wish x to be small. Another way of estimating x would be to use the ambient prior probability of Q. Another way may be to base the calculation of x on how many conditions are being met in the context in which x is being applied. Another way would be just to assume that xis 0.5, and force equal probabilities between worlds c and d as in figure 3. Some of these ,;~ssignment techniques are discussed in this paper, but a more complete discussion can be found in (2).

The tree reproduced in figure 2 suggests the following new method of entailment to infer probabilistically from the set {A~oA 2, · · ·,A,.,A1AA2A· ··AA,.=>B) to the set { B }, where 7t~o1tz, · · · 7t,. are the probabilities of the premises A~oA2, · ·· ,A,., and 1tR is the probability of the rule:

1. Make the semantic tree for the base set to find the number of possible worlds.
2. Assign the probabilities 1t1,1t2, · · · ,rt,. ,1tR amongst the worlds consistently.
3. Each of these worlds provides a context in which to test the consistency of B. Find in which of these worlds B can be true, false, or either. Allow the expert to provide context splits for the worlds where B can consistently be either true or false.

The entailed probability of B is then the sum of the probabilities of all the worlds in which it can only be true, plus the respective context split proportions of the worlds where it can be either true or false.

4. The Update Method of Solution

The update method of solution, proposed in Cheeseman [Cheeseman1983a], is a particular case of the general one-point method of solution which covers all iterative methods of the form:

and the method can be expressed as follows.

1. Number the equations l...n.
2. For each ai solve equation i in terms of the other variables.
3. Assume initial values for each of the ai.
4. Choose the next ai, and recalculate it in terms of the others.
5. If the change in any of the ai 'sis more thane then back to 4.
6. Otherwise stop with success.

Figure 4: Algorithm for Update Solution Method.

Where e is a small number representing the tolerance in the approximation. This method will always converge on a solution, but the time taken is dependent on two things: (1) the number of ai 's to be solved for, and (2) the initial starting values for the ai 's.

Paris et al [Paris1988a] shows that the problem of computing these factors to a reasonable accuracy is NP-hard, and consequently such methods are probably unfeasible. The method proposed in this paper is possible because of the internal structure of entailment problems, which is described in the next section.

5. A Semantic Tree Template for the Entailment Rule

In the spirit of maximum entropy we include only the premises involved with a rule, and the rule itself- since it is only these sentences we have probabilities for. The semantic tree for any rule of the form A 1 AA 2" · · · AA,. =>B which involves n + 1 sentences, will produce 2" + 1 worlds, rather than 2"+ 1 worlds. For completeness, the effects of the worlds on the conclusion B is shown in brackets.

1. AllA1,A2, · ·· ,A,. true, Rule true. (B true.)
2. All A1,A2, ···,A,. true, Rule false. (B false.)
3. At least one of A 1,A2, · · · ,A,. false, Rule true. (B true or false.)

Figure 5: The Possible Worlds for an Entailment Base Set.

In a predicate calculus rule of the form: lf(x1,x2, · · · ,x,.)A1(x1)AA2(xz)A · · · AA,.(x.)=>B(x1,xz, · · · ,x,.) the same number of worlds is produced in direct analogy with the above cases, except that in case 2 the conclusion can be either true or false, and so the expert is given the opportunity of providing another context split. These cases are worked through in appendix B.

6. Consistency in the Semantic Tree

The inclusion of the implication rule imposes a consistency constraint on the probabilities of the premises A1.A2. ···,A,. . Namely, that in the world where the rule is false, (case 2), all of the premises are true. This logical necessity imposes the following probabilistic constraint:

For any probabilistic rule of the form p (A 1AA 2A · · · AA,. =>B }=1tR · the probabilities of the premises are consistent iff lfi.(i=l· · · n)p(Ai)>l-7tR.

Simply because the probability of the world where the rule is false is (1-7tR ), and this is a possible world shared by all the premises. Consequently, the probability assigned to each premise must be at least this large, -with some probability left over to be dispersed amongst it's other possible worlds. An exactly analagous constraint holds for the probabilities of the antecedents in a predicate calculus rule.

7. A New Algorithm for Solving the Maximum Entropy Equations

The algorithm can be expressed as follows. For any probabilistic rule of entailment of the form: p(A111. A2A ··· AA,.=>B) < 1, the corresponding aggregate factors are labelled a't, a h··· a,., aR as in section 3. The probabilites are labelled l,rt1,1tz. . .. ,7t,.,rtR such that 1 is the probability of the tautology; 1t1, .. . . 7t,. are the probabilities or propositions A 1o ··· ,A,. ; and 7tR is the probability of the rule. The solution is as follows:

Figure 6: Algorithm for Rapid Calculations of Aggregate Factors.

Once these aggregate factors are found for any consistent probability problem, the possible worlds can be rebuilt from the appropriate multiplication of factors. Not only will we have the probability of a conclusion but also a detailed breakdown of the probabilities of the contributing possible worlds.

The proof that this algorithm is correct is inductive, and can be found in appendix A. For the case where the probability of the rule is one, we use the same reasoning on a simplified version of the semantic tree.

8. Using Context Splits

We are now in a position to use conditional probabilities in the Probabilistic Logic in the form of the context splits. Obviously, if the expert provides all of the context splits, Probabilistic Logic is now able to produce point probabilities from the probabilistic entailment. If the expert wishes to specify all of these for a rule of the form A 1AA 2A · · · AA. =>B, the system requires:

1. the probabilistic strength of the rule p(A 1 ,A 2, · · · .A. =>B)
2. 2" -1 context splits.

Figure 10: Information the Expert can Provide.

As the number n increases, providing reliable context splits will become impracticable. This section suggests some mechanisms for dealing with this problem.

• 1/. If we assume that the probability of B and '"B is the same in each split context, then the probability of the conclusion is simply:

This method of assigning probability gives a very quick result.

• 2/. We can assign a contextual weight of 1/n to each of the sentences in the rule. e.g. for the case of n = 3, the contextual weight to each sentence is l/3, and for the tree:

• 3/. Another method is to get the expert to assign contextual weights to each of the propositions A 1 to A. as an indicator of how much the entailment of the conclusion depends on each of the individual A, .

So, for example, in the rule given, the expert may assign weights: (A t=0.5, A :z={>.3, A 3=0.2), and from the tree,

This system of Probabilistic Logic gives the expert all the necessary tools to fully design a subjective probability distribution to describe their level of expertise. All three of the above methods have been implemented in Prolog and may conveniently be used in meta-interpreted expert systems [Sterlingl986a] for deducing maximum entropy point probabilities from uncertain information and uncertain rules of inference. A fully operational expert system using these mechanisms is described in[Kane1989a].

9. Combination Problem

We have presented a completely sound method of providing the maximum entropy result from a probabilistic rule of inference, within the constraints of consistency. All of these rules may exist in a database independently of each other and be called on only when needed. A problem which arises is how best to combine the results of two reasoning processes, both of which it is consistent to fire, and both of which entail the same conclusion?

One solution would be to join the two rules together using the logical or-operator (since the conclusion can be entailed from either of the rules), and join the two probabilities together using the maximum entropy principle.

Example

The rules are:

Logical connection of the two rules using the or-operator gives -.A1v-.A2v-.A3v-.A4vB=A1AA2AA3AA4=>B . And the probability of the new rule is 7tt+7t2-7t1 * 1t2, using the independence assumption which is built into the maximum entropy principle.

10. Conclusion

What we have presented is a manner of getting a point estimate from a probabilistic rule of entailment using the maximum entropy distribution. The equations are not solved iteratively, and consequently, the result is achieved very quickly. This result has more mathematical significance than a point produced by the MYCIN inference mechanism, and can be computed just as quickly.

The system as presented might be thought of as a probabilistic Prolog, and is fully operational.

We have implemented these ideas in an expert system for vision recognition of 2-dimensional objects, and the system works succesfull y.

Acknowledgement

Dedicated to my dad, who showed me perseverance. With thanks to Heriot-Watt university's computer science department for help and encouragement. Particular thanks to Steven Salvini, Patrick McAndrew, Andrew Wallace, Hunter Davis; and the reviewers for pertinent suggestions.

Appendix A: Proof of Algorithm by Induction

The proof proceeds in four stages. First, to derive the expression for the world where the rule is false. Second, to show that for each of the terms au=t.2 .... . ·> there is a direct match of terms on the numerator and denominator of the expression: (1ti+1tR-l) I (1-7ti), i.e. all the unknown worlds where sentence Ai is true divided by all the worlds where A i is false. The third stage is related to the first and allows us to solve for a,. The fourth stage is for the final factor aR and is based on the worlds in which the rule is true, and a recursive expression for describing the contribution of each of the ·+1 possible worlds to this probability: a~R 0(1+aj)=1tR . i=2

Base Case

From the equations we get:

And the above equations satisfy the algorithm with n = 1.

Step

Algorithm is true for n, prove true for n+ 1.

The new premise A(n+tl is added to the antecedent arm of the rule, and placed after premise A. in the premise list. We now have aggregate factors a,,a t· .... a (n+tl,aR .

• 2/. In each row there are now 2-+ 1 possible worlds, where there used to be 2". The difference between the tree for n+ 1 propositions and n propositions, being that in row n+1 there are now 2" 1 's and 2" O's, and the rule is pushed down to position n+2.

For the half of the tree with O's in row n+ 1 we proved that there is a direct match to give each of the previous a; 's. For the other half, we use the same enumeration, and find that the factor for proposition n+ 1 cancels out on top and bottom. Furthermore the numerator still only holds the worlds where sentence Ai is true, and the denominator the worlds where Ai is false. Therefore the equation still holds.

Is the formula true for new row n+ 1?

The new tree was made up of two identical copies of the old tree, one of which has a 1 in row n+ 1, the other of which has a zero in row n+l.. Consequently, again it is possible to cancel the terms of the true worlds divided by the false worlds so that there is only a factor of a (-+tl left.

• 4/. The expression for all the worlds in terms of the factors for n o+l worlds is a,n(l+ai)

When we include the new row, we have a new multiplicative factor: We have two copies: one with an a.+2 in row n+ 1, and one with a 1. So the new expression for all the worlds is:

In the event that the probability of the rule is 1, we lose the world where the rule is false, and consequently the rule is subsumed into the tautology. In this case we have only n+ 1 factors, where

from steps 2 and 4 above, and is omitted in the interests of brevity.

Appendix B: Semantic Tree Case Analysis

Case 1: All A I> A 2, .. · , A. true, and rule true. With the rule clause having all the A 1 ,A 2, · · · ,A. negated, the rule is continuously resolved away by each literal, eventually releasing the literal B. Only the inclusion of -s in the set, would produce a contradiction.

Case 2: All A I> A 2, · · · , A. true, and rule false. The negation of the rule means that n+ 1 clauses replace the rule, where all of the A 1 ,A 2, · · · ,A. will be true, and the consequent is false. The inclusion of B in the set, would produce a contradiction.

• Case 3: At least one of A 1o A 2, · · · , A. false, and rule true. The literals in the rule cannot all be resolved away from the premises, and so no statement can be made about B from the rule. Consequently, either Bon -B will be consistent with the set. The number of worlds produced is 2"-1. (i.e. only removing the all true world from the list of posiblities.)

There is no analogous case for case 3 where the rule is false. This is because, the rule will split into n+ 1 clauses, with A 1 ,A 2, · · · .A. all true; and B false. Consequently, ifanyoftheA1,A2, ···.A. premises are false, a contradiction is immediately produced.

Now consider the predicate calculus case: { 3(x1)A 1(x1), 3(xz)A2(xz), · · · , 3(x.).A. (x.), 'v'(x1.x2. · · · .x.). A1(x1)AA2(xz}A · · · AA.(x.)=>B(x1,x2, · · · .x.) }, {3(a1,a2, · · · .a,.).B(a1.a2. · · ·.a.)).

When this conclusion is negated, the clause produced is: ....JJ (v1ov2. · · · ,v,.), where v1ov2, · · · ,v. are variables. When it is just simplified the clause produced is: B (g1,g 2, ·· ·g.) where g 1 ,g 2· · · · ,g,. are constants.

• Case 1: All3(x1).A1(x1), 3(xz)A2(xz), · · · , 3(x.)A. (x.) true, and rule true.

All the antecedent propositions being true gives the list A 1(c1). A2(cz), · ·· .A. (c.) where c1oc2, · ·· ,c. are constants. The rule being true gives ..A 1(x1)v · · · v..A.(x,.)vB(x1,x2, · ··x.) where x1.x2. · · · ,x,. are variables. From these we can resolve away to produce from the rule clause: B(c~oc 2, · · · c,.) and the inclusion of ....JJ (v1ov2, · · · ,v.) produces nil.

• Case 2: All 3(x1).A1(x1), 3(xz)A2(xz), · · · , 3(x.)A. (x,.) true, and rule false. The rule converts to n+1 clauses: the A.(c.), for i=1 ton, where c. is a unique constant for each predicate functor A.; plus a final clause which is ....JJ(c~oc 2, · ··,c.). The inclusion of B(g 1 ,g 2 ,· ·· ,g.) would not produce nil, and neither would the inclusion of B(v~ov 2, · · · ,v.).
• Case 3: At least one of 3(x1)A1(x1). 3(xz).A2(x2). · · · , 3(x.)A.(x.) false, and rule true. A directly analogous case to case 3 above. The rule does not free any information about the consequent, and so the second set can be true or false. Again we get 2"-1 possible worlds.