Interval-valued SHAP in Tree-Based Models

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.