🤖 AI

Unbiased Binning for Fairness-aware Attribute Representation

This paper addresses the bias introduced by feature discretization in fairness-aware machine learning by defining unbiased and epsilon-biased binning problems and proposing efficient dynamic programming and scalable local search algorithms to find optimal or near-optimal bucketizations that satisfy group parity constraints.

Original authors: Abolfazl Asudeh, Zeinab Asoodeh, Bita Asoodeh, Omid Asudeh

Published 2026-06-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Abolfazl Asudeh, Zeinab Asoodeh, Bita Asoodeh, Omid Asudeh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Sorting the Fruit Basket

Imagine you have a giant basket of fruit (a dataset) containing apples and oranges (different demographic groups, like different races or genders). Before you share this basket with a chef to make a pie (train a machine learning model), you decide to sort the fruit into smaller bowls (buckets or bins) based on how sweet they are (a specific attribute like income or age).

The Problem:
Usually, people sort the fruit by simply cutting the basket into equal-sized piles. They might say, "Put the first 100 fruits in Bowl 1, the next 100 in Bowl 2," and so on.

The paper argues that this simple method is dangerous. Because apples and oranges grow in different patterns, a simple "equal-size" cut might accidentally put almost all the apples in the first few bowls and almost all the oranges in the last few. When the chef uses these bowls to make decisions, they might treat the groups unfairly, not because the chef is biased, but because the bowls themselves were unfair.

The Goal:
The authors want to create a new way of sorting the fruit. They want to cut the basket into bowls where every single bowl has the exact same mix of apples and oranges as the original big basket. This is called "Unbiased Binning."

The Three-Step Solution

The paper proposes a toolkit to fix this sorting problem. Here is how they do it, step-by-step:

1. The "Perfect Cut" (Unbiased Binning)

First, they ask: "Can we cut the fruit so that every bowl is perfectly balanced?"

The Magic Trick: They realized you don't need to check every possible way to cut the fruit. You only need to look at specific "candidate cuts" where the ratio of apples to oranges matches the whole basket.
The Algorithm: They built a smart, step-by-step calculator (called Dynamic Programming) that quickly finds the best possible cuts to make every bowl perfectly balanced.
The Catch: Sometimes, the fruit is so unevenly distributed that it's mathematically impossible to make every bowl perfectly balanced without making some bowls tiny and others huge. In these cases, a "perfect" solution doesn't exist.

2. The "Good Enough" Cut ( $\epsilon$ -Biased Binning)

Since a perfect solution isn't always possible, they introduced a flexible version called $\epsilon$ -biased binning.

The Analogy: Instead of demanding a bowl be 50% apples and 50% oranges, they say, "Okay, let's allow a little wiggle room. As long as the bowl is between 45% and 55% apples, it's fine." That wiggle room is called $\epsilon$ (epsilon).
The Challenge: Finding the best "good enough" cut is much harder for computers to solve quickly, especially with huge baskets of fruit. The "perfect" calculator is too slow for massive datasets.

3. The "Smart Search" (Local Search & Divide-and-Conquer)

To handle huge datasets, they invented a two-part strategy:

Step A: The Rough Sketch (Divide-and-Conquer): They use a fast, rough method to quickly find a valid solution that fits the "wiggle room" rules. It's like drawing a quick sketch of the cut lines to make sure they aren't crazy. This happens very fast.
Step B: The Fine-Tuning (Local Search): Once they have that rough sketch, they look closely at the lines in that sketch. They wiggle the lines slightly left and right to see if they can find a slightly better arrangement that is still fair. They use the rough sketch as a "ceiling" to stop searching once they find something good enough.

Why this matters: This method is fast enough for real-world data (like millions of credit applications) and guarantees that if a fair solution exists, they will find it.

What They Tested (The Experiments)

The authors didn't just talk about theory; they tested their method on real data, including:

German Credit Data: A dataset used to decide who gets a bank loan.
COMPAS Data: A dataset used in the US criminal justice system to predict if someone might re-offend.

The Results:

Fairness Boost: When they used their new "fair sorting" method before training the computer models, the models became much fairer. The unfairness metrics (which measure how differently groups are treated) dropped significantly.
No "Free Lunch" (But a Small Price): Usually, making things fairer makes them less accurate. However, the authors found that with their method, the models stayed almost just as accurate, while becoming much fairer. The "price" of fairness was very small.
Individual Fairness: They also checked if the method treated similar individuals similarly. It did. The method fixed group unfairness without messing up individual fairness.

Summary

Think of this paper as a new sorting machine for data.

Old way: Cut the data into equal piles, accidentally creating unfair bowls.
New way: Use a smart algorithm to cut the data so every bowl has a fair mix of people.
If perfect isn't possible: Use a flexible rule (a little wiggle room) and a fast search method to find the fairest possible arrangement quickly.

The paper proves that by fixing the data before the computer learns from it, we can stop unfairness at the source, making the final decisions (like loan approvals or risk scores) much more just.

Technical Summary: Unbiased Binning for Fairness-aware Attribute Representation

1. Problem Definition

The paper addresses the issue of attribute binning (or bucketization), a common preprocessing step where raw continuous features are discretized into intervals before dataset sharing or model training. While binning is used for privacy preservation and noise reduction, the authors argue that standard binning methods (such as equal-size or equal-frequency binning) can inadvertently introduce or amplify bias against specific demographic groups.

The core problem is formulated as finding a $k$ -binning (partitioning an attribute into $k$ buckets) that satisfies group parity.

