Achieving Non-Discrimination in Prediction

1 Introduction

Discrimination-aware classification is receiving an increasing attention in the data mining and machine learning fields. Many methods have been proposed for constructing discrimination-free classifiers, which can be broadly classified into three categories: the pre-process methods that modify the training data [Kamiran and Calders, 2009a; Feldman et al., 2015; Zhang et al., 2017; Calmon et al., 2017; Nabi and Shpitser, 2017], the in-process methods that adjust the learning process of the classifier [Calders and Verwer, 2010; Kamishima et al., 2011; 2012; Zafar et al., 2017], and the post-process methods that directly change the predicted labels [Kamiran et al., 2010; Hardt et al., 2016]. All three categories of methods have their respective limitations. For the in-process methods, they usually perform some tweak or develop some regularizers for the classifier to correct or penalize discriminatory outcomes during the learning process. However, since the discrimination or fair constraints are generally not convex functions, surrogate functions are usually used for the minimization. As a result, additional bias might be introduced due to the approximation errors associated with the surrogate function. For the post-process methods, they are restricted to those who can modify the predicted label of each individual independently. Thus, methods that map the whole dataset or population to a new non-discriminatory one cannot be adopted for post-process, which means that a number of causal-based discrimination removal methods (e.g., [Zhang et al., 2017; Nabi and Shpitser, 2017]) cannot be applied.

In our work, we target the pre-process methods that modify the training data, where some methods only modify the label, such as the Massaging [Kamiran and Calders, 2009a; ˇZliobait˙e et al., 2011] and the Causal-Based Removal [Zhang et al., 2017], and some methods also modify the data attributes other than the label, such as the Preferential Sampling [Kamiran and Calders, 2012; ˇZliobait˙e et al., 2011], the Reweighing [Calders et al., 2009], and the Disparate Impact Removal [Feldman et al., 2015; Adler et al., 2016]. The fundamental assumption of the pre-process methods is that, since the classifier is learned from a discrimination-free dataset, it is likely that the future prediction will also be discriminationfree [Kamiran and Calders, 2009b]. Although this assumption is plausible, however, there is no theoretical guarantee to show "how much likely" it is and "how discrimination-free" the prediction would be given a training data and a classifier. The lack of the theoretical guarantees places great uncertainty on the performance of all pre-process methods.

In this paper, we fill this gap by modeling the discrimination in prediction using the causal model [Pearl, 2009]. A causal model is a structural equation-based mathematical object that describes the causal mechanism of a system. We assume that there exists a fixed but unknown causal model that represents the underlying data generation mechanism of the population. Based on the causal model, we define the causal measure of discrimination in population as well as in prediction. We then formalize two problems, namely discovering and removing discrimination in prediction. Based on specific assumptions regarding the causal model and the causal measure of discrimination, we conduct concrete analysis of discrimination. We derive the formula for quantitatively measuring the discriminatory e�ect in population from the observable probability distributions. We then derive the corresponding causal measure of the discrimination in prediction, as well as their approximations from the sample dataset. Finally, we link the discrimination in prediction with the discrimination in the training data by a probabilistic condition, which mathematically bounds the probability of the discrimination in prediction being within a given interval in terms of the training data and classifier.

As a consequence, we obtain two important theoretical results: (1) even if the discrimination in the training data is completely removed, the discrimination in prediction can still exist due to the bias in the classifier; and (2) for removing discrimination, di�erent from the claims of many previous work, not all pre-process methods can ensure non-discrimination in prediction even though they can achieve non-discrimination in the modified training data. We show that to guarantee nondiscrimination in prediction, the pre-process methods should only modify the label. Based on the results, we develop a twophase framework for constructing a discrimination-free classifier with a theoretical guarantee, which provides a guideline for employing existing pre-process methods or designing new ones. The experiments demonstrate the theoretical results and show the e�ectiveness of our two-phase framework.

2 ProblemFormulation

2.1 Notations and Preliminaries

We consider an attribute space which consists of some protected attributes, the label of certain decision attribute, and the non-protected attributes. Throughout the paper, we use an uppercase alphabet, e.g., X to represent an attribute; a bold uppercase alphabet, e.g., X, to represent a subset of attributes. We use a lowercase alphabet, e.g., x, to represent a realization of attribute X; a bold lowercase alphabet, e.g., x, to represent a realization of X. For ease of representation, we assume that there is only one protected attribute, denoted by C, which is a binary attribute associated with the domain values of the nonprotected group c + and the protected group c � . We denote the label of the decision attribute by L, which is a binary attribute associated with the domain values of the positive label l + and negative label l � . According to the convention in machine learning, we also define that l + = 1 and l � = 0. The set of all the non-protected attributes is denoted by Z = fZ1; � � � ; Zmg. Please refer to the notation table shown as Table 1.

