Evaluating Stochastic Rankings with Expected Exposure

Introduction

Information access systems such as retrieval and recommendation systems often respond to an information need with a ranking of items. Even with more sophisticated information display modalities, the ranked list is a central feature of most interfaces. Since users often inspect a ranked list in a nonrandom–usually linear–order, some items are exposed to the user before others. Even if a system can perfectly model relevance and rank items accordingly, it still must put items in a particular order, breaking relevance ties in some way and reifying small differences in relative relevance into distinct rank positions.

Nonuniform exposure of relevant items resulting from ranking has multiple effects. It strongly affects the allocation of user attention (and therefore content exposure, visibility, and consumption-related revenue) to results and their producers, giving rise to fairness concerns for content producers (Burke, 2017; Biega et al., 2018; Singh and Joachims, 2018); if there are qualitative differences in comparably-relevant results, systematically favoring results preferred by one group of users affects other groups’ quality of service (Mehrotra et al., 2017) and may affect user retention (Hashimoto et al., 2018); similarly, in recall-oriented search or in scenarios where a searcher is interested in broad subtopical exposure, systematically promoting some relevant documents over others may risk overlooking important content; it can homogenize users’ information experiences and promote rich-get-richer effects (Chaney et al., 2018); and, although not often analysed in the design of algorithms, nonuniform exposure to relevant content may affect users’ perception of the makeup of relevant information and its production community.

There may also be difference of degree: if there is a small difference in the relative relevance of two documents, but a large difference in the attention users tend to pay to the positions in which they are ranked, the ranking may amplify small difference in content value into a large difference in the producers’ return for providing that value.

Unfortunately, providing a static ranking for a query (in retrieval) or context (in recommendation) limits the ability for an algorithm to distribute exposure amongst relevant items. We propose to evaluate information access systems using distributions over rankings in response to a query or context. Figure 1 depicts this approach. More precisely, for a fixed query, we assume that a ranker, $\pi$, samples a permutation $\sigma$ from a distribution over the set of all permutations $S_{n}$ of $n$ documents. This allows it to provide equal exposure to relevant items in expectation. And while current evaluation metrics and methods measure the relevance or utility of a single ranking per query, with a distribution of rankings, we can compute the expected value of the metric.

This paper provides the foundation for an exposure-based approach to evaluating rankings and advocates for exploring the family of stochastic ranking policies within that framework. To that end, we 1 define the concept of expected exposure and ways to operationalize it; 2 discuss its relationship to existing retrieval metrics, including diversity, novelty, and fairness metrics; 3 apply it to measure item exposure under stochastic versions of existing retrieval and recommendation algorithms . We argue that exposure provides a means of looking at several different concerns in the evaluation and impact of information access systems, and believe generalizing evaluation from deterministic rankers to stochastic rankers provides a broad area of study with implications for classic and contemporary problems in information access.

We begin by discussing the connection of previous work with our exposure-based evaluation and stochastic ranking (§2). We will then present the framework for evaluating with expected exposure and stochastic ranking together (§3). These definitions of expected exposure have deep connections to existing metrics, which we describe in §4. We then describe our experimental apparatus for analyzing these metrics in §5. We also propose a procedure to optimize towards these metrics in §6. We conclude with a discussion of our findings (§7).

Related Work

Our work is inspired by and draws together two areas of work: 1 metrics recently developed in the context of algorithmic fairness, and 2 randomized ranking algorithms developed in the context of online learning and optimization.

Exposure optimization has been proposed as a means of achieving fairness in ranking: fairness for individuals means that exposure should be proportional to relevance for every subject in a system (Biega et al., 2018), while fairness for groups means that exposure should be equally distributed between members of groups defined by sensitive attributes such as gender or race (Singh and Joachims, 2018). From an optimization point of view, Singh and Joachims (2019) and Yadav et al. (2019) consider a similar notion of exposure fairness over multiple rankings as our work. Our work situates exposure-based measures in the context of information retrieval evaluation, allowing us to 1 extend them with user models from existing retrieval metrics, 2 relate them with the objectives and formalisms of other retrieval metrics, and 3 introduce a new experimentation protocols based on stochastic ranking.

Gao and Shah (2020) recently proposed a randomized policy for diversifying search results very similar to our work, albeit in the context of group fairness. While studying connection between fairness and diversity empirically, we attempt to more formally elucidate the relationship and study broader connections beyond group fairness.

Beyond the definitions explicitly focusing on exposure, other fairness definitions in practice lead to enhanced equality of exposure, for instance, by requiring equal proportions of individuals from different groups in ranking prefixes (Celis et al., 2018; Zehlike et al., 2017). Similarly, Yang and Stoyanovich (2017) measure fairness by computing sum of position-discounted set-wise parity at different rank thresholds. Beutel et al. (2019) approach fair ranking by conducting pairwise analysis of user engagement with the protected groups in a ranking. Zehlike and Castillo (2020) propose a supervised learning to rank method to optimize for fair exposure but focus only on the top position in ranking. It is not obvious how their proposed approach can be extended beyond the first rank position. In constrast to this literature, we study metrics that have clear user behavior model amenable to extension.

The notion of meritocratic fairness, originally introduced as a fairness objective for online bandit learning (Joseph et al., 2016) and then applied to the problem of selecting a group of individuals from incomparable populations (Kearns et al., 2017), intuitively requires that less qualified candidates do not have a higher chance of getting selected than more qualified candidates. In our setting, this translates to ensuring that less-relevant documents are not likely to be ranked above more-relevant documents. Our construct of target exposure connects this work to meritocratic fairness, in that a system satisfying equity of expected exposure will satisfy the goals of meritocratic fairness by allocating more exposure to relevant documents than to non-relevant documents, it also imposes a stronger constraint by requiring documents with comparable relevance to receive comparable exposure, preventing runaway popularity feedback loops that meritocratic fairness allows.

2. Stochastic Ranking

Randomization (either explicit or implicit) is ubiquitous in many information access systems and has been shown to be useful for eliciting user feedback and lead to desirable system properties. Pandey et al. (2005) first proposed randomized ranking motivated by click exploration. Further strategies (Radlinski and Joachims, 2007, 2006; Hofmann, 2013; Wang et al., 2016) have been developed following this approach for collecting unbiased feedback for learning to rank. Instead of using randomization to collect unbiased training data, Joachims et al. (2017) use it to estimate the parameters of a click propensity model that allows ranking models to be trained on biased feedback. Using randomness in ranking may also be a means of improving diversity (Radlinski et al., 2008).

Recently, Bruch et al. (2020) demonstrate that learning to rank models can be optimized towards expected values of relevance metrics computed over multiple rankings sampled based on estimated relevance. While not developed in the context of deploying a stochastic ranker, we adopt some of the methodologies therein in our experiments.

Expected Exposure

Given a query, we are interested in measuring the expected exposure of an item to a searcher with respect to items of similar relevance. Specifically, we would like to define a metric that quantifies a system’s deviation from an ideal expected exposure of items of the same relevance. To this end, we adopt the following principle of equal expected exposure,This principle is related to equity of attention (Biega et al., 2018), which also ties exposure to relevance. However, equity of attention was originally amortized across information needs. While this paradigm accounts for changing relevance, the system might increase exposure of items for inappropriate information needs. Thus, in this paper we propose to measure exposure per information need. In this sense, the distinction between equal expected exposure and equity of attention is similar to the difference between macroaveraging and microaveraging of relevance metrics.

Given a fixed information need, no item should be exposed (in expectation) more or less than any other item of the same relevance.

This principle complements the existing core principle of ranked retrieval that more relevant documents should appear before less relevant documents. In this section, we will introduce an evaluation methodology based on the principle of equal expected exposure.

We note that existing relevance metrics do not measure the extent to which systems satisfy this principle, as they typically ignore differences in exposure amongst items of the same relevance. As a result, existing relevance metrics will not be able to distinguish a system that satisfies this principle from one that does not.

