Counterfactual Fairness: Unidentification, Bound and Algorithm

1 Introduction

It is important to develop fairness-aware machine learning algorithms and models such that the decisions made with their assistance are subject to fairness requirements. In recent years, the research community has studied fairness-aware machine learning from the causal perspective [Zhang et al., 2017b; Zhang et al., 2017a; Zhang and Bareinboim, 2018; Nabi and Shpitser, 2018; Zhang et al., 2018b; Zhang et al., 2018a] using causal modeling [Pearl, 2009]. In these works, fairness is generally formulated and quantified as the average causal effect of the sensitive attribute on the decision attribute. The effect is evaluated by the intervention through the post-interventional distributions. Different from above works, [Kusner et al., 2017] introduced counterfactual fairness, based on the counterfactual inference, which considers the causal effect within a particular individual/group specified by of observational profile attributes. The notion of counterfactual fairness is more general than the intervention-based notions where the set of profile attributes is empty. Consequently, the counterfactual inference is more challenging than the intervention. This is because measuring interventions only considers the post-interventional distributions, but counterfactual inference considers both the real world without the intervention and the counterfactual world with the intervention. Researchers have proved that the counterfactual quantity cannot be uniquely computed from the observational data in some situations, which are referred to as the unidentifiable situations [Pearl, 2009].

The unidentifiable situations are big barriers to the application of counterfactual fairness. In [Kusner et al., 2017], the authors proposed three methods to evade the unidentifiability issue: 1) only non-descendants of the sensitive attribute are used in classification, 2) the non-deterministic substitutions of the hidden variables are postulated and inferred based on domain knowledge, or 3) the complete causal model is postulated and estimated, e.g., , being treated as the additive noise model then estimating the errors. However, the sensitive attribute is usually an inherent nature of data hence many attributes are its descendants. If all descendants are forbidden, very few attributes are allowed for classifier training, weakening the resultant fair classifier dramatically. Also, it is over-simplified to postulate the substitutions and their distributions, since the exogenous variables represent all possible sources of randomness; or presuppose that the causal model, which is supposed to represent the underlying mechanism of the world, is an additive model.

In this paper, we address the problem of learning counterfactually fair classifiers by mathematically bounding the unidentifiable counterfactual quantity. We leverage the counterfactual graph proposed in [Shpitser and Pearl, 2008] for depicting the independence relationships among variables in the real world and the counterfactual world which are of concern in the counterfactual quantity. Then, we adopt the c-component factorization to decompose the counterfactual quantity, and identify the terms that are the source of unidentification. We propose a graphical criterion for determining the identification of counterfactual fairness and develop the lower and upper bounds of counterfactual fairness in unidentifiable situations. Finally, we propose a post-processing method for reconstructing arbitrary classifiers in order to achieve counterfactual fairness. We formulate the reconstruction problem as a linear constrained optimization problem with the bounded counterfactual fairness criterion as the constraints.

In the experiments, we evaluate our methods and compare them with existing ones using real-world datasets and synthetic datasets where the ground-truth of counterfactual fairness can be precisely quantified. The results show that our method correctly achieves counterfactual fairness as expected according to our theorem, while obtaining high accuracy of prediction. On the contrary, the methods proposed in [Kusner et al., 2017] either fail to achieve counterfactual fairness or suffer from low accuracy due to simplified assumptions.

2 Preliminaries

2.1 Structural Causal Model and Intervention

Definition 1 (Structural Causal Model). A structural causal model M is represented by a triple 〈U, P (U), V, F〉 where

1. U is a set of exogenous variables of any types, i.e., discrete, continuous, or mixed. An arbitrary joint probability distribution P(U) is defined over U.
2. V is a set of endogenous variables that are determined by variables in U∪V.
3. F is a set of functions mapping fromU∪V to V. Specifically, for each X ∈ V, there is a function fX ∈ F mapping fromU∪(V\X) to X, i.e., X = fX(Pa(X), UX), where Pa(X) ⊆ V \ X stands for the endogenous variables that directly determine the value of X, and UX ⊆ U represents all sources of randomness.

