DppNet: Approximating Determinantal Point Processes with Deep Networks

Zelda E. Mariet, Yaniv Ovadia, Jasper Snoek

TL;DR

Determinantal Point Processes (DPPs) are the mathematical gold standard for picking diverse subsets of data, but their cubic computational cost makes them too slow for large datasets. DPPNET solves this by using a deep generative network with a novel "inhibitive attention" mechanism to mimic DPPs, achieving orders-of-magnitude speedups while maintaining the theoretical diversity guarantees of the original process.

The Bottleneck of Diverse Sampling

In machine learning, we often need to select a subset of items that are both high-quality and diverse—think of a search engine showing a variety of relevant results rather than ten nearly identical pages. Determinantal Point Processes (DPPs) are elegant probabilistic models designed exactly for this "quality-diversity" tradeoff.

However, DPPs suffer from a massive computational bottleneck. To sample from a ground set of $N$ items, you typically need $O(N^3)$ preprocessing time (for eigendecomposition) and $O(Nk^3)$ time to sample a subset of size $k$. This makes them impractical for real-time recommendation systems or large-scale data summarization. Furthermore, if the available items change (like a rotating inventory), you have to redo the expensive math from scratch.

Introducing DPPNET and Inhibitive Attention

To bypass these limitations, the authors introduce DPPNET, a generative deep neural network designed to approximate DPP sampling. Instead of calculating complex determinants, the network learns to predict the probability of adding a specific item to an existing subset.

The core innovation is the Inhibitive Attention Mechanism. While standard Transformer attention (like that used in Large Language Models) is designed to find similar items, DPPNET’s attention is "inhibitive." It calculates the similarity between a candidate item and the items already selected, then uses that information to lower the candidate's probability. Essentially, the more similar an item is to what you’ve already picked, the more the network "ignores" it, enforcing diversity.

DPPNET Architecture

Key technical details: * Sequential Sampling: The model builds the subset one item at a time, similar to how an autoregressive language model generates text word by word. * Training Signal: The network is trained to minimize the L1 distance between its output and the true marginal probabilities of a DPP, which can be computed offline during training. * Theoretical Guarantee: The authors prove that if a neural network approximates a log-submodular function (like a DPP) closely enough, the network itself inherits the mathematical properties that guarantee diversity.

Experimental Validation

The authors evaluated DPPNET across several diverse domains, including synthetic 2D grids, image datasets (MNIST & CelebA), recommendation datasets (MovieLens), and regression datasets (Ailerons).

Key Results

  • Speed and Scalability: DPPNET is orders of magnitude faster than standard DPP sampling and MCMC-based approximations. Because it uses standard neural network operations, DPPNET can be easily parallelized on GPUs, unlike traditional sequential DPP algorithms.
  • Quality: On tasks like generating points on a synthetic unit square, DPPNET achieves a lower Negative Log-Likelihood (NLL) than uniform sampling, meaning its samples closely match the "ideal" diverse distribution of a true DPP. Interestingly, "greedy mode finding" (simply picking the most probable item at each step) with DPPNET often yielded higher-quality subsets than actually sampling from the true, expensive DPP.
Qualitative and Quantitative Results

Limitations and Future Work

While highly effective, DPPNET has a few limitations:

  • Non-Exchangeability: In a true DPP, the order in which you pick items doesn't matter. In DPPNET, because it is sequential, the order does matter. While the authors suggest this could actually be a benefit for "ranking" tasks, it is a departure from the original theory.
  • Training Cost: While sampling is fast, training the model still requires calculating true DPP probabilities, which is slow. This means DPPNET is best suited for scenarios where you can afford a long training phase to get a very fast inference phase.

Future work could explore whether these networks can learn other complex combinatorial properties beyond just diversity and submodularity, bridging the gap between fast deep learning and principled discrete math.

Summary updated

Abstract

Determinantal point processes (DPPs) provide an elegant and versatile way to sample sets of items that balance the point-wise quality with the set-wise diversity of selected items. For this reason, they have gained prominence in many machine learning applications that rely on subset selection. However, sampling from a DPP over a ground set of size N is a costly operation, requiring in general an O(N^3) preprocessing cost and an O(Nk^3) sampling cost for subsets of size k. We approach this problem by introducing DppNets: generative deep models that produce DPP-like samples for arbitrary ground sets. We develop an inhibitive attention mechanism based on transformer networks that captures a notion of dissimilarity between feature vectors. We show theoretically that such an approximation is sensible as it maintains the guarantees of inhibition or dissimilarity that makes DPPs so powerful and unique. Empirically, we show across multiple datasets that DPPNET is orders of magnitude faster than competing approaches for DPP sampling, while generating high-likelihood samples and performing as well as DPPs on downstream tasks.
BibTeX
@inproceedings{mariet2019dppnet,
  author = {Zelda E. Mariet and Yaniv Ovadia and Jasper Snoek},
  title = {{DppNet: Approximating Determinantal Point Processes with Deep Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=HHeWqAA1Nbq},
}
Figure