On Interacting Defaults

ON INTERACTING DEFAULTS

Raymond Reiter and Giovanni Criscuolo

Department of Computer Science The University of British Columbia

ABSTRACT

Although most commonly occurring default rules are normal when viewed in isolation, they can interact with each other in ways that lead to the derivation of anomalous default assumptions. In order to deal with such anomalies it is necessary to re-represent these rules, in some cases by introducing non-normal defaults. The need to consider such potential interactions leads to a new concept of integrity, distinct from the conven­ tional integrity issues of first order data bases.

The non-normal default rules required to deal with default interactions all have a common patter~ Default theories conforming to this pattern are considerably more complex than normal default theories. For example, they need not have exten­ sions, and they lack the property of semi-monoto­ nicity.

I INTRODUCTION

In an earlier paper [Reiter 1980a) one of us proposed a logic for default reasoning. The objec­ tive there was to provide a representation for, among other things, common sense facts of the form "Most A's are B's", and to articulate an appropri­ ate logic to characterize correct reasoning using such facts.* One such form of reasoning is the derivation of default assumptions: Given a particu­ lar A, conclude that "This particular A is a B". Because some A's are not B's this conclusion must be treated as a default assumption or belief about the world since subsequent observations in the world may yield that "This particular A is not a B". The derivation of the belief that "This particular A is a B" is a form of plausible reasoning which is typically required whenever conclusions must be drawn from incomplete information about a world.

It is important to note that not all senses of the word "most" lead to default assumptions. One can distinguish two such senses:

This paper was written with the financial support of the National Science and Engineering Research Council of Canada under grant A7642.

* Other closely related work with much the same motivation is described in [McCarthy 1980), [McDer­

mott 1980) and [McDermott and Doyle 1980).

Istituto di Fisica Teorica University of Naples

1. A purely statistical connotation, as in "Most voters refer Carter." Here, "most" is being used exclusively in the sense of "the majority of". This setting does not lead to default assumptions: given that Maureen is a voter one would not want to assume that Maureen prefers Carter. Default logic makes no attempt to represent or reason with such statistical facts.

2. A prototypical sense, as in "Most birds fly." There is a statistical connotation here - the majority of birds do f1y - but there is also the sense that a characteristic of a prototypical or normal bird is being described. Given a bird Polly, one is prepared to assume that it flies unless one has reasons to the contrary.* It is towards such prototypical settings that default logic is addressed.

The concept of a prototypical situation is central to the frames proposal of [Minsky 1975) and is realized in such frame inspired knowledge repre­ sentation languages as KRL [Bobrow and Winograd 1977] and FRL [Roberts and Goldstein 1977). That these are alternative representations for some underlying logic has been convincingly argued in [Hayes 1977). Default logic presumes to provide a formalization of this underlying logic.

The approach taken by default logic is to distinguish between prototypical facts, such as "Typically mammals give birth to live young", and "hard" facts about the world such as "All dogs are mammals." The former are viewed as rules of inf e­ rence, called default rules, which apply to the latter "hard" facts. The point of view is that the set of all "hard" facts will fail to completely specify the world - there will be gaps in our know­ ledge - and that the default rules serve to help fill in those gaps with plausible but not infalli­ ble conclusions. A default theory then is a pair (D,W) where D is a set of default rules applying to some world being modelled, and W is a set of "hard" facts about that world. Formally, W is a set of first order formulae while a typical default rule of D is denoted

* One way of distinguishing between these two

senses of "most" is by replacing its setting using the word "typically". Thus, "Typically voters prefer Carter" sounds inappropriate, whereas "Typically birds fly" seems more accurate. In the rest of this paper we shall use "typically" when­ ever we are referring to a prototypical situation.

where a(*), Sl(*), ... ,Sn<*), w(*) are all first ord~r formulae whose free variables are among those of x = xl·····Xm· Intuitively, this default rule is interpreted as saying "For all individuals xl·····xm, if a(*) is believed and if each of Sl(X), ... ,Sn(X) is consistent with our beliefs, then w(X) may be believed." The set(s) of beliefs sanc­ tioned by a default theory is precisely defined by a fixed point construction in [Reiter 1980a]. Any such set is called an extension for the default theory in question, and is interpreted as an accep­ table set of beliefs that one may entertain about the world being represented.

