SHAP Theoretical Foundation

SHAP Theoretical Foundation

This document explains the theoretical foundations of SHAP (SHapley Additive exPlanations), including Shapley values from game theory, the principles that make SHAP unique, and connections to other explanation methods.

Game Theory Origins

Shapley Values

SHAP is grounded in Shapley values, a solution concept from cooperative game theory developed by Lloyd Shapley in 1951.

Core Concept: In cooperative game theory, players collaborate to achieve a total payoff, and the question is: how should this payoff be fairly distributed among players?

Mapping to Machine Learning:

• Players → Input features
• Game → Model prediction task
• Payoff → Model output (prediction value)
• Coalition → Subset of features with known values
• Fair Distribution → Attributing prediction to features

The Shapley Value Formula

For a feature $i$, its Shapley value $\phi_i$ is:

$$\phi_i = \sum_{S \subseteq F \setminus {i}} \frac{|S|!(|F|-|S|-1)!}{|F|!} [f(S \cup {i}) - f(S)]$$

Where:

• $F$ is the set of all features
• $S$ is a subset of features not including $i$
• $f(S)$ is the model's expected output given only features in $S$
• $|S|$ is the size of subset $S$

Interpretation: The Shapley value averages the marginal contribution of feature $i$ across all possible feature coalitions (subsets). The contribution is weighted by how likely each coalition is to occur.

Key Properties of Shapley Values

1. Efficiency (Additivity): $$\sum_{i=1}^{n} \phi_i = f(x) - f(\emptyset)$$

The sum of all SHAP values equals the difference between the model's prediction for the instance and the expected value (baseline).

This is why SHAP waterfall plots always sum to the total prediction change.

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

Features with identical effects receive identical attribution.

3. Dummy: If a feature $i$ doesn't change the model output for any coalition, then $\phi_i = 0$.

Irrelevant features receive zero attribution.

4. Monotonicity: If a feature's marginal contribution increases across coalitions, its Shapley value increases.

From Game Theory to Machine Learning

The Challenge

Computing exact Shapley values requires evaluating the model on all possible feature coalitions:

• For $n$ features, there are $2^n$ possible coalitions
• For 50 features, this is over 1 quadrillion evaluations

This exponential complexity makes exact computation intractable for most real-world models.

SHAP's Solution: Additive Feature Attribution

SHAP connects Shapley values to additive feature attribution methods, enabling efficient computation.

Additive Feature Attribution Model: $$g(z') = \phi_0 + \sum_{i=1}^{M} \phi_i z'_i$$

Where:

• $g$ is the explanation model
• $z' \in {0,1}^M$ indicates feature presence/absence
• $\phi_i$ is the attribution to feature $i$
• $\phi_0$ is the baseline (expected value)

SHAP proves that Shapley values are the only attribution values satisfying three desirable properties: local accuracy, missingness, and consistency.

SHAP Properties and Guarantees

Local Accuracy

Property: The explanation matches the model's output: $$f(x) = g(x') = \phi_0 + \sum_{i=1}^{M} \phi_i x'_i$$

Interpretation: SHAP values exactly account for the model's prediction. This enables waterfall plots to precisely decompose predictions.

Missingness

Property: If a feature is missing (not observed), its attribution is zero: $$x'_i = 0 \Rightarrow \phi_i = 0$$

Interpretation: Only features that are present contribute to explanations.

Consistency

Property: If a model changes so a feature's marginal contribution increases (or stays the same) for all inputs, that feature's attribution should not decrease.

Interpretation: If a feature becomes more important to the model, its SHAP value reflects this. This enables meaningful model comparisons.

SHAP as a Unified Framework

SHAP unifies several existing explanation methods by showing they're special cases of Shapley values under specific assumptions.

LIME (Local Interpretable Model-agnostic Explanations)

LIME's Approach: Fit a local linear model around a prediction using perturbed samples.

