Feature-Specific Coefficients of Determination in Tree Ensembles

Authors: Zhongli Jiang, Dabao Zhang, Min Zhang
Primary area: interpretability and explainable AI
Keywords: explainable ai, feature importance, shapley value, tree ensemble

Abstract:
Tree ensemble methods provide promising predictions with models difficult to interpret. Recent introduction of Shapley values for individualized feature contributions, accompanied with several fast computing algorithms for predicted values, shows intriguing results. However, individualizing coefficients of determination, aka $R^2$, for each feature is challenged by the underlying quadratic losses, although these coefficients allow us to comparatively assess single feature's contribution to tree ensembles. Here we propose an efficient algorithm, Q-SHAP, that reduces the computational complexity to polynomial time when calculating Shapley values related to quadratic losses. Our extensive simulation studies demonstrate that this approach not only enhances computational efficiency but also improves the estimation accuracy of feature-specific coefficients of determination.

Decision: withdrawn
Reviewer scores: 8, 3, 6, 3, 8

Reviews and discussion:
<thread>
creation date:
1730324712221

thread_type:
official_review

<thread_object>
creator: reviewer_wpck

<content>
summary:
The authors developed an algorithm Q-SHAP for fast and accurate
computation of Shapley features scores for regression problems, for
tree-based models like Gradient Boosted Machines. The algorithm is
evaluated using 3 synthetic and one real dataset, and is orders of
magnitude faster than comparator methods.

strengths:
- important problem

- creative and computationally very efficient solution

- well-written manuscript

weaknesses:
- relatively limited evaluation (3 synthetic datasets, one real with
  somewhat discordant results - see Questions section)

questions:
For the real data (Gleason score), there is a great match between top
15 features for Q-SHAP and SAGE, but mismatch between the two and
SPVIM. Can the authors comment on this discrepancy?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730398670364

thread_type:
official_review

<thread_object>
creator: reviewer_gqxu

<content>
summary:
The paper proposes a new algorithm, Q-SHAP, designed to efficiently calculate feature-specific coefficients of determination in tree ensemble models. This algorithm addresses the computational challenges associated with Shapley values for quadratic loss, particularly in high-dimensional data contexts where calculating feature contributions becomes complex and computationally intensive. By leveraging tree structure, Q-SHAP reduces the time complexity to polynomial time, making it feasible for large datasets and models. The contributions of Q-SHAP include:

- Q-SHAP reduces complexity, enabling fast computation of feature-specific R^2.

- Extensive simulations show Q-SHAP's superiority in estimating feature-specific R^2 over existing methods.

strengths:
- The paper introduces a novel algorithm, Q-SHAP, which specifically addresses the computational challenges of calculating feature-specific R^2 within tree ensembles.

- The paper explains the underlying motivation well and presents its contributions in a structured, sequential manner, making it easier for readers to follow.

- The authors conduct comprehensive simulations to test the algorithm's performance across various scenarios, demonstrating Q-SHAP’s accuracy and computational efficiency compared to well-known methods like SAGE and SPVIM.

weaknesses:
- While the paper acknowledges related methods like SAGE and SPVIM, it could better contextualize Q-SHAP's theoretical advantages over these approaches. Specifically, the paper could benefit from a more detailed comparison of the mathematical foundations and computational complexity of Q-SHAP versus these methods. Including a table or diagram that compares the key theoretical aspects, limitations, and unique benefits of each method would make Q-SHAP’s improvements clearer to readers.

- The paper mentions that Q-SHAP’s framework might be extendable to other quadratic loss functions, but it doesn’t explore this idea in depth. This is a missed opportunity to underscore the broader relevance of the algorithm, as generalizability can increase impact across various applications in machine learning and data science.

- Although the paper includes a real-data example (prostate cancer gene expression data), the experiments could further explore different types of datasets to stress-test Q-SHAP’s robustness across diverse scenarios. For instance, it would be informative to see how Q-SHAP performs in datasets with imbalanced classes, highly correlated features, or extreme high-dimensional spaces.

- While the paper demonstrates that Q-SHAP is computationally faster than SAGE and SPVIM, it lacks specific breakdowns of how time complexity is reduced in different stages of the computation. Additionally, it would be useful to know how Q-SHAP’s runtime scales with an increasing number of features or trees, beyond the static benchmarks shown.

questions:
The main issues have been highlighted in the section addressing weaknesses, but additional questions remain:

- Could you provide more insights or a breakdown of how polynomial time complexity is achieved within Q-SHAP? Specifically, a step-by-step breakdown of the algorithm, highlighting which specific operations contribute most significantly to reducing time complexity compared to existing methods, would clarify where the computational gains arise. This detailed explanation would make the efficiency improvements more actionable and understandable.

- Given Q-SHAP's improvements in feature-specific R^2 calculations, how does this translate to increased interpretability or trust in model predictions? Concrete examples or case studies where the improved accuracy of Q-SHAP’s feature-specific R^2 calculations enhances decision-making or model interpretation in real-world scenarios would help readers understand the practical impact of the method. For example, demonstrating applications in high-stakes fields like healthcare or finance would illustrate how Q-SHAP’s outputs can directly benefit practitioners.

