{'fraction_non_alphanumeric': 0.032885798769279946, 'fraction_numerical': 0.011947574522496604, 'mean_word_length': 4.618994162550516, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Supervised Feature Selection from High Dimensional Feature Spaces

The application of machine learning to image and video data often yields a high dimensional feature space. Effective feature selection techniques identify a discriminant feature subspace that lowers computational and modeling costs with little performance degradation. A novel supervised feature selection methodology is proposed for machine learning decisions in this work. The resulting tests are called the discriminant feature test (DFT) and the relevant feature test (RFT) for the classification and regression problems, respectively. The DFT and RFT procedures are described in detail. Furthermore, we compare the effectiveness of DFT and RFT with several classic feature selection methods. To this end, we use deep features obtained by LeNet-5 for MNIST and Fashion-MNIST datasets as illustrative examples. Other datasets with handcrafted and gene expressions features are also included for performance evaluation. It is shown by experimental results that DFT and RFT can select a lower dimensional feature subspace distinctly and robustly while maintaining high decision performance.


Introduction
Traditional machine learning algorithms are susceptible to the curse of feature dimensionality [1]. Their computational complexity increases with high dimensional features. Redundant features may not be helpful in discriminating classes or reducing regression error, and they should be removed. Sometimes, redundant features may even produce negative effects as their number grows. their detrimental impact should be minimized or controlled. To deal with these problems, feature selection techniques [2,3,4] are commonly applied as a data pre-processing step or part of the data analysis to simplify the complexity of the model. Feature selection techniques involve the identification of a subspace of discriminant features from the input, which describe the input data efficiently, reduce effects from noise or irrelevant features, and provide good prediction results [5].
For machine learning with image/video data, the deep learning technology, which adopts a pre-defined network architecture and optimizes the network parameters using an end-to-end optimization procedure, is dominating nowadays. Yet, an alternative that returns to the traditional pattern recognition paradigm based on feature extraction and classification two modules in cascade has also been studied, e.g., [6,7,8,9,10,11,12,13,14,15]. The feature extraction module contains two steps: unsupervised representation learning and supervised feature selection. Examples of unsupervised representation learning include multi-stage Saab [10] and Saak transforms [6]. Here, we focus on the second step; namely, supervised feature selection from a high dimensional feature space.

arXiv:2203.11924v3 [cs.LG] 19 Jun 2022
Inspired by information theory and the decision tree, a novel supervised feature selection method is proposed in this work. The resulting tests are called the discriminant feature test (DFT) and the relevant feature test (RFT), respectively, for the classification and regression problems. The DFT and RFT procedures are described in detail. We compare the effectiveness of DFT and RFT with several classic feature selection methods. Experimental results show that DFT and RFT can select a significantly lower dimensional feature subspace distinctly and robustly while maintaining high decision performance.
The rest of this paper is organized as follows. Related previous work is reviewed in Sec. 2. DFT and RFT are presented in Sec. 3. Experimental results are shown in Sec. 4. Finally, concluding remarks are given in Sec. 5.

Review of Previous Work
Feature selection methods can be categorized into unsupervised [16,17,18,19], semi-supervised [20,21], and supervised [22] three types. Unsupervised methods focus on the statistics of input features while ignoring the target class or value. Straightforward unsupervised methods can be fast, e.g., removing redundant features using correlation, removing features of low variance. However, their power is limited and less effective than supervised methods. More advanced unsupervised methods adopt clustering. Examples include [23,24,25]. Their complexity is higher, their behavior is not well understood, and their performance is not easy to evaluate systematically. Overall, this is an open research field.
Existing semi-supervised and supervised feature selection methods can be classified into wrapper, filter and embedded three classes [20]. Wrapper methods [26] create multiple models with different subsets of input features and select the model containing the features that yield the best performance. One example is recursive feature elimination (RFE) [27]. This process can be computationally expensive. Filter methods involve evaluating the relationship between input and target variables using statistics and selecting those variables that have the strongest relation with the target ones. One example is the analysis of variance (ANOVA) [28]. This approach is computationally efficient with robust performance. Another example is feature selection based on linear discriminant analysis (LDA). It finds the most separable projection directions. The objective function of LDA is used to select discriminant features from the existing feature dimensions by measuring the ratio between the between-class scatter matrix and the within-class scatter matrix. It can be generalized from the 2-class problem to the multi-class problem. Embedded methods perform feature selection in the process of training and are usually specific to a single learner. One example is "feature importance" (FI) obtained from the training process of the XGBoost classifier/regressor [29], which is also known as "feature selection from model" (SFM).
Inspired by information theory and the decision tree, a novel supervised feature selection methodology is proposed in this work. The resulting tests are called the discriminant feature test (DFT) and the relevant feature test (RFT) for classification and regression tasks, respectively. Our proposed methods belong to the filter methods, which give a score to each dimension and select features based on feature ranking. The scores are measured by the weighted entropy and the weighted MSE for DFT and RFT, which reflect the discriminant power and relevance degree to classification and regression targets, respectively.
To demonstrate the power of DFT and RFT, we conduct performance benchmarking between DFT/RFT, ANOVA and FI from XGBoost in the experimental section. To this end, we use deep features obtained by LeNet-5 for MNIST and Fashion-MNIST datasets as illustrative examples. Other datasets with handcrafted features and gene expressions features are also used for performance benchmarking. Comparison with the minimal-redundancy-maximal-relevance (mRMR) criterion [30,31], which is a more advanced feature selection method, is also conducted. It is shown by experimental results that DFT and RFT can select a lower dimensional feature subspace distinctly and robustly while maintaining high decision performance.

Proposed Feature Selection Methods
Being motivated by the feature selection process in the decision tree classifier, we propose two feature selection methods, DFT and RFT, in this section as illustrated in Fig. 1. They will be detailed in Sec. 3.1 and Sec. 3.2, respectively. Finally, robustness of DFT and RFT will be discussed in Sec. 3.3.

Discriminant Feature Test (DFT)
Consider a classification problem with N data samples, P features and C classes. Let f i , 1 ≤ i ≤ P , be a feature dimension and its minimum and maximum are f i min and f i max , respectively. DFT is used to measure the discriminant power of each feature dimension out of a P -dimensional feature space independently. If feature f i is a discriminant one, we expect data samples projected to it should be classified more easily. To check it, one idea is to partition [f i min , f i max ] into M nonoverlapping subintervals and adopt the maximum likelihood rule to assign the class label to samples inside each subinterval. Then, we can compute the percentage of correct predictions. The higher the prediction accuracy, the higher the discriminant power. Although prediction accuracy may serve as an indicator for purity, it does not tell the distribution of the remaining C − 1 classes if C > 2. Thus, it is desired to consider other purity measures.
In our design, we use the weighted entropy of the left and right subsets as the DFT loss to measure the discriminant power of each dimension. The reason of choosing the weighted entropy as the cost is that it considers the probability distribution of all classes instead of the maximum likelihood rule in prediction accuracy as stated above. A lower entropy value is obtained from a more biased distribution of classes, indicating the subinterval is dominated by fewer classes.
By following the practice of a binary decision tree, we consider the case, M = 2, as shown in the left subfigure of Fig.  1, where f i t denotes the threshold position of two sub-intervals. If a sample with its ith dimension, x i n < f i t , it goes to the subset associated with the left subinterval. Otherwise, it will go to the subset associated with the right subinterval. Formally, the procedure of DFT consists of three steps for each dimension as detailed below.

Training Sample Partitioning
For the ith feature, f i , we need to search for the optimal threshold, f i op , between [f i min , f i max ] and partition training samples into two subsets where x i n represents the i-th feature of the n-th training sample x n , and f i op is selected automatically to optimize a certain purity measure. To limit the search space of f i op , we partition the entire feature range, [f i min , f i max ], into B uniform segments and search the optimal threshold among the following B − 1 candidates: where B = 2 j , j = 1, 2 · · · , is examined in Sec. 3.3.

DFT Loss Measured by Entropy
Samples of different classes belong to S i L or S i R . Without loss of generality, the following discussion is based on the assumption that each class has the same number of samples in the full training set; namely S i L ∪ S i R . To measure the purity of subset S i L corresponding to the partition point f i t , we use the following entropy metric: where p i L,c is the probability of class c in S i L . Similarly, we can compute entropy H i R,t for subset S i R . Then, the entropy of the full training set against partition f i t is the weighted average of H L,t and H R,t in form of where N i L,t and N i R,t are the sample numbers in subsets S i L and S i R , respectively, and N = N i L,t + N i R,t is the total number of training samples. The optimized entropy H i op for the i-th feature is given by where T indicates the set of partition points.

Feature Selection Based on Optimized Loss
We conduct search for optimized entropy values, H i op , of all feature dimensions, f i , 1 ≤ i ≤ P and order the values of H i op from the smallest to the largest ones. The lower the H i op value, the more discriminant the ith-dimensional feature, f i . Then, we select the top K features with the lowest entropy values as discriminant features. To choose the value of K with little ambiguity, it is critical the rank-ordered curve of H i op should satisfy one important criterion. That is, it should have a distinct and narrow elbow region. We will show that this is indeed the case in Sec. 4.

Relevant Feature Test (RFT)
For regression tasks, the mapping between an input feature and a target scalar function can be more efficiently built if the feature dimension has the ability to separate samples into segments with smaller variances. This is because the regressor can use the mean of each segment as the target value, and its corresponding variance indicates the prediction mean squared-error (MSE) of the segment. Motivated by this observation and the binary decision tree, RFT partitions a feature dimension into the left and right two subintervals and evaluates the total MSE from them. We use this approximation error as the RFT loss function. The smaller the RFT loss, the better the feature dimension. Again, the RFT loss depends on the threshold f i t . The process of selecting more powerful feature dimensions for regression is named Relevant Feature Test (RFT). Similar to DFT, RFT has three steps. They are elaborated below. Here, we adopt the same notations as those in Sec. 3.1.

Training Sample Partitioning
By following the first step in DFT, we search for the optimal threshold, f i op , between [f i min , f i max ] and partition training samples into two subsets S i L and S i R for the ith feature, f i . Again, we partition the feature range, [f i min , f i max ], into B uniform segments and search the optimal threshold among the following B − 1 candidates as given in Eq. (3).

RFT Loss Measured by Estimated Regression MSE
We use y to denote the regression target value. For the ith feature dimension, f i , we partition the sample space into two disjoint ones S i L and S i R . Let y i L and y i R be the mean of target values in S i L and S i R , and we use y i L and y i R as the estimated regression value of all samples in S i L and S i R , respectively. Then, the RFT loss is defined as the sum of estimated regression MSEs of S i L and S i R . Mathematically, we have where N = N i L,t + N i R,t , N i L,t , N i R,t , R i L,t and R i R,t denote the sample numbers and the estimated regression MSEs in subsets S i L and S i R , respectively. Feature f i is characterized by its optimized estimated regression MSE over the set, T , of candidate partition points:

Feature Selection Based on Optimized Loss
We order the optimized estimated regression MSE value, R i op across all feature dimensions, f i , 1 ≤ i ≤ P , from the smallest to the largest ones. The lower the R i op value, the more relevant the ith-dimensional feature, f i . Afterwards, we select the top K features with the lowest estimated regression MSE values as relevant features.

Robustness Against Bin Numbers
For smooth DFT/RFT loss curves with a sufficiently large bin number (say, B ≥ 16), the optimized loss value does not vary much by increasing B furthermore as shown in Fig. 2. Figs. 2(a) and (b) show the DFT and RFT loss functions for an exemplary feature, f i , under two binning schemes; i.e., B = 16 and B = 64, respectively. We see that the binning B = 16 is fine enough to locate the optimal partition f i op . If B = 2 j , j = 1, 2, · · · , the set of partition points in a small B value is a subset of those of a larger B value. Generally, we have the following observations. The difference of the DFT/RFT loss between adjacent candidate points changes smoothly. Since the global minimum has a flat bottom, the loss function is low for a range of partition thresholds. The feature will achieve a similar loss level with multiple binning schemes. For example, Fig. 2

Image Datasets with High Dimensional Feature Space
To demonstrate the power of DFT and RFT, we consider several classical datasets. They include MNIST [32], Fashion-MNIST [33], the Multiple Features (MultiFeat) dataset, the Arrhythmia (ARR) dataset [34] from the UCI machine learning archive [35], and the Colon cancer dataset [36]. The latter three are used to measure DFT in the classification problem setting.
Dataset-1: MNIST and Fashion-MNIST. Both datasets contain grayscale images of resolution 28 × 28, with 60K training and 10K test images. MNIST has 10 classes of hand-written digits (from 0 to 9) while Fashion-MNIST has 10 classes of fashion products. In order to get deep features for each dataset, we train the LeNet-5 network [32] for the two corresponding classification problems and adopt the 400-D feature vector before the two FC layers as raw features to evaluate several feature selection methods. Besides original clean training images, we add additive zero-mean Gaussian noise with different standard deviation values to evaluate the robustness of feature selection methods against noisy data. The LeNet-5 network is re-trained for these noisy images and the corresponding deep features are extracted. For the performance benchmarking purpose, we list the test classification accuracy of the trained LeNet-5 for MNIST and Fashion-MNIST in Table 1 to illustrate the quality of the deep features. [37,38,39]. This dataset contains features of hand-written digits (from 0 to 9) extracted from a collection of Dutch utility maps [35], including 649 dimensional features for 200 images per class. Different from the  Dataset-4: ARR. This cardiac arrhythmia dataset has binary labels for 237 normal and 183 abnormal samples. Each sample contains 278 features. The 10-fold cross-validation is adopted to evaluate the classification performance.

DFT for Classification Problems
We compare effectiveness of four feature selection methods: 1) F scores from ANOVA (ANOVA F Scores), 2) absolute correlation coefficient w.r.t the class labels (Abs. Corr. Coeff.), 3) feature importance (Feat. Imp.) from a pre-trained XGBoost classifier, and 4) DFT. We adopt four classifiers to validate the classification performance. They are the Logistic Regression (LR) classifier [40], the Support Vector Machine (SVM) classifier [41], the Random Forest (RF) classifier [42], and the XGBoost classifier [29]. We have the following two observations. Fig. 3 compares the ranked scores of four feature selection methods on Fashion-MNIST dataset. The lower DFT loss, the higher importance of a feature. The other three have a reversed relation, namely, the higher the score, the higher the importance. Thus, we search for the elbow point for DFT but the knee point for the other methods. Clearly, the feature importance curve from the pre-trained XGBoost classifier has a clearer knee point and the DFT curve has a more obvious elbow point. In contrast, ANOVA and correlation-coefficient-based methods are not as effective in selecting discriminant features since their knee points are less obvious.

