Year: 2020

Abstract:
Machine learning has become more important in real-life decision-making but people are concerned about the ethical problems it may bring when used improperly. Recent work brings the discussion of machine learning fairness into the causal framework and elaborates on the concept of Counterfactual Fairness. In this paper, we develop the Fair Learning through dAta Preprocessing (FLAP) algorithm to learn counterfactually fair decisions from biased training data and formalize the conditions where different data preprocessing procedures should be used to guarantee counterfactual fairness. We also show that Counterfactual Fairness is equivalent to the conditional independence of the decisions and the sensitive attributes given the processed non-sensitive attributes, which enables us to detect discrimination in the original decision using the processed data. The performance of our algorithm is illustrated using simulated data and real-world applications.

heading: 1 INTRODUCTION
text: The rapid popularization of machine learning methods and the growing availability of personal data have enabled decision-makers from various fields such as graduate admission (Waters & Miikkulainen, 2014), hiring (Ajunwa et al., 2016), credit scoring (Thomas, 2009), and criminal justice (Brennan et al., 2009) to make data-driven decisions efficiently. However, the community and the authorities have also raised concern that these automatically learned decisions may inherit the historical bias and discrimination from the training data and would cause serious ethical problems when used in practice (Nature Editorial, 2016; Angwin & Larson, 2016; Dwoskin, 2015; Executive Office of the President et al., 2016).
Consider a training dataset D consisting of sensitive attributes S such as gender and race, nonsensitive attributes A and decisions Y . If the historical decisions Y are not fair across the sensitive groups, a powerful machine learning algorithm will capture this pattern of bias and yield learned decisions Ŷ that mimic the preference of the historical decision-maker, and it is often the case that the more discriminative an algorithm is, the more discriminatory it might be.
While researchers agree that methods should be developed to learn fair decisions, opinions vary on the quantitative definition of fairness. In general, researchers use either the observational or counterfactual approaches to formalize the concept of fairness. The observational approaches often describe fairness with metrics of the observable data and predicted decisions (Hardt et al., 2016; Chouldechova, 2017; Yeom & Tschantz, 2018). For example, Demographic Parity (DP) or Group Fairness (Zemel et al., 2013; Khademi et al., 2019) considers the learned decision Ŷ to be fair if it has the same distribution for different sensitive groups, i.e., P (Ŷ |S = s) = P (Ŷ |S = s′). The Individual Fairness (IF) definition (Dwork et al., 2012) views fairness as treating similar individuals similarly, which means the distance between Ŷ (si, ai) and Ŷ (sj , aj) should be small if individuals i and j are similar.
The other branch of fairness and/or discrimination definitions are built upon the causal framework of Pearl (2009a), such as direct/indirect discrimination (Zhang et al., 2017; Nabi & Shpitser, 2018), path-specific effect (Wu et al., 2019b), counterfactual error rate (Zhang & Bareinboim, 2018a) and counterfactual fairness (Kusner et al., 2017; Wang et al., 2019; Wu et al., 2019a). These definitions often involve the notion of counterfactuals, which means what the attributes or decision would be
if an individual were in a different sensitive group. With the help of the potential outcome concept, the measuring of fairness is no longer restricted to the observable quantities (Kilbertus et al., 2017; Zhang & Bareinboim, 2018b). For example, the Equal Opportunity (EO) definition Wang et al. (2019) has the same idea as IF but it can directly compare the actual and counterfactual decisions of the same individual instead of the actual decisions of two similar individuals. The Counterfactual Fairness (CF) definition (Kusner et al., 2017) or equivalently, the Affirmative Action (AA) definition (Wang et al., 2019) goes one step further than EO and derives the counterfactual decisions from the counterfactual non-sensitive attributes. We adopt CF as our definition of fairness and it is formally described in Section 2. We believe causal reasoning is the key to fair decisions as DeDeo (2014) pointed out that even the most successful algorithms would fail to make fair judgments due to the lack of causal reasoning ability.
For the observational definitions, fair decisions can be learned by solving optimization problems, either adding the fairness condition as a constraint (Dwork et al., 2012) or directly optimize the fairness metric as an object (Zemel et al., 2013). When using the counterfactual definitions, however, an approximation of the causal model or the counterfactuals is often needed since the counterfactuals are unobservable. In the FairLearning algorithm proposed by Kusner et al. (2017), the unobserved parts of the graphical causal model are sampled using the Markov chain Monte Carlo method. Then they use only the non-descendants of S to learn the decision, which ensures CF but will have a low prediction accuracy. In Wang et al. (2019), the counterfactual of A had S been s′ is imputed as the sum of the counterfactual group mean E(A|S = s′) and the residuals from the original group A− E(A|S = s). As we discuss later, this approach would only work when a strong assumption of the relationship between A and S is satisfied.

heading: 1.1 CONTRIBUTIONS
text: We develop the Fair Learning through dAta Preprocessing (FLAP) algorithm to learn counterfactually fair decisions from biased training data. While current literature is vague about the assumptions needed for their algorithms to achieve fairness, we formalize the weak and strong conditions where different data preprocessing procedures should be used to guarantee CF and prove the results under the causal framework of Pearl (2009a). We show that our algorithm can predict fairer decisions with similar accuracy when compared with other counterfactual fair learning algorithms using three simulated datasets and three real-world applications, including the loan approval data from a fintech company, the adult income data, and the COMPAS recidivism data.
On the other hand, the processed data also enable us to detect discrimination in the original decision. We prove that CF is equivalent to the conditional independence of the decisions and the sensitive attributes given the processed non-sensitive attributes under certain conditions. Therefore any wellestablished conditional independence tests can be used to test CF with the processed data. To our knowledge, it is the first time that a formal statistical test for CF is proposed. We illustrate the idea using the Conditional Distance Correlation test (Wang et al., 2015) in our simulation and test the fairness of the decisions in the loan approval data using a parametric test.

