Large-Margin Learning of Submodular Summarization Models

Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 224–233, Avignon, France, April 23 - 27 2012. c⃝2012 Association for Computational Linguistics Large-Margin Learning of Submodular Summarization Models Ruben Sipos Dept. of Computer Science Cornell University Ithaca, NY 14853 USA rs@cs.cornell.edu Pannaga Shivaswamy Dept. of Computer Science Cornell University Ithaca, NY 14853 USA pannaga@cs.cornell.edu Thorsten Joachims Dept. of Computer Science Cornell University Ithaca, NY 14853 USA tj@cs.cornell.edu Abstract In this paper, we present a supervised learning approach to training submodu- lar scoring functions for extractive multi- document summarization. By taking a structured prediction approach, we pro- vide a large-margin method that directly optimizes a convex relaxation of the de- sired performance measure. The learning method applies to all submodular summa- rization methods, and we demonstrate its effectiveness for both pairwise as well as coverage-based scoring functions on mul- tiple datasets. Compared to state-of-the- art functions that were tuned manually, our method significantly improves performance and enables high-fidelity models with num- ber of parameters well beyond what could reasonably be tuned by hand. 1 Introduction Automatic document summarization is the prob- lem of constructing a short text describing the main points in a (set of) document(s). Exam- ple applications range from generating short sum- maries of news articles, to presenting snippets for URLs in web-search. In this paper we focus on extractive multi-document summarization, where the final summary is a subset of the sentences from multiple input documents. In this way, ex- tractive summarization avoids the hard problem of generating well-formed natural-language sen- tences, since only existing sentences from the in- put documents are presented as part of the sum- mary. A current state-of-the-art method for document summarization was recently proposed by Lin and Bilmes (2010), using a submodular scoring func- tion based on inter-sentence similarity. On the one hand, this scoring function rewards summaries that are similar to many sentences in the origi- nal documents (i.e. promotes coverage). On the other hand, it penalizes summaries that contain sentences that are similar to each other (i.e. dis- courages redundancy). While obtaining the exact summary that optimizes the objective is computa- tionally hard, they show that a greedy algorithm is guaranteed to compute a good approximation. However, their work does not address how to select a good inter-sentence similarity measure, leaving this problem as well as selecting an appro- priate trade-off between coverage and redundancy to manual tuning. To overcome this problem, we propose a su- pervised learning method that can learn both the similarity measure as well as the cover- age/reduncancy trade-off from training data. Fur- thermore, our learning algorithm is not limited to the model of Lin and Bilmes (2010), but applies to all monotone submodular summarization models. Due to the diminishing-returns property of mono- tone submodular set functions and their computa- tional tractability, this class of functions provides a rich space for designing summarization meth- ods. To illustrate the generality of our approach, we also provide experiments for a coverage-based model originally …

Content truncated to 500 words