Penalizing Unfairness in Binary Classification

Introduction

As machine learning-based methods have become increasingly prevalent in decision-making processes that crucially affect people’s lives, accuracy is no longer the sole measure of a learning algorithm’s success. In settings such as loan approvals (Steel & Angwin 2010), policing (Goel et al. 2016), targeted advertisement (Sweeney 2013), college admissions, or criminal risk assessments (Angwin et al. 2016), algorithmic fairness must be carefully taken into account in order to ensure the absence of discrimination (Barocas & Selbst 2016; Crawford 2016).

Concerns of unfairness in classification were at the center of a recent media stir regarding the potential hazards of computer algorithms for risk assessment in the criminal justice system (Angwin et al. 2016; Liptak 2017). The COMPAS system (Inc. 2012), developed by Northpointe, is a proprietary algorithm, widely used in the United States for risk assessment and recidivism prediction. At the center of the controversy was an investigative report by Angwin et al. (Angwin et al. 2016), who observed that although the COMPAS algorithm demonstrated similar accuracy on whites and blacks when used to label individuals as either high or low risk for recidivism, the direction of errors made on whites versus blacks was very different. More specifically, the rate of individuals who were classified using the COMPAS algorithm to be “high risk” but who did not actually re-offend was almost twice as high for black individuals as for whites; among those who were classified as “low risk” and did actually re-offend, the rate was significantly higher for whites than it was for blacks (Larson et al. 2016).

At least theoretically, fairness could necessarily come at a very high cost to accuracy, but it is possible that the tension between fairness and accuracy is far less stark on real-world data. Despite this, to date, there have been only a handful of techniques for ensuring fairness in classification that have been proposed and tested empirically.

Motivated by this pressing need, we propose a new, easy-to-use, general-purpose technique for mitigating unfairness in classification settings. The approach deepens our understanding of how fairness considerations can be incorporated directly into the learning process, as opposed to imposing fairness post hoc on an arbitrary, unfair, learned classifier. We validate the ability of our approach to achieve both fairness and high accuracy, implementing and testing it on multiple datasets pertaining to recidivism, credit, loan defaults, and law school admissions. We find that our approach empirically outperforms existing approaches, and that fairness is often achievable at nearly no cost to accuracy.

Related Work

Approaches to algorithmic fairness generally fall into two categories—situations where no ground truth is known (or perhaps the notion of ground truth is not well-defined), and settings where the algorithm has access to labeled examples on which to learn (perhaps from historical examples). In situations without access to ground truth, typical approaches to fairness include changing the data (e.g., to prevent the learner from having direct/indirect access to attributes that are considered sensitive) (Zemel et al. 2013; Feldman et al. 2015; Bolukbasi et al. 2016), or adapting the classifier (e.g., to treat similar people similarly) (Dwork et al. 2012; Joseph et al. 2016; Kamishima et al. 2011). When ground truth information is available, we wish to prevent situations where the algorithm errs in favor of one group within the population. In the specific context of criminal risk assessments, Berk et al. (Berk et al. 2017) give a thorough comparison of various fairness notions.

Both Kleinberg et al. (Kleinberg et al. 2017) and Chouldechova (Chouldechova 2017) show that fair classification entails unavoidable trade-offs, and that there are a number of reasonable desiderata (calibration, matching false positive rates (FPR) across populations, and matching false negative rates (FNR) across populations), that cannot, in general, be achieved simultaneously (Angwin & Larson 2016). Follow-up work by Pleiss et al. (Pleiss et al. 2017) shows that even when calibration is compatible with a generalization of FPR- and FNR-matching, any algorithm achieving both must is no better than randomizing a percentage of the predictions of an existing classifier; further investigation of calibration as a criterion for fairness can be found in Hébert-Johnson et al. (Hébert-Johnson et al. 2017).

There are also computational challenges to fairness. Woodworth et al. (Woodworth et al. 2017) show that even in the restricted case of learning linear predictors, assuming a convex loss function, and demanding that only the sign of the predictor needs to be non-discriminatory, the problem of matching FPR and FNR requires exponential time to solve in the worst case. They also point out that for many distributions and hypothesis classes, there may not exist a non-constant, deterministic, perfectly fair predictor.