heading: 2 CAUSAL MODEL AND COUNTERFACTUAL FAIRNESS
text: For the discussion below, we consider the sensitive attributes S ∈ S to be categorical, which is a reasonable restriction for the commonly discussed sensitive information such as race and gender. The non-sensitive attributes A ∈ A ⊆ Rd, and the decision Y is binary as admit or not in graduate admission, hire or not in the hiring process, approve or not in loan assessment.
To bring the discussion of fairness into the framework of causal inference, we begin by constructing the Structural Causal Model (SCM) for the data. As described in Pearl (2009b), an SCMM consists of a set of exogenous variables U , a set of endogenous variables V , and F , a set of functions that assign value to each endogenous variable given its parents in V and the exogenous variables U . In our case (Figure 1), we consider V = {S,A, Y, Ŷ }, where {S,A, Y } are the observed data and Ŷ is the prediction of Y we made based on S and A. The only exogenous variable affecting Ŷ is a Uniform(0, 1) random variable UŶ so that we can conveniently express the value of Ŷ with a structural equation. We assume that US , UA, and UY , which are the exogenous variables that affect S, A, and Y respectively, are independent of each other. The structural equations on the right side of Figure 1 are described with the functions in F , one for each component in V . Here we express fŶ as an indicator function so that Ŷ is a Bernoulli random variable that takes value one with probability p(S,A). In general, p(s, a) could be any function that maps S × A to [0, 1], but we are more interested in such functions that will result in a fair decision, more details of which will be discussed in Section 3. It can be seen that the subset of exogenous variables {US , UA, UY } characterize everything we should know about a unit. Any two units with the same realization will have the same behavior and result irrespective of the other differences in their identities.
Here we give a simplified loan approval model as a running example to help understand the SCM we considered. Example 1. A bank asks each loan applicant for her/his race S and annual income A to decide to approve the application (Y = 1) or not (Y = 0). There are two races in the population of the applicants, S = 1 represents the advantageous group, and S = 0 for the disadvantageous one. Let US ∼ Uniform(0, 1), we generate S = 1{US < 0.7}. The annual income is log-normally distributed for each race group and its scale and location parameters may depend on race:
A = c1 exp{c2 + λaS + c3σSaUA}, where UA is a standard normal random variable, c1, c3 > 0, and c2 are constants that affect the median and spread of the population income, λa decides the difference in mean log income between the two race groups, and σa > 0 determines the standard deviation ratio of the log incomes. The decision by the bank can be simulated from a logistic model:
Y = 1{UY < expit(β0 + βaA+ βsS)}, where UY ∼ Uniform(0, 1) and expit(u) = (1 + e−u)−1.
In this example, βs characterizes the direct effect of the sensitive attribute on the decision: when βs > 0, the applications from the advantageous group are more likely to be approved by the bank when holding the income fixed. On the other hand, λa partly describes the indirect effect because when both λa and βa are positive, the advantageous group will have a higher income than the other group on average and thus be favored by the bank even if βs = 0. It is worth noting that, apart from the difference in the mean, the difference in higher moments could also cause unfairness indirectly as alluded to in Fuster et al. (2018). In general, if there are any differences in the distribution of A across the categories in S, the decision based on A might be unfair. However, the indirect effect caused by the differences in the higher moments of A could be case dependent and thus harder to interpret. In our case, σa > 1 will lead to a higher average income and hence higher approval probability on average for the advantageous group since the income distribution is right-skewed.
With the SCM in hand, we are ready to define the causal quantity we are interested in. Since most sensitive attributes, such as gender and race, cannot be altered in experiments, we will look into the counterfactuals, namely, what the results Y would be had S been different from the observed facts. This quantity is expressed as Ys(U) had S been s for a random unit with exogenous variables U sampled from the population. Define Ms to be the modified SCM from M (Figure 1) with the equation for S replaced with S = s. Then for any realization U = u, the unit level counterfactuals Ys(u) can be calculated from Ms. Similarly, we can define Ŷs(U) and Ŷs(u) as the counterfactual predicted decision and its realization. The counterfactual fairness can then be defined on both the decision and the prediction based on the counterfactual result. Here we denote Y as a placeholder for either Y or Ŷ . Definition 1. Counterfactual Fairness. Given a new pair of attributes (s∗, a∗), a (predicted) decision Y is counterfactually fair if for any s′ ∈ S,
Ys′(U)|{S = s∗, A = a∗} d = Ys∗(U)|{S = s∗, A = a∗}.
In other words, the conditional distribution of the counterfactual result should not depend on the sensitive attributes. It should be noted that there are two stages in evaluating the conditional counterfactuals. The first is updating the conditional distribution ofU . Take the decision Y from Example 1, if s∗ = 0, then US |{S = s∗, A = a∗} is from Uniform(0.7, 1) and UA|{S = s∗, A = a∗} is a constant (log(a∗/c1)− c2)/c3, but UY |{S = s∗, A = a∗} is still a Uniform(0, 1) random variable since UY is independent of S and A from the SCM. The next stage is deriving the conditional distribution of the counterfactuals from the structural equations of Ms and the conditional distribution of U . Continuing with our example, Y1(U)|{S = 0, A = a∗} would be equal in distribution to
fY (1, fA(1, UA), UY )|{S = 0, A = a∗} d =fY (1, fA(1, (log(a
∗/c1)− c2)/c3), UY ) d =1{UY < expit(β0 + βac1(a∗/c1)σa exp{λa + (1− σa)c2}+ βs)}
and Y0(U)|{S = 0, A = a∗} d = 1{UY < expit(β0 + βaa∗)}. Thus the bank’s decision Y would be counterfactually fair if σa = 1, λa = 0 and βs = 0.

