From global to local MDI variable importances for random forests and when they are Shapley values
Year: 2022

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 problems.

heading: 1 Motivation
text: While research in machine learning (ML) often focuses on predictive accuracy, another important topic concerns the interpretation of ML models and their predictions. Interpreting a model helps to uncover the mechanisms it captures (e.g., biomarkers useful to diagnose a disease), and to explain its predictions (e.g., why a particular patient is diagnosed healthy or 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 a model. They help to understand how the model works, and to 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 et 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], Li et al. [2019], Sutera [2019], Scornet [2020]). Assuming a sufficiently large learning set and number of trees, these works showed that importance measures have desirable properties, such as consistency with respect to the notion of feature relevance. They also analyzed the impact of learning meta-parameters (e.g., randomization level, tree depth, ensemble size) on such properties. While standard importance measures evaluate the global importance of a feature at the level of a dataset, several works proposed new approaches based on Shapley values to derive local scores reflecting the importance of a feature for a given prediction (e.g., Neto and Paulovich [2020], Lundberg et al. [2020], Izza et al. [2020]).
The contribution of the present work in this context is two-fold. First, we show that the standard mean decrease of impurity (MDI) measure when derived from totally randomized trees and in asymptotic
∗Corresponding author. Email address: sutera.antonio@gmail.com
35th Conference on Neural Information Processing Systems (NeurIPS 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).

heading: 2 Background
text: In what follows, we consider a standard supervised learning setting and denote by V = {X1, . . . , Xp} 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, a TU-game (V, v) (i.e., a cooperative game with transferable utilities) is defined by a finite set of players V = {X1, . . . , Xp}2 and a characteristic (or coalition) function v ∈ V : 2V → R, with v(∅) = 0, that maps a coalition (i.e., a 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) is monotonic if v(S) ≤ v(T ) if S ⊆ T ⊆ V . Let us denote by V −m the set V \ {Xm}. The marginal contribution MCvm(S) of player Xm ∈ V for S ⊆ V −m is defined by MCvm(S) = v(S ∪ {Xm}) − v(S). A player Xm ∈ V is called a null player if MCvm(S) = 0 for all S ⊆ V −m. Two players Xi and Xj are said to be symmetric whenever v(S ∪ {Xi}) = v(S ∪ {Xj}) for all coalitions S ⊆ V −i,j . A TU-value φv : V → R is a function that assigns to any player Xm ∈ V and any function v (∈ V is omitted in the rest) a value, denoted φv(Xm) ∈ R, also known as its payoff, 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 , ∑
Xm∈V φv(Xm) = 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, φv(Xi) = φv(Xj) if players Xi and Xj are symmetric. Two players of equal contributions in every game (i.e., with every coalition S) should get the same value.
Null player: For all v , φv(Xm) = 0 if Xm is a null player. A null player should get a zero payoff.
Strong monotonocity3: For all v, w and Xm ∈ V such that MCvm(S) ≥ MCwm(S) for all S ⊆ V −m, we have φv(Xm) ≥ φw(Xm). If a 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 player4, and Strong monotonicity is the Shapley value ϕShv defined by [Shapley, 1953]:
ϕShv (Xm) = ∑
S⊆V −m
|S|!(p− |S| − 1)! p! MCvm(S). (1)
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, a common definition of the relevance of a feature is as follows [Kohavi et al., 1997]:
A variable Xm ∈ V is relevant to Y (with respect to V ) iff ∃B ⊂ V : Xm ⊥̸ Y |B. A variable Xm is 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
2We use the same notations for the (set of) players as for (set of) input features, as the two will coincide later. 3In the ML literature, strong monotonicity is often called consistency [Lundberg and Lee, 2017]. 4Actually, 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 −m. 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 et 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 t into two child nodes (tL and tR). The test st used to partition the samples at node t is 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 ): ∆i(s, t) = i(t) − p(tL)p(t) i(tL) − p(tR) p(t) i(tR), where p(tL) and p(tR) are the proportions of samples that fall in nodes tL and tR respectively. Single decision trees suffer from a high variance that is 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 a different bootstrap sample with a local random selection of K(≤ 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 a tree T , the MDI importance of a variable Xm for predicting the output Y is defined as :
Imp(Xm, T ) = ∑
t∈T :ν(st)=Xm
p(t)∆i(st, t), (2)
where the sum is over all interior nodes t in T , ν(st) 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 Xm derived from forests of NT trees is then the average of Imp(Xm, T ) over all trees:
Imp(Xm) = 1
NT ∑ T Imp(Xm, T ). (3)
While this measure was initially proposed as a heuristic, Louppe et al. [2013] characterise it theoretically under the following conditions: (1) all input variables and the output are categorical (not necessarily binary) (2) trees use so-called exhaustive splits5, and (3) impurity is measured by Shannon entropy6. 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 NT → ∞ and a learning sample of infinite size), the MDI importance, denoted Imp∞, is given by:
Imp∞(Xm) = p−1∑ k=0 1 Ckp 1 p− k ∑
B∈Pk(V −m)
I(Y ;Xm|B), (4)
where Pk(V −m) is the set of subsets of V −m of cardinality k, and I(Y ;Xm|B) is the conditional mutual information of Xm 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]:
p∑ m=1 Imp∞(Xm) = I(Y ;V ). (5)
A direct consequence of Equation 4 is that a variable Xm is irrelevant iff Imp∞(Xm) = 0, which makes the MDI importance a sensible measure to identify relevant variables.
5Each node is split into |Xi| sub-trees, one for each of the |Xi| different values of the split variable Xi. 6A short introduction to information theory and the related notations used in the paper is provided in
Appendix G.
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).

