Reducing Disparate Exposure in Ranking: A Learning To Rank Approach

Introduction

Ranked search results have become the main mechanism by which we find content, products, places, and people online. These rankings are typically constructed to provide maximum utility to searchers, by ordering items by decreasing probability of being relevant (Robertson 1977). However, when the items to be ranked represent people, businesses, or places, ranking algorithms have consequences that go beyond immediate utility for searchers. Researchers have become increasingly concerned with various systematic biases (Friedman and Nissenbaum 1996) against socially-salient groups, caused by historic and current discriminatory patterns making their way into data-driven models. A common element in this line of research is the presence of a historically and currently disadvantaged protected group, and the concern of disparate impact, i.e., loss of opportunity for the protected group independently of whether they are (intentionally) treated differently. In the case of rankings, a natural way of understanding disparate impact is by considering differences in exposure (Singh and Joachims 2018) or inequality of attention (Biega et al. 2018), which translate into systematic differences in access to economic or social opportunities.

Disparate exposure in rankings. A number of issues, sometimes appearing jointly, call for reducing disparate exposure in information retrieval systems. First, there can be a situation in which minimal differences in relevance translate into large differences in exposure across groups (Singh and Joachims 2018; Biega et al. 2018), because of the large skew in the distribution of exposure brought by positional bias (Joachims et al. 2017). Second, there can be a legal requirement that requires protected elements to be given sufficient visibility among the top positions in a ranking (Zehlike et al. 2017; Celis et al. 2017). Third, there can be systematic discrepancies in the way in which documents are constructed, as in the case of certain sections in online resumes, which are completed differently by men and women (Altenburger et al. 2017); these discrepancies may in turn systematically affect ranking algorithms. Fourth, there can be systematic differences in the way ground truth rankings have been generated due to historical discrimination and/or annotator bias. These issues point to two conceptually different goals: reducing inequality of opportunity (as defined by O’Neill 1977) and reducing discrimination (as defined by Roemer 1998, chapter 12). Equality of opportunity seeks to correct a historical or present disadvantage for a group in society. Non-discrimination seeks to allocate resources in a way that does not consider irrelevant attributes.

Fairness-aware methods. These methods can be classified into pre-, in- and post-processing approaches, where pre-processing methods seek to mitigate discriminatory bias in training data, in-processing methods learn a bias-free model, and post-processing methods re-rank output items (Hajian et al. 2016). For rankings, several post-processing methods have been presented in the literature (Biega et al. 2018; Celis et al. 2017; Singh and Joachims 2018; Zehlike et al. 2017). Yet the post-processing approach has several limitations. First, the idea inherently suggests that there is always a trade-off between an optimally fair and an optimally relevant ranking, because a presumably “exact” model produces a “relevant” ranking that is then reordered to meet fairness constraints. Yet our experiments reveal that reducing bias against a protected group can increase relevance (Section 6.2). Second, a post-processing procedure still allows an unfair ranking model to be trained on biased features and later deployed. To achieve a fair outcome the only possibility using post-processing is to apply a predefined anti-discrimination policy that hard-codes fairness constraints and potentially ignores relevance judgments. In-processing methods can instead learn to ignore the protected features as well as their proxies. Pre-processing methods do not allow a biased model, yet our experiments show that creating an unbiased training set is not trivial and may easily lead to reverse discrimination. In summary, we make the following contributions:

Listwise Fairness: We propose a new metric for fairness in rankings that operates on the concept of disparate exposure. We use this to define the first listwise learning-to-rank (LTR) approach, named DELTR, that is concerned with reducing disparate impact at training time.

New Datasets: We perform extensive experiments on two different ranking tasks: expert search in a document retrieval setting, and ranking students by predicted performance. Our experiments comprise three real-world datasets, of which two are newly introduced (Section 5).

Non-Discrimination vs. Equal Opportunity: Our experimental descriptions draw a clear distinction between scenarios in which we seek to reduce discrimination, and situations in which we want to enhance equal opportunity, which is yet missing in the algorithmic fairness literature.

