Feature selection for support vector machines by means of genetic algorithm
Published 1 March 2004
Holger Fröhlich, Olivier Chapelle, Bernhard Schölkopf
Citations338
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
This paper presents a special genetic algorithm, which especially takes into account the existing bounds on the generalization error for support vector machines (SVMs), which is compared to the traditional method of performing cross-validation and to other existing algorithms for feature selection.
Abstract
The problem of feature selection is a difficult combinatorial task in machine learning and of high practical relevance, e.g. in bioinformatics. genetic algorithms (GAs) offer a natural way to solve this problem. In this paper, we present a special genetic algorithm, which especially takes into account the existing bounds on the generalization error for support vector machines (SVMs). This new approach is compared to the traditional method of performing cross-validation and to other existing algorithms for feature selection.
Keywords
Computer Science
Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning
49,278 Citations1989
This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.
Machine LearningSupport-vector networks
40,463 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
The MIT Press eBooksAdaptation in Natural and Artificial Systems
35,568 Citations1992John H. Holland
Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.
Machine LearningSupport-Vector Networks
33,035 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
Genetic Algorithms in Search, Optimization and Machine Learning
17,773 Citations1988David E. Goldberg, David Robson
Data Mining and Knowledge DiscoveryA Tutorial on Support Vector Machines for Pattern Recognition
16,433 Citations1998Christopher J. C. Burges
There are several arguments which support the observed high accuracy of SVMs, which are reviewed and numerous examples and proofs of most of the key theorems are given.
ACM Computing SurveysData clustering
13,184 Citations1999Anil K. Jain, M. Narasimha Murty +1 more
An overview of pattern clustering methods from a statistical pattern recognition perspective is presented, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners.
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
A training algorithm for optimal margin classifiers
11,594 Citations1992Bernhard E. Boser, Isabelle Guyon +1 more
A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented, applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions.
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.
Artificial IntelligenceWrappers for feature subset selection
8,925 Citations1997Ron Kohavi, George H. John
The wrapper method searches for an optimal feature subset tailored to a particular algorithm and a domain and compares the wrapper approach to induction without feature subset selection and to Relief, a filter approach tofeature subset selection.
International Conference on Neural Information ProcessingAdvances in kernel methods: support vector learning
5,815 Citations1999Bernhard Schölkopf, Christopher J. C. Burges +1 more
Support vector machines for dynamic reconstruction of a chaotic system, Klaus-Robert Muller et al pairwise classification and support vector machines, Ulrich Kressel.
Statistics and ComputingA genetic algorithm tutorial
4,451 Citations1994Darrell Whitley
This tutorial covers the canonical genetic algorithm as well as more experimental forms of genetic algorithms, including parallel island models and parallel cellular genetic algorithms.
Proceedings of the National Academy of SciencesBroad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays
4,210 Citations1999Uri Alon, Naama Barkai +5 more
A two-way clustering method is reported for analyzing a data set consisting of the expression patterns of different cell types, revealing broad coherent patterns that suggest a high degree of organization underlying gene expression in these tissues.
ePrints Soton (University of Southampton)An Introduction to Support Vector Machines
4,120 Citations2000Nello Cristianini, John Shawe‐Taylor
Artificial IntelligenceSelection of relevant features and examples in machine learning
3,295 Citations1997Avrim Blum, Pat Langley
This survey reviews work in machine learning on methods for handling data sets containing large amounts of irrelevant information and describes the advances that have been made in both empirical and theoretical work in this area.
Proceedings of the IEEENetworks for approximation and learning
3,257 Citations1990Tomaso Poggio, Federico Girosi
Regularization theory and a theoretical framework for approximation that leads to a class of three-layer networks called regularization networks are discussed, generalized to a formulation that includes task-dependent clustering and dimensionality reduction.
Elsevier eBooksA Practical Approach to Feature Selection
2,954 Citations1992Kenji Kira, Larry Rendell
Comparison with other feature selection algorithms shows Relief's advantages in terms of learning time and the accuracy of the learned concept, suggesting Relief's practicality.
Lecture notes in computer scienceEstimating attributes: Analysis and extensions of RELIEF
2,950 Citations1994Igor Kononenko
In the context of machine learning from examples this paper deals with the problem of estimating the quality of attributes with and without dependencies among them and is analysed and extended to deal with noisy, incomplete, and multi-class data sets.
Elsevier eBooksIrrelevant Features and the Subset Selection Problem
2,374 Citations1994George H. John, Ron Kohavi +1 more
A method for feature subset selection using cross-validation that is applicable to any induction algorithm is described, and experiments conducted with ID3 and C4.5 on artificial and real datasets are discussed.
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.
RPK (Politechniki Krakowskiej)Artificial Intelligence: A Modern Approach
1,746 Citations1995Stuart Russell, Peter Norvig
IEEE Transactions on Signal ProcessingComparing support vector machines with Gaussian kernels to radial basis function classifiers
1,381 Citations1997Bernhard Schölkopf, Kah-Kay Sung +5 more
The results show that on the United States postal service database of handwritten digits, the SV machine achieves the highest recognition accuracy, followed by the hybrid system, and the SV approach is thus not only theoretically well-founded but also superior in a practical application.
Foundations of genetic algorithmsThe CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination
1,042 Citations1991Larry J. Eshelman
CHC is described and analyzed, a nontraditional genetic algorithm which combines a conservative selection strategy that always preserves the best individuals found so far with a radical (highly disruptive) recombination operator that produces offspring that are maximally different from both parents.
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.
Information Processing LettersConstructing optimal binary decision trees is NP-complete
956 Citations1976Laurent Hyafil, Ronald L. Rivest
The proof to be given is relatively simple and the importance of this result can be measured in terms of the Jarge amount of effort that has been put into fmding efftient aJgorJthms for constructing optimal binary decision trees.
THE SPECTRUM KERNEL: A STRING KERNEL FOR SVM PROTEIN CLASSIFICATION
944 Citations2001Christina S. Leslie, Eleazar Eskin +1 more
A new sequence-similarity kernel, the spectrum kernel, is introduced for use with support vector machines (SVMs) in a discriminative approach to the protein classification problem and performs well in comparison with state-of-the-art methods for homology detection.
Studies in fuzziness and soft computingOn Kernel Target Alignment
853 Citations2006Nello Cristianini, Jaz Kandola +2 more
The notion of kernel-alignment, a measure of similarity between two kernel functions or between a kernel and a target function, is introduced, giving experimental results showing that adapting the kernel to improve alignment on the labelled data significantly increases the alignment on a test set, giving improved classification accuracy.
IEEE Transactions on Evolutionary ComputationDimensionality reduction using genetic algorithms
842 Citations2000Michael L. Raymer, William F. Punch +3 more
This work presents a new approach to feature extraction in which feature selection and extraction and classifier training are performed simultaneously using a genetic algorithm, and employs this technique in combination with the k nearest neighbor classification rule.
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.
Neural ComputationBounds on Error Expectation for Support Vector Machines
627 Citations2000Vladimir Vapnik, Olivier Chapelle
It is proved that the value of the span is always smaller (and can be much smaller) than the diameter of the smallest sphere containing the support vectors, used in previous bounds.
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.
Érudit documents and data repository (Érudit Consortium, University of Montreal)Inference for the Generalization Error
485 Citations1999Yoshua Bengio, Claude Nadeau
Model Selection for Support Vector Machines
347 Citations1999Olivier Chapelle, Vladimir Vapnik
New functionals for parameter (model) selection of Support Vector Machines are introduced based on the concepts of the span of support vectors and rescaling of the feature space and it is shown that using these functionals one can both predict the best choice of parameters of the model and the relative quality of performance for any value of parameter.
IEEE Transactions on Neural NetworksFast generic selection of features for neural network classifiers
230 Citations1992Frank Brill, Donald E. Brown +1 more
The authors describe experiments using a genetic algorithm for feature selection in the context of neural network classifiers, specifically, counterpropagation networks, and propose a method called the training set sampling, which selects feature sets that are as good as and occasionally better for counterPropagation than those chosen by an evaluation that uses the entire training set.
Probabilistic Kernel Regression Models
207 Citations1999Tommi Jaakkola, David Haussler
A class of exible conditional probability models and techniques for classi cation regression problems that comes from the use of kernel functions as in support vector machines and the generality from dual formulations of stan dard regression models is introduced.
NP-Completeness of Searches for Smallest Possible Feature Sets
101 Citations1994Scott Davies, Stuart Russell
The FOCUS algorithm, due to Almuallim and Dietterich, performs an explicit search for the smallest possible input feature set S that permits a consistent mapping from the features in S to the output feature.
Future Generation Computer SystemsAttribute selection for modelling
79 Citations1997Igor Kononenko, Se June Hong
This work examines various important concepts and approaches that are used for modelling a target attribute by other attributes in the data and contrasts their strengths.
Lecture notes in computer scienceFeature Selection via Genetic Optimization
44 Citations2002Sancho Salcedo‐Sanz, Mario de Prado‐Cumplido +2 more
A novel genetic operator which fixes the number of selected features, referred to as m-features operator, reduces the size of the search space and improves the GA performance and convergence.
Lecture notes in computer scienceFeature Extraction Using ICA
39 Citations2001Nojun Kwak, Chong‐Ho Choi +1 more
A new feature extraction algorithm using independent component analysis (ICA) for classification problems can be used in solving supervised classification problems to get new features which are made as independent from each other as possible and also convey the output information faithfully.