Bayesian Personalized Ranking (BPR) Algorithm
A Bayesian Personalized Ranking (BPR) Algorithm is a pairwise ranking algorithm that (approximately) optimizes average per-user AUC using stochastic gradient descent (SGD) on randomly sampled (user, positive item, negative item) triplets.
- Context:
- It can be implemented by a Bayesian Personalized Ranking (BPR) System.
- It can represent a Training Example as triple [math]\displaystyle{ (u,i,j) }[/math], such that:
- user has embedding [math]\displaystyle{ u }[/math]
- a positive item i with embedding [math]\displaystyle{ v_i }[/math] (this is an item that the user has previously interacted with)
- a (sampled) negative item j with embedding [math]\displaystyle{ v_j }[/math].
- It can define the affinity [math]\displaystyle{ x_{ui} }[/math] between a user u and an item i as the dot product between the user and the item embedding [math]\displaystyle{ x_{ui} = \langle u, v_i \rangle }[/math].
- It can learn that the user's affnity toward the positive item is more than the user's affinity toward the negative item, i.e., [math]\displaystyle{ x_{ui} \gt x_{uj} }[/math].
- It can learn embeddings such that the likelihood function below is maximized. (with the Gaussian priors on the user and item embeddings being omitted): [math]\displaystyle{ \operatorname{argmax}\Pi_{u \in U} \Pi_{i \in I} \Pi_{j \in I \backslash \{i\}} \sigma(x_{ui} - x_{uj}) }[/math]
- It can use the logistic function [math]\displaystyle{ \sigma (z) = \frac{1}{1+exp(-z)} }[/math] to approximate the non-continuous, non-differential function of [math]\displaystyle{ x_{ui} \gt x_{uj} }[/math].
- It can be a relatively Efficient Algorithm[1].
- It can be a relatively High-Precision Algorithm[2].
- It can be a relatively Low-Recall Algorithm (because of its negative sampling method) [3].
- …
- Example(s):
- the one proposed by (Rendle et al., 2009).
- …
- Counter-Example(s):
- See: Cold-Start Problem.
References
2016a
- (Rodrigo & de Oliveira, 2016) ⇒ Alfredo Lainez Rodrigo, and Luke de Oliveira. (2016). “Distributed Bayesian Personalized Ranking in Spark." Stanford CME-323 S16 projects_report
- ABSTRACT: Bayesian Personalized Ranking (BPR) is a general learning framework for item recommendation using implicit feedback (e.g. clicks, purchases, visits to an item), by far the most prevalent form of feedback in the web. Using a generic optimization criterion based on the maximum posterior estimator derived from a Bayesian analysis, BPR differentiates itself from other common recommendation algorithms in two main aspects. First, it directly optimizes the final objective of ranking. Second, it abstracts away the underlying rating computation model (which could be, for instance, matrix factorization or k-nearest-neighbors). In this paper, we define a distributed version of BPR using matrix factorization for the Spark ecosystem, which we implement in both Scala and Python (https://github.com/alfredolainez/bpr-spark ).
2016b
- https://cran.r-project.org/web/packages/rrecsys/vignettes/b6_BPR.html
- QUOTE: The algorithm addresses the One Class Collaborative Filtering problem (OCCF) by turning it into a ranking problem and implicitly assuming that users prefer items they have already interacted with another time. Instead of applying rating prediction techniques, BPR ranks candidate items for a user without calculating a “virtual” rating.
The overall goal of the algorithm is to find a personalized total ranking [math]\displaystyle{ \gt _u ⊂ I^2 }[/math] for any user [math]\displaystyle{ u ∈ \text{Users} }[/math] and pairs of items [math]\displaystyle{ (i,j) \in I^2 }[/math] that meet the properties of a total order (totality, anti-symmetry, transitivity).
The model uses a pair-wise interpretation of the implicit feedback matrix and tries to reconstruct for each user parts of >u, meaning a user's positive feedback represents a preference of the user over an item that the user did not provide any feedback on. In other words a positive only feedback will be transformed into positive and negative feedback in terms of pairs of items (i,j), where the user prefers i over j (positive) and correspondingly rephrased dislikes j over i (negative).
Given [math]\displaystyle{ \Theta }[/math] the parameter vector of a model (in rrecsys the model is a factorized matrix) to determine the personalized ranking for any [math]\displaystyle{ i∈I }[/math], BPR aims to maximize [math]\displaystyle{ p(\Theta| \gt u) ∝ p( \gt u|\Theta)p(\Theta) }[/math] posterior probabilities. Optimization of [math]\displaystyle{ \Theta }[/math] is achieved through a criterion called BPR-OPT which is related to the AUC metric and optimizes it implicitly. We optimized the parameter [math]\displaystyle{ \Theta }[/math] with gradient descent, by choosing randomly choosing triples [math]\displaystyle{ (u,i,j) }[/math] from the training data.
- QUOTE: The algorithm addresses the One Class Collaborative Filtering problem (OCCF) by turning it into a ranking problem and implicitly assuming that users prefer items they have already interacted with another time. Instead of applying rating prediction techniques, BPR ranks candidate items for a user without calculating a “virtual” rating.
2015
- https://github.com/quora/qmf
- QUOTE: BPR. This model (approximately) optimizes average per-user AUC using stochastic gradient descent (SGD) on randomly sampled (user, positive item, negative item) triplets. Asynchronous, parallel Hogwild! [3] updates are supported in QMF to achieve near-linear speedup in the number of processors (when the dataset is sparse enough).
2014
- (Rendle & Freudenthaler, 2014) ⇒ Steffen Rendle, and Christoph Freudenthaler. (2014). “Improving Pairwise Learning for Item Recommendation from Implicit Feedback.” In: Proceedings of the 7th ACM International Conference on Web search and data mining. ISBN:978-1-4503-2351-2 doi:10.1145/2556195.2556248
- QUOTE: Pairwise algorithms are popular for learning recommender systems from implicit feedback. For each user, or more generally context, they try to discriminate between a small set of selected items and the large set of remaining (irrelevant) items. Learning is typically based on stochastic gradient descent (SGD) with uniformly drawn pairs. In this work, we show that convergence of such SGD learning algorithms slows down considerably if the item popularity has a tailed distribution.
2009
- (Rendle et al., 2009) ⇒ Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. (2009). “BPR: Bayesian Personalized Ranking from Implicit Feedback.” In: Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence. ISBN:978-0-9749039-5-8
- ABSTRACT: 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 k-nearest-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.