A Decision-Theoretic Approach to Natural Language Generation

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 552–561, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics A Decision-Theoretic Approach to Natural Language Generation Nathan McKinley Department of EECS Case Western Reserve University Cleveland, OH, USA nath@nmckinley.com Soumya Ray Department of EECS Case Western Reserve University Cleveland, OH, USA sray@case.edu Abstract We study the problem of generating an En- glish sentence given an underlying prob- abilistic grammar, a world and a com- municative goal. We model the genera- tion problem as a Markov decision process with a suitably defined reward function that reflects the communicative goal. We then use probabilistic planning to solve the MDP and generate a sentence that, with high probability, accomplishes the com- municative goal. We show empirically that our approach can generate complex sen- tences with a speed that generally matches or surpasses the state of the art. Further, we show that our approach is anytime and can handle complex communicative goals, including negated goals. 1 Introduction Suppose someone wants to tell their friend that they saw a dog chasing a cat. Given such a com- municative goal, most people can formulate a sen- tence that satisfies the goal very quickly. Fur- ther, they can easily provide multiple similar sen- tences, differing in details but all satisfying the general communicative goal, with no or very lit- tle error. Natural language generation (NLG) de- velops techniques to extend similar capabilities to automated systems. In this paper, we study the re- stricted NLG problem: given a grammar, lexicon, world and a communicative goal, output a valid English sentence that satisfies this goal. The prob- lem is restricted because in our work, we do not consider the issue of how to fragment a complex goal into multiple sentences (discourse planning). Though restricted, this NLG problem is still dif- ficult. A key source of difficulty is the nature of the grammar, which is generally large, probabilis- tic and ambiguous. Some NLG techniques use sampling strategies (Knight and Hatzivassiloglou, 1995) where a set of sentences is sampled from a data structure created from an underlying gram- mar and ranked according to how well they meet the communicative goal. Such approaches natu- rally handle statistical grammars, but do not solve the generation problem in a goal-directed manner. Other approaches view NLG as a planning prob- lem (Koller and Stone, 2007). Here, the commu- nicative goal is treated as a predicate to be sat- isfied, and the grammar and vocabulary are suit- ably encoded as logical operators. Then auto- mated classical planning techniques are used to derive a plan which is converted into a sentence. This is an elegant formalization of NLG, however, restrictions on what current planning techniques can do limit its applicability. A key limitation is the logical nature of automated planning systems, which do not handle probabilistic grammars, or force ad-hoc approaches for doing so (Bauer and Koller, 2010). A second limitation comes from re- strictions on the goal: it may be …

Content truncated to 500 words