Preliminary Report On A Program For Generating Natural Langugage

Introduction

At the present time, there are intelligent, interective prosrams under development which will require greater fluency in generatin& netural lan&uage than any current system can offer. Three such programs, in particular, are a personal schedulin& program (Goldstein <2>), 1 progr~mmer's ISsislanl (Rich 1nd Shrobe <3>), and the MACSYMA advisor (Geneserilh <4>).

A characteristic of all these programs is that they will employ models of their users - of their habits, and the things they are likely to know in various situations. They will also maintain models of themselves and their intentions as they reason and interact with their users. This will h.ave a large effect on the design of a suitable generating facility for them.

Level of Fluency Desired

The sort of conversations we hope these progr~ms will eventually be able to have are typified by the short example below, between a scheduling program (P) playing the part of a secretary scheduling appointments for a professor, and a student (S).

• (S) I want to see Professor Winston sometime in the next few days.
• (P) He's pretty busy this week. Can it wail?
• (H) No, I need his signature on my petition before Friday.
• (P) Well, maybe he can squeeze you in tomorrow morning. Give me your name ·nd check back in an hour.

These are very fluent 11nswers by human standards. The wording is colloquial - "pretty busy", "squeeze you in" - but at the same lime, it deliber~lely conveys useful information; casual speech can give an impression of flexibility. Impressions like this can be as important to the total message as the sentence's propositional content. Similarly, the use of "well" at the beginning of a reply can signal an admission on the part of the speaker that the answer which follows may not be adequate. This realizes a need within the discourse situation that is properly part of conversations amon& people, and should be included in converslalions between computers and people.

MesSI&es

Before the linguistic component is called in, the main program (for example <2>,<3>, or <4>) has IS total a picture as it needs of whet is to be uid. II knows that it wants to mention certain perticular entites and certain relelions among them, and to achieve 1 certain effect upon its audience. To communicate with the linguistic component, this information is collected into a data structure, a ·message·. A message can be viewed IS consisting of two sorts of things.

1. A collection of pointers to the internal objects thai are to be talked eboul. The pointers are annotated to describe how the objects relate to each other and the messaae as a whole.

1. A list of features which characterize the primary program's communicative intent in making that messqe.

The following structure is an example of what a mesuge might look like. The word on the left of each pair Is the ennotelion, and the phrases on the right in angle-brackets represent objects in the main program with rouahly the meanina of those phrases.

rnessege-1

feetures (prediction) proposition <status-of-person> ltype <busy> lot <Winston> hedge <70'l chance>

time-predicted < 12:00-17:00>

This message may be translated into the sentence: "Professor Winston will probably be busy all afternoon·.

The character of the translation

Translation from the internal representation of a computer program to natural language is very much like translating from one lenguage to another, and the same problems arise. Basically, the problems are that the same concepts may not exist IS primitives in each lenauage, and that the conventions of the laraet languaae mey require additional information that was not in the source lenguage. Translation, therefore, cannot be simply one for one.

What Enalish phriSe should be used for a particular element in the program's message will vary as a function of what is in the rpst of the message and of what the external context is. To allow these factors to be adequately considered, lht !ranslalion of an element is carried out by special procedures called ·compOsers· which may lake into account a wide variety of phenomena as they do their translation.

Every concept, name, structure, process, or other entity which the main program might employ in a message will be associated with such a describing procedure. The association might be a direct pointer from a unique name in the program to its composer, or it might be derived by examining ·is-a· links or ·type· features associated with the object (e.g. all things of type ·event· might share a composer). Composers are run at predetermined points in the translation process and are designed to expect a particular computational/grammatical context at that point.

The translation to English, then, does not employ a single, unified grammar, such as an ATN (<7>,<8>). Instead, the grammatical information is distributed among the individual composers. This is in part a matter of prognmmina aesthetics, end in pert due to a belief that the attendant increase in modulerity and flexibility will make the arammar more tractable end eesier to improve.

Control Structure

