Functional ANOVA offers a principled framework for interpretability by decomposing a model's prediction into main effects and higher-order interactions. For independent features, this decomposition is well-defined, strongly linked with SHAP values, and serves as a cornerstone of additive explainability. However, the lack of an explicit closed-form expression for general dependent distributions has forced practitioners to rely on costly sampling-based approximations. We completely resolve this limitation for categorical inputs. By bridging functional analysis with the extension of discrete Fourier analysis, we derive a closed-form decomposition without any assumption. Our formulation is computationally very efficient. It seamlessly recovers the classical independent case and extends to arbitrary dependence structures, including distributions with non-rectangular support. Furthermore, leveraging the intrinsic link between SHAP and ANOVA under independence, our framework yields a natural generalization of SHAP values for the general categorical setting.
Figures & tables
Figure 1: ANOVA-Based Shapley Values on the Binarized MNIST Dataset. We apply our framework on a MLP trained on binarized MNIST, encoded as a tabular dataset of shape (60000,784) . The attribution targets the predicted probability of the specific class ‘3’, defined as f(x):=P(MLP(x)=3) . (Left) The original input sample (digit ‘8’). (Middle) Signed local attributions: red pixels increase the probability of the target class ‘3’, while blue pixels decrease it. (Right) Absolute attribution magnitudes. We observe a behavior consistent with the nature of the digits. The pixels on the right side, which overlap with the shape of a ‘3’, positively contribute to the target probability (red). Conversely, the pixels on the left side close the loops, acting as the distinguishing features between an ‘8’ and a ‘3’; these pixels correctly penalize the target probability (blue), allowing the model to rule out class ‘3’.
Order
Subset A
Norm ∥fA∥22
Intercept
∅
0.111
Main Effects
{1}
0.518
{2}
0.074
{4}
0.000
Interactions
{1,2}
0.074
{1,4}
0.000
Table 1: Norms of ANOVA Decomposition elements fA .
Dataset
d
{N1,…,Nd}
∣E∣
Car Evaluation
6
{4,4,4,3,3,3}
1728
Nursery
8
{3,5,4,4,3,2,3,3}
12960
Table 2: Uniform categorical datasets.
X1
X2
X3
X4
X5
X6
Class 0
2.01
1.30
0.01
0.28
0.03
0.30
Class 1
0.16
0.15
0.00
0.04
0.01
0.05
Class 2
2.89
1.46
0.02
0.71
0.05
0.71
Class 3
0.21
0.09
0.01
0.04
0.04
0.12
Table 3: 100×ISE on Car Evaluation .
X1
X2
X3
X4
X5
X6
X7
X8
Class 0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Class 1
1.6
3.7
0.3
0.3
0.2
0.0
0.3
1.8
Class 2
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Class 3
1.9
4.4
0.2
0.0
0.1
0.0
0.1
1.7
Class 4
0.2
0.3
0.1
0.1
0.0
0.0
0.1
0.3
Table 4: 100×ISE on Nursery .
Figure 2: Global Feature Importance on Mushrooms dataset.
Dataset
d
r
∣E∣
Poker Hand
10
25 000
525
Connect-4
42
67 000
342
Dota2 Results
113
102 000
3115
Table 5: Characteristics of large-scale sparse datasets.
Dataset
rmain
Time
R2
MSE
Rel. MSE
Poker Hand
76
1.8s
0.003
0.24
49%
Connect-4
83
10s
0.45
0.07
13%
Dota2
112
23s
0.36
0.02
6%
Table 6: Performance & Metrics. Top: Fast approximation restricted to main effects ( rmain ). Bottom: Higher rank approximation ( rlow ) for reconstruction analysis.
Figure 3: Global feature importance on the Poker Hand dataset.
rlow
Time
R2
MSE
Rel. MSE
Main Effects
674
10s
0.54
0.04
41%
Low rank
2 500
90s
0.77
0.02
20%
Middle rank
5 000
300s
0.83
0.01
15%
High rank
10 000
15min
0.86
0.01
12%
Table 7: Performance & Metrics.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Orthogonality
Differences between indicators
d
XGB R2
Closed-Form
TreeHFD
Main Effects
Shapley Values
2
0.9975
1.54×10−19
1.77×10−4
1.87×10−3
1.33×10−5
4
0.9966
5.65×10−18
4.73×10−3
2.44×10−2
5.57×10−4
6
0.9966
1.42×10−16
8.31×10−3
2.02×10−2
3.81×10−4
8
0.9899
3.57×10−16
8.59×10−3
7.88×10−3
4.89×10−5
10
0.9790
2.72×10−16
6.65×10−4
1.61×10−3
2.26×10−6
Appendix
Table 8: Comparison between our closed-form ANOVA and TreeHFD.