PaperlayerView exact revision on arXiv

Source-linked AI summary

Stability and Multigroup Fairness in Ranking with Uncertain Predictions

Siddartha Devic, Aleksandra Korolova, David Kempe, Vatsal Sharan

arXiv:2402.09326v1cs.LG

TL;DR

Rankings in systems such as job selection are often derived from predictions generated by machine-learning models for classification tasks. The paper studies ranking functions that map uncertain predictions to distributions over rankings, focusing on uncertainty-aware rankings and their fairness composition. UA rankings are stable, compose with individually fair predictors, and preserve multigroup fairness guarantees of multiaccurate or multicalibrated predictors.

  • Problem

    Rankings in systems such as job selection are often derived from predictions generated by machine-learning models for classification tasks.

    Source: §1 · p. 1

  • Method

    The paper studies ranking functions that map uncertain predictions to distributions over rankings, focusing on uncertainty-aware rankings and their fairness composition.

    Source: §1.1 · p. 2, §3.3 · p. 9, §4 · p. 12

  • Results

    UA rankings are stable, compose with individually fair predictors, and preserve multigroup fairness guarantees of multiaccurate or multicalibrated predictors.

    Source: §1 · p. 2, §7 · p. 22

  • Takeaways & Limitations

    UA rankings connect individual and subgroup fairness guarantees while limiting sensitivity to prediction noise.

    Source: §4 · p. 12, §7 · p. 22

    The guarantees are studied for individuals sampled i.i.d.; extending them to correlated labels is left for future work.

    Source: §4 · p. 12, §7 · p. 22

Abstract

from arXiv · show

Rankings are ubiquitous across many applications, from search engines to hiring committees. In practice, many rankings are derived from the output of predictors. However, when predictors trained for classification tasks have intrinsic uncertainty, it is not obvious how this uncertainty should be represented in the derived rankings. Our work considers ranking functions: maps from individual predictions for a classification task to distributions over rankings. We focus on two aspects of ranking functions: stability to perturbations in predictions and fairness towards both individuals and subgroups. Not only is stability an important requirement for its own sake, but -- as we show -- it composes harmoniously with individual fairness in the sense of Dwork et al. (2012). While deterministic ranking functions cannot be stable aside from trivial scenarios, we show that the recently proposed uncertainty aware (UA) ranking functions of Singh et al. (2021) are stable. Our main result is that UA rankings also achieve multigroup fairness through successful composition with multiaccurate or multicalibrated predictors. Our work demonstrates that UA rankings naturally interpolate between group and individual level fairness guarantees, while simultaneously satisfying stability guarantees important whenever machine-learned predictions are used.

1 Introduction

Rankings often turn uncertain machine-learning predictions into consequential decisions, but it is unclear how those predictions should determine rankings. The paper studies stability and fairness in ranking functions, including how uncertainty-aware rankings relate to individual and subgroup guarantees.

1 Introduction

  • When predictions are uncertain, converting class-probability distributions into meaningful rankings is unclear, even though decisions must precede observation of individuals’ true suitability.Rankings commonly derive from machine-learning predictors used in settings such as hiring, advertising, and content ranking.Source: §1 · pp. 1–2

1.1 Our Contributions

  • Stable ranking functions compose with individually fair predictors to yield a natural generalization of individual fairness for rankings.Stability makes ranking outcomes less sensitive to small prediction changes, a concern when learned predictions contain noise.Source: §1.1 · pp. 2–3, §1 · p. 2
  • Deterministic ranking functions cannot be both stable and nontrivial, whereas multiclass uncertainty-aware rankings are anonymous and stable.The paper argues that achieving stability and anonymity therefore requires randomization.Source: §1.1 · p. 3
  • UA rankings preserve multiaccuracy and multicalibration guarantees of the predictor, extending subgroup fairness to ranking distributions.As the predictor is calibrated for more refined subgroups, its UA ranking more closely reflects the ranking induced by unknown ground-truth classes.Source: §1.1 · p. 3

1.2 Related Work

  • Prior work studies fair or uncertain rankings, while this paper combines uncertainty, fairness, and stability; its group-fairness guarantees use predictor calibration and permit overlapping groups.Compared with Dwork et al. (2019), the paper’s guarantees are compatible with stability and apply at each ranking position.Source: §1.2 · p. 4

2 Notation and Preliminaries

The preliminaries define probabilistic multiclass predictions and ranking functions, then specify anonymity and stability as properties of those functions.

2 Notation and Preliminaries

  • Total variation distance measures the maximum probability difference over events, and the paper also uses entry-wise matrix norms.Labels are ordinal, with higher classes preferred.Source: §2 · p. 5

