Year: 2021

Abstract:
We explore the fairness issue that arises in recommender systems. Biased data due to inherent stereotypes of particular groups (e.g., male students’ average rating on mathematics is often higher than that on humanities, and vice versa for females) may yield a limited scope of suggested items to a certain group of users. Our main contribution lies in the introduction of a novel fairness notion (that we call equal experience), which can serve to regulate such unfairness in the presence of biased data. The notion captures the degree of the equal experience of item recommendations across distinct groups. We propose an optimization framework that incorporates the fairness notion as a regularization term, as well as introduce computationally-efficient algorithms that solve the optimization. Experiments on synthetic and benchmark real datasets demonstrate that the proposed framework can indeed mitigate such unfairness while exhibiting a minor degradation of recommendation accuracy.

heading: 1 INTRODUCTION
text: Recommender systems are everywhere, playing a crucial role to support decision making and to decide what we experience in our daily life. One recent challenge concerning fairness arises when the systems are built upon biased historical data. Biased data due to polarized preferences of particular groups for certain items may often yield limited recommendation service. For instance, if female students exhibit high ratings on literature subjects and less interest in math and science relative to males, the subject recommender system trained based on such data may provide a narrow scope of recommended subjects to the female group, thereby yielding unequal experience. This unequal experience across groups may result in amplifying the gender gap issue in science, technology, engineering, and mathematics (STEM) fields.
Among various works for fair recommender systems (Yao & Huang, 2017; Li et al., 2021; Kamishima & Akaho, 2017; Xiao et al., 2017; Beutel et al., 2019; Burke, 2017), one recent and most relevant work is Yao & Huang (2017). They focus on a scenario in which unfairness occurs mainly due to distinct recommendation accuracies across different groups. They propose novel fairness measures that quantify the degree of such unfairness via the difference between recommendation accuracies, and also develop an optimization framework that well trades the fairness measures against the average accuracy. However, it comes with a challenge in ensuring fairness w.r.t. the unequal experience. This is because similar accuracy performances between different groups do not guarantee a variety of recommendations to an underrepresented group with historical data bearing low preferences and/or scarce ratings for certain items. For instance, in the subject recommendation, the fairness notion may not serve properly, as long as female students exhibit low ratings (and/or lack of ratings) on math and science subjects due to societal/cultural influences (and/or sampling biases). Furthermore, if the recommended items are selected only according to the overall preference, the biased preference for a specific item group will further increase, and the exposure to the unpreferred item group will gradually decrease.
Contribution: In an effort to address the challenge, we introduce a new fairness notion that we call equal experience. At a high level, the notion represents how equally various items are suggested even for an underrepresented group preserving such biased historical data. Inspired by an informationtheoretic notion “mutual information” (Cover, 1999) and its key property “chain rule”, we quantify our notion so as to control the level of independence between preference predictions and items for any group of users. Specifically, the notion encourages prediction Ỹ (e.g., 1 if a user prefers an item; 0 otherwise) to be independent of the following two: (i) user group Zuser (e.g., 0 for male; and 1 for
female); and (ii) item group Zitem (e.g., 0 for mathematics; and 1 for literature). In other words, it promotes Ỹ ⊥ (Zuser, Zitem); which in turns ensures all of the following four types of independence that one can think of: Ỹ ⊥ Zitem, Ỹ ⊥ Zuser, Ỹ ⊥ Zitem|Zuser, and Ỹ ⊥ Zuser|Zitem. This is inspired by the fact that mutual information being zero is equivalent to the independence between associated random variables, as well as the chain rule:
I(Ỹ ;Zuser, Zitem) = I(Ỹ ;Zitem) + I(Ỹ ;Zuser|Zitem) = I(Ỹ ;Zuser) + I(Ỹ ;Zitem|Zuser).
(1)
See Section 3.1 for details. The higher independence, the more diverse recommendation services are offered for every group. We also develop an optimization framework that incorporates the quantified notion as a regularization term into a conventional optimization for collaborative filtering in recommender systems (e.g., the one based on matrix completion Koren (2008); Koren et al. (2009)). Here one noticeable feature of our framework is that the fairness performances w.r.t. the above four types of independence conditions can be gracefully controlled via a single unified regularization term. This is in stark contrast to prior works (Yao & Huang, 2017; Li et al., 2021; Kamishima & Akaho, 2017; Mehrotra et al., 2018), each of which promotes only one independence condition or two via two separate regularization terms. See below Related works for details. In order to enable an efficient implementation of the fairness constraint, we employ recent methodologies developed in the context of fair classifiers, such as the ones building upon kernel density estimation (Cho et al., 2020a), mutual information (Zhang et al., 2018; Kamishima et al., 2012; Cho et al., 2020b), or covariance (Zafar et al., 2017a;b). We also conduct extensive experiments both on synthetic and two benchmark real datasets: MovieLens 1M (Harper & Konstan, 2015) and Last FM 360K (Celma, 2010). As a result, we first identify two primary sources of biases that incur unequal experience: population imbalance and observation bias (Yao & Huang, 2017). In addition, we demonstrate that our fairness notion can help improve the fairness measure w.r.t. equal experience (to be defined in Section 3.1; see Definition 2) while exhibiting a small degradation of recommendation accuracy.
Related works: In addition to Yao & Huang (2017), numerous fairness notions and algorithms have been proposed for fair recommender systems (Xiao et al., 2017; Beutel et al., 2019; Singh & Joachims, 2018; Zehlike et al., 2017; Narasimhan et al., 2020; Biega et al., 2018; Li et al., 2021; Kamishima & Akaho, 2017; Mehrotra et al., 2018; Schnabel et al., 2016). Xiao et al. (2017) develop fairness notions that encourage similar recommendations for users within the same group. Beutel et al. (2019) consider similar metrics as that in Yao & Huang (2017) yet in the context of pairwise recommender systems wherein pairewise preferences are given as training data. Li et al. (2021) propose a fairness measure that quantifies the irrelevancy of preference predictions to user groups, like demographic parity in the fairness literature (Feldman et al., 2015; Zafar et al., 2017a;b). Specifically, they consider the independence condition between prediction Ỹ and user group Zuser: Ỹ ⊥ Zuser. Actually this was also considered as another fairness measure in Yao & Huang (2017). Similarly, other works with a different direction consider the similar notion concerning the independence w.r.t. item group Zitem: Ỹ ⊥ Zitem (Kamishima & Akaho, 2017; Singh & Joachims, 2018; Biega et al., 2018). Mehrotra et al. (2018) incorporate both measures to formulate a multi-objective optimization. In Section 2.2, we will elaborate on why the above prior fairness notions cannot fully address the challenge w.r.t. unequal experience.
There has been a proliferation of fairness notions in the context of fair classifiers: (i) group fairness (Feldman et al., 2015; Zafar et al., 2017b; Hardt et al., 2016; Woodworth et al., 2017); (ii) individual fairness (Dwork et al., 2012; Garg et al., 2018); (iii) causality-based fairness (Kusner et al., 2017; Nabi & Shpitser, 2018; Russell et al., 2017; Wu et al., 2019; Zhang & Bareinboim, 2018b;a). Among various prominent group fairness notions, demographic parity and equalized odds give an inspiration to our work in the process of applying the chain rule, reflected in equation 1. Concurrently, a multitude of fairness algorithms have been developed with the use of covariance (Zafar et al., 2017a;b), mutual information (Zhang et al., 2018; Kamishima et al., 2012; Cho et al., 2020b), kernel density estimation (Cho et al., 2020a) or Rényi correlation (Mary et al., 2019) to name a few. In this work, we also demonstrate that our proposed framework (to be presented in Section 3) embraces many of these approaches; See Remark 1 for details.

