Challenge result analysis Isabelle Guyon, Steve Gunn, Asa Ben-Hur and, Gideon Dror.

The NIPS 2003 challenge on feature selection is over, but the website of the challenge is still open for post-challenge submissions. We present on this page an analysis of the challenge results and supplementary material to help researchers in the field. The workshop slides present our initial analysis. A paper summarizing the main results will be published in the NIPS 2004 proceedings. A book in preparation will provide chapters on the best methods and further analyses.

Summary

We provided participants with five datasets from different application domains and called for classification results using a minimal number of features. All datasets are two-class classification problems. The data were split into three subsets: a training set, a validation set, and a test set. All three subsets were made available at the beginning of the benchmark, on September 8, 2003. The class labels for the validation set and the test set were withheld. The identity of the datasets and of the features (some of which were random features artificially generated) were kept secret. The participants could submit prediction results on the validation set and get their performance results and ranking on-line for a period of 12 weeks. On December 1st, 2003, the participants had to turn in their results on the test set. The validation set labels were released at that time. On December 8th, 2003, the participants could make submissions of test set predictions, after having trained on both the training and the validation set.

The competition attracted 78 research groups. In total 1863 entries were made on the validation sets during the development period and 135 entries on all test sets for the final competition. The winners used a combination of Bayesian neural networks with ARD priors and Dirichlet diffusion trees. Other top entries used a variety of methods for feature selection, which combined filters and/or wrapper or embedded methods using Random Forests, kernel methods, or neural networks as a classification engine.

See more details on the benchmark protocol in the challenge FAQ and in our report.

Datasets

The identity of the datasets was revealed at the NIPS 2003 workshop. The datasets were chosen to span a variety of domains (cancer prediction from mass-spectrometry data, handwritten digit recognition, text classification, and drug discovery), and a variety of difficulties (the input variables are continuous or binary, sparse or dense; one dataset has unbalanced classes.) One dataset (Madelon) was artificially constructed to illustrate a particular difficulty: selecting a feature set when no feature is informative by itself. We chose datasets that had sufficiently many examples to create a large enough test set to obtain statistically significant results. To prevent researchers familiar with the datasets to have an advantage, we concealed the identity of the datasets during the benchmark. We performed several preprocessing and data formatting steps, which contributed to disguising the origin of the datasets. In particular, we introduced a number of features called probes. The probes were drawn at random from a distribution resembling that of the real features, but carrying no  information about the class labels. Such probes have a function in performance assessment: a good feature selection algorithm should eliminate most of the probes. The details of data preparation can be found in a technical memorandum. The datasets can be dowloaded from the workshop web site (see also our mirror.) The validation set labels are now available.

Scoring

Final submissions qualified for scoring if they included the class predictions for training, validation, and test sets for all five
tasks proposed, and the list of features used. Optionally, classification confidence values could be provided. Performance
was assessed using several metrics:

• BER: The balanced error rate, that is the average of the error rate of the positive class and the error rate of the negative class. This metric was used because some datasets (particularly Dorothea) are unbalanced.
• AUC: Area under the ROC curve. The ROC curve is obtained by varying a threshold on the discriminant values (outputs) of the classifier. The curve represents the fraction of true positive as a function of the fraction of false negative. For classifiers with binary outputs, BER=1-AUC.
• Ffeat: Fraction of features selected.
• Fprobe: Fraction of probes found in the feature set selected.

