Trees, forests, and impurity-based variable importance

2020·Arxiv

Abstract

Abstract

Tree ensemble methods such as random forests [Breiman, 2001] are very popular to handle high-dimensional tabular data sets, notably because of their ability to detect sparse signals and their resulting good predictive accuracy. However, when machine learning is used for decision-making problems, settling for the best predictive procedures may not be reasonable since enlightened decisions require to understand the phenomena underlying the data, which is accessible only with an in-depth comprehension of the algorithm prediction process. Unfortunately, random forests are not intrinsically interpretable since their prediction results from averaging several hundreds of decision trees. A classic approach to gain knowledge on this so-called black-box algorithm is to compute variable importances, that are employed to assess the predictive impact of each input variable. Variable importances are then used to rank or select variables and thus play a great role in data analysis. Mean Decrease Impurity (MDI) is one of the two variable importance measures in random forests. However, there is no theoretical justification to use MDI: we do not even know what this indicator estimates. In this paper, we analyze MDI and prove that if input variables are independent and in absence of interactions, MDI provides a variance decomposition of the output, where the contribution of each variable is clearly identified. We also study models exhibiting dependence between input variables or interaction, for which the variable importance is intrinsically ill-defined.

1 Introduction

Decision trees [see Loh, 2011, for an overview] can be used to solve pattern recognition tasks in an interpretable way: in order to build a prediction, trees ask to each observation a series of questions, each one being of the form “Is variable than a threshold are to be determined by the algorithm. Thus the prediction for a new observation only depends on the sequence of questions/answers for this observation. One of the most popular decision trees is the CART procedure [Classification And Regression Trees, Breiman et al., 1984], which unfortunately suffers from low accuracy and intrinsic instability: modifying slightly one observation in the training set can change the entire tree structure together with the predicted values in some areas of the input space.

To overcome this last issue, and also improve their accuracy, ensemble methods, which grow many base learners and aggregate them to predict, have been designed. Random forests, introduced by Breiman [2001], are among the most famous tree ensemble methods. They proceed by growing trees based on CART procedure [Breiman et al., 1984] and randomizing both the training set and the splitting variables in each node of the tree. Breiman’s [2001] random forests have been under active investigation during the last two decades mainly because of their good practical performance and their ability to handle high-dimensional data sets. They are acknowledged to be state-of-the-art methods in fields such as genomics [Qi, 2012] and pattern recognition [Rogez et al., 2008], just to name a few. If empirical performances of random forests are not to be demonstrated anymore [Fern´andez-Delgado et al., 2014], their main flaw relies on their lack of interpretability because their predictions result from averaging over a large number of fully-grown trees (typically several hundreds): each tree may be interpreted, due to its recursive structure, but random forests remain an obscure black-box procedure.

Since interpretability is a concept difficult to define precisely, people eager to gain insights about the driving forces at work behind random forests predictions often focus on variable importance, a measure of the influence of each input variable to predict the output. In Breiman’s [2001] original random forests, there exist two importance measures: the Mean Decrease Impurity [MDI, or Gini importance, see Breiman, 2002], which sums up the gain associated to all splits performed along a given variable; and the Mean Decrease Accuracy [MDA, or permutation importance, see Breiman, 2001] which shuffles entries of a specific variable in the test data set and computes the difference between the error on the permuted test set and the original test set. Because of its very definition, MDI is an importance measure that can be computed for trees only, since it strongly relies on the tree structure, whereas MDA is an instantiation of the permutation importance that can be used for any predictive model. Both measures are used in practice even if they possess several major drawbacks.

MDI is known to favor variables with many categories [see, e.g., Strobl et al., 2007, Nicodemus, 2011]. Even when variables have the same number of categories, MDI exhibits empirical bias towards variables that possess a category having a high frequency [Nicodemus, 2011, Boulesteix et al., 2011]. MDI is also biased in presence of correlated features [Nicodemus and Malley, 2009]. A promising way to assess variable importance in random forest consists in designing new tree building process or new feature importances as in the R package party [Strobl et al., 2008, 2009, R Core Team, 2013] or in Li et al. [2019], Zhou and Hooker [2021]. On the other hand, MDA seems to exhibit less bias than MDI but tends to overestimate correlated features Strobl et al. [2008]. Besides, its scale version [the default version in the R package randomForest, Liaw and Wiener, 2002] depends on the sample size and on the number of trees, the last being an arbitrary chosen parameter [Strobl and Zeileis, 2008]. The interested reader may refer to Genuer et al. [2008] and Genuer et al. [2010] for an extensive simulation study about the influence of the number of observations, variables, and trees on MDA together with the impact of correlation on this importance measure. Despite all their shortcomings, one great advantage of MDI and MDA is their ability to take into account interaction between features even if unable to determine the part of marginal/joint effect [Wright et al., 2016].

