Co-Regularized Ensemble for Feature Selection

1 Introduction

Feature selection aims to reduce redundancy and noise in the original feature set. It has twofold role in improving both the efficiency and accuracy of data analysis. During recent years, feature selection has attracted much research attention [Gao et al., 2011; Nie et al., 2010; Cai et al., 2011; Zhao and Liu, 2007; Yang et al., 2011]. Supervised feature selection determines feature relevance by evaluating feature's correlation with the classes. It usually yields better and more reliable performance than unsupervised feature selection because of the utilization of class labels. However, in many real world applications, labeling a large number of training data is tedious and time-consuming. Provided the number of labeled training data is small, the performance of existing feature selection algorithms is usually restrained. Therefore, it turns out to be a great challenge to design a feature selection algorithm for the cases when only a few labeled data per class are available.

Suppose we have a supervised learning problem where the number of features is very large (compared to the number of labeled training data), but there is only a small number of features that are relevant to the learning task. In such a setting, over-fitting would be a potential problem. We can apply feature selection to reduce the number of features. Alternatively, we can use the technique of regularization to control the over-fitting phenomenon. For example, the penalty term of ℓ1-norm in Lasso [Tibshirani, 1996] is used to induce sparse model, whereas the ℓ2-norm in ridge regression [Hoerl and Kennard, 1970] is used to discourage the coefficients from reaching large values. In order to evaluate the importance of the selected features jointly, the ℓ2,1-norm regularized feature selection algorithms [Nie et al., 2010; Cai et al., 2011] utilize ℓ2,1-norm to control classifier's capacity and also ensure it is sparse in rows, making it particularly suitable for feature selection.

SVM maximizes the geometric margin of training data. The hyperplane for classification is constructed by finding a subset of the most discriminative training data, i.e., the support vectors. Whereas, least square regression minimizes the sum of squared residuals between an observed value and the fitted value provided by a model and all the training data. If we add an ℓ2,1-norm to different loss functions of SVM and least square regression, e.g., ℓ2,1-norm SVM [Cai et al., 2011] and ℓ2,1-norm least square regression [Nie et al., 2010], the selected feature subset learned from the same training set may be different. This disagreement motivates us to ensemble different criteria and take advantages of them, the goal of which is to obtain an optimal feature subset. Minimization of a co-regularization term has been shown to be an effective way to reduce disagreement of different classifiers [Brefeld et al., 2006; Sindhwani and Rosenberg, 2008]. In this paper, we propose to ensemble different feature selection algorithms by adding a joint ℓ2,1-norm of multiple feature selection matrices which correspond to different feature selection algorithms. This joint ℓ2,1-norm plays the role of co-regularization as follows. In each round of the alternating optimization algorithm developed in this paper, the updated feature selection matrices in the former rounds can be used to regularize the current optimization criterion. Thus, the joint ℓ2,1-norm can enhance the regularization effect for each criterion. The benefits are: On one hand, for the cases when the number of labeled training data is small, co-regularization can further alleviate over-fitting. On the other hand, common irrelevant or noisy features in different feature selection matrices should be uncovered, which results in an optimal feature subset.

Note that the co-regularized classifiers in this paper are trained on the same training set represented in the same feature space, which is different from the multi-task learning [Argyriou et al., 2008; Ma et al., 2012; Yang et al., 2013] and the co-regularization methods in multi-view learning [Brefeld et al., 2006; Sindhwani and Rosenberg, 2008]. Although previous works [Opitz, 1999; Tsymbal et al., 2003] also addressed feature selection and ensembles, the goals are to improve classification by re-sampling different feature subsets, which is not for feature selection. How to ensemble different classifiers by a co-regularized ℓ2,1-norm for feature selection has not been explored in previous works.

2 The Objective Function

In this section, we give the objective function of the coregularized Ensemble for Feature Selection (EnFS) algorithm proposed in this paper. Later in the next section, we propose an efficient algorithm to optimize the objective function. It is worth mentioning that EnFS aims to select discriminative features according to labels of the training data, where different models of supervised feature selection are integrated through a co-regularization term, making it different from existing feature selection algorithms.

