Abstract
This paper introduces a novel framework for feature selection in linear classifiers by utilizing only the first two moments—mean and covariance—of data classes. By integrating the multivariate Chebychev-Cantelli inequality with $L_1$ regularization, the author formulates the feature selection problem as a Second Order Cone Program (SOCP). This approach provides a guaranteed upper bound on misclassification error while identifying a minimal set of relevant features, offering a robust, distribution-independent alternative to traditional classification methods.
Introduction
In the era of high-dimensional data, fields such as genomics frequently encounter the "curse of dimensionality." Researchers often deal with datasets containing thousands of features (e.g., gene expressions) but only a handful of samples. In such scenarios, selecting the most relevant features is essential for building interpretable and generalizable classifiers.
Traditional feature selection often relies on the $L_0$ norm to count non-zero weights, a combinatorial problem that is NP-hard. Furthermore, many existing classifiers assume specific underlying data distributions, such as Gaussianity. This research addresses two primary gaps: achieving distribution independence—building a classifier that works for any distribution given its moments—and ensuring robustness against noisy or inaccurate estimates of mean and covariance in small-sample regimes.
Methodology
Moment-Based Classification
The proposed framework shifts the focus from individual raw data points to summary statistics. Each class is represented by its mean ($\mu$) and covariance ($\Sigma$). To handle the uncertainty of the underlying distribution, the author employs a multivariate version of the Chebychev-Cantelli inequality. This inequality allows for the definition of a "worst-case" scenario, ensuring the classifier maintains a specific performance level regardless of the actual data distribution.
Sparsity and SOCP Formulation
To achieve feature selection, the author incorporates $L_1$ regularization. By minimizing the $L_1$ norm of the weight vector $w$, the model encourages sparsity, effectively forcing the weights of irrelevant features to zero.
By combining these probabilistic bounds with the $L_1$ objective, the problem is transformed into a Second Order Cone Program (SOCP). SOCPs are a class of convex optimization problems that can be solved efficiently using modern interior-point methods, providing a more tractable alternative to $L_0$ optimization.
Robustness Extension
Recognizing that empirical estimates of mean and covariance are often noisy in small-sample settings, the paper introduces a "Robust SOCP." This formulation assumes that the true moments lie within an uncertainty set (specifically an ellipsoid) centered around the empirical estimates. To maintain computational tractability, the author restricts this uncertainty to the linear span of the training data.
Experimental Evaluation
Datasets
The performance of the SOCP formulations was evaluated on two distinct types of data:
- Synthetic Data: A controlled environment with 1,000 features where only 10 were discriminatory. This tested the algorithm's ability to filter out 99% noise.
- Microarray Data (SRBCT): Real-world biological data involving Small Round Blue Cell Tumors. This included six binary classification tasks with 2,308 features and very small sample sizes (often fewer than 30 per class).
Key Findings
- The $\eta$ Dial: The parameter $\eta$ represents the lower bound on the probability of correct classification. The research highlights a trade-off: increasing $\eta$ improves the guaranteed accuracy bound but typically requires the inclusion of more features.
- Feature Sparsity: On synthetic data, the SOCP correctly identified the 10 relevant features. At lower $\eta$ values, it proved even more selective than standard Linear Programming (LP), identifying only the single most critical feature. On the SRBCT datasets, the SOCP achieved zero Leave-One-Out (LOO) error using less than 2% of available features.
- Generalization and Fisher Connection: The author demonstrates that the classic Fisher Discriminant is a special case of this framework when the probability bound $\eta$ is maximized. While standard LP formulations sometimes found slightly smaller feature sets, the SOCP approach provided competitive results with the added benefit of a rigorous probabilistic guarantee on generalization error.
Conclusion and Future Work
This paper demonstrates that summary statistics—the first two moments—are sufficient for effective feature selection and classification in high-dimensional spaces. The SOCP framework offers a robust, distribution-free method for identifying critical features, particularly in "small $m$, large $n$" scenarios common in bioinformatics.
While the current formulation assumes the data lies within the linear span of the training set—a potential limitation in some real-world applications—it opens the door for significant future work. The author suggests that extending this framework via kernels to create nonlinear classifiers is a promising direction for advanced data-mining applications.
Summary updated