An Evidence-based Framework for a Theory of Inheritance

1 Introduction

The notion of nonmonotonic inheritance is fundamental to common-sense reasoning. For instance, knowing that Bateman is a mammal, one would conclude that it does not fly. This is because normally mammals do not fly and in the absence of any other information, we regard Bateman as inheriting its inability to fly from mammals. H one later learns that Bateman is a bat, then he will probably change his mind, concluding that it does fly. However, after learning that Bateman is a dead bat, he would again change his mind concluding that it cannot fly. In this example, knowing that Bateman is a bat is more informative than knowing that it is a mammal, and knowing that it is a dead bat is even more informa­ tive, as far a5 Bateman'· ability to fly is concerned. In essence, the knowledge that an individual belongs to a subclass provides more information about the individual than the knowledge that the individual belongs to its superclass. We also notice that the first two conclusions are defeasible, while the third one is not.

Birds normally fly, while toys normally do not. H an item is a toy bird, then we conclude that it does not fly. This is because the item being a toy contributes more evidence in support of its inability to fly than does bird in support of its flying ability. Notice that there is no class-subclass relationship between toys and birds.

Some approaches to inheritance (e.g., [Touretzky, 1986], [Horty et al., 1987]) are proof-theoretic. They give algorithms for computing sets of acceptable paths supported by a network, rather than specifying the states of the world the network represents. Others (e.g., [Etherington, 1983], [Haugh, 1988], [Krishnaprasad et al. 1988a], [Przymusinska and Gelfond, 1988], [Thoma­ so~ et al., 1987]) present translations of inheritance net­ works into some standard logical formalism. The seman­ tics of the networks is then captured through the model theory for the respective logical formalism. In particular, a theory based on prioritized circumscription transforms a network into a set of first-order sentences augmented with meta-level minimality constraints embodying pref­ erence· [Krishnaprasad et al., 1988a]. The first-order models of the resulting translation are the states of the world the network represents. The circumscriptive the­ ory of [Haugh, 1988] formalizes the network at a meta­ level. The set of models of the translation in [Haugh, 1988] encode· the meaning of the network. [Przymusin­ ska and Gelfond, 1988] views a network as representing a set of beliefs of a rational agent, and captures this interpretation by translating the network into Moore's Autoepistemic logic [Moore, 1985]. The preference crite­ ria is axiomatized in the translated theory. [Pearl, 1988] provides probabilistic semantics to networks, by assign­ ing to them a set of possible worlds and an associated probability distribution.

We propose to view networks as specifying a set of belief-evidence pairs. "Strength of evidence" is explicitly incorporated into the object language, and we have de­ veloped a model theory for the resulting logic. The dom­ inance of property inheritance from a subclass over that from a superclass is captured by making the evidence contributed by subclass membership stronger than that contributed by superclass membership. This provides an evidence-based semantics to networks as a set of justified beliefs.

In this paper, we present a logic to formalize inher­ itance networks by combining concepts from logic pro­ gramming and multi-valued logics in a uniform frame­ work. The main ideas behind this approach are as fol­ lows:

• A naive formalization of inheritance networks in first-order logic leads to inconsistencies. As we do

not have a satisfactory means of modifying a the­ ory in the presence of "equally strong" conflicting evidences, we pursue an approach in which contra­ diction can be represented explicitly [Belnap, 1977a] [Blair, 1987] [Kifer and Lozinsk.ii, 1989] [Thomason et al., 1987], thereby providing an adequate rep­ resentational framework for ambiguous inheritance networks.

• Ambiguity in inheritance networks leads to an ex­ plosion in the number of expansions that could arise. (See [Etherington, 1983] [Haugh, 1988] [Kr­ ishnaprasad et al., 1988a] [Pad~ham, 1988] [Przy­ musinska and Gelfond, 1988] lTouretzky, 1986].) Furthermore, reasoning in the intersection of all the expansions is not computationally viable [Touret­ zky, 1987]. Thus, computational efficiency consider­ ations force us to look in the direction of formalisms that associate fewer models to networks. In this pa­ per, we show how a unique model can be associated with every inheritance network. This resembles the d:eptical theory of non-monotonic inheritance net­ works of [Horty et al., 1987], but is more general.
• To compute property inheritance, we need to per­ form certain bookkeeping functions such as track­ ing down the relative strengths of evidences. This is formalized by specifying how true or false a given statement is and how much is known about it [Gins­ berg, 1986].
• Our specification language is a Horn clause lan­ guage. The "ordering" of the evidences in the rule heads embodies the meta-knowledge about the pri­ orities associated with the abnormality predicates in the circumscriptive theory of [Krishnaprasad et al., 1988a]. The truth and the information order. ings can be incorporated into the logic language by extending its syntax and modifying the definition of satisfaction, that is, truth of a sentence in a model, along the same lines as in [Blair, 1987] [Kifer and Li, 1988] [Kifer and Lozinsk.ii, 1989].
• Most importantly, our approach is based on solid logic foundations, which provides a basis for the design and optimization of provably correct inheri­ tance algorithms.

