Expectation-Maximization for Learning Determinantal Point Processes

Abstract

A determinantal point process (DPP) is a probabilistic model of set diversity compactly parameterized by a positive semi-definite kernel matrix. To fit a DPP to a given task, we would like to learn the entries of its kernel matrix by maximizing the log-likelihood of the available data. However, log-likelihood is non-convex in the entries of the kernel matrix, and this learning problem is conjectured to be NP-hard. Thus, previous work has instead focused on more restricted convex learning settings: learning only a single weight for each row of the kernel matrix, or learning weights for a linear combination of DPPs with fixed kernel matrices. In this work we propose a novel algorithm for learning the full kernel matrix. By changing the kernel parameterization from matrix entries to eigenvalues and eigenvectors, and then lower-bounding the likelihood in the manner of expectation-maximization algorithms, we obtain an effective optimization procedure. We test our method on a real-world product recommendation task, and achieve relative gains of up to 16.5% in test log-likelihood compared to the naive approach of maximizing likelihood by projected gradient ascent on the entries of the kernel matrix.

References in corpus (2)

• Near-optimal Nonmyopic Value of Information in Graphical Models
• Learning Determinantal Point Processes

Cited by in corpus (12)

• DGCN: Diversified Recommendation with Graph Convolutional Networks
• Personalized Bundle List Recommendation
• Learning from the Dark: Boosting Graph Convolutional Neural Networks with Diverse Negative Samples
• Feature-aware Diversified Re-ranking with Disentangled Representations for Relevant Recommendation
• Diversified Hidden Markov Models for Sequential Labeling
• PTP: Parallelized Tracking and Prediction with Graph Neural Networks and Diversity Sampling
• DLow: Diversifying Latent Flows for Diverse Human Motion Prediction
• Inference for determinantal point processes without spectral knowledge
• Probabilistic Generating Circuits
• Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes
• Provable Non-Convex Optimization and Algorithm Validation via Submodularity
• Testing Determinantal Point Processes