From a theoretical perspective, there are only but a few results on variable importance computed via tree procedures. The starting point for theory is by Ishwaran [2007] who studies a modified version of permutation importance and derives its asymptotic positive expression, when the regression function is assumed to be piecewise constant. A scaled population version of the permutation importance is studied by Zhu et al. [2012] who establish rate of convergence for the probability that a relevant feature is chosen in a modified random forest algorithm. The exact population expression of permutation importance is computed by Gregorutti et al. [2017] for a Gaussian linear model.

Regarding the MDI, there are even fewer results. Louppe et al. [2013] study the population MDI when all features are categorical. In this framework, they propose a decomposition of the total information, depending on the MDI of each variable and of interaction terms. They also prove that the MDI of an irrelevant variable is zero and that adding irrelevant variables does not impact the MDI of relevant ones. Even if these results may appear to be very simple, the proofs are not straightforward at all, which explains the few results on this topic. This work was later extended by Sutera et al. [2016] to the case of context-dependent features.

Whereas recent works tackled the question of (in)consistency of the MDA [Ramosaj and Pauly, 2019, B´enard et al., 2021], there exists no general result establishing the consistency of MDI toward population quantities when computed with the original random forest algorithms: all existing results about MDI focus on modified random forests version with, in some cases, strong assumptions on the regression model. Therefore, there are no guarantees that using impurity-based variable importance computed via random forests is suitable to select variables, which is nevertheless often done in practice.

Agenda. In this paper, we focus on the regression framework and derive theoretical properties about the MDI used in Breiman’s [2001] random forests. Section 2 is devoted to notations and describes tree and forest construction, together with MDI calculation. The main results are gathered in Section 3. We prove that both population MDI and empirical MDI, computed with Breiman’s random forests, can be seen as a percentage of explained variance and are directly related to the quadratic risk of the forest, a result already proved by Louppe et al. [2013] and Sutera et al. [2016] for the population MDI in presence of categorical features. We also derive the expression of the sum of MDIs for two groups of variables that are independent and do not interact, which is at the core of our analysis. The analysis highlights that fully-developed random forests (whose tree leaves contain exactly one observation) produce inaccurate variable importances and should not be used for that purpose. In Section 4, we establish that for additive regression models with independent inputs, the MDI of each variable takes a very simple, interpretable form, which is the variance of each univariate component ). We prove that empirical MDI computed with Breiman’s forest targets this population quantity, which is nothing but a standard way to decompose the variance of the output. Hence, in the absence of input dependence and correlation, MDI computed with random forests provides a good assessment of the variable importance. To the best of our knowledge, it is the first result proving the good properties of the empirical MDI computed with Breiman’s forests. To move beyond the additive models and understand the impact of interactions, we study a multiplicative model in Section 5. In this model, MDI is ill-defined and one needs to aggregate many trees to obtain a consistent MDI value. Averaging trees is known to be of great importance to improve accuracy but it turns out to be mandatory to obtain consistent variable importance measure in the presence of interactions. The impact of dependence between input variables is studied in Section 6. We stress out that correlated variables are more likely to be chosen in the splitting procedure and, as a consequence, exhibit a larger MDI than independent ones. As for the presence of interactions, this highlights the importance of computing MDI by averaging many trees. Proofs are postponed to Section 7. Experiments on MDI can be found on the ArXiv version of this paper.

2 Notation and general deﬁnition