Despite these theoretical challenges, learning fair classifiers remains an important, practical problem that must be addressed on real data—decisions must be taken, and trade-offs must be made. To this end, there have been a number of recent specific technical proposals for achieving algorithmic fairness. The fairness objective we study in this paper, that of matching false positive and false negative rates across populations in classification tasks, has in particular received substantial attention in the literature.

Hardt et al. (Hardt et al. 2016) propose a post hoc approach for learning such a fair classifier, probabilistically flipping some of the decisions of a given (unfair) trained classifier in order to match FPR and FNR across populations. Their approach yields a predictor which is not restricted to any hypothesis class, and that is a (possibly randomized) function of the original (non-fair) learned predictor and of the sensitive attribute (population membership). Although this is an elegant and appealing idea, the Hardt et al. approach only guarantees optimality for a strictly convex loss function and an unconstrained hypothesis class (Woodworth et al. 2017). Follow-up work of Woodworth et al. (Woodworth et al. 2017), shows that, in many cases, any such post hoc approach might result in a highly sub-optimal classifier. As Woodworth et al. conclude, post-processing an unfair classifier is sometimes insufficient to achieve the best possible combination of fairness and accuracy; rather, in some cases, fairness considerations should be actively integrated into the learning process.

Zafar et al. (Zafar et al. 2017) give one such approach to integrating FPR and FNR matching into learning. Their algorithm relaxes the (non-convex) fairness constraints into proxy conditions, each in the form of a convex-concave (or, difference of convex) function. They then heuristically solve (Shen et al. 2016) the resulting optimization problem for a convex loss function.

The approach of the present work is to incorporate a penalty for unfairness into the learning objective. This is inspired in part by Kamishima et al. (Kamishima et al. 2011), who designed an unfairness penalty term based on a very different notion of fairness, referred to in their paper as indirect prejudice, which restricts the amount of mutual information between the prediction and the sensitive attribute.

The present work introduces new penalty terms, designed to enforce matching of FPR and FNR. Our approach is easy to use, and general in the sense it can be plugged in and utilized in a range of learning settings concerning classification problems. The accuracy-fairness trade-offs of our approach empirically compare favorably with the algorithms of Zafar et al. (Zafar et al. 2017) and Hardt et al. (Hardt et al. 2016) on the COMPAS dataset, and we further validate the performance of our approach on several additional datasets from other fields of interest.

Fair Learning

In classical machine learning theory, when considering a classification task, the objective is typically to minimize a loss function that reflects the errors the chosen classifier makes on a fresh sample of data. One might naturally adjust the loss function to penalize differently for different sorts of errors (false positive or false negative, in the binary case), however, a priori, the classical approach does not do anything to control the distribution of errors across different sub-populations.

2 Preliminaries

Then, given a data set $S$ and a classifier $\hat{Y}$, writing $\hat{y}^{i}=\hat{Y}(x^{i})$, we can formally define the false positive rate (FPR) and false negative rate (FNR) of $\hat{Y}$ on $S$ as follows:

Given a value $a\in\{0,1\}$ of the protected attribute $A$, we denote by $FPR_{A=a}(\hat{Y})$, $FNR_{A=a}(\hat{Y})$ the false positive and false negative rates of $\hat{Y}$ on $\{(x,y)\in S:x_{1}=a\}$.

Penalizing Unfairness

Our approach to learning a fair classifier integrates fairness considerations into the learning process by penalizing unfairness, and is inspired by the concept of regularization. Typically in regularization, the added penalty term is a function only of the learned hypothesis, penalizing for complexity in the model, aiming to prevent overfitting. Here, we introduce a new type of penalty, which is not only hypothesis-dependent, but is also data-dependent, and which is set at a group level rather at an individual level. As our goal is to learn a classifier that matches FPR and FNR rates across populations, we define two types of penalizers that aim at minimizing the differences between the FPR and FNR (respectively) across sub-groups in the population, for the trained classifier. Our penalization scheme minimizes the differences between the empirical FPR and FNR as evaluated on the relevant sub-groups in the training set $S$, and relies on statistical guarantees proven in Woodworth et al. (Woodworth et al. 2017) to yield fairness on the true underlying distribution $\mathcal{D}$, for a sufficiently large dataset drawn i.i.d. from $\mathcal{D}$.

