Improving Recommendation Diversity with Determinantal Point Processes and Greedy Optimization

The goal of a recommendation system consists of two aspects: Exploitation (relevance) and Exploration (diversity). Exploitation focuses on relevance calculation based on user behavior, while Exploration addresses cold‑start issues and aims to uncover latent user interests.

Exploration is broken down into three dimensions:

Coverage – the proportion of all items that appear in recommendations, especially for new content.

Surprise – recommending items that are not obviously related to past behavior but are still liked by the user.

Diversity – mixing different types of items in a short time window, measured by item‑pair similarity.

To quantify diversity, the article discusses Temporal Diversity (changing recommendations over time) and Spatial Diversity (pairwise dissimilarity within a recommendation list). It illustrates how focusing solely on relevance leads to homogeneous recommendations.

The core solution is a Determinantal Point Process (DPP) model, which selects a subset of items that maximizes both relevance and diversity by maximizing the determinant of a kernel matrix L . The DPP objective is submodular, allowing a greedy algorithm to approximate the optimal subset.

Because direct determinant computation is cubic in the subset size, the authors accelerate inference using Cholesky decomposition . By maintaining a lower‑triangular matrix V , each iteration reduces to quadratic, and further incremental updates bring the complexity down to linear time.

Experimental results on large item sets (2000‑6000 items) show a 100× speedup with no performance loss, and the proposed method outperforms baseline algorithms on relevance‑diversity metrics (MRR, ILAD, ILMD) across multiple datasets.

In summary, the DPP‑based greedy algorithm, combined with Cholesky‑based acceleration, effectively enhances recommendation diversity while dramatically improving computational efficiency, making it suitable for real‑time recommendation scenarios.