Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes

• URL: http://arxiv.org/abs/2508.14499v1
• Date: Wed, 20 Aug 2025 07:39:14 GMT
• Title: Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes
• Authors: Majid Mohammadi, Krikamol Muandet, Ilaria Tiddi, Annette Ten Teije, Siu Lun Chau,
• Abstract summary: Shapley values are widely recognized as a principled method for attributing importance to input features in machine learning.<n>We show that the exact computation of Shapley values scales exponentially with the number of features.<n>Our work provides more scalable, axiomatically sound, and uncertainty-aware explanations for predictions generated by structured probabilistic models.
• Score: 12.496136169054541
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Shapley values are widely recognized as a principled method for attributing importance to input features in machine learning. However, the exact computation of Shapley values scales exponentially with the number of features, severely limiting the practical application of this powerful approach. The challenge is further compounded when the predictive model is probabilistic - as in Gaussian processes (GPs) - where the outputs are random variables rather than point estimates, necessitating additional computational effort in modeling higher-order moments. In this work, we demonstrate that for an important class of GPs known as FANOVA GP, which explicitly models all main effects and interactions, *exact* Shapley attributions for both local and global explanations can be computed in *quadratic time*. For local, instance-wise explanations, we define a stochastic cooperative game over function components and compute the exact stochastic Shapley value in quadratic time only, capturing both the expected contribution and uncertainty. For global explanations, we introduce a deterministic, variance-based value function and compute exact Shapley values that quantify each feature's contribution to the model's overall sensitivity. Our methods leverage a closed-form (stochastic) M\"{o}bius representation of the FANOVA decomposition and introduce recursive algorithms, inspired by Newton's identities, to efficiently compute the mean and variance of Shapley values. Our work enhances the utility of explainable AI, as demonstrated by empirical studies, by providing more scalable, axiomatically sound, and uncertainty-aware explanations for predictions generated by structured probabilistic models.

Related papers

• Computing Exact Shapley Values in Polynomial Time for Product-Kernel Methods [11.743255602108775]
  PKeX-Shapley is a novel algorithm that enables the exact computation of Shapley values in time.<n>We show that PKeX-Shapley yields computational efficiency and enhances interpretability in kernel-based learning.
  arXiv  Detail & Related papers  (2025-05-22T10:53:04Z)
• Improving the Weighting Strategy in KernelSHAP [0.8057006406834466]
  In Explainable AI (XAI) Shapley values are a popular framework for explaining predictions made by complex machine learning models.<n>We propose a novel modification of KernelSHAP which replaces the deterministic weights with ones to reduce the variance of the resulting Shapley value approximations.<n>Our methods can reduce the required number of contribution function evaluations by $5%$ to $50%$ while preserving the same accuracy of the approximated Shapley values.
  arXiv  Detail & Related papers  (2024-10-07T10:02:31Z)
• Scaling and renormalization in high-dimensional regression [72.59731158970894]
  We present a unifying perspective on recent results on ridge regression.<n>We use the basic tools of random matrix theory and free probability, aimed at readers with backgrounds in physics and deep learning.<n>Our results extend and provide a unifying perspective on earlier models of scaling laws.
  arXiv  Detail & Related papers  (2024-05-01T15:59:00Z)
• Energy-Based Model for Accurate Estimation of Shapley Values in Feature Attribution [7.378438977893025]
  EmSHAP (Energy-based model for Shapley value estimation) is proposed to estimate the expectation of Shapley contribution function.<n>GRU (Gated Recurrent Unit)-coupled partition function estimation method is introduced.
  arXiv  Detail & Related papers  (2024-04-01T12:19:33Z)
• 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)
• Generalizing Backpropagation for Gradient-Based Interpretability [103.2998254573497]
  We show that the gradient of a model is a special case of a more general formulation using semirings. This observation allows us to generalize the backpropagation algorithm to efficiently compute other interpretable statistics.
  arXiv  Detail & Related papers  (2023-07-06T15:19:53Z)
• Explaining the Uncertain: Stochastic Shapley Values for Gaussian Process Models [15.715453687736028]
  We present a novel approach for explaining Gaussian processes (GPs) that can utilize the full analytical covariance structure in GPs. Our method is based on the popular solution concept of Shapley values extended to cooperative games, resulting in explanations that are random variables. The GP explanations generated using our approach satisfy similar axioms to standard Shapley values and possess a tractable covariance function across features and data observations.
  arXiv  Detail & Related papers  (2023-05-24T13:59:03Z)
• Monte Carlo Neural PDE Solver for Learning PDEs via Probabilistic Representation [59.45669299295436]
  We propose a Monte Carlo PDE solver for training unsupervised neural solvers.<n>We use the PDEs' probabilistic representation, which regards macroscopic phenomena as ensembles of random particles.<n>Our experiments on convection-diffusion, Allen-Cahn, and Navier-Stokes equations demonstrate significant improvements in accuracy and efficiency.
  arXiv  Detail & Related papers  (2023-02-10T08:05:19Z)
• Multiplicative noise and heavy tails in stochastic optimization [62.993432503309485]
  empirical optimization is central to modern machine learning, but its role in its success is still unclear. We show that it commonly arises in parameters of discrete multiplicative noise due to variance. A detailed analysis is conducted in which we describe on key factors, including recent step size, and data, all exhibit similar results on state-of-the-art neural network models.
  arXiv  Detail & Related papers  (2020-06-11T09:58:01Z)
• Rigorous Explanation of Inference on Probabilistic Graphical Models [17.96228289921288]
  We propose GraphShapley to integrate the decomposability of Shapley values, the structure of computation MRFs, and the iterative nature of BP inference. On nine graphs, we demonstrate that GraphShapley provides sensible and practical explanations.
  arXiv  Detail & Related papers  (2020-04-21T14:57:12Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)

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.