In summary, the evidence-based logic developed here gives an alternative way of representing inheritance net­ works. In addition, this formalism can also be used to specify the formal semantics of inheritance networks by translating the networks into it.

In Section 2, we develop a logical framework for in­ heritance networks. In Section 3, we discuss the charac­ teristics of our approach and present extensions such as "preferential" inheritance and inheritance through paths with "negative" arcs.

2 An Evidence-Based Theory

2.1 Language

A term is an individual constant or a variable. An atom is a proposition or a formula q(t), where q is a unary predicate and t is a term. Literal· are of the form p : T, where p is an atom and T is a priority con1tant. A rule is a statement of the form p : T <= q : "'(, where p and q are atoms, T and "'( are priority constants. A fact is a ground literal. A clau1e is either a fact or a rule.

To capture dependency relationship among predicates, we define ~ relation as follows.

Definition 1 q ~ p (read q precedes p) iff either there is a rule in P of the form p: T <= q: "'(, or, recursively, p : T <= r : A and q ~ r.

An inheritance 1pecijication is a set of clauses, such that ~ is an acyclic partial order on atoms. This elim­ inates the possibility of "recursive" inheritance, whose utility is unclear.

2.2 Priority constants

The priority constant T in p : T represents the type and the relative strength of evidence in support of p. Fol­ lowing [Belnap, 1977a] [Ginsberg, 1986] [Fitting, 1988], the priority constants are viewed on two different scales: one on the basis of their truth-content and the other on the basis of their information-content. For instance, -3 in the negative literal p : -3 represents an evidence of strength 3 supporting -,p. The following relations are defined on the set of prionty constants.

• ~l is a semi-lattice order, i.e., a partial order equipped with the least upper bound operation. We will use lubJJ(A) to denote the least upper bound of the set A.
• R:t is an equivalence relation on priority constants with respect to truth-content. For our purposes, we need only three equivalence classes representing differing information levels of truth, falsity or in­ consistency in the evidence for an atom. To model both strict and defeasible links, we require that each equivalence class of R:t has a unique ~JJ-maximal el­ ement. These can be thought of as signifying true, falle or top (inconsistent) element and may be used to override any default conclusions that may be derivable from the specification.

Additionally, we define:

• e (T <JJ '"f) iff (T ~l '"f) A (T :f. '"f).
• e (T ~tl '"f) iff (T ~l '"f) A (T R:t '"f).

2.3 Interpretation and Model

Let E be a set of clauses. The domain D of any Her­ brand interpretation is collection of all individual con­ stants mentioned in E. A Herbrand ba1e of E is a collec­ tion of all facts of the form p : T, where p is a ground atom and Tis a priority constant. A Herbrand interpre­ tation I of E is a subset of the Her brand base of E, such that if p : T E I and A ~tl T then p : A E I. Furthermore, we require that if p : A E I and p : T E I then A R:t T.

Given two interpretations I and J, J !;JJ I (resp. J !;tJJ I) iff for every literal p: T E J, there exists a literal p : A E I such that T ~· A (resp. T ~tl .X). Note that J !;tJJ I is equivalent to saying that J ~ I. An interpretation I is minimal in a set of interpretations S iff ..., 3J E S : J C:JJ I and it is mazimal iff..., 3J E S: I C:JJ J.

A fact p(t) : Tis ·ati·fied in I (denoted I I=Ao p(t) : -r) ift' there is a fact p(t) : .\ E I such that T $Ao .\. A fact p(t): Tis ·trongly ·atufied in I (denoted I f=,., p(t): -r) ift' 3 p(t) : .\ E I such that T $eAo .\. Equivalently, I FtAo p(t) : Tift' p(t) : T E I.

