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
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 ( ≥10 classes, 13)
UCR (10 classes, 6)
UCR (12 classes, 5)
UCR (37 classes, 1)
PCC(%)
RP(%)
TI
PCC(%)
RP(%)
TI
PCC(%)
RP(%)
TI
PCC(%)
RP(%)
TI
PCC(%)
RP(%)
TI
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 (PCC) , the rate of pruning (RP) , and the relative inference time (TI) .
Figure 3: Performance comparison of feature selection methods based on the probability of correct classification PCC versus the rate of pruning Rp on UCR datasets with varying class counts.
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 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 M={80,130,230,400,670,1140} .
Figure 5: Critical difference diagrams for different feature selection methods. (a) Ranking based on PCC over 2-Class UCR Datasets. (b) Ranking based on RP over 2-Class UCR Datasets. (c) Ranking based on PCC over UCR Datasets with more than 10 classes. (d) Ranking based on RP over UCR Datasets with more than 10 classes.
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.
Rittwika Kansabanik, Adrian Barbu
Department of Statistics, Florida State University
Dynamic programming for optimal classification trees becomes computationally expensive as the numbers of features and training samples increase. We develop a joint feature- and sample-space reduction framework based on STreeD. Weighted STreeD merges duplicate records created after projection onto a fixed candidate set into weighted representatives. This reduces sample-dependent computation without changing the fixed-candidate optimization problem. Adaptive STreeD repeatedly refines a bounded candidate set, retains features used by the incumbent tree, rebuilds the weighted representation, and solves the resulting reduced problems. Each certified Weighted STreeD solution is optimal for its current candidate set, while the outer feature search remains heuristic over the full feature space. Experiments on five data sets show that Weighted STreeD achieves speedups of up to 121.41 times over standard STreeD. Adaptive STreeD reduces runtime in matched comparisons at depths 2 to 4 and continues to return feasible trees at greater depths where full-feature methods are limited by time or memory. Under the same computational budget, its predictive performance remains comparable to the evaluated optimal classification tree baselines and is higher in some comparisons. These results show how joint feature- and sample-space reduction can scale dynamic-programming-based optimal-tree learning to more demanding instances.
Jiancheng Tu, Wenqi Fan
Department of Computing, The Hong Kong Polytechnic University · Department of Management and Marketing, The Hong Kong Polytechnic University
Feature selection is a fundamental machine learning and data mining task, involved with discriminating redundant features from informative ones. It is an attempt to address the curse of dimensionality by removing the redundant features, while unlike dimensionality reduction methods, preserving explainability. Feature selection is conducted in both supervised and unsupervised settings, with different evaluation metrics employed to determine which feature selection algorithm is the best. In this paper, we propose FSEVAL, a feature selection evaluation toolbox accompanied with a visualization dashboard, with the goal to make it easy to comprehensively evaluate feature selection algorithms. FSEVAL aims to provide a standardized, unified, evaluation and visualization toolbox to help the researchers working in the field, conduct extensive and comprehensive evaluation of feature selection algorithms with ease.
Muhammad Rajabinasab, Arthur Zimek
Department of Mathematics and Computer Science University of Southern Denmark Odense, Denmark