Skeptical Inheritance: Computing the Intersection of Credulous Extensions

1 Introduction

Inheritance, like other forms of defeasible reasoning, sanctions uncertain conclusions. In unambiguous con­ texts, these conclusions are only as reliable as the general rules from which they are derived: concluding that a par­ ticular bird can fly is reasonable only if birds generally fly. Ambiguity introduces another kind of uncertainty: if we have evidence that Charlie is a bird, and other evi­ dence that he is not, our reasoning is still more uncertain because our assumptions are questionable.

t · Anti-Military

· Nixon

Credulous reasoning involves this second kind of un­ certainty. A credulous reasoner sanctions any internally consistent state of the world. For example, in figure 1, credulous inheritance allows either the conclusion that Nixon is a pacifist, or that Nixon is not a pacifist. In either case, the 'choice is arbitrary. Once we accept one of these conclusions, however, we can reason further: if we assume that Nixon is a pacifist, we can conclude that, like a typical pacifist, he is anti-military. Credulous in­ heritance permits us to believe that Nixon is not a paci­ fist, or is a pacifist, and therefore is anti-military, but either way our beliefs must be internally consistent.

0 The author is supported by an IBM Graduate Fellowship.

While credulous inheritance offers many alternatives, skeptical inheritance yields a single, unambiguous set of conclusions for any inheritance hierarchy. Ideally skep­ tical inheritance supports exactly those conclusions true in every credulous extension. In the next section, we provide formal definitions of ambiguity, credulous exten­ sions, and ideally skeptical inheritance. We then present two approximate approaches to skeptical inheritance, ambiguity blocking and ambiguity propagating inheri­ tance. The failure of these path-based approaches to be both sound and complete for ideally skeptical inheritance indicates the importance of reasoning about conclusions, or inferences, rather than about their supporting paths, or arguments. In section 5, we demonstrate an ATMS­ like labeling scheme for inheritance hierarchies, based on a limited form of Boolean satisfiability. This label­ ing gives a precise description of dependencies in the hierarchy, including an exact representation of ideally skeptical inheritance. Finally, in section 6, we present a definition of preemption, or specificity, and provide a polynomial-time algorithm for computing the results of specificity. Although the definition of specificity itself is neither skeptical nor credulous, the output of the speci­ ficity algorithm can be used as input to the ideally skep­ tical inheritance algorithm to yield a polynomial-time al­ gorithm for computing ideally skeptical inheritance with specificity .

2 Ambiguity and credulous extensions

An inheritance hierarchy r = (Vr, Er) is a directed acyclic graph with positive and negative edges, intended to denote "is-a" and "is-not-a" respectively. We write a positive edge from a to x as a· x, and a negative edge a · ·x. We call a sequence of positive edges a· St · · · Sn · x (n ~ 0) a positive path, and a sequence of positive edges followed by a single negative edge a· St · · · Sn · ·X ( n ~ 0) a negative path . 1 We use lower case Greek letters to stand for sequences of positive edges, so these positive and neg­ ative paths might be abbreviated a· u · x and a· u · -.x. We takes * to be a variable ranging over the set { ·, .-,} : s * x stands for any edge from s to x ( s · x or s · -.x) and s fx to stand for the edge of opposite sign ( s · -.x or s · x, respectively) .

1 The approach described in this paper is upwards rea­ soning. That is, inheritance works from the focus node up-

A path, or argument, a ·U*X supports the inference "a is (not) an x ." We use the notation a-+x (aftx) to stand for this inference, or conclusion, independently of the path through which it is derived. One inference-e.g., a-+x-may have many supporting arguments-a · u · x, a· T. x, etc. We use"'-'+ in much the same way as *· as a variable ranging over the set { -+, ft}, and say that a""-+ X if either a-+x or aftx. Throughout much of this paper, paths and inferences will be used interchangeably; in sec­ tion 4, however, the distinction will become important.