A causal model is formally defined as follows.

Definition 1 (Causal Model). A causal model M is a triple M = hU; V; Fi where

1. U is a set of hidden contextual variables that are determined by factors outside the model.
2. V is a set of observed variables that are determined by variables in U [ V.
3. F is a set of equations mapping from U�V to V. Specifically, for each Vi 2 V, there is an equation fi mapping fromU� (VnVi) to Vi, i.e.,

where pai is a realization of a set of observed variables PAi � VnVi called the parents of Vi, and ui is a realization of a set of hidden variables Ui � U.

The causal e�ect in the causal model is defined over the intervention that fixes the value of an observed variable(s) V to a constant(s) v while keeping the rest of the model unchanged. The intervention is mathematically formalized as do(V = v) or simply do(v). Then, for any variables X; Y 2 V, the distribution of Y after do(x) is defined as [Pearl, 2009]

where Yx(u) denotes the value of Y after intervention do(x) under context U = u.

Note that P(u) is an unknown joint distribution of all hidden variables. If the causal model satisfies the Markovian assumption: (1) the associated causal graph of the causal model is acyclic; and (2) all variables in U are mutually independent, P(yjdo(x)) can be computed from the joint distribution of V according to the truncated factorization formula [Pearl, 2009]

where the summation is a marginalization that traverses all value combinations of V 0 = VnfX; Yg, and �X=x means replacing X with x in each term.

2.2 Model Discrimination in Prediction

Assume that there exists a fixed population over the space C � Z � L. The values of all the attributes in the population are determined by a causal model M, which can be written as

where fL can be considered as the decision making process in the real system. Without ambiguity, we can also use M to denote the population, and use the terms mechanism and population interchangeably. In practice, M is unknown and we can only observe a sample dataset D = f(c ( j) ; z ( j) ; l ( j) ); j = 1; � � � ; ng drawn from the population.

A classifier h is function mapping from C � Z to L. A hypothesis space H is a set of candidate classifiers. A learning algorithm analyzes dataset D as the training data to find a classifier from H that minimizes the di�erence between the predicted labels h(c ( j) ; z ( j) ) and the true labels l ( j) ( j = 1; � � � ; n). Once training completes, the classifier is deployed to infer prediction on any new unlabeled data. It is usually assumed that the unlabeled data is drawn from the same population as the training data, i.e., M. Therefore, in prediction, the values of all the attributes other than the label are determined by the same mechanisms as those in M, and meanwhile the classifier acts as a new mechanism for determining the value of the label. We consider Mwith function fL(�) being replaced by classifier h(�) as the causal model of classifier h, denoted by Mh, which is written as

If we apply the classifier on D, we can obtain a new dataset Dh by replacing the original labels with the predicted labels, i.e., Dh = f(c ( j) ; z ( j) ; h(c ( j) ; z ( j) )); j = 1; � � � ; ng. Straightforwardly, Dh can be considered as a sample drawn fromMh.

The discrimination in prediction made by classifier h can be naturally defined as the discrimination in Mh. To this end, we first define a measure of discrimination in M based on the causal relationship specified by M, denoted by DEM called the true discrimination. By adopting the same measure, we denote the discrimination in Mh by DEMh , called the true discrimination in prediction. Then, we denote the approximation of DEM from dataset D by DED, and similarly denote the approximation of DEMh from dataset Dh by DEDh .

Our target is to discover and remove the true discrimination in prediction, i.e., DEMh , based on certain causal measure of discrimination defined on M, i.e., DEM. When calculating DEMh from dataset D, we may encounter disturbances such as the sampling error of D and the misclassification of h. We then need to compute analytic approximation to DEMh . Thus, we define the problem of discovering discrimination in prediction as follows.

Problem 1 (Discover Discrimination in Prediction). Given a causal measure of discrimination defined on M, i.e., DEM, a sample dataset D and a classifier h trained on D, compute analytic approximation to the true discrimination in prediction, i.e., DEMh .

If the true discrimination in prediction is detected according to the approximation, the next step is to remove the discrimination through tweaking the dataset and/or the classifier. Thus, we define the problem of removing discrimination in prediction as follows.

Problem 2 (Remove Discrimination in Prediction). Given DEM, D and h, tweak D and/or h in order to make DEMh be bounded by a user-defined threshold �.

3 Discover Discrimination in Prediction

In the above general problem definitions, DEM can be any reasonable causal measure of discrimination defined on any causal model. However, a concrete analysis of discrimination must rely on specific assumptions regarding the causal measure of discrimination and the causal model. The remaining of the paper is based on following assumptions: (1) M satisfies the Markovian assumption; (2) we consider all causal effects (total e�ect) of C on L as discriminatory; (3) we assume that C has no parent and L has no child. The first assumption is necessary for computing the causal e�ect from the observable probability distributions. The second assumption is because the total causal e�ect is the causal relationship that is easiest to interpret and estimate. We will extend our results to other discrimination definitions such as those in [Zhang et al., 2017; Bonchi et al., 2017] in the future work. The last assumption is to make our theoretical results more concise and can be easily relaxed.

3.1 Causal Measure of Discrimination

We first derive the true discrimination in M. The key of discrimination is a counterfactual question: whether the decision of an individual would be di�erent had the individual been of a di�erent protected/non-protected group (e.g., sex, race, age, religion, etc.)? To answer this question, we can perform an intervention on each individual to change the value of protected attribute C and see how label L will change. We consider the di�erence between the expectation of the labels when performing do(c + ) for all individuals and the expectation of the labels when performing do(c � ) for all individuals, and use it as the causal measure of discrimination.

To obtain the above di�erence, note that the causal model is completely specified at the individual level when context U = u is specified. For each individual specified by u, denote the label of individual u by Lc +(u) (resp. Lc �(u)) when C is fixed according to do(c + ) (resp. do(c � )). Then, the di�erence in the label of individual u is given by Lc +(u) � Lc �(u). The expected di�erence of the labels over all individuals is hence given by E[Lc + (u)�Lc � (u)]. Based on this analysis, we obtain the following proposition.

Proposition 1. Given a causal model M, the true discrimination is given by

Proof. The above expectations can be computed as

where the last step is according to Eq. (1). According to Eq. (2), we have

On the other hand, since C has no parent, we have

Thus, we have P(l + jdo(c + )) = P(l + jc + ), leading to E[Lc +(u)] = P(l + jc + ). Similarly we can prove E[Lc �(u)] = P(l + jc � ). Hence, the proposition is proven. �

Interestingly, the obtained discrimination causal measure is the same as the classic statistical discrimination metric risk di�erence, which is widely used as the non-discrimination constraint in discrimination-aware learning [Romei and Ruggieri, 2014]. Our analysis can help understand the assumptions and scenarios in which the risk di�erence applies.

Given dataset D, we approximate DEM using the maximum likelihood estimation, denoted by DED as shown below.

Proposition 2. Given a dataset D, the discrimination in D is given by

where

with ˆP(�) being the conditional frequency in D.

Given a classifier h : C�Z ! L, denote the predicted labels by ˜L. By adopting the same causal measure of discrimination of DEM, we obtain DEMh shown as follows.

Proposition 3. Given a causal model M and a classifier h, the true discrimination in prediction is given by

where P(˜ l + jc + ) (resp. P(˜ l + jc � )) is the probability of the positive predicted labels for the data with C = c + (resp. C = c � ).

We similarly define DEDh as the maximum likelihood estimation of DEMh .

Proposition 4. Given a dataset D and a classifier h trained on D, the discrimination in Dh is given by

where

with I[�] the indicator function.

3.2 Bounding Discrimination in Prediction

To approximate DEMh from D, sampling error cannot be avoided since D is only a subset of the entire population. Although exact measurement of sampling error is generally not feasible as M is unknown, it can be probabilistically bounded. In the following we first bound the di�erence between DEM and its approximation DED, and then extend the result to the di�erence between DEMh and its approximation DEDh .

Proposition 5. Given a causal model M and a sample dataset D with size of n, the probability of the di�erence between DEM and DED no larger than t is bounded by

where n + and n � (n + +n � = n) are the numbers of individuals with c + and c � in D.

Proof. By definition of DEM and DED we have

Denoting by l (+j) the label of the jth individual in D with C = c + , we can write ˆP(l + jc + ) as

where indicators I[l (+j) =l + ] ( j = 1 � � � n + ) can be considered as independent random variables bounded by the interval [0; 1]. Note that E[ ˆP(l + jc + )] = P(l + jc + ). According to the Hoe�ding's inequality [Murphy, 2012], we have

Similarly, we have P �� � �P(l + jc � ) � ˆP(l + jc � ) � � � � t � � 2e �2n � t 2 . Therefore, we have

where the last line is by substituting x with p n � p n + + p n � t. �

For extending Proposition 5 to Proposition 6, the di�erence is that, since h is a classifier depending on training data D, indicators I[h(c (+ j) ;z (+ j) )=l + ] cannot be considered as independent. Thus, the Hoe�ding's inequality cannot be directly applied and a uniform bound for all hypotheses in H is needed.

Proposition 6. Given a causal model M, a sample dataset D, and a classifier h : C � Z ! L from hypothesis space H, the probability of the distance between DEMh and DEDh no larger than t is bounded by

where

with d being the VC dimension of H.

Proof. According to the definitions of DEMh and DEDh ,

Similar to the proof of Proposition 5, we treat ˆP(˜ l + jc + ) as the mean of indicators I[h(c (+j) ;z (+j) )=l + ] ( j = 1 � � � n + ). According to the generalization bound in statistical learning theory [Vapnik, 1998], if H is finite we have

where jHj is the size of H. If H is infinite we have

where d is the VC dimension of H. Then the proposition can be proven similarly to Eq. (6). �

Proposition 6 provides an approximation of DEMh from DEDh . However, since pre-process methods deal with the training data, it is imperative to further link DEMh with DED. Next, we give the relation between DEDh and DED in terms of a bias metric that we refer to as the the error bias.

Definition 2 (Error Bias). For any classifier h trained on a training dataset D, the error bias is given by

where " + 1 ; " � 1 are the percentages of false positives on data with C = c + and C = c � respectively, and " + 2 ; " � 2 are the percentages false negatives on data with C = c + and C = c � respectively.

Proposition 7. For any classifier h that is trained on D, we have

Proof. By definition, " + 1 is given by

which can be rewritten as

Similarly, " + 2 is given by

Subtracting " + 2 from " + 1 , we obtain

which is equivalent to

Similarly for data with C = c � , we have

On the other hand, according to Eq. (4) and (5) we have

Using Proposition 7, we rewrite Propositions 6 to Theorem 1 that is easier to interpret and utilize in practice.

Theorem 1. Given a causal model M, a sample dataset D and a classifier h trained on D, DEMh is bounded by

where the meaning of �(t) is same as that in Proposition 6.

Theorem 1 gives a criterion of non-discrimination in prediction that incorporates both the discrimination in the training data and the error bias of the classifier, i.e., � � �DED + "h;D � � � being bounded by a threshold �. It shows that either given a discrimination-free dataset D, i.e., jDEDj � �, or a "balanced" classifier, i.e., � � �"h;D � � � � �, we cannot guarantee nondiscriminatory prediction. Instead, it requires to ensure that the sum of DED and "h;D is within the threshold.

4 Remove Discrimination in Prediction

This section solves the problem of removing discrimination in prediction: if criterion � � �DED + "h;D � � � � � is not satisfied for a classifier, how can we meet the criterion through modifying the training data and tweaking the classifier? Denote by D � a dataset obtained by modifying D, and by h � a new classifier trained on D � . Note that when the training data is modified, the error bias of the classifier built on it will also change. Thus, it is di�cult to perform the training data modification and the classifier tweaking simultaneous. We propose a framework for modifying the training data and the classifier in two successive phases, as summarized in Algorithm 1.

Algorithm 1: Two-phase framework.

• 1 If � � �DED+ "h;D � � � � �, we are done. Otherwise, modify the labels in the training dataset D to obtain a modified dataset D � such that jDED � j � �.
• 2 Train a classifier h � on D � . If � � �DED � + "h � ;D � � � � � �, we are done. Otherwise, tweak classifier h � to meet the above requirement.

In the first phase, we modify D to remove the discrimination it contains. The modified dataset D � can be considered as being generated by a causal model M � that is different fromMwith respect to the modification. Note that if � � �DED � + "h � ;D � � � � � � is achieved, Theorem 1 ensures the bound of discrimination for M � h � , i.e., the discrimination of h � performed onM � , but not for Mh � , i.e., the discrimination of h � performed on the original population. If we only modify the label of D, M � can be written as

Then, the causal model of any classifier h � trained on D � and performed onM � is given by

which is equivalent toMh � . Thus, non-discrimination inM � h � also means non-discrimination in Mh � . On the other hand, if we modify attributes other than L, since the new unlabeled data is drawn from the original population, Mh � is inconsistent with M � h � . As a result, the non-discrimination result of the training data cannot be applied to the prediction of the new data. Therefore, we have the following corollary derived from Theorem 1.

Corollary 1. Let D � be a modified dataset fromD, and h � be a new classifier trained on D � . If D � only modifies the labels, then � � �DED � + "h � ;D � � � � � � is a su�cient condition to achieve

where the meaning of �(t) is same as that in Proposition 6.

In the second phase, we make modifications to h � to reduce the error bias. Although dealing with a di�erent fairness criterion, existing methods for balancing the misclassification rates (e.g., [Hardt et al., 2016]) can be easily extended for solving this problem. For the purpose of evaluating the correctness of our theoretical results, here we use a simple algorithm RandomFlip for reducing the error bias that can be applied to any classifier. After the classifier makes a prediction, RandomFlip randomly flips the predicted label with certain probability p + (resp. p � ) if the individual has C = c + (resp. C = c � ) to achieve � � �DED � + "h � ;D � � � � � �, where p + can be computed according to the prediction of h � over D � . Denoting � = �� jDED � j, it su�ces to make j" + 1 �" + 2 j � �=2 and j" � 1 � " � 2 )j � �=2. Assume that " + 1 � " + 2 > �=2, then it can be easily shown that p + should satisfy (" + 1 � " + 2 � �=2) � n + fp+tp � � p + � (" + 1 � " + 2 ) � n + fp+tp � . Similar result can be obtained if " + 1 � " + 2 < ��=2.

5 Empirical Evaluation

5.1 Experimental Setup

In this section, we conduct experiments to evaluate our theoretical results. For simulating a population, we adopt a semisynthetic data generation method. We first learn a causal model M for a real dataset, the Adult dataset [Lichman, 2013], and treat it as the ground-truth. We then generate the training data D based on M. The causal model is built using the open-source software Tetrad [Glymour and others, 2004].

The Adult dataset consists of 11 attributes including age, education, sex, occupation, income, etc. Due to the sparse data issue, we binarize each attribute's domain values into two classes to reduce the domain sizes. We treat sex as C and income as L. The discrimination is measured as 0:13 in M, i.e., DEM = 0:13. Based on the underlying distribution of M, we generate a number of training data sets with di�erent sample sizes.

When constructing discrimination-free classifiers using the two-phase framework, we select one representative data modifying algorithm that only modifies L, the Massaging (MSG) algorithm [Kamiran and Calders, 2009a]. For other algorithms, we will evaluate their performance in preserving data utility in the future work. For comparison, we also include an algorithm that modifies Z, the Disparate Impact Removal (DI) algorithm [Adler et al., 2016]. The proposed RandomFlip algorithm is used for tweaking the classifier. We assume a discrimination threshold � = 0:05, i.e., we want to ensure that the discrimination in prediction is not larger than 0.05.

5.2 Experiment Results

We first measure the discrimination in each training data set, i.e., DED. Then, we learn the classifier h from the training data where two classifiers, decision tree (DT) and support vector machine (SVM) are used. By replacing the labels in the training data with the labels predicted by the classifier, we obtain Dh whose discrimination is measured as DEDh . Finally, we measure the discrimination in prediction, i.e., DEMh according to Proposition 3. For each sample size, we repeat the experiments 100 times by randomly generating 100 sets of training data. We report the average and variance of each measured discrimination.

The results are shown in Table 2. As expected, with the increase of the sample size, the di�erence between DEM and DED decreases as shown by the variance. Since DED > 0:05, the training data contains discrimination. As a result, both the training data with predicted labels, i.e., Dh, and the prediction, i.e., Mh, also contain discrimination.

To show the e�ectiveness of the two-phase framework, we first apply MSG to completely remove the discrimination in the above training data, obtaining the modified training data D � . Then, a decision tree h � is built on D � , and the RandomFlip algorithm is executed to tweak the classifier so that the error bias is less than 0.05, i.e., � � �"h � ;D � � � � � 0:05. Finally, we measure the discrimination in Mh � . For comparison, the same process is also performed for DI. The results are shown in Table 3. By using the two-phase framework, discrimination is removed from the training data as shown by DED � , and more importantly, removed from the prediction as shown by DEMh� . We also see that, if the classifier tweaking is not performed, the prediction still contains discrimination. However, for DI, even when the discrimination is removed from the training data, and the error bias in the classifier is also removed, there still exists discrimination in prediction. These results are consistent with our theoretical conclusions.

6 Conclusions

In this paper, we addressed the limitation of the pre-process methods that there is no guarantee about the discrimination in prediction. Our theoretical results show that: (1) only removing discrimination from the training data cannot ensure nondiscrimination in prediction for any classifier; and (2) when removing discrimination from the training data, one should only modify the labels in order to obtain a non-discrimination guarantee. Based on the results, we developed a two-phase framework for constructing a discrimination-free classifier with a theoretical guarantee. The experiments adopting a semi-synthetic data generation method demonstrate the theoretical results and show the e�ectiveness of our two-phase framework.

Acknowledgments

This work was supported in part by NSF 1646654.