In high-dimensional machine learning, we often face a trade-off between computational efficiency and model accuracy. To combat the "curse of dimensionality," researchers typically turn to dimensionality reduction. While techniques like Principal Component Analysis (PCA) or Random Projections create new, artificial features to represent data, a more interpretable approach is feature selection: choosing a small subset of the original features that preserve the dataset's essential structure.
The challenge lies in knowing which features to keep. Recent research has converged on a powerful mathematical tool to solve this: leverage scores. By treating dimensionality reduction as a spectral problem, researchers have developed algorithms that can prune thousands of dimensions down to a handful while providing rigorous mathematical guarantees on performance.
The Intuition: Finding the "Influential" Dimensions
Not all features contribute equally to the shape of a dataset. Imagine a dataset where one column is almost entirely zeros except for a few critical outliers, while another column contains random noise. The first column has high "leverage" because it defines a unique direction in the data space that cannot be replicated by other features.
Leverage scores quantify this importance. Formally, they are derived from the Singular Value Decomposition (SVD) of the data matrix. As explored in Dimensionality Reduction for k-means Clustering, leverage scores identify the dimensions that are most critical for representing the data's "skeleton." By sampling features with a probability proportional to these scores, we can create a "sketch" of the data that retains its global geometric properties.
Provable Guarantees for Clustering
For a long time, feature selection was guided by heuristics. However, Anastasios Zouzias, Christos Boutsidis, Michael W. Mahoney, and Petros Drineas bridged this gap in Stochastic Dimensionality Reduction for K-means Clustering. They introduced the first feature selection algorithm for $k$-means with provable accuracy guarantees.
The mechanism works by using the SVD to find the best low-rank approximation of the data and then calculating leverage scores relative to that subspace. This ensures that the selected features preserve the distances between points, which is the fundamental requirement for clustering. Even when the number of features is drastically reduced, the resulting clusters remain a constant-factor approximation of the optimal clusters in the original high-dimensional space.
Preserving the Margin in Classification
The utility of leverage scores extends beyond unsupervised learning into supervised tasks like Support Vector Machines (SVMs). In Feature Selection for Linear SVM with Provable Guarantees, Saurabh Paul, Malik Magdon-Ismail, and Petros Drineas demonstrated that leverage-score sampling can reduce features while maintaining the classification margin.
By using spectral sparsification, they showed that one can select a subset of features such that the geometry of the data—specifically the width of the gap separating different classes—is preserved. This allows a linear SVM to be trained on a fraction of the data without losing its ability to generalize to new points.
Local vs. Global Structure
While leverage scores focus on the global spectral structure, other methods like the Laplace scoring algorithm focus on preserving local geometry. In Construction of High-quality Economic Development Indicator System Based on Unsupervised Learning, Liwen Tang and colleagues used this approach to select economic indicators.
The Laplace score evaluates a feature's power to preserve the "neighborhood" of data points. If two points are close in the original space, a good feature should also keep them close in the reduced space. This data-driven approach removes the need for subjective human judgment in feature selection, relying instead on the intrinsic manifold of the data.
Beyond Linear Features: Random Fourier Features
The concept of leverage-based sampling has even reached kernel methods, which operate in infinite-dimensional spaces. Random Fourier Features (RFFs) are typically used to approximate kernels by mapping data into a finite-dimensional space.
Traditional theory suggested that the number of random features needed to maintain accuracy was proportional to the number of data points ($n$). However, Sharp Analysis of Random Fourier Features in Classification shows that by using ridge leverage scores—a variation of leverage scores designed for regularized problems—one can achieve optimal accuracy with only $O(\sqrt{n} \log n)$ features. This significantly lowers the memory and time requirements for large-scale kernel classification.
Summary
The shift from heuristic feature selection to spectral methods like leverage-score sampling represents a move toward more robust, theoretical machine learning. By identifying the "skeletal" dimensions of a dataset through the lens of the SVD or the Laplacian, researchers can reduce dimensionality in a way that is both computationally efficient and mathematically sound. Whether for clustering, SVMs, or kernel methods, these techniques ensure that we lose the noise, but keep the signal.