Study on Colorblindness: As stated by Dwork et al. 2012, being “colorblind” on discriminatory training data, i.e. merely ignoring protected attributes, can be a bad idea, because non-protected attributes serve as proxies for the protected ones (Calders and Verwer 2010). In our experiments we analyze in which cases colorblindness yields the best results, and in which it is among the worst results both in terms of relevance and fairness. We also explain how these cases are related to contribution 3, and show that DELTR performs well in terms of fairness and relevance in all tested scenarios.

FA*IR as Pre-Processing Approach: We demonstrate a pre-processing approach for fairness in rankings by applying a post-processing method, FA*IR (Zehlike et al. 2017), to our training data before the learning routine starts. These experiments show two interesting insights:

Related Work

Fairness in ranking is concerned with a sufficient presence, a consistent treatment, and a proper representation of different groups across all ranking positions (Castillo 2018). At a high level, this line of research has the goal of producing rankings based on relevant characteristics of items, in which items belonging to the protected group are not under-represented or systematically relegated to lower ranking positions (Yang et al. 2018). Singh and Joachims 2017 introduce the concept of exposure of a group, based on empirical observations that show that the probability that a user examines an item ranked at a certain position, decreases rapidly with the position. We will use this concept to present a new evaluation metric that measures exposure as the average probability of a group to be ranked in the top position. Previous works on fair rankings (Yang and Stoyanovich 2017; Zehlike et al. 2017; Celis et al. 2017; Singh and Joachims 2017; Biega et al. 2018) have been concerned with creating a fairness-aware ranking from a given set of scores, and can be considered post-processing approaches—they are given a ranking and re-rank elements to achieve a desired objective. In contrast, our approach DELTR is learning-based as it extends ListNet (Cao et al. 2007), a well-known listwise LTR framework. It constitutes the first listwise in-processing approach to reduce discrimination and inequality of opportunity in rankings, because it learns a ranking function with an additional objective that reduces disparate exposure. While the recently proposed pairwise approach by Beutel et al. 2019 cares about disparate treatment, our listwise method directly optimizes the actual exposure a protected group would get, and is hence concerned with disparate impact. Also we do not take user feedback into account, as it constitutes an additional source of unconscious biases, that we want to study separately.

Background: ListNet in a nutshell

We consider a set of queries $Q$ with $|Q|=m$ and a set of documents $D$ with $|D|=n$. Each query $q$ is associated with a list of candidate documents $d^{(q)}\subseteq D$, where each document is represented as a feature vector $x^{(q)}_{i}$. For each query the list of feature vectors $x^{(q)}$ is associated with a list of judgments: $x^{(q)}\rightarrow y^{(q)}$. The standard objective then is to learn a ranking function $f$ that outputs a list $\hat{y}^{(q)}$ of new judgments $\hat{y}^{(q)}_{i}$ for each feature vector $x^{(q)}_{i}$. Ideally, the function $f$ should be such that the sum of the differences (or losses) $L$ between the training judgments $y^{(q)}$ and the predicted judgments $\hat{y}^{(q)}$ is minimized: $\min\left(\sum_{q\in Q}L\left(y^{(q)},\hat{y}^{(q)}\right)\right).$

As rankings are combinatorial objects, the naive approach to find an optimal solution for $L$ leads to exponential execution time in the number of documents. Hence, instead of considering an actual permutation of documents, Cao et al. 2007 only focus on the probability for a document $d_{i}^{(q)}$ to be ranked in the top position:

DELTR: Disparate Exposure in Learning To Rank

For our listwise fairness approach we assume that the retrieved items belong to two distinct social groups (such as men and women, or majority and minority ethnicity), and that one of these groups is protected (Pedreshi et al. 2008). At training time, we are given an annotated set consisting of queries and ordered lists of items for each query. At testing time, we provide a query and a document collection, and expect as output a list of top-$k$ items from the collection that should be relevant to the query, and additionally should not exhibit disparate exposure.

