KernelSHAP: A Model-Agnostic Approach

Shapley values establish a theoretical foundation for fair feature attribution. However, their exact calculation often requires evaluating the model on all possible subsets of features ($2^M$ evaluations for $M$ features), which is computationally infeasible for most models. Approximation methods address this challenge, with KernelSHAP being a widely used, model-agnostic approach to estimate these values.

Think of KernelSHAP as building a bridge between the ideas we saw in LIME and the theoretical rigor of Shapley values. Like LIME, KernelSHAP explains a prediction by fitting a local surrogate model. However, instead of arbitrary perturbations, KernelSHAP uses a specific sampling strategy and weighting scheme derived directly from the properties of Shapley values. This makes it model-agnostic – it doesn't need to know the internal workings of your complex model, only its input and output behavior.

How KernelSHAP Works

KernelSHAP estimates the contribution of each feature to the prediction for a specific instance $x$. Here’s a breakdown of the process:

1. Sampling Coalitions: To estimate the effect of a feature, we need to evaluate the model's output when that feature is present versus when it is "absent". KernelSHAP achieves this by generating samples, often called "coalitions". A coalition represents a subset of the original features being present.
2. Representing Feature Absence: How do we simulate a feature being "absent" for a model that expects all features? KernelSHAP uses a background dataset. To create a perturbed sample representing a specific coalition (subset of features), the features present in the coalition keep their values from the instance $x$ we want to explain. The features absent from the coalition take values sampled from the background dataset. This background dataset ideally represents the expected distribution of feature values, allowing us to approximate the effect of removing a feature by replacing it with a typical value.
3. Model Evaluation: The original black-box model is used to get predictions for each of these generated perturbed samples.
4. Weighted Linear Regression: KernelSHAP then fits a weighted linear regression model to these predictions. The inputs to this linear model are binary indicators ($z'$) representing whether each original feature was present ($z'_i=1$) or absent ($z'_i=0$) in the perturbed sample. The target variable is the prediction made by the original model for that perturbed sample. The model takes the form: $g(z') = \phi_0 + \sum_{i=1}^{M} \phi_i z'_i$ Here, $g(z')$ approximates the prediction of the original model for the coalition represented by $z'$, $M$ is the number of features, $\phi_0$ is the base value (the average prediction over the background dataset, $E[f(X)]$), and the coefficients $\phi_i$ are the estimated SHAP values for each feature $i$.
5. SHAP Kernel Weights: The main part is the weighting. Samples are not weighted equally in the regression. KernelSHAP uses specific weights, known as the SHAP kernel, derived from the Shapley value definition. These weights give more importance to coalitions with very few features (e.g., only one feature present) or almost all features (e.g., only one feature absent). This weighting scheme ensures that the resulting coefficients ($\phi_i$) satisfy the desirable properties of Shapley values, such as local accuracy and consistency, as closely as possible through this estimation process.

A simplified view of the KernelSHAP workflow, highlighting the use of the instance, background data, model evaluations, and weighted linear regression to estimate SHAP values.

Practical Notes

• Model-Agnosticism: KernelSHAP's primary strength is its ability to work with any machine learning model, regardless of its internal structure. As long as you can provide inputs and get outputs, you can use KernelSHAP.
• Background Dataset Choice: The choice of the background dataset is significant. It defines the baseline for "missing" features. A common approach is to use a representative sample of the training data or a summarized version (e.g., using k-means centroids) to reduce computation. The SHAP library often defaults to using zeros or means/modes, but providing a data sample is generally recommended for more meaningful results.
• Computational Cost: Generating samples, running the model predictions, and fitting the weighted regression can be computationally intensive, especially for models with slow prediction times, high-dimensional data, or when using a large background dataset. The number of samples needed for accurate estimation scales with the number of features.
• Approximation Quality: Remember that KernelSHAP provides estimates of the true Shapley values. The accuracy depends on the number of samples used and the suitability of the background dataset. For tree-based models, specialized algorithms like TreeSHAP (discussed next) can compute exact SHAP values much more efficiently.

KernelSHAP provides a powerful and theoretically grounded way to apply the principles of Shapley values to virtually any machine learning model. It serves as a fundamental tool in the SHAP framework, enabling explanations even for complex black-box systems where model internals are inaccessible. However, its computational demands mean that for specific model types like trees, more efficient, specialized methods are often preferred.