Computing EM-based Alignments of Routes and Route Directions as a Basis for Natural Language Generation

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 958–966, Beijing, August 2010 Computing EM-based Alignments of Routes and Route Directions as a Basis for Natural Language Generation Michael Roth and Anette Frank Department of Computational Linguistics Heidelberg University {mroth,frank}@cl.uni-heidelberg.de Abstract Route directions are natural language (NL) statements that specify, for a given navigational task and an automatically computed route representation, a se- quence of actions to be followed by the user to reach his or her goal. A corpus- based approach to generate route direc- tions involves (i) the selection of elements along the route that need to be mentioned, and (ii) the induction of a mapping from route elements to linguistic structures that can be used as a basis for NL generation. This paper presents an Expectation-Maxi- mization (EM) based algorithm that aligns geographical route representations with semantically annotated NL directions, as a basis for the above tasks. We formu- late one basic and two extended models, the latter capturing special properties of the route direction task. Although our current data set is small, both extended models achieve better results than the sim- ple model and a random baseline. The best results are achieved by a combination of both extensions, which outperform the random baseline and the simple model by more than an order of magnitude. 1 Introduction The purpose of route directions is to inform a per- son, who is typically not familiar with his cur- rent environment, of how to get to a designated goal. Generating such directions poses difficul- ties on various conceptual levels such as planning the route, selecting landmarks (i.e., recognizable buildings or structures) and splitting the task into appropriate single instructions of how to navigate along the route using the selected landmarks as reference points. Previously developed natural language genera- tion (NLG) systems make use of simple heuristics for the task of content selection for route direc- tions (Dale et al., 2005; Roth and Frank, 2009). In our work, we aim for a corpus-based approach that can be flexibly modeled after natural, human- produced directions for varying subtasks (e.g., in- door vs. outdoor navigation), and that facilitates multilingual extensions. By employing salient landmarks and allowing for variation in NL real- ization, such a system is expected to generate nat- ural sounding directions that are easier to memo- rize and easier to follow than directions given by a classical route planner or navigation system. NLG for route directions crucially differs from other generation tasks such as document summa- rization (Mani, 2001) in that the selection and or- dering of input structures for language generation is heavily situation-dependent, i.e., dependent on the specific properties of a given route to be fol- lowed. In line with a corpus-based NLG approach, we propose to automatically align geographical route representations as produced by a route planner with an annotated corpus of NL directions given by humans for the respective routes. The induced alignments will (i) serve to identify which ele- ments of a route …

Content truncated to 500 words