Consistent feature attribution for tree ensembles
Scott M. Lundberg
SLUND 1@ CS . WASHINGTON . EDU
Paul G. Allen School of Computer Science, University of Washington, Seattle, WA 98105 USA

arXiv:1706.06060v6 [] 17 Feb 2018

Su-In Lee
SUINLEE @ CS . WASHINGTON . EDU
Paul G. Allen School of Computer Science and Department of Genome Sciences, University of Washington, Seattle, WA
98105 USA

Abstract
It is critical in many applications to understand
what features are important for a model, and why
individual predictions were made. For tree ensemble methods these questions are usually answered by attributing importance values to input
features, either globally or for a single prediction.
Here we show that current feature attribution
methods are inconsistent, which means changing the model to rely more on a given feature
can actually decrease the importance assigned
to that feature. To address this problem we develop fast exact solutions for SHAP (SHapley
Additive exPlanation) values, which were recently shown to be the unique additive feature
attribution method based on conditional expectations that is both consistent and locally accurate. We integrate these improvements into the
latest version of XGBoost, demonstrate the inconsistencies of current methods, and show how
using SHAP values results in significantly improved supervised clustering performance. Feature importance values are a key part of understanding widely used models such as gradient
boosting trees and random forests. We believe
our work improves on the state-of-the-art in important ways, and so impacts any current user of
tree ensemble methods.

1. Introduction
Understanding why a model made a prediction is important for trust, actionability, accountability, debugging, and
many other common tasks. To understand predictions from
tree ensemble methods, such as gradient boosting trees or

random forests, importance values are typically attributed
to each input feature. These importance values can be computed either for a single prediction, or an entire dataset to
explain a model’s overall behavior.
Concerningly, current feature attribution methods for tree
ensembles are inconsistent, meaning they can assign higher
importance to features with a lower impact on the model’s
output. This inconsistency effects a very large number of
users, since tree ensemble methods are widely applied in
research and industry.
Here we show that by connecting tree ensemble feature attribution methods with the recently defined class of additive feature attribution methods (Lundberg & Lee, 2017)
we can motivate the use of SHapley Additive exPlanation
(SHAP) values as the only possible consistent feature attribution method with desirable properties.
SHAP values are theoretically optimal but can be challenging to compute. To address this we derive exact algorithms
for tree ensemble methods that reduce the computational
complexity of computing SHAP values from exponential
to O(T LD2 ) where T is the number of trees, L is the maximum number of leaves in any tree, and D is the maximum
depth of any tree. By integrating this new algorithm into
XGBoost, a popular tree ensemble package, we demonstrate performance that enables predictions from models
with thousands of trees, and hundreds of inputs, to be explained in a fraction of a second.
In what follows we first discuss the inconsistencies of current feature attribution methods as implemented in popular
tree enemble software packages (Section 2). We then introduce SHAP values as the only possible consistent attributions (Section 3), and present Tree SHAP as a high speed
algorithm for estimating SHAP values of tree ensembles
(Section 4). Finally, we use a supervised clustering task
to compare SHAP values with previous feature attribution
methods (Section 5).

Consistent feature attribution for tree ensembles

(A)

(B)

(Fever = Yes, Cough = Yes)

(Fever = Yes, Cough = Yes)

Fever

Cough

No

Yes

Cough

No

Cough

Yes

Fever

Fever

No

Yes

No

Yes

No

Yes

No

Yes

0

0

0

100

0

0

10

110

output = [Cough & Fever]*100

output = [Cough & Fever]*100 + [Cough]*10

Attributions

Path (output)
SHAP (output)
Split count
Path (gain)
SHAP (gain)

Fever
25
37.5
1
33
50

Cough
50
37.5
2
67
50

Attributions

Inconsistency
Inconsistency

Fever
50
37.5
2
58
37

Cough
30
47.5
1
42
63

Figure 1. Two tree models meant to demonstrate the inconsistencies of current feature attribution methods. The Cough feature has a
larger impact on tree B, but is assigned less importance by all three standard methods. The “output” attributions explain the difference
between the expected value of the model output and the current output. The “gain” represents the change in the mean squared error over
the whole dataset between when no features are used and all features are used. All calculations assume a dataset (typically a training
dataset) perfectly matching the model and evenly spread among all leaves. Section 2 describes the standard “path” methods, while
Section 3 describes the SHAP values and their interpretation.

