Multi-document Summarization via Budgeted Maximization of Submodular Functions
Published 2 June 2010
Hui Lin, Jeff Bilmes
Citations366
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown, both theoretically and empirically, that a modified greedy algorithm can efficiently solve the budgeted submodular maximization problem near-optimally, and derive new approximation bounds in doing so.
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 submodular maximization problem near-optimally, and we derive new approximation bounds in doing so. Experiments on DUC’04 task show that our approach is superior to the bestperforming method from the DUC’04 evaluation on ROUGE-1 scores. 1
Keywords
Computer Science
Computer Networks and ISDN SystemsThe anatomy of a large-scale hypertextual Web search engine
15,828 Citations1998Sergey Brin, Lawrence M. Page
This paper provides an in-depth description of Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext and looks at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
ROUGE: A Package for Automatic Evaluation of Summaries
8,286 Citations2004Chin-Yew Lin
Four different RouGE measures are introduced: ROUGE-N, ROUge-L, R OUGE-W, and ROUAGE-S included in the Rouge summarization evaluation package and their evaluations.
Mathematical ProgrammingAn analysis of approximations for maximizing submodular set functions—I
4,458 Citations1978George L. Nemhauser, Laurence A. Wolsey +1 more
It is shown that a “greedy” heuristic always produces a solution whose value is at least 1 −[(K − 1/K]K times the optimal value, which can be achieved for eachK and has a limiting value of (e − 1)/e, where e is the base of the natural logarithm.
Empirical Methods in Natural Language ProcessingTextRank: Bringing Order into Text
3,347 Citations2004Rada Mihalcea, Paul Tarau
TextRank, a graph-based ranking model for text processing, is introduced and it is shown how this model can be successfully used in natural language applications.
Journal of the ACMA threshold of ln <i>n</i> for approximating set cover
3,122 Citations1998Uriel Feige
ACM SIGIR ForumThe Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries
2,210 Citations2017Jaime Carbonell, Jade Goldstein
A method for combining query-relevance with information-novelty in the context of text retrieval and summarization and preliminary results indicate some benefits for MMR diversity ranking in document retrieval and in single document summarization.
The use of MMR, diversity-based reranking for reordering documents and producing summaries
2,144 Citations1998Jaime Carbonell, Jade Goldstein
This paper presents a method for combining query-relevance with information-novelty in the context of text retrieval and summarization, and preliminary results indicate some benefits for MMR diversity ranking in document retrieval and in single document summarization.
Submodular functions and convexity
986 Citations1983László Lovász
In “continuous” optimization convex functions play a central role, and linear programming may be viewed as the optimization of very special (linear) objective functions over very special convex domains (polyhedra).
Information Processing LettersThe budgeted maximum coverage problem
976 Citations1999Samir Khuller, Anna Moss +1 more
This work proposes a (1−1/ e ) -approximation algorithm for the budgeted maximum coverage problem and argues that this approximation factor is the best possible, unless NP ⫅ DTIME (n O ( log log n) ) .
Journal of Combinatorial Theory Series BA Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time
680 Citations2000Alexander Schrijver
This work gives a strongly polynomial-time algorithm minimizing a submodular function f given by a value-giving oracle that does not use the ellipsoid method or any other linear programming method.
Operations Research LettersA note on maximizing a submodular set function subject to a knapsack constraint
676 Citations2003Maxim Sviridenko
An (1-e^-^1)-approximation algorithm for maximizing a nondecreasing submodular set function subject to a knapsack constraint is obtained and requires O(n^5) function value computations.
Journal of the ACMA combinatorial strongly polynomial algorithm for minimizing submodular functions
585 Citations2001Satoru Iwata, Lisa Fleischer +1 more
Graph-based ranking algorithms for sentence extraction, applied to text summarization
472 Citations2004Rada Mihalcea
This paper presents an innovative unsupervised method for automatic sentence extraction using graph-based ranking algorithms and shows that the results obtained compare favorably with previously published results on established benchmarks.
Lecture notes in computer scienceA Study of Global Inference Algorithms in Multi-document Summarization
365 Citations2007Ryan McDonald
This work defines a general framework for inference in summarization and presents three algorithms: a greedy approximate method, a dynamic programming approach based on solutions to the knapsack problem, and an exact algorithm that uses an Integer Linear Programming formulation of the problem.
Non-monotone submodular maximization under matroid and knapsack constraints
220 Citations2009Jon Lee, Vahab Mirrokni +2 more
This paper gives the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints, and improves the approximation guarantee of the algorithm to 1/k+1+{1/k-1}+ε for k≥2 partition matroid constraints.
Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling
214 Citations2007Christoph Ambühl, Monaldo Mas +1 more
It is proved that the scheduling problem is as-hard to approximate as vertex cover when the so-called fixed cost, that is present in all feasible solutions, is subtracted from the objective function.
PageRank on semantic networks, with application to word sense disambiguation
211 Citations2004Rada Mihalcea, Paul Tarau +1 more
A new open text word sense disambiguation method that combines the use of logical inferences with PageRank-style algorithms applied on graphs extracted from natural language documents is presented.
Text summarization model based on maximum coverage problem and its variant
149 Citations2009Hiroya Takamura, Manabu Okumura
The augmented model is superior to the best-performing method of DUC'04 on ROUGE-1 without stopwords and augmenting the summarization model so that it takes into account the relevance to the document cluster.
FigshareA note on the budgeted maximization of submodular functions
133 Citations2018Andreas Krause, Carlos Guestrin
arXiv (Cornell University)Non-monotone submodular maximization under matroid and knapsack constraints
114 Citations2009Jon Lee, Vahab Mirrokni +2 more
Graph-based submodular selection for extractive summarization
80 Citations2009Hui Lin, Jeff Bilmes +1 more
This work proposes a novel approach for unsupervised extractive summarization that builds a semantic graph for the document to be summarized and optimization is formulated as optimizing submodular functions defined on the semantic graph.
Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
76 Citations2009Gagan Goel, Chinmay Karande +2 more
Submodularity Cuts and Applications
27 Citations2009Yoshinobu Kawahara, Kiyohito Nagano +2 more
This work presents a novel algorithm for maximizing a submodular set function under a cardinality constraint based on a cutting-plane method and implemented as an iterative small-scale binary-integer linear programming procedure.