Discriminative Feature Selection via A Structured Sparse Subspace Learning Module

Zheng Wang, Feiping Nie, Lai Tian, Rong Wang, Xuelong Li

Introduction

In modern data science, high-dimensional datasets—where the number of features far exceeds the number of samples—are commonplace across domains like computer vision, genomics, and text analysis. While rich in information, these datasets often contain significant noise and redundancy. Feature selection is a critical preprocessing step aimed at identifying a discriminative subset of features to improve model performance and reduce computational overhead.

Traditionally, state-of-the-art methods have relied on $\ell_{2,1}$-norm regularization as a convex proxy for sparsity. However, this approach introduces two significant challenges:

  1. Hyperparameter Sensitivity: Users must manually tune a trade-off parameter ($\lambda$) to balance loss against sparsity, a process that is computationally expensive and often lacks a clear heuristic.
  2. Ranking Instability: $\ell_{2,1}$ methods assign continuous scores to features. Minor data perturbations can flip the rankings of features with similar scores, leading to inconsistent and unreliable feature subsets.
Comparison of $L_{2,1}$ sparse learning (a) and $L_{2,0}$ structured sparse learning (b). The latter provides a clear binary selection, avoiding ranking instability.

Methodology: Structured Sparse Subspace Learning ($S^3L$)

To address these limitations, researchers have introduced the Subspace Sparsity Discriminant Feature Selection ($S^2DFS$) algorithm. At its core is the Structured Sparse Subspace Learning ($S^3L$) module, which directly optimizes the $\ell_{2,0}$-norm constraint. Unlike proxy methods, $S^3L$ explicitly limits the transformation matrix to exactly $k$ non-zero rows, corresponding to the desired number of features.

Key Innovations

  • Trace Ratio Objective: The framework utilizes a Linear Discriminant Analysis (LDA) objective in trace ratio form. This formulation is mathematically robust, effectively minimizing intra-class variance while maximizing inter-class separation.
  • Direct $\ell_{2,0}$ Optimization: The authors demonstrate that under low-rank conditions, the typically NP-hard $\ell_{2,0}$ problem admits a closed-form global solution.
  • Minimization-Majorization (MM) Framework: For general cases, an MM framework iteratively solves the non-convex objective by decomposing it into simpler, convergent sub-problems. This ensures a stable solution without the need for sparsity-balancing hyperparameters.

Experimental Evaluation

The $S^2DFS$ algorithm was benchmarked against several high-dimensional datasets, including text (20News, Text1), web data (WebKB), character recognition (Binalpha), and face images (Pixraw10P, Pubfig).

Key Results

The experimental results highlight the superiority of $S^2DFS$ in three main areas:

  1. Classification Accuracy: $S^2DFS$ consistently outperformed state-of-the-art methods like RFS, CRFS, and DLSRFS. As shown in the Pubfig dataset results, the method maintains a performance lead across varying numbers of selected features.
  2. Efficiency and Convergence: The algorithm is highly efficient, typically reaching convergence in fewer than 15 iterations. This rapid convergence is facilitated by a power iteration method used to handle large-scale eigenvalue decompositions.
  3. Stability: By treating feature selection as a structural constraint rather than a weighted ranking, $S^2DFS$ produces more reliable feature subsets that are less sensitive to numerical fluctuations in the input data.
Average classification accuracy on the Pubfig dataset, comparing $S^2DFS$ (labeled 'Our') against other state-of-the-art feature selection methods.

Conclusion and Future Work

$S^2DFS$ represents a significant step forward in feature selection by eliminating the need for tedious hyperparameter tuning and providing a mathematically grounded approach to direct sparsity optimization. While currently limited to linear models, the authors plan to extend the $S^3L$ module to non-linear architectures, potentially further enhancing its discriminative power for complex, non-linear datasets.

Summary updated

Abstract

In this paper, we first propose a novel Structured Sparse Subspace Learning S^3L module to address the long-standing subspace sparsity issue. Elicited by proposed module, we design a new discriminative feature selection method, named Subspace Sparsity Discriminant Feature Selection S^2DFS which enables the following new functionalities: 1) Proposed S^2DFS method directly joints trace ratio objective and structured sparse subspace constraint via L2,0-norm to learn a row-sparsity subspace, which improves the discriminability of model and overcomes the parameter-tuning trouble with comparison to the methods used L2,1-norm regularization; 2) An alternative iterative optimization algorithm based on the proposed S^3L module is presented to explicitly solve the proposed problem with a closed-form solution and strict convergence proof. To our best knowledge, such objective function and solver are first proposed in this paper, which provides a new though for the development of feature selection methods. Extensive experiments conducted on several high-dimensional datasets demonstrate the discriminability of selected features via S^2DFS with comparison to several related SOTA feature selection methods. Source matlab code: https://github.com/StevenWangNPU/L20-FS.
BibTeX
@inproceedings{wang2020discriminative,
  author = {Zheng Wang and Feiping Nie and Lai Tian and Rong Wang and Xuelong Li},
  title = {{Discriminative Feature Selection via A Structured Sparse Subspace Learning Module}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/416},
}
Figure