It turns out that the general class of default theories is mathematically intractable. According­ ly, many of the results in [Reiter 1980a] (e.g. that extensions always exist, a proof theory, conditions for belief revision) were obtained only for the class of so-called normal default theories, namely theories all of whose defaults have the form

Such defaults are extremely common; for example "Typically dogs bark.:

DOG (x) : M BARK(x)

BARK(x)

"Typically American adults own a car.":

AMERICAN(x) " ADULT(x) : M((Ey) .CAR(y) "OWNS(x,y))

(Ey).CAR(y) "OWNS(x,y)

Many more examples of such normal defaults are des­ cribed in (Reiter 1980a]. Indeed, the claim was made there that all naturally occurring defaults are normal. Alas, this claim appears to be true only when interactions involving default rules are ignored. For normal default theories such inter­ actions can lead to anomalous conclusions.

It is the purpose of this paper to describe a variety of settings in which interactions involving defaults are important, and to uniformly generalize the notion of a normal default theory so as to cor­ rectly treat these interactions. The resulting semi-normal default theories will then be seen to lack some important properties: for example they need not have extensions, and they lack the semi­ monotonicity property which all normal theories en­ joy. We shall also see that the interactions in­ troduced by default rules lead to a new concept of data base integrity, distinct from the integrity issues arising in first order data bases.

This paper is an abridged version of [Reiter and Criscuolo 1980].

II INTERACTING NORMAL DEFAULTS

In this section we present a number of examples of default rules which, in isolation, are most naturally represented as normal defaults but whose interaction with other defaults or first order for­ mulae leads to counterintuitive results. In each case we show how to "patch" the representation in order to restore the intended interpretation. The resulting "patches" all have a uniform character, which will lead us in Section TIIB to introduce the notion of a semi-normal default theory.

These are both normal defaults. Default logic then admits the conclusion that "Typically A's are C's" in the following sense: If a is an individual for which A(a) is known or believed, and if -B(a) and -c(a) are not known or believed, then C(a) may be derived. In other words, normal default theories impose transitivity of "typically". But this need not be transitive, for example:

From these one would not want to conclude that "Typically high school dropouts are employed."* Transitivity must be blocked. This can be done in general by replacing the normal default (2.2) by fue non-normal default

To see why this works, consider a prototypical in­ dividual a which is an A i.e. A(a) is given. By (2.1) B(a) can be derived. But B(a) cannot be used in conjunction with (2.4) to derive C(a) since the consistency condition -A(a) " C(a) of (2.4) is vio­ lated by the given A(a). On the other hand, for a prototypical individual b which is a B (i.e. B(b) is given) (2.4) can be used to derive C(b) since pre­ sumably nothing is known about b's A-ness -we do not know that A(b) - so that the consistency condi­ tion of (2.4) is satisfied.

The introduction of non-normal defaults like (2.4) is a particularly unpleasant solution to the transitivity problem, for as we shall see in Sedjon IIIB, the resulting non-normal default theories lack most of the desirable properties that normal theories enjoy. For example, they sometimes fail to have an extension, they lack semi-monotonicity, and their proof theory appears to be considerably more complex than that for normal theories. Accor­ dingly, to the extent that it can be done, we would prefer to keep our representations "as normal as possible." Fortunately transitivity can be blocked using normal defaults whenever it is the case that in addition to (2.1) and (2.2) we have "Typically B's are not A's". This is the case for example (2.3): "Typically adults are not high school drop­ outs". Under this circumstance, the following nor­ mal representation blocks transitivity:

* Nor would we want to conclude that "Typically high school dropouts are not employed." Rather we would remain agnostic about the employment status of a typical high school dropout.

Notice how, whem given that B(a), a simple back­ chain ing interpreter would establish the goal C(a) . Back-chaining into (2 . 7) yields the subgoal B(a) " - A(a). This splits into the subgoal B(a), which is given and hence solved, and the subgoal "A(a) . This latter back-chains into (2.6) yielding the subgoal B(a) whi ch is solved. There remains only t o ve rify the consistency requirements associ­ ated with the defaults (2.6) and (2.7) entering mto the proof i.e. to verify that {C(a), - A(a)} is con­ sistent with all of the first order formulae in fo r ce . Such a back-chaining default reasoner is an i ncomplete realization of the complete proof proce­ dure of (Reiter 1980a). The reader might find it instructive to simulate this back-chaining inter­ preter for the case that A(a) is given, in order to see how a derivation of C(a) is prevented.