•  Make pairwise comparisons between classifiers for each dataset.
• Use the McNemar test to determine whether classifier A better than classifier B according to the BER with 5\% risk. Obtain a score of 1 (better), 0 (don't know) or –1 (worse).
• If the score is 0, break the tie with Ffeat if the relative difference in Ffeat is larger than 5\%.
• If the score is still 0, break the tie with Fprobe.
• The overall score for each dataset is the sum of the pairwise comparison scores (normalized by the maximum achievable score, that is the number of submissions minus one).
• The global score is the average of the dataset scores.

The scoring code is available.

Results

We have published at the workshop the result tables for December 1st and December 8th submissions (Note: there is an error in these files in the AUC ranking that does not affect the results and will be corrected soon.) The results of the best entries are summarized in the two tables below. We indicate in the last column a test of significance of the difference in BER between the entry and the top ranking entry. One indicates a significant difference and zero no significant difference (with 5% risk.) The results of the tests were averaged over the five datasets.

The winners of the benchmark (both December 1st and 8th are Radford Neal and Jianguo Zhang, with a combination of Bayesian neural networks and Dirichlet diffusion trees. Their achievements are significant since they win on the overall ranking with respect to our scoring metric, but also with respect to the balanced error rate (BER), the area under the ROC curve (AUC), and they have the smallest feature set among the top entries that have performance not statistically significantly worse. They are also the top entrants December 1st for Arcene and Dexter and December 1st and 8th for Dorothea.

We performed a survey of the methods employed among the top ranking participants (see our report for details.) A variety of methods achieved excellent results. A Bayesian method won and other groups reported performance improvements with ensemble methods. Yet the second ranking group reported no significant performance benefit of using ensembles, with a regularized least-square kernel classifier. The winners use a combination of filters and embedded feature selection methods. Other groups achieve honorable results with simple correlation-based filters. The winners use a neural network classifier, but kernel methods dominate the top ten entries. Some groups obtain good results with no feature selection at all, with strongly regularized methods.

Regularization has been a key element of the success of the top entrants. They have demonstrated that, in spite of the very
adverse proportions of number of examples vs. number of features, it is possible to perform well without feature selection
and to perform better with non-linear classifiers than with linear classifiers.

Result verifications

We (the benchmark organizers) performed a number of result verifications to validate the observations we made on the challenge results and verify that the challenge entries were sound (i.e. that there was not potential cheating.)

1) Hyperparameter selection study

We selected 50 feature subsets (five for each dataset both for December 1st and for December 8th entries). You can download the challenge entries corresponding to these 50 feature subsets (including the subsets themselves.) We used a soft-margin SVM implemented in SVMlight, with a choice of kernels (linear, polynomial, and Gaussian) and a choice of preprocessings and hyperparameters selected with 10-fold cross-validation (see all the details of our experimental design.) For the December 8th feature sets, we trained on both the training set and the validation set to be in the same conditions as the challengers. The Matlab code can be dowloaded as well as the results of our best classifiers selected by CV and the results of the vote of our top 5 best classifiers selected by CV. The datasets themselves are not included since they can be dowloaded from the challenge web site. To format them in Matlab format, use our sample code.

Linear vs. non-linear classifier
We verified empirically the observation from the challenge results that non-linear classifiers perform better than linear classifiers by training an SVM on feature subsets submitted at the benchmark.

For each dataset, across all 10 feature sets (5 for December 1st and 5 for December 8th), for the top five best classifiers obtained by hyperparamenter selection, we computed statistics about the most frequently used kernels and preprocessings (Note: since the performance of the 5th performer for some datasets was equal to that of the 6th 7th and even the 8th, to avoid the arbirtrariness of picking the best 5 by "sort" we picked also the next several equal results.) In the table below, we see that the linear SVM rarely shows up in the top five best hyperparameters combinations.

Preprocessing
We tried 3 preprocessings:

• normalize1: each feature was separately standardized, by substracting its mean and dividing by (std + fudge factor). In case of sparse data, the mean was not substracted.
• normalize2: each example is divided by its L2 norm.
• normalize3: each example is divided by the mean L2 norm of examples.

Effectiveness of SVMs
One observation of the challenge is that SVMs (and other kernel methods) are effective classifiers and that they can be combined with a variety of feature selection methods used as "filters". Our hyperparameter selection experiments also provide us with the opportunity to check whether we can get performances that are similar to those of the challengers by training an SVM on the feature sets they declared. This allows us to determine whether the performances are classifier dependent. As can be seen in the figure below, for most datasets, SVMs achieve comparable results as the classifiers used by the challengers. We achieve better results for Gisette. For Dorothea, we do not match the results of the challengers, which can partly be explained by the fact that we did not select the bias properly (our AUC results compare more favorably to the challengers' AUCs.) We are currently redoing the experiments to address that issue.
 
 

Effectiveness of ensemble methods
One observation of the challenge is that ensemble methods usually yield improved results. We performed a simple voting among the 5 top classifers obtained in our hyperparameter selection study. The results shown in the figure below demonstrate some improvement, particularly for Dexter and Arcene. The significance of these results need further analysis and complemetary simulations must be made to get a more clear-cut answer.

2) Challenge result validity verification

Our benchmark design could not hinder participants from "cheating" in the following way. An entrant could "declare" a smaller feature subset than the one used to make predictions. To deter participants from cheating, we warned them that we would be
performing a stage of verification.

In the result tables (December 1st and December 8th), we see that entrants having selected on average less than 50% of the features have feature sets generally containing less than 20% of probes. But in larger subsets, the fraction of probes can be substantial without altering the classification performance. Thus, a small fraction of probes is an indicator of quality of the feature subset, but a large fraction of probes cannot be used to detect potential breaking of the rules of the challenge.

First check
We performed a first check with the Madelon data. We generated additional test data (two additional test sets of the same size as the original test set: 1800 examples each.) We sent the top entrants the new test sets, restricted to the feature subset they had submitted. We asked them to return the class label predictions. We scored the results and compared them to their results on the original test set to detect a significant discrepancy. Specifically, we performed the following calculations:

• Compute for each test set the mean error rate over the 5 entries checked: mu1, mu2, mu3.
• Compute the overall mean mu=mu1+mu2+mu3/3.
• Compute corrective factors mu/mu1, mu/mu2, mu/mu3.
• Apply the corrective factors to the error rates obtained.
• Compute an error bar as sqrt{mu(1-mu)/m}, where m is the size of each test set.

Second check
We performed another check with all the datasets. We examined the 50 feature sets of our hyperparameter study that were submitted by challengers. We looked for BER performance outliers in the best SVM results. To correct for the fact that our best "reference" SVM classifier does not perform on avarage similarly to the challengers' classifiers, we computed a correction for each dataset k:
       c_k = average_k(Reference_SVM_BER - Corresponding_challenge_BER)
where the average is taken for each dataset over 10 feature sets (5 for each date.)
We computed the following T statistic:
       T=(Reference_SVM_BER - Corresponding_challenge_BER  - c_k)/stdev(difference_k)
where stdev(difference_k) is the standard deviation of (Reference_SVM_BER - Corresponding_challenge_BER - c_k), computed separately for each dataset.
We show in the figure below the T statistics as a function of the corresponding challenge BER for the various entries. We also show the limits corresponding to one sided risks of 0.01 (dashed line) and 0.05 (dotted line) to reject to null hypothesis that the T statistic is equal to zero (no significant difference in performance between the entry and our reference method.) No entry is suspicious according to this test. The only entry above the 0.05 line is for Madelon and had a fraction of probes of zero, so it is really sound.
N.B. The lines drawn according to the T distributions were computed for 9 degrees of freedom (10 entries minus one.) Using the normal distribution instead of the T distribution yields a dotted line (risk 0.05) at 1.65 and a dashed line (risk 0.01) at 2.33. This does not change our results.

3) On-going work

We are presently working on reproducing the best challenge results with the simplest possible methods. Owing to the success of filter methods in this benchmark, we are conducting a systematic study, decoupling the problem of selecting features from that of  classifying. We are testing classifiers including nearest neighbors, Parzen windows, SVMs, kernel ridge regression, tree classifiers, and neural networks, on the best feature subsets selected in the challenge. We are also generating feature subsets with various methods that we will test with our canonical classification methods. We are creating a library of routines that will be made publicly available.

The analysis of the challenge results also revealed that hyperparameter selection may have played an important role in
winning the challenge. Indeed, several groups were using the same classifier (e.g. an SVM) and reported significantly different results. We have started laying the basis of a new benchmark on the theme of model selection and hyperparameter selection.