Kronecker Determinantal Point Processes

Abstract

Determinantal Point Processes (DPPs) are probabilistic models over all subsets a ground set of $N$ items. They have recently gained prominence in several applications that rely on "diverse" subsets. However, their applicability to large problems is still limited due to the $\mathcal{O}(N^3)$ complexity of core tasks such as sampling and learning. We enable efficient sampling and learning for DPPs by introducing KronDPP, a DPP model whose kernel matrix decomposes as a tensor product of multiple smaller kernel matrices. This decomposition immediately enables fast exact sampling. But contrary to what one may expect, leveraging the Kronecker product structure for speeding up DPP learning turns out to be more difficult. We overcome this challenge, and derive batch and stochastic optimization algorithms for efficiently learning the parameters of a KronDPP.

References in corpus (10)

• Solving the apparent diversity-accuracy dilemma of recommender systems
• Determinantal Processes and Independence
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• Determinantal point process models and statistical inference : Extended version
• Learning Mixtures of Submodular Shells with Application to Document Summarization
• Diversity Networks: Neural Network Compression Using Determinantal Point Processes
• Fast DPP Sampling for Nyström with Application to Kernel Methods
• Efficient Sampling for k-Determinantal Point Processes
• Low-Rank Factorization of Determinantal Point Processes for Recommendation
• Diversifying Sparsity Using Variational Determinantal Point Processes

Cited by in corpus (4)

• Boltzmann machines and energy-based models
• Maximum likelihood estimation of determinantal point processes
• Probabilistic Generating Circuits
• Deep Determinantal Point Processes