Variable selection procedure for binary classification 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))
 A: Metropolis scanning / MCMC


*

*Select few features randomly for a
start, train classifier only on them
and obtain the error. 

*Make some
random change to this working set --
either remove one feature, add
another at random or replace some
feature with one not being currently
used.

*Train new classifier and get
its error; store in dE the difference
the error on the new set minus the error on the previous set. 

*With probability min(1;exp(-beta*dE)) accept this change, otherwise reject it and try another random change.

*Repeat it for a long time and finally return the working set that has globally achieved the smallest error.


You may extend it with some wiser control of beta parameter. Simpler way is to use simulated annealing when you increase beta (lower the temperature in physical analogy) over the time to reduce fluctuations and drive the algorithm towards minimum. Harder is to use replica exchange.
A: If you are only interested in generalization performance, you are probably better off not performing any feature selection and using regularization instead (e.g. ridge regression).  There have been several open challenges in the machine learning community on feature selection, and methods that rely on regularization rather than feature selection generally perform at least as well, if not better.
A: Greedy forward selection.
The steps for this method are:


*

*Make sure you have a train and validation set

*Repeat the following

*

*Train a classifier with each single feature separately that is not selected yet and with all the previously selected features

*If the result improves, add the best performing feature, else stop procedure


A: A very popular approach is penalized logistic regression, in which one maximizes the sum of the log-likelihood and a penalization term consisting of the L1-norm ("lasso"), L2-norm ("ridge"), a combination of the two ("elastic"), or a penalty associated to groups of variables ("group lasso"). This approach has several advantages:


*

*It has strong theoretical properties, e.g., see this paper by Candes & Plan and close connections to compressed sensing;

*It has accessible expositions, e.g., in Elements of Statistical Learning by Friedman-Hastie-Tibshirani (available online);

*It has readily available software to fit models. R has the glmnet package which is very fast and works well with pretty large datasets. Python has scikit-learn, which includes L1- and L2-penalized logistic regression;

*It works very well in practice, as shown in many application papers in image recognition, signal processing, biometrics, and finance.

A: Backward elimination.
Start with the full set, then iteratively train the classifier on the remaining features and remove the feature with the smallest importance, stop when the classifier error rapidly increases/becomes unacceptable high.
Importance can be even obtained by removing iteratively each feature and check the error increase or adapted from the classifier if it produces it (like in case of Random Forest). 
A: I have a slight preference for Random Forests by Leo Breiman & Adele Cutleer for several reasons:


*

*it allows to cope with categorical and continuous predictors, as well as unbalanced class sample size;

*as an ensemble/embedded method, cross-validation is embedded and allows to estimate a generalization error;

*it is relatively insensible to its tuning parameters (% of variables selected for growing a tree, # of trees built);

*it provides an original measure of variable importance and is able to uncover complex interactions between variables (although this may lead to hard to read results).


Some authors argued that it performed as well as penalized SVM or Gradient Boosting Machines (see, e.g. Cutler et al., 2009, for the latter point).
A complete coverage of its applications or advantages may be off the topic, so I suggest the Elements of Statistical Learning from Hastie et al. (chap. 15) and Sayes et al. (2007) for further readings.
Last but not least, it has a nice implementation in R, with the randomForest package. Other R packages also extend or use it, e.g. party and caret.
References:
Cutler, A., Cutler, D.R., and Stevens, J.R. (2009). Tree-Based Methods, in High-Dimensional Data Analysis in Cancer Research, Li, X. and Xu, R. (eds.), pp. 83-101, Springer.
Saeys, Y., Inza, I., and Larrañaga, P. (2007). A review of feature selection techniques in bioinformatics. Bioinformatics, 23(19): 2507-2517.
