PaperlayerView exact revision on arXiv

Source-linked AI summary

Determinantal point processes for machine learning

Alex Kulesza, Ben Taskar

arXiv:1207.6083v4stat.MLcs.IRcs.LG

TL;DR

Structured probabilistic models face computational difficulty as interrelated decisions create combinatorial output spaces, especially with global negative interactions. This paper introduces DPPs for machine learning, develops their intuitions, algorithms, and extensions, and shows efficient inference alongside tractable and intractable cases.

  • Problem

    Structured output spaces create combinatorial inference problems, while global negative interactions remain intractable for graphical models and often defeat heuristic methods.

  • Method

    The paper introduces DPPs as probabilistic models of global negative correlations and develops parameterized conditional DPPs with learned log-linear quality scores.

  • Results

    DPPs support efficient sampling, marginalization, conditioning, and related inference, although finding their mode is NP-hard even to approximate within a factor of 8.

  • Takeaways & Limitations

    DPPs provide a machine-learning framework for modeling global negative correlations while sharing information across input-dependent training examples.

  • Takeaways & Limitations

    The L-ensemble representation requires an inverse that exists only when the DPP assigns nonzero probability to the empty set.

Abstract

from arXiv · show

Determinantal point processes (DPPs) are elegant probabilistic models of repulsion that arise in quantum physics and random matrix theory. In contrast to traditional structured models like Markov random fields, which become intractable and hard to approximate in the presence of negative correlations, DPPs offer efficient and exact algorithms for sampling, marginalization, conditioning, and other inference tasks. We provide a gentle introduction to DPPs, focusing on the intuitions, algorithms, and extensions that are most relevant to the machine learning community, and show how DPPs can be applied to real-world applications like finding diverse sets of high-quality search results, building informative summaries by selecting diverse sentences from documents, modeling non-overlapping human poses in images or video, and automatically building timelines of important news stories.

1 Introduction

DPPs provide probabilistic models of global negative correlations with efficient inference, offering a tractable alternative for structured outputs where graphical models struggle. The paper develops machine-learning-oriented foundations, algorithms, extensions, and applications for selecting diverse, high-quality sets.

  • Global negative interactions remain intractable in graphical models, while DPPs provide efficient algorithms for sampling, marginalization, conditioning, and other inference tasks.
  • DPPs are fully probabilistic models of diversity, unlike several related diverse-set methods, while retaining algorithmic tractability.
  • The paper applies DPPs to diverse news summarization, image search, human pose estimation, and news threading.
  • The paper presents mathematical background, modeling extensions, efficient algorithms, and theoretical results intended to support practical modeling and learning.
  • Representation and algorithms: Its representation and algorithm sections expose quality–diversity tradeoffs, compare DPPs with MRFs, and develop dual inference and random-projection approximations.
  • Structured DPPs: Structured DPPs make efficient inference possible for diverse sequences or trees and are demonstrated on paths, pose estimation, and text threading.

2 Determinantal point processes

DPPs emerged from quantum physics and random matrix theory, where they describe repulsive or anti-bunching phenomena. The paper introduces this background before focusing on machine-learning-relevant intuitions, algorithms, and computational properties.

  • Macchi identified DPPs as “fermion processes” because they describe fermion systems at thermal equilibrium and their anti-bunching behavior.
  • Specific DPPs appeared earlier in major random matrix theory results, and the mathematics community later developed extensive theory and surveys.
  • The paper’s overview emphasizes the aspects of DPPs most relevant to machine learning, including intuitions, algorithms, and computational properties.

2.1 Definition