The first penalizer we propose is based on relaxing the 0-1 loss, to instead consider the margin from the decision boundary. We will penalize the difference in the average distance from the decision boundary across different values of the protected attribute A.

We define the Absolute Value Difference (AVD) FPR penalty term to be

The FNR penalty term is defined analogously. We note that this penalizer is convex in $\theta$. In order for the penalizer to also be differentiable at 0, we define a second variant (using the same notation for $\overline{x}$), which we term the Squared Difference (SD) penalizer:

Again, we define the FNR penalizer analogously.

The Importance of Incorporating Fairness in the Learning Phase

We briefly illustrate a simple example (based on one in Woodworth et al. (Woodworth et al. 2017)) which demonstrates the potential impact of incorporating fairness considerations into the learning process, rather than post-processing a learned classifier for fairness.

In the example, each data point lies in $X=(X_{1},X_{2})=\{0,1\}^{2}$ and has two features—$X_{1}=A$ is the protected attribute, and $X_{2}$ is a non-protected attribute—and a label in $Y=\{0,1\}$. Given $\epsilon\in(0,\frac{1}{4})$, we define a distribution $\mathcal{D}_{\epsilon}$ over labelled examples as follows:

Note that $\mathcal{D}_{\epsilon}$ is defined s.t. $A\perp X_{2}|Y$.

Assume the hypothesis class $\mathcal{H}$ is unconstrained, and contains all of the (possibly randomized) functions $h:X\rightarrow\{0,1\}$. Note that classifying according to $X_{2}$ alone is a completely fair classifier (the FPR and FNR are both equal across $A=0$ and $A=1$) that achieves 0-1 loss $2\epsilon$, and thus provides an upper bound on

The Bayes optimal predictor with respect to the 0-1 loss is

which, in our case, gives $\hat{h}(X)=A$. This classifier has 0-1 loss of only $\epsilon$. However, in terms of fairness, it performs as badly as possible, as it induces the maximal possible differences in both the FPR and FNR rates across the two sub-populations in the distribution.

Incorporating Fairness in the Learning Process

Absent fairness considerations, the best separating halfspace (in terms of the 0-1 loss) would provide us with classifications identical (on the given distribution) to those of the Bayes optimal classifier, and thus would have 0-1 loss of $\epsilon$, while being maximally unfair. However, as shown in Figure 1, using our proposed method of penalization (as described in detail in Section 6) yields a halfspace which induces equivalent performance on $\mathcal{D}_{\epsilon}$ as classifying according to $X_{2}$, resulting in 0-1 loss of $2\epsilon$ and perfect fairness.

Case Study: Fair Classification Using Logistic Regression

We wish to solve the following optimization problem:

For convenience, we will denote the objective in (1) by $\text{Objective}(\theta;S,d_{1},d_{2})$, and the objective in the proxy problem (2) by $\text{Proxy}(\theta;S,c_{1},c_{2},q)$. As the proxy is easy to solve using standard methods, we use it when optimizing, and then shift back to the original problem for estimating the quality of our results.

Experiments

We validate our approach using multiple datasets containing real-life data from the fields of criminal risk assessment, credit, lending, and college admissions. In each of the datasets we select a binary feature and treat it as the protected attribute (e.g., race or gender), which is the feature we require our trained classifier to behave fairly upon. Our proposed method performs well on all of these datasets, succeeding in removing unfairness almost entirely, at a very modest price in terms of accuracy.

Our method For the purpose of comparison with Zafar et al. (Zafar et al. 2017) and Hardt et al. (Hardt et al. 2016) on the COMPAS data, we use a parameter $c$ to induce three possible combinations of weights on the FPR and FNR penalization terms: $c=c_{1}$ and $c_{2}=0$; $c_{1}=0$ and $c=c_{2}$; and $c=c_{1}=c_{2}$. For the other three datasets, we consider only $c=c_{1}=c_{2}$. The reason for varying the values of $c$ in the training phase is since we shifted to a proxy problem, in which we rely on the distance from the decision boundary rather the actual classifications. It is possible, of course, that even better results are attainable using our scheme with other combinations of $c_{1},c_{2}$, and $q$. To explore the accuracy/fairness trade-off curve for the relaxed optimization problem (2), we train for different values of $c$, starting at $c=0$ (which is just standard logistic regression), and growing gradually.

