Learning Determinantal Point Processes

By Alex Kulesza, B. Taskar. 2011

170 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Mathematical Physics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, background): “2 Learning Quality We begin by showing how to learn a parameterized quality model qi(X;θ) when the diversity feature function φi(X) is held fixed [85].”
Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity (2017, methodology): “Despite these theoretical guarantees, greedy algorithm is widely used for DPP due to its promising empirical performance [29, 19, 49].”
Recent advances in document summarization (2017, methodology): “2) submodular maximization [116, 117], parameterized [118, 172], volume maximization [93, 94, 61, 207],”
Near-Optimal MAP Inference for Determinantal Point Processes (2012, methodology): “in real-world scenarios [5, 13] has typically operated in this range.”
A Systematic Exploration of Diversity in Machine Translation (2013, methodology): “DPPs have been applied to summarization (Kulesza and Taskar, 2011) and discovery of topical threads in document collections (Gillenwater et al., 2012).”
Video Summarization with Long Short-Term Memory (2016, result): “This decomposition is similar in spirit to the quality-diversity (QD) decomposition proposed in [45].”
Diverse Sequential Subset Selection for Supervised Video Summarization (2014, methodology): “The notion of exclusion has made DPP an appealing tool for modeling diversity in application such as document summarization [14, 13], or image search and ranking [17].”
Mind the Gap: A Generative Approach to Interpretable Feature Selection and Extraction (2015, methodology): “Methods for inducing diversity, such as determinantal point processes [26], have been used to find diverse solutions on applications ranging from detecting objects in videos [27], topic modeling [28], and variable selection [29].”
Learning Mixtures of Submodular Shells with Application to Document Summarization (2012, unknown): “90 Kulesza and Taskar [23] 38.”