3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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]$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.