A Reduction to Binary Approach for Debiasing Multiclass Datasets

Ibrahim Alabdulmohsin, Jessica Schrouff, Oluwasanmi Koyejo

Abstract

While algorithmic fairness research has traditionally focused on binary classification and binary sensitive attributes, real-world datasets—ranging from image classification to healthcare diagnostics—are predominantly multiclass. This paper introduces Reduction-to-Binary (R2B), a model-agnostic preprocessing algorithm designed to debias multiclass datasets. By decomposing complex multiclass fairness constraints into parallel binary tasks using the Alternating Direction Method of Multipliers (ADMM), R2B provides formal fairness guarantees while avoiding the common pitfalls of simpler heuristic approaches.

Introduction

The majority of existing fairness literature addresses the "binary-binary" scenario: a binary prediction (e.g., hire vs. don't hire) and a binary sensitive attribute (e.g., male vs. female). However, this framework fails to capture the complexity of modern data. In the TensorFlow Dataset catalog, fewer than 10% of image classification datasets are binary. Furthermore, protected attributes under legal frameworks like the US Equal Credit Opportunity Act—such as race, religion, and age—are inherently non-binary.

Addressing fairness in multiclass settings is non-trivial. Simple extensions of binary debiasing methods often fail due to the "normalization trap," where the mathematical steps required to ensure a valid probability distribution re-introduce the very bias the algorithm intended to remove. R2B addresses these challenges by providing a robust, scalable framework for multiclass demographic parity.

The Reduction-to-Binary (R2B) Framework

R2B is a preprocessing method that modifies training labels before model training begins. This approach ensures the method is model-agnostic, allowing it to be used with any downstream classifier, including Random Forests, Deep Neural Networks, or k-Nearest Neighbors.

The Normalization Trap

A common "common sense" approach to multiclass debiasing involves debiasing each class label independently and then normalizing the results so they sum to one. However, this normalization step creates a dependency between classes that can re-introduce bias. R2B is specifically engineered to bypass this hurdle by treating the debiasing and normalization as a joint optimization problem.

Optimization via ADMM

The core of R2B is the use of the Alternating Direction Method of Multipliers (ADMM) to decompose the global multiclass optimization problem—minimizing label distortion while enforcing demographic parity—into two alternating, iterative steps:

  1. Parallel Debiasing: Each class label is debiased independently using the Randomized Threshold Optimizer (RTO), an efficient algorithm for binary fairness.
  2. Aggregation and Normalization: The results are aggregated and adjusted to ensure they form a valid probability distribution across all classes.

Through this iterative process, the algorithm converges to an optimal set of debiased labels that satisfy a specified fairness tolerance ((\epsilon)).

Experimental Evaluation

The authors validated R2B across diverse benchmarks to test its scalability and effectiveness in high-dimensional settings.

  • Adult Income Dataset: Repurposed to predict one of 16 education levels with sex as the sensitive attribute. On a biased version of the dataset, R2B reduced Demographic Parity (DP) from 48.0% to 1.0%, outperforming standard baselines.
  • COCO Dataset: In this computer vision task (predicting the distribution of 80 object classes), R2B achieved the highest accuracy (48.1%) among debiasing methods while maintaining a negligible DP of 1.1%.
  • Dermatology Dataset: In a healthcare context predicting 27 skin conditions with age as the sensitive attribute, R2B matched the best-performing baselines in Top-1, Top-2, and Top-3 accuracy while successfully mitigating dataset bias.

Key Insights

Scalability in High-Dimensional Spaces

Feature-based debiasing methods, such as the Demographic Parity Remover, often struggle as the number of features increases. R2B, by focusing on label modification rather than feature transformation, remains robust even in high-dimensional settings. This makes it particularly suitable for complex tasks like image classification.

Theoretical Guarantees

Unlike many heuristic debiasing methods, R2B provides a formal "Bias Guarantee." The authors provide a mathematical bound on the demographic parity of any classifier trained on the output of the R2B algorithm, ensuring that the fairness constraints are reliably met.

Limitations and Future Work

While R2B is a significant step forward for multiclass fairness, it has specific limitations:

  • Metric Constraints: It currently focuses on Demographic Parity. Because it is a preprocessing method, it does not yet accommodate "error parity" metrics like Equalized Odds, which require knowledge of prediction errors.
  • Attribute Types: The algorithm is designed for categorical sensitive attributes. Continuous attributes (like exact age) must be binned into categories before processing.
  • Causal Fairness: R2B addresses statistical parity rather than causal fairness, which may be a requirement in specific domains like healthcare where the underlying cause of a disparity is relevant.

Future research may extend this reduction-to-binary approach to other fairness definitions and develop methods to handle continuous sensitive variables without the need for discretization.

Summary updated

BibTeX
@inproceedings{alabdulmohsin2022reduction,
  author = {Ibrahim Alabdulmohsin and Jessica Schrouff and Oluwasanmi Koyejo},
  title = {{A Reduction to Binary Approach for Debiasing Multiclass Datasets}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=ogNrYe9CJlH},
}
Figure