Source-linked AI summary
Obtaining fairness using optimal transport theory
Eustasio del Barrio, Fabrice Gamboa, Paula Gordaliza, Jean-Michel Loubes
TL;DR
Biased data can make binary classification unfair across protected groups, motivating fairness measures based on prediction outcomes. The paper relates Disparate Impact and Balanced Error Rate, then repairs input data with optimal transport, including Wasserstein barycenters and Random Repair. The analysis develops multidimensional repair and real-data procedures, where one procedure achieves Statistical Parity and smaller classification error than alternatives.
Problem
The paper asks how to detect and mitigate unfair discrimination in binary classification when a protected attribute may be encoded in the data and true labels may be unavailable.
Method
It modifies input data to weaken the protected attribute's relationship with observations, using Wasserstein-barycenter repair, multidimensional transport, and Random Repair.
Results
Procedure (B) achieves Statistical Parity for both classification rules and yields smaller repaired-data classification error than procedures (A) and (C).
Takeaways & Limitations
Optimal-transport data repair provides a fairness-oriented alternative when changing the classifier is impractical or the learning labels are unavailable.
Takeaways & Limitations
The practical total-repair procedure does not make the repaired group datasets identical, so it does not reach the stated fairness condition.
Abstract
from arXiv · showhide
Statistical algorithms are usually helping in making decisions in many aspects of our lives. But, how do we know if these algorithms are biased and commit unfair discrimination of a particular group of people, typically a minority? \textit{Fairness} is generally studied in a probabilistic framework where it is assumed that there exists a protected variable, whose use as an input of the algorithm may imply discrimination. There are different definitions of Fairness in the literature. In this paper we focus on two of them which are called Disparate Impact (DI) and Balanced Error Rate (BER). Both are based on the outcome of the algorithm across the different groups determined by the protected variable. The relationship between these two notions is also studied. The goals of this paper are to detect when a binary classification rule lacks fairness and to try to fight against the potential discrimination attributable to it. This can be done by modifying either the classifiers or the data itself. Our work falls into the second category and modifies the input data using optimal transport theory.
1 Introduction
Machine-learning decisions increasingly affect sensitive areas, creating risks that biased training data can propagate or legitimize unfair treatment. This paper studies fairness assessment and data-based repair using optimal transport.
- Machine-learning decision algorithms now influence sensitive domains including medicine, hiring, lending, policing, and criminal sentencing.
- Biased learning samples can teach algorithms discriminatory patterns that are propagated through automated decisions and given mathematical legitimacy.
- The paper focuses on Disparate Impact for protected variables such as sex, age, and ethnic origin.
- Fairness can be pursued by changing classifiers or modifying input data so the protected attribute becomes unpredictable.
- The paper analyzes Disparate Impact, justifies Wasserstein-barycenter repair, extends repair to multidimensional data, and proposes Random Repair.
- Its structure covers fairness relationships, probabilistic data repair, Wasserstein-barycenter limitations, real-data applications, and proofs.
2 Fairness using Disparate Impact assessment
The paper formalizes fairness through Disparate Impact, Statistical Parity, and Balanced Error Rate, linking these notions to protected-attribute predictability and conditional-distribution distances. Its results characterize fairness using classifier outcomes and Total Variation distance.
- The framework predicts binary success Y from covariates X while modeling protected membership S as minority or default class.
- Disparate Mistreatment instead concerns unequal correct-classification probabilities across protected groups.
- Statistical Parity requires equal positive-prediction probabilities across protected groups, although true outcomes may be unavailable.
- Disparate Impact at level τ is defined by DI(g, X, S) ≤ τ, with Statistical Parity corresponding to DI(g, X, S) = 1.
- Balanced Error Rate averages class-conditional errors and supports defining whether the protected attribute is ε-predictable from X.
- Theorem 2.1 gives an if-and-only-if relationship between Disparate Impact at level τ and an upper bound on BER.
- The minimum BER is related to Total Variation distance between L(X|S = 0) and L(X|S = 1), linking fairness to conditional feature distributions.
- Smaller Total Variation distance makes S less predictable from X; equality of conditional distributions yields independence and DI(g, X, S) = 1.
3 Removing disparate impact using Optimal Transport
The paper frames fair data repair as transforming each protected-group conditional distribution into a common law, so classifiers using the repaired data achieve Statistical Parity. It uses optimal transport, Wasserstein distances, and barycenters to select and construct these transformations while limiting information loss.
- Probabilistic model for data repair: Data repair targets the absence of observed labels by modifying input data rather than changing the classifier.The approach is intended for settings where Y is unavailable or the classification methodology cannot be changed.
- Probabilistic model for data repair: Achieving Statistical Parity requires transforming the conditional distributions of X given each protected-group value into the same distribution.The transformation depends on the protected attribute through a random function T_S.
- Probabilistic model for data repair: A common target distribution ν should be simultaneously close to the group-conditional laws to reduce information loss and preserve prediction using the repaired variable.The repair also requires finding an optimal transport from each conditional distribution to ν.
- Optimal transport formulation: The paper uses Wasserstein distance as a computationally tractable alternative to total variation for comparing and moving probability distributions.Optimal transport plans map L(X | S) to the repaired law L(Ẋ).
- Wasserstein barycenters: A Wasserstein barycenter minimizes weighted variation across distributions and serves as a meaningful common representation of their mean variations.For two distributions, the paper studies barycenter computation and its use in data repair; general computation is difficult.
- Wasserstein barycenters: In one dimension, the repair target is constructed by averaging the quantile functions of the two conditional distributions, while higher-dimensional cases require barycenter computation.The one-dimensional construction corresponds to the minimizer of the Wasserstein barycenter criterion.
4 Full and Partial Repair with Wasserstein Barycenter
The paper repairs group-conditional distributions by transporting them toward a Wasserstein barycenter, then studies full, partial, and random repair as fairness–accuracy tradeoffs. Full repair targets a common distribution, while partial and random repair seek more controllable compromises.
- Total repair: The two conditional distributions are transported to their weighted Wasserstein barycenter, producing a transformed variable with a common conditional distribution.Optimal transport maps T_s push each conditional distribution toward the barycenter; their existence is guaranteed under absolute continuity.
- Total repair: For two distributions, computing the barycenter is equivalent to computing the optimal transport map between them.The barycenter can be represented through displacement along the transport map, so its computational complexity matches that of computing the map.
- Accuracy after repair: The repair framework compares classification using repaired inputs with classification using the full variables (X, S), and bounds the information loss under Lipschitz conditional label probabilities.The analysis defines the best risks for repaired data and full data, then uses Theorem 4.3 under Lipschitz assumptions on η_s.
- Accuracy after repair: The Wasserstein barycenter is a feasible fairness target because minimizing the risk bound leads to transporting both conditional distributions toward it, although the resulting bound is only an upper bound.The paper presents barycenter transport as a reasonable way to achieve statistical parity, while limiting the conclusion to guidance from an upper bound.
- Random repair: Random Repair randomly selects between a target distribution and the original conditional distributions, with the Bernoulli parameter λ controlling the repair amount.The paper promotes this procedure as a way to improve Disparate Impact without hampering classification efficiency too much.
- Partial repair: Partial repair interpolates between unchanged conditional distributions and the barycenter, with λ = 0 leaving data unchanged and λ = 1 giving full repair.Choosing λ balances classification accuracy against reduced predictability of the protected variable, measured through total variation distance.
- Partial repair: For geometric partial repair, dTV(µ0,λ, µ1,λ) = 1 when λ ≤ 2K/(2K + 1), so the protected attribute can remain perfectly predictable near full repair.This motivates an alternative procedure designed to control total variation distance more effectively.
5 Numerical Analysis of Fair Correction of a database
The paper adapts optimal-transport repair to empirical datasets with unequal protected-group sizes, introducing a procedure that achieves total fairness and a random variant trading fairness against accuracy. On Adult Income data, repair substantially improves Disparate Impact, with procedure (B) achieving Statistical Parity and Random Repair offering competitive prediction error.
- 5.1.1 Total repair: Empirical distributions with unequal group sizes may lack Monge maps, so repair uses an optimal transport distribution represented by a transport matrix.Each source point may distribute mass across several target points, or several sources may map to one target.
- 5.1.1 Total repair: Procedure (A) replaces each original point with one repaired point but leaves the two protected-group datasets different and fails to achieve total fairness.It preserves exactly n0 + n1 points while generalizing earlier one-dimensional repair ideas.
- 5.1.1 Total repair: Procedure (B) splits each point’s mass across multiple repaired versions, forming the complete barycenter distribution and guaranteeing total fairness.For every positive transport weight, the algorithm creates corresponding modified points for both protected groups.
- 5.1.1 Total repair: When protected groups have equal size and uniform weights, transport becomes a bijection, so procedures (A) and (B) coincide and total fairness is achieved.In this case, the Monge problem is equivalent to optimal matching.
- 5.1.2 Random repair: Random Repair selects original or repaired points according to λ, controlling the fairness–accuracy trade-off; on Adult Income, procedure (B) reaches Statistical Parity with lower error than procedure (A).The experiments use 29,825 Adult Income instances; Random Repair and Geometric Repair produce different DI–error trade-offs across classifiers and repair levels.
- 5.2 Application to a real example: 0.1927 error with Random Repair versus 0.2076 with Geometric Repair for random forests, while both achieve DI 0.5.For the logit rule, Random Repair gives DI 0.3 with error 0.2068, whereas Geometric Repair gives DI 0.55 with error 0.2136.
6 Appendix
The appendix derives fairness-related classification properties and bounds the risk change caused by transport-based modification of the input data. It also formalizes assumptions and identifies a practical limitation of the transport construction.
- Assumptions: The analysis assumes conditional densities for X given each protected class are absolutely continuous with respect to a common measure.The conditioned variables X/S = i have density functions f_i, and their probability measures share a dominating measure μ.
- Classification analysis: Misclassification error is decomposed into the two protected-class-specific error probabilities weighted by P(S = 0) and P(S = 1).The decomposition uses P(g(X) = 1 | S = 0) and P(g(X) = 0 | S = 1).
- Classification analysis: Bayes’ formula expresses protected-class posterior probabilities through class priors and conditional densities, determining the Bayes classifier’s comparison rule.The posterior comparison is equivalent to π0f0(X) > π1f1(X).
- Fairness criteria: For equal class priors, the Balanced Error Rate becomes P(g(X) ≠ S), linking BER to the misclassification probability of the protected attribute.The appendix specializes the BER expression to π0 = π1 = 1/2.
- Transport-based modification: The risk difference between classification with original and transported inputs is bounded using changes in the conditional regression functions under the transport maps.The bound involves |η0(X) − η0∘T0(X)| and |η1(X) − η1∘T1(X)|, with Lipschitz and Cauchy–Schwarz arguments used in the derivation.