Specificity and Inheritance in Default Reasoning

1 Introduction

It has been proposed [Makinson, 1989; Kraus et al., 1990] that default reasoning systems be analyzed in terms of their (default) consequence relations. A number of in­ ference rules (or axioms) have generally been accepted [Pearl, 1991; Makinson, 1989] as a reasonable set of desiderata for a commonsense consequence relation. De­ spite the general acceptance of these desiderata, they fail to reconcile two accepted lines of reasoning, widely known as "inheritance" and "specificity" . These can be illustrated by the classical Tweety example as fol­ lows: Consider the database (Figure 1) containing four defaults, "penguins are birds", "penguins do not fly", "birds fly" and "birds have wings". "Specificity" tells us that if Tweety is a penguin, then Tweety does not fly be­ cause penguin is a more specific classification of Tweety than bird. "Inheritance", on the other hand, does equip Tweety with wings, by virtue of being a bird, albeit an exceptional bird with respect to flying ability.

*The research was partially supported by Air Force grant #AFOSR 90 0136, NSF grant #IRI-9200918, and Northrop­ Rockwell Micro grant #93-124.

The inheritance and specificity lines of reasoning de­ pend on the interactions among the defaults in the database. An inspection of the rules proposed in past desiderata reveals that, invariably, each rule refers to the defaults database as one unit ; no reference is made to specific subsets of defaults, the interaction among which produces the tension between inheritance and specificity. In this paper we propose a new rule, called coherence, that resolves this tension. Intuitively, the coherence rule prefers formulas that are more compatible with the de­ faults database. We will formalize the requirements of inheritance and specificity, and show that any conse­ quence relation that satisfies the coherence rule (and the standard desiderata) will honor both requirements. In the next section, we review the accepted desiderata (including rational monotony) [Pearl, 1991] before intro­ ducing the coherence rule. We will analyze the behavior of the closure of the extended desiderata which we call coherence closure.

In Section 3 we refine the semantics of system Z [Pearl , 1990) to satisfy the coherence rule. First we review the semantics of system Z and the definition of belief rank­ ings. Coherence constraints are then further imposed on admissible rankings to make them satisfy the coherence rule. We show that the resulting system is sound with respect to the extended desiderata. We also present a procedure for computing the most compact admissible belief ranking in the coherence closure. In the last sec­ tion we compare related work.

2 An Extended Desiderata

Normality defaults are formulas of the form cp--+ 'lj; where cp and 'lj; are wffs, and --+ is a new binary connective. cp is called the antecedent of the normality default and 1jJ is its consequent. The intended meaning of cp --+ 'lj; is

"typically if cp, then '1/J." We use a new symbol f-.- to represent a default consequence relation. The intended reading of cp f-.- 'ljJ is: given a set of facts (observations) cp, we can conclude by default 'lj;. We will also write ~ to represent the default consequence relation induced by the default data base ~.

2.1 The Standard Desiderata

Given a fixed set of defaults ~~ the desiderata for its default consequence relation f-.- are:

Rule 1 (Logic) If cp :J 'lj; 1 then cp f-.- '1/J.

Rule 2 (Cumulative) If cp f-.- 1, then cp f-.- 'ljJ if and only if cp 1\f f-.- 'ljJ.

Rule 3 (Cases) If cp f-.- 'ljJ and 1 f-.- '1/J, then cp V 1 f-.- '1/J.

Rule 4 (Direct Inference) If cp --> 'ljJ E ~~ then cp r- 7/>.

Rule 5 (Rational Monotony) If cp f-.- 'ljJ and it is not the case that cp f-.- 'I 1 then cp 1\ 1 f-.- 'ljJ.

Rules 1-5 above represent the standard desiderata which is supported by two different interpretations of de­ faults, probabilistic semantics [Adams, 1975; Pearl, 1991] and model preference semantics [Shoham, 1988]. The desiderata (excluding rational monotony) offers a com­ plete characterization [Adams, 1975; Pearl, 1991] of f.­ entailment, a consequence relation induced by inter­ preting each default sentence as a statement of condi­ tional probability assertion, infinitesimally removed from certainty. 1 By contrast, in model preference semantics a default cp --> 'ljJ is interpreted as "'1/J holds in all the most preferred worlds compatible with cp". It has been shown lLehmann, 1988] that the ability to represent preference among worlds by some numerical rank is a necessary and sufficient condition for the satisfaction of the desider­ ata. This confluence of two diverse interpretations offers a strong argument for the acceptance of the rules as a desiderata for default reasoning.

