Cohort Shapley value for algorithmic fairness

Variable importance measures have a long history and there has been a recent surge in interest motivated by problems of explainable AI. The global sensitivity analysis literature studies black box functions used in engineering and climate models among others. Much of that work is based on a functional ANOVA model of the function relating the output to inputs. Variance explained is partitioned using Sobol’ indices (Sobol’,, 1993). Saltelli et al., (2008) is an introductory textbook and Razavi et al., (2021) is a current survey of the field. Wei et al., (2015) provide a comprehensive survey of variable importance measures in statistics. They include 197 references of which 24 are themselves surveys. Molnar, (2018) surveys variable importance measures used in explainable AI. Prominent among these are SHAP (Lundberg and Lee,, 2017) and LIME (Ribeiro et al.,, 2016). LIME makes a local linear approximation to a black box function $f(\cdot)$ and one can then take advantage of the easier interpretability of linear models. SHAP is based on Shapley value from cooperative game theory (Shapley,, 1953), that we describe in more detail below.

Ordinarily we can compare two prediction methods by waiting to see how accurate they are on unknown future data or, if necessary, use holdout data. This does not carry over to deciding whether LIME or SHAP or some other method has made a better explanation of a past decision. Suppose that we want to understand something like why a given applicant was turned down for a loan. When $f(\cdot)$ is available to us in closed form then there is no doubt at all about whether the loan would have been offered under any assortment of hypothetical feature combinations that we choose. We can compare methods by how they define importance. Choosing among definitions is a different activity, essentially a philosophical one, and we face tradeoffs. Our problem is one of identifying the causes of given effects when we have perfect knowledge of $f(\cdot)$ for all input variable combinations. This is different from the more common learning task of quantifying the effects of given causes. That distinction was made by Holland, (1988) in studying causal inference. It goes back at least to Mill, (1843).

A problem with many, but not all, measures of variable importance is that they are based on changing some feature values from one level to another, while holding other features constant and then looking at the changes to $f(\cdot)$. When the underlying features are highly correlated, then some of these combinations can be quite implausible, casting doubt on any variable importance methods that use them. In extreme cases, the combinations can be physically impossible (e.g., systolic blood pressure below diastolic) or logically impossible (e.g., birth date after graduation date). The use of these combinations has also been criticized by Hooker and Mentch, (2019).

To avoid using impossible values, Cohort Shapley method¹¹1https://github.com/cohortshapley/cohortshapley from Mase et al., (2019) uses only observed data values. For any target subject $t\in\{1,\dots,n\}$ and any feature variable $j=1,\dots,d$ we obtain a Shapley value $\phi_{j}=\phi_{j}(t)$ that measures the impact of the value of feature $j$ on $f(\cdot)$ for subject $t$. As we describe below, those impacts can be positive or negative. Using one of the Shapley axioms we will be able to aggregate from individual subjects to an impact measure for the entire data set. We can also disaggregate from the entire data set to a subset, such as all subjects with the protected level of a protected variable.

In this paper we use the cohort Shapley method from Mase et al., (2019) to measure variable importance. One of the features of cohort Shapley is that it can attribute importance to a variable that is not actually used in $f(\cdot)$. This is controversial and not all authors approve but it is essential in the present context of algorithmic fairness.

Our contribution is to provide a method of quantifying bias at both individual and group levels with axiomatic consistency between the individual and group measures and without requiring any impossible or unobserved combinations of input variables. The approach can even be used when the prediction algorithm is not available as for instance when it is proprietary.

We investigate the COMPAS data (Angwin et al.,, 2016) which include predictions of who is likely to commit a crime. There is great interest in seeing whether the algorithm is unfair to Black subjects. In the given context, the prediction code $f(\cdot)$ is a proprietary algorithm, unavailable to us and so we cannot change any of the values in it. What we have instead are the predictions on a set of subjects. Cohort Shapley can work with the predictions because it does not require any hypothetical feature combinations. Figure 1 shows cohort Shapley impacts for the race of the subjects in the COMPAS data, computed in a way that we describe below. As it turns out the impact of race on whether a subject was predicted to reoffend was always positive for Black subjects and it was always negative for White subjects. For some other measures that we show, the histograms overlap. The average impact for Black subjects was $0.067$ and the average for White suspects was $-0.101$. For context, the response values were $1$ for those predicted to reoffend and $0$ for those predicted not to reoffend.

