  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.
