3. How does SHAP Work and can be Applied?

SHAP uses classic Shapley values from a branch of mathematics called game theory and their related extensions.

3.1 Cooperative game

Imagine a scenario where a group of players collaborates to achieve a certain outcome, and the value of that outcome is generated by the entire group. In the context of a machine learning model, a prediction would be the value and the features would be the players.

3.2 Marginal contribution

The marginal contribution of a feature is the change it makes to a prediction when introducing it to the group. However, there is an issue because the order in which a feature is introduced will influence its marginal contribution.

For example, consider a simple scenario where we have three players A, B and C. If we want to work out the marginal contribution of each player to the group, it may differ based on the order that each player is introduced to the group. Imagine if players A and B had overlapping skillsets. Then, whichever player A or B was introduced first would provide a larger marginal contribution because part of the second player's contribution would already be included by the first. In other words we need to consider the sequences: ABC, ACB, BAC, BCA, CAB, CBA.

This is where we introduce Shapley values.

3.3 Shapley values

Shapley values are computed from averaging the marginal contributions of each feature across all possible permutations of features in the group. In other words, the marginal contribution of each feature is calculated for every possible order that each feature can be introduced to the group and the Shapley value is defined as the average of those marginal contributions for each feature.

The sum of the Shapley values for an outcome is equal to the difference between the prediction and some baseline prediction.

3.4 Computation

Notice that in the sequence above, if we were to compute the marginal contribution for player A being introduced in position 0 then we would only need to calculate one of ABC or ACB. This is because of the additive property of Shapley values. The outcome of all the possible sequences should be the same so it doesn't matter what order the rest of the players are introduced after (and before) the player of interest. This simplifies the computation as we can now consider the subsets of sequences in which each player is introduced at a certain position, weight them accordingly and take the average for the Shapley value.

With this intuition, the full mathematical expression can be understood and is described in the original paper linked above.

3.5 SHAP values

A problem becomes evident when more features are added to a model. The Shapley values become exponentially more expensive to compute and becomes unfeasible very quickly. SHAP proposes using other additive feature attribution methods to approximate calculations such as Local Interpretable Model-agnostic Explanations (LIME) and Deep Learning Important FeaTures (DeepLIFT). For full details of these implementations, refer to the original paper linked above.