We will start by remaining agnostic about how items are exposed to searchers, only that there is some way in which searchers interact with a ranking of items that is related to the exposure. More formally, let a ranking be defined as a permutation of the $n$ documents in the corpus. The set of all permutations of size $n$ is referred to as the symmetric group or $S_{n}$ in abstract algebra. Given a query $q\in\mathcal{Q}$ with $m$ relevant documents, an optimal permutation would place some ordering of the $m$ relevant items at the top positions, followed by some ordering of the $(n-m)$ nonrelevant documents. Per existing models, exposure monotonically—often-exponentially—decreases with position in a ranking. Therefore, for a static ranking, we can see that 1 some relevant documents receive more exposure than other relevant documents, and 2 some nonrelevant documents receive more exposure than other nonrelevant documents. A static ranking will therefore always violate equal expected exposure. Unfortunately, classic retrieval systems only provide and are evaluated according to static rankings.

However, we know that there are $m!(n-m)!$ optimal rankings. If an oracle provided us with an optimal ranking at random, any relevant item would be ranked in position $0\leq i<m$ with the same probability.Note that we use base-0 ranks throughout this manuscript. As a result, all relevant items would receive the same exposure in expectation; similarly all nonrelevant items would receive the same exposure in expectation. Such a oracle would satisfy equal expected exposure. We will refer to the expected exposure of all items under the oracle policy as the target exposure, represented as a $n\times 1$ vector $\epsilon^{*}$.

Just as we can satisfy ideal expected exposure by using a stochastic oracle, a retrieval system can improve the distribution of exposure by using a stochastic policy, a protocol where, in response to a query, a distribution over rankings is provided. Formally, given a query $q$, a ranking policy $\pi$ provides a distribution over all permutations, $\sum_{\sigma\in S_{n}}\pi(\sigma|q)=1$. Classic ranking algorithms are a special case which only assign probability to a single, static permutation. We will refer to such an algorithm as a deterministic policy. We note that most classic evaluation metrics (e.g. mean average precision) only evaluate a single, static permutation from a deterministic policy.

Given a policy $\pi$ and a model of how the searcher might interact with a ranking, we can compute the expected exposure of all of the items in the corpus. We will represent the expected exposure of all items under $\pi$ as a $n\times 1$ vector $\epsilon$.

In order to measure the deviation from equal expected exposure, we compare the target exposure $\epsilon^{*}$ and sytem exposure $\epsilon$. One simple way to do this is to compute the squared error between $\epsilon^{*}$ and $\epsilon$,

where EE-D or expected exposure disparity measures inequity in the distribution of exposure; EE-R or expected exposure relevance measures how much of the exposure is on relevant documents; the remaining term is constant for a fixed information need.

This derivation allows us to clearly decompose expected exposure into a relevance and disparity components. A system that achieves optimal EE-R may maximize disparity (e.g. a static ranking with all relevant items at the top). Similarity a system that minimizes EE-D will have very bad expected exposure relevance (e.g. a random shuffling of the corpus every time a query is submitted).

We empirically observed (in §5.3) a tradeoff between the disparity (EE-D) and relevance (EE-R). This tradeoff is often controllable by a parameter in a stochastic policy that affects the degree of randomization. So, at one extreme, the parameter results in a deterministic policy that can achieve high relevance but also incurs high disparity. At the other extreme, the parameter results in a policy that randomly samples from amongst all permutations, achieving the lowest disparity but the lowest relevance. Given that such a parameter can often be swept between a minimum and maximum disparity, we can plot a disparity-relevance curve reflecting the nature of this tradeoff. We use the area under this curve, EE-AUC, as a summary statistic of this curve.

While we expect EE-R to behave similar to traditional relevance-based metrics–especially those sharing similar assumptions about how searchers interact with a ranking, reasoning about relevance and disparity within a single formalism allows us to compose aggregate metrics like EE-AUC, which traditional metrics do not capture (§5.3).

So far, we have remained agnostic about how items are exposed to users. In this section, we will describe how we can compute the exposure vector $\epsilon$ for an arbitrary ranker, including the oracle ranker. Unlike previous fair ranking metrics, we approach exposure by adopting user models from existing information retrieval metrics. We focus on models from two metrics, rank-biased precision and expected reciprocal rank, although this analysis can be extended to more elaborate browsing models (Diaz et al., 2013).

