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.