Sentence Compression Beyond Word Deletion

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 137–144 Manchester, August 2008 Sentence Compression Beyond Word Deletion Trevor Cohn and Mirella Lapata School of Informatics University of Edinburgh {tcohn,mlap}@inf.ed.ac.uk Abstract In this paper we generalise the sen- tence compression task. Rather than sim- ply shorten a sentence by deleting words or constituents, as in previous work, we rewrite it using additional operations such as substitution, reordering, and insertion. We present a new corpus that is suited to our task and a discriminative tree-to- tree transduction model that can naturally account for structural and lexical mis- matches. The model incorporates a novel grammar extraction method, uses a lan- guage model for coherent output, and can be easily tuned to a wide range of compres- sion specific loss functions. 1 Introduction Automatic sentence compression can be broadly described as the task of creating a grammatical summary of a single sentence with minimal in- formation loss. It has recently attracted much at- tention, in part because of its relevance to appli- cations. Examples include the generation of sub- titles from spoken transcripts (Vandeghinste and Pan, 2004), the display of text on small screens such as mobile phones or PDAs (Corston-Oliver, 2001), and, notably, summarisation (Jing, 2000; Lin, 2003). Most prior work has focused on a specific instantiation of sentence compression, namely word deletion. Given an input sentence of words, w1, w2 . . . wn, a compression is formed by dropping any subset of these words (Knight c⃝ 2008. Licensed under the Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported li- cense (http://creativecommons.org/licenses/by-nc-sa/3.0/). Some rights reserved. and Marcu, 2002). The simplification renders the task computationally feasible, allowing efficient decoding using a dynamic program (Knight and Marcu, 2002; Turner and Charniak, 2005; McDon- ald, 2006). Furthermore, constraining the problem to word deletion affords substantial modeling flex- ibility. Indeed, a variety of models have been suc- cessfully developed for this task ranging from in- stantiations of the noisy-channel model (Knight and Marcu, 2002; Galley and McKeown, 2007; Turner and Charniak, 2005), to large-margin learn- ing (McDonald, 2006; Cohn and Lapata, 2007), and Integer Linear Programming (Clarke, 2008). However, the simplification also renders the task somewhat artificial. There are many rewrite opera- tions that could compress a sentence, besides dele- tion, including reordering, substitution, and inser- tion. In fact, professional abstractors tend to use these operations to transform selected sentences from an article into the corresponding summary sentences (Jing, 2000). Therefore, in this paper we consider sentence compression from a more general perspective and generate abstracts rather than extracts. In this framework, the goal is to find a summary of the original sentence which is grammatical and con- veys the most important information without nec- essarily using the same words in the same or- der. Our task is related to, but different from, paraphrase extraction (Barzilay, 2003). We must not only have access to paraphrases (i.e., rewrite rules), but also be able to combine them in order to generate new text, while attempting to …

Content truncated to 500 words