We assume to be given a data set observations (X) distributed as the generic pair (X. Our aim is to estimate the regression function , defined as m(X) = E[Y |X], using a random forest procedure and to identify relevant variables, i.e. variables on which m depends.

Remark 1. Note that we confine the analysis to the regression setting with (bounded) continuous input variables. Extending our work to the classification setting is not straightforward, since our main result relies on the additive regression framework which does not have any equivalent in classification. Assuming that all input variables are continuous is a mild and common hypothesis in the random forest literature [see, e.g., Arlot and Genuer, 2014, Wager and Walther, 2015, Zhou and Hooker, 2021, just to name a few] which drastically eases the mathematical analysis.

2.1 CART construction and empirical MDI

CART [Breiman et al., 1984] is the elementary component of random forests [Breiman, 2001]. CART construction works as follows. Each node of a single tree T is associated with a hyper-rectangular cell included in [0. The root of the tree is [0itself and, at each step of the tree construction, a node (or equivalently its corresponding cell) is split in two parts. The terminal nodes (or leaves), taken together, form a partition of [0. An example of such tree and partition is depicted in Figure 1, whereas the full procedure is described in Algorithm 1.

We define now the CART-split criterion. To this aim, we let generic cell and ) be the number of data points falling into A. A split in A is a pair (j, z), where j is a dimension in {1, . . . , d} and z is the position of the cut along the j-th coordinate, within the limits of be the set of all such possible cuts in A. Then, for any (, the CART-split criterion [Breiman et al., 1984] takes the form

Figure 1: A decision tree of depth k = 2 in dimension d = 2 (right) and the corresponding partition (left).

where the average of the ’s belonging to ), with the convention 0/0 = 0. At each cell A, the best split () is finally selected by maximizing over

To remove ties in the argmax, the best cut is always performed along the best cut direction , at the middle of two consecutive data points. Once the tree has been built, the tree prediction ) for a new query point x is computed as the average of the falling into the same leaf as x.

The CART-split criterion ) can be rewritten as the difference in impurity between the cell A and its two children, where the impurity is simply defined as the variance of the output in regression [see also Chapter 4 in Breiman et al., 1984]. The impurity is thus related to the splitting criterion and can be used to assess variable importances via MDI. More precisely, the Mean Decrease in Impurity (MDI) for the

variable computed via a tree T is defined by

where the sum ranges over all cells A in T that are split along variable the fraction of observations falling into A. In other words, the MDI of the weighted decrease in impurity related to splits along the variable

2.2 Theoretical CART construction and population MDI

In order to study the (empirical) MDI defined in equation (3), we first need to define and analyze the population version of MDI. First, we define a theoretical CART tree, as in Algorithm 1, except for the splitting criterion which is replaced by its population version. Namely, for all cells A and all splits (, the population version of the CART-split criterion is defined as

Therefore in each cell of a theoretical tree , the best split () is chosen by maximizing the population version of the CART-split criterion that is

Of course, in practice, we cannot build a theoretical tree since it relies on the true distribution (X, Y ) which is unknown. A theoretical tree is just an abstract mathematical object, for which we prove properties that will be later extended to the (empirical) CART tree, our true object of interest.

As for the empirical MDI defined above, the population MDI for the variable computed via the theoretical tree is defined as

where all empirical quantities have been replaced by their population version and the theoretical CART tree is used instead of the empirical CART tree defined in Section 2.1. We also let

Random forest A random forest is nothing but a collection of several decision trees whose construction has been randomized. In Breiman’s forest, CART procedure serves as base learner and the randomization is performed in two different ways:

1. Prior to the construction of each tree, a sample of the original data set is randomly drawn. Only this sample is used to build the tree. Sampling is typically done using bootstrap, by randomly drawing n observations out of the original n observations with replacement.

2. Additionally, for each cell, the best split is not selected along all possible variables. Instead, for each cell, a subsample of mtry variables is randomly selected without replacement. The best split is selected only along these variables. By default, mtry = d/3 in regression.

Random forest prediction is then simply the average of the predictions of such randomized CART trees. Similarly, the MDI computed via a forest is nothing but the average of the MDI computed via each tree of the forest.

In the sequel, we will use the theoretical random forest (forest that aggregate theoretical CART trees) and the population MDI to derive results on the empirical random forest (forest that aggregate empirical CART trees; the one widely used in practice) and the empirical MDI.

3 Main theoretical result

For any theoretical CART tree , and for any , we denote by the truncation of , that is the subtree of rooted at [0, in which each leaf has been cut at most k times. Let ) be the cell of the tree function and any cell

be the variance of the function f in the cell A with respect to the distribution of X. Proposition 1 states that the population MDI computed via theoretical CART trees can be used to decompose the variance of the output, up to some residual term which depends on the risk of the theoretical tree estimate.

Proposition 1. Assume that is a noise satisfying and almost surely, for some constant . Consider a theoretical CART tree . Then, for all

where Xis an i.i.d. copy of X.

Note that few assumptions are made in Proposition 1, which makes it very general. In addition, one can see that the sum of population MDI is close to the used to assess the quality of regression model. The population is defined as

Hence, the sum of MDI divided by the variance of the output corresponds to the percentage of variance explained by the model, which is exactly the population Therefore, Proposition 1 draws a clear connection between MDI and the very classical

We say that a theoretical tree is consistent if limtheoretical tree is consistent, then its population ] as shown in Corollary 1 below.

Corollary 1. Grant assumptions of Proposition 1. Additionally, assume that and, almost surely, lim. Then, for all , there exists K such that, for all k > K,

Consistency (and, in this case, tree consistency) is a prerequisite when dealing with algorithm intepretability. Indeed, it is hopeless to think that we can leverage information about the true data distribution from an inconsistent algorithm, intrinsically incapable of modelling these data. Therefore, we assume in this section that theoretical trees are consistent and study afterwards variable importances produced by such algorithm. This strategy has been also adopted in Ramosaj and Pauly [2019], who assume the consistency of the (infinite) empirical random forests [Assumption A5, page 6; see also Assumption A2, page 9 in B´enard et al., 2021]. In the next sections, we will be able to prove tree consistency for specific regression models, allowing us to remove the generic consistency assumption in our results, as the one in Corollary 1.

Corollary 1 states that if the theoretical tree is consistent, then the sum of the MDI of all variables tends to the total amount of information of the model, that is V[m(X)]. This gives a nice interpretation of MDI as a way to decompose the total variance V[m(X)] across variables. Louppe et al. [2013] prove a similar result when all features are categorical. This result was later extended by Sutera et al. [2016] in the case of context-dependent features. In their case, trees are finite since there exists only a finite number of variables with a finite number of categories. The major difference with our analysis is that trees we study can be grown to arbitrary depth, since we consider continuous input variables, along which an infinite number of splits can be performed. We thus need to control the error of a tree stopped at some level k, which is exactly the right-hand term in equation (5).

According to Corollary 1, the sum of the MDI is the same for all consistent theoretical trees: even if there may exist many theoretical trees, the sum of MDI computed for each theoretical tree tends to the same value, regardless of the considered tree. Therefore, all consistent theoretical tree produce the same asymptotic value for the sum of population MDI.

In practice, one cannot build a theoretical CART tree or compute the population MDI. Proposition 2 below is the extension of Proposition 1 for the empirical CART procedure. Let be the (empirical) CART tree built with data set and let, for all be the truncation of . Denote by ] the empirical variance of Y computed on the data set . Define, for any function , the empirical quadratic risk via

