Elamur Research⌕
☰
home / papers / 2011 / A Class of Submodular Functions for Document Summarization

A Class of Submodular Functions for Document Summarization

Summary

Lin and Bilmes treat extractive multi-document summarization, both generic and query-focused, as maximizing a monotone submodular set function under a length budget. Such functions have diminishing returns. A cheap greedy procedure therefore comes with a provable constant-factor bound relative to the optimal summary.

The authors build an objective from two parts:

  • a coverage (fidelity) term L1(S), which measures how well the chosen sentences represent the whole document set;
  • a diversity reward, which splits sentences into clusters and applies a concave function (a square root) to the summed sentence rewards inside each cluster. This favours picking from many clusters rather than piling up from one.

For query-focused tasks, the sentence rewards mix query-independent centrality with query overlap. The overlap uses WordNet expansion of nouns. Coefficients are tuned with Nelder-Mead to maximize ROUGE-2 F-measure.

On DUC-04 to DUC-07, the system matches or beats the best previously reported results, using only basic NLP. The paper also shows that MMR and concept-coverage methods are hidden instances of submodular optimization. This frames objective design as the central question for the field.

Key points

  • The greedy algorithm gives at least (1 − 1/e) ≈ 0.632 of the optimum under a cardinality limit. Under a knapsack (word-budget) limit, a cost-scaled greedy variant from the authors' earlier work gives a (1 − 1/√e) factor.
  • The MMR gain function turns out to be submodular but not monotone, so the greedy guarantee does not carry over to it. Concept-coverage objectives are monotone submodular.
  • On DUC-05, the system reaches 8.38% ROUGE-2 recall. This beats the extractive system of Daumé et al. (7.67%) and even their abstractive-style "vine-growth" system (8.24%).
  • On DUC-07, the system outperforms PYTHY and topic-model-based systems. With three clusterings (0.3N, 0.15N, 0.05N) trained on DUC-05 and DUC-06, it beats the best DUC-07 system on ROUGE-2 F-measure. That system relied on Yahoo! web search, which this one does not.
  • Expanding sentences with WordNet synonyms and hypernyms helped relevance estimation. Expanding the query with synonyms hurt performance, likely because it added noise.

Interesting ideas

  • I1. Diversity as a reward rather than a penalty. Subtracting a redundancy penalty breaks monotonicity. Applying a concave function per cluster keeps the objective monotone while still discouraging repetition. The same trick fits any selection task, such as data subset selection or corpus sampling.
  • I2. Assembling objectives from closure rules. Nonnegative weighted sums of submodular functions, and nondecreasing concave functions applied to them, stay submodular. This lets you build a task-specific objective from parts while keeping the optimization guarantee.
  • I3. Multi-resolution clusterings. Adding several diversity terms built from clusterings of different granularity, instead of choosing one cluster count, improved results. It is a simple hedge against a poorly chosen K.
  • I4. Auditing existing heuristics for hidden structure. Checking whether a known method (e.g., MMR) is secretly submodular, and whether it is monotone, tells you whether its greedy procedure has any guarantee. This is a useful diagnostic for other greedy pipelines.
  • I5. Separating query relevance from global importance. The singleton reward is a convex mix of a query-independent centrality score and a query-overlap score, each normalized to a similar range. This is a light, transferable way to make a generic selector query-aware.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Cited by

