Maximum Entropy and Variable Strength Defaults

1 Introduction

There have been several suggestions of what might con­ stitute the best consequence relation to be associated with a set of propositional defaults. The weakest, and most widely accepted, is System P [Adams, 1975), [Kraus et al., 1990]. Of those which handle the more complex default interactions, such as exceptional inheritance, cor­ rectly, the maximum entropy approach (me) has, ar­ guably, the clearest objective justification being derived from a well understood principle of indifference. In this paper, the me-approach of [Goldszmidt et al., 1993] is extended so that the me-ranking for an arbitrary set of variable strength defaults can be found. A new al­ gorithm is presented along with a sufficient condition for its successful computation. As well as handling the usual examples from the literature in a satisfactory way this extended framework provides a flexible method fo; handling default knowledge through its use of variable strength defaults which sheds some light on previously ambiguous examples. Indeed, the results suggest that some examples are inherently ambiguous. However, the clear underlying principle of the me-approach clarifies why this ambiguity arises, and suggests how it might be resolved.

2 Deriving the me-ranking

Consider a set of defaults, ~ = {ri : ai =? b;} where a, b, c, are formulre of a finite propositional language, C, with the usual connectives /\, v, ·, -+. The symbol, =?, denotes a default connective. The models of C are contained in the set M. A model , m E M, is said to verify a default, a =? b, if m f= a/\b. Conversely, a model, m, is said to falsify a default, a=? b, if m f= a 1\ ·b.

The semantics of defaults is given in terms of condi­ tional probabilities. Each default a =? b is supposed to constrain a set of probability distributions. For exam­ ple, if it were assumed that P( ·bla) = 0.05, then the set {a =? b} would define all those probability distributions which satisfied the constraint imposed by the default. However, in this context no actual conditional probabil­ ities are specified only the (fixed) relationships between the defaults in a given set.

The entropy of a probability distribution over a set of models M is given by

The problem is to select that probability distribution which maximises (1) subject to constraints imposed by the defaults. The main supposition underlying this for­ malism is that specifying relative orders of magnitude for the conditional probabilities corresponding to each default implies a similar order of magnitude description of the probabilities of each model. This is achieved by parameterising the conditional probabilities and examin­ ing the behaviour as the parameter tends to zero. Intu­ itively, this can be thought of as taking a set of assump­ tions to the extreme in order to ascertain what other information is implied. The intuitive interpretation of the relative orders of magnitude between defaults is that one is required to specify their relative strengths; that is, numerically higher strength defaults can be thought of as holding more strongly than, or as having priority over, those of lower strength. Note that the symbol "" will be used to denote asymptotic equality since, for the purposes of this analysis, it is only the asymptotic be­ haviour of the probabilities that is important not their actual values, nor indeed the actual value of entropy.

Goldszmidt et al. (1993] originally chose to use in­ equalities for the default constraints but were unable to obtain results except for a small class of default sets termed minimal core sets, which were guaranteed to sat~

isfy the constraints as equalities. As they pointed out, for minimal core sets, their algorithm is easily adapted to cater for variable strength defaults. For arbitrary sets, however, the algorithm is unsound and an analysis of the behaviour of the me-approach applied to variable strength defaults was not provided.

In this revised analysis, the maximum entropy ap­ proach is extended by insisting on working with strict equality constraints, at least up to asymptotic equiva­ lence. Specifying relative strengths for all defaults lim­ its the region of possible probability distributions from which the maximum entropy distribution is taken. Al­ though this requires a firmer commitment, that is, more information, from the knowledge engineer, it leads to me-solutions in a much larger number of cases.

Each default is assigned an associated strength, or or­ der of magnitude, relative to the other defaults. Asymp­ totically, the coefficients of conditional probabilities can be ignored and so only the relative orders of magnitude between models will be relevant. The strength of each default is therefore expressed as some power of a param­ eter c which has no significance other than linking all defaults together. Thus a default a => b will be said to have relative strength s iff P( -,bla) ,...., c 8 for some in­ teger s > 0. Letting c -t 0, the term € 8 -t 0 and so P(bla) -t 1, and the default becomes arbitrarily certain. In specifying a default, it is assumed that the knowl­ edge engineer is encoding information which he takes to be almost certain. Similarly, the probability of each model m will be assumed to be asymptotically equivalent to some non-negative integer power ~~:(m) of e:, so that P(m) ,..., e;"'(m) for ~~:(m) 2: 0. The constraints imposed on P by the defaults {ri} can be written as:

Using these constraints and the Lagrange multiplier technique to find the point of maximum entropy, Gold­ szmidt et al. [1993] derived the following elegant and simple approximation for the probability of each model

