Top-k Supervise Feature Selection via ADMM for Integer Programming

Mingyu Fan, Xiaojun Chang, Xiaoqin Zhang, Di Wang, Liang Du

TL;DR

Most feature selection methods rank features and simply pick the top $k$, a strategy that often yields suboptimal results. This paper introduces a novel supervised method that directly identifies the optimal subset of $k$ features by formulating the problem as a 0-1 integer programming task and solving it efficiently using the Alternating Direction Method of Multipliers (ADMM).

What Problem Does This Paper Address?

In the world of high-dimensional data—like high-resolution images or complex video streams—we are often drowning in noise and redundancy. Feature Selection (FS) is the process of identifying the most relevant "bits" of data to improve model accuracy and reduce computational costs.

The "gold standard" for sparsity is the $\ell_0$-norm, which simply counts the number of non-zero features. however, optimizing for the $\ell_0$-norm is NP-hard (computationally "impossible" for large datasets). To get around this, researchers usually use "relaxations" like the $\ell_1$-norm (Lasso), which are easier to solve but don't always pick the absolute best $k$ features. Other methods rank features individually, ignoring how they might perform together as a team. This paper tackles the challenge of solving the "exact" top-$k$ selection problem directly and efficiently.

Methods

The authors propose a supervised feature selection model based on regularized least squares regression. Their key innovation lies in how they handle the discrete "select or don't select" nature of the problem:

  1. Formulation: They use an $\ell_{0,2}$-norm constraint, which forces the model to pick exactly $k$ columns (features) from the data matrix.
  2. The Integer Programming Trick: They transform the selection process into a 0-1 integer programming problem. Since this is normally hard to solve, they employ the $\ell_2$-box method. This replaces the discrete $\{0, 1\}$ constraint with the intersection of two continuous geometric shapes: a box and a shifted $\ell_2$-sphere.
  3. ADMM Optimization: By turning a discrete problem into a continuous one, they can use the Alternating Direction Method of Multipliers (ADMM). This algorithm breaks the complex problem into smaller sub-problems—solving for the projection matrix and the selection vector iteratively—until the model converges on the best feature subset.

Datasets

The researchers evaluated their method on three widely recognized benchmark image datasets:

  • Coil-20: 1,440 images of 20 different objects (1024 dimensions).
  • MNIST: 6,996 images of handwritten digits 0-9 (784 dimensions).
  • Yale-B: 2,114 frontal-face images of 38 individuals (1024 dimensions).

Key Insights and Ideas

  • Direct Selection vs. Ranking: Unlike "filter" methods (like Fisher Score) that look at features in isolation, this method looks at the collective predictive power of the feature subset.
  • Geometric Equivalence: The most elegant part of the paper is the proof that a binary constraint (0 or 1) can be perfectly represented by the intersection of a box and a sphere. This allows the authors to use powerful continuous optimization math on a discrete problem.
  • Hard Sparsity: While $\ell_1$ methods often result in many features having tiny, near-zero weights, this ADMM approach enforces "hard" sparsity, ensuring that exactly $k$ features are chosen and the rest are ignored.

Key Results

The proposed method was tested using both 1-Nearest Neighbor (1-NN) and Support Vector Machine (SVM) classifiers.

  • Superior Accuracy: Across all three datasets, the ADMM-based method consistently outperformed state-of-the-art competitors like RFS, ReliefF, and even other $\ell_{0,2}$ approximation methods.
  • Fast Convergence: The algorithm typically reaches a stable solution within 50 to 80 iterations, making it practical for real-world use.
  • Efficiency with Fewer Features: The method showed a particularly strong advantage when the number of selected features ($k$) was small, suggesting it is highly effective at weeding out noise.

Limitations and Future Work

The primary drawback noted is computational complexity. The algorithm requires matrix inversions that scale at $O(D^3)$, where $D$ is the number of dimensions. While this is manageable for the datasets tested (around 1000 dimensions), it could become a bottleneck for extremely high-dimensional "big data" applications (e.g., genomics with tens of thousands of features).

The authors explicitly state that their future work will focus on reducing this computational overhead to make the method more scalable.

Summary updated

Abstract

Recently, structured sparsity inducing based feature selection has become a hot topic in machine learning and pattern recognition. Most of the sparsity inducing feature selection methods are designed to rank all features by certain criterion and then select the k top ranked features, where k is an integer. However, the k top features are usually not the top k features and therefore maybe a suboptimal result. In this paper, we propose a novel supervised feature selection method to directly identify the top k features. The new method is formulated as a classic regularized least squares regression model with two groups of variables. The problem with respect to one group of the variables turn out to be a 0-1 integer programming, which had been considered very hard to solve. To address this, we utilize an efficient optimization method to solve the integer programming, which first replaces the discrete 0-1 constraints with two continuous constraints and then utilizes the alternating direction method of multipliers to optimize the equivalent problem. The obtained result is the top subset with k features under the proposed criterion rather than the subset of k top features. Experiments have been conducted on benchmark data sets to show the effectiveness of proposed method.
BibTeX
@inproceedings{fan2017top,
  author = {Mingyu Fan and Xiaojun Chang and Xiaoqin Zhang and Di Wang and Liang Du},
  title = {{Top-k Supervise Feature Selection via ADMM for Integer Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/228},
}
Figure