PaperlayerView exact revision on arXiv

Source-linked AI summary

Certifying and removing disparate impact

Michael Feldman, Sorelle Friedler, John Moeller, Carlos Scheidegger, Suresh Venkatasubramanian

arXiv:1412.3756v3stat.MLcs.CY

TL;DR

The paper asks how to certify and remove disparate impact when algorithmic decision processes may be proprietary or difficult to interpret. It links disparate impact to balanced error rate and protected-attribute predictability, then repairs data to suppress that predictability while preserving useful signal. Experiments support effective certification and favorable fairness–accuracy comparisons, while performance depends on the classifier and the method currently handles numerical attributes only.

  • Problem

    Determining disparate impact is difficult when computer-based decision processes are undisclosed or hard to explain, motivating outcome-based analysis of the data algorithms use.

  • Method

    The paper certifies disparate-impact absence by testing protected-attribute predictability and removes it by transforming unprotected data while retaining the protected attribute.

  • Results

    Experiments found certification effective with three classifiers, fairness–utility tradeoffs for partial repairs, and higher accuracy than related fairness procedures at desired fairness values.

  • Takeaways & Limitations

    Changing the data to achieve fairness allows strong classifiers to be used for prediction while preserving much of the signal in unprotected attributes.

  • Takeaways & Limitations

    Repair performance varies substantially with the chosen classification algorithms, and the presented algorithm operates only on numerical attributes.

Abstract

from arXiv · show

What does it mean for an algorithm to be biased? In U.S. law, unintentional bias is encoded via disparate impact, which occurs when a selection process has widely different outcomes for different groups, even as it appears to be neutral. This legal determination hinges on a definition of a protected class (ethnicity, gender, religious practice) and an explicit description of the process. When the process is implemented using computers, determining disparate impact (and hence bias) is harder. It might not be possible to disclose the process. In addition, even if the process is open, it might be hard to elucidate in a legal setting how the algorithm makes its decisions. Instead of requiring access to the algorithm, we propose making inferences based on the data the algorithm uses. We make four contributions to this problem. First, we link the legal notion of disparate impact to a measure of classification accuracy that while known, has received relatively little attention. Second, we propose a test for disparate impact based on analyzing the information leakage of the protected class from the other data attributes. Third, we describe methods by which data might be made unbiased. Finally, we present empirical evidence supporting the effectiveness of our test for disparate impact and our approach for both masking bias and preserving relevant information in the data. Interestingly, our approach resembles some actual selection practices that have recently received legal scrutiny.

1 Introduction

The paper frames disparate impact as a legal and computational problem: certify decision outcomes without inspecting proprietary algorithms, then modify data to reduce protected-attribute leakage while preserving useful information.

  • Legal motivation: Disparate impact makes an otherwise neutral hiring process illegal when its outcomes differ by race, as established in Griggs v. Duke Power Co.The ruling led Duke Power Co. to stop using intelligence scores and diplomas that were largely correlated with race.
  • Operational definition: The adopted generalized 80% rule declares disparate impact when the positive-outcome probability ratio between protected groups is at most τ = 0.8.The definition evaluates conditional probabilities over the given dataset and binary decision outcomes.
  • Problem formulation: The paper addresses certification of classification outcomes and removal of disparate impact from datasets without judging or disclosing the underlying algorithm.Certification concerns outcomes predicted from Y, while removal changes Y but leaves the protected attribute C unchanged.
  • Contributions: The paper links disparate impact to balanced error rate, uses protected-attribute predictability to certify its absence, and develops data transformations that prevent such predictability.The transformation is intended to preserve signal in unprotected attributes and remain close to the original data distribution.
  • Empirical results: Empirically, the certification algorithm was effective with three classifiers, while partial repairs exposed a fairness–utility tradeoff and achieved higher accuracy than related procedures at desired fairness values.The authors attribute this comparison to changing the data while allowing strong classifiers to perform prediction.
  • Detection: A better classifier provides a more sensitive detector of disparate impact because the detection procedure itself uses a classification algorithm.The paper argues that stronger pattern learning can both introduce subtle dependencies and help detect them.

2 Related Work

Related work divides discrimination-mitigation methods into classifier modification and data modification, with prior approaches addressing indirect prejudice, individual fairness, and group-based fairness.

  • Approaches: Prior work broadly achieves fairness either by modifying classifiers or by modifying the input data.The paper places its own approach in the data-modification category.
  • Classifier modification: Regularization methods reduce indirect prejudice while retaining accurate classification, but reported reductions in prejudicial outcomes also reduce classification accuracy.Kamishima et al. use a classifier regularizer to penalize prejudicial outcomes.
  • Individual and group fairness: Fairness-through-awareness work combines individual fairness based on similarity with statistical group-based fairness criteria similar to those studied here.The cited approaches seek comparable outcomes for similar individuals and, in Zemel et al., also incorporate group fairness.
  • Disparate-impact measures: The paper’s 80% rule is part of broader prior work measuring discrimination through a classifier’s confusion matrix.Pedreschi, Ruggieri, and Turini examine the same rule within that larger class of measures.

