Controlling a Language Generation Planner

1 Introduction

The process of natural language generation starts with the specification of the 'need to communicate,' the propositional goals for a target language text, and a pragmatic profile of the speech situation - knowledge about the speaker, the hearer, the style of communication, etc. (cf. [DiMarco and Hirst, 1988, Hovy, 1987, Hovy, 1988b, McDonald, 1985]). The generator then has to perform the following tasks:

1. Content Delimitation. The system must select which of the propositions related to the propositional goals should be overtly realized, and which should be left for the human hearer/reader to infer (e.g., [McKeown, 1985]).
2. Text Structuring. The system must determine the order of propositions, the boundaries of sentences in the target language text and the nature of discourse connectives among the elements of the target text ( cf. [Hovy, 1988a, Mann and Thompson, 1987]).
3. Lexical Selection. The system must select open-class lexical units to be used in the target language text (e.g., [Goldman, 1975, Granville, 1983, Jacobs, 1985, Kit­ tredge eta/., 1988, Nirenburg eta/., 1988a, Ward, 1988, Sondheimer et a/., 1988]).
4. Syntactic Selection. The system must select syntactic structures for the target language clauses (e.g., [Mann, 1983, McDonald, 1983, Meteer et a/., 1987]) and per­ form closed-class lexical selection according to syntac­ tic structure decisions (e.g., [Pustejovsky and Niren­ burg, 1987]).

·This work was partially funded by an ffiM Japan I Tokyo Research Laboratory research contract.

Victor Lesser

Computer and Information Sciences University of Massachusetts Amherst, MA 01003

Eric Nyberg

Center for Machine Translation Carnegie Mellon University Pittsburgh, PA 15213

1. Coreference Treatment. The system must introduce anaphora, deixis and ellipsis phenomena when appro­ priate (e.g., [Derr and McKeown, 1984, Sondheimer et a/., 1988, Werner and Nirenburg, 1988]).
2. Constituent Ordering. The system must establish the order of syntactic constituents in a sentence (e.g., [Hovy, 1988a, Kenschaft, 1988]).
3. Realization. The system must map from syntactic rep­ resentations with lexical insertions into surface strings (e.g., [Tomita and Nyberg, 1988]).

Our natural language generator, DIOGENES [Nirenburg et a/., 1988a], is designed to account for all of the above tasks but the first one. The design and development of the content delimitation stage received lower priority due to the intended initial application of DIOGENES - machine translation. The input to a generator in a knowledge-based MT system is the result of the analysis of a source language text, and takes the form of a set of statements in an intermediate represen­ tation language, or interlingua. The interlingua text (ll...T) already contains the results of the content delimitation stage of generation.

