Abstract
We consider the problem of semi-supervised feature selection, where we are given a small amount of labeled examples and a large amount of unlabeled examples. Since a small number of labeled samples are usually insufficient for identifying the relevant features, the critical problem arising from semi-supervised feature selection is how to take advantage of the information underneath the unlabeled data. To address this problem, we propose a novel discriminative semi-supervised feature selection method based on the idea of manifold regularization. The proposed method selects features through maximizing the classification margin between different classes and simultaneously exploiting the geometry of the probability distribution that generates both labeled and unlabeled data. We formulate the proposed feature selection method into a convex-concave optimization problem, where the saddle point corresponds to the optimal solution. To find the optimal solution, the level method, a fairly recent optimization method, is employed. We also present a theoretic proof of the convergence rate for the application of the level method to our problem. Empirical evaluation on several benchmark data sets demonstrates the effectiveness of the proposed semi-supervised feature selection method.
Introduction
Feature selection is a critical step in high-dimensional data analysis, aimed at reducing dimensionality and improving model interpretability. In many practical applications, labeled data is expensive to obtain, whereas unlabeled data is plentiful. Traditional supervised methods often struggle with overfitting in small-sample regimes, while unsupervised methods may overlook features essential for classification. This paper addresses the challenge of Semi-Supervised Feature Selection (SSFS) by proposing FS-Manifold, a framework that integrates the discriminative power of maximum-margin classifiers with the structural information provided by unlabeled data through manifold regularization.
The FS-Manifold Framework
The core of the FS-Manifold approach is the integration of manifold regularization into the feature selection process. The method is built on the assumption that the classification function should vary smoothly along the manifold where the data resides. If two data points—whether labeled or unlabeled—are close in the high-dimensional space, they are likely to share the same label. FS-Manifold captures this geometric intuition using a graph Laplacian, which penalizes functions that change rapidly between neighboring points.
Optimization and Continuous Relaxation
The problem is formulated as a convex-concave optimization task. The objective is to maximize the classification margin (similar to Support Vector Machines) while simultaneously minimizing a manifold-based penalty. To handle the combinatorial nature of selecting exactly $m$ features, the authors employ a continuous relaxation, allowing feature weights to vary between 0 and 1, making the mathematical optimization tractable.
Optimization via the Level Method
To solve the resulting optimization problem, the authors utilize the Level Method, a cutting-plane technique known for its efficiency in non-smooth convex optimization. A key contribution of this work is the theoretical proof of the convergence rate for the Level Method in this specific context, establishing a complexity of $O(1/\epsilon^2)$. This ensures that the algorithm can scale to practical problem sizes more effectively than traditional semidefinite programming (SDP) solvers.
Empirical Evaluation
The performance of FS-Manifold was evaluated on two primary benchmarks: the USPS Digit Dataset and the 20-Newsgroups text dataset.
USPS Digit Classification
The experiments focused on challenging binary classification tasks, such as distinguishing between digits 2 vs. 3, 3 vs. 8, and 4 vs.
- The number of labeled training samples was varied from 6 to 40 to assess performance in low-data regimes.
Key Results
As shown in the figures, FS-Manifold consistently achieves higher test accuracy than supervised baselines like Fisher score, L0-SVM, and L1-SVM. The performance gap is most pronounced when the number of labeled samples is extremely small (e.g., 6 or 10 samples), highlighting the effectiveness of leveraging unlabeled data to "fill the information gap."
In the 20-Newsgroups text classification tasks (DS1: auto vs. motor, DS2: baseball vs. hockey, DS3: gun vs. mideast), FS-Manifold also demonstrated superior performance. For instance, on the "gun vs. mideast" task, the method improved accuracy by approximately 4% over the Fisher method. Furthermore, FS-Manifold exhibited lower standard deviation across trials, indicating greater stability and robustness to the specific choice of labeled samples.
Conclusion and Future Work
FS-Manifold provides a robust framework for feature selection when labeled data is limited. By combining the "maximum margin" principle with manifold regularization, the algorithm effectively utilizes the geometric structure of unlabeled data to guide feature selection.
Despite its success, the method has limitations. It requires the user to specify the number of features to select ($m$) beforehand, which the authors identify as an "external oracle" problem. Additionally, constructing the adjacency graph for manifold regularization can be computationally expensive for extremely large-scale datasets. Future work may explore automated methods for determining the optimal number of features and further optimizing graph construction techniques.
Summary updated