A DPP assigns probabilities to subsets while encoding nonpositive correlations through determinants of a marginal kernel. Its examples and geometric interpretation show how repulsion favors spread-out, diverse configurations.

  • A point process is a probability measure over finite subsets, capturing whether points cluster, occur independently, or spread apart.
  • The paper focuses on discrete finite ground sets, treating items as elements of Y = {1, 2, . . . , N}.
  • In a discrete DPP, subset-inclusion probabilities are determinants of principal submatrices of a marginal kernel K.
  • A valid marginal kernel satisfies 0 ⪯ K ⪯ I, and its diagonal entries give individual inclusion probabilities.
  • Large off-diagonal kernel entries indicate negative pairwise correlations, making similar items less likely to co-occur.
  • DPP samples spread points relatively uniformly, unlike independent sampling, which produces random clumping.
  • Examples: DPPs describe diverse structures including descents, non-intersecting random walks, spanning-tree edges, random-matrix eigenvalues, and Aztec-diamond tilings.

2.2 L-ensembles

L-ensembles represent DPPs with a positive semidefinite similarity matrix L, assigning subset probabilities through determinants normalized by det(L + I). Their geometric interpretation makes the quality–diversity tradeoff explicit, while K and L provide complementary representations.

  • Definition: An L-ensemble assigns each subset Y probability det(L_Y) / det(L + I), with L positive semidefinite.The normalization follows from summing determinants over all subsets.
  • Representations: The marginal kernel is K = I − (L + I)^−1, so L and K offer alternative representations of the same DPP.The conversion can be performed using an eigendecomposition.
  • Limitations: L-ensembles exclude DPPs assigning zero probability to the empty set, because Equation (25) requires an inverse that fails when a K eigenvalue equals 1.The paper notes that k-DPPs can sidestep this representational limit by controlling sample cardinality.
  • Representations: L directly models atomic subset probabilities, whereas K provides marginal probabilities; this motivates focusing modeling efforts on L-ensembles.L need only be positive semidefinite, while K's eigenvalues are bounded above.
  • Geometry: In the feature-vector view, subset probability is proportional to squared spanned volume, favoring large-magnitude and mutually orthogonal vectors.Parallel feature vectors yield zero probability of joint selection.

2.3 Properties

DPP properties explain how marginal kernels control inclusion, deletion, complements, cardinality, and ordering-related behavior. These properties support both interpretation and flexible control over sampled subsets.

  • Closure properties: Restricting a DPP to a subset A produces another DPP with marginal kernel K_A.The kernel is restricted to the retained elements.
  • Closure properties: The complement of a DPP is also a DPP, with marginal kernel I − K.The complement remains diversifying because non-inclusion events inherit negative dependence.
  • Scaling: Scaling K by γ, where 0 ≤ γ < 1, is equivalent to independently deleting each selected element with probability 1 − γ.This yields the distribution associated with K = γK′.
  • Cardinality: The sample cardinality is distributed as the number of successes in N Bernoulli trials with success probabilities λ_n/(λ_n + 1), so it cannot exceed rank(L).The eigenvalues of K are λ_n/(λ_n + 1).
  • Cardinality: Fixing cardinality can be preferable when applications require a predetermined number of selected items, such as exactly ten search results.The paper introduces k-DPPs for this purpose elsewhere.

2.4 Inference

DPPs support exact marginalization, conditioning, and sampling despite an exponential number of possible subsets, although matrix operations determine practical scale and mode finding remains NP-hard.

  • Computational scope: Although DPP realizations are exponential in N, many inference tasks can be performed in polynomial time.The section evaluates computational practicality under interactive and more generous resource constraints.
  • Normalization: Determinants can be computed in O(N^3) time by matrix decomposition, with faster asymptotic bounds available through matrix multiplication.The paper cites approximately O(N^2.376) using Coppersmith–Winograd.
  • Normalization: N ≈ 5,000 supports interactive determinant computation, while N ≈ 40,000 takes about five minutes; memory becomes limiting beyond that scale.Sparse storage helps only when sparsity is extreme because determinant computation remains expensive.
  • Marginalization: Marginalization uses the marginal kernel, whose computation is dominated by matrix inversion requiring at least O(N^ω) time or O(N^3) with standard methods.Eigendecomposition is often practical because it is also central to sampling.
  • Conditioning: Conditional DPPs remain DPPs under natural appearance and non-appearance constraints, and conditioning costs at most a small constant factor more than marginalization.Conditioning only on non-appearance can avoid an inversion in some cases.
  • Sampling: The sampling algorithm selects eigenvectors according to eigenvalue-dependent probabilities, then iteratively selects items while orthogonalizing the remaining subspace.Its output is generated in uniformly random order.
  • Mode finding: Finding the most probable subset is NP-hard, including under cardinality constraints, and approximating it within a factor of 8/9 + ε is NP-hard.The hardness applies to maximizing det(L_Y) over subsets.