Denote X = {x1, x2, . . . , xn} as the training set, where xi ∈ Rd (i = 1, . . . , n) is the i-th datum and n is the total number of training data. Suppose the n training data x1, x2, . . . , xn are sampled from c classes, we define yi ∈ {0, 1}c×1 (i = 1, . . . , n) as the label vector of xi. The jth element of yi is 1 if xi belongs to the j-th class, and 0 otherwise. X = [x1, x2, . . . , xn] ∈ Rd×n is the data matrix. Y = [y1, y2, . . . , yn] ∈ {0, 1}c×n is the label matrix. In this paper, I is the identity matrix. For a constant m, 1m ∈ Rm is a column vector with all of its elements being 1 and Hm = I - 1m 1m1Tm ∈ Rm×m is the centering matrix. For an arbitrary matrix A ∈ Rr×p , its ℓ2,1-norm is defined as ||A||2,1 = ∑ri=1 √∑pj=1 A2ij . Tr(·) represents the trace operator.

Suppose we have t feature selection matrices Wl ∈ Rd×c (l = 1, . . . , t), which are learned respectively from t classifiers:

where l = 1, . . . , t and λl > 0 is the regularization parameter of the l-th classifier. Function Ll and J l are the loss and regularization functions, respectively. In Eq. (1), regularization function J l has twofold role in controlling the capacity of Wl to avoid over-fitting and inducing sparsity in Wl for feature selection. For example, as indicated in [Nie et al., 2010; Yang et al., 2011], when minimizing the ℓ2,1-norm of Wl, some rows of Wl shrink to zero, making Wl particularly suitable for feature selection. As mentioned before, when using Wl(l = 1, . . . , t) for feature selection, the selected appropriate feature subset may be different for different classifiers. That is, if we uncover the common irrelevant or noisy components in Wl(l = 1, . . . , t), we can expect a better performance of feature selection.

Denote W = [W1, . . . ,Wt] ∈ Rd×(∑tl=1 c) and define a co-regularization function Ω(W), the objective function of the co-regularized ensemble for feature selection is

where α > 0 is the regularization parameter. Note that, the t classifiers in Eq. (2) are trained on the same training set {X, Y }, making it different from the multi-task learning methods [Argyriou et al., 2008; Ma et al., 2012; Yang et al., 2013]. The minimization problems in Eq. (2) can be solved using an alternating optimization method. That is, the remaining t-1 feature selection matrices Wj(j = 1, . . . , l - 1, l + 1, . . . , t) are fixed when optimizing the l-th classifier. Thus, the corresponding fixed parts in the co-regularization function Ω(W) can be used to regularize the l-th classifier for the current iteration round. In this way, the problem of overfitting can be further alleviated, especially for the cases when only a few labeled data per class are available. Furthermore, the minimization of the co-regularization function Ω(W) also uncovers the common irrelevant or noisy components in the t feature selection matrices Wl(l = 1, . . . , t). The optimal W may lead to a better performance of feature selection than using each Wl(l = 1, . . . , t), which are estimated respectively from each classifier.

In our EnFS algorithm, we use two representative loss functions of multi-class SVM [Crammer and Singer, 2002] and least square regression. The goal is to take advantages of them and obtain an optimal feature subset. For each classifier, we propose to select the features that are most correlated to labels and rewrite Eq. (2) as follows for feature selection.

where b ∈ Rc×1 is the bias term for the least square regression. In Eq. (3), W = [W1,W2] and t = 2. Function f svm is the multi-class hinge loss defined as [Crammer and Singer, 2002; Cai et al., 2011]

where W1 = [w1, . . . ,wc]. The index yi ∈ {1, . . . , c} and yi = j if Yji = 1. In Eq. (3), with the term ||W1||2,1 and ||W2||2,1, our algorithm is able to evaluate the informativeness of all features jointly for the multi-class SVM and least square regression, respectively. The co-regularization term ||W||2,1, on the other hand, enables W1 and W2 to have the same sparse patterns and share the common components. In the optimization of Eq. (3), the fixed part of W1 in ||W||2,1

