Applying standard machine learning approaches for classification can produce unequal results across different demographic groups. When then used in real-world settings, these inequities can have negative societal impacts. This has motivated the development of various approaches to fair classification with machine learning models in recent years. In this paper, we consider the problem of modifying the predictions of a blackbox machine learning classifier in order to achieve fairness in a multiclass setting. To accomplish this, we extend the 'post-processing' approach in Hardt, Price, and Srebro (2016), which focuses on fairness for binary classification, to the setting of fair multiclass classification. We explore when our approach produces both fair and accurate predictions through systematic synthetic experiments and also evaluate discrimination-fairness tradeoffs on several publicly available real-world application datasets. We find that overall, our approach produces minor drops in accuracy and enforces fairness when the number of individuals in the dataset is high relative to the number of classes and protected groups.
As machine learning begins moving into sensitive
predictions tasks, it becomes critical to ensure the fair performance
of prediction models. Naively trained machine learning
systems can replicate biases present in their training data,
resulting in unfair outcomes that can accentuate societal
inequities. For example, machine learning systems have been
discovered to be unfair in predicting time to criminal
recidivism
Copyright © 2022 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). assumption that model parameters are accessible to the algorithm, but there is increasing availability of powerful blackbox models whose internal parameters can be either inaccessible or too costly to train. In this paper, we address the case where outcomes are multiclass and the user has received a pre-trained blackbox model. The main contributions of our work are as follows: • We show how to extend Hardt, Price, and Srebro (2016) to multiclass outcomes. • We demonstrate in what data regimes multiclass postprocessing is likely to produce fair, useful, and accurate results via a set of rigorous synthetic experiments. • We demonstrate the results of our post-processing algorithm on publicly available real-world applications.
produce our experimental results as well as the synthetic and real-world datasets can be found on our github page1.
As in Hardt, Price, and Srebro (2016), we consider the problem of enforcing fairness on a blackbox classifier without changing its internal parameters. This means that our approach only has access to the predicted labels y^i from the blackbox classifier, the true labels yi, and the protected attributes ai for i 2 f1; :::; N g where N is the number of individuals. The goal of our approach is to produce a new set of updated and fair ’adjusted’ predictions yadj that sati isfy a desired fairness criterion. For each of y^i, yi, and ai, we define corresponding random variables Y^ , Y , A. Then, following Hardt, Price, and Srebro (2016) we define the random variable for the adjusted predictions Y adj to be a randomized function of Y^ and A. We extend the approach in Hardt, Price, and Srebro (2016) by allowing multiclass outcomes, such that the sample spaces of Y^ , Y , and Y adj are a collection of discrete and mutually exclusive outcomes C = f1; 2; ::::; jCjg. We in principle allow the sample space of the protected group A, A , to contain any number of discrete values as well: A = f1; 2; :::; jA jg.
1https://github.com/scotthlee/fairness/tree/aaai Linear Program Our approach involves the construction of a linear program over the conditional probabilities of the adjusted predictor P r(Y adj = yadjjY^ = y^; A = a) such that a desired fairness criterion is satisfied by those probabilities. In order to construct the linear program, both the loss and fairness criteria must be linear in terms of the protected attribute conditional probability matrices Pa = P r(Y adjjY^ ; A = a) which have dimensions jCj jCj.
functions which are linear in the group conditional adjusted probabilities Pa. More specifically we consider minimizing expected losses of the form:
E[l(yadj; y)] =
jCj X X X P r(Y adj = i; Y = j; A = a)l(i; j; a) a2A i=1 j6=i
jCj = X X X Wiaj P r(A = a; Y = j) l(i; j; a) a2A i=1 j6=i where Wiaj = P r(Y adj = ijY = j; A = a) are the protected attribute conditional confusion matrices. Under the independence assumption Y adj ? Y jA; Y^ , we can write Wa = PaZa where Za = P r(Y^ jY; A = a), the class conditional confusion matrices of the original blackbox classifier’s predictions. The matrices Za are estimated empirically from the training data (yi, and ai) and blackbox predictions of the model (y^i). Therefore, this formulation of the objective function remains linear in the protected attribute conditional probability matrices, Pa, as is necessary for the linear program. This definition is similar to Hardt, Price, and Srebro (2016) except we let the loss l(i; j; a) also be a function of protected attributes instead of just the true and adjusted labels, which allows controlling the strictness of penalties for errors made for specific protected groups and classes. The most straightforward version of this loss is letting l(yadj; y; a) be the zero-one loss (ignoring the protected attributes) which results in minimizing the sum of the joint probabilities of mismatch between Y adj and Y . We refer to this approach as unweighted loss. Another approach is to set l(yadj; y; a) equal to one over the joint probabilities of the true label and protected attribute 1=P r(Y = y; A = a) (estimated empirically), which we refer to as weighted loss. Intuitively, this option reweights the loss to give rarer protected groups and label combinations equal importance to the optimization which could improve fairness when very low membership minority protected groups exist in the dataset. This option for the objective function can be equivalently minimized by maximizing the diagonals (true detection rates) of the group conditional confusion matrices Wa.
Types of Fairness We consider several versions of multiclass fairness criteria, all of which can be written as a collection of jA j 1 pairwise equalities setting a fairness criterion of interest equal across all groups. Moreover, each of the terms in these equalities can be written as some jCj jCj matrix M a times the adjusted probability matrix Pa, and therefore are linear in the adjusted probabilities as needed for the linear program (see appendix A for the exact form M a takes for the different fairness criteria).
The first definition involves requiring strictly equal performance across protected groups.
Definition 1 (Term-by-Term Multiclass Equality of Odds). A multiclass predictor satisfies term-by-term equality of odds if the protected group conditional confusion matrices Wa are equal across all protected groups:
W1 = W2 = = WjA j (1)
This is a straightforward extension to the multiclass case of equality of odds defined in Hardt, Price, and Srebro (2016). Notice that since this definition requires equality of each off-diagonal term of Wa across all groups, it enforces that not only are errors made at the same overall rate across groups, but also that the rate of specific types of errors are equal. For some practical applications, term-by-term equality of odds is important, such as predicting criminal recidivism times binned into three years, two years, one year, and ”never recommits”. In this case, making the error of predicting 3 years until recidivism when the actual time is 1 year is much worse than predicting 3 years when the actual time is 2. Therefore, it is critical for fairness in this application that the rates of specific types of errors are strictly equal across groups.
Instead of requiring strict equality of off-diagonal terms of Wa we can instead enforce equality across the classwise overall false detection rates F DR, which leads to the next fairness definition: Definition 2 (Classwise Multiclass Equality of Odds). A multiclass predictor satisfies classwise multiclass equality of odds if the diagonals of the protected group conditional confusion matrices and the protected attribute conditional vector of false detection rates are equal across all protected groups: diag(W1) = diag(W2) = FDR1 = FDR2 = = FDRjA j where FDRa = P r(Y adjjY adj 6= Y; A = a).
This version of fairness can ’trade’ better performance for a specific protected group on one off diagonal term in Wa (i.e. lower error probability for that term) for poorer performance of the same group on a different off diagonal term (i.e. higher error probability for another term). Individually each class label has it’s true detection rate, and overall false detection rate set equal across groups. Thus, this type of fairness is ’classwise’.
For some problems it is sufficient to maintain fair true detection rates across classes and allow false detection rates to differ across groups. This is even less restrictive than Definition 2. This may be desirable when, for example, deciding whether an accepted college application should be accepted into a honors program, accepted with scholarship, or regularly accepted. Since all the outcomes are positive, unfairness across false detection rates may not be critical, as long as the true detection rates are fair across groups. This motivates the following fairness criteria: Definition 3 (Multiclass Equality of Opportunity). A multiclass predictor satisfies equality of opportunity if the diagonals of the protected group conditional confusion matrices Wa are equal across all groups: diag(W1) = diag(W2) =
A common and even more relaxed version of fairness
called demographic parity only requires the rate of class
predictions across different groups to be equal
Definition 4 (Multiclass Demographic Parity). A multiclass predictor satisfies demographic parity if the protected group conditional class probabilities are equal across groups: P r(Y adjjA = 1) = P r(Y adjjA = 2) = = P r(Y adjjA = jA j) (4)
Enforcing this version of fairness for certain datasets may
produce effectively unfair outcomes
Note that while the learned adjusted probabilities after running the linear program, Pa are guaranteed to be fair, taking the max value over the learned probabilities when predicting on an individual level will not maintain fairness. In fact, it can occur that taking the max over the adjusted probabilities will just result in identical predictions as those made by the original blackbox classifier. Instead, when predicting the class of an individual, the corresponding learned adjusted probabilities must be sampled from in order to maintain the fairness guarantee.
Most prior work done on post-processing based fairness
approaches focus on binary task prediction.
Several adversarial approaches to multiclass fairness have
been investigated recently; although these are not blackbox
post-processing algorithms.
Multiclass blackbox post-processing techniques are less
studied; although there have been a few new approaches
recently. Notably,
In broader terms, Hossain, Mladenovic, and Shah (2020) unify many of the published methods for learning fair classifiers by showing that equalized odds, equal opportunity, and other common measures of fairness in the binary setting are subsumed by their proposed generalizations of the economic notions of envy-freeness and equitability. They show that these generalizations of fairness apply to the multiclass setting, but post-processing techniques are incapable of achieving them. We show here that this notion is not entirely correct, at least in a narrow sense, and that fairness can be achieved with post-processing techniques in the multiclass setting, so long as the joint distribution P (Y; Y^ ; A) is either fully known or can be reasonably approximated by a large-enough sample of training data.
Synthetic Data To explore the effect of different data regimes and optimization goals on post-adjustment discrimination, we conducted thorough (though by no means exhaustive) synthetic experiments for a 3-class outcome. We constructed synthetic datasets with N = 1; 000 observations for each unique combination of the following data-generating hyperparameters: • The number of unique values for the protected attribute, jA j. We explored setting jA j = 2 or jA j = 3 (see results with jA j = 2 in our github repository) • The amount of class imbalance for the labels Y . For simplicity, we did not allow this to vary across protected groups. • Group balance, or the number and relative size of minority groups compared to majority groups. This varied according to the number of groups but was generally either none, weak, or strong. • Predictive bias as the difference in mean true detection rate, T DR, between the groups. We vary this from mild predictive bias (10 percent difference) to severe bias with the minority group T DR being near chance. The predictive bias is set to always favor the majority group.
This process yielded 117 datasets. For each one, we ran the linear program to adjust the (synthetic) biased blackbox predictions 8 times, once for each unique combination of the objective function and type of fairness, yielding a total of 936 adjustments. After each adjustment, we recorded two broad measures of the fair predictor’s performance: • Triviality, or whether any of the columns in Wa = P r(Y adjjY; A = a) contained all zeroes (i.e., whether any levels of the outcome were no longer predicted). • Discrimination, or the percent change in loss for the adjusted predictor relative to that of the original predictor. For this measure, we examined two specific metrics: global accuracy and the mean of the group-wise T DRs. These are equivalent to 1 minus the post-adjustment loss under the two versions of the objective functions we present above.
To quantify the average effect of each hyperparameter on discrimination, we fit two multivariable linear regression models to the resulting dataset, one for each discrimination metric. Before fitting the models, we converted the categorical hyperparameters (so all but loss) to one-hot variables, and then we set a reference level for each, removing the corresponding column from the design matrix. We then fit the models separately using ordinary least squares (OLS) and calculated confidence intervals (CIs) for the resulting coefficients.
Results Table 1 shows coefficients and 95% confidence intervals for the regression models with jA j = 3. The results highlight several important points: • Predictive bias and class imbalance are the two main drivers of decreases in post-adjustment discrimination, for both accuracy, and T DR. • High group imbalance for the protected attributes lowers post-adjustment discrimination, but only from the perspective of global accuracy–even with 2 strong minorities (3-group scenario), mean T DR only drops by 1.1%. • Relative to the weighted objective, the unweighted objective leads to higher scores for global accuracy but lower scores for mean T DR. This is perhaps unsurprising, but it is worth noting nonetheless. • Despite finding better accuracy solutions, we also found that the unweighted objective leads to trivial solutions far more frequently (30% of the time it was used) than the weighted version of the loss (0.2% of the time it was used). This trend will likely worsen with increasing dimension of either the number of classes or the number of protected groups. • Fairness is generally harder to achieve with 3 protected groups than with 2, since the intercepts are lower for both accuracy and mean T DR. We believe this to be a general consequence of forcing fairness across more groups and expect this trend to continue as the number of groups increases.
Dataset Descriptions To further examine the performance
characteristics of our algorithm, we ran it on several
realworld datasets described below.
1. Drug Usage
For each of these datasets, we obtained a potentiallybiased predictor Y^ by training a random forest on all available informative features (including the protected attribute) to predict the multiclass outcome, and then taking the categories corresponding to the row-wise maxima of the outof-bag decision scores as the set of predicted labels. We then adjusted the predictions with the weighted objective and term-by-term equality of odds fairness constraint and recorded the relative changes in global accuracy and mean T DR as the outcome measures of interest, as with our synthetic experiments.
Exploring the Effect of Finite Sampling Hardt, Price, and Srebro (2016) note that their method will not be effected by finite sample variability as long as the joint distribution P r(Y; Y^ ; A) is known, or at least well-approximated by a large sample. In practical applications, however, the sample at hand may not be large enough to approximate the joint distribution with precision. This problem is exacDataset (N) erbated when the number of observations N is small relative to the number of probabilities learned by the algorithm of which there are jCj jCj jA j total. This difficulty is therefore more severe for our extension in this work where jCj > 2.
In these cases, the adjusted predictor Y adj may have worse classification performance and higher disparity when applied to unseen, out-of-sample data. As a preliminary exploration of this effect, we used 5-fold cross-validation to generate out-of-sample predictions for each of the observations in our real-world datasets. Keeping Y , Y^ , and A fixed, we solved the linear program on 80% of the data and then used the adjusted probabilities Pa to obtain class predictions for the observations in the remaining 20%. As with the predictions obtained from solving the linear program on the full dataset, we measured the changes in accuracy and mean T DR for the cross-validated predictions. Because fairness is not guaranteed when the joint distribution assumption is violated, we also measured post-adjustment fairness. Exploring the Fairness-Discrimination Tradeoff When there are large gaps in a predictor’s performance across groups, i.e., when predictive bias is high, strict fairness may not always be possible or desirable to achieve because of the large amount of randomization required to balance the blackbox classifier’s predictions. To explore the tradeoff between fairness and discrimination, we ran the linear program on each of the real-world datasets once for each of the four kinds of fairness. For each combination of dataset and fairness type, we varied the equality constraints of the linear program–the maximum percent difference allowed between any pairwise comparison of fairness measures between groups–from 0.0 to 1.0 in increments of 0.01, and then plotted the value of the weighted objective at each point as a function of the global measure of fairness corresponding to the fairness type under consideration. To obtain these global measures, we took the maximum of the mean differences across pairs of groups of the following metrics: • W, or the matrix of probabilities P (Y adjjY ), for termby-term equality of odds • Youden’s J index, or T DR+(1 F DR) 1, for classwise equality of odds • T DR for equal opportunity • P (Y adj) for demographic parity
We note here that taking the maximum of the maxima of the pairwise differences would also be a valid and sensible global measure. So that the plots show performance under optimal conditions, we do not use cross-validation to obtain Y adj, i.e., we obtain it by solving the linear program on the entire dataset.
Results Table 2 shows changes in global accuracy and mean T DR after adjustment with the weighted objective and term-by-term conditional fairness constraint for our four datasets, using cross-validation as described above to capture some of the variability that comes with finite sampling. Overall, adjustment lowered both accuracy and mean T DR. Although, for the bar passage, drug usage, and Parkinson’s datasets, the drops were moderate, with average relative changes in both metrics coming in at around 12% and 15%, respectively (without cross-validation, the drops were much smaller at 3% and 4%). For the obesity dataset, the drops are much larger at 47% and 46%, respectively, which are indeed substantial and would likely make the predictor unusable in practical settings. On in-sample data, these drops were both only around 7%, and so we suspect that characteristics of the data, like large class imbalance or small overall sample size, are responsible for the poor performance. Perhaps most importantly, the post-adjustment disparity for all datasets is non-zero, and for three of the datasets actually increases. The bar passage dataset was the only example where the out-of-sample post-adjustment disparity decreased to near zero likely due to it being the largest dataset. This starkly points out the sensitivity of the method to estimating the joint probabilities P r(Y; Y^ ; A), and shows that the approach is unlikely to work in smaller dataset regimes which have a larger combination of classes and protected attributes. Note that for in-sample results, post-adjustment disparity drops completely to 0.0 for all datasets since it is strictly enforced by the linear program in Table 2.
Figure 1 shows fairness-discrimination plots for our 4 datasets with the weighted objective and each of the 4 fairness constraints. Under strict fairness, with inequality set to 0, equalized odds is the hardest to satisfy, showing the largest increase in Brier score. For the drug usage, obesity, and Parkinson’s datasets, discrimination improves approximately linearly as fairness worsens; for the bar passage dataset, discrimination improves to a point, but then worsens as fairness approaches the value for the original, unadjusted predictor Y^ . For all datasets, the total loss of discrimination under strict fairness is relatively small (the biggest drop is around 7.5 percentage points on Brier score), but the random forests’ predictions were only mildly biased to begin with, so we expect this gap to increase for less-fair predictors.
Generally, our post-processing approach to achieving fairness in multiclass settings seems both feasible and efficient given a large enough dataset size. We have shown above that the linear programming technique proposed by Hardt, Price, and Srebro (2016) can be extended to accommodate a theoretically arbitrarily large number of discrete outcomes and levels of a protected attribute. Nonetheless, our synthetic experiments and analyses of real-world datasets show that are a few important considerations for using the approach in practice.
In many cases, the effect of finite sampling may be nonnegligible, especially when the number of observations N is small relative to number of outcomes jCj or the number of protected groups jA j. For example, the obesity dataset with jCj = 5 and N = 1; 490 saw a large relative drop of 46% in mean T DR after adjustment under cross-validation. We also saw this effect extend to fairness, which was not reduced completely to zero on out-of-sample data for any of the realworld datasets. In fact, for the drug usage dataset we found post-adjustment disparity doubled on out-of-sample data.
This last observation raises a concerning point: for some classification problems, the post-adjustment predictions on out-of-sample data may increase disparity rather than lowering it. For the largest of the datasets, the bar passage dataset with N = 22; 406, neither of these issues was a concern. Even under cross-validation, the relative change in T DR was only -8%, and the disparity dropped to near 0 (-95% decrease). Given this, we expect that with a large enough dataset size, our approach will be far more reliable on out-of-sample data. Future work more precisely quantifying the number of training examples needed for reliable out-of-sample fair performance with our approach is needed.
More generally, even when finite sampling variability is
not an issue, not all datasets will lend themselves well to
this kind of post-processing approach. In our synthetic
experiments, we showed that severe class imbalance and
severe predictive bias (predicting at nearly the level of chance
for minority protected groups) lead to large drops in
postadjustment performance on average. In many of the
single experimental runs for synthetic datasets with these
settings, the resulting derived predictor was effectively
useless, either producing trivial results or lowering predictive
performance to near chance (for all groups) for one or
more class outcomes. In these circumstances, it may be
more sensible to enforce fairness through a combination of
pre-processing, in-processing, and post-processing methods,
rather than through a post-processing method alone. Indeed,
This work was supported in part by the HPI Research Center in Machine Learning and Data Science at UC Irvine (P. Putzel), as well as in part by an appointment to the Research Participation Program at the Centers for Disease Control and Prevention, administered by the Oak Ridge Institute for Science and Education (P. Putzel). We would also like to thank Chad Heilig, and Padhraic Smyth for their helpful comments on the approach and paper.
Hardt, M.; Price, E.; and Srebro, N. 2016. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29: 3315–3323.
der to obtain linearity in the protected attribute conditional probability matrices Pa we must find an expression of the form Wa = PaMa:
Wiaj =P r(Y adj = ijY = j; A = a) = X P r(Y adj = j; Y^ = kjY = j; A = a) = X P r(Y adj = ijY = j; A = a; Y^ = k) = X P r(Y adj = ijY^ = k; A = a)
P r(Y^ = kjY = j; A = a)
P r(Y^ = kjY = j; A = a) where Zkaj = P r(Y^ = kjY = j; A = a), and can be estimated empirically using the original predictions of the blackbox classifier. Thus we have Wa = PaZa. Moving from the third to fourth line requires the conditional independence assumption Y adj ? Y jA; Y^ . This assumption is violated in cases where the blackbox predictions are weak, for example completely random, and can intuitively be thought of as requiring that the initial blackbox classifier has reasonable discriminative performance. In other words, relevant information for predicting Y is contained in Y^ .
Multiclass equality of opportunity only requires enforcing equality on the diagonals of Wa, and therefore is linear in Pa as well.
Enforcing the classwise version of multiclass equality of odds requires enforcing equality of opportunity, which is already shown to be linear above, and also enforcing the overall false detection rates to be equal across protected groups. So in order for classwise multiclass equality of odds to be linear, the false detection rates must be linear in Pa, shown below:
F DRca =P r(Y adj = cjY 6= c; A = a) =
P r(Y adj = c; Y 6= c; A = a)
P r(Y 6= c; A = a) = X X P r(Y adj = c; Y = c0; Y^ = j; A = a)
P r(Y 6= c; A = a) = X X Pcaj Zjac0 P r(Y = c0; A = a)
P r(Y 6= c; A = a) Zjac0 P r(Y = c0; A = a)
P r(Y 6= c; A = a) j c06=c j c06=c = X Pcaj X = X Pcaj Vjac
c06=c j j where Vjac = Pc06=c ZjacP0 rP(rY(Y6=c=;Ac0=;Aa=) a) . This allows us to write the protected attribute conditional false detection rates as FDRa = diag(PaVa). As before, Va can be computed from the empirical estimates of Za, and P r(Y = i; A = j).
For multiclass demographic parity we can write: Da =P r(Y adjjA = a) =
1 P r(A = a) k
X P r(Y adj; A = a; Y^ = k) k k =PaP r(Y^ jA = a) = X P r(Y adjjY^ = k; A = a) = X P r(Y adjjY^ = k; A = a)P r(Y^ = kjA = a) P r(Y^ = k; A = a)
P r(A = a) which is again linear in Pa, and the conditional probability vector P r(Y^ jA = a) can be computed emprically. Synthetic Experiment Results with jA j = 2 Hyperparameter Class Balance Predictive Bias
Level
–
Low Medium High
Change in Acc (CI)
Change in TDR (CI)