Connection to SHAP: LIME approximates Shapley values but with suboptimal sample weighting. SHAP uses theoretically optimal weights derived from Shapley value formula.

Key Difference: LIME's loss function and sampling don't guarantee consistency or exact additivity; SHAP does.

DeepLIFT

DeepLIFT's Approach: Backpropagate contributions through neural networks by comparing to reference activations.

Connection to SHAP: DeepExplainer uses DeepLIFT but averages over multiple reference samples to approximate conditional expectations, yielding Shapley values.

Layer-Wise Relevance Propagation (LRP)

LRP's Approach: Decompose neural network predictions by propagating relevance scores backward through layers.

Connection to SHAP: LRP is a special case of SHAP with specific propagation rules. SHAP generalizes these rules with Shapley value theory.

Integrated Gradients

Integrated Gradients' Approach: Integrate gradients along path from baseline to input.

Connection to SHAP: When using a single reference point, Integrated Gradients approximates SHAP values for smooth models.

SHAP Computation Methods

Different SHAP explainers use specialized algorithms to compute Shapley values efficiently for specific model types.

Tree SHAP (TreeExplainer)

Innovation: Exploits tree structure to compute exact Shapley values in polynomial time instead of exponential.

Algorithm:

• Traverses each tree path from root to leaf
• Computes feature contributions using tree splits and weights
• Aggregates across all trees in ensemble

Complexity: $O(TLD^2)$ where $T$ = number of trees, $L$ = max leaves, $D$ = max depth

Key Advantage: Exact Shapley values computed efficiently for tree-based models (XGBoost, LightGBM, Random Forest, etc.)

Kernel SHAP (KernelExplainer)

Innovation: Uses weighted linear regression to estimate Shapley values for any model.

Algorithm:

• Samples coalitions (feature subsets) according to Shapley kernel weights
• Evaluates model on each coalition (missing features replaced by background values)
• Fits weighted linear model to estimate feature attributions

Complexity: $O(n \cdot 2^M)$ but approximates with fewer samples

Key Advantage: Model-agnostic; works with any prediction function

Trade-off: Slower than specialized explainers; approximate rather than exact

Deep SHAP (DeepExplainer)

Innovation: Combines DeepLIFT with Shapley value sampling.

Algorithm:

• Computes DeepLIFT attributions for each reference sample
• Averages attributions across multiple reference samples
• Approximates conditional expectations: $E[f(x) | x_S]$

Complexity: $O(n \cdot m)$ where $m$ = number of reference samples

Key Advantage: Efficiently approximates Shapley values for deep neural networks

Linear SHAP (LinearExplainer)

Innovation: Closed-form Shapley values for linear models.

Algorithm:

• For independent features: $\phi_i = w_i \cdot (x_i - E[x_i])$
• For correlated features: Adjusts for feature covariance

Complexity: $O(n)$ - nearly instantaneous

Key Advantage: Exact Shapley values with minimal computation

Understanding Conditional Expectations

The Core Challenge

Computing $f(S)$ (model output given only features in $S$) requires handling missing features.

Question: How should we represent "missing" features when the model requires all features as input?

Two Approaches

1. Interventional (Marginal) Approach:

• Replace missing features with values from background dataset
• Estimates: $E[f(x) | x_S]$ by marginalizing over $x_{\bar{S}}$
• Interpretation: "What would the model predict if we didn't know features $\bar{S}$?"

2. Observational (Conditional) Approach:

• Use conditional distribution: $E[f(x) | x_S = x_S^*]$
• Accounts for feature dependencies
• Interpretation: "What would the model predict for similar instances with features $S = x_S^*$?"

Trade-offs:

• Interventional: Simpler, assumes feature independence, matches causal interpretation
• Observational: More accurate for correlated features, requires conditional distribution estimation

TreeExplainer supports both via feature_perturbation parameter.

Baseline (Expected Value) Selection

The baseline $\phi_0 = E[f(x)]$ represents the model's average prediction.

Computing the Baseline

