Source-linked AI summary
Consistent feature attribution for tree ensembles
Scott M. Lundberg, Su-In Lee
TL;DR
Tree-ensemble feature attribution methods can assign lower importance to a feature whose model effect increases, undermining explanations of widely used models. The paper derives fast exact Tree SHAP algorithms and integrates them with XGBoost. SHAP provides consistent attributions and practical explanations for large tree ensembles, while the paper also identifies computational challenges in estimating conditional expectations and handling exponential complexity.
Problem
Existing tree-ensemble attribution methods are inconsistent, assigning lower importance when a feature’s true model effect increases, despite the importance of explaining predictions.
Method
The paper connects tree-ensemble attribution to SHAP values, derives exact polynomial-time algorithms for tree ensembles, and integrates them into XGBoost.
Results
SHAP values are shown to provide consistent attributions, while Tree SHAP enables explanations for models with thousands of trees and hundreds of inputs in a fraction of a second.
Takeaways & Limitations
SHAP values provide a practical replacement for previous tree-ensemble feature attribution methods.
Takeaways & Limitations
Tree SHAP addresses the exponential complexity challenge, but efficient estimation of E[f(x) | xS] remains a stated challenge.
Abstract
from arXiv · showhide
Note that a newer expanded version of this paper is now available at: arXiv:1802.03888 It is critical in many applications to understand what features are important for a model, and why individual predictions were made. For tree ensemble methods these questions are usually answered by attributing importance values to input features, either globally or for a single prediction. Here we show that current feature attribution methods are inconsistent, which means changing the model to rely more on a given feature can actually decrease the importance assigned to that feature. To address this problem we develop fast exact solutions for SHAP (SHapley Additive exPlanation) values, which were recently shown to be the unique additive feature attribution method based on conditional expectations that is both consistent and locally accurate. We integrate these improvements into the latest version of XGBoost, demonstrate the inconsistencies of current methods, and show how using SHAP values results in significantly improved supervised clustering performance. Feature importance values are a key part of understanding widely used models such as gradient boosting trees and random forests, so improvements to them have broad practical implications.
1. Introduction
Tree-ensemble feature attributions are important for understanding predictions, but existing methods can be inconsistent. The paper connects these methods to SHAP values and develops fast tree-specific algorithms, followed by comparisons with prior methods.
- Feature importance values help explain tree-ensemble predictions for individual cases and entire datasets.
- Existing tree-ensemble attribution methods can assign lower importance when a feature’s model impact increases.
- SHAP values are presented as the only consistent additive feature attributions with desirable properties.
- Tree SHAP reduces exact computation from exponential complexity to O(TLD2), enabling explanations for large ensembles in a fraction of a second.The algorithm is integrated into XGBoost and supports models with thousands of trees and hundreds of inputs.
- The paper evaluates SHAP against previous attribution methods in supervised clustering.
2. Current feature attributions are inconsistent
Standard tree-ensemble feature importance methods can reverse the apparent importance of a feature as its effect grows. The paper explains this inconsistency through path-based attribution rules and contrasts them with SHAP values.
- Popular tree-ensemble packages provide feature importance values intended to summarize model behavior and identify features driving predictions.
- Dataset-level importance is typically computed as the sum of loss reductions, or “gain,” across splits using each feature.
- Single-prediction methods measure changes in model output along the decision path rather than loss reduction.
- Both standard approaches consider only splits along the decision path, so they are termed path methods.
- In Figure 1, path methods and split count assign less importance to Cough in tree B despite its larger output impact; SHAP remains consistent.The comparison assumes equal leaf coverage and perfect regression accuracy for the gain calculations.
3. SHAP values are the only consistent feature attributions
SHAP values arise as the unique additive feature attributions satisfying local accuracy, missingness, and consistency. The construction represents model outputs through binary feature-presence patterns and uses conditional expectations with Shapley values to assign feature contributions.
- Additive feature attribution methods explain a model output as a sum of real values assigned to input features.
- Their explanation model is a linear function of binary variables representing feature presence or absence.The binary variables are z′ ∈ {0, 1}^M, where M is the number of input features.
- The unique desirable solution satisfies local accuracy, missingness, and consistency.Local accuracy equates attribution sums with the explained output, while missing features receive no attribution and stronger feature impact cannot reduce its attribution.
- SHAP constructs feature attributions by evaluating conditional expectations for observed feature subsets and applying classic Shapley values.The mapping from original inputs to binary missing-feature patterns enables evaluating the model under different observed-feature sets.
- SHAP values are the only consistent, locally accurate additive attributions that obey missingness and use conditional dependence to measure missingness.This gives SHAP a strict theoretical improvement over existing tree-ensemble approaches by eliminating their consistency problems.
4. Tree SHAP: Fast SHAP value computation for decision trees
Tree SHAP addresses SHAP’s computational barriers for tree ensembles by replacing exponential computation with exact polynomial-time algorithms that track subset contributions efficiently.
- SHAP computation faces both difficulty estimating conditional expectations and exponential complexity in the number of features.
- Tree-specific methods estimate conditional expectations recursively using node values, split features, thresholds, and subtree cover.
- The polynomial-time algorithm tracks the proportions of all possible feature subsets flowing to each tree leaf.
- The resulting approach computes exact SHAP values for tree ensembles in O(TLD2) time, rather than exponential time.
- Tree SHAP preserves subset-size weighting by tracking each possible subset size during recursion, using EXTEND and UNWIND operations.
5. Supervised clustering experiments
The experiments apply supervised clustering to prediction explanations in Alzheimer’s disease data and show that SHAP-based explanations yield clearer and better outcome-separating clusters than path explanations.
- The study clusters feature attributions to identify Alzheimer’s subgroups with similar mechanisms of disease and predicted CERAD cognitive outcomes.
- Positive and negative attributions are represented as red and blue bars, respectively, and stacked to visualize each prediction as a sum of feature effects.
- The experiment uses 518 participants, 200 gene expression module features, and an XGBoost model whose predictions are explained before hierarchical clustering.
- SHAP explanations produce clearer hierarchical cluster structure than standard XGBoost path explanations.
- Unsupervised clustering performs no better than random, path explanations perform significantly better, and SHAP values perform significantly better still.
- The clustering comparison evaluates how long R2 remains high as hierarchical groups merge from one group per sample to a single group.
6. Conclusion
The paper concludes that classic tree-ensemble attribution methods are inconsistent, while fast SHAP algorithms make theoretically consistent feature attribution practical in XGBoost.
- Classic tree-ensemble attribution methods can assign less importance to a feature even when its true effect increases.
- SHAP values provide the unique consistent way to attribute feature importance described in the paper.
- Fast SHAP algorithms integrated with XGBoost make SHAP a practical replacement for previous tree-ensemble attribution methods.