More Notes on "A Clash of Intuitions"

1 Introduction

A major problem for network representations of defea­ sible and default knowledge (called 'nonmonotonic in­ heritance structures') concerns the use of 'redundant' links. Whilst the use of shortest-path algorithms for de­ riving network conclusions returns the (intuitively) cor­ rect result in many cases, in many other cases it does not [Touretzky, 1 984]. One obvious answer is to as­ sert 'redundant' links explicitly into the network rep­ resentation so that shortest-path algorithms continue to work correctly. Such links represent binary assertions which explicitly relate by one link two nodes which pre­ viously were related by two or more intervening links. But the introduction of such 'redundant links' can make previously non-problematic network structures problem­ atic: unambiguous structures can become ambiguous, and there may be side-effects in other parts of the net­ work not involved with the redundant link.

Touretzky (1986] describes a formal mechanism called on-path preemption which comes into play when a re­ dundant link causes such problems. The general idea is that where there is a redundant link, another path can override paths containing the redundant link (as will be described later). The effect is to implement formally the basic requirement that, despite the presence of redun­ dant links, more general information should be overrid­ den by more specific, i.e. that information from more specific superclasses should take precedence over infor­ mation from more general superclasses in cases of con­ flict . However, Sandewall (1986] notes that Touretzky's definitions do not take into account cases where the reand so (typically) not grey. In this example elephant is a typical class in that elephants typically are grey. Royal .elephant, though, contains an exception to the typical class to which it belongs (elephant) . The ElL interpretation here is that Royal.elephant inherits the property of typical non-greyness from an exceptional class ('1') for which non-greyness is typical. Informa­ tion which is exceptional to the typical class and which belongs to the exceptional class is inherited as typical by subclasses and instances of the exceptional class, unless overridden.

The reasoning behind this interpretation is as follows. In the current literature the isa links are used to spec­ ify superclass relationships as well as infer inheritance relationships in the typical class case. In exceptional cases the not-isa link specifies a non-superclass relation­ ship but nevertheless requires a property to be inher­ ited, namely, the opposite of what would be typically inherited. This is questionable: if isa is used to specify class relationships as well as to infer inheritance relation­ ships, then not-isa should he used for explicitly ruling out certain class relationships (therefore stronger than no links at all) as well as prohibiting inheritance of any sort . However, not-isa is usually used to convey the in­ formation that the negation of the property referred to by a class name is to be inherited. The proposed excep­ tional class ('1') is meant to address this point explicitly, by allowing the opposite or negation of what would be typically inherited to be inheritable in its own right . This would leave not-isa to perform the simple but important task of explicitly ruling out certain subclassfsuperclass relationships, without necessarily being involved in as­ pects of inheritance.

ElL's approach here is to create an exceptional class which can be inserted into the structure so that the fol­ lowing new path results:

where 'If is the exceptional class which is just like the elephant class, except that it is a subclass to a class (non-grey things) which stands for the opposite of what elephants typically are a subclass of (grey things) . Mech­ anisms for locating 'If in inheritance structures will be provided later.

2.2 Acquired and inheritable properties

There is also a distinction between acquired properties, which are properties that an object picks up from the environment, and inheritable properties, which are prop­ erties that an object can inherit from its class{es). The underlying rationale is that an inheritable property has the same meaning no matter by what or whom it is inher­ ited, whereas an acquired property, since it is acquired by an object or class from the environment , cannot be passed by inheritance to other objects/classes without assuming that those objects/ classes have also acquired this property from the environment. Since this assump­ tion cannot always be guaranteed to hold, acquired prop­ erties can only be attached to objects/ classes if it is as­ serted that they have acquired that property from the environment.

3 Conceptual foundations of multiple inheritance with exceptions

The following definitions will make the assumptions and motives of ElL clear. First, multiple inheritance, and inheritable and acquired properties, are defined.

Definition 1 Multiple inheritance is the heredity of one or more properties by an individual or by a class, from two or more classes, either of which can be typical or exceptional .

Definition 2 An inheritable property is a property that may pass via a class to a subclass or individual.

Definition 3 An acquired property is a property derived from experience and training or as a result of interaction with the environment. This kind of property cannot be inherited by subclasses or individuals of a class which has an acquired property.

Next , exceptional class is defined .

