PaperlayerView exact revision on arXiv

Source-linked AI summary

Interval-valued SHAP in Tree-Based Models

Chenrui Zhu, Vu-Linh Nguyen, Marie-Hélène Masson, Sébastien Destercke

arXiv:2610.11953v1cs.LG

TL;DR

Small realistic perturbations can substantially change SHAP values, motivating robustness analysis for tree-based models. The paper uses an IDM-based approach to compute interval-valued attributions under leaf uncertainty, and reports case studies and experiments on their behavior, bootstrap variability, and uninformative-feature importance.

  • Problem

    SHAP values can shift substantially under small realistic perturbations, and existing imprecise-SHAP approaches leave unclear when their intervals cover tree-based-model SHAP values.

    Source: §I · p. 1

  • Method

    An IDM-based method introduces a few unannotated instances into tree leaves and computes interval-valued SHAP using pessimistic and averaging principles.

    Source: §I · pp. 1–2

  • Results

    The authors report efficient computation of the intervals and present case studies and experiments relating them to bootstrap-retraining variability and uninformative-feature importance.

    Source: §I · p. 2, §V · p. 10

  • Takeaways & Limitations

    The interval-valued attributions provide a way to analyze SHAP robustness in decision trees and random forests and can help estimate the importance of uninformative features.

    Source: §V · p. 10

    A detailed study of margin-based ranking stability for single trees and ensembles is left for future work.

    Source: D. Discussion · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

The introduction motivates robust SHAP analysis for tree models and proposes IDM-based intervals for changes in leaf outputs. The background frames trees as predictors and feature attributions as cooperative-game contributions under a chosen missing-feature semantics.

I. INTRODUCTION

  • Small realistic perturbations can substantially shift SHAP values, while tree-based models also change with small training-data perturbations; stable tree structure can matter for interpretability.The paper notes that interpreting tree structures can be costly and that model stability is especially relevant when those structures support decision-making or rule extraction.Source: §I · p. 1
  • The proposed IDM method assesses attribution robustness by adding a few unannotated instances to leaves and deriving interval-valued SHAP under pessimistic and averaging principles.The introduction says theoretical results support efficient computation and that the approach extends to Banzhaf values and random forests.Source: §I · pp. 1–2

A. Decision-tree models

  • A decision tree routes an input through feature-threshold tests to a leaf, whose output supplies the prediction; this paper keeps the tree structure fixed while varying leaf outputs.The considered leaf values include quantities such as target-class probability, with the paper focusing on that supervised-learning setting.Source: A. Decision-tree models · p. 2

B. Feature attribution as a coalitional game

  • Feature-attribution methods such as SHAP model features as a cooperative game, assigning each feature a contribution to the prediction for the instance being explained.The interventional value function fixes features in a coalition to the explained instance and averages over the remaining features using a background distribution.Source: B. Feature attribution as a… · p. 2
  • The results also cover other missing-feature semantics when the coalition value is an expectation under a distribution independent of the leaf-output vector.The text gives conditional expectations and path-dependent semantics as alternatives to the interventional semantics.Source: B. Feature attribution as a… · p. 2

C. Shapley attributions

The paper recalls Shapley attribution and contrasts it with the raw Banzhaf value. It then shows that, for fixed tree conditions, coalition values and attributions are linear in the leaf outputs.

C. Shapley attributions

  • The Shapley value is characterized by axioms including efficiency, symmetry, linearity, and dummy.The standard convention defines an intercept so the efficiency identity relates the sum of feature attributions to the difference between the full-coalition and empty-coalition values.Source: C. Shapley attributions · p. 2
  • The raw Banzhaf value averages marginal contributions uniformly, generally lacks the Shapley efficiency identity, and often produces similar feature rankings in practice.The text notes its attractive computational properties for tree models.Source: C. Shapley attributions · p. 2

D. Leaf-linear representation of the game and attributions

  • For a fixed tree, instance, background distribution, and missing-feature semantics, each coalition value is linear in the leaf-output vector.The coalition value is the expected tree prediction with coalition features fixed to the explained instance and the other features integrated over the background distribution.Source: D. Leaf-linear representation of the… · p. 3
  • The reach probabilities over leaves do not depend on leaf outputs, so the paper’s uncertainty analysis varies leaf outputs rather than re-estimating routing probabilities.This linear representation makes each coalition value a weighted sum of leaf outputs, with reach probabilities supplying the weights.Source: D. Leaf-linear representation of the… · p. 3

2) Linearity of the attribution value ϕ(w):

The paper represents each feature’s SHAP value as a linear form in the leaf-value vector. The coefficient vector depends on the fixed tree and attribution setup, enabling the later interval analysis and extensions.

2) Linearity of the attribution value ϕ(w):

  • For each feature, the SHAP value is a linear form in the leaf-value vector, with a coefficient for each leaf.The coefficient vector depends on the tree structure, explained instance, background distribution, and missing-feature semantics, but not on the leaf values.Source: 2) Linearity of the attribution value… · p. 3
  • Because the coefficients are fixed once the tree and attribution setup are fixed, SHAP variation under this analysis reduces to variation in leaf outputs.The paper identifies this leaf-linear representation as the key ingredient for its interval-valued robustness analysis.Source: 2) Linearity of the attribution value… · p. 3
  • The same results apply to Banzhaf indices by replacing the Shapley coefficient vector with the Banzhaf coefficient vector.The paper then focuses on SHAP.Source: 2) Linearity of the attribution value… · p. 3