Notice also that the representation (2.5), (2.6) and (2.7) yields a very interesting predic­ tion. Given an individual a which is simultaneously an instance of A and B, nothing can be concluded about its C-ness. This prediction is confirmed with respect to example (2.3): Given that John is both a high school dropout and an adult, we do not want to assume that John is employed. Notice that the non­ normal representation (2.1) and (2.4) yields the same prediction. We shall have more to say about defaults with common instances of their prerequi­ si t es in Section IIC.*

A somewhat different need for blocking transi­ tivity arises when it is the case that "Typically A's are not C's" i.e. in addition to (2.1) and (2.2) we have

For example,

Under these circumstances, consider a prototypical i nstance a of A. By (2.1) and (2.2) C(a) can be der ived. But by (2.8) - C(a) can be derived. This means that the individual a gives rise to two diff­ erent extensions for the fragment default" theory (2.1), (2.2) and (2.8). One of these extensions­ the one containing C(a) - is intuitively unaccep­ table; only the other extension - the one containing - C(a) - is admissible. But a fundamental premise of default logic is that ~ extension provides an accept ab l e se t of beliefs about a world. The prob­ l em then is to eliminate the extension containing C(a) . This can be done by replacing the normal de­ fau lt (2.2) by the non-normal (2.4), exactly as we did earlier i n order to block the transitivity of "typically". Now, given A(a), B(a) can be derived from (2.1), and - C(a) from (2.8). C(a) cannot be derived using (2 .4) s ince its consistency require­ ment is violated. On the other hand, given a proc0-

is a default rule then a(!) is its prerequisit e .

typical instance b of B, C(b) can be derived using (2. 4).

Once again a non-normal default has been intro­ duced, something we would prefer to avoid. As before, a normal representation can be 'found when­ ever it is the case that "Typically B's are not A's". This is the case for example (2. 9) : "Typi­ cally adults are not university students". Under this circumstance the following normal representa­ tion will do:

Notice that this representation predicts that any individual which is simultaneously an instance of A and B will be an instance of not C, rather than an instance of C. This is the case for example (2.9): Given that Maureen is both a university sor dent and an adult one wants to assume that Maureen is not employed.

Figure 2.1 summarizes and extends the various cases discussed in this section. The first three entries of this table are unprobl~~tic cases which were not discussed, and are included only for completeness.

B. Interactions Between "All" and "Typically"

Phenomena closely related to those stemming f rom the non-transitivity of "typically" arise from interactions between normal defaults and certain universally quantified first order formulae. Con­ sider

Default logic forces the conclusion that "Typically A's are C's" in the sense that if a is a prototypical A then it will also be a C. But this con­ clusion is not always warranted, for exampl€: "All 21 year olds are adults." } "Typically adults are married." (2.12)

Given that John is a 21 year old, we would not want to conclude that he is married. To block the un­ warranted derivation, replace (2.11) by

As was the case in Section IIA the introduction of this non-normal default can be avoided whenever it is the case that "Typically B's are not A's"* by means of the representation (2.10) together with

Notice that this representation, as well as fue representation (2.10) and (2.13) predicts that no conclusion is warranted about the C-ness of any given common instance of A and B.

that tion A related problem arises when "Typically A's are not C's" so to (2.10) and (2.11) we have it is the case that, in addi-

For example:

"All Quebecois are Canadians."

"Typically Canadians are native English speakers."

"Typically Quebecois are not native English

speakers."

As in Section IIA, a prototypical instance a of A will give rise to two extensions for the theory (2.10), (2.11) and (2.15), one containing C(a); the other containing - C(a). To eliminate the extension con­ taining C(a), replace (2.11) by (2.13).

As before, the introduction of the non-normal default (2.13) can be avoided whenever it is the case that "Typically B's are not A's", by means of the representation (2.10), (2.14) and (2.15).

Figure 2.2 summarizes the cases discussed in this section. The first three entries of this table are unproblematic cases which were not dis­ cussed, and are included only for completeness.

C. Conflicting Default Assumptions : Prerequisites with Common Instances

In this section we discuss the following pat­ tern, in which a pair of defaults have contradictacy consequents but whose prerequisites may share common instances*:

* Note that example (2.12) seems not to have this character. One is unlikely to include that "Typi­ cally adults are not 21 years old" in any represen­ tation of a world.