Given a dataset $Q$ and fixing a $d_{1},d_{2}\in\{0,1\}$ of interest, we use the following training scheme:

Split $Q$ at random into training set $S$ and test set $T$.

For each $c$, perform cross-validation on $S$ to select the corresponding best value $q_{c}$ for the regularization parameter.

For each $(c,q_{c})$, let $\theta_{c}=\argmin\limits_{\theta}\text{Proxy}(\theta;S,c,c,q_{c})$.

Select $\theta^{*}\in\argmin\limits_{\theta_{c}}\text{Objective}(\theta_{c};S,d_{1},d_{2})$.

Evaluate performance using $\theta^{*}$ on test set $T$.

We report the average of five such runs, each with a fresh training-test split.

We solve the relaxed convex optimization problem using the CVXPY solver. Due to stability issues with large training sets, we use a train/test split of 30-70 on the larger datasets, rather than 70-30 as on the COMPAS dataset The code implementing our method can be found at https://github.com/jjgold012/lab-project-fairness.

We briefly describe the other algorithmic approaches to which we compare: Zafar et al. (Zafar et al. 2017) performs optimization by considering a proxy for the bias: the covariance between the samples’ sensitive attributes and the signed distance between the feature vectors of misclassified users and the classifier decision boundary. Zafar et al. Baseline (Zafar et al. 2017) tries to enforce equal FP/FN rates on the different groups by introducing different penalties for misclassified data points with different sensitive attribute values during the training phase. Hardt et al. (Hardt et al. 2016) performs post-processing on a standard trained (unfair) logistic regressor, picking different decision thresholds for different groups, and possibly adding randomization.

2 Experimental Results

In what follows, we use the following notation, given a trained classifier $\hat{Y}$:

The values $FPR_{A=0}(\hat{Y})$, $FPR_{A=1}(\hat{Y})$, $FNR_{A=0}(\hat{Y})$, $FNR_{A=1}(\hat{Y})$ are reported as evaluated on the test set.

The Correctional Offender Management Profiling for Alternative Sanctions (COMPAS) records from Broward County, Florida 2013-2014, made available online by ProPublica, are perhaps the best-studied data in the context of fairness. The goal in this scenario is to successfully predict recidivism within two years, based on features such as age, gender, race, number of prior offenses, and charge degree. The dataset contains 5,278 samples. The protected attribute in this scenario is race, where $A$ indicates black or white. We filtered the dataset using the same features as Zafar et al. (Zafar et al. 2017), to allow for comparison.

In Table 1, we compare the performance of our approach with that of three other techniques from the literature. Each method was trained based on logistic regression. As a basis for comparison, we also present the performance of vanilla logistic regression, absent fairness considerations, with the regularization parameter selected via cross-validation. Zafar et al. (Zafar et al. 2017) do not incorporate regularization in any of the approaches they report. Results for Zafar et al., Zafar et al. baseline, and Hardt et al. appear here as reported in Zafar et al. (Zafar et al. 2017). Our method selects the classifier based on the training set only and reports its performance over the test set. Results for the three other approaches, reported by Zafar et al. (Zafar et al. 2017), are based on tuning parameters after seeing the trade-off curve over the test set, and reporting according to the best selection of these parameters.

We find that the vanilla logistic regressor (absent fairness considerations) results in significant unfairness, as $\mathbf{D_{FPR}}=0.20$, and $\mathbf{D_{FNR}}=0.30$. The overall accuracy of this classifier measured on the test set was $0.672$. Zafar et al. (Zafar et al. 2017) report a slightly different baseline of: Accuracy = 0.668, $\mathbf{D_{FPR}}=0.18$, $\mathbf{D_{FNR}}=0.30$. Our SD penalization approach empirically achieves approximately the same accuracy as the Zafar et al. (Zafar et al. 2017) approach, with significantly better fairness. It is difficult to compare fairness-accuracy tradeoffs with the Hardt et al. (Hardt et al. 2016) approach, since their accuracy is significantly lower than ours. A more direct comparison is possible by noting that our learned classifier can be post-processed to improve its fairness at a direct cost to accuracy. Hence, we can achieve accuracy of $0.659$ with $\mathbf{D_{FPR}}=\mathbf{D_{FNR}}=0.01$, which compares very favorably with the Hardt et al. accuracy rate of 0.645 given the same FPR and FNR rates. For completeness, we note that using a 50-50 training-test split (again not using the test set for parameter selection), our method (SD, both considerations) produces a classifier that provides: Accuracy = 0.659, $\mathbf{D_{FPR}}=0.01,\mathbf{D_{FNR}}=0.05$. This classifier can be post-processed to achieve rates of: Accuracy = 0.655, $\mathbf{D_{FPR}}=\mathbf{D_{FNR}}=0.01$.

