TreeSHAP and Feature Importance

A credit model's default importance plot ranks a random customer ID hash among its top five features. The hash predicts nothing. It ranks highly because its thousands of distinct values gave the tree search many thresholds that happened to reduce training impurity. The plot was accurate about what the trees did and misleading about what matters, and choosing a better measure starts with deciding which question you want answered.

Three measures, three questions

Impurity (gain) importance sums, over every split on feature \(j\), the reduction in the training loss the split achieved. It is free and measures how much fitting used a feature. Its bias toward high-cardinality and continuous features (decision trees and impurity splitting) was shown for random forests by Strobl and colleagues, who also found that bootstrap sampling with replacement adds its own bias and that subsampling without replacement with conditional inference trees removes it (Strobl et al., 2007, Bias in Random Forest Variable Importance Measures, BMC Bioinformatics 8:25).

Permutation importance shuffles feature \(j\) in held-out data and records the increase in loss, measuring how much held-out performance depends on it. But permuting a feature breaks its correlation with the others and asks the model to predict on combinations that never occur, such as a 20-year-old with 30 years of credit history. Hooker, Mentch and Zhou showed that these permute-and-predict methods force the model to extrapolate and can be highly misleading under dependence (Hooker, Mentch & Zhou, 2021, Unrestricted Permutation Forces Extrapolation, Statistics and Computing 31, arXiv:1905.03151).

SHAP values attribute each individual prediction to features using the Shapley value from cooperative game theory, and a global importance is then an average of absolute attributions.

The Shapley value and why trees make it tractable

With feature set \(F\) of size \(M\), a value function \(v(S)\) giving the model's expected output when only the features in \(S\) are known, the attribution to feature \(i\) for input \(x\) is

It is the average marginal contribution of \(i\) over all orders in which features could be revealed. The attributions sum to the prediction minus the baseline \(v(\varnothing)\), and Lundberg and Lee showed this is the unique additive attribution satisfying local accuracy, missingness and consistency (Lundberg & Lee, 2017, A Unified Approach to Interpreting Model Predictions, NeurIPS, arXiv:1705.07874).

The sum has \(2^{M-1}\) subsets per feature: at \(M = 30\), over \(5 \times 10^8\) evaluations of \(v\), each itself an expectation. Model-agnostic methods sample.

TreeSHAP computes the exact values. It defines \(v(S)\) for a tree by following the splits on features in \(S\) and, at a split on a feature outside \(S\), descending both branches weighted by the fraction of training rows that went each way (the node "cover"). Rather than enumerating subsets, the algorithm walks each root-to-leaf path once while maintaining, for every possible subset size, the proportion of subsets that reach that leaf, which is enough to recover the Shapley weights. This reduces the cost from \(O(TL2^M)\) to \(O(TLD^2)\) for \(T\) trees with at most \(L\) leaves and depth \(D\) (Lundberg, Erion & Lee, 2018, Consistent Individualized Feature Attribution for Tree Ensembles, arXiv:1802.03888). For 1,000 depth-6 trees with 64 leaves, \(TLD^2 \approx 2.3 \times 10^6\) operations per explained row. The same work showed gain and split-count importance are inconsistent: a change that makes a feature matter more can lower its gain importance. A later paper built global summaries from local explanations (Lundberg et al., 2020, From Local Explanations to Global Understanding with Explainable AI for Trees, Nat. Mach. Intell. 2).

The disagreement that has not gone away

The value function hides a choice. "Path-dependent" TreeSHAP's cover weighting approximates the observational conditional expectation \(\mathbb{E}[f(X) \mid X_S = x_S]\), which keeps feature combinations realistic but lets a feature the model never uses receive credit through correlation with one it does. The interventional version, \(\mathbb{E}[f(x_S, X_{\bar S})]\), replaces absent features with draws from a background dataset independent of \(x_S\), which is true to the model but evaluates it off the data manifold, the same extrapolation problem as permutation.

Janzing, Minorics and Blöbaum argued from causal reasoning that the interventional form is the correct one for attributing a model's output (Janzing et al., 2020, Feature Relevance Quantification in Explainable AI: A Causal Problem, AISTATS, arXiv:1910.13413). Chen, Janizek, Lundberg and Lee replied that the choice depends on whether you want to be true to the model or true to the data (Chen et al., 2020, True to the Model or True to the Data?, arXiv:2006.16234). Sundararajan and Najmi showed that the various operationalisations satisfy different axioms and can attribute the same prediction differently (Sundararajan & Najmi, 2020, The Many Shapley Values for Model Explanation, ICML, arXiv:1908.08474). "The SHAP value" is therefore not a single quantity.

When it breaks

Correlated features split or steal credit. Near-duplicate features share attribution according to which one the trees happened to split on; dropping one can double the other's importance with no change in accuracy.

Attribution is not causation. A feature can carry high attribution because it proxies for the real driver; changing it in the world may do nothing.

The output scale changes the story. For classifiers, TreeSHAP usually attributes the log-odds, where contributions add. Converting to probabilities is non-linear, so a feature's effect on probability depends on the other features, and log-odds rankings do not transfer directly.

Mean absolute SHAP is not importance for accuracy. A feature that fits noise can shift predictions a lot without improving held-out loss.

The baseline is part of the answer. Interventional attributions depend on the background dataset: explained against all customers or against approved customers, the same prediction gets different values, and neither is wrong.