Proposition 2 (Empirical version of Proposition 1). Let be the CART tree, based on the data set

where is the estimate associated to , as defined in Algorithm 1.

Note that equations (5) and (6) in Proposition 1 and Proposition 2 are valid for general tree construction. The main argument of the proof is simply a telescopic sum of the MDI which links the variance of Y in the root node of the tree to the variance of Y in each terminal node. These equalities hold for general impurity measures by providing a relation between root impurity and leaves impurity. As in Proposition 1, Proposition 2 proves that the of a tree can be written as

which allows us to see the sum of MDI as the percentage of variance explained by the model. This is particularly informative about the quality of the tree modelling when the depth k of the tree is fixed.

Trees are likely to overfit when they are fully grown. Indeed, the risk of trees which contain only one observation per leaf is exactly zero. Hence, according to equation (6), we have

and the of such tree is equal to one. Such does not mean that trees have good generalization error but that they have enough approximation capacity to overfit the data. Additionally, for a fully grown tree

For fully grown trees, the sum of MDI contains not only all available information V[m(X)] but also the noise in the data. This implies that the MDI of some variables are higher than expected due to the noise in the data. The noise, when having a larger variance than the regression function, can induce a very important bias in the MDI by overestimating the importance of some variables. The bias of MDI has already been empirically studied. To circumvent the overfitting problem of MDI computations (using a single data set to build the trees and estimate the variable importances), Zhou and Hooker [2021] use a test set to compute MDI that are less biased. A quantification of the MDI bias has been proposed recently in Li et al. [2019] in which they show that deep trees tend to exhibit larger MDI bias for irrelevant variables. Their analysis provides finite-sample bounds for MDI of irrelevant variables whereas our analysis is asymptotic for both relevant and irrelevant variables.

The above discussion stresses out that, when interested by interpreting a decision tree, one must never use the MDI measures output by a fully grown tree. However, if the depth of the tree is fixed and large enough, the MDI output by the tree provides a good estimation of the population MDI as shown in Theorem 1.

Model 1. The regression model satisfies is continuous, X admits a density bounded from above and below by some positive constants and independent Gaussian noise of variance

Theorem 1. Assume Model 1 holds and that for all theoretical CART tree surely,

Let be the CART tree based on the data set . Then, for all there exists such that, for all k > K, for all n large enough, with probability at least 1

