Structured Inheritance Networks and Natural Language Understanding

STRUCTURED INHERITANCE NETUORKS AND NATURAL LANGUAGE UNDERSTANDING

Henry H. Leitner* Center for Research in CoAputint Techtology Ai~en CoAputation Laboratory Harvard University CaAbridge, KA 02138

Hichael U. FreeMan Advanced DevelopMent Organization Federal and Special SysteAs Group Burroughs Corporation, P.O. Box 517 Paoli, PA 19301

One of the Aost salient difficulties facing the designer of a Natural Language Interface is the appropriate characterization of the seAantics and pragAatics of new doMains. Uhereas various syntactic parsers have been developed which are largely doMain-independent <at least in principle>, the possibility of accoAplishing soMething siAilar in the realM of seMantics and pragMatics has never been convincingly deAonstrated. Focusing on the various episteMological bases for associating attributes with entitits, we exaMint soMe of the rtquireAents that this suggtsts need be Met by a systeA which claiAs to provide a doMain-independent conceptual scheMa core, froM which doAain-specific extensions can be interactively elaborated. In addition to showing how our approach differs froA one which tries to arrive at canonical representations in terAs of invariant seAantic priAitives, we s~etch out ways in which it can be integrated into a general parsing ftechanisM.

o. IM!BQ~Y~!!QH

An ultiftate goal of researchers in natural language <NL) processing is to have a systeM that interacts appropriately with huMan users in their own natural language. However,

• it is unfeasible at present to construct a 9!D!tll systeA which can handle all NL inputs in every doMain and situational context.

