Source-linked AI summary
Learning Determinantal Point Processes
Alex Kulesza, Ben Taskar
TL;DR
The paper addresses how to learn DPPs from labeled data for subset-selection problems requiring both relevance and diversity. It introduces feature-based conditional DPPs with convex, efficient learning and applies them to extractive summarization, where experiments on DUC data achieve state-of-the-art performance.
Problem
Learning DPPs from labeled data remains an open question for subset-selection tasks that must balance relevance with diversity.
Method
The paper parameterizes conditional DPPs with features, enabling convex maximum-likelihood learning and efficient inference for input-dependent candidate sets.
Results
Experiments on the DUC 2004 multi-document summarization task demonstrate state-of-the-art performance.
Takeaways & Limitations
Conditional DPPs provide a model that combines high-quality and diverse selections while retaining tractable learning and inference.
Takeaways & Limitations
Exact MAP inference is NP-hard, so the paper uses sampling or a greedy submodular approximation; efficient learning of the similarity matrix remains open.
Abstract
from arXiv · showhide
Determinantal point processes (DPPs), which arise in random matrix theory and quantum physics, are natural models for subset selection problems where diversity is preferred. Among many remarkable properties, DPPs offer tractable algorithms for exact inference, including computing marginal probabilities and sampling; however, an important open question has been how to learn a DPP from labeled training data. In this paper we propose a natural feature-based parameterization of conditional DPPs, and show how it leads to a convex and efficient learning formulation. We analyze the relationship between our model and binary Markov random fields with repulsive potentials, which are qualitatively similar but computationally intractable. Finally, we apply our approach to the task of extractive summarization, where the goal is to choose a small subset of sentences conveying the most important information from a set of documents. In this task there is a fundamental tradeoff between sentences that are highly relevant to the collection as a whole, and sentences that are diverse and not repetitive. Our parameterization allows us to naturally balance these two characteristics. We evaluate our system on data from the DUC 2003/04 multi-document summarization task, achieving state-of-the-art results.
1 INTRODUCTION
Subset selection often requires balancing item relevance against group diversity, a challenge illustrated by extractive summarization. The paper introduces learnable conditional DPPs with convex, efficient training and applies them to summarization.
- Motivation: Subset selection tasks seek high-quality, diverse item sets, including summaries that cover important information without repetition.In summarization, relevance to the document collection must be balanced against diversity among selected sentences.
- DPPs: DPPs naturally model negative correlations and support exact polynomial-time inference for marginals, conditional probabilities, and sampling.Their tractability makes them attractive for diversity-oriented selection despite being less general than Markov random fields.
- Contribution: The paper addresses learning DPPs from data by proposing conditional DPPs with convex and efficient maximum-likelihood learning.It also develops exact and efficient feature-expectation computation during training.
- Evaluation: The approach is evaluated on extractive multi-document summarization using DUC 2004 data and reported as state of the art.The paper organizes this evaluation after developing the model, learning procedure, and inference methods.
2 DETERMINANTAL PROCESSES
DPPs define subset probabilities through determinants, yielding negative dependence and efficient inference. Their L-ensemble and quality–similarity decomposition provide an interpretable representation for diverse subset selection.
- Definition: A DPP assigns inclusion probabilities through determinants of submatrices of a positive semidefinite marginal kernel K.For every subset A, P(A ⊆ Y) = det(K_A), with K constrained by K ⪯ I.
- Negative dependence: DPPs encode negative correlations: large off-diagonal kernel entries indicate that item pairs tend not to co-occur.They therefore cannot represent positive co-occurrence correlations relative to independence.
- Intuition: DPP sampling spreads points for coverage, unlike independent sampling, which can produce random clumping.This geometric behavior motivates DPPs for selecting diverse items such as summary sentences.
- L-ensembles: An L-ensemble represents subset probabilities as det(L_Y) / det(L + I), using a positive semidefinite kernel L.L-ensembles directly model atomic subset probabilities and are convenient for optimization.
- Quality and diversity: The Gram decomposition separates item quality from similarity, combining both so quality raises selection likelihood while similarity reduces joint selection.The decomposition also enforces positive semidefiniteness and supports an interpretable geometric view through squared volumes.
- Inference: DPPs support efficient marginals, normalization, conditional probabilities, and inclusion or exclusion probabilities despite exponentially many possible subsets.These operations can be computed using eigendecompositions of L and related matrices.
3 DPPs VS. MRFs
DPPs and repulsive MRFs can both model negative correlations, but their constraints differ for three or more items. DPP positive semidefiniteness imposes transitive similarity structure that limits representational flexibility.
- Model comparison: The repulsive MRF paired with a DPP uses negative pairwise interactions, while the DPP kernel is subject to a global positive semidefinite constraint.MRF interaction weights are individually constrained to be nonpositive; DPP similarities additionally obey transitivity-like structure.
- N = 2: For N = 2, MRFs and DPPs are equivalent because both can represent every negatively correlated binary distribution.The equivalence is characterized by P(y1 = 1)P(y2 = 1) ≥ P(y1 = 1, y2 = 1).
- N = 3: For N = 3, the models have equal parameter counts but generate different realizable ternary-factor manifolds.The comparison represents both models with node potentials and one ternary factor, then examines two-dimensional slices.
- Representational difference: DPP transitivity prevents one item from being strongly anti-correlated with two others while those two remain unrelated, a pattern an MRF can represent.When negative correlations are weak, the two models are qualitatively similar; stronger interactions expose the difference.
4 CONDITIONAL DPPs
The paper introduces conditional DPPs for selecting subsets from input-dependent candidate sets, particularly sentences in document clusters. Feature-based quality scores and similarity representations make the model suitable for discriminative learning.
- Conditional model: A conditional DPP assigns probabilities to subsets of an input-dependent candidate set Y(X), such as sentences from a document cluster.Summarization additionally imposes a total-length constraint on the selected sentences.
- Kernel representation: The conditional model uses an input-dependent positive semidefinite kernel L(X), whose normalization is efficiently computed as det(I + L(X)).This retains the L-ensemble form while conditioning the distribution on the input.
- Feature parameterization: The kernel decomposition uses quality scalars q_i(X) and normalized similarity vectors φ_i(X), allowing flexible similarity features.Similarity features may be arbitrary measurements, including infinite-dimensional features when they define a proper kernel.
- Feature parameterization: Quality is modeled with a log-linear feature model using f_i(X) and parameters θ, while similarity features φ_i(X) serve a distinct role.The paper explicitly separates features for item quality from features measuring item similarity.
5 LEARNING
The model learns conditional DPP parameters by maximizing training-set log-likelihood, yielding a concave objective whose gradient can be computed efficiently from DPP marginals.
- The training data pairs each input X_t with a selected subset Y^t, and parameters θ are learned by maximizing the training-set log-likelihood.
- The log-likelihood is concave in θ because its parameter-dependent terms are linear or a concave negative log-sum-exp composition.
- The likelihood gradient equals empirical feature counts minus expected feature counts under the model distribution.
- 21? The expected-count sum is exponential in |Y(X)|, so the method rewrites it using DPP marginal inclusion probabilities instead of enumerating subsets.The supplied passage numbers do not support beginning the sentence with a numeric figure; the computational issue and remedy are supported by the cited passages.
- DPP marginal probabilities come from the diagonal of the marginal kernel K, which eigendecomposition computes efficiently for the gradient algorithm.
6 MAP INFERENCE
At test time, the paper predicts a set for an unseen input using either exact DPP sampling or a budget-constrained MAP set. Because exact MAP inference is NP-hard, the paper considers sampling-based and greedy submodular approximations, with the latter working well in practice despite nonmonotonicity.
- Inference choices: Exact sampling from the conditional DPP is possible in cubic time, but the authors found better performance with a budget-constrained MAP set.The budget limits total item cost to B.
- Approximation: Computing the MAP set exactly is NP-hard, motivating approximate inference methods.The paper considers both brute-force sampling and greedy optimization.
- Approximation: A brute-force approximation samples many sets and selects the highest-probability feasible set under the budget constraint.Only sampled sets satisfying the total-cost budget are considered.
- Approximation: A more practical approximation exploits submodularity and uses a simple greedy algorithm for the MAP optimization.The greedy approach targets the budget-constrained objective described in the section.
- Approximation: Although related monotone-submodular algorithms have formal guarantees, this MAP problem is not generally monotone; nevertheless, the proposed algorithm works well in practice.The algorithm is closely related to methods by Lin and Bilmes (2010) and Krause and Guestrin (2005).
7 SUMMARIZATION
The summarization experiments learn extractive summaries from DUC data using oracle targets, tf-idf-based features, and several inference and baseline methods. Evaluation uses ROUGE on DUC 2004, with preprocessing and summary-length choices defining the comparison setting.
- Data and task: The model selects candidate sentences from document clusters and outputs them in their original document order.The candidate set contains all cluster sentences, although preprocessing may narrow it.
- Evaluation: ROUGE-1F is the primary metric, supplemented by ROUGE-1P, ROUGE-1R, ROUGE-2F, and ROUGE-SU4F under DUC-matching settings.ROUGE compares n-gram overlap with human reference summaries; the implementation uses stemming without stopword removal.
- Training targets: Oracle extractive training summaries are built greedily by adding the sentence with maximal mean unigram F-measure and removing covered reference words.This procedure targets high precision and recall against human references.
- Experimental setup: Training uses DUC 2003, testing uses DUC 2004, and L-BFGS optimization selects parameters with a Gaussian prior.The prior variance is tuned on a development subset using ROUGE-1F.
- Inference and baselines: The expensive MAP comparison samples 10^6 summaries, while baselines include the first 665 bytes and DUC 2004 systems, including SubMod.Overlong sampled summaries are trimmed to 665 bytes; Table 2 reports all-method results on DUC 2004, with updated ROUGE scores for actual competitors.
8 CONCLUSION
The paper applies DPPs to subset selection, using their quality–diversity tradeoff for extractive summarization and identifying broader applications and open directions.
- DPPs model subset selection by balancing high-quality items against diversity that reduces redundancy and increases coverage.
- The approach achieves state-of-the-art performance on the DUC 2004 multi-document summarization task.
- Learning DPPs may also support search systems that return relevant results covering multiple interpretations of ambiguous queries.
- Future summarization work includes combining extractive selection with internal sentence compression to produce more informative summaries.
- Efficiently learning the similarity matrix remains an open question that could enable more expressive DPP models.