PaperlayerView exact revision on arXiv

Source-linked AI summary

Consistent Individualized Feature Attribution for Tree Ensembles

Scott M. Lundberg, Gabriel G. Erion, Su-In Lee

arXiv:1802.03888v3cs.LGstat.ML

TL;DR

Tree-ensemble attribution methods can be inconsistent, undermining meaningful comparisons of feature importance. The paper develops exact, efficient SHAP methods for trees, extends them to interactions, and reports better human alignment, influential-feature recovery, clustering, and visualization opportunities.

  • Problem

    Tree-ensemble feature attributions are often heuristic and not individualized, and popular methods can assign lower importance when a feature’s true impact increases.

  • Method

    The paper uses SHAP values as the unique consistent and locally accurate attributions, derives a polynomial-time Tree SHAP algorithm, and defines SHAP interaction values.

  • Results

    SHAP values better align with human intuition, recover influential features, and enable practical supervised clustering, SHAP summary plots, and SHAP dependence plots.

  • Takeaways & Limitations

    Tree SHAP’s exponential speed improvements make consistent individualized explanations and interaction analysis practical for tree ensembles.

  • Takeaways & Limitations

    Applying SHAP to missing features requires defining a mapping from binary missing-feature patterns to the original model input space.

Abstract

from arXiv · show

Interpreting predictions from tree ensemble methods such as gradient boosting machines and random forests is important, yet feature attribution for trees is often heuristic and not individualized for each prediction. Here we show that popular feature attribution methods are inconsistent, meaning they can lower a feature's assigned importance when the true impact of that feature actually increases. This is a fundamental problem that casts doubt on any comparison between features. To address it we turn to recent applications of game theory and develop fast exact tree solutions for SHAP (SHapley Additive exPlanation) values, which are the unique consistent and locally accurate attribution values. We then extend SHAP values to interaction effects and define SHAP interaction values. We propose a rich visualization of individualized feature attributions that improves over classic attribution summaries and partial dependence plots, and a unique "supervised" clustering (clustering based on feature attributions). We demonstrate better agreement with human intuition through a user study, exponential improvements in run time, improved clustering performance, and better identification of influential features. An implementation of our algorithm has also been merged into XGBoost and LightGBM, see http://github.com/slundberg/shap for details.

1 INTRODUCTION

The paper identifies inconsistency in tree-ensemble feature attributions and develops SHAP-based methods to provide consistent individualized explanations, efficient computation, interaction effects, and attribution-based visualizations.

  • Understanding individualized and global feature attributions helps assess tree-ensemble predictions for trust, actionability, accountability, and debugging.
  • Popular tree-ensemble attribution methods can reduce a feature’s assigned importance when that feature’s true impact increases, making cross-feature comparisons unreliable.
  • SHAP values connect game-theoretic and local-explanation ideas to provide the unique consistent feature-attribution method with desirable properties.
  • The Tree SHAP algorithm reduces exact computation from O(TL2M) to O(TLD2), enabling explanations for previously intractable ensembles in a fraction of a second.The resulting dataset-scale explanations support SHAP dependence plots and SHAP summary plots as alternatives to traditional visualization methods.
  • SHAP interaction values directly represent pairwise interaction effects while retaining consistency for individual predictions.
  • The paper evaluates SHAP methods through user-study agreement, computational performance, influential-feature identification, supervised clustering, and visualizations on XGBoost and NHANES I data.

2 INCONSISTENCIES IN CURRENT FEATURE ATTRIBUTION METHODS

Common tree-ensemble attribution methods summarize feature importance globally or for individual predictions, but gain, split count, and Saabas can be inconsistent. SHAP values address this by combining conditional expectations with Shapley values, averaging effects across feature orderings to obtain consistent, locally accurate attributions.

  • Current attribution methods: Individualized attributions explain one prediction, whereas global attributions summarize feature importance across an entire dataset.Tree-specific individualized methods are less established and model-agnostic alternatives are slower and subject to sampling variability.
  • Current attribution methods: Gain measures total loss or impurity reduction from a feature’s splits, while split count measures how often the feature is used to split.Permutation importance instead evaluates the change in model error after randomly permuting a feature in the test set.
  • Inconsistency: Gain, split count, and Saabas can assign lower importance after a feature’s model impact increases, preventing reliable comparisons across features.In the two-tree example, Cough becomes more important in Model B but is attributed less importance by these methods; Saabas can also rank Fever above Cough there.
  • SHAP values: SHAP values explain a function output as a sum of feature effects introduced into conditional expectations, averaging over all possible feature orderings.Because nonlinear functions depend on introduction order, this averaging is the game-theoretic basis of SHAP attribution.
  • SHAP values: SHAP is the unique additive attribution method satisfying local accuracy, missingness, and consistency under conditional dependence.Local accuracy makes attributions sum to the function output, missingness assigns no importance to absent features, and consistency prevents increased model impact from decreasing attribution.

3 TREE SHAP: FAST SHAP VALUE COMPUTATION FOR TREES

