MARGIE: Memory Analysis Response Generation, and Inference on English

1. Introduction

A program is no~ running at the Stanford Artificial Intel I igence Project that analyzes natural language sentences into an underlying language-free conceptual representation; stores this representation in memory , establ ishes references and makes inferences; encodes the concept~al representation into an Eng I ish syntactic representat ion ; and then encodes the syntactic representation into an English string. The program has t~o modes: PARAPHRASE and INFERENCE. In PARAPHRASE mode up to 158 semant ic paraphrases can be generated from an input sentence by read ing the conceptual representation underly ing that sentence using di fferent ~ords and concept comb inations·. In INFERENCE mode, most of the possible inferences that can be made from an input sentence are produced as output.

2. Examples

INPUT: Reading the book reminded Rita to loan the book to B iII.

OUTPUT: Rita remembered to give the book to Bi I I and ehe expects him to return it to her because someone read the book.

INPUT: John prevented Bi I I from giving a banana to Mary by sel I ing a banana to Rita. OUTPUll: Bi I I ~as unable to give a banana to Mary because Rita traded John some money for a banana. OUTPUT2: Rita bought a banana from John caused Mary not could get a banana from Bi I I.

3. Organization

The theoretical basis for this system is Conceptual Dependency as expounded by the authors [6], [7], and [9]. The natural language analyzer ~as ~ritten by Chris Riesbeck and is described in [5]. It is a different program than ~e have used before.~ith an emphasis on analyzing meaning before cons ider ing syntax. The conceptual memory is the ~ark of Chuck Rieger [4]. Nei I Goldman [2] ~rote the program that encodes conceptual representations into Eng I ish syntactic ones. We have devoted almost no effort to~ards encoding our syntact ic representations into ~elI constructed Eng I ish strings. Instead ~e have modified Simmons' [18], [11] program to accomplish this task.

4. Theoretical Approach

It is really not possible to adequately judge a system on the basis of a smal I sample of its output. Ad hoc procedures could be ~ritten that would perform ~elI on smal I data bases. It has been our intent here to have this system reflect our thinking along theoretical I ines as ~el 1 as possible : We have, on occas ion sacrificed efficiency for theory. The conceptual representations used are intended to account for the concepts that are remembered ~hen a human hears a sentence. Like~ise, the processes used in our programs are intended to mimic human processing

insofar as that can be determined.

The .core of the system is Conceptual Dependency theory. Thts theory postulates that there are six basic concept types: things,actions, attributes of thing.s, attributes of actions, times and locat ions. These concept types are connected in only sixteen possible ~ays. The pr inciple ones are: Thing <·> Action,which signifies an actor acting; Action .a-Thing ~hich signifies the object of

Thing

Thing

an Action; Action ~

which signifies the

