A Clash of Intuitions: The Current State of Nonmonotonic Multiple Inheritance Systems

1. Introduction

Early attempts at combining multiple inheritance with exceptions were based on straightforward extensions of tree­ structured inheritance systems, and were theoretically un­ sound. Two well-known examples are FRL [Roberts and Goldstein 1977] and NETL [Fahlman 1979]. In The Math­ ematics of Inheritance S11stems, or TMOIS, Touretzky de­ scribed two classes of problems that these systems cannot handle [Touretzky 1986]. One involves reasoning with true but redundant assertions; the other involves ambiguity.

TMOIS provided the definition and analysis of a the­ oretically sound multiple inheritance system, along with some inference algorithms based on parallel marker prop­ agation. Other definitions for inheritance have since been proposed in [Sandewall1986] and [Horty et al. 1987] that are equally sound and intuitive, but do not always agree with the system defined in TMOIS. At the heart of the con­ troversy is a clash of intuitions about certain fundamental issues in inheritance reasoning. In this paper we catalog the issues, map out a design space, and describe some in­ teresting properties that result from various choices of def­ initions. Just as there are alternative logics, there may be no single "best" approach to nonmonotonic multiple inher­ itance.

Thia material ia baaed on work aupported by the National Science Foundation under Grant No. IST-8516313.

2. Bulc Terminology

An Inheritance network is a labeled directed graph whose nodes represent individuals and classes, and whose links denote various relations between the nodes. The pri­ mary relation is the IS-A link, which is written as z -+ II· Links of form z f+ J1 are called IS-NOT-A links. If a is an individual and p and q are classes, the links a -+ p and a f+ q have straightforward logical interpretations as the sentences p(a) and- q(a), respectively. Links between classes, such as p -+ q and p f+ q, have no fixed logical interpretation; they might represent sentences in a first or­ der, default, or nonmonotonic logic, depending on the type of inheritance system in which they appear.

A tree-atructured Inheritance system is one whose nodes and IS-A links form a tree. In contrast, a multi­ ple inheritance system does not restrict nodes to hav­ ing at most one immediate superior; typically the only re­ quirement is that the inheritance graph (or at least the IS-A subgraph) must be acyclic. Acyclic multiple inheri­ tance graphs are sometimes referred to as "tangled hierar­ chies" [Fahlman 1979].

