# Random forest permutation test: Is permutation of the training set appropriate?

I have a rather high-dimensional data set (p > 1000) with several variables ranking significantly higher than the rest in terms of variable importance (measured by Gini impurity).

However, these variables are highly correlated and thus it is unclear whether each variable actually holds unique information or simply ranks high due to correlation to the causal variable.

My general approach for testing the significance of the importance of variables is a bootstrap permutation test, i.e. I first bootstrap from the training data and build a random forest model and then permute the columns in the out-of-bootstrap samples and check if I observe a significant decline in accuracy.

In these cases my assumption under H0 is that these variables are completely uninformative and thus it shouldn't matter whether I permute the column of the training or test set.

However, in the above case, the assumption does not hold. The variables are predictive and and due to sub-sampling of variables at each split, they will get selected during model training. If I now permute the corresponding columns of the test set, it is clear that the performance will drop, although this does not indicate whether these variables hold unique information at all.

Therefore, I'm thinking about changing my approach in the sense that I'm permuting the variables in the training set and not in the test set.

My question is: Is this approach valid? Is permutation of variables in the training set a better approach in general? If not, in which cases would it be not appropriate?

• This shouldn't be a problem, random forests are stochastic enough that they should eliminate the effect of correlated variables. The argument mtry decides how many random features you select during each tree, if this value is small enough then you are likely not to select correlated features so there won't be a problem. Commented Jan 9, 2019 at 7:42
• @user2974951 I don't see how mtry should control for that, IMO small mtry would make it even worse. if y ~ x_1 and x_2 ~ x_1 then x_2 will be predictive for y and thus the model will split upon it more often than random. So if I then analyze the variables importance using information from the number of splits,x_2 will seem important even though it does not hold unique information. Commented Jan 9, 2019 at 11:05
• There's not much you can do about that, permutation tests won't save you either. If two variables are highly correlated then they will exert a similar effect on the outcome, you cannot determine causality with such an approach. Maybe a partial correlation can give you some idea of the situation. Commented Jan 9, 2019 at 11:25
• @user2974951 I definitely agree on that if on the causality part, however I just want to check whether a feature 'adds information' to a model by analyzing the performance of the model after permuting this feature. The assumption is that if it does not give a gain of predictive power, it's not holding unique information. Again, I agree that this doesn't tell me whether the feature is causal / non-causal but the approach should give insight into whether it's information content is redundant and 'covered' by other features. With this goal in mind, does permutation seem like a good approach? Commented Jan 9, 2019 at 11:35
• Maybe... it is worth trying, although this does seem unecessary to me. You could just drop variables sequentially and check each model accuracy, if a variable adds no new information the accuracy should remain the same so you can conclude that variable is bunk. Commented Jan 9, 2019 at 11:46

To answer your question, it seems the same to me whether you scramble columns in the set you train on or before you pass the test set: Effectively if you scramble before training, the model expects things in scrambled order, and then the canonical order looks scrambled to it. Or if you train on the canonical order, then the scrambled order looks scrambled.

I wouldn't take either of these approaches to decide feature importance, because when I misplace a column, I don't just misplace it in isolation; I displace the one where it has to go. Maybe you could devise some crazy Hamming distance scheme to figure out how much to weight the inaccuracies of models training on scrambled datasets, but this seems like it would require a lot of models and be computationally expensive, and it shouldn't be necessary.

Generally you can just train a random forest on your data and then look to see how many nodes chose particular features as the one to split on. Sklearn's random forest has _feature_importances, for example. As you mention, each node already takes a random subset of features to decide splits, so in a way you already get your scramble.

If you're concerned about duplication of information across features, and because you have an absurd number of features, consider feature reduction techniques. You want $$N$$, the number of samples, to be much much greater than $$p$$, because curse of dimensionality: You can't really fill the super-high-dimensional 1000-dimensional space with examples; its volume is just too large. Your results will be pretty unpredictable nonsense unless the problem is constrained enough that models can find a somewhat stable function (or decision surface or whatever).

• Thanks for your answer. Unfortunately, feature importance measures derived from the number of times they are used for splits (such as Gini importance) does not help in cases of correlated features. For example, suppose you have two two feature vectors with are highly correlated to the response but identical. Due to variable sub-sampling at each split, both of them will get an equally high importance assigned, even though one is completely useless in terms of performance! Commented Jan 8, 2019 at 18:33
• That's also why I'm convinced that permuting only the column of the test set is a bad approach. For example, consider the case where you have 4 variable, x1, x2, x3 and x4. Also assume that x1 = x2 and highly predictive while x3 and x4 are noise. Let's say that the random forest has an mtry = 2. Now, if you train the forest on this unpermuted data, x1 and x2 will be split upon equally often. Therefore, if you suddenly permute column x2 in the test set, the performance of the random forest will drop, even though you didn't remove information! Commented Jan 8, 2019 at 18:39
• On the other hand, if you permute x2 before training, the model will split by x1 a lot more often and the performance will stay more or less the same when applied to a unpermuted test set. Commented Jan 8, 2019 at 18:40
• No, the proper approach here is to deduplicate features, or if you know columns 1 and 2 are the same or highly correlated and insist on not deduplicating, then the importance is the sum of their importances. Permuting before vs after training is functionally equivalent. It won't split more often on x1 if you permute before training; it will go find where you put x2 and split on that feature just as much as it did in the unscrambled case. Commented Jan 9, 2019 at 16:27
• You asked if the approach is a good idea. I and @user2974951 have given what insight we can. Commented Jan 9, 2019 at 17:30