Provable Detection of Propagating Sampling Bias in Prediction Models

Pavan Ravishankar, Qingyu Mo, Edward McFowland Iii, Daniel B. NeillAAAI 2023 · DOI

Abstract

Machine learning fairness is often evaluated in isolation at either the data or prediction stages. This paper presents a mathematical framework to quantify how "differential sampling bias" (DSB) in training data propagates through the modeling pipeline to infect final predictions. We derive theoretical thresholds that allow auditors to provably detect this bias using subset scanning techniques. Our contributions include a closed-form propagation formula and proofs of asymptotic detectability, validated on the COMPAS and NYPD Stop-Question-Frisk datasets.

Introduction

Fairness in machine learning (ML) is a critical concern, yet the relationship between biased training data and biased predictions is often treated as a black box. A primary source of unfairness is differential sampling bias (DSB), which occurs when a subpopulation is sampled such that the relationship between features ($X$) and outcomes ($Y$) in the training set deviates from the true population. For instance, if law enforcement disproportionately targets specific neighborhoods, an ML model trained on resulting arrest records will learn an inflated risk profile that reflects policing patterns rather than actual criminal behavior.

This research addresses a fundamental question for auditors: Exactly how much data bias is required before it becomes statistically detectable in a model's predictions?

Methodology: The Bias Propagation Pipeline

The authors model the ML lifecycle as a four-stage process: data collection, modeling, prediction, and auditing (Bias Scan).

The four-stage pipeline of bias propagation and detection.

To detect bias at the prediction stage, the researchers utilize Bias Scan, a multi-dimensional subset scanning algorithm. Bias Scan identifies intersectional subgroups (e.g., specific combinations of race, gender, and age) where predicted probabilities deviate significantly from observed outcomes.

Theoretical Contributions

The paper establishes four key theorems:

  1. Propagation Formula: A closed-form expression relating injected bias ($\Delta$) to the resulting Log-Likelihood Ratio (LLR) score.
  2. Detection Thresholds: Asymptotic results for the "null distribution," defining the score expected in the absence of bias to set a significance threshold ($\alpha$).
  3. Provable Detectability: Proof that as dataset size increases, the probability of detecting any non-zero DSB approaches 100%.
  4. Minimum Bias Calculation: A method to determine the minimum bias ($\Delta_{thresh}$) required for detection in finite datasets.

Experimental Validation

The framework was validated using two datasets:

  • COMPAS: A recidivism dataset used for semi-synthetic experiments where known amounts of bias were injected into specific subgroups.
  • NYPD Stop-Question-Frisk (SQF): Real-world data used to estimate DSB by comparing historical records against a hypothetical "less biased" weapon-focused strategy.

Key Results

The experiments confirmed that bias propagation is mathematically predictable. As shown in the figures below, the observed Bias Scan scores (LLR) and the overlap between injected and detected biased groups follow the theoretical curves.

Comparison of theoretical and empirical bias detection. (a) LLR scores vs. bias amount. (b) Overlap between injected and detected subgroups.

In the COMPAS experiments, once the injected bias ($\Delta$) exceeded the calculated threshold ($\Delta_{thresh}$), the detection power (overlap) jumped toward 1.0, indicating near-perfect detection. For the NYPD data, the method identified a significant biased subgroup (non-Bronx residents under 70) with an estimated DSB of $\Delta \approx 2.675$.

Discussion and Limitations

While this framework provides a rigorous tool for auditors, several limitations remain. The current proofs assume "rectangular" subgroups defined by simple feature intersections, which may not capture complex non-linear patterns. Additionally, the model focuses on sampling bias and does not yet account for measurement bias (incorrect labels) or omitted variable bias. Furthermore, the method requires auditors to have access to ground-truth outcomes for the test set, which may not always be available in real-time monitoring scenarios.

Conclusion

This work bridges the gap between data-stage and prediction-stage fairness by providing a provable link between training bias and detectable prediction errors. By quantifying the "gray zone" where bias exists but remains indistinguishable from noise, it offers a vital theoretical foundation for building more transparent and accountable machine learning systems.

Summary updated

BibTeX
@inproceedings{ravishankar2023provable,
  author = {Pavan Ravishankar and Qingyu Mo and Edward McFowland III and Daniel B. Neill},
  title = {{Provable Detection of Propagating Sampling Bias in Prediction Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i8.26144},
}
Figure