Alleviating the recommendation bias via rank aggregation

Two benchmark data sets are employed to evaluate the performance of recommendation algorithms, namely, Movielens and Netflix. Both of them are movie rating data set, where users rate their watched movies (rephrased as items in this paper) with an explicit integer scores from 1 to 5. For each data set, we use only the ratings no less than 3 to construct links of the bipartite network. Table 1 summarizes the statistical features of the two data sets. To evaluate the offline performance of different models, each data set is randomly divided into two subsets: the training set containing $90\%$ of the links and the probe set $10\%$ of the links. The training set is treated as known information to make recommendation and the probe set is used to test the accuracy performance of the recommendation results.

In order to evaluate the performance of recommendation algorithms, we adopt three typical metrics in this paper, which can be categorized into accuracy, diversity and coverage measures.

When designing a recommender algorithm, one major concern is the accuracy of recommendation results. We make use of Precision to measure the recommendation accuracy. For a target user $u$, the recommender system will return him a ranked list of his uncollected items. Precision is the fraction of accurately recommended items to the length of recommendation lists. By averaging over the Precision of all users, we obtain the overall Precision of the system,

$\text{Precision}(L)=\frac{1}{m}\sum\limits_{k=1}^{m}\frac{h_{k}}{L}$,

where $L$ is the fixed length of recommendation list, $m$ the total number of users in the system, and $h_{k}$ the number of accurately recommended items in the recommendation list of $u_{k}$.

Besides accuracy, diversity has been regarded as another important concern in evaluating a recommendation model. The diversity measures how different are the recommendation lists from each other, and can be quantified by Hamming Distance. Given two different users $u$ and $v$, borrowing inspiration from the Hamming distance of two strings, we can calculate recommendation diversity in a similar way, as

$\text{HD}_{uv}(L)=1-\frac{D_{uv}(L)}{L}$

where $D_{uv}(L)$ is the number of common items in the recommendation lists of length $L$ of users $u$ and $v$. Clearly, the higher is the value, the more personalized lists are recommended to users. By averaging over the Hamming Distances of all user pairs, we obtain the overall diversity of the system.

Coverage is usually measured by the percentage of items that an algorithm is able to recommend to users. While being simple and intuitive, this definition may not be very robust, since the contribution to the metric of an item that has been recommended just once is equal to that of other item recommended a thousand times [11]. Therefore, Fleder and Hosanagar [12] proposed to use the Gini coefficient to measure the imbalance in the number of times each item is recommended,

$\text{Gini}(L)=1-\frac{1}{n-1}\sum\limits_{q=1}^{n}{(2q-n-1)p(i_{q})}$

where $i_{q}$ is the $q$-th least recommended item, $p(i_{q})$ is the ratio of the recommended times of $i_{q}$ to the recommended times of all the items.

For every user-item pair, say user $u$ and item $i$, an algorithm $\pi$ will produce a score, $\pi\text{-score}(u,i)$, predicting how much user $u$ likes item $i$. Next, we briefly review the famous $P^{3}$ algorithm and three of its improved versions.

1. (1)

   The $P3$ algorithm, also known as NBI [13] or ProbS [14] algorithm, can be seen as a three-step random walk process in the user-item bipartite network. The walker starts on the target user $u$, and at each step moves to randomly chosen one of its neighbor nodes, finally arrives the target item $i$ after three steps. The transition probability of the walker from current node to its neighbor node is equal to the reciprocal of the degree of current node. Therefore, the transition probability from $u$ to $i$ is

   $P3\text{-score}(u,i)=\sum\limits_{j=1}^{n}\sum\limits_{v=1}^{m}{\frac{a_{uj}a_{vj}a_{vi}}{k_{u}k_{j}k_{v}}}$.

   Since the transition probability of the first step is identical for the same user, the divisor $k_{u}$ is deleted from the above formula in the remainder of this paper.

2. (2)

   The $P^{3}_{\alpha}$ algorithm [15], raises the transition probability of $P^{3}_{\alpha}$ to the power of $\alpha$, i.e.,

   $P_{\alpha}^{3}\text{-score}(u,i)=\sum\limits_{j=1}^{n}\sum\limits_{v=1}^{m}{\frac{a_{uj}a_{vj}a_{vi}}{(k_{j}k_{v})^{\alpha}}}$

   where the parameter $\alpha$ ranges over the real numbers. we can see that when $0<\alpha<1$, the transition probability of every step is zoomed in, and $\alpha>1$ zoomed out. However, the zoom scale of unpopular items is much smaller than that of popular ones.

3. (3)

   The $RP_{\beta}^{3}$ algorithm [16], introduces a simple re-ranking procedure dependent on the popularity of target item into the score of $P^{3}$ as follows,

   $RP_{\beta}^{3}\text{-score}(u,i)=\frac{1}{k_{i}^{\beta}}\sum\limits_{j=1}^{n}\sum\limits_{v=1}^{m}{\frac{a_{uj}a_{vj}a_{vi}}{k_{j}k_{v}}}$

   where the parameter $\beta$ ranges over the non-negative numbers. we can see that if $\beta=0$, it reduces to $P3$. When $\beta>0$, the popular items will get smaller scores, and the larger is $\beta$, the stronger is the score suppression of popular items.