heading: 3.1 Totally randomized trees
text: Let us consider a TU-game (V, v), where V is the set of variables and the coalition function v is the mutual information v(·) = I(Y ; ·). Since v(∅) = I(Y ; ∅) = 0, this is a valid TU-game. This TU-game is monotonic since we have I(Y ;T ) = I(Y ;S) + I(Y ;T \ S|S) ≥ I(Y ;S) as soon as S ⊆ T ⊆ V (using the chain rule and the positivity of the conditional mutual information). Marginal contributions for v can be rewritten as:
MCvm(S) = v(S ∪ {Xm})− v(S) = I(Y ;S ∪ {Xm})− I(Y ;S) = I(Y ;Xm|S), (6)
using the definition of (conditional) mutual information. A null player is thus defined as a variable Xm such that MCvm(S) = I(Y ;Xm|S) = 0 for all S ⊆ V −m. This definition exactly coincides with the definition of an irrelevant variable (Section 2), since I(Y ;Xm|S) = 0 is equivalent to Y ⊥ Xm|S. Two variables Xi and Xj are symmetric whenever v(S ∪ {Xi}) = v(S ∪ {Xj}) for all S ⊆ V −i,j , which is equivalent to I(Y ;Xi|S) = I(Y ;Xj |S) for all S ⊆ V −i,j , i.e., Xi and Xj bring the same information about Y 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 ∈ V ,
Imp∞(Xm) = ϕ Sh v (Xm), (7)
where ϕShv is the Shapley value with v(S) = I(Y ;S) (∀S ⊆ V ).
The proof7 of this theorem follows from a direct comparison of Equations 1 and 4.
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: ∑p
m=1 Imp∞(Xm) = v(V ) = I(Y ;V ), which states that MDI importances decompose, in an additive way, the mutual information I(Y ;X1, . . . , Xp). This results is identical to Equation 5.
Symmetry: If Xi and Xj are symmetric, then Imp∞(Xi) = Imp∞(Xj). This property is easy to check knowing that I(Y ;S ∪ {Xi}) = I(Y ;S ∪ {Xj}) implies that I(Y ;Xi|S) = I(Y ;Xj |S) and therefore swapping Xi and Xj in Equation 4 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 a stronger result, stating in addition that Imp∞(Xm) = 0 only if Xm is irrelevant to Y .
Strong monotonicity: Let us assume two outputs Y1 and Y2. Strong monotonicity says that if for all feature subsets S ⊆ V −m: I(Y1;Xm|S) ≥ I(Y2;Xm|S), then we have ImpY1∞(Xm) ≥ ImpY2∞(Xm). This property states that if a variable brings more information about Y1 than about Y2 in all contexts S, it is more important to Y1 than to Y2.
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 setting8. MDI importance will be compared with other measures from the literature that explicitly seek to estimate the same quantities in Section 5.
7The proofs of all theorems are in Appendix A. 8For 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].

