Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes
Majid Mohammadi, Krikamol Muandet, Ilaria Tiddi, Annette Ten Teije, Siu Lun Chau · 2025
Read Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes by Majid Mohammadi, Krikamol Muandet, Ilaria Tiddi, Annette Ten Teije, Siu Lun Chau (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-14499.txt.
Introduction
Majid Mohammadi, Krikamol Muandet, Ilaria Tiddi, Annette Ten Teije, and Siu Lun Chau speed up a fair way of crediting inputs in AI models, in a 2025 paper. Shapley values, borrowed from game theory, split a model's output fairly among its input features. Computing them exactly normally takes time that explodes as features grow. The cost worsens for models that give probabilities, not single numbers.
For one useful class of Gaussian process models, the team prove exact Shapley values can be found in quadratic time. Those models spell out each feature's effect and each pair's interplay. Quadratic time is fast enough for real use. They define the scores for single cases and for whole data sets. Faster fair credit could make model explanations routine in high-stakes fields.
Catalog record
| CREATOR | Majid Mohammadi, Krikamol Muandet, Ilaria Tiddi, Annette Ten Teije, Siu Lun Chau |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-14499
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes Majid Mohammadi, Krikamol Muandet, Ilaria Tiddi, Annette Ten Teije, Siu Lun Chau 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ö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. Keywords: Stochastic Shapley value, Gaussian processes, Explainable AI Introduction As machine learning (ML) systems are increasingly deployed in high-stakes applications, the demand for interpretability has grown substantially. Practitioners and regulators alike now seek models whose predictions can be understood and trusted—not only globally, across the entire data distribution, but also locally, for specific predictions. To address this need, the literature offers two distinct approaches: (i) designing inherently interpretable models, such as linear models or generalized additive models (GAMs), or (ii) applying post-hoc interpretation methods like SHAP Lundberg and Lee 2017 or LIME Ribeiro et al. 2016 to interpret complex, black-box models. However, interpretability is context-dependent. A model that appears interpretable to ML practitioners—such as GAM—may remain opaque to domain experts or end-users, such as medical professionals. In such cases, even inherently interpretable models may require an additional explanatory layer to translate their insights into signals accessible to non-technical stakeholders. Functional ANOVA Gaussian Processes (FANOVA GPs) ( Durrande et al. 2011 ) are a class of probabilistic models that combine the flexibility of GPs with the interpretability of functional ANOVA decompositions. They represent the prediction function as a sum of functions defined over subsets of input features, where each term models either a main effect or a higher-order interaction. By enforcing functional ANOVA constraints ( Hooker 2004 ) , these components become orthogonal (see Section 2 ), allowing the contribution from each subset to be uniquely and meaningfully identified. Unlike conventional kernels, which typically entangle all features through a single joint interaction term, FANOVA GPs encode a structured hierarchy of interactions—from individual features to the full feature set—making the decomposition both interpretable and expressive. This structure enables precise attribution of predictive behavior to specific feature sets, while preserving GP’s nonparametric nature and the ability to quantify uncertainty. As a result, FANOVA GPs offer a compelling foundation for interpretable probabilistic modeling. Nonetheless, as FANOVA GPs impose an interpretable additive structure by construction, the number of potential interactions grows exponentially with the number of input features. Consequently, identifying the overall contribution of each feature—especially in the presence of higher-order interactions—can become cognitively intractable for human users, much like interpreting a random forest by examining each tree’s decision logic. Moreover, existing interpretation methods for FANOVA GP either lack axiomatic support or are computationally inefficient. For example, global sensitivity analysis techniques based on first-order Sobol indices ( Sobol 2001 ; Lu et al. 2022 ) ignore interaction effects, fail to satisfy key axioms such as efficiency ( Owen 2014 ) , and often underestimate feature importance. On the other hand, although the GPSHAP algorithm of Chau et al. 2023 could, in principle, be applied to FANOVA GPs, it does not exploit their additive structure—a structure that, as we show, enables significant computational savings. Moreover, the standard expectation-based value functions they employ require additional estimation, introducing potential sources of error. In contrast, our approach adopts a more natural value function tailored to FANOVA models ( Fumagalli et al. 2025 ; Mohammadi et al. 2025a ) , allowing us to compute exact Shapley values without estimation, thereby avoiding approximation errors entirely. Our approach also yields stochastic explanations that account for the predictive uncertainty inherent in GPs. In short, this paper proposes algorithms that leverage the structure of FANOVA GPs to deliver both local and global explanations via the Shapley value ( Shapley 1953 ) , computed exactly and in quadratic time . Our key technical insight is that the orthogonal additive decomposition allows us to derive a closed-form (stochastic) Möbius representation of the prediction function, enabling efficient computation of Shapley values and their associated uncertainty propagated from the GPs. We develop recursive algorithms, inspired by Newton’s identities, that avoid exponential enumeration over feature subsets and compute the Shapley values for local and global explanation efficiently. The contributions of this paper can be summarized as follows: 1. Explaining the uncertain. We propose the FGPX-Shapley-L ( F ANOVA GP -based e X act Shapley value for L ocal explanation) algorithm to provide local explanations in the form of stochastic Shapley values ( Ma et al. 2008 ) for FANOVA GPs that can be computed in quadratic time through a recursive algorithm using Newton’s identities. 2. Explaining the uncertainty. We propose the FGPX-Shapley-G (G for global) algorithm to attribute the variance of the prediction as global feature attribution, following the spirit in classical global sensitive analysis literature. A recursive, quadratic-time algorithm is also devised to ensure computational efficiency. Taken together, our results show that interpretability, axiomatic attribution, and computational efficiency need not be at odds—provided that the model admits the right structure. FANOVA GPs, and the methods we develop to explain them, offer a new blueprint for scalable and rigorous explainable machine learning. Preliminaries Notations. We denote the set of d features by \mathcal{D} , and its power set 2^{\mathcal{D}} . The training set \{\boldsymbol{x}_{i},y_{i}\}_{i=1}^{n} consists of \boldsymbol{x}_{i}\in\mathbb{R}^{d} and y\in\mathbb{R} (regression) or y\in\{1,\dots,\ell\} ( \ell -class classification). Let \textbf{X}\in\mathbb{R}^{n\times d} denote the full input dataset, and \textbf{X}_{\mathcal{S}} its restriction to feature subset \mathcal{S}\in 2^{\mathcal{D}} ; the corresponding sample space is X_{\mathcal{S}} . The probability density of feature i is denoted p(X_{i}) . We use calligraphic letters for sets, capital letters for random variables, and bold-faced lower- and upper-cased letters for vectors and matrices, respectively. Element-wise product is denoted by \odot , expectation over data and model f ’s predictive distribution is denoted by \mathbb{E}_{X} and \mathbb{E}_{f} , and variances by \mathbb{V}_{X} and \mathbb{V}_{f} . 2.1 FANOVA Gaussian process We focus our exposition on regression tasks for clarity. Nonetheless, the proposed Shapley algorithms remain applicable to classification problems, provided that the posterior distribution of the FANOVA GP is available. We assume observations y arise from a latent function f(\boldsymbol{x}) corrupted