where the a; are related to the Lagrange multipliers for each rule. Making a further assumption that the a; can also be approximated by a relative order of magnitude, thus writing ai ,..., e;~<(r;), the probability expressions (3) are substituted back into the constraints (2) yielding 16.1 simultaneous equations with 16.1 unknowns, the ~~:(r;).

In the limit as e: -t 0 those models with the lowest powers of e: will dominate, and the constraints reduce to:

Given this ranking, ~~:(r;) , over defaults, the me-ranking over models, ~~:(m), can be found using equation (3). The me-rank of each model is given by the sum of the me­ ranks of those defaults it falsifies:

This completes the derivation of the maximum entropy ranking with ~~:(m) defining the me-consequence relation. The following section looks at conditions under which the assumptions used to find equations (4) and (5) are valid.

3 Robustness of rankings

In the above analysis, it was assumed that it was only necessary to consider the asymptotic behaviour of the defaults, and that fixing the relative strength of defaults in this way uniquely determined the me-ranking. It turns out that while this is not true in general, it is true for a useful class of problems which this section characterises. As an example of a case in which the assumptions are not true, consider the following where the probabilities (3) are used to consider what may happen when all defaults have the same strength but their coefficients are allowed to vary.

Example 3.1

The table shows whether a model falsifies or verifies each default and gives its (unnormalised) probability using equation ( 3):

Using the substitution u = 1 ~E, with all defaults having equal strength of 1, and letting their coefficients be c1, c2, c3, respectively, the constraint equations (2) give rise to three simultaneous equations:

Solving these for the a; in terms of u gives:

Now consider what happens asymptotically for various values of the coefficients.

Case 1: Let c1 = 2{c2 - c3) {for c2 > c3). This gives a solution of o 1 "' u, o2 "' 1, 03 "' u and leads to an me-ranking over defaults of {1,0,1). The corresponding me-ranking over models is given in the table below.

Case 2: Let c2 = c3 . This gives a solution of o 1 "'u, 02 "' u, 03 "' 1, and an me-ranking over defaults of {1,1,0). The corresponding me-ranking is given in the table below.

Case 3: Let c1 + c3 = c2. This gives a solution of o 1 "' u 2 , o 2 "' l, 03 "' u 2 and an me-ranking over defaults of {2,-1,2). The corresponding me-ranking is given in the table below.

Different choices for the coefficients clearly lead to com­ pletely different me-rankings over the defaults and, more importantly, over the models. This is because there are multiple solutions to the non-linear simultaneous equa­ tions given by {4) . In addition to having many solu­ tions, these equations may have no solution at all if the strength assignments represent inconsistent probabilistic constraints. However, for maximum entropy entailment to be well-defined, it is desirable to be able to determine when a unique solution to these equations can be found. This is guaranteed whenever the me-ranking is robust.

Definition 3.2 An integer ranking, K, over models is said to be robust 1 with respect to a set of defaults, { r i}, with associated strengths, {si}, if no two defaults share a common minimal falsifying model in K.

In the sequel, Vr (respectively, fr) represent minimal ver­ ifying (respectively, falsifying) models of r in "-· Simi­ larly, v~, (respectively, f;,) represent minimal verifying (respectively, falsifying) models of r' in K- 1 , and so on.

Definition 3.3 An integer rani ·1.g, K, over a set of de­ faults, {ri}, with associated strengths, {si}, is said to be me-valid with respect to that set if it satisfies (5) and for all r

Definition 3.4 Two me-valid rankings, K and K- 1 , are said to be distinct iff K( r) =f. K- 1 ( r) for some default r. Such a default is said to be distinctly ranked.

The following lemma shows that any distinctly ranked default, r, which has minimal K(/r) among distinctly ranked defaults, also has minimal K'{f;) among dis­ tinctly ranked defaults.

1 Adopting the use of "robustness" to indicate existence of a unique solution from [Bacchus et al., 1996].

Lemma 3.5 Given two distinct me-valid rankings, "' and K- 1 , if r is such that K( r) =f. K- 1 ( r) and for all r' with K(r') =f. K 1 (r'), K(/r') ~ K(/r), then K'(f;,) ~ K'{f;). Proof. Suppose otherwise, that is, there exists r' =f. r, such that K(r') =f. K'(r') with K(/r') ~ K(/r) but K'{f;) > K- 1 u;,). Without loss of generality, suppose that r' has minimal K'{f;,) among distinctly ranked defaults. Now, because K is me-valid, K(vr) + Sr = K(/r), and Vr can only falsify defaults, s, for which K(s) = K 1 (s), so that K(vr) = K'(vr)· It follows that

