Source-linked AI summary
Policy Learning for Fairness in Ranking
Ashudeep Singh, Thorsten Joachims
TL;DR
Conventional LTR optimizes user utility while overlooking how rankings allocate exposure and economic opportunity among items. The paper formulates fair LTR as stochastic policy learning with merit-based exposure constraints and introduces Fair-PG-Rank. Empirical evaluations report bias identification and effective optimization of individual and group fairness.
Problem
Conventional LTR methods maximize utility for users while typically ignoring rankings’ effects on item exposure and economic success.
Method
The paper uses stochastic ranking policies and empirical risk minimization to optimize utility under merit-based fairness-of-exposure constraints, implemented by Fair-PG-Rank.
Results
Across simulated and real-world evaluations, Fair-PG-Rank identifies biased features, outperforms heuristic approaches, and effectively learns under individual and group fairness constraints.
Takeaways & Limitations
Fair-PG-Rank directly optimizes ranking utility and fairness without relying on upper bounds or heuristic surrogate measures.
Takeaways & Limitations
Merit-proportional exposure constraints can be infeasible for many queries, such as when one item has relevance 1 and others have very small relevance ε.
Abstract
from arXiv · showhide
Conventional Learning-to-Rank (LTR) methods optimize the utility of the rankings to the users, but they are oblivious to their impact on the ranked items. However, there has been a growing understanding that the latter is important to consider for a wide range of ranking applications (e.g. online marketplaces, job placement, admissions). To address this need, we propose a general LTR framework that can optimize a wide range of utility metrics (e.g. NDCG) while satisfying fairness of exposure constraints with respect to the items. This framework expands the class of learnable ranking functions to stochastic ranking policies, which provides a language for rigorously expressing fairness specifications. Furthermore, we provide a new LTR algorithm called Fair-PG-Rank for directly searching the space of fair ranking policies via a policy-gradient approach. Beyond the theoretical evidence in deriving the framework and the algorithm, we provide empirical results on simulated and real-world datasets verifying the effectiveness of the approach in individual and group-fairness settings.
1. Introduction
Ranking systems strongly affect items’ exposure and economic success, yet conventional LTR optimizes user utility without accounting for item-side effects. The paper introduces Fair-PG-Rank and a policy-learning framework for utility optimization under individual and group fairness constraints.
- Ranking positions influence items’ exposure and economic success across multi-sided online systems.
- Fairness for rankings has been comparatively under-explored despite the societal and economic influence of online information systems.
- Fair-PG-Rank maximizes user utility while rigorously enforcing merit-based exposure constraints toward ranked items.
- Fair-PG-Rank identifies representation biases that post-processing methods cannot detect by design.
- Fair-PG-Rank performs better than heuristic approaches and supports individual and group fairness through policy-gradient learning.
2. Learning Fair Ranking Policies
The framework formulates fair LTR as stochastic policy learning that optimizes ranking utility while constraining expected disparity. It defines merit-based individual and group exposure criteria, while relaxing infeasible proportionality constraints through inequalities.
- The framework seeks exposure proportional to item merit while explicitly specifying allocation rules and preserving ranking utility.
- Fair LTR is formulated with empirical risk minimization, incorporating exposure-allocation constraints and concrete individual and group fairness measures.
- Stochastic ranking policies distribute expected exposure continuously, enabling finer control and gradient-based optimization; deterministic rankings are a special case.
- The utility objective can use metrics such as DCG, NDCG, Average Rank, or ERR, with NDCG used as the concrete focus.
- Fair LTR constrains policies to expected disparity at most δ and estimates query-distribution expectations empirically from training samples.
- The method steers the utility-fairness trade-off with a Lagrange multiplier λ rather than minimizing over λ for a fixed δ.
- Position bias measures attention by rank position, while document exposure is expected attention under the ranking policy and merit is a relevance-based function.
- Exact proportional exposure constraints can be infeasible; relaxed inequalities prevent higher-merit items from receiving exposure beyond their merit while allowing excess exposure elsewhere.
3. Fair-PG-Rank: A Policy Learning Algorithm for Fair LTR
Fair-PG-Rank learns stochastic ranking policies that optimize user utility while enforcing individual- and group-fairness exposure constraints. It uses differentiable Plackett-Luce policies and policy-gradient optimization with Monte Carlo estimates for both utility and disparity.
- Fair-PG-Rank: A Policy Learning Algorithm for Fair LTR: Fair-PG-Rank searches stochastic ranking policies that jointly optimize utility and fairness-of-exposure constraints.The framework supports both individual- and group-fairness disparity measures.
- Plackett-Luce Ranking Policies: Each policy combines a differentiable scoring model with a sampling method that defines a distribution over rankings.The scoring model may be linear or neural, while rankings are sampled according to the resulting policy.
- Plackett-Luce Ranking Policies: The Plackett-Luce policy assigns ranking probabilities through recursive softmax choices over the remaining documents.Both ranking probabilities and their derivatives can be computed efficiently when the scoring model is differentiable.
- Policy-Gradient Training Algorithm: Policy-gradient training uses stochastic gradient descent and Monte Carlo samples because exact gradients over exponentially many rankings are intractable.The same expectation-based approach estimates gradients for user utility and fairness disparity.
- Policy-Gradient Training Algorithm: Unlike heuristic or upper-bound LTR objectives, policy gradients directly optimize a specified utility metric and disparity measure, including non-smooth ranking objectives.PG-Rank supports metrics such as NDCG, DCG, ERR, Average-Rank, IPS-weighted metrics, and listwise metrics.
- Policy-Gradient Training Algorithm: Variance reduction subtracts a query-specific average reward, while entropy regularization encourages exploration and avoids suboptimal deterministic policies.The entropy term is weighted by the regularization coefficient γ.
4. Empirical Evaluation
Experiments on simulated and real-world datasets evaluate Fair-PG-Rank for utility optimization and individual or group fairness. The results show competitive utility learning and controllable fairness–utility trade-offs, including mitigation of biased features.
- Experimental setup: Fair-PG-Rank is evaluated on simulated data, Yahoo, and German Credit using NDCG as the utility metric.The experiments use merit M(rel) = rel and position bias proportional to 1/log2(1+j).
- Accurate ranking policies: PG-Rank achieves competitive performance against conventional LTR methods on Yahoo, outperforming RankSVM for linear models in NDCG@10 and ERR.The comparison uses the highest-probability ranking from the learned stochastic policy.
- Simulated data: The post-processing baseline becomes less fair as λ increases, whereas Fair-PG-Rank reduces disparity; the alternative heuristic has little effect on disparity.The post-processing method is misled by relevances estimated with the biased feature x2.
- Individual fairness: On Yahoo, varying λ lowers individual disparity while reducing NDCG@10 for both linear and neural-network models.Figure 2 distinguishes training curves from test-set performance.
- Group fairness: On German Credit, Fair-PG-Rank reliably trades off test NDCG and group disparity across runs, while the baselines fail to achieve the same trade-off.The figure reports standard deviation over five runs.
5. Conclusion
The paper concludes that stochastic policy learning provides a framework for ranking systems that jointly optimize user utility and merit-based exposure fairness. Fair-PG-Rank directly optimizes these objectives and works under both individual and group fairness constraints.
- Conclusion: The framework learns ranking policies that maximize user utility while obeying application-specific fairness constraints on exposure allocated according to merit.Fairness is imposed on how exposure is allocated to ranked items.
- Conclusion: Fair-PG-Rank directly optimizes utility and fairness with policy gradients rather than upper bounds or heuristic surrogate measures.The method estimates expectation gradients from sampled rankings using the log-derivative trick.
- Conclusion: The algorithm supports individual and group disparity gradients estimated from finite samples of rankings drawn from the learned policy.Both utility and disparity are expectations over rankings sampled from πθ.
- Conclusion: Algorithm 1 samples queries and Plackett–Luce rankings, averages utility and disparity gradients, and updates model parameters until validation convergence.The update uses the utility gradient minus λ times the disparity gradient.
B.1 Yahoo! Learning to Rank dataset
The Yahoo! Learning to Rank Set 1 dataset contains large training and test query collections with variable-sized candidate document sets and 700-dimensional query-document features.
- Dataset scale: Set 1 contains 19,944 training queries and 6,983 test queries.The corresponding document totals are 473,134 for training and 165,660 for testing.
- Representation and labels: Each query has a variable-sized candidate document set represented by 700-dimensional feature vectors.The dataset provides integer relevance judgments from 0, meaning bad, to 4, meaning perfect.
B.2 German Credit Dataset
The German Credit dataset is adapted from binary credit classification into ranking queries containing sampled relevant and irrelevant individuals, with gender defining the groups.
- Source dataset: The original dataset contains 1,000 individuals described by 20 numerical and categorical attributes.Each individual has a creditworthiness label.
- Ranking adaptation: Each ranking query samples 10 individuals with irrelevant and relevant documents in a 4:1 ratio.Relevant documents are creditworthy individuals, while irrelevant documents are non-creditworthy individuals.
- Group attribute: Gender defines membership in groups G0 and G1 for the group-fairness experiments.The group attribute is assigned to each individual in the adapted ranking task.
B.3 Baselines
The experiments compare Fair-PG-Rank with a post-processing linear-program baseline using estimated relevances and a Softmax-based cross-entropy baseline with a disparity penalty.
- Post-processing method: The post-processing baseline trains linear regression to estimate relevances, then solves a linear program imposing a disparate-exposure constraint for each test query.The resulting probabilistic ranking matrix represents document-position probabilities and is evaluated with NDCG and Dgroup.
- Post-processing method: The linear program maximizes utility minus a λ-weighted fairness term using estimated relevance utilities and logarithmic position-bias values.Its objective is P∗= argmaxP uT Pv −λξ, with ui = 2 ˆ reli −1 and vj = 1 log 1+j.
- Post-processing method: Because the baseline relies on estimated relevances, minimizing disparity in the linear program cannot guarantee zero disparity on unseen queries.The experiments instead vary λ from 0 to 0.2; at λ = 0.2, estimated-relevance disparity reaches zero for all queries.
- Zehlike and Castillo (2018): The Zehlike–Castillo baseline uses Softmax top-1 document probabilities, cross-entropy utility loss, and squared group-exposure disparity optimized by stochastic gradient descent.Training minimizes the sum of cross entropy and λ times the disparity measure.
B.4 Model and Training: Yahoo! Learning to Rank challenge dataset
For the Yahoo! Learning to Rank challenge dataset, the experiments train both linear and neural scoring models with policy-gradient settings that differ in initialization and learning rate.
- Model architectures: The experiments train two model types: a linear model and a neural network with one hidden layer of size 32 and ReLU activation.The models are used for experiments in Section § 4.1.
- Initialization: The linear-model weights are initialized uniformly between (−0.001, 0.001), while neural-network weights use the range (−1, 1).The passage specifies separate initialization ranges for the two architectures.
- Training procedure: Both models use entropy regularization γ = 1.0, a baseline, and S = 10 samples for gradient estimation.Training proceeds for 20 epochs, updating the model one query at a time.
B.5 Model and Training: German Credit Dataset
For the modified German Credit Dataset, the experiments evaluate Fair-PG-Rank with a linear scoring model across fairness-penalty values and compare it with the stated baselines.
- Model and optimization: The German Credit experiment trains a linear scoring model with Adam at a fixed learning rate of 0.001 and no regularization.The model is trained using a sample size of S = 25 for gradient estimation.
- Fairness setting: The experiment varies λ from 0 to 25 to evaluate different fairness-utility trade-offs.The passage specifies the λ range used for the German Credit evaluation.
- Comparison: Fair-PG-Rank is compared against the baselines described in Section § B.3.The comparison uses the same baseline set introduced for the experiments.