heading: 2 PROBLEM FORMULATION
text: As a key technique for operating recommender systems, we consider collaborative filtering which estimates user ratings on items. We first formulate an optimization problem for collaborative filtering building upon one prominent approach, matrix completion. We then introduce a couple of fairness measures proposed by recent prior works (Yao & Huang, 2017; Li et al., 2021; Kamishima & Akaho, 2017), and present an extended optimization framework that incorporates the fairness measures as regularization terms.

heading: 2.1 OPTIMIZATION BASED ON MATRIX COMPLETION
text: As a well-known approach for operating recommender systems, we consider matrix completion (Fazel, 2002; Koren et al., 2009; Candès & Recht, 2009). Let M ∈ Rn×m be the ground-truth rating matrix where n and m denote the number of users and items respectively. Each entry, denoted by Mij , can be of any type. It could be binary, five-star rating, or any real number. Denote by Ω the set of observed entries of M . For simplicity, we assume noiseless observation. Denote by M̂ ∈ Rn×m an estimate of the rating matrix.
Matrix completion can be done via the rank minimization that exploits the low-rank structure of the rating matrix. However, since the problem is NP-hard (Fazel, 2002), we consider a well-known relaxation approach that intends to minimize instead the squared error between M and M̂ in the observed entries:
min M̂ ∑ (i,j)∈Ω (Mij − M̂ij)2. (2)
There are two well-known approaches for solving the optimization in equation 2: (i) matrix factorization (Abadir & Magnus, 2005; Koren et al., 2009); and (ii) neural-net-based parameterization (Salakhutdinov et al., 2007; Sedhain et al., 2015; He et al., 2017). Matrix factorization assumes a certain structure on the rating matrix: M = LR where L ∈ Rn×r and R ∈ Rr×m. One natural way to search for optimal L∗ and R∗ is to apply gradient descent (Robbins & Monro, 1951) w.r.t. all of the Lij’s and Rij’s, although it does not ensure the convergence of the optimal point due to non-convexity. The second approach is to parameterize M̂ via neural networks such as restricted Boltzmann machine (Salakhutdinov et al., 2007) and autoencoder (Sedhain et al., 2015; Lee et al., 2018). For instance, one may employ an autoencoder-type neural network which outputs a completed matrix M̂ fed by the partially-observed version of M . For a user-based autoencoder (Sedhain et al., 2015), an observed row vector of M is fed into the autoencoder, while an observed column vector serves as an input for an item-based autoencoder (Sedhain et al., 2015). In this work, we consider the two approaches in our experiments: matrix factorization with gradient descent; and autoencoder-based parameterization.
One common way to promote a fair recommender system is to incorporate a fairness measure, say Lfair (which we will relate to an estimated matrix M̂ ), as a regularization term into the above base optimization in equation 2:
min M̂
(1− λ) ∑
(i,j)∈Ω
(Mij − M̂ij)2 + λ · Lfair (3)
where λ ∈ [0, 1] denotes a normalized regularization factor that balances prediction accuracy against the fairness constraint. For the fairness-regularization term Lfair, several fairness measures have been introduced.

