A Class of Submodular Functions for Document Summarization

TLDR

The authors propose a new class of submodular functions for document summarization. These functions combine a representativeness term with a diversity reward, are monotone nondecreasing and submodular, and thus admit efficient greedy optimization with a constant‑factor optimality guarantee. On DUC 2004–2007 corpora, the proposed functions outperform state‑of‑the‑art methods in both generic and query‑focused summarization, and the authors show that many existing summarization techniques are special cases of submodular optimization.

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.