Research map / Learning theory and algorithms / Prediction and decision losses
SHAP values via sparse Fourier representation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FourierShap, which approximates black-box or tree models with a sparse Walsh-Hadamard (Fourier) representation and then computes exact interventional SHAP values from it via a closed-form, parallelizable summation.
Problem
Computing SHAP values requires an exponential sum over feature coalitions, making explanation of large datasets slow, especially in the black-box setting where only query access is available.
Approach
Exploits spectral bias: neural nets and tree ensembles over binary features have sparse, low-degree Walsh-Hadamard spectra. The paper derives a closed-form expression for the interventional SHAP value of a single Fourier basis function, which removes the exponential sum and linearizes computation over frequencies and background points, so the sparse Fourier approximation is computed once and amort
Key results
- Closed-form interventional SHAP computation for Fourier representations runs in Theta(n|D|k) flops and yields SHAP values identical to TreeSHAP for exact tree Fourier representations.
- In the black-box setting, FourierShap achieves roughly 10-100x speedup over DeepLift while being more accurate and using only query access, per the paper's claims.
- Reported speedups of 10-10000x over baseline methods across settings (conclusion); tunable accuracy-speed trade-off via Fourier sparsity k.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FourierShap instead of baseline methods for SHAP computation | SHAP computation · Overall experiments | speedup: 10-10000x | Helped |
| Use FourierSHAP instead of DeepLift | Neural network SHAP computation · Neural network models | speedup: 10-100x | Helped |
| Use FourierSHAP instead of FastShap | Amortized model-agnostic SHAP computation · FourierSHAP's four experimental settings | SHAP accuracy: 3/4 settings | Mixed |
| Use exact Fourier representation to compute tree-model SHAP values | Random forest models · Tree setting | SHAP value agreement | Helped |
| Increase Fourier sparsity parameter k | FourierSHAP · Black-box models | SHAP accuracy | Helped |
| Increase Fourier sparsity parameter k | FourierSHAP · Black-box models | runtime | Hurt |
| Use Precompute instead of Base implementation (ablation) | FourierSHAP implementation · Implementation experiments | runtime | Helped |
| Use Positional instead of Sparse implementation (ablation) | FourierSHAP implementation · Low-degree Fourier spectra | runtime | Helped |
| Increase FastShap MLP depth | FastShap · Black-box SHAP accuracy | SHAP accuracy | No clear effect |
Limitations
- Requires binary or one-hot categorical inputs; continuous features must be discretized.
- Black-box accuracy depends on the Fourier approximation quality, which is approximate for neural networks.
- Ground-truth SHAP values rely on KernelSHAP run to convergence rather than exact computation for black-box experiments.
Experimental setup
Datasets: Entacmaea fluorescent protein SGEMM GPU kernel performance GB1 protein fitness avGFP fluorescence
Benchmarks: Entacmaea SGEMM GB1 avGFP
Metrics: R^2 of Fourier approximation vs black-box R^2 of SHAP values vs ground truth speedup relative to KernelSHAP runtime
Baselines: KernelSHAP LinRegShap DeepLift FastSHAP TreeSHAP FastTreeSHAP PLTreeSHAP GPUTreeShap
Builds on: KernelSHAP TreeSHAP sparse Walsh-Hadamard transform FastSHAP neural tangent kernel spectral bias
Closest papers by meaning
- On the Tractability of SHAP Explanations under Markovian Distributions (ICML 2024 · similarity 0.88)
- OperatorSHAP: Fast and Accurate Shapley Value Estimation for Neural Operators (NeurIPS 2026 · similarity 0.88)
- SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism (NeurIPS 2025 · similarity 0.88)
- InstaSHAP: Interpretable Additive Models Explain Shapley Values Instantly (ICLR 2025 · similarity 0.87)
- Provably Accurate Shapley Value Estimation via Leverage Score Sampling (ICLR 2025 · similarity 0.87)
- Shaping Up SHAP: Enhancing Stability through Layer-Wise Neighbor Selection (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.