CS Paper Radar

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

Zhongli Jiang, Min Zhang, Dabao Zhang

cs.LG stat.ML ·submitted 2026-08-25 06:06 UTC · v1

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Where Tree Ensembles Decide: Structural Local Explanation with Decision Predicate Graphs

cs.LG ·2026-11-13 ·Sylvio Barbon Junior, Luca Longo
hot direction similarity 0.62
Abstract · Code, data and results: https://doi.org/10.5281/zenodo.24201497. Supplementary material attached as an ancillary file

Tree ensembles are among the most accurate models for tabular data, yet the computation behind a single prediction is spread over hundreds of decision rules. Feature attributions and counterfactuals explain such predictions through the influence of features or a change of the input, leaving open which of the thresholds applied by the trees a prediction responds to, while structural explanations compress these rules and lose the trees behind them. To address this gap, we propose a local Decision Predicate Graph (local DPG), which gathers the rules executed for a sample into a verifiable record of the computation, with a class support that reproduces every explained prediction. From these rules we select the critical predicate, the executed predicate whose crossing is estimated to move the model most strongly toward a chosen class, which offers the user a concrete threshold and the trees that share it, without an external explainer. Across 16 datasets and four ensemble families, it separates differently predicted neighbours better than random and nearest-threshold predicates. A single crossing recovers the true class in 46-69% of wrong predictions, against 29-50% when the same rule is applied to the feature ranked first by TreeSHAP, a measure close to the selection criterion, and on planted faults it finds the faulty threshold in 46-71% of the resulting errors, against 6-21% at random. Although training-free edits of these predicates did not reduce the error on unseen data, the critical predicate complements attributions and counterfactuals by naming where a prediction can be changed.

0.32

FQTree: Fine-grained Quantization and Hardware Generation of Boosted Decision Trees

cs.AR cs.LG ·2026-08-12 ·Zhiqiang Que, Chang Sun, Haiyang Wang, Dinesh Pamunuwa, Roshan Weerasekera +4 more
publishedcode/data similarity 0.62
Abstract · accepted by ASAP'26. Code available at https://github.com/ecs-bristol/FQTree