A ground rule p : T {: q : 'Y is ·ati·fied in I ift' whenever I l=eAo q : -y, I I=Ao p : T. A nonground rule p : T {: q : 'Y is ·ati·fied in I ift' all its ground instances are satisfied in I. (A fact may be thought of as a rule whose empty body is strongly satisfied in all interpretations.)

A set of clauses P is ·ati·fied in I, if all its clauses are satisfied in I. A literal p : .\ is 1upported by P in I if .\ $eAo lub., ( { 'Y I p : 'Y {: q : 6 E P and I FtAo q : 6}). In words, p : .\ is supported by P in I if the combined conclusion derived from P on the basis of assuming facts in I strongly satisfies p : .\.

An interpretation I is a model of a set of clauses P ift' P is satisfied under I. A model I of P is 1upported if every literal p : T E I is supported by P in I.

2.4 Existence of Supported Models

In this section, we show that every inheritance specifica­ tion has supported models.

Lemma 1 Every inheritance ·pecification P con·iding only of fact· admit· a 1upported Herbrand model.

By dratifying P based on --<-ordering, a supported model can be constructed in a standard way, using tech­ niques similar to those described in [Apt et al, 1987].

Lemma 2 Every inheritance ·pecification P admit· a 1upported Herbrand model.

2.5 Unique :model se:mantics

In this section, we demonstrate that a unique supported model can be naturally associated with every inheritance specification.

Lemma 3 For an inheritance ·pecification, P, con·i·t­ ing of facti only, there ezi·tl a unique 1upported Her­ brand model of P.

Given an inheritance specification P, we define an op­ erator Tp that maps a Herbrand interpretation I into a Herbrand interpretation Tp(I) as follows.

Definition 2 Tp(I) is a !_;.,-minimal interpretation sat­ isfying the set of literals { p : T I p : T ·{: q : 'Y is a ground instance of a clause in P and I FtAo q : 'Y }.

Note that Tp is not monotonic with respect to c.,. For instance, let P consist of a single rule p: -1 {: q: +1 and consider a pair of interpretations I and J such that I = {p: -1,q: +2}andJ = {p: -2,q: -3}. (See Fig­ ure 1.) Clearly, I !.;Ao J. However, Tp (I) = {p : -1} and Tp(J) = 0. Fortunately, Tp has the following weaker property that saves the situation: if I CtAo J then Tp(I) !.;Ao Tp(J). -

Lemma 4 Tp {I) !;tAo I iff I i· a model of P, and Tp {I) = I iff I i· a 1upported model of P.

We show the existence and uniqueness of a supported model of an inheritance specification P in two steps.

Theore:m 1 Every inheritance ·pecification P admit. at mo1t one 1upported model. Equivalently, there ezi·u at mo·t one 1olution to the fizpoint equation Tp {I) = I.

The unique supported model for P, denoted Mp, can be described as lims-oo Tp(0). But this does not give us an efficient way of computing the fixpoint of Tp because the successive approximations change nonmonotonically. However, we can build Mp monotonically by an iterated fixpoint construction, similar to [Apt et al, 1987].

For convenience of exposition, and wlg., we assume that predicates appearing as facts and those that appear as heads of the rules are disjoint.

Inheritance Algorith:m

Let H be the set of ground atoms, A. be the set of atoms whose literals acquire meaning at the ith step of the iteration, and Ms be the set of literals at the ith step of the iteration representing the intermediate state in the computation of the supported model for P. Then

• Ao = 0.
• Mo is the !.;Ao-minimal interpretation satisfying all ground facts in P.
• .Ao+t = A. U {p I p is a --<-minimal ground atom in (H-At)}. (Recall: --< is the "depends on" relation defined in Section 2.1.)
• Mt+t is the !_;.,-minimal interpretation satisfying Mi U {p : T I p is a +minimal ground atom in (H -At), p: T {: q : 'Y is a ground instance of a clause in P and Ms !=tAo q : 'Y }.
• Mp = U,M,.

Theore:m 2 The ·et of literal· Mp computed by the al­ gorithm i· a 1upported model of P.

Note that absence of function symbols in our language makes our approach computationally viable.

From Theorem 1 and Theorem 2 it follows that

Theore:m 3 Every inheritance ·pecification P ha· a unique 1upported model Mp auociated with it.

3 Discussion

In this section, we illustrate our theory on a number of examples. In particular, we explain how this language can be used to specify inheritance networks. For def­ initeness let us pick the semi-lattice in Figure 1. The priority constants are numbers annotated with symbols +, -, or *. All the constants with the same sign are truth-equivalent w.r.t. :::::::t (i.e., -1 :::::::t -3, ·2 :::::::t ·5, etc.). Intuitively, constants +1, +2, ... denote the degree of confidence that a fact is tr~, while -1, -2, ... denote the degree of confidence in the falsehood of a fact. The constants d, ·2, ... represent the degree ofinconsist.ency in the evidences supporting facts. Also +w, -w, and *"' represent certain information about truth, falsity and inconsistency respectively.

Consider the <1-ordering depicted in Figure 1. The meaning resulting from such a choice resembles the meaning attributed to networks by the skeptical theory of [Horty et al., 1987]. Intuitively, p(a) : +n E Mp means that "a has property p", and p(a) : -mE Mp stands for "a has property -,p". In contrast, p(a) : ·l E Mp is interpreted as ambiguity about p(a).

To evaluate a ground atomic query p with respect to an inheritance specification P, determine the maximal support, -r, of a corresponding literal p: Tin Mp. Note that this is well- defined by the definition of an interpre­ tation.

Our inheritance networks are bipolar DAGs, that is, both positive and negative arcs are present. Our formal­ ism is powerful enough to specify inheritances of individ­ uals known to possess negated properties. Furthermore, we take the view of inheritance in which individuals are "moving upwards" similar to the one taken in [Horty et al., 1987] and [Krishnaprasad et al., 1988a]. The prop­ erties of an individual are obtained by forward chaining and there is ilo coupling among the inheritances of indi­ viduals belonging to the same class (unlike [Touretzky, 1987]).

Paraphrasing the famous Tweety example, we get the following rules.

• fly(z): +1 ~ bird(z) : +1.
• fly(z) : -2 ¢: penguin(z): +1.
• bird(z) : +w ~ penguin(z): +w.
• penguin(TWEETY): +w.

As we see, the relative magnitude of priority constants in the heads of the rules captures the intuition that the default conclusion obtained by applying the second rule takes precedence over the conclusion obtained by the first rule. Note that, as the name suggests, priority constants represent the relative strength of evidences. Thus, the absolute magnitude of priority constants has no special significance, and only the relative aspect counts. Also, the relative strength of evidence that enables the body has no bearing on the relative strength of evidence in the conclusion, in the case of default rules. This is because, we are modelling defeasible reasoning, where at each step, we hold on to the most plausible conclusion, and where bodies of difFerent rules are considered as inde­ pendent sources of support, whose relative strengths are determined by the priority constants in rule heads. Note that these aspects distinguish our formalization from probabilistic approaches to inheritance [Pearl, 1988].

The priority constants are not restricted to be nu­ merical values. One may in fact use constants repre­ senting the nodes of the network as priorities, with the information-ordering specified by the network topology. This is illustrated below by rewriting the first two de­ feasible rules of the Tweety example as follows, where ..l represents the least positive evidence.

• fly(z): +bird ~ bird(z): +..l.
• fly(z): -penguin ~ penguin(z): +..l.

The ordering <l is set-up in such a way that the evidence-content of penguin is stronger than that of bird, which can be inferred from the network, because there is a directed path from penguin to bird.

Our theory allows representation of both strict and defeasible links. To specify that some of the rules are exception-free, we may add rules of the form: p : -w ~ q : +w, p : +w ~ q : -w etc. These rules let guaranteed conclusions to propagate as such, which can be used to override contlicting default conclusions.

If the body of the rule is true by default, then the con­ clusion drawn from this rule must only have the status of a default conclusion. Priorities are used essentially only in arbitrating between contlicting conclusions; their ab­ solute values are insignificant. The exception-free rules let us propagate and derive new conclusions that are known to be true or false beyond doubt. This is illus­ trated by the dead bird example:

• dead(DODO) : +·trict.
• bird(DODO) : +.trict.
• fly(z): -·trict ~ dead(z) : +ltrict.
• fly(z): +default ~ bird(z): +·trict.

Even though there are contlicting conclusions about the flying ability of Dodo, the contlict can be resolved in favour of Dodo being unable to fly by virtue of being dead. This is because the latter conclusion is strict, as opposed to the default conclusion through bird.

To illustrate the treatment of ambiguity, we consider the Nixon diamond example.

• republican(NIXON): +w.
• quaker(NIXON): +w.
• pacifi·t(z): -1 ~ republican(z): +1.
• pacifi·t(z) : +1 ~ quaker(z) : +1.

The unique supported model associated with this speci­ fication contains pacifilt(N IXON) : .t, meaning that our knowledge about Nixon being a pacifist is inconsis­ tent.

Our formalization allows inheritances through paths containing negative arcs.

• Pro_American(GBR): +w:
• Pro_American(INDIA): +w.
• Pro..SO'Viet(CU BA): +w.
• Pro..SO'Viet(INDIA): +w.
• Vote(z): +1 ~ Pro_American(z): +w.
• Vote(z) : -1 ~ Pro..Soviet(z): +w.
• SuppdrLContra·..Rebeb(z): +1 ~ Vote(z): +1.
• Support..Sandini·ta·(z): +1 ~ Vote(z): -1.

One may interpret "+" as a "yes"-vote, "-" as a "no"- vote and "·" as an abstention. From the above specifica­ tion we conclude that GBR supports the Contra rebels, while Cuba supports the Sandinistas. We cannot offer any conclusions about India's intentions because it ab­ stains from voting.

There are advantages over the theory presented in [Horty et al., 1987] that accrue out of ordering evidences to resolve ambiguities that are not inherent to the prob­ lem. This is illustrated by the following example.

• toy(J AY): +w.
• bird(J AY): +w.
• fly(z): -2 ~ toy(z): +w.
• fly(z): +1 ~ bird(z): +w.

Even though the topology of this network resembles the one for Nixon diamond, we may resolve the ambigu­ ity in favour of toys being unable to tly, while [Horty et al., 1987] cannot differentiate between these two cases.

The notion of supportedness buys us certain advantages over [Ginsberg, 1986] as illustrated below.

• bird. (Fact)
• bird ::::} /lie·. (Defeasible rule)
• flie· --+ -,aero. (Strict rule)

According to [Ginsberg, 1986], this admits two C:1-minimal models, where the truth-lattice and information-lattice corresponding to these values is given in Figure 2. In one model /lie· is true by default and aero is false by default, while in the other /lie· is false, while aero is unknown.

Ginsberg notes that this does not allow one to con­ dude that the bird tlies by default, because such a con­ clusion is not true in all C:1-minimal models. He goes on to propose a criterion to prefer the first model over the second one by formalizing a notion of "strength of assumption" and discarding the second model by virtue of being based on "unreasonably" strong assumptions compared to the first one. We, on the other hand, do not run into such a problem. Indeed, in our formalism we would represent that problem as follows:

• bird: +w.
• /lie· : +1 ~ bird: +1.
• aero : -w ~ flie· : +w.
• aero: -1 ~ flie·: +1.

This admits a unique supported model containing fiie&: +1 and aero: -1. The interpretation corresponding to the second minimal model in the Ginsberg's approach is not supported because fiie·: -w (i.e., fiie· is false) does not have any justification.

One may try to translate inheritance networks into our logic to give them a formal semantics. The main problem here is the choice of priority constants based on the network topology. We will sketch such an approach below.

Define the evidence set corresponding to a network to be{+,-}x({..l,w} UN). Thefirstcomponentofan evidence represents its truth-content, while the second component captures the information-content . ..l repre­ sents minimum information, while w represents maxi­ mum information. The ordering of entities in N on the information scale is consistent with the -.(-ordering ofthe corresponding nodes in the network. That is, if p is a subclass of q (p ...( q), then +q <1 +P and -q <1 +p (similarly for -p).

We choose priority conltantl to represent finite subsets of the evidence set. Informally, a priority constant speci­ fies the set of evidences in support of an atom. The truth and the information-content of a priority constant, 11" 1 is determined solely by the <1-maximal elements of 1r. For instance, in the Tweety example, the priority constant corresponding to fiy(TWEETY} is {+bird, -penguin}, which is equivalent to {-penguin}. The lub1 of a set of priority constants is obtained by taking their union. For instance, in the Nixon diamond example, the lub1 of {-republican} and {+quaker} is { -republican,+quaker}. Because -republican and +quaker are incomparable on the information scale and they have contlicting truth values, the conclusion about Nixon's pacifism is incon­ sistent.

The translation of a positive arc from an individual node i to a property node p is: p( i) : { +w }; a negative arc is translated as: p( i) : { -w}. The translation of a positive arc from a property node p to a property node q is: p(z): {+q} ~ q(z): {+..l}; the translation ofa neg­ ative arc is: p(z): { -q} ~ q(z): {+..l}. The meaning assigned to an inheritance network corresponds to the unique supported model associated with its translation.

An advantage of our approach is that inheritance spec­ ifications can be designed in the same style as Prolog programs. This is because the meaning of a predicate depends only on the meanings assigned to the predicates in bodies of rules defining that predicate.

4 Conclusion

We have described a logical framework for a theory of inheritance obtained by a novel combination of con­ cepts from logic programming and multi-valued logics. A Horn-clause logic language is used to specify the net­ works. A model theory for the language is provided and a unique supported model is associated with each net­ work. We have also presented an algorithm to compute this model. Our theory resembles the skeptical theory of [Horty et al., 1987], but is more general. "Preferen­ tial" inheritance and inheritance through paths contain­ ing negative arcs can be expressed in our formalism. Our framework can also be extended to formalize credulous theories of inheritance.

Acknowledgements

We would like to thank David S. Warren for en­ lightening discussions on the subject of inheritance and the referees for their comments and suggested improve­ ments.