An outline of this paper is as follows. Section 2 introduces our notation, defines Shapley value, and presents a few of the variable importance measures and fairness definitions from the literature. Section 3 describes the COMPAS recidivism data set. Section 4 has our analysis of that data including a Bayesian bootstrap for uncertainty quantification. Section 5 has our conclusions. An appendix presents some additional COMPAS results like the ones we selected for discussion.

Shapley value (Shapley,, 1953) is used in game theory to define a fair allocation of rewards to a team that has cooperated to produce something of value. Many variable importance problems can be formulated as a team of input variables generating an output value or an output variance explained. We then want to apportion importance or impact to the individual variables.

Suppose that a team of $d$ members produce a value $\mathrm{val}(1{:}d)$, and that we have at our disposal the value $\mathrm{val}(u)$ that would have been produced by the team $u$, for all $2^{d}$ teams $u\subseteq 1{:}d$. Let $\phi_{j}$ be the reward for player $j$. It is convenient to work with incremental values $\mathrm{val}(j\!\mid\!u)=\mathrm{val}(u+j)-\mathrm{val}(u)$ for sets $u$ with $j\not\in u$.

Shapley introduced quite reasonable criteria:

1.  1)

   Efficiency: $\sum_{j=1}^{d}\phi_{j}=\mathrm{val}(1{:}d)$.

2.  2)

   Symmetry: If $\mathrm{val}(i\!\mid\!u)=\mathrm{val}(j\!\mid\!u)$ for all $u\subseteq 1{:}d\setminus\{i,j\}$, then $\phi_{i}=\phi_{j}$.

3.  3)

   Dummy: if $\mathrm{val}(j\!\mid\!u)=0$ for all $u\subseteq 1{:}d\setminus\{j\}$, then $\phi_{j}=0$.

4.  4)

   Additivity: if $\mathrm{val}(u)$ and $\mathrm{val}^{\prime}(u)$ lead to values $\phi_{j}$ and $\phi_{j}^{\prime}$ then the game producing $(\mathrm{val}+\mathrm{val}^{\prime})(u)$ has values $\phi_{j}+\phi^{\prime}_{j}$.

He found that the unique valuation that satisfies all four of these criteria is

Formula (1) is not very intuitive. Another way to explain Shapley value is as follows. We could build a team from ${\varnothing}$ to $1{:}d$ in $d$ steps, adding one member at a time. There are $d!$ different orders in which to add team members. The Shapley value $\phi_{j}$ is the increase in value coming from the addition of member $j$, averaged over all $d!$ different orders. From equation (1) we see that Shapley value does not change if we add or subtract the same quantity from all $\mathrm{val}(u)$. It can be convenient to make $\mathrm{val}({\varnothing})=0$.

We discuss some variable importance measures based on Shapley value below. We use the framework from Sundararajan and Najmi, (2020). They survey many uses of Shapley value in explainable AI.

Most mechanisms for investigating variable importance proceed by changing some, but not all, of the input variables to $f(\cdot)$. For $u\subseteq 1{:}d$ the hybrid point $\boldsymbol{w}=\boldsymbol{x}_{u}{:}\boldsymbol{z}_{-u}$ has

We can investigate changes to $\boldsymbol{x}_{u}$ by examining $f(\boldsymbol{x}_{u}{:}\boldsymbol{z}_{-u})-f(\boldsymbol{x})$ for various points $\boldsymbol{x},\boldsymbol{z}\in\mathcal{X}$.

