PaperlayerView exact revision on arXiv

Source-linked AI summary

qshap: Fast Shapley Decomposition of $R^2$ for Gradient-Boosted Trees

Zhongli Jiang, Min Zhang, Dabao Zhang

arXiv:2608.24104v1stat.MLcs.LG

TL;DR

Existing attribution methods often explain individual tree-ensemble predictions, while many applications need feature contributions to global predictive performance. The paper introduces qshap, which exactly decomposes GBDT R2 through Shapley values and quadratic loss, with efficient implementations and an accelerated oblivious-tree backend. For sample sizes from 1,000 to 100,000, qshap runtime increased only from approximately 0.09 to 0.14 seconds in the reported comparison.

  • Problem

    Local attribution methods explain individual predictions, but they do not directly decompose global predictive performance measures such as R2.

  • Method

    Q-SHAP deterministically computes exact Shapley decompositions of R2 for fitted GBDTs by decomposing quadratic loss, using shared tree representations and specialized computation for oblivious trees.

  • Results

    For sample sizes from 1,000 to 100,000, qshap runtime increased only from approximately 0.09 seconds to 0.14 seconds in the reported comparison.

  • Takeaways & Limitations

    qshap provides feature- and observation-level R2 attribution for xgboost, lightgbm, and catboost through R and Python workflows with compiled C++ backends.

  • Takeaways & Limitations

    The current work focuses on decomposing R2 under squared-error loss, while extension to more general loss functions remains a foundation for future work.

Abstract

from arXiv · show

Numerous methods have been developed to quantify feature attributions in individual predictions for tree ensembles. However, many applications require global measures of feature contributions to overall model performance. Although local attribution scores can be aggregated to characterize feature importance, such summaries do not directly decompose measures of predictive performance, such as $R^2$. This article introduces qshap, available in both R and Python, which provides Shapley decomposition of $R^2$ values for gradient-boosted decision trees (GBDTs) to quantify feature-specific contributions to model performance. By decomposing the quadratic loss of individual observations, qshap provides flexible tools to explore the importance of individual features and observations. qshap currently supports widely used GBDT implementations, including xgboost, lightgbm, and catboost, through a unified tree representation and efficient C++ backends. Its modular design can accommodate other GBDT implementations built from binary decision trees. In addition, we introduce a specialized backend for oblivious trees that exploits their symmetric structure to substantially accelerate computation.

1. Introduction

GBDTs are widely used and predictive, but their growing complexity makes feature interpretation difficult. Existing local and global importance methods answer different questions, motivating Q-SHAP’s exact decomposition of model R2 for fitted GBDTs.

  • GBDTs, including XGBoost, LightGBM, and CatBoost, are widely used for tabular prediction because of their predictive performance and scalability.
  • Built-in tree summaries describe variable usage, permutation importance measures performance deterioration after perturbation, and SHAP provides feature attributions.
  • Local SHAP methods explain individual predictions, but applications also require global measures of how features contribute to overall model fit.
  • Shapley-based R2 decompositions allocate explained variance fairly, but linear-model approaches generally require exponentially many feature permutations and are limited to linear models.
  • SAGE, SPVIM, and Shapley effects provide other global importance formulations based on loss reduction, resampling, inference, or population-level variance.
  • Q-SHAP computes exact feature-specific Shapley values of explained variance for fitted GBDTs in polynomial time without sampling or model refitting.

2. Methodological foundations

Q-SHAP decomposes fitted GBDT model R2 into feature-specific Shapley contributions exactly, using linear and quadratic prediction terms evaluated through tree structure. qshap extends this framework to boosted ensembles and accelerates computation for oblivious trees.

  • Feature-specific decomposition: Feature-specific R2 contributions are formulated as Shapley allocations of explained variation, equivalently reductions in squared error.
  • Linear and quadratic Shapley values: Each contribution separates into an ordinary SHAP term for predictions and a quadratic SHAP term for squared predictions.
  • Linear and quadratic Shapley values: For decision trees, the quadratic term is computed exactly by aggregating interactions between pairs of leaves rather than enumerating feature coalitions.
  • Boosted-tree ensembles: Boosted-tree decomposition uses residuals and sequential stagewise updates, avoiding explicit expansion of interactions between every pair of trees.
  • Accelerated algorithm for oblivious trees: Oblivious-tree symmetry enables O(LD) computation, while grouping observations by leaf requires at most min(n, L) evaluations per tree.
  • Computational evaluation: With p = 100 and K = 100, qshap runtime increased from approximately 0.09 to 0.14 seconds as n grew from 1,000 to 100,000.

