Interval-valued SHAP in Tree-Based Models

arXiv:2610.11953 · cs.LG · Submitted 2026-10-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Interval-valued SHAP in Tree-Based Models".

Tom: The gist The paper proposes an imprecise Dirichlet model (IDM) based method to analyze the robustness of Shapley values in tree-based models by quantifying interval-valued Shapley values when unannotated instances…

Jane: First, who's behind it and why it matters.

Title and authors: Tom: So we're diving into the paper titled Interval-valued SHAP in Tree-Based Models. This whole idea is about taking those Shapley values that explain how much each feature contributes to a prediction and turning them into intervals instead of single numbers.

Jane: Exactly. It starts by saying that Shapley values can be pretty fragile, meaning tiny changes in the input data or the model structure can cause big swings in those attribution scores. So, this paper proposes using an imprecise Dirichlet model based method to measure this robustness by calculating interval-valued Shapley values when you introduce a few unannotated instances into the leaves of your tree.

Lu: It's interesting because they frame it as quantifying the uncertainty around the original Shapley value by looking at what happens when you have these new, incomplete data points in the leaves. They are using principles like pessimistic and averaging principles to define these intervals, which is a way of handling incomplete data that we already see used elsewhere twelve <ref:2610.11953#pg2>.

Meng: So, if I'm just thinking about this for practical engineering purposes, what does quantifying the uncertainty look like when you're trying to deploy a model? Are we talking about something easy to compute or something that slows down our whole inference pipeline?

Lalam: The paper points out that computing these interval-valued Shapley values is a combinatorial optimization problem, which means brute force search isn't practical, so they have to find ways for efficient computation <ref:2610.11953#pg3>.

Tom: Right. So the big question here is how do you actually compute these intervals efficiently, especially when dealing with decision trees? That seems like a huge hurdle given the complexity of Shapley value calculations normally.

The paper's summary: Jane: To get into the core mechanism, the paper shows that because of how the tree is structured, each feature's Shapley value can actually be expressed as a linear combination of all those leaf values <ref:2610.11953#pg4>. This linearity is key because it makes calculating these values much more tractable than trying to calculate them directly from every possible coalition.

Lu: That’s because the game value, or the Shapley value, becomes linear in the leaf outputs, which simplifies everything down to just working with those leaf values <ref:2610.11953#pg3>. They then talk about how the efficiency of the averaging principle requires efficiency in computing expected values of multinomial distributions.

Tom: So we have these linear expressions involving leaf values, and now we need a way to handle the uncertainty introduced by those leaf parameters. That's where they introduce the idea of interval-valued attributions based on an imprecise Dirichlet model <ref:2610.11953#pg5>.

Meng: The paper models this uncertainty by connecting it to virtual samples, leading to an interval of values for each leaf parameter, like a lower bound and an upper bound based on the number of unannotated instances introduced. They then study two ways to derive these attributions: unknown allocation which is pessimistic, and stochastic allocation which is averaging <ref:2610.11953#pg5>.

Lalam: When they look at unknown allocation, they formulate it as finding the infimum of a linear function over the set of reachable values, and that optimization problem can be solved using a greedy approach summarized in Algorithm one <ref:2610.11953#pg5>.

Jane: And for stochastic allocation, they find that the attribution endpoints are averaged with respect to an allocation distribution P(m), yielding expected endpoints characterized by EM

phi inn i(M): equals phi i(w) minus C exp alpha sign i (s) <ref:2610.11953#pg5>.

Tom: That’s a lot of mathematical machinery packed into defining these intervals, but it seems the paper is really focusing on providing a formal framework for quantifying how much uncertainty we can put around those attribution scores.

The paper's improvements: Tom: Beyond just defining the intervals, the authors suggest some ways to actually use this information to improve things. They focus on how you compare different features and how you measure stability across a whole ranking.

Lu: For ranking stability, they propose looking at the pairwise attribution margin γij(w) which is defined as phi i(w) minus phi j(w), and checking if all adjacent lower margins are positive to see if the whole ranking is robust at uncertainty level s <ref:2610.11953#pg8>, <ref:2610.11953#pg9>.

Meng: That sounds like a way to certify a robust top-k set of features, which would be really useful for building systems where you need to know exactly which features are driving the prediction under some level of noise.

Jane: And for debiasing uninformative features, they introduce SHAPPess, which is defined as the infimum of the interval length over all possible allocations <ref:2610.11953#pg10>. This gives you a conservative proxy for attribution stability without needing to retrain the model or recompute SHAP on new data splits <ref:2610.11953#pg10>.

Lalam: They also show that this interval-valued SHAP can provide a tractable and interpretable debiasing proxy, and they even compare its performance against other methods like SHAPSafe for separating informative from uninformative features <ref:2610.11953#pg8>.

Tom: It seems the main improvement is turning a static attribution score into an interval that tells you the range of possible scores it could have, and then using metrics like SHAPPess to make conservative decisions about feature importance.

