Fairness Constraints: Mechanisms for Fair Classification

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, Krishna P. Gummadi
Max Planck Institute for Software Systems (MPI-SWS), Germany

Abstract
Algorithmic decision making systems are
ubiquitous across a wide variety of online aswell as offline services. These systems rely oncomplex learning methods and vast amountsof data to optimize the service functionality,
satisfaction of the end user and profitability. However, there is a growing concern thatthese automated decisions can lead, even in
the absence of intent, to a lack of fairness,i.e., their outcomes can disproportionately
hurt (or, benefit) particular groups of people sharing one or more sensitive attributes(e.g., race, sex). In this paper, we introduce
a flexible mechanism to design fair classifiers
by leveraging a novel intuitive measure of decision boundary (un)fairness. We instantiate
this mechanism with two well-known classifiers, logistic regression and support vector
machines, and show on real-world data that
our mechanism allows for a fine-grained control on the degree of fairness, often at a small
cost in terms of accuracy.
A Python implementation of our mechanism
is available at fate-computing.mpi-sws.org

1

INTRODUCTION

Algorithmic decision making processes are increasingly
becoming automated and data-driven in both online(e.g., spam filtering, product personalization) as well
as offline (e.g., pretrial risk assessment, mortgage approvals) settings. However, as automated data analysis replaces human supervision in decision making, andthe scale of the analyzed data becomes “big”, there are
growing concerns from civil organizations [Bhandari,
2016], governments [Podesta et al., 2014, Muñoz et al.,2016], and researchers [Sweeney, 2013] about potential
loss of transparency, accountability and fairness.
Anti-discrimination laws in many countries prohibit
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS) 2017, Fort Lauderdale, Florida, USA. JMLR: W&CP volume 54. Copyright 2017 by the author(s).

unfair treatment of people based on certain attributes,
also called sensitive attributes, such as gender orrace [Civil Rights Act, 1964]. These laws typicallyevaluate the fairness of a decision making process bymeans of two distinct notions [Barocas and Selbst,
2016]: disparate treatment and disparate impact.
A decision making process suffers from disparate treatment if its decisions are (partly) based on the subject’s sensitive attribute information, and it has disparate impact if its outcomes disproportionately hurt(or, benefit) people with certain sensitive attribute values (e.g., females, blacks).
While it is desirable to design decision making systems free of disparate treatment as well as disparate
impact, controlling for both forms of unfairness simultaneously is challenging. One could avoid disparate
treatment by ensuring that the decision making process does not have access to sensitive attribute information (and hence cannot make use of it). However,ignoring the sensitive attribute information may stilllead to disparate impact in outcomes: since automateddecision-making systems are often trained on historical data, if a group with a certain sensitive attributevalue was unfairly treated in the past,1 this unfairness may persist in future predictions through indirect discrimination [Pedreschi et al., 2008], leading todisparate impact. Similarly, avoiding disparate impact in outcomes by using sensitive attribute information while making decisions would constitute disparate
treatment, and may also lead to reverse discrimination [Ricci vs. DeStefano, 2009].
In this work, our goal is to design classifiers—
specifically, convex margin-based classifiers like logistic
regression and support vector machines (SVMs)—that
avoid both disparate treatment and disparate impact,
and can additionally accommodate the “business necessity” clause of disparate impact doctrine. Accord1

Like earlier studies on fairness aware-learning, we assume that while historical class labels may be biased
against group(s) with certain sensitive attribute value(s),they still contain some degree of information on the true
(unbiased) labels. Assuming the class labels to be completely biased and having no information on the true labels
would render a learning task on such a dataset pointless.

Fairness Constraints: Mechanisms for Fair Classification

ing to the business necessity clause, an employer canjustify a certain degree of disparate impact in order tomeet certain performance-related constraints [Barocas
and Selbst, 2016]. However, the employer needs to ensure that the current decision making incurs the least
possible disparate impact under the given constraints.
To the best of our knowledge, this clause has not beenaddressed by any prior study on fairness-aware learning.
While there is no specific numerical formula laid out by
anti-discrimination laws to quantify disparate impact,
here we leverage a specific instantiation supportedby the U.S. Equal Employment Opportunity Commission: the “80%-rule” (or more generally, the p%rule) [Biddle, 2005]. The p%-rule states that the ratio
between the percentage of subjects having a certain
sensitive attribute value assigned the positive decisionoutcome and the percentage of subjects not havingthat value also assigned the positive outcome should
be no less than p:100. Since it is very challenging
to directly incorporate this rule in the formulation of
convex margin-based classifiers, we introduce a novel
intuitive measure of decision boundary (un)fairness asa tractable proxy to the rule: the covariance between
the sensitive attributes and the (signed) distance between the subjects’ feature vectors and the decisionboundary of the classifier.
Our measure of fairness allows us to derive two complementary formulations for training fair classifiers:
one that maximizes accuracy subject to fairness constraints, and enables compliance with disparate impact
doctrine in its basic form (i.e., the p%-rule); and another that maximizes fairness subject to accuracy constraints, and ensures fulfilling the business necessity
clause of disparate impact. Remarkably, both formulations also avoid disparate treatment, since they do
not make use of sensitive attribute information while
making decisions. Our measure additionally satisfies
several desirable properties: (i) for a wide variety of
convex margin-based (linear and non-linear) classifiers,
it is convex and can be readily incorporated in theirformulation without increasing their complexity; (ii)it allows for clear mechanism to trade-off fairness andaccuracy; and, (iii) it can be used to ensure fairness
with respect to several sensitive attributes. Experiments with two well-known classifiers, logistic regression and support vector machines, using both synthetic
and real-world data show that our fairness measure allows for a fine-grained control of the level of fairness,often at a small cost in terms of accuracy, and provides
more flexibility than the state-of-the-art (see Table 1).
Related Work. A number of prior studies have focused on controlling disparate impact and/or disparate
treatment-based discrimination in the context of bi-nary classification [Romei and Ruggieri, 2014]. Thesestudies have typically adopted one of the two following
strategies:
The first strategy consists of pre-processing the training data [Dwork et al., 2012, Feldman et al., 2015,
Kamiran and Calders, 2009, 2010]. This typically involves (i) changing the value of the sensitive attributes
or class labels of individual items in the training data,or (ii) mapping the training data to a transformed
space where the dependencies between sensitive attributes and class labels disappear. However, these approaches treat the learning algorithm as a black box
and, as a consequence, the pre-processing can lead tounpredictable losses in accuracy.
The second strategy consists of modifying existing classifiers to limit discrimination [Calders andVerwer, 2010, Kamishima et al., 2011, Goh et al.,2016]. Among them, the work by Kamishima et al.
[Kamishima et al., 2011] is the most closely related toours: it introduces a regularization term to penalize
discrimination in the formulation of the logistic regression classifier.
Recently, Zemel et al. [2013], building on Dwork et al.
[2012], combined both strategies by jointly learning afair representation of the data and the classifier parameters. This approach has two main limitations: i) it
leads to a non-convex optimization problem and does
not guarantee optimality, and ii) the accuracy of theclassifier depends on the dimension of the fair representation, which needs to be chosen rather arbitrarily.
Many of the prior studies suffer from one or more of
the following limitations: (i) they are restricted to anarrow range of classifiers, (ii) they only accommodatea single, binary sensitive attribute, and (iii) they cannot eliminate disparate treatment and disparate impact simultaneously. Table 1 compares the capabilities
of different methods while achieving fairness.
Finally, as discussed earlier, disparate impact is particularly well suited as a fairness criterion when historical decisions used during the training phase are biased
against certain social groups. In such contexts, proportionality in outcomes (e.g., p%-rule) may help mitigate
these historical biases. However, in cases where the(unbiased) ground-truth is available for the training
phase, i.e., one can tell whether a historical decision
was right or wrong, disproportionality in outcomes canbe explained by the means of the ground-truth. In
those cases, disparate impact may be a rather misleading notion of fairness, and other recently proposed
criteria like “disparate mistreatment” by Zafar et al.
[2017], may be better suited notions of fairness. For
more discussion into this alternative notion, we point
the reader to our companion paper [Zafar et al., 2017].

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, Krishna P. Gummadi

