Combined SVM-Based Feature Selection and Classification

Julia Neumann, Christoph Schnörr, Gabriele SteidlMachine Learning 2005 · DOI · OpenReview

Abstract

In high-dimensional data analysis, identifying relevant features is as crucial as achieving high classification accuracy. This paper introduces a suite of "embedded" feature selection methods that integrate feature pruning directly into the Support Vector Machine (SVM) training process. By utilizing Difference of Convex (D.C.) functions programming, the authors develop a robust framework for both linear and nonlinear feature selection. Experimental results on benchmark and real-world datasets, including microarray and medical imaging data, show that these methods significantly reduce model complexity and improve interpretability without sacrificing generalization performance.

Introduction

The "curse of dimensionality" poses a significant challenge in machine learning, where an excess of features relative to samples can lead to overfitting and reduced model interpretability. Traditional approaches to feature selection are often categorized as filters (pre-processing) or wrappers (iterative testing). However, these often fail to capture the internal dynamics of the classifier. This research addresses the gap in "embedded" methods, specifically focusing on the difficulty of performing feature selection within nonlinear SVMs, which are powerful but notoriously difficult to prune.

Methodology: Embedded Feature Selection via DCA

The authors propose four continuous optimization approaches that combine SVM margin maximization with sparsity-inducing penalties. These include the $\ell_2$-$\ell_1$-SVM and the more aggressive $\ell_2$-$\ell_0$-SVM, which utilizes a concave approximation of the $\ell_0$-norm. For nonlinear scenarios, the authors introduce Quadratic FSV and Kernel-Target Alignment.

Feature selection path showing the reduction of active features as the regularization parameter λ increases.

To solve these non-convex problems, the authors employ the Difference of Convex functions Algorithm (DCA). As shown in the figure above, as the regularization parameter $\lambda$ increases, the model systematically discards irrelevant features (moving from a set of four features to just one), effectively finding the most parsimonious representation of the data. This unified framework allows for mathematically rigorous handling of non-smooth penalties that would otherwise be computationally intractable.

Experimental Evaluation and Results

The proposed methods were tested on various datasets, including standard UCI benchmarks, high-dimensional microarray data (Colon Cancer), and a real-world CT organ classification task involving 650 image features.

Key Findings

  • Sparsity vs. Accuracy: On the microarray dataset, the $\ell_2$-$\ell_0$-SVM reduced the feature count from 2,000 to just 18 while improving test error from 10% to 5% compared to standard linear SVMs.
  • Medical Imaging: In CT scan classification, the embedded methods achieved high accuracy using as few as 3 to 18 features out of 650, demonstrating the potential for real-time clinical application.
  • Nonlinear Superiority: For datasets with complex decision boundaries, such as 'liver' and 'ionosphere', nonlinear embedded selection methods like Quadratic FSV significantly outperformed linear models.
Nonlinear decision boundary and corresponding feature selection for a synthetic dataset.

Discussion and Conclusion

The synergy between $\ell_2$ regularization (for accuracy) and sparsity penalties (for selection) allows for the creation of models that are both accurate and simple. The authors found that implicit selection in kernels naturally discards noise; adding random features "disturbs" the geometry of the feature space, and the algorithm avoids this by zeroing out the noise.

While the DCA is sensitive to local minima and currently focused on binary classification, this framework represents a significant step forward in making high-dimensional SVM models more interpretable and efficient. Future research will explore multi-class extensions and automated hyperparameter tuning for the various weight parameters ($\lambda, \mu, \nu$) introduced by these methods.

Summary updated

Abstract

Feature selection is an important combinatorial optimisation problem in the context of supervised pattern classification. This paper presents four novel continuous feature selection approaches directly minimising the classifier performance. In particular, we include linear and nonlinear Support Vector Machine classifiers. The key ideas of our approaches are additional regularisation and embedded nonlinear feature selection. To solve our optimisation problems, we apply difference of convex functions programming which is a general framework for non-convex continuous optimisation. Experiments with artificial data and with various real-world problems including organ classification in computed tomography scans demonstrate that our methods accomplish the desired feature selection and classification performance simultaneously.
BibTeX
@article{neumann2005combined,
  author = {Julia Neumann and Christoph Schnörr and Gabriele Steidl},
  title = {{Combined SVM-Based Feature Selection and Classification}},
  journal = {Machine Learning},
  year = {2005},
  doi = {10.1007/s10994-005-1505-9},
}
Figure