Global sensitivity analysis (Razavi et al.,, 2021) works with an analysis of variance (ANOVA) defined in terms of $\boldsymbol{x}\in\mathcal{X}$ with independent components for which $\sigma^{2}=\mathrm{var}(f(\boldsymbol{x}))<\infty$. The sets $\mathcal{X}_{j}$ can be discrete or continuous. It is common there to measure the importance of a subset of variables by variance explained. For instance, the lower Sobol’ index for variables $\boldsymbol{x}_{u}$ is $\underline{\tau}^{2}_{u}=\mathrm{var}(\mathbb{E}(f(\boldsymbol{x})\!\mid\!\boldsymbol{x}_{u}))$ which is usually normalized to $\underline{\tau}^{2}_{u}/\sigma^{2}$. The upper Sobol’ index is $\overline{\tau}^{2}_{u}=\sigma^{2}-\underline{\tau}^{2}_{-u}$, that is, everything not explained by $\boldsymbol{x}_{-u}$ is attributed to $\boldsymbol{x}_{u}$. These measures are very natural in settings where the components of $\boldsymbol{x}$ can all vary freely and independently, but such is usually not the case for inputs to a black box machine learning model.

The quantitative influence function (QII) method of Datta et al., (2016) uses a model in which the features are statistically independent from their marginal distributions.

In baseline Shapley (see Sundararajan and Najmi, (2020)), there is a baseline tuple $\boldsymbol{x}_{b}\in\mathcal{X}$ of $\boldsymbol{x}$, such as the sample average $\bar{\boldsymbol{x}}$. Then the value for variable subset $u$ and subject $t$ is $f(\boldsymbol{x}_{t,u}{:}\boldsymbol{x}_{b,-u})$. We get the same Shapley values using $\mathrm{val}(u)=f(\boldsymbol{x}_{t,u}{:}\boldsymbol{x}_{b,-u})-f(\boldsymbol{x}_{b})$. Then the total value to explain for subject $t$ is $f(\boldsymbol{x}_{t})-f(\boldsymbol{x}_{b})$. The counterfactuals are changes in some subset of the values in $\boldsymbol{x}_{t}$. Important variables are those that move the value the most from the baseline $f(\boldsymbol{x}_{b})$ to subject $t$’s value. Shapley’s combination provides a principled weighting of the effect of changing $x_{b,j}$ to $x_{t,j}$ given some subset $u$ of variables that have also been changed.

Conditional expectation Shapley (Sundararajan and Najmi,, 2020) uses a joint distribution $D$ on $\mathcal{X}$ and then for subject $t$ $\mathrm{val}(u)=\mathbb{E}_{D}(f(\boldsymbol{x})\mid\boldsymbol{x}_{u}=\boldsymbol{x}_{t,u})$ under $D$. SHAP (Lundberg and Lee,, 2017) is a conditional expectation Shapley using a distribution $D$ in which the features are independent. Cohort Shapley (Mase et al.,, 2019) that we describe next is very nearly conditional expectation Shapley with $D$ equal to the empirical distribution.

In cohort Shapley the counterfactual does not involve replacing $\boldsymbol{x}_{tu}$ by $\boldsymbol{x}_{bu}$. It is instead about concealing the values of $\boldsymbol{x}_{tu}$. It is what Kumar et al., (2020) call a conditional method because it requires specification of a conditional distribution on the features. The version we present here is a form of conditional expectation Shapley using the empirical distribution of the data.

For every pair of values $x_{tj},x_{ij}\in\mathcal{X}_{j}$ we can declare them to be similar or not. In the present context we take similarity to just be $x_{tj}=x_{ij}$. For a target subject $t\in 1{:}n$ and set $u\subseteq 1{:}d$ we define the cohort $C_{u}=C_{tu}=\{i\in 1{:}n\mid\boldsymbol{x}_{iu}=\boldsymbol{x}_{tu}\}$. These are the subjects who match subject $t$ on all of the variables $j\in u$. They may or may not match the target on $j\not\in u$. None of the cohorts is empty because they all contain $t$. The value function in cohort Shapley is the cohort mean

Here $\hat{y}_{i}=f(\boldsymbol{x}_{i})$ but we write it this way because in practice we might not have $f(\cdot)$ at our disposal, just the predictions $\hat{y}_{i}$.

