Incremental Generation by Incremental Parsing Masayuki Otsuka , Dept. of Philosophy, King's College London Matthew Purver , Dept. of Computer Science, King's College London Abstract: --------- The paper shows how an incremental generator can be constructed based on the incremental parsing framework described in Dynamic Syntax (Kempson, Meyer-Viol, Gabbay 2001), without adding a generator-specific vocabulary or intermediate levels of representation. The resulting generator is defined purely in terms of the parsing process, together with a notion of tree subsumption. A simple Prolog implementation is described, together with various possible improvements in efficiency. Introduction: ------------- Dynamic Syntax (DS) is a parsing-directed approach in which a decorated tree structure representing a semantic interpretation for a string is incrementally projected following the left-right sequence of the words. In DS, parseability of a string is seen as the successful incremental construction of a logical form (in a tree-structure format), using all the information given by the words in sequence, each being associated with a macro of actions for updating a partial tree. The system of DS parsing establishes mappings from an initial state to goal states by using computational actions and lexical actions defined (for some natural language) using the modal tree logic LOFT (Blackburn and Meyer-Viol 1994). Actions are defined as transition functions between intermediate states, which monotonically extend tree structures and node decorations. Both are partial in two senses: (a) node relations can be partially specified; and (b) decorations can be underspecified. The final states are well-formed iff all the partiality and underspecification is resolved. In other words, in DS, grammaticality is defined as parseability, and there is no central grammar of the kind assumed by most approaches to generation. In this paper we give a description of a prototype generator based on the DS approach (which incorporates a prototype parser as the central subpart). We assume a fully specified source tree as input (the 'goal tree' for some parser): given this, the generator incrementally produces a set of corresponding strings. In assuming a source tree, we are ignoring some issues that might be required in a dialogue system, such as concept generation, and translation from some flat meaning representation (e.g. a FOL formula) into a decorated source tree. We are therefore treating a generator as a module which supports that part of the generation process called sugaring (Ranta 1994) or linguistic realisation (Reiter and Dale 1995), i.e. translation from some unambiguously structured object in some language (generally a logic) for meaning representation to natural language strings. Naive Generation: ----------------- It turns out that very little is required beyond the standard DS notion of parseability. For a naive generator, all that is required is a notion of tree subsumption: this allows any candidate partial tree produced in the generation process to be checked against the goal tree to determine whether it is a sensible candidate (by checking for tree mergeability without inconsistency in node relations and decorations). At any point in the parsing process, a DS parser state can be seen as a pair of a partial string (the input so far) and a set of associated partial trees. With generation, we view the generator state as a set of these parser states (a set of pairs of 'possibly acceptable' partial strings and their associated sets of partial trees). At each stage of generation, each pair is extended by tentatively extending the partial string by adding any word from the lexicon. The associated set of possible (partial) trees is produced using the standard parser, and only those which are subsumed by the goal tree are kept. Any strings associated with empty tree sets are then rejected. Generation is complete when the process can be continued no further (any string extension results in an empty parser state), and the set of output strings is taken as those for which the associated tree set contains a member identical to the goal tree. Lexical selection is implicit: any word in the lexicon which is not associated with a node (or formula decorating a node) in the goal tree will produce empty tree sets, and therefore cannot produce acceptable extended partial strings. Parseability by a hearer is of course guaranteed, as strings are produced by incremental parsing. Efficiency: ----------- This naive process sounds inefficient: as the basic concept is to generate all possible strings and check whether parsing them gives a sensible tree, one might expect N! possible paths given a lexicon of N words. However, the incremental nature means that this is not the case: unsuitable search paths are eliminated on a stage-by-stage basis by the subsumption check. A Prolog implementation of this naive version generates simple sentences in a few seconds. We explore efficiency improvements by lexical selection and search method. Lexical selection uses the decorations of the input goal tree to produce a limited set of lexical items which can be used by the generator, consisting of a set L of words which correspond to logical formula decorations (e.g. N, V, Adj, Det) and a set F of functional words (e.g. relativiser, complementiser). This reduces the search space considerably, with the number of paths at most (L+F)! and in fact significantly less (see above). The incremental nature of the generation process allows us to apply various search methods, and stop the process once any string has been found which is associated with a tree identical to the goal tree (rather than continuing until all search paths are terminated). Using a depth-first approach with this method will therefore cause only one string to be produced; whereas using a breadth-first approach will cause only the set of all strings of the shortest possible length to be produced. This provides scope for probabilistic (or other heuristic) methods to increase efficiency by constraining the search using techniques (e.g. beam search) well known in areas such as speech recognition. Summary: -------- The paper sets out a formal definition of a generation process for DS, in terms of the parsing process, and describes a naive computational implementation together with some possible improvements. In closing, we note that this (a) parsing-oriented, and (b) incremental view of generation promises to provide a basis for an explanation of certain psycholinguistic observations about dialogue such as co-ordination between speakers and continuation of one speaker's utterance by another.