Rank-biased precision (RBP) is a metric that assumes that a user’s probability of visiting a position decreases exponentially with rank (Moffat and Zobel, 2008),

where $\mathbf{y}^{*}$ is the $n\times 1$ binary relevance vector; $\gamma$ is referred to as the patience parameter and controls how deep in the ranking the user is likely browse; and $k$ is the maximum browsing depth. The multiplicative factor $1-\gamma$ ensures that the measure lies in the unit range.

We consider that the expected exposure of a document $d$ is computed, in expectation, as,

where $\overline{\sigma}$ is a map from document indexes to ranks. This allows us to compute $\epsilon$ for an arbitrary policy $\pi$.

Recall that the oracle policy selects randomly amongst all rankings with all of the relevant documents at the top. Since each document occurs at each of the top $m$ positions equally, the target expected exposure for a relevant document is,

Since the set of nonrelevant documents is usually very large, all nonrelevant documents will have equal expected exposure close to zero.

Expected reciprocal rank (ERR) is a metric that assumes that a user’s probability of visiting a position is dependent on how many relevant documents appear a earlier positions (Chapelle et al., 2009). The intuition is that earlier relevant documents may satisfy the user and prompt them to stop scanning the ranking. We adopt generalized expected reciprocal rank, a model which incorporates a patience parameter similar to that used in RBP (Chapelle et al., 2009, §7.2).

where $\phi$ converts relevance to a probability of stopping the browsing. Normally this is zero for nonrelevant documents and some value between 0 and 1 for relevant documents. As with RBP, the expected exposure of document $d$ can be computed as,

Similarly, the target expected exposure of a relevant document is,

and close to zero for nonrelevant documents.

2. Extension to Graded Judgments

So far, we have focused on binary relevance. For graded judgments, the ideal ranker always orders documents correctly by grade. We take all permutations satisfying this requirement and assume the ideal ranker has nonzero support only for these values. We then compute the expected exposure for documents by grade. Let $m_{g}$ be the number of documents with relevance grade $g$ and $m_{>g}$ the number of documents with relevant grade strictly larger than $g$. Without loss of generality, assume that grades take integer values. Given an RBP browsing model, the optimal exposure for a document $d$ with grade $g$ is,

The derivation for the ERR user model is similar.

We note that this extension assumes that the a searcher will always prefer to see items with higher grade. In situations where, for example, the grade of an item is inversely correlated with some important property of a document (e.g. a subtopic, authors from underrepresented groups), then these groups will be under-exposed. In such cases, an alternative definition of $\epsilon^{*}$ may be more appropriate (see §4.2).

Relationship to Other Metrics

Expected exposure, both in motivation and in definition, has connections to existing retrieval metrics. In this section, we will discuss those relationships, highlighting the unique properties that expected exposure measures.

Measures such as RBP and ERR could be considered precision metrics, as they reward rankers for retrieving relevant material higher in the ranking. While based on the same user model, it is not the case that optimizing RBP will also minimize Equation 1, even if exposure is based on an RBP browsing model. To see why, consider a deterministic policy that outputs a static optimal ranking. Although EE-R will be optimal, EE-D will be very large since exposure is concentrated at the top ranks. Indeed, the value of EE-D for a static optimal ranking will be as bad as a static ranking that places all of the relevant document at the bottom since disparity is based only on the exposure and not on relevance. The converse, that minimizing Equation 1 also optimizes RBP, is true. If expected exposure is based on the RBP user model, a system that optimizes expected exposure will essentially be shuffling relevant documents at the top of the ranking and nonrelevant items in the bottom, just as with the oracle in §3.

Optimizing recall means focusing on ensuring that all of the relevant items in the corpus occur at high ranks. Several of our motivating examples might be considered addressable by a retrieval system optimized for high recall (e.g. e-discovery, academic search, systematic review). However, if we assume, as many user models do, that a user may terminate their scan of a ranking early, then there is a chance that even a high-recall system, especially in situation where there are numerous relevant documents, a user will not be exposed to all relevant items. As a result, we would argue that expected exposure reduces the risk of overlooking a relevant document.