Conclusion: Jane: So to wrap up on this paper, the authors propose an IDM-based method for analyzing the robustness of Shapley values in tree-based models by quantifying interval-valued Shapley values when virtual samples are introduced into the tree leaves <ref:2610.11953#pg11>. They showed these intervals can be computed efficiently under both the pessimistic and averaging principles <ref:2610.11953#pg5>.

Lu: The paper gives case studies and experiments illustrating how this behavior relates to empirical variability produced by bootstrap retraining <ref:2610.11953#pg5>, and it also shows how the method can better estimate the importance of uninformative features <ref:2610.11953#pg10>.

Meng: From an engineering standpoint, seeing that these intervals align with empirical variability from bootstrap retraining is a strong validation because it means the math we're doing isn't just theoretical; it matches real-world noise in model retraining.

Lalam: And for culture, this means we can build tools that give us a more stable view of feature importance without needing to re-run heavy SHAP computations every time we want to assess robustness.

Tom: It’s a solid contribution because it gives us a way to get some interpretable debiasing proxy that doesn't require retraining or extra data splits, which is pretty practical for safety-critical applications. That’s the big picture with this work on Interval-valued SHAP in Tree-Based Models.

Chenrui Zhu, Vu-Linh Nguyen, Marie-Helène Masson, Sebastien Destercke

Universite de technologie de Compiègne · IUT de l’Oise

cs.LG

Submitted: 2026-10-08

Updated: 2026-10-08

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 81/100

The gist: The gist The paper proposes an imprecise Dirichlet model (IDM) based method to analyze the robustness of Shapley values in tree-based models by quantifying interval-valued Shapley values when

Key concepts

Imprecise Dirichlet Model (IDM): This model is used to mathematically define the uncertainty surrounding the parameters of tree leaves. It connects leaf parameter uncertainty to virtual samples, resulting in an interval [lower, upper] for each leaf value. These bounds are interpreted either in a frequentist or Bayesian manner.
Pessimistic and Averaging Principles: These are two methods used to derive the interval-valued Shapley values. The pessimistic principle finds the most conservative (smallest) possible attribution interval, while the averaging principle calculates an expected endpoint based on a specified distribution of virtual samples.

Summary

The gist The paper proposes an imprecise Dirichlet model (IDM) based method to analyze the robustness of Shapley values in tree-based models by quantifying interval-valued Shapley values when unannotated instances are introduced into the leaves. This method is significant because it addresses the fragility of Shapley values due to small changes and provides a framework for assessing model stability, particularly for interpretability in safety-critical applications.

How it works

The core idea is to associate the robustness of each Shapley value with an interval-valued Shapley value that covers the original value, induced by introducing a small number of unannotated instances into the training data<ref:2610.11953#pg3>. This is implemented following common principles in handling incomplete data, namely the pessimistic and averaging principles<ref:2610.11953#pg3>. The problem of computing interval-valued Shapley values is combinatorial optimization, making brute-force search impractical<ref:2610.11953#pg3>.

The paper derives theoretical results for efficient computation of these interval-valued Shapley values in the case of decision trees<ref:2610.11953#pg3>. For each instance, it shows that the Shapley value associated with each feature can be expressed as a linear combination of the leaf values<ref:2610.11953#pg4>. The efficiency of the averaging principle requires efficiency in computing expected values of multinomial distributions<ref:2610.11953#pg3>. The efficiency of the pessimistic principle is achieved by leveraging linearity and the property that leaf values are convex decreasing (concave increasing) functions in the number of unannotated instances<ref:2610.11953#pg3>.

Interval-valued attributions

The uncertainty in leaf parameters wl is modeled by connecting it to virtual samples, leading to an interval of values [wl lower, wl upper] = [nl/Nl + ml, nl + ml/Nl + ml], where the bounds are interpreted either in a frequentist way or a Bayesian way corresponding to the Imprecise Dirichlet Model (IDM)<ref:2610.11953#pg5>. The user specifies a unique number s of virtual instances to be distributed among the tree leaves, resulting in an allocation vector m=(ml)l∈L<ref:2610.11953#pg5>.

The paper studies two settings for deriving interval-valued attributions: unknown allocation (pessimistic) and stochastic allocation (averaging)<ref:2610.11953#pg5>. Under unknown allocation, the problem is formulated as finding the infimum of the linear function ϕi(w) over the set of reachable values ran(w), which is solved by finding an optimal allocation m<ref:2610.11953#pg5>. This optimization problem can be solved using a greedy approach, summarized in Algorithm 1<ref:2610.11953#pg5>.

Under stochastic allocation, the attribution endpoints are averaged with respect to the allocation distribution P(m), yielding EM[ϕ inn i(M)] = ϕi(w) - C exp α sign i (s)<ref:2610.11953#pg5>. These expected endpoints characterize average attribution uncertainty under a specified placement law π<ref:2610.11953#pg5>.

Extensions to tree-ensemble

The leaf-linear representation extends directly to ensembles, where the ensemble attribution is linear in the collection of leaf outputs<ref:2610.11953#pg7>. The ensemble can be interpreted as a large tree whose leaves are non-empty intersections, but an approximate approach is proposed by relaxing the requirement that leaf lT (27) should be non-empty and defining the attribution using (26)<ref:2610.11953#pg7>. The greedy algorithm from Algorithm 1 can be extended to find an allocation on the (possibly empty) leaves of the ensemble that is optimal under the pessimistic principle<ref:2610.11953#pg7>.

