Multi-document Summarization via Budgeted Maximization of Submodular Functions

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 912–920, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Multi-document Summarization via Budgeted Maximization of Submodular Functions Hui Lin Dept. of Electrical Engineering University of Washington Seattle, WA 98195, USA hlin@ee.washington.edu Jeff Bilmes Dept. of Electrical Engineering University of Washington Seattle, WA 98195, USA bilmes@ee.washington.edu Abstract We treat the text summarization problem as maximizing a submodular function under a budget constraint. We show, both theoretically and empirically, a modified greedy algorithm can efficiently solve the budgeted submodu- lar maximization problem near-optimally, and we derive new approximation bounds in do- ing so. Experiments on DUC’04 task show that our approach is superior to the best- performing method from the DUC’04 evalu- ation on ROUGE-1 scores. 1 Introduction Automatically generating summaries from large text corpora has long been studied in both information retrieval and natural language processing. There are several types of text summarization tasks. For example, if an input query is given, the generated summary can be query-specific, and otherwise it is generic. Also, the number of documents to be sum- marized can vary from one to many. The constituent sentences of a summary, moreover, might be formed in a variety of different ways — summarization can be conducted using either extraction or abstraction, the former selects only sentences from the origi- nal document set, whereas the latter involves natu- ral language generation. In this paper, we address the problem of generic extractive summaries from clusters of related documents, commonly known as multi-document summarization. In extractive text summarization, textual units (e.g., sentences) from a document set are extracted to form a summary, where grammaticality is as- sured at the local level. Finding the optimal sum- mary can be viewed as a combinatorial optimiza- tion problem which is NP-hard to solve (McDon- ald, 2007). One of the standard methods for this problem is called Maximum Marginal Rele- vance (MMR) (Dang, 2005)(Carbonell and Gold- stein, 1998), where a greedy algorithm selects the most relevant sentences, and at the same time avoids redundancy by removing sentences that are too sim- ilar to already selected ones. One major problem of MMR is that it is non-optimal because the deci- sion is made based on the scores at the current it- eration. McDonald (2007) proposed to replace the greedy search of MMR with a globally optimal for- mulation, where the basic MMR framework can be expressed as a knapsack packing problem, and an integer linear program (ILP) solver can be used to maximize the resulting objective function. ILP Al- gorithms, however, can sometimes either be expen- sive for large scale problems or themselves might only be heuristic without associated theoretical ap- proximation guarantees. In this paper, we study graph-based approaches for multi-document summarization. Indeed, several graph-based methods have been proposed for extrac- tive summarization in the past. Erkan and Radev (2004) introduced a stochastic graph-based method, LexRank, for computing the relative importance of textual units for multi-document summarization. …

Content truncated to 500 words