SHAP values via sparse Fourier representation

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. We assume the black-box predictor or tree model accepts binary (zero-one) features. Motivated by spectral bias in real-world predictors, we first approximate the predictor using compact Fourier representations, exactly for trees and approximately for black-box models. In the second stage, we introduce a closed-form formula for 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.