Random permutation test for feature selection

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?

-
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 citeseerx.ist.psu.edu/viewdoc/… 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

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).
• The $N$ features with the lowest p-values
• All features with a p-value$<\epsilon$