3. The R package qshap

qshap provides a two-step R workflow for computing and visualizing feature-specific R2 contributions from supported gradient-boosted tree models.

  • Workflow: qshap constructs a model-specific explainer with gazer() and computes global feature-specific R2 decomposition with rsq().The package supports xgboost, lightgbm, and catboost models through a common interface.
  • Supported models: The package supports xgboost, lightgbm, and catboost through backend-specific explainers sharing a common class structure.Backend dispatch preserves a unified user interface for rsq() and loss().
  • Implementation: gazer() parses fitted tree models into qshap_tree_explainer objects containing parsed trees and cached summaries for the C++ backend.The parsed representation supports subsequent numerical computations.
  • Outputs: rsq() returns feature-specific R2 values, feature names, total R2, feature and sample counts, and an optional local squared-loss decomposition.The default print method reports total R2 and the top contributing features.
  • Visualization: The package includes plot() for visual summaries of global importance scores and provides a direct CRAN installation route.The documented workflow uses plot(out) after computing rsq().

3.2. A case study with California housing data

The case study applies qshap to California housing data, fitting a deliberately simple xgboost model to predict median house value before decomposing its R2.

  • Data: 20,640 California census block-group observations and nine predictors are used to predict median house value.Predictors include geographic, demographic, housing, income, and ocean-proximity variables.
  • Preprocessing: The ocean_proximity categorical variable is converted to numeric codes before model fitting.The response is median_house_value and the remaining variables are predictors.
  • Data preparation: The data are downloaded from OpenML and converted into a data frame for analysis.The workflow extracts the response and predictor columns before fitting.
  • Model: The example fits xgboost with 50 boosting rounds and maximum tree depth two, retaining default values for other parameters.Random seed 42 is set for reproducibility.

3.5. Constructing the explainer

The explainer workflow extracts tree structure with gazer() and then uses rsq() to compute exact feature-specific R2 contributions for the fitted model.

  • Explainer construction: gazer() converts xgboost, lightgbm, and catboost models into a unified tree structure for subsequent Q-SHAP computations.This extraction isolates backend-specific model conventions from downstream calculations.
  • Tree representation: The parsed tree representation records child indices, split features and thresholds, depth, node samples, values, and node count.These fields describe the tree topology and stored quantities needed by the backend.
  • R2 decomposition: rsq() returns the empirical R2 of the fitted model together with the contribution assigned to each feature.The print method orders feature contributions from largest to smallest.
  • Result: 0.7646 total R^2 is reported for 9 features and 20,640 samples in the California housing example.The reported total summarizes the fitted model used for the decomposition.
  • Exactness: Q-SHAP computes the decomposition exactly from the fitted tree structure without Monte Carlo sampling, and feature contributions sum to empirical R2.The paper verifies the efficiency identity by comparing summed feature contributions with fitted-model R2.

3.7. Local decomposition of the squared loss

qshap extends the global R2 decomposition with observation-level squared-loss contributions, allowing feature effects to be examined for individual observations.

  • Local decomposition: qshap can return observation-level squared-loss contributions from which global feature-specific R2 values are obtained.The loss() function provides the local decomposition directly.
  • R2 scaling: local_rsq standardizes the loss decomposition on the R2 scale, with each feature column summing to its corresponding global feature-specific R2.This connects local observation-level values to the global decomposition.
  • Interpretation: Positive local values indicate that a feature contributes positively to model fit for an observation, while negative values indicate the opposite direction.The sign is interpreted observation by observation.
  • Example: The California housing output displays local contributions for all nine features across individual observations.The reported rows include geographic, housing, demographic, income, and ocean-proximity variables.

3.8. Parallel computing

qshap exploits additivity across observations to process data subsets independently and combine their results into global feature-specific estimates. The R implementation supports serial or multicore execution through configurable worker counts.

  • Parallel computing: qshap partitions observations into disjoint subsets, processes them in parallel, and aggregates results into global feature-specific estimates.The strategy follows from the decomposition being additive across observations.
  • Parallel computing: The R implementation uses PSOCK clusters through the parallel package for multicore execution.This approach is compatible with CRAN environments.
  • Parallel computing: ncore = 1 selects serial execution, whereas ncore = -1 uses all available cores.The ncore argument controls the number of workers.
  • Parallel computing: Parallel computing is most beneficial when datasets, ensembles, or tree depths are large enough to outweigh worker-startup overhead.The passage explicitly ties the benefit to computational workload exceeding parallelization overhead.

3.9. Visualization