2.5 Related processes

Related point-process models capture independence, spatial repulsion, clustering, or general interactions, but often trade intuitive constructions for difficult inference. DPPs are distinguished by efficient exact inference, while broader determinant-based generalizations retain important open computational questions.

  • DPPs and related processes: DPPs are essentially unique among diverse-subset point processes in offering efficient and exact algorithms for probabilistic inference.This computational property makes them especially appealing for machine learning applications.
  • Poisson point processes: Poisson point processes include items independently, making inference efficient but modeling no correlations between selected items.They can be represented as DPPs with a diagonal marginal kernel.
  • Procedural processes: Procedural modifications of Poisson processes introduce correlations through intuitive constructions, but general statistical inference becomes difficult.This limitation motivates more holistic process definitions.
  • Matérn and RSA processes: Matérn processes enforce spatial repulsion through thinning and minimum-distance rules, but their likelihoods or moments are generally computationally difficult.For general Type III processes, likelihood estimation requires expensive Markov chain Monte Carlo.
  • Gibbs and Markov processes: Gibbs and Markov point processes provide general frameworks for modeling correlations through energy functions and local interaction potentials.Pairwise Markov processes commonly define interactions through functions of item distance.
  • Generalizations of determinants: α-determinantal processes interpolate between determinant and permanent cases, but their modeling usefulness and computational advantages remain open questions.The determinant is recovered at α = −1, while the permanent occurs at α = +1.

3 Representation and algorithms

This section decomposes DPPs into quality and diversity components, compares their expressive power and tractability with MRFs, and develops representations and algorithms for efficient inference and approximation.

  • Quality vs. diversity: The kernel decomposition separates item quality from global diversity and implicitly enforces positive semidefiniteness.This supports independent modeling of the two components while simplifying learning.
  • Expressive power: DPPs combine global negative interactions with efficient exact probabilistic inference, unlike general MRFs whose inference is NP-hard.The comparison targets whether DPP tractability entails a substantial expressive cost.
  • Comparing DPPs and MRFs: DPPs and MRFs have comparable parameter counts but differ structurally: DPP constraints are global, whereas MRF edge potentials are individually nonpositive.This global constraint enables representational behaviors unavailable to locally constrained pairwise MRFs, while MRFs can capture some limited positive correlations.
  • Comparing DPPs and MRFs: DPPs can represent context-dependent global repulsion, such as limiting the total number of selected items, which pairwise MRFs cannot express effectively.A pairwise MRF cannot exclude a set of three or more items without excluding some pair among them.
  • Representations and algorithms: The dual representation makes normalization and marginalization constant-time in N, sampling linear in N, and determinant computation O(D^ω).For a subset A of size k, computing its inclusion probability requires O(D^2k^2 + k^ω) time; the complete dual sampler runs in O(NDk^2 + D^2k^3).
  • Approximation: Random projections reduce diversity-feature dimension while providing theoretical guarantees that approximate the original DPP and preserve volumes spanned by k columns.The approximation guarantee includes probability at least 1 −δ, with e^6kε −1 approximately 6kε when kε is small.

4 Learning