As for Corollary 1, Theorem 1 relies on the consistency of theoretical trees, which is essential to obtain positive results on tree interpretability. It is worth noticing that Theorem 1 is not a straightforward extension of Corollary 1. The proof is based on the uniform consistency of theoretical trees and combines several recent results on tree partitions to establish the consistency of empirical CART tree.

It is not possible in general to make explicit the contribution of each MDI to the sum. In other words, it is not easy to find an explicit expression of the MDI of each variable. This is due to interactions and correlation between inputs, which make difficult to distinguish the impact of each variable. Nevertheless, when the regression model can be decomposed into a sum of two independent terms, we can obtain more precise information on MDI. To this aim, let, for any set X

Model 2. There exists are independent and

where are continuous functions, is a Gaussian noise pendent of X and X admits a density bounded from above and below by some positive constants.

Lemma 1. Assume Model 2 holds. Then, for all , the criterion not depend on and is equal to . Besides, any split leaves the variance of unchanged.

Lemma 1 will be used to prove Proposition 3 below but is informative on its own. It states that if the regression model can be decomposed as in Model 2, the best split along coordinates in J does not depend on or on the ranges of coordinates in

Proposition 3. Assume Model 2 holds. Let be a tree built on distribution (Xbe the truncation of the tree at level k. Similarly, let a tree built on distribution (Xbe the truncation of the tree at level k. If for any tree , almost surely,

then, for any tree built on the original distribution (X, Y ), almost surely,

Proposition 3 states that the consistency of any theoretical trees results from the consistency of all theoretical trees built on subsets () of the original set of variables, under Model 2. This is of particular significance for proving the consistency of theoretical tree for a new model which can be rewritten as a sum of independent regression functions: we can then deduce the tree consistency from existing consistency results for each regression function. Note that there are no structural assumptions on the functions apart from the continuity. In particular, the class of functions in Model 2 is wider than additive functions. Note also that importance measures via random forests have been designed for groups of variables. For instance, Gregorutti et al. [2015] extended the MDA to groups of variables and studied it theoretically in an additive regression framework. More recently, a tree algorithm tailored for groups of variables have been proposed by Poterie et al. [2019].

Theorem 2 below establishes the limiting value of the sum of MDI in subgroups J and , both for the population version and the empirical version of the MDI, as soon as all theoretical trees are consistent.

Theorem 2. Under the assumptions of Proposition 3, for all , there exists K such that, for all k > K,

Besides, for all , there exists K such that, for all k > K, for all n large enough, with probability at least 1

According to Theorem 2, the limiting value of the MDI for subgroup J (resp. subgroup ) is equal to the variance of the corresponding component of the regression function, that is )]). We will use Theorem 2 in the Section 4 to derive explicit expressions for the MDI of each variable, assuming a specific form of the regression function.

4 Additive Models

To pursue our analysis, we consider in this section a specific type of regression models: additive regression functions with independents inputs.

Model 3 (Additive model). The regression model writes

where each is continuous; is a Gaussian noise , independent of X; and X

Additive regression models were popularized by Stone [1985] [see also Hastie and Tibshirani, 2017]. They were used as a generic framework for studying random forests in some previous works Klusowski [2020], Scornet et al. [2015], notably due to their simple structure and their absence of interactions. Indeed, due to the model additivity, there is no interaction between variables: the contribution of each variable for predicting the output is reduced to its marginal contribution. Since we also assume that features are independent, the information contained in one variable cannot be inferred by the values of other variables.

By considering a model with no interaction and with independent inputs, we know that the contribution of a variable has an intrinsic definition which does not depend on other variables that are used to build the model. In Model 3, the explained variance of the model V[m(X)] takes the form

which holds only because of independent inputs and the absence of interactions. The variance explained by the jth variable is defined unambiguously, and independently of which variables are considered in the model, as )]. Therefore any importance measure for which aims at decomposing the explained variance must output )]. It turns out that the MDI computed via CART trees converges to this quantity.

Theorem 3 (Additive model). Assume that Model 3 holds. Let be any theoretical CART tree and be the empirical CART tree. Then, for all , there exists K such that, for all k > K, for all j,

Moreover, for all , there exists K such that, for all k > K, for all n large enough, with probability at least 1

Since the MDI computed via random forests is nothing but the average of MDI computed by trees, Theorem 3 also holds for MDI computed via random forests. To the best of our knowledge, Theorem 3 is the first result highlighting that empirical MDI computed with CART procedure converge to reasonable values that can be used for variable selection, in the framework of Model 3.

