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 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.
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.
