On Inheritance in Knowledge Representation

1. Specifyln1 Idiosyncratic Inheritance

1 Experience with representing tlarge( 1 vJtrieties of knowlecrge show that a small trlc ton < Ol) escape standard representation schemes, requirin& specialized "fixes" (F ahlman, 1979). The idiosyncratic nature of language and knowledge precludes its complete structuring using a small set of classes and associated processes. We conjecture that a small set of inheritance types will not suffice. In a some cases the inheritance relation will have to be specialized to the particular concepts they relate. Hence, the inheritance link is context sensitive. Tailoring Inheritance tQ. Its context (~quires ~ explication of ~ what i! to !2J2_ ansferred, excluded, added, and/or modified.

Current approaches to handling idiosyncratic inheritance rely on property classification to distinguish between properties to be inherited and those not to be Inherited (e.g., structure vs assertion properties, set vs type properties). For example, a structural property is inherited ~among 1;lasses while assertions are not. But anomalous sub-classes may occur which do not Inherit all inheritable attribuies (classification is fuzzy at best). To handle anomalous sub-classes, arti.fr.ci4l 1ub-cla11e1 are inserted between the original super-class and sub-classes. Appropriate attributes are moved from the super-class to the artificial classes. This phenomenon Is called anomal)' i.nduced clall-lpli.ttinfl. Typically, class-splitting Is a bifurcation where one branch is a sinaleton

set ~ontalnlns the anomaly. Class-splitting Increases the size and complexity of the representation thus Increasing search time, obfuscating possible relationships amon& concepts, and negating the stora&e and description benefits of Identifying concepts with class descriptions. It seems that knowledge classification Is an art which tries to reduce anomaly induced class-splitting. - Secondly, a knowledge representation must represent arbitrary mappings between concepts. For example a man Is like a pig If you map nose onto snout and home onto sty.

1Thle ·····rch w .. ·ponoored by the O.fenM Adv·nced R .... rch Project· Aaency (000), Ar~ Order No. 3597, Monitored by the Air force Avioniu Lebor~tory Contr·ct !533815-78-C-1551. In .dditlon, the author 11 ·upported In ~rt by · N.tioMI RtM·rch CouncM of C.Ndl Poetarllduete Scholer·hip.

2wor·t ceM I· 2N cle·n· for N ·llribute~o le, · dlecrilllin.tio11 n.t.

To reduce the complexity of representing Idiosyncratic concepts · and their inheritance relations and to allow more expressive power in describing the similarity relationships between concepts, declarative, Idiosyncratic Inheritance relations are introduced. Current approaches to specifyng Inheritance is Implicit In the representation and explicit In the procedures that manipulate the representatio!"'. Our goal is to move the explication of Inheritance from the procedure to an inheritance relation. This enables the context-sensitive specification of inheritance modification. Thus removing the need for class-splitting and any other complexity Increasing methods. Secondly, the concept of inheritance is expanded to encompass similarity mappings between concepts (e.s., analogical relations). In the following, we focus not on one particular representation but attempt to describe the mechanism In a representation independent fashion.

We propose a single unidirectional INHERITANCE (INH) relation between two concepts (A -- INH --> B) with an attached INHERITANCE CONCEPT (C). The inheritance concept C explicitly states what set of information is Inherited, what Is excluded, what Is created, and what is modified. The inheritance concept can be viewed as a label on the Inheritance link specifying a set of transformations. To allow specifications of this type, a language for manipulating representations must be created. While trying not to be pinned down to a single representation, we propose the followln& primitives:

1. ~: Information passed from A to B.
2. !QQ: New Information added to B.
3. EXCLUDE: Information In A not passed to B.
4. SUBSTITUTE: Information in A replaced by new Information In B.3
5. -RESTRICT: Substitution results in a restriction of possible values.
6. -CONTRADICT: Substitution results in a contradiction in semantics.
7. -GENERALIZE: Substitution results in an expansion of possible values.
8. -~: Substitution results in an analogical replacement of information.
9. -Rll!Nt: Replace with more detailed description.

These primitives are applied to any slot, description, link node, and other structured primitives of a representation: They specify modifications of the physical structure of a concept to create a new concept. These primitives admit the description of arbitrary transformations among concepts. They are additions to existing representations an~ are to ~e . i.nterpreted as specifying modifications ustng the prtmtttves of the particular representation language.