heading: 2.2 FAIRNESS MEASURES IN PRIOR WORKS (YAO & HUANG, 2017; KAMISHIMA & AKAHO,
text: 2017; LI ET AL., 2021)
We list three of them, which are mostly relevant to our framework to be presented in Section 3. For illustrative purpose, we will explain them in a simple setting where there are two groups of users, say the male groupM and the female group F . The first is value unfairness proposed by Yao & Huang (2017). It quantifies the difference between prediction errors across the two groups of users over the
entire items:
VAL := 1
m m∑ j=1 ∣∣∣∣ 1|MΩ| ∑ (i,j)∈Ω:i∈M
(Mij − M̂ij)︸ ︷︷ ︸ prediction error w.r.t.M
− 1 |FΩ| ∑ (i,j)∈Ω:i∈F
(Mij − M̂ij)︸ ︷︷ ︸ prediction error w.r.t. F ∣∣∣∣ (4) whereMΩ and FΩ denote the male and female group w.r.t. observed entries, respectively. While the measure promotes fairness w.r.t. prediction accuracy across distinct groups, it may not ensure fairness w.r.t. the diversity of recommended items to users. To see this clearly, consider an extreme scenario in which the ground truth rating is very small Mij∗ ≈ 0 for a certain item j∗ (say science subject) for all i ∈ F . In this case, minimizing VAL may encourage M̂ij∗ ≈ 0 for all i ∈ F . This then incurs almost no recommendation of the science subject to the females, thus giving no opportunity to experience the subject. This motivates us to propose a new fairness measure (to be presented in Section 3.1) that helps mitigate such unfairness.
On the other hand, Kamishima & Akaho (2017) introduce another fairness measure, which bears a similar spirit to demographic parity in the fairness literature (Feldman et al., 2015; Zafar et al., 2017a;b). The measure, named Calders and Verwer’s discrimination score (CVS), quantifies the level of irrelevancy between preference predictions and item groups. To describe it in detail, let us introduce some notations. Let Zitem be a sensitive attribute w.r.t. item groups, e.g., Zitem = 0 (literature) and Zitem = 1 (science). Let Ŷ be a generic random variable w.r.t. estimated ratings M̂ij’s. To capture the preference prediction, let us consider a simple binary preference setting in which Ỹ := 1{Ŷ ≥ τ} where τ indicates a certain threshold. Specializing the measure into the one like demographic parity, it can be quantified as:
CVS := |P(Ỹ = 1|Zitem = 1)− P(Ỹ = 1|Zitem = 0)|. (5) Minimizing the measure encourages the independence between Ỹ and Zitem, thereby promoting the same rating statistics across different groups. However, it does not necessarily ensure the same statistics when we focus on a certain group of users. It guarantees the independence only in the average sense. To see this clearly, consider a simple scenario in which there are two groups of users, say female and male. Let Zuser be another sensitive attribute w.r.t. user groups, e.g., Zuser = 0 (female) and Zuser = 1 (male). Fig. 1 illustrates a concrete example where Ỹ is independent of Zitem. Notice that the number of 1’s w.r.t. Zitem = 0 (over the entire user groups) is the same as that w.r.t. Zitem = 1. However, focusing on a certain user group, say Zuser = 0, Ỹ is highly correlated with Zitem. Observe in the case Zuser = 0 that the number of 1’s is 9 for Zitem = 0, while it reads 0 for Zitem = 1.
Li et al. (2021) consider a similar measure, named user-oriented group fairness (UGF), yet which targets the independence w.r.t. user groups. Similar to CVS, we can define it by replacing Zitem with Zuser in equation 5:
UGF := |P(Ỹ = 1|Zuser = 1)− P(Ỹ = 1|Zuser = 0)|. (6)
However, by symmetry, the high correlation issue discussed via Fig. 1 still arises.

heading: 3 PROPOSED FRAMEWORK
text: We first propose new fairness measures that can regulate fairness w.r.t. the opportunity to experience inherently-low preference items, as well as address the high correlation issue discussed as above. We then develop an integrated optimization framework that unifies the fairness measures as a single regularization term. Finally we introduce concrete methodologies that can implement the proposed optimization.

