Unbiased Binning: Fairness-aware Attribute Representation DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06

Abolfazl Asudeh, Zeinab (Mila) Asoodeh, Bita Asoodeh, Omid Asudeh · 2025

Read Unbiased Binning: Fairness-aware Attribute Representation DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 by Abolfazl Asudeh, Zeinab (Mila) Asoodeh, Bita Asoodeh, Omid Asudeh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-21785.txt.

Introduction

Sharing data often starts with binning: raw values, like income, are grouped into ranges. Abolfazl Asudeh, Zeinab Asoodeh, Bita Asoodeh, and Omid Asudeh show in this 2025 paper that this step can quietly bake in unfairness. A poor choice of bin edges can skew group shares and harm later decisions. The authors set out to bin without that bias.

They define the unbiased binning problem: find the grouping closest to equal-size bins that keeps group shares even in every bin. They prove the best edges must come from a small candidate set, then give an efficient algorithm to search it. Fair bins sometimes cost too much accuracy, or do not exist at all. So the paper also defines a relaxed version that allows a small set bias, with a fast optimal method and a scalable search method on top.

Catalog record

CREATORAbolfazl Asudeh, Zeinab (Mila) Asoodeh, Bita Asoodeh, Omid Asudeh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-21785

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Unbiased Binning: Fairness-aware Attribute Representation DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 Abolfazl Asudeh, Zeinab (Mila) Asoodeh, Bita Asoodeh, Omid Asudeh Abstract . 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 ε \varepsilon -biased binning problem that bounds the group disparities across buckets to a small value ε \varepsilon . We first develop a dynamic programming solution 𝖣𝖯 \mathsf{DP} that finds the optimal binning in quadratic time. The 𝖣𝖯 \mathsf{DP} algorithm, while polynomial, does not scale to very large settings. Therefore, we propose a practically scalable algorithm, based on local search ( 𝖫𝖲 \mathsf{LS} ), for ε \varepsilon -biased binning. The key component of the 𝖫𝖲 \mathsf{LS} algorithm is a divide-and-conquer ( 𝖣 & 𝖢 \mathsf{D\&C} ) algorithm that finds a near-optimal solution for the problem in near-linear time. We prove that 𝖣 & 𝖢 \mathsf{D\&C} finds a valid solution for the problem unless none exists. The 𝖫𝖲 \mathsf{LS} algorithm then initiates a local search, using the 𝖣 & 𝖢 \mathsf{D\&C} solution as the upper bound, to find the optimal solution. In addition to theoretical analysis, we perform extensive experiments using real-world and synthetic datasets to validate our problem and evaluate our algorithms. Besides confirming the efficiency of the algorithms, our experiments verify that while fairness-unaware binning can generate biased attribute representations, this bias can be significantly reduced at a negligible price of fairness. 1. Introduction For various reasons such as augmenting privacy preservation and minimizing the impact of noise ( Mironchyk and Tchistiakov 2017 ) , attribute binning (also known as bucketization) is widely applied in domains such as credit scoring ( Oliveira et al. 2008 ; Zeng 2014 ) , where the raw attribute values are partitioned into discrete intervals, known as bins or buckets 1 1 1 We use the terms “bin” and “bucket” interchangeably. , each representing a category of values. The original attribute values that fall into a given interval are replaced by the bin value. Equal-size (aka. equal-frequency) binning, in particular, ensures an equal number of tuples fall inside each bucket ( Kotsiantis and Kanellopoulos 2006 ; Boulle 2005 ) . Despite its conceptual simplicity and computational appeal, the process of attribute bucketization frequently induces unintended biases, thereby amplifying preexisting disparities embedded within the dataset. To further clarify this issue, let us present the following motivation example. Example 0. Consider a credit scoring application that stratifies individuals based on income. Income disparities across different demographic groups, when combined with binning, may inadvertently cluster marginalized populations predominantly into lower-tier buckets. Such biased attributes can propagate biases throughout the data analytics pipeline, further exacerbating unfairnesses within downstream decisions. This issue becomes critically important in sensitive domains such as finance, healthcare, employment screening, and criminal justice, wherein biased data transformations can yield discriminatory and inequitable outcomes ( Angwin et al. 2022 ; Barocas and Selbst 2016 ) . For example, diagnostic healthcare models trained on bucketized attributes exhibiting demographic bias might disproportionately recommend preventive care measures to certain populations while neglecting others ( Obermeyer et al. 2019 ) . Similarly, credit scoring systems employing improperly bucketized financial attributes may lead to unfair loan application denials, particularly disadvantaging marginalized communities ( Hurley and Adebayo 2016 ) . Conversely, despite its substantial implications, this problem has been overlooked by the literature, while prior research has predominantly concentrated on training fair models using potentially biased attributes. Therefore, towards filling this gap, in this paper we introduce the unbiased binning problem, wherein the goal is to ensure demographic group parity across buckets, while minimally deviating from equal-size bucketization. In order to efficiently solve the problem, we define “boundary candidates”, a small set of possible boundaries, and prove that the optimal unbiased binning must draw the bucket boundaries only from this set. We develop an efficient dynamic programming approach on top of the boundary candidates that finds the optimal unbiased binning. Due to several reasons, such as distribution mean differences between various groups, unbiased binning may cause a high price of fairness, significantly deviating from the equal-size binning, and sometimes, an unbiased binning may not even exist. On the other hand, a small amount of bias might be tolerable in binning in such settings. Therefore, we next introduce the problem of \varepsilon -biased binning that bounds the group-disparity between the buckets to \varepsilon . Our proposed solution for unbiased binning is not applicable for \varepsilon -biased binning, since the concept of boundary candidates does not extend to the new setting. To address this issue, we introduce a matrix that specifies the set of possible \varepsilon -biased buckets, and use it to extend our dynamic programming ( \mathsf{DP} ) approach for \varepsilon -biased binning. Our DP solution, however, is not scalable to very large settings since it has a quadratic time complexity. Table 1 . Key aspects of the algorithms presented in the paper. Practically Time Space Problem Algorithm Optimal? Scalable? Complexity Complexity Unbiased UnbiasedBinning ✓ ✓ O(n\log n+m^{2}k) O(mk) Binning (Algorithm 2 ) \varepsilon -biased \mathsf{DP} (Algorithm 4 ) ✓ ✗ O(n^{2}k) O(n^{2}) Binning \mathsf{D\&C} (Algorithm 5 ) ✗ ✓ O(n\log n) O(n) \mathsf{LS} (Algorithm 6 ) ✓ ✓ O(n^{k}) O(n) Thus, we propose a practically scalable solution for \varepsilon -biased binning based on a local search around equal-size binning. A key component of our practical solution is a divide and conquer \mathsf{D\&C} algorithm that finds a near-optimal \varepsilon -biased binning in a near-linear time. We prove that when \mathsf{D\&C} fails to find a valid solution, the problem is infeasible. The \mathsf{D\&C} algorithm can serve as a heuristic for finding a practical (non-optimal) solution for the problem. The local search \mathsf{LS} algorithm uses the output of \mathsf{D\&C} to limit its search space to only the combinations with smaller objective values. Table 1 summarizes the key aspects of our proposed algorithms. Besides theoretical analysis, we conduct an extensive set of experiments on both real-world and synthetic datasets to (i) empirically validate the practical relevance of our problem and the effectiveness of our algorithms, and (ii) evaluate the performance of our algorithms across a wide range of settings. Our experimental results demonstrate not only the efficiency and scalability of our algorithms but also underscore that traditional fairness-unaware binning approaches can lead to biased attribute representations, potentially resulting in unfair decisions in downstream tasks. On the other

Read the complete text