MethodOur method
Kamiran and Calders [2010]
Calders and Verwer [2010]
Luong et al. [2011]
Kamishima et al. [2011]
Zemel et al. [2013]
Feldman et al. [2015]
Goh et al. [2016]

Disp.
Treat.
3
3
3
3
7
3
3
3

Disp.
Imp.
3
3
3
7
3
3
3
3

Business.
Necessity
3
7
7
7
7
7
7
7

Polyvalentsens. attrs.
3
7
7
7
7
7
3
3

Multiplesens. attrs.
3
7
7
7
7
7
3
3

Range ofclassifiers
Any convex margin-based
Any score-based
Naive Bayes
Any score-based
Logistic Regression
Log lossAny (only numerical non-sens. attrs.)
Ramp loss

Table 1: Capabilities of different methods in eliminating disparate impact and/or disparate treatment. None ofthe prior methods addresses disparate impact’s business necessity clause. Many of the methods do not generalize
to multiple (e.g., gender and race) or polyvalent sensitive attributes (e.g., race, that has more than two values).

2

FAIRNESS IN CLASSIFICATION

For simplicity, we consider binary classification tasks
in this work. However, our ideas can be easily extended to m-ary classification.
In a binary classification task, one needs to find a
mapping function f (x) between user feature vectors
x ∈ Rd and class labels y ∈ {−1, 1}. This task isachieved by utilizing a training set, {(xi , yi )}N
i=1 , toconstruct a mapping that works well on an unseen
test set. For margin-based classifiers, finding this mapping usually reduces to building a decision boundary
in feature space that separates users in the training set
according to their class labels. One typically looks fora decision boundary, defined by a set of parameters θ ∗ ,that achieves the greatest classification accuracy in atest set, by minimizing a loss function over a training
set L(θ), i.e., θ ∗ = argminθ L(θ). Then, given an unseen feature vector xi from the test set, the classifier
predicts fθ (xi ) = 1 if dθ∗ (xi ) ≥ 0 and fθ (xi ) = −1otherwise, where dθ∗ (x) denotes the signed distancefrom the feature vector x to the decision boundary.
If class labels in the training set are correlated with
one or more sensitive attributes {zi }N
i=1 (e.g., gender,race), the percentage of users with a certain sensitive
attribute having dθ∗ (xi ) ≥ 0 may differ dramaticallyfrom the percentage of users without this sensitive attribute value having dθ∗ (xi ) ≥ 0 (i.e., the classifier
may suffer from disparate impact). Note that this may
happen even if sensitive attributes are not used to construct the decision boundary but are correlated with
one or more of user features, through indirect discrimination [Pedreschi et al., 2008].

(or more generally the “p%-rule”), if the ratio between
the percentage of users with a particular sensitive attribute value having dθ (x) ≥ 0 and the percentage ofusers without that value having dθ (x) ≥ 0 is no lessthan 80:100 (p:100). For a given binary sensitive attribute z ∈ {0, 1}, one can write the p%-rule as:min

P (dθ (x)≥0|z=1) P (dθ (x)≥0|z=0)
P (dθ (x)≥0|z=0) , P (dθ (x)≥0|z=1)



p
≥ 100
.

(1)
Unfortunately, it is very challenging to directly incorporate the p%-rule in the formulation of convex
margin-based classifiers, since it is a non-convex function of the classifier parameters θ and, therefore, itwould lead to non-convex formulations, which are difficult to solve efficiently. Secondly, as long as the userfeature vectors lie on the same side of the decisionboundary, the p%-rule is invariant to changes in thedecision boundary. In other words, the p%-rule is afunction having saddle points. The presence of saddle points furthers complicate the procedure for solving non-convex optimization problems [Dauphin et al.,2014]. To overcome these challenges, we next introduce a novel measure of decision boundary (un)fairness
which can be used as a proxy to efficiently design classifiers satisfying a given p%-rule.

3

OUR APPROACH

2.1 Fairness Definition
First, to comply with disparate treatment criterion
we specify that sensitive attributes are not used in deN
cision making, i.e., {xi }N
i=1 and {zi }i=1 consist of disjoint feature sets.

In this section, we first introduce our measure of decision boundary (un)fairness, the decision boundary
covariance. We then derive two complementary formulations. The first formulation ensures compliancewith disparate impact doctrine in its basic form (ensure a given p%-rule) by maximizing accuracy subject to fairness constraints. The second formulation
guarantees fulfilling disparate impact’s “business necessity” clause by maximizing fairness subject to accuracy constraints.

Next, as discussed in Section 1, our definition of
disparate impact leverages the “80%-rule” [Biddle,2005]. A decision boundary satisfies the “80%-rule”

For conciseness, we append a constant 1 to all feature vectors (xi ) so that the linear classifier decisionboundary equation θ T x + b = 0 reduces to θ T x = 0.

Fairness Constraints: Mechanisms for Fair Classification

3.1 Decision Boundary Covariance
Our measure of decision boundary (un)fairness is defined as the covariance between the users’ sensitive
attributes, {zi }N
i=1 , and the signed distance fromthe users’ feature vectors to the decision boundary,{dθ (xi )}N
i=1 , i.e.:
Cov(z, dθ (x))= E[(z − z̄)dθ (x)] − E[(z − z̄)]d¯θ (x)
N

≈

1 X
(zi − z̄) dθ (xi ),
N i=1

(2)

where E[(z − z̄)]d¯θ (x) cancels out since E[(z − z̄)] = 0.
Since in linear models for classification, such as logistic
regression or linear SVMs, the decision boundary issimply the hyperplane defined by θ T x = 0, Eq. (2)PN
reduces to N1 i=1 (zi − z̄) θ T xi .
In contrast with the p%-rule (Eq. 1), the decisionboundary covariance (Eq. 2) is a convex function withrespect to the decision boundary parameters θ, sincedθ (xi ) is convex with respect to θ for all linear, convex margin-based classifiers.2 Hence, it can be easily
included in the formulation of these classifiers without
increasing the complexity of their training.

larger loss in accuracy. Note that since the above optimization problem is convex, our scheme ensures thatthe trade-off between the classifier loss function anddecision boundary covariance is Pareto optimal.
Remarks. It is important to note that the distance tothe margin, dθ (x), only depends on the non-sensitive
features x and, therefore, the sensitive features z are
not needed while making decisions. In other words, we
account for disparate treatment, by removing the sensitive features from the decision making process and, fordisparate impact, by adding fairness constraints during the training process of the classifier. Additionally, the constrained optimization problem (4), canalso be written as a regularized optimization problem
by making use of its dual form, in which the fairness
constraints are moved to the objective and the corresponding Lagrange multipliers act as regularizers.
Next, we specialize problem (4) for logistic regression
classifiers.
Logistic Regression. In logistic regression classifiers, one maps the feature vectors xi to the class labels
yi by means of a probability distribution:

Moreover, note that, if a decision boundary satisfies
the “100%-rule”, i.e.,
P (dθ (x) ≥ 0|z = 0) = P (dθ (x) ≥ 0|z = 1),(3)then the (empirical) covariance will be approximately
zero for a sufficiently large training set.
3.2

Maximizing Accuracy Under Fairness
Constraints
In this section, we design classifiers that maximize
accuracy subject to fairness constraints (e.g., a specificp%-rule), and thus may be used to ensure compliancewith the disparate impact doctrine in its basic form.
To this end, we find the decision boundary parameters
θ by minimizing the corresponding loss function over
the training set under fairness constraints, i.e.:
minimize L(θ)
PN
subject to N1 i=1 (zi − z̄) dθ (xi ) ≤ c,
PN
1
i=1 (zi − z̄) dθ (xi ) ≥ −c,N(4)

where c is the covariance threshold, which specifies anupper bound on the covariance between each sensitive
attribute and the signed distance from the feature vectors to the decision boundary. In this formulation, c
trades off fairness and accuracy, such that as we decrease c towards zero, the resulting classifier will satisfy a larger p%-rule but will potentially suffer from a2

For non-linear convex margin-based classifiers like nonlinear SVM, equivalent of dθ (xi ) is still convex in the transformed kernel space. See Appendix A for details.

p(yi = 1|xi , θ) =1,
1 + e−θT xi(5)where θ is obtained by solving a maximum like∗lihood problem
PN over the training set, i.e., θ =argminθ − i=1 log p(yi |xi , θ). Thus, the correspondPN
ing loss function is given by − i=1 log p(yi |xi , θ), andproblem (4) adopts the form:
PN
minimize − i=1 log p(yi |xi , θ)PN
subject to N1 i=1 (zi − z̄) θ T xi ≤ c,
PN
(6)
1
T
i=1 (zi − z̄) θ xi ≥ −c,
N
Appendix A presents the specialization of our formulation for both linear and non-linear SVM classifiers.
3.3

Maximizing Fairness Under Accuracy
Constraints
In the previous section, we designed classifiers thatmaximize accuracy subject to fairness constraints.
However, if the underlying correlation between theclass labels and the sensitive attributes in the training set is very high, enforcing fairness constraints
may results in underwhelming performance (accuracy)
and thus be unacceptable in terms of business objectives. Disparate impact’s “business necessity” clauseaccounts for such scenarios by allowing some degreeof disparate impact in order to meet performance constraints. However, the employer needs to ensure thatthe decision making causes least possible disparate
impact under the given performance (accuracy) constraints [Barocas and Selbst, 2016]. To accommodate

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, Krishna P. Gummadi

such scenarios, we now propose an alternative formulation that maximizes fairness (minimizes disparate impact) subject to accuracy constraints.
To this aim, we find the decision boundary parameters
θ by minimizing the corresponding (absolute) decisionboundary covariance over the training set under constraints on the classifier loss function, i.e.:
PN
minimize | N1 i=1 (zi − z̄) dθ (xi )|(7)
subject to L(θ) ≤ (1 + γ)L(θ ∗ ),where L(θ ∗ ) denotes the optimal loss over the training
set provided by the unconstrained classifier and γ ≥ 0
specifies the maximum additional loss with respect tothe loss provided by the unconstrained classifier. Here,
we can ensure maximum fairness with no loss in accuracy by setting γ = 0. As in Section 3.2, it is possible
to specialize problem (7) for the same classifiers andshow that the formulation remains convex.
Fine-Grained Accuracy Constraints. In many
classifiers, including logistic regression and SVMs, theloss function (or the dual of the loss function) is additive over the points in the training set, i.e., L(θ) =PN
i=1 Li (θ), where Li (θ) is the individual loss associated with the i-th point in the training set. Moreover,the individual loss Li (θ) typically tells us how close
the predicted label f (xi ) is to the true label yi , bymeans of the signed distance to the decision boundary. Therefore, one may think of incorporating loss
constraints for a certain set of users, and consequently,
prevent individual users originally classified as positive(by the unconstrained classifier) from being classified
as negative by the constrained classifier. To do so, wefind the decision boundary parameters θ as:
PN
minimize | N1 i=1 (zi − z̄) θ T xi |subject to Li (θ) ≤ (1 + γi )Li (θ ∗ ) ∀i ∈ {1, . . . , N },(8)
where Li (θ ∗ ) is the individual loss associated to thei-th user in the training set provided by the unconstrained classifier and γi ≥ 0 is her allowed additional loss. For example, in thecase of logistic rePNgression classifier, θ ∗ = argminθ i=1 − log p(yi |xi , θ)and the losses for individual points are Li (θ) =− log p(yi |xi , θ). Now, if we set γi = 0, we are enforcing that the probability of the i-th user to be mappedin the positive class to be equal or higher than in theoriginal (unconstrained) classifier.

4

EVALUATION

We evaluate our framework on several synthetic andreal-world datasets. We first experiment with our first
formulation and show that it allows for fine-grained
fairness control, often at a minimal loss in accuracy.
Then, we validate our second formulation, which allows maximizing fairness under accuracy constraints,

and also provides guarantees on avoiding negative classification of certain individual users or group of users.
Here, we adopt the p%-rule [Biddle, 2005] as ourtrue measure of fairness. However, as shown in Appendix B.2, we obtain similar results if we consider
another measure of fairness used by some of the previous studies in this area.
4.1 Experiments on Synthetic Data
Fairness constraints vs accuracy constraints. To
simulate different degrees of disparate impact in classification outcomes, we generate two synthetic datasetswith different levels of correlation between a single, binary sensitive attribute and class labels. We then train
two types of logistic regression classifiers: one typemaximizes accuracy subject to fairness constraints(Section 3.2), and the other maximizes fairness underfine-grained accuracy constraints (Section 3.3).
Specifically, we generate 4,000 binary class labels
uniformly at random and assign a 2-dimensionaluser feature vector per label by drawing samples from two different Gaussian distributions:p(x|y=1) = N ([2; 2], [5, 1; 1, 5]) and p(x|y=−1) =N ([−2; −2], [10, 1; 1, 3]). Then, we draw each user’s
sensitive attribute z from a Bernoulli distribution:p(z = 1) = p(x0 |y = 1)/(p(x0 |y = 1) + p(x0 |y = −1)),
where x0 = [cos(φ), − sin(φ); sin(φ), cos(φ)]x is simply a rotated version of the feature vector, x.
We generate datasets with two values for the parameter φ, which controls the correlation between the sensitive attribute and the class labels (and hence, theresulting disparate impact). Here, the closer φ is tozero, the higher the correlation. Finally, we trained
both types of constrained classifiers on each dataset.
Fig. 1a shows the decision boundaries provided by theclassifiers that maximize accuracy under fairness constraints for two different correlation values and two(successively decreasing) covariance thresholds, c. We
compare these boundaries against the unconstrained
decision boundary (solid line). As expected, given thedata generation process, fairness constraints map into
a rotation of the decision boundary (dashed lines),
which is greater as we decrease threshold value c orincrease the correlation in the original data (fromφ = π/4 to φ = π/8). This movement of the decision boundaries shows that our fairness constraints are
successfully undoing (albeit in a highly controlled setting) the rotations we used to induce disparate impact
in the dataset. Moreover, a smaller covariance threshold (a larger rotation) leads to a more fair solution,although, it comes at a larger cost in accuracy.
Fig. 1b shows the decision boundaries provided by theclassifiers that maximize fairness under fine-grained
accuracy constraints. Here, the fine-grained accuracy

Fairness Constraints: Mechanisms for Fair Classification
Acc=0.87; p%-rule=45%
Acc=0.82; p%-rule=70%
Acc=0.74; p%-rule=98%

Acc=0.87; p%-rule=24%
Acc=0.71; p%-rule=62%
Acc=0.60; p%-rule=99%

φ = π/4

φ = π/8(a) Maximizing accuracy under fairness constraints

Acc=0.87; p%-rule=45%
Acc=0.78; p%-rule=76%
Acc=0.64; p%-rule=93%

Acc=0.87; p%-rule=24%
Acc=0.78; p%-rule=54%
Acc=0.53; p%-rule=99%

φ = π/4

φ = π/8(b) Maximizing fairness under accuracy constraints

Figure 1: The solid light blue lines show the decision boundaries for logistic regressors without fairness constraints.
The dashed lines show the decision boundaries for fair logistic regressors trained (a) to maximize accuracy under
fairness constraints and (b) to maximize fairness under fine-grained accuracy constraints, which prevents users
with z = 1 (circles) labeled as positive by the unconstrained classifier from being moved to the negative class.
Each column corresponds to a dataset, with different correlation value between sensitive attribute values (crosses
vs circles) and class labels (red vs green).
constraints ensure that the users with z = 1 classified as positive by the unconstrained classifier (circles
above the solid line) are not labeled as negative by
the fair classifier. The decision boundaries provided
by this formulation, in contrast to the previous one,are rotated and shifted versions of the unconstrainedboundary. Such shifts enable the constrained classifiers to avoid negatively classifying users specified in
the constraints.
We also illustrate how the decision boundary of a nonlinear classifier, a SVM with RBF kernel, changes under fairness constraints in Appendix B.1.
4.2 Experiments on Real Data
Experimental Setup. We experiment with two realworld datasets: The Adult income dataset [Adult
data, 1996] and the Bank marketing dataset [Bankdata, 2014]. The Adult dataset contains a total of45,222 subjects, each with 14 features (e.g., age, educational level) and a binary label, which indicates
whether a subject’s incomes is above (positive class)or below (negative class) 50K USD. For this dataset,
we consider gender and race, respectively, as binary
and non-binary (polyvalent) sensitive attributes. The
Bank dataset contains a total of 41,188 subjects, eachwith 20 attributes (e.g., marital status) and a binary label, which indicates whether the client has subscribed (positive class) or not (negative class) to a term
deposit. In this case, we consider age as (binary) sensitive attribute, which is discretized to indicate whether
the client’s age is between 25 and 60 years. For detailed statistics about the distribution of different sensitive attributes in positive class in these datasets, werefer the reader to Appendix B.2.
For the sake of conciseness, while presenting the results
for binary sensitive attributes, we refer to females andmales, respectively, as protected and non-protectedgroups in Adult data. Similarly, in Bank data, werefer to users between age 25 and 60 as protected andrest of the users as non-protected group. In our experiments, to obtain more reliable estimates of accuracy
and fairness, we repeatedly split each dataset into a
train (70%) and test (30%) set 5 times and report the
average statistics for accuracy and fairness.
Maximizing accuracy under fairness constraints. First, we experiment with a single binary
sensitive attribute, gender and age, for respectively,
the Adult and Bank data. For each dataset, we train
several logistic regression and SVM classifiers (denotedby ‘C-LR’ and ‘C-SVM’, respectively), each subject
to fairness constraints with different values of covariance threshold c (Section 3.2), and then empiricallyinvestigate the trade-off between accuracy and fairness. Fig. 2a shows the (empirical) decision boundary covariance against the relative loss incurred by
the classifier. The ‘relative loss’ is normalized between
the loss incurred by an unconstrained classifier and by
the classifier with a covariance threshold of 0. Here,each pair of (covariance, loss) values is guaranteed to
be Pareto optimal, since our problem formulation isconvex. Additionally, Fig. 2b investigates the correspondence between decision boundary covariance andp%-rule computed on the training set, showing that, as
desired: i) the lower the covariance, the higher the p%rule the classifiers satisfy and (ii) a 100%-rule maps tozero covariance.
Then, we compare our approach to a well-known
competing method from each of the two categories
discussed in Section 1: preferential sampling approach [Kamiran and Calders, 2010], applied to logistic regression (‘PS-LR’) and SVM (‘PS-SVM’), as an
example of data pre-processing, and the regularized logistic regression (‘R-LR’) [Kamishima et al., 2011], asan example of modifying a classifier to limit unfairness.
Fig. 2c summarizes the results: the top panel shows av-

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, Krishna P. Gummadi
C-SVM

C-LR

50
25

0.4
0.2
0
Empirical covariance
C-LR

0.83
0.81

C-SVM

C-LR

20

C-LR

% in +ve classp%-rule70
45

PS-SVM

0.91

0.9

100

20

C-SVM

0.05
0
Empirical covariance

Adult and Bank

Adult and Bank(a) Loss vs. Cov.

(b) Cov. vs. p%-rule

40

60
80
p%-rule100

60
80p%-rule

100

R-LR

30

25
20
15
10
5

0.1

0.1
0.05
0
Empirical covariance60
80p%-rule

30

20

0

40

C-SVM

95

0.5

PS-LR

0.79
0.4
0.2
0
Empirical covariance

1

R-LR

Accuracy

75

0

C-SVM

C-LR

0.85
Accuracyp%-ruleRelative loss

0.5

Relative loss

C-SVM

100

% in +ve class

C-LR

1

20
10
0

20

40

60
80
p%-rule

Adult

100

20

40

Bank

(c) Single binary sensitive attribute

Figure 2: [Maximizing accuracy under fairness constraints: single, binary sensitive attribute] Panels in (a) show
the trade-off between the empirical covariance in Eq. 2 and the relative loss (with respect to the unconstrainedclassifier), for the Adult (top) and Bank (bottom) datasets. Here each pair of (covariance, loss) values isguaranteed to be Pareto optimal by construction. Panels in (b) show the correspondence between the empiricalcovariance and the p%-rule for classifiers trained under fairness constraints. Panels in (c) show the accuracy
against p%-rule value (top) and the percentage of protected (dashed) and non-protected (solid) users in thepositive class against the p%-rule value (bottom).
C-LR

0.84
Accuracy

Accuracy

0.84
0.82
0.8
0.78

0.82
0.8
0.78

1 0.8 0.6 0.4 0.2 0Multiplicative cov. factor (a)
White

Black

Asian

1 0.8 0.6 0.4 0.2 0Multiplicative cov. factor (a)Am-Ind

Other

Male

Female40% in +ve class% in +ve class

40
30
20
10

30
20
10

1

0.8 0.6 0.4 0.2

01

0.8 0.6 0.4 0.2

0Multiplicative cov. factor (a)Multiplicative cov. factor (a)Non-binary

SeveralFigure 3: [Maximizing accuracy under fairness constraints: non-binary and several sensitive attributes]
The figure shows accuracy (top) and percentage ofusers in positive class (bottom) against a multiplicative factor a ∈ [0, 1] such that c = ac∗ , where c∗ denotes the unconstrained classifier covariance.
erage accuracy and the bottom panel the percentage
of protected (dashed lines) and non-protected (solidlines) users in positive class against the average p%rule, as computed on test sets. We observe that: i) the
performance of our classifiers (C-LR, C-SVM) and regularized logistic regression (R-LR) is comparable, ours
are slightly better for Adult data (left column) whileslightly worse for Bank data (right column). However,