- Are there limitations of Q-SHAP that practitioners should be aware of when using it on different types of tree models? A specific section dedicated to discussing Q-SHAP's limitations and potential pitfalls would be helpful. This could include guidelines on when Q-SHAP might not be the best choice, as well as precautions users should take when applying it to various tree model variants. Such a section would provide practical insights and help manage expectations for different use cases.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730573564961

thread_type:
official_review

<thread_object>
creator: reviewer_cdvg

<content>
summary:
The authors present Q-SHAP, a polynomial-time algorithm for computing Shapley-valued-based individual feature contributions to R^2 for tree ensemble models for a dataset in aggregate (as opposed to using Shapley to explain individual predictions). R^2 decomposition is expressed in terms of Shapley values for model predictions and squared model predictions for individual data points and then summed over the data. The authors leverage the piecewise-constant prediction surface of trees within individual leaves and apply the inverse fast fourier transform to achieve polynomial-time computation .Q-SHAP is shown to do a better job than 2 competing methods of estimating R^2 feature importance for a collection of toy problems of 3 variables where ground truth is known.  Q-SHAP is also illustrated on one real world bioinformatics gene expression problem where the number of features (17k) far exceeds the number of data points (551).

strengths:
The work is original to the best of my knowledge. Given the large volume of ML papers in recent years, it's possible that there are other polynomial time methods for the same problem, but I'm not aware of them. 

I think the paper clearly has enough significance to merit acceptance at ICLR. Tree ensembles such as gradient boosting machines (XGBoost, etc) continue to be state of the art for tabular problems, as evidenced in their prevalence in winning Kaggle competitions. Feature importance is certainly a significant topic for such models. It's quite worthwhile to be able to do a Shapley decomposition at the dataset level to explain R^2 contributions of features for such models. 

The clarity of the paper could be improved (see my comments in weaknesses) but is near the adequate range for acceptance.

weaknesses:
I think the experimental results are a little thin. There is only one real-world example in the paper. I realize that you can't really get ground-truth for feature importance for real world problems, so that does make it somewhat less important to have results on a large collection of real datasets than for a paper where predictive accuracy is the main contribution. Even so, I would have preferred to see the paper illustrated on at least one more problem. The gene expression problem seems quite extreme in terms of having number of features >>> number of data points. I realize that large feature sets may be the area where Q-SHAP shines, but results on a 2nd problem which is not such an outlier in terms of number of features would have been nice. 

While I realize that there is plenty of interest in Shapley and that Shapley is the unique solution to a set of key desiderata, I also would have appreciated more illustration of the failings of a method like feature permutation importance, given how prominent that method is. I'm not familiar with the Ishwaran paper that is cited, but it's not in a well known ML journal (by the way Electronic Journal of Statistics has a misspelling in the citations.."Elecctronic" ). 

I also have several typo/rewrite suggestions:

page 2

for any set of feature -> for any set of features

and dummy? "null player" is I think a more standard term for that Shapley criterion.

page 3 

lies on the fact -> lies in the fact

Fig 2 caption hypothetic -> hypothetical

Page 8 

maximum depth of Models -> maximum depth of models

Page 9
based the result-> based on the result

quadartic -> quadratic

questions:
Do you have results on another real-world problem?

Can you explain in more detail the failings of permutation importance and how a Shapley approach would be better, with a concrete example?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730684991095

thread_type:
official_review

<thread_object>
creator: reviewer_nzh9

<content>
summary:
The paper proposes an extension of Shapley values to decision tree ensembles for quadratic losses for the whole training set. Similar to TreeSHAP, it exploits the tree hierarchy in calculation. Experiments are performed on simulations studies and on a real genome data.

strengths:
The is the first paper that adapts Shapley values for tree ensembles for quadratic losses, which can be used to estimate coefficient of determination globally for the whole training set.

weaknesses:
1. The motivation of the paper is not clear. Shapley values by itself are quite controversial in terms of an interpretability tool, and using it globally to estimate coefficient of determination is not clear. 
2. The paper is hard to follow. The actual algorithm is presented in Sections 3.3 and Section 4 which is only one page. It is not obvious how it is different from the previous work.

questions:
Does the algorithm exactly estimate the Shapley values or approximately?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730713884166

thread_type:
official_review

<thread_object>
creator: reviewer_kwc8

<content>
summary:
Coefficients of determination, R2,  represents the total variation explained by a feature. However, its computation for the datasets with huge number of features is challenging due to the underlying quadratic loss. This study introduces the Q-SHAP algorithm, a novel approach for calculating Shapley values in tree ensembles to decompose R2 and  speed up its computation.  The goal is to reduce the computational complexity to polynomial time when calculating Shapley values related to quadratic loss terms. The proposed approach leverages tree structure, polynomial-based calculations and the Inverse Fast Fourier Transform (IFFT). 

