Interventional SHAP Values and Interaction Values for Piecewise Linear Regression Trees

Artjom Zern, Klaus Broelemann, Gjergji KasneciAAAI 2023 · DOI

Introduction

SHAP (Shapley Additive exPlanations) has become a cornerstone for interpreting machine learning models. However, its exact computation is often computationally prohibitive, scaling exponentially with the number of features. While the TreeSHAP algorithm efficiently handles standard decision trees with constant leaf values, it is not directly applicable to Piecewise Linear Regression Trees (PLRTs). PLRTs, which utilize linear regression models at each leaf, are increasingly popular in high-performance libraries like LightGBM but present a significant challenge for efficient explanation.

Furthermore, interventional SHAP—which evaluates a model's internal logic by comparing predictions against a background dataset—typically requires iterating over the entire background set for every explanation. This creates a massive bottleneck for large-scale applications. This paper introduces a highly efficient algorithm to compute exact interventional SHAP and interaction values for PLRTs, achieving significant speedups over traditional methods.

Methodology

The proposed solution leverages a two-pronged approach involving mathematical decomposition and algorithmic optimization.

Interval Decomposition and Path-Based Logic

The authors represent the SHAP contribution function as a sum of indicator functions over intervals of feature subsets. They derive a closed-form solution for the SHAP values of these indicator functions, allowing for an analytical "walk" through the tree to update SHAP values. This path-based logic recognizes that for tree-based models, the contribution of a background point is determined solely by its decision path.

Visualization of tree paths and feature subset intervals used for SHAP computation.

Background Data Aggregation

To decouple runtime from the size of the background dataset $D$, the authors pre-process the background data into a specialized structure that stores essential statistics (counts and means) of how background data flows through the tree. By combining interval mathematics with these pre-computed statistics, the "Aggregated" explainer (Algorithm 3) only needs to traverse the tree structure once per explanation, regardless of the background dataset size.

Experimental Evaluation

The approach was evaluated on seven regression datasets from OpenML, ranging from computer performance (cpu_act) to the Million Song Dataset (year), which contains over 500,000 instances.

Key Results

The empirical results demonstrate that the proposed algorithms offer both superior speed and accuracy compared to existing baselines.

  • Computational Efficiency: On the "year" dataset, the Aggregated algorithm was approximately 10x faster than the basic interventional approach while utilizing the full background dataset. For piecewise linear models, the speedup is even more pronounced compared to standard interventional TreeSHAP implementations.
  • Accuracy vs. Sampling: Traditional methods often rely on subsampling (e.g., 100 or 1,000 background points) to reduce computation time. However, this paper shows that such approximations often miss critical nuances. The proposed aggregation method achieves significantly higher $R^2$ scores by enabling exact computation with the full background set in less time than it takes to process a small sample.
  • Interaction Values: The framework extends to SHAP Interaction Values with a complexity of $O(3^d d n)$, making it feasible for deeper trees where previous methods were too slow.
Runtime comparison (in seconds) across various datasets and SHAP computation methods for piecewise constant and piecewise linear trees.

Conclusion and Future Work

This work provides a robust framework for explaining PLRTs efficiently. By shifting from brute-force estimation to analytical computation via data aggregation, it removes the "speed limit" for interventional SHAP in tree-based models.

Future research directions include extending this logic to observational SHAP, which remains NP-hard due to feature dependencies. Additionally, while the memory overhead for background data aggregation is currently manageable, optimizing memory usage for extremely deep trees or massive ensembles remains an area for improvement. Finally, adapting the interval decomposition logic to non-tree architectures like neural networks presents an intriguing challenge.

Summary updated

BibTeX
@inproceedings{zern2023interventional,
  author = {Artjom Zern and Klaus Broelemann and Gjergji Kasneci},
  title = {{Interventional SHAP Values and Interaction Values for Piecewise Linear Regression Trees}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i9.26322},
}
Figure