2. Current feature attributions are
inconsistent
Tree ensemble implementations in popular packages such
as XGBoost (Chen & Guestrin, 2016), scikit-learn (Pedregosa et al., 2011), and the gbm R package (Ridgeway,
2010), allow a user compute a measure of feature importance. These values are meant to summarize a complicated
ensemble model and provide insight into what features
drive the model’s prediction. Unfortunately the standard
feature importance values provided by all of these packages are inconsistent, this means that a model can change
such that it relies more on a given feature, yet the importance assigned to that feature decreases (Figure 1).
For the above packages, when feature importance values
are calculated for an entire dataset they are by default based
on the reduction of loss (termed “gain”) contributed by
each split in each tree of the ensemble. Feature importances are then defined as the sum of the gains of all splits
for a given feature as described in Friedman et al. (Breiman
et al., 1984; Friedman et al., 2001).
Methods computing feature importance values for a single prediction are less established, and of the above packages, only the most recent version of XGBoost supports
these calculations natively. The method used by XGBoost
(Saabas) is similar to the classical dataset level feature importance calculation, but instead of measuring the reduction of loss it measures the change in the model’s output.

Both current feature attribution methods described above
only consider the effect of splits along the decision path, so
we will term them path methods. Figure 1 shows the result
of applying both these methods to two simple regression
trees. For the gain calculations we assume equal coverage
of each of the four tree leaves, and perfect regression accuracy. In other words, an equal number of dataset points fall
in each leaf, and the label of those points is exactly equal
to the prediction of the leaf. The tree in Figure 1A represents a simple AND function, while the tree in Figure 1B
represents the same AND function but with an additional
increase in predicted value when Cough is “Yes”.
The point of Figure 1 is to compare feature attributions between A and B, where it is clear that Cough has a larger impact on the model in B than the model in A. As highlighted
below each tree, we can see that current path methods (as
well as the simple split count metric) are inconsistent because they allocate less importance to Cough in B, even
though Cough has a larger impact on the output of the tree
in B. The “output” task explains the change in model output from the expected value to the current predicted value
given Fever and Cough. The “gain” explains the reduction
in mean squared error contributed by each feature (assuming a dataset as described in the previous paragraph). In
contrast to current approaches, the SHAP values (described
below) are consistent, even when the order in which features appear in the tree changes.

Consistent feature attribution for tree ensembles

3. SHAP values are the only consistent feature
attributions
It was recently noted that many current methods for interpreting machine learning model predictions fall into the
class of additive feature attribution methods (Lundberg &
Lee, 2017). This class covers all methods that explain a
model’s output as a sum of real values attributed to each
input feature.
Definition 1 Additive feature attribution methods have
an explanation model that is a linear function of binary
variables:
M
X
g(z 0 ) = φ0 +
φi zi0 ,
(1)
i=1

where z 0 ∈ {0, 1}M , M is the number of input features,
and φi ∈ R.
The zi0 variables typically represent a feature being observed (zi0 = 1) or unknown (zi0 = 0), and the φi ’s are
the feature attribution values.
As previously described in Lundberg & Lee, an important
attribute of the class of additive feature attribution methods is that there is a single unique solution in this class
with three desirable properties: local accuracy, missingness, and consistency (Lundberg & Lee, 2017). Local accuracy states that the sum of the feature attributions is equal to
the output of the function we are seeking to explain. Missingness states that features that are already missing (such
that zi0 = 0) are attributed no importance. Consistency
states that changing a model so a feature has a larger impact
on the model, will never decrease the attribution assigned
to that feature.
In order to evaluate the effect missing features have on a
model f , it is necessary to define a mapping hx that maps
between the original function input space and the binary
pattern of missing features represented by z 0 . Given such a
0
mapping we can evaluate f (h−1
x (z )) and so calculate the
effect of observing or not observing a feature (by setting
zi0 = 1 or zi0 = 0).
0
SHAP values define fx (S) = f (h−1
x (z )) = E[f (x) | xS ]
where S is the set of non-zero indexes in z 0 (Figure 2), and
then use the classic Shapley values from game theory to
attribute φi values to each feature:

