TreeSHAP: Efficient Computation for Tree Models
What You'll Learn
You'll learn how TreeSHAP computes exact SHAP values for tree-based models in polynomial time, making interpretability practical for forests and boosted trees.
The Computational Challenge
Computing exact SHAP values naively requires evaluating all possible feature subsets—an exponential problem. For n features, that's 2^n subsets. KernelSHAP approximates to avoid this explosion, but for tree-based models, we can do better.
TreeSHAP's Key Insight
TreeSHAP exploits the structure of decision trees to compute exact SHAP values efficiently. Instead of considering all feature subsets independently, TreeSHAP traverses the tree once per feature, tracking how predictions change when that feature is "absent."
Think of it like this: imagine you're trying to measure a friend's influence on group decisions. Instead of rerunning every historical decision with and without them (exponential), you review the decision tree of past choices and mathematically compute their average impact by following which branches would change (polynomial).
How It Works
TreeSHAP recursively traverses each decision tree, maintaining:
- The probability of reaching each node when a feature is unknown
- The expected prediction along paths where the feature doesn't split
For ensemble models (Random Forests, XGBoost), it averages contributions across all trees. The algorithm runs in O(TLD²) time, where T is trees, L is leaves, and D is depth—polynomial and fast in practice.
Why This Matters
TreeSHAP made SHAP practical for real-world tree models. You get exact Shapley values (not approximations like KernelSHAP) for Random Forests and gradient boosting models in seconds, not hours.
Key Takeaway: TreeSHAP leverages tree structure to compute exact SHAP values in polynomial time, making precise feature attribution efficient for tree ensembles without approximation.