Disparate Exposure. We assume that items in $D$ belong to two different groups, which we denote by $G_{0}$ for the non-protected group, and $G_{1}$ for the protected group. Items in the protected group have a certain protected attribute, such as belonging to an underprivileged group. As argued in Section 1, the protected group may, due to various causes including historic discrimination or erratic data collection procedures, have a significant disadvantage in the training dataset. This is likely to cause a model to predict rankings with a large discrepancy in exposure, and not only to reproduce but reinforce discrimination and unequal opportunities for already disadvantaged groups.

To define a measure of “unfairness” we borrow the definition of Singh and Joachims 2018 on exposure of a document $d$ in a ranked list generated by a probabilistic ranking $P$, and adapt it for top-one-probabilities (eq. 1) to match ListNet’s accuracy metric:

where $v_{1}$ is the position bias of position 1, indicating its relative importance for users of a ranking system (Järvelin and Kekäläinen 2002). Hence, the average exposure of documents in group $G_{p}$ with $p\in\left\{0,1\right\}$ is

Finally, we adapt the first definition of equal exposure in (Singh and Joachims 2018), demographic parity, which ensures that the average exposure across items from all groups is equal. With this we can now introduce an unfairness criterion measured in terms of disparate exposure:

Note that in contrast to (Singh and Joachims 2018), using the squared hinge loss gives us a metric that prefers rankings in which the exposure of the protected group is not less than the exposure of the non-protected group, but not vice versa. This means that our definition will optimize only for relevance in cases where the protected group already receives as much exposure as the non-protected group.

We note that other fairness objectives can be used as long as they can be optimized efficiently (e.g., are differentiable), and that the definition in Equation 5 can be easily extended to multiple protected groups by considering average or maximum difference of exposure between a protected group and the non-protected one.

with larger $\gamma$ expressing preference for solutions that focus on reduction of disparate exposure for the protected group, and smaller $\gamma$ expressing preference for solutions that put emphasis on the differences between the training data and the output of the ranking algorithm. The parameter $\gamma$ depends on desired trade-offs between ranking utility and disparate exposure that are application-dependent. To set it, we looked at the ratio between $L$ and $U$ and used this as $\gamma_{\texttt{small}}$. For $\gamma_{\operatorname{large}}$ we increased $\gamma_{\operatorname{small}}$ by an order of magnitude. We remark that, even if $\gamma$ is set very high DELTR only increases fairness until exposure for both groups is equal. We confirmed this with synthetic experiments in two different settings: one where all non-protected items appeared at the top positions, and one where all protected items were followed by all non-protected ones. In the first setting, increasing values of $\gamma$ lead to more exposure of the protected group and items are put to higher positions. However DELTR does not over-compensate and moves protected items only as long as exposure is not equal across groups. In the second case DELTR behaves like a standard LTR algorithm.

Optimization. For the ranking function to infer the document judgments we use a linear function $f_{\omega}(x^{(q)}_{i})=\langle\omega\cdot x^{(q)}_{i}\rangle$ (Cao et al. 2007), and Gradient Descent to find an optimal solution for $L_{\mathit{DELTR}}$. We can now rewrite the top-one-probability for a document (eq. 1) and set $\phi$ to an exponential function, which is strictly positive, increasing and convenient to derive:

To use Gradient Descent we need the derivative of $L_{\mathit{DELTR}}(y^{(q)},\hat{y}^{(q)})$ which in turn consists of the derivatives of the disparate exposure and accuracy metric respectively.

Experiments