The incremental value $\mathrm{val}(j\!\mid\!u)$ is then how much the cohort mean moves when we reveal $x_{tj}$ in addition to previously revealed variables $\boldsymbol{x}_{tu}$. Having specified the values, the Shapley formula provides attributions. Note that $\mathrm{val}({\varnothing})$ is the plain average of all $\hat{y}_{i}$ and Shapley value is unchanged by subtracting $\mathrm{val}({\varnothing})$ from all of the $\mathrm{val}(u)$. Furthermore, when there are many variables, then very commonly $C_{t,1{:}d}=\{t\}$ and then the total value to be explained, $\mathrm{val}(1{:}d)-\mathrm{val}({\varnothing})$ is simply $\hat{y}_{t}-(1/n)\sum_{i=1}^{n}\hat{y}_{i}$.

Just as there are many ways to define variable importance, there are multiple ways to define what fairness means. Some of those definitions are mutually incompatible and some of them differ from legal definitions. Here we present a few of the issues. See Corbett-Davies and Goel, (2018), Chouldechova and Roth, (2018), Berk et al., (2018), and Friedler et al., (2019) for surveys. We do not make assertions about which definitions are preferable.

For $y,\hat{y}\in\{0,1\}$, let $n_{y\hat{y}}$ be the number of subjects with $y_{i}=y$ and $\hat{y}_{i}=\hat{y}$. These four counts and their derived properties can be computed for any subset of the subjects. The false positive rate (FPR) is $n_{01}/n_{0\text{\tiny$\bullet$}}$, where a bullet indicates that we are summing over the levels of that index. We ignore uninteresting corner cases such as $n_{0\text{\tiny$\bullet$}}=0$; when there are no subjects with $y=0$ then we have no interest in the proportion of them with $\hat{y}=1$. The false negative rate (FNR) is $n_{10}/n_{1\text{\tiny$\bullet$}}$. The prevalence of the trait under study is $p=n_{1\text{\tiny$\bullet$}}/n_{\text{\tiny$\bullet$}\text{\tiny$\bullet$}}$. The positive predictive value (PPV) is $n_{11}/n_{\text{\tiny$\bullet$}1}$. As Chouldechova, (2017, equation (2.6)) notes, these values satisfy

See also Kleinberg et al., (2016).

Equation (2) shows how some natural definitions of fairness conflict. FPR and FNR describe $\hat{y}\!\mid\!y$, while PPV describes $y\!\mid\!\hat{y}$. If two subsets of subjects have the same PPV but different prevalences $p$, then they cannot also match up on FPR and FNR. Fairness in $y\!\mid\!\hat{y}$ terms and fairness in $\hat{y}\!\mid\!y$ terms can only coincide in trivial settings such as when $\hat{y}=y$ always or empirically unusual settings with equal prevalence between subjects having different values of a protected attribute.

Hardt et al., (2016) writes about measures of demographic parity, equalized odds and equal opportunity. Demographic parity, requires $\Pr(\hat{y}=1\!\mid\!\boldsymbol{x}_{p})=\Pr(\hat{y}=1)$ where $\boldsymbol{x}_{p}$ specifies the levels of one (or more) protected variables. Equalized odds requires $\Pr(\hat{y}=1\!\mid\!y=y^{\prime},\boldsymbol{x}_{p})=\Pr(\hat{y}=1\!\mid\!y=y^{\prime}),y^{\prime}\in{0,1}$, so that false positive rates and true positive rates are both equal across groups. Because $\mathrm{FNR}=1-\mathrm{TPR}$ the false negative rates are also equal. Equal opportunity is defined in terms of a preferred outcome. When $y=0$ is preferred, it requires that $\mathrm{Pr}(\hat{y}=1\!\mid\!y=0,\boldsymbol{x}_{p})=\mathrm{Pr}(\hat{y}=1\!\mid\!y=0)$ That is, the false positive rate is unaffected by the protected variables.

Chouldechova, (2017) considers a score $s$ (such as $\hat{y}$) to be well calibrated if $\mathrm{Pr}(y=1\!\mid\!s,\boldsymbol{x}_{p})=\mathrm{Pr}(y=1\!\mid\!s)$ for all levels of $s$. A score attains predictive parity if $\mathrm{Pr}(y=1\!\mid\!s>s_{*},\boldsymbol{x}_{p})=\mathrm{Pr}(y=1\!\mid\!s>s_{*})$ for all thresholds $s_{*}$. The distinction between well calibratedness and predictive parity is relevant when there are more than two levels for the score.