Features selected by DFT achieves comparable and stable classification performance
Tables 2 -5 summarize the classification accuracy using four classifiers at two reduced dimensions selected by the DFT loss curve based on early and late elbow points on Dataset-1. The RBF kernel is used for SVM. We see that DFT can achieve comparable (or even the best) performance among the four methods at the same selected feature dimension. The accuracy gap between the late elbow point and the full feature set (400-D) is very small. They are 0.62% and 0.94% using XGBoost classifier for clean MNIST and Fashion-MNIST, respectively. The late elbow point only uses 25-35% of the full feature set. The gaps in classification accuracy on noisy images are 0.58% and 1.6% for MNIST and Fashion-MNIST, respectively, indicating the robustness of the DFT feature selection method against input perturbation.
We also show the classification performance on the Colon dataset using LR and SVM in Table 6, where the linear kernel is used in SVM. DFT has the minimum or a comparable number of errors in leave-one-out validation. Furthermore, DFT can always achieve fewer errors as compared to the setting of using all 2000 features.

Comparison between DFT and mRMR
The minimal-redundancy-maximal-relevance (mRMR) [30,31] aims at finding a feature set with high relevance to the class while keeping the selected features with small redundancy, leading to an efficient but effective subset of features. It combines constraints measured by the mutual information of both relevance to the class and redundancy between selected features and treats it as an optimization problem. In this experiment, we compare DFT with mRMR using its incremental selection scheme.
Figs. 4-6 compare the performance of mRMR and DFT on MultiFeat, Colon and ARR datasets with SVM and XGBoost classifiers. For MultiFeat and Colon, DFT can achieve very competitive performance with mRMR. Specifically, the most discriminant feature of MultiFeat selected by DFT is identical to the first feature selected by mRMR. The error rate with the top 5 features selected by mRMR is smaller than that of DFT. Yet, the performance gap is substantially narrowed after selecting more than 10 features out of the total 649 features. Overall, the error rate of DFT and mRMR converges at similar reduced dimensions, as shown in Figs. 4 and 6. On the other hand, the error rate of DFT on the    ARR dataset is much lower than that of mRMR, with around 2.5% and 5% gap at 100 selected features for SVM and XGBoost, respectively, as shown in Fig. 6.

DFT requires less running time
We compare time efficiency of DFT, ANOVA, mRMR and feature importance from the XGBoost model. Table 7 summarizes the running time for MultiFeat, Colon and ARR datasets. All methods are run on the same CPU. The pre-trained XGBoost classifier uses the maximum depth of one with 300 trees. For filter methods such as ANOVA and DFT, the time is evaluated on all features without parallel computing. For mRMR, we set the maximum to 100 for incremental selection, which is smaller than the full feature set. ANOVA is the fastest and DFT method ranks the second on all three datasets. The running time of DFT with B = 16 is about ×2.6, ×7.3 and ×23.1 times faster than mRMR on MultiFeat, Colon and ARR, respectively. To further reduce the running time, our proposed DFT can be easily improved by adopting parallel computing since it processes each feature independently before the feature ranking.

DFT with feature pre-processing
DFT assigns a score to each feature and selects a subset without any pre-processing. Yet, there might be correlation between features so that a redundant feature subset might be selected based on feature ranking [43]. Instead of adding redundancy measure to the DFT loss, we study the effect of combining DFT with feature pre-processing, such as PCA for feature decorrelation. We choose clean MNIST and Fashion-MNIST datasets as examples and perform PCA on the 400-D deep features without energy truncation. The DFT loss is calculated for each of 400 PCA-decorrelated features. After feature selection, the XGBoost classifier is applied. Fig. 7 compares the test accuracy under different selected dimensions for each setting. We see that PCA pre-processing improves the classification performance with the same selected dimension.
Furthermore, PCA pre-processing allows a smaller feature dimension for the same performance. For example, the accuracy on Fashion-MNIST saturates at around 15-D and 30-D with and without pre-processing, respectively. This can be explained by the energy compaction capability of PCA. Fig. 8 shows the histogram of energy ranking of the feature subset selected by DFT with and without PCA preprocessing. The raw features are first sorted by decreasing energy (variance) prior to feature selection. We see that the selected subset tends to gather in the first 20 to 50 principal components with PCA pre-preprocessing while the selected features are more widely distributed without PCA.

