vault

Determinantal Point Processes

6 min read

Determinantal Point Processes

Determinantal Point Processes (DPPs) are a class of probability distributions over subsets of a fixed ground set that favor diverse subsets. The name reflects the mathematical structure: the probability of a particular subset is proportional to the determinant of a kernel submatrix indexed by the items in the subset. In recommendation, DPPs provide a probabilistic alternative to the greedy re-ranking of Maximal Marginal Relevance: rather than greedily picking items one by one based on a heuristic relevance-vs-similarity tradeoff, a DPP gives a principled probability distribution over diverse subsets and can sample from it (or find the maximum-a-posteriori subset). The most influential application of DPPs to recommendation is Chen, Zhang & Zhou’s NeurIPS 2018 paper “Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity”, which provided a fast greedy MAP-inference algorithm tractable for production use, plus YouTube’s CIKM 2018 deployment description which detailed the production engineering. DPPs are increasingly used at companies that need stronger diversity guarantees than MMR provides, although MMR remains more common because of its simplicity.

1. The Mathematical Object

A DPP over a finite ground set Y = {1, 2, ..., N} is parameterized by a positive semi-definite kernel matrix L ∈ ℝ^{N × N}. The probability of a subset S ⊆ Y is:

P_L(S) ∝ det(L_S)

where L_S is the submatrix of L indexed by the rows and columns in S, and det(·) is the determinant. The proportionality constant normalizes over all possible subsets.

The key intuition: the determinant of a positive semi-definite matrix is the volume of the parallelepiped spanned by its rows (or columns). Two highly-similar items have rows that are nearly parallel, yielding small determinant (small volume — collapsed parallelepiped). Two dissimilar items have rows that are more orthogonal, yielding larger determinant (larger volume). Diverse subsets — where items are mutually dissimilar — therefore get higher probability.

The kernel L encodes both quality (via its diagonal: L_{ii} is the squared “quality” of item i) and similarity (via its off-diagonal: L_{ij} = q_i · q_j · sim(i, j) where sim(i, j) is a similarity between items i and j). A common parameterization:

L_{ij} = q_i · q_j · ⟨φ_i, φ_j⟩

where q_i ≥ 0 is the quality of item i (e.g., its predicted relevance score) and φ_i ∈ ℝ^k is a feature vector for item i (e.g., its content embedding). The dot product ⟨φ_i, φ_j⟩ is the similarity.

2. The Two Inference Tasks

DPPs support two natural inference tasks for re-ranking:

Sampling. Draw a random subset from the DPP. Each draw gives a stochastically diverse subset; multiple draws give multiple diversity-aware recommendation lists. Sampling from a DPP is tractable in O(N · K²) for a K-sized subset using the standard sampling algorithm (involving the eigendecomposition of L).

MAP (Maximum A Posteriori) inference. Find the subset S that maximizes P_L(S). This is the deterministic “best diverse subset of size K” problem. MAP inference for DPPs is NP-hard in general, but greedy approximations exist that perform well in practice.

The Chen, Zhang & Zhou 2018 paper’s contribution was a fast greedy MAP-inference algorithm that updates a Cholesky factor incrementally as items are added to S. The total cost for selecting K items from N candidates is O(N · K²) — same as MMR — and the empirical quality of the resulting subset is competitive with exact MAP.

3. The Greedy MAP Algorithm

Given a DPP with kernel L:

S = []
while |S| < K:
    next_item = argmax_{i ∈ Y \ S}  log det(L_{S ∪ {i}})  -  log det(L_S)
    S.append(next_item)

The expression log det(L_{S ∪ {i}}) − log det(L_S) is the log-marginal-gain of adding item i to S. Standard properties of determinants give a closed-form expression for this gain in terms of i’s relationship to the items already in S:

log det(L_{S ∪ {i}}) − log det(L_S) = log( L_{ii} − L_{i, S} · L_S^{-1} · L_{S, i} )

The right-hand side is a Schur-complement-style term measuring how much new “volume” item i adds. The Cholesky factorization of L_S is maintained incrementally as S grows, making each step O(K²).

4. Comparison with MMR

DPPs and MMR both produce greedy diverse subsets. The differences:

Theoretical foundation. DPPs are a probability distribution with mathematical properties (sub-modularity, repulsion, marginalization). MMR is a heuristic without a probabilistic interpretation.

Marginal gain calculation. DPPs compute the marginal gain via the determinant Schur complement, which captures all pairwise interactions with already-selected items (not just the maximum). MMR uses just the max similarity to the closest already-selected item.

Tunability. DPPs are tuned by the kernel parameterization (quality q_i, similarity sim(·, ·)), which gives more design flexibility than MMR’s single λ knob.

Empirical results. DPPs typically produce more globally diverse subsets than MMR. The gap is application-dependent.

For most production deployments, MMR is adequate. DPPs are deployed when the diversity requirements are stronger or when the probabilistic interpretation is valuable.

5. The YouTube Deployment

Wilhelm, Ramanathan, Bonomo, Jain, Chi, Gillenwater (CIKM 2018) describe YouTube’s deployment of DPP-based diverse recommendation. Notable engineering choices:

  • Scaled MAP inference. YouTube’s candidate set is large (~hundreds); the greedy MAP algorithm is run per request.
  • Quality-similarity decomposition. The kernel uses learned item quality scores and content-feature similarities.
  • A/B test improvements. The deployment showed measurable improvements in user satisfaction metrics over MMR.

This paper was one of the first detailed industrial descriptions of DPP-based diversity re-ranking and helped popularize the approach.

6. When to Use DPPs

DPPs are appropriate when:

  • Diversity is a critical objective and MMR’s heuristic does not produce adequate results.
  • The candidate set is small enough for the O(N · K²) greedy MAP (typically N ≤ ~1000).
  • A principled probability distribution over diverse subsets is valuable (e.g., for active learning, exploration).

Do not use DPPs when:

  • MMR is adequate — it is simpler and faster to deploy.
  • The candidate set is huge (the matrix operations are quadratic).
  • You need easily-tunable behavior — DPPs have more knobs and are harder to tune.

7. Strengths

  • Probabilistically principled.
  • Captures pairwise interactions among all selected items, not just the max.
  • Sampling and MAP inference both tractable with greedy algorithms.
  • Provably approximates the global optimum under sub-modularity arguments.

8. Weaknesses

  • More complex than MMR — kernel design, MAP inference algorithm, etc.
  • Quadratic in candidate set size for typical greedy MAP.
  • Less engineering experience in the broader recommender community than MMR.

9. See Also

Graph View

Backlinks