A causal model is associated with a causal graph G where each node corresponds to a variable in V 1 , and each edge, denoted by an arrow, points from a node X to another node Y if X is an input of fY . In this manuscript, we focus on the Markovian causal model where all exogenous variables are independent. Thus, the causal graph is simplified by omitting all exogenous variables and the edges associated with them. For any set of nodes X, we use Pa(X)G , Ch(X)G , An(X)G , and De(X)G to denote the sets of parents, children, ancestors, and descendants of X in G.

In the causal model, the quantitative measure of causal effects is facilitated by interventions through do-calculus [Pearl, 2009], which simulates the physical interventions that force some variable X to take certain values x. Formally, the intervention that fixes the value of X to x is denoted by do(x). The mathematical meaning of do(x) in a causal model M is defined as the substitution of equation X = fX(Pa(X)G , UX) with X = x. The causal model after performing do(x) is called a submodel denoted byMx. For another endogenous variable Y which is affected by the intervention, its interventional variant in submodelMx is denoted by Yx. The distribution of Yx, called the post-intervention distribution of Y under do(x), is denoted by P(yx). For simplicity, we rewrite P(yx) as Px(y), meaning the distribution of (the variant of) Y in submodel Mx. Similarly, we can rewrite the condition distribution of Yx given Zx, i.e., P(yx|zx), as Px(y|z). Pearl [Pearl, 2009] proposed three rules of do-calculus to infer post-intervention distributions from observational data, by converting post-intervention distributions to observational distributions.

1 An uppercase letter denotes an attribute and a lowercase letter denotes an attribute value. Similarly, a bold uppercase letter denotes a set of attributes and a bold lowercase letter denotes a set of values.

2.2 Counterfactual Inference and Unidentification

In Section 2.1, the causal effect is estimated using intervention where the post-intervention distribution concerns the counterfactual world represented by submodel Mx only. If we infer the post-intervention distribution while conditioning on certain individuals or groups specified by a subset of endogenous variables, the inferred quantity will involve two worlds simultaneously, the real world represented by causal model M, and the counterfactual worldMx, hence cannot be resolved by do-calculus directly. Such causal inference problem is called the counterfactual inference, and the distribution of Yx conditioning on the real world observation O = o is denoted by P(yx|o). Note that Yx is a variable in submodel Mx, while O are variables in original causal model M.

Apparently, inferring P(yx|o) requires to know the connection between the real world and the counterfactual world. This can be done if we have complete knowledge of the causal model. According to [Pearl, 2009], the counterfactual inference can be exactly performed using three steps if the complete model, including all the structural equations, is known: 1. Abduction: Update P(u) by observation O = o to obtain P(u|o). 2. Action: ModifyMby intervention do(x) to obtain the submodel Mx. 3. Prediction: Use modified submodel 〈Mx, P(u|o)〉 to compute the probability of Yx,, i.e., the consequence of the counterfactual inference.

The above method is usually infeasible in practice due to the lack of the complete knowledge of the causal model. If we only have the causal graph and observational data, which is a common scenario in the literature, the counterfactual quantity might be evaluated by using the IDC* algorithm developed in [Shpitser and Pearl, 2008]. However, in certain situations where the IDC* algorithm fails, the corresponding counterfactual quantity cannot be uniquely computed from the observational data in theory. These situations are referred to as the unidentifiable situations. One typical unidentifiable situation [Shpitser and Pearl, 2008] is shown in Lemma 1.

Lemma 1. Let X, Y be two variables such that Y is a parent of X, then P(Y = y, Yx = y′ ) is unidentifiable if y ̸= y′ .

3 Quantifying and Bounding Counterfactual Fairness

Fairness-aware learning is widely studied using causal modeling to capture the causal connection between the sensitive attribute and the challenged decision [Kilbertus et al., 2017; Li et al., 2017; Zhang et al., 2017b; Zhang and Bareinboim, 2018; Nabi and Shpitser, 2018; Chiappa, 2019; Kusner et al., 2017]. We adopt the notion of counterfactual fairness proposed in [Kusner et al., 2017], which formulates fairness as the equivalence of two counterfactual quantities. Although this notion captures the true intuition behind fairness, it faces significant computational challenges due to the unidentifiability of counterfactual inference. In this section, we first give the formal definition of counterfactual fairness for predictive models and explain its physical meaning. Then, we show how to address above challenges by mathematically bounding the unidentifiable counterfactual quantity.