Tree SHAP addresses the practical difficulty of computing exact SHAP values for tree ensembles by replacing exponential enumeration with a polynomial-time algorithm. It recursively tracks subset-flow information through tree paths while preserving the weighting needed for exact attributions.

  • Motivation: Tree-specific SHAP methods are motivated by the exponential complexity of exact SHAP computation and the difficulty of estimating conditional expectations efficiently.The section introduces a direct but slow approach before presenting the faster Tree SHAP algorithm.
  • Direct estimation: The direct tree algorithm estimates E[f(x) | xS] recursively using node values, branch indexes, split thresholds, feature indexes, and node cover.Node cover represents how many training samples fall into each subtree, supporting conditional expectation estimation.
  • Complexity: O(TLD^2) time and O(D^2 + M) memory replace exponential-time exact SHAP computation for tree ensembles.For balanced trees, the maximum depth is D = log L, where T is the number of trees, L the maximum leaves per tree, and M the number of features.
  • Polynomial-time algorithm: Tree SHAP recursively tracks the proportions and weights of subsets flowing through each leaf instead of enumerating all 2^M subsets independently.Its path representation records unique split features, zero and one path fractions, and the proportions of subsets by cardinality.
  • Algorithm mechanics: Algorithm 2 uses path extension, recursion, and unwinding to maintain correctly weighted subset contributions when features recur along tree paths.UNWIND reverses prior path extensions and handles repeated splits on the same feature before leaf-level attribution weights are accumulated.

4 SHAP INTERACTION VALUES

SHAP interaction values extend SHAP attributions to pairwise effects, separating interactions from main effects for individual predictions. They preserve consistency-based guarantees and can reveal interactions that ordinary feature attributions may conceal.

  • Definition: SHAP interaction values represent pairwise feature effects as a matrix of attribution values for a given model prediction.They extend Shapley values using the Shapley interaction index from game theory.
  • Interaction allocation: Each pairwise interaction is split equally between its two features, so Φi,j = Φj,i and the total interaction effect is Φi,j + Φj,i.This symmetric allocation defines how pairwise effects are distributed in the interaction matrix.
  • Main effects: Main effects are defined by subtracting a feature’s SHAP interaction values from its SHAP value.This separates the feature’s non-interaction contribution from its pairwise effects.
  • Interpretation: SHAP interaction values enable separate consideration of main and interaction effects for individual predictions while retaining analogous axiomatic guarantees.This separation can uncover important tree-ensemble interactions that might otherwise be missed.
  • Efficient computation: Tree SHAP reduces interaction-value computation by applying the algorithm twice: once with feature j present and once with feature j absent.The interaction is interpreted as the difference between feature i’s two corresponding SHAP values.

5 EXPERIMENTS AND APPLICATIONS

The experiments evaluate SHAP through human agreement, computational performance, supervised clustering, influential-feature identification, and individualized visualizations. Across these applications, SHAP supports intuitive credit allocation, faster exact explanations, clustering by prediction reasons, and richer displays of feature impacts.

  • 5.1 Agreement with Human Intuition: The user study found SHAP’s equal distribution of credit most intuitive for allocating a risk increase between Fever and Cough.Participants evaluated how to apportion a 60-point risk increase from 20 to 80.
  • 5.2 Computational Performance: An XGBoost model with 1,000 depth 10 trees and 100 input features could be explained in 0.08 seconds using Algorithm 2.Algorithm 2 provides a significant runtime improvement over prior exact-computation approaches.
  • 5.3 Supervised Clustering: Supervised clustering groups individuals by similar feature-attribution patterns rather than directly clustering their input features.In the UCI census dataset, clustered explanations formed distinct subgroups sharing common reasons for predicted income outcomes.
  • 5.4 Identification of Influential Features: SHAP-based supervised clustering outperformed Saabas-based clustering in explaining model-output variance for both census and Alzheimer’s cognitive-score datasets.Performance was evaluated by tracking R2 as hierarchical groups were merged.
  • 5.5.1 SHAP Summary Plots: SHAP summary plots show individualized attribution distributions, feature values, and impact direction across all individuals in a concise visualization.In the NHANES mortality model, age showed broad importance, while systolic blood pressure had a large impact mainly for a minority with high blood pressure.
  • 5.5.2 SHAP Dependence Plots: SHAP dependence plots provide a richer individualized alternative to partial dependence plots.They are enabled by SHAP values being unique to each prediction.

6 CONCLUSION

The conclusion presents SHAP as a consistent replacement for heuristic tree-ensemble attributions and extends it to pairwise interactions. Tree SHAP makes exact explanations practical while enabling supervised clustering and richer attribution visualizations.

  • 6 CONCLUSION: SHAP avoids the inconsistency of common tree-ensemble attribution methods, which can assign lower importance when a feature’s true impact increases.This consistency supports meaningful comparison of attribution values across features.
  • 6 CONCLUSION: Tree SHAP provides polynomial-time exact SHAP values, making explanations for previously intractable tree ensembles inexpensive.The conclusion links this speedup to practical applications including supervised clustering, summary plots, and dependence plots.
  • 6 CONCLUSION: SHAP interaction values consistently measure potentially hidden pairwise interaction relationships.They extend SHAP to interaction effects rather than dividing an interaction’s impact among individual features.
Loading 1802.03888v3…