SHAP values via sparse Fourier representation

• URL: http://arxiv.org/abs/2410.06300v2
• Date: Sun, 11 May 2025 19:42:54 GMT
• Title: SHAP values via sparse Fourier representation
• Authors: Ali Gorji, Andisheh Amrollahi, Andreas Krause,
• Abstract summary: SHAP (SHapley Additive exPlanations) values are a widely used method for local feature attribution in interpretable and explainable AI.<n>We propose an efficient two-stage algorithm for computing SHAP values in both black-box setting and tree-based models.
• Score: 38.818224762845624
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• Efficiently Access Diffusion Fisher: Within the Outer Product Span Space [18.839096876681644]
  We show that the diffusion Fisher actually resides within a space spanned by the outer products of score and initial data.<n>We develop two efficient approximation algorithms to access the trace and matrix-vector multiplication of DF.<n> Experiments in likelihood evaluation and adjoint optimization demonstrate the superior accuracy and reduced computational cost of our proposed algorithms.
  arXiv  Detail & Related papers  (2025-05-29T09:13:36Z)
• Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization [56.805574957824135]
  Two-way partial AUCAUC is a critical performance metric for binary classification with imbalanced data.<n>Existing algorithms for TPAUC optimization remain under-explored.<n>We introduce two innovative double-coordinate block-coordinate algorithms for TPAUC optimization.
  arXiv  Detail & Related papers  (2025-05-28T03:55:05Z)
• Enhanced Derivative-Free Optimization Using Adaptive Correlation-Induced Finite Difference Estimators [6.054123928890574]
  We develop an algorithm designed to enhance DFO in terms of both gradient estimation efficiency and sample efficiency.<n>We establish the consistency of our proposed algorithm and demonstrate that, despite using a batch of samples per iteration, it achieves the same convergence rate as the KW and SPSA methods.
  arXiv  Detail & Related papers  (2025-02-28T08:05:54Z)
• Iterative Methods for Full-Scale Gaussian Process Approximations for Large Spatial Data [9.913418444556486]
  We show how iterative methods can be used to reduce the computational costs for calculating likelihoods, gradients, and predictive distributions with FSAs. We also present a novel, accurate, and fast way to calculate predictive variances relying on estimations and iterative methods. All methods are implemented in a free C++ software library with high-level Python and R packages.
  arXiv  Detail & Related papers  (2024-05-23T12:25:22Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  We propose a straightforward and efficient Shapley estimator, SimSHAP, by eliminating redundant techniques. In our analysis of existing approaches, we observe that estimators can be unified as a linear transformation of randomly summed values from feature subsets. Our experiments validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.
  arXiv  Detail & Related papers  (2023-11-02T06:09:24Z)
• Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
  We introduce a notion of self-concordant smoothing for minimizing the sum of two convex functions, one of which is smooth and the other may be nonsmooth. We prove the convergence of two resulting algorithms: Prox-N-SCORE, a proximal Newton algorithm and Prox-GGN-SCORE, a proximal generalized Gauss-Newton algorithm.
  arXiv  Detail & Related papers  (2023-09-04T19:47:04Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise. In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
  arXiv  Detail & Related papers  (2023-06-13T01:18:16Z)
• Provable benefits of score matching [30.317535687908755]
  We give the first example of a natural exponential family of distributions such that score matching loss is computationally efficient to optimize. We show that designing a zeroth-order or first-order oracle for optimizing the likelihood loss is NP-hard. Minimizing the score matching loss is both computationally and statistically efficient, with complexity in the ambient dimension.
  arXiv  Detail & Related papers  (2023-06-03T03:42:30Z)
• IBIA: An Incremental Build-Infer-Approximate Framework for Approximate Inference of Partition Function [0.0]
  Exact computation of the partition function is known to be intractable. We propose a novel incremental build-infer-approximate framework for approximate inference. We show that the framework can be used to efficiently compute the partition function.
  arXiv  Detail & Related papers  (2023-04-13T09:40:23Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Adaptive deep density approximation for fractional Fokker-Planck equations [6.066542157374599]
  We present an explicit PDF model induced by a flow-based deep generative model, KRnet, which constructs a transport map from a simple distribution to the target distribution. We consider two methods to approximate the fractional Laplacian. Based on these two different ways for the approximation of the fractional Laplacian, we propose two models, MCNF and GRBFNF, to approximate stationary FPEs and time-dependent FPEs.
  arXiv  Detail & Related papers  (2022-10-26T00:58:17Z)
• A Stochastic Bundle Method for Interpolating Networks [18.313879914379008]
  We propose a novel method for training deep neural networks that are capable of driving the empirical loss to zero. At each iteration our method constructs a maximum linear approximation, known as the bundle of the objective learning approximation.
  arXiv  Detail & Related papers  (2022-01-29T23:02:30Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.