High Efficiency Realization for a Wide-Coverage Unification Grammar

High Efficiency Realization for a Wide-Coverage Unification Grammar⋆ John Carroll1 and Stephan Oepen2 1 University of Sussex 2 University of Oslo and Stanford University Abstract. We give a detailed account of an algorithm for efficient tactical gener- ation from underspecified logical-form semantics, using a wide-coverage gram- mar and a corpus of real-world target utterances. Some earlier claims about chart realization are critically reviewed and corrected in the light of a series of practical experiments. As well as a set of algorithmic refinements, we present two novel techniques: the integration of subsumption-based local ambiguity factoring, and a procedure to selectively unpack the generation forest according to a probability distribution given by a conditional, discriminative model. 1 Introduction A number of wide-coverage precise bi-directional NL grammars have been developed over the past few years. One example is the LinGO English Resource Grammar (ERG) [1], couched in the HPSG framework. Other grammars of similar size and coverage also exist, notable examples using the LFG and the CCG formalisms [2,3]. These grammars are used for generation from logical form input (also termed tactical generation or real- ization) in circumscribed domains, as part of applications such as spoken dialog systems [4] and machine translation [5]. Grammars like the ERG are lexicalist, in that the majority of information is encoded in lexical entries (or lexical rules) as opposed to being represented in constructions (i.e. rules operating on phrases). The semantic input to the generator for such grammars, often, is a bag of lexical predicates with semantic relationships captured by appropriate instantiation of variables associated with predicates and their semantic roles. For these sorts of grammars and ‘flat’ semantic inputs, lexically-driven approaches to realization – such as Shake-and-Bake [6], bag generation from logical form [7], chart generation [8], and constraint-based generation [9] – are highly suitable. Alternative approaches based on semantic head-driven generation and more recent variants [10,11] would work less well for lexicalist grammars since these approaches assume a hierarchically struc- tured input logical form. Similarly to parsing with large scale grammars, realization can be computation- ally expensive. In his presentation of chart generation, Kay [8] describes one source of potential inefficiency and proposes an approach for tackling it. However, Kay does not report on a verification of his approach with an actual grammar. Carroll et al. [12] ⋆ Dan Flickinger and Ann Copestake contributed a lot to the work described in this paper. We also thank Berthold Crysmann, Jan Tore Lønning and Bob Moore for useful discussions. Fund- ing is from the projects COGENT (UK EPSRC) and LOGON (Norwegian Research Council). R. Dale et al. (Eds.): IJCNLP 2005, LNAI 3651, pp. 165–176, 2005. c⃝ Springer-Verlag Berlin Heidelberg 2005 166 J. Carroll and S. Oepen ⟨ h1, { h1:proposition m(h2), h3: run v(e4, x5), h3:past(e4), h6: the q(x5, h7, h8), h9: athlete n(x5), h9: young a(x5), h9: polish a(x5) }, { h2 =q h3, h8 =q h9 } ⟩ Fig. 1. Simplified MRS for an utterance like the young Polish athlete ran (and variants). Elements from …

Content truncated to 500 words