A Semantical Approach to Stable Inheritance Reasoning

1 Introduction

A number of techniques exist for reasoning with non­ monotonic multiple inheritance systems. While they have drawn the attention of many researchers, consen­ sus on the meaning of networks and the approach to be taken by inheritance reasoners has yet to be achieved. In fact, the number of choices available to the designer of such systems is considerable. In [Touretzky et al. 1987), the design space for inheritance reasoners is explicitly mapped out , and the widely varied approaches and im­ plications of existing schemes are made clear. There it is claimed that this divergence represents a number of different, but equally plausible reasoning strategies, suitable for various tasks. We conjecture that a compar­ ison of such techniques is made difficult by a lack of a semantic account of inheritance reasoning, and without such, the intuitive appeal and adequacy of these systems cannot be accurately evaluated. A semantic characteri­ zation of inheritance reasoning can more readily capture our intuitions. Furthermore, such a semantics can be used as a yardstick with which to measure the adequacy of syntactic, algorithmic techniques.

The goal of this paper is to provide a semantic charac­ terization of inheritance reasoning. This will be achieved by, first, providing a semantic interpretation of network links, and second, utilizing the concept of minimal (or preferred) models to account for the nonmonotonic na­ ture of inference in inheritance systems. We will also show how this approach differs from traditional meth­ ods in a crucial respect .

1.1 Definition of a Network

Inheritance systems are essentially devices which per­ form (possibly nonmonotonic) inference in a computa­ tionally feasible manner by restricting the form "sen­ tences" in the "language" can take. Although many definitions of inheritance networks exist , the following is similar in spirit to the one given in [Touretzky 1986] . The details will be much simpler though, since we require less machinery to elucidate the relevant concepts in this paper. In particular, while inheritance networks gener­ ally deal with both classes of objects and individuals, we will not distinguish individuals in order to simplify the treatment. As well, the only relationship between classes permitted is the ISA (or subclass) relation.