Figure 2 illustrates the accuracy/fairness trade-offs achievable using our scheme. Increasing the weight $c$ on the proxy fairness penalizers results in reducing their magnitude. The figure also illustrates how our relaxed penalizers succeed in tracking the real FPR and FNR differences.

3 Additional Datasets

Table 2 provides summary statistics on each of the datasets on which we tested our approach. We also briefly describe the datasets below.

The Adult Dataset http://archive.ics.uci.edu/ml/datasets/Adult is based on 1994 US Census data. The task we consider is to predict whether the income of each individual is over or under 50K dollars per year, based on features such as occupation, marital status, and education. The protected attribute selected in this task is gender.

The Loan Default Dataset https://archive.ics.uci.edu/ml/datasets/default+of+credit+card+clients contains data regrading Taiwanese credit card users. The task we consider is to predict whether an individual will default on payments, based on features such as history of past payments, age, and the amount of given credit. The protected attribute is gender.

The Admissions Dataset http://www2.law.ucla.edu/sander/Systemic/Data.htm contains records of law school students who went on to take the bar exam. The task we consider is to predict whether a student will pass the exam based on features such as LSAT score, undergraduate GPA, and family income. The protected attribute is set to race.

Table 3 describes the performance of our approach on these datasets, and Figures 3, 4, and 5 illustrate the fairness-accuracy trade-offs we achieve in each context. Overall, we see that unfairness is nearly eliminated while accuracy remains quite high. The dataset on which accuracy suffers most under our approach is the Adult dataset, which is also the dataset on which the vanilla regression is the most unfair.

Discussion

Ensuring fairness in machine learning entails addressing the philosophical question of, given a particular setting, how fairness should formally be defined. Given a formal notion of fairness, the next question is how it can be achieved, and at what cost to accuracy. Over the past few years, FPR- and FNR-rate matching have emerged as compelling fairness notions deserving of attention. As we see from our experiments, fairness-unaware learning algorithms are sometimes extremely unfair according to these metrics. It is important, then, to ask what can be done to address this, and how accuracy will be impacted.

As learning optimal classifiers to match FPR and FNR across populations may be computationally intractable (Woodworth et al. 2017), it is natural that multiple approaches to this problem might emerge, each with its own pros and cons. Prior to our work, two groundbreaking papers had proposed approaches to ensuring FPR- and FNR-matching. Hardt et al.-style post-processing (Hardt et al. 2016) is easy to implement and can be layered atop an already (unfairly) trained classifier. However, in some applications, because it does not integrate fairness in the learning process, it may be inherently sub-optimal. We illustrate this drawback in Section 5. Some might also find post-processing distasteful, as it intentionally reduces accuracy on some individuals, in order to compensate for poor accuracy on others. The proxy-based approach of (Zafar et al. 2017) makes nice use of the concept of disciplined convex-concave programming, however it has not been shown capable of lowering the unfairness below a certain (non-negligible) threshold.

As we show, fairness can successfully be achieved in many real-world settings via the addition of a judiciously chosen penalty term in the learning objective. We hope that this penalization approach, and the proxy we introduce for imposing FPR- and FNR-matching, will expand and enrich the toolkit for state-of-the art fair learning, and will help bring the goal of fair learning within reach.

Acknowledgements

This work was supported in part by NSF grants CNS-1254169 and CNS-1518941, US-Israel Binational Science Foundation grant 2012348, Israeli Science Foundation (ISF) grant #1044/16, a subcontract on the DARPA Brandeis Project, and the HUJI Cyber Security Research Center in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office.

References