Recommender systems have been applied successfully in a number of diferent domains, such as, entertainment, commerce, and employment. Their success lies in their ability to exploit the collective behavior of users in order to deliver highly targeted, personalized recommendations. Given that recommenders learn from user preferences, they incorporate diferent biases that users exhibit in the input data. More importantly, there are cases where recommenders may amplify such biases, leading to the phenomenon of bias disparity. In this short paper, we present a preliminary experimental study on synthetic data, where we investigate diferent conditions under which a recommender exhibits bias disparity, and the longterm efect of recommendations on data bias. We also consider a simple re-ranking algorithm for reducing bias disparity, and present some observations for data disparity on real data.
Recommender systems have found applications in a wide range of
domains, including e-commerce, entertainment and social media,
news portals, and employment sites [
One of the most popular classes of recommendation systems
is collaborative filtering. Collaborative Filtering (CF) uses the
collective behavior of all users over all items to infer the preferences of
individual users for specific items [
Bias in recommendations is not necessarily always problematic. For example, it is natural to expect gender bias when recommending clothes. However, gender bias is undesirable when recommending job postings, or information content. Furthermore, we want to avoid the case where the recommender system introduces bias in the data, by amplifying existing biases and reinforcing stereotypes. We refer to this phenomenon, where there is a diference between input and recommendation bias, as bias disparity.
In this paper, we consider the problem of bias disparity in recommendation systems, and we make the following contributions: (a) We define notions of bias and bias disparity for recommender ∗Copyright 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Presented at the RMSE workshop held in conjunction with the 13th ACM Conference on Recommender Systems (RecSys), 2019, in Copenhagen, Denmark. systems; (b) Using synthetic data we study diferent conditions under which bias disparity may appear. We consider the efect of the iterative application of recommendation algorithms on the bias of the data; (c) We present some observations on bias disparity on real data, using the MovieLens1 dataset; (d) We consider a simple re-ranking algorithm for correcting bias disparity, and we study it experimentally. 2
The problem of algorithmic bias, and its flip side, fairness in
algorithms, has attracted considerable attention in the recent years [
One type of recommendation bias that has been considered in the
literature is popularity bias [
These notions of fairness do not take into account the presence of
diferent (protected) groups of users, and diferent item categories
that we consider in this work. This setting is considered in [
Fairness in terms of correcting rating errors for specific groups
of users was studied in [
We consider a set of n users U and a set of m items I. We are given a binary n × m matrix S, where S(u, i) = 1 if user u has selected 1MovieLens 1M: https://grouplens.org/datasets/movielens/1m/ item i, and zero otherwise. Selection may mean that user u liked post i, or that u purchased product i, or that u watched video i.
We assume that users are associated with an attribute AU , that partitions them into groups depending on their value for the attribute. For example, the attribute AU may be the gender of the user, partitioning the users into men and women. We will typically assume that we have two groups, and one of the groups is the protected group. Similarly, we assume that items are associated with an attribute AI , e.g., the genre of a movie, which partitions them into categories, e.g., action and romance movies.
Given the association matrix S, we define the input preference ratio PRS (G, C) of group G for category C as the fraction of selections from group G that are in category C. Formally:
PRS (G, C) = ÍÍuu ∈∈GG ÍÍii ∈∈CI SS((uu,, ii)) (1) This is essentially the conditional probability that a selection is in category C given that it comes from a user in group G.
To assess the importance of this probability we compare it against the probability P (C) = |C |/m of selecting from category C when selecting uniformly at random. We define the bias BS (G, C) of group G for category C as:
BS (G, C) = PRS (G, C) (2)
P (C) Bias values less than 1 denote negative bias, that is, the group G on average tends to select less often from category C, while bias values greater than 1 denote positive bias, that is, that group G favors category C disproportionately to its size.
We assume that the recommendation algorithm outputs for each user u a ranked list of r items Ru . The collection of all recommendations can be represented as a binary matrix R, where R(u, i) = 1 if item i is recommended for user u and zero otherwise. Given matrix R, we can compute the output preference ratio of the recommendation algorithm, PRR (G, C), of group G for category C using Eq. (1), and the output bias BR (G, C) of group G for category C.
To compare the bias of a group G for a category C in the input data S and the recommendations R, we define the bias disparity, that is, the relative change of the bias value.
BD(G, C) = BR (G, C) − BS (G, C) (3)
BS (G, C)
Our definitions of preference ratios and bias are motivated by
concepts of group proportionality, and group fairness considered
in the literature [
For the recommendations, in our experiments, we use a user-based K -Nearest-Neighbors (UserKNN) algorithm. The UserKNN algorithm first computes for each user, u, the set NK (u) of the K most similar users to u. For similarity, it uses the Jaccard similarity, JSim, computed using the matrix S. For user u and item i not selected by u, the algorithm computes a utility value
V (u, i) = Ín Í∈NnK∈N(uK) (JuS)imJS(ium, (nu),Sn(n), i) (4) The utility value V (u, i) is the fraction of the similarity scores of the top-K most similar users to u that have selected item i. To recommend r items to a user, the r items with the highest utility values are selected. 4
In this section, we present experiments with synthetic data. Our goal is to study the conditions under which the UserKNN exhibits bias disparity. 4.1
Users are split into two groups G1 and G2 of size n1 and n2 respectively, and items are partitioned into two categories C1 and C2 of size m1 and m2 respectively. We assume that users in G1 tend to favor items in category C1, while users in group G2 tend to favor items in category C2. To quantify this preference, we give as input to the data generator two parameters ρ1, ρ2, where parameter ρi determines the preference ratio PRS (Gi , Ci ) of group Gi for category Ci . For example, ρ1 = 0.7 means that 70% of the ratings of group G1 are in category C1. The datasets we create consist of 1,000 users and 1,000 items. We assume that each user selects 5% of the items in expectation, and we recommend r = 10 items per user.
We perform two diferent sets of experiments. In the first set, we examine the efect of the preference ratios, and in the second set, the efect of group and category sizes. All reported values are averages over 10 experiments. 4.2
In these experiments, we create datasets with equal-size groups G1 and G2, and equal-size item categories C1 and C2, and we vary the preference ratios of the groups.
4.2.1 Symmetric Preferences: In the first experiment, we assume that the two groups G1 and G2 have the same preference ratios by setting ρ1 = ρ2 = ρ, where ρ takes values from 0.5 to 1, in increments of 0.05. In Figure 1(a), we plot the output preference ratio PRR (G1, C1) (eq. PRR (G2, C2)) as a function of ρ. Note that in this experiment, bias is the preference ratio scaled by a factor of two. We report preference ratios to be more interpretable. The dashed line shows when the output ratio is equal to the input ratio and thus there is no bias disparity. We consider diferent values for K , the number of neighbors. A first observation is that when the input bias is small (PRS ≤ 0.6), the output bias decreases or stays the same. In this case, users have neighbors from both groups. For higher input bias (PRS > 0.6), we have a sharp increase of the output bias, which reaches its peak for PRS = 0.8. In these cases, the recommender polarizes the two groups, recommending items only from their favored category.
In Figure 1(b), we report the preference ratio for all candidate items for recommendation for each user (i.e., if the system recommended all items with non zero utility). Surprisingly, the candidate items are less biased even for high values of the input bias. This shows that: (a) Utility proportional to user-similarity increases bias, since the top-r recommendations with the highest utility are signiifcantly more biased, (b) It is possible to reduce bias by re-ranking the candidate items.
Increasing the value of K increases the output bias. Adding neighbors increases the strength of the signal, and the algorithm discriminates better between the items in the diferent categories, causing 0.5 0.6 0.7 0.8 0.9 1
input preference ratio (c) P RR (G1, C1), asymmetric case 0.5 0.6 0.7 0.8 0.9 1
input preference ratio (d) P RR (G2, C2), asymmetric case 0.5 0.6 0.7 0.8 0.9
input preference ratio (b) Ratio of candidate items
K=10 K=20 K=50 1 it to favor the preferred category. Understanding the role of K is a subject for future study.
4.2.2 Asymmetric Preferences: In this experiment, group G1 has preference ratio ρ1 ranging from 0.5 to 1, while G2 is unbiased with fixed preference ratio ρ2 = 0.5. In Figure 1, we show the recommendation preference ratio for groups G1 (Figure 1(c)) and G2 (Figure 1(d)) as a function of ρ1.
We observe that the output bias of group G1 is amplified at a rate much higher than in Figure 1(a), while group G2 becomes biased towards category C1. Surprisingly, the presence of the unbiased group G2 has an amplifying efect on the bias of G1, rather than a moderating one, more so than an oppositely-biased group. This is due to the fact that the users in the unbiased group G2 provide a stronger signal in favor of category C1, compared to the symmetric case where group G2 is biased over C2. This reinforces the bias in favor of category C1. As expected, the unbiased group adopts the biases of the biased group
In this experiment we examine bias disparity with unbalanced groups and categories.
4.3.1 Varying Group Sizes: We first consider groups of uneven size. We set the size n1 of G1 to be a fraction ϕ of the number of all users n, ranging from 5% to 95%. Both groups have fixed preference ratio ρ1 = ρ2 = 0.7. Figure 2(a) shows the output recommendation preference ratio PRR (G1, C1) as a function of ϕ. The plot of PRR (G2, C2) is the mirror image of this one, so we do not report it.
We observe that for ϕ ≤ 0.3 group G1 has negative bias disparity (PRR (G1, C1) < 0.7). That is, the small group is drawn by the larger group. For medium values of ϕ in [0.35, 0.5], the bias of both groups is amplified, despite the fact that G1 is smaller than G2. The increase is larger for the larger group, but there is increase for the smaller group as well.
We also experimented with the case where G2 is unbiased. In this case G2 becomes biased towards C1 even for ϕ = 0.05, while the point at which the bias disparity for G1 becomes positive is much earlier (ϕ ≈ 0.2). This indicates that a small biased group can have a stronger impact than a large unbiased one.
4.3.2 Varying Category Sizes: We now consider categories of uneven size. We set the size m1 of C1 to be a fraction θ of the number items m, ranging from 10% to 90%. We assume that both groups have fixed preference ratio ρ1 = ρ2 = 0.7. Figure 2(b) shows the recommendation preference ratio PRR (G1, C1) as a function of θ . The plot of PRR (G2, C2) is again the mirror image of this one. 0.8 1 0.5 o it ra0.4 e c n re0.3 e fr e tp0.2 u p tuo0.1 1 o ita0.8 r e ecn0.6 fr e rep0.4 t u tup0.2 o 0 0
Note that as long as θ ≤ 0.7, group G1 has positive bias (greater than 1) for category C1 since bias is equal to ρ1/θ . However, it decreases as the size of the category increases. When the category size is not very large (θ ≤ 0.5), the output bias is amplified regardless of the category size. For θ > 0.7, G1 is actually biased in favor of C2, and this is reflected in the output. There is an interesting range [0.6, 0.7] where G1 is positively biased towards C1 but its bias is weak, and thus the recommendation output is drawn to category C2 by the more biased group.
We observed bias disparity in the output of the recommendation algorithm. However, how does this afect the bias in the data? To study this we consider a scenario where the users accept (some of) the recommendations of the algorithm, and we study the longterm efect of the iterative application of the algorithm on the bias of the data. More precisely, at each iteration, we consider the top-r recommendations of the algorithm (r = 10) to a user u, and we normalize their utility values, by the utility value of the top recommendation. We then assume that the user accepts a recommendation with probability equal to the normalized score. The accepted recommendations are added to the data, and they are fed as input to the next iteration of the recommendation algorithm.
We apply this iterative algorithm on a dataset with two equally but oppositely biased groups, as described in Section 4.2.1. The results of this iterative experiment are shown in Figure 3(a), where we plot the average preference ratio for each iteration. Iteration 0 corresponds to the input data. In our experiment a user accepts on average 7 recommendations. For this experiment we set the number of neighbors K to 50.
We observe that even with the probabilistic acceptance of recommendations, there is a clear long-term efect of the recommendation bias. For small values of input bias, we observe a decrease, in line with the observations in Figure 1(a). For these values of bias, the recommender will result in reducing bias and smoothing out differences. The value of preference ratio 0.6 remains more or less constant, while for larger values the bias in the data increases. Therefore, for large values of bias the recommender has a reinforcing efect, which in the long term will lead to polarized groups of users. 5
In this experiment, we use the Movielens 1M dataset2. We consider as categories the genres Action and Romance, with 468 and 463 movies. We extract a subset of users U that have at least 90 ratings in these categories, resulting in 1,259 users. Users in U consist of 981 males and 278 females.
In Table 1, we show the input/output bias and in parentheses the bias disparity for each group-category combination. The right part of the table reports these numbers when the user groups are balanced, by selecting a random sample of 278 males. We observe that males are biased in favor of Action movies while females prefer Romance movies. The application of UserKNN increases the strong input bias for males in the output. Females are moderately biased in favor of Romance movies. Hence, their output bias is drawn to Action items. We observe a very similar picture for balanced data, indicating that the changes in bias are not due to the group imbalance.
To address the problem of bias disparity, we consider an algorithm that performs post-processing of the recommendations. Our goal is to adjust the set of recommended items, so as to ensure that there is no bias disparity. In addition, we would like the new recommendation set to have the maximum possible utility.
Abusing the notation, let R∗ denote the set of user-item pairs produced by our recommendation algorithm, where (u, i) ∈ R∗ 2MovieLens 1M: https://grouplens.org/datasets/movielens/1m/ denotes that u was recommended item i. We will refer to the pair (u, i) as a recommendation. The set R∗ contains r recommendations for each user, thus, rn recommendations in total. Let V (R∗) = Í(u,i)∈R∗ V (u, i) denote the total utility of the recommendations in set R∗. Since R∗ contains for each user u the top-r items with the highest utility, R∗ has maximum possible utility among all sets with r recommendations per user.
However, as we have seen in our experiments, the set R∗ may have high bias disparity. We will adjust the recommendations in the set R∗ to produce a new set of recommendations R, with r recommendations per user, with zero bias disparity. Clearly this will come at the expense of utility. Our goal is to find the set R with the minimum utility loss.
Since we have two categories, to achieve zero bias disparity, it sufices to have BR (Gi , Ci ) = BS (Gi , Ci ). Without loss of generality assume that BR∗ (Gi , Ci ) > BS (Gi , Ci ). Let Ci denote the category other than Ci . We decrease the output bias BR by swapping recommendations (u, i) of category Ci with recommendations (u, j) of category Ci . Given a target bias value, we can compute the number of swaps for achieving zero bias disparity. The utility loss incurred by swapping (u, i) with (u, j) is V (u, i) − V (u, j). The goal is to find the swaps with the minimum utility loss.
We present a simple and eficient greedy algorithm for this task. Let NS denote the desired number of swaps. The algorithm starts with the set R = R∗, and performs NS steps. At each step it computes a set of candidate swaps by pairing for each user u the lowest-ranked recommendation (u, i) in R from category Ci , with the highest ranked recommendation (u, j) not in R from category Ci , and performs the swap with the minimum utility loss. It is easy to show that the algorithm is optimal, that is, it achieves the minimum utility loss. We refer to this algorithm as the GULM (Group Utility Loss Minimization) algorithm.
By design, when we apply the GULM algorithm on the output of the recommendation algorithm, we eliminate bias disparity (modulo rounding errors) in the recommendations. We consider the iterative application of the recommendation algorithm, in the setting described in Section 4.4, assuming again that the probability of a recommendation being accepted depends on its utility. The results are shown in Figure 3(b). For values of preference ratio up to 0.65, we observe that bias remains more or less constant after re-ranking. For larger values, there is some noticeable increase in the bias, albeit significantly smaller than before re-ranking. The increase is due to the fact that the recommendations introduced by GULM have low probability to be accepted. 7
In this short paper, we performed a preliminary study of bias disparity in recommender systems, and the conditions under which it may appear. Using synthetic data, we observed that recommendation algorithms can introduce bias disparity even for moderately biased groups. We view this analysis as a first step towards a systematic analysis of the factors that cause bias disparity. We intend to investigate more recommendation algorithms, and more datasets, including the case of numerical, rather than binary, ratings. It is also interesting to examine this work in the context of other definitions for bias and fairness.