A Framework for Recommending Relevant and Diverse Items

Chaofeng Sha, Xiaowei Wu, Junyu NiuIJCAI 2016

Abstract

Recommender systems frequently encounter a trade-off between accuracy and diversity, often resulting in redundant "top-$k$" lists that fail to capture the full range of user interests. This paper introduces a novel framework that optimizes for three pillars: relevance, diversity, and user interest coverage. By formulating the item selection process as a submodular optimization problem, the authors provide efficient greedy algorithms with theoretical performance guarantees. Evaluations on the MovieLens 1M dataset demonstrate that the proposed method simultaneously improves both precision and diversity over traditional baselines.

Introduction

The goal of a recommender system is to provide users with items they will find valuable. However, focusing solely on predicted ratings often leads to "filter bubbles" where users receive repetitive suggestions. For example, a fan of science fiction might be recommended five very similar space operas, ignoring their secondary interest in documentaries. This research addresses this by integrating "user interest coverage"—ensuring the recommended list reflects the breadth of a user's historical preferences—alongside relevance and diversity.

The Proposed Framework

The authors extend standard Probabilistic Matrix Factorization (PMF) by defining a new objective function, $g(S)$, for selecting a subset of items $S$. This function balances three components:

  1. Relevance: The predicted user rating for the items.
  2. Coverage ($\alpha$): The similarity between recommended items and the user’s historical ratings, ensuring the list aligns with known interests.
  3. Diversity ($\beta$): The Euclidean distance between items in the recommended set to minimize redundancy.

Optimization via Submodularity

Selecting the optimal subset $S$ is computationally intensive (NP-hard). However, the authors prove that their coverage and diversity functions are monotonic and submodular. Submodularity implies "diminishing returns," allowing the use of a greedy "hill-climbing" algorithm. This approach iteratively selects the item that provides the maximum marginal gain, ensuring a solution that is mathematically guaranteed to be near-optimal while remaining computationally feasible for large datasets.

Experimental Results

The framework was tested on the MovieLens 1M dataset. The researchers compared their approach (PMF+$\alpha$+$\beta$) against standard PMF and an Entropy-Regularized (ER) model.

Breaking the Precision-Diversity Trade-off

A key insight from the experiments is that increasing diversity does not necessarily come at the cost of precision. By incorporating user interest coverage, the model can remove redundant items that contribute little to the user's overall satisfaction, thereby improving precision.

Precision vs. Beta for list lengths k=10, 20, and 30. The proposed framework (colored lines) achieves higher precision than the PMF and PMF+ER baselines, showing a peak performance as diversity weight increases.

As shown in the precision plots, the proposed method significantly outperforms the baselines across different list lengths. The parameter $\beta$ allows for fine-tuning the balance; as $\beta$ increases, precision initially rises as redundancy is eliminated before eventually declining when diversity begins to outweigh relevance.

Superior Diversity Performance

The framework also consistently outperformed the Entropy-Regularized baseline in terms of diversity.

Diversity vs. Beta for k=10. The proposed framework shows a sharp increase in diversity as the weight beta increases, plateauing at a level significantly higher than the baselines.

The use of Euclidean distance between item vectors proved to be a more effective measure of variety than rating entropy, allowing the system to provide a more varied experience that still respects the user's historical interest profile.

Conclusion

By treating recommendation as a multi-objective optimization problem involving relevance, coverage, and diversity, the authors provide a robust framework for generating high-quality recommendation lists. The submodular nature of the objective function ensures that the system remains scalable. Future work will explore incorporating temporal dynamics to account for shifting user interests and further optimizing the diversification process for real-time deployment.

Summary updated

BibTeX
@inproceedings{sha2016framework,
  author = {Chaofeng Sha and Xiaowei Wu and Junyu Niu},
  title = {{A Framework for Recommending Relevant and Diverse Items}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure