Shapley Values: From Game Theory to Model Interpretation

In today’s world of machine learning, model interpretability is becoming increasingly important. One particularly elegant tool for this is Shapley Values - a concept that originated in game theory and is now revolutionizing how we understand machine learning models.

The Game Theory Roots

Imagine a group of students working on a term paper:

  • Jens gathers research data and literature
  • Karo performs data analysis and creates charts
  • Thilo writes and edits the paper

The paper’s success depends on everyone: Jens’ research lays the foundation, Karo’s analysis adds depth, and Thilo’s writing ties it all together. But how do you fairly divide credit for the final grade? Each student’s contribution is relevant, but their impact depends on the collaboration.

Lloyd Shapley’s Shapley Values provide a fair method to allocate credit, considering each person’s unique contribution to the group’s success. Developed in 1951, this framework ensures every role is recognized based on its impact.

The Basic Idea of Shapley Values

The Shapley Value of a “player” represents their average marginal contribution to the outcome across all possible combinations of players. While quantifying individual contributions in a collaborative project like a term paper (the outcome) can be challenging, statistical models offer principled methods for this kind of computation. This is why the concept of Shapley Values translates so well to machine learning. Here, instead of students, we have features, and instead of a final grade, we have model predictions.

For a feature $i$, the Shapley Value $\phi_i$ is defined as:

$$ \phi_i = \sum_{S \subseteq N \setminus {i}} \frac{|S|!\,(n-|S|-1)!}{n!} \Big[\widehat{f}_x(S \cup {i}) - \widehat{f}_x(S)\Big] $$

Where:

  • $N$ is the set of all features
  • $S$ is a subset of features not containing $i$
  • $n = |N|$ is the total number of features
  • $\widehat{f}_x(S)$ is the model prediction using only features in subset $S$
  • $|S|$ denotes the number of features in subset $S$

The term $|S|!(n-|S|-1)!/n!$ represents the weight of the marginal contribution of the set $S$. How are these weights computed? Well, occurence of the factorial operator “$!$” hints that they follow from a combinatorial consideration. Here it is:

The weights are derived from permutations of $n$ features, of which there are $n!$ total. For a subset $S$ excluding feature $i$, the goal is to determine how many permutations place $S$ before $i$. The features in $S$ can be arranged in $|S|!$ ways, and the remaining features excluding $S$ and $i$ can be arranged in $(n - |S| - 1)!$ ways. Multiplying these gives the number of permutations where $S$ precedes $i$. Normalizing by $n!$ gives $|S|!(n - |S| - 1)!/n!$, the proportion of such permutations, ensuring fair contribution weights for each subset. We have

$$ \sum_{S \subseteq N \setminus {i}} \frac{|S|!(n-|S|-1)!}{n!} = 1. $$

Further properties are:

  1. Efficiency: The sum of Shapley Values equals the difference from the base prediction $$\sum_{i=1}^n \phi_i = \widehat{f}_x(N) - E[\widehat{f}_x(\emptyset)]$$

  2. Symmetry: If two features $i$ and $j$ contribute equally to all subsets, then: $$\phi_i = \phi_j$$

  3. Dummy: If a feature $i$ adds no marginal value, then: $$\phi_i = 0$$

  4. Linearity: For two models $f$ and $g$: $$\phi_i(f + g) = \phi_i(f) + \phi_i(g)$$

Some Technical Considerations

The primary challenge in computing Shapley Values lies in their combinatorial nature: evaluating all possible subsets of features to determine marginal contributions has a computational complexity of $\mathcal O(2^n)$, and so exact computation becomes infeasible for models with large $n$.

Tree models, however, are a special case where exact Shapley Values can be computed efficiently. Their hierarchical structure allows contributions to be derived directly from decision paths without evaluating every subset. By leveraging this structure, implementations like .TreeExplainer() in the Python library SHAP achieve polynomial complexity $\mathcal O(TL)$, where $T$ is the number of trees and $L$ is the maximum depth, making it computationally efficient. Other models require sampling or approximation techniques when the feature space is large.

In this follow-up post, I demonstrate how to use Shapley Values with a random forest trained in Python to explain the contributions of individual features to its predictions.

That’s it for now 😊.