Tasks 2 through 7 above are best interpreted as planning tasks. The treatment of generation as planning was first in­ vestigated by Appelt [Appelt, 1985], whose generation sys­ tem was an application of NOAH-style planning [Sacerdoti, 19771 Hovy [Hovy, 1988b] argues that while content de­ limitation is best performed in such a manner, a different, data-driven 'restrictive' planner is best suited for the rest of the planning tasks. The reason for this is that Tasks 2 through 6 perform selection out of a set of alternative ex­ pressive means, based on dynamically determined heuristics that depend on the state of a number of different planning processes. The search space is complex and dynamic. The search is non-deterministic, since some early decisions have to be re-evaluated based on additional knowledge and con­ straints obtained as a result of later processing. The knowl­ edge used for search breaks down into several areas specific to the various input meanings and means of expression (see Table 1).

A most promising method for performing this type of complex task is the use of a flexible, data-driven, agenda­ controlled environment that has come to be associated with the blackboard style of control (cf., e.g., [Englemore and Morgan, 1988]). A version of such a blackboard-type ar­ chitecture was designed for the DIOGENES planner. This ar­ chitecture is very general and is expected to accommodate future changes in the volume and type of knowledge. This paper describes the DIOGENES planner for tasks 2 through 6 above.

The purpose of the planner is to map the set of input meanings specified in an ILT into a set of target language expressive means, including:

• target language lexical units
• target language syntactic constructions
• the ordering of words and syntactic constructions
• text architectonics - the ordering of clauses and the boundaries of sentences

A typical ILT contains a wide variety of meanings (cf. [Nirenburg et al., 1988a] or [Nirenburg and Carbonell, 1987]), each of which has a set of associated expressive means. The types of input meaning and their typical means of target language realization are illustrated in Table 1.

In the case where the ILT is incomplete, the DIOGENES planner utilizes default strategies. In the absence of a more specific strategy, it will plan a target language clause for every ILT proposition head (typically, a domain event in­ stance) and a target language noun phrase for each domain object instance (role) in the ILT.

Section 2 of this paper presents the architecture of the DIOGENES planner and its components. In Section 3 the knowledge sources used in DIOGENES are described. Section 4 contains an example of a typical control problem in the planner. In Section 5 we report on the status of DIOGENES and directions of future work, and compare DIOGENES to some other NLG planners.

2 The Architecture

The DIOGENES planner architecture is illustrated in Figure 1. The system components include a set of knowledge sources, organized in clusters according to the type of input mean­ ings and expressive means they handle, a set of blackboard spaces, an agenda with its scheduler, and a set of background knowledge repositories.

2.1 The Input and the Output

The input to the system is represented as a semantic net­ work using the FRAMEKIT knowledge representation system [Nyberg, 1988]. It consists of a set of ILT clauses, each of which contains both a proposition with its corresponding set of case roles, and a set of non-propositional meanings, such as those of speech act, focus and modality. The most impor­ tant links among propositions include causal and temporal ones, while relations among ILT clauses include discourse cohesion and time of speech act

Figure 2 presents a sample input in graphic form (see sample ILl's in [Nirenburg et al., 1988al). 1

1 From the standpoint of expressive power this network is com­ parable to the one used by the GOSSIP system [Kittredge et al., 1988]; There are, however, a number of important differences­ for instance, the �~SIP network does not include discourse cohe­ sion markers, or, being a computational embodiment of the 'Mean­ ing- Text' model [Menuk, 1974], does not use case role labels, numbering them instead

The output of the DIOGENES planner is an ordered set of LFG-like functional structures of target language utterances, with lexical items inserted at the terminal level.

2.2 The Lexicon

The lexicon for natural language generation contains map­ pings from single units of meaning representation into tar­ get language open-class lexical items. The meanings are formulated using an independently constructed model of the domain underlying the texts to be generated. The problems ll(ld tasks associated with acquiring a domain model (called the concept lexicon in DIOGENES ) are described elsewhere [Nirenburg et al., 1988bl. For a detailed discussion of the structure of the lexicon in DIOGENES see [Nirenburg and Nirenburg 19881

3 Knowledge Sources

DIOGENES planning tasks are performed by its knowledge sources (KSs). In this section we describe the current in­ ventory of KSs and illustrate the process flow in the mo­ GENES planner. In the following description, the KSs are grouped according to the type of processing they perform. The KSs inside a group tend to be more tightly coupled by the control strategy than those belonging to different groups. However, results posted by KS instances (KSis) from other groups can also influence the decisions made by a KS, as illustrated below.

3.1 Lexical Selection Knowledge Sources

The task of selecting open-class lexical items (basically, nouns, verbs, adjectives and adverbs) is performed in mo­ GENES by a set of three knowledge sources - GL-Search, Collocationally-Constrain, and Select-Best - and is influ­ enced by the coreference knowledge sources (see below). The lexical selection process in DIOGENES has been de­ scribed in detail elsewhere (e.g., [Nirenburg and Nirenburg 1988]). Briefly, there are two rounds of GL-Search in­ stantiation. First, a GL-Search KSI is fired for each of the proposition and role heads and when their lexicalization is determined, another round of GL-Search instantiations is fired, if needed, to lexicalize modifiers. The Collocationally­ Constrain KSs are fired to ensure contextual collocational compatibility among the lexical selections. Select-Best uses a s~tic proximity metric between an input meaning and each of Its potential realizations 2 to select the best match.

3.2 Coreference Knowledge Sources

The knowledge sources in this group are the Anaphora-KS an~ the Definite-Description-KS. They are triggered by the existence of coreference links between roles in the input ILT, and a set of coreference heuristic rules that take into account the lexical selections made for other instances of the coreferential item. If the constraints on instantiation of the Anaphor~-KS hold, the instance will generate the pro­ noun appropnate for referencing a previously generated noun phrase. For a description of this algorithm in DIOGENES see [Werner and Nirenburg, 19881 If the constraints on instanti­ ation of the Definite-Description-KS hold, the instance will in turn trigger an instance of GL-Search, with the search algorithm modified to create a definite description (i.e., the lexical unit used in the previous reference to the concept will not be included in the candidate list). See [Sondheimer et al., 1988] for a discussion of lexical selection for definite descriptions. The coreference links among propositions and among ILT clauses are treated by KSs from the text structure group.

:vntese are stored in the candidate realization list already filtered through collocational constraints.

Table 1: Meanings and Their Realizations.

3.3 The Text Structure Knowledge Source

The Text-Structure-KS determines the ways in which ILT clauses will be distributed among target language sentences. Its instances are triggered for each ILT clause in the input, and appear on the agenda at the same time as those for the GL-Search KS from the lexical selection group. The knowledge that it uses includes discourse cohesion and tem­ poral links among the input ILT clauses. In the absence of this knowledge, the default strategy is to produce a target language sentence for every ILT clause and to retain the order in which the ILT clauses appear in the input (this is recorded in the time slot in the speech-act subframe of the ILT clause frame). The output of this KS is the skeleton output structure for the entire DIOGENES planner. This struc­ ture will then be filled in by the rest of the KSs. Since target language conjunctions and lexical clues for discourse coh~ion (e.g., 'therefore', 'moreover') are among the ex­ pressive means used by this KS, it can trigger instantiation of a Closed-Class lexical selection KSI (see 3.4 below).

. ~is KS als? makes_ decisions to treat coreference by el­ lipsis or by usmg relative clauses. For example, the input

(open Johnl bookl) (read Johnl bookl (aspect.phase =begin))

would be generated as 'John opened a book and started to read' using the ellipsis strategy, and as 'John started to read the book he had opened' using the relative clause strategy.

3.4 Syntactic Selection Knowledge Sources

There are two main syntactic selection knowledge sources in DIOGENES -Build-Clause and Build-NP, responsible for pro­ ducing syntactic structures for target language clauses and noun_ phrases, respectively. The tasks performed by these ~~s mclude translating semantic relations among ILT propo­ Sitions and roles (e.g., agent, theme, goal) into appropriate target language grammatical relations (e.g., subject, object, adjunct). During this process, instances of two auxiliary KSs are triggered- Closed-Class Lexical Selection KSis to select closed-class lexical items, such as prepositions or determin­ ers (see !Pustejovsky and Nirenburg, 1987] for a discussion of closed-class lexical selection), and Feature KSis to de­ termine the syntactic features (e.g., tense, number) of the output constituents. Build-Clause uses some of the results of the Text Structure KS, e.g., information about whether the current clause has to be generated as a part of a conjoined construction or as a relative clause.

3.5 Constituent Ordering Knowledge Sources

The Ordering KS processes constituents in the output struc­ ture and stipulates their left-to-right ordering in the output string. At present, the Ordering KS in DIOGENES orders only adjective modifiers of a noun phrase head (see [Kenschaft, 1988] for details). This module will produce, under default conditions, a phrase like 'big black wooden house' and not, say, 'wooden big black house.' The latter will be produced if the focus.given slot in the II...'r pointed to the represen­ tation for 'big black house' and the focus.new slot, to the representation of 'wooden.'

3.6 Summary and an Illustration

Table 2 illustrates the nature of the DIOGENES knowledge sources. Each KS is shown along with its group, the black­ board events that trigger its instantiation, its inputs and outputs, and the knowledge it uses. This includes static knowledge, such as the lexicons and grammars, and dy­ namic knowledge, such as the results posted by other KSs on the blackboard.

The task of managing large amounts of knowledge sources has several characteristics with serious implications for con­ trol:

1. The KSis whose results will become a part of the out­ put can be only partially determined a priori based on general ex~tations.
2. Although a large number of KSis can accumulate on the agenda during the planning process, only a small

number will actually have to execute in order for an output to be produced. ·

1. Since the set of KSis on the agenda is expected to be large, it is necessary to to a) further limit the search space and b) speed up search by enhancing efficiency through the introduction of extra control knowledge.

In order to enhance cooperation among the KSis and ad­ dress these characteristics of the planning process, we intro­ duce the following control strategies:

• Obviation. Since many more KSs may be instantiated than are actually required to produce a solution, a con­ trol strategy that involves obviation becomes a natural choice. Whenever a particular KSI becomes superflu­ ous because of a particular control decision (as illus­ trated in Figure 4 below), that KSI may be deactivated on the agenda, so that unnecessary processing may be avoided. Since the obviated KSI is merely deactivated and not removed from the agenda, it need not be re­ instantiated if the obviating control decision is retracted later; the obviated KSI can be re-activated simply by re-ftagging its status as active. Since obviation is trig­ gered by a contextual situation, its treatment has to be opportunistic.
• A partial ordering on KSI execution. Text-Structure KSis receive first priority, followed by coreference KSis with Priority 2. The lexical selection KSis for proposition and role heads have Priority 3, as well as the syntactic KSis (Build-Clause and Build-NP). The lexical selection KSis for modifiers and the Feature KSis from the Syntactic group are assigned Priority 4. Finally, the Ordering KSis receive the lowest priority (5).

Figure 3 shows an intermediate state of the system during processing of the input shown in Figure 2. Processing prior to the moment depicted in the figure has completed lexical selection of both the proposition heads and the first four role heads. The results were posted on the Lexical Space and the corresponding KSis were removed from the agenda (obvi­ ated). These events triggered the instantiation of a number of GL-Search KSs for lexical selection of modifiers in the above input components 3 · The system has also built clause and NP structures using two instances of Build-Clause and five instances of Build-NP. The results were posted on the Syntactic Space and the corresponding KSis were removed. Seven instances of the ordering KS were created (not shown in the figure). An instance of a Closed-Class lexical selec­ tion KS was triggered to select the preposition associated with the realization of the 'goal' case role.

Figure 3 also shows the results of a Text-Structure KSI - the two clauses will be combined into a single compound target language sentence. The coordination of clauses will be realized lexically, hence Closed-Class-LS2 is triggered to select the appropriate conjunction. The agent role of the second clause will be realized through ellipsis; as a result, Thble 2: DIOGENES Knowledge Sources. Legend: GL stands for Generation Lexicon; CL, for Concept Lexicon; LS, for Lexical Selection; SS, for Syntactic Selection; C, for Coreference, TS, for Text Structure; CO, for Constituent Ordering; CS for Candidate Set; FCS, for Filtered Candidate Set NP4 is deleted from the syntactic space, and the KSis GL­ Searc~ and Coreferencel are obviated as they are no longer needed.

3 Note that no GL--Search KSI is present for finding the modifiers of 'throw', 'ball' and 'dent.' This is because the lexical units that were selected completely cover the meanings of the corresponding ILT units.

4 A Sample Control Problem

Control problems arise in our non-sequential architecture when a solution proposed for one planning task influences the outcome of another. Since the architecture does not or­ der the application of KSis, two KSis that are triggered as part of the same subtask may create a conflict if the solu­ tion choice proposed by one precludes any solution choice by the second. A limited backtracking algorithm, coupled with a simple truth maintenance system, is used to recover from these types of control problems. We will illustrate this algorithm with a sample control problem involving the application of two Collocationally-Constrain KSis within a single role or proposition.

The initial KSis of the lexical selection group perform selection of proposition and role heads, which, when found, become the system's current choice. Next, for each un­ expressed property in the input, the same set of KSs are instantiated, in no particular order.

In general, this is the task of lexical realization in an hierarchically structured context Let us consider the exam­ ple of two case roles (A and B) within a proposition (C) (cf. Figure 4). Let us assume that the head for the propo­ sition has been selected, and that a lexical unit has already been selected for Role A. Suppose, next, the Collocationally­ Constrain KSI responsible for Role B finds that none of its candidates can collocate with the current selection on C. Al­ though this momentary failure is local to a single KSI, it has global consequences - since backtracking will require a different choice on C (to allow a choice of B), all KSis which assumed the initial choice on C must be re-processed. In other words, one can't assume that the new choice for C will collocate with the selection on A. This type of conflict is resolved in three steps:

1. Detection. A particular KSI reaches a local failure state (in our example, the current choice on C disallows an appropriate choice for B) and this event is posted on an appropriate blackboard space, creating a history of error detection and recovery.

1. Retraction. The decision must be made to retrigger, in the context of the currently posted history, the KSI whose previous choice must be retracted (in our exam­ ple, the current choice for C must be retracted). The 'guilty' KSI will then be forced to post its next best choice.
2. Truth Maintenance. Since retraction of a previous so­ lution choice may change the working knowledge of another KSI, any other solution choices that depended on the retracted data must be re-calculated (in our ex­ ample, the lexeme choice for A must be re-calculated once the next best choice for C has replaced the previ­ ous choice).

Our desire is to limit the occurrence of this type of back­ tracking. In the worst case, an exhaustive search of the space of lexical choices will be made before an acceptable com­ bination or proof of failure is established. Since we initiate backtracking only in extreme circumstances, i.e., when no choices are currently acceptable for a given unit of meaning, extra search is kept to a minimum. In addition, we place an upper resource bound on the number of conflict resolution attempts, after which an arbitrary selection is made with the possible cost of a loss in stylistic quality of the output.

The type of truth maintenance required by our system is simple compared to the complicated TMS components im­ plemented m some systems. Whenever a solution choice is made which, in turn, depends on another choice, the de­ pendent solution adds an IF-ERASED demon to the parent choice, such that retraction of the parent will cause the child to be re-calculated 4 · In terms of our previous example, se­ lecting a choice for A would cause an IF-ERASED demon to be placed on the currently active choice for C. This demon would cause the choice for A to be recalculated in the event that the original choice for C were retracted.

5 Status and Future Improvement

In this paper we have described an initial investigation into the organization of search for natural language generation planning, as implemented (using CommonLisp, the X Win­ dows system and the FRAMEKIT knowledge representation system) in the DIOOENES system (see [Nyberg et al., 1988] for the user's guide). In the next version of the DIOOENES planner we intend to include a more complex control model in the lexical selection phase, means of explicit reasoning about relationships among the tasks and their preconditions, and a more intelligent way of forcing a solution. Certain applications may require the planner to produce multiple so­ lutions instead of outputting the first satisficing choice. This functionality will lead to extra search time at all levels of the blackboard. Finally, we would like to investigate appropriate ways of introducing top-down constraints in our bottom-up search process. These constraints must be introduced not as imperatives, as in schema-based systems [McKeown, 1985] or hierarchical planners [Appelt, 1985], but rather provide additional heuristics for guiding search. This type of strategy has also been advocated by Hovy [Hovy, 1988c], though for different purposes.

'This is similar to the data dependency maintained in the AMORD system [deKleer et a/., 1978], which triggers a search through all data dependency links following the retraction of an assertion.

A speed-up of the planning process can be achieved by in­ troducing coarse-grain parallelism, whereby different knowl­ edge source classes are treated by different processors. In the current implementation the lexical selection and corefer­ entiality treatment processes are run in a distributed manner.

We also plan to enhance the expressive means of the planner by including prosodic phenomena (in written text, expressed through the use of italics, boldface, underlining, itemization, etc.) whenever stylistically appropriate.

Acknowledgements

Many thanks to Allan Heydon, Inna Nirenburg, Irene Niren­ burg, Victor Raskin, Bob Whitehair, and the current and former members of the DIOOENES project: Scott Huffman, Ed Kenschaft, Rita McCardell and Philip Werner.