φi =

X
S⊆N \{i}

|S|!(M − |S|! − 1)
[fx (S ∪ {i}) − fx (S)]
M!
(2)

where N is the set of all input features.
The SHAP values are the only possible consistent, lo-

cally accurate method that obeys the missingness property
and uses conditional dependence to measure missingness
(Lundberg & Lee, 2017). This is strong motivation to use
SHAP values for tree ensemble feature attribution, particularly since current tree ensemble feature attribution methods already obey all of these properties except consistency.
This means that SHAP values provide a strict theoretical
improvement over existing approaches by eliminating the
unintuitive consistency problems shown in Figure 1.

4. Tree SHAP: Fast SHAP value computation
for decision trees
Despite the compelling theoretical advantages of SHAP
values, their practical use is hindered by two problems:
1. The challenge of estimating E[f (x) | xS ] efficiently.
2. The exponential complexity of Equation 2.
Here we focus on tree models and propose fast SHAP value
estimation methods specific to trees and ensembles of trees.
We start by defining a straightforward, but slow, algorithm
in Section 4.1, then present the much faster and more complex Tree SHAP algorithm in Section 4.2.
4.1. Estimating SHAP values directly in O(T L2M ) time
If we ignore computational complexity then we can compute the SHAP values for a decision tree by estimating
E[f (x) | xS ] and then using Equation 2 where fx (S) =
E[f (x) | xS ]. For a tree model E[f (x) | xS ] can be estimated recursively using Algorithm 1, where v is a vector
of node values, which takes the value internal for internal nodes. The vectors a and b represent the left and right
node indexes for each internal node. The vector t contains
the thresholds for each internal node, and d is a vector of
indexes of the features used for splitting in internal nodes.
The vector r represents the cover of each node (how many
data samples fall in that subtree).
4.2. Estimating SHAP values in O(T LD2 ) time
Here we propose a novel algorithm to calculate the same
values as in Section 4.1, but in polynomial time instead
of exponential time. Specifically, we propose an algorithm that runs in O(T L log2 L) for balanced trees, and
O(T LD2 ) for unbalanced trees.
The general idea of the polynomial time algorithm is to recursively keep track of what proportion of all possible subsets flow down into each of the leaves of the tree. This
is similar to running Algorithm 1 simultaneously for all
2M subsets S in Equation 2. It may seem reasonable to
simply keep track of how many subsets (weighted by the

Consistent feature attribution for tree ensembles

Figure 2. SHAP (SHapley Additive exPlanation) values explain the output of a function as a sum of the effects φi of each feature being
introduced into a conditional expectation. Importantly, for non-linear functions the order in which features are introduced matters, so
SHAP averages over all possible orderings. Proofs from game theory show this is the only possible consistent and locally accurate
approach. In contrast, standard path methods for tree ensembles (Section 2) are similar to using a single ordering defined by a tree’s
decision path.

Algorithm 1 Estimating E[f (x) | xS ]
procedure EXPVALUE(x, S, tree = {v, a, b, t, r, d})
procedure G(j, w)
if vj 6= internal then
return w · vj
else
if dj ∈ S then
return xdj ≤ tj ? G(aj , w) : G(bj , w)
else
return G(aj , wraj /rj ) + G(aj , wraj /rj )
end if
end if
end procedure
return G(1, 1)
end procedure

cover splitting of Algorithm 1) pass down each branch of
the tree. However, this combines subsets of different sizes
and so prevents the proper weighting of these subsets, since
the weights in Equation 2 depend on |S|. To address this
we keep track of each possible subset size during the recursion. The EXTEND method in Algorithm 2 grows all
these subsets according to given fraction of ones and zeros, while the UNWIND method reverses this process. The
EXTEND method is used as we descend the tree. The UNWIND method is used to undo previous extensions when
we split on the same feature twice, and to undo each extension of the path inside a leaf to correctly compute the
weights for each feature in the path.
In Algorithm 2, m is the path of unique features we have
split on so far, and contains four attributes: d the feature
index, z the fraction of “zero” paths (where this feature is
not in the set S) that flow through this branch, o the fraction of “one” paths (where this feature is in the set S) that
flow through this branch, and w which is used to hold the
proportion of sets of a given cardinally that are present. We
use the dot notation to access these members, and for the
whole vector m.d represents a vector of all the feature indexes. (For code see https://github.com/slundberg/shap)

5. Supervised clustering experiments
One intriguing use for prediction level feature attributions
is what we term “supervised clustering”, where instead of
using an unsupervised clustering method directly on the
data features, you run clustering on the feature attributions
(Lundberg & Lee, 2016).
Supervised clustering naturally handles one of the most
challenging problems in unsupervised clustering: determining feature weightings (or equivalently, determining a
distance metric). Many times we want to cluster data using features with very different units. Features may be in
dollars, meters, unit-less scores, etc. but whenever we use
them as dimensions in a single multidimensional space it
forces any distance metric to compare the relative importance of a change in different units (such as dollars vs. meters). Even if all our inputs are in the same units, often
some features are more important than others. Supervised
clustering uses feature attributions to naturally convert all
the input features into values with the same units as the
model output. This means that a unit change in any of the
feature attributions is comparable to a unit change in any
other feature attribution. It also means that fluctuations in
the feature values only effect the clustering if those fluctuations have an impact on the outcome of interest.
Here we compare feature attribution methods by applying
supervised clustering to disease sub-typing, an area where
unsupervised clustering has contributed to important discoveries. The goal of disease sub-typing is to identify subgroups of patients that have similar mechanisms of disease (similar reasons they are sick). Here we consider
Alzheimer’s disease where the predicted outcome is the
CERAD cognitive score (Mirra et al., 1991), and the features are gene expression modules (Celik et al., 2014).
By representing the positive feature attributions as red bars
and the negative feature attributions as blue bars (as in Figure 2), we can stack them against each other to visually
represent the model output as their sum. Figure 3 does
this vertically for each participant. The explanations for
each participant are then stacked horizontally according the

Consistent feature attribution for tree ensembles

Samples (patients) ordered by explanation similarity

Model output (Alzheimer’s score)

(A) Path explanations

Samples (patients) ordered by explanation similarity

Model output (Alzheimer’s score)

(B) SHAP explanations

Figure 3. SHAP feature attributions produce better clusters than standard path attributions for supervised clustering of 518 participants
in an Alzheimer’s research study. An XGBoost model with 300 trees of max depth six was trained on 200 gene expression module
features using a shrinkage factor of η = 0.01. This model was then used to predict the CERAD cognitive score of each participant. Each
prediction was explained, and then clustered using hierarchical agglomerative clustering (imagine a dendrogram joining the samples
above each plot). Red feature attributions push the score higher, while blue feature attributions push the score lower. A) The clusters
formed with standard “path” explanations from XGBoost. B) Clusters using our Tree SHAP XGBoost implementation.

