Exact Functional ANOVA Decomposition for Categorical Inputs Models

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.

When a machine learning model makes a prediction, which features actually drove the decision? This question lies at the heart of eXplainable AI (XAI). Modern architectures chain millions of non-linear operations between input and output, making the direct link impossible to inspect by hand. A long-standing answer is to decompose the prediction into the contribution of each feature, of each pair, and so on — a framework known as functional ANalysis Of VAriance (ANOVA). But a clean closed-form decomposition is only known when the input features are independent, an assumption that real-world tabular data with categorical variables rarely satisfy. We close this gap for categorical inputs. By combining ANOVA literature with linear algebra and Boolean Fourier analysis, we derive an exact decomposition valid under any dependence structure. Our approach turns the explanation of any categorical-input model into an explicit additive sum and computed once, replacing noisy sampling-based approximations with a principled and theoretically grounded answer.