With the grammar distributed among a very large number of separate processes, the task of coordinating their actions becomes of paramount importance. Roughly speaking, the translation process has this character : the intentions and objects in the message will suggest (via their compOsers) slretegies for real izina themselves in English. However, these strategies may be blocked or modified by general linguistic information in ·the gremmar·, or by the effects of decisions made by earlier slrateaies. (The term "the grammar· refers to the collective information in the composers and their data structures, rather than some central body of constraints.) ·

The control structures required to implement this process are themselves, very simple. This is because the descr iptive epperatatus of the grammar can provide a rich enouah description of the situation to direct the actions of the compOsers and keep them, in effect, from tripping over each other's feet.

This would not be possible if it were not for the fact that neturel lanauages are very complex entities with rich structures. In more concrete terms, this is to say that languqes are made up of 1 relatively large number of types of structures (noun phrases, function words, inflectional endings, modifiers, etc.) and that the possible arrangements of these structures are very highly restricted - only a few combinations are pOssible. By encoding this information into a system of features and data structures, end then writing a grammar for the compOsers in terms of that system, 1 tremendous, implicit coordination should be achieved.

This coordination does not come automatically of course. Since situations are defined in terms of features, a composer will recognize where it is by using conditional statements involving those features. The larger the number of pOssible situations that I particular composer may be run in, the more intricate its conditionals will be, and the harder the compOser will be for the human designer to write. ·

Pert of the job of cuttin& down on the complexity can be done in the grammar by increasing each feature's descriptive power (and probably adding to their Ioiii number). The more informelion that a given feature codes for, then the more decision~ thel can be made solely on its basis. An even more effect ive technique is to closely control when the individual composers will be run. This can provide imr.1icit situational information. Also, if it cen be arranged that a decision, once made, seldom has to be reconsidered, then a considerable overhead in mechanism and composer code will be saved.

The requirement of linear order

One of the fundamental charecterislics of naturtl language is that utterances are necessarily made up of linear strings of words. This requlrment is an inescapable fact of the "physics" of naturel language and accordinaly, it has been given a large role in conveying information. It can realize propositional meanina end rhetorical intent, and permit abbrevi1t ions throughout the utterance for example.

Fortunately for the program designer and the linguist, those things that are ordered are not arbitrary clumps of words, but rether structural units (noun phrase, adverb, etc.) with two import ant char aclerislics.

1. They seem (not coincidentally) to describe categories of experience which are nalur1l to us as people and which we will probably wanl to introduce into our computer progr~ms.
2. Linguistically speaking, they are very modular and c·n usually be ·moved· to several different positions within an ulter~nce to achieve rhetorical effects, and require only minim1l, well specified structural changes in each position.

The majority of the descriptive compOsers in the lexicon will describe their corresponding internal entities with just such coherent grammatical structures. Most of the syntactic details of these structures vary with position in the sentence. If these composers can be given 1 guarantee that the position of their object will not be shifted as the utterance is further developed, there will be a considerable savings in the complexity of individual composers and in the overhead required to manage them.

Two Phases

To provide this quaranlee, the translat ion process is divided into two phases. During the first phase, the message as 1 whole is ex1mined according to the intentions given for it 1nd the ennotetion for each object that it mentions. A ·plan· is selected for it (see below) which embodies the syntactic structure of the ultimate utterance and which has "slots" in it into which the laraely "unewpanded" objects of the mesuae are transfered. In this phase, all of the elements in the messaae which will involve orderin& conventions in their realiution (translation) are found and the plan modified to accomodale them.

Durin& the second phase, the developed plan, which is essentially a constituent structure tree with the possible positions eMplicitly labeled, is "walked" from lefl to ri&hl and lop down - as it would be spoken - and the objects in it are dascribed by their composers as they are encountered. With the "proto-utterance" represented in its surf ace structure form during this phase, relationships become apparant which could not otherwise be seen. These include the possibililes for pronominalizing elements, and the actual scope of qu1nlifiers. These can be dealt with by syntactic procedures associ1led with the fe1tures end gr1mm1litll units in the plan.

Dill-directed processing

In both phases, control is data-directed. In the first phase, the d1l1 structure being interpreted is the message, and in the second, it is the plan that was chosen 1nd filled in during the first ph1se. This is enother source of coordination for the composers since the control of their order of execution is now governed by struct~res which can be written to be very rich in grammatic1l informetion.

Let me summarize what has been said so far. This design proposes that a very loose, modular framework can be used in language generation; that it will be most convenient if the domain and audience specialists in the program be allowed to work out their message independently of its ultimate linguistic details; and that when the lime comes to consider the linguistics, the process should be viewed as a translation which is performed by a large number of specialist procedures associated with the possible things which may appear in a message. The operation of these specialists can be coordinated implicitly by the grammar and dat. structures that are developed.

In the rest of this paper, I will describe ~ome of operations 11nd structures of this design in more detail.

All natural language programs and linguistic theories employ, in one form or another, a tree structured constituent analysis of their sentences in terms of the traditional arammalical units. My design · is no different, except that I have found it necessary to augment the usual descriptive framework to make it capable of the task at hand. This has resulted in the data structure I call a "plan".

The principle function of plans is to mark the possible positions in a grammatical unit, in terms of a fixed vocabulary of slots such as "subject", "main verb", "post-verb-modifiers", end so on. The slots in a plan ue arrenged in a fixed order corresponding to the normal English surface structure. For elCample, if we used the grammar developed t.1 Winograd in his SHRDLU program <5>, the slots in 1 noun phriSe would be as follows.

NG - !determiner !ordinal !number !adjectives fclasifiers !head noun !qualifiers

Since the slots are named, they can be referred to directly from within the grammar, rather than requiring some complicated tree walk and string matching operation as in PROGRAIIAIIAAR <5>, or in transformational grammars. The grammar can, for eumple when it is doing verb aareement, ask what is the number of the object in the subject slot, or, when considering using exlraposition, ask if the subject witt be described using a clause.

The major motivation for naming the possible positions within a arammatical unit involves more than convenience in writing arammatical rules. The basic operation durin& the first phase is to insert another element from the message into an established plan. To do this, the composing procedure must know: 1) what positions are open in this plan where it is grammatically feas1ble to put this element; and 2) if more than one position is available, in what ways do their properties vary so that a reasoned decision can be made as to which one is best in this case.

