Random Feature Pruning: SEED-MAX Algorithm Achieves 92% Pruning Rate

Random feature extraction methods often face the challenge of feature redundancy in multi-class tasks. A recent paper proposes the SEED-MAX algorithm, which recursively computes empirical risk to identify the most compact yet informative feature subset. Experiments show that this method achieves a pruning rate of approximately 92% on UCR time series datasets, with virtually no loss in classification accuracy.

The Feature Redundancy Dilemma of Random Kitchen Sinks

Weighted Random Kitchen Sinks (W-RKS) is a commonly used feature extraction technique in supervised learning. Its core idea is to project raw data into a high-dimensional space via random mappings, then construct classifiers through weighted combinations. The advantage of this approach lies in its computational simplicity and complete theoretical guarantees, making it particularly suitable for handling nonlinearly separable data.

However, the fatal weakness of W-RKS is that the randomly generated features contain a large number of redundant and ineffective components. The sampling process of random weights and biases does not guarantee that every feature contributes to the final classification; many features merely increase model complexity without bringing information gain.

In multi-class problems, this redundancy issue becomes even more pronounced. An increase in the number of classes means more complex decision boundaries, and the proportion of truly effective dimensions in the random feature space further decreases. How to select key subsets from a large number of random features has become the core challenge in improving the practicality of W-RKS.

