A stochastic algorithm for feature selection in pattern recognition
Published 1 January 2007Open access
Sébastien Gadat, Laurent Younès, Isabelle Guyon
Citations60
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new model addressing feature selection from a large dictionary of variables that can be computed from a signal or an image, using the probability as a state variable and optimizing a multi-task goodness of fit criterion for classifiers based on variable randomly chosen according to P is introduced.
Abstract
We introduce a new model addressing feature selection from a large dictionary of variables that can be computed from a signal or an image. Features are extracted according to an efficiency criterion, on the basis of specified classification or recognition tasks. This is done by estimating a probability distribution P on the complete dictionary, which distributes its mass over the more efficient, or informative, components. We implement a stochastic gradient descent algorithm, using the probability as a state variable and optimizing a multi-task goodness of fit criterion for classifiers based on variable randomly chosen according to P. We then generate classifiers from the optimal distribution of weights learned on the training set. The method is first tested on several pattern recognition problems including face detection, handwritten digit recognition, spam classification and micro-array analysis. We then compare our approach with other step-wise algorithms like random forests or recursive feature elimination. Keywords: stochastic learning algorithms, Robbins-Monro application, pattern recognition, classification algorithm, feature selection
Keywords
Computer Science
Machine LearningRandom Forests
126,192 Citations2001Leo Breiman
Internal estimates monitor error, strength, and correlation and these are used to show the response to increasing the number of features used in the forest, and are also applicable to regression.
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
The Elements of Statistical Learning: Data Mining, Inference, and Prediction
19,345 Citations2013Trevor Hastie, Robert Tibshirani +1 more
ScienceMolecular Classification of Cancer: Class Discovery and Class Prediction by Gene Expression Monitoring
11,622 Citations1999Todd R. Golub, Donna K. Slonim +10 more
A generic approach to cancer classification based on gene expression monitoring by DNA microarrays is described and applied to human acute leukemias as a test case and suggests a general strategy for discovering and predicting cancer classes for other types of cancer, independent of previous biological knowledge.
Machine LearningGene Selection for Cancer Classification using Support Vector Machines
9,839 Citations2002Isabelle Guyon, Jason Weston +2 more
This paper proposes a new method of gene selection utilizing Support Vector Machine methods based on Recursive Feature Elimination (RFE), and demonstrates experimentally that the genes selected yield better classification performance and are biologically relevant to cancer.
The MIT Press eBooksLearning with Kernels
9,548 Citations2001Bernhard Schölkopf, Alexander J. Smola
Learning with Kernels provides an introduction to SVMs and related kernel methods that provide all of the concepts necessary to enable a reader equipped with some basic mathematical knowledge to enter the world of machine learning using theoretically well-founded yet easy-to-use kernel algorithms.
The Annals of StatisticsAdditive logistic regression: a statistical view of boosting (With discussion and a rejoinder by the authors)
6,842 Citations2000Jerome H. Friedman, Trevor Hastie +1 more
This work shows that this seemingly mysterious phenomenon of boosting can be understood in terms of well-known statistical principles, namely additive modeling and maximum likelihood, and develops more direct approximations and shows that they exhibit nearly identical results to boosting.
Optimizing search engines using clickthrough data
3,898 Citations2002Thorsten Joachims
The goal of this paper is to develop a method that utilizes clickthrough data for training, namely the query-log of the search engine in connection with the log of links the users clicked on in the presented ranking.
Neural ComputationNeural Networks and the Bias/Variance Dilemma
3,563 Citations1992Stuart Geman, Elie Bienenstock +1 more
It is suggested that current-generation feedforward neural networks are largely inadequate for difficult problems in machine perception and machine learning, regardless of parallel-versus-serial hardware or other implementation issues.
Neural ComputationA Practical Bayesian Framework for Backpropagation Networks
2,934 Citations1992David Mackay
A quantitative and practical Bayesian framework is described for learning of mappings in feedforward networks that automatically embodies "Occam's razor," penalizing overflexible and overcomplex models.
Journal of Artificial Intelligence ResearchSolving Multiclass Learning Problems via Error-Correcting Output Codes
2,718 Citations1995Tom Dietterich, Ghulum Bakiri
It is demonstrated that error-correcting output codes provide a general-purpose method for improving the performance of inductive learning programs on multiclass problems.
Signal ProcessingBlind separation of sources, part I: An adaptive algorithm based on neuromimetic architecture
2,522 Citations1991Christian Jutten, Jeanny Hérault
Machine LearningChoosing Multiple Parameters for Support Vector Machines
2,182 Citations2002Olivier Chapelle, Vladimir Vapnik +2 more
The problem of automatically tuning multiple parameters for pattern recognition Support Vector Machines (SVMs) is considered by minimizing some estimates of the generalization error of SVMs using a gradient descent algorithm over the set of parameters.
Adaptive Algorithms and Stochastic Approximations
2,044 Citations1990Albert Benveniste, Michel Métivier +1 more
The juxtaposition of these two expressions in the title reflects the ambition of the authors to produce a reference work, both for engineers who use adaptive algorithms and for probabilists or statisticians who would like to study stochastic approximations in terms of problems arising from real applications.
Efficient Feature Selection via Analysis of Relevance and Redundancy
1,977 Citations2004Lei Yu, Huan Liu
It is shown that feature relevance alone is insufficient for efficient feature selection of high-dimensional data, and a new framework is introduced that decouples relevance analysis and redundancy analysis.
Stochastic modelling and applied probabilityStochastic Approximation and Recursive Algorithms and Applications
1,953 Citations2003Harold J. Kushner, G. George Yin
Neural ComputationShape Quantization and Recognition with Randomized Trees
1,282 Citations1997Yali Amit, Donald Geman
A new approach to shape recognition based on a virtually infinite family of binary features (queries) of the image data, designed to accommodate prior information about shape invariance and regularity, and a comparison with artificial neural networks methods is presented.
Studies in fuzziness and soft computingCombining SVMs with Various Feature Selection Strategies
991 Citations2008Yiwei Chen, Chih‐Jen Lin
This article investigates the performance of combining support vector machines (SVM) and various feature selection strategies, some are filter-type approaches: general feature selection methods independent of SVM, and some are wrapper-type methods: modifications of S VM which can be used to select features.
Feature Selection for SVMs
977 Citations2000Jason Weston, Sayan Mukherjee +4 more
The resulting algorithms are shown to be superior to some standard feature selection algorithms on both toy data and real-life problems of face recognition, pedestrian detection and analyzing DNA microarray data.
Fast Binary Feature Selection with Conditional Mutual Information
833 Citations2004François Fleuret
It is shown that this feature selection method outperforms other classical algorithms, and that a naive Bayesian classifier built with features selected that way achieves error rates similar to those of state-of-the-art methods such as boosting or SVMs.
MPG.PuRe (Max Planck Society)Use of the zero norm with linear models and kernel methods
700 Citations2003Jason Weston, André Elisseeff +2 more
A simple but practical method is derived for implementing a simple modification of vanilla SVM via an iterative multiplicative rescaling of the training data for minimizing the zero-norm of the parameters of linear models in learning.
Feature selection for high-dimensional genomic microarray data
629 Citations2001Eric P. Xing, Michael I. Jordan +1 more
This paper reports on the successful application of feature selection methods to a classification problem in molecular biology involving only 72 data points in a 7130 dimensional space and investigates regularization methods as an alternative to feature selection.
ePrints Soton (University of Southampton)Result Analysis of the NIPS 2003 Feature Selection Challenge
546 Citations2004Isabelle Guyon, Steve Gunn +2 more
The NIPS 2003 workshops included a feature selection competition organized by the authors, which took place over a period of 13 weeks and attracted 78 research groups and used a variety of methods for feature selection.
Extracting support data for a given task
542 Citations1995Bernhard Schölkopf, Chris Burges +1 more
It is observed that three different types of handwritten digit classifiers construct their decision surface from strongly overlapping small subsets of the data base, which opens up the possibility of compressing data bases significantly by disposing of theData which is not important for the solution of a given task.
Neural NetworksTraining a 3-node neural network is NP-complete
541 Citations1992Avrim Blum, Ronald L. Rivest
It is NP-complete to decide whether there exist weights and thresholds for this network so that it produces output consistent with a given set of training examples, and this results suggest that those looking for perfect training algorithms cannot escape inherent computational difficulties just by considering only simple or very regular networks.
Margin based feature selection - theory and algorithms
416 Citations2004Ran Gilad-Bachrach, Amir Navot +1 more
This paper introduces a margin based feature selection criterion and applies it to measure the quality of sets of features and devise novel selection algorithms for multi-class classification problems and provide theoretical generalization bound.
Detecting Concept Drift with Support Vector Machines
413 Citations2000Ralf Klinkenberg, Thorsten Joachims
A new method to recognize and handle concept changes with support vector machines is proposed and it is shown that it can e(cid:11)ectively select an appropriate window size in a robust way.
International Journal of Computer VisionCoarse-to-Fine Face Detection
274 Citations2001François Fleuret, Donald Geman
The approach is sequential testing which is coarse-to-fine in both in the exploration of poses and the representation of objects, and the spatial distribution of processing is highly skewed and detection is rapid, but at the expense of (isolated) false alarms which could be eliminated with localized, more intensive, processing.
Stochastics and stochastics reportsOn lipschitz continuity of the solution mapping to the skorokhod problem, with applications
269 Citations1991Paul Dupuis, Hitoshi Ishii
SIAM Journal on Control and OptimizationA Dynamical System Approach to Stochastic Approximations
203 Citations1996Michel Benaı̈m
Neural ComputationA Computational Model for Visual Selection
159 Citations1999Yali Amit, Donald Geman
Feature selection from huge feature sets
137 Citations2002J. Bins, Bruce A. Draper
This work addresses the feature selection problem by proposing a three-step algorithm that uses a variation of the well known Relief algorithm to remove irrelevance, and which is shown to be more effective than standard feature selection algorithms for large data sets with lots of irrelevant and redundant features.
Arrow@dit (Dublin Institute of Technology)Solutions to Instability Problems with Sequential Wrapper-based Approaches to Feature Selection
135 Citations2002Kevin Dunne, Pádraig Cunningham +1 more
Examples of the problem of instability in feature subset selection are illustrated and a solution based on the aggregation of several runs of a sequential search is suggested, which does seem to stabilise the process.
BiosystemsReliable classification of two-class cancer data using evolutionary algorithms
133 Citations2003Kalyanmoy Deb, A. Raji Reddy
The use of a multiobjective EA (NSGA-II) has enabled a smaller gene subset size to correctly classify 100% or near 100% samples for three cancer samples and introduced a prediction strength threshold for determining a sample's belonging to one class or the other.
Iterative RELIEF for feature weighting
133 Citations2006Yijun Sun, Jian Li
A new interpretation of RELIEF as an online algorithm that solves a convex optimization problem with a margin-based objective function and extends the newly proposed algorithm to handle multiclass problems by using a new multiclass margin definition.
Feature subset selection bias for classification learning
108 Citations2006Surendra K. Singhi, Huan Liu
This research endeavors to provide illustration and explanation why the bias may not cause negative impact in classification as much as expected in regression.
Probability Theory and Related FieldsConvex duality and the Skorokhod Problem. II
106 Citations1999Paul Dupuis, Kavita Ramanan
Edinburgh Research Explorer (University of Edinburgh)Feature selection based on the Shapley value
105 Citations2005Shay B. Cohen, Eytan Ruppin +1 more
Empirical comparison with several other existing feature selection methods shows that the backward eliminati-nation variant of CSA leads to the most accurate classification results on an array of datasets.
SIAM Journal on Control and OptimizationRate of Convergence for Constrained Stochastic Approximation Algorithms
34 Citations2002R. Buche, Harold J. Kushner
The necessary techniques are developed and it is shown that the stationary Gaussian diffusion is replaced by an appropriate stationary reflected linear diffusion, whose variance plays the same role as a measure of the rate of convergence.
Memory-based character recognition using a transformation invariant metric
23 Citations2002P. Simard, Y. Le Cun +1 more
A new distance measure which can be made locally invariant to any set of transformations of the input; and can be computed efficiently is proposed.
NonlinearityConvergence with probability one of stochastic approximation algorithms whose average is cooperative
12 Citations2000Michel Benaı̈m
Studies in fuzziness and soft computingCombining a Filter Method with SVMs
11 Citations2008Thomas Navin Lal, Olivier Chapelle +1 more
Here it is explained how the Fisher criterion was used as a feature selection method, how the regularization parameter C of the SVM was chosen, and how the number of features used for each data set was estimated.
Lecture notes in computer scienceFast Video Retrieval under Sparse Training Data
4 Citations2003Yan Liu, John R. Kender
A novel heuristic method for selecting image features for video, called the Complement Sort-Merge Tree (CSMT), which combines the virtues of a wrapper model approach for better accuracy with those of a filter method approach for incrementally deriving the appropriate features quickly.
Studies in fuzziness and soft computingCombining Information-Based Supervised and Unsupervised Feature Selection
4 Citations2008Sang-Kyun Lee, Seung‐Joon Yi +1 more
This work proposes an enhanced filter method that exploits features from two information-based filtering steps: supervised and unsupervised, and attempts to reduce biases caused by misleading causal relations induced in the supervised selection procedure.
HAL (Le Centre pour la Communication Scientifique Directe)Apprentissage d'un vocabulaire symbolique pour la détection d'objets dans une image
3 Citations2004Sébastien Gadat