Shapley Value

Shapley Value

Note: If you think I should correct something, let me know 😊.

This blog includes:

1. What is Shapley Value
2. Why do we use Shapley Value
3. Shapley Value by Hand
4. Shapley Value by Code

What is Shapley Value

Shapley value is a solution concept in game theory that measures the contribution of each team player (or feature) in a game (or model prediction).

Where/Why Do We Use Shapley Value

Shapley value is used in XAI (Explainable AI) to quantify the contribution of each feature to the outcome. Imagine a game played by 3 teams (A, B, and C) where team B wins. To fairly divide the prize money among players, the Shapley value helps determine each player's contribution. In machine learning, features are like players, and the prediction is the game outcome.

Shapley Value by Hand

Consider the formula:

\[ \phi_i = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (|N| - |S| - 1)!}{|N|!} \left[ v(S \cup \{i\}) - v(S) \right] \]

Here, N is the total number of features; S is a subset of features; v is a function (or model); and i is one feature. For example, assume v(S) has the following values:

To compute the Shapley value for feature A, for instance, you would substitute the values into the formula, sum the contributions, and divide by the number of permutations (3! = 6) to get \(\phi_A = 11\). Similarly, you would get 13 for B and 6 for C.

Shapley Value by Code

Below is an example of how to compute Shapley values in Python:

import matplotlib.pyplot as plt
import cv2
import numpy as np
import itertools
from tqdm import tqdm
import torch
import torchvision.transforms as transforms
from torchvision.models import resnet18
from PIL import Image

def preprocess_image(image, size=(224, 224)):
    transform = transforms.Compose([
        transforms.Resize(size),
        transforms.ToTensor(),
        transforms.Normalize(mean=[0.485, 0.456, 0.406],
                             std=[0.229, 0.224, 0.225])
    ])
    return transform(image).unsqueeze(0)
    
def mask_image(image, mask, fill_value=0):
    masked_image = image.clone()
    for i in range(3):
        masked_image[0, i][mask == 0] = fill_value
    return masked_image
    

The code below shows how to compute the Shapley values given 4 image regions:

def shapley_values(image, model, feature_parts):
    n = len(feature_parts)
    shap_values = np.zeros(n)
    S = list(itertools.chain.from_iterable(
        itertools.combinations(range(n), r) for r in range(n + 1)
    ))
    with torch.no_grad():
        for subset in tqdm(S, desc="Calculating Shapley values"):
            subset_mask = sum(feature_parts[i] for i in subset) > 0
            masked_image = mask_image(image, subset_mask)
            output = model(masked_image).squeeze()
            predicted_value = output.max().item()
            for i in range(n):
                if i not in subset:
                    subset_with_i_mask = sum(feature_parts[j] for j in subset + (i,)) > 0
                    masked_image_with_i = mask_image(image, subset_with_i_mask)
                    output_with_i = model(masked_image_with_i).squeeze()
                    predicted_value_with_i = output_with_i.max().item()
                    marginal_contribution = predicted_value_with_i - predicted_value
                    shap_values[i] += marginal_contribution / len(S)
    return shap_values

# Example usage:
image_path = "African_Bush_Elephant.jpg"
image = Image.open(image_path).convert("RGB")
image_tensor = preprocess_image(image)
# Create four regions:
height, width = image_tensor.shape[2:]
region_masks = [
    (np.zeros((height, width)), (0, height // 2, 0, width // 2)),
    (np.zeros((height, width)), (0, height // 2, width // 2, width)),
    (np.zeros((height, width)), (height // 2, height, 0, width // 2)),
    (np.zeros((height, width)), (height // 2, height, width // 2, width))
]
feature_regions = []
for mask, (x1, x2, y1, y2) in region_masks:
    mask[x1:x2, y1:y2] = 1
    feature_regions.append(torch.tensor(mask, dtype=torch.bool))
shap_values = shapley_values(image_tensor, model, feature_regions)
print("Shapley Values for each region:", shap_values)
    

Try loading your favorite model and play with the region size!