The problem here is which default assumption (if any) should be made when given an instance a of both A and B i.e. should C(a) be assumed, or - C(a) or neither? Two cases have already been considered: 1. If it is the case that all A's are B's, then row 6 and possibly row 7 of Figure 2.2 provide represen-

is a default rule, then a(}t) is its prerequisite and w("it) its consequent.

tations; in both - C(a) is derivable whenever A(a) and B(a) are simultaneously given.

2. If it is the case that "Typically A's are B's" then row 6 and possibly row 7 of Figure 2.1 provide representations in both of which - C(a) is deriv­ able given A(a) and B(a).

The problematic setting is when there is no entailment relationship between A and B. For example:

Now, given that John is both a Quaker and a Republi­ can, we intuitively want to make no assump.tions about his warlike nature. This can be done in the general case by replacing the representation (2.16) by the non-normal defaults

This representation admits that a typical A is not a C, a typical B is a C, but a typical A which is also a B leads to no conclusion.

When it is the case that "Typically A's are mt B's" and "Typically B's are not A's" the non-normal defaults (2.18) can be replaced by the following normal ones:

This appears to be the case for example (2.17):

"Typically, Republicans are not Quakers."

"Typically, Quakers are not Republicans."

It is not always the case that the pattern (2.16) should lead to no default assumptions for common instances of A and B. Consider:

"Typically full time students are not employed." "Typically adults are employed."

Suppose that John is an adult full time student. One would want to assume that he is not employed. So in general, given the setting (2.16) for which the default assumption - C is preferred for common instances of A and B, use the following non-normal representation:

Whenever, in addition, it is the case that "Typi­ cally B's are not A's", use the following normal representation:

III DISCUSSION

In this section we discuss some issues raised by the previous results of this paper. Specifically, we address the question of data base integrity ari­ sing from default interactions, as well as some of the formal problems associated with the non-normal default rules introduced to correctly represent these interactions. We conclude with a brief dis­ cussion of semantic network representations for de­ fault reasoning.

A. Integrity of Default Theories

A very nice feature of first order logic as an Artificial Intelligence representation language is the extensibility of any theory expressed in this language. That is, provided that some axiomatiza­ tion of a world has that world as a model (so that the axiomatization faithfully represents certain aspects of that world) then the result of adding a new axiom about the world is still a faithful rep~­ sentation. It is true that specialized deduction mechanisms may be sensitive to such updates (e.g. adding a new "theorem" to a PLANNER-like data base); but semantically there is no problem. Unfortunately, as we have seen, default theories lack this semantic extensibility; the addition of a new default rule may create interactions leading to unwarranted con­ clusions, even though in isolation this rule appears perfectly correct.

This observation leads to a new concept of data base integrity, one with quite a different character than the integrity issues arising in data base management systems [Hammer and McLeod 1975) or in first order data bases [Nicolas and Yazdanian 1978, Reiter 1980b). For such systems an integrity con­ straint specifies some invariant property which every state of the data base must satisfy. For ex­ ample, a typical integrity constraint might specify that an employee's age must lie in the range 16 to 99 years. Any attempt to update the data base with an employee age of 100 would violate this constraint. Formally one can say that a data base satisfies some set of integrity constraints if the data base is logically consistent with the constraints. The role of integrity constraints is to restrict the class of models of a data base to include as a model the par­ ticular world being represented. Now the objective of the default representations of Section II had precisely this character; we sought representations which would rule out unwarranted default assumptions so as to guarantee a faithful representation of real world common sense reasoning. But notice that there was no notion of an integrity constraint with which the representation was to be consistent. Indeed, consistency of the representation cannot be an issue at all since ~ default theory will be consistent provided its first order facts are [Reiter 1980a, Corollary 2.2]. It follows that, while there is an integrity issue lurking here, it has a different nature than that of classical data base theory.

We are thus led to the need for some form of integrity maintenance mechanism as an aid in the de­ sign of large default data bases. The natural ini­ tial data base design would involve representing all default rules as normal defaults, thereby ignoring those potential interactions of the kind analyzed in Section II. An integrity maintenance system would then seek out possible sources of integrity viola­ tions and query the user as to the appropriate de­ fault assumptions to be made in this setting. Once the correct interpretation has been determined, the system would appropriately re-represent the offend­ ing normal default rules. For example, when con­ fronted with a pair of default rules of the form (2.16), the system would first attempt to prove that A and B can have no common instance i.e. that W u {(Ex).A(x) A B(x)} is inconsistent, where W is the set of first order facts. If so, this pair of defaults can lead to no integrity violation. Other­ wise the system would ask whether a common instance of A and B is typically a C, a - C, or neither, and depending on the response would suitably re­ represent the pair (2.16), if necessary by non­ normal default rules.

B. Semi-Normal Default Theories

In Section II we had occasion to introduce cer­ tain non-normal default rules in order, for example, to block the transitivity of "typically". Inspec­ tion of the representations of that section will ~ veal that all such non-normal default rules share a common pattern; they all have the form A(x) : M(- B(x) A C(x))

C(x)

Accordingly, it is natural to define a default rule to be semi-normal iff it has the form

where a, e and w are formulae of first order logic with free variables among 1 = Xl·····xm. A default theory is semi-normal iff all of its default rules are semi-normal. Normal default rules are a special case of semi-normal, in which e(i) is the identi­ cally true proposition.

(Reiter 1980a] investigates the properties of normal default theories. Among the results obtained there are the following:

1. Every normal theory has an extension.
2. Normal theories are semi-monotonic i.e. if D1 and D2 are sets of normal default rules and if E1 is an extension for the theory (Dl, W), then the theory (Dl u D2, W) has an extension E2 such that E1 ~ E2.

One consequence of semi-monotonicity is that one can continue to maintain one's old beliefs when­ ever a normal theory is updated with new normal de­ faults. Another is a reasonably clean proof theory.

Unfortunately, semi-normal default theories ar joy none of these nice properties. For example, the following theory has no extension:

To see that semi-monotonicity may fail to hold for semi-normal theories consider the theory

This has unique extension Th({B}) where, in general, Th(S) is the closure of the set of formulae S under first order theoremhood. If the new default rule

: M - A

- A is added to this theory a new theory is obtained with unique extension Th({- A}) and this does not contain Th({B)).

Most of the formal properties of semi-normal default theories remain unexplored. Two problems m particular require solutions: Under what conditi~ are extensions guaranteed to exist, and what is an appropriate proof theory?

C. Default Inheritance in Hierarchies: Network Representations

In Section II we focused on certain fairly simple patterns of default rules. Our choice of these patterns was conditioned by their frequent occurrence in common sense reasoning, and by the fact that they are typical of the kinds of default knowledge which various "semantic" network schemes presume to represent and reason with. Most such networks are designed to exploit the natural hier­ archical organization of much of our knowledge about the world and rely heavily for their inferencing power upon the inheritance of properties associated with a general class "down the hierarchy" to more restricted classes.

Space limitations prevent a thorough discussion of the relationship between the considerations of this paper and network representations for default reasoning. Instead we summarize various conclusions which are argued at length in [Reiter and Criscuolo 1980]:

1. Except in the simplest of settings, network in­ terpreters fail to reason correctly with defaults.
2. Network representations are best viewed as in­ dexing schemes for logical formulae. An impor­ tant role of indexing is the provision of an efficient path tracing heuristic for the consis­ tency checks required by default reasoning.
3. Such consistency checks are examples of the kind of resource limited computations required in common sense reasoning (Winograd 1980].

IV CONCLUSIONS

Default theories are complicated. Unlike theories represented in first order logic, default theories lack extensibility. Whenever a new default rule is to be added to a representation its poten­ tial interactions with the other default rules must be analyzed. This can lead to a re-representation of some of these defaults in order to block certain unwarranted derivations. All of which leads to a new concept of data base integrity, distinct from the integrity issues arising in first order data bases. These observations also suggest the need for a default integrity maintenance system as a tool for aiding in the design of large default data bases. Such a system would seek out potentially interacting defaults during the data base design phase and query the designer about the consequences of these inter­ actions.

Semi-normal default theories are complicated. They have none of the nice properties that make nor­ mal theories so appealing. Most of their formal properties are totally unexplored. At the very least a proof theory is needed, as well as condi­ tions under which extensions are guaranteed to E-Yist.

ACKNOWLEDGEMENTS

Many of the results and examples of this paper were inspired by a conversation that one of us (R.R.) had with N. Sridharan one afternoon in Vancouver. It was he who first pointed out to us the need for non-normal defaults in common sense reasoning.

This work was done with the financial assis­ tance of the National Science and Engineering Re­ search Council of Canada grant A7642. G. Criscuolo was sponsored by the Council for a six month re­ search position with the Department of Computer Science at the University of British Columbia.