heading: 3 PREPROCESSING, LEARNING, AND TESTING
text: Define a preprocessing procedure PD(s, a) : S × A → A′ to be a function that maps attributes (s, a) to the processed attributes a′ given the training dataD. Here we consider two such procedures. Denote Pn(S = s) as the empirical p.m.f. of S and En(A|S = s) as the empirical conditional mean of A given S learned from data D. Definition 2 (Orthogonalization). An orthogonalization procedurePDO is a preprocessing procedure such that
PDO (s∗, a∗) = ∑ s â(s)Pn(S = s),
where â(s) = a∗ − En(A|S = s∗) + En(A|S = s),∀s ∈ S.
It is easy to see thatPDO (s∗, a∗) = a∗−En(A|S = s∗)+En(A) is a one-to-one function of a∗ for any fixed s∗. Denote F̂js(x) = Pn(Aj ≤ x|S = s) as the empirical marginal cumulative distribution function (CDF) of the jth element of the non-sensitive attributes given the sensitive attribute S = s. Define its inverse as
F̂−1js (z) = inf{x : Pn(Aj ≤ x|S = s) ≥ z}. (3.1)
Definition 3 (Marginal Distribution Mapping). A marginal distribution mapping PDM is a preprocessing procedure such that
PDM (s∗, a∗) = ∑ s â(s)Pn(S = s),
where the jth element of â(s) is [â(s)]j = F̂−1js (F̂js∗([a ∗]j) for j = 1, · · · , d.
Let P , PO, and PM denote the population level preprocessing procedure corresponding to PD, PDO , andPDM , respectively. It is obvious thatPO(s∗, a∗) = a∗−E(A|S = s∗)+E(A) is still a one-to-one function of a∗ for any fixed s∗, and the jth element of PM (s∗, a∗) is
[PM (s∗, a∗)]j = ∑ s F−1js (Fjs∗([a ∗]j)P(S = s),
where Fjs is the marginal CDF of the jth element of A given S = s and F−1js is defined similarly to (3.1) but replacing Pn with P. It can be seen that if Aj is a discrete variable, then F−1js (Fjs∗(x)) is strictly increasing for s = s∗; and if Aj is a continuous variable, then F−1js (Fjs∗(x)) may not be strictly increasing when Fjs∗(x) is constant on some interval of x. Therefore PM (s∗, a∗) is only a one-to-one function of a∗ for any fixed s∗ when the marginal CDF of each continuous element in A given S = s∗ is strictly increasing.

heading: 3.1 FAIR LEARNING ALGORITHM
text: Besides preprocessing procedures, we also have different choices of learners. A Fairness-ThroughUnawareness (FTU) predictor fFTU (a) only uses the non-sensitive attributes A to predict the conditional mean of Y . A Machine Learning predictor fML(s, a) uses both the sensitive and non-sensitive attributes to predict E(Y |S,A). An Averaged Machine Learning (AML) predictor fAML(a) = ∑ s fML(s, a)Pn(S = s)ds. Note that we still need to train the ML predictor to obtain the AML predictor, but it only needs the non-sensitive attributes as its input when making a prediction since the sensitive attributes are averaged out. Algorithm 1 could use any learner f ∈ {f : A → [0, 1]} to learn the decisions from the processed data, and we would consider the FTU and AML learners in our numerical studies.
Algorithm 1: Fair Learning through dAta Preprocessing (FLAP) Input: Training data D, preprocessing procedure PD, learner f , test attributes (s, a).
1 for (si, ai, yi) in D do 2 a′i = PD(si, ai) 3 end 4 Create the processed data D′ = {(si, a′i, yi)}ni=1 5 Learn predictor f from D′ 6 Calculate a′ = PD(s, a) 7 Draw Ŷ from Bernoulli(f(a′))
Output: Ŷ
Apart from the structural assumptions made in Figure 1, extra conditions of the structural equation fA(s, uA) must be satisfied for the preprocessing method to work.
Condition 1 (Strong non-sensitive). The partial derivative ∂∂uA fA(s, uA) does not involve s.
Condition 2 (Weak non-sensitive). The sign of ∂∂uA fAj (s, uA) does not change with s for all uA and all j = 1, · · · , d.
These two conditions describe the relationship between the sensitive and non-sensitive attributes. Condition 2 is weaker than Condition 1. For example, an additive model fA(s, uA) = β0 + β1s + β2uA satisfies both conditions, while an interaction model fA(s, uA) = β0 + β1s+ β2uA + β3suA does not satisfy Condition 1 but will satisfy Condition 2 if β2 + β3s is greater than (or less than, or equal to) zero for all s. In our running example, ∂∂uA fA(s, uA) = c1c3σ s a exp{c2+λas+c3σsauA} > 0 for s = 0, 1. So it meets Condition 2 but not Condition 1. We prove in the following theorem that these conditions, together with the SCM, are sufficient for Algorithm 1 to generate counterfactually fair decisions.
Theorem 1. Let Ŷ be the output from Algorithm 1, i.e., 1{UŶ < f(PD(s, a))}.
1. If the procedure PDO is adopted, Ŷ is counterfactually fair under Condition 1.
2. If the procedure PDM is adopted, Ŷ is counterfactually fair under Condition 2.
We prove Theorem 1 in Appendix A. The intuition is that the FLAP algorithm learns the decision from processed data only, and the processed data contain no sensitive information since the preprocessing procedure can remove A’s dependence on S under the non-sensitive condition.

heading: 3.2 TEST FOR COUNTERFACTUAL FAIRNESS
text: Data preprocessing not only allows us to learn a counterfactually fair decision but also enables us to test if the decisions made in the original data are fair. When Condition 1 holds, we can use the data processed by the orthogonalization procedure to test fairness. When the strong condition does not hold but Condition 2 is satisfied, we need an extra condition to utilize the marginal distribution mapping procedure for fairness testing.
Condition 3. The conditional marginal CDF Fjs(x) is strictly increasing for all such j that Aj is continuous and all s ∈ S.
In other words, each non-sensitive attributes Aj should be either a discrete random variable or a continuous one with non-zero density on R. This condition ensures that PM (s∗, a∗) is a one-to-one function as discussed earlier. With these conditions, we can establish the equivalence between CF and the conditional independence of decision and sensitive information given the processed nonsensitive information. Theorem 2. Consider the original decision Y :
1. Under Condition 1, Y is counterfactually fair if and only if Y⊥S|PO(S,A).
2. Under Conditions 2 and 3, Y is counterfactually fair if and only if Y⊥S|PM (S,A).
Its proof is in Appendix A. Theorem 2 allows us to test CF using any well-established conditional independence test. In practice, given a decision dataset D = (si, ai, yi)ni=1, we can obtain the empirical processed non-sensitive attributes PD(si, ai) and test if Y⊥S|PD(S,A). If the p-value of the test is small enough for us to reject the conditional independence hypothesis, then the original decision is probably biased and algorithms such as FLAP should be used to learn fair decisions.

heading: 4 NUMERICAL STUDIES
text: In this section, we compare the decisions made by different algorithms in terms of fairness and accuracy using simulated and real data, and also investigate the empirical performance of the fairness test using simulated data with small sample sizes. We consider three cases for generating the simulation data. The first one is Example 1 and the second one is a multivariate extension of it where we introduce one more sensitive group and include the education years of the loan applicants as another non-sensitive attribute and let their annual income depend on it. The third example is a replica of the admission example constructed by Wang et al. (2019). The details of these examples and the parameters chosen in the simulation are presented in Appendix B.
As discussed before, Condition 2 is satisfied in Example 1 but Condition 1 is not. Moreover, both Examples 2 and 3 do not satisfy either condition in general due to the cutoff in the value of their non-sensitive attributes, and hence neither of the proposed preprocessing methods can achieve CF in theory. However, the weaker Condition 2 will hold in Example 2 when the mean education years of the three sensitive groups are the same, in which case the marginal distribution mapping method should work.

heading: 4.1 FAIRNESS EVALUATION
text: We compare our FLAP algorithm with
1. ML: the machine learning method using both sensitive and non-sensitive attributes without preprocessing, which is a logistic regression of Y on S and A;
2. FTU: the Fairness-Through-Unawareness method which fits a logistic model of Y on nonsensitive attributes A alone without preprocessing;
3. FL: the FairLearning algorithm proposed by Kusner et al. (2017); 4. AA: the Affirmative Action algorithm proposed by Wang et al. (2019).
All these methods can output a predicted score p given the training data D and test attributes (s, a), denoted p(s, a;D) and draw the random decision Ŷ from Bernoulli(p(s, a;D)). For ML method, p(s, a;D) = fML(s, a); for FTU method, that is fFTU (a). We denote the predicted scores of the FairLearning and AA algorithms as fFL(s, a;D) and fAA(s, a;D), respectively. For our FLAP method, we use the marginal distribution mapping procedure and try both the AML and the FTU learners described in Section 3 and name the methods as FLAP-1 and FLAP-2. Their predicted scores are fAML(PDM (s, a)) and fFTU (PDM (s, a)), respectively. We mainly use the Mean Absolute Error (MAE) of the predicted score on the test set to measure the prediction performance, and also include the area under the ROC curve and average precision of the prediction in Appendix B for
completeness. All these metrics show similar results about the prediction performance. The metric for measuring the counterfactual fairness (CF-metric) is defined as
max r,t∈S
1
Ntest Ntest∑ i=1 |p(r, âDM (r, si, ai);D)− p(t, âDM (t, si, ai);D)|,
where âDM (s, s ∗, a∗) is defined as â(s) in Definition 3. Note that the CF-metric should be zero when decisions are CF under Condition 2. In real world applications where the condition cannot be verified, a CF decision is not guaranteed to have zero CF-metric, although we expect the CFmetric to be lower for fairer decisions in general. This definition is different from the AA-metric proposed by Wang et al. (2019) in two folds. First, it allows us to consider more than two sensitive groups by taking the maximum of the pairwise difference of predicted scores, but it reduces to the AA-metric for two sensitive groups. Second, we use the marginal distribution mapping method to compute the counterfactual non-sensitive attributes âDM (s, s
∗, a∗) had the unit been in a different sensitive group s. This ensures that all the derived counterfactual attributes are within the range of observed attribute values. In comparison, Wang et al. (2019) use the orthogonalization method to compute the counterfactual attributes and thus a female student having test score 0.98 would have a counterfactual score of 1.48 had she been a male if the male mean test score is 0.5 higher than female. This out-of-range counterfactual score is unreasonable and problematic when being used as the input of the score prediction function p.
For Example 1, we hold other parameters fixed while increase σa from 1 to 2.8 to see how the difference in the variation of the non-sensitive attribute between sensitive groups affects fairness. As expected, the AA algorithm which essentially uses the orthogonalization method cannot achieve CF since Condition 1 is not met. However, both FLAP algorithms’ CF-metrics are zero when using the marginal distribution mapping preprocessing (Figure 2a).
Wang et al. (2019) showed that the AA algorithm can achieve zero AA-metric in Example 3, but it does not satisfy either of the non-sensitive conditions for achieving CF. As shown in Figure 2b, all algorithms we consider cannot achieve CF, but the FLAP algorithms still have the lowest CF-metric. The results of Example 2 are shown in Appendix B and there is no significant difference between the MAE of the AA and FLAP algorithms in all examples. In general, we expect fairer predictions to have higher MAEs since they correct the discriminatory bias of the original decisions.

heading: 4.2 FAIRNESS TEST
text: The Conditional Distance Correlation (CDC) test (Wang et al., 2015) is a well-established nonparametric test for conditional independence. We use it here to illustrate the performance of the fairness test with the three simulated examples. For each example, we use different combinations of parameters to obtain simulated datasets with different fairness levels, which are measured by the CFmetric. A CDC test with a significance level of 0.05 is then conducted to test if Y⊥S|PD(S,A) for each dataset. The simulation-test process is repeated 1000 times for each combination of parameters to estimate the power of the test, namely the probability of rejecting the null hypothesis that the decisions are counterfactually fair. The results are summarized in Figure 3.
When the decisions are generated fair, which are shown as the points with CF-metrics equal to zero, the type I error rate is around 0.05 for all examples. The power of the test grows as we make the decisions more unfair, or increase the sample size.

heading: 5 REAL DATA ANALYSIS
text: We apply our methods to a loan application dataset from a fintech company, the adult income dataset from UCI Machine Learning Repository1 and the COMPAS recidivism data from ProPublica2 (Angwin & Larson, 2016). Here we present our analysis of the loan application data, and the results from the other two publicly available datasets are shown in Appendix C since the conclusions are similar.
In the loan application case, the fintech lender aims to provide short-term credit to young salaried professionals by using their mobile and social footprints to determine their creditworthiness even when a credit history may not be available. To get a loan, a customer has to download the lending app, submit all the requisite details and documentation, and give permission to the lender to gather additional information from her/his smartphone, such as the number of apps, number of calls, and SMSs, and number of contacts and social connections. We obtained data from the lending firm for all loans granted from February 2016 to November 2018. The decisions Y are whether or not the lender approves the loan applications. The attributes are applicants’ gender, age, salary, and other information collected from their smartphones. Both gender and age are regarded as sensitive information here and we find that the decisions are made in favor of the senior and female applicants. Since we can only deal with categorical sensitive attributes, we divide the applicants into two age groups by the lower quartile of the age distribution and create a categorical variable S ∈ {0, 1, 2, 3} to denote the group of the applicants: female younger than 28; male younger than 28; female older than 28; and male older than 28. The effective sample size after removing missing values is 203,656.
Non-parametric conditional independence tests will not be efficient for this real case due to the large sample size. Therefore we test the conditional independence of Y and S given PDM (S,A) by fitting a simple logistic model for Y with S and PDM (S,A) as the explanatory variables and testing if the coefficient of S is significantly different from zero. The p-value of the F-test is almost zero and indicates that the decisions are unfair for applicants in different groups. When other attributes are fixed to their means, the predicted approval probabilities of the four groups from the logistic model are 0.924 (young female), 0.899 (young male), 0.948 (senior female), and 0.946 (senior male), also indicating that the decisions are most in favor of the senior and female applicants.
We then separate the data into a training set of 193,656 samples and a test set of 10,000 samples. The training dataset is used to learn the decisions with different algorithms and the test dataset is used to evaluate the CF-metric and MAE. The results are summarized in Table 1. Our FLAP algorithms have lower CF-metrics compared with other algorithms and their MAEs are only greater than the ML method. Among the FLAP algorithms, the two using the marginal distribution mapping preprocessing procedure have better CF-metric and similar MAE. The FLAP algorithm using the FTU learner (FLAP-2) performs slightly better than the one using the AML learner (FLAP-1). Note that in real-world applications, fairer decisions may not have higher MAEs as expected in the simulation studies because we do not have access to all the variables possessed by the original decision-maker. When the original decisions depend on additional information, the FLAP and other
1https://archive.ics.uci.edu/ml/machine-learning-databases/adult/ 2https://github.com/propublica/compas-analysis
fair learning methods may yield predictions closer to or further away from the original decisions, and thus leading to lower or higher MAEs.

heading: 6 DISCUSSION
text: We propose two data preprocessing procedures and the FLAP algorithm to make counterfactually fair decisions. The algorithm is general enough so that any learning methods from logistic regression to neural networks can be used, and counterfactual fairness is guaranteed regardless of the learning methods. The orthogonalization procedure is faster and ensures counterfactually fair decisions when the strong non-sensitive condition is met. The marginal distribution mapping procedure is more complex but guarantees fairness under the weaker non-sensitive condition.
We also prove the equivalence between counterfactual fairness and the conditional independence of decisions and sensitive attributes given the processed non-sensitive attributes under the non-sensitive assumptions. We illustrate that the CDC test is reliable for testing counterfactual fairness when the sample size is small. When the size gets bigger, however, we need a more efficient testing method for the fairness test.
It is well understood but still worth noting that causal inference comes with strong assumptions, such as the SCM and the non-sensitive conditions in our case. Moreover, these assumptions are often unverifiable in general, although we may test some of them when only considering a restricted class of models. As the saying goes, “all models are wrong, but some are useful”. The FLAP method may require unverifiable assumptions in practice, but we make it general enough and easy to follow in the hope that this would encourage decision-makers to address the fairness issue with its help.

heading: A PROOF OF MAIN RESULTS
text: A.1 PROOF OF THEOREM 1
Proof. We prove the theorem for a general class of learners {f : A → [0, 1]} that only take the non-sensitive attribute a as the input. Clearly, both fFTU or fAML belong to this class. We follow the Abduction-Action-Prediction steps in Theorem 7.1.7 Pearl (2009b) to evaluate the conditional expectation of Ŷs′(U) given the evidence S = s∗, A = a∗,
E(Ŷs′(U)|S = s∗, A = a∗) = ∫ f(PD(s′, fA(s′, u)))pUA|S,A(u|S = s ∗, A = a∗)du,
where pUA|S,A(u|s∗, a∗) denotes the conditional density of UA given S = s∗ and A = a∗. If PD(s′, fA(s′, u)) does not depend on s′, so will E(Ŷs′(U)|S = s∗, A = a∗) and we will have
E(Ŷs′(U)|S = s∗, A = a∗) = E(Ŷs∗(U)|S = s∗, A = a∗). Note that PD(s′, fA(s′, u)) = ∑ s â(s)Pn(S = s) for both the preprocessing procedures we are considering. Therefore, it suffices to show that â(s) does not depend on s′.
First, consider the Orthogonalization procedure PDO where â(s) = fA(s
′, u)− En(A|S = s′) + En(A|S = s) = fA(s
′, u)− E(A|S = s′) + En(A|S = s)− (En − E)(A|S = s′). Note that A|{S = s′} = fA(s′, UA) and the first order Taylor expansion of it gives
E(A|S = s′) = E ( fA(s ′, u) + ∂
∂u fA(s, u) ∣∣∣∣ s=s′,u=u′ (UA − u) )
= fA(s ′, u) +
∂
∂u fA(s, u) ∣∣∣∣ s=s′,u=u′ E(UA − u)
for some u′ between u and UA. By Condition 1
â(s) = ∂
∂u fA(s, u) ∣∣∣∣ s=s∗,u=u′ E(u− UA) + En(A|S = s) + oP(n)
and thus it does not depend on s′.
Second, consider the Marginal Distribution Mapping procedure PDM . Let fAj (s, u) = eTj fA(s, u) where ej is a d-dimensional vector with the jth element being one and all other elements being zeros. The jth element of â(s) is [â(s)]j = F̂−1js (F̂js′(fAj (s
′, u))) for j = 1, · · · , d. Again, the first order Taylor expansion of fAj (s ′, UA) gives
F̂js′(fAj (s ′, u)) = Pn(Aj ≤ fAj (s′, u)|S = s′)
= P(fAj (s′, UA) ≤ fAj (s′, u)) + (Pn − P)(Aj ≤ fAj (s′, u)|S = s′)
= P ( fAj (s ′, u) + ∂
∂u fAj (s, u) ∣∣∣∣ s=s′,u=u′ (UA − u) < fAj (s′, u) ) + oP(n)
for some u′ between u and UA. Under Condition 2,
F̂js′(fAj (s ′, u)) = P
( sign ( ∂
∂u fAj (s, u) ∣∣∣∣ s=s∗,u=u′ ) (UA − u) < 0 ) + oP(n)
does not depend on s′ and hence a(s) is a function of s and u alone.
A.2 PROOF OF THEOREM 2
Proof. The steps of proving the two statements of Theorem 2 are similar. To remove redundancy, we use the notation P whenever the argument is true for both the preprocessing procedures PO and PM .
First, we show that Y is counterfactually fair if Y⊥S|P(S,A). The posterior mean of the counterfactual Ys′(U) given S = s∗ and A = a∗ can be evaluated in two steps: first find the conditional distribution of U = {UA, US , UY }, and then calculate the conditional expectation of the counterfactuals from the SCM. Since the effect of US is blocked by setting S = s′ and UY is independent of S and A, only the distribution of UA will be affected by the given information and effect the counterfactuals Ys′(U).
E(Ys′(U)|S = s∗, A = a∗) = ∫ E(fY (s′, fA(s′, u), UY )pUA|S,A(u|S = s ∗, A = a∗)du. (A.1)
Under the SCM, E(fY (s′, fA(s′, u), UY ) is the same as the expectation of the observed decision Y given the attributes S = s′, A = fA(s′, u). Therefore (A.1) is equal to∫
E(Y |S = s′, A = fA(s′, u))pUA|S,A(u|S = s ∗, A = a∗)du (A.2)
= ∫ E(Y |S = s′,P(S,A) = P(s′, fA(s′, u)))pUA|S,A(u|S = s ∗, A = a∗)du (A.3)
= ∫ E(Y |P(S,A) = P(s′, fA(s′, u)))pUA|S,A(u|S = s ∗, A = a∗)du (A.4)
= ∫ E(Y |P(S,A) = P(s∗, fA(s∗, u)))pUA|S,A(u|S = s ∗, A = a∗)du (A.5)
=E(Ys∗(U)|S = s∗, A = a∗). (A.6) Equation (A.3) replaces the condition A = fA(s′, u) with P(S,A) = P(s′, fA(s′, u)) because PO(S,A) is a one-to-one function of A given S and PM (S,A) is also a one-to-one function of A given S under Condition 3. Equation (A.4) is due to the conditional independence of Y and S, and (A.5) uses the result that P(s′, fA(s′, u)) = P(s∗, fA(s∗, u)), which can be shown following the proof of Theorem 1. Repeat the steps (A.1) to (A.5) and we shall get the same result for E(Ys′(U)|S = s∗, A = a∗). Note that both Ys′(U) and Ys∗(U) are binary random variables, therefore the equivalence in expectation implies that
Ys′(U)|{S = s∗, A = a∗} d = Ys∗(U)|{S = s∗, A = a∗}.
The above result holds for any s′, s∗ ∈ S, so the definition of counterfactual fairness is satisfied. Next we show that Y⊥S|P(S,A) if Y is counterfactually fair. The counterfactual fairness of Y implies
E[fY (s′, fA(s′, UA), UY )|S = s∗, A = a∗] =E[fY (s∗, fA(s∗, UA), UY )|S = s∗, A = a∗].
(A.7)
Let a′ = P(s∗, a∗), then
(UA, UY )|{S = s∗, A = a∗} d = (UA, UY )|{S = s∗,P(s∗, A) = a′} (A.8)
since P(s∗, a∗) is a one-to-one function of a∗ for each s∗. Using the Bayesian formula, the posterior density of UA is
pUA|S,P(u|S = s ∗,P(s∗, A) = a′) (A.9)
= pUA(u)P(S = s∗)pP|S,UA(a′|S = s∗, UA = u) P(S = s∗) ∫ pUA(u)pP|S,UA(a ′|S = s∗, UA = u)du , (A.10)
where pUA|S,P(u|s∗, a′) denotes the conditional density of UA given S = s∗ and P(s∗, A) = a′, pUA(u) denotes the prior density of UA, and pP|S,UA(a
′|S = s∗, UA = u) denotes the conditional density of P(s∗, A) given S = s∗ and UA = u. As a density function, (A.10) is proportional to its kernel pUA(u)pP|S,UA(a
′|S = s∗, UA = u), which equals pUA(u)pP|S,UA(a′|S = s′, UA = u) because P(S,A) does not depend on S when UA is given as shown in the proof of Theorem 1. Repeating the steps and we can show that the posterior density of UA given S = s′,P(s′, A) = a′ is also proportional to pUA(u)pP|S,UA(a
′|S = s′, UA = u). Together with the assumption in the SCM that UY is independent of S,P(S,A), we have
(UA, UY )|{S = s′,P(s′, A) = a′} d = (UA, UY )|{S = s∗,P(s∗, A) = a′}. (A.11)
The intuition here is that if the processed non-sensitive data are equal, then they provide the same information about UA regardless of the sensitive information in the original data. Substituting the conditions {S = s∗, A = a∗} in (A.7) with the equivalent conditions in (A.8) and (A.11) gives
E[fY (s′, fA(s′, UA), UY )|S = s′,P(s′, A) = a′] =E[fY (s∗, fA(s∗, UA), UY )|S = s∗,P(s∗, A) = a′].
(A.12)
Under the SCM and structural equations defined in Figure 1, (A.12) implies
E[Y |S = s′,P(S,A) = a′] = E[Y |S = s∗,P(S,A) = a′]. (A.13) Since (A.13) holds for any s′, s∗ ∈ S, it yields that
E[Y |S,P(S,A)] = E[Y |P(S,A)] and hence Y⊥S|P(S,A) for binary Y .

heading: B DETAILS OF SIMULATION EXAMPLES
text: Example 2. The bank now collects the race S, education year E and annual income A information from loan applicants. There are three possible race groups S = {0, 1, 2} and S = 1{US > 0.76} + 1{US > 0.92}, meaning that a random applicant could be from the majority race group (0) with probability 0.76, or from the minority group 1 or 2 with probability 0.16 or 0.08. Let UE be a standard normal random variable and µE = λe0 + 1{S = 1}λe1 + 1{S = 2}λe2, the education year is E = max{0, µE + 0.4µEUE}. Let µA = log(λa0 + 1{S = 1}λa1 + 1{S = 2}λa2), the annual income is
A = exp{µA + 0.4µEUE + 0.1UA}. The decision of the bank is modeled as
Y = 1{UY < expit(β0 + 1{S = 1}β1 + 1{S = 2}β2 + βaA+ βeE)}.
Here λe0, λe1, and λe2 decide the mean education year of the three race groups. λa0, λa1, and λa2 decide the median annual income. The annual income and the education year are positively correlated through UE . β1 and β2 characterize the direct effect of the race information while the λ’s indicate the indirect effect together with βe and βa. In this example, neither of Conditions 1 and 2 holds if βe and λe1 and/or λe2 are not zero due to the maximum operator in fE . Even if λe1 = λe2 = 0, only the weaker Condition 2 will hold due to the same reason for Example 1.
Example 3 is a replica of the admission example constructed by Wang et al. (2019). Example 3. The admission committee of a university collects the gender S and test score T information from applicants. The gender is simulated from S = 1{US < 0.5}, where S = 1 for male and S = 0 for female. Let UT ∼ Uniform(0, 1) and we generate the test score as
T = min{max{0, λS + UT }, 1}. The decision of the committee is
Y = 1{UY < expit(β0 + βtT + βsS)}.
It is worth noting that both Examples 2 and 3 do not satisfy either of Conditions 1 and 2 due to the cutoff in the value of their non-sensitive attributes education years and test score. Take Example 3, there will be a positive probability (λ to be exact) of seeing male students with test score 1 if λ > 0. Check that
∂
∂uT fT (s, uT ) = { 1, 0 < uT < 1− λs 0, 1− λs < uT < 1
and we can see that its sign does change with s for any fixed uT . Therefore, neither of the proposed preprocessing methods can achieve CF in theory.
In Figures 2a and 4c, we choose c1 = 0.01, c2 = 4, c3 = 0.2 and fix β0 = −1, βa = 2, βs = 1, λa = 0.5 while increase σa from 1 to 2.8 to see how the difference in the variation of non-sensitive
(0.0 , 0.0 ) (0.0 , 0.2 ) (0.0 , 0.4 ) (-0. 2, 0 .0) (-0. 2, 0 .2) (-0. 2, 0 .4) (-0. 4, 0 .0) (-0. 4, 0 .2) (-0. 4, 0 .4)
Difference due to ( i1, i2)
0.00
0.05
0.10
0.15
0.20
0.25
CF -m
et ric
(0.0 , 0.0 ) (0.0 , 0.2 ) (0.0 , 0.4 ) (-0. 2, 0 .0) (-0. 2, 0 .2) (-0. 2, 0 .4) (-0. 4, 0 .0) (-0. 4, 0 .2) (-0. 4, 0 .4)
Difference due to ( i1, i2)
0.31
0.32
0.33
0.34
0.35
0.36
M AE
(0.0 , 0.0 ) (0.0 , 0.2 ) (0.0 , 0.4 ) (-0. 2, 0 .0) (-0. 2, 0 .2) (-0. 2, 0 .4) (-0. 4, 0 .0) (-0. 4, 0 .2) (-0. 4, 0 .4)
Difference due to ( i1, i2)
0.68
0.70
0.72
0.74
RO C
AU C
(0.0 , 0.0 ) (0.0 , 0.2 ) (0.0 , 0.4 ) (-0. 2, 0 .0) (-0. 2, 0 .2) (-0. 2, 0 .4) (-0. 4, 0 .0) (-0. 4, 0 .2) (-0. 4, 0 .4)
Difference due to ( i1, i2)
0.86
0.88
0.90
Av er
ag e
pr ec
isi on ML
FTU FL AA FLAP-1 FLAP-2
attribute between sensitive groups affects fairness. In Figures 2b and 4d, we set β0 = −1, βt = 2, βs = 1 and increase λ from 0 to 0.8 to see how the mean difference of test scores affects fairness.
In Figure 4a and 4b, we choose β0 = −1, β1 = β2 = 0, βa = 1, βe = 2, λe0 = 1.07, λi0 = 0.58. In Figure 4a, we change (λi1, λi2) while fix λe1 = 0 and λe2 = 0 to see how the mean difference of income affect fairness. The results are telling the same story as Figure 2a: since only the weaker non-sensitive condition is met, the AA-algorithm cannot achieve CF but the FLAP algorithms with marginal distribution mapping procedure can.
In Figure 4b, we change (λe1, λe2) while fix λi1 = 0 and λi2 = 0 to see how the mean difference of education affect fairness. The results are similar to those of Figure 2b where all algorithms we consider cannot achieve CF but the FLAP algorithms still have the lowest CF-metric.

heading: C DETAILS OF REAL DATA ANALYSIS
text: We use the adult income data to predict whether an individual’s income is higher than $50K with information including sex, race, age, workclass, education, occupation, marital-status, capital gain and loss. Sex and race are regarded as sensitive attributes. The training set has 32,561 samples and the test set has 16281 samples. The comparison of the FLAP and other methods are shown in Table 2.
The COMPAS (Correctional Offender Management Profiling for Alternative Sanctions) recidivism data contains the demographic data such as sex, age, race, and record data such as priors count, juvenile felonies count, and juvenile misdemeanors count of over 10,000 criminal defendants in Broward County, Florida. The task is to predict whether they will re-offend in two years. According to ProPublica, “Black defendants were often predicted to be at a higher risk of recidivism than they actually were.” Here we treat sex and race as sensitive attributes and try to predict recidivism in a counterfactually fair manner. We only use the data for Caucasian, Hispanic, and African-American individuals due to the small sample sizes of other races. The remaining data are divided into a training set of 5,090 samples and a test set of 1697 samples. The results are shown in Table 3
Similar to the results we have shown for the loan application data, the FLAP methods using the marginal distribution mapping preprocessing procedure have lower CF-metric and are thus considered fairer than other fair learning algorithms, and their MAEs are comparable to other methods.

Review summaries:
The paper addresses the problem of preprocessing the data in a way that the predictions of a learning task will be counterfactually fair. The counterfactual fairness definition is borrowed from that of (Kusner et al., 2017). The authors propose ortogonaliza tion and marginal distribution mapping so as to achieve counterfactual fairness. They test their proposed approach on synthetic and real data.