Boosted decision trees (BDTs) are widely used in latency-critical applications, but efficient hardware deployment remains challenging. Existing designs often rely on uniform or manually tuned fixed-point formats, which can introduce unnecessary hardware cost or accuracy loss. This work presents the FQTree algorithm{https://github.com/ecs-bristol/FQTree} for fine-grained quantization-aware training of BDTs, together with the QXGB framework for automatic hardware generation. FQTree introduces a hardware-oriented leaf-value quantization scheme that uses a global quantization step together with a tree-wise shift, enabling compact non-negative integer leaf representations, controlled clipping/pruning, and bias folding to reduce datapath cost. This work further applies this quantization during boosting so that later trees adapt to the errors of the already-quantized ensemble, and then lowers the trained model into low-latency hardware implementations through a compiler-based flow. Results on JSC, MNIST, and NID show that our method reduces LUT usage by 26-57\% compared with the state-of-the-art FPGA-based BDT designs while matching or improving accuracy.

0.74

CRAFT-GBM: Selecting Best Features for Gradient-Boosted Machine Learning

cs.LG math.ST ·2026-11-09 ·Basil Kuok, Yi Zhou, Yao Xuan, Shuping Li, Ke-Wei Huang
similarity 0.60
Abstract

Feature subsampling is used to accelerate gradient-boosted trees, yet standard approaches fix the feature count in advance and largely ignore the split-gain evidence accumulated during training. We introduce CRAFT-GBM (Confidence-Ranked Adaptive Feature Tracking), a native LightGBM extension that uses this evidence to adapt which---and, by default, how many---features are searched each boosting round. CRAFT-GBM transforms root-split gains into bounded observations and constructs joint time-uniform bounds valid under adaptive, non-stationary training histories. In its default endogenous mode, after initialization, CRAFT-GBM retains exactly the features that cannot yet be ruled out as best, letting the selected feature-set size $K_t$ emerge from training history rather than a pre-specified fraction. With probability at least $1-δ$, every feature with the largest expected gain is retained jointly across all rounds after initialization. When a feature fraction $f$ is specified instead, CRAFT-GBM ranks features by their interval point estimates and provides an approximate top-$K$ guarantee for feature budget $K_f$. We implement CRAFT-GBM within LightGBM while preserving its native feature-bundling representation, and evaluate it across 14 public and synthetic dataset families and four noise-augmented settings. In the fully endogenous setting, CRAFT-GBM reduces per-fit training time by 39.74\% with 1.04\% lower test loss in the geometric mean across all 18 RQ1 experiments. Under pre-specified feature fraction $f$, Exogenous CRAFT-GBM also yields aggregate training-time reductions up to 13.52 percentage points larger than random feature subsampling, with no increase in aggregate test loss relative to full-feature LightGBM. Accumulated training evidence can thus support adaptive feature search with statistical guarantees while retaining the practical advantages of native gradient boosting.

0.14

TreeWalker: Partial Evaluation for Grouped Tree-Ensemble Inference

cs.LG cs.PFcs.PL ·2026-10-02 ·Durmus Karatay, Richard Newman
top venuebenchmarktheorycode/data similarity 0.60
Abstract · 23 pages, 9 figures, 11 tables. Accepted at NeurIPS 2026. Code and data: https://github.com/Shopify/treewalker/tree/neurips2026-final

Many prediction tasks evaluate a trained tree ensemble on groups of rows that share feature values: discrete-time survival models expand each patient into $G$ time steps, click-through-rate models score every item in a search session, and scenario analyses vary a few inputs while holding the rest fixed. Standard inference treats each row independently and ignores this input-side correlation. We present TreeWalker, which instantiates partial evaluation for grouped tree-ensemble inference: constant features are static, varying features dynamic. TreeWalker walks each tree once per group, partitions a row bitmask at varying splits, and skips empty subtrees via an unsplit shortcut. It reads standard LightGBM and XGBoost models; training is unchanged. We prove a structural work decomposition: per-tree work splits into the constant-projected subtree size $|T_c|$, $G$ leaf writes, and a predicate-mask provisioning cost $Q$. For the trace evaluator, per-row work approaches $(d_v+1)/(d+1)$ as $G \to \infty$, giving asymptotic speedup $1/(1-\barρ_G)$. On Intel, TreeWalker is ${\sim}3\times$ faster than a row-independent traversal at the reference model size ($T{=}500$, $L{=}8$; $G{=}16$ for SUPPORT/FLCHAIN and empirical groups for Expedia) and $7.7$--$9.1\times$ faster at $G{=}128$ on the survival datasets; on Arm, $2.5$--$2.9\times$ and $5.5$--$6.0\times$. On a scenario-analysis benchmark it is faster in all $16$ configurations on both machines. For f64 models, outputs match treelite GTIL up to tree-ordering roundoff; for f32 models, TreeWalker's f64 leaf accumulation is closer than native f32 to an exactly rounded reference on every audited row.

0.53

Sparse Oblique Rule Boosting for Simpler Additive Rule Ensembles

cs.LG ·2026-09-06 ·Shahrzad Behzadimanesh, Pierre Le Bodic, Geoffrey I. Webb, Mario Boley
published similarity 0.59
Abstract · Accepted for publication in Journal of Data Mining and Knowledge Discovery. The Version of Record is forthcoming

Small additive ensembles of symbolic rules offer interpretable prediction models. Traditionally, these ensembles use rule conditions based on conjunctions of simple threshold propositions $x \geq t$ on a single input variable $x$ and threshold $t$, resulting geometrically in axis-parallel polytopes as decision regions. While this form ensures a high degree of interpretability for individual rules and can be learned efficiently using the gradient boosting approach, it relies on having access to a curated set of expressive input features so that a small ensemble of axis-parallel regions can describe the target variable well. Absent such features, reaching sufficient accuracy requires increasing the number and complexity of individual rules, which diminishes the interpretability of the model. Here, we extend classical rule ensembles by introducing logical propositions with learnable sparse linear transformations of input variables, i.e., propositions of the form $\mathbf{x}^T\mathbf{w} \geq t$, where $\mathbf{w}$ is a learnable sparse weight vector, enabling decision regions as general polyhedrons with oblique faces. We propose a learning method using gradient boosting based on a weighted logistic regression. Empirical results across 14 regression and classification tasks demonstrate that the proposed method achieves lower model complexity than competitive baselines while maintaining similar or better predictive accuracy. Hence, the approach provides a favorable trade-off between interpretability and accuracy and reduces the reliance on manual feature engineering.

0.35

RelShap: Relationally Consistent Shapley Explanations

cs.LG ·2026-08-11 ·Seungeun Lee, Joao Fonseca, Julia Stoyanovich
code/data similarity 0.58
Abstract

Machine learning pipelines commonly flatten relational data into single-table representations, discarding structural constraints. Widely used Shapley value-based feature attributions then rely on feature independence, evaluating the model on combinations that could never arise in the underlying data, producing misleading explanations. We propose RelShap, a framework that incorporates relational constraints and data provenance into Shapley value computation, restricting both background data and coalition evaluation to relationally valid configurations. The framework is estimator-agnostic and composes with Kernel SHAP, Monte Carlo, and Leverage SHAP without altering their sampling or weighting properties. Functional dependencies further induce equivalence classes over feature coalitions, which RelShap exploits to reduce runtime without changing Shapley values; we provide a combinatorial characterization of the expected speedup. Experiments across multiple datasets, models, and estimators show that RelShap produces explanations that are more faithful to the data-generating process, correctly identifying the dominant feature in controlled settings where existing methods, including Conditional SHAP and ManifoldShap, do not. Our code is available at: https://github.com/duneag2/relshap.

0.24

When Feature Representation Changes Local Explanations: A Controlled Comparison of SHAP and LIME under Numerical Discretization

cs.LG ·2026-11-16 ·Parv Patel
code/data similarity 0.58
Abstract · 20 pages, 7 figures, 6 tables. Code: https://github.com/Parvptl/shap-lime-representation-sensitivity

Local feature attributions are computed over a feature representation chosen by an upstream data-engineering step, yet they are read as statements about the underlying quantity. We ask how discretizing one continuous feature changes local KernelSHAP and LIME explanations when the classifier is held fixed, and whether the two explainers respond differently. A random forest is trained on UCI Adult and frozen; age is collapsed onto equi-width or quantile bin representatives (k in {3,5,10}) before the model receives it, and the same 120 held-out instances are explained in every condition across multiple seeds. We show analytically and numerically that for KernelSHAP this is exactly equivalent to explaining the unchanged model at the quantized instance against a quantized background, so the comparison is between two effective inputs rather than a pure explainer effect; for LIME no such equivalence holds. Each attribution change is compared with a seed-noise floor from re-running the explainer on the unchanged condition. KernelSHAP's age attribution exceeds its noise floor in all 6 pre-specified conditions (median ratios 2.4-59, all significant after Holm correction); on the raw scale LIME's exceeds its floor in only 2 of 6 and in the rest is no larger than its own run-to-run variation. SHAP's normalized change exceeds LIME's in every condition (rank-biserial 0.81-1.00), while LIME is 2.5-4.6x less consistent across repeats. Predicted classes change for only 0.8-5.8% of instances and held-out ROC-AUC never falls below 0.9097, yet 45-94% of instances show a large SHAP attribution change with no class flip. Feature-importance rankings barely move (median Spearman >= 0.979, top-3 overlap 1.00). The representation change and the change in effective input cannot be separated within a frozen-model design.

0.42

Interval-valued SHAP in Tree-Based Models

cs.LG ·2026-10-08 ·Chenrui Zhu, Vu-Linh Nguyen, Marie-Hélène Masson, Sébastien Destercke
similarity 0.58
Abstract

Shapley values are among the most popular feature-attribution explanations. Efficient approaches for computing/estimating Shapley values for tree-based models, which are state-of-the-art for tabular data sets, have been developed. However, it is known that Shapley values can be (highly) unrobust due to small and realistic changes. In this paper, we propose an imprecise Dirichlet model (IDM) based method to analyze the robustness of Shapley values in decision trees and random forests. Technically, it is done by quantifying and analyzing the interval-valued Shapley values when a few unannotated instances are randomly introduced to the leaves of the trees. The interval-valued Shapley values can be defined following common principles in handling incomplete data: the pessimistic and averaging principles. We derive various theoretical results that lead to efficient computation of the interval-valued Shapley values. We also show that the proposed method can be straightforwardly generalized to the case of Banzhaf values. We then present various case studies and experiments to illustrate the behaviour of the proposed interval-valued Shapley values and their applications in debiasing uninformative features.

0.25