III. INTERVAL-VALUED FEATURE ATTRIBUTION UNDER LEAF UNCERTAINTY

The section models leaf-output uncertainty by adding unannotated virtual samples, then bounds feature attributions under alternative assumptions about how those samples reach the leaves. For unknown allocation, the pessimistic bounds can be computed efficiently using a greedy allocation procedure.

A. From virtual samples to leaf uncertainty

  • A total budget s of unannotated instances is allocated across leaves, with each leaf’s target-class output bounded by treating all added instances as absent from or belonging to that class.This gives s a direct interpretation as the number of imprecise observations the explanation must tolerate, without prespecifying their locations.Source: A. From virtual samples to leaf… · p. 4

B. Interval-valued attributions

1) unknown allocation (pessimistic):

  • The pessimistic principle enlarges each endpoint using its most adverse allocation, and the lower- and upper-bound allocations may differ and depend on the feature.The lower-bound solution is derived first, with an analogous solution for the upper bound.Source: 1) unknown allocation (pessimistic) · pp. 4–5
  • Under unknown allocation, the pessimistic endpoint optimization is separable and concave, so a greedy procedure assigns each virtual sample to the leaf with the largest marginal gain.The direct implementation runs in O(s|L|) time.Source: 1) unknown allocation (pessimistic) · p. 5

2) Stochastic allocation (averaging):

The averaging principle replaces worst-case optimization with an expectation over a specified distribution of virtual-sample allocations. Under a multinomial placement model, the resulting expected interval is no wider than the corresponding worst-case envelope.

2) Stochastic allocation (averaging):

  • With stochastic allocation, attribution endpoints are averaged over a specified allocation distribution; the paper considers M ∼ Multinomial(s, π), giving each leaf marginal Mℓ ∼ Binomial(s, πℓ).The placement distribution π can represent, for example, uniform placement or placement proportional to empirical leaf mass.Source: 2) Stochastic allocation (averaging) · p. 5
  • Because the correction terms are nonnegative, the expected interval is no wider than the worst-case envelope, and it describes uncertainty under the chosen placement law π.The worst-case endpoints optimize over all allocations, while the averaging endpoints average over allocations sampled from π.Source: 2) Stochastic allocation (averaging) · p. 5

C. Extensions to tree-ensemble

The leaf-linear attribution representation extends to tree ensembles, allowing interval-valued analysis either through an exact but potentially costly tree conversion or through an approximation. The approximate pessimistic method can produce an outer approximation, whereas the approximate averaging method need not enclose the exact result.

C. Extensions to tree-ensemble

  • By linearity in model output, ensemble attributions remain linear in the concatenated collection of tree leaf outputs under fixed tree structures.An ensemble can be interpreted as a tree whose leaves are non-empty intersections of leaves from its component trees, but constructing it can be costly.Source: C. Extensions to tree-ensemble · p. 6
  • The approximate pessimistic ensemble procedure allocates samples over possibly empty leaves and selects high-marginal-gain leaves tree by tree.Because gains can come from empty leaves, its intervals are an outer approximation of those obtained by converting the ensemble to a tree and applying the pessimistic principle.Source: C. Extensions to tree-ensemble · p. 6
  • An approximate averaging procedure can average corrections across ensemble leaves, equivalently averaging the corrections of the individual trees’ leaves, but its intervals are not necessarily exact or an outer approximation.Source: C. Extensions to tree-ensemble · p. 6

D. Discussion

For ranking stability, the paper compares feature pairs under the same leaf-output vector using their attribution margin, rather than comparing separate attribution intervals. Adjacent margins can certify a full ranking or a coarser tiered ranking, while detailed margin-based certification is left for future work.

D. Discussion

  • Pairwise ranking stability is assessed using γij(w) = ϕi(w) − ϕj(w) under the same leaf-output vector, since separate feature intervals may have endpoints attained under different vectors.Source: D. Discussion · p. 6
  • If every adjacent lower margin in a nominal ranking is positive, the full ranking is robust; ambiguous adjacent pairs can instead yield a certified tiered ranking.For example, features 1 and 2 may remain jointly above feature 3 even when their relative order is uncertain.Source: D. Discussion · p. 6
  • As the uncertainty budget s increases, pairwise ranking certificates become harder to maintain, and the paper leaves detailed margin-based ranking certification for future work.In the experiments, it uses the simpler sufficient criterion ϕi > ϕj to certify that feature i ranks above feature j.Source: D. Discussion · pp. 6–7

IV. EXPERIMENTS

The experiments evaluate interval-valued attributions from a practitioner’s perspective, asking how robust they are locally and across test sets. They also examine agreement with bootstrap variability, certainty regions, and debiasing uninformative features.