heading: 3.1 NEW FAIRNESS MEASURES
text: The common limitation of the prior fairness measures (Yao & Huang, 2017; Kamishima & Akaho, 2017; Li et al., 2021) is that the independence between preference predictions and item groups may not be guaranteed for a certain group of users. This motivates us to consider the conditional independence as a new fairness notion, formally defined as below.
Definition 1 (Equalized Recommendation) A recommender system is said to respect “equalized recommendation” if its prediction Ỹ is independent of item’s sensitive attribute Zitem given user’s sensitive attribute Zuser: Ỹ ⊥ Zitem|Zuser.
Inspired by the quantification methods w.r.t. equalized odds in the fairness literature (Jiang et al., 2019; Donini et al., 2018; Hardt et al., 2016; Woodworth et al., 2017), we quantify the new notion via:
DER := ∑
z1∈Zuser ∑ z2∈Zitem ∣∣∣P(Ỹ = 1|Zuser = z1)− P(Ỹ = 1|Zitem = z2, Zuser = z1)∣∣∣, (7) for arbitrary alphabet sizes |Zuser| and |Zitem|. Here DER stands for the difference w.r.t. two interested probabilities that arise in equalized recommendation, and this naming is similar to those in prior fairness metrics (Donini et al., 2018; Jiang et al., 2019). It captures the degree of violating equalized recommendation via the difference between the conditional probability and its marginal given Zuser. Notice that the minimum DER = 0 is achieved under “equalized recommendation”. One may consider another measure which takes “max” operation instead of “ ∑ ” in equation 7 or a different measure based on the ratio of the two associated probabilities. We focus on DER in equation 7 for tractability of an associated optimization problem that we will explain in Section 3.2.
The constraint of “equalized recommendation” encourages the same prediction statistics of items for every user group, thereby promoting the equal chances of experiencing a variety of items for all individuals. However, the notion comes with a limitation. The limitation comes from the fact that conditional independence does not necessarily imply independence (Cover, 1999):
Ỹ ⊥ Zitem|Zuser 6=⇒ Ỹ ⊥ Zitem. (8) Actually, the ultimate goal of a fair recommender system is to ensure all of the following four types of independence:
Ỹ ⊥ Zitem, Ỹ ⊥ Zuser|Zitem, Ỹ ⊥ Zuser, Ỹ ⊥ Zitem|Zuser. (9) One natural question that arises is then: What is a proper fairness notion which allows us to respect all of the above four conditions preferably in one shot? In an attempt to succinctly represent all of the four conditions, we invoke an information-theoretic notion, mutual information (Cover, 1999). One key property of mutual information, called the chain rule, gives an insight:
I(Ỹ ;Zuser, Zitem) = I(Ỹ ;Zitem) + I(Ỹ ;Zuser|Zitem) = I(Ỹ ;Zuser) + I(Ỹ ;Zitem|Zuser).
(10)
From this, we can readily see that
I(Ỹ ;Zuser, Zitem) = 0 =⇒ I(Ỹ ;Zitem) = 0, I(Ỹ ;Zuser|Zitem) = 0, I(Ỹ ;Zuser) = 0, I(Ỹ ;Zitem|Zuser) = 0.
(11)
This is due to the non-negativity property of mutual information. The key observation in equation 11 motivates us to propose a new fairness notion that we call equal experience.
Definition 2 (Equal Experience) A recommender system is said to respect “equal experience” if its prediction Ỹ is independent of both Zitem and Zuser: Ỹ ⊥ (Zitem, Zuser).
Similar to DER, we also quantify the notion as the difference between the conditional probability and its marginal:
DEE := ∑
z1∈Zuser ∑ z2∈Zitem ∣∣∣P(Ỹ = 1)− P(Ỹ = 1|Zitem = z2, Zuser = z1)∣∣∣ , (12) for arbitrary alphabet sizes |Zuser| and |Zitem|. We also coin the similar naming: DEE (difference w.r.t. two interested probabilities that arise in equal experience).

heading: 3.2 FAIRNESS-REGULARIZED OPTIMIZATION
text: Taking DEE as the fairness-regularization term Lfair in the focused framework (equation 3), we get:
min M̂
(1− λ) ∑
(i,j)∈Ω
(Mij − M̂ij)2 + λ · DEE (13)
where λ ∈ [0, 1] denotes a normalized regularization factor. Here one challenge that arises in equation 13 is that expressing DEE in terms of an optimization variable M̂ is not that straightforward.
To overcome the challenge, we take the kernel density estimation (KDE) technique (Cho et al., 2020a) which enables faithful quantification of fairness-regularization terms. One key benefit of the KDE approach is that the computed measures based on KDE is differentiable w.r.t. model parameters, thus enjoying a family of gradient-based optimizers (Géron, 2019; Kingma & Ba, 2014b). Since the problem context where the KDE technique (Cho et al., 2020a) was introduced is different from ours, we describe below details on the technique, tailoring it to our framework.
Implementation of DEE via the KDE technique (Cho et al., 2020a): We first parameterize prediction output M̂ via matrix factorization or a neural network. Let w be a collection of parameters w.r.t. M̂ . It could be a collection of matrix entries of L and R when employing matrix factorization M̂ = LR. Or it could be a collection of neural network parameters in the latter case.
The key idea of the KDE technique is to approximate the interested probability distributions via kernel density estimator defined below:
Definition 3 (Kernel Density Estimator (KDE) (Davis et al., 2011)) Let (ŷ(1), . . . , ŷ(s)) be i.i.d. examples drawn from a distribution with an unknown density f . Its KDE is defined as: f̂(ŷ) := 1 sh ∑s i=1 fk ( ŷ−ŷ(i) h ) where fk is a kernel function (e.g., Gaussian kernel function (Davis et al., 2011)) and h > 0 is a smoothing parameter called bandwidth.
For DEE, the interested probability distributions are P(Ỹ = 1) and P(Ỹ = 1|Zitem = z2, Zuser = z1). Let us first consider P(Ỹ = 1). Remember Ỹ := 1{Ŷ ≥ τ}, so Ŷ should be taken into consideration initially. Using the KDE, we can estimate the probability density function of Ŷ , say fŶ (ŷ):
f̂Ŷ (ŷ) = 1
nmh n∑ i=1 m∑ j=1 fk
( ŷ − M̂ij
h
) . (14)
This together with Ỹ := 1{Ŷ ≥ τ} gives:
P̂(Ỹ = 1) = ∫ ∞ τ f̂Ŷ (ŷ)dŷ = 1 nm n∑ i=1 m∑ j=1 Fk ( τ − M̂ij h )
where Fk(ŷ) := ∫∞ ŷ fk(t)dt. Since the approach relies upon a family of gradient-based optimizers, the gradients of P̂(Ỹ = 1) and P̂(Ỹ = 1|Zitem = z2, Zuser = z1) need to be computed explicitly. Using the technique in Cho et al. (2020a) (Proposition 1 therein), we can readily approximate ∇wDEE. See Appendix A.2 for details.
Remark 1 (Other choices for a measure of “equal experience”) Instead of DEE, one can resort to other measures based on prominent tools employed in the fairness literature: covariance (Zafar et al., 2017a;b), mutual information (Zhang et al., 2018; Kamishima et al., 2012; Cho et al., 2020b), Wasserstein distance (Jiang et al., 2020) and Rényi correlation (Mary et al., 2019). We leave a more detailed explanation in Appendix A.3.

