Am I performing feature selection correctly? I'd like to design a feature extraction, selection, and classification scheme to use on novel data sets. For each row in a table I calculate 10 features. I then select which features are relevant (using a training set), and finally predict a label for each row using a Naive Bayes classifier (using a testing set). Ideally, this would be automated such that a user can just load a table and click "go".
Here's my issue. Even with feature selection, classification using a single, known relevant feature can outperform classification on all features. That is, running the classifier using a single feature that we know performs well can yield better predictions than running the classifier on all selected relevant features. I know that classifiers are "garbage in, garbage out", so including irrelevant features can lower the performance. But I thought the feature selector would prevent garbage from going into the classifier.
Am I maybe not being strict enough with my feature selection? Should I include less features in the first place? Is there an obvious error I'm making somewhere else? 
Here's a breakdown of what I'm doing in case it's useful.


*

*Calculate 10 features for each row of the table.

*Split the table into testing and training in a k-fold scheme.

*Select the relevant features using the training data and the criterion fisher-ratio > 0.2. For this I used the function IndFeat.m in matlab, which calculates fisher's ratio between the training labels and the feature of interest. A higher ratio means the feature is more informative about the labels. A description of fisher's ratio is here, and a description of the matlab function is here.

*Using the selected features, classify on the testing data.

*Repeat steps 2-5 for each k folds.

 A: Your feature selection criterion 

fisher-ratio > 0.2

has an implicit parameter which you have fixed to a constant.  It would be better to view the 0.2 part as a free tuning parameter

fisher-ratio > lambda

As you say, when you use your criterion for a fixed value of 0.2, the resulting model is always dominated by a model with less predictors.  You should be able to recover this information from a better training procedure.  
If you think of lambda as a parameter to be tuned in the algorithm, then cross validation will help you determine a good value of lambda.  To do this, create a grid of lambda you are willing to consider, say [.1, .2, .3, ...] and then train your algorithm on all your folds for each such value of lambda.  Then, the average out of fold error for each such lambda you used is an estimate of the out of sample error of your model when features are selected according to the criterion fisher-ratio > lambda.  This will let you (approximately) select the feature selection strength that results in the best model. 
In your case, if everything works out consistently, this should validate your suspicion that you should select a small number of powerful features.
A: Your approach hinges on one crucial assumption: fisher ratio is sufficient as a source of information to determine a variable's importance.
If in your dataset this doesn't hold true this method will not work. One way I could think of to strengthen this approach would be to add a few more criteria in addition to fisher-ratio to determine if a variable should be used. (Even the default stepwise regression could possibly give you some information.)
