A Class of Submodular Functions for Document Summarization

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 510–520, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics A Class of Submodular Functions for Document Summarization 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 design a class of submodular functions meant for document summarization tasks. These functions each combine two terms, one which encourages the summary to be representative of the corpus, and the other which positively rewards diversity. Critically, our functions are monotone nondecreasing and submodular, which means that an efficient scalable greedy optimization scheme has a constant factor guarantee of optimality. When evaluated on DUC 2004-2007 corpora, we obtain better than existing state-of-art results in both generic and query-focused document summarization. Lastly, we show that several well-established methods for document summarization correspond, in fact, to submodular function optimization, adding further evidence that submodular functions are a natural fit for document summarization. 1 Introduction In this paper, we address the problem of generic and query-based extractive summarization from collec- tions of related documents, a task commonly known as multi-document summarization. We treat this task as monotone submodular function maximization (to be defined in Section 2). This has a number of criti- cal benefits. On the one hand, there exists a simple greedy algorithm for monotone submodular func- tion maximization where the summary solution ob- tained (say ˆS) is guaranteed to be almost as good as the best possible solution (say Sopt) according to an objective F. More precisely, the greedy algo- rithm is a constant factor approximation to the car- dinality constrained version of the problem, so that F( ˆS) ≥ (1 − 1/e)F(Sopt) ≈ 0.632F(Sopt). This is particularly attractive since the quality of the so- lution does not depend on the size of the problem, so even very large size problems do well. It is also important to note that this is a worst case bound, and in most cases the quality of the solution obtained will be much better than this bound suggests. Of course, none of this is useful if the objective function F is inappropriate for the summarization task. In this paper, we argue that monotone nonde- creasing submodular functions F are an ideal class of functions to investigate for document summarization. We show, in fact, that many well-established methods for summarization (Carbonell and Goldstein, 1998; Filatova and Hatzivassiloglou, 2004; Takamura and Okumura, 2009; Riedhammer et al., 2010; Shen and Li, 2010) correspond to submodular function opti- mization, a property not explicitly mentioned in these publications. We take this fact, however, as testament to the value of submodular functions for summariza- tion: if summarization algorithms are repeatedly de- veloped that, by chance, happen to be an instance of a submodular function optimization, this suggests that submodular functions are a natural fit. On the other hand, other authors have started realizing explicitly the value of submodular functions for …

Content truncated to 500 words