RFT for Regression Problems
We convert the discrete class labels arising from the classification problem to floating numbers so as to formulate a regression problem. We compare effectiveness of four feature selection methods: 1) variance (Var.), 2) absolute correlation coefficient w.r.t the regression target (Abs. Corr. Coeff.), 3) feature importance (Feat. Imp.) from a pre-trained XGBoost regressor (of 50 trees), and 4) RFT. Again, we can draw two conclusions.   Table 8 summarizes the regression MSE at two reduced dimensions selected by the RFT loss curves using early and late elbow points. The proposed RFT can achieve comparable (or even the best) performance among the four methods at the same selected feature dimension regardless whether the input images are clean or noisy. By employing only Figure 9: Comparison of relevant feature selection capability among four feature selection methods for the regression task on the Fashion-MNIST dataset.

Conclusion and Future Work
Two feature selection methods, DFT and RFT, were proposed for general classification and regression tasks in this work. As compared with other existing feature selection methods, DFT and RFT are effective in finding distinct feature subspaces by offering obvious elbow regions in DFT/RFT curves. They provide feature subspaces of significantly lower dimensions while maintaining near optimal classification/regression performance. They are computationally efficient. They are also robust to noisy input data.
Recently, there is an emerging research direction that targets at unsupervised representation learning [6,7,8,11,12,14,15]. Through this process, it is easy to get high dimensional feature spaces (say, 1000-D or higher). We plan to apply DFT/RFT to them and find discriminant/relevant feature subspaces for specific tasks.