Learning Non-Linear Feature Maps, With An Application To Representation Learning
Authors: Dimitrios Athanasakis, John Shawe-Taylor, Delmiro Fernandez-Reyes
ICLR 2014

Abstract: Recent non-linear feature selection approaches employing greedy optimisation of Centred Kernel Target Alignment(KTA) exhibit strong results in terms of generalisation accuracy and sparsity. However, they are computationally prohibitive for large datasets. We propose randSel, a randomised feature selection algorithm, with attractive scaling properties. Our theoretical analysis of randSel provides strong probabilistic guarantees for correct identification of relevant features. RandSel's characteristics make it an ideal candidate for identifying informative learned representations. We've conducted experimentation to establish the performance of this approach, and present encouraging results, including a 3rd position result in the recent ICML black box learning challenge as well as competitive results for signal peptide prediction, an important problem in bioinformatics.


Peer review:
[Review]:
We would like to thank the reviewers for their positive feedback and insightful comments. 

Regarding the theory supporting the algorithm, something that both reviewers a39c and 89fd have brought up,  
we have updated the proof sketch to reflect that the supporting theory relies on Hoeffding's bound for U-Statistics and provides a high-confidence bound provided a sufficient sample size. The 12.5% stems from the fact that the sample size requirement is typically too large in practice. Thus a more conservative approach employing an iterative scheme that rejects a percentage of the features after each iteration was used. We try to interweave this better with the paper by providing an additional example where the technical conditions hold more strongly (in the updated figure 1), and contrasting that with the iterative scheme (figure 2). 
 
Regarding the comparison of our approach to the existing approach employed by SignalP, we agree with reviewer a39c 
that further testing is required and added further emphasis to this statement in the updated text. The entries of Table 1 were renamed to reflect where they come from, in accordance to the suggestion of reviewer 89fd.  
 
We have proceeded to rename the paper 'Principled Non-Linear Feature Selection' in response to the comments of reviewer c360. 
 
Regarding the runtime of our approach, I believe that results could be misleading, owing to the fact that currently the method only employs matlab, whereas stability selection and svms are in c-code with a matlab interface. Informally speaking the method was fast enough to process a single fold in the kaggle contest in roughly an hour. For the signal peptide prediction, this time is vastly increased but is still not substantially worse than competing methods.