• Definition An inheritance network over a finite set of classes r is an acyclic set of ordered triples (links) of the form (sign x, y) where sign E { #, +,-} and x,yE f.

The intended interpretation of the links in these net­ works is as follows:

• (+A, B) means "members of A are members of B" .
• (-A, B) means "members of A are not members of B".
• (#A, B) means "members of A may or may not be members of B".

For instance, (+ Apple , RedThing) represents the as­ sertion that apples are red. The third type of link is not meant to be true when it is unknown whether A's are B's; rather, it is intended to state that both of the other links are false . In other words, the link is true exactly when the relationship of A to B is known, and that relationship is (something like) . "A's may or may not be B's with roughly equal likelihood" (e.g. (#American, Republican)).

Networks are often represented as directed graphs in the obvious manner (see, e.g., [Touretzky 1986]). A link (+A, B) will be also written as A____. B, and (-A, B) as A+ B .

Given a network, an inheritance reasoner is charged with the task of deciding which statements (or links)

should be inferred from those given. If classes were in­ terpreted as monadic predicates and links as universally­ quantified statements, there would exist an obvious translation of networks into first-order logic. The inheri­ tance reasoner then could simply be a first-order theorem prover to act on these new sentences; the semantics of inheritance networks would be clear. In fact, for inheri­ tance networks without exceptions, this interpretation is acceptable. The problem is most natural subclass rela­ tionships are not universal. Exceptions are the rule, so to speak. Therefore, the treatment here will be of inher­ itance networks with exceptions. In this type of network, all links will be viewed as exception-allowing. If (+A, B) is a link in the network, it may be the case that a par­ ticular A is not a B. This suggests the links be given a normative interpretation. So (+A, B), in an exception­ allowing network, stands for "Normally A's are B's".

In exception-allowing networks, the semantic import of the links is not as clear as in the case of nets which pro­ hibit exceptions. Attempts have been made to interpret links in terms of autoepistemic logic ([Touretzky 1986]) and default logic ([Etherington and Reiter 1983]) with limited success; and while these may provide a loose se­ mantic interpretation for the links themselves, little at­ tempt has been made to account for the nature of infer­ ence in exception-allowing networks. While exception­ less networks are (relatively) unproblematic, classical semantics will not adequately reflect exception-allowing networks, due to their nonmonotonic nature.

A survey of the traditional approaches to inheri­ tance reasoning can be found in [Touretzky et al. 1987]. For reference to specific systems of inheritance, see, for example, [Touretzky 1986], [Horty et al. 1986], and [Sandewall 1986].

2 A Minimal Model Approach to Inheritance

2.1 Interpretation of Li,nks

As mentioned in the previous section, links in an inher­ itance network can be reasonably interpreted as assert­ ing normative statements. Obviously, such statements are not necessarily universally true regarding members of their constituent classes; but they should be subjected to some normative attribution. Some objections to this denotation are raised by Touretzky [1986, pp.6-7]; how­ ever, these are not serious and are not considered here (see [Boutilier 1989]).

In [Boutilier 1988], the conditional logic E is presented for reasoning about default or prototypical properties 1 . The language of E is that of classical propositional logic augmented with the connective =>. The intended in­ terpretation of a sentence A => B is "If A holds, then in the normal course of events, B holds as well". The logic is given a possible worlds semantics that provides the desired intuitive characterization of such exception­ allowing sentences. Given a set of possible worlds and a reflexive, transitive, forward-connected (if xRy and xRz, then either yRz or zRy) relation on that set (represent­ ing accessibility of less-exceptional worlds), A => B is true at some world if there is some accessible world such that A holds, and A :::) B holds at all worlds accessible from that point.

1 E is an extension of the logic N found in [Delgrande 1987] that deals with nested conditionals.

Since E has a well-developed semantics, and we have argued that links in inheritance networks be given a normative interpretation, it seems that translating in­ heritance networks into sentences of the logic E would provide an adequate logical account of the "connective" --+. In fact, it is precisely this device which will be used to provide a semantic account of links in a network. The following translation is suggested:

1. (+A, B) is translated to A=> B, with the interpre­ tation that A's are normally B's.
2. (-A, B) is translated to A => -.B, interpreted as A's are normally not B's.
3. (#A, B) is translated to -.(A=> B) 1\ -.(A=> -.B). This states that neither of the other two alternatives hold.

Now the semantic import of a network is clear: a net­ work is a collection of sentences in the language of E, and as such, has associated with it the semantics of the logic E.

While the meaning of networks themselves has been specified, the logic E cannot be used alone to identify nonmonotonic consequences, and hence, cannot account for inference in inheritance networks. We must establish new conditions with which to capture the nonmonotonic nature of inheritance.

A number of algorithms characterizing inference have been presented in the literature 2 , but these characterizations yield incredibly divergent results [Touretzky et al. 1987]. It is conjectured that this state of affairs exists because a clear semantic account of in­ ference in inheritance reasoners has not been proposed. A yardstick is needed which can measure the intuitive appeal of syntactic characterizations and enhance our understanding of the entire process.

The approach we will take is one suggested by Shoham [1986]. To identify the nonmonotonic consequences of a theory, we restrict our attention to those models of the theory which are in some sense preferred. We will as­ sociate a reflexive, transitive preference relation $ with the set of models of a network, where M1 $ M2 is in­ tended to mean M1 is as prefable as M2 . The preferred models are those minimal in this relation. The minimal model approach seems to be able to capture in a nat­ ural fashion the ideas behind nonmonotonic reasoning, therefore we will enlist it to aid in providing a semantic characterization of inheritance reasoning.

Before discussing the concept of a preferred model, we must define a model for an inheritance network. Links in a network have been associated with sentences in the language of E. Therefore, under this plausible normative interpretation, E-models could be considered as mod­ els of inheritance networks, an E-model satisfying a net­ work exactly when it satisfies the translation of its links.

2 These can apply to sentences of E as well as to other syntactic entities, or links, they were designed for.

Preference criteria could then be defined for E-models such that minimal E-models of the network determine the nonmonotonic consequences (or extensions) of that network.

While in principle this could be achieved, it is ~ot the tack taken here. In dealing with the full generality of the language of E complications and sub_tleti~ may arise which are not entirely relevant to the discussion at hand. Thus, a simpler notion of a model will be provided, allowing full attention to be paid to the relevant aspects of the preference relation.

Definition An /-model (over a finite set of classes f) is a set of links such that exactly one of(+ A, B), (- A, B), (# A, B) is in the set for each A, B ~ r,A ::f B, and the ISA/ISNOTA-subgraph ofth1s set is acyclic.

Definition An I-model I satisfies a network <) iff for each link A E <), A E I.

2.2 The Assumption of Redundancy

In [Touretzky 1986), Touretzky presents his notion of in­ ferential distance, the use of which has become a hall­ mark of contemporary inheritance reasoners. A class B is defined to be "closer" to a class A than is a class C in a network if there exists a path from A to C which passes through B. If a conflict arises with respect to a property that class A should inherit, then this conflict is resolved by inheriting the property from the closest of the conflicting superclasses.

The use of inferential distance in this manner yields intuitive results from a number of networks. For in­ stance, the network in Figure 1 asserts that people who work hard (H) are productive (P), and that most re­ searchers ( R) are quite diligent, yet fail to make signifi­ cant progress (for the sake of argument!). Now Sarah (S) should inherit the characteristic of being productive by virtue of being a hard worker, while the fact that she's a researcher suggests she's not productive at all. Reason­ ing based on inferential distance will solve this conflict by determining that Sarah is unproductive because re­ searchers are a specific subclass of hard workers (i.e. R is closer to S than is H).

This example shows the intuitive appeal of inferen­ tial distance. Why is it, though, that such an arbi­ trary criterion as ~inherit from the closest superclass" provides intuitive results in this case? Suppose Sarah is a hard worker for reasons altogether independent of her being a researcher (say, her editorial work), and is quite productive because of this. In such a case, inferen­ tial distance does not provide intuitive results. The fact that R is closer to S than is H is no reason to inherit properties from R instead of H . Howeve~, th~s coun­ terexample is intuitively unacceptable. G1ven JUst the information in the network, the conclusion that Sarah is unproductive should be forthcoming. The reasoner should assume Sarah is a hard worker because she is are­ searcher (since the an independent reason makes the use of inferential distance quite unreliable) . In other words, the link S --+ H is "redundant", due to the presence of the links S --+ R and R --+ H. Without assuming such redundancy, the justification for inferential distance simply doesn't exist.

Calling links redundant may give the impressio~ th~t such links add no information to a network, wh1ch IS not the intention 3 . Rather than call these links redun­ dant, "independently justified" may be a more appropri­ ate term. In general, a link is considered to be redundant in a network if there exists a set of links that can be con­ strued as the reason for the truth of that link. A more rigorous and comprehensive definition of_redund~~cy c~n be given after the development of certam defimtlons m the next subsection.

2.3 The Preference Relation

In the minimal model framework, nonmonotonic conse­ quences are derived by identifying the preferred models of a theory, in this case, a network. In the terminology of other network formalisms, the preferred models should be those which satisfy permissible "arguments", or paths. Rather than speak of arguments, we will use the con­ cept of support. For instance, if the links A ---+ B and B --+ C belong to r, then these sentences will support the conclusion A --+ C, unless more specific evidence contradicts this. It remains to be stated what consti­ tutes this specific evidence for inheritance networks.

It will be convenient to use the path notation of tra­ ditional reasoners as shorthand.

Definition A path (*ZJ, z2, ... , Zn) is contained in a set of links <) iff each of the links ( + z1, z2), ( + z2, z3), ... , (*Zn-J,Zn) is in<) (where* E {+,-}).

For convenience, *will denote the "complement" of *· which is any sign not equal to * (e.g. if the value of * is +, then* can be either of# or-). Notice that paths can only be positive or negative, while links can be neutral as well. If A is a (positive or negative) link (* z, y), then X denotes either of the two complement links (* z, y) 4 ·

We will now define a reflexive, transitive preference relation on the set of I-models. In general, models which respect the transitivity of subclass relationships should be preferred to those which do not. That is, if a model contains the path (· z1, z2, ... , zn), then it should also contain the link (·z1, zn)· Unsurprisingly however, there are exceptions to this rule, when more specific evidence presents itself. These exceptional conditions reflect re­ dundancy considerations.

3 Indeed the conclusions reached from a network with a "redund~t" link may be different from those with the link missing (e.g. see [Touretzky 1986, pp.1o-11], or [Boutilier 1989]).

·E.g. (+x,y) has two complements, (-x,y) and (#x,y), while the complement of(# x, y) is undefined.

Example Assume the following paths are present in a network r :

where 1 ~ i < n - 1. The first path indicates sup­ port for the assertion XI - Xn. This is because XI's are x2 's, which are X3 's, and so on. The second sequence can be interpreted as the reason x; - x;+l holds. Now, this line of reasoning can be ex­ tended to show that the justification for concluding XI - Xn is the path (+XI, .. . , X;, y, Xi+I> ... , Xn)· However, it is also known that y-f-+ Xn . This makes y an exceptional subclass of Xi+I with respect to Xn. Therefore XI should inherit properties from y over Xi+I· making XI an exceptional subclass of Xi+I· Just as with inferential distance, since y and Xi+I conflict with respect to property Xn, XI should in­ herit the property XI+ Xn from y, since y is closer to XI than is Xi+I · The concept illustrated in this example is closely related to Touretzky's [1986] no­ tion of preclusion.

Example Assume the following paths are present in a network r:

where 2 ~ i < n. The first path indicates support for the assertion XI - Xn and the reason for this (ifthe second path is taken into consideration) is be­ cause XI's are x2 's, which are ... x; 's, which are y's, which are Xi+l 's, ... which are Xn 's. However, the third link asserts that XI's are not y's, thus disabling the entire chain of reasoning. Hence, the conclusion XI - Xn should not be drawn. This example illus­ trates a concept closely related to Touretzky's [1986] notion of contradiction.

These definitions, in the style of [Touretzky 1986], will formalize the concepts required by the preference rela­ tion. Let 41 be any set of inheritance links.

Definition A type-1 intermediary to a path (*Xb ... , Xn) in 41 is any class y such that either

Definition A type-2 intermediary to a path (*XI, ... , Xn) in 41 is any class y such that either

1. y = x; : (1 < i < n); or
2. the path ( + x;, YI, ... , Yi, ... , Ym, Xi +I) E 41 : m ~ 1, 2 ~ i < n - 1, and y = Yi ; or

Figure 2 illustrates exactly where an intermediary of either type can be situated along a path. Both type1 and type-2 intermediaries can be viewed, given the assumption of redundancy of links, as reasons for the support of the conclusion (*XI, xn) from the appropriate path. In the examples, it was seen that support for this conclusion should be withdrawn if a type-1 y exists such

Figure 2: Positioning of intermediaries

that y -/-+ Xn holds, or if a type-2 z exists such that XI+ z holds.

Now that the reasons for disabling the support for a conclusion have been discussed, a definition of supported sentences can be presented along with the preference re­ lation for models. Recall that meta-variable * ranges over { +,-}, while * can be any of the three signs. Let 41 be any set of links.

Definition A link (*XI, Xn) is supported in 41 by the path¢= (*XI, ... ,xn) iff

1. ¢E41,
2. There exists no type-1 y to ¢ in 41 such that (* y, Xn) E 41, and
3. There exists no type-2 z to ¢ in 41 such that (+xi,z) E41.

A link A is supported in 41 iff there exists a path ¢ E 41 which supports A.

Definition The set of contradicted links in 41 is

In other words, if a link A is supported in 41, its com­ plement links are contradicted (if either is in 41 ).

Definition An I-model MI is as preferable as. an I­ model M2 (written MI ~ M2) iff

M1 is preferred to M2 (written MI < M2) iff M1 ~ M2 and not M2 ~ M1.

The preferred models of a network are those models which satisfy the links of the network and are minimal in the relation ~- The nonmonotonic consequences of a theory, or network, are precisely those links true in all preferred models. Essentially, the preferred models of a network are those which satisfy as many supported links as possible, where a link is supported if there is a "chain of reasoning" (path) which leads to that conclusion, and no more specific evidence (intermediaries) inhibit this support.

Given the definitions here, a formal characterization of the notion of redundant link, discussed in the last subsec­ tion, can be given. The idea is that a redundant link is one which has some independent justification, consisting of a set of other links, for its truth.

Definition A link (* x1. xn) is redundant in a network 41 iff there exists a path (*XI, ... , xn) (where n > 2) such that the restriction (in the graph-theoretic sense) of 41 to {x1, ... , xn} contains no contradicted links.

3 A Comparison to Existing Techniques

There are a number of different intuitions regarding the exact nature of inheritance reasoning, and these are reflected in a divergent collection of reasoning tech­ niques. The "clash of intuitions" is described in detail in [Touretzky et al. 1987], and the space of options avail­ able to an inheritance reasoner is explicitly mapped out. There it is claimed that these choices represent a number of different, but equally plausible, reasoning strategies, suitable for varying tasks. We claim here that many of these design options are unintuitive, and while space pro­ hibits a complete discussion of where the minimal model reasoner fits along this scale and a presentation of exam­ ples (see [Boutilier 1989] for details), we will show how it differs from other techniques in a crucial respect.

In the terminology of [Touretzky et al. 1987], our ap­ proach is skeptical, in that conclusions are reached only when no evidence contradicts them. Unlike the "re­ stricted skepticism" of [Horty et al. 1986], this approach is truly skeptical. The reasoner performs coupling, it is not opportunistic, and it uses on-path preemption, all de­ sirable qualities. As well, the reasoner is stable, a point to be discussed in greater detail now.

3.1 Stability and Redundancy

In (standard) logics the property ofmonotonicity is guar­ anteed by definition. Letting S and T be sets of sen­ tences, a a sentence, and C the consequence operation of some logic, the property of monotonicity can be ex­ pressed as

Of course, this property is too strong for nonmonotonic inference systems. However, a property known as the Cumulation Property was proposed in [Gabbay 1985] as being a minimal requirement (among others) of any non­ monotonic reasoning system. Interpreting C as the non­ monotonic "consequence" operation of such a system, this property can be expressed as

This condition asserts that if a sentence is derivable from some theory, the addition of that sentence to the theory won't affect the set of consequences 5 .

An inheritance reasoner is said to be stable iff it sat­ isfies the Cumulation Property. In other words, a rea­ soner is stable if, for any network, the addition of a link representing a consequence of that network will not in­ validate any consequences of the original network, nor introduce new consequences. While stability is a seem­ ingly incontrovertible property of inheritance reasoners, reasoners which use inferential distance (ID-reasoners), such as those of [Touretzky 1986] or [Horty et al. 1986], do not exhibit this attribute.

Consider the network in Figure 3. In this network an ID-reasoner will conclude that D's are not L's, and hence make no conclusion about D's with respect to A's.

5 Actually, Gabbay proposed two separate rules, Weak Monotonicity and Cut, which were combined in [Besnard 1988) as the resultant Cumulation Property.

Notice that the conclusion that M's are A's is also war­ ranted. Now consider the network augmented with "M's are A's" (sanctioned in the original network), via the explicit link M - A. In contrast to its determination in the original network, an ID-reasoner will now assert that D's are indeed A's. Even though a link has been added which was previously deducible from the network, it significantly altered the consequences of the network. The minimal model characterization of inheritance, how­ ever, is stable, almost by definition. The link D -A is not true in all minimal models of either network, thus D - A is not concluded in either case. The question remains whether stability makes the minimal model rea­ soner a more plausible approach than ID-reasoners.

It is suggested that this sort of instability may be desirable, giving inheritance reasoners an added flex­ ibility by allowing "a sensitivity to the structure of arguments that is difficult to achieve in deductive systems" [Horty et al. 1986, p.21] . This claim is sup­ ported by the following interpretation of the networks. Let D stand for Moby, W for Whales, M for Mammals, L for Land-Dwellers, and A for Air-Breathers. Given the information in the first network, the reasoner cannot (and should not) conclude that Moby is an air breather. In the second network, the direct link from mammals to air breathers changes things, it is argued. While whales are still not land-dwellers, they are mammals and mam­ mals are directly linked to air breathers (hence, they are air breathers independently of being land dwellers 6 ) . Therefore, it is claimed, the instability exhibited by the reasoner is actually quite useful because the desired con­ clusion is reached, namely, that Moby is an air breather.

Clearly, this argument is incompatible with the notion of redundancy assumed by the minimal model reasoner. A simple change in the interpretation of this network will perhaps illustrate the problem clearly. Let all nodes be interpreted as before except for A, which will now stand for Walking-Things. ID-reasoners will determine that Moby the whale can walk because of the explicit link from M to A. In other words, they assume the link is not redundant (i.e. it is independently justified). On the other hand, .the minimal model reasoner will not conclude anything about whales (in particular, Moby) walking, since the link from M to A is assumed to be redundant. That is, mammals can walk because they are land-dwellers.

The key difference between the reasoners is in their treatment of redundant links. One may say that since each "works" (gives intuitive conclusions) on a different example, each is useful for different purposes. The mini­ mal model reasoner assumes that M - A is redundant, useful in one instance, while the others do not, helpful in the other circumstance. However, it seems that the mini­ mal model reasoner is more principled in its choice. It as­ sumes that all links with a certain "topology" are redun­ dant. If it turns out that a particular network has this "shape" but its link is not redundant (e.g. M ---+ A), then the reason for the minimal model reasoner's lack of intuitive conclusions is obvious: it wasn't designed to work on this network (which does not fit its definition of an inheritance network).

6 ln fact , this is the case in the real world, which is why the results seem so appropriate.

In contrast, the reasoners of (Touretzky 1986) and [Horty et a/. 1986) are a little less clear in this respect. While the use of inferential distance makes a tacit as­ sumption about redundancy, these systems fail to make clear which links will be taken to be redundant. As a result, they are designed to work on specific examples, some of which have redundant links, and some of which have "pseudo-redundant" links. The problem is, looking at an uninterpreted network, we cannot distinguish these types of links. While the minimal model reasoner makes its principles explicit by stating that all such links are redundant, the other reasoners exhibit a certain unpre­ dictability.

3.2 Concluding Remarks

While many syntactic characterizations of inheritance reasoning exist, the semantics of these systems has re­ mained unclear and, as a result, disparate conclusions abound. We have provided a semantic interpretation of links in these networks and a semantic characterization of inference in inheritance systems, based on minimal models. In particular, we have pointed out what appears to be a deficiency in inferential distance based reasoners which causes unstable behavior 7 and a certain lack of predictability. While ID-reasoners work well on a num­ ber of networks, the minimal model reasoner seems more principled in its design choices.

The characterization presented here is quite intuitive, and it can be extended in .a number of ways. As it stands, the semantic interpretation of links and the se­ mantic account of the inference process are somewhat distinct. The approach may be augmented to account for more "general" inheritance reasoning by extending the the preference relation to E-models, rather than 1models. In this manner, we may account for the full interpretation of networks, and characterize how infor­ mation in non-network form can be integrated. Also, an account can be given of inheritable properties and relations of classes (see, e.g., [Touretzky 1986]). As ID­ reasoners and the approach presented here differ with respect to stability, the minimal model characterization cannot be construed as a semantics for these forms of inheritance. Those algorithms are of no use for comput­ ing the consequences of a network, in the sense defined here. While consequences can be derived in a "brute force" fashion, a (clearly desirable) syntactic account of the "traditional" sort has yet to be developed.

7 While inferential distance causes a violation of the "if" clause of the Cumulation Property, those reasoners (e.g. [Horty et al. 1986]) which use off-path preemption as well, also violate the "only if" clause, resulting in "super-unstable" behavior.

Acknowledgements

Thanks to Bart Selman for helpful discussion and Susan McRoy and Gerhard Lakemeyer (and the referees) for commenting on an earlier draft of this paper. This re­ search was supported by an NSERC Postgraduate Schol­ arship.