In our experiments, we consider three real-world datasets summarized in Table 1. We study non-discrimination, through experiments that seek to reduce biases unrelated to utility (Sec. 6.1), or biases that originate from different score distributions at the same relevance level across social groups (Sec. 6.2). Due to the nature of these biases we do not expect to see a trade-off between search utility and list-wise fairness, as both can be achieved at the same time. In the first case (Sec. 6.1), excluding the protected attribute for training will lead to the best result in terms of utility and list-wise fairness. In the second case (Sec. 6.2) we want to explicitly include the protected feature to achieve higher utility and less disparate exposure. DELTR can handle both cases without prior knowledge about the underlying bias. Additionally we study substantive equality of opportunity, through experiments that seek to reduce biases due to utility differences that pre-exist (Sec. 6.3). We apply DELTR to each dataset with two different values of $\gamma$: $\gamma_{\operatorname{large}}$ in which $\gamma$ is comparable to the value of the standard loss $L$, and $\gamma_{\operatorname{small}}$ in which it is an order of magnitude smaller. Then we compare the results against several baselines:

W3C experts (TREC Enterprise) Dataset. This dataset originates from the expert search task at the TREC 2005 Enterprise Track (Craswell et al. 2005), where an algorithm has to retrieve a sorted list of experts for a given topic, given a corpus of e-mails written by possible candidates. While all experts are considered equally expert, we injected a discriminatory pattern in this dataset by sorting the ground truth for each training query in the following order:

This simulates a scenario where expertise has been judged correctly, but training lists have been ordered with a bias against women, placing them systematically below men at the same level of expertise. We computed a series of text-retrieval features for each query-document pair, such as word count and tf-idf scores by usage of the Elasticsearch Learning to Rank Plug-in (OpenSource Connections 2017).

Engineering Students Dataset. The dataset contains anonymized historical information from first-year students at a large school in a Chilean university. As qualification features we are given the results of the Chilean university admission test named PSU in categories math, language, and science, their high-school grades, and the number of credits taken in their first year.

Law Students Dataset. This dataset originates from a study by Wightman 1998 that examined whether the LSAT (Law Students Admission Test in the US) is biased against ethnic minorities. It contains anonymized historical information from first-year students at different law schools. We use a uniform sample of 10% of this dataset, while maintaining the distribution of gender and ethnicity.

Baselines. We compare DELTR with a small and a large value for $\gamma$ to pre-, in- and post-processing approaches. Our in-processing baselines constitute

In the pre- and post-processing baselines we apply the algorithm FA*IR (Zehlike et al. 2017) to the training data and the predicted rankings of a standard LTR method, respectively. FA*IR is a top-$k$ ranking algorithm that ensures a minimum target proportion $p$ of a protected group at every prefix of a ranking based on a statistical significance test. In our pre-processing baseline experiments we process a given training dataset with FA*IR to free the data from potential bias and create fair training data.

We use three different values of $p$, $p^{*}=$ the ratio of protected candidates in the dataset, $p^{+}=p^{*}+0.1$ and $p^{-}=p^{*}-0.1$, to show how crucial the right choice of $p$ is, especially in a pre-processing setting. Afterwards we use ListNet (Cao et al. 2007) to train a ranker over all features, both sensitive and non-sensitive. The post-processing baseline also uses ListNet and trains a ranker over all available features, including the protected one. Then FA*IR is applied to the predicted rankings, potentially resulting in a reordering of the items. We use the same parameters $p^{*},p^{+}$ and $p^{-}$ as in the pre-processing experiments.

Experimental Results

In this section we present the results of each experimental setting, which are depicted in Figure 1 and summarized in Table 2.