can be used to regularize the least square regression, and vice versa, which can help to tackle the problem of over-fitting and result in an optimal W for feature selection.

3 Optimization of EnFS Algorithm

In this section, we introduce the optimization of the objective function in Eq. (3). In fact, there are two unknown variables W1 and W2 to be estimated. We propose an alternating optimization algorithm to solve the optimization problem in Eq. (3).

Denote Wl = [w1 l , . . . ,wd l ] (l = 1, 2) and W = [w1 , . . . ,wd ], where d is the number of features. We first fix W2, and the optimization problem becomes:

following [Ma et al., 2012], we rewrite Eq. (5) as follows:

where D1 and D are diagonal matrices with each element on the diagonal, i.e., d1ii and dii (i = 1, . . . , d), are respectively defined as

Omit the fixed part Tr(W T 2 DW2) in Eq. (6), we have

where µ = α/λ1. Denote U = D1 + µD we have

Eq. (9) is the objective function of multi-class ℓ2,1-norm SVM [Cai et al., 2011], which can be efficiently solved by alternately updating W1 and U until convergency. When U is fixed, let W ∗ 1 = U 12W and X∗ = U - 12 X, objective function in Eq. (9) is equivalent to

which can be solved by Crammer's algorithm [Crammer and Singer, 2002] using LIBLINEAR [Fan et al., 2008]. Let ˆ W1 ∗ be the solution of Eq. (10), we have

Then we fix W1, the objective function in Eq. (3) becomes min W2 ||W T 2 X+b1Tn -Y ||2F +λ2||W2||2,1+α||W||2,1, (12)

Algorithm 1 Ensemble Feature Selection (EnFS)

Input: Input data X ∈ Rd×n and labels Y ∈ {0, 1}c×n . Regularization parameters λ1, λ2, and α

Output: Matrix W ∈ Rd×c

• 1: Set r = 0 and initialize W1 ∈ Rd×c and W2 ∈ Rd×c randomly;
• 2: W = [W1,W2];
• 3: repeat
• 4: Compute the diagonal matrix Dr 1 , Dr 2 , and Dr according to d1ii = 1 2||wi1 ||2 , d2ii = 1 2||wi2 ||2 , and dii = 1 2||wi ||2 ;
• 5: repeat
• 6: Compute W ∗ 1 = U 12W and X∗ = U - 12X;
• 7: Solve Eq. (10) and compute W ∗ 1 ;
• 8: Update U by U =D1 + α λ1 D;
• 9: until Convergence
• 10: Update W1 byW r+1 1 = U - 12 ˆ W1 ∗ ;
• 11: Update W2 by W r+1 2 = (XHnHT n XT + λ2D2 + αD)-1XHnY T ;
• 12: Update W r+1 = [W1,W2];
• 13: r = r +1;
• 14: until Convergence
• 15: ReturnW.

which is equivalent to

where D2 is a diagonal matrix with each element d2ii (i = 1, . . . , d) on the diagonal, which is defined as

By setting the derivative of Eq. (13) w.r.t. b to 0. we have

Substituting Eq. (15) into Eq. (13) we obtain

By setting the derivative of Eq. (16) w.r.t. W2 to 0, we have

Therefore, we have

Based on the above mathematical deduction, we propose an alternating algorithm to optimize the objective function in Eq. (3), which is summarized in Algorithm 1. Once W is obtained, we sort the d features according to ||wi ||F (i = 1, . . . , d) in descending order and select the top ranked ones. The convergence of solving Eq. (9) by alternately updating W1 and U has been proved in [Cai et al., 2011]. The object function in Eq. (13) is equivalent to

which is the object function of the ℓ2,1-norm regularized least square regression and its convergence has been proved in [Nie et al., 2010]. Thus, when we alternately fix the values of W1 and W2, the optimal solutions obtained from Algorithm 1 make the value of objective functions decreased and Algorithm 1 is guaranteed to be converged.

4 Experiments

4.1 Experiment Setup

In our experiment, we have collected a diversity of 6 public datasets to compare the performance of different feature selection algorithms. These datasets include two color image datasets, i.e., MIML [Zhou and Zhang, 2007] and MFlickr [Huiskes and Lew, 2008], one hand written digit image dataset, i.e., USPS [Hull, 1994], one face image dataset, i.e., YaleB [Georghiades et al., 2001], one protein gene data, i.e., Protein [Wang, 2002], and one vehicle classification data in distributed sensor networks, i.e., SensIT Vehicle [Duarte and Hen Hu, 2004]. Detailed information of the six datasets is summarized in Table 1. For MIML and MFlickr, we extract the 128 dimensional color coherence as features for each image. As there exists the multi-labeled samples in MIML and MFlickr, we remove these samples and let each sample only belong to one class.

We compare EnFS proposed in this paper with the following feature selection algorithms.

• Full Features which adopts all the features for classification. It is used as baseline method in this paper.
• Fisher Score [Duda et al., 2001] which depends on fully labeled training data to select features with the best discriminating ability.
• Feature Selection via Joint ℓ2,1-Norms Minimization (FSNM) [Nie et al., 2010] which employs joint ℓ2,1norm minimization on both loss function and regularization to realize feature selection across all data points.
• SparseMultinomial Logistic Regression via Bayesian ℓ1 Regularization (SBMLR) [Cawley et al., 2007] which exploits sparsity by using a Laplace prior and is used for multi-class pattern recognition. It can also be applied to feature selection.
• Feature Selection via Spectral Analysis (FSSA) [Zhao and Liu, 2007] which is a semi-supervised feature selection method using spectral regression.
• Multi-class ℓ2,1-norm Support Vector Machine (SVM21) [Cai et al., 2011] which is an ℓ2,1-norm regularized SVM. It is one of the feature selection methods ensembled in the proposed EnFS.
• ℓ2,1-norm Least Square Regression (LSR-21) [Nie et al., 2010] which is an ℓ2,1-norm regularized least square regression. It is another feature selection method ensembled in the proposed EnFS.

In this experiment, we set λ1 and λ2 in Eq. (3) to the same value for all the datasets. Thus, for the proposed EnFS, parameters λ (denotes the same value of λ1 and λ2) and α are tuned. To fairly compare different feature selection algorithms, we tune all the parameters (if any) by a "grid-search" strategy from {10-6 , 10-5 , . . . , 105 , 106}. We set the number of selected features as {10, 20, . . . , 90} for MIML, MFlickr, and SensIT, {20, 40, . . . , 200} for USPS, {100, 200, . . . , 900} for YaleB, and {30, 60, . . . , 300} for Protein. For all the algorithms, we report the best results obtained from different parameters. To investigate the performance of feature selection for the cases when only a few labeled data per class are available, we set the number of labeled data per class to 5 and randomly sample these labeled data to form the training sets. For each dataset, we repeat the sampling for 10 times and report the average results.

In our experiment, each feature selection algorithm is first performed to select features. Then three classifiers, i.e., linear multi-class SVM [Crammer and Singer, 2002], least square regression, and multi-class kNN (k = 1), are performed based on the selected features respectively to investigate the performance of feature selection. For the classifier of least square regression, we learn a threshold from the labeled training data to quantize the continuous label prediction scores to binary. We use Accuracy as evaluation metric in this paper.

4.2 Experimental Results and Discussions

