Source-linked AI summary
Learning Mixtures of Submodular Shells with Application to Document Summarization
Hui Lin, Jeff A. Bilmes
TL;DR
Learning arbitrary submodular functions is hard, so the paper learns weights over parameterized submodular shells that instantiate across structured inputs. It provides a risk bound under approximate inference and reports the best results so far on standardized query-focused extractive summarization benchmarks.
Problem
Learning arbitrary submodular functions is hard, motivating restricted but expressive parameterized families that can be learned across structured inputs.
Method
The paper learns mixture coefficients over submodular shells in a large-margin structured-prediction framework using subgradient descent.
Results
The method achieves the best results reported so far on standardized benchmark tasks for query-focused extractive document summarization.
Takeaways & Limitations
Submodular shell mixtures offer an expressive structured-prediction score representation while retaining risk guarantees under approximate inference.
Takeaways & Limitations
Approximate inference is necessary because exact inference for the expressive shell scores is intractable, and naive approximate learning can produce poorly learned models.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies learning structured mixtures of submodular functions because learning arbitrary submodular functions is hard, then extends this idea to shell mixtures applicable across varying ground sets.
- Learning arbitrary submodular functions is difficult, with prior results ruling out constant-factor approximation in one learning-theoretic setting.
- Known submodular components can still be combined into conical mixtures whose weights are learned, motivating the problem of learning submodular mixtures.
- Submodular shells abstract functions that become instantiated submodular functions when supplied with a ground set and associated parameters.
- Shell mixtures support training across different ground sets, such as document collections whose sentence sets vary between examples.For document t, the ground set consists of its sentences, while β(t) can contain sentence term-frequency vectors.
- The paper introduces max-margin learning for shell mixtures and provides a risk bound when submodular maximization is approximate.
2 Structured Prediction
Structured prediction maps inputs to combinatorial outputs, but valid outputs can be exponentially numerous, making exact inference challenging and motivating structural assumptions.
- Structured prediction concerns domains whose inputs or outputs may be combinatorial structures rather than simple labels.
- For each input x, only a subset Yx of the possible outputs may be valid, such as valid parse trees for a sentence.
- The valid-output set Yx is typically still exponential in size, creating a primary computational challenge for structured prediction.
- Common solutions assume decomposable scores or exploitable combinatorial structure so dynamic programming, integer programming, or related algorithms can find good outputs.
3 Submodular Shell Scores
Submodular shell scores provide expressive, efficiently approximable structured predictors whose instantiated components are combined through learned nonnegative weights.
- Submodular shell score functions model global interactions among parts while retaining near-optimal maximization algorithms with rigorous guarantees.
- The hypothesis uses a nonnegative weight vector over shell components, making the instantiated weighted score submodular.
- Shell parameters α are shared across ground sets, whereas β is associated with each particular ground set and its instantiation.
- Training uses labeled structured instances, a loss function, and empirical risk minimization to learn conical mixture weights over shells.
- Shell mixtures can represent rich function families, including truncation-based functions, coverage-like functions, concave cardinality sums, and weighted matroid rank functions.
- Document-summarization functions based on coverage or diversity can also be viewed as mixtures of submodular shells.
4 Learning Submodular Shell Mixtures
The paper learns submodular shell mixtures with a large-margin structured-prediction procedure using projected subgradient descent. Because inference is approximate, it analyzes the resulting risk and establishes guarantees for undergenerating subgradient methods.
- Approximate Learning: Approximate learning is required because submodular maximization is NP-hard, and loss-augmented inference must also account for the loss function's form.When the loss is modular or submodular, a ρ-approximate inference algorithm can be applied to loss-augmented inference.
- Large Margin Learning: The large-margin objective learns component weights so the observed output scores above alternatives by a margin while minimizing generalized hinge loss and quadratic regularization.
- Large Margin Learning: Projected subgradient descent updates the weights using approximate loss-augmented inference and projects them onto the non-negative orthant to preserve submodularity.The update uses a dimension-wise maximum with zero after subtracting a step-size-scaled subgradient.
- Analysis: The analysis bounds the risk gap between efficient approximate learning and exact but intractable learning, rather than only approximating the exact learner's parameters.The additional risk is (R∗+(1−ρ)M)/ρ; it decreases as ρ increases and vanishes when ρ = 1.
- Analysis: Theorem 1 provides a risk bound for approximate learning with undergenerating subgradient methods, a case for which the paper states no prior generalization analysis was available.Greedy submodular maximization has approximation factor 1 −1/e and is usually close to 1 in practice, suggesting little additional risk in this setting.
5 Application to Document Summarization
The paper applies submodular shell mixture learning to extractive document summarization, modeling summary quality with expressive coverage and diversity functions. It also develops a submodular ROUGE-like loss that preserves efficient approximate inference and associated guarantees.
- Application: Submodular shell mixtures are applied to extractive document summarization as a case study.The task selects a subset of sentences from a document ground set.
- Loss and inference: The modified Pyramid score is monotone submodular, while the proposed ROUGE-like loss is monotone submodular and makes loss-augmented inference budgeted submodular maximization.This enables efficient near-optimal algorithms and preserves the theoretical analyses; empirically, the proposed loss outperforms 1 −fROUGE.
- Shell components: Coverage and diversity are modeled by generalized submodular shell components for summary scoring.The proposed class extends earlier functions that model both coverage and diversity.
- Shell components: Diversity components diminish the benefit of selecting multiple sentences from the same cluster.Clusters are generated by an algorithm, and singleton rewards determine the contribution of selected elements.
- Shell components: Clustered facility-location components count only the highest-reward representative when a summary contains multiple elements from one cluster.This construction yields diminishing returns within clusters and remains submodular.
- Shell components: Fidelity components use a saturation threshold to stop increasing coverage credit once an information element is sufficiently covered.The coverage functions are monotone submodular, and larger fidelity values tend to produce more well-covered elements.
6 Related work
The paper situates its shell-mixture approach relative to online submodular learning and large-margin summarization methods, emphasizing broader expressiveness and optimization guarantees.
- Prior online submodular-learning methods address feature-rich utility models or ranking under specialized assumptions and feedback settings.
- The earlier large-margin summarization representation is a special case of a submodular shell mixture.
- Shell mixtures preserve linearity in parameters when features are treated as inputs to submodular components, enabling Algorithm 1 for nonlinear score constructions.
- Unlike the compared approach, the shell-mixture method uses a submodular loss-augmented objective and nonnegative weight projection to preserve approximate-inference guarantees and submodularity.
7 Experiments
The experiments evaluate shell mixtures on generic and query-focused NIST DUC summarization benchmarks, using mixtures of fidelity, diversity, and clustered facility-location components. The method achieves the best reported results on DUC-05 through DUC-07 according to the paper.
- Query-independent summarization: 60 DUC-03 document clusters provide the generic-summarization training examples, with a 15-component fidelity mixture.
- Query-independent summarization: The generic model uses cosine similarities over unigram TF-IDF, bigram TF-IDF, and latent-semantic-analysis vectors, each with five saturation thresholds.
- Results: The learned shell mixture significantly outperforms previously reported results on generic summarization and achieves the best reported results on DUC-05, DUC-06, and DUC-07.Results from the compared prior work are not directly comparable because that work used a non-standard DUC-04 split with only five test documents.
- Query-focused summarization: DUC-06 and DUC-07 train the DUC-05 task, DUC-05 and DUC-07 train DUC-06, and DUC-05 and DUC-06 train DUC-07.
- Query-focused summarization: The query-focused mixture contains 6 clustered facility-location, 18 diversity, and 1 fidelity component, totaling 25 components.
8 Conclusions
The paper proposes learning submodular shells as an expressive structured-prediction framework and applies it to query-focused extractive summarization. It also provides a risk bound when inference is approximate.
- Submodular shells abstract families of submodular functions that can be instantiated using structured-prediction inputs.
- Projected subgradient descent learns mixture coefficients over shells that instantiate into weighted sums of submodular functions.
- The shell-mixture representation is expressive, and learning risk can be bounded when only approximate inference is possible.
- On standardized query-focused extractive summarization benchmarks, the approach achieves the best results reported so far.