How TreeSHAP Avoids Listing Every Feature Group
We are still explaining Maya: A = Returning, B = Premium, C = High usage. The tree predicts 90, its baseline is 52, and the feature contributions from the previous chapter are 24⅓, 3, and 10⅔. We will derive those same numbers using the leaf paths.
Calculate one leaf at a time
When some inputs are hidden, the prediction is a weighted average of the four leaves. This table records each leaf's part of the baseline:
| Leaf | Conditions | Customers | Baseline part |
|---|---|---|---|
| 10 | New, Basic | 3 of 10 | 3 |
| 30 | New, Premium | 1 of 10 | 3 |
| 50 | Returning, Low | 2 of 10 | 10 |
| 90 | Returning, High | 4 of 10 | 36 |
Revealing an input changes these weights. The change in the whole prediction is the sum of the changes from the leaves. Averaging over reveal orders preserves that sum, so we can calculate a feature's contribution at each leaf and then add them:
Follow the weight reaching the 90 leaf
The path first asks whether Maya is Returning, then whether her usage is High. Six of the ten customers are Returning; four of those six have High usage.
Hidden route weight = (6/10) × (4/6) = 2/5.
Baseline part = (2/5) × 90 = 36.
At an unknown split, use the child-to-parent count ratio. At a known split, follow Maya's value: the branch she takes gets multiplier 1, and the other branch gets 0. This gives all four cases for the 90 leaf:
| Known details | Route weight | Weight × 90 |
|---|---|---|
| None | (6/10) × (4/6) | 36 |
| Only A | 1 × (4/6) | 60 |
| Only C | (6/10) × 1 | 54 |
| A and C | 1 × 1 | 90 |
Calculate A’s share of the 90 leaf
Plan B is absent from this path and has no effect on this leaf. In the six reveal orders, A comes before C three times and after C three times. The two cases therefore have equal weight:
| Order on this path | A’s change | C’s change |
|---|---|---|
| A, then C | None → Only A 60 − 36 = 24 | Only A → A and C 90 − 60 = 30 |
| C, then A | Only C → A and C 90 − 54 = 36 | None → Only C 54 − 36 = 18 |
| Average | (24 + 36) / 2 = 30 | (30 + 18) / 2 = 24 |
This leaf is fully accounted for: 36 + 30 + 24 = 90.
Add the four leaf explanations
| Leaf | Baseline | A | B | C |
|---|---|---|---|---|
| 10 | 3 | −1.5 | −1.5 | 0 |
| 30 | 3 | −7.5 | 4.5 | 0 |
| 50 | 10 | 3⅓ | 0 | −13⅓ |
| 90 | 36 | 30 | 0 | 24 |
| Total | 52 | 24⅓ | 3 | 10⅔ |
Negative entries account for leaves that lose weight. Revealing that Maya is Returning rules out the 30 leaf, for example. Adding the columns gives 52 + 24⅓ + 3 + 10⅔ = 90.
Separate the feature being revealed from the others
To extend the calculation to longer paths, write $z$ for a feature's multiplier while hidden and $o$ for its multiplier when revealed. On our 90-leaf path:
| Feature | Hidden: z | Revealed: o |
|---|---|---|
| A: Returning | 3/5 | 1 |
| C: High usage | 2/3 | 1 |
Revealing A changes only A's multiplier, from 3/5 to 1. The leaf value and C's current multiplier stay fixed:
The same reasoning applies to any feature j on any leaf path: multiply the leaf value $u$ by j's change $o_j-z_j$, then by the other features' multipliers. We only need an efficient way to average that last product over reveal orders.
Group the products by how many features came before j
Let $d$ be the number of distinct features on the path. For each of the other $d-1$ features, choose $z_i$ when hidden or $o_i$ when revealed. Groups with the same number of revealed features have the same Shapley weight, so we can add their products first.
Store those sums as the coefficients of a polynomial:
The product includes only the other features on this path. Selecting $z_i$ leaves feature i hidden; selecting $o_it$ reveals it. The power of $t$ counts the revealed features. Consequently, the coefficient $q_k$ of $t^k$ adds all products with exactly $k$ revealed features.
Feature j is equally likely to occupy any of the d positions. Given that k features precede it, each of the $\binom{d-1}{k}$ possible groups is equally likely. Each such group therefore gets weight $1/[d\binom{d-1}{k}]$. The weighted average of the other features' product is:
Multiply this average by the leaf value and j's multiplier change:
Apply the equation to the same 90 leaf
For A, the only other feature is C. Its factor is $2/3+t$, so $q_0=2/3$ and $q_1=1$. The two positions for A each have weight 1/2:
This is exactly the table's average, $(24+36)/2$. The polynomial has organized the same calculation by how many other features are already known.
Update the coefficient list without listing the groups
Start with the coefficient list [1]. Multiplying by one more factor $(z+ot)$ updates entry k as follows:
There are two ways to finish with k revealed features. Keep the new feature hidden and use an old group of size k, or reveal it and use an old group of size k−1. The equation adds both possibilities. Entries outside the old list are zero.
| Added factor | Coefficient list |
|---|---|
| None | [1] |
| A: 3/5 + t | [3/5, 1] |
| C: 2/3 + t | [2/5, 19/15, 1] |
The middle entry is $(3/5)\times1+1\times(2/3)=19/15$. It combines “only C revealed” and “only A revealed.” Every path update combines products this way, keeping one number for each group size.
Build the full product $P$ once. For a particular j, remove its factor to obtain $Q_j$. From $P=(z_j+o_jt)Q_j$, matching coefficients gives:
Here $p_k$ is a full-product coefficient. Removing A gives $q_0=(2/5)/(3/5)=2/3$ and $q_1=(19/15-2/3)/(3/5)=1$. We have recovered C's factor without rebuilding the product. This division assumes positive hidden fractions, as in our tree.
If a path tests the same feature twice, combine its multipliers
Knowing one feature's value answers every split that tests it. If two splits on the path both test j, combine their hidden fractions and their revealed fractions:
The combined revealed multiplier is 1 only if Maya's value satisfies both conditions. Otherwise it is 0. Use this combined pair as one factor in the polynomial. Counting the two splits as separate features would allow one occurrence to be known while the other remains hidden, which cannot represent knowing the input.
This is why d counts distinct features. In the recursive TreeSHAP implementation, an unwind removes the feature's earlier path entry and an extend inserts the combined entry.
Why this takes less work
A path's coefficient list grows one entry at a time. Building it takes $1+2+\cdots+d=O(d^2)$ work. Removing one factor and computing its weighted sum takes $O(d)$; repeating this for all d features also takes $O(d^2)$.
For T trees, at most L leaves per tree, and maximum path depth D, this gives $O(TLD^2)$ arithmetic operations for one explained row. The calculation stores sums by group size instead of evaluating every feature group separately.
Add tree contributions in the same way as tree predictions
The same addition rule used for leaves also applies to trees. If a model predicts $F(x)=b+\sum_t a_tf_t(x)$, then:
The constant b goes into the baseline. A forest average uses $a_t=1/T$; a boosted sum uses the weights in that sum. These equations hold on the additive output scale being explained.
We have now obtained the contribution formula and its efficient calculation. Both depend on the rule used when a feature is hidden. The next chapter changes that rule while keeping Maya, the ten customers, and the tree fixed.
The exact Python calculation implements the polynomial form above. The TreeSHAP paper and reference implementation express the path updates through extend and unwind operations.