R-LR uses sensitive attribute values from the test set
to make predictions, failing the disparate treatment
test and potentially allowing for reverse discrimination [Ricci vs. DeStefano, 2009]; ii) the preferential
sampling presents the worst performance and always
achieves p%-rules under 80%; and, (iii) in the Adult
data, all classifiers move non-protected users (males)to the negative class and protected users (females) tothe positive class to achieve fairness, in contrast, inthe Bank data, they only move non-protected (young
and old) users originally labeled as positive to the negative class since it provides a smaller accuracy loss.
However, the latter can be problematic: from a business perspective, a bank may be interested in finding
potential subscribers rather than losing existing customers. This last observation motivates our second
formulation (Section 3.3), which we experiment withlater in this section.
Finally, we experiment with non-binary (race) andseveral (gender and race) sensitive attributes in Adult
dataset. We do not compare with competing methods
since they cannot handle non-binary or several sensitive attributes. Fig. 3 summarizes the results byshowing the accuracy and the percentage of subjects
sharing each sensitive attribute value classified as positive against a multiplicative covariance factor a ∈ [0, 1]
such that c = ac∗ , where c∗ is the unconstrained classifier covariance3 (note that p%-rule is only defined for3
For several sensitive features, we compute the initialcovariance c∗k for each of the sensitive feature k, and thenFairness Constraints: Mechanisms for Fair Classification

0.75

40

0.7

20
0.1
1
10
Multiplicative loss factor (γ)γ-LR (N-P)

100

0.9

80
0.8
60
0.7

40

0.6

20
0.1
1
10
100
Multiplicative loss factor (γ)

Adultγ-LR (P)Fine-γ-LR (N-P)

35
25
15
5

40
30
20
10
0

0.1
1
10
Multiplicative loss factor (γ)

Bank

0.1
1
10
100
Multiplicative loss factor (γ)Adult(a) Acc and p%-ruleFine-γ-LR (P)50% in +ve class60

Fine-γ-LR (p%-rule)% in +ve class

80

0.8

Accuracy

Accuracy

Fine-γ-LR (Acc)

100p%-ruleγ-LR (p%-rule)p%-ruleγ-LR (Acc)

0.85

Bank
(b) % in +ve class

Figure 4: [Maximizing fairness under accuracy constraints] Panels in (a) show accuracy (solid) and p%-rule value(dashed) against γ. Panels in (b) show the percentage of protected (P, dashed) and non-protected (N-P, solid)
users in the positive class against γ.
a binary sensitive feature). As expected, as the valueof c decreases, the percentage of subjects in the positive class from sensitive attribute value groups becomenearly equal4 while the loss in accuracy is modest.
Maximizing fairness under accuracy constraints. Next, we demonstrate that our second formulation (Section 3.3) can maximize fairness while
precisely controlling loss in accuracy. To this end, we
first train several logistic regression classifiers (denotedby ‘γ-LR’), which minimize the decision boundary covariance subject to accuracy constraints over the entire dataset by solving problem (7) with increasing values of γ. Then, we train logistic regression classifiers(denoted by ‘Fine-γ-LR’) that minimize the decisionboundary covariance subject to fine-grained accuracy
constraints by solving problem (8). Here, we preventthe non-protected users that were classified as positiveby the unconstrained logistic regression classifier frombeing classified as negative by constraining that theirdecision from distance boundary stays positive whilelearning the fair boundary. We then increase γi = γ
for the remaining users. In both cases, we increased
the value of γ until we reach a 100%-rule during training. Fig. 4 summarizes the results for both datasets,by showing (a) the average accuracy (solid curves) and
p%-rule (dashed curves) against γ, and (b) the percentage of non-protected (N-P, solid curves) and protected (P, dashed curves) users in the positive classagainst γ. We observe that, as we increase γ, the classifiers that constrain the overall training loss (γ-LR)
remove non-protected users from the positive class andadd protected users to the positive class, in contrast,
the classifiers that prevent the non-protected usersthat were classified as positive in the unconstrainedclassifier from being classified as negative (Fine-γ-LR)
add both protected and non-protected users to the poscompute the covariance threshold separately for each sensitive feature as ac∗k .
4
The scarce representation of the race value ‘Other’(only 0.8% of the data) hinders an accurate estimation of
the decision boundary covariance and, as a result, the classifier does not reach perfect fairness with respect to thissensitive attribute value.

itive class. As a consequence, the latter achieves lower
accuracy for the same p%-rule.

5

DISCUSSION & FUTURE WORKIn this paper, we introduced a novel measure of decision boundary fairness, which enables us to ensure fairness with respect to one or more sensitive attributes,
in terms of both disparate treatment and disparate impact. We leverage this measure to derive two complementary formulations: one that maximizes accuracy
subject to fairness constraints, and helps ensure compliance with a non-discrimination policy or law (e.g., agiven p%-rule); and another one that maximizes fairness subject to accuracy constraints, and ensures fulfilling certain business needs (e.g., disparate impact’s
business necessity clause).
Our framework opens many avenues for future work.
For example, one could include fairness constraints
in other supervised (e.g., regression, recommendation)
as well as unsupervised (e.g., set selection, ranking)learning tasks. Further, while we note that a decreasing covariance threshold corresponds to an increasing (more fair) p%-rule, the relation between the twois only empirically observed. A precise mapping between covariance and p%-rule is quite challenging toderive analytically since it depends on the specific classifier and the dataset being used. Such a theoreticalanalysis would be an interesting future direction. Finally, in this paper we consider disparate impact as
our notion of fairness with the assumption that thehistorical training data may contain biases against certain group(s). Since the actual proportions in positiveclass from different groups (e.g., males, females) in the
ground-truth dataset are not available (we only haveaccess to a biased dataset), ensuring equal proportions
from each group in the positive class (removing disparate impact) serves as an attractive notion of fairness. However, in cases where the historical groundtruth decisions are available, disparate impact can be
explained by the means of the ground truth, and alternative notions of fairness, e.g., disparate mistreatment [Zafar et al., 2017], might be more suitable.

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, Krishna P. Gummadi