[Location

[

recipient and the donor of an Action; Action ..0

~hich signifies the direction of an Action; Action~

sign i fies the mental object of an action;Thing<·

Attribute signifies that a Thing has and, Thing~ Action 111( Attribute changed Attributes on some scale signif ies that an action has

[

caused a state change.

Attribute Whenever a t~o-headed arro~ is present a conceptualization is said to exist .

Location

Attribute Conceptual Dependency uses only fourteen possible Actions. These Actions are primitive building blocks from which verbs describing conip I e>< chains of these Actions can be built. These Actions are:

PROPEL

GRASP

MOVE

INGEST

EXPEL

SMELL

SPEAK

LISTEN-TO

LOOK-AT

MTRANS

ATRANS

PTRANS

CONC

MBUILO

These Actions are described in detai I else~here [7]. The most important are MTRANS (transfer of mental information!; PTRANS (change of location!: and ATRANS (transfer of possession!.

What is important about the ~ystem described here is that for the e><amples it does, it functions the ~ay ~e would claim an ideal language understanding system must. Namely, the analysis of the input is done to a deep conceptua I I eve I using conceptua I information rather then by doing a syntactic analysis first. T~en it is operated upon using the language-frAe nature of th1s depth, and then repacked into Eng I ish.

5. The Analuzer

The natural language analyzer attempts to e><tract the conceptual dependency representation underlying a sentence. There are several things that distinguish the approach to parsing described here from others. The first matter is the use of a predetermined representation of the meaning of sentences, i.e. conceptual dependency. The determinati~n of t~e syntactic structure of a sentence is an Instrument 1n the primary task of figuring out ~hat that sentence means. In fact synta>< has been denigrated to the status of something to use ~hen alI else fai Is.

Our analyzer also differs from traditional parsers in having been ~ritten ~ith an emphasis on ~hat individual words can and do communicate, not on ~hat possible syntactic structures there are and ~hat they mean. Thus the ana I yzer does not I ook for the presence or absence of a particular structure by template matching nor by feature recognition. Rather those ~ords that might appear as features for the structure have attached to them programs that perform the task ~hich ~ould be considered as the meaning of the structure. For e><ample, the analyzer does not look for an active or a passive construction. Attached to the various forms of the verb "be" is an instruction that says that the following words wi I I be tel ling some fact about the subject and further if the verb form . fol ~~~i~g ~sa past participle (i.e. a verb form ~1th 1nd1cat1ons of tense) then something is being told about what happened to the subject. Imp I ici ~ then in t~e in~tr~cti~ns attached to "be" is the act1ve /pass1ve d1st1nct1on but it not looked for in those terms but rather is part of a general semantic function of "be" just like "John is dead."

The fol lo~ing description of the analysis of a sentence may help to clarify the processes involved. The sentence is "John told Mary that Bi I I wants a book." The first ~ord of the sentence, "John" tells the analyzer nothing about ~hat is going to happen. but only gives a subject for some verb or predication to fo! lo~: Subject is a syntactic relationship that has semant1c !mporta~ce only in that it is a place to save som7th1ng. ~h1 le the conceptualization involving that someth1ng 1s yet unkno~n. Th.ere are other place-holders avai I able, 1 ike object and recipient ~hich are . useful to _distinguish words from each other ~ithout mak1ng a commitment about any particular conceptual role they ~iII play. Thus in "John gave Mary a beating," the ~ord "give" assigns a syntactic role of recipient to "Mary" but eventually the conceptual role for "Mary" ~iII be as the conceptual object of "beat". Syntactic roles thus serve a purely utilitarian function, highly specific to the needs of the verb involved. No semantic reality is attached to them and thus one verb's us& of ~hat the analyzing program labels an object ~iII have no necessary relationship to what some other verb does ~ith ~hat it cal Is an object. A verb needs only enough places to save those things for ~hich it hasn't determined conceptual roles.

Returning to the sample sentence, fol lo~ing "John" ~e have the verb "told". No~ this ~ord tel Is us many things. It tells us that there Is a communicative act involved (~hich is cal led MTRANS in conceptual dependency). By its morphology it tel Is us the act took place before the time of speaking. It tel I us that the subject of the verb is the actor of the action and also that the information was originally in the active part of his mind, cal led the Conscious Processor !CPJ. It tel Is us that if a human fol lo~s then that person's CP is the conceptual recipient of the communication. It te I Is us that there ~ i I I be a another conceptualization, I ike "Bi I I ~ants a book," or at least a ~ord signifying a set of conceptualizations, I ike a "lie" or a "story", ~hich ~ill follow soon.

The ne><t ~ord , "Mary", satisfies the e><pectation of a recipient for the action. Like "John" the major action on the part of "Mary" is to say it is a human. Out of conte><t it doesn't add any ne~ e><pectations to the hand I ing of the sentence.

The ne><t ~ord, "that", is one that does have functional effect on the analysis of the sentence. It says that if it is fol lo~ed by a simple noun it is being used to say that the object follo~ing, e.g. "that joke", is one the hearer should kno~ about, either from past kno~ledge or from information that is about to come. If "that" is fo II o~ed by anything e I se it says that the conceptualization e><pected by the previous verb is being started and the analyzer should be prepared for a new set of syntactic and conceptual roles and role f iII ers.

The ne><t ~ord,"Bi II", is not a simple noun and so the analyzer, obeying ~hat "that" told it, assumes that "Bi II" is a ne~ subject, just I ike "John" ~as. Other than that and information about the starting point for tense determination the analyzer kno~s nothing, out of conte><t.

The ne><t ~ord, ·~ants", says quite a bit. As should be obvious the verbs and acts and function ~ords ,I ike "that" and prepositions ,are the driving force behind the analyzer. They set up conditions that tell where ~hat has come and ~hat is predicted to come should fit and the nouns and adjectives and previous conte><t serve as the data base for these instructions to operate upon. "Wants" gives us the conceptual information that the topic of the sentence is something that "Bi II" believes ~iII cause him pleasure. In Conceptual Dependency a person's belief of some conceptualization is represented as the presence of that conceptualization in the passive part of his mind, cal led the Long Term Memory (LTMJ. "Wants" tells us that if a verb form "to X" follo~s then that is the action Bi I I ~ould I ike and further either he is the actor or, if the "to" ~as preceded by another person, then that person is the actor of ·the action specified by the verb. If the only thing that fol lo~s ·~ants" is a noun phrase then the action that ~auld give Bi I I pleasure must be assumed from the nature of the object and the conte><t. There are other options fol lo~ing ·~ants" of course but the above includes the relevant one.

The ne><t word is "a" ~hich causes a syntactic holding to occur in the analysis. That is "a" tells the analyzer to collect from the sentence first a complete phrase, ending with a noun, attach the preceding adjectives and nouns to this final noun ~ith the appropriate conceptual relationships and then pass this result back to the I ist of e><pectations set up by the previous function ~ords of the sentence. The finding of a phrase boundary is not independent of the conte><t of the sentence, nor is it a clear cut process, as can be seen from the two sentences, "The city people I ike is New York" and "The city people I ike New York." But then very IJttle in the comprehension of sentences is clear cut.

The next word, "book", is absorbed into the phrase being bui It, but we don't know yet if the phrase is ended or if "end" or "marker" or something wi I I follow.

The next thing to come is the end of the sentence. This has a major effect on many analyses. The various function words have prov1s1ons for what kind of assumptions to make if the sentence ends before they get all the information they need . The first use of the sentence end is by the instructions attached .to "a". The article recognizes that the end of a sentence ends a phrase and so the concept of a "book", noted as being i nde fin i te I y referenced, is passed back to the instructions attached to "wants". These instructions, seeing that the sentence is finished and seeing that no action has yet been specified involving the book , make an assumption that B iII wants to have the book. This is a general assumption made with alI inanimate physical objects. Another assumption that might have been made i.f the object were a person is that Bi I I wanted that per~on to come to him. When "wants" has taken care of all thebusiness that it needs to, the structure of B iII wanting a book is passed back to the instructions attached to "told". Since everything that "told" has said was crucial has been done the analysis of the sentence is finished. The final result follows, first as the analyzer outputs it and then as one normally finds it represented in articles on conceptual dependency.

(JOHN TOLD MARY THAT BILL WANTS A BOOK!

!!ACTOR !JOHNll <=> . !*MTRANS*l TO !*CP* PART !MARY! l J FROt1 . <*CP* PART <JOHN! l l MOBJECT <!CON <!CON !!ACTOR !*ONEl*l <=> !*ATRANS*l OBJECT !BOOKl REF (*A*ll TO !BILLll J TIME !1IMe3JJ <&C ((ACTOR !BILLll o>T (*JOY*l <=>F (*JOY*) J INC !2l TIME <TIMe2J J l J <s> <*MLOC* VAL (*L™* PART !BILLlllll TIME <TIMeeJJJ TIME !TIMelJJ

TIMee ! (VAL *hl l

TIMe! !!BEFORE TIMee Xll

TIMe2 !!AFTER TIMee Xll

TIMe3 ((AFTER TIMee Xll

We have seen now what sort of concerns have guided the construction of this analyzer. The stress has been on the finding of the meaning, not the structure, of a sentence. The processes avai I able have been ones based on a left to right handling of sentences, where each word contributes something to the choices to be made and the analysis program itself is basically a . monitor executing these contributions. Further not only is the meaning the ul itmate goal of the analysis but meaning, in conceptual representation, is the major source of information to guide the getting of more meaning. For example, the fact that a communication

1~as i nvo I ved makes the ana I yzer I oak for another conceptualization, not the particular syntax of "tel 1".

This approach has not solved immediately any of the classic problems of ambiguity and contextual relevance. What it does do is provide a format where the solutions to such problems can be formulated in terms that match commonsense descriptions of how people figure out meanings.

The sentence whose analysis was followed above wi I I be discussed further with respect to reasonable inferences that can be made upon it. The section on generation uses different examples which give a better indication of the paraphrase capabi I ity of the generator. These other examples can also be successfully analyzed by the program and the analyses differ in no fundamental way from what has just been described. An example is "John advised Mary to drink the wine." "John", "Mary", and "wine" are like the nouns in "John told Mary that Bi II ~1ants a book." "Advised" is the communicative act MTRANS as is "told", with the added expectation that the word "to" w i II probably introduce an action for the recipient to perform, and further if the recipient performs this action the recipient wi I I be better for it. Hence the analyzer's output for "John advised Mary to drink the wine" is :

!!ACTOR !JOHNll <=> (*MTRANS*l TO !MARYll REF !*THE*)) FROM !*CP* PART !JOHNll MOBJECT !!CON !!ACTOR !MARY!) <=> !*INGEST*) REF !*THE*J) TO !*INSIDE* PART !MARYlJ) FROM !MARYlll INST !NILJJ MODE !NILJ TIME !(ACTORJJJ <aC !!ACTOR !MARYll <~>T (*JOY*l INC !2l Tlt1E <TIMe2J MODE !NILJ l l l l FOCUS !N ILl Tl ME !TI Mell l !*CP* PART REF (*THE*l l OBJECT !WINEl !*MOUTH* PART <T!Me3J FOCUS <E>F (~OY*l ) (!ACTOR) J MODE

TIMee

TIMe! !!BEFORE TIMee Xll

TIMe2 !!AFTER T!Mel Xll

TIMe3 !!AFTER TIMel Xll

which graphically is the following:

MEMORY's principal tasks are the following:

1. to convert the format of the input, as just described, to positional internal memory form. This process also involves the I inking-in of immediately-identifiable concepts with the occurence !ets of those concepts (occurence sets are explained shortly).
2. to establish references to tokens of concepts for as many of the other concepts and possible from the descriptive set returned for the analyzer. An example of a descriptive set is: real world tokens as each from for "John"

X: !!!SA X #PERSON! !MALE Xl !NAME X "JOHN"ll

When the descriptive set unambiguously identifies some

#JOHN in MEMORY, this #JOHN is used in the internal form. When no #JOHN satisfies the descriptive set, or ~hen several do, a !possibly temporary! token is created storing the facts in the descriptive set as its occurenc~ set, and noting this event on the list !UNKNOWNREF.

• !31 to extract subpropositions from the conceptualization at points before and during inferencing. Those extracted before usually come from BEL 1 ink ~~~ as in "the red dog", !DOG .... !ACTOR !DOG! <a> !COLOR,VAL !REDJJJJ l embeddings, and, together ~ith the main proposition, comprise the initial list of propositions submitted to the breadth-first inferencer.

!41 to generate inferences of five basic types from each subproposition. These five types are !"X~ Y" means "Y is Inferred from X"l:

• !al NORMATIVE. What is the normal state of affairs in the ~or I d? EXAMPLE: "Where is John a·t SAM Tuesdau?" "Probably at ~ork."
• !bl PERIPHERAL. What "surrounds" a si tuatlon; ~hat do people automatically assume ~hen hearing something? EXAMPLE: "John told Mary that Bi II sa~ Rita." ~ "John kno~s that Bi I I sa~ Rita."
• !cl CAUSATivE. What ~ere probable causes of some state or action. EXAMPLE: "John hit Maru." ~"John was mad at Mary."
• (d) RESULTATIVE. What are the probable results of some state or action? EXAMPLE: "John bit Bi I I"~ "Bi I I is hurt."
• !el PREDICTIVE. What might an actor do, given his current state? EXAMPLE: "John wants an icecream cone." ~"John might go to the store."

A very important goal for making inferences is to analyze an input on both the ACTUAL level !what the conceptual dependency diagram conveys I iteral lyl and the level of INTENTION of the actors (~hy did they do ~hat they did,) For all inferences, particular attention is accorded to maintaining a record of what generated ~hat. This means that for any proposition in MEMORY, there is a list of other propositions ~hich participated in its generation, and a I ist of propositions in whose generation it has participated. Also, for RESULTATIVE and· CAUSATIVE inferences, in addition to the ne~ inference, a !CAUSE X Yl relationship is generated between the old and new information.

• !51 to make use of RESULTATIVE and CAUSATIVE inferences to fi I I in missing causal chains. For example, the ana I ys is of "Mary kissed B iII because he hit John. · would result in a causal which stood for several intervening unspecified causals: (a) Bill's hitting John caused John to be hurt, (b) John's being hurt pleased Mary !a peripheral inference is that Mary feels a negative emotion toward B iII J, (c) Mary's pI easure was caused by John's action, (d) Mary therefore feels a positive emotion toward John, !el this causes her to kiss John. This is a v.ery common and important MEMORY function, and is ca II ed CAUSAL CHAIN EXPANSION.
• !61 to detect when the same inferred information asises from two distinct sources !for example, when a PREDICTIVE inference made from one I ine of a story is confirmed by some later story line). This is cal led KNITTING !see [4JJ, and generally indicates that MEMORY has, by inferences, been able to show how information in a etory is connected. A very simple example of this is the following:

"Mary was hit by a car." "She went to the hosp ita I."

"John wanted a wrench."

"He went to the hardware store."

or where, inferring that Mary was badly hurt, MEMORY predicts that she wi I I go to the hospital, ·and this is immediately confirmed by the next I ine !notice that this pred iction would help understand "The nurses were very kind." if this sentence were the second I ine of this story!.

• !71 to detect and try to fi II in miss ing or unspecified concepts !tokens) or events during inferencing. This includes supplying information to the analyzer in cases such as "John hit Mary", where, in the absence of other information, the object of the PROPEL ACT involved in the hit is inferred (by a NORMATIVE inference! to be !HAND PART !JOHN! J · In the sequence "John pi eked up a rock." "He hit Mary. " , MEMORY would apply the knowledge that people hit other people with whatever they are currently holding, and would in this case return !ROCK ~~ !ACTOR !ROCK! <·> (*LOC* VAL !HAND PART !JOHNJJJJI. In the example which wi I I be described shortly, MEMORY wi I I detect a missing concept during inferencing, and wi I I ask a question about it.

MEMORY rei ies on two main data types for the storage of conceptual information and concepts and their tokens: CONCEPTS and ~. A bond is a I ist of concepts which is stored with property BONDVALUE under a system-generated atom, cal led a SUPERATOM. A concept, or a token of a concept is simply a LISP-generated atom. If it has a name, the name is stored in the same way alI other conceptual information about the concept is stored. Both bonds and concepts have an OCCURENCE SET, ~hose value is a I ist of superatoms under which are stored bonds in ~hich X occurs. MEMORY is therefore a· fully inverted structure. Conceptually, the occurence set of a bond or concept is a catalog of alI conceptual kno~ledge about that bond or concept. This form of data base faci I itates rapid lookup and simp I ifies simulation of para I lei associat ive searches.

In addition to its occurence set, each bond, X, has associated with it two very important properties: its REASON SET and OFFSPRING SET. The reason set is the list of other propositions in MEMORY which contributed to the generation of X, and the offspring set is a I ist of propositions in whose generation X has participated. Thus MEMORY is preserves I ines of reasoning as wei I as the facts lying along those I ines. Other properties of bonds and concepts are: TRUTH {is this fact currently believed or not), RECENCY !~hen was this bond or concept last accessed), and STRENGTH (if believed, with what strength). Strengths are propagated and can be dynamic~! ly updated when the strength of propositions on some bond's reason set changes.

The flow of information in MEMORY in response to conceptual input is as follows. The graph is transformed syntactically into internal positional notation. During th i s process, subpropositions communicated by BEL <~~1 I inks and main-conceptualization modifiers !I ike time and location! are noted as potent ial subpropositions. Also during this phase, direct references to predicates and concepts are immediately I inked into the correct occurence sets. This includes the creation of new time tokens. Next, as many references to tokens are established from descriptive sets as are possible. Potential BEL subpropositions used in this step are processed no further. Possibly temporary tokens are created for alI unidentified referents {using the available descriptive sets), and bonds are created for the structure's proposi.tions and stored. At this point, there is the main conceptualization, a I ist of subpropositions , and a I ist of unidentified references.

The main conceptualization and subpropositions are submitted in paral lei to the inference mechanism. This is a simple breadth-first monitor which looks at the predicate of the proposition for which inferences are desired, and locates the ~CE MOLECULE for that predicate. No pattern matching is done in the monitor, only in inference molecules. The monitor also collects as much TIME information as can be found about the bond into a condensed form and makes it available to the inference molecule. All inference molecules are time and context sensitive. The molecules are highly structured LISP PROGs which the monitor executes.

The result of executing an inference molecule is a I ist of inferences (which are pointers to newly created bonds in MEMORY!, organized by inference TYPE and a simple INTEREST measure. Inferences are reordered, cut off below certain interest and strength levels, and stored on the master I ist. After inferencing has ceased, the monitor rescans the master .I ist to detect actions, asserts the volition of actors by assuming the actor WANTED the results of his action, and submits these new WANT propositions to the inferencer again.

As each inference is generated, an "evaluation function" is applied to it to detect one of three situations: confirmation, contradiction or augmentation. These are the heart of the causal chain expansion and knitting mechanisms described above, but are beyond the scope of this paper (see [4JJ. Also during the inferencing, the I ist of unidentified concepts may be augmented by some new inference requiring knowledge which MEMORY cannot guess (the example wi I I show such a case) . These go on !UNKNOWNREF. There is a similar I ist, cal led !UNKNOWNCON on which missing actions or states (which MEMORY cannot predict) are noted.

After all inferencing ceases, the referencer is re­ entered in the hope that the inferencer has generated new information about unidentified references at the beginning. ] f any more can· be so I ved at this time, the inference mechanism is re-applied, not duplicating previous work since inference molecules remember which inferences were successful on the first pass. This second pass is done in case the no~-accessible occurence sets of the ne~ly identified concepts wi I I open new inference paths.

Afte·r these processes, potential responses come from the following sources: interesting inferences, !UNKNOWNREF and IUNKNOWNCON . At present there are no heuristics for deciding ~hat to say, so MEMORY merely dumps everything on the generator for expression. For each conceptualization to be expressed, this involves conversion from internal to external format. Part of this is just syntactic, but part is deciding ~hat information to include about each bond and concept since there are generally many members of each concept's and each bond's occurence set. This is a theoretical issue which has not been addressed by· this research. Hence, MEMORY uses some fairly simple heuristics for deciding ~hat to include in the expression of each bond and concept. Examples of ~hat to include are: for all concepts, a NAME if possible; for bodyparts, who is it part of; for a state, its begin and end times (or just a time); for an action, time, mode, location, and so on.

The proper hand! ing of time relations has been a central issue in this project. ln MEMORY, this means that, as ~elI as time-sensitive inference molecules, there must exist proof procedures for determining BEFORE (and other) relationships. Also this means that outdated propositions can be kept around by proper maintenance of their time dependencies. The imp! ications of this approach from the standpoint of the frame problem are discussed in [4].

A summary of what happens to the parser output from the sentence "John told Mary that Bi I I wants a book." ~iII no~ be given . We ~iII not pursue the problems of reference establishment, but assume a perfect internal form can be created immediately. Only the inferences ~hich go to the generator ~iII be shown.

The internal form ~hich results from this input is: (time relations have been omitted for clarity)

(P: peripheral, R: resultative, C: causative, PR: predictive, N: normative, MlQ: missing information

question)

• (PJ John be I i eves that B i II wants a book. (People generally believe ~hat they communicate to others. J
• (RJ Mary now knows that Bi I I ~ants a book. (People normally believe factual information they are told.)
• (PJ B iII 1~ants a book. !MEMORY believes what it hears too.)
• (P,Rl Bi I I ~ants to come to possess a book. (People want actions because of the predictable results of those actions. One certain result of an ATRANS is that the recipient acquires possession of the object.)
• (P,Rl Bi I I possibly ~ants someone else to cease to have a book.

(Another result of the ATRANS is that the donor ceases to have the object. This has a much lower strength than the previous one.)

• !Nl B iII ~1ants to read a book . !People usually ~ant to have objects to use them in their normal function.)
• (P~Rl Bi I I wants to know the concepts contained in a book . (This ~ould be a result of reading a book.)
• !MIQJ A book about what? (The concepts predicted by the last inference are not known. Other useful inferences could be generated if MEMORY kne~ ~hat the book is about.)
• (PRJ Bi II might get himself a book. (Knowing someone's state, he may be predicted to do certain things.)
• (PRJ John might give Bi II a book. (Kno~ing someone's wants, another person might
• attempt to satisfy th~m.l
• !PRJ Mary might give Bi II a book. (etc.)
• (CJ John may want Mary to give B iII a book. (A person's motivation for communicating a want might be to have that want satisfied.)

Memory passes each of these in turn to the conceptual generator.

7. Gene.rator

The third major component of this system is the generator, which has the task of expressing arbitrary conceptual structures in surface lexical form. This is accomplished by two sequential transformations of representation. The first phase produces a syntactic "case" network from the conceptual representation. The second phase is carried out by our version of Simmons' program, which uses an augmented finite-state transition network to map these case networks onto surface forms.

When the memory model decides it wishes to express some information as natura I I anguage strings, it passes a I ist of conceptualizations containing that information to the generator. The generator is capable of expressing the inferences .made by the memory model from our example sentence; ho~Jever, to better explain ho~< generation is accomplished and to demonstrate the paraphrase capabi I ities of the program, it J~i II be useful to consider the second example mentioned in section 5. When paraphrasing, the generator might receive the encoding produced by the parser for "John advised Mary to drink the ~<ine". The structure which the generator ~<arks with is:

This network consists of a set of nodes !Nl,N2, ·.. ) each associated with a set of syntax relation-value pairs . Both the tokenJ e.g., JOHNl -- and the relations-­ e.g . , OBJ2 --of !BJ are assumed to be language-dependent. The tokens in !BJ are not Eng\ ish ~<ords. They are, however, entries in an Eng\ ish lexicon, ~<hich can be easily mapped (by dictionary look-up) onto Eng\ ish ~<ords. The relations are chosen because of the syntactic rules of Eng I ish. In order to create the syntax net, the generator must choose the proper lexical entries and syntax relations based on the contents of the language free conceptual structure.

The simple conceptual ~ lexical transformations JOHNl ---> JOHN and WINEl ---> WINE are accomplished via dictionary I oak-up in the current program. It is the method of discovery of the tokens ADVISE and DRINK, ~<hich do not correspond to any isolated conceptual units in !AJ, which makes the generation process both interesting and po~<er fu I.

The generator has avai \able to it a set of discrimination nets through ~<hich conceptual structures are filtered to discover ~<ord sense units. Each discrimination net is a binary tree, ~<ith predicates at branching nodes and ~<ord senses at terminal nodes. The predicates are of three distinct types:

1. pattern matching ~<i thin a conceptual structure
2. high-level definition-- does a substructure of the conceptualization satisfy the predicates of a particular ~<ord sense
3. memory queries requests for information from ~<arid model, possibly requjring deduction

Given a conceptual structure, the generator must first find an appropriate discrimination net. The skeletal structure of the conceptualization is checked (<··>, <&s>, etc.). In some cases the structure alone specifies the proper network. In example !AJ above, ~<e have a simple event, and the primitive ACT involved !here, MTRANSJ is checked to determine ~<hich net to use. Figure 1 sho~<s a portion of the net~<ork ~<hich ~<auld be chosen for this example.

When this net is applied to (AJ initial tests at node 1, which discriminate representations of 'perception' verbs from 'communication' verbs, pass control to node 3. Here it is determined that REFUSE1 is not an appropriate sense for !AJ and contra I passes down to node 6. A test here discriminates a class of verbs meaning "communicate that an event would benefit someone". !AJ falls into this meaning class, so control passes to node 13. At this node a ch~ice ,.base~ . on t~e identi t~ of . the "potentially benefitted IndiVidual 1s made. S1nce 1n our example this is the RECIPIENT of the MTRANS !MARYll, the branch leading to ADVISE! and RCMND (a sense of "recommend") is taken. Eventually terminal node 55 ~ith the ~ord sense ADVISE! is reached.

'ADVISEl' has associated ~ith it a lexicon entry !ADVISE! and a frame~ork --a I ist of syntax relations ~ith a specification of a substructure of the conceptualization ~here the value for each can be found. For 'ADVISE!' the frame~ork contains the pairs:

RELATION

CONCEPTUAL LOCATION

ACTSBJ OBJ2

ACTOR RECIPIENT OBJECT

Each of these substructures is then used as the generator program, resulting in the syntax net !Bl. Further processes add such TENSE, VOICE, and determiners to the syntax an argument to construct"ion of information as net.

INFinitive

This example has sho~n ho~ the generator may reconstruct a syntactic case representation of an English input directly from its conceptual representation. It is not necessarily the case, ho~ever, that the syntax net derived ~iII correspond directly to the original input. There are t~o independent sources of the paraphrase capabi I ities of the generator. The first is implicit in the theory on ~hich this form of generation depends. Since the conceptual net~orks from ~hich the generator ~orks are (1 l I anguage-free, and

!21 unique representations of meaning,

the generator is not tied to the same vocabulary as the parser, nor even to a synonymous one. In generating !Bl from !Al, there is no clue that the ~ord 'advise' ~as used in the original statement.

There is also an explicit paraphrase capability in the generator. Terminal hodes may contain, in addition to ~ord-sense tokens, pointers back into the discrimination net. (These pointers are ~ritten as [t node-index) in Figure 1. In fact, some terminals contain only such pointers.! In paraphrase mode, the control algorithm may ignore a ~ord-sense token at a terminal and resume the filtering operation at the node indicated by the pointer, thus finding a different ·~ord-sense' for the conceptual (sub-) structure. This sense may have a very different lexical unit and syntax frame~ork associated ~ith it, resulting in a syntax net differing in many aspects from that previously obtained. If 'ADVISEl'~ere ignored in the preceding example, filtering ~ould resume at node 54 of the discrimination net, and the head 'RCMND' (among others) ~ould be found. The fol lo~ing paraphrases are among those obtained for conceptual izatidn !Al:

John recommended to Mary she drink the ~ine.

John suggested Mary ~ould I ike to drink the ~ine.

John told Mary she ~ould enjoy drinking the ~ine.

No further description of the surface generation phase ~ i I I be given here. It shou I d be emphasized, ho~ever, that the relations ~e are dealing ~ith in the syntax nets have only syntactic significance to the process, and no semantic properties are ascribed to them. All 'meaning' is treated at the conceptual level; thus .the notion of a semantic net as proposed by Simmons has no place in MARGIE's generation system. In addition to obvious theoretical implications of this difference, there is the practical consequence that ~e can, in general, expect a simpler net~ork grammar to handle a given subset of a language. Consider, for example,

{a) John broke the ~indo~.

(b) John remembered to go home.

The 'semantic' deep case interpretation may involve marking John as an AGENT (instigator of an action) in {al, but as a DATive or EXPeriencer (one affected by an action) in (b). We can mark 'John' as ACTSBJ in both cases, since the only property of the relation in ~hich ~e are interested is that it becomes the subject NP in active sentences.

8. Conclusion

MARGIE is intended primarily to be the beginnings of a larger .more complex system for language understanding. Many effect 1 ve natura I I anguage underefand i ng programs ~ork 1n ~everely restricted domains. Thus, many of the techniques that ~ork, for example, in Woods' moon rocks system [131 or Winograd's [121 blocks ~orld are not necessarily expandable to a larger domain. We have felt ~hat a consistent co~ceptual representation is very Important be:o~e attempting 7omputer understanding. Our analyzer ut1 I 1zes the properties of this system to aid its analysis of input sentences. The memory, ~hich certainly o~es much of its design to notions brought for~ard by Qui I I ian [3) and Becker [1), operates on these conceptual ~epre~enta~ions, ~hus simplifying the problem of handling 1dent1cal 1nforma~1on by al !o~ing only one possible deep format for a g1ven mean1ng. Inference is thus more straightfor~ard because of the very fe~ primitive actions that exist in the system (see [71 and [8)). By using a deep. con7eptual 7ystem of the type ~e propose, the Engl1 sh-l1ke quail ty of the input is lost. While this faci I itates understanding it also creates the problem of receding information back into English. We have found Simmons' program to be helpful in this regard, but most of the problem ~as left unsolved by his program since his representations are considerably less deep than ours.

We have found MARGIE encouraging ~ith respect to the prospects of a larger system and thus ~e stress that ~hi le ~ur com~uter results are interesting, it is the theoretical des1gn of the system that is important for future efforts.

9. References

1. Becker, J. 'A Mode I for the Encoding of Exper i entia I Information' in Schank and Colby (edsl, Computer Models of Thought and Language, W.H. Freeman&. Co., San Francisco 1973.
2. Go I dman, N. 'Computer Generation of Natura I Language from a Deep Conceptual Base' Ph.D. thesis, Computer Science Dept., Stanford University, Stanford Cal. 1973. '
3. Qui II !an, R. 'Semantic Memory', Bolt Beranek & Ne~man, Cambridge, Mass., 1966.
4. Rieger, C. 'Conceptual Memory', Ph.D. thesis, Computer Science Dept., Stanford University, Stanford Cal. 1973.
5. Riesbeck, C. 'Computer Analysis of Natural Language in Context', Ph.D. thesis, Computer Science Dept., Stanford University, Stanford Cal. 1973.
6. Schank, R. 'Conceptual Dependency: A Theory of Natural Language Understanding' in Cognitive Psuchology vel. 3, no. 4, 1972.
7. Schank, R. 'The:·Fourteen Primitive Actions and Their Inferences', Stanford AIM-183, Computer Science Dept., Stanford University, Stanford Cal. 1973.
8. Schank, R. and Rieger, C. 'Inference and the Computer Understanding of Natural Language', Stanford AIM-197, Computer Science Dept., Stanford Cal. 1973.
9. Schank, R., et al 'Primitive Concepts Underlying Verbs of ~hought', Stanford AIM-162, Computer Science Dept., Stanford University, Stanford Cal., 1972.
10. Simmons, R. 'Semantic Net~orks: Their Computation and Use for Understanding Eng I ish Sentences' in Schank & Colby {edsl Cqmputer Models of Thought and Language, W.H. Freeman 1973.
11. Simmons, R. and Slocum, J. 'Generating Eng I ish Discourse from Semantic Net~orks', Communications of the ACM, val. 15, no. 10, October 1972.
12. Winograd, T. Unperstanding Natural Language , Academic Press, Ne~ ·York, 1973.
13. Woods, W. 'Transition Net~ork Grammars for Natura I Language Analysis', Communications of the ACM, vol. 13, no. 10, October 1970.