When the possible positions in an utterance are marked with unique names, it becomes possible to associate grammatical information with them to use in situations such as 1bove. IIAost of this inform1tion will prob1bly reside directly in the relev1nl composers, but some will be used by functions which medi1le the insertion of an object into a slot.

The function of such mediation is to relieve the composers of the need to know low level syntactic informatioro. The verb group is a prime example. Because of the intricacy of its syntax, it witt be convenient to have only one slot, VG, in a clause or verb phrase plan, and let 1 function associated with VG manage 1 full verb group plan below it. The function determines what sub-slot should be filled (perhaps even changing the actual configuration of the slots) 1nd adjusts the features of the group if necessary. This w1y, the bulk of the composers no longer need to know 1bout del1ils such as: "if you add a modal verb ("would") to 1 verb croup, you h1ve to add a marker to the main verb to inhibit the l1ter morpholoaical expression of tense".

Plans are associated with grammatical units, with possibly 1 sep1r1le pl1n for each set of grammatical features lh1l 1 unit might h1ve, refleclin& the different slots lh1l may be present in each CISe. By knowin& the features of a unit, 1 composer will know euctly what slots to expect it to have. The next section h1s eumples of how plans are used.

Translalins a Message

Most of the work in the first phase is done by org1niZIIion11 composers associated with the intentional fe~lures on the messages. Each such composer will include code which understands the possible annotations that typically 1re mentioned with such intentions, and which will govern their insertion into 1 pl1n 1t the proper time. Consider the eumple message given e1rlier and repealed here.

mesSige-1 fe1lures (prediction) proposition <status-of-person> !type <busy> lot <Winston> hedae <70" ch1nce> time-predicted < 12:00-17:00>

Here, the org1nizing composer will be associated with the feature "prediction". Typically, one element of the message will be most important and is translated first. The others will probably refer to it 1nd may need to be realized iMide the plan that it wiS lransl1led into. In this elSe, the p·rime element is the one annotated "proposition", an object of the sort "status of a person". Pl1n selection is done by the descriptive composer for this sort and is suided by further characteristics of the Clbjecl . The lexicon will record lh1l the type properly <busy> must be realized as a predicate 1djective. This leads to the following, parli1lly filled in pl1n.

node-1 fe1tures (clause major copular pred-adj) slots !pre-sentential-modifiers <> !subject <Winston> lvg BE fpred-adj "busy"

lcomplement <> lpost-sententill-modifiers <>

The rest of the message is transferred by the prediction composer chunk by chunk. Predictions 1re of future events, so ·will· is added to the verb group; the "hedge", <701 ch1nce> will be re1lized as 1n 1dverb, say, "probably", 1nd so it is ldded to the adverb slot in the verb group; and "time-predicted" is I time modifier to the cl1use, making it part of the post-sententi~l­ modifiers. With the entire me:;uge tr1nsfered, the pl1n looks hke this.

node-! features (cl1use m1jor copul1r pred-ldj) slots lpre-sententill-modifiers <> !subject <Winston> Iva node-2 futures (verb-group future modified) slots lmod1l "will" lpre-vb-ldv "prob1bly" lmvb BE lpred-adj "busy" !complement <> !post-sentential-modifiers < 12:00-1 7 :00>