Contrary to Theorem 2, Theorem 3 does not assume the consistency of the theoretical tree. Indeed, in the context of additive models, one can directly take advantage of Scornet et al. [2015] to prove the consistency of theoretical CART trees.

Surprisingly, the population version of MDI has the same expression as the population version of MDA (up to factor 2), as stated in Gregorutti et al. [2017]. Thus, in the particular context of additive models with independent features, both MDI and MDA target the same quantity, which is the natural way to decompose the total variance. In this context, MDI and MDA can then be employed to rank features and select variables based on the importance values they produce.

Note that MDI is computed with truncated trees, i.e. trees that contain a large number of observations in each node. This is mandatory to ensure that the variance of the output in the resulting cell is correctly estimated. As mentioned before, considering fully grown trees would result in positively-biased MDI, which can lead to unintended consequences for variable selection. We therefore stress that MDI must not be computed using fully grown trees.

Theorem 3 proves that MDI computed with any CART tree are asymptotically identical: the MDI are consistent across trees. The only interest to use many trees to compute the MDI instead of a single one relies on the variance reduction property of ensemble methods, which allows us to reduce the variance of the MDI estimate when using many trees.

Remark: invariance under monotonous transformations Tree-based methods are known to be invariant by strictly monotonous transformations of each input. Letting being any monotonous transformation applied to variable regression model writes

where ) are the new input variables. Assuming that Theorem 3 can be applied in the more general setting where 1])), the MDI for this new problem satisfies

Therefore the asymptotic MDI is invariant by monotonic transformation, assuming that Theorem 3 holds for any marginal distribution of X (with independent components).

The most famous instance of additive regression models is the well-studied linear model [see, e.g., Rencher and Schaalje, 2008, Searle and Gruber, 2016].

Model 4 (Linear model). The regression model writes

where, for all is a Gaussian noise , independent of X; and X

As for Model 3, there is only one way to decompose the explained variance for linear models with independent input, as stated by Nathans et al. [2012] and Gr¨omping [2015] (and the references therein), which is below proves that MDI converge to these quantities and provides information about the theoretical tree structure in Model 4.

Theorem 4 (Linear model). Assume that Model 4 holds. For any cell [0, 1], the coordinate which maximizes the population CART-split criterion (4) satisfies

and the splitting position is the center of the cell; the associated variance reduction is

Let be any theoretical CART tree and be the empirical CART tree. Then, for all , there exists K such that, for all k > K and for all j,

Moreover, for all , there exists K such that, for all k > K, for all n large enough, with probability at least 1

Theorem 4 establishes that, for linear models with independent inputs, the MDI computed with CART trees whose depth is limited is exactly the quantity of interest, which depends only on the magnitude of , since all variables have the same variance. Theorem 4 is a direct consequence of Theorem 3. However, for linear models, one can compute explicitly the best splitting location and the associated variance decreasing, which is stated in Theorem 4. Being able to compute the variance decreasing for each split allows us to compute the MDI directly, without using Theorem 3. Note that the splitting location and variance reduction has been first stated by Biau [2012] and then by Ishwaran [2013].

Remark 2. All our results focus on the asymptotic behaviour of the MDI computed with CART. A natural next step in our analysis would be to derive rates of convergence for MDI, in order to quantify the accuracy of a variable ranking based on MDI. Unfortunately, we are limited by the (asymptotic) tree consistency assumption (see assumption in Corollary 1). If we had access to the rate of consistency of a tree, we could leverage on that to establish upper bounds on the rate of consistency of MDI. Although interesting, this line of work seems difficult. However, some generic arguments based on partition shapes have been used to establish rate of consistency for groups of MDI [MDI of irrelevant variables, see Theorem 1 in Li et al., 2019]. Interesting finite-sample lower bounds on MDI can also be found in Klusowski [2019].

In this section, we studied additive (linear) models and proved that, for these models with independent inputs, MDI computed with truncated CART is consistent. This result is based on CART consistency proved in Scornet et al. [2015] for additive models with independent inputs. One can naturally wonder what happens if the additivity assumption (or the independence assumption) is removed. In these cases, the general approach, developed in this section, is unfortunately not valid. The next two sections focus on two specific settings, and show that, when one of these two assumptions is removed, the MDI is ill-defined.

5 A model with interactions

In the absence of interaction and dependence between inputs, the MDI is a measure of variable importance which is independent of the set of variables included in the model, as stated in Theorem 3. However, this is not true as soon as we consider classes of models that present interactions or dependence. In this section, we study the influence of interactions via the following model.

Model 5 (Multiplicative model). Let . The regression model writes