In our notations, S ∈ {s+, s-} denotes the sensitive attribute, Y ∈ {y+, y-} denotes the decision, and X denotes the set of other attributes. The historical dataset D drawn from a distribution P(X, S, Y ) is used to train a classifier f : X, S → ˆ Y . The underlying mechanism that determines a distribution P(X, S, ˆ Y ) is represented by a causal model M. The causal graph associated with the causal model is denoted by G. Then, counterfactual fairness is defined as follows.

Definition 2. (Counterfactual Fairness) Given a set of attributes Z ⊆ X, a classifier f : X, S → ˆ Y is counterfactually fair w.r.t. Z, if under any observational condition Z = z we have

Recall that a lowercase letter with a subscript represents a value assignment to the corresponding variable in the submodel, e.g., ˆ ys is a value of ˆ Ys in the submodelMs.

The physical meaning of counterfactual fairness can be interpreted as follows. Consider candidates are applying for a job and a predictive model is used to make the decision ˆ Y . We concern an individual from disadvantage group s- who is specified by a profile z. Straightforwardly, the probability of the individual to get the positive decision is P(ˆ y|s-, z), which is equivalent to P(ˆ ys-|s-, z) since the intervention makes no change to S's value of that individual. Now assume the value of S for this very individual had been changed from s- to s+. The probability of this individual to get the positive decision after the hypothetical change is given by P (ˆ ys+|s-, z). Therefore, if two probabilities P(ˆ ys- |s-, z) and P(ˆ ys+|s-, z) are identical, we can claim the individual is treated fairly as if he/she had been from the other group.

3.1 Identification of Counterfactual Quantity

In this section, we identify the source of unidentification for the counterfactual quantity and give a graphical criterion determining the identifiability of the counterfactual quantity. Our method is inspired by the IDC* algorithm and we further extend it to bound the unidentifiable quantity.

The analysis of P(ˆ ys|s′ , z) concerns the connection between two causal models, M and Ms. Thus, we apply the make-cg algorithm [Shpitser and Pearl, 2008] to the causal graph G to construct a new graph G ′ that depicts the independence relationship among all variables inMandMs that are of concern in the analysis. The make-cg algorithm first combines the two causal graphs and makes them share the same exogenous variables U, corresponding to the shared causal context or background. Then, it removes the duplicated endogenous nodes which are also not affected by do(s). The resultant graph is the so-called counterfactual graph. Next, we apply the c-component factorization [Tian and Pearl, 2002] to decompose counterfactual graph G ′ into disjoint subgraphs called the c-components, such that any two nodes in the same c-component are connected by a bi-directed path 2 . After that, the joint distribution of all variables in the counterfactual graph can be factorized as the product of the conditional distribution of each c-component. Our theoretical analysis will show that if certain c-component has the unidentifiability issue that cannot be resolved by summation, the corresponding counterfactual quantity is unidentifiable. Without loss of generality, we first use an example to illustrate our idea. Consider the causal graph G shown in Figure 1 (a) where there are five attributes A, B, C, S, ˆ Y : S is the sensitive attribute; ˆ Y is the prediction of the decision attribute obtained by any classifier; A is the ancestor of ˆ Y but not the descendant of S; B is the intersection between the ancestor of Y and the descendant of S; and C is the descendant of S but not the ancestor of ˆ Y . We aim to study the identifiability of P(ˆ ys|s′ , z), where Z is an arbitrary subset of {A, B, C}.

The counterfactual graph denoted by G ′ is shown in Figure 1 (b), where the bi-directed dash edge implies that the two nodes share the same exogenous variables. Note that A and As are merged as A since they are duplicated. Next, we apply the c-component factorization. In Figure 1 (b), there are five c-components: 〈A〉, 〈S〉, 〈B,Bs〉, 〈C,Cs〉, and 〈ˆ Y , ˆ Ys〉. We can factorize P(ˆ ys, s′ , z) as

where R(w) = P (w|Pa(W)G′ ) for any node set W, x = {a, b, c}, and z is any subset of x. Then, we can derive that

