Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity

Abstract

The determinantal point process (DPP) is an elegant probabilistic model of repulsion with applications in various machine learning tasks including summarization and search. However, the maximum a posteriori (MAP) inference for DPP which plays an important role in many applications is NP-hard, and even the popular greedy algorithm can still be too computationally expensive to be used in large-scale real-time scenarios. To overcome the computational challenge, in this paper, we propose a novel algorithm to greatly accelerate the greedy MAP inference for DPP. In addition, our algorithm also adapts to scenarios where the repulsion is only required among nearby few items in the result sequence. We apply the proposed algorithm to generate relevant and diverse recommendations. Experimental results show that our proposed algorithm is significantly faster than state-of-the-art competitors, and provides a better relevance-diversity trade-off on several public datasets, which is also confirmed in an online A/B test.

Cited by in corpus (32)

• DGCN: Diversified Recommendation with Graph Convolutional Networks
• Recent Advances in Diversified Recommendation
• SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios
• Differentiable Scaffolding Tree for Molecular Optimization
• A Methodology for the Offline Evaluation of Recommender Systems in a User Interface with Multiple Carousels
• Convergence of Sparse Variational Inference in Gaussian Processes Regression
• In Conclusion Not Repetition: Comprehensive Abstractive Summarization With Diversified Attention Based On Determinantal Point Processes
• Personalized Re-ranking for Improving Diversity in Live Recommender Systems
• Towards Diverse and Accurate Image Captions via Reinforcing Determinantal Point Process
• Revisit Recommender System in the Permutation Prospective
• HieRec: Hierarchical User Interest Modeling for Personalized News Recommendation
• Multi-Agent Determinantal Q-Learning
• Diverse Sample Generation: Pushing the Limit of Generative Data-free Quantization
• Hypergraph Clustering for Finding Diverse and Experienced Groups
• Improving End-to-End Sequential Recommendations with Intent-aware Diversification
• Reconfiguration Problems on Submodular Functions
• Multiple-criteria Based Active Learning with Fixed-size Determinantal Point Processes
• GRN: Generative Rerank Network for Context-wise Recommendation
• Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes
• Improving Accuracy and Diversity in Matching of Recommendation with Diversified Preference Network
• Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes
• Deep Dynamic Neural Network to trade-off between Accuracy and Diversity in a News Recommender System
• PP-Rec: News Recommendation with Personalized User Interest and Time-aware News Popularity
• DPPNet: Approximating Determinantal Point Processes with Deep Networks
• Bandit Learning for Diversified Interactive Recommendation
• ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions
• Exploration-Exploitation Motivated Variational Auto-Encoder for Recommender Systems
• Latent Unexpected Recommendations
• Diverse and Non-redundant Answer Set Extraction on Community QA based on DPPs
• Towards Deterministic Diverse Subset Sampling
• Diversity-Aware Batch Active Learning for Dependency Parsing
• Sampling from a $k$-DPP without looking at all items