A bipolar inheritance system is one that contains both positive (-+) and negative (I+) links. A unipolar sys­ tem contains only positive links, and therefore cannot di­ rectly express negative statements such as "Clyde is not a cabbage." (One can represent negative statements indi­ rectly in a unipolar system by creating a positive link to a "non-cabbage" node, but unipolar inference algorithms won't support it properly.) NETL and TMOIS are ex­ amples of bipolar systems. FRL and the type systems of object-oriented programming languages are unipolar.

A nonmonotonlc inheritance system permits excep­ tion· to inherited properties. NETL and TMOIS rely on bipolar links to achieve nonmonotonicity: negative links are used to override positive inherited information, and positive links to override negative inherited information. Other systems use explicit exception links for this purpose [Borgida 1985], [Etherington 1987], [Fahlman et al. 1981]. Bipolarity and nonmonotonicity are independent proper­ ties. The type systems of object-oriented programming languages are unipolar monotonic, but frame systems such as FRL are unipolar norrmonotonic. In a recent technical report, we describe a bipolar monotonic system [Thomason et al. 1986].

A homogeneou1 inheritance system is either mono­ tonic (all links are strict) or thoroughly nonmonotonic (all links are defeasible.) Heterogeneous inheritance systems have also been proposed, e.g., in [Etherington 1987]; these would contain a mixture of strict and defeasible links. In this paper we are concerned with bipolar, nonmonotonic, homogeneous multiple inheritance systems, which we feel are the most interesting homogeneous class. Heterogeneous systems are not yet well understood, and are not considered here.

The theory of an inheritance network is a fixedpoint consisting of paths of form z1 -+ ··· "-+ z,. or z1 -+ ··· -+ x,._1 -f+ z,. which are generated by inference rules. (This definition relies on the fact that, due to the nature of the inference rules, -1+ may appear only as the last link of a path.) Inference rules derive new paths from existing ones, starting with the paths of length 2 that are the links of the net. A fixedpoint of a nonmonotonic network is called atl extension rather than a theory, because theories are assumed to be deductive and therefore unique. Nonmon<>­ tonic inference is not purely deductive; nonmonotonic nets may have multiple extensions-.

The set of conclusions associated with an extension is the set of statements of form z1 -+ z,. if the extension contains a path of form z1 -+ ··· -+ z,., or z1 -f+ z,. if the extension contains a path of form z1 -+ ··· -+ z,._1 -f+ z,.. It is possible for two distinct extensions to be associated with the same set of conclusions, if they arrive at those conclusions through different inference paths.

3. Shortest Path Reasoners

In the past, multiple inheritance systems have usually been defined informally, e.g., by specifying a procedure for traversing an inheritance graph in response to a query. These reasoners, which use either breadth-first or depth­ first searches, are called shortest path reasoners, because the answer they return is always the one with the shortest inference path from the starting node. A typical example is NETL, which was designed in conjunction with special parallel hardware that could perform breadth-first searches quickly.

Shortest path algorithms are efficient, and they are provably correct for tree-structured inheritance systems with or without exceptions. They are also appropriate for mul­ tiple inheritance systems that do not admit exceptions. However, when multiple inheritance is combined with ex­ ceptions, the definition of correct inheritance reasoning be­ comes much more complex. Although it is still unknown whether there is a single "beat" reasoning strategy for mul­ tiple inheritance with exceptions, the following two prob­ lems clearly eliminate shortest path reasoning as a candi­ date.

3.1. Reasoning With Redundant Statement.

Figure 1 illustrates the problem of reasoning in. a net containing true but redundant statements, which can only occur in a multiple inheritance system. Clyde is an ele­ phant and elephants are gray, but Clyde is also a royal

·

Figure 1: A network with a redundant link.

elephant, and royal elephants are not gray. The redun­ dant IS-A link from Clyde to elephant causes problems for simple-minded inference algorithms because in the presence of such links inheritance paths are no longer independent. In particular, shortest path reasoning algorithms no longer apply.

The intuition underlying inheritance with exceptions is that claims about subclasses are more specific, and so can incorporate information about exceptional cases. There­ fore, subclasses should be allowed to override superclasses. Clyde is not gray because royal elephants aren't gray; the information from royal elephant overides the information from elephant despite the presence of a direct redundant link from Clyde to elephant.

3.2. Reasoning in the Presence of Ambiguity

Figure 2 illustrates the problem of reasoning in the presence of ambiguity. This familiar example is known as the Nixon diamond. Quakers are typically pacifists while Republicans typically are not. Nixon is both a Quaker and a Republican. Ia he a pacifist or isn't he? One might choose to draw no conclusion, or one might generate two extensions as TMOIS does, with Nixon being a pacifist in one and a non-pacifist in the other. The crucial point is that the ambiguity must be recognized.

Simple depth-first search algorithms, which work per­ fectly well for tree-structured networks, have no way to recognize the ambiguities that can arise in multiple inheri­ tance situations. Shortest path reasoners will either choose one of the two poaaible conclusions about Nixon arbitrarily, or else report that both conclusions are true at the same time, i.e., that Nixon simultaneously is and is not a paci­ fist. Neither behavior is theoretically sound. The inability to recognize ambiguity is another reason why shortest path algorithms are unacceptable for reasoning about situations involving nonmonotonic multiple inheritance.

-'· A Clash of Intuitions

The two problems described in section 3 were solved in TMOIS by introducing a measure called the inferential distance ordering as a replacement for path length. The precise definition of inferential distance is highly technical, but it essentially states that an inference path A -+ ... -+ B f+ P should preempt a path A -+ ... -+ C -+ P iff there is a path A -+ .·· -+ B -+ ··· -+ C establishing for A that B is a subclass of C.

Although inferential distance is important for distin­ guishing inheritance systems from other nonmontonic rea­ soning systems such as default logic [Touretzky 1984], it does not by itself yield a unique definition of nonmonotonic multiple inheritance. There are a number of other choices to be made. Touretzky built into TMOIS certain assump­ tions about reasoning that other investigators, approaching inheritance with a different set of intuitions, may not share. In the remainder of this section we describe four areas in which intuitions have clashed. It should be stressed that all of these systems treat redundancy and ambiguity in the correct way, and appear both theoretically sound and in­ tuitively appealing. Nonetheless, we will describe cases in which they give conflicting results.

-'.1. Skeptical vs. Credulous Reasoning

A skeptical reasoner refuses to draw conclusions in am­ biguous situations. 1 A skeptical reasoner would therefore offer no opinion as to whether Nixon was or was not a pacifist. Credulous reasoners, on the other hand, try to conclude as much as possible. To avoid inconsistency, a credulous reasoner must generate multiple extensions so that contradictory conclusions can be isolated from one an­ other. TMOIS describes such a reasoner. In one of the two credulous extensions of figure 2 the inference path NIXON -+ QUAKER -+ PACIFIST is admissible; in the other, the path NIXON-+ REPUBLICAN f+ PACIFIST is admissible.

1 Thia wu the attitude toward reasoning of the first philosophical skep­ tics; they refused to draw a conclusion in cues in which any reason could be produced for the opposite conclusion.

Since skeptical reasoning always generates a unique ex­ tension, there is no need to consider sets of extensions. We expect skeptical reasoning algorithms to be simpler and more efficient than credulous ones; in our investigations so far, this has indeed been the case. On the other hand, one advantage of credulity is that after generating all per­ missible extensions they can be examined for interesting properties.

Skeptical inheritance as defined in [Horty et al. 1987] is not equivalent to taking the intersection of all credulous extensions. One reason is that, in the presence of multiple ambiguities, skeptical inference may permit certain paths that are not permitted in all credulous extensions. Con­ sider figure 3. Nixon's pacifism is ambiguous here, and consequently, so are his feelings about the military. But a simple skeptical reasoner would not recognize the sec­ ond ambiguity. The reason is that since it is ambiguous whether or not Nixon is a pacifist, there are no valid paths from Nixon to pacifist to anti-military in the skeptical ex­ tension. Therefore the path from Nixon to football fan to not-anti-military is unopposed, so one may conclude that Nixon is not anti-military. This is the approach recom­ mended in [Horty et al. 1987].

It might be preferable for ambiguity to be propagated from pacifist to anti-military, based on the following argu­ ment: we are reserving judgement about whether Nixon is a pacifist or not, but conceivably he could be one. In that case he could conceivably be anti-military. Being a foot­ ball fan he could also conceivably be not anti-military, so we should reserve judgement on whether he is anti-military.

An ambiguity-propagating version of skepticism would be more compatible with credulous reasoning, in that the skeptic never draws conclusions about matters that would be decided differently in different credulous extensions. The goal of ambiguity-propagating skepticism is to produce a single extension whose conclusions are consistent with the intersection of all credulous extensions. It is not yet known whether this can be done without computing all the cred­ ulous extensions.

4.2. Upward vs. Downward View of Reuonlng

The most common intuitive model of inheritance has properties flowing downward from classes to their aubclaues and instances-though the flow can be interrupted by an exception. This downward view· is the one promoted in TMOIS and, informally, in FRL and NETL. An opposing view of inheritance has inference working upwards. This conception, which is explicitly chosen in [Horty et al. 1987], stresses arguments (or proof sequences), and imagines them being constructed from the bottom up. 2 The upward and downward views aren't always compatible, as the following two examples illustrate.

4.2.1. Coupling in Downward Reuonen

Figure 4 demonstrates an important difference between upward and downward credulous reasoners. (In this sec­ tion we consider only credulous reasoners; the skeptical approach would generate a single extension with no inter­ esting conclusions about A or B.) A downward credulous reasoner produces two extensions from figure 4, due to the ambiguity about whether B's are E's. One extension con­ tains B-+C-+E and A-+B-+C-+E while the other contains B-+Df+E and A-+B-+Df+E. Notice that in each extension, the conclusion about A 'a being E'a is identical to the con­ clusion about B's being E's. The property that a aubclau is always in agreement with its superclaues (in the absence of explicit exceptions) is known as coupllng. Downward reasoners necessarily produce coupled theories because the only properties a node can inherit are those of its superiors. Upward reasoners are not so constrained.

In an upward credulous reasoner the arguments made about A in figure 4 need not depend on conclusions that were drawn about B, since properties are not flowing down from B to A. So in addition to the above two extensions, an upward reasoner could produce two uncoupled extensions. One would contain B-+C-+E and A-+B-+Df+E; the other would contain B-+Df+E and A-+B-+C-+E.

Intuitively, coupling appears to be a desirable prop­ erty for reasoners to have. It may be p01111ible to constrain upward reasoners to produce only coupled theories, but this could compromise their ability to reach unambiguous conclusions where downward reasoners do not, a property known as opportunistic inference.

4.2.2. Opportunism ln Upward Reuonen

Node B is ambiguous in figure 5 for the same reason it's ambiguous in figure 4: there are two mutually contradic- Figure 4: Reasoners that exhibit coupling treat A and B identically.

2 Note that although both FRL and NETL pzwent propertiea u flowing downward from clu- to individuaJ., in fact their March alcorithma proceed in the oppoaite direction, atarting with the individual and proceeding up the IS-A hierarchy to increuingly generalaupercw-. Only TMOIS generates inference patha from top to bottom.

tory paths B-+C-+E and B-+Df+E. For now let us consider only skeptical reasoners. No skeptical reasoner should draw a conclusion about whether B's are E's. But what should it conclude about A's being E's? In a downward skepti­ cal reasoner, since B is ambiguous and therefore neither an E nor a non-E, there is no property for A to inherit. So a downward reasoner would draw no conclusion about whether A's are E's.

In an upward skeptical reasoner, the link Af+D rules out the potential inference path A-+B-+Df+E, leaving the path (or argument) A-+B-+C-+E to go through unopposed. The upward reasoner seizes on any chance to prove some­ thing, in this case that A's are E's, even though B remains ambiguous on this point. Because upward reasoners are op­ portunistic, they sometimes reach conclusions in situations where a downward reasoner would abstain.

Upward and downward credulous reasoners also behave differently with respect to figure 5. A credulous upward rea­ soner would generate two extensions: · one in which B's were E's, and one in which they were not. A's would beE's in both extensions. TMOIS, a credulous downward reasoner, would also generate two extensions, but the extension con­ taining B-+Df+E would contain no conclusion at all about A's, since the potential path A-+B-+Df+E is cancelled by the A f+ D link.

4.3. On-Path vs. Off-Path Preemption

Figure 1, which contains a redundant link, supports two conflicting inference paths: CLYDE -+ ELEPHANT -+ GRAY-THING and CLYDE-+ ROYAL-ELEPHANT f+ GRAY­ THING. The latter path is said to preempt 3 the former. Since royal elephant is on the path from Clyde to elephant, presumably it has more specific information about Clyde than elephant does. The redundant direct link from Clyde to elephant caused problems for early nonmonotonic inher­ itance reasoners precisely bec!louse shortest path algorithms don't correctly implement preemption.

An inheritance reasoner may adopt either of two ver­ sions of preemption, which we call on-path and off-path pre­ emption. On-path preemption, first described in TMOIS, is the stricter approach: one path may preempt another only if the preempted path contains a redundant link (or "level skip," as it's called in NETL) that would short­ circuit part of the preemptor. If a node interrupts a re­ dundant link, as african-elephant interrupts the link from Clyde to elephant in figure 6, the preemption relation no longer holds. Figure 6 generates the two conflicting paths CLYDE-+ ROYAL-ELEPHANT f+ GRAY-THING and CLYDE -+ AFRICAN-ELEPHANT -+ ELEPHANT -+ GRAY-THING. Even though royal elephant is on the path from Clyde to elephant, preemption doesn't hold because royal elephant is not on any path from Clyde through African elephant to elephant; in other words, figure 6 contains no redundant links.

Choosing the downward view of reasoning for a mo­ ment, we note that royal elephants are not gray while African elephants are gray. Since neither class is a subclass of the other, and Clyde is an instance of both, he could inherit either one's grayness property. Clyde's grayness is there­ fore ambiguous, so the network should have two extensions. A similar argument holds if we choose the upward view of inheritance.

Sandewall argues that on-path preemption in TMOIS is too restrictive, citing figure 6 as an example where our intuitions suggest that Clyde is unambiguously not gray [Sandewall 1986]. He proposes a more permissive rule, one which we call off-path preemption. The argument for off-path preemption begins with the fact that both royal elephant and African elephant's paths to gray thing must go through elephant. The fact that African elephants are typically gray shouldn't influence Clyde, because African elephants aren't explicitly gray, they merely inherit gray­ ness from elephant. Royal elephant overrides the elephant node's grayness property with more specific information.

This argument does lead to the desired conclusion that Clyde is not gray in figure 6. Off-path preemption in genera! is more permissive (more willing to let one path over­ ride another rather than cause an ambiguity) than on-path preemption. But is it more intuitive?

3 Inatead of "preemption,· the term "preclusion· wu used in TMOIS. The concept ia the a&me.

Consider figure 7, which has the same topology as fig­ ure 6 but different node labels. Marines are typically men, and most men drink beer. Chaplains are typically men but they typically don't drink beer. George is a marine chap­ lain. In this sitution we are less certain that George doesn't drink beer, which the off-path version of preemption would insist is the case. Marines and chaplains are quite different from each other; possibly even antithetical. Both types of individual are rather different from the typical man. It is therefore difficult to predict which properties George will inherit from chaplain and which from marine. Perhaps the specific knowledge that chaplains don't drink beer should take precedence over what we know about men, but per­ haps not. The most relevant missing bit of information is the rate of beer drinking among marines. If this ii far higher than the rate of abstention among chaplains, one would be better off assuming George is a beer drinker than Like Sandewall'ssystem, the skeptical reasoner described in !Horty et al. 1987J uses off-path rather than on-path pre­ emption. A permiuive view of preemption allows a skep­ tical system to reach conclusions where a strict on-path approach would see an ambiguity. On the other hand, a credulous reasoner that chose off-path preemption would simply produce a subset of the extensions allowable with on-path preemption; for credulous reasoners it may pay to take a more cautious, strict approach.

~.4. Clasalcal va. Intuitive Notlona of Conalstency

According to clauical logic, if it is pouible to derive any pair of statements p and ,.., p then the initial axioms are inconsistent and the only theory that the axioms generate is the one containing every statement. Thll theory of course destroys any useful information that may be contained in the axioms.

Graph-oriented approaches to reasoning avoid this prob­ lem, since a statement A cannot be derived from a set of statements r unleu r creates a path supporting A. In fact, even strictly monotonic inheritance networks are non-clauical in this respect, as we show in !Thomason et al. 1986J. Figure Sa is a clauically inconsistent net: it con­ tains the statements p(a) and ,.., p(e&). Such a net might represent the sentences "Clyde is an elephant" and "Clyde is not an elephant." Although we can't use it to derive all pouible statements, the locical inconsistency of the net­ work is easily apparent.

This side-effect of craph-based reasoning is clearly de­ sirable, since it enables craceful decradation of information retrieval in the presence of inconsistent data. Here, claai­ ciallogic is inadequate as a theory of inheritance reasoning, and should be replaced with a more adequate approach. In !Thomason et e&l. 1986J, we show that the. simple four­ valued logic of !Belnap 1977aJ, !Belnap 1977bJ is adequate for characterizing monotonic inheritance.

In other cases, claaical lope is overly liberal: figure 8b is not clauically inconsistent. This figure could represent the sentences "elephants are cray" and "elephants are not gray." The two links of the figUre are expressed in predi­ cate calculus as (Vz)lp(z) -+ q(.:z:)J and (V.:z:)lp(z) -+ ,.., q(.:z:)J. As long as there are no instances of elephants, there is no logical contradiction here, even though the topology of the network is the same as that of figure Sa. TMOIS labels fig­ ure Bb inconsistent because even if there are no instances of p's, it makes no sense to simultaneously believe both "the typical p is a q" and "the typical p is not a q." An­ other argument for the inconsistency of 8b is that it simpli­ fies thinp if networks with identical topologies are treated identically.

The intuitive notion of consistency put forth in TMOIS, motivated by the desire to talk about vaguely-specified con­ cepts such as "the typical p," is at odds not only with clauicallogic but with the default and nonmonotonic logic formulations of inheritance as well. For example, figure 8b is usually expressed in default logic !Reiter 1980J as:

4 In fact, if marine· are unuually avid couumers ol beer, one micht argue that marine ahould have a direct link to beer drinker. Suc:h a link would be redundant u far u the marine node iUelf i1 c:oncerDed, but it would aupply additional evidence in favor of beer drinkiq for particular iutanc:ea of marine, auch u Georae.

If multiple instances of p's exist, some may be inferred (via the first default) to be q's, and others (via the sec­ ond default) not to be q's; in any case no contradiction will arise. The same is true in nonmonotonic logic, where figure 8b would be expressed as:

A conservative reasoner could refrain from assigning any interpretation to a net containing even a single incon­ sistency. But since an inconsistency in one part of the net doesn't necessarily affect inference in other parts, it may be pouible to reason around the inconsistency and in some cases produce useful inferences.

5. Conclualon

The study of inheritance reasoning has rapidly moved through stages similar to ones that deductive logic has paued through, at a much more glacial pace. Reflection on reasoning practices has produced a large body of patterns and generalizations relating to sound inheritance reason­ ing; this reasoning was formalized in TMOIS, and meta the­ oretical results were established about the formalization. In this paper, we have described the discovery of several dimensions along which alternative approaches to inheri­ tance reasoning can be generated, all of which appear to be equally sound.

The existence of these approaches has many theoret­ ical consequences, which we are exploring in our current research. The inheritance theory of TMOIS needs to be generalized; and other treatments of nonmonotonic reason­ ing may need to be liberalized. For instance, the modal nonmonotonic logic of [McDermott and Doyle 1980] renders the inference from [A 1\ MB] -+ B and A to LB V L ~ B valid. On the natural interpretation of this inference in nets, it does hold good for credulous reasoners. But it fails for skeptical reasoners. This makes it desirable to search for a more general logic, that is neutral with respect to the design space of sound inheritance reasoners.

However, this theoretical work needs to be combined with more "empirical" investigations of the alternatives. Sandewall has suggested that a useful way to approach the question of sound multiple inheritance reasoning with ex­ ceptions proceed might be to create a catalog of problem­ atic networks [Sandewall1986]. Inheritance formalisms can then be compared by contrasting their handling of the cases in the catalog. As new definitions of inheritance are pro­ posed, new examples may be added to the catalog to further refine the distinctions between the various schemes.

We have in effect been pursuing this approach. Al­ though the various examples appearing throughout TMOIS were not collected in a formal catalog, the two primary ex­ amples, known as the Clyde level skip (figure 1) and the Nixon diamond (figure 2), were used in [Touretzky 1984] to contrast TMOIS with other formulations such as short­ est path reasoning and Etherington's formalization of in­ heritance in Reiter's default logic [Etherington 1987]. Of course, the project of collecting examples has to be com­ bined with extracting generalizations from the data and relating these generalizations to systematic theories. Thus, as well as presenting interesting examples where intuitions clash, we have presented in this paper a taxonomy of in­ heritance systems, and have presented four areas where definitions of multiple inheritance can disagree. A more systematic catalog is presented in [Touretzky et al. 1987].

Even after the careful analysis conducted in TMOIS, the problem of nonmonotonic multiple inheritance is far from conclusively resolved; its subtleties continue to sur­ prise us.

Acknowledgements

We thank David Etherington and Erik Sandewall for il­ luminating correspondence, and Jon Doyle for helpful com­ ments on an earlier draft of this paper.