First, we compare the performance of different feature selection algorithms. In Table 2, 3, and 4, We report the comparisons of feature selection algorithms on six datasets using multi-class SVM, least square regression, and multi-class kNN (k = 1) as classifiers, respectively. We can see from the three tables that the classification results of feature selection algorithms are generally better than that of Full Features, except for SBMLR. Moreover, the feature number is reduced by performing feature selection, resulting in the classification much faster. Therefore, it is more efficient. We can also see from these three tables that EnFS algorithm proposed in this paper obtains the best performance. For all these methods, the number of labeled data per class is set to 5. These results demonstrate that the proposed EnFS obtains better performance for the cases when only a few labeled data per class are available. Thirdly, we observe that, except for the USPS and YaleB datasets, the performance of EnFS is conspicuously better than that of SVM-21 and LSR-21. This observation validates that it is effective to add a co-regularization term ||W||2,1 (in Eq. (3)) to share the sparse patterns in W and help to alleviate over-fitting. Finally, we observe that classification using multi-class SVM and kNN achieve better performance than the least square regression. The main reason is, for classification evaluation of least square regression, the threshold learned from the small size of training data (i.e., 5 per class) leads to a bias in the quantization of continuous label prediction scores.

To further investigate the effectiveness of ensemble by the co-regularization term ||W||2,1, we compare the performance of SVM-21, LSR-21, and EnFS, when the numbers of labeled data per class are set to {5, 6, . . . , 10}. The results are plotted in Fig. 1, which are obtained by performing kNN (k = 1) classifier based on the selected features. We can see from Fig. 1 that the performance of EnFS is generally better than that of SVM-21 and LSR-21 for all the numbers of labeled data per class. As the numbers of labeled data per class are small (compared to the sizes of six datasets, see Table 1), the results in Fig. 1 further validates the effectiveness of EnFS in alleviating the problem of over-fitting.

Fig. 2 demonstrates the learned matrix W of MIML dataset using algorithms SVM-21, LSR-21, and EnFS, respectively. Columns represent the classes and rows represent the 128 color coherence features. Firstly, we can observe from Fig. 2 that, when minimizing the ℓ2,1-norm of W, many rows of W shrink to zeros and results in a sparse pattern of feature selection for all classes. Secondly, it is clear in Fig. 2 that SVM-21 and LSR-21 output different sparse patterns of W by training on the same set of labeled data. This disagreement of spars patterns will result in different subsets of selected features. Finally, the results in Fig. 2 demonstrate the ensemble effect of EnFS for SVM-21 and LSR-21 clearly. For example, as the numbers of sparse row in the learned W using SVM-21 and LSR-21 are different, EnFS makes a compromise.

Next, we study the convergence of the proposed EnFS in Algorithm 1. Fig. 3 shows the convergence curves of our EnFS algorithm according to the objective function value in Eq. (3) on all the datasets. The figure shows that the objective function value monotonically decreases until converged by applying the proposed algorithm. It can be seen that our algorithm converges within a few iterations. For example, it takes no more than 10 iterations for MFlickr and YaleB and no more than 20 iterations for MIML, USPS, and SensIT. For Protein, it takes 30 iterations to converge.

5 Conclusion

While supervised feature selection has been well explored in lots of previous works, it is not straightforward to ensemble different classifiers for a better performance of feature selection, especially for the cases when the number of labeled training data is small. As over-fitting may be a potential problem in such a setting, we have proposed a method of co-regularized ensemble for feature selection. The coregularized ℓ2,1-norm can enhance the effect of regularization and uncover common irrelevant features, so as to improve the performance of feature selection in some cases. Ensemble classifiers in the proposed EnFS are trained on the same training set represented in the same feature space, making it different from the multi-task learning methods and existing coregularization algorithms in multi-view learning. To show the ensemble effect of the proposed general framework of EnFS, we ensemble SVM and least square regression to show the performance improvement of feature selection. It is worth noting that, when one of the ensembled classifiers uncovers the irrelevant features, classifier ensemble for feature selection not necessarily improves the performance. That is to say, performance improvement of classifier ensemble for feature selection is data dependant, which will be further explored in the future. EnFS also has an extension ability of incorporating other criteria of classification into the optimization process or define new form of regularization term.

Acknowledgments

This paper was partially supported by the NSFC (under Grant 61202166) and Doctoral Fund of Ministry of Education of China (under Grant 20120032120042).