qshap integrates global and observation-level visualization through a unified plotting interface. Its plots rank feature contributions, show cumulative or elbow patterns, and inspect extreme observation-level contributions.

  • Visualization: qshap’s plot() method supports bar plots, elbow plots, cumulative contribution plots, and heatmaps for global and local feature-specific R2.The default visualization is a bar plot, while type = "gcorr" produces a generalized-correlation bar plot.
  • Feature displays: Median income has the largest California housing contribution, followed by ocean proximity, longitude, and latitude.The generalized correlation coefficient plot preserves this feature ranking on a correlation-like scale.
  • Ranked contributions: Elbow plots highlight contribution changes for identifying leading features, whereas cumulative plots show accumulation toward the fitted model’s total R2.These summaries operate on ranked feature contributions.
  • Observation-level contributions: The heatmap displays selected observations with rows ordered by signed row totals and defaults to the most extreme positive and negative contributions.The n_show argument controls how many observations are displayed.

4. The Python package qshap

The Python package follows the R workflow through an interface to the same C++ backend, converting fitted models before computing feature-specific R2 values. On identical data and model parameters, the two implementations return consistent values at the reported precision.

  • Python workflow: The Python interface passes a fitted model to gazer(), converts it to a unified internal format, and supplies it to rsq().The interface accepts and returns NumPy-based numerical objects and provides Matplotlib visualization functions.
  • Supported models: qshap supports decision-tree and gradient-boosting estimators from scikit-learn, xgboost, lightgbm, and catboost.The package is available through GitHub and PyPI.
  • Case study: The Python section demonstrates the workflow with xgboost on the California housing data using gazer(), rsq(), and visualization functions.The demonstration computes local results and exposes both R2 and loss outputs.
  • Cross-language consistency: The R and Python implementations return consistent feature-specific R2 values at the reported precision when using the same model parameters and data.This comparison uses the model fitted under identical conditions.

5. Internal design of the R package

The R package separates model-specific parsing from common Q-SHAP computation through unified tree objects and dispatch layers. Cached summaries and compiled numerical routines support feature-specific R2 and local loss calculations across supported tree models.

  • Class design: A simple_tree stores topology, split information, depth, node weights or counts, node values, and missing-value routing when required.Leaf nodes use child index −1.
  • Model support and dispatch: The qshap_tree_explainer stores the model, parsed trees, model metadata, cached summaries, and precomputed arrays used by the C++ backend.It connects a fitted model to Q-SHAP computation.
  • Class design: qshap_result stores feature-specific R2 values, feature names, total R2, sample size, feature count, and optionally local loss contributions.Its methods support printing, summarizing, plotting, and data-frame conversion.
  • Model support and dispatch: gazer() dispatches on model class, formats native models into simple_tree objects, and converts them into tree_summary objects.This separation keeps model-library conventions outside the numerical backends.
  • Numerical backend: The numerical kernels combine ordinary TreeSHAP term T1, Q-SHAP quadratic term T2, and stagewise residuals to obtain local loss and feature-specific R2 values.Compiled C++ routines use cached tree summaries for these calculations.
  • Model-specific formatting: The formatter preserves library-specific prediction information, including topology, thresholds, missing-value routing, node weights, initial predictions, and output scaling.Separate formatters are described for xgboost, lightgbm, and catboost, including specialized handling for oblivious trees.
  • Extensibility: Extending qshap to a new binary-tree model requires fitted-tree recovery, ordinary per-tree TreeSHAP quantities, a gazer() method, and formatter and dispatch updates.The existing general backend can be reused when the required common representation is available.

6. Conclusion

qshap computes feature-specific R2 values for boosted tree models in R and Python, combining exact Shapley decomposition with workflows for observation-level and global contributions. It supports major GBDT implementations and accelerates computation for oblivious trees, while focusing on well-defined R2 under squared-error loss.

  • Software and contribution: qshap computes feature-specific R2 values for boosted tree models in both R and Python using an exact Shapley-value decomposition.The workflow includes constructing explainers, extracting observation-level loss contributions, calculating global contributions, and visualizing feature importance.
  • Software and contribution: The package supports xgboost, lightgbm, and catboost through a shared tree representation and efficient compiled C++ backends.For arbitrary binary trees, it uses the general-tree Q-SHAP algorithm.
  • Software and contribution: A specialized oblivious-tree backend exploits symmetric structure, groups observations by leaf, and reuses computations to substantially reduce computation time.CatBoost is the main example of an implementation using this backend.
  • Scope: The current work decomposes a well-defined R2 under squared-error loss and provides a foundation for extending the framework to more general loss functions.The stated scope is the decomposition of R2 under squared-error loss.
Loading 2608.24104v1…