Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes

Abstract

Determinantal point processes (DPPs) have attracted significant attention in machine learning for their ability to model subsets drawn from a large item collection. Recent work shows that nonsymmetric DPP (NDPP) kernels have significant advantages over symmetric kernels in terms of modeling power and predictive performance. However, for an item collection of size $M$, existing NDPP learning and inference algorithms require memory quadratic in $M$ and runtime cubic (for learning) or quadratic (for inference) in $M$, making them impractical for many typical subset selection tasks. In this work, we develop a learning algorithm with space and time requirements linear in $M$ by introducing a new NDPP kernel decomposition. We also derive a linear-complexity NDPP maximum a posteriori (MAP) inference algorithm that applies not only to our new kernel but also to that of prior work. Through evaluation on real-world datasets, we show that our algorithms scale significantly better, and can match the predictive performance of prior work.

arXiv commentICLR 2021

References in corpus (12)

• Learning Determinantal Point Processes
• Guarantees for Greedy Maximization of Non-submodular Functions with Applications
• Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity
• Diversity Networks: Neural Network Compression Using Determinantal Point Processes
• Fast DPP Sampling for Nyström with Application to Kernel Methods
• Expectation-Maximization for Learning Determinantal Point Processes
• Fast determinantal point processes via distortion-free intermediate sampling
• Fixed-point algorithms for learning determinantal point processes
• Learning Nonsymmetric Determinantal Point Processes
• On Sampling and Greedy MAP Inference of Constrained Determinantal Point Processes
• Learning Signed Determinantal Point Processes through the Principal Minor Assignment Problem
• Woodbury Transformations for Deep Generative Flows

Cited by in corpus (2)

• Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes
• Nonparametric estimation of continuous DPPs with kernel methods