An inheritance hierarchy r supports a path a· u * x, written r I> a·U*X, if the path a ·Sl . .. Sn*X is in Er and it is admissible; f supports an inference a""-+ X if it supports some corresponding path. Initially, we will take "admis­ sible" to be vacuous: any path actually in r is supported. This is credulous inheritance at its most general, so that any conflicting paths are potentially ambiguous and re­ sult in corresponding credulous extensions. In section 6, we extend this definition to include a specificity criterion analogous to Touretzky's [1986] inferential distance.

A brief aside on , semantics is relevant here. If every conflict is taken to be ambiguous, preemption strate­ gies may be viewed as ambiguity-resolving heuristics­ preferences as to how these ambiguities should be re­ solved. This results in a preference-based semantics for inheritance, where credulous extensions play a role anal­ ogous to models in Shoham's [1988] model-preference se­ mantics for nonmonotonic logics. This is precisely the view we are espousing here; a more complete exploration of the approach may be found in [Stein, 1990].

Ambiguity arises when two supported paths conflict. Formally, an inheritance hierarchy r is ambiguous w.r.t. a node a if there is some node x E Yr such that r I> a-+x and r I> aftx. In this case, we say that the ambiguity is at x. Ambiguity is always relative to a node: for example, the hierarchy in figure 2 is unambiguous w.r.t. a, but ambiguous w.r.t . b (at e). Credulous inheritance is a means of resolving these ambiguities.

A credulous extension of an inheritance hierarchy r with respect to a node a is a maximal unambiguous sub­ hierarchy of r with respect to a: if xr,a is a credulous extension of r w.r.t. a, then there is no unambiguous subgraph of r supporting a proper superset of the paths

wards, rather than from the root downwards. The ramifica­ tions of upwards versus downwards reasoning are discussed in [Touretzky et al., 1987); some complexity concerns are de­ scribed in [Selman and Levesque, 1990].

..

that xr.a supports. An example of a network with sev­ eral credulous extensions-and some non-extensions-is given in figure 3. If xr,a is a credulous extension of r w.r .t. ar a is called the focus node of xr,a. If an exten­ sion X ,a?. a-+X, X is true in xr,a; similarly aftx and false in X ,a.

In general, there may be many credulous extensions of r. Iff is ambiguous w.r.t. a, there will be several exten­ sions of r w.r.t. a. {xr·a}; denotes the set of credulous extensions of r w.r.t. a. Further, {xr·a};-the set of credulous extensions w.r.t : a-may differ from {xr·b};: ambiguities which arise in determining what a is may never arise in determining what b is. However, comput­ ing the credulous extensions of a hierarchy w.r .t . mul­ tiple foci is independent of the order in which they are considered . 2