Consistent feature attribution for tree ensembles

Algorithm 2 Tree SHAP
procedure TS(x, tree = {v, a, b, t, r, d})
φ = array of len(x) zeros
procedure RECURSE(j, m, pz , po , pi )
m = EXTEND(m, pz , po , pi )
if vj 6= internal then
for i ← 2 to len(m) do
w = sum(UNWIND(m, i).w)
φmi = φmi + w(mi .o − mi .z)vj
end for
else
h, c = xdj ≤ tj ? (aj , bj ) : (bj , aj )
iz = io = 1
k = FINDFIRST(m.d, dj )
if k 6= nothing then
iz , io = (mk .z, mk .o)
m = UNWIND(m, k)
end if
RECURSE(h, m, iz rh /rj , io , dj )
RECURSE(c, m, iz rc /rj , 0, dj )
end if
end procedure
procedure EXTEND(m, pz , po , pi )
l = len(m) + 1
m = copy(m)
ml+1 .(d, z, o, w) = (pi , pz , po , l = 0 ? 1 : 0)
for i ← l − 1 to 1 do
mi+1 .w = mi+1 .w + po mi .w(i/l)
mi .w = pz mi .w[(l − i)/l]
end for
return m
end procedure
procedure UNWIND(m, i)
l = len(m)
n = ml .w
m = copy(m1...l−1 )
for j ← l − 1 to 1 do
if mi .o 6= 0 then
t = mj .w
mj .w = n · l/(j · mi .o)
n = t − mj .w · mi .z((l − j)/l)
else
mj .w = (mj .w · l)/(mi .z(l − j))
end if
end for
for j ← i to l − 1 do
mj .(d, z, o) = mj+1 .(d, z, o)
end for
return m
end procedure
RECURSE(1, [], 1, 1, 0)
return φ
end procedure