98 papers of our library cite it (of the 140884 whose bibliographies we read); 4 of them have a page here, 94 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{lin2011class,
  title = {{A Class of Submodular Functions for Document Summarization}},
  author = {Lin, Hui and Bilmes, Jeff},
  booktitle = {Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies},
  year = {2011},
  url = {https://aclanthology.org/P11-1052/}
}

References

37 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. F. Bach. 2010. Structured sparsity-inducing norms through submodular functions. Advances in Neural Information Processing Systems. find
  2. J. Carbonell and J. Goldstein. 1998. The use of MMR, diversity-based reranking for reordering documents and producing summaries. In Proc. of SIGIR. find
  3. A. Celikyilmaz and D. Hakkani-tür. 2010. A hybrid hierarchical model for multi-document summarization. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 815–824, Uppsala, Sweden, July. Association for Computational Linguistics. find
  4. H. Daumé, J. Langford, and D. Marcu. 2009. Search-based structured prediction. Machine learning, 75(3):297–325. find
  5. H. Daumé III and D. Marcu. 2006. Bayesian query-focused summarization. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, page 312. find
  6. C. Fellbaum. 1998. WordNet: An electronic lexical database. The MIT press. find
  7. E. Filatova and V. Hatzivassiloglou. 2004. Event-based extractive summarization. In Proceedings of ACL Workshop on Summarization, volume 111. find
  8. A. Haghighi and L. Vanderwende. 2009. Exploring content models for multi-document summarization. In Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 362–370, Boulder, Colorado, June. Associati… find our card
  9. J. Jagarlamudi, P. Pingali, and V. Varma. 2006. Query independent sentence scoring approach to DUC 2006. In DUC 2006. find
  10. S. Jegelka and J. A. Bilmes. 2011. Submodularity beyond submodular energies: coupling edges in graph cuts. In Computer Vision and Pattern Recognition (CVPR), Colorado Springs, CO, June. find
  11. D. Kempe, J. Kleinberg, and E. Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the 9th Conference on SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). find
  12. S. Khuller, A. Moss, and J. Naor. 1999. The budgeted maximum coverage problem. Information Processing Letters, 70(1):39–45. find
  13. V. Kolmogorov and R. Zabin. 2004. What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):147–159. find
  14. A. Krause and C. Guestrin. 2005. Near-optimal nonmyopic value of information in graphical models. In Proc. of Uncertainty in AI. find
  15. A. Krause, H.B. McMahan, C. Guestrin, and A. Gupta. 2008. Robust submodular observation selection. Journal of Machine Learning Research, 9:2761–2801. find
  16. H. Lin and J. Bilmes. 2010. Multi-document summarization via budgeted maximization of submodular functions. In North American chapter of the Association for Computational Linguistics/Human Language Technology Conference (NAACL/HLT-2010), Los Angeles, CA, June. find
  17. H. Lin and J. Bilmes. 2011. Word alignment via submodular maximization over matroids. In The 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-HLT), Portland, OR, June. find
  18. H. Lin, J. Bilmes, and S. Xie. 2009. Graph-based submodular selection for extractive summarization. In Proc. IEEE Automatic Speech Recognition and Understanding (ASRU), Merano, Italy, December. find
  19. C.-Y. Lin. 2004. ROUGE: A package for automatic evaluation of summaries. In Text Summarization Branches Out: Proceedings of the ACL-04 Workshop. find
  20. L. Lovász. 1983. Submodular functions and convexity. Mathematical programming-The state of the art,(eds. A. Bachem, M. Grotschel and B. Korte) Springer, pages 235–257. find
  21. M. Minoux. 1978. Accelerated greedy algorithms for maximizing submodular set functions. Optimization Techniques, pages 234–243. find
  22. M. Narasimhan and J. Bilmes. 2005. A submodular-supermodular procedure with applications to discriminative structure learning. In Proc. Conf. Uncertainty in Artifical Intelligence, Edinburgh, Scotland, July. Morgan Kaufmann Publishers. find
  23. M. Narasimhan and J. Bilmes. 2007. Local search for balanced submodular clusterings. In Twentieth International Joint Conference on Artificial Intelligence (IJ-CAI07), Hyderabad, India, January. find
  24. H. Narayanan. 1997. Submodular functions and electrical networks. North-Holland. find
  25. G.L. Nemhauser, L.A. Wolsey, and M.L. Fisher. 1978. An analysis of approximations for maximizing submodular set functions I. Mathematical Programming, 14(1):265– 294. find
  26. P. Pingali, K. Rahul, and V. Varma. 2007. IIIT Hyderabad at DUC 2007. Proceedings of DUC 2007. find
  27. V. Qazvinian, D.R. Radev, and A. Ozgür. 2010. Citation Summarization Through Keyphrase Extraction. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 895– 903. find
  28. A. Ratnaparkhi. 1996. A maximum entropy model for part-of-speech tagging. In EMNLP, volume 1, pages 133–142. find our card
  29. K. Riedhammer, B. Favre, and D. Hakkani-Tür. 2010. Long story short-Global unsupervised models for keyphrase based meeting summarization. Speech Communication. find
  30. C. Shen and T. Li. 2010. Multi-document summarization via the minimum dominating set. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 984–992, Beijing, China, August. find
  31. Coling 2010 Organizing Committee. find
  32. M. Sviridenko. 2004. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41–43. find
  33. H. Takamura and M. Okumura. 2009. Text summarization model based on maximum coverage problem and its variant. In Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, pages 781–789. Association for Computational Linguistics. find
  34. K. Toutanova, C. Brockett, M. Gamon, J. Jagarlamudi, H. Suzuki, and L. Vanderwende. 2007. The PYTHY summarization system: Microsoft research at DUC 2007. In the proceedings of Document Understanding Conference. find
  35. D. Wang, S. Zhu, T. Li, and Y. Gong. 2009. Multi-document summarization using sentence-based topic models. In Proceedings of the ACL-IJCNLP 2009 Conference Short Papers, pages 297–300, Suntec, Singapore, August. Association for Computational Linguistics. find
  36. L.A. Wolsey. 1982. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385–393. find
  37. P. Zhao, G. Rocha, and B. Yu. 2009. Grouped and hierarchical model selection through composite absolute penalties. Annals of Statistics, 37(6A):3468–3497. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lin-2011-class-submodular-functions-document-summarization/