Random Kitchen Sinks (RKS) was proposed by Rahimi and Recht in 2007, with its theoretical foundation based on random approximation of kernel methods. Traditional kernel methods (such as SVM using RBF kernels) require computing the Gram matrix with complexity of O(n²) or even O(n³), making it difficult to scale to large datasets. The core insight of RKS comes from Bochner's theorem: shift-invariant kernel functions can be represented as expectations under the probability distribution of their Fourier transform (i.e., spectral density). Therefore, one only needs to randomly sample several frequency vectors ω from this distribution and construct the feature mapping z(x) = cos(ωᵀx + b) (with b sampled from a uniform distribution), then the inner product z(x)ᵀz(x') is an unbiased estimate of the kernel function k(x,x'). The weighted version W-RKS further introduces learnable weights for each random feature, determined by minimizing empirical risk, which is equivalent to training a linear model in a high-dimensional random feature space. The advantage of this method lies in combining the expressive power of kernel methods with the training efficiency of linear models, but at the cost of requiring a large number of random features to achieve sufficient approximation accuracy, thereby introducing redundancy.

SEED-MAX: Transforming Feature Selection into Nested Model Selection

The innovation of this paper lies in reformulating the feature selection problem as a variant of the sequential nested model selection problem. Traditional feature selection methods typically evaluate the importance of each feature independently or use greedy strategies to progressively add features. The nested model selection perspective emphasizes the conditional dependencies between features—the value of a feature depends on its combined effect with other already-selected features.

Based on this framework, the authors propose the Successive Empirical Excess Risk Difference Maximization (SEED-MAX) algorithm. The core logic of this algorithm is to recursively compute empirical risk, selecting at each step the candidate feature that can maximally reduce the excess risk to add to the set.

The recursive process of SEED-MAX can be understood as follows: the algorithm maintains a set of selected features, evaluates in each iteration the marginal contribution of all unselected features to the empirical risk when added, selects the feature with the largest contribution to add to the set, then repeats this process. This greedy recursive strategy is computationally efficient while obtaining theoretical guarantees of selection correctness through the theoretical framework of nested model selection.

Sequential nested model selection refers to a candidate model set forming a nested sequence M₁ ⊂ M₂ ⊂ … ⊂ M_K, where the algorithm sequentially selects the best from the current model's extensions at each step. Unlike filter methods that independently evaluate feature importance (such as chi-square tests, mutual information), nested model selection considers interaction effects between features: a feature may contribute little when viewed alone but can significantly reduce risk when combined with another feature. Compared to greedy forward selection, nested model selection emphasizes theoretical guarantees of selection consistency—that is, under what conditions the algorithm can select the truly optimal subset with high probability. SEED-MAX adapts this framework to the feature selection scenario, treating each candidate feature subset as a nested model, and through recursive computation of empirical excess risk (i.e., the difference between the risk of the current subset and the risk after including more features) to determine the addition decision at each step, thereby achieving a balance between greedy efficiency and theoretical guarantees.

Theoretical Guarantees: Lower Bound on Correct Selection Probability

An important theoretical contribution of the paper is deriving a lower bound on the probability of SEED-MAX correctly selecting features. This lower bound indicates that as the training dataset size increases, the probability of the algorithm correctly identifying the optimal feature subset can approach 1 indefinitely.

The significance of this theoretical result lies in providing reliability guarantees for feature pruning. In practical applications, users can work backward from their requirements for correct selection probability to determine the required training sample size. This is more scientific and controllable than relying solely on empirical parameter tuning.

Fisher Test Accelerates Pruning: Achieving 92% Pruning Rate

To further improve pruning speed, the paper introduces the Fisher Test (F-Test) on top of SEED-MAX to further evaluate retained features. The F-Test is used to determine the statistical significance of features on classification results, quickly eliminating features that do not contribute significantly in a statistical sense.

The sequential combination of SEED-MAX and F-Test produces significant results. Experiments on UCR time series classification datasets show that this combined method can achieve approximately 92% pruning rate—meaning only 8% of the original random features are retained—while the decrease in classification accuracy is almost negligible.

Comparative experiments also show that SEED-MAX alone can already effectively prune, but adding F-Test further improves the pruning rate while maintaining classification performance. This indicates that statistical testing and risk minimization-based selection strategies are complementary.

Fisher Test (F-Test) is a parametric test method in statistics used to compare whether the variances of two or more groups of data are significantly different. In the context of feature selection, the F-Test is typically used to evaluate whether the mean differences of a feature across different classes are significant: the ratio of between-group variance to within-group variance constitutes the F statistic, and a larger ratio indicates that the feature contributes more to class discrimination. Under the null hypothesis (feature is independent of class), the F statistic follows an F distribution, from which the p-value can be calculated. When the p-value is below a preset significance level (such as 0.05), the null hypothesis is rejected and the feature is retained; otherwise it is eliminated. The advantage of the F-Test is its extremely fast computation (involving only means and variances), making it suitable for rapid initial screening of large numbers of features. When combined with SEED-MAX, SEED-MAX is responsible for selecting conditionally dependent feature subsets from a global risk perspective, while the F-Test performs secondary refinement from a statistical significance perspective. Their complementarity further improves the pruning rate from the level achieved by SEED-MAX alone to approximately 92%.

Implications for Feature Selection Practice

This work provides a feasible solution path for the efficiency problems faced by random feature methods in practical deployment. A 92% pruning rate means significant reductions in model storage requirements and inference computation, which is particularly important for edge devices and real-time application scenarios.

It is worth noting that the applicability of the SEED-MAX framework may not be limited to W-RKS. Any learning task that relies on a large number of candidate features and performs screening could potentially benefit from this nested model selection perspective. The authors have open-sourced the implementations of SEED-MAX and SEED-MAX-F-Test on GitHub, facilitating reproduction and extension by researchers and engineers.

From a methodological perspective, transforming feature selection into a nested model selection problem provides a new theoretical tool. Future research can explore the application potential of this framework in scenarios such as deep learning feature layer pruning and ensemble learning base learner selection.

One-line Summary

SEED-MAX transforms random feature selection into nested model selection, combining Fisher testing to achieve 92% pruning rate with virtually no accuracy loss on UCR datasets.

Paragraph Summary

This article introduces a recent paper on random feature pruning. Weighted Random Kitchen Sinks (W-RKS), while computationally simple with theoretical guarantees, suffers from severe feature redundancy in multi-class tasks. The paper proposes the SEED-MAX algorithm, reformulating feature selection as a variant of sequential nested model selection, progressively selecting the optimal feature subset by recursively computing empirical excess risk. Theoretical analysis proves that the lower bound on correct selection probability can approach 1 as the training set grows. Building on this, the paper further introduces the Fisher Test (F-Test) for statistical significance screening, achieving approximately 92% pruning rate on UCR time series datasets with virtually no loss in classification accuracy. The algorithm has been open-sourced on GitHub, providing an efficient model compression path for edge devices and real-time applications, and its framework is also expected to extend to scenarios such as deep learning and ensemble learning.