Figure 4. A quantitative performance measure of the clusterings
shown in Figure 3. If all 518 samples are placed in their own
group, and each group predicts the mean value of the group, then
the R2 value (the proportion of outcome variance explained) will
be 1. If groups are then merged one-by-one the R2 will decline
until when there is only a single group it will be 0. Hierarchical clusterings that well separate the outcome value will retain a
high R2 longer during the merging process. Here unsupervised
clustering did no better than random, supervised clustering with
the XGBoost “path” method did significantly better, and SHAP
values significantly better still.

leaf order of a hierarchical clustering. This groups participants with similar predicted outcomes and similar reasons
for that predicted outcome together. The clearer structure
in Figure 3B indicates the SHAP values are better feature
attributions, not only theoretically, but also practically.
The improvement in clustering performance seen in Figure
3 can be quantified by examining how well each clustering
explains the variance of the CERAD score outcome. Since
hierarchical clusterings encode many possible groupings,
we plot in Figure 4 the change in the R2 value as the number of groups shrinks from one group per sample (R2 = 1),
to a single group (R2 = 0).

6. Conclusion
Here we have shown that classic feature attribution methods for tree ensembles are inconsistent, meaning they can
assign less importance to a feature when the true effect
of that feature increases. In contrast, SHAP values were
shown to be the unique way to consistently attribute feature importance. By deriving fast algorithms for SHAP values and integrating them with XGBoost, we make them a
practical replacement for previous methods. Future directions include deriving fast dataset-level SHAP algorithms
for gain (as opposed to the instance-level algorithm presented here), and integrating SHAP value algorithms into
the released versions of common packages.

Consistent feature attribution for tree ensembles

Acknowledgments
We would like to thank Gabriel Erion for suggestions that
lead to a simplified algorithm, as well as Jacob Schreiber
and Naozumi Hiranuma for providing helpful input.

References
Breiman, Leo, Friedman, Jerome, Stone, Charles J, and
Olshen, Richard A. Classification and regression trees.
CRC press, 1984.
Celik, Safiye, Logsdon, Benjamin, and Lee, Su-In. Efficient dimensionality reduction for high-dimensional network estimation. In International Conference on Machine Learning, pp. 1953–1961, 2014.
Chen, Tianqi and Guestrin, Carlos. Xgboost: A scalable
tree boosting system. In Proceedings of the 22Nd ACM
SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 785–794. ACM, 2016.
Friedman, Jerome, Hastie, Trevor, and Tibshirani, Robert.
The elements of statistical learning, volume 1. Springer
series in statistics Springer, Berlin, 2001.
Lundberg, Scott and Lee, Su-In. An unexpected unity
among methods for interpreting model predictions.
arXiv preprint arXiv:1611.07478, 2016.
Lundberg, Scott and Lee, Su-In. A unified approach
to interpreting model predictions.
arXiv preprint
arXiv:1705.07874, 2017.
Mirra, Suzanne S, Heyman, A, McKeel, D, Sumi, SM,
Crain, Barbara J, Brownlee, LM, Vogel, FS, Hughes,
JP, Van Belle, G, Berg, L, et al. The consortium to
establish a registry for alzheimer’s disease (cerad) part
ii. standardization of the neuropathologic assessment of
alzheimer’s disease. Neurology, 41(4):479–479, 1991.
Pedregosa, Fabian, Varoquaux, Gaël, Gramfort, Alexandre, Michel, Vincent, Thirion, Bertrand, Grisel, Olivier,
Blondel, Mathieu, Prettenhofer, Peter, Weiss, Ron,
Dubourg, Vincent, et al. Scikit-learn: Machine learning in python. Journal of Machine Learning Research,
12(Oct):2825–2830, 2011.
Ridgeway, Greg. Generalized boosted regression models. documentation on the r package gbm, version 1.6–3,
2010.
Saabas,
Ando.
Interpreting
random
forests.
http://blog.datadive.net/
interpreting-random-forests/. Accessed:
2017-06-15.

