In this article , we will talk about SHAP in detail. We will discuss What are Shapley Values ? , Mathematical foundation behind the Shapley Values and How does SHAP (Shapley Additive Explanations) reframes the Shapey Value problem in detail. Also we will discuss What is Local Accuracy, Missingness, and Consistency in the context of explainable models , What is the Shapley Kernel etc.
What is Shapley Values ?
SHAP values were introduced by Lundberg and Lee (2016) as a way to provide local explanations for machine learning models. They built upon Shapley's work in cooperative game theory, using the Shapley value to explain how each feature in a model contributes to the prediction for a particular instance.
Shapley values were invented by Lloyd Shapley as a way of providing a fair solution to the following question: if we have a coalition C that collaborates to produce a value V, how much did each individual member contribute to that final value ?
So what does this mean ? We have a coalition C, a group of cooperating members that work together to produce some value V, called the coalition value. This could be something like, a corporation of employees that together generate a certain profit, or a dinner group running up a restaurant bill. We want to know exactly how much each member contributed to that final coalition value; what share of the profit does each employee deserve, how much each person in the dinner party owes to settle the bill.
However, answering this gets tricky when there are interacting effects between members, when certain permutations cause members to contribute more than the sum of their parts. To find a fair answer to this question that takes into account these interaction effects, we can compute the Shapley value for each member of the coalition.
So let’s how we can compute the Shapley value for member 1 of our example coalition. The way this is done is by sampling a coalition that contains member 1, and then looking at the coalition formed by removing that member.
We then look at the respective values of these two coalitions, and compare the difference between the two.
This difference is the marginal contribution of member 1 to the coalition consisting of members 2, 3, and 4; how much member 1 contributed to that specific group.
So we then enumerate all such pairs of coalitions, that is, all pairs of coalitions that only differ based on whether or not member 1 is included, and then look at all the marginal contributions for each.
The mean marginal contribution is the Shapley value of that member.
We can do this same process for each member of the coalition, and we’ve found a fair solution to our original question.!
Mathematically, the whole process looks like this, but all we need is to know that the Shapley value is the average amount of contribution that a particular member makes to the coalition value.
Shapley Values To SHAP
Now, translating this concept to model explainability is relatively straightforward, and that’s exactly what Scott Lundberg and Su-In Lee did in 2017 with their paper “A Unified Approach to Interpreting Model Predictions,” where they introduced SHAP.
SHAP reframes the Shapley value problem from one where we look at how members of a coalition contribute to a coalition value to one where we look at how individual features contribute to a model’s outputs.
They do this in a very specific way, one that we can get a clue to by looking at the name of their algorithm; Shapley Additive Explanations. We know what Shapley values are, we know what Explanations are, but what do they mean by Additive?
Lundberg and Lee define an additive feature attribution as follows: if we have a set a of inputs x, and a model f(x), we can define a set of simplified local inputs x’ (which usually means that we turn a feature vector into a discrete binary vector, where features are either included or excluded) and we can also define an explanatory model g.
What we need to ensure is that One: if x’ is roughly equal to x then g(x’) should be roughly equal to f(x)
two: g must take below form, where phi_0 is the null output of the model, that is, the average output of the model, and phi_i is the explained effect of feature_i; how much that feature changes the output of the model. This is called it’s attribution.
If we have these two, we have an explanatory model that has additive feature attribution. The advantage of this form of explanation is really easy to interpret; we can see the exact contribution and importance of each feature just by looking at the phi values.
Local Accuracy, Missingness and Consistency
Now Lundberg and Lee go on to describe a set of three desirable properties of such an additive feature method; local accuracy, missingness, and consistency.
Local Accuracy
Local accuracy : it simply says if the input and the simplified input are roughly the same, then the actual model and the explanatory model should produce roughly the same output.
Missingness
Missingness states that if a feature is excluded from the model, it’s attribution must be zero; that is, the only thing that can affect the output of the explanation model is the inclusion of features, not the exclusion.
Consistency
Finally, we have consistency (and this one’s a little hard to represent mathematically), but it states that if the original model changes so that the a particular feature’s contribution changes, the attribution in the explanatory model cannot change in the opposite direction;
So for example, if we have a new model where a specific feature has a more positive contribution than in the original; the attribution in our new explanatory model cannot decrease.
Now while a bunch of different explanation methods satisfy some of these properties, Lundberg and Lee argue that only SHAP satisfies all three; if the feature attributions in our additive explanatory model are specifically chosen to be the shapley values of those features, then all three properties are upheld.
Shapley Kernel
The problem with SHAP, however, is that computing Shapley values means you have to sample the coalition values for each possible feature permutation, which in a model explainability setting means we have to evaluate our model that number of times.
For a model that operates over 4 features, it’s easy enough, it’s just 16 coalitions to sample to get all the Shapley values. For 32 features, that’s over 17 billion samples, which is entirely untenable. To get around this, Lundberg and Lee devise the Shapley Kernel, a means of approximating shapley values through much fewer samples.
So what we do is we pass samples through the model, of various feature permutations of the particular datapoint that we’re trying to explain.
Of course, most ML models won’t just let you omit a feature !
So what we do is define a background dataset B, one that contains a set of representative datapoints that the model was trained over.
We then fill in our omitted feature or features with values from the background dataset, while holding the features that are included in the permutation fixed to their original values.
We then take the average of the model output over all of these new synthetic datapoints as our model output for that feature permutation, which we’ll call that y bar.
So once we have a number of samples computed in this way,
We can formulate this as a weighted linear regression, with each feature assigned a coefficient.
With a very specific choice of weighting for each sample, based on a combination of the total number of features in the model, the number of coalitions with the same number of features as this particular sample, and the number of features included and excluded in this permutation, we ensure that the solution to this weighted linear regression is such that the returned coefficients are equivalent to the Shapley values.
This weighting scheme is the basis of the Shapley Kernel, and the weighted linear regression process as a whole is Kernel SHAP.
Now, there are a lot of other forms of SHAP that are presented in the paper (Deep SHAP, Low Order SHAP , Max SHAP , Linear SHAP , Tree SHAP etc) , ones that make use of model-specific assumptions and optimizations to speed up the algorithm and the sampling process, but Kernel SHAP is the one among them that is universal and can be applied to any type of machine learning model. This general applicability is why we chose Kernel SHAP as the first form of SHAP to implement for TrustyAI.
Kernel SHAP Example
I’ll run through an example of the Python SHAP implementation provided by Lundberg and Lee. So first I’ll grab a dataset to run our example over, and I’ve picked the Boston housing price dataset, which is a dataset consisting of various attributes about Boston neighborhoods and the corresponding house prices within that neighborhood.
Incomplete. Coming soon