017 The Web 2018 Paper Review - How to Improve the Classic Recommendation Algorithm BPR #
Today, let’s take a look at an excellent short paper from the World Wide Web Conference. There are mainly two types of papers presented at the conference: long papers of 10 pages and short papers, also known as poster papers, of 2 pages. Short papers mainly present small achievements or important ongoing research. Each year, the conference selects a Best Short Paper award.
The paper I want to share with you today is titled “An Improved Sampler for Bayesian Personalized Ranking by Leveraging View Data” (link). It also has six authors and, just like the previous paper we introduced, they are all from Tsinghua University and the National University of Singapore.
Bayesian Personalized Ranking #
To understand the content of this paper, we need to explain what “Bayesian Personalized Ranking” (BPR) is. For a detailed introduction to BPR, refer to the reference [1]. Here, we will provide a high-level summary of BPR.
Simply put, BPR is a pairwise learning algorithm used in recommendation systems. In our previous discussion of search algorithms, we mentioned various pairwise learning algorithms. Pairwise learning is not about learning the labels or response variables for each data instance, but about learning a relative order. The goal is to rank all positive instances above negative instances. In other words, for pairwise learning, the prediction value for each data instance is not important. The sorting algorithm is concerned with accurately ranking positive instances above negative instances for each pairwise combination. This requires BPR to have higher predicted values for positive instances compared to negative instances.
BPR mainly aims to solve the problem of only predicting individual data points in recommendation systems. For example, when modeling the preference matrix of user items, most previous algorithms were unable to effectively model unobserved data. However, BPR is a pairwise algorithm, so we only need to focus on the observed data and their relationships. This allows for more significant effects on user preferences, especially when there is “implicit feedback” data. Implicit feedback refers to the expression of preferences by users during their interactions with the system. These user behaviors are often incomplete, so the algorithm and model need to effectively model these behaviors.
Main Contributions and Core Methods of the Paper #
After understanding what BPR is roughly about, let’s take a look at the main contributions and core methods of this paper.
Firstly, as we mentioned earlier, the core of BPR is to learn a pairwise ranking problem. During training, we need to learn and update parameters based on pairs of positive and negative instances. However, in a natural user implicit feedback dataset, positive instances are often the minority while negative instances are the majority. Therefore, a traditional method is to “uniformly” sample negative instances to form pairs relative to a positive instance, a process sometimes referred to as “sampling”.
This paper has two main contributions. The first contribution is that the authors found that it is unnecessary and may even affect the final learning effect to uniformly sample negative instances globally. The second contribution is that, for the application in e-commerce, the authors invented a method of negative instance sampling that allows the learning algorithm to utilize more user “view” information, thus significantly improving the overall training effect of the algorithm.
Experimental Results of the Method #
The dataset used in this paper includes data from the “Beibei” maternal and child products and Tmall. The Beibei dataset consists of approximately 160,000 users, 120,000 products, 2.6 million purchases, and 46 million views. The Tmall dataset consists of 30,000 users, over 30,000 products, 460,000 purchases, and over 1.5 million views. Both datasets exhibit a “sparsity” (Sparsity) of over 99%.
First, the authors conducted experiments by sampling only a small portion of negative samples without selecting them from the entire global space, such as only a few hundred negative samples instead of tens of thousands. The experimental results showed that this approach not only did not affect the accuracy of the algorithm on Beibei, but actually improved it. However, on the Tmall dataset, the algorithm’s performance did not improve and showed a slight decline. Nevertheless, the authors considered this trade-off worthwhile because reducing the dataset significantly reduced the training time of the algorithm. Based on this experiment, the authors concluded that global sampling is unnecessary.
Next, the authors proposed a new concept, that is, dividing the user data set into three sets: “purchase set” (C1), “browse but not purchase set” (C2), and “remaining data” (C3). The authors suggested that for BPR to achieve the best results, these three sets need to be sampled. In other words, we need to form pairs of C1 and C2, C1 and C3, as well as C2 and C3 for learning.
Specifically, different proportions were tried for sampling these three sets in the Beibei and Tmall datasets. The general experience is that the data sampled in C3 should be larger than that in C2, which should be larger than that in C1. Essentially, this means that the training algorithm needs to better learn the user’s preference for disliking certain items. By adopting this sampling approach, the authors demonstrated that the model’s performance is about 60% better than traditional BPR or simply using the “most popular items” as recommendation results.
Summary #
Today, I have discussed an excellent short paper from this year’s World Wide Web conference. The paper introduces how to improve a classical recommendation algorithm called BPR to enhance efficiency and significantly improve algorithm effectiveness.
Let’s recap the key points: Firstly, we introduced the meaning of BPR from a high-dimensional perspective. Secondly, we briefly introduced the main contributions and ideas of the paper. Lastly, we shared the experimental results of the paper.
Finally, I leave you with a thought-provoking question. Besides the pairing approach of positive and negative instances proposed in this paper, can you think of other information that can help us form more pairs when users browse websites?
References
- Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. BPR: Bayesian personalized ranking from implicit feedback. Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI ‘09). AUAI Press, Arlington, Virginia, United States, 452-461, 2009.