For example, role restriction would have an INHERITANCE link sp~c.ifylng all of the str~cture Inherited using the PASS prtmtttve, and the node betng restricted by using the RESTRICT pr imi tive. Differentiation, that is, the addition of SLOTS would use the ADO primitive. Analogical inheritance would require the PASSing of some information, EXCLUSION of other information, ADDition of new information, and the SUBSTITUTION of Information via a MAP (as found in ,.1- structures (Moore & Newell, 1972)). Just what is the semantics of the information PASSED, ADDED, MAPPED, etc. depends on the underlying representation.

It is obvious from the current specification of the Inheritance concept that a great deal of information would have to be specified by the PASS primitive. In al~o~t all cases the PASS p~imitive will be the primary prtmttive used. The more tnformation to PASS, i.e., the more complex the concept, the more cumbersome it is to write the inheritance concept. To alleviate this problem we re - introduce the notion of information classes which is the basis of current representations. The inh~ritance pr imitives would then specify that a class of representation structures, e.g., assertions, structures, etc., is to be PAS':ED, EXCLUDED, etc. But the inheritance concept can still refer to particular structures (node or link). Extending the classification concept to its logical conclusion, we can associate a type with the inheritance concept. For example, IS-A, OSUPERC, INSTANCE/OF, etc. can all be inheritance concept types whose inheritance definition correspond to their interpretation in other representa~ions. But the typed inheritance concept may also spectfy exceptions to the type's inheritance def init ion. That Is, an Inheritance relation could have an inheritance concept of type "is-a" (which has a standard definition composed of inheritance primitives) but is modified in the particular context by additional Inheritance primitives. Since inheritance t,pe, are defined using Inheritance primitives, new types can be defined for commonly occuring relat ions.

3 11 thould b. noted the! eub11itute 11 the combl111tion of ··elude end Mid. We Include it 11 · primitive becau·· ··perelint it into ··elude end Mid would lo11 the Information the! there II · contlnaency, the! one etructure replec11 enother.

To illustrate these ideas an example is taken from zoology. Example 1 depicts a simplified representation language. A concept is divided into three parts: 1) the VIEW which specifies what the concept is related to. Each slot in the VIEW is a different inheritance concept, 2) the META-CORPUS which specifies whoiistic (set, type) information, and 3) the CORPUS which specifies structure information. Example 2 represents a partial description of a ·mammal <· denotes a concept). To add ·platypus to the set of ·mammals requires concept-splitting (the platypus is an exception to the mammal specification, it lays e~gs): create ·monotreme with ·egg-laying value for ·btrth-process (ex. 4), and another concept with ·live-birth value for ·birth-process. The alternative approach taken in this paper results In ex. 5. The ·platypus has an inheritance concept of type ·IS-A, but the definition of ·IS-A Is overidden by the CONTRADICT primitive specifying that the ·platypus lays eggs instead of live birth. The REFINE primitive is used to replace the ·head slot with a ·bill and ·skull slot.

2. Specifylnt Derivative Relations

A second motivation for describing the relationship between two concepts explicitly is to allow learning and discovery systems to analyse how concepts are ~ from other concepts.

The goal of learning and discovery systems is to generate new concepts via specialization, generalization , or analogy. In particular, these systems seo.rch for derivations that are "interesting", where interesting is defined by some heuristic metric. To properly focus search, the method for deriving one concept from another must be recorded. This information is used to analyse how a concept was derived and what should be done to derive a different but related concept. In Lenat's AM system (1976), a set of heuristics were used to decide how to alter (extend) existing concepts to derive new and Interesting concepts. A similar approach is used by Fox ( 1978) to decide how to specialize concepts to create new and interesting concept hierarchies. In Winston's system (1978), transfer frames are hypotheses for what slots to transfer between concepts; heuristics are used for deciding candidate slots. In each system, there exists a set of actions whose application defines a space of new concepts. The action(s) chosen and reason(s) for the choice(s) are important pieces of information used by these systems in decidin~ how to extend concepts. The INHERITANCE r.oncept shollld store it.

We further define each of the INHERITANCE primitives as having the following three attibutes: 1) SET 2) VALUE 3) REASONS. The SET attribute specifies the information the pr imitive could act on. That is PASS, ADO, EXCLUDE, MAP, RESTRICT, GENERALIZE, or REFINE. The VALUE specifies the actual information chosen from the SET. REASONS specify what decisions led to the choice. Of the three attributes, REASONS is the least defined as It is dependent on both representation and inference mechanisms. If a PASS was to be specified, then the SET attribute of the PASS would list all the structures, e.g., DATTRS the PASS could be applied to. The VALUE attribute would denote the actual structure chosen, the REASON attribute would "explain" why the value was chosen from the SET.

