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.
Introduction
Extractive multi-document summarization aims to select a small subset of sentences from a large collection that best represents the whole while minimizing redundancy. Historically, researchers relied on ad-hoc greedy heuristics like Maximum Marginal Relevance (MMR). However, these methods often lack a rigorous mathematical foundation. This paper addresses two core challenges: mathematically defining a "good" summary (Objective Design) and finding a high-quality solution efficiently despite the NP-hard nature of subset selection (Optimization).
The authors argue that many successful summarization methods were "accidentally" submodular. By explicitly embracing submodularity, they design objective functions that allow for optimization algorithms with provable performance bounds.
Proposed Submodular Objectives
The authors propose a new class of objective functions $F(S)$ that combine two monotone submodular terms:
$$F(S) = \mathcal{L}(S) + \lambda \mathcal{R}(S)$$
Coverage ($\mathcal{L}(S)$)
Instead of a simple sum of similarities, the authors introduce a saturation function. It measures how well the summary $S$ covers the corpus $V$. Once a specific document unit is "covered" enough (reaching a threshold $\alpha$), further similar sentences provide no extra benefit. This prevents the summary from focusing excessively on a single popular topic.
Diversity ($\mathcal{R}(S)$)
Sentences are partitioned into clusters (topics). The reward for picking sentences from a cluster grows with the square root of the number of sentences chosen from that cluster. Because the square root is a concave function, the marginal gain of picking additional sentences from the same cluster decreases, naturally encouraging the algorithm to select from diverse clusters.
Because these functions are monotone submodular, a simple greedy algorithm—repeatedly picking the sentence that increases the score the most—is guaranteed to find a solution within approximately 63% of the absolute theoretical optimum.
Evaluation and Key Results
The approach was evaluated on the Document Understanding Conference (DUC) corpora (2003–2007), which are standard benchmarks for generic and query-focused summarization.
State-of-the-Art Performance
The proposed method outperformed existing systems on DUC 2004 (generic) and DUC 2005-2006 (query-focused) in terms of ROUGE scores. A striking finding is that ROUGE-N itself is a monotone submodular function, explaining why submodular optimization aligns so well with the evaluation metric.
The Power of Saturation
In generic summarization, simply adding the saturation threshold $\alpha$ to a standard similarity objective significantly boosted performance. As shown in the DUC-04 results, the ROUGE-1 F-measure improved from 32.44% to 38.65%, surpassing the previous best-known system.
Discussion and Insights
- Reward Diversity, Don't Just Punish Redundancy: Older methods like MMR use redundancy penalties that often break the "monotone" property, losing theoretical guarantees. Positively rewarding diversity via concave functions is mathematically cleaner and more effective.
- Submodularity as a Natural Fit: Several previous state-of-the-art methods were actually instances of submodular optimization. This suggests submodularity is the underlying "grammar" of the summarization task.
Conclusion and Future Work
While the method achieves top-tier results, it remains dependent on the quality of pre-clustering (e.g., $K$-means). Future work could explore more advanced NLP techniques, such as language models or richer semantic features, to improve the coverage terms. Additionally, query expansion techniques using external web search could further enhance query-focused summarization performance.
Summary updated