where is a Gaussian noise , independent of X; and X

Theorem 5 (Multiplicative model). Assume that Model 5 holds. For any cell A = , the coordinate which maximizes the population CART-split crite- rion (4) satisfies

and the splitting position is the center of the cell; the associated variance reduction is

Let be any theoretical CART tree and be the empirical CART tree. Then, for all , there exists K such that, for all k > K,

Moreover, for all , there exists K such that, for all k > K, for all n large enough, with probability at least 1

Theorem 5 gives the explicit splitting position for a model with interactions. Deriving splitting positions allows us to prove that the theoretical tree is consistent which, in turns, proves that the sum of MDI converges to the explained variance V[m(X)], according to Theorem 1.

We are also interested in obtaining the exact MDI expression for each variable, as established for additive models. However, Theorem 2 no longer applies since the regression model cannot be decomposed into independent additive components. It turns out to be impossible to derive explicit expression for each MDI in this model. To see this, note that there exist many theoretical trees in Model 5. Two of them are displayed in Figure 2. They result in the same partition but the first split can be made either along , right). Surprisingly, the variable importance computed with these trees is larger for the variable that is split in the second step. This exemplifies that splits occurring in the first levels of trees do not lead to the largest decrease in variance, which in turn, shows that variable importances based on the frequency of splitting along a variable in the first level(s) of a tree are inaccurate. Nonetheless, this holds only when interactions are present: in the case of the additive models defined in Section 4, the decrease in variance is stronger in the first tree levels. A direct consequence of this fact is that two different theoretical tree can output two different variable importance, as shown by Lemma 2 below.

Figure 2: Two theoretical tree partitions of level k = 2: the first split is performed along ) for the tree on the left (resp. on the right).

Lemma 2. Assume that Model 5 holds. Then, there exists two theoretical trees

According to Lemma 2, there exist many different theoretical trees for Model 5 and the MDI may vary when computed with different theoretical trees. This is a major difference with additive models for which each theoretical tree asymptotically output the same MDI. Since MDI are usually used to rank and select variables, the fact that each tree can output a different MDI, and therefore a different variable ranking, is a major drawback for employing this measure in presence of interactions. One way to circumvent this issue could be to compute the MDI via a random forest: the randomization of splitting variables yields different trees and the aggregation of MDI across trees provides a mean effect of the variable importance. For example, in Model 5, one can hope to obtain importance measure that are equal since Model 5 is symmetric in all variables. This is impossible with only one tree but is a reachable goal by computing the mean of MDI across many trees as done in random forests. More generally, for simple regression problems, a single tree may be sufficient to predict accurately but many shallow trees are needed to obtain accurate MDI values.

6 A model with dependent inputs

Our previous results relies on the (often unrealistic) assumption that input variables are uniformly distributed over [0, and thus independent. To gain insights on the impact of input dependence on MDI, we study a very specific model in which input features are not independent. We will prove that even in this very simple model, MDI has some severe drawbacks that need to be addressed carefully. Accordingly, we consider the simple case where the input vector X ) is of dimension two and has a distribution, parametrized by , defined as

The distribution of X is uniform on 2squares on the diagonal. Examples of such distribution are displayed in Figure 3. For such distribution, the correlation between

Figure 3: Illustration of distributions for X, with parameter (right).

is given by Lemma 3.

Lemma 3. Let X as defined in (9). Then

