Multi-Sentence Compression: Finding Shortest Paths in Word Graphs

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 322–330, Beijing, August 2010 Multi-Sentence Compression: Finding Shortest Paths in Word Graphs Katja Filippova Google Inc. katjaf@google.com Abstract We consider the task of summarizing a cluster of related sentences with a short sentence which we call multi-sentence compression and present a simple ap- proach based on shortest paths in word graphs. The advantage and the novelty of the proposed method is that it is syntax- lean and requires little more than a tok- enizer and a tagger. Despite its simplic- ity, it is capable of generating grammati- cal and informative summaries as our ex- periments with English and Spanish data demonstrate. 1 Introduction Sentence compression (henceforth SC) is a task where the goal is to produce a summary of a sin- gle sentence which would preserve the important part of the content and be grammatical. Starting from the early work of Jing & McKeown (2000), in the last decade SC has received considerable at- tention in the NLP community. Ubiquitous use of mobile devices is an obvious example of where SC could be applied–a longer text of an email, news or a Wikipedia article can be compressed sentence by sentence to fit into a limited display (Corston-Oliver, 2001). Another reason why SC is so popular is its potential utility for extractive text summarization, single or multi-document (Mani, 2001). There, a standard approach is to rank sen- tences by importance, cluster them by similarity, and select a sentence from the top ranked clusters. Selected sentences almost always require revision and can be reformulated succinctly as it is often only a part of the sentence which is of interest. It is this multi-document summarization scenario which motivates our work. Given a cluster of similar, or related, sentences, we aim at summarizing the most salient theme of it in a short single sentence. We refer to this task as multi-sentence compression. Defined this way, it comes close to sentence fusion which was orig- inally introduced as a text-to-text generation tech- nique of expressing content common to most of the input sentences in a single sentence (Barzi- lay & McKeown, 2005). However, since then the technique has been extended so that now fusion also stands for uniting complementary content in a single concise sentence (Filippova & Strube, 2008b; Krahmer et al., 2008). Since our method is not designed for the “union” kind of fusion, we think it is more appropriate to classify it as a sen- tence compression technique. Two challenges of SC as well as text summa- rization are (i) important content selection and (ii) its readable presentation. Most existing systems use syntactic information to generate grammatical compressions. Incidentally, syntax also provides clues to what is likely to be important–e.g., the subject and the verb of the main clause are more likely to be important than a prepositional phrase or a verb from a relative clause. Of course, syn- tax is not the only way to gauge word or phrase importance. …

Content truncated to 500 words