Thus a revised goal ftight be a systeM that interacts intelligently with certain types of users in their own NL in Rit~i,Wl!r universes of discourse (e.g., PARRY, LUNAR, SOPHIE, PLANES, SAH, ··· >. However,

• users AIV find it difficult (if not iMpossible> to Ma~e theAselves understood in various instances;
• the effort involved in converting such systeAs to new doMain and context coverage is 'RDii~ltl~ll·

For these ~easons, a revised goal Aight be a systeA that can bt tasily extended or custoMized by users, at run tiAt Ce.g., LIFER or REL>. However,

• to be generally effective, this ftay deAand that a user be ftore linguistically and coftputationally sophisticated than can be reasonably expected.

;-rhis-w~rk-was-supporied in part by the RoMe Air DevelopMent · Center under contract F-30602-77-C-0197.

Thus a revised goal Might be a systeM that can be easily shifted to new doMains by its designers or ftaintainers <e.g., ROBOT>. However,

• the real expertise concerning a new doMain is generally not in the hands of the NLI C~L interface) designers or Maintainers.

Thus a revised goal Might be a systeA that can be conveniently shifted to new doAains by "knowledge base experts" who need not also be linguistic or coAputational specialists (e.g., KRL or KLONE>. However,

• there is generally the need to start over each tiAe froA scratch in order to avoid introducing inconsisttncies and incoMprthtnsible conceptualizations into the pre-existing knowledge network.

Thus a fifth goal revision is to have a systeM which can be easily adapted to new doAains by knowledge base experts who work within a conceptual franewor~ that builds upon a '2[! of very abstract concepts which can be further generalized or specialized to represent doMain-specific concepts, viewpoints, etc. This raises a nuAber of questions that we will address in the course of this paper:

• Is it possible to develop a "core" ~nowledge network <KNET> that can fulfill the function proposed for it above?
• Assu"ing that we can develop such a KNET, what additional proficiency would a doMain-expert or an interactive systeM need in order to expand it appropriately for a particular doMain or application?

• AssuRing that we can develop such a KNET, what additional proficiency would a do"ain-expert or an interactive systtR need in order to expand it appropriately for a particular doRain or application!
• Uhat type of general parsing "tchanisR would be needed for autoRatic adaptation to any newly expanded network! Specifically, how can standard syntactic analysis Rechanis"s be used to create conceptual ·Reaning· structures, rathtr than purtly forRal syntactic objects!
• Uhat would the role of the lexicon be in such a parter, and what torts of expertise would be nttdtd for creating, expanding, or "odifying any particular instance of such a lexicon!
• AssuRing that we havt this NL parser which "aps English (for exaRple) into conceptual rtP.restntations of the user's intent, what relation do tuch rtprtttntations bear to forRal querits that would actually realize this intent?

BrachRan developed a knowledge representation notation <SI-Nttsl which has a very clear and explicit epistt"olosy. According to Brach"an, ·structured conceptual objects are organized in lattice-like networks, with inheritance between descriptions carried by structured 'cables'."* An exaRple conceptual structure is illustrated in Figure 1:

The oval shapes denote conceptual entities, while the ~Rl! D9~11 <squares> are intended to reprtsent the in!tDii9Dil description of potential role fillers in ~gn~t~!· The third coftponent part of the forRalisft is the ~tructural ~escription

<diaRond shape> which expresses interrelationships betwten tht conceptual subparts. As described by BrachRan, "these relationships [i.e., the role descriptions plus structural descriptions) give tht Concept its 'gestalt'."

~htnever two concepts are in a generalization/specialization relationship to one another, the features they have in coR"on can bt factored out in such a way that only the differences need be represented. This is illustrated in Figure 2, where the AKO <e-~ind-gfl link reprtstnts a channel along which co""on properties can bt inherittd tither intact, rtstricted or differentiated froR a ftore general to a Rore specialized conctpt. Uhenever a concept is specialized to tht extent that ill of its role-description nodts have values associated with theA, it takes on a special status as an iD~iXi~Yil!~ concept. This is denoted by a shaded oval (cf. "HARVARD" in Figure 2>, and is conntcted to its parent concept via an INSTS link.

It should be stressed that Brach"an's priftary goal was to Rake explicit the stftantics of a representation systeft, thereby overco"ing the expressivt inadequacies of tht ftany "seftantic nttwork" node-arc schtftts in recent years. He ftakes no claiRs whatsoever about the se"antics of ~bll il ~tins rtRrt,!D~I~ -- any concept can be rtprestnted in the SI-Ntt forftalis" any way the user chooses. Thus a particular concept ftight be defined in tYD,!iODil ter"s or in terfts of its ftajor parts and subparts, etc. The seftantics of the world one thinks tslhe is ftodelling art DQ! iftplicitly eftbedded in Brach"an's syste" -- but the seftantics of the representation syste" itself !~! clear and precise.

* Brachftan, Ron: "Theoretical Studies in Language Understanding." BBN Report Caftbridge, Hass., Septe~ber, 1978, p. 25. Natural 113888,

The preceding reftarks raise softe rather basic issues, such as: what does it ftean for a concept to have an !ttri~Y~I or to have a role; how do the latter becofte associated with concepts originally, etc. One reason we need to concern ourselves with such issues is that if a taxono"y of the ways in which different types of attributes can be associated with concepts is developed, then there is hope -- at least in this area -- of being able to give a ~nowledge ~ase !d"inistrator <KBA> auto"ated assistance in creating or extending a core seRantic network. This ftatter is discussed further in Section 4.

Our point of departure here is the observation that the initial association of attributes with entities results fro" the 'tiJ~iRD of so"ething which did not exist 11 IU'b before. This does not necessarily entail the crtation of a new ~h~!!,!l object. In the context of hu"an society, for instance, one is usually concerned with the creation of new social, political or legal entities. Thus, being ~RrD into 1 particular society transforfts a Rere <huRan> being into a societal entity having attributes such as MAKE, RESIDENCE, NARITAL-STATUS, and so on. Note that we are not speaking of the association of a particular value with an attribute, but rather of the !'tri~Y~I i!ttl! with a new entity, within the fraRework of a highly developed social or legal order.

In this fraftework, the relationship of !~~~ll resulting fro" specific t~IDtl takes on fundaRental proRinence. For exaftple, as the result of an instance of the ·HIRE" event concept represented in Figure 1, a state of "EHPLOYNENT" coRes into being. The seftantics of the DATTR/RESULT arrow in Figure 3 is fttant to capture this relationship.

In turn, this allows us to conceptualize an ENPLOYEE as a societal person put into a statr of eRployRent as a result of playing the rQll of the "second party· <or q-agent> in a particular type of contractual event, naftely that represented by the "HIRE· concept in Figurt 1~· The QUA link in Figure 4 is thr fteans by which we rrprrsent this interdrpendencr of relationships.

Thr QUA link is the priftary channrl over which new att~ibutts coRe to be attached to already existing ent1ty concrpts. Note that this is not siRply a Ratter of ~il~iD9 a given entity froft tofte particular perspective, although it does give rise to such possibilities, as illustrated by the VIZ links in Figure 4. In this latter case, however, ~he .perspective is taken as already having been 1ntr1nsically established, whereas in the forfter cast what is being represented is how such perspectives are actually to be defined. This distinction between VIZ and QUA links becoftes quitr clear vhrn one addresses the probleft of Raking explicit the seRantics of inheritance associated with tach of the two link types.

The VIZ link hat precisely the safte inheritance properties as the AKO link. The only difference is . that it serves to ~!r!!~iRD the ftultl-diRensional attribute space of a given entity type into proper subsets. This allows one to distinguish higher level entity concepts in the ·gestalt· of a lover level entity concept having Rultiple inheritance paths. The reason for doing so, however, is contained within the seftantics of the QUA link.

Since QUA links can derive froft role description nodes within verbal concepts, the relationships between the parent role node and other role nodes within the verbal concept open up new paths for attributive inheritance that are not present in just the AKO (or VIZ> links. In the case of ENPLOYEE, for exaftple, as illustrated in Figure 4 attributes such as EMPLOYER, DATE/PLACE-OF-HIRE: etc., result not froft its AKO relationship to

* The iftportance of ftodelling ROLE-ENTITY associations has also been stressed by Bachftan and Dayar ·rhe Role Concept in Data Models." YLDI-~ Tokyo, Japan, October 6-B, 1977. - - '

SOCIETAL-PERSON, but rather to tht other role dtscription nodes in tht TO/BE/EHPLDYED conctpt, which theftselves derive foR the TO/HIRE concept via the DATTR/RESULT link illustrated in Figure 3. Now, by dtsctnding into the ttructural-~escription <SID> nodts of these verbal conctpts, ont arrives at conceptual rtpresentations of how tht various roles subsuRed under the verbal concept are theAselves related to one another. Yherever an S/D coRponent co-references the <q-agent> node in TO/HIRE to which the EHPLDYEE concept is ultiRately rooted, one has a potential source for generating a VIZ link. If one regards a TO/HIRE event, for tXIRple, as consisting of a job-offer and a job-acceptance, in which the applicant <q-aqent> coAAits hifttelf or herself to perfor" certain services in return tor certain recoApenses over softe sort of tiRe-span, then for each service to be perforAtd, the tRploytt can bt viewed as its agent (t.g., YORKER>, and for tach rtcoftpense to bt receivtd, tht eRployee can be vitwed as its benefactive (e.g., PAYEE, GROUP-INSUREE, etc.>. These are precisely the perspectives that we have represented via the VIZ links in Figure 4. In this way, an attribute such as SALARY coAts down the VIZ link froR PAYEE to EHPLOYEE, just IS JOB-SITE dots froR YORKER, whereas RESIDENCE coRes down the AKO link troR SOCIETAL-PERSON, and ENPLOYER over the QUA link froft TO/BE/EHPLOYED via the DATTR/RESULT link froft TO/HIRE.

The discussion up to this point has focused on how attributes coAt to be associated with entities through perforAance evtnts which result in certain socially or letally recotnized states. Ue have said relatively little about the specification of doRains froA which these attributes can take on Rtaningful values. Ye have siAply placed a ~alue/restriction <VIR> liak on role-description nodes (pointint to such concepts as SOCIETAL/PERSON, L£8AL/£NTITY, PERFORMANCE>, and have relied on the indulttnce of our audience to accept this 11 obvious. This has led us to gloss over the deterAinatioa of the AKO-link between 1 QUA-derived concept and the Y/R concept associated with the role-dtscriptioa node to which the QUA points. Yet it 11 not atcessarily obvious in what sense an essentially functionally specified entity can be retarded as ·a-kind-ofM object pure and siAple. Put another way, we neld to look "ore closely at the inplications of saying that the event of castint an entity into a particular role results in the ·creation· of 1 new entity through its association with attributes <ng~ just attribute-values) which it did not previously possess. In what follows, we will briefly consider how this approach leads one to view the doAain specification <VIR> of attributes of this type as an event-driven state-transition network, troft which secondary attributes can be derived, as dictated by whatever the prag"atic needs of a given user coftftunity Right be. This also provides an extreftely straightforward fteans for specifying certain types of data base integrity constraints, update histories, identity conditions on transforftable objects, etc.

In Figure 3 we represented the · concept TO/BE/ENPLOYED as connected to the event concept TO/HIRE via a DATTR/RESULT link. Ue're all aware , however, that one reRains e"ployed by a particular legal entity only so long as certain other events do not occur, e.g., being fired, laid off, released, retired or dying. Uhenever any of these other events occurs, one enters a corresponding new state. In tact, the history of this progression froA one state to another via events of the types just Aentioned can itself be viewed as the value of tone higher level attribute, say, ENPLOYNENT/STATUS. Just as a SOCIETAL/PERSON acquirts an ENPLOYER attribute throu9h beco"ing an ENPLOYEE (cf. Figure 4), so a new-born hu"an acquires an ENPLOYNENT/STATUS through beco"ing a SOCIETAL/PERSON 11 1 result of being born into a particular typt of society. Part of the "definition· of such 1 society is precisely the types of attributes that are associated with individuals upon their birth into it. And the do"ain-specifications of ftost of these attributes are nost naturally represented as constellations of event-Atdiated state-transition networks, such as that illustrated in Figure ~ for ENPLOYNENT-STATUS.

For any instance of a SOCIETAL/PERSON, the actual value of its ENPLOYNENT/STATUS is the current state it happens to be in. Since the latter results froft a specific event-instance, one could just as well rtgard the tvent itself as the prinary value, froR which a current state value can alNays be coAputed on deRand. The converse, of course, does not hold, thus underscoring the derived or secondary nature of state attributes such as ENPLOYNENT-STATUS. Let us therefore restrict our attention si"ply to an E"PLOY"ENT/DETERNINING/EYENT/HISTORY. In ordtr to capture the safte sort of knowledge as that represented in the stale-transition network of Figure S, we can conceive of the attribute itself as an active object, ftuch along the lines of an abstract data type. In addition to recording a series of events of certain types <constituting thr "history" of the participatlng object in this respect), such an abstract attribute would also behave as a ~2D&~gr for events yet to occur. Since the set of possible events at any given ftOftent is constrained by the previous event-history of the object, the analog of the state-transition network in Figure S would be an event-ftonitoring transition network. Froft this one can not only derive values for the secondary state-attributes of Figure S, but one can also set triggers for autoftatic updates to preserve data base integrity in a natural way.

Consider, for instance, the case of two eftployees of a coftpany who art ftarried to one another. Since the SPOUSE/DETERKINING/EVENT attribute of each would be ftonitoring, aftong other things, for the death of the other spouse, the value for the derived KARITAL/STATUS attribute would be subject to autoftatic update for ~g~b tftployees. This could autoftatically propagate updates in tax-status, group-insurance status, etc.

The usefulness of the KNET distinctions we have ftade so far becofte apparent in discussing how a conventional syntactic analyzer could guide a direct ftapping froft NL input into a corresponding conceptual representation, as well as for interactive construction of doftain-sptcialized KNETs. Ue will consider the interpretation of the ·noun phrase, "NY eftployee~. Our NL parser's lexicon, in addition to providing the syntactic processor with various graftftatical/syntactic inforftation, also contains the possible conceptual basts for the concepts (denoted by lexicon entries) which ftay already be present in the KNET. The lexical ite" NY, for instance, ftay be regarded as a city/state ENTITY, as a LOCATION/SITE, or as an ACTION/SITE.* The linkage between lexicon entries and the actual KNET is illustrated below for NY and EKPLOYEE:

* Note the different senses of NY in: "NY is located on the East coast," "He is a NY eftployee," and "No NY shipftents were sent out."

In processing an input containing the noun phrase "NY eftployee·, the syntactic analysis routine first identifies 1~12~11 as head noun and NY as potential ftodifier; the conceptual processor is sent this inforftation in the forft of a teftplatt which "says· that we have identified the potential conctpt NY/EKPLOYEE -- for which a representation dots not yet exist. But certain facts Jr! known. The syntactic analyzer will ask the conctptual unit to try and link the NY and EKPLOYEE concepts in such a way that NY can be considered an ATTR/VALUE/REFERENCE of EMPLOYEE via the scheftatic teftplate illustrated in Figure 7:

In exaftining the possible ways in which a path betwttn NY and EKPLOYEE can be established to fit the teftplatt, we find that NY could bt viewtd as a LOCATION/SITE. Ue thtrefort try the interpretation of NY as ftOdifying a LOCATION/SITE. Procedurally we will have to build specializations of the TO/BE/LOCATED/AT/SITE concept, as well as additional specializations of other concepts in order to create the proper connections. The pattern we are trying to instantiate is one in which the doftain-object <VQIJ> has EMPLOYEE as its value/restriction. However, at the start of our ftatching we discover that the TO/LOCATE/AT/SITE concept has a V/R of PHYSICAL/OBJECT. The strategy at this point is to see if there is an AKO path between EHPLOYEE and PHYSICAL/OBJECT. Note the ftUltiplt ~!~~~~ we have fro" EMPLOYEE to PHYSICAL/OBJECT <e.g., eftployee as a

"site/qualified" Vit!lt or ttli~ID~:~ttl29>· For each possible path the parser fills in the appropriate structure, so we actually produce ~~g interprttations of NY tftployeea (a) an eRployee who li~!! in NY; and <b> an eftployee who ~Vr~l in NY. (Vt could evtn produce a third interpretation! a person who is born in MY -- if the KMET contained that view>.

Ont should note that in the structural ~escription part of concepts, thtr; exists not only infornation about how the various roles are rtlattd to one another, but also iDRli~ID~I~ii!:IRI,i!i' inforftation on how to actually go about retrieving inforftation froft a data bast in 1 given conputer environRent. The sane sort of building operations which generate the conctpt nodes leading to the representation of MY/E"PLOYEE will tailor the inforRation rttrieval routints in the SD's -- so that for each conctptual rtprestntation of NY/E"PLDYEE wt also have an inpleRentation-bound procedure. The inplentntation-bound procedure is MOT the "Rtaning· of NY t~tployee -- 11 "procedurali sts" often setn to claiR. Our approach nakts it clear that two very differtnt things really occura One is the conctptual representation building process, and the other is the process which constructs an inpltnentation-deptndent representation which can be executed to check whether any MY eRployee exists, who they are, how ftany there are, etc., depending upon the intent of the original input. The latter representation, however, really is irrtltvant so far as building conceptual representations are concerned. Btlow is illusrated the KNET after the virtual nodes have been constructed for the parsing of MY/EMPLOYEE. ,..,,_'

Modularity has been achieved in the separation of donain independent froft dtpendent knowltdgt, and tht ttparation of syntactic, senantic <and pragRatic> exptrtise. Mo longer it the lexicon a ·wastebasktt· for idiosyncratic infornation which can't bt factortd out and forRalized. Secondly, we have a perspicuous, toftprehensible and conftunicable fornalisn which lends itself readily to conctptual/linguistic extension by a KBA who builds upon a 'IIU. SI-Net for a given univtrtt of discourst. Mott that ke ~ve D2~ gone the route of Schank and his co-workers -- who argue in favor of "senantic priRitivesN and the belief that all conctpts can bt algorithftically deCOftPOitd into their prinitives (via the encoding of teRantic dtfinitions of words in ter~s of a tftall set of ACTs> for all Hls. Schank's assuftPtions run counter to 1 fairly old and wtll established philosophical tradition that warns against trying to arrivt at a canonical decoftposition of NL utterancts in terftS of stftantic prinitivts. "ore seriously, Voods and others have pointed out that such <CD) dtconposition is often undesirablt (if it Hltt possible>, si1ce necessary inforRation which is prtstnt in the original surfac· encoding of the ntssatt usually gtts lost. To ftake ftatters worst, tht ltxicons of Schank's iftpleRtnttd systtfts art enornously conplex, and havt never been for~ally characterized. The hope, thtn, of adapting a lexicon fron one application to another seefts fraught with difficultits.

A third iftportant contribution is the delegation of syntax to what appears to be its iRRt2Rtit11 tQlf· Just as hunan parsers apparently do not build, naintain and nanipulate syntactic structures as fl!tDil i~JI,~Ir so too do we believe that our parsing techniqut need not construct intricate, inttrntdiatt syntactic structures. Instead, we btlitvt that tht ·appropriate rolt" of syntax dwtlls nort within such areas as& idtntifying the boundarits of phrasal constituents and tstablishing various ·cue· rthUoMhips aftOnt thtlt; focusing in on Uitr's lnttnt Ci.t., helping to rtsolve certain forRs of tlliptit and anaphora>; and handling o\htr discourse-sensitivt ftatures such as negation-quantification inttraction and scoping.

Finally, we belitve that the only hope for realizing truly flexiblt NLI's lits in the elaboration of an tpistenological fraftlwork fir~ly grounded in the social/contractual aspects of huRan interaction. It should then bt possible to shift to new doftain applications sinply through the inttractivt sptcialization of a core KNET created within this franework. Ve hertby dedicate all such systens to Jean Jacques ROUSSEAU.