As pointed out earlier, the SUBSTITUTE primitive Is equivalent to an E)(CLUDE and ADD. Hence, it has two sets of attributes. (SETe, VALUEe, REASONe) describe the Information to be replaced, and (SET 8 , VALUE 8 , REASON a) describes the Information actually substituted.

By specifying each of those attributes for each of the inheritance primitives, it is hoped that more information will be made available for learning and discovery systems to make decisions intelligently. By no means are these attributes complete. Their purpose is to focus attention on the types of information needed in inheritance specifications.

Example 6 Illustrates how the SET, VALUE and REASON primitives are specified in ADD. In this example, a ·platypus Is specialized as a apurple-platypus by choosing a color out of the set of possible colors.

3. Conclusion

Inheritance Is the primary, most powerful representation primitive available in knowledge representations. The explication of representation semantics has led to the creation of many types of inheritance links. The semantics of these inheritance types are defined by the procedures that manipulate the representation. Two problems arise in classifying inheritance relations. First, some inheritance relations are idiosyncratic and do not conform to popular classifications. Second, learning and discovery systems require an explication of how concepts are related, In particular what Information is inherited, modified, added and/or excluded, and upon what information were these changes based. To adequately deal with these problems, the semantics of inheritance must be moved from the procedures to the representation. This view led to the creation of a general inheritance relation with an associated Inheritance concept. The inheritance concept explicitly defines what information is inherited by concept, and what additions, deletions and substitutions are made. It also describes the set of choices available in making the alterations and why a particular alteration was chosen.

4. References

1. Brachman R.J., (1977), "A Structural Paradigm for Representing Knowledge," (Ph.D. Thesis), Harvard University, May 1977.
2. Fehlman S.E., (1977), "A System for Representing and Using Real-World Knowledge," (Ph.D. Thesis), Artificial Intelligence Laboratory, MIT, AI-TR-450.
3. Fehlman S.E., (1979), Private Communication.
4. Fox M.S., (1978), "Knowledge Structuring: An Overview," Proceedings of the Second Conference of the Canadian STciett_ for Computational Studies of Intelligence. or onto Ont ., July 1978.
5. Hayes P.J., ( 1977), "On Semantic Nets, Frames and Associations," Proceedings of the Fifth lnternatonal ~ Conference Q!l Artificial Intelligence. Cambridge MA, Aug. 1977.
6. Lena! D.B., (1976), "AM: An Artificial Intelligence Approach to Discovery in Mathematics as Heuristic Search,", (Ph.D. Thesis), Computer Science Dept. Stanford U., AIM-286.
7. Levesque H., and J. Mylopoulos (1978), "A Procedural Semantics for Semantic Networks," AI MEMO 78-1, Dept. of Computer Science, University of Toronto.
8. Moore J., and A. Newell, ( 1973), "How can Merlin Understand," In L. Gregg (ed.), Knowledge and Cognition, Potomac MD.: Lawrence Erlbaum Associates.
9. Winston P.H. ( 1978), "Learning by Creatifying Transfer Frames," Artificial Intelligence, Vol. 10, pp. 147-172.

Examples

1. { ·Concept View: <view-slots> M;t;-corpus: <meta-corpus-slots> Corpus: <corpus-slots>}
2. {·Mammal

Corpus:

·Nursing-Method: aBreast

·Birth-Process: alive

acolor:

·Head:}

1. (·Mammal Corpus: ·Nursing-Method: aBreast}
2. {·Monotreme

View:

·Is-a: aMammal

Corpus:

·Birth-Process: aEgg-laylng}

1. { ·Platypus
2. ~:

als-A: aMammal

(Corpus:

(CONTRADICT DESCRIPTION OF ·Birth-Process SLOT WITH ·Egg-laying)

(REFINE SLOT aHead TO SLOT aBill AND SLOT ·Skull))}

1. {·Purple-Platypus

VIew:

·Is-a: ·Platypus

(Corpus: (ADD VALUE aPurple TO DESCRIPTION OF SLOT aColor FROM SET {ared, ayellow, apurple}

FOR REASON "environment Is purple"))}