Gertjan van Noord
& Günter Neumann
Alfa-informatica RUG, The Netherlands
Deutsches Forschungzentrum für Künstliche Intelligenz, Saarbrücken, Germany
In a natural language generation module, we often distinguish two components. On the one hand it needs to be decided what should be said. This task is delegated to a planning component. Such a component might produce an expression representing the content of the proposed utterance. On the basis of this representation the syntactic generation component produces the actual output sentence(s). Although the distinction between planning and syntactic generation is not uncontroversial, we will nonetheless assume such an architecture here, in order to explain some of the issues that arise in syntactic generation.
A (natural language) grammar is a formal device that defines a relation between (natural language) utterances and their corresponding meanings. In practice this usually means that a grammar defines a relation between strings and logical forms. During natural language understanding, the task is to arrive at a logical form that corresponds to the input string. Syntactic generation can be described as the problem to find the corresponding string for an input logical form.
We are thus making a distinction between the grammar which defines this relation, and the procedure that computes the relation on the basis of such a grammar. In the current state of the art unification-based (or more general: constraint-based) formalisms are used to express such grammars, e.g., Lexical Functional Grammar (LFG) [Bre82], Head-Driven Phrase-Structure Grammar (HPSG) [PS87] and constraint-based categorial frameworks (cf. [Usz86] and [ZKC87]).
Almost all modern linguistic theories assume that a natural language grammar not only describes the correct sentences of a language, but that such a grammar also describes the corresponding semantic structures of the grammatical sentences. Given that a grammar specifies the relation between phonology and semantics it seems obvious that the generator is supposed to use this specification. For example, Generalized Phrase Structure Grammars (GPSG) [GKPS85] provide a detailed description of the semantic interpretation of the sentences licensed by the grammar. Thus one might assume that a generator based on GPSG constructs a sentence for a given semantic structure, according to the semantic interpretation rules of GPSG. Alternatively, [Bus90] presents a generator, based on GPSG, which does not take as its input a logical form, but rather some kind of control expression which merely instructs the grammatical component which rules of the grammar to apply. Similarly, in the conception of [GP90], a generator is provided with some kind of deep structure which can be interpreted as a control expression instructing the grammar which rules to apply. These approaches to the generation problem clearly solve some of the problems encountered in generation---simply by pushing the problem into the conceptual component (i.e., the planning component). In this overview we restrict the attention to the more ambitious approach sketched above.
The success of the currently developed constraint-based
theories is
due to the fact that they are purely declarative. Hence, it is an
interesting objective---theoretically and practically---to use one
and the same grammar for natural language
understanding and
generation. In fact the potential for reversibility was a
primary motivation for the introduction of Martin Kay's
Functional Unification Grammar (FUG). In recent years
interest in such a reversible architecture has led to a number
of publications.
The different approaches towards the syntactic generation problem can be classified according to a number of dimensions. It is helpful to distinguish between
A generator proceeds from left to right if the elements of the right-hand-side of a rule are processed in a left-to-right order. This order is very common for parsing, but turns out to be unsuitable for generation. For example, [Shi88] presents an Earley-based generation algorithm that follows a left-to-right scheduling. It has been shown that such a strategy leads to a very inefficient behavior when applied for generation. The reason is that the important information that guides the generation process, namely the logical forms, is usually percolated in a different manner. Therefore, semantic-head-driven generation approaches have become popular, most notably the algorithm described in [SPvNM90,Van90,Van93], but see also [CRZ89,GH90,Ger91,Neu94]. Such approaches aim at an order of processing in which an element of the right-hand-side of a rule is only processed once its corresponding logical form has been determined.
As in parsing theory, generation techniques can be classified according to the way they construct the derivation trees. Bottom-up and top-down traversals have been proposed as well as mixed strategies. For example, bottom-up generation strategies are described in [Shi88,Van93], top-down approaches are described in [Wed88,DIP90], and mixed strategies are described in [SPvNM90,Ger91,Neu94].
As in parsing, bottom-up approaches solve some non-termination problems that are encountered in certain top-down procedures.
The above mentioned two dimensions characterize the way in which derivation trees are constructed. A particular choice of these parameters defines a non-deterministic generation scheme, giving rise to a search space that is to be investigated by an actual generation algorithm. Hence, generation algorithms can be further classified with respect to the search strategy they employ. For example, a generation algorithm might propose a depth-first backtrack strategy. Potentially more efficient algorithms might use a chart to represent successfully branches of the search space, optionally combined with a breadth-first search (see for example, [Ger91,CRZ89]). Moreover, there also exist chart-based agenda driven strategies which allow the modeling of preference-based best-first strategies (e.g., [Den94,Neu94]).
Syntactic generation is one of the most elaborated and investigated fields in the area of natural language generation. In particular, due to the growing research in the Computational Linguistics area, syntactic generation has now achieved a methodological status comparable to that of natural language parsing. However, there are still strong limitations which weakens their general applicability for arbitrary application systems. Probably the most basic problems are:
None of the syntactic generators process grammars whose size and status would go beyond that of a laboratory one. The newly proposed approaches in Computational Linguistics are in principle capable of processing declaratively specified grammars, and hence are potentially open to grammars which can be incrementally extented. However, as long as the grammars do not achieve a critical mass, the usability of the approaches for very large grammars is a speculation. The same is true for the status of the lexicons. Currently, generators only use small lexicons. Consequently most of the systems trivialize the problem of lexical choice as being a simple look-up method. However, if very large lexicons were to be used then the lexical choice problem would require more sophisticated strategies.
Of course, there exists some generators whose grammatical coverage is of interest, most notably those from the Systemic Linguistics camp (see section 4.1). However, these generation grammars have a less transparent declarative status, and hence are limited with respect to re-usability and adaptation to other systems.
All known syntactic generators have a limited degree of functionality. Although some approaches have been proposed for solving specific problems, such as generating ellipsis (e.g., [JW82]); generation of paraphrases (e.g., [MS88,Neu94]); generation of referential expressions [Dal90]; or incremental generation (e.g., [DK87]), there exists currently no theoretical and practical framework, which could serve as a platform for combining all these specific operational issues.
Taking these limitations as a basis, important key research problems specific to syntactic generation are:
These are needed for obtaining reasonable linguistic competence. As a prerequisite, grammatical knowledge must be specified declaratively in order to support the re-usability, not only for other systems, but also for integrating different specific generation performance methods.
The generation procedures sketched above all come up with a possible utterance for a given meaning representation. However, given that natural language is very ambiguous the chances are that this proposed utterance itself is ambiguous, and therefore might lead to undesired side-effects. Some preliminary techniques to prevent the production of ambiguous utterances are discussed in [NvN94,Neu94].
This will be important in order to obtain efficient but flexible systems. This would allow competence grammar to be used in those cases where prototypical constructions (i.e., the templates) are not appropriate or even available.