SHAP

SHapely Additive exPlanations

SHapley Additive exPlanations (SHAP) is a popular explainability algorithm that connects game theory with local explanations. SHAP aims to explain the prediction for any input (e.g., an image) as a sum of contributions from its feature values (e.g., image pixels).

SHAP assumes that the individual features (e.g., image pixels) in the input (e.g., an image) participate in a cooperative game whose payout is the model prediction. The algorithm uses game theory to distribute the payout among these features fairly. The payout is known as the Shapely value of a feature.

What are Shapely values?

Let’s assume that an image $X$ can be represented as a set of pixels $X = \{X_{ij}: 0 \leq i < H, 0 \leq j < W \}$, where $H$ and $W$ are the height and width of the image. Now, given a neural network $f(.)$, let $f_S(X)$ represent the prediction on the image $X$ when only pixels in the set $S$ are considered while making the prediction (in other words, pixels not present in set $S$ are set to zero).

Now, let $P_{ij} = \{ S: S \subset X \text{ AND } X_{ij} \in S \}$ denote all such subsets of $X$ that contain pixel $X_{ij}$.

Let’s consider one such subset $S$. We define $\text{MC}_S(i,j)$, the “Marginal contribution” of $(i,j)^{th}$ pixel corresponding to set $S \in P_{ij}$ as the change in prediction score when the pixel $X_{ij}$ is removed from set $S \in P_{ij}$. In other words,