Learning Sparse SVM for Feature Selection on Very High Dimensional Datasets

Mingkui Tan, Li Wang, Ivor W. TsangICML 2010 · OpenReview

Introduction

In fields like genomics or text analysis, researchers often deal with "high-dimensional, low-sample size" data—where there are thousands or millions of features but relatively few examples. Standard Support Vector Machines (SVMs) use all available features, which can lead to overfitting on noise and slow predictions.

To address this, researchers seek sparsity. Ideally, an $l_0$-norm regularizer is used to directly count and minimize the number of active features. However, $l_0$ optimization is NP-hard. Existing workarounds, such as $l_1$-norm relaxation, Recursive Feature Elimination (RFE), and convex relaxations (SDP/QCQP), either fail to achieve desired sparsity, suffer from "monotonicity" (permanently discarding useful features), or are computationally explosive on large datasets.

This paper introduces the Feature Generating Machine (FGM), a novel framework that makes $l_0$-norm SVMs practical for datasets with millions of features. By reformulating the feature selection problem into a convex Multiple Kernel Learning (MKL) task, FGM achieves state-of-the-art sparsity and accuracy without the computational bottlenecks of previous methods.

The Feature Generating Machine

The FGM framework relies on three main mathematical transformations:

  1. MIP Formulation: The authors represent feature selection by adding a 0-1 indicator variable to each feature, converting the SVM into a Mixed Integer Programming (MIP) problem.
  2. Convex Relaxation to MKL: Using the minimax inequality, the difficult MIP is transformed into a Multiple Kernel Learning (MKL) problem. Selecting a subset of features becomes equivalent to choosing a "base kernel."
  3. Cutting Plane Algorithm: Because the number of possible feature subsets is astronomically large, the MKL problem is solved iteratively using a cutting-plane method:
  4. Feature Generation: Find the "most violated" feature subset. The authors demonstrate that this sub-problem can be solved exactly and efficiently simply by sorting coefficients.
  5. MKL Optimization: Add this new subset to a "working set" and re-optimize the weights using an efficient MKL solver.
  6. Iterate: Repeat until the model converges to a global optimum.

A key insight of FGM is its non-monotonicity. Unlike RFE, which permanently discards features, FGM generates pools of feature subsets. The final model is a convex combination of these subsets, allowing it to re-evaluate feature importance in different contexts and making it highly robust to noise. Furthermore, the authors provide a formal proof that this iterative approach reaches the global optimum of the relaxed problem in a finite number of steps.

Experimental Setup

FGM was evaluated across a diverse range of benchmarks:

  • Synthetic Data: A binary classification task with "composite" features to test the identification of feature groups that only work well together.
  • Small/Medical Data: Datasets like WDBC (breast cancer), USPS (digits), and Microarray data.
  • Massive-Scale Data: High-dimensional text and web data (e.g., RCV1, News20). The largest datasets (URL reputation) contained over 3.2 million features.

Key Results

FGM demonstrated exceptional scalability, successfully handling the 3.2-million-feature URL dataset where previous convex relaxation methods crashed or timed out.

Performance of FGM and baselines as the number of noisy features increases.

As shown in the synthetic experiments, FGM was the only method able to perfectly identify "ideal" composite features and maintain high testing accuracy as the noise level increased. On real-world datasets, it consistently matched or outperformed RFE and $l_1$-SVM while maintaining higher levels of sparsity.

In terms of efficiency, FGM typically converges in fewer than 10 iterations. It proved significantly faster than RFE on high-dimensional datasets because it solves a series of small MKL problems rather than retraining full SVMs thousands of times.

Limitations and Future Work

  • Parameter Selection: The algorithm requires the user to specify $B$ (the number of features to select). In practice, the optimal number of features is often unknown, necessitating cross-validation which adds computational overhead.
  • Linear Focus: The current implementation focuses on linear SVMs. Extending the efficient "sorting trick" for feature generation to non-linear kernels remains a challenge.
  • Memory Constraints: The MKL step requires storing or calculating kernel matrices for the selected subsets, which could become a bottleneck if the number of iterations grows very large.

Summary updated

Abstract

A sparse representation of Support Vector Machines (SVMs) with respect to input features is desirable for many applications. In this paper, by introducing a 0-1 control variable to each input feature, l0-norm Sparse SVM (SSVM) is converted to a mixed integer programming (MIP) problem. Rather than directly solving this MIP, we propose an efficient cutting plane algorithm combining with multiple kernel learning to solve its convex relaxation. A global convergence proof for our method is also presented. Comprehensive experimental results on one synthetic and 10 real world datasets show that our proposed method can obtain better or competitive performance compared with existing SVM-based feature selection methods in term of sparsity and generalization performance. Moreover, our proposed method can effectively handle large-scale and extremely high dimensional problems.
BibTeX
@inproceedings{tan2010learning,
  author = {Mingkui Tan and Li Wang and Ivor W. Tsang},
  title = {{Learning Sparse SVM for Feature Selection on Very High Dimensional Datasets}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=SJ4ASoWO-r},
}
Figure