Discussion

For ranking stability, it is more appropriate to compare two features under the same leaf vector w by defining the pairwise attribution margin γij(w) = ϕi(w) - ϕj(w)<ref:2610.11953#pg8>. The stability of a whole ranking can be tested by checking adjacent margins γi(k)i(k+1)(w), k = 1,..., n−1<ref:2610.11953#pg9>. In the context of debiasing uninformative features, the pessimistic principle allows for a conservative proxy for attribution stability by defining SHAPPess as the infimum of the interval length over all possible allocations<ref:2610.11953#pg10>. The results suggest that interval-valued SHAP can provide a tractable and interpretable debiasing proxy without retraining the model or recomputing SHAP on additional data splits<ref:2610.11953#pg10>.

Conclusion

In this paper, an IDM-based method is proposed to analyze the robustness of SHAP values in tree-based models by quantifying interval-valued Shapley values when virtual samples are introduced into the tree leaves<ref:2610.11953#pg11>. These intervals, defined under the pessimistic and averaging principles, can be computed efficiently<ref:2610.11953#pg5>. The method provides case studies and experiments illustrating their behavior and relationship with empirical variability produced by bootstrap retraining<ref:2610.11953#pg5>. It also shows how the method can better estimate the importance of uninformative features<ref:2610.11953#pg10>.

How it works

The paper evaluates the proposed framework using decision trees for local analysis and random forests for ensemble settings<ref:2610.11953#pg5>. It examines which nominally important features remain robust under a given uncertainty level, how interval-valued attribution agrees with empirical attribution variability under bootstrap retraining, and how interval-valued attribution varies between confident and ambiguous decision regions<ref:2610.11953#pg5>.

Case study

A case study on the Diabetes dataset illustrates that under the pessimistic principle, features like plasma glucose and BMI have overlapping intervals, making their internal order ambiguous, but they remain clearly separated from all remaining features, yielding the conclusion that “glucose and BMI are the two dominant drivers of the prediction, while age has a secondary effect”<ref:2610.11953#pg9>. Under the averaging principle, the intervals for plas and BMI no longer overlap, preserving their nominal order<ref:2610.11953#pg9>.

Bootstrap-based validation

The correlation between SHAP interval lengths and bootstrap variability is shown to be moderately high for single trees and high for random forests across various datasets<ref:2610.11953#pg5>. The results confirm that the proposed intervals are aligned with the empirical variability produced by bootstrap retraining<ref:2610.11953#pg5>.

Attribution in certain and ambiguous regions

For random forests, a clear negative association is observed between margin scores mar(x) and the length of attribution intervals, indicating that instances with smaller margin scores tend to have wider attribution intervals<ref:2610.11953#pg10>. This is expected as predictions in more ambiguous regions are also more fragile from the viewpoint of feature attribution<ref:2610.11953#pg10>.

Application

The study demonstrates that SHAPPess reduces the importance assigned to uninformative high-cardinality features, suggesting that interval-valued SHAP can provide a tractable and interpretable debiasing proxy without retraining the model or recomputing SHAP on additional data splits<ref:2610.11953#pg10>. The AUC scores for separating informative from uninformative features show that both SHAPPess and SHAPSafe achieve competitive performance compared to other methods<ref:2610.11953#pg8>.

Conclusion

The paper proposes an IDM-based method to analyze the robustness of SHAP values in tree-based models by quantifying interval-valued Shapley values when virtual samples are introduced into the tree leaves<ref:2610.11953#pg11>. These intervals, defined under the pessimistic and averaging principles, can be computed efficiently<ref:2610.11953#pg5>. The method provides case studies and experiments illustrating their behavior and relationship with empirical variability produced by bootstrap retraining<ref:2610.11953#pg5>. It also shows how the method can better estimate the importance of uninformative features<ref:2610.11953#pg10>.

References

[1] S. M. Lundberg, G. G. Erion, S.-I.

Improvements for AI systems

The system can compute interval-valued SHAP values for tree-based models to quantify robustness against small, realistic changes in input data or model structure by associating the robustness of each Shapley value with an interval-valued Shapley value.
The system can perform feature importance debiasing by using the pessimistic principle to derive a conservative proxy for attribution stability, defined as SHAPPess i(s) = 1/J X J j=1 inf ϕ∈[ϕU i(xj;s),ϕU i(xj;s)] ϕ.
The system can assess ranking stability by comparing adjacent margins, testing If all adjacent lower margins are positive, then the complete ranking is robust at uncertainty level s, allowing for the certification of a robust top-k set of features.
The system can provide empirical evidence linking attribution interval lengths to model retraining variability by computing the Spearman correlation between SHAP interval lengths and bootstrap variability, confirming that the observed association is not specific to a certain s.
The system can distinguish between confident and ambiguous decision regions by correlating the margin score mar(x):= ˆp(1)(x) − pˆ(2)(x) with the average attribution interval length, noting that instances with smaller margin scores tend to have wider attribution intervals.