A Skeptic's Menagerie: Conflictors, Preemptors, Reinstaters, and Zombies in Nonrnonotonic Inheritance

1 Introduction

In earlier work we presented a skeptical approach to nonmono­ tonic inheritance reasoning [ 4] that differed in several respects from Touretzky's original credulous approach [15]. The main difference is that conflicting paths such as the well-known Nixon diamond generate multiple extensions in a credulous reasoner, while a skeptical reasoner produces a single exten­ sion in which all conflicted paths are excluded. As discussed in our "Clash oflntuitions" paper [ 16], inheritance systems of either type may differ in several other technical respects, such as the direction in which arguments are extended in comput­ ing inheritance (upward vs. downward reasoning), the precise definition of the preemption relation, the treatment of nega­ tive information, and the admission of strict (as opposed to defeasible) links.

In this paper we analyze another major point of difference among nonmonotonic reasoners: the treatment of defeated · paths, primarily in skeptical systems. We define several types of possible interactions among paths according to the types of defeat involved. This "skeptics's menagerie" provides new in­ sights into inheritance reasoning, and helps us to evaluate the computational consequences of alternative axiomatizations.

2 Defeat in Inheritance Systems

Let r bean inheritance network containing defeasible positive or negative links of form x ..... y or x -f. y. A path u through a network is a sequence of links, e.g., the path x ..... y -f. z is composed of the links x ..... y andy -f. z. Let rJ> be the extension of r containing all paths through r permitted by some upward skeptical inheritance rule, such as the one in [ 4]. By definition, r ~ rJ>. We say that r "permits" u (written r ~ u) iff u E rJ>.

John F. Horty

Institute for Advanced Computer Studies University of Maryland College Park, MD 207 42

Definition 1 A path p is a situator of x ---> r ---> w -f. y with respect to x ---> u ---> z ---> y iff p has the form x ---> r1 ..... w ..... ~ ..... z. (Similarly for paths of opposite polarity.) .J