Choosing a credulous extension involves making an arbitrary choice. Skeptical inheritance is intended to se­ lect only those inferences that are not arbitrary. These are precisely the inferences which hold in any credulous extension, or possible state of the world. Formally, an inheritance hierarchy r skeptically permits an inference a"'-'+x, written r ~ a"'-'+X, if for every credulous extension xr.a E {xf'a};, xr,a I> a"'-'+X. ~ defines ideally skepti­ cal inheritance.

Unfortunately, there is no "skeptical extension" cor­ responding to the definition of ideally skeptical in­ heritance. The closest we can come is n(r, a), the subgraph of r containing those edges that are in every credulous extension of r w.r .t. a: 3 O(f, a) = (Vr, n r a Exr.a) . n(r, a) supports ex{ X; · }; i actly those arguments, or sequences of edges, that are in every credulous extension. However, there may be

inferences a"'-'+x that are supported in every credulous

2 It might therefore seem logical to define a credulous ex­ tension independently of any particular node; this would sim­ ply be a maximal subgraph with no ambiguity w.r.t . any node. Unfortunately, this is not terribly useful, as disam­ biguating one node (say, bin figure 2) can require eliminating perfectly good paths for another node (e.g. the path a-+e ).

3 Throughout this paper, we use the notation ~(r, a), where ~ stands for upper case Greek letter, to refer to a uniquely determined subhierarchy of r w.r.t. a: for example, the skeptical extension O(f, a); the ambiguity blocking ex­ tension B(f, a); the ambiguity propagating extension TI(r, a); the specificity extension E(f, a).

extension of r w.r.t. a, but have different supporting ar­ guments in different extensions: some extensions may contain one sequence of edges-a · u · x-while other ex­ tensions contain a different sequence of edges-a · T · x. Hierarchies with this property are discussed in section 4. This means that, n(r, a )-and any other path-based "skeptical extension" -can support at most a subset of the inferences ideally skeptical inheritance admits; cap­ turing the complete set of inferences requires reasoning about cases.

3 Ambiguity blocking inheritance

The first attempt at skeptical inheritance was taken by Horty et . a/. [1987]. 4 They argue that an ambiguous line of reasoning should not be allowed to interfere with other potential conclusions. Because this approach dis­ continues a line of reasoning as soon as an ambiguity has been reached, we refer to it as ambiguity block­ ing inheritance. Although Horty et. a/. describe one specific theory-including, e.g., a particular preemption strategy-ambiguity blocking inheritance defines a gen­ eral approach:

Starting from the focus node a, if a node x is ambiguous w.r.t . a in r, eliminate all edges into and out of x . When the entire hierarchy has been scanned, the remaining edges form a new network, B(r, a), which is unambiguous w.r.t. a. This is the ambiguity blocking skeptical extension of r; ambi­ guity blocking inheritance concludes that a network r admits a...,_.x exactly when B(r, a) I> a. (1' *X.

While ambiguity blocking inheritance seems reason­ able, it results in some anomalous conclusions. Consider, for example, figure 4. Ambiguity blocking inheritance on r with focus node a determines that e is ambiguous w.r.t. a, so it eliminates all edges to and from e. In particular, it eliminates the edge e · /, making f unambiguous w.r.t . a: B(f, a) I> a-+ f. This is certainly one possibility. But it is also possible that a-+e; and if a-+e, it is ambiguous whether a-+ /-that is, a might not be an f. It is cer­ tainly not safe to assume from the ambiguity at e that the path a · b · d · f is always true. But this is precisely what ambiguity blocking inheritance does. 5

4 According to Harty (personal communication), a "skep­ tical" approach to inheritance is one which offers a unique, unambiguous set of conclusions for any inheritance hierar­ chy. This differs with our intuition that "skeptical" means "unwilling to believe uncertain conclusions." In Harty's view, computing the intersection of the credulous extensions is only one way to reason "skeptically."

A more severe anomaly follows from this first. Ambi­ guity blocking inheritance computes a kind of "parity" on the number of ambiguities in a path. According to Horty et. a/., the network in figure 5 is skeptical as to whether a is-a e or an i, but supports the conclusions that a is-a g and a j. Similarly, this net is skeptical about whether b or f is-a j, but allows the paths from a and d to j. More than the first anomaly, this result calls into question the intuitiveness of ambiguity block­ ing inheritance. In any case, ambiguity blocking inher­ itance is promiscuous: there are inferences a"'-+x such that B(r, a) I> a'"'-+ X but r )'-a"'-+ X.

4 Ambiguity propagating inheritance

Unlike ambiguity blocking inheritance, ambiguity prop­ agating inheritance allows ambiguous lines of reasoning to proceed. An argument thus cannot be certain unless there are no counterarguments; in contrast, ambiguity blocking inheritance considers only unambiguous coun­ terarguments. Like ambiguity blocking inheritance, am­ biguity propagation defines a family of algorithms. One such algorithm is outlined here; a complete definition and discussion may be found in [Stein, 1989]. This al­ gorithm computes II(r, a), the ambiguity propagating skeptical extension of r w.r.t . a, in time O(Er ):

Starting from the focus node a, if a node x is am­ biguous w.r.t. a in r, rather than eliminating all edges to and from x, retain x but mark it as am­ biguous, and continue inheriting. Although paths to and from x will not be in II(r, a), they can still act as counterarguments and prevent other nodes from being unambiguous. II(r, a) is the subgraph of r with those edges X* y E Er such that X and y are both unambiguous w.r.t . a.

For example, the cascading ambiguities of figures 4 and 5, which gave ambiguity blocking inheritance difficulty, present no problem for ambiguity propagating inheritance. Figure 6 gives the ambiguity propagating extension for the network in figure 5.

5 Horty et. al. originally pointed out this difference be­ tween ambiguity blocking inheritance and ideally skeptical in­ heritance in (Harty et al., 1987] and [Touretzky et al., 1987) .

In fact, II(f, a) never supports extra paths. II(f, a) is a subset of n(r, a), the "best approximation" to a skep­ tical extension, with the further property that II(f, a) and n(r, a) support a~x for exactly the same nodes x. II(f, a) and O(f, a) both support those arguments, or sequences of edges, w.r.t. a that are true in all credulous extensions of r w.r.t. a. But there are some inferences a~x that are supported by every credulous extension of r w.r.t. a, but have different supporting arguments in different extensions. In these circumstances, we need to reason about inferences rather than paths.

For example, consider the hierarchy in figure 7. 6 Every credulous extension w.r.t. seedless grape vine supports the inference seedless grape vine -plant, so ideally skep­ tical inheritance concludes that seedless grape vines are plants. Suppose, for example, that a seedless grape vine is a fruit plant; then it is a plant. Suppose that it is not a fruit plant; then it is unambiguously an arbor plant, and therefore a plant. In any state of the world, no mat­ ter how we resolve the ambiguities of the taxonomy, a seedless grape vine is a plant.

If we wish to determine what is true in all possible worlds, we cannot avoid this kind of reasoning. There are facts which are true in all credulous extensions, but which have no justification in the intersection of those extensions. This is why we cannot generate a "skeptical extension" -no particular set of edges of r from seedless grape vine to plant is in every credulous extension, so no such path can be in the "skeptical extension." Thus every path-based approach to skeptical inheritance will always be either unsound or incomplete with respect to ideally skeptical inheritance. We can only compute the always-true inferences by, in effect, reasoning about all of the credulous extensions . Fortunately, in acyclic hier­ archies, such reasoning is tractable.

6 Apparently, Matt Ginsberg independently proposed a hi­ erarchy with similar properties, in which Nixon is always po­ litically motivated.

5 Ideally skeptical inheritance

Ideally skeptical inheritance, applied to an inheritance hierarchy r, computes those inferences a~x that have some supporting argument in every credulous extension of r w.r.t . a. We compute ideally skeptical inheritance by keeping track of the conditions under which an infer­ ence a~x has support. If a~x always has support, then it is true in every credulous extension of r . .

Let Cpos be the "positive children" of x-the nodes Pi E Yr with positive edges Pi · x E Er-and let Cneg be the "negative children" of x. Then if none of Cpos is true (i.e., not a-pi), x cannot be true: it has no support at all. If at least one of Cpos is true, but none of Cneg is true, then x is true: its true positive children provide it with a supporting argument. If at least one of Cpos is true, but at least one of Cneg is true, too, then x is ambiguous: it has some support, but there is also a counterargument.

We can phrase this as a constraint satisfaction problem: ·

a: The focus node is always true: r ~ a-+a.

V;G_po·; ::::>x: x cannot be true if none of its positive children IS.

((V;Cpo·;) 1\ V;Cneg;) ::::> x: If x has support but no counter­ argument, x is true.

There is no constraint corresponding to the third condi­ tion; if x is ambiguous, it is unconstrained.

If we conjoin these constraints, we get the bicondi­ tional

This is the condition under which r 1-- a-x. In the fol­ lowing algorithm for computing ideally skeptical inher­ itance, we label x with a formula corresponding to this constraint. The notation [x] = [y] means that the propo­ sitional variable y is the label of the node named x. The usual rules w.r.t. connectives, T, and 1., apply.

The label of x describes exactly those conditions under which the focus node a is-a x. If x is labeled T it is always true-r 1-- a-x. If x is labeled 1., its lab~l can never be satisfied, so there is no credulous extension of f W.r.t. a that SUpports a-x. If a node X is labeled cp, x is true (a-x) in exactly those credulous extensions where cp is true. For example, in the labeling of figure 1, [anti-military]= [pacifist]; that is, Nixon is anti-military in exactly those extensions in which he is also a pacifist.

To determine the properties of node a: 7

1. Label [a]= [T].

2. Label all leaves (other than a, if a is a leaf) [..L].

7 This algorithm computes the conditions under which a-+x. The condition under which a-f+x is given by (V;[Cneg;)) 1\ (V;[Cpo.;)).

Figure 8: a 1s an x whenever the label of x has truth value T .

1. For a generic node, x, with positive children Gpo·; and negative children Cne'i' label

Figure 8 gives the skeptical labeling of the hierarchy of figure 7.

This labeling corresponds roughly to an "ATMS label­ ing" of the hierarchy- the label of a node is its justifi­ cation. We can use the labeling for incremental update of the hierarchy. Consider, for example, the hierarchy of figure 1. If we later discover that Nixon is a pacifist, the labeling automatically tells us that he is antimili­ tary as well (since (anti-military] = (pacifist], and now [pacifist] = [T]) . In fact, we can incorporate all sorts of ambiguity resolving information-from specificity, to domain-specific knowledge, to updated beliefs-into this labeling simply by adding further constraints.

The complexity of this extended labeling algorithm, including further constraints, is unknown. Since it is a special case of boolean satisfiability, the problem may be N'P-hard. However, for the limited case of determining that a label is falsifiable-i.e. that there is some cred­ ulous extension that does not include the node-Kautz and Selman [1989] provide a polynomial algorithm. This means that we can compute the exact intersection of credulous extensions- ideally skeptical inheritance-in polynomial time.

6 Specificity

In the discussion of skeptical inheritance above, we as­ sumed that all paths in the hierarchy were equally ac­ ceptable. In this section, we describe a specificity crite­ rion, or preemption strategy, that makes choices among certain competing paths. The idea of a specificity criterion dates from [Etherington and Reiter, 1983) and [Touretzky, 1986) . Since then, many definitions of specificity have appeared in the literature, but all op­ erate on the same underlying principle: more specific information is likely to be more accurate. For example, in figure 9, information about penguins is more specific to Tweety than information about birds, so we can infer that Tweety does not fly.

We define specificity recursively. Certainly, if a * X E Er , then r supports a..__..x- that is, both the path, and the inference "a is (not) an x ." But what about compound paths?

Consider the path a. u *X (u = Sl . .. Sn, n;::: 0} . r supports a· u * x w.r .t . a if

1. None of the edges of a· u (a · s1 and s; · Si+l, (1 5 i < n)) is redundant in r w.r.t . a,
2. r supports a . u, and
3. a· U +X is not preempted in f w.r .t . a.

More generally, r supports b . T * w w.r .t. a if for every set of positive edges u, whenever r supports a · U · b, f also SUpports a · U · b · T * W .

The path a . u * X is preempted in r w.r .t . a there is some direct intermediary s; E u, with i strictly less than n, such that r supports the path a · s1 · · · s; I x .

An edge b · w is redundant in r w.r .t . focus node a if r supports some path b . ql ... qn . w, n strictly greater than 0, w.r .t. a, and r does not support a · r · ·q;, for any 0 5 i 5 n, w.r.t. a.

Although the definitions of supported and redundant are mutually dependent, they are not circular. Because the hierarchy is acyclic, it can be ordered topologically, and the definition of support for a path from a to x depends only on the redundancy of nodes strictly topo­ logically earlier than x.

The difficulties caused by redundant links were noted by Touretzky [1986] : in the second hierarchy (f') in fig­ ure 9, the edge from king penguin to bird is redundant­ king penguins are typically birds even without that link. However, if that edge is not excluded, there will be a path Tweety · king penguin · bird · flies for which no in­ termediate node has an edge to -.flies. Clearly, this is not the intended meaning here (or, indeed, in any net­ work of this form, since the "penguin" node is always more specific than the "bird" node).

This definition of specificity is on-path and upwards. On-path means that a path is preempted only if one of its member nodes is involved in a counterargument. In contrast, some preemption strategies also allow a path to be preempted by a counterargument originat­ ing with a node off the path. Upwards inheritance rea­ sons about the properties of a particular object, rather than the objects possessing a particular property. Our definition most closely resembles an upwards version of [Touretzky, 1986] .

If we examine a hierarchy, r J from the perspective of a particular node, a, specificity provides a means of prun­ ing the hierarchy- removing those edges that have been preempted . We call this subhierarchy E(r, a) , the speci­ ficity extension of r w.r.t . a. For example, the speci­ ficity extensions of the hierarchies in figure 9 w.r.t. king penguin are shown in figure 10. The definition of speci­ ficity above always yields a unique specificity extension for a hierarchy w.r.t. a focus node. Figure 11 gives a polynomial-time algorithm for calculating the specificity extension of an inheritance hierarchy.

Not all of the ambiguities in an inheritance hierarchy are susceptible to specificity. For example, "diamond" ambiguities such as the Nixon diamond of figure 1 can­ not be resolved using any preemption technique. For this reason, E(r, a) may still contain ambiguities, and may yield several credulous extensions w.r.t. a. These credulous extensions are the possible world-states con­ sistent with the specificity criterion, and are a subset of the possible world-states delimited by r-the credulous extensions of r w.r.t. a. In particular, the credulous ex­ tensions of E(r, a) are the preferred extensions of r w .r. t . a, according to the preference induced by specificity:

Let X[·a and X[·a be two credulous . exten­ sions of an inheritance hierarchy r w.r.t. focus node a. Then specificity prefers X[·a to X[·a (X[·a ~ X['a) if there are some node x and non­ redundant, preempted path a · IT* X in r such that x[·a supports a·u·x and x[·a does not, and x[·a and x[·a agree on all nodes that topologically pre­ cede x (according to some topological sort). 8

7 Discussion

Hierarchies like figure 7 demonstrate that determin­ ing universal truths requires reasoning about inferences rather than paths. It follows that any purely path-based approach to inheritance must be either unsound or in­ complete for ideally skeptical inheritance. Some addi­ tional bookkeeping mechanism, such as the "ATMS la­ beling" introduced here, must be added to inheritance systems that perform this type of reasoning.

The framework for skeptical inheritance, and the preference-based semantics of (Stein, 1990], are both independent of a particular definition of speci­ ficity. However, the tractability of the specificity criterion in section 6 makes it particularly use­ ful here. Recent results (Kautz and Selman, 1989, Selman and Levesque, 1990] indicate the intractability of many basic inheritance problems. Our specificity cri­ terion provides a tractable basis for both credulous and skeptical inheritance reasoning.

Proofs of several results described in this paper, and further exploration of these ideas, may be found in (Stein, 1989].

8 We could insist that x[·a and x[·a agree on all nodes that precede x in any topological sort. It turns out that the minimal elements under this definition of preference are equivalent to the minimal elements under the definition given here.

Compute-Specificity-Extension

Acknowledgments

Discussions with Leora Morgenstern, David Touretzky, Jeff IIorty, Henry Kautz, and the (individual and col­ lective) members of Brown University AI group were in­ valuable in this work. The comments of the two IJCAI referees were extremely helpful as well.