Unbiased Binning: A binning is unbiased if the ratio of each demographic group within every bucket equals the global ratio of that group in the entire dataset.
Objective: The primary goal (Problem 1) is to find an unbiased binning that minimizes the deviation from an initial equal-size binning (specifically, minimizing the difference between the maximum and minimum bucket sizes).
$\epsilon$ -Biased Binning: Recognizing that perfect unbiased binning may not exist or may incur a high "price of fairness" (significant deviation from equal sizes), the authors introduce a relaxed problem: finding a binning where the group disparity in any bucket is at most $\epsilon$ .

2. Methodology

The paper proposes a suite of algorithms tailored to different constraints and dataset sizes.

2.1 Exact Solution for Unbiased Binning (Equal-Size)

For the specific case of finding an unbiased binning that minimizes size deviation from an equal-size baseline, the authors develop a Dynamic Programming (DP) approach.

Boundary Candidates: The algorithm first identifies a set of "boundary candidates." An index $i$ is a candidate if the cumulative ratio of a specific group up to $i$ matches the global ratio of that group. The authors prove (Theorem 1) that any optimal unbiased binning must draw its boundaries exclusively from this set.
DP Formulation: The algorithm uses a recursive function $OPT(j, \kappa)$ to partition the first $j$ boundary candidates into $\kappa$ unbiased buckets, tracking the maximum and minimum bucket widths to minimize their difference.
Complexity: The algorithm runs in $O(n \log n + m^2 k)$ time and $O(mk)$ space, where $n$ is the dataset size, $m$ is the number of boundary candidates, and $k$ is the number of buckets.

2.2 Solutions for $\epsilon$ -Biased Binning

Since the boundary candidate concept does not extend to the relaxed $\epsilon$ -biased setting, and the exact DP approach for this setting has quadratic time complexity ( $O(n^2 k)$ ), the authors propose a practically scalable two-step approach:

Divide-and-Conquer (D&C):
- This algorithm recursively partitions the data into two "super buckets" to find a valid $\epsilon$ -biased solution quickly.
- It starts with a midpoint boundary and iteratively expands the search radius until an $\epsilon$ -biased split is found.
- Theorem 4 proves that if a valid $\epsilon$ -biased binning exists, D&C will find it.
- Complexity: $O(n \log k)$ (near-linear), making it highly scalable.
Local Search (LS):
- To find the optimal $\epsilon$ -biased binning (minimizing size deviation), LS uses the solution from D&C as an upper bound.
- It defines a search window around the boundaries of the initial equal-size binning, constrained by the objective value of the D&C solution.
- It exhaustively checks combinations within this window to find a solution with a lower objective value.
- Complexity: $O(n \log n + (w_{dnc})^{k-1})$ , where $w_{dnc}$ is the objective value of the D&C solution. While theoretically exponential in $k$ , the authors note it is efficient in practice as adversarial cases with large $w_{dnc}$ are rare.

3. Key Contributions

Problem Formulation: The paper formally defines the Unbiased Binning problem and the relaxed $\epsilon$ -Biased Binning problem, highlighting the gap in literature regarding fairness at the data preparation stage.
Theoretical Guarantees:
- Proof that optimal unbiased binning boundaries must belong to a specific set of candidates.
- Proof that the D&C algorithm is complete (it finds a solution if one exists).
Algorithmic Suite:
- An exact DP algorithm for equal-size unbiased binning.
- A scalable D&C algorithm for finding valid $\epsilon$ -biased solutions in near-linear time.
- A Local Search algorithm that leverages D&C to find optimal $\epsilon$ -biased solutions efficiently.
General Applicability: Unlike the DP solution for unbiased binning, the D&C and LS algorithms are general and not restricted to equal-size binning; they can act as post-processing steps for any black-box bucketization method.

4. Experimental Results

The authors evaluated their algorithms on real-world datasets (German Credit, COMPAS) and synthetic datasets.

Fairness Impact: Experiments demonstrated that standard fairness-unaware binning introduces measurable bias. Applying $\epsilon$ -biased binning significantly reduced group unfairness metrics (Disparate Impact, Statistical Parity Difference, Equal Opportunity Difference) in downstream models (Logistic Regression and SVM).
Price of Fairness: Reducing bias by half resulted in substantial improvements in fairness metrics while maintaining or slightly improving model accuracy. The "price of fairness" (deviation from equal bucket sizes) was found to be negligible in many cases.
Individual Fairness: The study observed that while group fairness improved significantly, individual fairness (measured by consistency) remained largely stable, suggesting unbiased binning does not harm individual-level fairness.
Scalability: The D&C and LS algorithms demonstrated high efficiency on large datasets, whereas the quadratic-time DP solution was limited to smaller settings.
Integration: Combining $\epsilon$ -biased binning with downstream FairML techniques (Exponentiated Gradient) showed that data preparation can complement model-level interventions, though the marginal gain was smaller when the data was already pre-processed for fairness.

5. Significance and Claims

The paper positions unbiased binning as a necessary, though insufficient, component of a responsible data analytics pipeline.

Complementary Role: The authors explicitly state that unbiased binning does not replace FairML techniques (like training fair models) but serves as a critical preprocessing step to prevent the propagation of bias before model training begins.
Practical Relevance: The work argues that bias introduced during data preparation is a tangible source of downstream unfairness. By addressing this early, practitioners can significantly reduce the burden on downstream fairness interventions.
Modest Claims: The authors are careful to note that while their methods reduce bias and improve fairness metrics, they do not guarantee fairness in all downstream tasks. The effectiveness depends on the specific data distribution and the chosen $\epsilon$ threshold. The paper emphasizes that achieving fair outcomes requires coupling fairness-aware data preparation with fair algorithm development.