KernelSHAP

KernelSHAP solves a weighted least squares problem to recover Shapley values. The Shapley kernel assigns infinite weight to the empty and full coalitions, and weights intermediate coalition sizes by:

• π(z) = (M-1) / (M choose |z| * |z| * (M - |z|))

This weighting scheme guarantees the solution satisfies the efficiency, symmetry, dummy, and additivity axioms of Shapley values. The regression targets are the model's predictions on coalitionally masked inputs.

Each coalition is encoded as a binary vector z' ∈ {0,1}^M, where 1 indicates a feature is present and 0 indicates it is absent. The explanation model is linear in this simplified space:

• g(z') = φ₀ + Σ φᵢ z'ᵢ

To map back to the original feature space, a mapping function h_x(z') imputes missing features by sampling from the background dataset. This binary encoding is what makes the additive feature attribution framework computationally tractable.

KernelSHAP requires a background dataset to compute the expected model output when features are missing. When a feature is masked (set to 0 in the coalition vector), its value is replaced by samples drawn from this background:

• Single reference: Use the dataset mean or median for fast, approximate explanations
• Full distribution: Use k-means summarized samples for more accurate conditional expectations
• Interventional approach: Sample from the marginal distribution to break feature correlations, yielding causal SHAP interpretations

The choice of background directly impacts whether you get observational or interventional SHAP values.

Exact Shapley value computation requires evaluating all 2^M coalitions, which is infeasible for high-dimensional data. KernelSHAP approximates the solution by:

• Subsampling coalitions: Drawing N coalitions according to the Shapley kernel distribution
• Convergence guarantees: Error decreases at rate O(1/√N) with the number of samples
• Variance reduction: Techniques like paired sampling (evaluating both z' and its complement) reduce estimator variance
• nsamples parameter: Controls the trade-off between explanation accuracy and computational cost

KernelSHAP can be understood as LIME with a specific kernel and weighting scheme. While LIME uses heuristically chosen proximity measures, KernelSHAP's kernel is derived from coalitional game theory to satisfy Shapley axioms:

• LIME's local surrogate model + Shapley kernel = Shapley value recovery
• The regression loss function minimizes Σ π(z') [f(h_x(z')) - g(z')]²
• This unification means KernelSHAP inherits LIME's model-agnostic flexibility while providing theoretically guaranteed fairness in feature attribution

KernelSHAP scales exponentially with the number of features in the worst case. Practical considerations include:

• Feature limit: Typically feasible for M < 30 features without excessive sampling
• Model evaluations: Each coalition requires a full model forward pass, making it expensive for large models
• Alternatives: For tree models, use TreeSHAP (exact, polynomial time); for deep networks, use DeepSHAP or GradientExplainer
• Mitigation: Feature grouping or dimensionality reduction before applying KernelSHAP can extend its applicability to wider datasets

The overarching game-theoretic framework that unifies additive feature attribution methods. KernelSHAP is one specific, model-agnostic implementation within this framework.

• Unifies LIME, DeepLIFT, and Shapley values under a single class of additive explanation models
• Guarantees three desirable properties: local accuracy, missingness, and consistency
• Provides the theoretical foundation that KernelSHAP's weighted linear regression approximates

A solution concept from coalitional game theory that fairly distributes a total payout among players based on their marginal contributions. KernelSHAP directly estimates these values for ML features.

• Each feature is treated as a player in a cooperative game where the payout is the model prediction
• The Shapley value for a feature is the weighted average of its marginal contribution across all possible feature coalitions
• Computing exact Shapley values requires evaluating 2^M coalitions, making approximation essential for high-dimensional data

A model-specific alternative to KernelSHAP that computes exact Shapley values for tree-based models in polynomial time rather than exponential time.

• Exploits the internal structure of decision trees to track feature contributions along paths
• Computes exact values without sampling, eliminating approximation error
• Orders of magnitude faster than KernelSHAP for models like XGBoost, LightGBM, and random forests
• Not applicable to neural networks or other non-tree architectures where KernelSHAP remains necessary

A representative sample of data used by KernelSHAP to compute the expected model output and to impute missing features during coalition evaluation.

• Replaces absent features with values drawn from the background to simulate their removal
• The choice of background dataset directly impacts SHAP value estimates
• Common strategies include using k-means centroids, a random sample, or the full training set
• Smaller background sets reduce computation time but may introduce sampling bias

A visualization that combines global feature importance with feature effect directionality by displaying the distribution of SHAP values across all instances.

• Features ranked by mean absolute SHAP value, showing overall impact magnitude
• Each point is a single instance, colored by feature value (red = high, blue = low)
• Reveals whether high feature values push predictions upward or downward
• Exposes non-linear relationships and interaction effects at a glance

A predecessor and conceptual cousin to KernelSHAP that also uses local surrogate models to explain individual predictions. KernelSHAP's kernel was derived from LIME's framework.

• LIME samples instances around a prediction and fits a sparse linear model
• KernelSHAP improves on LIME by using a specially weighted kernel that guarantees Shapley value convergence
• LIME's kernel is heuristic; KernelSHAP's kernel is theoretically grounded in game theory
• Both are model-agnostic, but KernelSHAP provides stronger theoretical guarantees for feature attribution