4. (4)

   The $HHP$ algorithm [14], is a nonlinear hybrid of ProbS and HeatS, which is written as,

   $HHP\text{-score}(u,i)=\sum\limits_{j=1}^{n}\frac{a_{uj}}{k_{i}^{1-\lambda}k_{j}^{\lambda}}\sum\limits_{v=1}^{m}{\frac{a_{vj}a_{vi}}{k_{v}}}$

   where the parameter $\lambda$ ranges from 0 to 1. when $\lambda=1$, it reduces to ProbS or $P3$, and when $\beta=0$, it reduces to HeatS.

Compared with the original $P3$ algorithm, all the three improved ones can greatly increase the recommendation diversity and accuracy, of course to different extents [14, 15, 16]. Besides the above listed three algorithms, P3 is also improved in many other ways [17, 18, 19, 20, 21]. The interested reader is referred to a survey article for comprehensive comparisons [22].

Given a user $u$, we rank all his uncollected items in descending order of $\pi\text{-score}(u,i_{t})$, $t\in\{1,2,\cdots,n\}$, and refer to the rank number of item $i_{t}$ in this sequence as the forward rank number, denoted by $\text{f-rank}^{\pi}(u,i_{t})$. Given an item $i$, all the users who do not collect it are ranked in descending order of $\pi\text{-score}(u_{k},i)$, $k\in\{1,2,\cdots,m\}$, then we can similarly define the backward rank number $\text{b-rank}_{\pi}(u_{k},i)$. In short, a specified user-item pair is corresponding to two different rank numbers, f-rank number and b-rank number, respectively from the viewpoints of user and item.

Following the results of $P3$ algorithm on Movielens and Netflix data sets, we present two scatter plots of the f-rank number against the b-rank number of the same user-item pair in Figure 2, respectively for three manually chosen values of small, median and large item degree. It is observed that the f-rank number exhibits a negative correlation with the item degree. This means that most unpopular items seldom get the opportunity to be recommended to users, and a few popular items always appear in the head of recommendation lists. That is why the recommendation coverage of P3 algorithm is not that good. Different from the f-rank numbers, the b-rank numbers for three values of item degree, are almost uniformly distributed in the whole range, which is preferred by a personalized recommender system.

Based on this observation, we introduce the aggregation rank number, which is a weighted linear aggregation of the forward and backward rank numbers, defined by

$\text{ag-rank}^{\pi}(u,i)=(1-\lambda)*\text{f-rank}^{\pi}(u,i)+\lambda*\text{b-rank}^{\pi}(u,i)$,

where $\lambda$ is an adjustable parameter ranging in closed interval [0,1]. Finally, we give a target user a recommendation list of his uncollected items in ascending order of this aggregation rank number. We call this re-ranking framework as Two Way Ranking Aggregation, shorted by TWRA, and accordingly denote the algorithm $\pi$ combined with this framework as TWRA($\pi$). when $\lambda=0$, the framework reduces to the original algorithm $\pi$. while $\lambda=1$, the framework will produce recommendation results merely from the standpoint of items, regardless of user experience.

Figure 3 plots the performance of TWRA($P^{3}$) model against the parameter $\lambda$ on MovieLens and Netflix data sets, respectively. The length of recommendation list is set to 20. We find that as the parameter $\lambda$ is traversed from 0 to 1, the values of diversity and coverage increase in most of the range, and fall down when $\lambda$ approaches 1. The curves of accuracy have a slightly rising head and a long dropping tail, where the $\lambda$ value for the break point is closer to 0 than 1 on both data sets. In a word, the coverage/diversity values and the accuracy values become a trade-off in most range of $\lambda$, with a short coincident increase when $\lambda$ is small. Therefore, we empirically choose the optimal $\lambda$ value to be 0.3 and 0.4 respectively on Movielens and Netflix data sets in the following performance comparison.

Table 2 summarizes the detailed values of evaluation measures on two data sets when the length of recommendation list is set to 20. Compared with the original $P3$ algorithm, TWRA($P3$) model greatly improves the values of Hamming Distance and Gini coefficient by 70.5% and 792% on Movielens data set, and 48% and 2875% on Netflix data set. What is more, TWRA($P3$) model also improves the accuracy value by 42.6%. The significant improvements on Gini coefficient again confirm the disadvantage of popularity bias of original $P3$ algorithm.

According to Table 2, TWRA($P3$) model beats state-of-the art P3 improved algorithms on Hamming Distance and Gini coefficient, while its accuracy is also comparable. Compared with the second-best $RP^{3}_{\beta}$ algorithm, the increased percentage of TWRA($P3$) on diversity and coverage is much larger on Netflix than Movielens data set, and the accuracy is better on Netflix data set but a little worse on Movielens data set. Thus, we get the conclusion that TWRA framework play a more significant role in sparser (Netflix) than denser (Movielens) data set. The possible reason is that the sparser is the data set, the information that can be utilized by recommendation algorithm is less, where the reversed rank will provide useful supplement to the direct recommendation. Since most of current commercial recommender systems are deployed on sparse user-item networks, our proposed rank aggregation framework is of great practical significance.