TreeSHAP

Unlike KernelSHAP, which relies on sampling coalitions and linear regression to approximate SHAP values, TreeSHAP computes the exact Shapley values for tree ensembles. It achieves this by recursively tracking the proportion of all possible feature coalitions that flow down each branch of the tree, eliminating the variance introduced by stochastic approximation methods.

A naive Shapley value calculation requires evaluating all 2^M feature coalitions, resulting in exponential time complexity. TreeSHAP reduces this to O(TLD^2) time and O(D^2 + M) memory, where T is the number of trees, L is the maximum number of leaves, D is the maximum tree depth, and M is the number of features. This makes exact SHAP computation feasible for deep ensembles with hundreds of features.

TreeSHAP simultaneously satisfies local accuracy (the sum of feature attributions equals the model's prediction for a single instance) and consistency (if a model changes so a feature's contribution increases, its SHAP value does not decrease). Because TreeSHAP computes exact Shapley values, it inherits these game-theoretic guarantees, ensuring explanations are both faithful and logically coherent across different models.

TreeSHAP supports two modes of feature conditioning. Tree path-dependent SHAP (the default) follows the tree structure and respects the correlation structure learned by the model. Interventional SHAP breaks feature correlations by using a background dataset to marginalize over absent features, aligning with Pearl's do-calculus for causal inference. This distinction is vital when features are highly correlated in the real world.

Tree-based models like XGBoost natively handle missing values by learning a default branch direction during training. TreeSHAP correctly accounts for these missingness-aware splits when allocating credit. If a feature is missing, it receives zero attribution for that instance, and the remaining features are credited appropriately, preserving the completeness property even with incomplete input vectors.

A unified game-theoretic framework that assigns each feature an importance value for a particular prediction, representing its marginal contribution averaged over all possible feature orderings.

• Core Properties: Local accuracy, missingness, and consistency.
• Connection: TreeSHAP is the exact, polynomial-time algorithm for computing these values specifically for tree ensembles.
• Output: A linear decomposition of a prediction into the sum of feature attributions and a base value.

A model-agnostic global explanation method that measures the drop in a model's performance score after randomly shuffling the values of a single feature, breaking its association with the target.

• Contrast with TreeSHAP: Measures global importance based on error increase, while TreeSHAP provides local, instance-specific attributions with a game-theoretic foundation.
• Limitation: Can produce misleading results when features are highly correlated, a problem TreeSHAP's conditional expectation variant addresses.

A global visualization tool that shows the marginal effect of one or two features on the predicted outcome by averaging the model's predictions over the marginal distribution of all other features.

• Relationship: SHAP dependence plots are a sharper alternative that reveal interaction effects and heterogeneity hidden by PDPs.
• Advantage of SHAP: PDPs can produce physically impossible data points when features are correlated; SHAP values provide a more faithful representation of the model's learned structure.

A quantitative evaluation criterion that measures how accurately an attribution map reflects the true importance of features by perturbing the most important inputs and measuring the resulting prediction drop.

• Relevance: Used to benchmark TreeSHAP against other attribution methods like LIME or Integrated Gradients.
• Process: Features are removed in order of descending attribution magnitude; a steeper drop in model confidence indicates higher faithfulness.
• Outcome: TreeSHAP consistently demonstrates high faithfulness due to its exact computation of Shapley values.