Experimental results are shown on Figure 1a, averaged over all folds, using $\gamma_{\texttt{small}}=20K$, $\gamma_{\texttt{large}}=200K$, and $p^{*}=0.105$, which is the proportion of women in the dataset. In this experiment we expect the “colorblind” approach to achieve the best results, because we injected a strong bias against women that was completely unrelated to their expertise. The setting corresponds to a non-discrimination case, where we want to exclude the protected feature from training for relevance reasons and we expect to see no trade-off between accuracy and list-wise fairness when optimizing for both. Figure 1a confirms our expectations. Note that we measure utility in terms of precision at ten instead of Kendall’s tau, because we want to know which algorithm finds most of the true experts and ranks them accordingly. Colorblind LTR performs best in terms of relevance and achieves almost equal exposure for men and women, by distributing women evenly across rankings. Standard LTR (including the biased protected feature) performs worse in terms of relevance and exposure than most of the other approaches. Indeed, the model discriminates against women based solely on their gender, by placing all women at the bottom of the ranking (not shown), even those that were considered experts in the ground truth. The in-processing approach DELTR reduces the gap in exposure between men and women, and scores best in terms of relevance compared to all other fair algorithms. Post-processing (blue “$F$”) with $p^{+}$ achieves better exposure, but leads to a slight over-representation of women at the top-positions, which causes the lower relevance w.r.t. DELTR. When using pre-processing FA*IR (orange “$\overline{F}$”) with the intuitive $p^{*}$, the model is not de-biased, meaning that this value for $p$ is too low for this setting. However, pre-processing using $p^{+}$, which is only slightly larger than $p^{*}$, not only increases exposure to the profound detriment of the non-protected group, but also performs significantly worse than all other approaches in terms of relevance (Figure 1a, all dots lying above the gray line in the figures mean that the protected group now receives higher exposure than the non-protected one). These effects of a too small or too large $p$ for all cases of FA*IR, post- and pre-processing can be seen in all following results: a too small $p$ shows no effect on the exposure of the protected group in the rankings. However, a too large $p$ can result in an over-representation of protected elements at the top positions. This may result into inverting the bias, such that non-protected items are now ranked low solely because of their group membership. In contrast on the one hand DELTR always results in better exposure, even if $\gamma$ is set low. On the other hand it excludes the risk of reverse discrimination by design. This advantage comes from the fact that in-processing methods consider both objectives simultaneously. They constantly trade relevance against fairness measures until the best balance is found, while pre- or post-processing approaches examine relevance and fairness measures consecutively and hence the sweet spot must be found manually.

2. Bias due to Different Score Distributions – Engineering Students (high school type)

In this experiment, we consider students coming from public high schools as the protected group and those from private high schools as the non-protected. Results appear in Figure ($\gamma_{\texttt{small}}=100K$, $\gamma_{\texttt{large}}=5M$ and $p^{*}=0.348$, which is the proportion of students from public high schools). The ground truth shows that students from public schools perform worse on average in the admission test, but tend to have higher grades in university than students from private high schools with the same scores. One explanation for this phenomenon is that public schools tend to provide an education of inferior quality compared to private schools in Chile. For achieving the same test scores, students from public schools need to have better academic aptitudes (similar to observations in (Glynn 2019)). This scenario corresponds to achieving non-discrimination with different underlying score distributions, while the same ground truth utility exists across social groups. Under these circumstances, including the protected attribute will lead to better performance in terms of relevance and exposure. We therefore expect the colorblind LTR to be among the worst approaches, and standard LTR to be among the best. The results in Figure confirm our expectations. We see that the colorblind method performs significantly worse than most approaches both in terms of exposure and in terms of relevance. DELTR, given that students from the protected group already receive higher exposure, does not further increase their ranks, preserving the quality of the ranking result (due to the asymmetry of the method). The same is true for FA*IR in pre- and post-processing, in this case with small values of $p$. Recall however that a small $p$ did not do the trick in exp 6.1, because those bias’ properties were of a different kind. DELTR can handle both types of biases without knowing their nature a-priori. In the post-processing setting FA*IR with $p^{+}$ achieves equal exposure ratios as DELTR, but less relevance. In the pre-processing experiment, a too large $p$-value ($p^{*}$ and $p^{+}$), leads the LTR algorithm to place too much weight on the protected feature, resulting in a strong decline of relevance.

3. Achieving Substantive Equal Opportunity

As the remaining three experiments all relate to the same goal of achieving substantive equal opportunity (O’Neill 1977), we will describe our findings jointly in this section.

Engineering students (gender). Figure summarizes the results obtained with parameters $\gamma_{\texttt{small}}=3K$, $\gamma_{\texttt{large}}=50K$, and $p^{*}=0.202$, which is the proportion of women in this dataset.