Note that c′s in P(c, c′s |s′ , a) and ˆ y′ in P(ˆ y, ˆ ys|a, b, b′s ) can be canceled out by summation. By applying the mseparation, we can remove b from P(ˆ ys|a, b, b′s ), as B is dseparated from ˆ Ys conditioning on A and Bs. Thus, we obtain

To further analyze Eq. (1), we consider two cases below.

Case 1 (B /∈ Z): In this case, we have b under the Σ of Eq. (1), hence b in P(b, b′s |s′ , a) can be canceled out by summation, resulting in P(b′s |s′ , a). Then, we can remove s′ from P(b′s |s′ , a) as Bs is d-separated from S conditioning on A, resulting in P(b′s |a). We can further rewrite P(ˆ ys|a, b′s ) as Ps(ˆ y|a, b′ ), and rewrite P(b′s |a) as P(b′s |a). At last, we invoke do-calculus Rule 2 [Pearl, 2009] to convert Ps(ˆ y|a, b′ )

2 A bi-directed path is a path consisting of bi-directed edges only.

Case 2 (B ∈ Z): In this case, since we don't have b under the Σ, term P(b, b′s |s′ , a) cannot be reduced, resulting in

From above two cases we see that, P(ˆ ys|s′ , z) in Case 1 is identifiable as all terms in Eq. (2) can be read from observational data. One can verify that this result is consistent with the IDC* algorithm. However in Case 2, since P(b, b′s |s′ , a) in Eq. (3) is unidentifiable according to Lemma 1, P(ˆ ys|s′ , z) is also unidentifiable. In this example, the identifiability of P (ˆ ys|s′ , z) depends on whether node B, the intersection of S's descendants and ˆ Y 's ancestors, is in set Z or not. We summarize this result as follows.

Proposition 1. For the causal graph in Figure 1 (a), P (ˆ ys|s′ , z) is unidentifiable if and only if B ∈ Z.

3.2 Bounding Unidentifiable Counterfactual Quantity

In Eq. (3), we identify the source of unidentifiability. Next, we derive the lower and upper bounds for P(ˆ ys|s′ , z) as shown in the following proposition, which works for both identifiable and unidentifiable situations.

Proposition 2. For the causal graph in Figure 1 (a) we have

where x = {a, b, c}, z is any subset of x, and M = {B} ∩Z.

Proof. Suppose B ∈ Z, thenM= {B}. Obviously, we have P (ˆ y|s, a, b′ ) ≤ max b′ {P(ˆ y|s, a, b′ )} .