References
Adult data. http://tinyurl.com/UCI-Adult, 1996.
Bank data. http://tinyurl.com/UCI-Bank, 2014.
S. Barocas and A. D. Selbst. Big Data’s Disparate
Impact. California Law Review, 2016.
E. Bhandari.
Big Data Can Be Used To Violate Civil Rights Laws, and the FTC Agrees.
https://www.aclu.org/blog/free-future/big-datacan-be-used-violate-civil-rights-laws-and-ftc-agrees,
2016.
D. Biddle. Adverse Impact and Test Validation: A
Practitioner’s Guide to Valid and Defensible Employment Testing. Gower, 2005.
T. Calders and S. Verwer.
Three Naive Bayes
Approaches for Discrimination-Free Classification.
Data Mining and Knowledge Discovery, 2010.
Civil Rights Act. Civil Rights Act of 1964, Title VII,
Equal Employment Opportunities, 1964.
Y. N. Dauphin, R. Pascanu, C. Gulcehre, K. Cho,
S. Ganguli, and Y. Bengio. Identifying and Attacking the Saddle Point Problem in High-dimensional
Non-convex Optimization. In NIPS, 2014.
C. Dwork, M. Hardt, T. Pitassi, and O. Reingold. Fairness Through Awareness. In ITCSC, 2012.
M. Feldman, S. A. Friedler, J. Moeller, C. Scheidegger,
and S. Venkatasubramanian. Certifying and removing disparate impact. In KDD, 2015.
G. Goh, A. Cotter, M. Gupta, and M. Friedlander. Satisfying Real-world Goals with Dataset Constraints. In NIPS, 2016.
F. Kamiran and T. Calders. Classifying without Discriminating. In IC4, 2009.
F. Kamiran and T. Calders. Classification with No
Discrimination by Preferential Sampling. In BENELEARN, 2010.
T. Kamishima, S. Akaho, H. Asoh, and J. Sakuma.
Fairness-aware Classifier with Prejudice Remover
Regularizer. In PADM, 2011.
B. T. Luong, S. Ruggieri, and F. Turini. kNN as an
Implementation of Situation Testing for Discrimination Discovery and Prevention. In KDD, 2011.
C. Muñoz, M. Smith, and D. Patil. Big Data: A
Report on Algorithmic Systems, Opportunity, andCivil Rights. Executive Office of the President. The
White House., 2016.
D. Pedreschi, S. Ruggieri, and F. Turini.
Discrimination-aware Data Mining.
In KDD,2008.

J. Podesta, P. Pritzker, E. Moniz, J. Holdren, andJ. Zients. Big Data: Seizing Opportunities, Preserving Values. Executive Office of the President.
The White House., 2014.
Ricci vs. DeStefano. U.S. Supreme Court, 2009.
A. Romei and S. Ruggieri. A Multidisciplinary Survey
on Discrimination Analysis. KER, 2014.
B. Schölkopf and A. J. Smola. Learning with Kernels:
Support Vector Machines, Regularization, Optimization, and Beyond. MIT press, 2002.
L. Sweeney. Discrimination in Online Ad Delivery.
ACM Queue, 2013.
M. B. Zafar, I. Valera, M. G. Rodriguez, and K. P.
Gummadi. Fairness Beyond Disparate Treatment &Disparate Impact: Learning Classification without
Disparate Mistreatment. In WWW, 2017.
R. Zemel, Y. Wu, K. Swersky, T. Pitassi, andC. Dwork. Learning Fair Representations. In ICML,
2013.

Fairness Constraints: Mechanisms for Fair Classification

A

Particularizing the Fairness Constraints for SVM

One can specialize our fair classifier formulation proposed in (4) as:
Linear SVM. A linear SVM distinguishes among classes using a linear hyperplane θ T x = 0. In this case, theparameter vector θ of the fair linear SVM can be found by solving the following quadratic program:Pnminimize kθk2 + C i=1 ξisubject to yi θ T xi ≥ 1 − ξi , ∀i ∈ {1, . . . , n}ξi ≥ 0, ∀i ∈ {1, . . . , n},P
N1T
N Pi=1 (zi − z̄) θ xi ≤ c,
(9)
N
1
T
i=1 (zi − z̄) θ xi ≥ −c,N2
where θ and ξ are
Pnthe variables, kθk corresponds to the margin between the support vectors assigned to different
classes, and C i=1 ξi penalizes the number of data points falling inside the margin.

Nonlinear SVM. In a nonlinear SVM, the decision boundary takes the form θ T Φ(x) = 0, where Φ(·) is anonlinear transformation that maps every feature vector x into a higher dimensional transformed feature space.
Similarly as in the case of a linear SVM, one may think of finding the parameter vector θ by solving a constrained
quadratic program similar to the one defined by Eq. (9). However, the dimensionality of the transformed feature
space can be large, or even infinite, making the corresponding optimization problem difficult to solve. Fortunately,
we can leverage the kernel trick [Schölkopf and Smola, 2002] both in the original optimization problem and thefairness inequalities, and resort instead to the dual form of the problem, which can be solved efficiently. In
particular, the dual form is given by:
PN
PN
minimize
i=1 αi +i=1 αi yi (gα (xi ) + hα (xi ))subject to αi ≥ 0, ∀i ∈ {1, . . . , N },PN
i=1 αi yi = 0,
PN
1
N Pi=1 (zi − z̄) gα (xi ) ≤ c,
(10)N
1i=1 (zi − z̄) gα (xi ) ≥ −c,
N
PN
where α are the dual variables, gα (xi ) = j=1 αj yj k(xi , xj ) can still be interpreted as a signed distance to thePN
decision boundary in the transformed feature space, and hα (xi ) = j=1 αj yj C1 δij , where δij = 1 if i = j andδij = 0, otherwise. Here, k(xi , xj ) = hφ(xi ), φ(xj )i denotes the inner product between a pair of transformedfeature vectors and is often called the kernel function.

B

Additional Experiments

B.1

Experiments on Non-linear Synthetic Data

Here, we illustrate how the decision boundary of an non-linear classifier, a SVM with radial basis function (RBF)
kernel, changes under fairness constraints. To this end, we generate 4,000 user binary class labels uniformly at
random and assign a 2-dimensional user feature vector per label by drawing samples from p(x|y = 1, β) =βN ([2; 2], [5 1; 1 5]) + (1 − β)N ([−2; −2], [10 1; 1 3]) if y = 1, and p(x|y = −1, β) = βN ([4; −4], [4 4; 2 5]) + (1 −β)N ([−4; 6], [6 2; 2 3]) otherwise, where β ∈ {0, 1} is sampled from Bernoulli(0.5). Then, we generate eachuser’s sensitive attribute z by applying the same rotation as detailed in Section 4.1.
Figure 5 shows the decision boundaries provided by the SVM that maximizes accuracy under fairness constraints
with c = 0 for two different correlation values, set by φ = π/4 and φ = π/8, in comparison with the unconstrained
SVM. We observe that, in this case, the decision boundaries provided by the constrained SVMs are very different
to the decision boundary provided by the unconstrained SVM, not simple shifts or rotations of the latter, andsuccessfully reverse engineer the mechanism we used to generate the class labels and sensitive attributes.
B.2

