A Reduction to Binary Approach for Debiasing Multiclass Datasets
Authors: Ibrahim Alabdulmohsin
Jessica Schrouff
Oluwasanmi O Koyejo
Venue: NeurIPS 2022 Accept (2022)
Keywords: Fairness
Classification
Demographic Parity
Deep Learning
Computer Vision
Healthcare

Abstract: We propose a novel reduction-to-binary (R2B) approach that enforces demographic parity for multiclass classification with non-binary sensitive attributes via a reduction to a sequence of binary debiasing tasks. We prove that R2B satisfies optimality and bias guarantees and demonstrate empirically that it can lead to an improvement over two baselines: (1) treating multiclass problems  as multi-label by debiasing labels independently and (2) transforming the features instead of the labels. Surprisingly, we also demonstrate that independent label debiasing yields competitive results in most (but not all) settings. We validate these conclusions on synthetic and real-world datasets from social science, computer vision, and healthcare. 


A Reduction to Binary Approach for Debiasing Multiclass Datasets
Ibrahim Alabdulmohsin
Jessica Schrouff Google Research London, United Kingdom
Google Research Zürich, Switzerland
bbomosiingoogge..... com
schrouf f fwwoogle.....oooooo com
Oluwasanmi Koyejo
Google Research
Mountain View, United States sanmik0google. com
Abstract
We propose novel reduction-to-binatt (R2B) approach that enforces demographic parity for multiclass classification with non-binary sensitive attributes via reduc- tion to sequence of binary debiasing tasks. We prove that R2B satisfies optimality and bias guarantees and demonstrate empirically that it can lead to an improvement over two baselines: (1) treating multiclass problems as multi-label by debiasing labels independently and (2) transforming the features instead of the labels. Sur- prisingly, we also demonstrate that independent label debiasing yields competitive results in most (but not all) settings. We validate these conclusions synthetic and real-world datasets from social science, computer vision, and healthcare.
Introduction
Several studies have demonstrated that predictors are susceptible to unintended bias - for example. deep neural networks (DNNs) amplify spurious correlations in the training data (Hendricks et al.
2018 Bolukbasi et al., 2016 Caliskan et al. 2017 Zhao et al.) 2017] Yang et al.) [020b]] Wang et al.
2020b Stock and Cisse 2018). Moreover,
arise, where the performance of the model for minority groups is disproportionately worse than for the majority (Zhao et al. 2017
disparities
Buolamwini and Gebru 2018 Deuschel al.) 2020). Studies, such as Buolamwini and Gebru 2018
and Wang et al. (2020a), observe that one source of this disparity is that datasets may reflect societal stereotypes, thereby highlighting the importance of debiasing datasets.
Nevertheless, despite the proliferation of research on algorithmic faimess in recent years, very few methods exist that can handle multiclass classification tasks with non-binary sensitive attributes. This gap is particularly noteworthy given that this setting the norm in real-world applications, not the exception. Considering multiclass classification, out of the 70+ image classification datasets in the TensorFlow Dataset catalog (Abadi et al.) 2015). less than 10% are for binary classification problems. Along similar lines, considering non-bi sensitive attributes, the seven protected attributes according to the US Equal Credit Opportunity Act of 1974 (U.S, Government Publishing Office 1974) non-binary, such gender, race, religion, and age.
Two approaches are available to handle such a broad setting, to the best of our knowledge. One option is to view the multiclass problem multi-label and debias every label separately, i.c. transform the labels such that they are uncorrelated with the sensitive attribute, before normalizing the output into a
Now at DeepMind
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1
N.
Y
debias
normalize
0
An illustration of why treating multiclass problems as multi-label may not achieve demo- graphic parity (DP). We assume binary sensitive attribute s and a matrix Y of label conditional probability consisting of three data records (rows) and three classes (columns). Multiclass DP exists Elyls = * Ely s 1], where y E RR3 a vector of probability scores over the three possible classes (see Equation 2 Observe that Y does not satisfy DP because the probability scores are not independent of s. The matrix Y (in middle) debiases every label separately (to see this, average s = 0 rows and compare to the s = 1 row). But, to construct proper multiclass scores, its rows are normalized into probability distributions Y, which reintroduces bias. See Appendix A for details.
Figure I:
valid probability distribution. However, this approach lacks fairness guarantees since normalizing the output can re-introduce bias (see Figure for cartoon illustration). Second, one can debias the instance features instead of the labels irrespective of the number of classes, such as using the demographic parity remover (Feldman et al. 2015), which debiases every feature separately in a vank-preserving manner. However, debiasing the features can be suboptimal when the number of features is large as we demonstrate in Section 4 Note, in particular, that the latter approach requires good estimate of the true cumulative distribution function (CDF) for each feature, but the uniform rate of convergence of the multivariate empirical CDF to the true CDF decreases as the number of features grows (Naaman 2021). We explore the performance of this approach and illustrate in Appendix B how it can fail when using, for example, equal-width binning to estimate the CDFs.
To address this gap in the literature, we propose a reduction- cedtuction-tobinaat to-binary (R2B) approach for debiasing multiclass datasets that can accommodate an arbitrary number of classes and groups and does not require access to the sensitive attribute at prediction time. The proposed algorithm is based on the alternating direction method of the multipliers (ADMM) (Boyd al., 201T). which is a framework for decomposing optimization problems into a sequence of parallel tasks. Using ADMM, we show that the task of debiasing multiclass datasets reduces to a sequence of parallel debiasing jobs on each class separately, along with aggregation step. Each debiasing job can be executed using the randomized threshold optimizer (RTO) algorithm of Albaluuuuloooi and Lucie (202T), which was originally proposed as post-hoc rule for binary classification in this work, we adopt it as a preprocessing method. The overall algorithm inherits the guarantees of ADMM including convergence and optimality. Our empirical results demonstrate that the proposed algorithm can lead to an improvement over the two outlined baselines; i.e. treating multiclass problems as multi-label, and transforming the features instead of the labels.
Surprisingly, we also demonstrate that the baseline multi-label approach in most (but not all) settings despite the potential impact of normalization on bias (cf. Figure D In Appendix A we provide an argument for why this can happen under idealized assumptions.
yields competitive results
Statement of Contribution. This work addresses a gap in the machine learning literature on demographic parity for multiclass classification with non- non-binary sensitive attributes. Our contributions are: (1) we derive method for debiasing multiclass datasets with categorical sensitive attributes of arbitrary cardinality with respect to demographic parity our approach reduces to a sequence of debiasing tasks binary labels, (2) establish theoretical guarantees for the proposed algorithm, (3) we study the impact of the experiment settings (e.g. number of features, number classes, etc) on the debiasing algorithms using synthetic data and validate different debiasing methods real- world datasets from three domains: social science, computer vision, and healthcare, and (4) we evaluate the baseline multi-label approach in debiasing multiclass datasets and demonstrate that it yields competitive results in most (but not all) settings.
2 Related Work
In the binary classification setting, several algorithms have been proposed for mitigating bias in machine learning. These are often classified into three groups depending on which step in the machine learning pipeline the debiasing effort takes place. First, there are preprocessing methods that are applied prior to training, such as by learning a fair representation (Zemel et al., 2013 Lum and

---

Johndrow 2016 Bolukbasi et al., 2016 Calmon et al. 2017 Madras et al. 2018) or re-weighting
training examples (Kamiran and Calders 2012). One example of a preprocessing method that transforms the labels is the optimized score transformation (OST) method (Wei et al., 2019) whereas the DP remover method of afeledaan et al.] (2015) transforms the features. Feature debiasing has the advantage of not depending on the labels and can therefore be applied in any task setting.
Second, in- in-processing methods intervene during training, such as by adjusting the gradient updates (Zhagg et al. 2018) or by adding explicit constraints into the optimization problem; e.g. (Zalar al. 2019). In Agarwal et al. (2018). it is shown that many fairnsss criteria can be enforced during training via reduction approach to cost-sensitive classification rules. Our proposed algorithm for the multiclass setting also reduces to a sequence of debiasing rounds. However, every round decomposes into multiple parallel debiasing jobs for each label separately (i.e. using algorithms for debiasing binary labels) and we operate the preprocessing setting. Reduction methods, in which solutions to simple problems are reused to solve complex tasks, are not uncommon in machine learning. Besides Agarwal et al. (2018), other examples include the MetaCost method (Domingos) 1999). error correcting codes (Dietterich and Bakiri 1994), boosting (Schapire and Freund 2014). conditional probability estimation (Beygelzimer et al., 2009), ranking (Balcan et al. 2007). and relating reinforcement learning to classification (Langlord and Zadrozny 2005).
Third, many post-processe processoossing methods have been proposed in the literature (Corbett- Davies et al. 2017: Menon and Williamson, 2018: Celis et al. [019) Kamiran et al., 2012] Hardt et al. [2016] Wei et al. 2019 AAladdulmossin and Lucic [022]. One recent example is the randomized threshold optimizer (RTO) of (lladdulmohsin and Lucic
[ucic] (2021), which can provably approximate the optimal unbiased predictor (i.e. it is statistically consistent) and can be solved efficiently via stochastic gradient descent (SGD). Our ADMM based approach for debiasing multi-class datasets utilizes RTO to debias every label separately before aggregating results.
To our knowledge, two methods have been developed for multiclass classifications. First is the algorithm Denis al. (202T), which assumes that the sensitive attribute is binary, whereas the sensitive attribute can be non- non-binary in our setting. Second, Yang et al. (2020a) propose both in- processing and post-proot post-processing procedures; the latter of which requires access to the sensitive attribute at prediction time and cannot be directly applied as a preprocessing method on discrete labels.
Advantages of R2B. The proposed ADMM-based reduce-to-binary (R2B) algorithm is a pre- processing method. This offers three immediate advantages. First, it is agnostic to the choice of the training algorithm; unlike, for example, in-processing methods that are often designed with a specific model and a choice of training method in mind, Second, R2B does not require access to the sensitive attribute at prediction time, which is a critical advantage over post-processing methods (Zafar et al., 2019). Third, R2B reduces the debiasing task to a sequence of rounds of debiasing the labels, not training classifiers. The computational overhead in our approach is often negligible compared to in-processing methods that provide reduction approach to sequence of classification rules, such as in Agarwal et al.) (2018), in which the entire model is trained several times. Unlike the multi-lahel approach, R2B is guaranteed to debias the dataset up to the prescribed bias tolerance level. In addition, R2B performs better than other baselines, such as preprocessing the features instead of the labels. Importantly, can be applied in the multiclass setting with a non-binary sensitive attribute.
3 Reduction to Binary Method
Notation. We reserve boldface letters for random variables (e.g. x), small letters for instances (e.g.
c). capital letters for matrices (e.g. X), and calligraphic typeface for sets (e.g. the instance space A'). f X + R is multivariate function, we write fx( : X' + E for the k-th component of f. We denote [n] = {0, I.................... n 1} and reserve T7e (2(x) for the Bayes regressor: (z) = p(y k|x = x). We assume that the sensitive attribute is known training time and it has a finite range. We denote the instance space X, the dataset D : [D] = N, the target set ) {0, 1,.., L - 1} and the sensitive attribute g : X + S where S RR.. We write X's for the portioning of X induced by S: i.e. Xs- (Xy.... XR-1) ) the set of groups/subpopulltions where
م X,. We will occasionally write x; for the i-th instance in the training dataset. We also denote I E R." for the vector of all I's and RM for the vector of all zeros. both cases, the dimension is implicit and should be inferred with case from the context. Finally, |||||| p is the Frobenius norm of the matrix X.
3

---

3.1 Multiclass Demographic Parity
Definition. Before deriving the reduction-to-binaae (R2B) method, we first describe how demo- graphic parity is extended to the multiclass setting. In the binary classification setting, demographic parity measures the difference in mean outcomes across groups. More precisely, let ʃ
[0. 1] be a binary predictor that outputs a probability score f(z) ply 11x= = z). Then, f is said to
satisfy demographic parity if the following holds (Dwork ct al. 2012 Zafar et al. 2017 Mehrabi
ct al. 2019 Alabdulmohsin and Lucic 2021):
max Ex(f(x) g(x) s] min Ex g(x) s) c. .ES
(1)
SES
where g : X' + S is the sensitive attribute. A crowd-soureing study found that DP matches with the
common perception of bias (Srivastava al. 2019 In the multiclass setting, let fa : X + [0, 1] be
the probability score assigned to the class it E y given the instance I E X and let f X - [0. 1
In this work, we follow the definition used in Denis et al. 2021 and say that s satisfies e demographic parity if:
(r..,....T.-I((( (r.-1(x))² be the multivariate function [(x) (Jo(z), [x(),, ....,
DP()) = max kEY
max [xx ( (xx) s] min (x(fa(x) s(x) = =s]} Se. SES
(2)
#ES
Hence, predictors with small demographic parity have similar mean outcomes across all groups S with respect to all of the predicted targets. We take the maximum here instead of the average to avoid pitfalls that arise when some classes are more preferred than others, which is analogous to the "fairness gerrymandering" phenomenon, where predictors may exhibit small bias across the intersection of groups on average, but not at the worst-case intersection (Kearns et al., 2018). Here, instead of disparities across groups, we highlight worst-case disparities across classes. In Appendix we discuss some scaling effects of the number of classes on the definition of multiclass DP.
3.2 Derivation of the Ceatuctionto-Binarr (R2B) Algorithm
In the binary classification setting where y = {0, 1). a natural measure of performance is the 0-1 misclassification error rate. Minimizing the expected 0-1 error is equivalent to maximizing the linear functional (x) (x) 1)] (Alabdulmohsin and Lucie 2021 where 9 are the new debiased labels and 7/1 (z) = p = 1|x = x) is the Bayes regressor. Here, the minimization with respect to the debiased labels ÿ X - R Hence, if access to the Bayes regressor is available at training time, one can usually compute j(s) that minimizes the expected 0-1 loss subject to the desired fairness constraints by solving convex optimization problem; ef. (Menon and Williamson 2018 Alabdulmohsin and Lucic 2021
Celis et al. 2019 Wei et al., 2019).
Unfortunately, such advantage no longer holds in the multiclass setting because the top-1 accuracy is often insufficient. For top-k accuracy, however, the squared loss is statistically consistent (Yang and Koyejo 2020). Hence, we propose to minimize the & distance [[(ū(x) x(x))² between the debiased predictions and the original labels. Throughout the sequel, y(z) X' + R gives the probability scores assigned to the different classes for the instance X, which can be degenerate distribution as is often the case. The objective function [ū(()) - y(x)?)] can be written as:
(A/2) Ex 11x()) Exl0(x) v(x) Constant,
where x= = 1. Rewriting the objective function in the form 3 provides an alternative interpretation: by minimizing the objective in (3). one seeks a solution that minimizes the regularized top- error. This holds because the probability of correctly classifying
example z equals ((x) y(x) when yn (z) = ply = k|xx = 2). Regularization, however, discourages extreme predictions. We fix À ==1 since it corresponds to minimizing the squared loss, although R2B can handle any >> 0.
The task of debiasing labels in a dataset can hence be cast into the convex optimization problem:
Σ { (1/2) (102)) 11) - 0(x)² v(x)"v(z)} }.
min
(4)
RR4
RED
s.t.
max kEY
{ mmx Ex (x) s| min (x SES
lg(x)= =s] Se
SES
Yx E D: 1s [zx) = ^ ((x) 2 0.

---

Pscudocode of the reduction-to-binat (R2B) algorithm for debiasing multiclass datasets with categorical sensitive attributes of arbitrary cardinality.
Algorithm 1:
Inputs: (1) Step size > O; (2) Demographic parity tolerance level 2 0; (3) Label matrix Y E R V where Yu = p(y for the i-th training example; (4) Sensitive attribute E [R] where g(i) is the sensitive class the i-th training example.
Output: Debiased probability scores Y E R demographic parity; i.c. solution to Equation
Y
0A 1 that minimize ||Y Y
|| subject
Training: Set Y (0) Y and ~ (())) = 0 E R
NxL
Repeat until stopping criterion (cf. Section 3.3
Debias in Paraliel:
Set p(t) = Y + T - I(o) Let f( E R. be the k-th column of F(1), Solve the following
debiasing task for each class separately (c.g. using RTO (Alabdulmohsin and Lucie 202T)):
arg min SS
(1 r)+l)\2100+1 ok fk
max *ES
N [vx (i) o(i) s) min .
RIEIN] (i) 9(1) s) Se
2. Aggregate Results:
(a) Set (( " (i): unnormalized score assigned class E y the i-th training example.
(b) Normalize probability scores using:
z (((+1) + v +00 - (1(0111 (0066))+0000 +1(0)) 1- -1.
(c) Update: U(+1) 10 + H(+1) - z(t!)
Return y= Z.
Instead of solving this optimization problem directly, we re- re-expssss it into more convenient form:
min $xX+R4
Σ
(1/2))11(00 (())T + Ir(x(1)))-
(5)
RED
s.t.
max kEY
max Ex (x) (x(x) s] - min Ex (x) g(x) = =s] se sES
SES
Yo D ((z) =(x)
< (x)) < 1.
We introduced dummy constraint ((x) and replaced 1sT ((x) 1 with a term T=(((x)) in the objective function where:
0, oo, otherwise.
())x=)
[=(ū(z))
(6)
Clearly, the optimization problem 55 is equivalent the original optimization problem
Algorithm I presents pseudocode for the proposed reduction- to-bbnaary (R2B) method for solving the optimization problem in (5). At a high-level, the algorithm decomposes the debiasing task into sequence of rounds. each round, the probability scores assigned different classes are debiased normalized. The next
independently. This produces new set of scores, denoted H()) that step is to normalize them so that they sum to one. The set of normalized probability scores is given by z() After that, the objective function is altered slightly and the process is repeated. We prove that Algorithm @ the optimal solution (5) and discuss suitable stopping criteria in Section 3.3
3.3 Analysis of the Algorithm
Proposition 1 (Optimality). Algorithm terminates with an optimal solution ( which the debiased probability scores assigned to the i-th example are given by the i-th row of the matrix Y.
Stopping Criteria. The simplest stopping criterion to use in Algorithm | is the number of ADMM rounds. Boyd et al. (20TT) observes that 50-100 rounds are often sufficient, which we also observe to be true in our experiments (see Figure 3). Alternatively, one may use the sum of the "primal" and
5

---

"dual residuals". In Algorithm 1 the optimality conditions of ADMM (Boyd et al. 2011) I reduce to the
following conditions z = H ()) and z((+1) = ( Hence, we may define 6p = 2 (0)) ||F
and 6, = || - 2 and stop when 6p + 6, are below a prescribed threshold. In our implementation, we follow the first approach and set the maximum number of ADMM rounds to 100.
Bias Guarantee. For our next result, we write [x)( for the average value of a function f on the training examples, and write E[f(x)] for the expectation of over the true distribution of instances.
Proposition 2 (Bound on bias). Let Ip- be the probability simplex in R-_ and F be class of functions from X to Pt, such that the set {Ju If E F} has a Rademacher complexity d. Suppose that all training examples (x, Y.S.))) S) E 'D are drawn i..dd. and are debiased using Algorithm D with bias level e 2 O. Let h(s) : X + pl. be the debiased labels. Let f E -Fbe be the final classifier. Then,
where no = minge(R) [[[[(x)= = 8} x E D is the size of the smallest group in the training dataset, I, = |
with a probability of at least 1 - 8, we have: DP(J) S + 2T + 2d +
-
V
log 2LR
2no
is the number of classes, R = |S| is the number of groups, and suPkey, =E[Rg] [B[[x(x) (x(x)
s| - (x) g = .||. where both expectations are measured on the training dataset.
Proposition provides a formal justification to the preprocessing approach: states that if the training labels are debiased using Algorithm [] then classifier trained on the debiased data is guaranteed to exhibit small bias in the future as long as four conditions are satisfied: (1) the level of bias in the training data is small; i.. < 1 in Algorithm II (2) the classifier fits the training examples well; i.c. I < 1. (3) the complexity of the classifier is not too large (does not memorize examples); i.e. d < 1, and (4) there exists large number of training examples for each group in S; i.e. ng log LRR
4 Experiments
We compare R2B against the two baselines: (1) treating multiclass datasets as multi-label, and (2) transforming the features. In the multi-label approach, we use two recent algorithms for debiasing binary labels: optimized score transformation (OST) (Wei et al., 2019) and RTO (Alabdulmohsin and Lucic 2021) with y = 0.01 and p = E[ys] (default) values. After that, the scores are normalized to sum to one. Note that 7 < 1 in the RTO algorithm corresponds approximately rule, hence we refer to it as hard hard-threshold optimizer (HTO). In the second approach, we apply the demographic parity remover (DPR) method of Feldman et al. (2015), which debiases features. In the latter case, we use equal-mass binning when estimating the cumulative density function (see Appendix B). All three baselines can be motivated via provable optimality guarantees (Wei et al.) 2019; Alabdulmohsin and Lucic |021 Feldman et al. 2015). We also include for comparison training without debiasing the data, which we denote as BL We note that existing multiclass fairness approaches such as Yang et al. 2020a) cannot be applied for pre-processing as they require either probability estimates or weighted classifiers. We highlight in boldface the method with the best accuracy among the set of methods that achieve the smallest bias within the margin of error.
hard-thresholdin
In R2B, on the other hand, we use a step size of 0.5 in Algorithm I aand a maximum number of 100 ADMM rounds. We also report results when a single round of R2B is used, which we denoted as R2B, Except for the healthcare dataset whose splits are fixed, we split data at random into 25% % for test and 75% for training. We debias the dataset prior to training and measure performance (e.g. accuracy and DP) on the test split. All methods use the same splits. We re-run every experiment with ten different random seeds and report both the averages and 99% confidence intervals.
4.1 Synthetic Dataset
We begin our analysis with synthetic data. In this dataset, let I. be the number of classes and d be the number of features. We use a mixture of T. Gaussians whose means are sampled from (0, o²T) with x² 1/d and y = [Z]. For the sensitive attribute, we set it equal to [y = 0) with probability 1/2: otherwise, it is chosen uniformly at random from the set (0. ....... 4]: i.e. |S| = 5. Hence, bias
is introduced into the dataset. The classifiers are k-NN with k = 5 and Random Forest (RF) with
"Source code is publicly available at: httpa/////oo/ooooooooooor/oerrrr cree/master/eeee mm1 mmebiiaserdrrrrreeeee

---

classesmé
Closee-11
Classes-64
Cassess
Denrog sprte Party
10
15
0.6
1.0
1000
2010
Exemples Class
Exemples Class
Cless
Class
2.0
100
1.0
Tieets 20
-Peatrree 100
1.0
>Pealu 1000
The Accurneyy
04
0.3
Dd
0.5
0.9
08
0.0
0.0
057
171
0.4
0.
0.
04
0.4
1220
F25
02
1020
2005
4050
1020
2002
4030
02
1020
2000
4030
0.2
1020
2000
4000
02
1920
4010
02
1020
2002
4000
Examples per Class
Exomples per Cless
Exammpes per Class
# EExamples per Class
Examppes per Cless
EExamppes per Cless
Figure 2: Top two displays the multiclass demographic parity (DP) as measured using 2 for the synthetic dataset with varying numbers of classes, features, and training examples using INN as classifier (see Appendix[C full figures). The reduction-to-binary (R2B) method provides a stronger fairness guarantee than the competing methods. The bottom row shows the prediction accuracy.
Canseenn
instures
sestures 100
Festres-11 1.
Festurts-
Feotuess 10
Fegtures- 100
Demosggghe grehe Bwrty
0.2
00.00
0,30
6.200
0:25
1.2
10F
30F 521
10
227
10'
Figure 3: The level of bias in the training data is plotted as measured by (2) vs. the number of ADMM rounds for different levels of bias tolerance E {0, 0.025, 0.05, 0.075, 0.10} (see legend) using the kNN classifier (see full figures in Appendix In general, 50-100 rounds of ADMM in R2B are sufficient to reach convergence in agreement with prior observations (Boyd et al. 2011)
maximum depth 5, both implemented using Scikit-Learn (Pedregosa et al. 2011). We vary the number of classes in (4, 16, 64), the number of features in [10, 100), and the number of training examples per class in {1000, 2000, 40003. We set the bias tolerance e to zero in all experiments since, otherwise, these methods provide incomparable mechanisms for controlling bias. Figure 2 displays the results for k-NN and Appendix contains the full figures.
As shown in Figure 2 R2B provides stronger fairness guarantee than the other competing methods. In addition, we observe that debiasing the features performs poorly when the number of features is large. As mentioned earlier, one possible explanation is that as the number of features grows, the rate of convergence of the multivariate empirical cumulative distribution function (EDF) to the true cumulative distribution function (CDF) decreases (Naaman) 2021). However, debiasing the features in Feldman et al. 2015) relies on having a correct estimate of the CDF since it matches quantiles.
Moreover, we observe that the multi-label approach (i.c. OST, HTO, and R2B0) can also fail in several cases. As illustrated in the cartoon example of Figure [ this is because normalization impacts bias. In one experiment, for example, the level of DP in the training labels is reduced to less than 0.01 after debiasing labels separately using OST but bias increases to over 0.22 following normalization.
In Figure 3 we also plot the level of DP in the training labels as function of the number of ADMM rounds R2B for five different levels of bias tolerance e E (0, 0.025, 0.05, 0.075, 0.10). We observe that R2B converges in about 50 ADMM iterations, which is consistent with earlier observations in the literature (Boyd et al. (01T). In addition, when the level of bias in the data smaller than e, the algorithm does not introduce any additional bias as expected.
7

---

Table 1: A summary of the performance results (99% confidence intervals) for the five debiasing algorithms on the Adult Income benchmark dataset, where the goal is to predict the education level. For each of the two classifiers Random Forest (RF) and k-NN, we either use the original data (p = 0) or inject bias (p = 0.5) as described in Section 4.2 First column is the bias in the data. The debiasing methods are the baseline (BL), DP remover (DPR) (Feldman al. 2015), optimized score transformation (OST) (Wei et al. 2019): randomized threshold optimizer with = 0.01 (HTO)
AAlabuulmohsin and Lucic 2021) R2Bg and R2B (our method).
Criterion
P
Leamer
DATA
OST
HIO
R2B (ours)
0.0
RP
5.0
3.8 + .2
1.5 + 3
3.7
2.9 +
2.8 3
2.2 + .2
196]
KNN
5.0
4.7 +
3.0
4.5
3.2 2
3.1 =
2.1 .
0.5
RF
48.0
22.8 1
9.5
1.7 .3
2.2 1
21 1 .2
1.0 + .2
KNN
48.0
26.5 1
23.3 13.3000 .6
2.9 .4
3.4
3.3
1.1
42.6 +
41.0
42.6
42.5
42.6
ACC [%}
KNN
35.5 1: 5
33.4 33
35.3 1 55
35.2
35.2 .5
35.5 - .5
RF
42.0 +
39.0 .7
34.1 4
33.9
34.0
34.0
KNN
31.9
- 5
313
30.2 4
29.1
29.6
31.1 =
4.2
Real-world Applications
Next, we validate R2B on applications from three domains: (1) social science, (2) computer vision, and (3) healthcare. Experiments involving neural networks are executed on Tensor Processing Units.
Adult Income dataset. The first dataset is the Adult Income dataset (Kohavi 1996). In our case, predict the education level of each individual from the remaining attributes. There are 16 classes in this dataset and 29 features, such as marital status, age, and occupation. The total number of examples (both training and test) is 48,842. The sensitive attribute sex and only includes two categories ( ('Male', 'Female'). We compare the debiasing methods in [able[]for both the Random Forest (RF) and K-NN classifiers (top two rows). Besides the original dataset, we also introduce bias and class imbalance into the data (both training and test) and compare methods: with probability {0, 1). This
p 0.5, the label y {0, (.... 15} increases bias in the original labels from about 0.05 to around 0,48 and introduces class imbalance as w The performance of each debiasing method in this dataset is shown in Table [ bottom two rows. In most cases, R2B provides a stronger bias guarantee compared to the other methods. Appendix F provides similar performance results for Top-K accuracy.
is set to be equal to the sensitive attribute
COCO dataset. The second dataset we use is the COCO dataset (Lin et al. 2014). It contains 80 classes corresponding to the objects in each image, such as chairs, cars, and handbags. We transform this multi-label problem into multiclass problem using soft labels: y to be equal to the fraction of the objects that belong to each class in each image. The soft label approach corresponds formally the task of predicting the distribution of objects seen in the image or, equivalently, the task of predicting the class of an object chosen uniformly at random from the corresponding image. We follow the procedure of (Wang et al. (020a) in inferring the sensitive attribute based on the image caption: we use images that contain either the word "woman" or the word "man" " in their captions but not both. The total number of examples is 22,616. Because the task here is to predict the distribution of classes seen in the image, we define accuracy in terms of the total variation distance between probability distributions. Specifically, let ý be the model's 's prediction, then acc(ý. y) = 1 [1/2)][ı y/11. Note that 0 < (c < 1. See Appendix for for further details about the training procedure. Besides the original dataset, we also introduce bias and class imbalance with p = 0.5 as described previously. Results are provided in Table 2 As shown in the table, both R2B and the multi-label methods perform much better than transforming the features (DPR), which is consistent with the earlier observations on synthetic data. Moreover, R2B performs better overall.
set the target label
Dermatology. In this task, we are interested in predicting 27 skin conditions (26 plus an 'other' label representing the long tail) from images of the pathology of interest, the patient's 's age and sex")
'The level of demographic parity in the original data can be different from the baseline results, because the baseline model may not predict the original labels. For instance, when p = 0.5, noise is added the labels to make them biased but such noise can ignored by the model. "Sex corresponds clinician self' recorded sex and only includes two categories ( ('Male", 'Female")
8

---

Table 2: A summary of the performance results (99% confidence intervals) for the five debiasing algorithms on the COCO benchmark dataset with soft labels. See Section 4.2 for details. Similar to Table 1
experiment with both the original dataset (p 0) and with introduced bias (p 0.5).
DATA
BL
DPR
OST
HTO
R2Be
R2B (ours)
.3
d:
+
DP [%]]
0.5
62.9
4.0 6
52.3 3.4
0.7 +
1.3
1.0
1.1 #
0.0
28.0 2.0
39.8 =
32.8
40.6
ACC 1981
0.5
43.8 +
50.1 + 2.7
42.5 +: .2
39.6 1 .2
43.8 +
48.1 ..4
Table A summary of performance results on a Dermatology dataset (Liu et al. 2020), where the goal is to predict the clinical condition from images of the pathology. DP is 0.09 in the original data.
Metric
BL.
DPR
OST
ИTO
R2Bg
R2B (ours)
DP [S]
4.8
5.0 +:0+:0
Top- [8]]
58.6
0.5
58.3 +
0.7
58.5 1 0.5
48.9 0.9
58.3 1 0.7
59.1 4 0.6
Top-2 [8]]
79.1 0.7
78.6
79.3 + 0.6
67.5
79.0
Top-3 188]
89.1 0.1
86.8 0.6
88.8 + 0.6
0.8
87.2 0.6
87.2 + 0.6
The dataset is subset of the one used Liu et al. (2020) and consists of de-identified retrospective adult cases from teledermatology service serving 17 sites from 2 states in the United States. It split according to condition prevalence for training (n = 12, 024), tuning for hyper-parameterss (n = 1, 925) and hold-out testing (n 1, 1242).. We train deep learning model to predict skin conditions as multiclass task, as per the architecture described in Liu et al. (2020); Roy et al. (2021). For debiasinn. we fit R2B the tune split and assess the model performance. Following Liu et al. (2020), we report the top-1, 1, top-2, and top-3 accuracy on the test split. Table reports DP on the test split well. For ease, we bucket age according to [18,30), [30,45), [45, 65) and [65,90) for debiasing. We note that the number cases per condition and per intersection of the attributes might be low, is common in data-scarce domains such healthcare. Results presented in Table
Summary of Findings. The other baselines in all of the experiments and outperforms the other methods in some cases, such as in the synthetic data, the Adult Income dataset, and COCO. In addition, the multi-label approach using OST and R2B,
to-binary (R2B) approach performs at least as well as the
to offer competitive results in most (but not all) settings. In Appendix A we provide an argument for why this might happen under idcalized assumptions. However, it is worth emphasizing that the multi-label approach not guaranteed debias datasets successfully as illustrated earlier in Figure | and demonstrated using synthetic (Figure 2 and real (Table data. On other other hand, R2B offers strong guarantees (cf. Propositions and
Discussion and Limitations
In this paper, we derive reduction approach for debiasing multiclass datasets according to demo- graphic parity (DP). The algorithm reduces the overall task into sequence of parallel debiasing jobs
Table 4: A summary of the observed error parities for the five debiasing algorithms on all of the classification tasks, which is defined be the difference between the maximum and minimum losses conditioned on each group. In the original datasets (i.e. = 0), we do not observe an increase in parity when the training data is debiased to account for DP. However, error parity seems to increase when introducing large bias to such data (i.e. with p = 0.5).
Task
BL
DPR
OST
IITO
R2B,
R2B (ours)
Adult (RF)
0.7 0.7000 0.1
0.7 + 0.4
1.0
0.8 0.84:..
1.0
0.7 + 0.3
Adult (KNN)
0.7
0.3
0.7 0.2
0.3
0.8
0.8 0.3
0.7 1 0.3
COCO
4.4
5.7
4.0
5.1
4.2
5.1 0.5
Demn
5.6 1.9
5.1 0.8
1.9
5.7 5.7.1..
6.1
5.9 0.9119 2.1
Adult (RF)
7.6
31.3
49.9 0.2
50.1 0.3
49.9
49.8 10.8+00
Adult (KNN)
2.0
1.2
12.5 1.8...8 0.8
8.1 8.1.0.33
7.8 7.8...0.
31.3
0.5
COCO
23.1
2.0
21.9
17.1 0.4
22.7 2..
38.7 0.8

---

on binary labels. Due to this reduction, the algorithm scales well to large datasets with several classes. We verify empirically on both synthetic and real-world datasets that outperforms other baselines.
Nevertheless, is worth emphasizing that "fairness" is a societal concept and should not be reduced to statistical metrics, such as DP (Dixon et al. 2018 Selbst al. 2019). As such, the claims of this paper hold for the narrow technical definition of DP, not for fairness in its broader sense.
One limitation in R2B is that it accommodates DP but cannot accommodate error parity metrics, such as equalized odds. This is because it operates in the pre-processing setting, where prediction "errors" are yet undefined. In particular, for anti-causal predictive tasks (Schölkopf al., (012) as the case in dermatology (Castro and Glocker 2020), Veitch et al. (2021) suggest that equalized real-world settings, do
fairness constraint. Nevertheless, not observe an increase in error parity when the training data is debiased to account for DP as shown in Table 4 except when bias is introduced into the data (i.e. with p 0.5)). Mitigating DP can reduce accuracy when the labels are correlated with the sensitive attribute as has been noted in several works; e.g. (Menon and Williamson 2018: Zhao and Gordon| 2019). Finally, it accommodates categorical sensitive attributes only, not continuous. While the majority of protected attributes are indeed categorical and continuous attributes can be converted into categorical features by binning their values (e.g. age in the dermatology example), handling continuous sensitive attributes without resorting to binning remains challenge. We leave such questions for future work.
odds would be causally-groundee
Acknowledgements
The authors would like to acknowledge and thank Yuan Liu and Alex Brown at Google Health Al for their support with the dermatology application, and thank Kathy Meier- Hells--ell and Lucas Dixon from Google Responsible Al team for their feedback on earlier drafts of this manuscript.
References
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viégas, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., and Zheng, X. (2015). TensorFlow: Large-scale machine learning on heterogeneous systems. Software available from tensorftow.org.
Agarwal, A., Beygelzimer. A., Dudik, M., Langford, J., and Wallach, H. (2018). A reductions approach fair classification. In JCML.
Alabdulmohsin, I. and Lucic, M. (2021). A near optimal algorithm for debiasing trained machine learning models. In NeurIPS.
Balcan, M.-F., Bansal, N., Beygelzimer, A., Coppersmith, D., Langford, J., and Sorkin, G. B. (2007). Robust reductions from ranking to classification. In COLT.
Beygelzimer, A., Langford, J., Lifshits, Y., Sorkin, G., and Strehl, A. L. (2009). Conditional probability tree estimation analysis and algorithms. In UAI.
Bolukbasi, T., Chang, K.-W., Zou, J. Y., Saligrama, V., and Kalai, A. T. (2016). Man is to computer programmer as woman is homemaker? debiasing word embeddings. In NeurIPS.
Bousquet, O., Boucheron, S., and Lugosi, G. (2003). Introduction to statistical learning theory. Springer.
Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn.. 3(1):1-122.
Boyd, S. and Vandenberghe, L. (2004). Convex optimization. Cambridge University Press.
10

---

Buolamwini, J. and Gebru, T. (2018). Gender shades: Intersectional accuracy disparities in commer- cial gender classification. In FAccT.
Caliskan, A., Bryson, J. J., and Narayanan, A. (2017). Semantics derived automatically from language corpora contain human-like biases. Science, 356(6334).
Calmon, F., Wei, D., Vinzamuri, B., Ramamurthy, K. N., and Varshney, K. R. (2017). Optimized pre-processing for discrimination prevention. In NeurIPS.
Castro, Daniel C.. W. I. and Glocker, B. (2020). Causality matters in medical imaging, Nature Communications, 11.
Celis, L. E., Huang, L.,, Keswani, V., and Vishnoi, N. K. (2019). Classification with fairness constraints: A meta-algorithm with provable guarantees. In FAceT.
Corbett-Davies S., Pierson, E.,, Feller, A., Goel, S.,, and Huq, A. (2017). Algorithmic decision making and the cost of fairness. In SIGKDD.
Deng, J., Dong, W. Socher, R., Li, L.-J,, Li, K., and Fei-Fei, L. (2009). Imagenet: A large-scale hierarchical image database. In CVPR.
Denis, C., Elie, R., Hebiri, M., and Hu, E. (2021). Fairness guarantee multi-class classification. arXiv preprint arXiv: 109.11999233
Deuschel, J., Finzel, B., and Rieger, (2020). Uncovering the bias in facial expressions. arXiv preprint ar11v:2011.1131.
Dietterich, T. G. and Bakiri, G. (1994). Solving multiclass learning problems via error-coreeting output codes. Journal of artificial intelligence research, 2:263-286.
Dixon, L., Li, J., Sorensen, Thain, N., and Vasserman, L. (2018). Measuring and mitigating unintended bias in text classification. In Conference on AI, Ethics, and Society.
Domingos, P. (1999). Metacost: A general method for making classifiers cost-sensitive. In SIGKDD, pages 155-164.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. (2012). Fairness through awareness. In Innovations in Theoretical Computer Science.
Feldman. M., Friedler, S. A.. Moeller, J., Scheidegger, C., and Venkatasubramanian,, S. (2015).
Certifying and removing disparate impact. In SIGKDD, pages 259-268.
Freedman, D. and Diaconis, P. (1981). On the histogram density estimator: L2 theory. Zeitschrift für Wahrccheinicckketssheeeeii und Verwandte Gebiete, pages 453-476.
Hardt, M., Price, E., Srebro, N., et al. (2016). Equality of opportunity in supervised learning. In NeurIPS.
He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In CVPR.
Hendricks, L. A., Burns, K. Saenko, K., Darrell, T., and Rohrbach, A. (2018). Women also snowboard: Overcoming bias captioning models. In ECCV.
Kamiran, F. and Calders, Т. (2012). Data preprocessing techniques for classification without discrim- ination. Knowledge and Information Systems.
Kamiran, F., Karim, A., and Zhang, X. (2012). Decision theory for discrimination-awaree caassaaii classification. In ICDM.
Kearns, M., Neel, S., Roth, A., and Wu, Z. S. (2018). Preventing fairness gerrymandering: Auditing and learning for subgroup faimesss In ICML, pages 2564 2572.
Kohavi, R. (1996). Scaling up the accuracy of naive-Bayes classifiers; A decision-tree hybrid. In SIGKDD.

---

Langford, J. and Zadrozny, B. (2005). Relating reinforcement learning performance to classification performance. In ICML, pages 473-480.
Lin, T., Maire, M., Belongie, J., Bourdev, L. D., Girshick, R. B., Hays, J., Perona, P., Ramanan, D., Doll' r. P., and Zitnick, C. L. (2014), Microsoft COCO: common objects in context. CoRR, abs/1405.0311
Liu, Y., Jain, A., Eng. C., Way, D. H., Lee, K., Bui, P., Kanada, K., de Oliveira Marinho, G., Gallegos, J., Gabriele, S., Gupta, V., Singh, N., Natarajan, V., Hofmann- Welnnn-oo,,, R., Corrado, G. S., Peng, L. H., Webster, D. R., Ai, D., Huang, S. J., Liu, Y., Dunn, R. C.. and Coz, D. (2020). A deep learning system for differential diagnosis of skin diseases. Nat. Med., 26(6):900- -088
Lum, K. and Johndrow, J. (2016). A statistical framework for fair predictive algorithms. arXiv preprint wxXiv:1610.0807..
Madras, D., Creager, E., Pitassi, T., and Zemel, R. (2018). Learning adversarially fair and transferable representations. ICML..
Massart, (2007). Concentration inequalities and model selection. Springer.
Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., and Galstyan, A. (2019). survey on bias and fairness in machine learning, arXiv preprint arXiv:1908.0966.
Menon, A. K. and Williamson, R. C. (2018). The cost of fairness in binary classification. In FAceT.
Naaman, M. (2021). On the tight constant in the multivariate dvorensky-Kieffrrwwoofvvi inequality. Statistics & Probability Letters, 173.
Nishihara, R., Lessard, L., Recht, B., Packard, A., and Jordan, M. (2015). A general analysis of the convergence of admm. In ICML, pages 343-352.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. (2011). Scikit-learn: Machine learning Python. Journal of Machine Learning Research, 12.
Roelofs, R., Cain, N., Shlens, J., and Mozer, M. C. (2020). Mitigating bias in calibration error estimation. arXiv preprint arXiv:2012.08665.
Roy, A. G., Ren, Azizi, S., Loh, A., Natarajan, V., Mustafa, B., Pawlowski, N., Freyberg, Liu, Y., Beaver, 7., Vo, N., Bui, P., Winter, S., MacWilliams, P., Corrado, G. S., Telang, U., Liu, Y., Cemgil, T., Karthikesalingam, A., Lakshminarayanan, B., and Winkens, J. (2021). Does your dermatology classifier know what it doesn't know? detecting the Long-Tail of unseen conditions.
Schapire, R. and Freund, Y. (2014). Boosting: Foundations and Algorithms. MIT Press.
Schölkopf, B., Janzing, D., Peters, J., Sgouritsa, E., Zhang. K., and Mooij, (2012). On causal and anticausal learning. In ICML, pages 459-466.
Selbst, A. D., Boyd, D., Friedler, S. A., Venkatasubrammnnian, S., and Vertesi, J. (2019). Faimeess and abstraction in sociotechnical systems. FAccT.
Srivastava, M., Hcidari, H., and Krause, A. (2019). Mathematical notions vs. human perception of fairnsss: A descriptive approach to faimess for machine learning. arXiv preprint arXiv:
Stock, and Cisse, M. (2018). Convnets and imagenet beyond accuracy: Understanding mistakes and uncovering biases. ECCV.
U.S. Government Publishing Office (1974). THE Equal Credit Opportunity Act.
Veitch, V., D' Amour, A., Yadlowsky, S., and Eisenstein, J. (2021). Counterfactual invariance to spurious correlations: Why and how pass stress tests.
Wang, A., Narayanan, A., and Russakovsky, (2020a). Revise: A tool for measuring and mitigating bias in visual datasets. In ECCV.
12

---

Wang, Z., Qinami, K., Karakozis, I. C., Genova, K., Nair, P., Hata, K., and Russakovsky, O. (2020b). Towards fairness in visual recognition: Effective strategies for bias mitigation. In CVPR.
Wei, D., Ramamurthy, K. N., and Calmon, F. d. (2019). Optimized score transformation for fair classification. arXiv preprint urXiv:/906.00000
Yang. F., Cisse, M., and Koyejo, S. (2020a). Fairness with overlapping groups. arXiv preprint arXiv:2006. 13485.
Yang. and Koyejo, S. (2020). On the consistency of top-k surrogate losses. II H. D. and Singh, A., editors, ICMI., volume 119 of Proceedings of Machine Learning Research, pages 10727-10735. PMLR.
Yang. K., Qinami, K., Fei-Fei, L., Deng, J., and Russakovsky, O. (2020b). Towards fairer datasets: Filtering and balancing the distribution of the people subtree in the imagenet hierarchy. In FAccT.
Zafar, M. B., Valera, I., Gomez Rodriguez, M., and Gummadi, K. P. (2017). Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In International Conference World Wide Web.
7 M. B., Valera, I., Gomez-Rodrigue, M., and Gummadi, K. P. (2019). Fairness Constraints: A Flexible Approach for Fair Classification. Journal of Machine Learning Research.
Zemel, R., Wu, Y., Swersky, K., Pitassi, T., and Dwork, C. (2013). Learning fair representations. In ICML.
Zhang, B. H., Lemoine, B., and Mitchell, M. (2018). Mitigating unwanted biases with adversarial learning. Conference on AI, Ethics, and Society.
Zhao, H. and Gordon, G. (2019). Inherent tradeoffs in learning fair representations. In NeurIPS.
Zhao, J., Wang, T., Yatskar, M., Ordonez, V., and Chang, K.-W. (2017). Men also like shopping: Re- ducing gender bias amplification using corpus-level constraints. arXiv preprint arXiv: arXiv: 170::0077055
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 5
(c) Did you discuss any potential negative societal impacts your work? [Yes] We provide an algorithm for debiasing datasets. One potential negative impact is to view the narrow technical definition of demographic parity as a definition of fairness in its broader sense.
We caution against this in Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Please see Appendices.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] Code has been made publicly available. Both the Adult and COCO datasets are publicly available. The dermatology dataset is not available the public.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Instructions for reproducing experimental results are provided in the main paper (see Section 4 and the supplementary materials (see Appendix H))
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] We report error bars on all results.
13

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section [ Experiments involving deep neural networks are executed on TPUs. The training protocol is described in the paper and in Appendix H (for COCO dataset).
4. If you using existing assets (e-g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite software packages (c.g. Scikit-Learn and TensforFlow), datasets (e.g. ImageNet, Dermatology,
COCO, Adult), and cite the models
(e.g. ResNets).
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either the supplemental material or as URL? [Yes] We release an implementation of the proposed algorithm.
(d) Did you discuss whether and how consent obtained from people whose data you're 're using/curating? [No] For the dermatology dataset, this has been discussed in the original paper (Liu et al. 2020).
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] The dermatology dataset consists of de- indentified retrospective adult cases described in Section 2
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board
(IRB) approvals, if applicable? [Yes] We discuss Ethics approvals of the dermatology
data in Appendix []
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "taAVWLpDr4", "reviewer": "Reviewer_DJH3", "summary": "This paper proposes a reduction-to-binary method, which enforce demographic parity for multi-class classification with non-binary sensitive attributes. It mainly exploits the alternating direction method of the multipliers (ADMM) to decompose the task of debiasing multi-class datasets into a sequence of parallel debiasing jobs. Experiments are implemented on several datasets to demonstrate its effectiveness.", "questions": "Please see the weakness part for the novelty, fairness, and experimental comparison in the above comments.  ", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths：\nThis paper introduces a pre-processing method for multi-class classification with non-binary sensitive attributes with ADMM and experiments are performed to show the performance. In addition, the algorithm are analyzed from different theoretical perspectives.\n\nWeaknesses:\nFirst, the novelty is relatively limited. It mainly extends RTO [1] with ADMM and apply it as a pre-processing method. For example, [2] also exploits ADMM to optimize score transformation for fair classification.  \n  \nSecond, this method is pre-processing method for debiasing multiclass datasets with categorical sensitive attributes. However, some problems are ignored. On the one hand, since the method builds upon the narrow definition of demographic parity, it may not ensure the true fairness [3]. Though this has been discussed in Sec.5 of the paper, fairness is an important motivation for such debiasing work as illustrated in the introduction part. More criterion should be considered. On the other hand, the proposed R2B method does not consider the influences of noisy labels when performing label debiasing.\n\nFurther, the experiments are not enough and training settings are relatively simple. For COCO dataset, linear classifiers with softmax activations and cross entropy loss are trained using pretrained features. The total number of examples is 22,616. Such way of training is difficult to demonstrate the effectivity of the proposed method in large-scale datasets when training from scratch is required. As a pre-processing method, more representative models on large-scale datasets should be re-trained to verify the performance.   \n\n[1] Alabdulmohsin I M, Lucic M. A near-optimal algorithm for debiasing trained machine learning models[J]. Advances in Neural Information Processing Systems, 2021, 34: 8072-8084.\n\n[2] Wei D, Ramamurthy K N, Calmon F P. Optimized score transformation for fair classification[J]. Proceedings of Machine Learning Research, 2020, 108.\n\n[3] Wang Z, Qinami K, Karakozis I C, et al. Towards fairness in visual recognition: Effective strategies for bias mitigation[C]//Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2020: 8919-8928.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "t1u70Ss8is", "reviewer": "Reviewer_tbyd", "summary": "This paper tries to debias multi-classification models. The proposed method builds on top of the alternating direction method of the multipliers algorithm. It decomposes debiasing multi-classification into a sequence of parallel jobs on each class, followed with an aggregation step. The paper includes experimental results on both synthetic and real-world datasets and found the resultspromising. ", "questions": "Discussed in \"Strengths and Weakness\" section.", "limitations": "The paper does emphasize that \"fairness\" is a societal concept and can not be reduced to statistical metrics. It also discussed the limitations of the proposed method and gives reasonable explanations and potential solutions.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. A new way of debiasing multi-classification models.\n2. The paper provides both theoretical guarantees and empirical results.\n3. The paper explores both classic machine learning models and deep learning models.\n\n\nWeakness:\n1. While we do see that demographic parity is reduced by R2B(the proposed method), the test accuracy also drops, especially when the number of classes is relatively small. This is captured in Figure 2 and Table 1.\n2. As pointed out by the paper itself, error parity increases when the dataset has large bias. \n3. The paper may benefit from having analysis on how the proposed method perform differently when models are different (from different families of machine learning models).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mhlkd38pP8I", "reviewer": "Reviewer_jQyz", "summary": "The paper proposed a novel reduction-to-binary (R2B) approach that enforces demographic parity for multiclass classification with non-binary sensitive attributes via a reduction to a sequence of binary debiasing tasks. It proved that R2B satisfies optimality and bias guarantees. It also demonstrated empirically that it can lead to improvements over baselines and produced competitive results. The authors validated the method on synthetic and real-world datasets from social science, computer vision, and healthcare.", "questions": "Overall, this is a good paper with solid experiments and analysis, and I can see its potential for the broader field.\n\nPlease see the weakness part for detailed questions. I paste here some key questions for summary\n\n1. No fine-grained results provided for R2B on where the improvements mainly come from.\n\n2. The datasets evaluated were relatively small-scale. \n\n3. No runtime / training cost analysis. \n4. The overall performance was comparable to other algorithms, but no clear advantage. ", "limitations": "The authors have adequately addressed the limitations in the last section of the main paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths \n\n1. The paper studies an interesting yet important topic, namely multiclass classification with non-binary sensitive attributes.\n\n2. The paper proposed a debiasing method for multiclass datasets with categorical sensitive attributes. It further established theoretical guarantees for the proposed algorithm.\n\n3. The evaluation was done on real-world datasets from social science, computer vision, and healthcare domains. The performance is notable compared to competing baselines.\n\n4. The writing is clear and easy to follow. The paper is well structured.\n\n### Weaknesses\n1. Where does the improvement come from? As the authors noted, potential bias and class imbalance could cause existing algorithms fail for underrepresented data. Yet, no fine-grained results provided for R2B on where the improvements mainly come from. For example, for classes with fewer observations, does it produce more balanced / fair predictions? If so, why is it the case?\n\n2. The datasets evaluated were relatively small-scale. The number of samples and data diversity seem to be limited for the datasets tested. What would be the case when you scale the dataset size up? Without validation on larger datasets, the performance may not be justifiable.\n\n3. No runtime / training cost analysis. What is the additional cost (both time and memory) when introduing the debias procedure?\n\n4. The overall performance was comparable to other algorithms, but no clear advantage. Some of the numbers seem to lie in the noise region. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "kGUBT1bMKN4", "reviewer": "Reviewer_EEH6", "summary": "The paper considers the fairness of the multi-class classification task. The authors reduce a multi-class debasing problem to a set of parallel binary classification debasing tasks for each class label k, followed by an aggregation step. For the binary debias task, they leverage existing method e.g., RTO, to achieve the debiased goal for each label. They apply their debias technique in the pre-processing step: with the \"debiased\" labels obtained from their R2B method, they compare with some other pre-processing methods in terms of the DP fairness goal and model accuracy. ", "questions": "1. As indicated above, is there a way to verify why the normalization method in Alg.1 will not re-introduce bias (or reduce that)?\n2. For the comparison of the results, e.g, in Fig.2, the DP is in $10^{-3}$ order, then how much difference can we say between your method with other baselines? Is such a difference significant? \n3. For the comparison with other baselines, e.g., with the HTO, what if you did not set the $\\gamma$ as the hard-thresholding but follow Alabudulmohsin 2021 to do the grid search? Will your R2B still outperform it?\n4. Others:\n    - The y-axis in Fig.3 is not correct. The maximum value should be 0.1 (or *1/10 for other values).\n    - It will be great if you can introduce a concept before using it in the paper. For example, in the introduction, the authors mentioned \"label debiasing\" or \"debiased label\" without defining it, which makes it hard to follow.\n - The $**2$ in $l_2$ distance in #149 seems in the wrong position. \n - #155: do you mean correctly classifying or misclassifying? ", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Existing literature about fairness usually focuses on the binary classification task, this paper extends this to the multi-class scenario which is a more realistic setting and provides a pre-processing methodology to do this. With their reduction, the algorithm can scale to large datasets. \n\nWhile their motivation is important and realistic, it seems to me, the authors just reduce the multiclass problem to a set of binary cases and do an aggregation without further verifying why such an aggregation method works. The aggregation method seems to matter a lot in their method as indicated in the introduction, the normalization could re-introduce bias. However the authors do not mention how their choice can address this re-introducing issue. Also, for the experimental results, it is hard for readers to distinguish between a DP score 5.1 vs 5.0 (e.g., Table 3). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HOoZwz7rzzD", "reviewer": "Reviewer_qxof", "summary": "The authors introduced a method to extend the current debiasing methods to the multi-class classification problems. The core idea is to formulate the loss function as an L2 regression loss constraint by traditional DP.  Then the optimization problem is solved by ADMM algorithm efficiently; each iteration is only required to solve a binary classification subproblem. The optimality and bound of bias are analyzed. Finally, experiments on both synthetic and commonly used real datasets are conducted to show the reduction in bias while accuracy is sustained. \n", "questions": "The first limitation of this paper seems to be the loss function itself. Authors choose L2 regression loss instead of the more commonly used cross-entropy loss. This assumption seems critical for applying ADMM. \n\nFurthermore, I doubt the correctness of the optimality theorem in the paper. It is true that the whole function is strongly convex as a function of yhat, but we are really optimizing over the model parameters in yhat. Even if we consider yhat as free variables, they are constrained by nonconvex set C = DP <= \\epsilon. \n\nThere are a few places that are confusing to me:\n\nL140 “Minimizing the expected 0-1 error is equivalent to minimizing the linear…”: I think it should be maximizing the linear functional rather than minimizing.\n\nL148: “the squared loss is statistically consistent”, I checked (Yang et al. 2020), but I can’t find a relevant claim that squared loss is statistically consistent.\n\nL155: “probability of misclassifying an example x equals y^(x)T y(x)”: this should be correctly classifying the example x?\n\nFinally, the format of the tables is ambiguous: the boldface is applied to some (but not all) best methods. For example, in Table 2, only R2B column is highlighted, but other methods are better in DP or accuracy. Similar issue is found in Table 3. In Table 4 there is no boldface in the whole table. So I think efforts are needed to make it more consistent. \n", "limitations": "Please see the section above.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well organized and smooth to read in general, although I found some unclear places (listed in the next section). The idea of transforming the multi-class problem into multiple binary problems is novel and elegant to me. The empirical evaluations are sufficient.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept