PaperlayerView exact revision on arXiv

Source-linked AI summary

Pairwise Fairness for Ranking and Regression

Harikrishna Narasimhan, Andrew Cotter, Maya Gupta, Serena Wang

arXiv:1906.05330v3cs.LGstat.ML

TL;DR

Ranking and regression need fairness measures, but the appropriate definition can vary. The paper develops pairwise metrics for discrete groups and continuous protected attributes, and reports that constrained optimization is flexible and effective at reducing fairness violations, with trade-offs against AUC or MSE.

  • Problem

    Ranking and regression models increasingly affect daily life, yet fairness metrics for these models need to be defined and measured, with no single fairness definition presumed right.

    Source: Introduction · p. 1

  • Method

    The paper formulates ranking and regression fairness through pairwise comparisons, extending classification analogues to discrete groups and continuous protected attributes.

    Source: Introduction · p. 1, Ranking Pairwise Fairness Metrics · p. 1, Regression Pairwise Fairness Metrics · p. 2

  • Results

    Across experiments, methods often traded off AUC or MSE against fairness; constrained optimization was effective at low pairwise violations and was best in 3 of 4 strict comparisons against Beutel et al. [2019].

    Source: Conclusions · p. 7

  • Takeaways & Limitations

    Constrained optimization is the most flexible and direct strategy considered, while post-processing was more restricted and did not perform as well as directly training a model.

    Source: Conclusions · p. 7

    The regression metrics assume that higher scores are either desirable or undesirable.

    Source: Regression Pairwise Fairness Metrics · p. 2

Abstract

from arXiv · show

We present pairwise fairness metrics for ranking models and regression models that form analogues of statistical fairness notions such as equal opportunity, equal accuracy, and statistical parity. Our pairwise formulation supports both discrete protected groups, and continuous protected attributes. We show that the resulting training problems can be efficiently and effectively solved using existing constrained optimization and robust optimization techniques developed for fair classification. Experiments illustrate the broad applicability and trade-offs of these methods.

Introduction

The paper proposes pairwise fairness metrics for ranking and regression, analogous to classification fairness notions. It frames these metrics as a flexible way to define and train for different fairness goals.

Introduction

  • The paper argues that ranking and regression need fairness measures, while allowing different definitions rather than prescribing one “right” definition.Source: Introduction · p. 1
  • The paper distinguishes unsupervised statistical parity from supervised equal opportunity through which candidate pairs must be ranked equally often.For restaurant rankings, statistical parity compares French and Mexican restaurants regardless of price; equal opportunity compares cheap restaurants against expensive ones across groups.Source: Introduction · p. 1
  • Ranking becomes pairwise binary classification, enabling fairness metrics for ranking, regression, discrete groups, and continuous protected attributes.The proposed metrics can be trained using state-of-the-art constrained optimization algorithms.Source: Introduction · p. 1

Ranking Pairwise Fairness Metrics

The paper defines ranking fairness through pairwise accuracy: whether a model correctly orders candidates within the same query. It builds supervised parity and unsupervised statistical parity criteria from those comparisons.

Ranking Pairwise Fairness Metrics

  • Pairwise accuracy measures whether the model ranks a labeled-better candidate above a labeled-worse one, with group membership specifying the pair type.Pairs are drawn within queries; group-level averages form a K × K matrix, and overall pairwise accuracy is AUC.Source: Ranking Pairwise Fairness Metrics · pp. 1–2

Pairwise Equal Opportunity

  • Pairwise equal opportunity requires equal correct-ranking rates across protected-group pairings, with relaxed parity or maximin variants available.The paper notes that equal opportunity and equal odds coincide when all pairwise accuracies are constrained equivalently.Source: Pairwise Equal Opportunity · p. 2

Within-Group vs. Cross-Group Comparison

  • Separate cross-group equal opportunity from within-group equal accuracy when cross-group labels may be less reliable or comparisons are rare.This permits constraining within-group ranking accuracy without imposing a cross-group constraint.Source: Within-Group vs. Cross-Group Comparison · p. 2

Marginal Equal Opportunity

  • Marginal pairwise equal opportunity equalizes each group’s accuracy averaged over comparisons with other groups, loosening fine-grained constraints that may be infeasible or statistically weak.Source: Marginal Equal Opportunity · p. 2

Statistical Parity

  • Pairwise statistical parity requires cross-group pairs to have equal chances of ranking either group higher, without using training labels.The label-free criterion may suit settings where cross-group comparisons are too apples-to-oranges or raters lack expertise.Source: Statistical Parity · p. 2