Similarly, since r' was chosen to have minimal ,, (!;,) among distinctly ranked defaults, K- 1 ( V~,) + Sr' = K- 1 {f;,), and v~, can only falsify defaults, s, for which K'{s) = K( s), and K- 1 ( v~,) = K( v~,). It follows that

Putting {7) and {8) together, K(/r) ~ K'(f;) > K'(f;,) ~ K(/r') ~ K(/r), which contradiction implies that K- 1 {f;,) ~ K- 1 {f;), as required. e

Theorem 3.6 Given a finite set of defaults, {ri}, with associated strengths, { si}, if a robust me-valid ranking, K, exists then it is unique.

Proof. Let K and K- 1 be distinct me-valid rankings and r be a distinctly ranked default with minimal K(/r) among distinctly ranked defaults and, by Lemma 3.5, mini­ mal K'{f;). Suppose that K is robust. Then fr fal­ sifies only r and other defaults, s, with K(s) = K'(s); also K( Vr) = K- 1 ( v~) since they only falsify non-distinctly ranked defaults, and, since both K and ,_, are me-valid, it follows that K(/r) = K'{f;) with K(r) =f. K'(r).

Consider K- 1 (/r) for which K- 1 {/r) ~ K- 1 {!;). But K'{f;) = K{fr) and fr falsifies only non-distinctly ranked defaults and r itself, for which K(r) =f. K'(r). Therefore K- 1 (/r) > K'{f;) and hence K'(r) > K(r) .

Now, iff; falsified no other distinctly ranked default, K(f;) < K'{f;) = K{/r), which contradicts fr being minimal in "-· This implies that J; must falsify some other distinctly ranked defaults and hence ,_, is not ro­ bust. Let these be r1 , r2, ... , rn; since all these ri are also minimal distinctly ranked defaults in K- 1 , by Lemma 3.5, they are also minimal in K and there must exist /r 1 , fr 2 , ··· , frn, minimally ranked falsifying models in K such that K(/r) = K(/r.) for all ri. Further, because K is robust, none of the /r; can falsify any other distinctly ranked defaults.

But, by the same argument as above, this implies that for all ri, K(ri) < K'(ri)· However, this in turn implies that J; which falsifies r, all the ri, and non-distinctly ranked defaults, must have a lower rank than fr in K, i.e., K{f;) < K'{f;) = K(/r), which contradicts fr being the minimal falsifying model of r in "-· Hence, "' cannot be robust either. It follows that, if two distinct me­ rankings exist, neither can be robust, and any robust me-valid ranking is unique. ·

Note that given two distinct rankings, "' and K 1 , it may still be the case that K(m) = K 1 (m) for all m, i.e., the ranking over models may be unique despite there being multiple solutions for the K(ri) to the constraint equa­ tions (5) and (6). For example, the set {r1 : a=> b, r2 : --.b => -.a}, produces the two equations

which have no solution unless s1 = s2 in which case there are an infinite number of solutions. However, all solutions lead to the same unique ranking over models. Refining the robustness condition and understanding its significance in such cases is the subject of ongoing re­ search.

4 Computing the me-ranking

Using the robustness condition and equation (4), it is possible to determine the me-ranking over defaults one by one. Robustness guarantees that for at least one de­ fault the currently computed minimal ranks of models are indeed their geimine ranks in the me-ranking.

Let the function MINV(r) (respectively, MINF(r)) be defined so that it returns the rank of the current min­ imal verifying model of r (respectively, the rank of the current minimal falsifying model of r excluding its own contribution) using equation (5). Then equation (6) can be re-written as

which in the algorithm is used to assign the rank of a default using

Algorithm to compute me-ranking

Input: a set of defaults, {r;}, and associated strength assignments, {s;}. Output: the me-ranking, K. ., or an exception if the set is p-inconsistent, or if the robustness condition is violated.

1. Initialise all K(r;) = oo.
2. From all r; with K(r;) = oo, find the minimal value of s; + MINV(ri) and select any r ; for which this holds, say r.
3. If MINV(r) = oo then the input set is p-inconsistent. Output an exception.
4. Find MINF(r) .
5. If MINF(r) = oo the robustness condition is violated. Output an exception.
6. Let K(r) := Sr + MINV(r)- MINF(r).
7. If any K(r;) = oo goto step 2.
8. Assign ranks to models using equation (5).
9. Validate the ranking by ensuring both that the constraints (4) and that the robustness condition are satisfied . Output either the me-ranking or an exception.

This algorithm clearly terminates at step 3, if the in­ put set is probabilistically inconsistent, or at step 5, or at step 9. Termination does not guarantee that a valid ranking has been found but this is checked for and re­ ported at step 9. The following theorem proves that, pro­ vided the robustness condition is satisfied, the algorithm will compute the unique me-ranking. That the algorithm works given certain pre-conditions can be verified if the two ranks in the assignment (10) can be shown to be valid. This requires that the ranks selected for MINV ( r) and MINF(r) when the assignment is made are indeed the minimal ranks for r.

Theorem 4.1 Given a finite set of defaults, {ri}, with associated strengths, { Si}, the algorithm computes the unique me-ranking, "'' if it is robust.

Proof. The theorem is proved by induction. On the first pass of the loop no rules have been ranked and so the ranks of each rule ranked (i.e. none) are correct. The inductive hypothesis assumes that at the nth pass of the loop all rules ranked in the previous ( n- 1) passes have been assigned their correct me-ranks. Consider that on the nth pass of the loop, rule r, with minimal Si + MINV(ri), is selected to be ranked.

Let Vc be a verifying model of r such that K( Vc) = MINV(r). Suppose that Vc is not a minimal verifying model of r, so there exists Vr, such that K(vr) < K(vc)· Now, K(vr) < MINV(r), the computed minimal verifying rank for r, so it must be the case that Vr falsifies some rule, r' =f. r, which has not yet been ranked, and since r' was not selected to be ranked in this pass of the loop it follows that

Then, since Vr falsifies r', K(/r') ~ K( Vr), in particular, using (6)

