TreeSHAP

Unlike KernelSHAP which requires O(2^M) model evaluations for M features, TreeSHAP computes exact Shapley values in O(TLD^2) time, where T is the number of trees, L is the maximum number of leaves, and D is the maximum tree depth. This makes it feasible for ensembles with hundreds of features.

• Processes thousands of predictions per second
• Scales linearly with the number of trees
• No sampling or approximation required

TreeSHAP mathematically guarantees the efficiency property (also called local accuracy): the sum of all feature SHAP values plus the expected model output exactly equals the model's prediction for that instance.

• f(x) = φ₀ + Σᵢ φᵢ
• No residual or unexplained variance
• Enables complete decomposition of every prediction
• Critical for regulatory audit trails

TreeSHAP natively computes SHAP interaction values, capturing pairwise feature interactions without additional model evaluations. The algorithm tracks how features split paths jointly through the tree ensemble.

• Captures synergistic and antagonistic feature pairs
• Interaction matrix: Φ_{i,j} for all feature pairs
• Reveals non-additive model behavior
• Useful for detecting feature engineering opportunities

TreeSHAP supports two distinct conditioning strategies that yield different interpretations:

• Interventional (feature_perturbation='interventional'): Breaks correlations by sampling from marginal distributions. Reflects causal model behavior when features are manipulated.
• Observational (feature_perturbation='tree_path_dependent'): Preserves correlations by following actual tree paths. Faster but may attribute importance to correlated features that aren't causally relevant.

Choose based on whether you need causal or descriptive explanations.

TreeSHAP uses a background dataset to compute the expected model output E[f(x)], which serves as the baseline for all explanations. The algorithm stores sufficient statistics from the background data on each tree node.

• Baseline = average prediction over background samples
• Smaller background datasets reduce computation time
• Choice of background affects baseline value and attributions
• Use representative samples for meaningful explanations

TreeSHAP works natively with all major tree-based model frameworks without requiring model conversion or approximation:

• XGBoost: Native integration via xgboost.XGBRegressor and XGBClassifier
• LightGBM: Direct support through the SHAP package
• CatBoost: Compatible with ordered boosting structures
• scikit-learn: RandomForest, GradientBoosting, DecisionTree, and ExtraTrees
• Ensembles: Averages SHAP values across all trees automatically

The game-theoretic foundation of TreeSHAP. A Shapley value is a fair payout to a player (feature) based on their marginal contribution across all possible coalitions. In ML, the 'payout' is the difference between the model's prediction and the average prediction. TreeSHAP computes these exactly by exploiting the internal structure of tree models, avoiding the exponential complexity of naive coalition enumeration.

A fundamental Shapley axiom guaranteed by TreeSHAP. The Efficiency property states that the sum of all feature attributions exactly equals the difference between the model's prediction and the baseline value (expected output). This ensures a complete, fair accounting of the prediction. If a model outputs 0.8 and the baseline is 0.2, the SHAP values sum to exactly 0.6.

TreeSHAP extends beyond individual feature effects to capture pairwise interactions. SHAP interaction values distribute credit among all pairs of features, revealing synergistic or antagonistic effects. For tree models, TreeSHAP computes these exactly by tracking co-occurrence of features along decision paths. This is critical for identifying features that only matter in combination, such as age and income jointly affecting credit risk.

The primary global visualization for TreeSHAP output. A summary plot combines feature importance (ranked by mean |SHAP|) with feature effects. Each point is a single instance, colored by feature value (red=high, blue=low), and positioned by its SHAP value. This reveals not just which features matter, but how they matter—showing non-linear relationships, variance, and outlier effects in a single dense graphic.

An instance-level visualization decomposing a single prediction. Starting from the baseline value E[f(X)], each feature's contribution is displayed as a bar pushing the prediction higher (red) or lower (blue) until reaching the final output f(x). This provides a transparent, step-by-step audit trail for individual decisions, essential for regulatory compliance and debugging specific model errors.

TreeSHAP supports two causal interpretations. Interventional SHAP breaks feature correlations by sampling from marginal distributions, answering 'what if we intervene on X?'. Observational SHAP conditions on observed values, preserving correlations and reflecting the model's behavior on the natural data manifold. TreeSHAP's feature_perturbation parameter controls this, with 'tree_path_dependent' being the fast observational default.