heading: 4 EXPERIMENTS
text: We conduct experiments both on synthetic and two benchmark real datasets: MovieLens 1M (Harper & Konstan, 2015) and Last FM 360K (Celma, 2010). We generate synthetic data so as to pose fairness issues. Algorithms are implemented in PyTorch (Paszke et al., 2019), and experiments are performed on a server with Titan RTX GPUs. All the simulation results (to be reported) are the ones averaged over five trials with distinct random seeds. In Appendix A.6, we also present the running times of our algorithm and baselines on the synthetic and real datasets.

heading: 4.1 SYNTHETIC DATASET
text: Here we highlight two types of bias: population imbalance and observation bias (Yao & Huang, 2017). For illustrative purpose, let us explain them in a simple subject-recommendation example where there are two user groups (Zuser = 0 for male and Zuser = 1 for female) and two item groups (Zitem = 0 for science and Zitem = 1 for literature). Population imbalance refers to the difference in the ground-truth preferences between two user groups, e.g., for the science subject, male students exhibit higher ratings relative to females. Observation bias is the one that occurs due to the stereotype formed by societal and cultural influences. To understand what it means, let us consider a scenario where a male student equally likes science and literature subjects. But due to the stereotype that male students prefer science to literature in general, there may be very sparse ratings from male students for literature. The system trained based on such data might incorrectly interpret as if male students dislike literature. Such data is said to have observation bias.
We generate synthetic data that bear the two biases in the context of binary ratings, i.e., Mij ∈ {+1 (like),−1 (dislike)}. We divide n users into male and female groups each of n2 , sayM and F . Items are also divided into two groups of m2 , say male-preferred groupM
′ and female-preferred group F ′. To account for population imbalance, we first generate the ground-truth rating matrix M ∈ Rn×m using the following four probabilities: {pMM′ , pMF ′ , pFM′ , pFF ′} where pMM′ indicates the probability that a male student likes a male-preferred subject (science). More precisely, for i ∈M and j ∈M′,
Mij = { +1, w.p. pMM′ ; −1, w.p. 1− pMM′ . (15)
Similarly the other probabilities are defined. To ensure the low-rank structure, say rank r, of the rating matrix, we generate r2 basis rating vectors for male group as per the above preference probabilities, and similarly another set of r2 basis rating vectors is generated for female group. Every male student picks one of the r2 basis vectors w.r.t. the male group uniformly at random, and similarly for every female student. This then yields rank(M) = r.
To control observation bias, we introduce another probability set: {qMM′ , qMF ′ , qFM′ , qFF ′} where qMM′ denotes the probability that a male student’s rating is observed for a male-preferred subject. More precisely, for i ∈M and j ∈M′,
(i, j) ∈ {
Ω, w.p. qMM′ ; Ωc, w.p. 1− qMM′ . (16)
Similarly the other probabilities are defined. For simplicity, throughout all the synthetic data simulations, we assume a symmetric setting in which pMM′ = pFF ′(= p0), pMF ′ = pFM′(= p1), qMM′ = qFF ′(= q0), and qMF ′ = qFM′(= q1).
We consider a setting in which (r, n,m) = (20, 600, 400). We leave a more detailed explanation of experiments on the synthetic dataset in Appendix A.4. First, we check whether the bias actually incurs unfair recommendations. For ease of understanding, we consider two scenarios: (i) population imbalance varies without observation bias; and (ii) observation bias varies without population
imbalance. Fig. 2 (Left) presents the 1st scenario, demonstrating that the fairness performance measured in DEE decreases with an increase in population imbalance, controlled by |p0 − p1|. Fig. 2 (Right) considers the 2nd scenario. We see the same trend yet now w.r.t. the variation of observation bias.
Table 1 presents the prediction error (RMSE) and fairness performances on the synthetic dataset having observation bias (q0, q1) = (0.2, 0.01) yet without population imbalance (p0, p1) = (0.4, 0.4). We consider four fairness measures: (i) DEE (in equation 12); (ii) DER (in equation 7); (iii) VAL (in equation 4); (iv) UGF (in equation 6); (v) CVS (in equation 5). We also compare our algorithm with four baselines: (i) unfair (no fairness constraint); (ii) VAL-based algorithm (Yao & Huang, 2017); (iii) UGF-based algorithm (Li et al., 2021); (iv) CVS-based algorithm (Kamishima & Akaho, 2017). Each baseline, say VAL-based algorithm, achieves the best fairness performance only for VAL, while it does not work well under the other fairness measures. On the other hand, our algorithm offers great fairness performances for all the measures, except for VAL, which our framework does not target.

heading: 4.2 REAL DATASETS
text: We consider two benchmark datasets: MovieLens 1M (Harper & Konstan, 2015), and Last FM 360K (Celma, 2010). We run experiments employing both matrix factorization (MF) based and autoencoder (AE) based techniques. In Appendix A.5, we leave a more detailed explanation of experiments on the real datasets and the results of AE-based technique. The results of real data experiments are listed in Tables 2 and 3. As in the synthetic data setting, we can make two relevant observations. All baseline algorithms fail to respect our metric (DEE) while meeting their own. We also see that our algorithm exhibits significant performances for all the fairness measures except for VAL which does not have close relationship with the equal experience that we aim at.

heading: 5 EXTENSION
text: In this section, we discuss the extension of our work: (i) introducing a new notion that bears a similar spirit to equalized odds, and (ii) applying our notion to the fair ranking context.
Our fairness notion equal experience aims at recommending a variety of items for all user groups. Demographic parity is similar to our notion in the sense of considering the irrelevancy of predictions to groups. On the other hand, equalized odds is the fairness notion that concerns equal error rates (e.g., true/negative positive rate) across user groups by employing the ground-truth label Y . Similar to equalized odds, our measure in recommender systems can readily be extended to a setting in which the ground-truth label is available to exploit. The key idea is to promote Ỹ ⊥ (Zuser, Zitem)|Y . See Appendix A.7 for details.
Many end-to-end recommender systems offer a recommendation list via two processes: (i) candidate generation, and (ii) ranking. In this work, we focus on the first candidate generation which we built collaborative filtering for. But our proposed notion can also be applicable in generating an end ranked list. The idea behind the end-ranked list generation is to define Ỹ as an indicator function which returns 1 when the item of interest belongs to, say top-k item set (0 otherwise). In this case, the same notion Ỹ ⊥ (Zuser, Zitem) serves a proper role. We leave detailed implementation of this notion under the fair ranking context for a future work.

heading: 6 CONCLUSION
text: We introduced a novel fairness notion, equal experience, capable of respecting the desired requirements for fair recommender systems: independence between preference predictions and user groups; conditional independence for a certain user group, and vice versa for item groups. The notion also seamlessly integrates into prior fairness algorithms. Extensive experiments revealed the existence of unfairness (or bias) w.r.t. equal experience, and our fair optimization framework successfully mitigates such unfairness with minimal prediction accuracy loss. Our future work of interest is four-folded: (i) merging our notion with unexamined algorithms relying upon Rényi correlation or Wasserstein distance; (ii) constructing a robust and fair recommender system in the presence of data poisoning; (iii) developing a blind fair recommender system without sensitive attributes; and (iv) extending our notion to fair ranking.

heading: ETHICS STATEMENT
text: The proposed fairness notion and framework (which faithfully respects the notion) will enable a recommender system to offer an enough opportunity for users to experience various groups of items against stereotypes. Users are further influenced by the various experiences when making more essential choices such as choosing a job. Hence, it can give significant impacts upon users who can expand their options via diverse experiences. On the other hand, users provide sensitive information to a service provider of fair recommender systems, and there is a possibility that the user’s sensitive information could be abused. Hence, one future work of great potential might be to develop a framework that ensures fairness even in the blind setting where sensitive information is not available.

heading: REPRODUCIBILITY STATEMENT
text: To ensure the reproducibility of experiments, we provide a step-by-step guideline as to synthetic data construction in Section 4.1. We also provide a thorough description regarding two real datasets, MovieLens 1M (Harper & Konstan, 2015) and Last FM 360K (Celma, 2010), along with data preprocessing methods in Section 4.2. All the hyperparameter settings w.r.t. synthetic and real data experiments are listed in Appendix A.4 and A.5, respectively. We present the average running time of all algorithms together with specific computer configuration details in Appendix A.6. Lastly, the codes are available at https://github.com/cjw2525/FairRec.

heading: A APPENDIX

heading: A.1 OUTLINE
text: In the appendix, we first provide further explanation for the implementation of KDE technique. We also present other choices for a measure of equal experience in further detail. Next, we provide a detailed explanation of experimental settings on both synthetic and real datasets: MovieLens 1M (Harper & Konstan, 2015) and Last FM 360K (Celma, 2010). We then present additional experimental results which are not included in the main paper due to space limitation, and as well as provide a complexity analysis of our approach. We also provide a detailed explanation for the extension of our measure to the fairness notion: Ỹ ⊥ (Zuser, Zitem)|Y , and present experimental results for this extension.
A.2 IMPLEMENTATION OF KDE TECHNIQUE
In order to approximate∇wDEE, we first calculate the gradient of P̂(Ỹ = 1) employing the technique in Cho et al. (2020a):
∇wP̂(Ỹ = 1) = 1
nmh n∑ i=1 m∑ j=1 fk
( τ − M̂ij
h
) · ∇wM̂ij . (17)
We can apply the same procedures w.r.t. the second interested probability P̂(Ỹ = 1|Zitem = z2, Zuser = z1). Merging equation 17 and the counterpart w.r.t. the second probability, we can readily obtain:
∇wDEE ≈ ∑
z1∈Zuser ∑ z2∈Zitem H ′δ ( P̂(Ỹ = 1|Zitem = z2, Zuser = z1)− P̂(Ỹ = 1) ) ×∇w ( P̂(Ỹ = 1|Zitem = z2, Zuser = z1)− P̂(Ỹ = 1)
) (18) where Hδ(x) denotes the Huber loss (Huber, 1992) that takes 12x
2 when |x| ≤ δ; otherwise δ(|x| − 1 2δ).
A.3 OTHER CHOICES FOR A MEASURE OF "equal experience"
Instead of DEE in equation 12, one can resort to other measures based on prominent tools employed in the fairness literature: covariance (Zafar et al., 2017a;b), mutual information (Zhang et al., 2018; Kamishima et al., 2012; Cho et al., 2020b), Wasserstein distance (Jiang et al., 2020) and Rényi correlation (Mary et al., 2019). For instance, the covariance-based approach allows us to take Lfair as:
Lfair = E [ (Ŷ − E[Ŷ ])(Z − E[Z]) ] where Z := (Zitem, Zuser). (19)
Here we use Ŷ instead of Ỹ , as Ỹ incurs non-differentiability, hindering implementation. In the case of mutual information, one can take Lfair as:
Lfair = I(Ŷ ;Zitem, Zuser) ≥ I(Ỹ ;Zitem, Zuser). (20)
Again, for ease of implementation, we employ Ŷ . This choice is also relevant because it serves as an upper bound of I(Ỹ ;Zitem, Zuser). Notice that Ỹ is a function of Ŷ . Reducing I(Ŷ ;Zitem, Zuser) yields the minimization of the interested quantity I(Ỹ ;Zitem, Zuser). For implementation of I(Ŷ ;Zitem, Zuser), we may employ the variational optimization technique in (Zhang et al., 2018; Cho et al., 2020b) to translate it into a function optimization which can also be parameterized. Other choices can also be dealt with properly relying upon the associated techniques in (Jiang et al., 2020; Mary et al., 2019).

heading: A.4 SYNTHETIC DATASET EXPERIMENTS
text: We consider a setting in which (r, n,m) = (20, 600, 400). The synthetic data generated under the setting is randomly split into two subsets: 90% train set and 10% test set. Since Mij ∈ {+1,−1}, we set the threshold τ = 0, i.e., Ỹ = 1{Ŷ ≥ 0}. We train a matrix factorization (MF) based recommender system with the same rank as that of the dataset, i.e., L ∈ R600×20 and R ∈ R20×400. We set hyperparameters (δ, h) = (0.01, 0.01) and λ = 0.99 for KDE-based algorithm implementation. We use Adam optimizer for 1,000 iterations using full gradient. The learning rate is set to 1e-3 and (β1, β2) = (0.9, 0.999). The additional experimental results in a variety of scenarios are listed from Table 4 to 8. We also visualize how the predicted preference rate of item groups for every user group Pr(Ỹ = 1|Zuser, Zitem) changes under our framework. See Fig. 3 and 4.

heading: A.5 REAL DATASETS EXPERIMENTS
text: full.1 We divide user and item groups based on gender and genre, respectively. Action, crime, filme-noir, war are selected as male-preferred genre, whereas children, fantasy, musical, romance are selected as female-preferred genre. We can select male-preferred and femalepreferred genres in a variety of ways based on ratings and observations. For various scenarios, the experimental results with similar trends are obtained, so we report the results for one representative scenario. If we assume that the real dataset is generated from the same model as the synthetic dataset, we can estimate the following probabilities. We empirically estimate the interested probabilities w.r.t. population imbalance as: p̂MM′ = 0.627, p̂MF ′ = 0.517, p̂FM′ = 0.622, and p̂FF ′ = 0.595. Similarly we obtain the estimates for the other probabilities w.r.t. observation bias: q̂MM′ = 0.053, q̂MF ′ = 0.037, q̂FM′ = 0.037, and q̂FF ′ = 0.046.
• Last FM 360K: The associated task is to predict whether the user likes the artist or not. This dataset contains 359,347 users, 294,015 artists, and 17,559,530 play counts, i.e., rating matrix is 0.02% full.2 The data for play counts is converted to binary rating: +1 if counts > average, otherwise −1. We divide user and item groups based on gender and genre, respectively. Since this dataset only contains gender information, we use Last.fm API3 to collect the genre of corresponding artist’s music; the tag was associated with 5,706 artists. We also randomly select 5000 male and 5000 female users. Among 10 genres, we choose hip-hop and musical for male and female preferred genres, respectively. The final rating matrix of 10,000 users and 5,706 artists is 0.55% full. From the real data, we obtain empirical estimates for the interested probabilities w.r.t. population imbalance: p̂MM′ = 0.548, p̂MF ′ = 0.421, p̂FM′ = 0.438 and p̂FF ′ = 0.529. Similarly we obtain the estimates for the other probabilities w.r.t. observation bias: q̂MM′ = 0.0054, q̂MF ′ = 0.0011, q̂FM′ = 0.0036 and q̂FF ′ = 0.0038.
We randomly split the real datasets into 90% train set and 10% test set. In case of MovieLens data, the rating is five-star based, so we set the threshold τ = 3, i.e., Ỹ = 1{Ŷ ≥ 3}. On the other hand, for LastFM dataset, we set τ = 0 as Mij ∈ {+1,−1}. We run experiments employing both matrix factorization (MF) based and autoencoder (AE) based techniques. We set the rank as 512 for MF-based algorithm as was found by hyperparameter search. The structure of the employed autoencoder (Sedhain et al., 2015) is as follows: (i) encoder has two linear layers: 512 nodes with ReLU actiavation and 512 nodes with dropout layer (rate = 0.7) and ReLU activation; (ii) decoder has one layer with 512 nodes. For MovieLens 1M data (five-star ratings), we apply the clipping to the decoder output to fit into the range. For LastFM 360K data (binary rating: +1 and −1), we apply tanh activation. Hyperparameters for KDE-based algorithm are set to (δ, h) = (0.01, 0.01) and λ = 0.9. We use Adam optimizer for 1,000 iterations using full gradient, and the learning rate is
1http://www.movielens.org/ 2http://ocelma.net/MusicRecommendationDataset/lastfm-360K.html 3http://www.last.fm/api
set to 1e-3. Since the main paper contains mostly MF-based experiments, here we only present the performances of autoencoder based algorithm on both real datasets.

heading: A.6 COMPLEXITY ANALYSIS
text: We do complexity analysis of ours in light of other baselines. For comparison, we consider the running time measured under Pytorch on Xeon Silver 4210R CPU and TITAN RTX GPU. Table 11 presents the running times of matrix factorization based algorithms on the synthetic and real datasets. While our approach provides better fairness performance w.r.t. DEE (as in the above tables), it comes at a cost of an increased complexity, around twice relative to the CVS-based algorithm.
A.7 EXTENSION TO THE FAIRNESS NOTION: Ỹ ⊥ Zuser, Zitem|Y
Similar to DEE in equation 12, we quantify the notion via:∑ y∈{0,1} ∑ z1∈Zuser ∑ z2∈Zitem ∣∣∣P(Ỹ = 1|Y = y)− P(Ỹ = 1|Y = y, Zitem = z2, Zuser = z1)∣∣∣, (21) for arbitrary alphabet sizes |Zuser| and |Zitem|.
Using the KDE approach, similarly we can obtain:
P̂(Ỹ = 1|Y = y) = ∫ ∞ τ f̂Ŷ |Y (ŷ|y)dŷ = 1 |Iy| ∑
(i,j)∈Iy
Fk
( τ − M̂ij
h
) ,
where Fk(ŷ) := ∫∞ ŷ fk(t)dt; Yij := 1{Mij ≥ τ}; and Iy := {(i, j) : (i, j) ∈ Ω, Yij = y}. We can then compute the gradien w.r.t. w as:
∇wP̂(Ỹ = 1|Y = y) = 1 |Iy|h ∑
(i,j)∈Iy
fk
( τ − M̂ij
h
) · ∇wM̂ij . (22)
We can then enjoy a family of gradient-based optimizers (Géron, 2017; Kingma & Ba, 2014a). We provide experimental results for the extension on MovieLens 1M (Harper & Konstan, 2015) real dataset. We run experiments employing both matrix factorization (MF) based and autoencoder (AE) based techniques. We demonstrate that the framework based on the extended notion can indeed mitigate such unfairness while exhibiting a minor degradation of recommendation accuracy. The results are listed in Table 12 and 13.

Review summaries:
The presented study argued that a fair recommendation should be independent of both user and item. Therefore, the study introduced a new fairness notion, i.e., equal experience, and further incorporated this fairness notion as a regularisation term in the matrix completion framework to construct a fair recommender system. The proposed method was evaluated with three datasets (one synthetic and two real datasets). 

The paper is concerned with fairness in recommendations. Specifically, there are groups of users and groups of items. Previous work has modelled fairness as the constraint of all user groups having the same accuracy or as the prediction probability being independent of the item group or the user group. In this work, the notion is generalized so that the prediction is independent of both the item and user group. Optimization algorithms are shown to solve this problem along with experimental results.