From global to local MDI variable importances for random forests and when they are Shapley values
Authors: Antonio Sutera
Gilles Louppe
Van Anh Huynh-Thu
Louis Wehenkel
Pierre Geurts
Venue: NeurIPS 2021 Poster (2021)
Keywords: random forests
variable importances
shapley values
feature ranking
information theory
explainability
interpretable machine learning

Abstract: Random forests have been widely used for their ability to provide so-called importance measures, which give insight at a global (per dataset) level on the relevance of input variables to predict a certain output. On the other hand, methods based on Shapley values have been introduced to refine the analysis of feature relevance in tree-based models to a local (per instance) level. In this context, we first show that the global Mean Decrease of Impurity (MDI) variable importance scores correspond to Shapley values under some conditions. Then, we derive a local MDI importance measure of variable relevance, which has a very natural connection with the global MDI measure and can be related to a new notion of local feature relevance. We further link local MDI importances with Shapley values and discuss them in the light of related measures from the literature. The measures are illustrated through experiments on several classification and regression problems.

From global to local MDI variable importances for random forests and when they are Shapley values
Antonio Sutera," Gilles Louppe, Van Anh Huynh-Thu, Louis Wehenkel, Pierre Geurts Dept. of EE & CS, University of Liège, Belgium
{a w.s.sutee.g..uppp.. vahuynh, wehenkel, , p-uuurts))uullgge be
Abstract
Random forests have been widely used for their ability to provide so-called impor- lance measures, which give insight at global (per dataset) level on the relevance of input variables to predict a certain output. On the other hand, methods based Shapley values have been introduced to refine the analysis of feature relevance in tree-based models to a local (per instance) level. this context, we first show that the global Mean Decrease of Impurity (MDI) variable importance scores cor- respond to Shapley values under some conditions. Then, we derive local MDI importance measure of variable relevance, which has very natural connection with the global MDI measure and can be related to a new notion of local feature relevance. We further link local MDI importances with Shapley values and dis- cuss them in the light of related measures from the literature. The measures are illustrated through experiments several classification problems.
1
Motivation
While research in machine learning (ML) often focuses on predictive accuracy, another important topic concerns the interpretation of ML models and their predictions. Interpreting model helps to uncover the mechanisms captures (e.g., biomarkers useful to diagnose a disease), and to explain its predictions (e.g., why particular patient is diagnosed healthy sick). The latter becomes essential when a ML prediction may impact one's life, and as a way of checking the trustworthiness of a ML model (e.g., to identify unwanted biases). Common interpretation tools include variable importance measures that assess which, and to which extent, variables are important for model. They help to understand how the model works, and gain insight on the underlying modelled mechanism.
In tree-based methods, such as Random forests [Breiman, 2001], feature importance scores can be derived as a low-cost by-product of the learning step. Given their extensive use in applied research, tree-based importance measures have been studied both empirically (see, e.g., Strobl et al. [2007], Archer and Kimes [2008], Genuer al. [2010], Auret and Aldrich [2011]) and theoretically (see, e.g., Ishwaran et al. [2007], Louppe et al. [2013], Louppe [2014], Sutera et al. [2018], et al. [2019], Sutera [2019], Scornet [2020]). Assuming sufficiently large learning these works showed that importance measures have desirable properties, such as consistency with respect the notion of feature relevance. They also analyzed the impact of learning meta-parament (e.g., randomization level, tree depth, ensemble size) on such properties. While standard importance measures evaluate the global importance of a feature the level of dataset, several works proposed new approaches based on Shapley values to derive local scores reflecting the importance of a feature for given prediction (e.g., Neto and Paulovich [2020], Lundberg et al. [2020], Izza al. [2020]).
and number of trees,
The contribution the present work in this context two-fold. First, we show that the standard mean decrease of impurity (MDI) measure when derived from totally randomized trees and in asymptotic
"Correspondngg author. Email address: sutera intera.antonio@ee @aaiiio@@mmll cmm
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