2.1 Predictors

  • A predictor maps each individual to a distribution over ordinal labels, and predictions for n individuals form an n × L matrix.Each row represents one individual’s label distribution.Source: §2.1 · pp. 5–6, §2 · p. 5

2.2 Rankings and Ranking Functions

  • A ranking function maps predictions to randomized rankings, while the framework considers principals who interact with individuals through predictions rather than their raw features.A randomized ranking is represented by the marginal probability of each individual receiving each position.Source: §2.2 · p. 6

2.3 Desiderata of Ranking Functions

  • Anonymity requires outcomes to depend on predictions rather than individuals’ identities or dataset indices.Permuting the predictions must permute the ranking outcomes in the same way.Source: §2.3 · p. 6
  • Stability bounds changes in ranking probabilities by changes in predictions, addressing noise in machine-learning outputs.The formal condition uses the infinity norm for ranking matrices and the entry-wise 1-norm for prediction matrices.Source: §2.3 · p. 7

3 Predictions and Rankings

This section examines stability in ranking functions, its composition with individual fairness, and limitations on deterministic and uncertainty-aware rankings. It establishes that UA rankings are anonymous and stable while presenting a tight-up-to-factor-2 limitation and ruling out stability for sufficiently small γ.

3.1 Consequences of Stability

  • For individuals i and j, the ranking distributions differ by at most (2βγ) · d(xi, xj) when an anonymous γ-stable rule ranks predictions from a (β, d)-individually fair predictor.Stability and individual fairness are both Lipschitz conditions, so their composition yields an individually fair ranking.Source: §3.1 · p. 7, §3 · p. 7
  • γ · nϵ bounds the difference between rankings from an ϵ-accurate predictor and ground truth under any γ-stable ranking function.Thus, accurate individual-level uncertainty estimates induce accurate individual-level rankings.Source: §3.1 · pp. 7–8

3.2 Stability and Determinism are Incompatible

  • No deterministic ranking function is anonymous, and any deterministic stable ranking function is constant.The instability argument extends to any path-connected subset of possible predictions: a deterministic stable rule must be constant on that subset.Source: §3 · p. 7, §3.2 · p. 8

3.3 Uncertainty Aware Rankings

  • The discrete-label UA rule samples labels independently and breaks ties uniformly, enabling exact computation in O(n4 + n3L).The adaptation addresses predictors that output distributions over discrete label sets.Source: §3.3 · pp. 9–10
  • UA rankings are anonymous and 1-stable.This establishes a nonconstant stable randomized ranking rule.Source: §3.3 · p. 11
  • UA ranking expressivity is strictly increasing in the number of labels L.Adding labels expands the distributions the rule can represent.Source: §3.3 · pp. 11–12
  • The stability analysis is tight up to a factor of 2, ruling out, for example, 1/n-stability for UA rankings.This conclusion follows using Proposition 13.Source: §3.3 · p. 12
  • For any L ≥3 and n ≥2, rUA is not γ-stable for any γ<1/2.A change only to one individual's prediction shifts their probability of being ranked last from 1/2 to 0.Source: §3.3 · p. 12

4 Multigroup Fairness Guarantees

Uncertainty-aware (UA) rankings compose with multiaccurate and multicalibrated predictors to provide subgroup fairness guarantees relative to rankings based on ground truth. The guarantees extend across subgroup definitions, interpolating between group- and individual-level fairness as subgroup granularity changes.

4 Multigroup Fairness Guarantees

  • UA rankings derived from multiaccurate or multicalibrated predictors have outcomes close to ground-truth UA rankings for the corresponding groups.The result is stated for i.i.d. samples from a distribution over individuals.Source: §4 · p. 12, §4.1 · p. 13

4.1 Group-wise Accuracy Guarantees

  • Multiaccuracy guarantees subgroup-level ranking accuracy, while multicalibration refines the guarantee to prediction intervals within each subgroup.The multicalibration result also assumes multiaccuracy over the full domain.Source: §4.1 · pp. 13, 16

4.2 Multicalibration as Interpolating between Group and Individual Fairness

  • Changing the granularity of subgroup collection C lets the induced ranking interpolate between group- and individual-level fairness.Singleton groups approach individual-level accuracy as α approaches zero, with α = 0 recovering the ground-truth predictor.Source: §4.1 · p. 13, §4.2 · p. 16
  • Near-individual guarantees are usually unreasonable to expect because they require substantial samples and an agnostically PAC-learnable class of groups.The authors envision using sufficiently simple classes, such as categorical-feature conjunctions and numeric-feature intervals.Source: §4.2 · p. 16

5 Ranking Functions and Utility

The utility-maximizing ranking can be unstable and fail to preserve subgroup fairness, even when the predictor is nearly multiaccurate. A randomized mixture of that ranking with UA rankings offers a trade-off with approximate stability and fairness while retaining a utility guarantee.

