mlsanityData to 14 Oct 2026

SHAP values via sparse Fourier representation

arXiv 2410.06300 ↗First posted 8 Oct 2024cs.LGcited by 8

Not on the map. Why?

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.

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

41 of 72 references.

References · 41

  1. 2017A Unified Approach to Interpreting Model Predictionscited by 6,555
  2. 2016XGBoost: A Scalable Tree Boosting Systemcited by 5,166
  3. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  4. 2017Learning Important Features Through Propagating Activation Differencescited by 1,458
  5. 2018On the Spectral Bias of Neural Networkscited by 1,341
  6. 2017A Closer Look at Memorization in Deep Networkscited by 942
  7. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  8. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 738
  9. 2018On Lazy Training in Differentiable Programmingcited by 675
  10. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  11. 2017Deep Neural Networks as Gaussian Processescited by 622
  12. 2019The many Shapley values for model explanationcited by 344
29 more
  1. 2018CatBoost: gradient boosting with categorical features supportcited by 208
  2. 2019Explaining individual predictions when features are dependent: More accurate approximations to Shapley valuescited by 208
  3. 2019SGD on Neural Networks Learns Functions of Increasing Complexitycited by 204
  4. 2018Deep learning generalizes because the parameter-function map is biased towards simple functionscited by 183
  5. 2019Towards Understanding the Spectral Bias of Deep Learningcited by 174
  6. 2019Feature relevance quantification in explainable AI: A causal problemcited by 167
  7. 2020Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regressioncited by 154
  8. 2021The Low-Rank Simplicity Bias in Deep Networkscited by 154
  9. 2020Frequency Bias in Neural Networks for Input of Non-Uniform Densitycited by 140
  10. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  11. 2019The Convergence Rate of Neural Networks for Learned Functions of Different Frequenciescited by 135
  12. 2020True to the Model or True to the Data?cited by 126
  13. 2021FastSHAP: Real-Time Shapley Value Estimationcited by 125
  14. 2021Sampling Permutations for Shapley Value Estimationcited by 102
  15. 2020On the Tractability of SHAP Explanationscited by 92
  16. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  17. 2020Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networkscited by 77
  18. 2019A Fine-Grained Spectral Perspective on Neural Networkscited by 68
  19. 2017SGD Learns the Conjugate Kernel Class of the Networkcited by 54
  20. 2020Efficient computation and analysis of distributional Shapley valuescited by 38
  21. 2021Fast TreeSHAP: Accelerating SHAP Value Computation for Treescited by 29
  22. 2015Steps Toward Deep Kernel Methods from Infinite Neural Networkscited by 28
  23. 2017CLTune: A Generic Auto-Tuner for OpenCL Kernelscited by 27
  24. 2020GPUTreeShap: Massively Parallel Exact Calculation of SHAP Scores for Tree Ensemblescited by 14
  25. 2023A Scalable Walsh-Hadamard Regularizer to Overcome the Low-degree Spectral Bias of Neural Networkscited by 10
  26. 2024On the Tractability of SHAP Explanations under Markovian Distributionscited by 10
  27. 2013A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domaincited by 9
  28. 2015SPRIGHT: A Fast and Robust Framework for Sparse Walsh-Hadamard Transformcited by 6
  29. 2015Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transformcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 6; 2026: 2.

8 papers.

  1. 2025ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMscited by 16
  2. 2026An Odd Estimator for Shapley Valuescited by 5
  3. 2025From Decision Trees to Boolean Logic: A Fast and Unified SHAP Algorithmcited by 3
  4. 2025Tractable Shapley Values and Interactions via Tensor Networkscited by 2
  5. 2025SHAP values through General Fourier Representations: Theory and Applicationscited by 1
  6. 2026Exact Functional ANOVA Decomposition for Categorical Inputs Modelscited by 1
  7. 2025CUBE: Contrastive Understanding by Balanced Experimentscited by 0
  8. 2025Fourier Analysis on the Boolean Hypercube via Hoeffding Functional Decompositioncited by 0