For TreeExplainer:

• With background data: Average prediction on background dataset
• With tree_path_dependent: Weighted average using tree leaf distributions

For DeepExplainer / KernelExplainer:

• Average prediction on background samples

Importance of Baseline

• SHAP values measure deviation from baseline
• Different baselines → different SHAP values (but still sum correctly)
• Choose baseline representative of "typical" or "neutral" input
• Common choices: Training set mean, median, or mode

Interpreting SHAP Values

Units and Scale

SHAP values have the same units as the model output:

• Regression: Same units as target variable (dollars, temperature, etc.)
• Classification (log-odds): Log-odds units
• Classification (probability): Probability units (if model output transformed)

Magnitude: Higher absolute SHAP value = stronger feature impact

Sign:

• Positive SHAP value = Feature pushes prediction higher
• Negative SHAP value = Feature pushes prediction lower

Additive Decomposition

For a prediction $f(x)$: $$f(x) = E[f(X)] + \sum_{i=1}^{n} \phi_i(x)$$

Example:

• Expected value (baseline): 0.3
• SHAP values: {Age: +0.15, Income: +0.10, Education: -0.05}
• Prediction: $0.3 + 0.15 + 0.10 - 0.05 = 0.50$

Global vs. Local Importance

Local (Instance-level):

• SHAP values for single prediction: $\phi_i(x)$
• Explains: "Why did the model predict $f(x)$ for this instance?"
• Visualization: Waterfall, force plots

Global (Dataset-level):

• Average absolute SHAP values: $E[|\phi_i(x)|]$
• Explains: "Which features are most important overall?"
• Visualization: Beeswarm, bar plots

Key Insight: Global importance is the aggregation of local importances, maintaining consistency between instance and dataset explanations.

SHAP vs. Other Feature Importance Methods

Comparison with Permutation Importance

Permutation Importance:

• Shuffles a feature and measures accuracy drop
• Global metric only (no instance-level explanations)
• Can be misleading with correlated features

SHAP:

• Provides both local and global importance
• Handles feature correlations through coalitional averaging
• Consistent: Additive property guarantees sum to prediction

Comparison with Feature Coefficients (Linear Models)

Feature Coefficients ($w_i$):

• Measure impact per unit change in feature
• Don't account for feature scale or distribution

SHAP for Linear Models:

• $\phi_i = w_i \cdot (x_i - E[x_i])$
• Accounts for feature value relative to average
• More interpretable for comparing features with different units/scales

Comparison with Tree Feature Importance (Gini/Split-based)

Gini/Split Importance:

• Based on training process (purity gain or frequency of splits)
• Biased toward high-cardinality features
• No instance-level explanations
• Can be misleading (importance ≠ predictive power)

SHAP (Tree SHAP):

• Based on model output (prediction behavior)
• Fair attribution through Shapley values
• Provides instance-level explanations
• Consistent and theoretically grounded

Interactions and Higher-Order Effects

SHAP Interaction Values

Standard SHAP captures main effects. SHAP interaction values capture pairwise interactions.

Formula for Interaction: $$\phi_{i,j} = \sum_{S \subseteq F \setminus {i,j}} \frac{|S|!(|F|-|S|-2)!}{2(|F|-1)!} \Delta_{ij}(S)$$

Where $\Delta_{ij}(S)$ is the interaction effect of features $i$ and $j$ given coalition $S$.

Interpretation:

• $\phi_{i,i}$: Main effect of feature $i$
• $\phi_{i,j}$ ($i \neq j$): Interaction effect between features $i$ and $j$

Property: $$\phi_i = \phi_{i,i} + \sum_{j \neq i} \phi_{i,j}$$

Main SHAP value equals main effect plus half of all pairwise interactions involving feature $i$.

Computing Interactions

TreeExplainer supports exact interaction computation:

explainer = shap.TreeExplainer(model)
shap_interaction_values = explainer.shap_interaction_values(X)

