Technical Summary: QuadraSHAP

Problem Statement

Shapley values are a foundational tool for explaining machine learning predictions, offering feature attributions grounded in cooperative game theory. However, exact computation is generally intractable, requiring the evaluation of exponentially many feature coalitions ($2^{d-1}$). While model-specific methods (e.g., TreeSHAP, RKHS-SHAP) exploit structural properties to achieve polynomial time, they often face a persistent trade-off between numerical stability and computational efficiency.

Specifically, methods relying on polynomial interpolation (such as Linear TreeSHAP) suffer from rapid numerical instability as the polynomial degree increases (governed by tree depth or feature count) due to the ill-conditioning of Vandermonde inverses. Conversely, algebraic recursion methods (e.g., for product-kernel models) offer stability but incur substantially higher arithmetic costs. This paper addresses the need for a method that is simultaneously exact (or near-exact), numerically stable, and computationally efficient for a broad class of models exhibiting multiplicative structure.

Methodology

The paper introduces QuadraSHAP, a method for computing Shapley values for product games—cooperative games where the coalition value factorizes as a product of per-player terms ($v(S) = \prod_{j \in S} u_j$). This structure naturally arises in tree-based models and kernel methods with product kernels.

1. Integral Representation

The core theoretical contribution is recasting the Shapley value of a product game from a weighted sum over $2^{d-1}$ subsets into an exact one-dimensional integral. By utilizing the Beta-function representation of Shapley weights, the authors derive:
$$\phi_i(v) = (u_i - 1) \int_0^1 \prod_{j \neq i} \left( (1-t) + t u_j \right) dt$$
This transformation eliminates the need for subset enumeration or interpolation-based coefficient recovery.

2. Gauss–Legendre Quadrature

The integral is evaluated using Gauss–Legendre quadrature.

• Exactness: If the number of quadrature nodes $m_q$ satisfies $m_q \ge \lceil d/2 \rceil$, the method recovers the exact Shapley value.
• Approximation: If $m_q < \lceil d/2 \rceil$, the method provides a near-exact approximation. The error is proven to decay geometrically with respect to $m_q$, specifically bounded by $O(\rho^{-2m_q})$ for a Bernstein ellipse parameter $\rho > 1$. Empirically, a few hundred nodes suffice for high-precision estimates even with thousands of features, far below the theoretical exactness threshold.

3. Numerically Stable and Efficient Implementation

To address practical computational challenges, the authors propose specific algorithmic optimizations:

• Log-Space Evaluation: To prevent overflow and underflow in high dimensions, products are evaluated in log-space with explicit sign tracking. The estimator is computed as:
  $$\hat{\phi}_i(v) = (u_i - 1) \sum_{q=1}^{m_q} \omega_q \cdot \text{sgn}(P_q)\text{sgn}(T_{q,i}) \exp\left( \log|P_q| - \log|T_{q,i}| \right)$$
  where $P_q$ is the full product of terms and $T_{q,i}$ is the term for feature $i$.
• Shared Computation: Instead of recomputing the "leave-one-out" product for each feature, the full product is computed once, and the specific factor for feature $i$ is divided out. This reduces complexity from $O(d^2 m_q)$ to $O(d m_q)$.
• Parallelization: The computation utilizes associative scan primitives (prefix sums) to compute the log-space reductions in $O(\log d)$ parallel time.

Key Contributions

1. Exact Integral Formulation: The paper establishes that Shapley values for product games admit an exact integral representation, enabling the use of Gauss–Legendre quadrature.
2. Stability and Efficiency: QuadraSHAP resolves the stability-efficiency trade-off. It avoids the numerical instability of interpolation-based methods (like Linear TreeSHAP) while being significantly faster than algebraic recursion methods for product-kernel models.
3. Theoretical Guarantees: The method provides provable exactness for $m_q \ge \lceil d/2 \rceil$ and geometric convergence bounds for approximate regimes.
4. Scalable Algorithms: The authors derive algorithms with $O(d m_q)$ sequential work and $O(\log d)$ parallel time, making the method scalable to high-dimensional problems (thousands of features).

Experimental Results

The authors evaluate QuadraSHAP against state-of-the-art baselines (TreeSHAP, Linear TreeSHAP, FastTreeSHAP, shapiq, and PKeX-Shapley) on synthetic and real-world datasets.

• Tree Ensembles:
  • Speed: QuadraSHAP is the fastest numerically stable method across all tested configurations. On large ensembles ($10^5$ leaves), it outperforms TreeSHAP by 3–5$\times$ and FastTreeSHAP by 2–2.7$\times$.
  • Stability: In deep tree regimes (depth up to 100), competitors like Linear TreeSHAP and TreeSHAP exhibit catastrophic violations of the Shapley efficiency axiom (errors reaching $10^{186}$ or higher). QuadraSHAP maintains precision at the level of floating-point limits ($\sim 10^{-13}$).
• Product-Kernel Methods:
  • Scalability: For Kernel Ridge Regression with product kernels, QuadraSHAP is an order of magnitude faster than the current exact baseline (PKeX-Shapley).
  • High Dimensions: While PKeX-Shapley times out (300s limit) for feature dimensions $d \ge 2000$, QuadraSHAP completes explanations in seconds (e.g., 7.6s for $d=5000$).
• Approximation Quality: Experiments confirm that approximation error decays geometrically with the number of nodes $m_q$. For $d=5000$, using only 400 nodes (well below the exactness threshold of 2500) yields near-machine-precision accuracy.

Significance and Claims

The paper claims that QuadraSHAP provides a unified, robust framework for feature attribution in models with multiplicative structures. By leveraging the integral representation and Gauss–Legendre quadrature, it achieves:

• Numerical Robustness: It remains stable in high-dimensional and deep-tree settings where interpolation-based methods fail.
• Computational Superiority: It matches or exceeds the speed of the fastest existing methods while maintaining exactness or controlled approximation.
• Generality: The formulation unifies tree ensembles and product-kernel methods under a single computational paradigm.

The authors position QuadraSHAP as the fastest numerically stable method for these specific classes of models, offering a practical solution for explainability in complex, high-dimensional machine learning systems.