Introduction
In the era of high-dimensional data, feature vectors often contain thousands or even millions of dimensions, posing significant computational challenges for traditional machine learning algorithms. While Principal Component Analysis (PCA) is a standard tool for dimensionality reduction, its computational cost is often prohibitive for large-scale datasets. Random Projection (RP) offers a faster alternative by using random matrices to project data into lower-dimensional spaces. A popular variant, the Subsampled Randomized Hadamard Transform (SRHT), is favored for its speed, utilizing the Walsh-Hadamard Transform to "rotate" data before uniform sampling.
The Problem with Data-Independence
Standard SRHT is "data-blind." By treating every rotated dimension as equally likely to be informative, it ignores the underlying distribution and labels of the data. This uniform sampling strategy can result in significant variance in classification performance across different random runs, leading to instability and suboptimal accuracy.
As illustrated in the figure above, the accuracy of a linear SVM using standard SRHT can fluctuate wildly depending on the random subset of dimensions selected, making it unreliable for many practical applications.
Proposed Methods: Improved SRHT (ISRHT)
To address these limitations, this research introduces "Improved SRHT" (ISRHT) methods that move away from uniform sampling toward data-dependent strategies:
- ISRHT-nps (Importance Sampling): This method assigns a selection probability to each column based on its Euclidean norm. By prioritizing "high-energy" columns, it better preserves the geometric structure of the original data.
- ISRHT-top-r (Deterministic Sampling): A simpler, greedy version that selects the $r$ columns with the largest Euclidean norms from the rotated matrix.
- ISRHT-supervised: This version incorporates class labels to select columns that maximize inter-class separability while maintaining intra-class compactness. This optimization ensures that the reduced feature space is specifically tuned for classification tasks.
Key Results and Performance
The proposed ISRHT methods were evaluated on several high-dimensional benchmark datasets, including gisette and news20. The results consistently demonstrate that data-aware sampling significantly outperforms standard uniform sampling in both accuracy and stability.
In the gisette dataset comparison, ISRHT-supervised achieves the highest classification accuracy across various dimensions, notably outperforming standard SRHT and other common techniques like Gaussian or Achliotas projections. On the news20 dataset, ISRHT-supervised reached an accuracy of 78.33%, a substantial improvement over the 70.58% achieved by standard SRHT. Furthermore, the deterministic "top-r" approach often outperformed probabilistic importance sampling, suggesting that capturing the most energetic features is highly beneficial for SVM classification.
Conclusion
By incorporating data-dependent sampling strategies, ISRHT significantly enhances the performance and robustness of linear SVMs in high-dimensional settings. These improvements are achieved with negligible computational overhead, preserving the efficiency that makes SRHT a preferred choice for large-scale dimensionality reduction. Future research will focus on extending these supervised sampling techniques to non-linear kernels and other classification frameworks.
Summary updated