FairTree: Subgroup Fairness Auditing of Machine Learning Models with Bias-Variance Decomposition

1. Problem Statement

Machine learning model evaluation traditionally relies on aggregate performance metrics (e.g., Mean Squared Error, Accuracy), which often mask poor performance or systematic biases within specific subpopulations. Existing auditing tools like SliceFinder and SliceLine attempt to identify these "slices" (subgroups) but suffer from significant limitations:

• Discretization Requirement: They often require continuous covariates (e.g., age, income) to be discretized into bins, which can lead to information loss, arbitrary threshold selection, and the overlooking of small but critical subgroups.
• Lack of Diagnostic Granularity: They typically identify where performance drops but do not distinguish between systematic bias (consistent under/over-prediction) and variance instability (unreliable, inconsistent predictions).
• Computational Inefficiency: Some approaches rely on exhaustive search or computationally expensive resampling methods that do not scale well.

The paper proposes FairTree, a novel algorithm adapted from psychometric invariance testing (specifically Rasch and PL trees) to address these gaps.

2. Methodology

FairTree employs a recursive partitioning framework to detect subgroups where a model's loss function distribution differs significantly from the rest of the data. It offers two statistical variations for testing invariance:

A. The Splitting Criteria

The algorithm tests the null hypothesis that the expected value and variance of the loss function are invariant across all covariates.

1. Permutation Test:
   • A standard statistical approach where group memberships are shuffled to create a reference distribution.
   • Suitable for categorical and continuous data (by testing all unique split points).
   • Computationally intensive ($O(N \cdot \text{permutations})$).
2. Fluctuation Test (Proposed Innovation):
   • Adapted from the Generalized M-fluctuation test used in econometrics.
   • Bias Detection: Uses the Cumulative Sum (CUSUM) of centered residuals ordered by a covariate. Under the null hypothesis, this process converges to a standard Brownian bridge.
   • Variance Detection: Applies a similar fluctuation test to squared, conditionally centered residuals.
   • Advantages: Analytically derived (using the Kolmogorov distribution), avoiding the need for resampling. It handles continuous covariates directly without discretization and is computationally efficient ($O(N \log N)$).

B. Bias-Variance Decomposition

A core feature of FairTree is its ability to categorize detected performance disparities:

• Bias Shift: Indicates systematic discrimination (e.g., consistently under-predicting income for a specific group). This suggests a need for loss function adjustment or adversarial training.
• Variance Shift: Indicates instability or unreliability (e.g., high error variance for a specific group). This suggests a lack of sufficient or high-quality data for that subgroup, requiring data collection rather than just algorithmic tuning.
• Classification Logic:
  • Permutation version: Uses a heuristic ratio (e.g., if bias difference > 1.5 $\times$ variance difference).
  • Fluctuation version: Uses sequential statistical testing with Bonferroni correction on p-values for bias and variance processes.

C. Recursive Partitioning Workflow

1. Global Test: Check for invariance across all covariates.
2. Split: If a violation is found, split the data at the point of maximum deviation (lowest p-value).
3. Decompose: Classify the split as Bias, Variance, or Both.
4. Recurse: Repeat the process on the resulting subgroups until stopping criteria are met (e.g., no significant splits or sample size threshold).

3. Key Contributions

• Handling Continuous Covariates: Unlike SliceFinder/SliceLine, FairTree processes continuous, ordinal, and categorical features natively without discretization, preserving data integrity and avoiding arbitrary binning.
• Diagnostic Decomposition: It is the first auditing tool to explicitly separate performance disparities into bias (systematic error) and variance (instability), providing actionable insights for remediation.
• Statistical Rigor & Efficiency: The introduction of the Fluctuation Test provides a computationally efficient, analytically grounded alternative to permutation testing, maintaining high statistical power even with small sample sizes.
• Open Framework: The method is designed to be model-agnostic, applicable to both classification and regression tasks.

4. Experimental Results

The authors evaluated FairTree through three simulation studies and an empirical application on the UCI Adult Census dataset, comparing it against SliceLine.

• Type I Error & Power (Study I):
  • Both FairTree variants maintained Type I error rates close to the nominal level (0.05).
  • The Fluctuation Test demonstrated significantly higher statistical power than the Permutation Test, especially at moderate effect sizes and in scenarios with imbalanced group sizes (minority groups).
  • SliceLine failed to detect effects with default thresholds and showed inflated false positives with tuned thresholds.
• Bias-Variance Classification (Study II):
  • The Fluctuation Test accurately classified whether a disparity was due to bias, variance, or both.
  • The Permutation Test struggled when both bias and variance were present simultaneously.
  • SliceLine could not classify the type of error, only detecting the presence of a slice.
• Realistic Scenarios (Study III):
  • FairTree (Fluctuation) achieved near-perfect detection rates (0.97–1.00) across complex scenarios including continuous covariates, interaction effects, and confounding variables.
  • It successfully detected violations in small minority groups (10% of data) where statistical power is usually low.
• Empirical Illustration (UCI Adult Dataset):
  • FairTree successfully identified injected biases (age < 25) and variances (hours > 55).
  • Discretization Impact: When continuous variables were forced into bins (as required by SliceLine), the signal was diluted, leading to incorrect split points (e.g., detecting age $\le$ 35 instead of the true threshold).
  • Efficiency: The Fluctuation Test was orders of magnitude faster (21.6 ms) than the Permutation Test (26.4 s) on the large dataset.

5. Significance and Conclusion

FairTree represents a significant advancement in algorithmic fairness auditing by bridging the gap between psychometric invariance testing and machine learning evaluation.

• Practical Utility: By distinguishing between bias and variance, it guides practitioners toward the correct remediation strategy (algorithmic tuning vs. data collection).
• Robustness: Its ability to handle continuous variables without discretization prevents the "masking" of fairness violations that occurs in bin-based methods.
• Recommendation: The authors recommend the Fluctuation Test variant for most applications due to its superior power, speed, and analytical rigor, while noting the Permutation Test as a useful fallback for very small sample sizes where asymptotic assumptions might not hold.

The paper concludes that FairTree provides a flexible, statistically rigorous framework for evaluating model performance and fairness, particularly in scenarios involving small datasets or continuous covariates where existing tools fall short.