heading: 3.2 Non totally randomized trees
text: 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 us denote by ImpK∞(Xm) the importance of Xm derived from randomized trees built with a given value of K in asymptotic conditions. When K > 1, ImpK∞(Xm) can no longer be decomposed as in Equation 4, as some I(Y ;Xm|S) terms will not be included in the sum or with a weight different from the one in Equation 4. Actually, although ImpK∞ attributes a payoff to each variable in V , it can not be interpreted as a TU-value for the TU-game defined by (V, v), with v(·) = I(Y ; ·). Indeed, its computation requires to have access to conditional mutual information of the form I(Y ;Xm|S = s) for all coalition S but also for all set of values s of variables in S and the latter can not be derived from the knowledge only of I(Y ;S) for all S.
The efficiency and null player conditions are however still satisfied by ImpK∞: Efficiency: Louppe et al. [2013] showed that ∑p
m=1 Imp K ∞(Xm) = v(S) = I(Y ;V ) for all K as
soon as the trees are fully developed.
Null player If Xm is a null player (i.e., an irrelevant variable), then ImpK∞(Xm) = 0 [Louppe et al., 2013]. Note that ImpK∞(Xm) = 0 is however not anymore a sufficient condition for Xm to be irrelevant. It can be shown however that a strongly relevant variable Xm will always be such that ImpK∞(Xm) > 0 whatever K [Sutera et al., 2018]. Symmetry is not necessarily satisfied however, since I(Y ;Xi|S) = I(Y ;Xj |S) for all S ⊆ V −i,j does not ensure that I(Y ;Xi|S = s) = I(Y ;Xj |S = s) for all s, which would be required for the feature to be fully interchangeable when K > 1. Similarly, strong monotonicity is not satisfied either for ImpK∞, as shown in Example 1 in Appendix B.
Note that as discussed in [Louppe et al., 2013], the loss of several properties when K > 1 should not preclude using ImpK∞ as 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 can assess the importance of a 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 a 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.

heading: 4.1 Definition and properties
text: Let us denote by x = (x1, . . . , xp)T a given instance of the input variables, with xj the value of variable Xj . In what follows, we will further denote by xS a given set of values for the variables in a subset S ⊆ V (in particular, x{Xj} = xj).
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
Imp(Xm,x) = 1
NT ∑ T ∑ t∈T :ν(st)=Xm
∧x∈t
i(t)− i(txm) (8)
where the outer sum is over the NT trees of the ensemble, the inner sum is over all nodes that are traversed by x and where Xm is used to split, txm is the successor of node t followed by x in the tree (corresponding to Xm = xm), and i(.) is the impurity function.
This general measure quantifies how important is feature Xm to predict the output of the test example x represented by its input features. It collects all differences i(t)− i(txm) along all paths traversed by example x in the ensemble. In practice, this can be implemented very efficiently at no additional cost with respect to the computation of a prediction, as soon as all impurities, computed at training time, are stored at tree nodes.
The intuition behind this measure is that a variable is important for a sample x if it leads to important reductions of impurity along the paths traversed by x. Note that unlike global MDI, local MDI can be negative, as the impurity can increase from one node to one of its successors. A variable of negative importance for a given sample x is thus such that, in average over all paths traversed by x, it 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) = 1
N N∑ i=1 Imp(Xm,xi), (9)
where {(x1, y1), . . . , (xN , yN )} is the learning sample of N examples that was used to grow the 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 is thus a way to decompose the global MDI over all training examples.

heading: 4.2 Asymptotic analysis
text: In the categorical setting and asymptotic conditions, the decomposition in Equation 4 for totally randomized trees can be adapted to the local MDI measure, denoted Imp∞(Xm,x).
Theorem 2. (Asymptotic local MDI) The local MDI importance Imp∞(Xm,x) of a variable Xm with respect to Y for a given sample x as computed with an infinite ensemble of fully developed totally randomized trees and an infinitely large training sample is
Imp∞(Xm,x) = p−1∑ k=0 1 Ckp 1 p− k ∑ B∈P(V −m) H(Y |B = xB) −H(Y |B = xB , Xm = xm) (10)
where H(Y |·) is the conditional entropy of Y . Similarly as in the finite setting, Imp∞(Xm,x) can be negative, since the difference H(Y |B = xB)−H(Y |B = xB , Xm = xm) is not always positive. Example 2 in Appendix B illustrates one such a situation.
In asymptotic condition, the decomposition in Equation 9 furthermore becomes: Imp∞(Xm) = ∑ x∈V P (V = x)Imp∞(Xm,x), (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 ;Y ):
I(V ;Y ) = p∑ m=1 ∑ x∈V P (V = x)Imp∞(Xm,x). (12)