2. Fairness

Algorithmic fairness, in the context of information retrieval and recommendation, deals with the treatment of individuals associated with retrievable items (Burke, 2017). These might be document authors in text retrieval, job candidates in recruiting, or musicians in song recommendation.

Individual Fairness. Expected exposure is closely related to various notions of individual fairness that quantify the extent to which models are fair to all individuals. Dwork et al. defined individual fairness in the context of classification models seen as mappings from individuals to probability distributions over outcomes (Dwork et al., 2012). In this setting, individual fairness is defined using the Lipschitz condition: the distributions of classification outcomes $P_{C}$ of two individuals $u_{1},u_{2}$ who are sufficiently similar according to a chosen similarity metric $d$ should be close according to a distribution similarity metric $D$. Formally, if $d(u_{1},u_{2})<\delta$, then $D(P_{C}(u_{1}),P_{C}(u2))<\Delta$. When will a retrieval policy be individually fair according to this definition? Assume we define $\delta$ and $d$ such that two documents of equal relevance grade satisfy the above inequality, and two documents of different relevance grades do not. Assume furthermore that outcomes are measured as the expected exposure of individual documents. A stochastic ranker that distributes exposure (almost) equally among the documents of equal relevance grades (in particular if it achieves optimal expected exposure according to Eq. 1) is individually fair according to the above definition. However, the reverse does not hold: It is possible that an individually fair and an unfair stochastic rankers lead to similar values of the expected exposure measure (the total loss value in Eq. 1 can be aggregated equitably from documents of the same relevance level or from only few documents within a relevance grade).

3. Topical Diversity

Exposure metrics are closely related to topical diversity metrics (Santos et al., 2015). One common way to measure topical diversity is to consider so-called ‘intent-aware’ metrics defined as,

where $\mu(\sigma|a)$ computes a standard metric considering only those documents with aspect $a$ as relevant. The intent-aware RBP metric is defined as

Metric analysis

We are interested in empirically studying the EE-D and EE-R. Specifically, we will answering the following questions in our experiments: 1 can the metric distinguish between different randomization strategies? 2 does an exposure-based relevance metric measure something different from a static ranking metric based on the same user model?

The focus of this paper is on evaluation. However, we were interested in studying our metrics for stochastic rankers, which are not readily available outside of specialized online learning environments. As such, we developed several stochastic rankers for our experiments based on post-processing a precomputed set of retrieval scores.

where $\alpha\geq 0$. When $\alpha=0$, all permutations are equally likely and EE-D is minimized; as $\alpha$ increases $\pi$ concentrates around original static ranking and disparity degrades. We refer to this as the Plackett-Luce (PL) policy.

Rank Transpositions (RT)

Our second randomization strategy ignores the retrieval scores and samples permutations by shuffling the original ranked list. We shuffle by repeatedly sampling pairs of positions and swapping the documents. Such a process takes $\frac{1}{2}n\log n+cn$ iterations to converge to sampling a random permutation (Diaconis and Shahshahani, 1981). This is precisely a random walk on $S_{n}$ where permutations are connected by pairwise transpositions. As such, we can introduce a ‘restart probability’ to teleport the random walker back to the original ranked list. If this probability is $\theta$, then the number of steps of the random walk follows a geometric distribution with support $[0,\infty)$. Our randomization strategy then first samples the number of steps $k$ from the geometric distribution and then conducts $k$ random transpositions. We refer to this as the rank transposition (RT) policy.

These two methods are intentionally constructed to perform differently. The PL policy takes a deterministic policy’s scores into consideration and will, therefore, be more conservative in removing high-scoring items from the top of the ranked list. The RT policy, on the other hand, randomly swaps pairs, regardless of score or position. As a result, we suspect that the PL policy should outperform the RT policy, given a fixed base deterministic policy.

2. Method

We analyze the behavior of expected exposure metrics using the postprocessing of deterministic policies in two domains. The first is based on archival TREC submissions focus in information retrieval conditions. The Robust2004 dataset consists of 440 runs submitted to the TREC 2004 Robust track which evaluated systems on a set of 249 queries and binary relevance labels. We adopt this dataset because it has been well-studied in the context of evaluation metrics.

