Source-linked AI summary
BPR: Bayesian Personalized Ranking from Implicit Feedback
Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, Lars Schmidt-Thieme
TL;DR
Personalized ranking from implicit feedback is common, but standard recommendation methods are not directly optimized for ranking. BPR introduces a Bayesian ranking objective and bootstrap-based learning algorithm, outperforming alternative optimization methods for matrix factorization and k-nearest-neighbor models.
Problem
Existing implicit-feedback recommenders such as matrix factorization and adaptive k-nearest neighbors are not directly optimized for personalized ranking.
Method
BPR-Opt formulates personalized ranking as a Bayesian maximum-posterior objective, while LearnBPR optimizes it using stochastic-gradient descent with bootstrap sampling.
Results
BPR-optimized methods outperform other evaluated methods in personalized-ranking prediction quality across both datasets.
Takeaways & Limitations
Prediction quality depends substantially on optimizing model parameters for the ranking criterion rather than on the recommendation model alone.
Takeaways & Limitations
The Bayesian formulation assumes users act independently and that each user’s pairwise item orderings are mutually independent.
Abstract
from arXiv · showhide
Item recommendation is the task of predicting a personalized ranking on a set of items (e.g. websites, movies, products). In this paper, we investigate the most common scenario with implicit feedback (e.g. clicks, purchases). There are many methods for item recommendation from implicit feedback like matrix factorization (MF) or adaptive knearest-neighbor (kNN). Even though these methods are designed for the item prediction task of personalized ranking, none of them is directly optimized for ranking. In this paper we present a generic optimization criterion BPR-Opt for personalized ranking that is the maximum posterior estimator derived from a Bayesian analysis of the problem. We also provide a generic learning algorithm for optimizing models with respect to BPR-Opt. The learning method is based on stochastic gradient descent with bootstrap sampling. We show how to apply our method to two state-of-the-art recommender models: matrix factorization and adaptive kNN. Our experiments indicate that for the task of personalized ranking our optimization method outperforms the standard learning techniques for MF and kNN. The results show the importance of optimizing models for the right criterion.
1 Introduction
The paper addresses personalized item ranking learned from users’ implicit interactions, which are easier to collect than explicit feedback. It introduces BPR-Opt and LearnBPR, applies LearnBPR to two recommender model classes, and reports improved personalized-ranking performance.
- Motivation: Item recommendation creates a user-specific ranking of items from past interactions such as purchases and viewing history.Personalized recommendations can benefit both content providers and customers.
- Motivation: Implicit feedback, including clicks, view times, and purchases, is automatically tracked and easier to collect than explicit feedback.Users do not need to explicitly express their tastes.
- Contributions: BPR-Opt is a generic optimization criterion derived from the maximum posterior estimator for optimal personalized ranking and related to ROC-area maximization.The paper presents BPR-Opt as a criterion for personalized-ranking optimization.
- Contributions: LearnBPR maximizes BPR-Opt using stochastic gradient descent with bootstrap sampling of training triples.The authors report that LearnBPR is superior to standard gradient descent techniques for optimizing BPR-Opt.
- Contributions: LearnBPR is applied to two state-of-the-art recommender model classes, and experiments show BPR outperforms other learning methods for personalized ranking.The reported empirical result concerns the personalized-ranking task.
2 Related Work
Related work centers on collaborative filtering with learned kNN similarities and matrix factorization, alongside non-personalized learning-to-rank methods. The paper instead studies offline collaborative models that learn personalized rankings for individual users.
- Collaborative filtering: kNN collaborative filtering is described as the most popular recommender model, while recent work learns its similarity matrix specifically for the task.Traditional kNN similarity matrices use heuristics such as Pearson correlation; matrix factorization has also become popular for implicit and explicit feedback.
- Learning setting: The paper focuses on offline model-parameter learning, while prior MF work studied online fold-in for users whose feedback histories grow over time.The same fold-in strategy can be used for BPR.
- Learning to rank: Non-collaborative learning-to-rank approaches model permutation distributions or optimize neural networks, but learn only one non-personalized ranking.These approaches include permutation-distribution models and gradient-descent optimization of neural networks for ranking.
- Personalized ranking: In contrast, the paper’s collaborative models learn personalized rankings, producing one individual ranking per user.The evaluation reports that personalized BPR empirically outperforms the theoretical upper bound for non-personalized ranking in typical recommender settings.
3 Personalized Ranking
Personalized ranking recommends a user-specific total ordering of items from implicit feedback, where only positive observations are available. BPR addresses missing-value ambiguity by training on pairwise preferences that directly represent the ranking objective.
- Task definition: Personalized ranking provides each user with a ranked list or total ordering of all items based on implicit feedback such as purchases, views, or clicks.The ranking must satisfy totality, antisymmetry, and transitivity.
- Implicit feedback: Implicit-feedback data contains observed positive interactions, while unobserved entries mix genuinely negative preferences with missing values.Ignoring unobserved entries prevents typical machine-learning models from distinguishing the two levels.
- Conventional approach: Conventional recommenders assign positive labels to observed pairs and negative labels to every unobserved pair, then optimize single-item scores for values 1 and 0.Items are subsequently ranked by sorting their predicted personalized scores.
- Pairwise formulation: BPR instead trains on item pairs and optimizes correct pairwise rankings, assuming each observed item is preferred over every non-observed item for that user.This better represents ranking than replacing missing values with negative labels.
- Pairwise formulation: The resulting training set combines positive and negative pairs while leaving pairs between two non-observed items for future ranking, making training and test data disjoint.The observed subset of the user’s ordering is therefore used as training data for the actual ranking objective.
4 Bayesian Personalized Ranking (BPR)
This section derives BPR-Opt, a Bayesian optimization criterion for personalized ranking, and LearnBPR, a bootstrap-sampling stochastic gradient method for optimizing it. BPR uses the differentiable loss ln σ(x), while LearnBPR addresses convergence problems caused by full or poorly ordered gradient updates.
- Bayesian Personalized Ranking: BPR-Opt derives personalized ranking by maximizing a Bayesian posterior over model parameters, combining a likelihood for users’ latent pairwise preferences with a prior.The prior is a zero-mean normal distribution with covariance Σ_Θ = λ_ΘI, where λ_Θ provides model-specific regularization.
- Bayesian Personalized Ranking: The framework assumes users act independently and pairwise item orderings for a user are mutually independent, enabling the likelihood to factor across users and item pairs.A sound personalized total order additionally requires totality, antisymmetry, and transitivity.
- BPR and AUC: BPR-Opt parallels AUC but replaces its non-differentiable Heaviside loss with the differentiable loss ln σ(x), a substitution derived from maximum likelihood estimation.The AUC and BPR formulations differ, apart from normalization, in their loss functions.
- LearnBPR: LearnBPR optimizes the differentiable criterion with stochastic gradient descent that samples training triples uniformly with replacement, avoiding problematic traversal order and enabling stopping before a full data cycle.Full gradient descent is infeasible because the training set contains O(|S| |I|) triples, while user-wise traversal produces many consecutive updates for the same user-item pair.
- LearnBPR: LearnBPR converges much faster than typical user-wise stochastic gradient descent in the reported BPR-MF comparison.The comparison uses a BPR-MF model with 16 dimensions on the Rossmann dataset.
- Applying BPR to Recommendation Models: BPR methods can train matrix factorization and learned k-nearest-neighbor models by classifying prediction differences x̂_ui − x̂_uj rather than regressing individual predictions.Both model classes estimate hidden user preferences and produce a real-valued prediction for each user-item pair.
5 Relations to other methods
The paper contrasts BPR with implicit-feedback matrix factorization and explicit-feedback maximum-margin ranking. These methods differ in optimization level, loss, applicability, and learning assumptions.
- Matrix factorization: Pan et al. and Hu et al. use the same matrix-factorization model class as BPR but minimize square loss with SVD-based optimization.Their extensions include regularization and weights for feedback tuples.
- Matrix factorization: Hu et al. and Pan et al. assign weights to feedback tuples, using additional data or constants to distinguish positive from non-positive feedback.Hu et al. set c_ui = 1 for the rest; Pan et al. use lower constants for the rest.
- Matrix factorization: Their optimization operates on individual items and uses least squares, whereas BPR operates on item pairs and uses logistic optimization for qualitative classification.Least squares corresponds to maximum likelihood for normally distributed random variables, while the paper argues logistic optimization is more appropriate for item prediction.
- Matrix factorization: WR-MF can be learned in O(iter (|S| k^2 + k^3 (|I|+|U|))), while LearnBPR usually converges after m · |S| single-update steps.The WR-MF bound assumes c_ui is constant for non-positive pairs; LearnBPR converges after a subsample despite many available triples.
- Maximum-margin matrix factorization: MMMF targets explicit ratings but can be adapted to implicit feedback by assigning 0 to non-observed and 1 to observed items, yielding a criterion similar to BPR-MF.BPR uses a smooth hinge loss motivated by maximum likelihood, is generic across models, and LearnBPR differs from MMMF’s sparse-explicit-data learning method.
6 Evaluation
The evaluation compares BPR-based and standard learning methods for matrix factorization and k-nearest-neighbor recommendation on two implicit-feedback datasets. Using leave-one-out testing and average AUC, BPR methods achieve the strongest personalized-ranking results and outperform non-personalized methods.
- Compared methods: The study compares SVD-MF, WR-MF, and BPR-MF for matrix factorization, alongside Cosine-kNN and BPR-kNN for k-nearest-neighbor recommendation.The factorization models vary dimensions from 8 to 128.
- Datasets: The datasets comprise Rossmann online-shop purchases from 10,000 users and 4,000 items, plus a Netflix DVD-rental dataset converted to implicit feedback.Rossmann contains 426,612 recorded purchases, and the task is to predict each user’s next desired items.
- Evaluation protocol: Evaluation removes one randomly selected user-item action per user, trains on the disjoint remainder, and measures personalized rankings on the held-out test set using average AUC.AUC ranges from 0.5 for random guessing to 1 for the best achievable quality.
- Results: The two BPR-optimized methods outperform all other methods in prediction quality, showing that optimization choice matters even when matrix-factorization models are identical.On Netflix, an 8-dimensional BPR-MF model achieves comparable quality to a 128-dimensional WR-MF model.
- Personalized versus non-personalized ranking: Cosine-kNN outperforms the theoretical upper bound for any non-personalized ranking method, and therefore also outperforms all non-personalized methods.The reported upper bound is a real but non-tight estimate, and ranking by test-set popularity is not an AUC upper bound.
7 Conclusion
The paper presents BPR-Opt and LearnBPR as a generic Bayesian optimization criterion and stochastic-gradient learning algorithm for personalized ranking. Theoretical and empirical results indicate that optimizing with BPR is important because prediction quality depends substantially on the optimization criterion, not only the model.
- BPR-Opt is a maximum posterior estimator derived from a Bayesian analysis of personalized ranking.
- LearnBPR is a generic learning algorithm for optimizing models with respect to BPR-Opt, based on stochastic gradient descent.
- The results show that prediction quality depends substantially on the optimization criterion as well as the model.
- 0.8794 vs. 0.8801: on Netflix, the most-popular test AUC and the reported upper-bound AUC are quite similar.
- Both theoretical and empirical results indicate that BPR optimization is the right choice for personalized ranking.