Algorithmic stability and generalization of an unsupervised feature selection algorithm

Xinxing Wu, Qiang ChengNeurIPS 2021

Introduction

High-dimensional data is a double-edged sword in modern machine learning: it contains vast amounts of information but suffers from the "curse of dimensionality," making models computationally expensive and prone to overfitting. While dimensionality reduction techniques like Principal Component Analysis (PCA) help extract features, they create "latent" representations that are notoriously hard to interpret. With PCA, you cannot easily tell which specific original variables—such as a specific gene expression or an individual image pixel—actually drive the model's decisions.

Feature selection solves this interpretability issue by picking a discrete subset of the original variables. However, most existing unsupervised feature selection tools operate as theoretical "black boxes." Until now, the field has lacked a clear mathematical understanding of their algorithmic stability (how much the output changes if the training data is slightly perturbed) and their generalization ability (how well the selected features will perform on unseen data). This paper introduces a novel unsupervised feature selection algorithm that finally bridges the gap between heuristic performance and theoretical rigor, providing provable guarantees for both stability and generalization error.

A Dual-Network Architecture: Scorer and Selector

To tackle this theoretical void, the authors propose an Autoencoder (AE)-based architecture comprising two distinct but interacting components:

  1. The Feature Scorer: A global neural network that assigns an importance score to every feature based on its ability to reconstruct the entire dataset.
  2. The Feature Selector: A dependent sub-network that isolates only the top-$k$ highest-scoring features to perform the actual data reconstruction.

The core innovation of this method is utilizing the global scorer as a regularizer for the selector. During training, these two components interact iteratively. The scorer ensures that features are explored globally for their representational capacity, while the selector locally "excavates" the most essential variables.

Original images, selected pixel features, and reconstructed outputs for the COIL-20 dataset.

Mathematically, the authors prove that this dual-structure leads to Uniform Stability. They establish a convergence rate for the generalization error of $O(1/\sqrt{n})$, providing a theoretical safety net that ensures the algorithm is learning underlying patterns rather than simply memorizing the training samples.

Key Insights and Theoretical Contributions

The paper reinforces a core tenet of learning theory: if an algorithm is stable and insensitive to small perturbations in its input, it is significantly more likely to generalize well to unseen data.

Interestingly, the authors demonstrate that even when using a linear encoder and decoder, the discrete act of ranking and selecting the top-$k$ features introduces a "natural" non-linearity. This allows the model to capture complex data structures without relying on heavy non-linear activation functions, which are traditionally much harder to analyze theoretically.

The balance between the scorer and the selector is controlled by a regularization parameter ($\lambda_1$). The authors show that a properly tuned $\lambda_1$ is essential; setting it too high causes the model to underfit, while setting it too low forfeits the mathematical stability guarantees.

Empirical Evaluation and Results

The researchers evaluated their model across 10 diverse real-world datasets to ensure robustness across different domains, including Biological/Medical data (Mice Protein, GLIOMA, Prostate_GE, SMK_CAN_187, arcene), Image Recognition (COIL-20, MNIST-Fashion, USPS), and Speech/Activity data (ISOLET, Activity). The proposed method was benchmarked against ten established baselines, such as Laplacian Score (LS), Concrete Autoencoders (CAE), and Agnostic Feature Selection (AgnoS-S).

Selected pixel features highlighted in red on the USPS digit dataset.

The empirical results strongly validated the theoretical claims:

  • Superior Reconstruction: The proposed algorithm consistently achieved a lower Mean Squared Error (MSE) in data reconstruction compared to all ten baseline methods.
  • Better Downstream Performance: When the selected features were fed into a separate downstream classifier (Extremely Randomized Trees), the accuracy was significantly higher. Most notably, on the Mice Protein dataset, the new method achieved 99.1% accuracy, completely eclipsing the best baseline (AgnoS-S), which trailed at 51.9%.
  • Validation of Theory: Experimental plots confirmed that as the number of training samples ($n$) increased, the generalization gap (the difference between training error and test error) decreased exactly as predicted by their $O(1/\sqrt{n})$ theoretical bound.

Limitations and Future Work

Despite its strong theoretical foundation and empirical success, the algorithm has practical limitations. Primarily, it requires the user to pre-define $k$, the exact number of features to select. Similar to choosing the number of clusters in k-means, this remains a practical challenge that often requires domain expertise or extensive cross-validation.

Furthermore, while the paper successfully proves the theory for a linear version of the architecture, the authors acknowledge that fully non-linear scorers and selectors might offer even better empirical performance. However, establishing theoretical stability proofs for fully non-linear variants would be significantly more complex. Finally, future work could extend this logic beyond raw input variables (like individual pixels or genes) to select "important patterns" or higher-level structural features.

Summary updated

BibTeX
@inproceedings{wu2021algorithmic,
  author = {Xinxing Wu and Qiang Cheng},
  title = {{Algorithmic stability and generalization of an unsupervised feature selection algorithm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
}
Figure