3 Disparate Impact and Error Rates

This section reinterprets the 80% rule using classification error measures and protected-attribute prediction, yielding a dataset-based formulation of disparate impact and its reciprocal likelihood-ratio measure.

  • Error-rate formulation: The paper reinterprets the 80% rule using standard statistical measures rather than ordinary accuracy.The motivation is that class-sensitive error metrics relate more directly to the rule.
  • Notation: For notation, the protected attribute is binary, with X = 0 denoting the minority class and X = 1 the default class.The binary mapping is a convenience for analysis and does not express judgments about the classes.
  • Dataset formulation: The framework represents confusion-matrix entries as probabilities over paired classification outcomes under the input distribution, using the empirical distribution for a specific dataset.The 80% rule is then restated directly in terms of the dataset.
  • Class-conditioned metrics: Sensitivity is the conditional probability of returning YES for majority-class examples, while specificity is the conditional probability of returning NO for minority-class examples.These class-conditioned rates are used to connect classification performance with disparate impact.
  • Likelihood-ratio connection: The positive likelihood ratio is defined as sensitivity divided by one minus specificity, and the paper uses its reciprocal as DI.The reciprocal permits discussion of disparate-impact values before applying the threshold.
  • Scope: For multivalued protected attributes, the paper compares each non-default value pairwise with a designated majority class, leaving joint discrimination beyond scope.This treatment ignores zero-sum effects among different class values.

4 Computational Fairness

The paper defines computational fairness through whether protected attributes can be predicted from supposedly unprotected data, connecting this predictability to disparate impact. It uses balanced error rate to certify when classifiers cannot exhibit disparate impact, while noting important limits when minority selection rates are small.

  • Computational fairness: The computational fairness setting assumes an evaluator can inspect data D but not the decision algorithm A, which claims to use only unprotected attributes Y.The certification process focuses on outcomes and is indifferent to whether protected information is used directly or through proxy attributes.
  • Computational fairness: If protected attribute X cannot be predicted from remaining attributes Y, the algorithm is considered fair with respect to the evaluator on D.This intuition motivates defining fairness as non-predictability of X from Y.
  • Predictability and disparate impact: Balanced error rate (BER) measures the unweighted average of class-conditioned errors for a predictor of X from Y.The paper selects BER because it can be optimized with standard machine-learning predictors and related to the positive likelihood ratio underlying disparate impact.
  • Predictability and disparate impact: Theorem 4.1 states that a data set is (1/2 −β/8)-predictable if and only if it admits disparate impact, where β is the minority-class selection rate.This theorem supplies the formal link between protected-attribute predictability and the legal fairness criterion.
  • Limitations: As β approaches zero, the certification bound becomes vacuous, so low protected-class selection rates make discriminatory practices harder to detect.The paper illustrates this boundary with interviewing many protected-class applicants without hiring them, which lowers β.
  • Certification: Certification runs a BER-optimizing classifier to predict X from Y and declares the data set free from disparate impact when the observed error exceeds the derived threshold.With an optimal BER classifier, the lower bound on all classifiers' errors establishes that no classifier on D exhibits disparate impact.

5 Removing disparate impact

The paper repairs disparate impact by transforming unprotected attributes so protected-group distributions become indistinguishable while preserving within-group rank information. Full repair achieves fairness and rank preservation, while partial repair exposes a fairness–utility tradeoff.

  • Full repair: Strong rank preservation maps each value to a repaired counterpart with the same conditional rank, allowing higher-ranked applicants to remain preferred.For y in Y_x, the repaired value ȳ satisfies F_x(y) = F_x(ȳ).
  • Full repair: The median distribution minimizes the sum of earthmover distances to the protected-group distributions.This distribution is defined through the median of group-specific inverse quantiles and is the closest consensus distribution under the stated objective.
  • Full repair: The repair changes Y while retaining X and C, making protected attributes unpredictable from the transformed attributes.The resulting data set is constructed as (X, Ȳ, C), with only Y changed; the protected attribute and class remain unchanged.
  • Full repair: Theorem 5.1 states that the fully repaired data is fair and strongly preserves rank.The repair algorithm is designed for a single totally ordered attribute, while multiple totally ordered attributes are repaired individually.
  • Full repair: In the SAT example, group-specific score distributions are replaced by a common distribution with μ = 475 and σ = 75.A male score of 500 at the original 95th percentile becomes 625 at the repaired 95th percentile, while repaired female scores of 625 originally corresponded to 750.
  • Partial repair: Partial repair moves conditional inverse-quantile distributions toward the median distribution, with λ = 0 unchanged and λ = 1 fully repaired.The paper studies how utility decreases as λ increases and notes that partial repair creates a fairness–classification-accuracy tradeoff.

6 Experiments

