Generalized Functional ANOVA in Closed-Form: A Unified View of Additive Explanations

Technical Summary: Generalized Functional ANOVA in Closed-Form

Problem Statement
Modern machine learning models, particularly complex ensembles and neural networks, often operate as opaque "black boxes," making their input-output mappings difficult to interpret. While Explainable AI (XAI) has produced numerous post-hoc explanation methods (e.g., SHAP, LIME) and inherently interpretable models (e.g., GAMs, EBM), these approaches face two primary criticisms: they often rely on heuristic constructions lacking rigorous representation theorems, and they can be computationally expensive or formally intractable.

A central challenge in interpretability is the Functional ANOVA decomposition (or Hoeffding decomposition), which decomposes a predictor into main effects and higher-order interactions. While this decomposition is explicit and orthogonal for independent inputs, obtaining a tractable representation for dependent inputs remains difficult. Existing methods for dependent settings often require knowledge of the input density, are restricted to specific model types (e.g., tree ensembles), or have only recently been solved for categorical data. There is a need for a unified, model-agnostic framework that provides an explicit, closed-form solution for continuous dependent inputs and allows for efficient estimation from data.

Methodology
The authors propose a unified framework for the Generalized Functional ANOVA decomposition for continuous, bounded random variables. The methodology proceeds in three stages:

1. Theoretical Formulation (Closed-Form Basis):
   The paper establishes that the generalized functional ANOVA decomposition, defined as the solution to a constrained least-squares optimization problem in a Hilbert space, admits an explicit closed-form solution for continuous bounded features.

   • Assumption: The input vector $X$ is supported on a hyperrectangle $[-1, 1]^p$ with a density $f$ bounded away from zero and infinity.
   • Basis Construction: The authors construct a Riesz basis $\Xi$ for the space $L^2([−1, 1]^p, \mu_f)$ using normalized Legendre polynomials and an inverse likelihood weighting mechanism. Specifically, for a subset of variables $S$, the basis functions are defined as:
     $$\xi^{(m_S)}_S(x) := \frac{1}{\sqrt{2^{p-|S|}}} \cdot \frac{\prod_{j \in S} \tilde{P}_{m_j}(x_j)}{f_S(x_S)}$$
     where $\tilde{P}_m$ are normalized Legendre polynomials and $f_S$ is the marginal density of $X_S$.
   • Orthogonality: This construction ensures hierarchical orthogonality, meaning that for any strict subset $T \subset S$, the component $\nu_S$ is orthogonal to any function of $X_T$. This recovers the classical orthogonal decomposition in the independent case and connects naturally to Shapley values via Harsanyi dividends.

2. Estimation Algorithm:
   Since the basis is available in closed form, estimating the decomposition reduces to estimating the coefficients of the basis expansion via least-squares regression.

   • Truncation: To handle the infinite-dimensional nature of the problem, the authors employ a truncation set $I^K_d$ that limits the interaction order to $K$ and the polynomial degree to $d$. This leverages the "sparsity-of-effects" and "reluctance" principles.
   • Density Estimation: The marginal densities $f_S$ required for the basis are estimated from the data using truncated tensorized Legendre expansions.
   • Pipeline: The algorithm involves feature scaling (to $[-1, 1]$), density estimation, construction of the design matrix using the basis functions, and solving a linear system (using LARS for model selection and SVD for solving). The entire process is model-agnostic, requiring only input-output pairs.

3. Experimental Validation:
   The method is evaluated on synthetic analytical cases and six real-world datasets (Bike Sharing, California Housing, Census Income, etc.) using four model families: XGBoost, MLP, EBM, and NAM. It is compared against state-of-the-art methods (KernelSHAP, DeepSHAP, TreeSHAP, TreeHFD) and the native decompositions of interpretable models.

Key Contributions

1. Explicit Closed-Form Solution: The paper demonstrates that the generalized functional ANOVA decomposition for continuous bounded features admits an explicit solution, reducing the underlying non-parametric optimization to a least-squares regression problem.
2. Unified Framework: The formulation naturally recovers the classical independent case, orthogonal polynomial expansions, and the connection to Shapley values. It provides a rigorous mathematical grounding for additive explanations in the presence of dependent inputs.
3. Efficient Model-Agnostic Estimator: The authors propose a simple, polynomial-time algorithm to estimate the decomposition from a data sample without accessing the model's internal structure. The method exploits sparsity to remain tractable in practice.
4. Empirical Unification: Experiments show that existing explanation methods (SHAP variants) and interpretable models (GAMs, EBMs) closely approximate specific components of the functional ANOVA decomposition, suggesting the proposed framework unifies these disparate approaches.

Results

• Accuracy: The proposed estimator achieves high reconstruction accuracy ($R^2 \geq 0.85$) across all datasets and model families.
• Orthogonality: Despite using plug-in density estimates, the hierarchical orthogonality between components is faithfully preserved (low MaxCorr values).
• Efficiency: The method is computationally efficient, estimating decompositions for datasets with tens of thousands of samples in seconds (e.g., ~0.6s for 48k samples on Census Income).
• Comparison: Visual comparisons (Figs 1–4) indicate that the proposed method's main effects align closely with theoretical components in synthetic settings and with native effects from EBM/NAM, while offering a more rigorous decomposition than heuristic SHAP variants.

Significance and Claims
The paper claims to provide a unifying perspective on additive explanations. By grounding XAI methods in the rigorous mathematical object of the generalized functional ANOVA, the authors argue that:

• Additive explanations are not merely heuristic constructions but components of a well-defined mathematical object with structural properties.
• Many existing post-hoc methods and inherently interpretable models can be recast as approximations of specific components of this decomposition.
• The proposed approach offers a practical, efficient, and theoretically sound tool for decomposing black-box models, particularly in settings with dependent inputs where previous methods were limited or intractable.

The authors acknowledge limitations, including the assumption of bounded continuous inputs and the reliance on truncation for high-dimensional problems, noting that extending the framework to unbounded or mixed data types remains a challenge for future work.