Sentence generation as a planning problem

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 336–343, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Sentence generation as a planning problem Alexander Koller Center for Computational Learning Systems Columbia University koller@cs.columbia.edu Matthew Stone Computer Science Rutgers University Matthew.Stone@rutgers.edu Abstract We translate sentence generation from TAG grammars with semantic and pragmatic in- formation into a planning problem by encod- ing the contribution of each word declara- tively and explicitly. This allows us to ex- ploit the performance of off-the-shelf plan- ners. It also opens up new perspectives on referring expression generation and the rela- tionship between language and action. 1 Introduction Systems that produce natural language must synthe- size the primitives of linguistic structure into well- formed utterances that make desired contributions to discourse. This is fundamentally a planning prob- lem: Each linguistic primitive makes certain con- tributions while potentially introducing new goals. In this paper, we make this perspective explicit by translating the sentence generation problem of TAG grammars with semantic and pragmatic information into a planning problem stated in the widely used Planning Domain Definition Language (PDDL, Mc- Dermott (2000)). The encoding provides a clean separation between computation and linguistic mod- elling and is open to future extensions. It also allows us to benefit from the past and ongoing advances in the performance of off-the-shelf planners (Blum and Furst, 1997; Kautz and Selman, 1998; Hoffmann and Nebel, 2001). While there have been previous systems that en- code generation as planning (Cohen and Perrault, 1979; Appelt, 1985; Heeman and Hirst, 1995), our approach is distinguished from these systems by its focus on the grammatically specified contributions of each individual word (and the TAG tree it an- chors) to syntax, semantics, and local pragmatics (Hobbs et al., 1993). For example, words directly achieve content goals by adding a corresponding se- mantic primitive to the conversational record. We deliberately avoid reasoning about utterances as co- ordinated rational behavior, as earlier systems did; this allows us to get by with a much simpler logic. The problem we solve encompasses the genera- tion of referring expressions (REs) as a special case. Unlike some approaches (Dale and Reiter, 1995; Heeman and Hirst, 1995), we do not have to dis- tinguish between generating NPs and expressions of other syntactic categories. We develop a new per- spective on the lifecycle of a distractor, which allows us to generate more succinct REs by taking the rest of the utterance into account. More generally, we do not split the process of sentence generation into two separate steps of sentence planning and realization, as most other systems do, but solve the joint prob- lem in a single integrated step. This can potentially allow us to generate higher-quality sentences. We share these advantages with systems such as SPUD (Stone et al., 2003). Crucially, however, our approach describes the dynamics of interpretation explicitly and declara- tively. We do not need to assume extra machin- ery beyond the encoding of words as PDDL plan- …

Content truncated to 500 words