Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity
This work addresses the problem of slow DPP inference for practitioners needing efficient, diverse recommendations in real-time applications, representing an incremental improvement over existing methods.
The paper tackles the computational challenge of greedy MAP inference for determinantal point processes (DPP), which is NP-hard and slow for large-scale use, by proposing a novel algorithm that accelerates it and adapts to scenarios with limited repulsion. Experimental results show the algorithm is significantly faster than state-of-the-art competitors and improves the relevance-diversity trade-off on public datasets and in an online A/B test.
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.