Law students (gender). Figure 1d summarizes the results with $\gamma_{\texttt{small}}=3K$, $\gamma_{\texttt{large}}=50K$ and $p^{*}=0.437$, which is the proportion of women in this dataset.

Law students (race). Results appear in Figure 1e using parameters $\gamma_{\texttt{small}}=1M$, $\gamma_{\texttt{large}}=50M$ and $p^{*}=0.064$, which is the proportion of African-American students. We did not use $p^{-}$ because it would have been a negative number.

Interpretation. From the ground truth we know for all three experiments that the protected group scores worse than the non-protected one in their admission tests and also worse in terms of academic success after the first year. We therefore expect a trade-off between utility and exposure, if we optimize for more exposure than the protected group should receive based on their “true” performance. This is desirable if one wants to achieve substantive equal opportunity, corresponding to the usage of a disparate impact approach. If we assumed the training data was free of bias and/or mistakes and truly reflects a student’s achievements, the colorblind baseline corresponds to a group’s true performance. However we expect neither colorblind nor standard LTR to yield equality of exposure, because the protected group’s achievements fall behind the non-protected ones in the ground truth. Using the standard LTR baseline, i.e. including the protected feature into the training phase, leads to even better results in terms of accuracy in figures and 1d than colorblind LTR, but causes a significant drop in exposure for the protected group. Interestingly, in Figure 1e, we observe the reverse: including the protected feature leads to a drop both in accuracy and exposure w.r.t. colorblind. We suspect this happens because the distributions of true performances for each group are far apart in the ground truth, which causes the ranker to overshoot the target by putting far too much weight on the protected feature. Note that this constitutes a very different effect than what was described in Section 6.1, and is not further studied here. As before, being an in-processing approach DELTR consistently outperforms the pre- and post-processing baselines, both in terms of accuracy and in terms of list-wise fairness. This means that using DELTR, we lose less relevance for the same exposure achievement in a search result, than when using pre- or post-processing approaches like FA*IR. A too small $p$ again does not show any effects for the mitigation of disparate impact (pre- and post-processing FA*IR with $p^{-}$ in figures and 1d; and pre-processing FA*IR with $p^{*}$ in figure 1d). However a too large $p$ can quickly result not only in over-representation of the protected group, but also yields a significant decline in terms of result relevance, with no upper bound. We interpret this as “too many protected candidates that performed poorly being pushed to higher positions”, as FA*IR only takes relevance within groups into consideration. In-processing methods like DELTR can not produce over-representative models because they optimize for exposure and accuracy at the same time.

Conclusions

LTR models can reproduce and exaggerate discrepancies of the average group visibility from training data. In this paper we presented the in-processing approach DELTR. It extends ListNet with a list-wise fairness objective that reduces the extent to which protected elements receive less exposure. Our experiments showed that this additional objective does not necessarily come with a trade-off in accuracy. On the contrary, aiming for list-wise fairness will increase relevance in cases corresponding to non-discrimination. We showed that non-discrimination can be achieved by explicitly excluding or including the protected feature and studied the nature of underlying biases for each case. As it is hard to understand a-priori which bias is present, DELTR provides a convenient approach to handle both situations.

Future work. The parameter $\gamma$ provides great flexibility but more work is required to provide a systematic way of setting this parameter. We formalized the extension of our list-wise fairness notion to multiple protected groups, but still need to experimentally validate.

Reproducibility. All datasets and code for reproduction are available at https://github.com/MilkaLichtblau/DELTR-Experiments. DELTR is also available as a stand-alone library in Java and Python, as well as a plugin for Elasticsearch at https://github.com/fair-search.

Acknowledgments. Castillo thanks La Caixa project LCF/PR/PR16/11110009 for partial support. Zehlike thanks the MPI-SWS for their support. The authors thank Gina-Theresa Diehn and Pere Urbon for their assistance during this research.

References