Random Feature Pruning for Multi-Class Classification

Mohammad Amin Omidi; Babak Seyfe; Shahrokh Valaee

cs.LGOct 10, 2026

Random Feature Pruning for Multi-Class Classification

Authors: Mohammad Amin Omidi, Babak Seyfe, Shahrokh Valaee

Organizations: Information Theoretic Learning Systems Laboratory (ITLSL), Department of Electrical Engineering, Shahed University, Tehran, Iran · Department of Electrical and Computer Engineering, University of Toronto, Toronto, Canada

Abstract

Weighted sums of random kitchen sinks (W-RKS) is a commonly used feature extraction technique for supervised learning tasks. A major drawback of this method is the redundancy and ineffectiveness of many extracted random features. This paper investigates efficient methods for reducing such redundancy in multi-class classification problems. We specifically formulate feature selection as a variant of the sequentially nested model selection problem and introduce the Successive Empirical Excess Risk Difference Maximization (SEED-MAX) algorithm. It recursively computes empirical risks to identify the most parsimonious yet informative set of features. We derive an analytical lower bound for the probability of correct feature selection by the SEED-MAX algorithm. This lower bound on the probability of correct feature selection can be made arbitrarily close to one by increasing the training dataset size. To further enhance the rate of pruning, we evaluate the features retained by SEED-MAX using the Fisher test (F-Test). Empirical evaluations on UCR time-series classification datasets show that the sequential application of SEED-MAX with the Fisher test achieves approximately 92 percent rate of pruning with negligible degradation in classification accuracy. Implementations of the SEED-MAX and SEED-MAX-F-Test methods are available at https://github.com/OmidiAmin/seed-max-ftest.

Figures & tables

Figure 1: A visual illustration of the SEED-MAX algorithm (Algorithm 1 ).

Figure 2: Comparing empirical accuracy of estimating the most parsimonious set of features with the lower bound of Theorem 2 .

Method	UCR (107)			UCR ( $\geq 10$ classes, 13)			UCR (10 classes, 6)			UCR (12 classes, 5)			UCR (37 classes, 1)
	$P_{CC}(\%)$	$R_{P}(\%)$	$T_{I}$	$P_{CC}(\%)$	$R_{P}(\%)$	$T_{I}$	$P_{CC}(\%)$	$R_{P}(\%)$	$T_{I}$	$P_{CC}(\%)$	$R_{P}(\%)$	$T_{I}$	$P_{CC}(\%)$	$R_{P}(\%)$	$T_{I}$
MINIROCKET	86	0	1	85	0	1	82	0	1	72	0	1	82	0	1
POCKET	85	65	0.48	82	57	0.57	82	62	0.35	72	39	0.56	82	65	0.29
Detach-ROCKET	83	88	0.11	84	85	0.13	80	78	0.22	69	90	0.09	81	82	0.13
HIERVAR	85	91	0.16	85	74	0.24	82	82	0.14	71	79	0.18	83	59	0.35
F-Test	85	32	0.9	85	26	0.99	82	29	0.7	72	42	0.56	82	20	0.8

Table 1: Empirical results over 107 cleaned UCR [ 48 ] time-series classification datasets, evaluated using the probability of correct classification

(P_{CC})

, the rate of pruning

(R_{P})

, and the relative inference time

(T_{I})

Panel of Figure 3 — Figure 3: Performance comparison of feature selection methods based on the probability of correct classification $P_{CC}$ versus the rate of pruning $R_{p}$ on UCR datasets with varying class counts.

Panel of Figure 4 — Figure 4: Performance trajectories of various feature selection methods on (a) FordA (in UCR archive) as a 2-Class dataset, over the set of different training sample sizes $\mathcal{M}=\{134,258,496,954,1830,3508\}$ , and (b) MelbournePedestrian (in UCR archive) as a 10-Class dataset, over the set of different training sample sizes $\mathcal{M}=\{80,130,230,400,670,1140\}$ .

Panel of Figure 5 — Figure 5: Critical difference diagrams for different feature selection methods. (a) Ranking based on $P_{CC}$ over 2-Class UCR Datasets. (b) Ranking based on $R_{P}$ over 2-Class UCR Datasets. (c) Ranking based on $P_{CC}$ over UCR Datasets with more than 10 classes. (d) Ranking based on $R_{P}$ over UCR Datasets with more than 10 classes.

Feature Selection

Feature selection identifies compact, informative variables or input dimensions to improve prediction, efficiency, interpretability, and statistical inference.

See all 194 papers

Feature Selection for Latent Factor Models
Dec 13, 2024Rittwika Kansabanik, Adrian BarbuFeature Selection
Department of Statistics, Florida State University
Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction
Sep 5, 2026Jiancheng Tu, Wenqi FanDecision Tree Learning Dynamic Programming
Department of Computing, The Hong Kong Polytechnic University · Department of Management and Marketing, The Hong Kong Polytechnic University
FSEVAL: Feature Selection Evaluation Toolbox and Dashboard
Apr 20, 2026Muhammad Rajabinasab, Arthur ZimekFeature Selection Automated Evaluation
Department of Mathematics and Computer Science University of Southern Denmark Odense, Denmark

Dec 13, 2024J/K move · Enter open · S save

Feature Selection for Latent Factor Models

Rittwika Kansabanik, Adrian Barbu

Department of Statistics, Florida State University

Feature Selection

Open paper AskPDF arXiv

Feature selection is crucial for pinpointing relevant features in high-dimensional datasets, mitigating the 'curse of dimensionality,' and enhancing machine learning performance. Traditional feature selection methods for classification use data from all classes to select features for each class. This paper explores feature selection methods that select features for each class separately, using class models based on low-rank generative methods and introducing a signal-to-noise ratio (SNR) feature selection criterion. This novel approach offers a theoretically sound guarantee of feature recovery under specific assumptions and has been demonstrated to outperform some existing feature selection methods on standard classification datasets. Additionally, it can be easily applied in a class-incremental learning setup, yielding performance comparable to that of some current methods.

Abstract

Feature Selection

Explore similar work

Feature Selection for Latent Factor Models

Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction

FSEVAL: Feature Selection Evaluation Toolbox and Dashboard