heading: 4.3 Local MDI importances are Shapley values
text: Let us define a local characteristic function vloc(S;x) = H(Y )−H(Y |S = xS), which measures the decrease in uncertainty (i.e., the amount of information) about the output Y when the variables in S are known to be xS . This characteristic function is thus parameterized by x. The proof of
Theorem 1 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 vloc(.;x):
Imp∞(Xm,x) = ϕ Sh vloc(.;x) (Xm) (13)
As a consequence, Imp∞(Xm,x) satisfies the Shapley value properties at any point x, i.e.: Efficiency: vloc(V ;x) = H(Y ) −H(Y |V = x) = ∑p
m=1 Imp∞(Xm,x). This is in accordance with the decomposition in Equation 12, since ∑ x∈V P (V = x)vloc(V ;x) = ∑ x∈V P (V = x)(H(Y )−H(Y |V = x)) = I(V ;Y ). Symmetry: If Xi and Xj are such that H(Y ) − H(Y |S = xS , Xi = xi) = H(Y ) − H(Y |S = xS , Xj = xj) for every S ⊆ V −i,j , then Imp∞(Xi,x) = Imp∞(Xj ,x). Null player If Xi is such that H(Y |S = xS , Xm = xm) = H(Y |S = xS) for all S ⊆ V −m, then Imp∞(Xi,x) = 0.
Strong monotonicity: Assuming two outputs Y1 and Y2, if H(Y1|S = xS)−H(Y1|S = xS , Xm = xm) ≥ H(Y2|S = xS) − H(Y2|S = xS , Xm = xm) for all S ⊆ V −m, then we have ImpY1(Xm,x) ≥ ImpY2(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 vloc(·;x), since they are not uniquely defined by vloc(·;x). Indeed, tree splits along the paths traversed by x can not be determined from vloc(·;x) 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.

heading: 4.4 Local relevance
text: A major result regarding the global MDI importance in asymptotic conditions is its link with Kohavi et al. [1997]’s notion of feature relevance. A similar relationship can be established between local MDI importance measures and a new notion of local relevance (at the level of a samples) inspired from the null player property of Shapley values. Definition 2. Xm is locally irrelevant at x with respect to the output Y iff P (Y = y|X = xm, B = xB) = P (Y = y|B = xB) for all B ⊆ V −m and all y ∈ Y . It is locally relevant otherwise.
A variable is thus locally irrelevant at x 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) > 0.
In the categorical setting and asymptotic conditions, local relevance is linked to local MDI through the following theorem: Theorem 4. If a variable is locally irrelevant at x with respect to Y , then Imp∞(Xm,x) = 0.
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 Xm such that Imp∞(Xm,x) = 0 despite Xm being locally relevant at x. However, a globally relevant variable Xm will always receive a non zero Imp∞(Xm,x) at some x.

heading: 5 Discussion and related works
text: 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 vf̂ considered by these methods is v(S) = f̂S(xS)− f̂∅(x∅), where f̂S(xS) is the model to be explained restricted to the variables in S and f̂∅(x∅) is often set to E[f̂(X)]. Typically, f̂S(xS) is defined as E[f̂(X)|XS = xS ], where the expectation is over the conditional p(XS̄ |XS = xS) or the marginal (a.k.a. interventional)
p(XS̄) 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, Lundberg et al. [2020] have proposed TreeSHAP, a 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 x 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 x. 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 (vloc(V ;x)), while TreeSHAP/Saabas decompose model predictions9 (vf̂ ). As a 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 it 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 applies 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 > 1 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 as 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 vℓ(S) = E[ℓ(f̂∅(X∅), Y )]− E[ℓ(f̂S(XS), Y )] where ℓ is a loss function and expectations are taken over p(V,X). Covert et al. [2020] have shown that when ℓ is cross-entropy, f̂ is 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 in 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 it 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 a very natural characteristic function based on mutual information. Although they are 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.
9Although 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.

heading: 6 Illustrations
text: 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 Y ∈ {0, . . . , 9} with equal probability and seven binary variables representing each a segment of a seven-segment display and whose values are determined unequivocally from Y . The digits problem consists of an output Y ∈ {0, . . . , 9} and 64 integer inputs corresponding to the pixels of a 8 × 8 grayscale image of a 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., 2011] or method authors’ original code (data and code are open-source, see details in Appendix C).
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 5. Both methods remain very close when K is increased. Regardless of the importance measure, one can notice the masking effect that favors X1 and X4 at the expense of the other variables when K 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 an ensemble of 1000 Extra-Trees and with the three local importance measures. Scores from Saabas and TreeSHAP are obtained from the additive decomposition of the conditional probability of the predicted class (which 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 is 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 E for led). The mean correlation over all samples remains close to 1 for all pairs, although the variation (depicted by the shaded area delimiting the range between minimal and maximal correlations) is impacted by the value of K. As expected, Saabas and TreeSHAP, which both decompose model predictions, are closer to each other than to Local MDI.

heading: 7 Conclusion
text: MDI importances have been used extensively as a way of measuring, globally, the respective contribution 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 a 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 to 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 to 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 of the purely categorical setting. More experiments should be 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]).

heading: Acknowledgments
text: 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 DIGITALWALLONIA4.AI.

Review summaries:
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.