This section develops conditional DPPs that share information across variable-sized inputs, then learns quality parameters efficiently for diverse extractive summaries. On DUC 2004, DPP models outperform most baselines, with training and inference choices producing distinct performance–speed trade-offs.

  • 4.1 Conditional DPPs: Conditional DPPs make the ground set depend on input data, enabling information sharing across training examples and prediction on unseen inputs.For summarization, the ground set is the set of sentences in each news article or document cluster.
  • 4.1 Conditional DPPs: The model uses an input-dependent positive semidefinite kernel with quality and diversity components, while its normalization is computable as det(L(X)+I).The quality scores and diversity feature representations both depend on the input.
  • 4.2 Learning quality: The learning setup estimates parameters from input–subset training pairs by maximizing conditional log-likelihood to support accurate predictions on unseen inputs.The quality model is parameterized while the diversity feature function is held fixed, and quality scores use a log-linear model.
  • 4.2.1 Experiments: document summarization: DPP models outperform most DUC 2004 baselines, while maximum-likelihood training significantly improves performance over logistic-regression training.MBR inference performs best with sufficiently many samples, whereas greedy inference is faster than dpp-mbr100 and still yields superior results.
  • 4.2.1 Experiments: document summarization: Length and position features are important, while jointly removing similarity and LexRank features causes a significant performance drop.The joint effect suggests that similarity and LexRank convey related information.

5 k-DPPs

k-DPPs address the mismatch between DPP cardinality models and applications requiring fixed or alternative set sizes by conditioning on the number of selected items. They preserve diversity modeling while enabling exact polynomial-time inference and support controlled, diverse image-search results.

  • Motivation: Standard DPPs can assign implausible cardinalities, and their size and content models are fundamentally intertwined.They may produce empty or full sets, cannot represent the uniform distribution over k-sized sets, and impose a sum-of-Bernoullis cardinality model.
  • Model: k-DPPs condition a DPP on cardinality k, separating the content model from a task-chosen size model.This allows the desired set size to be fixed based on context while retaining the DPP’s diversifying properties.
  • Algorithms: Recursions for elementary symmetric polynomials make k-DPP normalization and sampling exactly solvable in polynomial time.The sampling procedure runs in O(Nk^3), while computing the necessary polynomials for singleton marginals takes O(N log(N)k^2).
  • Model: k-DPPs are more expressive than standard DPPs and can model both negative and positive correlations under suitable size models.A size model with either many or few items can make observing many items increase the likelihood of more items.
  • Experiments: image search: The image-search experiment uses k-DPPs to return query-relevant results that are diverse while controlling the number of results.The evaluation compares candidate result sets using human judgments; a learned mixture of k-DPPs achieves the best performance across categories.
  • Experiments: image search: A learned mixture of k-DPPs performs 14.58 percentage points above random in the cars category, compared with 9.59 points for MMR with a mixture of kernels.Across three categories, k-DPPs outperform MMR on two at 99% confidence, while the learned mixture of k-DPPs is best in all cases.

6 Structured DPPs

Structured DPPs extend DPPs to diverse sets of structured objects whose configurations are exponentially numerous. By combining dual DPP representations, dynamic programming, and second-order message passing, the paper obtains polynomial-time inference and applies the model to several structured prediction tasks.

  • Motivation: M^100 possible paths make explicit enumeration and construction of an M^100 × M^100 kernel infeasible.This illustrates the computational challenge created by structured items over many time steps.
  • Method: SDPP inference combines structured-prediction dynamic programming with dual DPP inference and second-order message passing.The dual representation is smaller than the kernel, while the specialized message-passing structure computes the needed quadratic quantities.
  • Results: SDPPs can normalize and sample in polynomial time under the proposed structured computations.The paper applies these methods to multiple human poses, citation-chain research lines, and news-text threads.
  • Motivation: Structured DPPs model diverse sets of objects such as sequences and trees despite their combinatorially many configurations.Structured representations can support diverse translations, protein alternatives, human poses, citation chains, and news threads.
  • Results: Random projections can substantially reduce computation and memory while maintaining a close approximation to the original model.The paper reports improved results over standard and heuristic baselines in the experimental settings.

6.1 Factorization

Structured DPPs factor quality multiplicatively and diversity additively over small subsets of structure parts. This factorization supports tractable modeling and gives intuition for why diversity suppresses near-duplicate trajectories while preserving high-quality alternatives.

  • Structured representation: Structured items consist of R parts, each taking one of M values, so the ground set contains N = M^R possible structures.A basketball-player path is represented by one discretized position for each recorded time step.
  • Factorization: The quality model decomposes multiplicatively over small factors, while diversity features decompose additively over those factors.Keeping factor scope small is required for tractability, and the decomposition parallels structured graphical models.
  • Tracking example: Positional factors score individual parts, whereas transitional factors score adjacent parts and can encourage smooth trajectories.In the tracking example, positional factors prefer high-traffic locations and transition factors enforce temporal smoothness.
  • Tracking example: Diversity features make trajectories that pass through similar positions appear similar, reducing their likelihood of co-occurring.The tracking features ignore the time at which a particle reaches a position, and transitional-factor diversity features are zero.
  • Tracking intuition: SDPP samples combine quality with repulsion, which is especially important because combinatorially many slightly perturbed paths can resemble a high-quality path.Independent sampling can therefore overproduce near-duplicates, while the diversity model suppresses them.
  • Tracking experiment: In the synthetic tracking experiment, SDPP trajectories are compared with independently sampled trajectories weighted only by quality scores.The model is scaled to produce an expected five trajectories, and Figure 17 contrasts the resulting samples.

6.2 Second-order message passing

Second-order message passing computes the dual quantities required for structured DPP inference without enumerating exponentially many structures. Under bounded factors and a tree or low-treewidth factor graph, the resulting computations remain efficient in the number of parts.

  • Computational challenge: Because N = M^R is exponentially large, ordinary DPP inference over the structured ground set is intractable.The dual representation C replaces the enormous kernel representation with a smaller representation.
  • Dual computation: Computing C directly through pairwise factor marginals is quadratic in the number of factors and their possible realizations.This direct approach becomes expensive when structures are large.
  • Second-order message passing: Factorizing the model yields an expression for C that can be computed in linear time using second-order message passing.The method computes second-order statistics over the graphical model with a specialized semiring.
  • Factor graphs: A factor graph contains variable nodes for structure parts and factor nodes for local factors, with edges encoding factor membership.The tracking example uses positional single-part factors and binary transitional factors.
  • Structural assumptions: Efficient inference assumes bounded factor degree and a tree or low-treewidth factor graph.The paper notes that arbitrary factors can contain all parts and assign values to every configuration, preventing efficient computation.
  • Belief propagation: Belief propagation computes combinatorial sums in O(M^cR) time when each factor has degree at most c.Each message considers at most M^c assignments, even though the corresponding global sum is exponential in the number of parts.
  • Semirings: Replacing ordinary operations with a carefully designed semiring lets belief propagation sum second-order quantities while retaining linear-time message passing.The paper identifies this operation as the key tool for efficient SDPP inference.

6.3 Inference

Structured DPP inference uses dual representations and second-order message passing to compute marginals and sample exponentially many structures efficiently. The resulting sampling algorithm runs in O(D^2k^3 + DM_cRk^2) time.

  • Structured DPP inference: A factorization of quality and diversity models, combined with the dual representation, enables tractable normalization, marginalization, and sampling for structured DPPs.Efficiency requires bounded-size factors forming a low-treewidth graph.
  • Computing marginals: Second-order message passing computes the dual matrix C in O(D^2M_cR) time from D(D+1)/2 unique entries.
  • Computing marginals: Part marginals require D separate belief-propagation applications, for total runtime O(D^2M_cR), with the same asymptotic cost for all or one part marginal.
  • Sampling: A naive sampler repeatedly runs belief propagation, whereas integrated sampling weaves sampling steps into one message-passing traversal.The naive method is polynomial but can be prohibitively expensive for large structures.
  • Sampling: The final SDPP sampler draws complete structures using conditional marginals and runs in O(D^2k^3 + DM_cRk^2) time.Here k is the number of selected eigenvectors; orthonormalization is asymptotically dominant.

6.4 Experiments: pose estimation