There is some debate about when or whether using protected variables can lead to improved fairness. See Xiang, (2020) who gives a summary of legal issues surrounding fairness and Corbett-Davies et al., (2017) who study whether imposing calibration or other criteria might adversely affect the groups they are meant to help.

The additivity axiom of Shapley value is convenient for us. It means that importances for the residual $y_{i}-\hat{y}_{i}$ is simply the difference of importances for $y_{i}$ and $\hat{y}_{i}$. We can aggregate importances from subjects to the whole data set by summing, or more interpretably averaging over $t=1,\dots,n$. We can also disaggregate from the whole data set to subsets of special interest by averaging cohort Shapley values over target subjects $t\in v\subset 1{:}n$.

Figure 2 shows histograms of Shapley impacts of race for the subjects in the COMPAS data. The first panel there reproduces the data from Figure 1 showing a positive impact for every Black subject and a negative one for every White subject for the prediction $\hat{y}$. For the actual response $y$, the histograms overlap slightly. By additivity of Shapley value the impacts for $y-\hat{y}$ can be found by subtracting the impact for $\hat{y}$ from that for $y$ for each subject $i=1,\dots,n$. The histograms of $y_{i}-\hat{y}_{i}$ show that the impact of race on the residual is typically positive for White subjects and negative for Black subjects.

Overlap of distributions is seen in equal opportunity (false positive rate: FPR) and false negative rate (FNR). In there, small number of adversely affected White and beneficially affected Black are observed. We can inspect further on these overlapped subjects to understand which conditions are exceptional cases. Also we can inspect on tail of the distribution to understand the extreme cases where bias is very likely observed.

Figure 3 shows histograms of Shapley impacts for race but now they are color coded by the subjects’ gender. We see that the impact on $\hat{y}$ is bimodal by race for both male and female subjects, but the effect is larger in absolute value for male subjects. The impacts for the response, the residual and false negative and positive values do not appear to be bimodal by race for female subjects, but they do for male subjects. The case of FN is perhaps different. The modes in Figure 2 are close together and not so apparent in Figure 3 which has slightly different bin boundaries. It is clear from these figures that the race differences we see are much stronger among male subjects.

The appendix includes some figures that each include 25 histograms. They are Shapley impact histograms for all five features color coded by each of the five features. There is one such figure for each of $y$, $\hat{y}$, $y-\hat{y}$, $\mathrm{FP}$ and $\mathrm{FN}$.

Tables 2 through 6 in the appendix record mean Shapley impacts for the five predictors and our responses measures, disaggregated by race and gender.

We take a particular interest in the residual $y_{t}-\hat{y}_{t}$. It equals $1$ for false negatives and $-1$ for false positives and $0$ when the prediction was correct. Table 1 shows a subset of the largest values for the residual $y_{i}-\hat{y}_{i}$.

What we see there is that revealing that a subject is Black tells us that, on average, that subject’s residual $y_{t}-\hat{y}_{t}$ is decreased by $3.6$%. Revealing that the subject is White increases the residual by $5.4$%. Revealing race makes very little difference to the residual averaged over male or over female subjects. Revealing gender makes quite a large difference of $-8.3$% for female subjects and $+2.0\%$ for male subjects.

To judge the uncertainty in the values in Table 1 we applied the Bayesian bootstrap of Rubin, (1981). That algorithm randomly reweights each data point by a unit mean exponential random variable. By never fully deleting any observation it allows one to also bootstrap individual subjects’ Shapley values though there is not space to do so in this article. Figure 4 shows violin plots of 1000 bootstrapped cohort Shapley values.

The risk of being falsely predicted to reoffend involves two factors: having $y_{i}=0$ and having $\hat{y}_{i}=1$ given that $y_{i}=0$. FPR is commonly computed only over subjects with $y_{i}=0$. Accordingly, in this section we study it by subsetting the subjects to $\{i\mid y_{i}=0\}$ and finding cohort Shapley value of $\hat{y}_{i}=1$ for the features.

Figure 5 shows cohort Shapley impact of race factor conditioned on race factor for FPR and FNR. The distribution of impacts conditioned on race are separated in the figure. This conditional analysis shows a stronger disadvantage for Black subjects.