Polynomial representation is computed by defining a polynomial based on the product of weights for features along the paths to leaves. Specifically, for each pair of leaves, calculate the union of their feature sets and the size of this union to identify the features involved in the paths to these leaves. To calculate the contribution for each feature in the combined feature sets, the algorithm considers a normalization coefficient to balance the contribution of each feature, proportional to the total number of features in the combined set. After applying a weight adjustment, the algorithm predicts each feature’s individual impact on the overall prediction by estimating the contributions through the coefficient polynomial, which aggregates these contributions to simplify the prediction process for the subset of features. 
The polynomial representation of feature contributions allows QSHAP to take advantage of IFFT, which is helpful for calculating the dot product of the polynomial representations of feature contributions. By applying IFFT, it  can quickly compute aggregated Shapley values over multiple leaves and trees, which is faster than directly summing or iterating over each possible combination. The paper has conducted experimentation on synthetic as well as real datasets.

strengths:
Scalability of the proposed approach: QSHAP achieves polynomial-time complexity, making it computationally feasible to use in large datasets and high-dimensional models. This efficiency is particularly advantageous compared to previous Shapley value methods that are NP-hard in general. 

Theoretical foundation: The authors provide mathematical proofs, such as the use of polynomial forms.

weaknesses:
Dependency on Tree Structure: The algorithm’s design leverages specific tree-based model properties, consequently, QSHAP may not directly generalize to non-tree ensemble methods. 

The authors need to simplify and better explain the part that they have computed the polynomial representation, using meaningful step wise flowchart, figures, etc.

questions:
The part that you explain about predicting polynomial representation needs a one paragraph summary in the beginning with a justification of the choices you have made, all in one place. The reader gets some ideas before going through all the formulas. Specially explaining how do you handle situations where features appear multiple times along the paths to the leaves? Does this affect the weight assignment for these features?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731472847693

thread_type:
official_comment

<thread_object>
creator: area_chair_9aah

<content>
title:
authors - reviewers discussion open until November 26 at 11:59pm AoE

comment:
Dear authors & reviewers,

The reviews for the paper should be now visible to both authors and reviewers. The discussion is open until November 26 at 11:59pm AoE.

Your AC
</content>
</thread_object>

</thread>
<thread>
creation date:
1732338060747

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to common concerns

comment:
Dear Reviewers,

We sincerely thank you for your thoughtful and detailed feedback on our manuscript. Your comments have given us an excellent opportunity to address concerns and refine the quality of our work. We have carefully reviewed each point raised and made revisions accordingly to improve the clarity and rigor of the manuscript.

We would like to address three common concerns here and address the left ones in response to corresponding reviewers. We would like to let you know that we have implemented Q-SHAP in Python and are ready to publish it via GitHub once the current review is complete.

1) Polynomial Complexity of Q-SHAP and Advantages over SAGE and SPVIM:

Here’s our complexity calculation of Q-SHAP (Algorithm 1) for a single tree and one sample: The two outer loops that iterate through the L tree leaves, resulting in a complexity of O(L^2). Within the inner loop, the computation involves the number of features induced by each pair of leaves, which is O(D) .The evaluation of  t[j]  involves the computation of  C(z) \cdot P(z) , which takes O(D) operations since the number of union features between two leaves is bounded by 2D. Combining these, the overall complexity for one tree and one sample is  O(L^2D^2) . For a dataset with sample size n, the complexity of Q-SHAP scales to O(nL^2D^2) for a single tree. With the advancements introduced in Section 4, Q-SHAP has a total complexity of O(TnL^2D^2) for an ensemble of T boosting trees.

For comparison, we list the computation complexities of all three methods in the below:

Q-SHAP:   O(T*L^2*D^2*n)

SAGE:       O(T*D*S*p*n)

SPVIM:     O(T*D*p* n^2*logn)

where

n — sample size;

T — number of trees;

D — maximum tree depth;

L — maximum number of tree leaves;

p — Number of features;

S — Number of permutations (S=10^20 in SAGE by default).


A prominent advantage of Q-SHAP is that the computation does not depend on the number of features p, which is critical in analyzing high-dimensional data. Such an advantage is achieved via Proposition 1, which eliminates dependence on p by leveraging the internal structure of the tree. Furthermore, unlike SAGE and SPVIM, which require extensive sampling, Q-SHAP directly utilizes the tree’s weight function introduced in Lines 210-214, eliminating the need for any sampling.

We have added Appendix E to provide such details.

2) Synthetic Data Analyses with Ground Truth:

Because of the concern on the ground-truth, we carefully designed three true models for the simulation study so that, for each model, we can obtain theoretical values of all feature-specific R^2 values. To mimic practical challenges, we have added different numbers of noisy features (resulting in a total of 100 and 500 features) as well as different sample sizes (500, 1000, 2000, 5000) and different levels of noise (with error standard deviation at 0,5, 1, 1.5). For each of these 72 different configurations, we simulated 1,000 datasets, leading to a total of 72,000 datasets. We have summarized the results in Section 5 of the main text and Section C of Appendix.
</content>
</thread_object>

</thread>


Metareview: