PaperlayerView exact revision on arXiv

Source-linked AI summary

FastSHAP: Real-Time Shapley Value Estimation

Neil Jethani, Mukund Sudarshan, Ian Covert, Su-In Lee, Rajesh Ranganath

arXiv:2107.07436v3stat.MLcs.CVcs.LG

TL;DR

Shapley explanations are theoretically attractive but expensive because exact calculation requires exponentially many model evaluations. FastSHAP learns an explainer using the Shapley weighted least squares characterization, producing estimates in one forward pass; experiments report accurate explanations with large speedups over non-amortized methods.

  • Problem

    Shapley value explanations for black-box models are computationally costly, creating an unmet need for faster approximations that maintain high accuracy.

  • Method

    FastSHAP trains a separate explainer model with an objective inspired by the Shapley value’s weighted least squares characterization, avoiding a ground-truth Shapley training set.

  • Results

    FastSHAP produces accurate Shapley estimates with significant speedups over non-amortized approaches and more accurate image explanations than popular gradient-based methods.

  • Takeaways & Limitations

    FastSHAP makes fast, high-quality Shapley explanations possible for large-scale models and opens a direction for efficient Shapley value estimation.

  • Takeaways & Limitations

    Exact Shapley recovery depends on a sufficiently large dataset, a sufficiently expressive explainer model, and satisfaction of the Efficiency constraint.

Abstract

from arXiv · show

Shapley values are widely used to explain black-box models, but they are costly to calculate because they require many model evaluations. We introduce FastSHAP, a method for estimating Shapley values in a single forward pass using a learned explainer model. FastSHAP amortizes the cost of explaining many inputs via a learning approach inspired by the Shapley value's weighted least squares characterization, and it can be trained using standard stochastic gradient optimization. We compare FastSHAP to existing estimation approaches, revealing that it generates high-quality explanations with orders of magnitude speedup.

1 INTRODUCTION

Shapley values offer theoretically grounded explanations for black-box models, but their computational cost creates a need for fast, accurate approximations. FastSHAP addresses this by learning an explainer that produces estimates in one forward pass and achieves accurate explanations with orders-of-magnitude speedups.

  • Exact Shapley value calculation requires an exponential number of model evaluations, making speed increasingly important for large, high-dimensional models.
  • Existing stochastic estimators reduce computational cost but still require many model evaluations, creating a runtime–accuracy trade-off.
  • FastSHAP learns a separate explainer model that outputs precise Shapley value estimates in a single forward pass.Its training objective is inspired by the Shapley value’s weighted least squares characterization and supports gradient-based optimization.
  • FastSHAP is an amortized approach for generating real-time Shapley value explanations.
  • FastSHAP provides accurate estimates with orders-of-magnitude speedups and outperforms gradient-based methods on quantitative image-explanation metrics.

2 BACKGROUND

Shapley values assign feature contributions by averaging marginal contributions across feature subsets, but their exact computation is exponential. KernelSHAP uses a weighted least squares formulation to estimate these values, yet still requires many evaluations for each input-output pair.

  • 2.1 SHAPLEY VALUES: Shapley values assign each feature a weighted average of its contribution across subsets that exclude that feature.
  • 2.1 SHAPLEY VALUES: The marginal contribution v(s + ei) − v(s) measures feature i’s contribution when added to subset s.
  • 2.1 SHAPLEY VALUES: In model explanation, the value function represents how a prediction changes when subsets of features are removed.
  • 2.1 SHAPLEY VALUES: Exact Shapley computation is infeasible for large d because its defining summation involves exponentially many subsets.
  • 2.2 KERNELSHAP: KernelSHAP estimates Shapley values by solving an approximate weighted least squares problem over sampled feature subsets.Although consistent and empirically unbiased, it often needs many samples and solves the problem separately for each input-output pair.

3 FASTSHAP

FastSHAP amortizes Shapley estimation with a learned parametric explainer trained through the Shapley weighted least squares objective rather than ground-truth explanations. Once trained, it produces explanations in one forward pass, while efficiency constraints and surrogate modeling support the training pipeline.

  • 3 FASTSHAP: FastSHAP amortizes explanation costs across data samples and avoids solving a separate optimization problem for every input.
  • 3.1 AMORTIZING SHAPLEY VALUES: The learned function φfast(x, y; θ) generates Shapley explanations in a single forward pass without requiring a ground-truth Shapley training set.
  • 3.1 AMORTIZING SHAPLEY VALUES: With sufficient data and model expressiveness, enforcing the Efficiency constraint yields exact Shapley values at the global optimizer.
  • 3.1 AMORTIZING SHAPLEY VALUES: Efficiency can be enforced by additive normalization or encouraged by penalizing the efficiency gap during training.
  • 3.1 AMORTIZING SHAPLEY VALUES: FastSHAP reduces gradient variance through minibatching, joint computation across classes, and multiple subset samples per input.
  • 3.1 AMORTIZING SHAPLEY VALUES: Its default value function uses a supervised surrogate model to approximate predictions when only a subset of features is observed.

