Generation in a Natural Language Interface

1. Some reatures or the ayatem

The PlffiED (PHRasal English Diction) generator is designed to produce natural language output from a conceptual knowledge structure. The generator uses a database of linguistic information shared with the language analyzer PHRAN (PHRasal ANalyser). While PHRED was originally conceived as an English r;enerator, currently operative versions of both PHRAN and PHRED are designed for use with multiple languages.

Natural language generation is sometimes viewed as the process of planning utterances to achieve a goal (Appelt, 1982). A division in this multi-stage process can be made between the task domain and the linguistic domain , or between the system level and the interface level. PHRED operates at the interface level. User input to the UNIX consultant system (UC) is first analyzed by PHRAN, produc­ ing a conceptual knowledge structure which motivates the system's response. This response, in the form of a conceptual structure, is then converted into natural language output by PHRED:

User: How do I delete a file!

• UC: Typlns ' rm filename ' deletes the file filename from the current directory.

User: Como se borra un archivo!

• UC: Para borrar el archlvo de nombre filename del eapaclo de trabaJo, ae eacrlbe' rm filename'.

User: How do I delete all the files from a directory!

• UC: Typlns ' rm · ' wlli remove all fllea wlt hln the current directory from the current directory.

Typlns ' rm -r dlrectoryname ' wm cause all files and dlrectorlea recuralvely lnr.lde or dlrectoryname to be deleted from dlrectoryname and removea the directory dlrectoryname from the worklns directory.

t This research wu sponsored io pan by the Olice of Nanl R .. euch nder contract NOOOU-!IG-C-<1732 ud the Nation>.l Scieoce Foudatioa uder cuntiST-8007045.

%. The common databaae

The database shaJ"ed by the phrasal analyzer (PHRAN) and phrasal generator (PHRED) consists of pattern-concept pairs, where the pattern contains the linguistic structure of a phrase and the con­ cept its internal representation. The use of the PC pair as a unit of linguistic knowledge distinguishes PHRED from some other language production mechanisms (see McDonald, I980) in which grammatical information and conceptual information are separated. Associated with each PC pair is a list of properties used for indexing the pair in the database and for adding knowledge to the system, as well as information about forms of agreement among constituents.

Patterns are lists of constituents, where each constituent in a pattern is generally described either as a pattern of speech (p-o-s) or as a member of a descriptive class (e.g. person, physical object). Pat­ terns may also be formed by conjunction and disjunction of other patterns and may contain specifications of constraints; for example " (and (root delete) (tense present) (voice active) (fonn infinitive))" is a pattern which would generate the infinitive verb " to delete". For a detailed description of PHRAN-PHRED patterns see (Wilensky Ill Arens, 1980).

The concepts currently used in the database are adaptations of conceptual dependency representations (see Schank, I975) with numerous predicates, primitives, and other V3l'iations added. The concepts are not intended to represent an irreducible set of primitives or a restrictive syntax, but merely to provide a functional representa­ tion compatible with the UC knowledge base.

A simple example of a pattern-concept pair is given below:

