# Feature selection with partial permutation

For feature selection, permutation tests are biased in favor of those categorical variables with a large number of levels [White1994]. Besides, it has been proposed [Deng2011] that partial permutations can be used to increase efficiency.

However, can partial permutations also solve the bias problem?

• I am sorry to bother you again, but I still think that you have to make clear what you mean by permutation tests. Permutation tests are not biased. Jun 17 '14 at 11:48
• Also I think it is a bit difficult to keep track of the conversation we are having here. Given the edit you made it is totally a different question. I don't know if you should have issued another question at this point. Maybe some moderator can help us on this. Jun 17 '14 at 12:06
• Thank you @Simeone for your input! I think the question is still valid after the edit, even more clear. In a nutshell, I would like to know if partial permutations can help to solve the bias problem of permutation tests in feature selection (especially when using Random Forests). Jun 17 '14 at 12:19
• As I see from your answer, you argue that there is not such a bias. However, I am still confused and I try to read articles as fast as possible to have a clear picture. Jun 17 '14 at 12:19

I think there might be a bit of confusion here.

The efficacy of the permutation approach to compute $p$-values is not questioned in the paper you are citing. Random forest's Gini importance is blamed to be biased towards categorical variables with lots of values. Also Random forest's variable importance based on the accuracy reduction after permutations is biased, even if you use sampling with no replacement: i.e. cforest is biased as well. That does not compute $p$-values indeed.

Moreover, you cited Altmann's paper which does not mention partial permutations. I guess you are talking about Deng2011. There is quite a bit of literature about biases of importance measures that can be solved with $p$-values computations. You might get back to Splitting Criterion papers like Kononenko1995 and Dobra2001 (beware the latter talks about bias in selection rather than in magnitude).

In Deng2011, the permutation approach simulates via Monte Carlo a $p$-value. The $p$-value takes into account the distribution of the feature importance under the null hypothesis of independence between feature and class. A $p$-value is unbiased because it compares the feature importance value you obtain to the one you would obtain at random.

Partial permutation have a different null hypothesis behind: the feature and the class are "almost" independent. The amount of independence in the null hypothesis is quantified by the permutation ratio $\delta$. $\delta$ is chosen to enhance interpretability I guess: if it is too high all $p$-values will be close to 1 and the decimal digits will differentiate between more and less important features. The authors indeed propose the default value to be $\delta = 0.2$, much less than 1.

• Thank you @Simeone for your reply. You are right, the link is not correct and the partial permutation is proposed only for efficiency. However, isn't true that the partial permutation can also reduce the bias of the importance score for categorical values with lot of levels. Or, at least, it is possible to detect a trend, e.g. repeating the same permutation test for permutation ratios of 0.2, 0.5 and 1.0 could give an intuition of which variables are more important. Jun 13 '14 at 9:31
• I am not really sure. I think that you restrict the permutations to a limited number of records you don't consider all possible permutations and thus you don't consider the full distribution of the feature importance. In case, how would you detect the trend changing the permutation ratios? Jun 15 '14 at 22:17

I came out with the explanation.

Why permutation tests are biased in favor of those categorical variables with a large number of levels?

If the range of a variable is small, a permutation of the values will return a similar vector. Therefore, the permutation test concludes that this variable does not give enough information because the score is similar with or without permutation. For example, if the original binary vector is [0 1 0 1 1 1 0 0] and the permuted one is [1 1 0 0 1 0 0 1], 50% of the values are unchanged, which is harder to occur if the variable has more levels.

Can a partial permutation solve the bias problem?

In the partial permutation, only a fraction of the values are shuffled, this percentage is named as the permutation ratio. For each position within the vector, it is considered that a collision occurs when the value in the original and permuted vectors are the same. Thus, the higher the collision probability, the higher the similarity between original and permuted vector. If the permutation ratio is zero, the collision probability is 1 because original and permuted variables are the same. When the ratio is one, we are applying a regular permutation where all the values are permuted. The literature proposes a permutation ratio of 0.2 that leads a range of collision probability between 0.9 and 0.8.

For example, we have the 8-elements original vector [1 2 3 4 3 2 1 0] with a permutation ratio of 6/8=0.75; hence, for simplicity, the last two values are not shuffled. We create our statistics from three permuted vectors, namely [2 4 3 1 2 3 1 0], [1 3 4 3 2 2 1 0] and [2 3 2 3 2 1 1 0]. The permuted vectors have 3, 4 and 2 collisions, respectively. Hence, the collision probability is (3+4+2)/(3*7)=0.375.

In the plot, the collision probabilities have been obtained through simulations over 1000 permutations for each configuration. Each line corresponds to a different dimension, number of values that the variable can take, e.g. a dimension of 2 implies a binary variable.

• Can you elaborate further about collision probabilities? Jun 15 '14 at 22:15
• Ah I got what you mean by permutation test. I don't think it is quite the same meaning of permutation tests of the papers you cited. Try to have a look here researchcommons.waikato.ac.nz/handle/10289/1506 Jun 17 '14 at 11:57
• @Simone, could you have a minute to explain me why is not the same? Jun 17 '14 at 12:22
• I think the misunderstanding originates from the first two sentences of this answer. A permutation test answer the question: is my statistic, computed with the actual feature, significantly better than what I would obtain at random? In order to do so, you permute the feature to make it independent to the target class and compute the value of the statistic, e.g. feature importance. In order to exploit the null hypothesis of independence you have to set what you defined collision probability to 0. Hence, set permutation ratio to 1. Jun 17 '14 at 23:53