4 RELATED WORK

Prior work includes model-specific approximations, stochastic sampling methods, and learned explainers. FastSHAP differs by learning Shapley estimates that are fast, model-class-agnostic, and independent of the feature-removal approach.

  • 4 RELATED WORK: Model-specific approximations can be relatively fast but may introduce bias and depend on particular feature-removal approaches.
  • 4 RELATED WORK: Figure 2 compares approximation accuracy with model-evaluation count across three datasets, showing FastSHAP as a single-forward-pass reference line.
  • 4 RELATED WORK: FastSHAP learns an explainer that replaces an estimate requiring orders of magnitude more model evaluations.
  • 4 RELATED WORK: Unlike other fast approximations, FastSHAP is agnostic to both model class and feature-removal approach.

5 STRUCTURED DATA EXPERIMENTS

FastSHAP is evaluated against non-amortized stochastic estimators on structured datasets and across multiple value functions. It reaches comparable accuracy with far fewer model evaluations, including at least a 200× advantage across the tested value-function formulations.

  • Accuracy evaluation: FastSHAP is compared with KernelSHAP, paired KernelSHAP, permutation sampling, and antithetical permutation sampling on structured datasets.The evaluation measures proximity to ground-truth Shapley values and varies the value-function formulation.
  • Computational comparison: FastSHAP generates explanations with a single forward pass, whereas baseline methods require model evaluations for sampled feature subsets.This difference is visualized as a horizontal FastSHAP line against evaluation-dependent baseline curves.
  • Computational comparison: At least 600× faster than original KernelSHAP and 200× faster than the best non-amortized baseline, FastSHAP reaches the same accuracy across all four datasets.KernelSHAP requires 1,200–2,000 evaluations; paired sampling requires 250–1,000, while permutation baselines require 200–1,000 evaluations depending on the variant.
  • Value-function robustness: FastSHAP maintains its computational advantage across surrogate, marginal, and baseline value functions on the marketing dataset.The baseline methods require at least 200 model evaluations and, in some cases, nearly 1,000 to match FastSHAP’s single-pass accuracy.

6 IMAGE EXPERIMENTS

The image experiments compare FastSHAP with Shapley estimators, gradient-based methods, and CXPlain using qualitative and inclusion/exclusion evaluations. FastSHAP provides versatile image explanations and retains strong performance with limited training data, while amortized methods offer low marginal explanation cost.

  • 6.2 EXPLANATION METHODS: The experiments compare FastSHAP, KernelSHAP variants, DeepSHAP, GradCAM, SmoothGrad, IntGrad, and CXPlain on CIFAR-10 and Imagenette.FastSHAP, CXPlain, and KernelSHAP produce 14 × 14 superpixel attributions for each class.
  • 6.3 QUALITATIVE REMARKS: FastSHAP and GradCAM generally localize important objects more reliably than the noisier or more granular baseline explanations.KernelSHAP often fails to localize important regions, while SmoothGrad, IntGrad, and DeepSHAP highlight only small parts of key objects.
  • 6.4 QUANTITATIVE EVALUATION: Inclusion and Exclusion AUC evaluate top-1 accuracy as important image regions are included or excluded, with lower Exclusion AUC and higher Inclusion AUC preferred.The evaluation model approximates the original model’s output for feature subsets, and explanations are evaluated by removing superpixels.
  • 6.4 QUANTITATIVE EVALUATION: FastSHAP outperforms all baselines on Exclusion AUC and ranks second only to KernelSHAP-S on Inclusion AUC.Removing FastSHAP-identified important pixels produces the sharpest decline in top-1 accuracy.
  • 6.4 QUANTITATIVE EVALUATION: FastSHAP is the only approach reported to excel at both Inclusion and Exclusion AUC, making it the most versatile explanation method in these experiments.GradCAM is competitive on Imagenette Exclusion AUC, while KernelSHAP-S marginally leads FastSHAP on Inclusion AUC.
  • 6.4 QUANTITATIVE EVALUATION: Using 25% of Imagenette training data, FastSHAP outperforms most baselines on both AUC metrics and remains competitive with 10%.
  • 6.5 SPEED EVALUATION: FastSHAP has fixed training cost but very low marginal explanation cost, supporting real-time use and potentially compensating for training time when explaining many images.KernelSHAP requires significantly more explanation time, whereas gradient-based methods are slightly slower than the amortized methods.

7 DISCUSSION

FastSHAP addresses the computational cost that has limited Shapley explanations for large-scale models by learning an explainer that produces estimates in one forward pass. The experiments report accurate estimates, significant speedups over non-amortized methods, and more accurate image explanations than popular gradient-based methods.

  • FastSHAP estimates Shapley values in a single forward pass using a learned explainer model.
  • FastSHAP avoids ground-truth Shapley training data by deriving its learning approach from the Shapley value’s weighted least squares characterization.
  • FastSHAP makes fast and high-quality explanations possible for large-scale model settings such as computer vision and natural language processing.