Our second dataset, MovieLens25M, is a movie recommendation dataset consisting of 25 million ratings of 59 thousand movies by 163 thousand users (Harper and Konstan, 2015). We used LensKit 0.8.4 (Ekstrand, 2020) to generate runs representing binary implicit-feedback matrix factorization (IMF) (Pilászy et al., 2010) and Bayesian personalized ranking (BPR) (Rendle et al., 2009).BPR is implemented by the implicit package (https://github.com/benfred/implicit). We adopt implicit feedback instead of ratings in order to study the behavior of expected exposure under binary relevance.

We use a $\gamma=0.50$ for all of our experiments, as consistent with standard TREC evaluation protocol. RBP and ERR are evaluated at depth 20. For stochastic rankers, we sample 50 rankings during evaluation to estimate expected exposure metrics. We found that this was sufficient to converge to appropriate expected metric values. Experiments randomizing deterministic policies rerank the top 100 documents from the original static ranking.

3. Results

Before analyzing our metrics in aggregate, we present our metrics on an example run from Robust2004. In Figure 2, we show the behavior of our randomization model for EE-R and EE-D, under both the ERR and RBP user models. We compare these metrics to RBP and ERR, two classic static ranking metrics. We also measure the generalized entropy of exposure on the relevant set of documents (Speicher et al., 2018); this allows us to assess the disparity amongst relevant items.

Comparing classic metrics and EE-R in the first and second rows, we observe correlated behavior as randomization changes. Across a sample of runs, we found that the expected RBP and EE-R were strongly correlated ($r=0.99$, $p<0.01$); a perfect correlation was observed between expected ERR and EE-R with an ERR model. This is unsurprising given that the relevance factor in the expected exposure metric is precisely the expectation of the static ranking metric. The imperfect correlation for RBP is due to normalization term in the classic RBP model.

Comparing generalized entropy and EE-D, we also observe correlated behavior across both RBP ($r=0.47$, $p<0.01$) and ERR user models ($r=0.65$, $p<0.01$). Because the generalized entropy is computed over only relevant documents, this suggests that EE-D is sensitive to changes in expected exposure to relevant documents, not the dominant, nonrelevant set.

Comparing the behavior of EE-D and EE-R in Figure 2, we notice the disparity-relevance tradeoff mentioned in §3. In order to visualize this tradeoff more clearly, we present example disparity-relevance curves for randomization of an arbitrary Robust2004 run and our two recommender systems on MovieLens25M in Figure 3. Disparity-relevance curves, when randomizing the same base policy, will have the same value of EE-R for $\text{EE-D}=1$ because this recovers the original static ranking. Similarly, all disparity-relevance curves begin with $\text{EE-R}=0$ at $\text{EE-D}=0$ because a completely random ranker will achieve minimal relevance by dint of the number of nonrelevant documents in the corpus (i.e. a random shuffle will mean that, in expectation, every document receives a tiny amount of attention). Turning to the randomization policies being studied, across both domains and multiple runs, PL randomization policies dominate RT policies across all disparity points, confirming our intuition that incorporating score information improves post-processing performance. This provides us with the ability to test the ability of exposure to distinguish between stochastic policies.

Given two stochastic rankers, we are interested in understanding whether our exposure metrics can more accurately identify the superior algorithm compared to a metric based on a static ranking. To that end, we randomly assigned the runs for the Robust2004 dataset to either PL or RT randomization. This provided us with EE-AUC for each run as well as an RBP value for its base deterministic policy. We ordered runs by the RBP and then inspected the EE-AUC for the associated run. In Figure 4, we can see that, while RBP, a metric based on a static ranking, can approximately order runs for a fixed randomization policy ($\tau=0.89$, $p<0.05$), it cannot distinguish between the PL and RT policies.

Optimizing for Expected Exposure

In the previous section, we introduced post-processing techniques to build stochastic rankers. Given a model that is perfectly able to predict relevance, Plackett-Luce randomization should perform optimally, especially for binary relevance. As such, a classic pointwise learning to rank model (Cossock and Zhang, 2006) with Plackett-Luce randomization may be an effective approach for expected exposure. Moreover, calibration of relevance does not happen with pairwise learning to rank models (Burges et al., 2005) and so we would expect these models, even if perfect, to perform worse than pointwise models, even with Plackett-Luce randomization. However, learning to rank models are not perfect estimators of relevance. Therefore, we believe there should be some advantage to optimizing directly for expected exposure.

In this section, we will examine the relationship between the performance of these approaches in the context of graded relevance as well as demographic parity (§4.2). We focused on a shared model architecture with varying loss functions in order to measure differences due to the objective alone, instead of artifacts resulting from the functional form of the models. We begin by describing how we optimize for expected exposure before proceeding to our empirical results.

Although optimizing for pointwise or pairwise loss has been well-studied in the information retrieval community, directly optimizing for a metric based on a distribution over rankings has received less attention.

We begin by defining an appropriate loss function for our model. Turning to Equation 1, we can drop the constant term and add a hyperparameter to balance between disparity and relevance,

where $\epsilon^{*}$ is based on graded relevance (§3.2).

Let $f_{\theta}:\mathcal{D}\rightarrow\Re$ be an item scoring function parameterized by $\theta$. Given a query, $\mathbf{y}$ is a $n\times 1$ vector of item scores for the entire collection such that, $\mathbf{y}_{d}=f_{\theta}(d)$. Using a Plackett-Luce model, we can translate the raw scores into sampling probabilities,

The smooth rank is sensitive to the temperature $\tau$. At high temperatures the smooth rank is a poor approximation of the true rank and at low temperatures may result in vanishing gradients. To rectify this issue, we employ the straight-through estimator (Bengio et al., 2013) to compute the true ranks in forward pass but differentiating the gradients with respect to the smooth ranks during backpropagation.

Using the estimated ranks and a specified user model we compute the exposure for each document. For example, assuming RBP as the user model the exposure of document $d$ from a single ranking $\sigma$ is given by $\epsilon_{d}=\gamma^{\overline{\sigma}_{d}}$. We compute expected exposure by averaging over $n_{\text{train}}$ different rankings—each generated by independently sampling different Gumbel noise in Equation 7.

We use this expected exposure vector $\epsilon$ in Equation 6 to compute the loss that we minimize through gradient descent. The relevance grades are not used for training beyond computing target exposure. We set $\tau$ in Equation 8 to $0.1$.

We can adapt this model to optimize group-level exposure metrics like demographic parity (§4.2). To do so, we replace $\|\epsilon\|^{2}_{2}$ with $\|\xi\|^{2}_{2}$ in Equation 6 to define an optimization objective that trades-off relevance and demographic parity.

This loss function assumes that the ideal policy distributes exposure equally across all demographics.

2. Experiment

We restrict our choice of baselines to neural networks so that the exposure-based optimization can be compared to baseline ranking loss functions with respect to the same model. Our base model consists of a fully-connected neural network with two hidden layers of size 256 nodes per layer and rectified linear unit for activation function. We choose a learning rate of $0.001$ and a dropout rate of $0.1$ and perform early-stopping for all models based on validation sets. Stochastic rankings are then derived by employing Plackett-Luce sampling over these deterministic policies (i.e. pointwise and pairwise models), with varying softmax temperatures to obtain different trade-off points between disparity and relevance. We set $n_{\text{train}}$ to 20 for our model and $n_{\text{test}}$ to 50 for all models.

Objectives

We consider three models in our experiments. The pointwise model minimizes the squared error between the model prediction and true relevance. The pairwise model minimizes misclassified preferences using a cross-entropy loss. The expected exposure model minimizes the loss in Equation 6 and, in our demographic parity experiments, Equation 9.

Data

Our experiments use the MSLR-WEB10k dataset (Qin and Liu, 2013), a learning-to-rank dataset containing ten thousand queries. We perform five-fold cross validation ($60/20/20$ split between training, validation, and testing sets). Each query-document pair is represented by a 136-dimensional feature vector and graded according to relevance on a five point scale. For the demographic parity experiments, we discretize the PageRank feature in the ranges ¡1000, 1000–10000, and $\geq$10000 and treat it as a demographic attribute. We confirm that this discretization scheme is reasonable as roughly $70\%$ of the queries have at least one document corresponding to each demography with a relevance grade greater than one.

3. Results

We present the results of our experiments in Table 1.

In terms of expected exposure, we did not observe a difference in performance between pointwise and pairwise models. However, directly optimizing for expected exposure resulted in a $3.9\%$ improvement in EE-AUC over the pointwise and pairwise models. We confirm that the difference in EE-AUC follows a normal distribution and accordingly perform a paired student’s t-test to check their statistical significance. The EE-AUC differences between our proposed method and the baselines are statistically significant $(p<0.01)$.

In terms of demographic parity, we observe a difference in performance between pointwise and pairwise models. Moreover, directly optimizing for expected exposure results in improved performance while directly optimizing for demographic parity further boosts performance. The gap in EE-AUC between all pairs of models are statistically significant $(p<0.01)$ in this case.

Discussion

Our theoretical results draw clear connections to several areas of information retrieval research. We believe, moreover, that our empirical results suggest that expected exposure metrics capture important aspects of a retrieval system that are not currently measured in information retrieval evaluation. Our experiments furthermore demonstrated that these metrics are not only effective for distinguishing systems with varying degrees of expected exposure but also that they can be optimized toward.

Although previously studied in the context of algorithmic fairness, we have demonstrated that there are deep connections to existing core areas of information retrieval research. These results warrant revisiting algorithms and results in classic tasks such as ad hoc retrieval, legal search, and diversity-sensitive retrieval.

Beyond relevance, fairness, and diversity, we believe this approach to evaluation opens avenues for studying probabilistic search systems in probabilistic way. Many search systems are defined as probabilistic models, capable of handling uncertainty about document relevance (Zhu et al., 2009), sometimes using online learning to refine scoring and ranking models and adapt to changing information needs. These models produce rankings in accordance with a probabilistic policy, so they naturally result in a distribution over rankings associated with each query. Expected exposure, along with computing expected values of other information retrieval metrics, provides a way to evaluate these models and study the effects of uncertainty. Moreover, modern search engines also randomize their rankings to reduce bias in feedback data (Hofmann, 2013). Although these systems are often evaluated log data and off-policy evaluation techniques, in the case of pre-launch batch evaluation, we can explicitly model the impact of randomization by evaluating the distribution over rankings.

Randomization and improving equal expected exposure may also help with user retention. In search systems, we often want to make sure that we do not overemphasize dominant intents, which can often homogenize populations (Mehrotra et al., 2017; Hashimoto et al., 2018). As such, randomization can allow us to balance exposure across heterogeneous intents. Exposure balancing may also prevent churn caused by starvation of producers in two-sided economy systems such as ride-sharing platforms (Sühr et al., 2019).

Our exposure model is flexible enough to incorporate more elaborate browsing models. Several exist others beyond RBP and ERR exist in the literature for rankings which deserve exploration. Furthermore, as searchers begin to interact with interfaces that are not based on rankings (e.g. two-dimensional grids, three-dimensional environments), alternative user models will need to be developed and incorporated.

We would also like to note possible limitations of this approach. First, the impact of randomization on user satisfaction is still an active area of research and we believe cumulative effects of randomization may be a novel extension to explore in the future work (Schnabel et al., 2018). Second, from an evaluation perspective, stochastic policies introduce logistical constraints on distribution representation and permutation sampling. Centralized evaluations like TREC would need to support a method for either interrogating a stochastic policy or requiring a large pool of samples, incurring data storage costs. Third, although we have focused on randomization in order to increase exposure, we believe that drawing a connection to sequential decision-making scenarios like amortized evaluation are exciting areas of future work.

Notwithstanding these limitations, evaluation through expected exposure, when coupled with stochastic policies, opens a new perspective for the study, understanding, and design of information retrieval systems.

Acknowledgements

Michael Ekstrand’s contribution to this work was supported by the National Science Foundation under Grant No. IIS 17-51278.

References