By applying this inequality to Eq. (3), we have P (ˆ

The second step is due to the condition ∑b′ P(b, b′s |s′ , a) = P (b|s′ , a), and the third step is due to B ⊥ C|A, S. Similarly, we can replace max with min to obtain Eq. (5).

If B /∈ Z, M = ∅. Then, we have max∅{P(ˆ y|s, a, b′ )} = min∅{P (ˆ y|s, a, b′ )} = P(ˆ y|s, a) and both Eq. (4) and Eq. (5) become ∑x\z\{b} P (s′ ,a,c)P (ˆ y|s,a) P (s′ ,z) , which is consistent with the identifiable situations (i.e., Eq. (2)).

3.3 Extending to General Case

Above results can be extended to the general case. Let A denote the ancestors of ˆ Y which are not the descendants of S, B denote the intersection between the ancestors of ˆ Y and the descendants of S, C denote the descendants of S which are not the ancestors of ˆ Y , i.e.,

Note that A, B, C are disjoint and X = A∪B∪C. Now we are ready to extend Propositions 1 and 2 to the general case.

Theorem 1. (Identification of Counterfactual Quantity) Given a causal graph G and the set of profile attributes Z, the counterfactual quantity P (ˆ ys|s′ , z) is unidentifiable if and only if B ∩ Z ̸= ∅.

Theorem 2. (Bounds of Counterfactual Quantity) Given a causal graph G and a set of profile attributes Z, we have

where we partition B to two disjoint sets: a set M ∈ Z and a set N /∈ Z such that M = B ∩ Z, N = B \ Z.

The proofs are similar to the previous ones.

4 Achieving Counterfactual Fairness in Classification

The derived bounds clear the path towards constructing counterfactually fair classifiers. In this section, we propose a postprocessing method for reconstructing any classifier to achieve counterfactual fairness. To this end, we first give a relaxed quantitative criterion of fairness based on Definition 2.

Definition 3 (τ-Counterfactual Fairness). Given a profile attribute set Z ⊆ X and a threshold τ , a classifier f : X, S → ˆ Y is counterfactually fair if under any condition Z = z,

In above definition, ∣∣DE(ˆ ys-→s+|z)∣∣ captures the amount of unfairness or discrimination of a classifier in terms of the difference in the positive decision rate for a certain group of individuals (specified by z) between the counterfactual world (where they had been changed to s+) and the real world (where they are actually in s-). If the amount of unfairness of a classifier is smaller than τ , we claim this classifier is (counterfactually) fair. Note that the first termP(ˆ ys+|s-, z) has the identification issue, but the second termP(ˆ ys-|s-, z) simply equals to P(ˆ y|s-, z) since the intervention do(s-) makes no change to the value of S for this group. By denoting the upper and lower bounds of P(ˆ ys+|s-, z) obtained in Theorem 2 as ub(P (ˆ ys+|s-, z)) and lb(P(ˆ ys+|s-, z)) respectively, we obtain the bounds of DE(ˆ ys-→s+|z) as follows.

Corollary 1. (Bounds of Counterfactual Fairness) The upper and lower bounds of counterfactual fairness DE(ˆ ys-→s+|z) are given by

Corollary 1 can facilitate the detection of unfairness from observational data. Specifically, if we have ub (DE(ˆ ys-→s+|z)) ≤ τ and lb (DE(ˆ ys-→s+|z)) ≥ -τ, then it is guaranteed that τ-counterfactual fairness is satisfied. If we have ub (DE(ˆ ys-→s+|z)) ≤ -τ or lb (DE(ˆ ys-→s+|z)) > τ, then it is guaranteed that τcounterfactual fairness cannot be satisfied. Otherwise, it is uncertain and cannot be determined from data.

Based on Corollary 1, we then propose an efficient method for constructing counterfactually fair classifiers. Note that the bounds are consistent with identifiable situations, so the method works for both identifiable/unidentifiable situations.

We consider to construct a new decision variable ˜ Y from ˆ Y in the causal model such that τ-counterfactual fairness regarding ˜ Y is satisfied. The objective is to find an optimal probabilistic mapping function P (˜ y|ˆ y, pa( ˆ Y )G ) that minimizes the difference between Y and ˜ Y , measured by the empirical loss ED[ℓ(Y, ˜ Y )], meanwhile, the new decisions are counterfactually fair. The formulation of this optimization problem is given below.

ProblemFormulation 1. Given a dataset D with prediction ˆ Y made by an arbitrary classifier, we aim to learn a postprocessing mapping function P(˜ y|ˆ y, pa( ˆ Y )G ) by solving the following optimization problem:

where ℓ(Y, ˜ Y ) is the 0-1 loss function.

It is easy to show that Problem Formulation 1 is a linear programming problem with P(˜ y|ˆ y, pa( ˆ Y )G ) as variables. Note that distribution P(˜ y|pa( ˆ Y )G ) can be obtained by P (˜ y|pa( ˆ Y )G ) = ∑ˆ y P(ˆ y|pa( ˆ Y )G )P (˜ y|ˆ y, pa( ˆ Y )G ). Thus, all constraints are linear w.r.t. P(˜ y|ˆ y, pa( ˆ Y )G ). On the other hand, for the objective function we have

And we also have

In the above expression, all probabilities except P(˜ y|ˆ y, x, s) are read from the training set D, making it a linear expression of P (˜ y|ˆ y, x, s).

5 Experiments

We evaluate our method and compare it with previous methods on two datasets. To show the correctness of our method, we generate a synthetic dataset from a known causal model with complete knowledge in our evaluation. We also use the Adult dataset [Lichman, 2013] to evaluate these methods in a real-world environment. We evaluate four methods for constructing classifiers: (1) the original learning algorithmwithout fairness constraints as the baseline (denoted by BL); (2) two methods (denoted by A1 and A3) from [Kusner et al., 2017] where A1 uses non-descendants of S only for building classifiers, and A3 presuppose the additive noise model for estimating the noise terms, which are then used for building classifiers; (3) our method (denoted as CF). By default, the discrimination threshold τ is set as 0.05.

5.1 Datasets

Synthetic Data. We manually build a causal model (where all variables are discrete) with complete knowledge of the exogenous variables and the functions (i.e., the contingency table) using Tetrad [Scheines et al., 1998]. The corresponding causal graph is shown in Figure 2a. This causal model consists of 5 endogenous variables, A, S, M, N, Y , and 5 independent exogenous variables, UA, US, UM, UN, UY . For simplicity, all endogenous variables have two domain values and all exogenous variables have three domain values. The distributions of the exogenous variables and the deterministic functions of the endogenous variables are randomly assigned. Then, we generate 100,000 examples from this causal model and split the data into training and testing sets with a ratio of 80/20. We consider S as the sensitive attribute and Y as the decision attribute. The profile attribute set Z contains A,M.

Adult Data. This dataset consists of 65,123 records with 11 attributes including education, sex, income etc.. We select 7 attributes, binarize their domain values, and split the dataset into the training and testing sets, following the 80/20 ratio. We apply the PC algorithm implemented in Tetrad to build the causal graph while the significant threshold is set as 0.01 for conditional independence testing. We use three tiers in the partial order for temporal priority: sex, age in Tier 1, education, marital-status and workclass are defined in Tier 2, and income defined in Tier 3. The causal graph is shown in Figure 2b, where sex is considered as the sensitive attribute and income is the decision attribute. age, education, maritalstatus, and workclass are contained the profile attributes Z.

5.2 Experiment on Synthetic Data

Quantifying Counterfactual Fairness. According to Theorem 1, the counterfactual fairness quantity is unidentifiable in this dataset. We evaluate the bounds of counterfactual fairness using Theorem 2. The ground truth (i.e., the exact values of all counterfactual quantities) is computed by applying the Abduction-Action-Prediction method. The results are shown in Table 1, where the first column indicates the indices of z's value combinations. As can be seen, the exact values of DE(ˆ ys-→s+|z) fall into the range of our bounds for all value combinations of Z, which validates our theorem.

BuildingCounterfactually FairClassifiers. We then evaluate the classifier learning methods. For the baseline method, we adopt the logistic regression (LR) and support vector machine (SVM). Then, we apply A1, A3, and CF on top of both classifiers. The counterfactual fairness is precisely evaluated and shown in Table 2 for all the methods using the Abduction-Action-Prediction method. The predictive accuracy is reported in Table 3. As expected, both A1 and CF achieve fairness, but our method achieves higher accuracy than A1, implying that A1 loses more information. On the other hand, we see that BL fails to achieve counterfactual fairness, because it ignores the fairness during the training. In addition, A3 also fails to achieve counterfactual fairness. This implies that assuming additive model may produce biased results when the underlying causal model is non-linear.

5.3 Experiment on Adult Dataset

We evaluate the fair classifier learning methods using the Adult dataset. Since we don't have the ground truth, we report bounds of counterfactual fairness for different methods. Table 4 shows that only A1 and CF can achieve counterfactual fairness for all value combinations of Z, but our CF consistently achieves higher accuracy than A1 as shown in Table 5. This is as expected since A1 is proved to be fair in [Kusner et al., 2017] (and also identifiable according to Theorem 1), but will inevitably lead to lower accuracy as only S's nondescendants are used. For BL and A3 in Table 4, either the lower bound is larger than τ or the upper bound is less than -τ, indicating the τ-counterfactual fairness is not achieved.

6 Conclusion

We focus on the unidentifiability challenge when applying counterfactual fairness in practice. We decompose the counterfactual quantity and identify the source of unidentification by leveraging the counterfactual graph and c-component factorization from Pearl's framework. We then develop the criterion of identification and the upper/lower bounds for counterfactual fairness. Finally, we formulate counterfactually fair classification as a linear programming problem. Empirical evaluations show our method is guaranteed to achieve counterfactual fairness in classification, while previous approaches either cannot achieve counterfactual fairness or suffer bad performance due to over-simplified assumptions.

Acknowledgments

This work was supported in part by NSF 1646654.