I (and (person) (with case subjective)) (and (root remove) (with person (matches I)) (with number (matches I))) (and (p-o-s noun-phrase) (with case objective)) ([(from (container)) (object (opt-val 2))1) I concept '(state-change (actor !actor) p-o-s 'sentence tense (value 2 tense) actor (value 3) (state-name location) (from (inside-of (object !object))) (to (not (inside-of (object !object))))

This PC pair contains knowledge about one form of the action "remove" which can be used by the interface with the UNIX Consul­ tant . The same pattern conesponds to both "John removed the eggs from the refrigerator" and " I removed the file roo from my direc­ tory." The pattern bas four constituents. In the first, "(and (person) (with case subjective))", the constraint "(with case subjective)" indi­ cates that if the case of the subject can be detennined, it must be nominative. This is a looser constraint than "(case subjective)", which w~uld specify that the subject muBt have the nominative-case property. The constraints "(with person (matches I))" and "(with number (matches 1))" in the next constituent specify that the verb, which must have the root "remove", agrees in person and number with the subject.

3. Implementation of the cenerator

The process of generation in PHRED can be divided into three phases: (I) fetching, (2) instantiation, and (3) interpretation. These three processes will be discussed in this section, with references to the "remove" pattern and to parts of the UC output from section I. As the generation of the sample output requires complete processing of many patterns, only certain aspects of the examples can be discussed.

3.1. Fetchlnc

While PHRAN and PHRED use the same knowledge struc­ tures, the indexing mecbanisms of the analyzer and generator are naturally different. In PlffiAN a pattern of speech is recognized and suggests a possible PC pair; in PlffiED the same pair must be sug­ gested by attributes of a concept or by properties of the conceptual structure.

PHRED's basic indexing mechanism uses multiple-key hashing, where primary and secondary keys are specified wit.hin the database. Keys may be arbitrary collections of properties and attributes; thus the same indexing scheme used for the most complex patterns is used for simple words. In the case of the "remove" entry above, the PC pair is indexed according to a combination of the "state-change" and the attributes "location", "inside-of" , and "not inside-of" . The indexing mechanism ignores variables (e.g. "!actor" ). A simpler pat­ tern, such as the word "the", may be indexed by the properties "(p­ o-s article)" and "(ref def)" , indicating a definite article.

For certain groups of patterns the choice of l!:eys is essential to the speed of fetching. In Spanish, there are numerous forms of each verb and one must be selected which agrees with its subject, some­ times with its object and indirect object as well. In other cases the choice of keys is non-essential. A default mechanism is provided where keys are not specified.

Fetching can take up most of the t ime used by the generator: in PHRED, running in compiled Franz Lisp on a VAX 11/780, most fetches take about 0.1 seconds of CPU time. As a typical sentence may require 20-30 fetches, most of the time used by the generator is in the fetching process.

3.%. Instantiation

The fetching mechanism returns a PC pair from a stream each time one is requested. Thus indexing on a secondary key may be delayed until an attempt is made to instantiate the PC pair(s) fetched on a primary key.

Instantiation consists of adding appropriate constraints to a selected pattern and simultaneously verifying that the pattern is appropriate tor the given concept. PHRED differs from generators which use a discrimination net as an indexing tool (see Goldman, 1975) in that it combines semantic tests with the addition of con­ straints. This method is efficient, given that the fetching mechanism generally yields few patterns tor instantiation.

The "remove" pattern in its instantiated form might be:

(and (person concept 'userl) (with case subjective)) (and (root remove) (tense past) (with person (matches 1)) (with number (matches 1))) (and (p-o-s noun-phrase ·concept '&lei) (with case objective)) (!(from (container concept 'directory!)) (object (opt-val 2))1)

The specification of the tokens to be represented by the indivi­ du a.l constituents and the tense of the verb have been added to the PC pair. If these additions lead immediately to a contradiction - for example, if the token "userl" does not represent a person - the instantiation will fail.

The tense property in the second constituent h38 b~en inherited from the tense property or the entire pattern. A sentence in the past tense implies a sentence with verbs in the past tense. The process of inheritance or attributes from the overall patt-ern to the individual constituents may be complex: A property may be inherited by more tban one constituent, as in the ca.~e or compound verb phrases, and there may be more complicated interactions between tbe attributes, as where a list of adjectives must be generated to describe a.n object.

Each fetch may return patterns which produce the desired p-o-s directly, or rewrite rules, which correspond to transformations or ot.her patterns. The remove pattern will produce a sentence directly, but must be rewritten to produce a.n infinitive phrase. Gen­ erally, rewrites are tried during instantiation only after failure of the direct patterns; however, certain rewrites may be fetched immedi­ ately : If the concept indicates negation , a negating transformation will be applied to the pattern corresponding to the negated concept.

3.3. Interpretation

After a given pattern has been instantiated, the pattern can be converted into verbal output. The process of interpreting a given constituent may (1) succeed in producing a phrase as output, (2) result in a recursive application of the fetch-instantiate-interpret sequence on the given constituent , or (3) fail because of the inability of the generator to produce a specified pattern of speech. The first case occurs when the constituent represents a word or list of words for output, such as "the big apple". The second occurs if the consti­ tuent contains a more complex pattern, for example, "(and (root remove) (tense past))". The third case, where no output produces the desired pattern of speech subject to the constraints given by the uninterpreted pattern, is difficult, because the system must back up to attempt an alternate pattern without destroying too much or the work it has done. Usually this results in backing up to the level where tbe failed pattern was fetched, getting another pattern from tbe stream, and attempting instantiation or the new pattern. Most often this new pattern will be a rewrite rule, and most of tbe failed pattern will be used in tbe instantiation of tbe rewritten pattern . A simple case or this is where tbe generator fails to produce a pattern or speech for tbe subject of a sentence and instead generates a pas­ sive sentence.

Tbe agreement of constituents within a pattern iti assured dur­ ing tbe interpretation phase. Constraints such as "(with person (matches 1))" are converted into properties-e.g. "(person third)" . In English there are few structures where agreement passes from right to left-such as tbe number of a determiner wbicb matches a succeed­ ing noun- but in other languages there are many examples where agreement within a pattern is much more complex. In all cases PHRED can ensure proper agreement if some order or interpreting tbe constituents allows tbe correct application of constraints. In English this means that nouns within noun phrases are interpreted before their attached determiners; in more inftected languages this means that verbs must generally be produced last.

Anapbora are specially bandied during interpretation . In the case of anaphoric constituents the generator applies a set of heuristics wbicb may (1) remove tbe conetituent entirely if it is not nece88ary to tbe utterance, (2) pronominalize , or (3) regenerate tbe entire con­ stituent. When used by UC, PHRED does not pronominalize unless specifically instructed.

4. Requirement. of a senerator l.n a friendly l.nterfaee

PHRED bas been designed to meet tbe following requirements or a generator in a natural language interface:

1. Speak the u·er'· lantJUase- This refers not only to the dis­ tinction between English and Spanish users, for example, but also to adaptability to tbe specifi( vocabulary or the user. A novice user will find expressions like "disk quota" and "read protection" difficult to fathom. Such phrases in tbe database are marked as being more technical.
2. Clarity and/or paraphra·e on demand- Where the user does not understand a particular phrase or (Onstruct, tbe sys­ tem must be capable of providing an explanation. If tbe expla.­ nation can be supplied by a linguisti( paraphrase, tbe generator provides it.
3. Be compatible with the anal)'·er- PHRED was designed to draw from a database of patterns used by PHRAN. The importance of this compatibility extends beyond the simple efficiency of having tbe same database shared by both analyzer and generator: PHRED can make use or information added dynamically by PHRAN to tbe database, and any new patterns constructed by the analyzer can be indexed and used by the generator.
4. Be adaptable to the u·er'· knowledp- The UNIX consultant's model or tbe user can provide PHRED with instructions wbicb will guide word choice, proncminalization, and tbe degree of explicitness or the output. This is nece88ary to provide information comprehensible to tbe user and to avoid telling tbe user what be already knows.

5. Conelu·lon

PHRED represents a natural language generator rooted in a knowledge base of linguistic information shared with the PHRAN analyzer. Tbe database, consisting of pattern-concept pairs, is main­ tained dynamically by the analyzer and generator. PHRED is an effective, extensible, language-independent program, and combines with PHRAN to provide a natural language interface adaptable to tbe individual user.

Reference.

Appelt, D. 1982. Planning Natural Language Utterances to Sat.isfy Multiple Goals. SRI International: AI C-enter Techni­ cal Note 259.

Goldman, N. 1975. Conceptual Generation. In R. C. Schank, Conceptual Information ProceWBing. American Elsevier Publish­ ing Company, Inc., New York.

Hendrix, Gary G. 1977. The Lifer lv!anual: A Guide to Build­ ing Practical Natural Language Interfaces. SRI International: AI Center Technical Note 138.

McDonald, D. D. 1980. Language Production as l'l Process or Decision-making Under Constraints. Pb. D. dissertation, MIT.

Schank, R. C. 1975. Conceptual Information ProceBBing. American Elsevier Publishing Company, Inc., New York.

Wilensky, R., and Arens, Y. 1980. PI-IRAN-A Knowledge­ based Approach to Natural Language Analysis. University of California at Berkeley Electronics Research Laboratory Memorandum UCB/ERL MS0/34.

Wilensky, R. and Morgan, M. 1981. Languages. Berkeley Electronic Memorandum UCB/ERL/M81/67. One Analyzer for Three Rec,earcb Laboratory