Definition 4 An exceptional class (called 'If) f or an in­ dividual or class X is a typical superclass (if X is a class) or typical class (if X is an individual) created in order to explain inconsistencies (involving inheritable properties only) arising from multiple inheritance with exceptions. It is similar in all respects except one to another typi­ cal superclass or typical class (let us say Y ) of X. That is, 'If carries with it everything that Y does except that, in the case of one property that Y carries, Ill carries as inheritable the opposite of that property.

The basic rule of inference in ElL is defined as follows.

Definition 5 Given 'If , Y and X , where X is a subclass of both 'If andY, X will inherit from Ill rather than from Y . Also, subclasses of, and individuals belonging to, X will inherit from 'If rather than Y.

That is, 'If has more explicit informat ion than Y. The exceptional information is more explicit because what was previously implicitly inherited by means of a not isa link (e.g. Royal.elephant f. grey) is now explicitly en­ capsulated in a class of its own so that the exceptional in­ formation becomes typically inheritable in its own right. Also, the exceptional information prevents more general information overriding more specific, as will be shown later.

4 A semi-formal introduction to exceptional inheritance

Let

• x represent an object,
• a represent x's typical class or superclass which has an inheritable property,
• f3 be x's class or superclass which has an acquired property (/3 is called 'acquired class' in the defini­ tions that follow),
• 6 be the inheritable property of a,
• ( be an exceptional class which is just like a except for the inheritable property with which it conflicts,
• cr is the property in respect of which a and ( differ (i.e. the exceptional property),
• 1 stand for the conjunction of ...,cr( x) and -,6 ( x) ( nei­ ther exceptional nor typical inheritable),
• 0 stand for 'provided that',
• ® signify an inconsistency or conflict between two classes with respect to the inheritable property,
• t> stand for a class similarity relationship between two classes of an object, except for one property ( cr) on which they differ, and
• E><l stand for a bidirectional relationship between W and a, both of which are immediate (super)classes of x.

The general form of an inheritance rule in ElL is as fol­ lows:

which stands for: 'If r can be derived and provided that the exceptions ~ have been tested for, then derive 6.' There are also rules of the form

where inheritance conclusions require only the excep­ tions to be tested for. The exception ~ consists of a cr (an exceptional property) or a 1 (an acquired property), or both. If an element of ~ is positive, the interpreta­ tion is: 'provided that the exception holds', and if an element of ~ is negative: 'provided that the exception doesn't hold'.

Three primitive relations (where 1/J( x) has the inter­ pretation of class or object x belonging to tjJ where tjJ stands for a class) are now described. First,

i.e. x's exceptional class (if there is one) is exactly like a typical superclass a of x except for an exceptional prop­ erty cr in respect of which a and ( differ (Definition 4) . Then,

and

i.e. if x belongs to a typical class and provided that x does not belong to an exceptional class, then x inherits the inheritable property 6 of typical class a (P R2); and provided that x belongs to an exceptional class then x does not have the typical inheritable property 6 of a (PR3).

An exception indicator rule is represented as follows (bearing in mind that ( stands for a class which contains the negation of some inheritable property 6):

The following definition describes this rule:

Definition 6 If x is an a and provided that it belongs to an exceptional class ({where ((x) t>a(x) by P Rl above), then there is a conflict between these classes regarding the typical inheritable property 6.

Similarly, an acquired property conflict is defined as fol­ lows:

where the conflict concerns whether a typical inheritable property or an acquired property should be inherited. To draw the right inheritance conclusion:

Definition 7 If x has typical superclass a, and provided that x is neither an instance of an exceptional class ( nor an instance of an acquired class /3, then x inherits property 6.

The above definition is formalized by:

EIL2

This leads to the following exception rules:

Definition 8 If x has typical superclass a, and provided that x is an instance of an exceptional class ( but not an instance of the acquired class /3, then x inherits the exceptional property cr.

The rule can be represented as follows:

Definition 9 If x has typical superclass a, and provided that x is an instance of the acquired class f3 but not an instance of the exceptional class (, then x has the ac­ quired property by assertion.

The above definition can be represented as follows:

Definition 10 If x has typical superclass a, and pro­ vided that x is an instance of an exceptional class ( and also an instance of the acquired class /3, then x has the acquired property by assertion.

The above definition can be represented in a rule as fol­ lows:

In other words, the acquired property overrides an inher­ itable property. This is because the acquired property is an explicit property (declared and asserted by the user), whereas the inheritable property is a typical (implicit) one.

Finally, Definition 11 If z has immediate (super)classes lt and a, then lt 1><1 a, i.e. 'II and a are bidirectionally related in that they conflict over 6. The bidirectional/ink cannot be used for drawing inheritance conclusions.

The above definition can be represented in a rule as fol­ lows:

Bidirectionality (signified by+-+ in the networks below) is meant to express the possibility of mutual specialization between a typical class and its related exceptional class. That is, just as an exceptional class is similar to a typical class except for an exceptional property, a typical class can be regarded as similar to an exceptional class except for a typical property.

5 The Clyde-Royal Elephant problem revisited

Consider the following primitive paths:

These paths are depicted in Figure 2. Clyde is neither a

member of an exceptional class nor a member of a class which has an acquired property, using EIL2:

If the following primitive paths are included (giving us the structure depicted in Figure 1):

first a check is made as to whether there is any conflict with the previous assertions, using P R2 and P R3:

These primitive relations identify the conflict:

The condition, exception and conclusion in the conflict rule are used to locate \), namely, an exceptional, imme­ diate superclass of Royal.elephant (the exception in the rule) . The following two primitive paths are added:

'II is the exceptional class which has the missing, com­ plementary aspect regarding the typical superclass prop­ erty, and its negative link with that property, namely, 'II f+ grey, signifies this. It follows by EIL6:

'II 1><1 elephant .

Figure 3 shows the ElL representation of the structure. There is a new path:

Using EIL3:

Since there are no acquired properties ('y) to consider, the inheritance conclusion is ..,grey( Clyde) .

6 On-path preemption revisited

The application of ElL to the on-path versus off-path debate can now be demonstrated. On-path preemption applies if there is redundancy in the inheritance network. Consider Figure 4 which is just like Figure 1 but now con­ tains a redundant link (Clyde -+ elephant) which can be derived from two primitive links already in the struc­ ture: Clyde -+ Royal .elephant and Royal .e/ephant -+ elephant.

There are now three paths starting at Clyde:

• (a) Clyde -+ Royal.elephant f+ grey
• (b) Clyde-+ elephant-+ grey
• (c) Clyde-+ Royal.elephant-+ elephant-+ grey

Path (c) is pruned on the basis that it contains a node (Royal .elephant) from which there is a link to another node which occurs later in the same path (grey) and is of opposite polarity. Royal .elephant and the infor­ mation it contains is therefore more specific to Clyde than the nodes which follow Royal.elephant in path (c), i.e. elephant. Also, path (b) is pruned because there is another path (path (a)) in which there is a node (Royal.elephant) - called an on-path intermediate - from which starts a subpath of opposite polarity to that of (b). Since there is a link between the on-path in­ termediate and a node (elephant) in path (b), path (a) contains more specific information despite the redundant link which reduces both paths to equal length. Path (b) is therefore pruned to leave path (a). However, the no­ tion of on-path intermediate crucially depends on the ex­ istence of a redundant link which bypasses that on-path intermediate. Sandewall [1986] presents the structure shown in Figure 5 to point out the shortcomings of onpath preemption. The redundant link in the structure in Figure 4 between Clyde and elephant is interrupted by the African.elephant node, thereby resulting formally in the loss of the redundant link. On-path preemption would then not be applicable, and given a skeptical ap­ proach nothing could be inferred about Clyde's colour.

Sandewall's point is that the Clyde f+ grey conclusion should nevertheless go through, since this supports our intuition that African.elephant doesn't affect that part of the network dealing with Clyde's greyness. Since one of Clyde's two immediate classes has some explicit infor­ mation concerning greyness, this should be preferred to derived information in cases of conflict. Sandewall 's pro­ posal of off-path preemption was intended to build this preference for explicit information directly into the in­ ferencing mechanism. However, Touretzky et al. [1987] argue that this approach is less intuitive than on-path, citing the structure in Figure 6 as an example of where

the analogous conclusion that George does not drink beer is not intuitively supported. The structures de­ picted in Figures 5 and 6 have the same topology, how­ ever. As stated earlier, the fact that the intuitive reading in the George structure seems to require more general information to override more specific information (i .e. information attached to man (drinks.beer) to override information attached to chaplain in the case of George) questions the claimed usefulness of preemption generally.

The ElL view is that the two structures above are not of the same topology at a deeper level when ana­ lyzed with ElL. Consider the Royal.elephant example again (Figure 5). Following the same analysis as was made for the Clyde-Royal.elephant example (Figures 1, 3), the resulting structure is depicted in Figure 7. Royal .elephant will inherit non-greyness through the ex­ ceptional class, just as before, as will Clyde. This is be­ cause W contains more explicit information, and classes (or individuals of a class) containing exceptional infor­ mation will be preferred to non-exceptional classes in cases of inheritance conflict. African.elephant will in­ herit greyness through elephant -+ grey. The 'path' African.elephant -+ elephant -+ W f+ grey is no in­ heritance path at all, since the bidirectional relationship between elephant and W is not an inheritance relation­ ship (Definition 11 ).

Now consider again the George example (Figure 6). In the George structure, both the classes marine and chaplain acquire their property of drinks .beer from the environment. It is the explicitly acquired properties which have the last word in this structure (by EIL5 and EIL6), not the implicit inheritance properties from the class man. Therefore, since the acquired property of drinks.beer is not associated with either chaplain or marine directly in this structure, nothing can be di­ rectly inferred about George. There are then options as to where drinks.beer should be linked in as an acquired property (dashed lines in Figure 8) . The property of drinks.beer (or its negation)" can be explicitly located with man, chaplain, marine, or George, or with more than one (since acquired properties are not inheritable). The ElL representation of the problem structure is that this is straightforward multiple inheritance, with no in­ heritable exceptions. If it is claimed that drinks.beer is indeed an inheritable property of man (just as grey is of elephant), this must be argued for . And that argument is a different one from the on-path versus off-path de­ bate. Importantly, the ElL representation of the George structure removes the implication that in certain struc­ tures more general information is to be preferred to more specific.