Unbiased Binning for Fairness-aware Attribute Representation

Discretizing raw features into bucketized attributes is a common step before sharing a dataset. However, this process can inadvertently introduce bias and amplify unfairness in downstream tasks.

In this paper, we address this issue by formulating the unbiased binning problem, which seeks bucketized attributes that satisfy group parity. We develop an e!cient dynamic programming algorithm to solve this problem for equal-size binning. In practice, however, an unbiased binning may incur a high price of fairness or may not exist at all, particularly when group distributions di"er substantially. To accommodate settings in which small deviations from perfect parity are acceptable, we introduce 𝐿-biased binning, which restricts group disparities across buckets to at most 𝐿. We #rst present a dynamic programming algorithm, DP, that computes the optimal solution in quadratic time. Although polynomial, DP does not scale to large datasets. To address this limitation, we propose a practically scalable algorithm based on a local search strategy (LS).

A key component of LS is a divide-and-conquer algorithm (D&C) that #nds a solution in near-linear time. We prove that D&C always returns a valid solution whenever one exists. The LS algorithm then performs a local search, using the D&C solution as an upper bound, to #nd the optimal solution. Our LS and D&C algorithms are general and are not restricted to equal-size binning.

To complement our theoretical analysis, we conduct extensive experiments on real-world and synthetic datasets. Besides con#rming the e!ciency of the algorithms, our experiments verify that while fairness-unaware binning can generate biased attribute representations, this bias can be signi#cantly reduced with a negligible price of fairness.