For is uniform over [0and accordingly, the correlation is null between the two components of X, as stated in Lemma 3. When (i.e. the number of squares) increases, that is the size of each square decreases, the distribution concentrates on the line . Therefore, when tends to infinity, the correlation should tend to 1, which is proved in Lemma 3.

The distribution defined in (9) is rather unusual, and one can wonder why not considering Gaussian distributions instead. This choice is related to the thresholding nature of decision trees. Since we want to compute explicitly the splitting criterion along each coordinate, we must have a closed expression for the truncated marginals (restriction to any rectangle of [0), which is not possible with Gaussian distribution. The distribution defined in (9) allows us to compute easily both truncated marginals and the joint distribution.

Model 6. Let . Assume that

where (is independent of (independent noise distributed as

In the framework of Model 6, Proposition 4 below states that the CART-split criterion has an explicit expression and highlights that splits along positively correlated variables () are more likely to occur compared to splits along independent ones (). Even if the model is very simple, it is the first theoretical proof that CART splitting procedure tends to favor positively correlated variables. Note however that considering negatively correlated variables will result in an opposite effect, i.e. a tendency to favour independent variables compared to negatively correlated ones.

Proposition 4. Assume that Model 6 holds. Then, the following statements hold:

(i) The splitting criterion has an explicit expression. For , each split is performed at the center of the support of the chosen variable.

Statement (ii) in Proposition 4 proves that a positive correlation between two variables increases the probability to split along one of these two variables. Indeed, in our particular model, the marginal effect of on the output must be at least twice the effect of in order to split along It is likely that the way the correlation impact the variable selection in trees depends both on the sign of the correlation and on the signs of coefficients in the linear model. Nevertheless, Proposition 4 proves that input dependence has an influence on variable selection in CART procedures. Theorem 6 provides the limiting MDI values given by theoretical and empirical CART trees, in Model 6.

Theorem 6. Let . Assume that Model 6 holds. Let be any theoretical CART tree and be the empirical CART tree. Then, for all , there exists K such that, for all k > K,

Additionally, for all , there exists K such that, for all k > K, for all n large enough, with probability at least 1

Theorem 6 gives the limiting values for the MDI. Unfortunately, since are correlated, it is only possible to have information on the sum of the two MDI of rather than on each one of them. According to Lemma 3, a simple calculation shows that the sum of importances of

Therefore, the group of variables has a larger importance because of their positive correlation. In this case, the amount of information provided by the two variables is larger than that provided by each one of them. This is a very important difference compared to the independent additive case, in which the sum of contributions of each variable is equal to the contributions of all variables. Here, even without interaction effects, this property does not hold, which leads to larger MDI for variables that are positively correlated. As mentioned before, the opposite effect would hold if the variables had a negative correlation or if they had coefficients of opposite signs in the linear model. The impact of correlation has been thoroughly investigated empirically for MDI Nicodemus and Malley [2009] and MDA Strobl et al. [2008] but we have theoretically shown above under Model 6 that correlation changes the MDI.

Even if the limiting value MDI) is known, we have no in- formation on how this quantity is split between variable inside the tree . Indeed, we can find two theoretical trees which produce very different MDI as stated in Lemma 4.

Lemma 4. Let . Assume that Model 6 holds. Then, there exists two theoretical trees

Even in the case of a simple linear model with correlated input, it is not wise to use the importance of a single tree to measure the impact of this variable on the output, since this measure can vary drastically between two different trees. Instead, one should rather use an average of this measure across many shallow trees, hoping that randomizing the eligible variables for splitting ensure enough tree diversity in the forest, which in turn, leads to more balanced variable importances.

The proof of Lemma 4 relies on exhibiting a tree whose early splits are made along only, until X is uniformly distributed in each cell. For this tree, the importance of is larger than the importance of have symmetric roles, one can also build a tree whose early splits are made along only. The difference of importance for between these two trees can be computed exactly, thanks to statement (i) and (ii) in Proposition 4.

Acknowledgements. We greatly thank the associate editor and the two referees for their careful reading and numerous insightful comments that strongly helped to improve the quality and the readability of the manuscript.

7 Proofs

Proof of Proposition 1. Let be a theoretical CART tree and define, for all the variance of the tree (the truncation of T at level k) as

where stands for the number of terminal nodes in is the set of terminal nodes in )]. By definition of the impurity measure, note that, for all k, the quantity corresponds to the reduction of impurity between level k and level k+1. Therefore, the impurity measure rewrites, for any

where ] by definition. Additionally,

yielding the desired conclusion

Proof of Corollary 1. Using notations of the proof of Proposition 1, for all x and, by assumption, almost surely, liming to the dominated convergence theorem,

Therefore,

Proof of Proposition 2. Equation (11) in the proof of Proposition 1, written with empirical quantities, leads directly to the first statement.

Proof of Theorem 1.

Uniform convergence of theoretical trees. Note that a tree is nothing but a sequence of splits. Therefore, any tree T can be seen as a sequence () such that • () represents the first split of the tree defined, for a split occurring along variable j at position s, as

• Each block () represents the mth split of the tree occurring along variable j at position s defined as

• Splits are ordered arbitrarily.

• In order to obtain a complete tree, we associate with all nodes whose construction is stopped, the split (0, . . . , 0). Since the split position belongs to [0, 1], we have

For any tree T represented by the sequence (

with 6) being a compact of ). Now, let

Set . Since the population CART-split criterion , defined in (4) is non negative, we have

Therefore, for all . Because of the uniform continuity of the splitting criterion (continuous on a compact), for all are closed.

Assume that for all . We know that 6) is compact and that, for all is a closed subset of 6). Then, according to Cantor’s intersection theorem