A FASTSHAP GLOBAL OPTIMIZER

FastSHAP’s constrained objective has the true Shapley values as its global optimum under sufficient data, optimization, and model expressiveness. Efficiency regularization relaxes the constraint at finite penalty strengths and can impair optimization when excessive.

  • Efficiency can be enforced through output normalization or relaxed with efficiency regularization using a penalty parameter γ > 0.
  • The constrained weighted least squares objective has a unique global minimizer that outputs the true Shapley values.This follows because the objective is precisely the Shapley value’s weighted least squares characterization.
  • The global optimizer outputs true Shapley values almost everywhere in the data distribution p(x, y).
  • Achieving the global optimum requires sampling from p(x), perfect optimization, and an expressive enough explainer function class.
  • Finite γ relaxes efficiency, while excessively large γ values make gradient-based optimization ineffective.

B ADDITIVE EFFICIENT NORMALIZATION

Additive efficient normalization projects estimated Shapley values onto the efficiency-constrained hyperplane. The projection preserves efficiency and is guaranteed to move estimates closer to the true values.

  • Additive efficient normalization projects estimates onto the hyperplane where the efficiency property is satisfied.It solves a minimum-distance problem subject to 1⊤φeff = v(1) − v(0).
  • The normalization transformation splits the efficiency gap evenly across all feature estimates.
  • FastSHAP implements additive efficient normalization as an output layer to ensure predictions satisfy efficiency.The step can be understood as projecting the network output onto the efficient hyperplane.
  • The corrected estimates are guaranteed to be closer to the true Shapley values than the original estimates.The guarantee follows from orthogonality and the Pythagorean theorem.

C REDUCING GRADIENT VARIANCE

FastSHAP reduces high-variance training gradients through joint class losses, minibatching, multiple coalition samples, and paired sampling. More coalition samples and paired sampling improve closeness to ground-truth Shapley values.

  • Single-sample training can produce gradient covariance that is too large for effective optimization.
  • FastSHAP jointly calculates losses across all output classes to reduce gradient variance.
  • Minibatching across independent inputs and sampling multiple coalitions per input provide additional gradient-variance reduction.
  • Paired sampling matches each coalition s with its complement 1 − s and improves FastSHAP accuracy in experiments.
  • Using more s samples per x improves FastSHAP’s closeness to ground-truth Shapley values.

D FASTSHAP MODELS AND HYPERPARAMETERS

FastSHAP uses neural-network explainers across tabular and image settings, with sampling and efficiency hyperparameters controlling training. Experiments find that more coalition samples, paired sampling, and training-time normalization improve accuracy, while efficiency penalties are less effective.

  • Models: Tabular experiments use neural-network explainers, with neural networks for news and marketing models and boosted trees for census and bankruptcy models.
  • Models: Image experiments use fine-tuned ResNet-50 models and a FastSHAP architecture producing a 14 × 14 × K output tensor.
  • Hyperparameters: Sampling hyperparameters control paired sampling and the number of coalition samples s taken per input x.
  • Sampling hyperparameters: Across all four datasets, increasing training samples of s generally improves mean ℓ2 distance to ground truth, and paired sampling improves accuracy for fixed sample counts greater than 1.
  • Efficiency hyperparameters: Training-time normalization uniformly outperforms no normalization or inference-only normalization, while efficiency regularization generally yields less accurate estimates.

E ADDITIONAL RESULTS FOR IMAGE EXPERIMENTS

Additional image experiments evaluate FastSHAP with log-odds and limited training data, alongside inclusion/exclusion curves and qualitative explanations across CIFAR-10 and Imagenette. FastSHAP remains competitive with substantially reduced training data and is compared with baseline explanation methods.

  • E.1 INCLUSION AND EXCLUSION METRICS: The log-odds inclusion and exclusion metrics reproduce roughly the same ordering between explanation methods as the main-text metrics.These metrics measure average log-odds for the original model’s predicted class while important features are included or excluded.
  • E.1 INCLUSION AND EXCLUSION METRICS: The additional evaluations vary the percentage of pixels included or excluded and report changes in top-1 accuracy or average log-odds for the predicted class.The inclusion and exclusion curves use a set of 1,000 images.
  • E.2 FASTSHAP ROBUSTNESS TO LIMITED DATA: FastSHAP remains competitive when trained on just 10% of the Imagenette training data.Performance is evaluated using inclusion and exclusion AUC based on top-1 accuracy.
  • E.2 FASTSHAP ROBUSTNESS TO LIMITED DATA: With 25% of the Imagenette training data, FastSHAP outperforms most baseline methods by a large margin.The comparison uses inclusion and exclusion AUC calculated from top-1 accuracy.
  • E.3 EXAMPLE FASTSHAP IMAGE EXPLANATIONS: Additional qualitative explanations are shown for randomly selected CIFAR-10 and Imagenette images across FastSHAP and baseline methods.The figures organize examples by image class and explanation method, with FastSHAP-only examples also reporting model logits.
Loading 2107.07436v3…