Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am confused about permutation analysis for feature selection in a logistic regression context.
Could you provide a clear explanation of the random permutation test and how does it applies to feature selection? Possibly with exact algorithm and examples.

Finally, How does it compare to other shrinkage methods like Lasso or LAR?

share|improve this question
Do you mean something like, e.g., where the entries of a single column of the design matrix are permuted, holding the response and other covariates fixed? If you have a particular reference you are using, it might be helpful to list it. – cardinal Apr 30 '11 at 13:36
I think this link… refers to the right technique. I am currently trying to get back in touch with the lecturer who told me about this method ... – Ugo May 2 '11 at 9:51
Didn't manage to get back in touch with him (Donald Geman) – Ugo May 13 '11 at 17:01
there are unclear points in your question that you might want to clarify. In the linked paper there is a pretty clear description of the algorithm. Do you want to ask something specific about this algorithm? Is it the idea of doing feature selection by computing marginal $p$-values that you want an explanation of? Moreover, you should question Definition 2 in the paper. It is an unsupported claim, which may be a working assumption, but small marginal $p$-values do not in general imply relevance. LAR is, by the way, doing linear regression and is not really for binary responses. – NRH May 13 '11 at 18:08
up vote 7 down vote accepted

(Don't have much time now so I'll answer briefly and then expand later)

Say that we are considering a binary classification problem and have a training set of $m$ class 1 samples and $n$ class 2 samples. A permutation test for feature selection looks at each feature individually. A test statistic $\theta$, such as information gain or the normalized difference between the means, is calculated for the feature. The data for the feature is then randomly permuted and partitioned into two sets, one of size $m$ and one of size $n$. The test statistic $\theta_p$ is then calculated based on this new partition $p$. Depending on the computational complexity of the problem, this is then repeated over all possible partitions of the feature into two sets of order $m$ and $n$, or a random subset of these.

Now that we have established a distribution over $\theta_p$, we calculate the p-value that the observed test statistic $\theta$ arose from a random partition of the feature. The null hypothesis is that samples from each class come from the same underlying distribution (the feature is irrelevant).

This process is repeated over all features, and then the subset of features used for classification can be selected in two ways:

  • The $N$ features with the lowest p-values
  • All features with a p-value$<\epsilon$
share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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