Source-linked AI summary
Evaluating Stochastic Rankings with Expected Exposure
Fernando Diaz, Bhaskar Mitra, Michael D. Ekstrand, Asia J. Biega, Ben Carterette
TL;DR
Ranked systems can allocate unequal attention among similarly relevant items, while static rankings limit exposure sharing. The paper evaluates stochastic distributions over rankings using expected exposure and existing browsing models, finding that the framework captures and optimizes exposure properties beyond conventional evaluation. It also identifies user-satisfaction, logistical, and graded-relevance scope limitations.
Problem
Ranked lists can amplify small relevance differences into unequal exposure, affecting visibility, producer returns, fairness, and information experiences.
Method
The paper defines expected exposure and evaluates stochastic policies that sample rankings, using user models from RBP and ERR.
Results
Expected exposure metrics distinguish systems with different exposure levels and can be optimized; direct optimization improved EE-AUC by 3.9% over pointwise and pairwise models, with p< 0.01.
Takeaways & Limitations
Randomization can balance exposure across relevant items and heterogeneous intents, while expected exposure provides a unified way to study relevance and disparity.
Takeaways & Limitations
The impact of randomization on user satisfaction remains under study, and stochastic evaluation introduces representation, sampling, and storage constraints.
Abstract
from arXiv · showhide
We introduce the concept of \emph{expected exposure} as the average attention ranked items receive from users over repeated samples of the same query. Furthermore, we advocate for the adoption of the principle of equal expected exposure: given a fixed information need, no item should receive more or less expected exposure than any other item of the same relevance grade. We argue that this principle is desirable for many retrieval objectives and scenarios, including topical diversity and fair ranking. Leveraging user models from existing retrieval metrics, we propose a general evaluation methodology based on expected exposure and draw connections to related metrics in information retrieval evaluation. Importantly, this methodology relaxes classic information retrieval assumptions, allowing a system, in response to a query, to produce a \emph{distribution over rankings} instead of a single fixed ranking. We study the behavior of the expected exposure metric and stochastic rankers across a variety of information access conditions, including \emph{ad hoc} retrieval and recommendation. We believe that measuring and optimizing expected exposure metrics using randomization opens a new area for retrieval algorithm development and progress.
1 INTRODUCTION
Ranked lists necessarily allocate attention unevenly, even among similarly relevant items, and static rankings limit how exposure can be distributed. The paper proposes evaluating stochastic distributions over rankings using expected exposure.
- Motivation: Ranked interfaces expose items in order, converting relevance ties or small relevance differences into distinct attention opportunities.This affects visibility, consumption, and returns to content producers.
- Motivation: Nonuniform exposure can create fairness concerns, reduce service quality, homogenize information experiences, and produce rich-get-richer effects.These effects arise across retrieval and recommendation settings.
- Proposed approach: Static rankings limit an algorithm’s ability to distribute exposure among relevant items.The limitation applies to retrieval queries and recommendation contexts.
- Proposed approach: The paper evaluates systems by sampling rankings from a distribution, enabling equal exposure among relevant items in expectation and expected metric values.This generalizes evaluation beyond one fixed permutation per query.
- Scope: The paper defines expected exposure, connects it to diversity, novelty, and fairness metrics, and studies stochastic retrieval and recommendation algorithms.It also proposes optimizing systems toward exposure-based metrics.
- Paper organization: The paper develops its framework by reviewing prior work, defining expected exposure, analyzing metric connections, running experiments, and proposing optimization procedures.
2 RELATED WORK
The paper connects exposure-based evaluation to fairness, randomized ranking, diversity, click exploration, and optimization of expected retrieval metrics. It positions its contribution as applying these ideas within a unified information-retrieval evaluation framework.
- Connections: The work brings together algorithmic fairness metrics and randomized ranking algorithms from online learning and optimization.
- Fairness: Exposure fairness has been formulated for individuals through relevance-proportional exposure and for groups through equal exposure across sensitive attributes.
- Fairness and diversity: Prior randomized policies have targeted search diversification and group fairness, while this paper studies broader connections between fairness and diversity.
- Fair ranking: Other fair-ranking approaches equalize group proportions, position-discounted parity, or engagement across protected groups.
- Meritocratic fairness: Meritocratic fairness requires less-qualified candidates not to outrank more-qualified candidates, connecting target exposure to relevance ordering.
- Randomization: Randomized ranking has been used for click exploration, unbiased feedback, click-model estimation, and improving diversity.
- Expected metrics: Prior work optimized expected relevance metrics over sampled rankings, and this paper adopts related methodologies without treating that work as deployment of stochastic rankers.
3 EXPECTED EXPOSURE
Expected exposure measures whether items of equal relevance receive equal attention in expectation under a ranking policy. The framework uses stochastic rankings and user browsing models to separate relevance from exposure disparity and expose their tradeoff.
- Principle: Equal expected exposure requires items with the same relevance to receive neither more nor less exposure than one another for a fixed information need.
- Principle: Existing relevance metrics generally ignore exposure differences among equally relevant items and therefore cannot distinguish policies that satisfy the principle from those that do not.
- Stochastic policies: For a query with m relevant documents, optimal rankings place relevant items above nonrelevant items, yielding m!(n−m)! equally optimal permutations.
- Stochastic policies: A stochastic policy samples a distribution over rankings, while deterministic policies assign probability to only one permutation.
- Exposure computation: Expected exposure is represented as a vector computed from a ranking policy and a model of how users interact with ranked results.
- Metric decomposition: Expected exposure decomposes into relevance and disparity components, so maximizing relevance can concentrate exposure while minimizing disparity can sacrifice relevance.
- RBP model: RBP models exponentially decreasing position visits, with patience γ controlling browsing depth and maximum depth k.
- ERR model: ERR makes browsing depend on earlier relevant documents, whose relevance can cause users to stop scanning; its generalized form also includes a patience parameter.
4 RELATIONSHIP TO OTHER METRICS
Expected exposure connects ranking evaluation to relevance, diversity, and fairness metrics while emphasizing how attention is distributed among relevant items.
- Expected exposure provides a framework for relating ranking evaluation to existing retrieval metrics and highlighting its distinct measurement properties.
- Under an RBP browsing model, optimizing expected exposure separates relevant documents from nonrelevant ones while distributing exposure among relevant documents.
- Expected exposure can reduce the risk of overlooking relevant documents when users terminate ranking scans early.
- Fairness: Expected exposure relates to individual fairness because equal-relevance documents can receive approximately equal expected exposure under a stochastic ranker.
- Fairness: Group fairness measures compare exposure deviations across document or provider groups, with targets supporting equal or relevance-proportional exposure.
- Topical Diversity: Intent-aware topical diversity metrics can reduce to scaled relevance terms in disparate-impact or demographic-parity formulations, while separately capturing disparity requires an EE-D term.
5 METRIC ANALYSIS
The analysis studies expected-exposure metrics by randomizing deterministic retrieval and recommendation policies with two stochastic ranking strategies across two datasets.
- The experiments examine whether expected-exposure metrics distinguish randomization strategies and differ from static metrics based on the same user model.
- Randomization Strategies: Plackett-Luce sampling uses retrieval scores and a randomness parameter, whereas rank transpositions shuffle the original ranking through random pair swaps.
- Randomization Strategies: The PL policy is expected to outperform RT because it preserves score information while RT ignores scores and positions.
- The study uses Robust2004 retrieval runs and MovieLens25M recommendation runs with binary relevance or implicit feedback.
- Results: Expected RBP and EE-R were strongly correlated at r=0.99, p<0.01, while expected ERR and EE-R showed perfect correlation under an ERR model.
- Results: EE-D correlated with generalized entropy at r=0.47, p<0.01 for RBP and r=0.65, p<0.01 for ERR, indicating sensitivity to relevant-document exposure.
- Results: Across both domains and multiple runs, PL policies dominated RT policies across all disparity points.
- Results: Static-ranking RBP approximately ordered runs for a fixed randomization policy with τ=0.89, p<0.05, but did not distinguish PL from RT.
EE-R (ERR)
The supplied axis labels list the values 1, 2, 4, 8, and static.
- The section includes the condition labeled static alongside numeric settings.
EE-D (ERR)
Figure 2 plots expected-exposure behavior for a Robust2004 run randomized with Plackett-Luce sampling under RBP and ERR browsing models.
- The horizontal axis shows α, with lower values indicating more randomization.
- The top row reports static ranking relevance metrics, while the second row reports expected exposure relevance metrics.
- The third row reports expected exposure disparity metrics, and the fourth row reports generalized entropy on relevant documents.
- The left and right columns use RBP and ERR browsing models, respectively.
6 OPTIMIZING FOR EXPECTED EXPOSURE
The paper optimizes stochastic ranking policies directly for expected exposure, balancing relevance and disparity through differentiable Plackett–Luce sampling and exposure-based losses. Experiments compare these models with pointwise and pairwise objectives on graded relevance and demographic parity.
- 6 OPTIMIZING FOR EXPECTED EXPOSURE: The optimization objective trades off relevance against disparity, with a related objective extending the approach to demographic parity.The demographic-parity loss assumes equal exposure across demographic groups.
- 6.1 Algorithm: Plackett–Luce randomization converts item scores into sampling probabilities for sequentially generated rankings.The model uses Gumbel noise and smooth ranks to make sampled rankings compatible with gradient-based optimization.
- 6.1 Algorithm: Expected exposure is estimated by averaging document exposure across independently sampled rankings and then used in a gradient-descent loss.The training target is exposure derived from relevance grades; the temperature is set to 0.1.
- 6.2 Experimental Setup: The experiments use a shared neural architecture with pointwise, pairwise, and expected-exposure objectives on MSLR-WEB10k.MSLR-WEB10k contains ten thousand queries with 136-dimensional query-document features and five graded relevance levels.
- 6.3 Results: 3.9% improvement in EE-AUC over the pointwise and pairwise models resulted from directly optimizing expected exposure, with p < 0.01 significance.Pointwise and pairwise models did not differ in expected-exposure performance.
- 6.3 Results: Directly optimizing expected exposure improved performance, while directly optimizing demographic parity further boosted it; all model-pair EE-AUC gaps were significant at p < 0.01.This result concerns the demographic-parity experiments.
7 DISCUSSION
The discussion connects expected exposure to information retrieval, probabilistic search, fairness, diversity, and user retention. It also identifies limitations involving user satisfaction, evaluation logistics, cumulative randomization effects, and non-ranking interfaces.
- 7 DISCUSSION: Expected exposure metrics capture retrieval-system aspects not currently measured in information retrieval evaluation and can be optimized directly.The authors report that the metrics distinguish systems with varying expected exposure.
- 7 DISCUSSION: The framework connects exposure-based evaluation to classic ad hoc, legal, and diversity-sensitive retrieval tasks.The authors argue that these connections warrant revisiting algorithms and results in those tasks.
- 7 DISCUSSION: Expected exposure provides a way to evaluate probabilistic search systems and explicitly model ranking randomization in pre-launch batch evaluation.This extends evaluation beyond relevance, fairness, and diversity to distributions over rankings produced by probabilistic policies.
- 7 DISCUSSION: Randomization can balance exposure across heterogeneous intents and may help user retention by reducing starvation of producers in two-sided systems.The paper frames these outcomes as possibilities rather than established effects.
- 7 DISCUSSION: Non-ranking interfaces such as two-dimensional grids and three-dimensional environments require alternative user models.The exposure model can incorporate more elaborate browsing models, but the paper identifies new interface forms as a boundary.
- 7 DISCUSSION: The approach is limited by unresolved effects on user satisfaction and logistical costs of representing and sampling stochastic policies.Centralized evaluations may require policy interrogation or large sample pools, increasing storage costs.
- 7 DISCUSSION: Coupling expected-exposure evaluation with stochastic policies opens a new perspective for studying and designing information retrieval systems.The conclusion is stated notwithstanding the approach’s limitations.