A situator establishes the "betweenness" required by the inferential distance metric for preemption to hold. The above definition produces "off-path preemption" (16], originally proposed by Sandewall [Ill. For .. on-path preemption" we require a closer relationship between the subject path and the situator: x ---> u ---> z' must be a subpath of p.

Definition 2 A path x ---> u ---> z ---> y is preempted in F iff F ~X ---> U ---> Z and there iS a preemptor path X ---> T ---> W -/-+ y with a permitted situator. (Similarly for paths of opposite polarity.)

In the famous "Clyde the elephant" example, the path Clyde ..... Elep'hant---> Gray is defeated by the preemptor Clyde ..... Royal-Elephant -f. Gray, since l' permits the situator Clyde ..... Royal-Elephant ..... Elephant. In our definition the situator must be a pet:mitted path, but some inheritance schemes only require the two subpaths x ..-+ r1 ---> w and w ---> ~ ---> z to be permitted [2; 6]. Inheritance systems also disagree about whether the preemptor must be permitted; some require only the initial segment x ..... r ---> w to be permitted.

Definition 3 A conflictor of a path x ---> u ---> y is a path x ..... r -f. y having no permitted situator with respect to the former path. (Similarly for paths of opposite polarity.)

Definition 4 A path x ---> u ---> y is conflicted in F iff F ~X ---> u and there is a conflictor x ---> r -f. y such that r ~ x ---> r. (Similarly for paths of opposite polarity.)

In the classic Nixon diamond example, the conflicted paths are Nixon --->Quaker --->Pacifist and Nixon --->Republican f+ Pacifist. Each is a conflictor of the other because neither is situated with respect to the other.

Conflictors, being unsituated, always generate multiple ex­ tensions in a credulous theory, or no conclusion in a skeptical theory, unless they are preempted by a direct link. We view direct links as preemptors and not conflictors because a direct link x -f. y is always situated with respect to any path from x to y; therefore it can never generate multiple extensions or no conclusion the way a true conflictor can. Returning to the elephant example, the direct link Royal-Elephant -f. Gray preempts the path Royal-Elephant ..... Elephant---> Gray, but does not conflict with it.

Definition S An inheritance defeater is either a conflictor or a situated preemptor.

The concept of a defeater as a general category of paths that interfere with a particular argument is due originally to Pollock [9; 10]. Since his overall theoretical framework is so different from ours, however, it is hard to find any exact correspondence between his notion of a defeater and the one presented here.

The definition of inheritability varies depending on whether one is using upward or downward reasoning. For upward reasoning we have:

Definition 6 A path x - u - y - z is inheritable iff x - u - y is permitted andy - z E r. (Similarly for negative paths.)

All links in r are permitted. Permission of longer paths is defined in terms of inheritability and defeat:

Definition 7 A path is permitted if it is inheritable and has no defeaters.

Finally, we need to define the conclusions an inheritance theory allows one to draw from a network:

Definition 8 r supports the conclusion x -+ y iff its exten­ sion contains some path x - u - y. (Similarly for negative paths.)

3 Defeater Defeaters

Some inheritance systems prohibit defeated paths from them­ selves acting as defeaters. In such a system, the ability of a path to act as a defeater may itself be defeated by some other path. Thus, these systems are said to admit "defeater­ defeaters," another term due to Pollock, and later used by Loui [7]. Since in these systems defeating a path prevents it from defeating other paths, adding a defeater-defeater to a nonmonotonic network can reinstate a previously defeated path. Given the two types of inheritance defeat defined in the preceding section, there are five types 1 of defeater-defeater in an inheritance system:

• preemptor-preemptor
• preemptor-conflictor
• conflictor-preemptor
• conflictor-conflictor
• situator-preemptor

These different types of defeater-defeater can have different effects in inheritance networks, and in some cases there is disagreement about the best way to handle them. We shall consider several of these issues in the following sections.

4 Reinstatement

Consider the network in Figure 1. The path X - Chicken f+ Flies is a preemptor of X - Chicken - Bird - Flies; it is situated by X - Chicken -+ Bird. It is not necessary that X - Chicken f+ Flies actually be a permitted path for it to be a preemptor. (In fact, X -+ Chicken f+ Flies is defeated by the direct link X - Flies.) But suppose we decided that preemptors must be permitted. This would cause the longer path to go through, since it has no permiued preemptor. In this case the path X - Flies would be acting as a "reins tater" of X - Chicken - Bird - Flies.

1 This missing type, situator-confiictor, will be discussed in sec­ tion 5.

· X

Figure 2: Conflictors can be reinstaters only in credulous theories.

Definition 9 A reinstater is a path whose permission defeats preemptors of other paths to the same conclusion, thereby allowing them to also go through.

Reinstaters are a type of defeater-defeater; specifically, they are preemption defeaters. In skeptical systems, reinstaters must be preemptor-preemptors, not preemptor-conflictors, since a reinstating path by definition must be permitted; in a skeptical system conflictors are never permitted. But in credulous reasoners conflictors will be permitted in some ex­ tensions, and can therefore act as reinstaters there. In Fig­ ure 2, for example, note that x -+ p - y is a conflictor of x -+ q f+ y, which is in turn a preemptor of x - q - r - y. The path x - p - y will be permitted in one of the two credulous extensions, and in that extension it can reinstate x -+ q - r - y if the inheritance axioms permit reinstate­ ment.

Reinstatement may not be desirable in inheritance reason­ ing. Suppose node X in Figure 1 stands for the concept "chicken with a jet pack." We have directly asserted that chickens with jet packs can fly, but the reason for their fly­ ing has nothing to do with their being birds. Therefore the direct link does not logically support the argument the rein­ stated path represents, which is that X can fly because birds fly. In general, the problem with reinstaters is that they al­ low any defeated argument to go through if its conclusion holds, even if the argument's reasons are undercut by more specific information. Therefore we conclude that reinstaters are undesirable.

To test our example further, suppose that X stands for the concept "wild chicken," and that wild chickens, having stronger wings than their domestic cousins, can fly. In this case the wild chicken's flying ability really is a consequence of its being a bird. This may seem to be evidence in favor of reinstatement, but what it really shows, we believe, is that the network of Figure 1 doesn't capt\U'e all of our knowledge about the relationship of wild chickens to ordinary chickens. In particular, it doesn't express the fact that the reason why wild chickens fly is that they cancel precisely those excep­ tional properties of chickens that prevent them from flying. Figure 3 shows one way to express this knowledge. The network mixes strict and defeasible links, and under the def­ inition of· inheritance given in [3], the path Wild-Chicken=> Chicken=> Bird-+ Strong-Wings-+ Flies is permitted. It is not, however, "reinstated" (as we have defined the term), as there is no preemptor that could have defeated it. This fol­ lows from the fact that no positive path from Wild-Chicken can reach Weak-Wings.

Reinstatement can affect not just the arguments a network permits, but also the conclusions it reaches. In Figure 4, if we do not allow reinstatement, the link x ...... o does not cause r to permit the situator path X ...... m -;. n ...... 0. Therefore the two paths x -+ m -f+ y and x ...... o ...... y conflict, and so a skeptical reasoner will draw no conclusion about whether x is a y. But if reinstatement is allowed, the permitted situator x-+ m -+ n -+ o causes x ...... m -f+ y to preempt x--. o ...... y, causing us to conclude x -f+ y.

Although reinstatement may be semantically undesirable, the parallel marker propagation algorithms described in [4] for defeasible nets and [17] for mixed nets depend on this property in order to compute preemption efficiently. One of the lemmas in the correctness proof of the algorithm in [4] States (roughly) that if X-+ Zt E F, Z; -+ Zi+l E F fori from 1 to n - 1, and r supports x -+ z; for i from 1 to n, then F ~X -+ Zt -+ ... -+ z,..

Consider what happens when the inheritance query algo­ rithm is asked to determine whether xis a y in Figure 4. Pro­ cessing nodes in degree order, the algorithm puts the "true" mark MT on x, m, n, and o, indicating that r supports x -+ m, X -+ n, and X -+ 0. Then it is ready to determine Whether F supports the conclusion x -+ y or x -f+ y. It marks all nodes with MT having a direct positive or negative link to y with marker Mdir; both m and o are so marked. Next, any nodes on preempted paths must be eliminated. A preemption mark, Mpre. is used to kill off nodes whose link to y is preempted by some lower node. This is done in a very simple way: Ev­ ery node with Mdir sends Mpre up"-+" links, and Mpre is propagated upward across"-+" links into nodes with MT as far as it will go. So node m first sends Mpre to node n, and node o sends it nowhere because no node above o has MT. Propagation then causes Mpre to spread upward from n too, killing off o. Finally, only those nodes that have Mdir and not Mpre are allowed to send MT up"-+" links or Mp up"-/-+" links toy. Since m is the only node meeting these conditions, y is marked with MF, meaning r supports x -f+ y.

The important thing to note here is that the preemption marker Mpre that originates at m flows from n to o precisely because m, n, and o are all marked with MT, meaning r supports x -+ m, x --. n, and x -+ o. But the preemption is only valid because, as the lemma tells us, this guarantees that F ~X -+ m -+ n -+ 0. The lemma holds for the sys­ tem in [4] because its definition of inheritance requires that preemptors not have preemptors of their own; this is what produces reinstatement.

In more recent work, Horty has developed an alternative axiomatization of skeptical preemption that does not admit reinstaters [51. In this scheme preempters need not be permit­ ted; they can defeat other paths even if they themselves are preempted by more specific paths.

· a

Figure 5: An example of a situator-preemptor.

It is an open question whether preemption without rein­ statement can be computed efficiently without enumerating all possible situator paths. It cannot be done using just par­ allel marker propagation with a bounded number of markers. The reason is that, referring to Figure 4 again, there can be an arbitrary number of paths between m and o. Only one of these need go through in order to situate the preemptor x -+ m -f+ y with respect to x- o - y, and each situator must be examined independently.

Thus we see the possiblity for an interesting tradeoff be­ tween inheritance definitions: some give the most "correct" results, while others have efficient algorithms that are correct in most cases, but will produce different results in certain situations. 2

5 Defeat of Situators

The previous section looked at defeat of preemption by de­ feating the preemptor. It's also possible to defeat preemption by defeating the situator. This form of defeat can result in a conflict (skepticism or multiple extensions) rather than the replacement of a conclusion with its opposite.

Figure 5 shows an example of a situator-preemptor. The path a -+ d - e has preemptor a - b -f+ e, with situator a - b - c - d. But the preemptor isn't situated because the situator isn't permitted; the link a -f+ c preempts its initial segment a - b - c. Unsituated preemptors are conflictors, so we must be skeptical about whether a is an e.

Situator-conflictors are excluded from our list of defcater­ defeaters because they have no independent effect. Let p be a path of form x - Tt -+ w - r:z - z. Suppose p is a situator of x -+ r -+ w -f+ y, a potential preemptor of the subject path, x -+ u -+ z -+ y. Then a conflictor ~ of p must be of form x -+ J-1. -f+ z, which also makes it a conflictor of x - u - z, an initial segment of the subject path. In all skeptical definitions, if an initial segment of a subject path is conflicted, the subject path is not even potentially inheritable; it will not be permitted. It therefore does not matter whether the subject path's preemptors have permitted situators.

~he tradeoff is further complicated by the fact that theoretical well-behavedness may not be the same as intuitive correctness. In [5], it is shown that skeptical extensions allowing reinstatement can be defined directly through a fixedpoint equation, while the only known definitions of skeptical extensions without reinstatement rely on an iterative process using degree. To the extent that fixedpoint approaches in nonmonotonic reasoning seem more declarative than iterative definitions, this may provide a theoretical reason for prefer­ ring reinstatement.

In credulous theories there are two cases to consider. Let e be a conflictor of the situator p. In extensions that supportx -f+ z (because e is permitted), the subject path has a conflicted initial segment and will not be inheritable. In extensions that support x -+ z, p will be a permitted path, and hence the situator will not be conflicted. So in credulous as well as skeptical theories, situator-conflictors do not function as defeater -defeaters.

6 Conflicted Paths

An important difference between defeat by preemptors vs. de­ feat by conflictors is that preempted paths cannot be extended further; they are dead. Conflicted paths will hold in some qedulous extension, and thus can be extended there, perhaps giving rise to other instances of defeat.

Since skeptical reasoning as defined in [4) does not allow conflicted paths to be extended, one way of making a path go through is to conflict some initial segment of its defeater. In the double-diamond example reproduced in Figure 6, be­ cause Nixon is conflicted about Pacifist, the negative path to Anti-Military goes through unopposed. Thus, the path Nixon - Republican -f+ Pacifist is acting as a conflictor-conflictor, another type of defeater-defeater.

An alternative notion of skepticism to the one presented here is one where the extension is the intersection of all cred­ ulous extensions. In [16) we called this "ambiguity propaga­ tion," and Stein and others view it as a more rational or pure form of skepticism [14; 8). Conflicted paths in such a system cannot be salvaged by conflictor-conflictors. This observa­ tion has led Makinson and Schlechta to propose the notion of "zombies:" conflicted paths that are dead but can still kill other paths [8]. In their proposal, conflictor-conftictors would not be defeater-defeaters. Thus, even though we are con­ flicted about Nixon's pacifism, we would still go on to form the zombie path Nixon-+ Quaker-+ Pacifist-+ Anti-Military to conflict with Nixon- Football-Fan f> Anti-Military, caus­ ing us to be skeptical about the upper diamond in Figure 6 as well as the lower.

Stein [13; 14] and Makinson and Schlechta [8] have shown that the intersection of all credulous extensions may not sup­ port some of the conclusions that all extensions support. This occurs when a conclusion is reached via different paths in two extensions. (Makinson and Schlechta call this a "floating conclusion.") Thus, marker propagation algorithms (which by our definition are limited to a constant number of markers) cannot support this ideal form of skepticism, since there is no way to keep track of which conclusions were reached in which extensions.

Recently, Schlechta has shown that no path-based ap­ proach to skeptical reasoning (for any "reasonable" form of skepticism) can produce the intersection of credulous exten­ sions [12]. Hence, we cannot even axiomatize ideal skep­ ticism in our purely path-based formalism. However, the analysis of various defeater-defeater situations reported here applies to other formulations of inheritance as well.

7 Defeat in Mixed Nets

Networks that mix strict and defeasible links, as in [3] and [5], use similar definitions of defeat to the ones presented here, ex­ cept that strict extensions of paths must be taken into account. (The strict extension of a path is the set of nodes reachable by purely strict links from the path's conclusion.) For example, a reinstater need not have the same conclusion as the reinstated path; the reinstated path's conclusion simply needs to be in the reins tater's strict extension.

One very interesting idea for mixed nets is to require that situators be strict paths. This is in accordance with Brach­ man's observation [I] that inclusion in natural hierarchies is strict; only properties are defeasible. Note that our proposal does not reduce the network to a simple class/property system as defined in [15], since it is still possible to chain off of defea­ sible links, defeasible inferences can have strict extensions, and they can generate conflicts. However, the preemption relation is simplified by requiring situators to be strict, since only defeasible paths have the potential to be reinstated, and these can never be situators.

Unfortunately, we still cannot allow reinstatement without affecting the conclusions the system will reach. Figure 7 shows an example of why this is true. The path x ~ v f> m <= y preempts x ~ v ~ u - y, with a strict situator x ~ v ~ u. The preemptor is itself preempted by the direct link x- m. But with no reinstatement, this does not restore any path from x toy. Therefore we should reach no conclusion about y. An axiomatization in which preemptors must be unpreempted (leading to reinstatement) would conclude that xis a y,

8 Conclusions

Inheritance theory has a richer structure than we previously imagined. Complex patterns of defeat and reinstatement were known to exist, but had not been systematically analyzed. Even within a narrow family of reasoners, such as skeptical, upward, purely defeasible systems, we find that differences in axiomatization can affect both the results produced and the efficiency of inference.

There are two immediate observations to be drawn from our investigations. First, axiomatizations of inheritance should avoid reinstatement, because it is semantically undesirable. But, second, marker propagation systems 3 have implicitly re­ lied on reinstatement, by assuming that preemptors will be permitted paths, in order to compute permission efficiently. Since they also cannot implement ideal skepticism, we con­ e! ude that simple marker propagation architectures may not be as well-suited to inheritance reasoning as previously thought. They may still be useful as fast query/retrieval devices, pro­ vided that the correctness of the query algorithm is enforced by other means, such as the conditioning algorithms of [15], or is shown experimentally to provide correct results for most naturally occurring networks.

Acknowledgements

This work was funded by National Science Foundation grant IRI-9003165. We thank Bart Selman and one of the anony­ mous referees for helpful discussions.