Regression Pairwise Fairness Metrics

The paper extends pairwise fairness metrics to regression, where models assign scores rather than rank candidates within queries. It defines fairness through comparisons between examples and their predicted scores.

Regression Pairwise Fairness Metrics

  • Regression pairwise metrics compare examples without query structure, treating higher scores as desirable or undesirable under an asymmetric-score assumption.Metrics can be computed over all N^2 example pairs, or a random subset when that is too large.Source: Regression Pairwise Fairness Metrics · p. 2

Regression Equal Opportunity

Regression Equal Accuracy

  • Pairwise equal accuracy requires each group’s within-group example pairs to be ranked equally faithfully, useful when groups have different labeling distributions.The passage contrasts jazz ratings concentrated at 4–5 stars with classical ratings spanning 1–5, which can make classical errors dominate MSE.Source: Regression Equal Accuracy · p. 3

Regression Statistical Parity

  • Pairwise statistical parity requires outputs for examples from different groups to be equally likely to place either group higher.Matching the groups’ output distributions is one sufficient condition and can be approximated by histogram matching.Source: Regression Statistical Parity · p. 3

Regression Symmetric Equal Accuracy

Continuous Protected Features

For continuous or ordered protected attributes, the paper defines comparisons by the ordering of protected-feature values rather than group membership. It extends pairwise fairness constraints to this setting.

Continuous Protected Features

  • Continuous protected-attribute comparisons condition pair accuracy on whether protected-feature values move in the same or opposite direction as labels.For height, the same-direction accuracy measures whether the taller candidate receives the higher score when that candidate should rank higher.Source: Continuous Protected Features · p. 3
  • The paper adapts discrete-group pairwise constraints to ordered attributes; equal opportunity requires equal accuracy when the taller or shorter candidate should rank higher.Source: Continuous Protected Features · p. 3

Training for Pairwise Fairness

The paper casts pairwise fairness training as constrained or robust optimization, then uses rate-constraint and proxy-Lagrangian methods to solve the resulting problems.

Training for Pairwise Fairness

  • The paper formulates ranking fairness training as constrained optimization with slack and also offers a robust optimization alternative; regression replaces AUC with MSE.The ranking formulation is developed for cross-group equal opportunity, but the formulation and algorithms apply to any pairwise metric.Source: Proposed Formulations · p. 3, Training for Pairwise Fairness · p. 3
  • Pairwise accuracies can be written as positive prediction rates on subsets of example pairs, allowing binary-fairness algorithms to solve the optimization problems.The subsets contain pairs whose labels are ordered and whose examples belong to specified groups.Source: Optimization Algorithms · p. 3
  • The proxy-Lagrangian framework handles the considered objective and constraint functions through a min-max game over model parameters and constraint weights.It learns a stochastic model supported on a finite set of functions in F.Source: Optimization Algorithms · p. 3
  • Equation (11) equates true-positive and true-negative rates across both pair sets, specifying equalized odds and equal opportunity.The passage defines the corresponding rate for pairs with z < z′ as TPRz<z′.Source: Optimization Algorithms · p. 3
  • Under certain assumptions, no-regret and swap-regret optimization converge to a stochastic model satisfying the specified constraints in expectation.The method uses hinge-based surrogates for the model-parameter player’s indicators.Source: Optimization Algorithms · p. 4

Related Work

Prior work covers fair classification, ranking, regression, and continuous protected attributes, while this paper extends pairwise fairness and constrained training across those settings.

Related Work

  • Fair-classification work expresses metrics such as demographic parity and equal opportunity as rate constraints and trains classifiers with constrained optimization, which this paper extends to ranking and regression..Source: Fair Classification · p. 4
  • Earlier fair-ranking work mostly uses list-wise exposure criteria, while other pairwise approaches focus on categorical groups or optimize an existing model through post-processing.Pinned AUC and weighted pinned AUC can also be expressed as linear combinations of pairwise accuracies.Source: Fair Ranking · p. 4, Pairwise Fairness · p. 4, Pinned AUC · p. 4
  • Compared with Beutel et al. [2019], this work broadens pairwise fairness to more statistical notions, regression, continuous protected features, and experiments across ranking and regression settings.The experiments span categorical and continuous protected attributes and public and real-world data.Source: Pairwise Fairness · p. 4
  • Unlike fixed residual-correlation regularization, the approach enforces user-specified pairwise constraints and automatically tunes group penalties, exposing fairness–accuracy trade-offs.Beutel et al. [2019] consider two protected groups, whereas this method supports any number of groups.Source: Pairwise Fairness · p. 4
  • Prior regression approaches target protected-feature independence, similar squared errors, or bounded group loss; this paper instead emphasizes supervised pairwise notions based on ordering.The cited definitions differ in their fairness objectives and how they assess regression errors.Source: Fair Regression · p. 5
  • Bucketing continuous protected features can create significance challenges with fine bins and unfairness concerns with coarse bins; prior work also studies continuous-feature criteria directly.Examples include tree-growing criteria, statistical-parity constraints, correlation control, and a Rényi maximum-correlation criterion.Source: Fair Regression · p. 5

