Extractive Multi-Document Summarization with Integer Linear Programming and Support Vector Regression

Proceedings of COLING 2012: Technical Papers, pages 911–926, COLING 2012, Mumbai, December 2012. Extractive Multi-Document Summarization with Integer Linear Programming and Support Vector Regression Dimitrios Galanis, Gerasimos Lampouras and Ion Androutsopoulos Department of Informatics Athens University of Economics and Business Patission 76, GR-104 34 Athens, Greece galanisd@aueb.gr, lampouras06@aueb.gr, ion@aueb.gr ABSTRACT We present a new method to generate extractive multi-document summaries. The method uses Integer Linear Programming to jointly maximize the importance of the sentences it includes in the summary and their diversity, without exceeding a maximum allowed summary length. To obtain an importance score for each sentence, it uses a Support Vector Regression model trained on human-authored summaries, whereas the diversity of the selected sentences is measured as the number of distinct word bigrams in the resulting summary. Experimental results on widely used benchmarks show that our method achieves state of the art results, when compared to competitive extractive summarizers, while being computationally efficient as well. KEYWORDS: Text Summarization; Integer Linear Programming; Support Vector Regression. 911 1 Introduction A multi-document summarization system aims to generate a single summary from an input set of documents. The input documents may have been obtained, for example, by submitting a query to an information retrieval engine and retaining the most highly ranked documents, or by clustering the documents of a large collection and then using each cluster as a set of documents to be summarized. Although evaluations with human judges also examine the coherence, referential clarity, grammaticality, and readability of the summaries (Dang, 2005, 2006; Dang and Owczarzak, 2008), and some of these factors have also been considered in recent summarization algorithms (Nishikawa et al., 2010b; Woodsend and Lapata, 2012), most current multi-document summarization systems consider only the importance of the summary’s sentences, their non-redundancy (also called diversity), and the summary length (McDonald, 2007; Berg-Kirkpatrick et al., 2011; Lin and Bilmes, 2011). An extractive multi-document summarizer forms summaries by extracting (selecting) sen- tences from the input documents, without modifying the selected sentences. By contrast, an abstractive summarizer may also shorten or, more generally, rephrase the selected sen- tences. In practice, the additional processing of the selected sentences may only marginally improve or even reduce the perceived quality of the resulting summaries (Gillick and Favre, 2009), though recent work has produced abstractive summarization methods that perform better than extractive ones (Berg-Kirkpatrick et al., 2011; Woodsend and Lapata, 2012). Nevertheless, the difference in the performance of extractive and abstractive summarizers is often small, and abstractive summarizers typically require more processing time, as well as tools and resources (e.g., reliable large coverage parsers, paraphrasing rules) that are often not available in less widely spoken languages. Hence, it is still worth trying to improve extractive summarizers, at least from a practical, application-oriented point of view. Many multi-document summarizers, especially extractive ones, adopt a greedy search when constructing summaries. For example, they may rank the sentences of the input documents by importance, and then iteratively add to the summary (and remove from the ranked list of input sentences) the …

Content truncated to 500 words