IV. EXPERIMENTS

  • The evaluation takes a practitioner’s perspective, aiming to show how to interpret and robustify the framework and provide empirical evidence for potential applications.The stated aim is not limited to demonstrating the method’s operation.Source: §IV · p. 7
  • The experiments ask whether nominally important features remain robust, interval-valued attributions agree with bootstrap variability, uncertainty differs by prediction certainty, and pessimism reduces uninformative-feature importance.The four questions are evaluated for individual predictions, with instance-level quantities also aggregated over the test set.Source: §IV · p. 7
  • The analysis starts with individual predictions and then aggregates the same instance-level quantities over the test set, preserving the method’s local focus.The aggregate summaries provide a dataset-level view of attribution robustness.Source: §IV · p. 7

A. Experimental protocol

The experimental protocol uses four public tabular binary-classification datasets and examines interval-valued SHAP through both a decision-tree case study and broader tree-based experiments. The Diabetes example illustrates how interval overlap and separation qualify feature-importance rankings.

A. Experimental protocol

  • The protocol uses Diabetes, Breast Cancer, Ionosphere, and Mortality; the first three datasets come from OpenML, while Mortality is the case study from [3].The paper identifies Table III as the dataset summary.Source: A. Experimental protocol · p. 7, Table III · p. 7
  • Each dataset uses 5-fold cross-validation, with hyperparameters selected by nested 3-fold cross-validation using balanced accuracy; random forests contain 100 trees.The minimum samples per leaf is tuned over 5, 10, and 20 for both model types.Source: A. Experimental protocol · p. 7

B. Case study

  • The case study interprets interval rankings through dominance, incomparability, and robust top-k groups, distinguishing clear comparisons from overlapping intervals.A robust top-k group can dominate features outside it even when its members’ internal order is ambiguous.Source: B. Case study · p. 7
  • The Diabetes case study uses a depth-6 decision tree with test accuracy 0.76 and reports two representative patients’ nominal SHAP values and magnitude-based intervals at s=2.The intervals use both the pessimistic and averaging principles.Source: B. Case study · p. 7
  • For patient 1, plasma glucose and BMI remain separated under both principles, but their small gap leaves secondary-driver rankings potentially fragile.The averaging principle gives narrower intervals while preserving the same ranking conclusion.Source: B. Case study · pp. 7–8

C. Bootstrap-based validation of interval-valued attributions

The section examines whether pessimistic attribution intervals track bootstrap variability, how attribution uncertainty relates to prediction certainty in random forests, and whether intervals can reduce apparent importance assigned to uninformative features.

C. Bootstrap-based validation of interval-valued attributions

  • The bootstrap validation asks whether larger pessimistic intervals track greater bootstrap-retraining variability, using 100 bagging-style bootstrap replicates per fold.The interval length is the proposed attribution interval length.Source: C. Bootstrap-based validation of… · p. 8

D. Attribution in certain and ambiguous regions

  • For random forests, smaller class-probability margins are negatively associated with average attribution-interval length, so more ambiguous predictions tend to have wider intervals.The margin is used as a confidence proxy; the analysis does not apply this proxy to single trees because their confidence scores are too coarse.Source: D. Attribution in certain and… · pp. 8–9

E. Application: debiasing uninformative features

  • The synthetic study tests whether interval-valued attribution can conservatively reduce uninformative-feature importance; only X2 carries signal among features with different cardinalities.The remaining features are generated independently of the outcome, and the signal strength for X2 varies with ρ.Source: E. Application: debiasing… · p. 9

1) Global study:

The global study finds that SHAPPess reduces importance assigned to uninformative high-cardinality features, while feature-ranking experiments find competitive AUC for SHAPPess and SHAPSafe. The paper presents interval-valued SHAP as a tractable stability and debiasing proxy, while noting that general-s ensemble computation for large ensembles remains challenging.

1) Global study:

  • SHAPPess reduces importance assigned to uninformative high-cardinality features, without claiming to remove all high-cardinality bias.The study presents it as a tractable, interpretable debiasing proxy that avoids retraining the model or recomputing SHAP on additional data splits.Source: Figure 1 · p. 9, 1) Global study · p. 9

2) Feature ranking:

  • Both SHAPPess and SHAPSafe achieve competitive AUC; SHAPSafe is slightly lower than SHAPPess, consistent with its goal of retaining features that may remain important under admissible perturbations.The AUC separates informative from uninformative features.Source: Table VII · p. 10, 2) Feature ranking · p. 10

V. CONCLUSION

  • The IDM-based method quantifies tree-based SHAP robustness with intervals induced by introducing a few virtual samples into leaves, using pessimistic and averaging principles.The paper reports theoretical results enabling efficient computation, case studies, and experiments relating the intervals to bootstrap-retraining variability.Source: §V · p. 10
  • Exact ensemble computation is future work; general s with large ensembles remains challenging, while s = 1 may be handled efficiently with heuristics.One proposed alternative for exact computation translates an ensemble into a potentially large single tree, whose construction and many leaves may be costly.Source: §V · p. 10

Related papers

Loading 2610.11953v1…