Experiments

Across ranking and regression experiments, constrained optimization generally reduced pairwise fairness violations, with trade-offs against AUC or MSE that varied by task. The experiments also compare robust optimization and several prior approaches across discrete and continuous protected attributes.

Experiments

  • The experiments cover five ranking and two regression problems, with random train/validation/test splits and validation data used to tune hyperparameters.For query-based datasets, metrics are evaluated per query and averaged; stochastic-model metrics are expectations over random score draws.Source: Experiments · p. 5

Pairwise Fairness for Ranking

  • Constrained optimization reduced Wiki Talk Pages fairness violation to 0.010 versus 0.014 for debiased weighting, but had slightly lower test AUC.The unconstrained model more often ranked a non-toxic comment containing “gay” above a toxic comment without the term.Source: Table 1 · p. 6, Figure 1 · p. 6, Wiki Talk Page Comments · p. 6
  • For three-group simulated ranking, constrained optimization reduced differences among group marginals more than robust optimization, at the cost of lower accuracy for all three groups.The methods respectively constrain marginal differences and maximize the minimum marginal accuracy.Source: Simulated Ranking Data · pp. 5–6
  • On Business Matching, constrained optimization achieved very low fairness violation with only marginally lower AUC; post-processing had similar fairness but lower AUC.Singh and Joachims [2018] did not produce feasible solutions, which the authors attribute to few pairs per query.Source: Business Matching · p. 6
  • On W3C Experts, constrained and robust optimization reduced fairness violations and improved test metrics; Beutel et al. [2019] achieved the lowest violation and highest AUC.The unconstrained model treated gender as a strong expertise signal, often ranking female candidates above male candidates.Source: W3C Experts Search · p. 7
  • For continuous-attribute ranking on Communities and Crime, constrained and robust optimization cut fairness violation by more than half, at the cost of lower test AUC.The protected attribute is percentage of Black population; the criterion compares pairwise accuracies across its values.Source: Communities and Crime (Continuous… · p. 7

Pairwise Fairness for Regression

  • In regression, Law School constraints sharply reduced fairness violation with a small MSE increase and beat Beutel et al. [2019], while Communities and Crime saw a large violation reduction but increased MSE.Law School uses gender as the protected attribute; Communities and Crime uses percentage of Black population as a continuous attribute.Source: Pairwise Fairness for Regression · p. 7

Conclusions

The paper develops pairwise fairness metrics for ranking and regression, including settings with discrete or continuous protected attributes. Experiments show that methods often trade off fairness and predictive performance, while constrained optimization is a flexible, direct strategy for reducing fairness violations.

Conclusions

  • Pairwise fairness metrics cover supervised and unsupervised notions in ranking and regression, with discrete or continuous protected attributes.The metrics can be incorporated into training using constrained optimization solvers.Source: Conclusions · p. 7
  • Methods often traded off AUC (or MSE) against fairness; constrained optimization was the most flexible and direct strategy and achieved low pairwise fairness violations, outperforming Beutel et al. [2019] in 3 of 4 cases where either method strictly performed better.Kallus and Zhou [2019], a post-processing method, was more restricted and did not perform as well as the proposed approach that directly trains a model from scratch.Source: Conclusions · p. 7
  • Pair selection specifies the fairness metric: the paper focuses on within-group and cross-group pairs, while side information or label differences could also guide pair selection or weighting.Presentation order is one example of ranking-side information that could be used to select or weight pairs.Source: Conclusions · p. 8

Appendix

Table 3 illustrates group-dependent pairwise accuracy for three groups and includes frequency-weighted row and column means for the restaurant-ranking example.

Appendix

  • Table 3 presents an example group-dependent pairwise-accuracy matrix for K = 3 groups.Source: Table 3 · p. 9
  • The example includes frequency-weighted row means.Source: Table 3 · p. 9
  • The example also includes frequency-weighted column means for the restaurant-ranking example.Source: Table 3 · p. 9

Proxy-Lagrangian Optimization

The proxy-Lagrangian approach optimizes ranking objectives subject to pairwise fairness constraints. Under strict-feasibility assumptions, its stochastic model is guaranteed to closely satisfy those constraints in expectation.

Proxy-Lagrangian Optimization

  • The proxy-Lagrangian formulation for two groups uses constraint differences Δij(f) = AGi>Gj(f) − AGj>Gi(f).Source: Proxy-Lagrangian Optimization · p. 9
  • Because pairwise metrics are non-continuous, optimization uses concave AUC and convex constraint surrogates that bound the original metrics.The experiments construct these surrogates by replacing indicator functions with hinge-based upper and lower bounds.Source: Proxy-Lagrangian Optimization · p. 9
  • The λ-player minimizes a weighted sum of the two constraint violations, while the θ-player uses surrogate objectives for optimization.Source: Proxy-Lagrangian Optimization · p. 9
  • No-regret updates for θ and swap-regret updates for λ produce a stochastic model supported on the T models visited during optimization.Source: Proxy-Lagrangian Optimization · p. 9
  • With model parameters that strictly satisfy the constraints with a margin, the returned stochastic model is guaranteed to closely satisfy pairwise fairness constraints in expectation for large T.Source: Proxy-Lagrangian Optimization · p. 9
  • The supplied visuals cover learned hyperplanes, test AUC and fairness violations, and a test pairwise-accuracy matrix for two-group simulated ranking.Source: Figure 2 · p. 10, Table 4 · p. 10, Figure 3 · p. 10

Connection to Weighted Pairwise Accuracy

The proposed constrained and robust optimization formulations can be understood as maximizing weighted pairwise accuracy, with the solver determining the weights that correspond to the specified fairness criteria.

Connection to Weighted Pairwise Accuracy

Additional Experimental Details/Results

Across experiments, constrained and robust optimization reduce pairwise fairness violations, with different ranking-objective trade-offs. Additional matrices show that strong group marginals can coexist with weaker overall accuracy, and one comparison method has feasibility and applicability limits.

Setup

  • Experiments use a 1/2:1/4:1/4 train-validation-test split; Wiki Talk Pages and Law School use minibatches of 100, while other datasets use full gradients.The proxy-Lagrangian solver runs 2,500 iterations; the debiased-weighting baseline balances positive and negative label proportions within groups.Source: Setup · p. 10, Hyperparameter Choices · p. 11

Experiment Constraining All Matrix Entries

  • Constrained and robust optimization both significantly reduce fairness violations; under all-entry constraints, robust optimization incurs only a marginal objective decrease while constrained optimization suffers a considerable decrease.The unconstrained algorithm has the highest ranking objective but very high fairness violations.Source: Experiment Constraining All Matrix… · p. 11

Additional Experimental Details/Results

  • In Figure 3, constrained optimization satisfies fairness constraints by lowering all four group-pair accuracies, while robust optimization maximizes the matrix’s minimum entry.The observed outcomes match the distinct optimization objectives.Source: Experiment Constraining All Matrix… · p. 11
  • The unconstrained ranking hyperplane ranks majority examples well but is less accurate on minority examples; constrained and robust hyperplanes work more equally well for both groups.Ranking quality depends on the hyperplane slope, not its intercept.Source: Experiment Constraining All Matrix… · p. 11

Additional Results for Simulated Ranking Task with 3 Groups

Additional Singh and Joachims [2018] Comparison

  • The Singh and Joachims post-processing approach was infeasible on Business matching, inapplicable to Wiki Talk Pages and Communities & Crime, and performed poorly on the proposed pairwise metrics.The reported reasons were few pairs per query, missing query-candidate structure, and its non-pairwise exposure-style constraint.Source: Additional Results for Simulated… · p. 11, Table 6 · p. 12

Pairwise Accuracy Matrices

  • On Business matching, robust optimization maximizes the minimum of the two marginals, yet overall accuracy suffers on examples outside the two groups.Debiasing negligibly reduces fairness violation but yields better row marginals than the unconstrained approach.Source: Pairwise Accuracy Matrices · p. 12
Loading 1906.05330v3…