# Unbiased Binning for Fairness-aware Attribute Representation

arXiv: https://arxiv.org/abs/2509.21785 · HTML: https://mlsanity.com/paper/2509.21785/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 54 references that are in the map.
- First posted on arXiv 26 Sep 2025.

## Builds on (most cited first, 17 of 17)

- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Fair Regression: Quantitative Definitions and Reduction-based Algorithms](https://mlsanity.com/paper/1905.12843/) (2019)
- [Representation Bias in Data: A Survey on Identification and Resolution Techniques](https://mlsanity.com/paper/2203.11852/) (2022)
- [Slice Tuner: A Selective Data Acquisition Framework for Accurate and Fair Machine Learning Models](https://mlsanity.com/paper/2003.04549/) (2020)
- [PreFair: Privately Generating Justifiably Fair Synthetic Data](https://mlsanity.com/paper/2212.10310/) (2022)
- [Fair Data Representation for Machine Learning at the Pareto Frontier](https://mlsanity.com/paper/2201.00292/) (2022)
- [Data Cleaning for Accurate, Fair, and Robust Models: A Big Data - AI Integration Approach](https://mlsanity.com/paper/1904.10761/) (2019)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Through the Fairness Lens: Experimental Analysis and Evaluation of Entity Matching](https://mlsanity.com/paper/2307.02726/) (2023)
- [Consistent Range Approximation for Fair Predictive Modeling](https://mlsanity.com/paper/2212.10839/) (2022)
- [Clustering with fair-center representation: parameterized approximation algorithms and heuristics](https://mlsanity.com/paper/2112.07030/) (2021)
- [iFlipper: Label Flipping for Individual Fairness](https://mlsanity.com/paper/2209.07047/) (2022)
- [Chameleon: Foundation Models for Fairness-aware Multi-modal Data Augmentation to Enhance Coverage of Minorities](https://mlsanity.com/paper/2402.01071/) (2024)
- [Threshold-Independent Fair Matching through Score Calibration](https://mlsanity.com/paper/2405.20051/) (2024)
- [Fair Spatial Indexing: A paradigm for Group Spatial Fairness](https://mlsanity.com/paper/2302.02306/) (2023)
- [Mining the Minoria: Unknown, Under-represented, and Under-performing Minority Groups](https://mlsanity.com/paper/2411.04761/) (2024)

## Built on by (most cited first, 1 of 1)

- [Auditing Discriminatory Patterns in Mortgage Lending Through Association Rules and Fair Binning](https://mlsanity.com/paper/2606.12435/) (2026)

## Abstract (arXiv)

Discretizing raw features into bucketized attribute representations is a popular step before sharing a dataset. It is, however, evident that this step can cause significant bias in data and amplify unfairness in downstream tasks. In this paper, we address this issue by introducing the unbiased binning problem that, given an attribute to bucketize, finds its closest discretization to equal-size binning that satisfies group parity across different buckets. Defining a small set of boundary candidates, we prove that unbiased binning must select its boundaries from this set. We then develop an efficient dynamic programming algorithm on top of the boundary candidates to solve the unbiased binning problem. Finding an unbiased binning may sometimes result in a high price of fairness, or it may not even exist, especially when group values follow different distributions. Considering that a small bias in the group ratios may be tolerable in such settings, we introduce the epsilon-biased binning problem that bounds the group disparities across buckets to a small value epsilon. We first develop a dynamic programming solution, DP, that finds the optimal binning in quadratic time. The DP algorithm, while polynomial, does not scale to very large settings. Therefore, we propose a practically scalable algorithm, based on local search (LS), for epsilon-biased binning. The key component of the LS algorithm is a divide-and-conquer (D&C) algorithm that finds a near-optimal solution for the problem in near-linear time. We prove that D&C finds a valid solution for the problem unless none exists. The LS algorithm then initiates a local search, using the D&C solution as the upper bound, to find the optimal solution.