# SHAP values via sparse Fourier representation

arXiv: https://arxiv.org/abs/2410.06300 · HTML: https://mlsanity.com/paper/2410.06300/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 72 references that are in the map.
- First posted on arXiv 8 Oct 2024.

## Builds on (most cited first, 30 of 41)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Learning Important Features Through Propagating Activation Differences](https://mlsanity.com/paper/1704.02685/) (2017)
- [On the Spectral Bias of Neural Networks](https://mlsanity.com/paper/1806.08734/) (2018)
- [A Closer Look at Memorization in Deep Networks](https://mlsanity.com/paper/1706.05394/) (2017)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [CatBoost: gradient boosting with categorical features support](https://mlsanity.com/paper/1810.11363/) (2018)
- [Explaining individual predictions when features are dependent: More accurate approximations to Shapley values](https://mlsanity.com/paper/1903.10464/) (2019)
- [SGD on Neural Networks Learns Functions of Increasing Complexity](https://mlsanity.com/paper/1905.11604/) (2019)
- [Deep learning generalizes because the parameter-function map is biased towards simple functions](https://mlsanity.com/paper/1805.08522/) (2018)
- [Towards Understanding the Spectral Bias of Deep Learning](https://mlsanity.com/paper/1912.01198/) (2019)
- [Feature relevance quantification in explainable AI: A causal problem](https://mlsanity.com/paper/1910.13413/) (2019)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [The Low-Rank Simplicity Bias in Deep Networks](https://mlsanity.com/paper/2103.10427/) (2021)
- [Frequency Bias in Neural Networks for Input of Non-Uniform Density](https://mlsanity.com/paper/2003.04560/) (2020)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies](https://mlsanity.com/paper/1906.00425/) (2019)
- [True to the Model or True to the Data?](https://mlsanity.com/paper/2006.16234/) (2020)
- [FastSHAP: Real-Time Shapley Value Estimation](https://mlsanity.com/paper/2107.07436/) (2021)
- [Sampling Permutations for Shapley Value Estimation](https://mlsanity.com/paper/2104.12199/) (2021)
- [On the Tractability of SHAP Explanations](https://mlsanity.com/paper/2009.08634/) (2020)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks](https://mlsanity.com/paper/2005.11879/) (2020)
- [A Fine-Grained Spectral Perspective on Neural Networks](https://mlsanity.com/paper/1907.10599/) (2019)

## Built on by (most cited first, 8 of 8)

- [ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs](https://mlsanity.com/paper/2505.17495/) (2025)
- [An Odd Estimator for Shapley Values](https://mlsanity.com/paper/2602.01399/) (2026)
- [From Decision Trees to Boolean Logic: A Fast and Unified SHAP Algorithm](https://mlsanity.com/paper/2511.09376/) (2025)
- [Tractable Shapley Values and Interactions via Tensor Networks](https://mlsanity.com/paper/2510.22138/) (2025)
- [SHAP values through General Fourier Representations: Theory and Applications](https://mlsanity.com/paper/2511.00185/) (2025)
- [Exact Functional ANOVA Decomposition for Categorical Inputs Models](https://mlsanity.com/paper/2603.02673/) (2026)
- [CUBE: Contrastive Understanding by Balanced Experiments](https://mlsanity.com/paper/2509.10825/) (2025)
- [Fourier Analysis on the Boolean Hypercube via Hoeffding Functional Decomposition](https://mlsanity.com/paper/2510.07088/) (2025)

## Abstract (arXiv)

SHAP (SHapley Additive exPlanations) values are a widely used method for local feature attribution in interpretable and explainable AI. We propose an efficient two-stage algorithm for computing SHAP values in both black-box setting and tree-based models. Motivated by spectral bias in real-world predictors, we first approximate models using compact Fourier representations, exactly for trees and approximately for black-box models. In the second stage, we introduce a closed-form formula for em exactly computing SHAP values using the Fourier representation, that ``linearizes'' the computation into a simple summation and is amenable to parallelization. As the Fourier approximation is computed only once, our method enables amortized SHAP value computation, achieving significant speedups over existing methods and a tunable trade-off between efficiency and precision.