so that K( Vr') < MINV ( r'). It follows that Vr', too, must falsify some rule, r" =f. r' =f. r, which has not yet been ranked. Then, since Vr' falsifies r", K(/r") ~ K( Vr' ). Continuing in this way, an infinite descending chain of distinct unranked rules is constructed. This contradicts the finite size of the original default set, and therefore Vc must be a minimal verifying model of r.

Let fc be a falsifying model of r such that K(fc) = K(r) + MINF(r) . Suppose that fc is not a minimal fal­ sifying model of r, so there exists fr. such that K(jr) < K(fc)· Now, since K(jr)- K(r) < MINF(r), the com­ puted minimal falsifying rank for r, it must be the case that fr falsifies some rule, r' =f. r, which has not yet been ranked, and since r' was not selected to be ranked in this pass of the loop it follows that

Now, fr falsifies r', and under the assumption that the robustness condition holds, no two defaults share a common minimal falsifying model in the me-ranking. There­ fore, ,.(fr') < ,.(fr) , and the following inequality holds

so that K,(Vr') < MINV(r 1 ), the computed minimal ver­ ifying rank for r 1 · It follows that Vr' , too, must falsify some rule, r 11 :f: r 1 :f: r, which has not yet been ranked. Then, since Vr' falsifies r 11 , ,.(fr") :::; ,.( Vr'). Continuing in this way, an infinite descending chain of distinct un­ ranked rules is constructed. This contradicts the finite size of the original default set and therefore f c must be a minimal falsifying model of r .

Given that for the selected rule, r, the values MINV(r) and MINF(r) calculated at this pass of the loop repre­ sent the me-ranks of its minimal verifying and falsifying models (excluding its own contribution), respectively, it follows that the assignment

is valid and r is assigned its correct me-rank. The theo­ rem follows by induction. ·

5 Examples

In the first example, the solution is tabulated explictly to illustrate the method of finding the me-ranking but later this is omitted to save space.

Example 5.1 (Exceptional inheritance)

The intended interpretation of this knowledge base is that birds fly, penguins are birds, penguins do not fly and birds have wings; each r; has strength 8;. The ta­ ble shows whether a model falsifies or verifies each de­ fault. The column headed ,.(m) gives the me-rank of each model in terms of the ,.(r;) using equation (5).

Substituting the ~~:(m) into the reduced constraint equations ( 4) gives rise to:

Clearly, the only solution to these equations is ~~:(r1 ) = 81, ~~:(r2) = 81 + 82, ~~:(r3) = 81 + 83, and ~~:(r4) = 84.

To determine default consequences it is necessary to compare the ranks of a default's minimum verifying and falsifying models. Since the solution holds for any strength assignment ( 81, 82, 83, 84) , it follows that some default conclusions may hold in general. In particular, it can be seen that the default p 1\ b => ·f is me-entailed since

This result is unsurprising since p 1\ b => ·f is a pref­ erential consequence of ~. A more interesting general conclusion is p => w, which follows since

Again this result holds regardless of the strength assign­ ments and illustrates that, for this example, the inheri­ tance of w to p via b is uncontroversial. ·

Example 5.2 (Nixon diamond)