Experiments evaluate certification and repair across three datasets, classifiers, and partial-repair levels, measuring fairness against utility. Repairs generally reach legal disparate-impact values, with dataset-dependent utility costs and comparable combinatorial and geometric results.

  • Experimental setup: Preprocessing removes protected attributes and unordered categorical features, converts ordered categories to integers, and scales features to [0, 1].The repair process retains access to the protected attribute X while classification excludes protected attributes from Y.
  • Certification: The certification analysis produces no points above its BER threshold and substantially below DI = 0.8; only a few near-threshold points are false positives.The authors attribute these points partly to estimation error in β and note that another classifier might permit a tighter threshold.
  • Fairness / Utility Tradeoff: Across datasets, increasing fairness causes utility to decay, but full repair reduces Adult Income utility only from about 74% to 72% versus German Credit from about 72% to 50%.Each unrepaired dataset begins with DI < 0.8 and can be repaired to a legal value.
  • Fairness / Utility Tradeoff: Combinatorial and geometric repairs yield similar DI and utility values across partial repairs, so either repair can be used.Some DI > 1 points are unfair to the majority class because DI uses fixed majority and minority reference groups.
  • Multiple protected attributes: When multiple protected attributes are repaired jointly, utility loss is close to the maximum loss for any single attribute rather than compounding.The authors associate this result partly with the dataset being large enough for each subgroup to remain sufficiently large.
  • Comparison to previous work: Compared with related methods, partially repaired German Credit and Adult datasets can achieve better accuracy at any chosen fairness value.Classifier choice also matters: on Adult Income, Naive Bayes repairs have better high-fairness accuracy than Logistic Regression repairs, while equal class weighting may improve the baseline comparison.

7 Limitations and Future Work

The paper identifies performance variation across repair algorithms and limits its current scope to U.S. legal frameworks and numerical attributes.

  • Repair performance differs substantially across the classification algorithms evaluated.The authors call for systematic study of dataset features, algorithms, and repair performance.
  • The paper’s disparate-impact discussion is tied to U.S. law, motivating future comparison of legal frameworks across jurisdictions.The authors propose investigating whether a single unifying formulation is possible.
  • The presented repair algorithm operates only on numerical attributes.Future work could generalize the procedures to categorical and vector-valued attributes.

A A Survey of Discrimination Types

The survey categorizes discrimination notions as disparate treatment or disparate impact, emphasizing that disparate impact focuses on outcomes rather than the decision process.

  • Discrimination notions are categorized as disparate treatment or disparate impact.Disparate impact is outcome focused and is less concerned with how an outcome was determined until legal scrutiny reaches the process.

A.1 Disparate Treatment

The paper distinguishes explicit discrimination from outcome-based concerns and examines cases where protected-class membership can affect decisions, fairness, or legal interpretation.

  • Disparate treatment refers to discriminatory outcomes caused by choices explicitly based on protected-class membership.The computer science literature has also called this blatant explicit discrimination or direct discrimination when the protected class enters the model.
  • Reverse tokenism cannot effectively conceal discrimination when rejecting qualified majority-class candidates is itself explicitly based on majority status.The paper connects this scenario to disparate treatment under Ricci v. DeStefano.
  • Ricci v. DeStefano involved disparate impact followed by a decision not to implement promotion-test results, which was found to discriminate against the majority class.The paper describes this as a circularity that disparate-impact repair must address.
  • Using protected-class membership may improve accuracy and benefit the protected class, but explicit use can constitute disparate treatment.If membership is not used and positive outcomes are proportionally unequal, the result may instead be disparate impact.
  • Disparate impact can be tested over joint classes such as protected status and another attribute to detect unfair outcomes within protected subgroups.The paper notes that the additional attribute may be legally permissible, such as student grades in college admissions.

A.2 Disparate Impact

Disparate impact concerns unequal outcomes associated with protected-class membership even when decisions use proxy attributes rather than protected status directly.

  • Disparate impact occurs when outcomes differ by protected-class membership despite a process that does not explicitly use that membership.The paper describes proxy attributes as a route by which such differences can arise.
  • Redlining uses neighborhood as a proxy for race to deny services.
  • Discrimination based on redundant encoding occurs when protected-class information is encoded in other decision-making data.The encoded information need not be explicitly used as a protected attribute.
  • Cutting off business with a population segment disproportionately containing protected-group members generalizes redlining.
  • Indirect discrimination arises when attributes dependent on protected-class membership generate discriminatory outcomes.
  • A self-fulfilling prophecy can arise when equal interview rates coexist with unequal hiring rates and later justify lower hiring of the protected class.The paper focuses on outcomes to avoid evaluating fairness solely from interview rates.
  • Negative legacy in training data is captured by disparate impact when it causes outcomes to differ by protected-class membership.If it causes no outcome differences, the paper considers the bias overcome under this standard.
  • Underestimation from a model that has not converged because of a small dataset is treated as a possible source of discrimination detectable through resulting outcomes.
Loading 1412.3756v3…