Annotating Composers . . . To properly fit the pointers/objects 1n · mesuce 1nto · p~1n, the organizing composer must know what sort of grammahcal object they will be. This e~n not always be directly deduce~ fro~ the nature of the annotation on the mesuce. For example, 1n thiS sentence the "hedge" might well have been an object correspondin& to the phrase "unless somethin& comes up", which is a bound cl1use and would have to go 11 the end of the post­ sentential-modifiers.

The necesury information can be m1inhined by uch descriptive composer as a permanent annotation in t~ form ~f .a fe1ture list which describes what sort of crammat1cal Unit 1t constructs. To check this for an object in the message, an orc1nizing composer will look up the object in the lexicon ~o see what composer will describe it, and then reid the 1nnot1hon on that composer. In this case, the features mi&ht be ·(adverb event­ modifer)·, versus "(clause bound conditional)".

An Example of a Composer

Each of the objects in a message will eventually be described by a general descriptive composer which is keyed to t~ sort .of object that they 1re, plus additional information assoc11ted w1th the names in each object . As there are "sorts" of objects in a progr~m, there will be descriptive composers in the lexicon . . ~me sorts might be reasons, actions, people, 1ppointments, actiVIties, times of the d1y, 1nd so on. This design m1kes no restrictions on the possible composers; only th·l they should reflect what properties objects have in common and common ways that they can be described. Individual objects will usually only supply parameters to their composers, but some may be idios~ncrati.c and instead point to complete words or phrases or to spec11lly ta~lored composing procedures.

Actions

~lions are things that something does: "making an appointment", "evaluating a procedure", "defendin& a chess piece", etc. The function of "the action composer" is to set up the syntactic environment thai all actions have in common. In this analysis, actions are realized as verb phrases, with the internal name of the action indicating in the lexicon what the verb should be, and the objects asocialed with the name (if any) becoming its syntactic objects in the phrase. .

An example of an action in a likely intern1l representahon might be the following (in a programmer's assistant)

<action-427> action set-v1lue-of variable switch! ;1 n1me from 1 progr~m set-to nil

We might see this in an utter1nce like "it is necessary to set the value of switch! to nil before leaving this routine".

The first thing any composer does when it begins to run is find out where it is. In the above utterance, the location would be in the second phase, with the ~etion-object in the "complement" slot. Other slots where 1ctions could occur 1re "subject", and as the main-proposition in 1n 1nswer to 1 question. With the situation known, the composer might disp1lch to a p1rticul1r block of code which handles th1t situation, but in this case, the only difference is that complements must hive infinitival verbs. This is done by adding a future tl) the verb group 11. the end of the operation.

All actions yield verb groups, so the composer begins by replacing the pointer in the complement slot with 1 synt1ctic node for a verb group. It must then get a plan for this verb group, 1nd fill in the 1ppropri1te slots of that plan with the subcomponents of the object. Then it is finished 1nd the node 1nd pl1n are in turn refined by their own composers IS the second ph1se controler walks 1l0n1 the plan to them.

The information on wh1l pl1n to use and wh1t tr~nsfers to m1ke is p1rt of 1n object's specific lexic1l entry. To aet 11 it, the action composer must know what property of the object describes its structure (of course, the proarammer must see to it that such a property exists) and then follow it into the lexicon for a plan and 1 mapping of properties on the object to slots in the plan. For the example action this entry is given below.