conditions (similar to those used to show the consistency with respect to the relevance) are Shapley values, and therefore have the same properties as any other importance measures based on these values (Section 3). Secondly, we propose a new local MDI measure for tree-based ensemble models to measure feature relevance locally, which naturally derives from global MDI and corresponds to Shapley values in the same conditions (Section 4). Global and local MDI are compared against other Shapley-value based scores, both conceptually (Section 5) and empirically (Section 6).
Background
In what follows, we consider standard supervised learning setting and denote by V [X, the set of p input variables, and by Y the output.
Game theory and Shapley value. We only remind here concepts and results that are useful later in the paper. Notations below are mostly adapted from [Besner, 2019].
In game theory, TU-game (V, (i.e.. cooperative game with transferable utilities) is defined by finite set of players V
:......;ppp'' and characteristic (or coalition) function v E V 2 + R. with v0) = 0, that maps a coalition (i.e., set) of players to a real number representing the outcome or gain of a game (see, e.g., [van den Brink et al., 2015]). A TU-game (V,v) v) is monotonic vSS) < (T) if C C V. Let us denote by V-m the set V \ (X }. The marginal contribution MC (S) of player X,, V for S S V is defined by MC (5) = v(5 J (Xm]) - v(S). A player Xm, E V is called null player if MC (S) = 0 for all S S V-m. Two players X, and X; are said to be symmetric whenever vSS U (X+)) v(S (X,)) for all coalitions $ V
A TU-vatee P. V + IR is function that assigns to any player Xm V and any function (E V is omitted in the rest) a value, denoted p (X,,) E IR also known as its payeff. reflecting its contribution in the game (V, v). Several properties or axioms for TU-values have been defined in the literature that are expected to be satisfied in practical contexts (see [Besner, 2019] for a more exhaustive list):
Efficiency: For all v. Σx.,ev &o (x.m)) v(V). The TU-value divides the total gain (i.e., gain when all players are involved) among all players in an additive way.
Symmetry: For all v, (X(,)) = (x(X) if players X, and X3 are symmetrie. Two players of equal contributions in every game (i.e., with every coalition S) should get the same value.
Null player: For all v, (x(( = 0 if X, is a null player. A null player should get a zero payoff-
Strong monotonocity': For all v. w and Xm E V such that MC;, (S) 2 MOW for all S C V-m we have (X,) 2 (X..) If player's marginal contributions are greater (or equal) in a game than in another in all coalitions, then its payoff in this game should not be lower than in the other.
Specific forms of TU-value have been studied in the literature from the point of view of which axioms they satisfy and how uniquely they are defined by these axioms. As one of the most prominent results, it has been shown [Young. 1985] that the only TU-value that satisfies Efficiency, Symmetry, Null player', and Strong monotonicity is the Shapley value othh defined by [Shapley, 1953]:
18
|S| 1)! MC,,(S). p!
(Xm)=
Σ SCV-m
Other equivalent formulations of the Shapley value, as well as other axiomatisations of this value, have been proposed in the literature. Axiomatisations of other, typically more general, sets of TU-values are also available (see [Besner, 2019] for a recent and exhaustive discussion of this topic).
Feature relevance. In the feature selection literature, common definition of the relevance of feature is as follows [Kohavi et al., 1997]:
A variable X.. E V is relevant to Y (with respect to V) iff AB c V : Xm / Y|B. A variable Xm irrelevant if it is not relevant. Relevant variables can be further divided into two categories according to their degree of relevance [Kohavi et al., 1997]: A variable Xm is strongly relevant
We use the same notations for the (set of) players for (set of) input features, the two will coincide later. II the MI. literature, strong monotonicity is often called consistency [I lundberg and Lce, 2017]. 'Actually, the Null player property is not required as it can be derived from strong monotonicity.

---

to Y (with respect to V) iff Y + Xm/V-"/ A variable X is weakly relevant if it is relevant but not strongly relevant. Strongly relevant variables thus convey information about the output that no other variable (or combination of variables) in V conveys.
Decision trees and forests. Each interior node of a decision tree [Breiman al., 1984] is labelled with a test based on some input and each leaf node is labelled with a value of the output. The tree is typically grown from a learning sample of size N drawn from P(V, Y) using a procedure that recursively partitions the samples at each node / into two child nodes (l2 and (g). The test 8t used to partition the samples at node t the one that maximises the mean decrease of some node impurity measure i(.) (e.g., the Shannon entropy. the Gini index or the variance of Y): Ai(s, = p(ta) p(ta)i((R)) i(tR), where p(tz,) and p((R) are the proportions of samples that fall in p(a
i(t) p(ty)
p(t) i(tz,) p(t,)
nodes ir and Ln respectively. Single decision trees suffer from high variance that very efficiently reduced by building instead an ensemble of randomized trees and aggregating their predictions. Popular methods are Breiman [2001]'s Random Forests that build each tree from different bootstrap sample with local random selection of K(S p) variables at each node from which to identify the best split, and Geurts et al. [2006]'s Extra-Trees which skip bootstrapping and additionally randomly select the split values. Following Geurts et al. [2006], Louppe et al. [2013], ensemble of randomized trees grown with the value of the randomization parameters K set to 1 will be called Totally randomized trees.
Mean decrease impurity importance. Given an ensemble of trees, several methods have been proposed to evaluate the (global) importance of variables for predicting the output [Breiman et al., 1984, Breiman, 2001]. This paper focuses on the Mean Decrease of Impurity (MDI) importance. Given tree T, the MDI importance of a variable Xm for predicting the output Y is defined as
Imp(X Xm, T)
Σ NET:M(S)) -
p(1)Ai(8t,()
where the sum is over all interior nodes t in T. v(s:) denotes the variable tested at node t, and p(t) is the fraction of samples reaching node t. Imp(Xm: T) is thus the (weighted) sum of impurity decreases over all nodes where Xm is used to split. The MDI importance of X,, derived from forests of Ny trees is then the average of Imp(Xm, T') over all trees:
Imp(X,))
Nr Σ T
Imp((mm T).
(3)
While this measure was initially proposed as a heuristic, Louppe et al. [2013] characterise it theo- retically under the following conditions: (1) all input variables and the output are categorical (not necessarily binary) (2) trees use so-called exhaustive splits", and (3) impurity is measured by Shannon entropy Later, we will refer to these conditions collectively as the categorical setting.
In the categorical setting, Louppe et al. [2013] (Thm. 1) show that for totally randomized trees (i.e., K 1) and in asymptotic conditions (i.e. assuming Nr - oo and learning sample of infinite size), the MDI importance, denoted Imp x is given by:
00 (Xpm)(Xm))))
Σ ppp-
Σ
I(Y;Xm!
Xm IB),
BEP((--")
where Pa (V-m) is the set of subsets of V-m of cardinality k, and I(Y; (m::X||B) is the conditional mutual information of X,, and Y given the variables in B. They also show that the sum of the MDI importances of all variables is equal to the mutual information between all input features and the output (Louppe et al., 2013, Thm. 2]:
Σ Imp (Xm) V):
(5)
A direct consequence of Equation 4 is that a variable X. is irrelevant iff Imp (Xm) = 0, which makes the MDI importance a sensible measure to identify relevant variables.
$ 'Each node split into |X]] sub-trees, one for each of the | different values the split variable Xt. "A short introduction to information theory and the related notations used in the paper is provided in Appendix G.
3

---

3 Global MDI importances are Shapley values
In this section, we revisit the theoretical analysis of Louppe et al. [2013] and Sutera [2019] in the light of TU-games and TU-values, focusing on the categorical setting and asymptotic conditions adopted by these authors. We show in Section 3.1 that MDI importances computed from totally randomized trees can be interpreted as the Shapley value for a particular TU-game and we then discuss in Section 3.2 the case of non totally randomized trees (i.e., K > 1).
3.1 Totally randomized trees
Let us consider TU-game (V. v). where V is the set of variables and the coalition function is
the mutual information v'.) :.). Since (0) = I(Y;)) 0. this is valid TU-game. This SIS) 2 I(Y;)) as soon as
TU-game is monotonic since we have I(;;T) = I(Y; +(Y; +) S S S V (using the chain rule and the positivity of the conditional mutual information). Marginal contributions for u can be rewritten as:
MCC, (S) v(S (X...)) v(S) I( I(Y; -
(6)
using the definition of (conditional) mutual information. A null player is thus defined as variable Xm such that MCM, (S) I(Y; X(m:X 0 for all S _ V-m This definition exactly coincides with the definition of an irrelevant variable (Section 2), since Xm.))) = 0 is equivalent to Y I. Xm SS. Two variables X; and X, are symmetric whenever v(S U (X;)) e(S (Xz}) for all S S V-ij, which is equivalent to I [Y; (X|S) I(Y; (Xys)) for all S C VVW,, X and X; bring the same information about in all contexts S.
With this definition, the following theorem shows that MDI importance of totally randomized trees corresponds to the Shapley value for this TU-game:
Theorem 1. (MDI are Shapley values) For all feature Xm E V.
x = = (Xm),
where 5h is the Shapley value with v(S) I(Y:))
The proof of this theorem follows from a direct comparison of Equations 1 and
Given this result, the four axioms that uniquely defines Shapley values are obviously satisfied. They translate into the following properties of the importances Imp
Efficiency: Σmm1 Imp (X,)) = v(V) I(Y; V). which states that MDI importances decompose, in an additive way, the mutual information XI,; Xp). This results is identical to Equation 5.
Symmetry: If X; and X; are symmetric, then Imp (X,) Impo (X²). This property is easy to
check knowing that [(;; S'S (X.)) = I(Y;5 J ( (X,}) implies that 7(Y; X,(S) = TY;; X,|S) and therefore swapping X, and X, in Equation would keep all terms of the sum unchanged.
Null player: If Xm, is a null player, i.e., an irrelevant variable, then Imp, (Xm) = 0. Note that Louppe et al. [2013] actually showed stronger result, stating in addition that Imp (X...) 0 only if X,, is irrelevant to Y.
Let assume two outputs Yi and Yg. Strong monotonicity says that if for all feature subsets S C V- I(Y1; Xm IS) 2 ((Y; (S), then we have Imp (Xm) 2 Imp ( (Xm)). This property states that if variable brings more information about Y1 than about Y/ all contexts S, it is more important to Y1 than to Y2.
Strong monotonicity:
The link between MDI importance and Shapley value shows that, in the finite setting, standard MDI importances from totally randomized trees compute an approximation of the Shapley values (for I(Y; V)), at least in the categorical setting.. MDI importance will be compared with other measures from the literature that explicitly seek to estimate the same quantities in Section 5.
7 TTe proofs theorems are Appendix A.
For example, in the context of an ensemble of binary decision trees. MDI importance measure does not estimate the same quantities as in the categorical setting [Louppe, 2014, Sutera, 2019].

---

3.2 Non totally randomized trees
When K > 1, K variables are randomly picked at each node and the best split, in terms of impurity reduction, among these K variables is selected to actually split the node. Because several variables then compete for each split, some variables might be never (or less often) selected if there are other variables providing larger impurity decreases. These masking effects will impact the properties of the
MDI importances. Let denote by Imp K (Xm) (Xm) the importance of Xm derived from randomized trees built with a given value of K in asymptotic conditions. When K > 1, Imp (Xm) can no longer be decomposed as in Equation 4, as some XX; [S) terms will not be included in the sum or with a weight different from the one in Equation 4. Actually, although Imp K attributes payoff to each variable in V, it can not be interpreted as TU-value for the TU-game defined by (V, with v1()) = .). Indeed, its computation requires to have access to conditional mutual information of the form [(; S 8) for all coalition S but also for all set of values of variables in S and the latter can not be derived from the knowledge only of I(; 5) for all S.
The efficiency and null player conditions are however still satisfied by x:
Efficiency: Louppe al. [2013] showed that Σ Imp (Xm) v(S) I(Y;V) for all K as soon as the trees are fully developed.
Null player If Xm a null player (i.e., an irrelevant variable), then Imp (X,,) [Louppe et al., 2013]. Note that Imp (Xm) 0 is however not anymore a sufficient condition for Xm, to be irrelevant. It can be shown however that a strongly relevant variable X,,, will always be such that Imp K (Xm) > O whatever K [Sutera et al., 2018].
Symmetry is not necessarily satisfied however, since I(Y; xX (S) for all S C V does not ensure that [Y; X,|S = s) = ;(Y;; = s) for all s, which would be required for the feature to be fully interchangeable when K > 1. Similarly, strong monotonieity is not satisfied either for Imp as shown in Example in Appendix B.
Note that as discussed in [Louppe et al., 2013], the loss of several properties when K > 1 should not preclude using Imp K an importance measure in practice. In finite setting, using K > 1 may still be a sound strategy to guide the choice of the splitting variables towards the most impactful ones during tree construction and therefore result in more statistically efficient estimates.
4 Local MDI importances
So far, MDI importances are global, in that they assess the overall importance of each variable independently of any test instance. An important literature has emerged in the recent year that focuses on local importance measures that assess the importance of variable locally, i.e., for a specific instance. In Section 4.1, we define a novel local MDI-based importance measure. We highlight the main properties of this measure and show in particular that it very naturally decomposes the standard global MDI measure. In Section 4.2, we show, in the categorical setting, that the asymptotic analysis of global MDI can be extended to the local MDI, which allows us, in Section 4.3 to show that local MDI importances are also Shapley values for specific characteristic function in the case of totally randomized trees. Finally, in Section 4.4, we propose a local adaptation of the notion of feature relevance and link it with the local MDI measure.
4.1 Definition and properties
Let us denote by x = (II,..., ., =ppT" given instance of the input variables, with 2y the value of variable X,. In what follows, we will further denote by æs given set of values for the variables in subset C V (in particular, T)11) xz)).
Definition 1. (Local MDI) The local MDI importance Imp(Xm, x) of a variable Xm with respect to Y for a given instance x is defined as follows
(X x) = NT
Σ T
i(t) i(tem)
(8)
(ET:((s)= Awet
5

---

where the outer sum is over the Nr trees of the ensemble, the inner sum is over all nodes that are traversed by a and where Xm used to split, t.m is the successor of node followed by æ in the tree (corresponding to X -m)) and i(.) is the impurity function.
This general measure quantifies how important is feature X to predict the output of the test example represented by its input features. It collects all differences i(t) i(t....) along all paths traversed by example æ in the ensemble. In practice this can be implemented very efficiently at no additional cost with respect the computation of prediction, as soon all impurities, computed training time, are stored at tree nodes.
The intuition behind this measure is that variable is important for sample if it leads to important reductions of impurity along the paths traversed by æ. Note that unlike global MDI, local MDI can be negative, the impurity can increase from one node one of its successors. A variable of negative importance for a given sample æ is thus such that, in average over all paths traversed by æ; actually increases the uncertainty about the output (because it helps for predicting the output of other instances).
A natural link between local and global MDI is given by the following result:
Imp(Xm) = N
Imp( Xm, x'),
where {xx,, vy"..... ... (x=,, )) ensemble of trees. This result can be shown easily by combining the definitions in Equations 2 and 8 of global and local MDI respectively. Local MDI thus a way to decompose the global MDI over all training examples.
is the learning sample of N examples that was used grow the
4.2 Asymptotic analysis
In the categorical setting and asymptotic conditions, the decomposition in Equation 4 for totally randomized trees can be adapted the local MDI measure, denoted Imp (Xm;
Theorem 2. (Asymptotic local MDI) The local MDI importance Imp (X,: (X, of a variable X with respect to Y for a given sample a computed with an infinite ensemble of fully developed totally randomized trees and an infinitely large training sample
Imp (Xm, x.)
Σ BEP(V-M)
H(Y =n) H(Y Bn, Xm Im) (10)
Ch Cp k=0
where H-Yl-) is the conditional entropy of Y. Similarly as in the finite setting, Imp on (Xm, x) can be negative, since the difference HY = xB) - HH B TB, Xm = Fm) is not always positive. Example in Appendix B illustrates such a situation.
In asymptotic condition, the decomposition in Equation furthermore becomes:
Imp (Xm.)
Σ P(V 1mp (Xm, x), æEV
(11)
where the sum is over all possible input combinations. Combined with 5, this leads to the following double decomposition (over features and instances) of the information I(V:)):
I(V;Y) =
P(V = x xmppmmpmpppp.. (Xm, x).
(12)
ØEV
4.3 Local MDI importances are Shapley values
Let us define a local characteristic function (So H(Y H(Y = æs)) which measures the decrease uncertainty (i.e., the amount information) about the output Y when the variables in S are known to be Øs. This characteristic function is thus parameterized by The proof of

---

Theorem can be adapted to the decomposition in Equation 10 to show that local MDI importances of totally randomized trees in asymptotic conditions are Shapley values with respect to (::
Impa0 20 (Xm: a) = Sh
(.:a)) (Xm)
(13)
As consequence, Imp xc (Xm m. x) satisfies the Shapley value properties at any point i.e.:
Efficiency: Vloc (V: x) H() H(Y x) Em Imp (Xm. x). This is in accordance
with the decomposition in Equation 12, since ΣæEy P(V = x Biocl (V;z) Ezev P(V
(VY - H(Y V =)) = Y(
Symmetry: If X; and X, are such that HY) HY|S x; = =z;) H() HY|S
Es, X3 = z2) for every S - V-Hj, then Imp (X,, = Imp x).
Null player If X; is such that HYYSS = æs, X. Im) ( S x.5) for all S C V-m then Imp (X,, x) =0. O.
Strong monotonicity: Assuming two outputs Y1 and Y2, if (Y =zs) H = xm
Tm) 2 HY2 = xs) HY = æg, Xm = Im) for all S _ V V- then we have
Imp Y1 (Xm, x) 2 Imp (Xm. x).
As in the case of global MDI, using non totally randomized trees (K > 1) will make local MDI to depart from the Shapley values, because of masking effects. Actually, local MDI importances will again not correspond to TU-values for (loe(=;x) since they are not uniquely defined by (+oc(;;)) Indeed, tree splits along the paths traversed by x can not be determined from (toc(;;)) a:) only, as they depend on impurity reductions on other paths as well. However, the efficiency and null player properties will again remain valid, although symmetry and strong monotonicity are not guaranteed.
4.4 Local relevance
A major result regarding the global MDI importance in asymptotic conditions is its link with Kohavi al. [1997]'s notion of feature relevance. A similar relationship can be established between local MDI importance measures and new notion of local relevance (at the level of a samples) inspired from the null player property of Shapley values.
with respect to the output Y iff P(Y y| Jmny B 2n) = P(Y = y B = BB) for all B C V-m and all y E y. It is locally relevant otherwise.
Definition 2. Xm is locally irrelevant
variable is thus locally irrelevant at if knowing its values never changes the probability of any output whatever the other variables that are known. Local relevance can be linked with global relevance through the following theorem.
Theorem 3. A variable Xm is irrelevant with respect to Y if and only if it is locally irrelevant with respect to Y for all x such that P(V = x:) > O.
In the categorical setting and asymptotic conditions, local relevance is linked to local MDII through the following theorem:
Theorem 4. If a variable is locally irrelevant at æ with respect to Y, then Imp. (Xm x) = O.
Theorem 4 coincides exactly with the null player property of Section 4.3. Local MDI importance is thus a sensible score to identify locally irrelevant variables. Note that, unlike with global MDI, there might exist variables X,, such that 1mp (Xm., .) O despite X,, being locally relevant at However, a globally relevant variable X,, will always receive a non zero Imp (Xm, x)) at some x.
5 Discussion and related works
In the literature, Shapley values have been mostly used to decompose model predictions f(x) at any x into a sum of terms that represent the (local) contribution of each variable to the prediction [Strumbelj and Kononenko, 2010, Lundberg and Lee, 2017]. The characteristic function v/ considered by these methods v(S) = fs(ss) - fo( where fs())) is the model be explained restricted the variables 5 and fo (mg) is often set to F.] Typically, f (as)) is defined as [x)( = as). where the expectation is over the conditional p(Xg) Xs æs) the marginal ka. interventional)
7

---

p(Xg) distribution. These methods are mostly model agnostic, i.e., they can handle any machine learning model, considered as a black-box, although the estimation of restricted models and the computation of the Shapley values (Equation 1) can be very challenging in general.
Among this literature, Lundherg al. [2020] have proposed TreeSHAP, framework to efficiently compute Shapley values when f are trees or sum of trees. One of the only alternative local importance measures for trees is Saabas' heuristic method (implemented in [Saabas, 2014]). Saabas' method measures local variable importances for a sample æ by collecting the changes in the (expected) model prediction due to each variable value along the tree branches followed by x. Like TreeSHAP, Saabas' importances sum to the model prediction at a. They are much faster to compute but do not satisfy all properties of Shapley values, in particular strong monotonicity.
One main difference between local MDI and TreeSHAP/Saabas as studied in Lundberg et al. [2020] is that local MDI decomposes entropy (or more generally impurity) reductions (Uioe (V; vv while TreeSHAP/Saabeee decompose model predictions (vz). As consequence, local MDI scores are independent of output normalisation or scaling and do not require to choose a specific class probability
score to be used as f(x) to be decomposed. This also allows to connect local and global MDI in a natural way, and gives a probabilistic interpretation to the null player property in terms of variable irrelevance. Algorithmically. local MDI uses the exact same collecting procedure along tree paths as Saabas' measure, replacing output differences with impurity reductions. Similarly as Saabas, local MDI results in a much more efficient and simpler estimation scheme than TreeSHAP but looses some properties of Shapley values in the general case. Section 4.3 however shows that these properties are retrieved in the case of totally randomized trees, at least asymptotically. This also applics to Saabas' measure (as sketched in Theorem 1 in the supplement of Lundberg et al. [2020]). Although TreeSHAP is guaranteed to ensure strong monotonicity asymptotically, the relevance of its scores is still tied to the quality of the tree-based model that it explains. For example, using TreeSHAP with Random forests with K > or pruned trees will also potentially lead to biases in the importance scores (e.g., due to masking effects) with respect to what would be obtained if f was the Bayes classifier. We believe this is a similar trade-off the one met in local MDI with respect to K.
Our results also highlight a link between global MDI and SAGE [Covert et al., 2020], a purely model-agnostic method for global importance computation. SAGE estimates Shapley values for (e( = Ele(fo(Xx)) Y)] E[e(fs(Xs), Y)] where l is loss function and expectations are taken over XV. Covert et al. [2020] have shown that when l is cross-entropy, f the Bayes classifier, and restricted models are estimated through the conditional distributions, then the population version of SAGE is strictly identical to Equation 4. Interestingly, both methods arrive to this population formulation through very different algorithms. SAGE explicitly estimates Shapley values, while global MDI are obtained by collecting impurity reductions at tree nodes a random forest. Global MDI departs from 4 and Shapley values when K > 1. On the other hand, being model agnostic, like TreeSHAP, SAGE is tied to the quality of the model explains. Given the difficulty of sampling from the conditional distribution, its implementation also samples from the marginal distribution instead, which makes it depart from Shapley values and affects its convergence to 4. In practice, we will show in the next section that both methods produce very similar results, when used with Random forests (but with a strong advantage to global MDI in terms of computing times).
Overall, we believe our analysis of local and global MDI sheds some new lights on these measures. Although they were not designed as such, these methods can indeed be interpreted as procedures to sample variable subsets and compute mutual information such that they provide estimates of Shapley values for very natural characteristic function based on mutual information. Although they tightly linked algorithmically with Random forests, they actually highlight general properties of the original data distribution independently of these models. This makes them very different from model-agnostic methods that explain pre-existing models, furthermore regardless of the data distribution when restricted models are estimated from marginal distributions.
"Although TreeSHAP authors advocate the decomposition of model predictions as the way to go, a variant of TreeSHAP [Lundberg et al., 2020] can also decompose model loss by enforcing feature independence, at a higher computational cost however than the local MDI measure proposed here.
8

---

Spearman correlation
9.10
AILL
0:11
Local Tree
131
122
620
1.5
536
0.31
115
Local Saabas
1.00
382
0.04
0.44
0.34
3.00
TreeSHAP Saabas
0-131
2.11
0.2
0:31 6.11
2.10
sqrt
60p
Figure 1: Normalized importance scores derived from an ensemble of totally and non-totally randomized Extra- Trees (with K = 1.....p) p) for the global MDI importance measure (left) and SAGE (right).
Figure 2: Mean correlation (over all samples) w.r.t. increasing K" be- tween absolute importance scores for digits ([min,max] is shaded).
Clss
Trassey Lasr Saaval
Mau
Can
SOO Seawe
Treddee tnsi Not Seaten
Tredwe Loor sot Seati
Trad
Nar
K=sqrt
K=sqrt
K=p
Figure 3: Local importances derived by local measures from forest of 1000 Extra- Trees with K {1, vp.p) p)) for led (left) and digits (right). Results for all samples can be found in Appendix E.
6 Illustrations
Here, global and local MDI are illustrated and compared against SAGE, Saabas, and TreeSHAP on two classification problems. The led problem [Breiman et al., 1984] consists of an output , 9} with equal probability and seven binary variables representing each segment of seven-segment display and whose values are determined unequivocally from Y. The digits problem consists of an output Y E (0.....9) 9} and 64 integer inputs corresponding the pixels of 8 x grayscale image of digit. Additional experiments on other datasets are reported in Appendix E. In all experiments, importance scores are computed either using Scikit-Learn [Pedregosa et al., 201 1] or method authors' original code (data and code are open-source, see details in Appendix C).
Y E ..,
Extra-Trees Global importances are shown in Figure 1 on the led dataset for an ensemble of 1000 Extra- Trees
[Geurts et al., 2006] and several values of K, with global MDI and SAGE (using the cross-entropy loss). Importances are normalized such that the sum of (absolute values of) the scores is equal to one. With K = 1, both approaches clearly yield very similar scores, as expected from the discussion in Section Both methods remain very close when is increased. Regardless of the importance measure, one can notice the masking effect that favors X1 and X, at the expense of the other variables when increases. The same effect appears when SAGE uses another loss function and for the global importance measure derived from TreeSHAP (see Appendix D).
Local importances are then computed for both classification problems from ensemble of 1000 Extra-Trees and with the three local importance measures. Scores from Saabas and TreeSHAP are obtained from the additive decomposition might not be the true class), Local feature importances for two samples are reported in Figure 3 by coloring either the corresponding segment (left) or pixel (right) for three values of K. The three local importance measures yield very similar importance scores, suggesting that they provide matching explanations of model predictions. This similarity further quantified by measuring the correlation between the (absolute value of) local importance scores of all pairs of methods for several K (Figure 2 for digits, Appendix for led). The mean correlation over samples remains close to 1 for all pairs, although the variation (depicted by the shaded area delimiting the range between minimal and maximal correlations) impacted by the value K. As expected, Saabas and TreeSHAP, which both decompose model predictions, are closer each other than to Local MDI.
the conditional probability of the predicted class (which

---

7 Conclusion
MDI importances have been used extensively as way of measuring, globally, the respective con- tribution of variables. In this paper, we showed that global MDI importances derived from totally randomized trees are actually Shapley values that decompose the mutual information I(V; Y) when the impurity measure is the Shannon entropy. We then proposed local MDI importance that very naturally decomposes global MDI over the training examples. We showed that local MDI importances are also Shapley values with respect to conditional entropy reductions and that they are consistent with respect a novel local relevance notion. We compared MDI importances conceptually with other recent local and global feature importance scores inspired from Shapley values and showed empirically that all these methods are very close, while both global and local MDI importances do not require any extra computation with respect to the tree construction. Overall, local and global MDI measures provide a natural and efficient way of explaining properties of the data distribution.
While the main results of this paper assume categorical variables and Shannon entropy as impurity measure, they can be extended other impurity measures and to regression (see Appendix F). As future works, we would like to better characterize these measures in non-asymptotic conditions and outside the purely categorical setting. More experiments should also carried out to better highlight differences, practically, between the MDI family and other methods such as TreeSHAP and SAGE that more explicitly approximate Shapley values. Finally, the link with Shapley values and TU-games in general could be further investigated to propose other extensions of MDI measures (for example to highlight variables interactions as in [Lundberg et al., 2020]).
Acknowledgments
Antonio Sutera is supported via the Energy Transition Funds project EPOC 2030-2050 organized by the FPS economy, S.M.E.s, Self-employed and Energy. This work was partially supported by Service Public de Wallonie Recherche under grant n² 2010235 ARIAC by DIGITALWALLONIAA.A.
References
Kellie Archer and Ryan V Kimes. Empirical characterization of random forest variable importance measures. Computational statistics & data analysis, 52(4):2299-2260, 2008.
Lidia Auret and Chris Aldrich. Empirical comparison of tree ensemble variable importance measures. Chemometries and Intelligent Laboratory Systems, 105(2):157-170, 2011.
Manfred Besner. Axiomatizations of the proportional shapley value. Theory and Decision, 86(2): 161-183, 2019.
Leo Breiman. Random forests. Machine learning, 45(1):5-32,2000
Leo Breiman, Jerome Friedman, Charles Stone, and Richard Olshen. Classification and regression trees, CRC press, 1984.
Ian Covert, Scott Lundberg, and Su-In Lee. Understanding global feature contributions with additive importance measures. Advances Neural Information Processing Systems, 33, 2020.
Robin Genuer, Jean-Michel Poggi, and Christine Tuleau-Malot. Variable selection using random forests. Pattern recognition letters, 31(14):2225-2236 2010.
Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. Machine learning. 63(1):3 2006.
Hemant Ishwaran et al. Variable importance in binary regression trees and forests. Electronic Journal of Statistics, 1:519-537, 2007.
Yacine Izza, Alexey Ignatiev, and Joao Marques-Silva On explaining decision trees. arXiv preprint arXiv:2010.11 1034, 2020.
Ron Kohavi, George H John, et al. Wrappers for feature subset selection. Artificial intelligence, 97 (1-2):273-324 324,, 1997.
10

---

Xiao Li, Yu Wang, Sumanta Basu, Karl Kumbier, and Bin Yu. A debiased mdi feature importance measure for random forests. Advances in Neural Information Processing Systems, pages 8047- 4057,2019
G. Louppe, L. Wehenkel, A. Sutera, and P. Geurts. Understanding variable importances in forests of randomized trees. In Advances Neural Information Processing Systems 26, pages 431-439, 2013.
Gilles Louppe. Understanding random forests: from theory practice. PhD thesis, Université de Liège, Liège, Belgique, 2014.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in neural information processing systems, pages 4765-4774, 2017.
Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable ai for trees. Nature machine intelligence, 2(1):2522-588) 2020.
Mário Popolin Neto and Fernando V Paulovich. Explainable matrix-visualization for global and local interpretability of random forest classification ensembles. arXiv preprint arXiv:2005.0423: 2020.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, al. Scikit-leam: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
Ando Saabas. Interpreting random forests. 2014. URL http://blog. http://bloo...aaiiieeo. datadive net/
interpreting wwweeetiinnrraddmmm.oo forddtsforesss.....o Last access: February 2021.
Erwan Scornet. Trees, forests, and impurity-based variable importance.
ar preprint
arXiv:2001.04295 2020.
Lloyd Shapley. A value for n-person games. Contributions to the Theory of Games, 2(28):307-317, 1953.
Carolin Strobl, Anne-Laure Boulesteix, Achim Zeileis, and Torsten Hothorn. Bias in random forest variable importance measures: Illustrations, sources and solution. BMC bioinformatics, 8(1):25, 2007.
Erik Strumbelj and Igor Kononenko. An efficient explanation of individual classifications using game theory. Mach. Learn. Res., 11:1-18, March 2010. ISSN 1532-4435.
Antonio Sutera. Importance measures derived from random forests: characterisation and extension. PhD thesis, Université de Liège, Liège, Belgique, 2019.
Antonio Sutera, Célia Châtel, Gilles Louppe, Louis Wehenkel, and Pierre Geurts. Random subspace with trees for feature selection under memory constraints. In International Conference on Artificial Intelligence and Statistics, pages 929_937, 2018.
René van den Brink, René Levinský, and Miroslav Zelený. On proper shapley values for monotone tu-games. International Journal of Game Theory, 44(2):449471,, 2015.
H Peyton Young. Monotonic solutions of cooperative games. International Journal of Game Theory, 14(2):65-72, 1985.


Reviews:
[{"review_id": "t7Pq6TtEbRn", "reviewer": "Reviewer_5L4p", "summary": "The authors provide conditions under which tree-based mean decrease in impurity (MDI) measures are Shapley values. This is an interesting and potentially useful connection, with particular implications for computation time of Shapley values in certain settings.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- More discussion of totally randomized trees is necessary: when are these reasonable or feasible to compute? What happens in finite samples?\n- Local MDI has a strange interpretation; the local MDI for an observation appears to depend on other instances, and thus is not truly local. Please provide more discussion of this measure and when it has a useful interpretation.\n- Does the summation from local to global MDI in Equation 9 hold? It seems that local MDI can be negative, but global MDI cannot.\n- I would redefine \"asymptotic local MDI\" as \"future local MDI\", since the term \"asymptotic\" doesn't really fit for local importance\n- Please define notation (e.g., $I$ and $H$) prior to its use\n- In the related work section, please discuss totally randomized trees in more detail\n- The figures are difficult to read, both due to their small size and the information contained. Please consider a different format (e.g., a table of values to replace Figure 2) to facilitate easier comparisons, and please increase the font size in all cases.\n- Please include more discussion of how to handle continuous variables in this framework\n- Please consider editing the section headings to make the manuscript flow more logically, and check for typos and other formatting\n- The proof of Theorem 3 provided in the supplement is too sparse: only an if-then relation (not an if and only if) appears to be proved there.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative impacts are discussed, but as in all cases in explainable AI there is potential for results to be misused; this should be discussed.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "q9nqafIKPPw", "reviewer": "Reviewer_gLH8", "summary": "The paper’s contributions are on variable importance measures in tree and tree ensembles. In particular, the paper provides an interpretation of the “mean decrease of impurity” measure (MDI) of totally randomised trees as Shapley values where the characteristic function of the underlying game is the mutual information between a feature variable set and the target variable. Moreover, a novel local variant of MDI measure is introduced that quantifies the impact of variable for the classification of a specific input point, which can again be interpreted as Shapley values in the case of totally randomised trees.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Given their availability in popular ML packages, MDI is widely used in practice to assess variable importance. However, its interpretation is not straightforward. Hence, results are important that characterise MDI in terms of other known quantities. The given results strongly build on previous work that connected MDI to mutual information. While the step from there to Shapley values is relatively small, it is still an important novel insight. Moreover, the proposed local variant of MDI is appealing for its simplicity and natural connection to global MDI which can be decomposed as an average over all local MDIs. Overall, the paper is a pleasantly well-written and provides a useful collection of results that help to interpret the classification of randomised tree ensembles.\n\nSome minor suggestions for improvement:\n- The experiments are nice to illustrate the measures, but perhaps some stronger experiments (potentially with synthetic data) could be devised that demonstrates that MDI can become misleading for large K when it is no longer a Shapely value \n- The paper manages to be mostly self-contained despite the relatively wide set of concepts it needs to introduce. What feels is missing, is a minimal introduction to mutual information and its properties as they are essential for the main results.\n- In the definition of strong monotonicity, the index of the MC function should be m\n- In Definition 2, it seems more readable to avoid the all quantifier over labels and simply require equality of the two conditional distributions of Y", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper should have a positive societal impact because its contributions help to make machine learning more interpretable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "MkZ2jhEsfDc", "reviewer": "Reviewer_TfJb", "summary": "This paper demonstrates a connection between Shapley values and a tree-based measure of global feature importance, then proposes a local version of that tree-based feature importance measure. The paper also offers a discussion of the properties satisfied by the proposed method and runs empirical tests of feature importance methods on a few datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I would rank the overall originality and quality of the current form of this paper rather low. While methods for identifying important features in tree-based models are generally of great interest due to the wide-spread use of these types of models in deployment, the significance of the proposed method is not well demonstrated (either theoretically or empirically), and several of the contributions of the paper have been discussed already in prior works.\n\nOne of the major contributions of this paper is the connection of MDI variable importance scores to Shapley values under certain conditions (randomized trees under asymptotic conditions). While developing the understanding of connections between older, more established tree-based methods for variable importance and more recent Shapley value-based methods is certainly of value and of interest, the connection between these methods has already been discussed in prior work, and in my opinion has been explained in a more intuitive way there. \n\nSpecifically, the method discussed in this paper can be thought of as a modified version of the Saabas algorithm [1], where output differences are replaced by impurity reductions (see lines 296-297 in this paper). The connection between algorithms like Saabas/MDI and the Shapley value was already made in Lundberg et al.’s 2019 paper (see the bottom of pg. 20-21 in the arxiv version of that paper) – Saabas/MDI only consider a single ordering to add players to the coalition, while the Shapley value averages over all orderings. When there are randomized trees under asymptotic conditions, all possible feature orderings will be considered in equal proportions, making these equivalent [2].\n\nFurthermore, this paper incorrectly states that TreeSHAP only decomposes model predictions. A significant portion of that work involves an algorithm called “Independent Tree SHAP” (see methods 10.2 of [2]), that allows for the attribution of a model’s loss to individual features at the local level, which is also discussed in [3]. TreeSHAP loss attributions should certainly be more thoroughly discussed theoretically or at least compared to empirically.\n\nI think there are a variety of avenues that could make this work significantly more impactful – either a theoretical analysis outside of the asymptotic conditions, or empirical results for more representative datasets (i.e. not toy examples like the digits/LED used in this paper) that the MDI values were of similar quality to SHAP while being meaningfully faster on these more realistic datasets.\n\nAs a minor comment, the notation is pretty dense, confusing, and occasionally overloaded – leading to ambiguity (like $v$ referring to both the characteristic function of a TU game [see line 48] and the variable tested in a certain node [see line 98]).\n\n[1] Ando Saabas. Interpreting random forests. 2014. http://blog.datadive.net/interpreting-random-forests/\n[2] Lundberg, Scott M., et al. \"From local explanations to global understanding with explainable AI for trees.\" https://arxiv.org/abs/1905.04610\n[3] Covert et al. \"Understanding global feature contributions with additive importance measures.\" https://arxiv.org/abs/2004.00668\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents previously unknown connection between the global Mean Decrease of Impurity (MDI) variable importance scores and Shapley values under certain conditions. The authors also derive local MDI feature importance measure link with Shepley values.  The paper presents novel insights, and the local MDIs are likely practically useful for its simplicity. This paper is clearly written and structured well. Overall, this paper constitutes an important contribution to the field and passes the bar for the acceptance to NeurIPS.
Decision: Accept (Poster)