Learning Mixtures of Submodular Shells with Application to Document Summarization

Hui Lin, Jeff A. Bilmes
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:477-488, 2012.

Abstract

We introduce a method to learn a mixture of submodular "shells" in a large-margin setting. A submodular shell is an abstract submodular function that can be instantiated with a ground set and a set of parameters to produce a submodular function. A mixture of such shells can then also be so instantiated to produce a more complex submodular function. What our algorithm learns are the mixture weights over such shells. We provide a risk bound guarantee when learning in a large-margin structured-prediction setting using a projected subgradient method when only approximate submodular optimization is possible (such as with submodular function maximization). We apply this method to the problem of multi-document summarization and produce the best results reported so far on the widely used NIST DUC-05 through DUC-07 document summarization corpora.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-lin12a, title = {Learning Mixtures of Submodular Shells with Application to Document Summarization}, author = {Lin, Hui and Bilmes, Jeff A.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {477--488}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/lin12a/lin12a.pdf}, url = {https://proceedings.mlr.press/r10/lin12a.html}, abstract = {We introduce a method to learn a mixture of submodular "shells" in a large-margin setting. A submodular shell is an abstract submodular function that can be instantiated with a ground set and a set of parameters to produce a submodular function. A mixture of such shells can then also be so instantiated to produce a more complex submodular function. What our algorithm learns are the mixture weights over such shells. We provide a risk bound guarantee when learning in a large-margin structured-prediction setting using a projected subgradient method when only approximate submodular optimization is possible (such as with submodular function maximization). We apply this method to the problem of multi-document summarization and produce the best results reported so far on the widely used NIST DUC-05 through DUC-07 document summarization corpora.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Learning Mixtures of Submodular Shells with Application to Document Summarization %A Hui Lin %A Jeff A. Bilmes %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-lin12a %I PMLR %P 477--488 %U https://proceedings.mlr.press/r10/lin12a.html %V R10 %X We introduce a method to learn a mixture of submodular "shells" in a large-margin setting. A submodular shell is an abstract submodular function that can be instantiated with a ground set and a set of parameters to produce a submodular function. A mixture of such shells can then also be so instantiated to produce a more complex submodular function. What our algorithm learns are the mixture weights over such shells. We provide a risk bound guarantee when learning in a large-margin structured-prediction setting using a projected subgradient method when only approximate submodular optimization is possible (such as with submodular function maximization). We apply this method to the problem of multi-document summarization and produce the best results reported so far on the widely used NIST DUC-05 through DUC-07 document summarization corpora. %Z Reissued by PMLR on 04 October 2026.
APA
Lin, H. & Bilmes, J.A.. (2012). Learning Mixtures of Submodular Shells with Application to Document Summarization. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:477-488 Available from https://proceedings.mlr.press/r10/lin12a.html. Reissued by PMLR on 04 October 2026.

Related Material