The intended interpretation is that quakers are paci­ ficists whereas republicans are not pacifists. Given a strength assignment of ( 81 , 82) is easily shown that ~~:(r1) = 81 and ~~:(r2) = 82. The classical problem associ­ ated with this knowledge base is to ask whether Nixon, being a quaker and a republican, is pacifist or not. This is represented by the default r 1\ q => p. The two relevant models to compare are r 1\ q 1\ p and r 1\ q 1\ ·P whose me-ranks in the general me-solution are

Clearly either r 1\ q => p or r 1\ q => ·p, or neither, may be me-entailed depending on the comparative strengths 81 and 82. This result is in accordance with the "intuitive" solution that no conclusion should be drawn regarding Nixon's pacifist status unless there is reason to suppose that one default holds more strongly than the other. In the case of one default being stronger, the conclusion favoured by the stronger would prevail. ·

Example 5.3 (Royal elephants/marine chaplains)

~ = { r1 : a => b, r2 : c => b, r3 : b => d, r 4 : a => ·d} There are two interpretations of this knowledge base. In the first, the propositions a, b, c, and d, stand for royal , elephant, african and grey, respectively; in the second, the propositions stand for chaplain, man, marine and beer drinker, respectively. The constraint equations ( 4) give rise to:

which have the unique solution ~~:(ri) = s1 + sg, ~~:(r2) = s2, ~~:(rg) = sg, and ~~:(r4) = sg + s4.

The key question relating to this knowledge base is "Are elephants which are both royal and african, not grey?", or alternatively, "Don't marine chaplains drink beer?" This translates into the default a 1\ c =? ·d which is me-entailed in general as can be seen from:

The result in this example is unambiguous, that is, it holds for all strength assignments 2 . However, [Touretzky et al., 1987] were not entirely happy about the conclusion that marine-chaplains do not drink beer. They argued that if the rate of beer drinking amongst marines was significantly higher than normal, then this might alter the behaviour associated with marine-chaplains.

Now, the default r5 : c =? d (marines drink beer) is in fact me-entailed by 6., but adding it to the database with all defaults having equal strength violates the ro­ bustness condition. If, however, rs were added with a higher strength, so that it represented a new constraint for the purposes of maximising entropy, a robust solution would result and the status of the default a 1\ c =? ·d would depend on the relative strengths s4 and ss.

So, Touretzky et al. were correct to suppose that if marines were heavier drinkers than men in general then it may not be clear whether marine chaplains are beer drinkers or not. However, it seems they were expect­ ing too much of a default reasoning mechanism (a path­ based inheritance reasoner in their case) in assuming it could draw such conclusions since this would involve us­ ing information which it had never been told. ·

It is interesting to note that many of the more complex examples from the literature (for example, see [Makin­ son and Schlechta, 1991]), which have been devised de­ liberately to overcome any intuitive biases, fail to satisfy the robustness condition when all defaults are assigned . equal strengths. If a set is probabilistically consistent it is usually possible to restore robustness by altering the strengths. This suggests that some sets may be too com­ plex for the human intuition to disentangle because they are ambiguous or underspecified. By requiring more in­ formation from the knowledge engineer, in terms of a strength assignment over defaults, some of these ambi­ guities can be cleared up and the hitherto implicit biases made explicit.

6 Conclusions

This paper has refined and extended the work of Gold­ szmidt et al. [1993] on applying the principle of maxi­ mum entropy to probabilistic semantics for default rules to enable it to be applied to a much wider class of default sets. A new algorithm was presented which finds the maximum entropy ranking for a set of variable strength defaults that satisfy a sufficient condition for a unique solution to exist. The output is a consequence relation based on a total ordering of models-a rational conse­ quence relation in the sense of Lehmann and Magidor [Lehmann and Magidor, 1992]. Some extreme technical cases remain to be investigated.

2 In fact all these examples have general solutions since they are minimal core sets as defined by Goldszmidt et al. [1993].

Using the me-approach for default reasoning provides the same benefits as its use in statistical problems. As Jaynes [1979] suggests, by encoding all known relevant information and finding the maximum entropy distribu­ tion, any observations which differ significantly from the result imply that other constraints, in this case defaults, exist. A closer approximation is obtained by adding more defaults or by adjusting the strengths. Instead of questioning the conclusions of a default reasoning sys­ tem, one should ensure that all relevant information has been encoded - the maximum entropy formalism en­ ables the precise and explicit representation of this as default knowledge. The main disadvantage of the me­ approach is its intractability, however, this extension to arbitrary sets has shed some light onto the causes of controversy among classical examples from the literature and pointed to ways of resolving them.