What are the variable/feature selection that you prefer for binary classification when there are many more variables/feature than observations in the learning set? The aim here is to discuss what is the feature selection procedure that reduces the best the classification error.
We can fix notations for consistency: for $i \in \{0, 1\}$, let $\{x_1^i,\dots, x_{n_i}^i\}$ be the learning set of observations from group $i$. So $n_0 + n_1 = n$ is the size of the learning set. We set $p$ to be the number of features (i.e. the dimension of the feature space). Let $x[i]$ denote the $i$-th coordinate of $x \in \mathbb{R}^p$.
Please give full references if you cannot give the details.
EDIT (updated continuously): Procedures proposed in the answers below
- Greedy forward selection Variable selection procedure for binary classification
- Backward elimination Variable selection procedure for binary classification
- Metropolis scanning / MCMC Variable selection procedure for binary classification
- penalized logistic regression Variable selection procedure for binary classification
As this is community wiki there can be more discussion and update
I have one remark: in a certain sense, you all give a procedure that permit ordering of variables but not variable selection (you are quite evasive on how to select the number of features, I guess you all use cross validation?) Can you improve the answers in this direction? (as this is community wiki you don't need to be the answer writter to add an information about how to select the number of variables? I have openned a question in this direction here Cross validation in very high dimension (to select the number of used variables in very high dimensional classification))