Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity
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 largescale 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.
Summary: This paper introduces an exact algorithm for greedy mode finding for DPPs which is faster by a factor of M (ground set size) than previous work on greedy MAP algorithms for DPPs; the authors also show that this algorithm can be further sped up when diversity is required over only a sliding window within long recommendations. As an additional contribution, the authors show that modeling recommendation problems with DPPs and generating recommendations via their algorithm outperforms other standard (non-DPP) recommender algorithms along various metrics.    -------------------  This paper builds upon the recent growing interest in leveraging Determinantal Point Processes for various machine learning problems. As the authors mention, a key advantage of DPPs is their ability to tractably balance quality and diversity requirements for most operations, with mode estimation being one of the only operations that remains NP-hard. Indeed, sampling from a DPP has been used in previous literature, presumably as a more scalable alternative to greedy MAP finding (e.g. for network compression). Although the usefulness of DPPs for recommender systems is now an accepted fact, the analysis provided in section 5 and 6.2 remains interesting, in particular thanks to the discussion of the tunable scaling of diversity and quality preferences and how it can easily be incorporated into the new formulation of the greedy algorithm. However, I would like to see a detailed theoretical comparison of the proposed greedy algorithm to the derandomized version of the lazy DPP sampling algorithm proposed in the thesis (Gillenwater, 2014).   --------------------  Quality: This paper is of good quality. Clarity: This paper is very clear. Originality: This paper is marginally novel - see below regarding its potential similarities to prior work. To my knowledge, however, there has not been an explicit mention of a fast greedy algorithm for DPP sampling prior to this submission. Significance: Fast greedy algorithms for DPPs are significant, as well as more broadly within recommendation systems (although the M^3 complexity might be a more general impediment to the use of the greedy MAP algorithm for DPPs within recommendations over very large set sizes).   --------------------  Detailed comments:  - Could you please detail the difference between your proposed algorithm and a derandomized greedy version of Alg. 2 of "Approximate Inference for DPPs" (Gillenwater, 2014) that uses all eigenvalues for the variable set V? In particular, the initialization of your variables d_i^2 is the same as that of the z_i of Gillenwater's Alg. 2, and the update rules also seem similar (although they are derived using a different logic).   - You might want to explicitly mention that higher MRR/ILAD/... are desirable for readers who aren't familiar with recommender systems. - Could you provide some intuition as to how the greedy algorithm performs when compared to simple DPP sampling for recommendations? It would be interesting to see how much of a gain the greedy approach provides over just sampling multiple times (O(M^3) if you need to compute the kernel eigendecomposition) from the DPP and keeping the subset with the highest probability.