Experiments on Real Data

Additional Data Statistics. In this section, we show the distribution of sensitive features and class labels in
our real-world datasets.

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, Krishna P. Gummadi

Acc=0.94; p% rule=42%(π/4),12%(π/8)

Acc=0.83; p% rule=95%

Acc=0.60; p% rule=97%(a) Unconstrained(b) φ = π/4(c) φ = π/8

Figure 5: Decision boundaries for SVM classifier with RBF Kernel trained without fairness constraints (left)
and with fairness constraints (c = 0) on two synthetic datasets with different correlation value between sensitive
attribute values (crosses vs circles) and class labels (red vs green).
Table 2: Datasets details (binary sensitive attributes: gender and age).
> 50K
9,539
1,669
11,208

Total
30,527
14, 695
45,222

Sensitive Attribute25 ≤ age ≤ 60
age < 25 or age > 60
Total(a) Adult dataset

γ-LR (CV score)

Fine-γ-LR (Acc)

Fine-γ-LR (CV score)

0
0.85

0.05

0.8

0.1

0.75
0.15
0.7

0.7

0.18

0.1
1
10
Multiplicative loss factor (γ)

0.2
0.1
1
10
100
Multiplicative loss factor (γ)

0.65

Adult

Bank
(a) Acc and CV score

γ-LR (P)Total
39,2101,97841,188Fine-γ-LR (N-P)

35
CV score

0.12

Accuracy

0.75

CV score

Accuracy

0.06

γ-LR (N-P)

0
0.9

0.8

Yes
3,970
670
4,640

(b) Bank dataset% in +ve classγ-LR (Acc)
0.85

No35,2401,308
36,548Fine-γ-LR (P)50% in +ve classy ≤ 50K
20,98813,02634,014

Sensitive Attribute
Males
Females
Total

25
15
5

40
30
20
10
0

0.1
1
10
Multiplicative loss factor (γ)

0.1
1
10
100
Multiplicative loss factor (γ)

Adult

Bank
(b) % in +ve class

Figure 7: [Maximizing fairness under accuracy constraints] Panels in (a) show the accuracy (solid) and CV scorevalue (dashed) against γ. Panels in (b) show the percentage of protected (P, dashed) and non-protected (N-P,
solid) users in the positive class against γ.

CV score as fairness measure. While evaluating the performance of our method in Section 4, we used p%-ruleas the true measure of fairness, since it is a generalization of the 80%-rule advocated by US Equal Employment
Opportunity Commission [Biddle, 2005] to quantify disparate impact. We would like to remark that this measureis closely related to another measure of fairness used by some of the previous works [Kamiran and Calders, 2009,
Kamishima et al., 2011, Zemel et al., 2013] in this area, referred to as Calder-Verwer (CV) score by Kamishima
et al. [2011]. In particular, the CV score is defined as the (absolute value of the) difference between the percentage
of users sharing a particular sensitive attribute value that lie on one side of the decision boundary and thepercentage of users not sharing that value lying on the same side, i.e., P (dθ (x) ≥ 0|z = 0)−P (dθ (x) ≥ 0|z = 1) .
In this section, we show that using CV score (instead of p%-rule) as a measure of fairness would yield similar
results.
First, we show that constraining the covariance between users’ sensitive attributes (Fig. 6a and Figure 6b), andthe signed distance from the decision boundary, corresponds to an increasing relative loss and decreasing CV

Fairness Constraints: Mechanisms for Fair Classification

Table 3: Adult dataset (Non-binary sensitive attribute: race)y ≤ 50K
382
934
28,6963,694
308
34,014

Sensitive Attribute
American-Indian/Eskimo
Asian/Pacific-Islander
White
Black
Other
Total

C-LR

C-SVM

C-SVM

C-LR

R-LR

0.15

PS-SVM

0.1

0.91
Accuracy

0.5

PS-LR

0.85
Accuracy

CV score

0.83
0.82
0.81

0.05

0.9

0.8
0

0.4
0.2
0
Empirical covariance

0.3

0.2

0.1

0

0.2

C-SVM

C-LR

CV score

0

0.1

0.05

0

C-LR

C-SVM

0.15
0.1
0.05
0

0.18

0.1

Adult and Bank

Adult and Bank(a) Loss vs. Cov.

(b) Cov. vs. CV score

0

C-SVM

30

25

25

20
15
10
0.15

0.1
0.05
CV-score

Adult

0.06

0

0.12
0.06
CV-score

0

R-LR

30

0.2

0.12
CV-score

5

0.1
0.05
0
Empirical covariance0.075 0.05 0.025
Covariance

0.24

CV-score

0.2

1

0.5

0.15

Covariance% in +ve class

C-LR

0.79
0.4

% in +ve class

Relative loss

Total
435
1,303
38, 9034, 228353
45,2220.84

0Relative loss

C-SVM

C-LR

0.2

1

> 50K
53
369
10,207534
45
11,208

0

20
15
10
5
0
0.24

0.18

Bank

(c) Single binary sensitive attribute

Figure 6: [Maximizing accuracy under fairness constraints: single, binary sensitive attribute] Panels in (a) show
the trade-off between the empirical covariance and the relative loss in accuracy (with respect to the unconstrainedclassifier), where each pair of (covariance, loss) values is guaranteed to be Pareto optimal by construction. Panelsin (b) show the correspondence between the empirical covariance in Eq. 2 and the CV score for classifiers trained
under fairness constraints for the Adult (top) and Bank (bottom) datasets. Panels in (c) show the accuracy
against CV score value (top) and the percentage of protected (dashed) and non-protected (solid) users in thepositive class against the CV score value (bottom).
score (a more fair decision boundary).
Next, we show the performance of different methods based on the CV score (Fig, 6c and 7). The results in Fig.6c
and 7 correspond to the ones shown in Fig. 2c and 4, where we took p%-rule as the measure of fairness. It canbe seen that both measures of fairness (p%-rule and CV score) provide very similar trades-off in terms of fairness
and accuracy.
Notice that according to the definitions provided in Section 2.1, a decreasing CV score corresponds to an increasing p%-rule (and hence, a more fair decision boundary).