# Negative population variable importance

## EDIT:

Question solved on mathoverflow.

The question is:

Is it possible for the population variable importance to be negative ?

The variable importance is defined below in the context it comes from: random forests. But no knowledge is required about random forests, the question is a simple statement in probability theory, and the reader can skip everything related to statistics.

Consider we run a random forest on $n$ independent realizations of a random vector $(X_1,X_2,X_3,Y)$ assuming $Y$ is a numerical response variable. Let $f$ be the best theoretical classifier defined by $E[Y\mid X_1, X_2, X_3]=f(X_1, X_2, X_3)$.

The variable importance $\hat I_j$ of the $j$-th predictor $X_j$ is defined as follows. For each tree $t$ of the random forest, there's a classifier $\hat f_t$. The mean squared error $MSE_t$ in tree $t$ is the mean squared prediction error in the out-of-bag sample of tree $t$. The $j$-th perturbed mean squared error $MSE_t^{(j)}$ is defined similarly after randomly permuting the values of $j$-th variable in the out-of-bag sample. Finally $\hat I_j$ is defined as the average difference $\overline{MSE}^{(j)} - \overline{MSE}$ over all trees.

Let's take $j=1$ to shorten the notations. In Correlation and variable importance in random forests (Gregorutti & al), an expected result is claimed : when $n$ and $ntree$ go to $\infty$, then $\hat I_1$ goes to the population variable importance $$I_1 = E\left[{\bigl(Y-f(X'_1,X_2,X_3)\bigr)}^2\right] - E\left[{\bigl(Y-f(X_1,X_2,X_3)\bigr)}^2\right]$$ where $X'_1$ is a random variable having the same distribution as $X_1$ but independent of all other random variables $X_2,X_3,Y$. Of course some kind of consistency of the random forest classifier $\hat f$ (aggregate of the $\hat f_t$) is required in order that this convergence result holds.

The question is: "is it possible that $I_1 < 0$?"

In case you are interested in a simple example, the paper Correlation and variable importance in random forests (Gregorutti & al) investigates some particular cases such as the additive case $f(X_1,X_2,X_3)=f_1(X_1)+f_2(X_2)+f_3(X_3)$. It is easy to check that $I_j=2Var\bigl(f_j(X_j)\bigr)$ in this case.

I found the answer in stackoverflow a bit confusing and convoluted, so let me present another approach: Since $X'_1$ is assumed independent of all other variables involved, it follows that

$$E(Y \mid X'_1,X_2, X_3) = E(Y \mid X_2, X_3)$$

Denote $I_{23}$ the sigma algebra generated by $X_2, X_3$ and $I_{123}$ the sigma algebra generated by $X_1, X_2, X_3$. Note that the $I_{23}$ is a subset of $I_{123}$.

So the question the OP asks is whether it is possible that

$$E\left[{\bigl(Y-E(Y \mid I_{23})\bigr)}^2\right] < E\left[{\bigl(Y-E(Y \mid I_{123})\bigr)}^2\right]\;\;\; ??$$

Informally put, we ask : "if we have more information, is it possible that the mean-squared error of our predictor will be larger than the mean-squared error of a predictor that is based on less information"?

Νο.

Since $I_{23}$ is a subset of $I_{123}$, by the Law of Iterated Expectations (the "tower property") it holds that

$$E(Y \mid I_{23}) = E\Big[E(Y \mid I_{23})\mid I_{123}\Big]$$

Inserting this in the inequality under inspection we ask whether it is possible that

$$E\left[{\left(Y-E\Big[E(Y \mid I_{23})\mid I_{123}\Big]\right)}^2\right] < E\left[{\bigl(Y-E(Y \mid I_{123})\bigr)}^2\right]\;\;\; ??$$

Now the two predictors are directly comparable because they are based on the same sigma algebra. And in $L^2$, the best predictor of $Y$ in terms of mean squared error given sigma-algebra $I_{123})$ is the function $E(Y \mid I_{123})$, and not any other function based on the same information set (like $E\Big[E(Y \mid I_{23})\mid I_{123}\Big]$).