Limitation: Exponentially complex for other explainers (only practical for tree models)

Theoretical Limitations and Considerations

Computational Complexity

Exact Computation: $O(2^n)$ - intractable for large $n$

Specialized Algorithms:

• Tree SHAP: $O(TLD^2)$ - efficient for trees
• Deep SHAP, Kernel SHAP: Approximations required

Implication: For non-tree models with many features, explanations may be approximate.

Feature Independence Assumption

Kernel SHAP and Basic Implementation: Assume features can be independently manipulated

Challenge: Real features are often correlated (e.g., height and weight)

Solutions:

• Use observational approach (conditional expectations)
• TreeExplainer with correlation-aware perturbation
• Feature grouping for highly correlated features

Out-of-Distribution Samples

Issue: Creating coalitions by replacing features may create unrealistic samples (outside training distribution)

Example: Setting "Age=5" and "Has PhD=Yes" simultaneously

Implication: SHAP values reflect model behavior on potentially unrealistic inputs

Mitigation: Use observational approach or carefully selected background data

Causality

SHAP measures association, not causation

SHAP answers: "How does the model's prediction change with this feature?" SHAP does NOT answer: "What would happen if we changed this feature in reality?"

Example:

• SHAP: "Hospital stay length increases prediction of mortality" (association)
• Causality: "Longer hospital stays cause higher mortality" (incorrect!)

Implication: Use domain knowledge to interpret SHAP causally; SHAP alone doesn't establish causation.

Advanced Theoretical Topics

SHAP as Optimal Credit Allocation

SHAP is the unique attribution method satisfying:

1. Local accuracy: Explanation matches model
2. Missingness: Absent features have zero attribution
3. Consistency: Attribution reflects feature importance changes

Proof: Lundberg & Lee (2017) showed Shapley values are the only solution satisfying these axioms.

Connection to Functional ANOVA

SHAP values correspond to first-order terms in functional ANOVA decomposition: $$f(x) = f_0 + \sum_i f_i(x_i) + \sum_{i,j} f_{ij}(x_i, x_j) + ...$$

Where $f_i(x_i)$ captures main effect of feature $i$, and $\phi_i \approx f_i(x_i)$.

Relationship to Sensitivity Analysis

SHAP generalizes sensitivity analysis:

• Sensitivity Analysis: $\frac{\partial f}{\partial x_i}$ (local gradient)
• SHAP: Integrated sensitivity over feature coalition space

Gradient-based methods (GradientExplainer, Integrated Gradients) approximate SHAP using derivatives.

Practical Implications of Theory

Why Use SHAP?

1. Theoretical Guarantees: Only method with consistency, local accuracy, and missingness
2. Unified Framework: Connects and generalizes multiple explanation methods
3. Additive Decomposition: Predictions precisely decompose into feature contributions
4. Model Comparison: Consistency enables comparing feature importance across models
5. Versatility: Works with any model type (with appropriate explainer)

When to Be Cautious

1. Computational Cost: May be slow for complex models without specialized explainers
2. Feature Correlation: Standard approaches may create unrealistic samples
3. Interpretation: Requires understanding baseline, units, and assumptions
4. Causality: SHAP doesn't imply causation; use domain knowledge
5. Approximations: Non-tree methods use approximations; understand accuracy trade-offs

References and Further Reading

Foundational Papers:

• Shapley, L. S. (1951). "A value for n-person games"
• Lundberg, S. M., & Lee, S. I. (2017). "A Unified Approach to Interpreting Model Predictions" (NeurIPS)
• Lundberg, S. M., et al. (2020). "From local explanations to global understanding with explainable AI for trees" (Nature Machine Intelligence)

Key Concepts:

• Cooperative game theory and Shapley values
• Additive feature attribution methods
• Conditional expectation estimation
• Tree SHAP algorithm and polynomial-time computation

This theoretical foundation explains why SHAP is a principled, versatile, and powerful tool for model interpretation.