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 demonstrate that samples from our model receive high likelihood under the more expensive DPP alternative.
Introduction: The Quality-Diversity Tradeoff
In machine learning, selecting a "representative" subset from a large pool of candidates is a recurring challenge. Whether choosing sentences for a document summary or products for a recommendation engine, one must balance quality (individual item relevance) with diversity (minimizing redundancy). Determinantal Point Processes (DPPs) are the mathematical gold standard for this tradeoff, using determinants to model repulsion between similar items.
Despite their elegance, DPPs are computationally expensive. Preprocessing requires $O(N^3)$ operations for a ground set of size $N$, making them impractical for large-scale, real-time applications. DPPNet aims to bridge this gap by using deep networks to approximate DPP behavior, providing the same repulsive properties at a fraction of the computational cost.
The DPPNet Architecture
DPPNet is a generative model designed to predict the probability of adding a new item to an existing subset sequentially. The core of the model is a novel inhibitive attention mechanism. While standard Transformer networks use attention to find similarities, DPPNet flips this logic to identify items that are dissimilar to those already selected.
As shown in the architecture diagram, the model functions like an unrolled recurrent network. At each step, it processes the current subset $S$ and the ground set $\Phi$ to output a probability distribution over remaining items. If a candidate item is too similar to the current subset, the inhibitive mechanism lowers its selection probability. Crucially, the authors provide theoretical proofs that if a network is trained to be sufficiently close to a log-submodular distribution (like a DPP), it inherits the mathematical "repulsion" property necessary for diversity.
Experimental Evaluation
The model was evaluated across several domains, including synthetic 2D point sets, image datasets (MNIST, CelebA), and recommendation systems (MovieLens). A key test involved Nyström kernel approximation on the Ailerons dataset, where DPPNet-selected subsets achieved lower Root Mean Squared Error (RMSE) than standard MCMC sampling methods while running significantly faster.
Visual results on synthetic data demonstrate that DPPNet captures the repulsive nature of true DPPs. As seen in the figure above, the Negative Log-Likelihood (NLL) of samples from DPPNet is nearly identical to the true DPP. Interestingly, the "Greedy Mode" of the model—where the highest-probability item is picked at each step—often finds subsets with even higher likelihoods than the true DPP itself.
Key Results and Insights
- Efficiency: DPPNet achieved a 30x speedup over standard DPP sampling for subsets of size 20 from a ground set of 100.
- High Fidelity: The model maintains high fidelity to the original DPP distribution, as evidenced by the NLL metrics.
- Scalability: By replacing exact mathematical determinants with a neural approximation, the authors demonstrate that "DPP-like" behavior can be scaled to practical applications without the cubic cost.
Limitations and Future Work
While powerful, DPPNet currently has limitations. The model is sensitive to selection order, whereas a true DPP is exchangeable (order-independent). Future work may incorporate "Deep Sets" architectures to address this. Additionally, the current reliance on pre-computed features (e.g., from a VAE) suggests a path toward end-to-end training, where feature encoders and the DPPNet are optimized simultaneously to learn diversity-aware embeddings.
Summary updated