5 Ranking Functions and Utility

  • The utility-maximizing ranking is unstable even for binary labels and an expected-utility map.It deterministically orders individuals by decreasing class utility τ(p_i).Source: §5 · p. 17
  • For fixed n, subgroup unfairness stays bounded away from zero as α approaches zero, despite a (C, α/2)-multiaccurate predictor.The result uses two equally likely types with identical uniform ground-truth label distributions and singleton groups.Source: §5 · p. 17
  • An arbitrarily small but nonzero prediction error can cause large changes in the utility-optimal ranking distribution, preventing preservation of predictor group fairness.The authors state this intuition for the two-type example.Source: §5 · p. 17

5.1 Utility-Stability Tradeoffs

  • Mixing UA and utility-optimal rankings provides approximate stability and a utility guarantee, with the mixing parameter controlling the trade-off.The mixture also has an approximate fairness guarantee derived from the multiaccuracy or multicalibration bounds.Source: §5.1 · pp. 18–19
  • The mixture is (ϕ, 1 − ϕ)-approximately stable.Approximate stability allows additive slack in how ranking changes depend on prediction changes.Source: §5.1 · p. 19

6 Experiments on Stability and Utility

Experiments test UA ranking stability under prediction noise and compare its utility with random and Plackett–Luce rankings. UA remains stable under multiclass predictions and outperforms both baselines in every reported utility instance.

6 Experiments on Stability and Utility

  • The section reports that UA rankings retain provable fairness and stability properties while offering better utility than random and Plackett-Luce baselines.The authors describe the experiments as relatively simplistic and not the main focus of the work.Source: §6 · p. 20

6.1 Stability Against SGD Noise in Neural Network Training

  • The experiments test ranking stability by comparing predictors trained with different random SGD seeds, then evaluating rankings on repeatedly sampled test subsets.The study uses paired networks trained from the same initialization and samples 30 individuals per trial.Source: §6.1 · pp. 20–21
  • The experiments use ACS employment predictions and Enrollment predictions for enrolled, graduated, or dropout status.ACS is restricted to California 2018 one-year person records and has 378,817 entries; Enrollment has 4,424 entries after cleaning.Source: §6.1 · p. 20
  • Across SGD training runs, UA ranking deviations are dominated by prediction shifts, while the optimal-utility ranking is often unstable.The reported UA behavior drastically surpasses the 1-stability bound; optimal-ranking instability was prevalent on real data.Source: Table 1 · p. 21, §6.1 · p. 21

6.2 Utility

  • UA ranking outperforms uniform and Plackett-Luce rankings in every reported utility instance.The comparison covers n = 20, 40, and 60 individuals from ACS and Enrollment, with means and standard deviations over 30 neural-network training runs.Source: Table 2 · p. 22, §6.2 · p. 22

7 Conclusions and Future Work

The conclusions highlight UA rankings’ stability and preservation of multigroup fairness guarantees from underlying predictors. They identify broader inheritance conditions and correlated sampled labels as directions for future work.

7 Conclusions and Future Work

  • UA rankings are stable and preserve multigroup fairness guarantees of their underlying classifiers.The paper frames stability as preventing large ranking deviations from noise in learned classifiers and notes its composition with individually fair predictions.Source: §7 · p. 22
  • The fairness-inheritance proof relies on individual interpolation; broader sufficient conditions and whether that property is necessary remain open questions.Individual interpolation treats one individual as competing against n − 1 others sampled from a single conditional distribution.Source: §7 · p. 22
  • Whether analogous individual and group fairness guarantees hold when sampled labels are correlated remains an open extension.The paper points to predictors trained on highly correlated data as a practical setting for investigation.Source: §7 · p. 22

A Proof of Key Lemma for Uncertainty Aware Ranking

The proof bounds the total variation distance between sums of independent categorical variables by the sum of their individual total variation distances. It obtains the bound through maximal couplings and a union bound.

A Proof of Key Lemma for Uncertainty Aware Ranking

  • For independent categorical variables, the total variation distance between their sums is at most the sum of the individual total variation distances.This is the stated lemma used in the proof of the key result.Source: A Proof of Key Lemma for Uncertainty… · p. 28
  • Maximal couplings bound each variable’s mismatch probability by its total variation distance, and a union bound controls any mismatch in the sums.The proof uses the coupling inequality to relate the distance between sum distributions to the probability that the coupled sums differ.Source: A Proof of Key Lemma for Uncertainty… · p. 28
  • For Lemma 12, the proof applies the sum-distance bound to vectors encoding whether other individuals’ labels exceed or equal a threshold.It then bounds the resulting distributional distance by summing the individual prediction distances.Source: A Proof of Key Lemma for Uncertainty… · pp. 28–29

Related papers

Loading 2402.09326v1…