set-value-of plan (v& SET ;a pointer into a morphologic1l lexicon object I (noun group prep "to" object2 <> m1pping del "the" held "v1lue" of-group (prep "of" np <> )) ((variable object l.of-croup.np) (set-to object2))

Note that this plan is not so much 1 grammatical skeleton IS a varlablized English phrase. With such inform1tion in the leKicon, the 1clion composer can employ slrtightforward pattern substitution functions to finish its job.

The Syntactic Environment

The primary operation in the second phase is. to describe the chunks of the message that have been embedded in the pl1n. This is done by walking the plan with a simple controler to run the composer for each object as it is encountered; print out the words given literally, and ignore any empty slots. Since 1 pl1n is esentially a constituent structure tree, walking it topdown, from left to right results in words being uncovered (and "spoken") in the same order as would occur if a human were making the utterance. AI the same lime, parts of the plan further on, which have not yet been walked, retain their unexp1nded char~eter, presenting those characteristics which may be important to know in decisions involving the whole utterante while hidin& those det1ils that are unimportant.

This points out that plans can be viewed as providing 1n environment lhat composers can 1sk questions of. Some questions are easy because their answers are represented directly ("whit is the transitivity of the main verb!") and others are much h1rder bec1use they must be computed ("are there 1ny intervening noun croups between me and that previous occurance of me way b1ck there?" - needed lor reflexive pronouns). However, in environments with different structures than that of plans, answering such question could become simple.

Such additional environments could be created as a side­ effect of the cOn$lruction and walking of a plan. Because the walking follows the temporal order of the generation of an utterance, it readily marks what the audience can be presumed to know at any given point.

1 have not yet done any work on determining just what such parallel environments should look like. That will come as grammars are written lor this design. However, it is clear that they must encode some very subtle aspects of what the audience knows, and should describe the syntactic situation in such a way as to guide pronominalization and "deletion" of later structures.

Pronominalization

Pronominalization is only one instance of a very general phenomena in language which "encourages" the speaker ~o abbreviate their utterance wherever possible. Languages contam conventional structures which themselves mark the relationships that are going on, so that the actual words need not be physically present (e.g. equi-np-deletion: "John is ready to please" - the subject · John" does not need !o be repeated with each verb).

Often conventions whkh allow potential descriptions to be omitted take into account semantic information that the audience is assumed to share. For example consider the sentence "White's knight can take a pawn". What is interesting here is that there is no need to say " .·. take a black pawn". Presumably, it is what ~e know about the semantics of "take" in chess games - that 1ts subject and object will be pieces of opposite colors - which has taken effect here.

Every composer describing an object will have to examine the "discourse" environment to see if it would be most appropriate to use a pro·noun or otherwise cut down on the normal amount of description.

Quantifier Scope

.

Certain relationships become apparent durmg the second phase that can not be seen at other limes. C"lc very important one is quantifier scope. Certain accidental misreadings can be generated as the plan is walked, precisely because the . individual composers work independently of each other. Th1s can be corrected by introducing "global" syntactic processes associated with the grammatical units, which can "monitor" the activities of the composers and insert corrective patches when necesury.

Situations in the grammar where such accidents are possible must be identified and routines designed for them. Then, when fny synl actic unit is entered by the second phase controler, a check will first be make lor any monitoring routines, which are then run b&lore going on. ·

One situation that would b& checked lor would be that of a verb followed by a conjoined object. The monitor would be ~ssociated with the verb group and go to work if it saw that a conjoined noun phrase followed. The problem is that the struc;_ture "(are (not A) and (8))" is usually misinterpreted by peopl& as (are not (A and 8))" with the scope of "not" inadvertently taking in B as well. The monitor must watch as the first conjunct is described, and if it begins with "not", it should patch the construclio~ by copying the "are" alter the "and" - "(are not A and ~re ~) . A repetoire of such monitors and patches w1ll be requ~red 1n the grammar.

Present Directions

The design that I have described here (see <I> lor greater detail) represents some contentions about what a very fluent "generation grammar" for English must deal with, and what control and data structures will be convenient to write that grammar ~~­ At this writing (June 1975), ~ LISP implementation of the dtts1gn IS well under way, and it is anticipated that part of a grammar ca~ be completed before the end of the summer . However, unlll a working grammar exists, and the generator has bee~ mterlace_d with some primary program, many of the things descnbed 1n t~1s paper remain contentions which I believe to be _ tr~, but w~1ch may turn out to be without substance, necess1tahng poss1bly drastic changes in the design. In particular, the program has made these assumptions.

1. That the candidate primary programs will have a sufficiently rich organizing structure that very general composers can be written, cutting down on the bulk of the lexicon, and that associating objects with composers will be a straightforward thing to do.
2. That the messages constructed by a main program will naturally be translatable without editing. Some problems in a message could be patched by the grammar, but others, like too much necessary embedding, could not be fixed without going directly back to the program and "explaining" that some material must be cut, letting the main program decide what is to be l&ft out.
3. The proposed grammar depends on having good information at all times, otherwis&, the composers may thrash and will continually lind themselves in unanticipated situations. This information will be encoded in a system of features and possible plans and slots. It must be possible to devise an adequate grammatical system, or else the resulting inefliciences may swamp the generator.
4. 4. The grammar will organize linguistic constructions in terms of the r&asons why speakers use them. However, the r&asons for using the bulk of the constructions in English are poorly understood. II is hoped that a combination of the fact that programs are presently rather simple mind&d compared to humans, and that initial hunches about the use of those gr ammaticat constructions which are called for will be close to correct, will make it possible to write a grammar without unmanagable aaps in it.

Some people in A.l . have said that languaae generation is "easy". Basically I aaree with them. I think that the structure of language is well enough understood that we should be able to have our programs spuk in very fluent English without &xcessive research. As in many things, however, to make 1 system "easy" to work with seems to require first introducing a rather complicated structuring framework in order to separate out its component influences into managable chunks, and let the messy interlacing details work themselves out, away from our view.