The logic rule says that logical conclusions are also default conclusions. The cumulative rule tells us that default conclusions are preserved when default conclu­ sions are added to or removed from the set of facts. The cases rule says that the default conclusions of two facts also follows from their disjunction. The direct inference rule allows us to conclude the consequent of a default regardless of the contents of the database when its an­ tecedent is all that has been learned. Finally, rational monotony captures the intuition that new observations ( 1) can be assumed to be "irrelevant" (does not affect the default conclusions) unless they are implausible to begin with.

1 In f-semantics, a default sentence is interpreted as a con­ straint on the infinitesimal conditional probabilities. The de­ fault conclusions are then the formulas that are forced to have extremely high probabilities by the constraints. Ra­ tional monotony is satisfied by restricting our attention to distributions .that are parameterized by f and are ana­ lytic in f. Alternatively, the interpretation of defaults as statements in nonstandard probability theory [Pearl, 1990; Goldszmidt and Pearl, 1991] also gives us rational monotony.

2.2 The Coherence Rule

The rationale for the coherence rule is that wffs (well formed formulas) that are more compatible with the de­ faults in ~ should be more believable and, in this pro­ posal, incompatibility is measured by the set of defaults that is falsified by the wff. A wff ¢ falsifies a default cp --> '1/J if ¢ :J cp 1\ ·'1/J and satisfies it if ¢ :J ( cp :J 'ljJ). Note that some defaults may neither be falsified nor sat­ isfied by a wff. The ~-partition (of the set of worlds 0) identifies the wffs whose degree of compatibility can be easily and unambiguously determined.

Definition 1 (~-partition) A set of wffs <I> is a ~­ partition if

1. for all d E ~ and ¢ E <I> 1 ¢ either falsifies or satisfies d,
2. for all w E nl we can find a ¢ E n such that w F ¢, and
3. w f= ¢; and w f= cPi implies that i = j.

The first requirement of the definition ensures that the status (falsified or satisfied) of each default is unambigu­ ous with respect to the members of <I>. The second and third requirements of the definition ensures that the sets of models of¢ is a partition of n.

We write <I>(~') to represent the element of <I> that falsifies precisely ~' ~ ~. Taking the set of falsified defaults as a measure of incompatibility, it is therefore reasonable to require that <I>(~') be judged more coher­ ent than <I>(~") whenever ~' C ~". Thus, if we know that either <I>(~') or <I>(~") is true, we should believe the former, written

Rule 6 further extends this requirement to hold in the context of every observation ¢:

Rule 6 (Coherence) Let ~' C ~" ~ ~ and ¢ be a wff. If¢ 1\ <I>(~') is satisfiable then

We will call the set of rules, 1 to 6, the extended desiderata.

The coherence rule turns out to be equivalent to a simple constraint on preferences among worlds. For no­ tational convenience, we will use the same symbol w to represent the world (the truth assignment on atomic propositions) and the conjunctive clause (a conjunction of literals, a wff) whose only model is w. We say a world w falsifies a default cp --> 'ljJ if w f= cp 1\ · '1/J. ~[w] rep­ resents the set of defaults in ~ falsified by the world w.

Theorem 1 (Coherence Constraints) Let fa be a default consequence relation that satisfies the desiderata. fa satisfies the coherence rule if and only if for all worlds w and V 1 ~[w] C ~[v] implies w V v faw.

This theorem follows from the fact that for every pair (w, ~' ~ ~)

The theorem tells us that for a default consequence rela­ tion satisfying the desiderata, conforming to the coher­ ence rule is equivalent to ensuring that worlds which are more compatible are considered more believable. This leads directly to a simple scheme for refining ranking systems (satisfying the desiderata) to make them sat­ isfy the extended desiderata. This will be considered in Section 3.

2.3 The Inheritance Rule

It is easy to show that the coherence rule ensures the inheritance of wings by penguins in the example of Fig­ ure 2. This example also shows that the coherence rule is not derivable from the standard desiderata. However, instead of focusing on a single example, we will propose a general formulation of the inheritance requirement and show that it is satisfied by any default system that sat­ isfies the extended desiderata.

The intuition behind inheritance reasoning is that since every member of a class is also a member of its superclass, the properties of the superclass should also be the properties of the class itself.

Rule 7 (Inheritance) Let~ be a data base of defaults of the form I -+ I' where I and I' are literals. If Ia -+ /1 -+ .. . In is a chain of defaults in ~ and ·I; is not the final consequent of another chain of defaults in ~ beginning with Ia for all i = 1, ... , n, then

2. Ia ~ln.

The inheritance rule says that if there is a chain of in­ creasingly general superclasses (or properties) Ia, ... , ln, then a member of Ia will inherit the properties of the superclasses until the chain of inheritance is "severed" by another contradictory chain. In the data base shown in Figure 2, the chain of rules

allows us to conclude that the penguin Tweety has wings. However, we cannot conclude that Tweety is mobile as the chain

is "severed" by the contradictory chain

This behavior is in general agreement with our intuitions.

The following theorem tells us that any default con· sequence relation that satisfies the extended desiderata supports inheritance of properties by subclasses.

Theorem 2 (Inheritance) Let~ be a data base of de­ faults of the form I -+ I' where I and I' are literals. If ~ satisfies the extended desiderata, then ~ satisfies the inheritance rule.

2.4 The Specificity Rule

Specificity arguments are usually defended by examples such as the one in Figure 2. We now cast these ar­ guments formally, as a general rule and show that any default consequence relation that satisfies the extended desiderata will satisfy the specificity rule as well.

Definition 2 (Specificity) A wff cp is more specific than cp' in ~, written cp > l1 cp', if cp ~ cp' and cp' ~ cp. Note that specificity is not limited to strict subclass re­ lationships; it is defined in terms of the consequence re­ lation itself which, being based on defaults, allows for exceptions and abnormalities. We say that a default cp -+ 'lj; is more specific than another cp' -+ 'lj;', written cp -+ 'lj; > l1 cp' -+ 'lj;' if its antecedent cp is more specific than cp'.

The specificity rule captures the intuition that , when two (possibly conflicting) defaults are applicable , the more specific default prevails. It is a generalization of the standard triangle penguin -+ bird -+ fly where the specificity penguin > l1 bird is dictated by a single de­ fault and yields penguin 1\ bird ~ ·fly. It turns out that , in this formulation, the specificity rule follows from the cumulative and direct inference rules.

Theorem 3 (Specificity) If f-- is a consequence re­ lation that satisfies the cumulative and direct inference rules, then f-- satisfies the specificity rule.

2.5 Other Examples

In addition to the standard penguin examples, a number of "particularly nasty" [sic] examples were considered in [Delgrande, 1994]. It was suggested that these examples illustrate some lines of reasoning that are intuitively de­ sirable for any default consequence relation. We will consider these lines of reasoning and show that every default consequence relation that satisfy the extended desiderata will handle them correctly. The first line of reasoning captures the intuition that defaults should be assumed to be independent and that they should be ac­ tivated whenever possible. Let ~ be a set of n default cp; -+ 'lj;;, i = 1, .. . , n. We write cpm and 1/!m to represent ;\";' cp; and ;\";' 1/!; respectively, for m = 1, ... , n .

This means that, although not all consequents can be true together, any proper subset of the consequents should still follow from their observed antecedents.

The next line of reasoning concerns the case where all the antecedents have been observed and it is known that at least one of the consequents is false; we should be adventurous and conclude that one and only one conse­ quent is false. This is the essence of the following rule.

The next rule says that if all the antecedents are true, a proper subset of false consequents should not interfere with the (default) conclusion of the other consequents.

While the independence rules are intuitive in the ex­ amples considered in [Delgrande, 1994], some may ar­ gue that there may be occasions when we will want to override these rules by more compelling considerations. For example if we discover an individual that falsifies all but one of the normality defaults, we may become con­ cerned about the whether this individual should not be treated as a class in itself, thus exonerated from inherit­ ing any of its class properties. However, we feel that in such extreme cases it should the burden of the knowledge provider (the programmer) to deviate from the normal style of knowledge representation and provide an explicit instruction for handling the case in question.

We agree with [Delgrande, 1994] that the above rules represent intuitive default inferences. The following the­ orem tells us that these inferences are guaranteed when­ ever we satisfy the extended desiderata.

Theorem 4 (Independence) If ~ satisfies the ex­ tended desiderata, then ~ satisfies rules 9 to 11.

3 Realizing the Extended Desiderata

Having axiomatized the desired behavior of a default consequence relation, we will now present an interpre­ tation of defaults that satisfies the extended desiderata. The approach is to extend system Z by adding con­ straints on admissible belief rankings. Since system Z has been shown to be characterized by Rule 1-5, the added constraints should enforce the coherence rule. We call this new system the coherence closure 2 of system Z.

3.1 Rankings and System Z: A Review

Definition 3 (Belief Rankings) A belief ranking ,.. is a non-negative integer function on the set of worlds n such that K(w) = 0 for some w E n. The belief rank of a wff cp is defined as:

Believability is associated with a lower rank and surprise or abnormality with a higher rank. Therefore, if K( cp) < K( 1/1), then cp is more believable than 1/J. A default cp --+ 1/J is interpreted as the constraint K(cpA1/;) < K(cpA·1/;) that is, cpA 1/J is more believable than cpA ·1/;. This leads to the notion ofadmissibility.

Definition 4 (Admissibility) A belief ranking ,.. zs admissible with respect to a defaults database ~' if

for every default cp--+ 1/J in ~. We say ~ is consistent if it has a ~-admissible belief ranking.

2 This new system may also be called a coherent rational closure to emphasize that the rational monotony rule is also satisfied by the system.

Each belief ranking,.. induces a default consequence re­ lation f;:-; where a f;:- ,6 if and only if K( a A ,B) < K( a A ·,6) . Given a defaults database, system Z bases its inference on the most compact belief ranking; the unique ranking that assigns the lowest possible rank to each world while respecting the admissibility constraints. This reflects the assumption that the worlds are considered to be as be­ lievable (normal) as possible. It can be shown that the most compact belief ranking (as well as any other specific ranking) induces a consequence relation that is charac­ terized by the desiderata (without the coherence rule).

3.2 The Coherence Closure

To support the inheritance line of reasoning, we now im­ pose coherence constraints on the admissible belief rank­ ings.

Definition 5 (Coherence) Given a defaults database ~' we say that world w is more coherent than world 11, writtenw <~ 11 if ~[w] C ~[11]. A ranking,.. is coherent if K( w) < K( 11) whenever w <~ 11.

We will write w < 11 when the defaults database ~ is not pertinent to the discussion. The transitivity of the co­ herence constraints follow directly from the transitivity of the subset relation.

Theorem 5 (Transitivity of Coherence) If w > w' and w' > w", then w > w".

As an illustration of coherence constraints, consider the standard example, ~ = {b--+ f,p--+ b,p--+ ·!}. Table 1 shows the defaults that are falsified by each of the world. The coherence constraints induced by ~ are bpf > bpf, bpf and w > bpf, bpf, bpf for all w with a non-empty ~[w] . Clearly not every ranking satisfy­ ing these constraints is admissible; we therefore require both the admissibility and coherence conditions of c­ admissibility.

Definition 6 ( C-Admissibility) Let ~ be a defaults database and let,.. be a belief ranking. ,.. is c-admissible with respect to ~ if,.. is both admissible and coherent. We say that ~ is c-consistent if~ has a c-admissible belief ranking.

Despite the addition of coherence constraints, c­ consistency turns out to be no different from consistency.

Theorem 6 (Consistency Equivalence) A set of de­ faults is c-consistent if and only if it is consistent.

In [Goldszmidt, 1992, p. 25], a procedure for testing the consistency of a database of defaults was presented. The procedure requires 0(1.6.1 2 ) satisfiability tests on the ma­ terial counterparts 3 of the defaults in b. [ Goldszmidt and Pearl, 1991]. Therefore the procedure is tractable for de­ faults databases that have Horn material counterparts [Dowling and Gallier, 1984].

As in system Z, we select the most compact belief ranking from the set of c-admissible rankings.

Definition 7 (The Kc Ranking) Let b. be a consistent set of defaults. A belief ranking Kc is the most compact c-admissible ranking if for all worlds w

for every K that is c-admissible with respect to b..

The following theorem shows that the most compact ranking is unique.

Theorem 7 (Minimization) Let K 1 and "-2 be belief rankings. If "-1 and "-2 are c-admissible, then K = min(K1, "-2) is c-admissible.

Definition 8 (Coherence Closure) Given a defaults database b., <p coherently entails '!/;, written <p ~'!/; if and only if

We call ~ the coherence closure of system Z.

Since ~satisfies Rule 1-5 [Pearl, 1990] and the coher­ ence constraints, it constitutes an interpretation of the extended desiderata (by Theorem 1).

3.3 Computing the Coherence Closure

The algorithm in Table 2 computes the most compact ranking relative to b. and requires an exponential num­ ber 0(2nn 2 ) of satisfiability tests where n is the size of b. . The key to computing the Kc ranking lies in the con­ struction of two non-negative integer-valued functions; a ranking zc( d) on the set of defaults b., and a ranking r( ¢) on the b.-partition of n, ct> = { ¢ = ct>(b..') 1 b.' ~ b.}. The zc rank records the minimal rank of worlds that verifies 4 a default while the r rank records the minimal rank required for c-admissibility. The ranking function ron the b.-partition ci> induces a belief ranking r(w) on n through the assignment

for every world w f= ¢.

The next theorem leads to a natural scheme of com­ puting the zc and r ranks.

Theorem 8 ( Goldszmidt [ Goldszmidt, 1992, The­ orem 2.4]) b. is c-consistent if and only if there is a default d E b.' such that d is toleraterf> by b.' for every non-empty subset b.' ~ b..

Given a c-consistent set of defaults D, we first compute the zc rank of every default that is tolerated by D and update the r ranking to ensure that it satisfies the re­ quirements for c-admissibility. Next we remove from D

3 The material counterpart of rp -+ '1/J is the wff rp :J '1/J.

4 A world w verifies a rule rp -+ '1/J if w I= rp A '1/J.

5 A default rp -+ '1/J is tolerated by a set S if the wff rp A '1/J /\; rp; :J '1/J; is satisfiable (where i ranges over all the rules inS) .

the default that has the smallest zc rank. We repeat this procedure until all the defaults have been removed.

Some terminology used in the procedure: We define .6.(¢;] = b.' whenever ¢; = ct>(b..'). If .6..(¢;] C .6..(</Jj], then ¢; is an ancestor of <Pi. The minimal ancestors of ¢; are its parents, and ¢; is a successor of its ancestors and a child of its parents. Procedure c-rank assigns a rank r( ¢;) to satisfiable formulas of the form ¢; = ct>( b.') where b.' ~ b.. The procedure assumes that the formulas ¢; are ordered such that every ¢; has a smaller index i than all its successors and a larger index than all its ancestors . Thus <Po = ct>(0) and <Pn = ci>(b..).

The following theorem tells us that the ranking r is precisely the Kc ranking.

Theorem 9 (Rank) The belief ranking as computed by procedure c-rank is precisely the most compact c­ admissible ranking Kc.

4 Discussion and Conclusion

Coherence closure may be viewed as a refinement of ce­ teris paribus ( cp) admissibility condition proposed in [Tan, 1994]. In addition to being admissible, a cp­ admissible ranking must satisfy additional constraints, requiring a world w to be ranked lower than a world v whenever there is a subset b.' C b. such that w verifies all the defaults in b.', v falsifies all the defaults in b.' and w and 11 agree on all the other defaults in b.\ !::.'. Clearly every cp-condition is also a coherence constraint, but not the converse.

Motivated by Brewka's preferred subtheories [Brewka, 1989], Boutilier [Boutilier, 1992] proposed an alternative way of resolving the tension between specificity and in­ heritance. Each default is assigned a priority and the set of defaults b. is partitioned into {b.;} according to their priorities. Given two worlds w and 11, attention is focused on the maximum priority (i = max(w, 11)) subset of de­ faults b..i where either b..i[w] C .6.;(11] or .6..;(11] C b..i[w]. The world that falsifies a smaller set of defaults , say w, is then considered strictly more believable than the other world, 11. Since b..[w] C .6.(11] implies b..i[w] ~ .6..;(11] for all i and b..i[w] C .6.;(11] for some i, it should be clear that if w < 11 is a coherence constraint, then w will also be considered strictly more believable than 11 by [Boutilier, 1992] . The converse however is not true and is not de­ sirable in general. The reason is that by comparing only the maximum priority subset of defaults b..max(w,v) an implicit interpretation is imposed on the priorities. The implicit interpretation is that the violation of a default with priority i is somehow more "damaging" than the vi­ olation of any number of defaults of lower priority. While [Brewka, 1989] gives little indication of the source of the priorities, [Boutilier, 1992] equates the priority of a de­ fault to the Z rank [Pearl, 1990] of the negation of its material counterpart. In the following analysis we will attempt to show that the implicit interpretation of pri­ orities when compounded with equating priorities to the Z rank of the negated material counterpart lead to coun­ terintuitive inferences.

Consider the familiar example containing the defaults s -+ a ("students are typically adults"), a -+ e ("adults

1) r(¢o) = 0 2) For i from 1 to n 3) r(¢;) = max{r(¢j) + 11 ¢i E parent(¢;)} 4) Let D = ~ 5) While D -j 0 6) Let Dt be the set of defaults tolerated by D 7) For d = cp--+ 1/J E Dt 8) /d = cp/\1/JI\{cp; :J 1/J; I cp; -t 1/J; ED} 9) zc(d) = min{r(¢;) 1 ¢; "/d is satisfiable} 10) For i from 1 to n 11) if dE~[¢;] then 12) r(¢;) = max{r(¢;), zc(d) + 1), r(¢j) + 11 ¢i E parent(¢;)} 13) Remove from D a default in Dt with the lowest zc rank

are typically employed") and s --+ ·e ("students are typ­ ically not employed") to which we add a fourth default x ---+ e where x is arbitrary. Since s --+ ·e has prior­ ity 2 and x --+ e has priority 1, violation of the default "students are typically not employed" is considered to be more "damaging" than the violation of the default "x's are typically employed" in [Boutilier, 1992]. This is counterintuitive as this conclusion is obtained indepen­ dently of the meaning of x. Thus even if x represents the statement "sells hamburgers in MacDonald's", violation of this statement is still considered less "damaging" than the violation of the default "students are typically not employed". Such counterintuitive behavior is not present in our semantics.

In [Delgrande, 1994], an approach based on preference orderings between worlds was presented. Beginning with an extant theory of default conditionals, any default that is true in this original theory prefers a world in which the material counterpart is true over a world in which it is false. In the new theory, a preference between two worlds is true when it can be attributed to some default and there is no more specific default that has a contradictory preference. The notion of specificity is also defined in terms of the truth of defaults in the original theory. This reliance on an extant theory of defaults make the system unnatural and complex. The intuitiveness of such a two step definition of a default theory is questionable and lacks a good philosophical justification. It is also not known if the desiderata is satisfied by the system.

In [Geffner, 1989], inference rules 1 to 4 were supple­ mented by an irrelevance rule which, unfortunately, in­ volves the evaluation of a meta-logical irrelevance pred­ icate I(-) . The proposed default consequence relation called conditional entailment was also shown to satisfy inference rules 1 to 4 together with irrelevance rule. Con­ ditional entailment like coherence closure is also defined in terms of preferences among worlds. The preference among worlds, in turn, depends on a priority relation among normality defaults specified by the user . It turns out that if the priority relation is empty (i .e. all de­ faults have the same priority) then conditional entail­ ment turns out to be equivalent to coherence closure.

Much work in default reasoning has been guided by examples rather than on generally accepted principles of reasoning. We hope our general formalization of no­ tions such as specificity, inheritance and coherence will help change this trend. It remains to be seen, though, whether the extended desiderata is sufficient for captur­ ing other patterns of plausible reasoning.

Acknowledgments

We would like to thank the anonymous reviewers for their constructive comments and suggestions. The first author is supported in part by a scholarship from the National Computer Board, Singapore.