The pose-estimation experiment applies structured DPPs to select multiple human poses while balancing detector quality against spatial diversity. Compared with independent and non-maximum-suppression baselines, the SDPP improves F1 at larger acceptance radii through higher recall.

  • Task and data: The task identifies multiple people’s poses in still images, representing each pose with torso, head, and arm parts.The dataset contains 73 annotated television-show frames.
  • Model: A factorized SDPP is needed because each part has approximately 75,000 possible values, producing about 4^75,000 possible poses.The pose structure is modeled as a two-level tree with the torso as root and head and arms as leaves.
  • Model: The diversity features encode constituent-part locations, making spatially overlapping poses more similar and therefore less jointly preferred.A held-out training set selects the kernel width σ.
  • Baselines: The SDPP prefers spatially diverse poses without requiring separation, allowing strong image evidence to override the diversity preference.Baselines include independent sampling and non-maximum suppression.
  • Results: As acceptance radius increases, the SDPP significantly outperforms both baselines; its higher F1 comes from increased recall at the cost of precision.
  • Results: During sampling, structured marginals discount but do not entirely preclude poses similar to those already selected.Figure 22 visualizes these changing marginals as probability clouds.

6.5 Random projections for SDPPs

Random projections reduce the diversity-feature dimension of structured DPPs to make inference feasible while preserving a close approximation to the original model. In a geographical-path task, projected k-SDPPs retain quality and geographic diversity, with diminishing gains beyond d ≈25.

  • Motivation: Structured DPP inference can become memory-limited because eigendecomposition costs O(D^3), while normalization, marginalization, and sampling scale quadratically in D.For D ≈30,000, a single belief-propagation message would require over 200 terabytes without dimensionality reduction.
  • Projection method: Random projections reduce diversity-feature dimension while retaining a provably close approximation under the required cardinality condition.The projection dimension must be logarithmic in labels and linear in the number of parts.
  • Geographical paths: The toy application models diverse, high-quality sets of four-stop travel routes over 200 cities using a factored k-SDPP.Quality favors popular cities and short routes, while diversity favors different geographic regions.
  • Geographical paths: As k increases, sampled paths show more configurations while continuing to emphasize popular cities and geographic diversity.
  • Projection results: Past d ≈25, approximation improvements fall sharply while memory and running-time costs become significant.The authors conclude that aggressive random projection is theoretically and empirically justified.

6.6 Experiments: threading graphs

Graph threading uses k-SDPPs to extract diverse, salient threads from large document graphs. The model jointly balances thread quality, diversity, controllable length and count, and computational efficiency across citation and news collections.

  • Task: Graph threading extracts diverse, salient singly connected chains from directed graphs of interrelated objects such as papers or news articles.For news, threads can represent timelines of major events.
  • Task: Unlike query-based search, a set of threads provides a concise high-level summary while conveying relationships among important objects.
  • Model: k-SDPP graph threading jointly addresses related text-analysis tasks with a global probabilistic model and tractable inference.
  • Model: The model aims to control thread quality, diversity, length, and count while remaining efficient in time and memory.
  • Inference: Random projection, second-order message passing, dual eigendecomposition, and k-DPP sampling produce thread sets from projected graph features.
  • Citation results: For citation graphs, sampled threads summarize distinct topics and salient terms while illustrating each area’s content and development.
  • News results: On news data, k-SDPP threads more closely resemble human summaries under every reported metric and receive significantly higher coherence ratings.
  • News results: Thanks to random projections, the k-SDPP is both the most faithful to human news summaries and fastest by a large margin.

7 Conclusion

The paper concludes that DPPs offer practical possibilities for diverse real-world data while retaining coherent probabilistic semantics and computational tractability. It also identifies unresolved theoretical and machine learning questions for future research.

  • DPPs offer exciting possibilities for a wide range of practical applications while remaining computationally efficient.
  • The Shannon-entropy conjecture that H(K) is concave in K remains unproved despite strong numerical support.
  • Efficient computation of quantities needed for distances such as the Hellinger distance remains unknown for p > 1.
  • Open machine learning questions include kernel choices, conditional independence, constrained inference, and learning similarity kernels from labeled data.
  • Further research could examine efficient inference for SDPPs over loopy factor graphs and their use in diversifying n-best lists.
Loading 1207.6083v4…