Machine learning (ML) is being increasingly applied to decisionmaking in sensitive domains such as nance, healthcare, crime prevention and justice management. Although it has the potential to overcome undesirable aspects of human decision-making, concern continues to mount that its opacity perpetuates systemic biases and discrimination reected in training data [3,4,47]. This concern has caused increasing regulations and demands for generating human understandable explanations for the behavior of ML algorithms-an issue addressed by the rapidly growing eld of eXplainable Articial Intelligence (XAI ); see [66] for a recent survey.
The development of XAI methods is motivated by technical, social and ethical objectives [12,24,46,48,55] including: (1) providing users with actionable insights to change the results of algorithms in the future, (2) facilitating the identication of sources of harms such as bias and discrimination, and (3) providing the ability to debug ML algorithms and models by identifying errors or biases in training data that result in adverse and unexpected behavior.
Most XAI research to date has focused on generating featurebased explanations, which quantify the extent to which input feature values contribute to an ML model's predictions. In this direction, methods based on feature importance quantication [5,24,30,56,58,59,65,86], surrogate models, causal and counterfactual methods [59,75,76], and logic-based approaches [23,40,81] are designed to reveal the dependency patterns between the input features and output of ML algorithms. These methods dier in terms of whether they address correlational, causal, counterfactual or contrastive patterns. While such explanations satisfy the aforementioned objectives (1) and (2) if we only consider the test data as a source of bias, they fall short in generating diagnostic explanations that let users trace unexpected or discriminatory algorithmic behavior back to the training data. Hence, they fail to satisfy objective (3) if the training data is the source of the bias. Indeed, information solely about output-input feature dependency is insucient to explain discriminatory and unexpected algorithmic decisions in terms of data errors and biases introduced during data collection and preparation. While a feature-based explanation can identify which features of a test data point are correlated with a misprediction or bias, it does not explain why the model exhibits this bias. To explain such behavior, we must trace the bias back to the data used to train the model. For example, feature-based approaches cannot generate explanations of the form: "The primary source of gender bias for this classier, which decides about loan applications, is its training data which exhibits bias against the credit scores of unmarried females who are house owners. "
In this paper, we take the rst step toward developing a framework for generating diverse, compact, and interpretable training data-based explanations that identity which parts of the training data are responsible for an unexpected and discriminatory behavior of an ML model. Specically, we introduce G, a system that nds patterns which compactly describe cohesive sets of training data points that, when eliminated, reduce the bias of the model. In other words, if the ML algorithm had been trained on the modied training data, it would not have exhibited the unexpected or undesirable behavior or would have exhibited this behavior to a lesser degree. Explanations generated by our framework, which complement existing approaches in XAI, are crucial for helping system developers and ML practitioners to debug ML algorithms by identifying data errors and bias in training data, such as measurement errors and misclassications [35,42,94], data imbalance [27], missing data and selection bias [29,61,62], covariate shift [74,82], technical biases introduced during data preparation [85], and poisonous data points injected through adversarial attacks [36,43,64,83]. It is known in the algorithmic fairness literature that information about the source of bias is critically needed to build fair ML algorithms because none of the current bias mitigation solutions ts all situations [27,31,36,82,94]. We use the example shown below to illustrate the dierence between feature-and data-based techniques, that explain bias based on the contribution of a subset of the training data.
Example 1.1. Consider a classier that predicts whether individuals described by their attributes (such as gender, education level, marital status, working hours, etc.) earn more than 50K a year. A system developer uses the classier to predict the income of individuals and, while analyzing the results, nds an unexpected negative result (earning less than 50K) for a female user: Based on her education (education = Bachelors), marital status (marital = Never-married), (age=34), and other features, this user should be classied as earning more than 50K. Upon closer examination, the developer realizes that the classier violates the commonly used fairness metric of statistical parity with respect to the protected group gender = 4<0;4. Statistical parity requires that the probability of being classied as the positive class (earning more than 50K in our example) is the same for individuals from the protected group as it is for individuals from the privileged group (we present fairness denitions in Section 2).
The developer uses an existing XAI package, such as LIME [75] or SHAP [59], to explain the algorithm's output for the user and learns that the user's gender and unmarried status were most responsible for the faulty prediction. We show examples of such explanations in Figure 1(a) and (b). These explanations, however, do not help the developer identify the source of the model's bias. In contrast, G identies cohesive subsets of the training data that are most responsible for the bias and compactly describes the subsets using patterns that are conjunctions of predicates. Figure 1(c) shows the top-3 explanations G produces. Pattern q 2 states that a sub-population that strongly impacts model bias is male spouses who work in the federal government for less than 40 hours per week. Indeed, in the Adult Income dataset (see Section 6), this subpopulation is the major source of gender bias, because it reports household income; hence, due to the bias in data collection, married males becomes highly correlated with high-income. In addition to producing such explanations, G also identies homogeneous updates for sub-populations that can maximally improve model bias. Figure 1(d) shows one such update (with bold outline). For instance, model bias would signicantly decline if we changed relationship status from "Spouse" to "Not married" and Workclass from federal employee to self-employed in the subset of the training data corresponding to q 2 . Such updates mean that our approach not only identies which subsets of training data are responsible for the bias, but also which features of the data points in these subsets are responsible.
Root causes and responsibility. Our rst contribution is to formalize root causes of bias and the causal responsibility of a subset of the training data for the bias of an ML model. Responsibility is measured as the dierence between the bias of the original model and that of a new model trained on the modied training data, obtained by either removing or updating the subset. We dene data-based explanations for bias as the top-k subsets of the training data that have the highest causal responsibility toward model bias. Pattern-based explanations. Such "raw explanations" based on subsets of data points may overwhelm (rather than inform) endusers. More compact and coherent descriptions are needed. Furthermore, sources of bias and discrimination in training data are typically not randomly distributed across dierent sub-populations; rather they manifest systematic errors in data collection, selection, feature engineering, and curation [29,35,42,61,62,69,94]. In other words, more often than not, certain cohesive training data subsets are responsible for bias. Our system generates explanations in terms of compact patterns expressed as rst-order predicates that describe homogenous training data subsets. By identifying commonalities within training data subsets, which are the main contributors to model bias, such explanations unearth the root causes of bias. To ensure that the generated explanations are diverse, our system lters explanations that refer to similar subsets of training data. Computational challenges. Computing such explanations is challenging for two main reasons. First, computing the causal responsibility of a given subset of data requires retraining the ML model, which is expensive. Second, it is computationally prohibitive to explore all possible subsets of training data to identify the top-: explanations. To address the rst challenge, we trace the model's predictions through its learning algorithm back to the training data. To do so, we approximate the change in model parameters by using either inuence functions [22] or by assuming that the updated model parameters can be computed by applying a single gradient decent step to the original model. First-order (FO) approximations of inuence functions have recently been proven useful in ML model debugging [50] by identifying the top-k training data points responsible for model mis-predictions. However, they do not eectively capture the ground truth inuence of training data subsets because of correlations between data points. To better approximate the change in model parameters, we utilize second-order (SO) inuence functions, which were shown to better correlate with ground truth subset inuence [9]. While even SO inuence functions can provide relatively poor estimates of the inuence of large portions of the training data, the approximation error of SO inuence functions is typically much better for coherent sets of data points as described by our patterns. To address the second challenge, we develop a lattice-based search algorithm based on ideas from frequent itemset mining [6] to discover frequent patterns. Our algorithm identies coarse-grained subsets of training data that are inuential and successively renes them to discover smaller inuential subsets. We introduce a novel quality metric for explanations, and optimizations that further prune the search space and eciently generate the top-k explanations. Update-based explanations. G is unique in that, in addition to generating explanations in terms of data removal, it also considers explanations based on updating data points. This aspect of G is motivated by the observation that not all features of a data point are erroneous and responsible for the bias. To identify an update that mitigates bias, we search for a homogeneous perturbation of some of the feature of the training data points described by a pattern (explanation) that leads to a maximal reduction in model bias. By homogeneous we mean that all data points in the subset are updated using the same perturbation vector, e.g., we change the marital status from never-married to divorced. We formulate the problem of computing update-based explanations as a constrained optimization problem that searches for a homogeneous update to a subset of training data in order to maximize bias reduction, and we solve it using projected gradient descent [15]. We make the following contributions:
• We formalize interventions on training data that remove or update training data points and estimate their eect on ML model bias.
Utilizing intervention, we dene predicate-based causal explanations to identify training data subsets that contribute signicantly to ML model bias (Section 3).
• We approximate the eect of training data deletion on model bias (Section 4.1) to avoid expensive retraining.
• We propose a principled approach for generating top-k explanations based on frequent pattern mining and use pruning techniques to reduce the size of the search space (Section 4.2).
• We introduce update-based, actionable explanations. These explanations identify not only which parts of the training data are responsible for the bias but also how to reduce or "repair" the bias. We formalize the problem of nding the most eective explanation as a constrained optimization problem that maximizes bias reduction. We propose a new algorithm based on projected gradient descent to determine the best homogeneous update for a responsible training data subset (Section 5).
• We conducted extensive experiments using real-world datasets to evaluate: (1) the end-to-end performance of G, (2) the accuracy of inuence estimation techniques, and (3) the quality and interpretability of explanations (Section 6). We show that G generates explanations that are consistent with insights from existing literature.
We now present pertinent background information on classication and algorithmic fairness. z,\). We denote the optimal parameters \ ⇤ of a classier as \ when it is clear from the context. Throughout this paper, we consider learning algorithms that use a loss function L(\ ) that is twice-dierentiable, which covers classication algorithms such as logistic regression [71], support vector machines (SVM) [71], and feedforward neural networks [88].
Algorithmic fairness. Consider a binary classier 5 \ with output . and a protected attribute ( 2 X, such as gender or race. Without loss of generality, we interpret . = 1 as a favorable (positive) prediction and . = 0 as an unfavorable (negative) prediction. To simplify the exposition, we assume D(() = {0, 1}, where ( = 1 indicates a privileged and ( = 0 indicates a protected group (e.g., males and non-males, respectively). Algorithmic fairness aims to ensure that the classier 5 makes fair predictions devoid of discrimination with respect to the protected attribute(s). Many fairness denitions have been proposed to quantify the bias of a binary classier (see [91] for a recent survey). The best-known ones are based on associative relationships between the protected attribute and the classier's outcome. These denitions are unlike causal notions of fairness, which incorporate background knowledge about the underlying data-generative process and dene fairness in terms of the causal inuence of the protected attribute on the classier's outcome [49,53,68,79]. We focus on three of the most widely used associational notions of fairness:
Statistical parity requires an algorithm to classify both the protected and privileged group with the same probability:
Equal opportunity requires both the protected and privileged group to have the same true positive rate:
Predictive parity requires that both protected and privileged groups have the same predicted positive value (PPV), i.e., correct positive predictions have to be independent of the protected attribute:
In practice, these fairness notions are often evaluated by estimating the probabilities on a test dataset D C4BC . Note that our techniques also work for other associational and causal notions of fairness (more details are in our technical report [73]).
In this section, we introduce root causes for bias and dene databased explanations for the bias of a classier. For now, we focus on generating explanations based on removal of data points from training data. In Section 5, we extend our framework to support explanations which update data points.
Consider a training dataset D, a learning algorithm A, a classier 5 \ trained by running A on D, and a fairness metric (Section 2)
where \ S is a classier trained on D S = D \ S.
Next, we introduce a metric to quantify the causal responsibility of a training data subset toward classier bias.
The larger the value of R F , the greater the responsibility of S toward bias. If R F (S) 0, then removing S from training data either does not change bias or further exacerbates it.
We dene data-based explanations based on causal responsibility. To formalize the notion of pattern-based explanations, we rst introduce patterns and dene an interestingness score for patterns.
A pattern q is a conjunction of predicates q = " 8 q 8 where each q 8 is of the form [-op 2], where -2 X is a feature, 2 is a constant and op 2 {=, <, , >, }.
Patterns represent training data subsets. For example, the pattern q = (gender = 'Female') ^(age < 45) describes data points where gender is 'Female' and age is less than 45. We use D to denote the set of all patterns dened over the training data D and denote the set of data points satisfying pattern q by D(q). Denition 3.4 (Support of a paern). The support of pattern q is denoted by (D? (q) and is dened as the fraction of data points that satisfy q, i.e., (D? (q) = |D(q)| |D|. Denition 3.5 (Interestingness of a paern). Given a biased classier 5 \ and a pattern q, we dene the interestingness of q to explain the bias of the classier 5 \ as:
The intuition behind our denition of interestingness is that if two patterns result in the same reduction in model bias, we are more interested in the pattern that requires fewer changes to the data (less support). Thus, interestingness measures the average bias reduction per data point covered by a pattern.
In addition to nding patterns with high interestingness scores, we also aim to return a diverse set of patterns that have little overlap in terms of the data points that they contain. Diversity helps us avoid returning patterns that are too similar to each other, i.e., that dier only in minor details. This is a desirable property because patterns with large overlap convey similar information and, thus, lead to redundancy. We capture the notion of diversity through a containment score as dened next. Denition 3.6 (Containment score). Given patterns q and q 0 , the containment score ⇠ measures the fraction of q contained in q 0 :
Furthermore, for a pattern q and a set of patterns , we dene
).
The containment score quanties the overlap between the data represented by a pair of patterns. Similar patterns have a higher fraction of overlapping data points (a containment score close to 1) and largely convey the same information dierently. Dissimilar or diverse patterns, have a containment score closer to 0.
We are now ready to formalize the problem of generating the top-: diverse and interesting data-based explanations: Denition 3.7 (Top-: explanations). Generating the top-: databased explanations for the bias F of a classier requires nding the top-: most responsible and diverse explanations. Formally, given a containment threshold 2, the goal is to compute a set : ✓ D of explanation candidates as dened below.
* (q), for 1 < 8 :.
Intuitively, : is computed by iteratively including into the current result set the next candidate with the highest score, skipping any candidate patterns whose overlap with one of the explanations in the result we have computed so far exceeds the threshold 2. Note that : is not well-dened if multiple patterns have the same score. We impose an arbitrary order over D to break ties.
Two major challenges complicate eorts to eciently compute top-: explanations. First, computing the causal responsibility of a pattern is computationally intensive: we have to train a new classier on the intervened training data obtained by removing the subset of data points covered by the pattern. Second, it is computationally prohibitive to exhaustively explore the space of all candidate explanations, which is exponential in the number of features.
This section describes our methods for addressing the challenges of computing top-: explanations for the bias of an ML model. First, we describe how to eciently approximate the causal responsibility of a training data subset, without having to retrain classiers (Section 4.1). Then, we develop a lattice-based search algorithm which utilizes the approximation methods for estimating causal responsibility to eciently generate top-: explanations (Section 4.2).
We now describe two methods for approximating the causal responsibility of a subset of the training data D on classier bias without retrain the classier. The rst method uses inuence functions (Section 4.1.1). The second is a simple, yet eective, approximation based on gradient descent (Section 4.1.2).
Recall from Section 2 that the optimal model \ ⇤ is the element of the set of possible models ⇥ minimizing the empirical risk, i.e.,
Let r \ L(\ ) and
be the gradient and the Hessian of the loss function, respectively. Under the assumption that the empirical risk L(\ ) is twice-dierentiable and strictly convex, it is guaranteed that H \ exists and is positivedenite, which further implies Hfoot_0 \ exists. 1 The inuence of up-weighting a data point z 2 D by n on the model parameters is computed as (detailed derivation in [73]):
To remove data point z, we consider up-weighting it by n = 1 = . The change in model parameters due to removing z can, therefore, be linearly approximated by computing 3\ ⇤ n ⇡ 1 = I \ (z). Inuence of subsets. Using rst-order (FO) inuence function approximation (Equation ( 2)), the eect of removing a subset of data points S ✓ D on model parameters can be obtained by:
The approximation shown in Equation ( 3) is quite accurate when the parameters of the updated model are close to those of the original model: because we estimate the eect of removing a set of data points by summing their individual eects, which means that we assume that the eect of removing one data point on the model is independent of the eect of removing any other data point. Put dierently, when approximating the inuence of a data point, we assume that the removal of other data points will not aect the model. While in general this assumption does not hold, it leads to an acceptable approximation if a small fraction of training data points is removed, but accuracy will decline when a larger fraction of training data is removed. For such large model perturbations, using higher-order terms can reduce approximation errors signicantly. This issue can be alleviated by computing the eect of uniformly up-weighting data points in a subset of training data by some small n, using the same idea as inuence functions but considering higher-order optimality criteria [9]. Specically, in the derivation of inuences, we do not ignore second-order terms of n for an even more accurate estimation of the group inuence of up-weighting a subset of training data points on model parameters, and we obtain the inuence as:
where
We refer the readers to [9] for detailed derivations of the above expression for the group inuence of a subset, but note that the second term (I 0 ) in the second-order (SO) approximation captures correlations among data points in S through a function of gradients and Hessians of the loss function at the optimal model parameters.
When training data points are correlated, the SO group inuence function is more informative and captures the ground truth inuence more accurately. We empirically compare the accuracy of rstand second-order inuence function approximations in Section 6. Causal responsibility. Inuence functions can be adopted to approximate causal responsibility using the chain rule of dierentiation, as follows. We can estimate the eect of up-weighting data points in S on a function 5 (\ ) as:
where
\ (S) depending on whether the inuence is computed using rst-or second-order group inuence function approximations, respectively.
Given a fairness metric F , I F (S) captures the eect of intervening on S on the bias of the classier and is used as the numerator in Denition 3.2 to compute the responsibility of S.
As shown in [50], FO inuence function approximations can be used to update individual training data points to maximize test loss. However, they deviate from ground truth inuence for a group of data points because they do not capture the data correlations in a group [10]. SO inuence functions, on the other hand, capture correlations but have only been explored for the case of subset removal [10].
To generate update-based explanations, we introduce an alternative approach for approximating causal responsibility. We assume that the updated model parameters are obtained through one step of gradient descent (which we use in Section 5) and empirically nd explanations that are more accurate than even SO inuence approximations (details in Section 6.3).
Note that as in Equation ( 1), the updated model parameters when a subset of data points is removed are given by:
The preceding equation can be solved using gradient descent by taking repeated steps in the direction of the steepest descent of the loss function (for data points in D \ S). However, inspired by the existing literature in adversarial ML attacks [44], which assumes that model parameters do not change signicantly when a small subset of data points is poisoned, we assume minimal change in model parameters. Thus, the change in model parameters is approximated in terms of a single step of gradient descent, as follows: where [ is the learning rate for the gradient step.
The eect of removing S on bias is then computed as the dierence in test bias before and after S is removed:
). While our single-step gradient descent approach can be used to estimate subset inuence, this may not be a good idea for learning algorithms that use more ecient techniques than gradient descent. We, therefore, use this approach mainly for generating update-based explanations in Section 5.
Having discussed several techniques for eciently approximating inuence, we now introduce our algorithm for nding the top-k explanations according to Denition 3.7. As discussed in Section 1, the naïve approach for computing the top-k explanations by evaluating all possible patterns is exponential in the number of attributes, and, thus, is infeasible even when we estimate the inuence of patterns.
Toward this objective, we propose ComputeCandidates, an algorithm that takes the training data as input and generates a list of candidate patterns. Figure 2 shows an example of part of the lattice search space for patterns. ComputeCandidates generates explanations starting with patterns each having a single predicate. The algorithm then iteratively generates patterns with 8 predicates by merging two patterns with 8 1 predicates that dier in only one predicate. For instance, it merges patterns 4 and 5 in Figure 2 into pattern 7 . The idea is similar to frequent itemset mining [6,39] in data mining where itemsets with = items are generated by successively merging candidate itemsets of smaller size.
By itself, building patterns bottom-up does not reduce the size of the search space. We propose two heuristics to address this issue. The rst heuristic is that we assume as input a support threshold g and only consider patterns whose support is above g. The rationale for this heuristic is that patterns with low support describe only a small portion of the training data and, thus, are unlikely to identify systematic issues. In our experiments in [73], with g as small as 1%, we did not observe patterns with low support reducing bias by much, and found much larger patterns (with ⇠ 27% support) dominating the top-k. For a candidate pattern q generated by merging patterns q 8 and q 9 we have sup(q) sup(q 8 ) and sup(q) sup(q 9 ). Thus, pruning q 8 prunes the entire sub-lattice whose root is q 8 . In Figure 2, pattern 3 is pruned since its support Session 4: Responsible Data Management and Fairness SIGMOD '22, June 12-17, 2022, Philadelphia, PA, USA (1%) is less than the threshold (5%). As a result, patterns formed by merging pattern 3 with another pattern, including patterns 5 and 7 and the entire sub-tree shaded blue , are also pruned. Our second heuristic is to prune patterns during merging. Consider a pattern q generated by merging patterns q 8 and q 9 . We only consider q if its responsibility exceeds the responsibility of the two patterns it is generated from: R(q) > R(q 8 ) and R(q) > R(q 9 ). Note that if this is the case, then * (q) > max(* (q 8 ), * (q 9 )), because * (q) = R F (D(q)) (D? (q) and as mentioned above (D? (q) min((D? (q 8 ), (D? (q 9 )). In Figure 2, we do not generate 4 (and subsequently its successors, shaded red ) because * (pattern 4 ) is less than both * (pattern 1 ) and * (pattern 2 ). The rationale for this heuristic is that patterns with more predicates are harder to interpret. Thus, an increase in the number of predicates should be justied by an increased impact on the bias of the model.
We now discuss our algorithm in more detail (pseudocode is shown in Algorithm 1). We start by generating all possible single predicate patterns (Line 1) by iterating through all features -2 X and each possible value E0; for the feature and generate three types of comparisons: -< E0;, -= E0;, and -> E0;. Note that for features with a large number of possible values, we can apply binning techniques to reduce the number of candidate patterns. Additionally, binning has the advantage of preventing the generation of almost identical explanations (e.g., hours < 40 and hours < 42).
We then iteratively create patterns (Line 7) of size 8 by merging two patterns of size 8 1 that dier in only one predicate to generate a candidate pattern of size 8. The algorithm terminates if no new candidates have been produced in the current iteration. For each generated candidate pattern q we test if its support is larger than the threshold g and its responsibility is larger than that of the patterns it was derived from. If both the conditions are fullled then we include q in 8 , the set of candidate patterns of size 8. Finally, we return all candidate explanations, which is the union of all sets 8 generated so far.
Note that while merging patterns, we do not have to consider patterns that are conicting. Patterns q 8 and q 9 are conicting if they both contain a predicate on an attributeand the conjunction of these predicates is unsatisable. In Figure 2, patterns 6 and 7 are conicting. The merged pattern q = 6 [ 7 has zero support, and we do not need to consider it further. Diversity of explanations. We use Algorithm 2 to compute a diverse set of top-k explanations as dened in Denition 3.7. We rst use ComputeCandidates to generate a set of candidate explanations, which is then sorted based on the interestingness score * . We iterate over the set in sort order, include patterns into the result, and skip patterns whose overlap with any of the previously added patterns exceeds the threshold 2.
We are interested in patterns that, when removed or modied, reduce bias maximally without signicantly aecting model accuracy. Instead of directly optimizing for minimal accuracy loss, we penalize patterns with high support (or, low interestingness score). As an extreme example, we can remove the entire data (that has the maximum support) and obtain a perfectly unbiased classier that makes random guesses. However, such a pattern has no explanatory value. This intuition aligns with the notion of minimality in database repair that seeks to nd minimal subsets of data responsible ; 10 for q 8 , q 9 2 8 1 do 11 if |q 8 \ q 9 | = 8 2 ^(D? (q 8 [ q 9 ) g then 12 q = q 8 [ q 9
13 if I (q) > I (q 8 ) ^I(q) > I (q 9 ) then for an inconsistency. Optimizing for bias reduction and accuracy loss simultaneously is an interesting direction for future work. Note that G's explanations describe training data subsets that may have potential data quality errors or point to historical biases reected in training data or bias that was introduced during data collection. These errors are not detectable using standard data cleaning algorithms such as outlier detection. G can be complemented with existing error detection mechanisms or external sources of information on data provenance to expose the errors in the identied subsets.
In this section, we formalize the problem of generating explanations based on updating training data. Given an inuential subset of training data obtained through the techniques proposed in Section 4, our goal is to nd a homogenous update that can lead to maximum bias reduction. Toward that goal, we rst discuss an approach for approximating the inuence of updating or perturbing a subset of training data on model bias.
Consider a classier with optimal parameters \ ⇤ trained on a training dataset D. Let S = {z 8 = (X 8 , . 8 )} < 8=1 be a subset of D consisting of < data points. Also, let S ? = {z ? 8 = (X ? 8 , .
? 8 )} < 8=1 be the result of uniformly updating each instance in S using a perturbation vector % = {X 1 , . . . , X |X | }. The attribute values of each data point z 2 S are updated by applying the perturbation vector: z ? = z+%, i.e., the 9-th attribute of z is updated by X 9 . For example, if the value of the working hours attribute for an individual is 32, then an update of 8 will change it to 40. In this example, uniform perturbation means that the working hours for all individuals from the subset S are increased by 8. Our goal is to compute the optimal parameters \ ? for a new model trained on D ? = (D \ S) [ S ? . We approximate \ ? using a single step of gradient descent (Section 4.1.2), as follows:
where [ is the learning rate for the gradient step. Therefore, the inuence of an update to S on the bias of the model can be measured using the chain rule, as follows:
Now, given a subset of training data, S ✓ D, our goal is to obtain an update on S that leads to the maximum bias reduction. That is, we want to solve the following optimization problem:
Using Equations ( 8) and ( 9), Equation (10) becomes:
We solve Equation (11) using the gradient descent algorithm to obtain the perturbation vector:
where [ is the learning rate of the gradient ascent step. An updated data point is obtained as z ? = z + % :+1 . Note that the preceding formulation can result in perturbations that lie outside the input domain. We add domain constraints to prevent this from happening. In particular, the updates should change an attribute of a data point from one value to another in the input domain, i.e., z, z ? 2 D(X) ⇥D(. ). We solve this constrained optimization problem in Equation ( 12) using projected gradient descent [20], which works as follows: if the updated data point violates the domain constraint, i.e., z ? 8 D(X) ⇥ D(. ), then project it back to the input domain D(X) ⇥ D(. ) as:
The projection ensures that z D? is the data point in the input domain D(X) ⇥ D(. ) that is closest to the actual perturbation z ? .
In our experimental evaluation of G, we aim to address the following questions: Q1: How eective are the proposed techniques for approximating causal responsibility of training data subsets? Q2: What is the end-to-end performance of G in generating interpretable and diverse data-based explanations? Q3: What is the quality of the update-based explanations? Q4: How eective is our approach at detecting data errors responsible for ML model bias?
c) Support vector machine (SVM).
Figure 3: Comparing inuence function approximations (first-order IF and second-order IF) against the one-step gradient descent approach (one-step GD) for estimating subset inuence on the German dataset.
We use standard datasets from the fairness literature. The data and code for the experiments can be found at the project page 2 . German Credit Data (German) [26]. Personal, nancial and demographic information (20 attributes) of 1, 000 bank account holders. The prediction task classies individuals as good/bad credit risks. Adult Income Data (Adult) [26]. Demographic information, level of education, occupation, working hours, etc., of 48, 000 individuals (14 attributes). The task predicts whether the annual income of an individual exceeds $50K. Stop, Question, and Frisk Data (SQF) [1]. Demographic and stop-related information for 72, 548 individuals stopped and questioned (and possibly frisked) by the NYC Police Department (NYPD). The classication task is to predict if a stopped individual will be frisked.
We considered three ML algorithms: logistic regression, support vector machines, and a feed-forward neural network with 1 layer and 10 nodes (we provide details about the hyper-parameters for in the G repository 3 ). We used the PyTorch [70] or sklearn [71] implementation of these algorithms. In accordance with existing literature on evaluation of fairness of ML algorithms on these datasets [19], the sensitive attributes are: gender (Adult), age (German), race (SQF). We implemented our algorithms in Python and used PyTorch's autograd package to compute the gradients and Hessian. At start up, we pre-computed the Hessian and gradients for faster computation of the inuence function approximations. We split each dataset into training and test data, trained an ML model over the training data, and generated explanations using our pattern generation algorithm. We report the top-k explanations for each dataset under dierent scenarios. For each explanation, we report the pattern q, its support (D? (q), and the ground truth change in bias (reported in terms of statistical parity unless stated otherwise) achieved by removing the data corresponding to the pattern from the training data. We solve Equation ( 13) using SciPy's optimize package for constrained optimization. For update-based explanations, we report the update to the data corresponding to the explanation's pattern and the change in bias resulting from the update. For both kinds of explanations, predicates that occur in more than one pattern are color-coded. We use the logistic regression model as the default ML model. Baseline. As a competitor for our approach, we trained a decision tree regressor (referred to as FO-tree) over FO inuence approximations of data points. FO-tree splits the training data into nonoverlapping subsets based on the values of an attribute at a node of the tree. The path from the root to a node of the tree corresponds to a conjunction of predicates that characterize the data points represented by that node. To generate the top-: explanations consisting of up to ; predicates, we identify the : nodes from the root (level 0) to level ; that have the maximum combined inuence of data points, and report the paths from the root node to these nodes. For example, to generate top-5 explanations with up to 3 predicates, we identify the 5 nodes up to a depth of 3 having the maximum FO inuence and report the conjunction of predicates that form the path from the root to each of these node.
In this set of experiments, we evaluated the quality of the proposed approaches for approximating inuence, and thereby causal responsibility. The ground truth inuence of subsets is computed by retraining the model after removing the subset from the training data. To estimate subset inuence using FO approximations, we summed the individual inuences, whereas the SO subset inuence is computed using Equation ( 4). We also compared the approximations for the one-step gradient descent approach described in Section 4.1.2, because we use this approach for update explanations.
Eectiveness. In Figures 3a to 3c, we report the absolute deviation of the inuence estimated by the dierent methods from the ground truth (y-axis) for the fairness denitions (x-axis) described in Section 2. We trained dierent classiers on the German dataset. We observed that, as expected, FO inuence approximations and one-step gradient descent deviated more from ground truth inuence than SO inuence. FO inuence approximation exhibits larger errors because it does not account for possible correlations among data points in the subset [10]; one-step gradient descent inuence approximation is not accurate because it uses a single step of gradient descent instead of iterating until the model parameters converge. This behavior is especially evident when the size of the group is large, which usually corresponds to large inuence (the bars on the outside of a metric). The key takeaway from this experiment is that SO inuence functions closely approximate ground truth inuence especially when model parameters do not change substantially (the middle bars). Eciency. In Figure 4, we report the average time taken by each method when subsets of varying sizes are removed from the training data. The brute force approach -retraining the model after removing the subset -is typically more than two orders of magnitude slower than even the most expensive method, especially when the fraction of removed training data points is small (e.g., inuence functions are up to 4 orders of magnitude faster when 0%-10% of the training dataset is deleted). We also observe that the one-step gradient descent approach, with the exception for SO inuence functions on neural networks, while eective in estimating ground truth inuence (as shown in Figure 3a, Figure 3c), is signicantly slower than inuence functions for estimating subset inuence. 7.39% 6.02%
Table 2: Top-3 explanations on Adult (g = 5%, neural networks, runtime=56s).
180B Race = Black ^Fits a relevant description=No ^Location=Outside ^Age< 25
16.89% 25.6%
Race = Black ^Fits a relevant description=No ^Location=Outside ^Age2 [25,45] 12.95% 13.7%
Race = White ^Engaging in a violent crime=No ^Casing a victim=Yes ^Proximity to scene of o↵ense=No 7.04% 8.16%
Table 3: Top-3 explanations for SQF (g = 5%, logistic regression, runtime=91s).
Note that the time cost for retraining is close to that of one-step gradient descent because we used the initial model parameters to speed up convergence during retraining. In practice, we have to adjust the learning rate for one-step gradient descent over multiple iterations, which makes it even more expensive. We conclude that retraining the model and using the one-step gradient descent approach are not feasible for generating the top-: explanations. The one-step gradient descent, however, is useful for generating update-based explanations as described in Section 4.1.2: inuence functions are not applicable to the optimization problem we have to solve for updates, and retraining is also not an option.
Next, we evaluate the performance of G for generating the top-: explanations for ML algorithms trained on dierent datasets.
German. This dataset is biased toward older individuals and considers them less likely to be characterized as high credit risks. In Table 1, we report the top-3 explanations up to 4 predicates generated by G (with their support and ground truth inuence) sorted by their interestingness score. We observe that one subset of 5% of data points explains more than half of the model bias, whereas another subset of around 6% of data points reduces bias by almost 36%. These explanations highlight fractions of training data that may have potential errors and hence, need attention. On inspection, we found that they correspond to training data points where older individuals are primarily labeled as low credit risks. By removing these individuals, the probability of an individual being classied as a high/low credit risk is uniformly distributed across the sensitive attribute age. As a result, the model's dependency on age is reduced, thus reducing overall model bias. Note that the top-2 explanations consist of predicates with the sensitive attribute for this dataset, signifying its importance in bias reduction. In comparison, we made the following observations about the explanations generated by FO-tree: entirely dierent regressor trees, and hence dierent explanations, were generated depending upon whether sklearn or PyTorch was used to t the model. While the sensitive attribute (age) formed the root node for the FO-tree generated on the PyTorch model, a non-intuitive attribute (installment rate) was the root in the FO-tree for the sklearn model. The top-2 explanations from FO-tree over the PyTorch model were consistent with our explanations whereas those generated from FO-tree over the sklearn model were less compact (consisting of 4 predicates each). Their (support, bias reduction) were (6.13%, 32.3%), (5.63%, 33.1%) and (12.9%, 8%), respectively. Adult. This dataset has been at the center of several studies that analyze the impact of gender [78,87] and has been shown to be inconsistent: income attributes for married individuals report household income. The dataset has more married males, indicating a favorable bias toward males. As seen in Table 2, the sensitive attribute gender plays an important role in all of the explanations. In this set of experiments on neural networks, we observed that second-order inuence functions did not estimate the model parameters accurately and greatly underestimated the ground truth inuence. This observation was consistent with the analysis provided in [10] for neural networks where the inuence of a group of data points has low correlation with ground truth inuence, and second-order inuences underestimate ground truth inuence. Our approach hinges on the applicability of inuence functions to correctly estimate the model parameters around the optimal parameters-an assumption that might not hold for neural networks. G still identied patterns that reduce model bias to some extent. In comparison, the top-3 patterns returned by FO-tree had higher support and lower ground truth inuence: (10.9%, 9.8%), (13.2%, 10.8%) and (5.9%, 11%), respectively. Note that even though the dataset has single predicates ([marital = Married], ⇠ 47% data) that remove bias almost completely, these predicates do not rank in the top-: explanations because of their low interestingness scores. SQF. This dataset highlighted that the practices of NYPD in stopping, questioning and frisking blacks (and latinos) more often compared to whites were unconstitutional and violated Fourth Amendment rights [2]. In Race = Black ^Fits a relevant description=No ^Location=Outside ^Age2 [25,45] 14.3% # Race = Black ^Fits a relevant description=No ^Location=Outside ^Age2 [25,45] 13.0% 13.7%
Race = White ^Fits a relevant description=Yes ^Location=Inside ^Age2 [25,45] 8.6% # Race = White ^Engaging in a violent crime=No ^Casing a victim=Yes ^Proximity to scene of o↵ense=No 7.0% 8.2%
Race = White ^Engaging in a violent crime=No ^Casing a victim=No ^Proximity to scene of o↵ense=Yes 13.7% " Table 6: Update-based explanations for the top-3 explanations for SQF ( g = 5%). Updates to the original explanation (top) are shown in bold outline (bottom). Change in bias reduction 180B is represented by # (decrease) or " (increase). Average time taken to update each point = 0.5s consisting of the protected group that were frisked and the privileged group that were not frisked. Because of these data points, the model learns that data points belonging to the privileged (protected) group are less (more) likely to be frisked, and therefore, cause bias in the model. By removing these data points, the privileged group becomes less correlated with the 'no frisk' outcome, thus reducing model bias. The topmost explanation generated by the FO-tree [(location=Outside) ^(race=White) ^(build<>Thin) ^(does not t a relevant description)] had similar support (13.2%) and bias reduction (27%) as our topmost explanation. The other two patterns had lower bias reduction (one of them had 0.15% reduction in bias) and greater support, and hence were less interesting.
In these experiments, we generated updates for the top-: explanations. For each explanation, we provide the perturbation that would result in the maximum bias reduction.
German. As seen in Table 4, updates typically involve perturbing the protected attribute (age). For example, the rst explanation suggests that by updating data points satisfying the pattern such that after the update they are in the protected instead of the privileged group, and by changing the gender to increase the chance of a positive outcome, bias is reduced by 42%. In this case, we found an update that would reduce model bias but not by as much as deleting those points would. Similarly, in explanation 2, older individuals that have a good credit history are considered low credit risks. By changing their age group to the protected group and credit history to a worse level, we now associate younger individuals with good credit risk and reduce model bias (albeit by an amount smaller than if the group was removed). The key takeaway here is that we can reduce model bias by updating the training data points referring to these patterns instead of removing them altogether. Adult. We report the update-based explanations for this dataset in Table 5. As mentioned before, this subset is biased toward married individuals and males. In explanation 1, individuals that were not married had lower income. By changing their marital status to married, we were able to reduce model bias by at least as much as would have been achieved those patterns deleted. Note, however, that in explanation 2, even by changing the gender and marital status to the preferred attribute values, we could not nd an appropriate update that would reduce the bias. After marital status, we found that education accounts for most of the bias [78]individuals with a higher level of education are associated with higher incomes. In explanation 2, by changing the education level we were able to reduce bias by almost the same amount as would have been achieved if the subset were altogether removed. SQF. In Table 6, we observe that changing particular attribute values can help us avoid discriminatory behavior for this dataset. For example, before the update in explanation 3, whites that appeared to be casing a victim (or studying them for probable targets) were not frisked -a clear case of discrimination. In this case, we were able to nd an update such that they did not case a victim even when close to the crime scene, and achieved even more reduction in model bias than if this subpopulation is removed altogether. Similarly, frisking blacks even when they do not t a relevant description was biased against them. In this case, updating this subset of data points such that whites that t a relevant description are frisked reduced the model bias but less than if the subset is removed.
To evaluate the scalability of inuence computations, we report in Figure 5 the eect of dataset size on the time taken to compute inuence of a subset by the approaches described in Section 4.1.
We replicated German to increase its size by a factor of 50 to 1, 600 yielding up to 1.6M training data points. To evaluate how dataset sizes aect inuence computation runtimes, we xed the size of the subset for which we compute the subset inuence to 5% (this threshold reects our problem setting where we are interested in small fractions of training data that need attention). We observed that both FO and SO inuence computations scale well in the dataset size, and achieve speed-ups of several orders of magnitude over retraining the model or using one-step gradient descent. Note that G has an upfront cost of pre-computing the gradients of the loss function and the Hessian. Once these computations are done, the time taken to compute subset inuence is negligible (as seen in Figure 5). In contrast, model retraining to compute subset inuence can be quite expensive. For example, using the feed-forward network on Adult, we observed that the pre-computations took ⇠ 1, 800B and the top-3 explanations were generated in 56B for a total time cost of ⇠ 1, 856B. In comparison, retraining the model after removing one subset took > 10B. We see benet in using G when a relatively large number of candidates are being considered to generate top-k explanations (which is the case with our datasets).
In Table 7, we report the time taken to generate the top-5 explanations on German when we allow more predicates in an explanation (indicated by the level in the lattice structure), and hence consider greater number of candidates. We observe that G's explanation generation using the lattice structure has good scalability (runtimes of < 25 min) for explanations with fewer predicates. In comparison, our ltering mechanism that accounts for diversity of explanations takes negligible amount of time (although considering more candidates increases the runtime of the ltering step).
To test the viability of G in detecting data errors, we applied our implementation as a detection mechanism for errors injected by data poisoning attacks [52,63]. The objective was to develop techniques to detect attacks that have superior performance (measured in terms of accuracy and fairness) on training data and are targeted at exacerbating model performance on test data. The state of the art in safeguarding against data poisoning attacks is to detect anomalies that do not conform to the rest of the data. However, anomaly detection fails in the presence of sophisticated attacks that are targeted at deteriorating model accuracy and/or fairness [36,43,64,83]. We performed experiments where we injected poisoned data points into the training data using non-random anchoring attacks [63]. We found that the outlier detection mechanism supported by scikitlearn [71], LocalOutlierFactor, was not able to detect any of the poisoned data points, because they follow a similar distribution as the original training data points. In comparison, when the data was clustered (using k-means or Gaussian mixture models clustering) and clusters were ranked in decreasing order of estimated SO inuence, we observed that the top-2 clusters contained almost 70% of poisoned points. While these results are promising, a detailed study demonstrating the eectiveness of second-order inuence functions in detecting adversarial attacks is out of the scope of this work and is an interesting direction for future work.
Our work relates to the following lines of research. Feature-based explanations. Much of XAI research focuses on explaining ML models in terms of dependencies between input features and their outcomes. Feature attribution methods quantify the responsibility of input features for model predictions [5,24,30,59,65,86]. Methods based on surrogate explainability approximate ML models using a simple, interpretable model [59,75]. Contrastive and causal methods explain ML model predictions in terms of minimal interventions or perturbations on input features that change the prediction [11,32,45,60,67,89,90,93]. Logic-based methods operate on logical representations of ML algorithms [23,40,81] to compute minimal sets of features that are sucient and necessary for ML model predictions. These approaches fall short in generating diagnostic explanations that help users trace an ML model's unexpected or discriminatory behavior back to its training data. Explanations based on training data. In contrast, data-based explanations attribute ML model predictions to specic parts of training data [14]. A popular approach ranks individual training data points based on their inuence on model predictions [10, 51] using inuence functions [22]-a classic technique from robust statistics that measure how optimal model parameters depend on training data points. Based on rst-order inuence functions, Rain [95] identies data points responsible for user constraints specied by an SQL query. Several recent works argue for the use of data Shapley values to quantify the contribution of individual data points [33,34,54], which is computationally expensive because the model needs to be retrained for each data point. Representer points explain the predictions of neural networks by decomposing the pre-activation prediction into a linear combination of activations of training points [98]. PrIU [96] is a provenance-based approach that incrementally computes the eect of removing a subset of training data points. Unlike prior methods, we generate: (1) explanations for the bias of an ML model, (2) interpretable explanations based on rst-order predicates that pinpoint a training data subset responsible for model bias, and (3) update-based explanations that reveal data errors in certain attributes of a training data subset. It is worth mentioning that model bias can be reduced not only by removing subsets of training data but also by adding appropriate training samples. Searching for in-distribution data points that explain away bias upon insertion into training data is a challenging problem that we plan to explore in the future. Note that our update-based explanations act as a combination of removing existing data points and adding new ones. Debugging ML models. Several recent works address debugging of ML models for bias, including fair-DAGs [97] and mlinspect [37] that attribute discrimination to class imbalance and address bias by tracking the distribution of sensitive attributes along ML pipelines. A closely related idea identies regions of the input domain that are not adequately covered by training data [7,8]. MLDebugger [57] identies minimal causes of unsatisfactory performance in ML pipelines using provenance of the previous runs. These approaches cannot highlight parts of training data responsible for biased outputs. DUTI [99] identies the smallest set of changes to training data labels so the model trained on the updated data can correctly predict labels of a trusted set of items from test data; this approach focuses on updating training labels, and is not applicable to our setting. Another line of work nds data slices in which the model performs poorly [21,72,77]; slices are discovered based on their association with model error and do not capture the causal eect of interventions. These techniques are not directly applicable to fairness where, unlike model error, bias due to a subset is not additive. Moreover, none of these interventions update data instances. Adversarial ML. We share similarities with adversarial ML that aims to degrade ML model fairness or predictions through adversarial attacks. The most relevant classes of attacks are based on data poisoning [18,84], which injects a minimum set of synthetic data points into the training data to compromise the performance or fairness of a model trained on the contaminated data [43,64,83]. In contrast, our goal is to detect those points. Machine unlearning. Our research also relates to the nascent eld of machine unlearning [13,38,41,80], which addresses the "right to be forgotten" provisioned in recent legislations, such as the General Data Protection Regulation (GDPR) in the European Union [92] and the California Consumer Privacy Act in the United States [25]. Current methods are typically designed for particular classes of ML models e.g., HedgeCut [80] supports ecient unlearning requests for decision trees. The techniques in this sub-eld could be integrated into our framework for ecient computation of causal responsibility. We defer this investigation to future study. Bias detection and mitigation. Prior work to detect and mitigate bias in ML models can be categorized into pre-, post-and in-processing methods [17]. We aim to pre-process data to reduce bias by removing bias and discrimination signals from training data [16,28,79], which is dierent from post-processing that deals with model output to handle bias, and in-processing that is aimed at building fair ML models. Pre-processing methods are independent of the downstream ML model, are usually not interpretable, and hence are insucient in generating explanations that reveal the potential source of bias. While not a direct focus of our research, our approach could help develop bias mitigation algorithms that are interpretable and account for the downstream ML model; hence, they would incur minimal information loss and generalize better. We defer this research to future work.
We present a novel approach for debugging bias in machine learning models by identifying coherent subsets of training data that are responsible for the bias. We introduce G, a principled framework for reasoning about the responsibility of such subsets and develop an ecient algorithm that produces explanations, which compactly describe responsible sets of training data points through patterns. We demonstrate experimentally that G is ecient and produces explanations that are interpretable and correctly identify sources of bias for datasets where ground truth biases are well understood. In the future, we plan to expand our approach beyond supervised ML algorithms with dierentiable loss functions to support a wider range of ML algorithms such as tree-based ML models and clustering algorithms. Moreover, we plan to leverage database techniques for incremental maintenance to eciently compute causal responsibility as opposed to approximating it. Another interesting future direction is to integrate G with database provenance to formalize the notion of provenance of ML model decisions that trace ML model outcomes all the way back to decisions made in the ML pipeline that might explain the bias and unexpected behavior of the model.
Please see[50] for a discussion on relaxing these assumptions on the loss function. Session 4: Responsible Data Management and Fairness SIGMOD '22, June 12-17,
2022, Philadelphia, PA, USA
https://github.com/romilapradhan/gopher Session 4: Responsible Data Management and Fairness SIGMOD '22, June 12-17, 2022, Philadelphia, PA, USA