Exact Functional ANOVA Decomposition for Categorical Inputs Models
This provides a foundational tool for interpretable machine learning, enabling exact decomposition of model predictions for categorical data without independence assumptions.
The paper tackles the problem of computing functional ANOVA decompositions for models with categorical inputs under dependent feature distributions, deriving a closed-form expression that eliminates the need for costly sampling-based approximations. The result is a computationally efficient framework that generalizes SHAP values to arbitrary dependence structures.
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.