Ex-Ante Assessment of Discrimination in Dataset

Data owners face increasing liability for how the use of their data could harm under-priviliged communities. Stakeholders would like to identify the characteristics of data that lead to algorithms being biased against any particular demographic groups, for example, defined by their race, gender, age, and/or religion. Specifically, we are interested in identifying subsets of the feature space where the ground truth response function from features to observed outcomes differs across demographic groups. To this end, we propose FORESEE, a FORESt of decision trEEs algorithm, which generates a score that captures how likely an individual's response varies with sensitive attributes. Empirically, we find that our approach allows us to identify the individuals who are most likely to be misclassified by several classifiers, including Random Forest, Logistic Regression, Support Vector Machine, and k-Nearest Neighbors. The advantage of our approach is that it allows stakeholders to characterize risky samples that may contribute to discrimination, as well as, use the FORESEE to estimate the risk of upcoming samples.

• We provide experimental proofs of how our measure of ex-ante risk is a useful warning sign for the demographic disparity, inequality of odds and opportunities of classifiers trained on a sample of the data.
• We show how model averaging over diverse decision trees provides reliable estimates for our ex-ante risk.

Problem Setting
We frame the task where a set of individuals sampled from X × Y (where x ∈ X describes individual's features and y ∈ Y the ground truth of target variable) can lead into finding g : X → Y used to support decision-making process. We assume that g has a sufficient performance such that the decision-makers consider the function g as part of the process. For example, g can be the classifier for mortgage applications, where upcoming applicants' information are the inputs and low and high risk of mortgage delinquency is the outcome. Additionally, we assume that for each sampled individual we are given their sensitive attributes s ∈ S, which represents protected information forbidden to be used in the classification. Furthermore, sensitive attribute is defined by the union of the different groups, i.e., S = ∪ j S i ∀i ∈ [j], with j the total of different groups and S i is a group of individuals with same sensitive attribute(s) usually represented by a number. Although S is not part of the inputs, they are allowed to be used as the evaluation of discrimination across the groups in the sensitive attributes.
The objective is to determine how likely any individual (x, s, y) ∈ D will lead into discrimination a function g : X → Y learned from D s.t. g show sufficient performance to be used by decision-makers. This objective implies two challenges. First, we have to define what discrimination stands for. And second, we are aimed to determine the discrimination when g is unknown, i.e., under ex-ante notion. We discuss and address these two aspects in the following section under a binary classification task, although this is extensible to other task types.

Risk Scores and Aggregate Misclassification Rates
Discrimination can be understood as the disparity between two groups of individuals. In the mortgage application example, disparities can be found along the process, i.e., if there is explicit evidence of disparity through the use of sensitive attributes as part of the classification, and there is sign of dependency between the outcome and the protected attribute, it can be determined that there exists disparate treatment [21]. One solution is to remove any sensitive attribute, which is known as Fairness Through Unawareness (FTU) [22]. However, FTU is not enough since the correlation of sensitive attribute with other features may still end up with disparities in the outcome, which is known as disparate impact [21]. Based on this fairness notion, Demographic Parity (demP ) measures disparity across groups over the outcome of a function g [21]. Similarly, individual fairness certificates that g maps similar outcomes for similar individuals [23]. Using these notions, we define an ex-ante measure by evaluating disparity on the labeled dataset (instead of the outcome of g) for similar individuals of a given sample. More in detail, we state that fairness risk score is the conditional probability of Y being 1 (from demP ) given X = x with differences in the sensitive attribute S (from individual fairness).
In the following formulation, we first discuss theoretically how the risk can be obtained from infinite population (or at least large enough). However, since this is not true for most of the cases, we then discuss two estimation proposals under finite population in Section 3. Definition 1. For any individual (x, s) ∈ X × S, its fairness risk score r(x) is defined as We claim that Definition 1 is ex-ante since it does not depend on any classifier that will use the data to make decisions. However, this is based only on independence notions of disparate treatments, which can lead into flaws of identification of discrimination. According to Kizilcec and Lee [7], separate notion can solve this issue by including the ground truth. We argue that Definition 1, as ex-ante risk, captures this granular and aggregate fairness properties of classifiers using the data: (i) differences in individual misclassification rates across demographic groups; (ii) differences in aggregate misclassification rates across demographic groups. Moreover, we show that ex-ante risk score is directly related to the differences δ mis (x) in misclassification rate conditional on X = x for an unknown function g, where δ mis is defined as Equation 2 .
Having this we state the Theorem 1, which implies that the ex-ante risk score captures how the misclassification rate of any unaware classifier vary across demographic groups. Consequently, for a given X = x, a large risk score means that individuals in one group will be more likely to be misclassified than in the other, regardless of the classifier. Theorem 1. For any unaware classifier g, x ∈ X , we have: are the characteristic functions of the sets {x ∈ X |g(x) = 1} and {x ∈ X |g(x) = 0}. Moreover, for a deterministic unaware classifier, δ mis (x) = r(x).
Proof. Let η s (x) denote P (Y |X = x, S = s). For any classifier g, we have where I {g(x)=1} is the indicator function equal to one whenever g(x) = 1; and, (a) uses the fact that conditional on X, g(X) is independent of Y . Therefore, If g is deterministic, we have either g(x) = 0 or g(x) = 1, which leads to δ mis (x) = r(x).
Our ex-ante fairness risk score also captures aggregate fairness properties of any classifier g, which allows us to look at the aggregate difference in misclasification rates [15] defined as Equation 3.
Large values for ∆ mis means that the error rate is not equalized across groups. Having this, we state Theorem 2, which implies that if the distribution of features X does not depend on the sensitive attribute, then the total variation between distribution of X conditional on S = s and S = s is zero and low aggregate risk scores implies low ∆ mis (g). Therefore, whenever the distribution shift between X|S = s and X|S = s is small, our measure of risk allows users to identify data that are unlikely to lead to unfair classification, when fairness is measured in terms of difference in misclassification rates (i.e., in terms of separation notions [7]). Theorem 2. For any unaware classifier g, where T V (P s , P ns ) is the total variation between the distribution P s of X conditional on S = s and the distribution P ns of X conditional on S = s.
where (a) uses the fact that c(x) ≤ 1 and η s , η ns ≤ 1, the triangular inequality. The result in Theorem 2 follows from the definition of total variation.

Risk Scores and Sub-population Fairness Metrics
Results in Theorem 2 do not provide us with a lower bound on aggregate fairness metrics, even in the absence of a distributional shift between P s and P ns . In this section, we show a lower bound for misclassification rates at the sub-population level. Specifically, for γ ∈ (0, 1), a sub-population level fairness metric measures the maximum value this metric takes over any subset G of the feature spaces X such that P (G) ≥ γ (e.g. [24,25,26]). Sub-population level definitions of algorithmic fairness are stronger than their aggregate counterparts, since they protect subgroups defined by a complex intersection of many sensitive attributes ( [25,27]) or a structured slicing of the feature space [24]. We define sub-population differences in misclassification rates of a classifier g as where ∆ mis (g|x ∈ G) is the difference in misclassification rates between demographic groups in sub-population G. Theorem 3. Suppose that there exists a sub-population G ⊂ X such that P (G) > γ, P s = P ns , and P (Y = 1|X = x, S = s) > P (Y = 1|X = x, S = s). For any stochastic classifier g : Theorem 3 implies that whenever the response function for a sub-population G, a classifier that predicts Y = 1 on this sub-population will lead to higher misclassification rates for one demographic group and the differences in misclassification rates will be bounded from below by the average risk score. Therefore, by looking at sub-populations with high predicted risk scores, the user can identify sub-populations where differences in sensitive attributes S will correlate with differences in misclassification rates.
Proof. Let 2κ = inf x∈G g(x) − 1/2 > 0. Using derivations from the proof of Theorem 1 and the assumption that P 0 = P 1 , we can show that where (a) uses that η s (x) ≥ η ns (x) on G.

Risk Estimation
To estimate the ex-ante risk score, we propose two methods: (i) a Bayesian-based approach to estimate the probability P (Y = 1|X = x, S = s) followed by the computation of the risk score r(x); (ii) an ensemble approach that averages the risk estimates from diverse decision trees.

Method 1: Risk Score of Average Models
Our first approach consists of first obtaining an estimate of the response function E[Y |X = x, S = s] and E[Y |X = x, S = s] and then, compute the risk score. We follow [28] and use an additive tree model BART ( [20] to obtain a non parametric estimate of the response functions. Given M trees T 1 , T 2 , ..., T M , we compute the risk score as BART uses a prior to regularize the depth of each tree T m . This non-parametric approach has been successful to estimate individual treatment effect following the seminal work of [28].

Method 2: Average of Risk Scores
One limitation of a BART estimate of the ex-ante risk score is that it requires to estimate both response functions BART averages decision trees to obtain a robust Bayesian estimate of each response function.
In this section, we present an algorithm that directly averages the risk score estimates from each decision tree.
Given a collection of trees T 1 , T 2 , ..., T M , we define as L 1 (x), L 2 (x), ..., L M (x) the leafs to which an individual with feature x ∈ X belongs to. For each decision tree T m , we compute its estimate r(x, T m ) of the risk score as the difference between demographic groups in the estimation error rate Y mis in L m (x): Our risk estimate is then Intuitively, decision trees partition the feature space into regions where outcomes are assumed to be constant. Leaf level risk scores characterize how violations of this assumption vary across demographic groups.
To obtain a robust risk estimate, we average a diverse set of trees obtained as followed: (i) we train each tree on a different random sub-sample of the insances and a random subset of the features; (ii) we retain the trees that achieve a minimum performance β ∈ (0, 1).
Step (i) allows to ensemble trees that see different aspect of the data generating process and de-correlates estimation errors.
Step (ii) allows to retain only the trees that captures at least partially the characteristics of the response function E[Y |X = x]. It is worthy to note that we use S in the training. We argue that for a leaf with none members of one group would reflect dependency between Y and S given X = x, hence a high risk of discrimination. Under an optimistic scenario, the expected misclassification rate should be equal across groups in the leaf, while the highest error rate is expected for the not present group under pessimistic one. Since we aim to flag probable discrimination, we argue that the latter is preferable. Note that a better approach might be used, however, according to the results in experiments section, our assumption seems to be sufficient. Finally, more details about the FORESEE algorithm are provided in the appendix.

Experimental Evaluation
We design our experiments to answer the four following research questions.
• RQ1: Do risk estimates from FORESEE and BART average to the ground truth risk in numerical simulations?
• RQ2: Is the ex-ante risk score a good predictor of how unfair classifiers using the data as input will be? • RQ3: Does our measure of risk allow the user to describe the sub-populations that are the most likely to be under-served by classifiers using the data as inputs? • RQ4: How can ex-ante risk score guide the development of fair algorithms?

Data sets
Synthetic Data First, we rely on numerical simulations to test whether FORESEE and BART are on unbiased estimator of the true risk score. We uniformly draw features from [0, 1] 2 and assign a sensitive attribute s with P (S = 1) = 0.5. For S = 1, we assign a label Y = 1. For S = 0, we assign a label Y = 1 with probability equal to 1 − x1+x2 2 . Therefore, for a given X = x, the ground truth risk is equal to r(x) = x1+x2 2 . We draw 5000 samples from this synthetic data, run FORESEE and BART to estimates r F ORESEE and r BART for each sample and compare their values to the ground truth risk r(x). We repeat the protocol 20 times with different seeds to compute mean and standard deviation of the risk estimates.
Real world datasets We use two benchmark data sets in fair machine learning and a new dataset in education data mining. The former two are publicly available at ProPublica webpage and UCI Machine Learning repository.
Adults (a.k.a. Census Income Data Set) consists of 48, 844 individuals described by 14 features that include marital status, education, working hours. The sensitive attribute is the gender to which individuals self-identify to. The outcome is whether an individual's income is larger than 50K [29].
Compas gathers information on 7, 214 individuals in the criminal justice system to assess their recidivism risk. Features include number of felonies, misdemeanors and degree of charges. The sensitive attribute is whether an individual self-identifies as African American. The outcome is whether an individual re-commits a crime within two years [2].
Dropout contains academic records of 4, 706 students in a Latin-American university. Features include grades and participation to academic support programs. The sensitive attribute is the gender to which each student self-identifies to. The outcome reflects drop out within the first two years.
We split each dataset into training and testing sets using a ratio of 70/30.

Risk Scores vs. Downstream Fairness Metrics
To explore how ex-ante risk score is informative of future unfair uses of the data, we train four models -Logistic Regression (LR), Random Forest (RF), k-Nearest Neighbors (KNN), and Support Vector Machine (SVM) -to predict Y from X. We compute accuracy for evaluating models' performance in Compas, and F-1 score in Adults and Dropout. We also compute three standard fairness metrics: demographic disparity δ demP [22]; inequality of opportunity δ opp [30]; and, inequality of odds δ odd [30]. We also classify individuals into High and Low Risk whose risk score are larger and smaller than λ, respectively. However, this threshold is truly context dependent. We leave it to the stakeholders to decide which threshold is appropriate in a specific application.

Risk Score and Mitigation
To show how our ex-ante risk score can guide machine learning developers, we explore two risk-based fairness mitigation strategies. We identify all instances with risk score larger than λ and apply two mitigation approaches: (i) pre-processing and (ii) post-processing.
Preprocessing removes the high-risk instances from the training set and only report classification outcomes on instances with low ex-ante risk score. This is a very relevant approach whenever stakeholder can replace automated decisions by human ones for outcomes with high ex-ante risk score. On the other hand, post-processing consists of adjusting the classification threshold over the classifier's predicted class conditional probabilities, while minimizing one of the aggregate fairness metrics and the error rates [30]. Figure 1 shows the mean and standard deviation of r F ORESEE (x) (left) and r BART (x) (right) against the ground truth risk r(x) for each x in our synthetic dataset. We observe that FORESEE generates a statistically less unbiased estimate of the ground truth risk since the mean of the r F ORESEE (x) across 20 simulations is equal to r(x) for almost all values of r(x) ∈ (0, 1). On the other hand, BART estimates have an upward bias for low values of the true risk score r(x) and a downward bias for large values r(x). This observation confirms our intuition that it is preferable to directly average risk estimates from local approximations instead of first estimating the response functions over the entire dataset and then computing the risk score.  Table 1 shows the classification performance of four models across our three real world datasets. Best classifiers in terms of F1 score/accuracy vary across datasets: Random Forest achieves the highest performance on Adults and Compas, while Logistic Regression on Dropout. Moreover, best classifiers generate significant fairness metrics, where of particular interest is whether our ex-ante risk score anticipates these fairness issues.

Model Adult Dropout
Compas  Table 1: Performances of machine learning models on each data set. Higher F-1 score and accuracy (acc) are better, whereas for Equalized Opportunity (δ opp ), Equalized Odd (δ odd ), and Demographic Parity (δ demP ), lower is better.  Across all datasets there exist instances with high risk scores, which indicates that misclassification rates would vary with changes in sensitive attribute. This is particularly striking for Compas, where whole of the population is estimated to have an ex-ante risk score larger than ≈ 0.4. High risk scores for Compas confirms findings in existing studies (e.g [2]) that this dataset is not well suited for training automated decision systems without significantly harming a demographic group.
Using Figure 2, we define as high risk a sample with risk higher than 0.5 for Adults and Compas, and higher than 0.06 for Dropout. In Table 2, we find that all three fairness metrics are higher for high risk individuals than low risk ones. This is evidence that our ex-ante risk score allows identifying individuals for which a given classifier's aggregate performances would significantly vary across demographic groups. Notice that the differences are not significant for Compas as the other datasets, which is consistent with the distribution of our risk core estimates depicted in Figure 2 and flags once again the issues of using this set for automated training [31].

Fairness Adult Dropout Compas Metric
High | Low High | Low High | Low  Table 2: Fairness metrics in absolute value for groups defined by level of ex-ante fairness risk score. The thresholds between Low and High risk groups are set to 0.5 for Adult and Compas, and 0.06 for Dropout. We truncate figures to three decimal places. Figure 3 shows the differences between the High and Low Risk profiles in the datasets. The high risk group is composed of the top 20% of samples with high risk scores drawn equally from both groups in S. The low risk group is similarly formed with the lowest 20% risk scores. From figure 3 we can characterizes high risks as in the following list (the low profile are the opposite to this description):

RQ3: Profiles for High and Low Risk Instances
• Adult: aged individuals, high number of working hours per week, and married or divorced.
• Dropout: students with low academic performances and higher numbers of academic warnings. • Compas: younger defendants, fewer criminal history, mostly felony as charge degree, and spending less days in jail.
Our risk score provides stakeholders and data owners information on the characteristics of individuals for which predictions would be affected by their sensitive attributes. A useful implication of the profiles in Figure 3 is to use with caution any data mining algorithm that predicts the target variable if the individual' risk estimate is high.

RQ4: Risk Score Guided-Mitigation Strategies.
We test the pre-and post-processing strategies previously described. Table 3 shows that a pre-processing strategy that removes samples at high risk of unfair outcomes is effective at reducing aggregate inequality of odds and opportunities. This result is evidence that our ex-ante risk score is instrumental in identifying the data instances that push the classifier toward unfair outcomes. Moreover, our pre-processing strategy even improves the performance, which are consistent with previous studies that have shown results in favor of pre-processing approaches [32,33]. On the other hand, removing high risk individuals in Compas dataset results in insignificant improvement, which is expected given the found distribution of risk scores. Intuitively, although we remove instances with scores > 0.5, the remaining still has high levels (mostly > 0.4). Consequently, we find that post-processing approaches on the risk sub-sample might be better a approach, where post-processing subjected to demographic parity is the best one. Table 3 also shows that post-processing tailored to high risk group is effective at reducing each fairness metric, although at a cost of performance. Therefore, developers can use the high risk group as a unit test against which they can automatically evaluate the fairness of their algorithm; then, post-process classification outcomes for that group.

Conclusions
Although the fair machine learning literature offers an abundance of metrics to measure the potential harmful effect on individuals of a machine learning model, stakeholders would like to anticipate these fairness pitfalls before investing in model development. We propose an ex-ante risk score to measure whether future performances of any classifier using the data will vary with sensitive attributes. Moreover, we propose a bagging approach (FORESEE) to estimate the risk score from a finite sample. Our experiments demonstrate that our risk score, although measured before model development, anticipates correctly whether a model using the data will under-serve some demographic groups. Moreover, our risk score offers useful guidance for stakeholders to decide whether a data is appropriate for training automated decision systems; for developers to mitigate potentially discriminatory outcomes; and for end-users to decide when to trust the outcome of the algorithm. However, our approach is still computational expensive. Also, although a pessimistic scenario assumption may over-estimate the misclassification rate variation, our results show this seems to be sufficient.