Multi-document Summarization via Budgeted Maximization of Submodular Functions

Hui Lin, Jeff A. BilmesNAACL 2010 · OpenReview

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 best-performing method from the DUC'04 evaluation on ROUGE-1 scores.

Introduction

In extractive multi-document summarization, the goal is to select a subset of sentences from a collection of related documents to form a concise summary. This summary must maximize information coverage while minimizing redundancy, all while adhering to a strict length limit, such as a byte or word budget.

Historically, this problem has been approached using heuristics like Maximum Marginal Relevance (MMR), which lack global optimality guarantees, or Integer Linear Programming (ILP), which is NP-hard and computationally expensive for large datasets. This paper proposes a solution that combines the speed of greedy heuristics with the rigorous performance guarantees of global optimization by framing summarization as a budgeted submodular maximization problem.

Methods: Budgeted Submodular Maximization

The authors leverage the mathematical property of submodularity, which formalizes the concept of diminishing returns. In the context of summarization, adding a sentence to a small summary typically provides more novel information than adding it to a larger summary that already contains similar content.

Objective Function

The proposed graph-based submodular objective function incorporates two main components:

  1. Representativeness: A "graph-cut" term that rewards sentences highly similar to the overall document cluster.
  2. Redundancy Penalty: A term that penalizes the selection of sentences that overlap significantly with those already chosen.

Modified Greedy Algorithm

To maximize this function under a budget $B$, the authors introduce a modified greedy algorithm. Instead of a simple greedy selection, the algorithm chooses sentences based on the ratio of information gain to scaled cost $(c_\ell)^r$, where $r$ is a scaling factor.

Algorithm 1: The modified greedy algorithm for budgeted submodular maximization.

The algorithm compares the resulting greedy set against the single best sentence that fits within the budget and returns the better of the two. This approach provides a theoretical guarantee: the output is at least a constant fraction ($1 - 1/\sqrt{e}$) of the true optimal value.

Datasets and Evaluation

The approach was tuned on the DUC 2003 dataset to determine optimal hyperparameters, such as the cost scaling factor $r$ and the redundancy penalty weight $\lambda$. Final evaluation was conducted on DUC 2004 (Task 2), a standard benchmark for multi-document summarization of English news articles with a 665-byte limit.

Key Insights

  • Submodularity as a Natural Fit: Diminishing returns accurately model human intuition regarding redundancy in summaries.
  • Cost Scaling: Introducing the factor $r$ allows the algorithm to effectively balance sentence value against its length, bridging the gap between abstract information scores and physical budget constraints.
  • Efficiency vs. Optimality: The modified greedy approach achieves near-optimal results with a fraction of the computational cost required by exact solvers.

Key Results

The proposed method demonstrates significant improvements in both computational efficiency and summarization quality.

  • Computational Speed: For a document cluster of 182 sentences, an ILP solver required approximately 17 hours to find the exact optimal summary. In contrast, the modified greedy algorithm completed the task in less than 0.01 seconds.
  • Near-Optimality: Empirical tests on DUC'03 clusters showed that the greedy algorithm consistently achieved over 90% of the true optimal objective function value.
  • State-of-the-Art Performance: On the DUC'04 dataset, the submodular approach achieved a ROUGE-1 score of 38.39%, outperforming established baselines and the top-performing system from the original competition.
Comparison of ROUGE-1 scores on DUC'04 Task 2.

Limitations and Future Work

The theoretical bounds rely on the objective function being monotone. While the inclusion of a redundancy penalty can technically violate strict monotonicity, the authors find that the bounds hold in practice because summaries are small relative to the source text. Additionally, while the algorithm optimizes a submodular surrogate, future work could explore direct optimization of evaluation metrics like ROUGE, although the authors suggest their submodular function may already be a strong proxy for human-judged quality.

Summary updated

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 best-performing method from the DUC'04 evaluation on ROUGE-1 scores.
BibTeX
@inproceedings{lin2010multi,
  author = {Hui Lin and Jeff A. Bilmes},
  title = {{Multi-document Summarization via Budgeted Maximization of Submodular Functions}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=BJ-t1mW_WB},
}
Figure