Multi-label Feature Selection via Global Relevance and Redundancy Optimization

1 Introduction

Multi-label learning deals with examples which may be associated with multiple labels simultaneously. It has attracted significant interests from the research community and has a wide range of applications. For example, in text categorization, a text needs to be tagged with several topics [Schapire and Singer, 2000]; in image annotation, an image needs to be tagged with multiple scenes [Boutell et al., 2004]; in bioinformatics, one wishes to recognize a gene with multiple functions [Elisseeff andWeston, 2001]. Normally, the aforementioned resources (e.g., text, image, and gene) are represented by feature vectors with high dimensionality. The high dimensionality of multi-label data not only leads to the increasing of the computational cost and memory storage requirement, but also limits the usage of machine learning models in real applications [Jian et al., 2016]. Feature selection is proved to be effective for removing irrelevant and redundant features in the feature representation, thus carrying the most discriminative information for multi-label learning [Lee and Kim, 2017; Lin et al., 2016; Wei and Li, 2019; Zhang et al., 2019].

∗ Shaozi Li is the corresponding author.

However, it is unwise to perform feature selection for multi-label learning directly. It means that achieving the purpose in a label-wise effective manner is deemed to be crucial for improving the generalization performance. First, labels in multi-label data are not independent but inherently correlated. For example, an image is likely to be annotated as sky if it has label cloud. Thus, it is necessary to capture label correlation to guide the feature selection process. Second, labels have their own inherent properties (e.g., the issues of the class-imbalance [Krawczyk, 2016], the relative labeling-importance [Li et al., 2015] and label-specific features [Zhang andWu, 2015]), and utilizing these inherent properties is also beneficial for multi-label feature selection.

To tackle the learning problem, a large family of existing algorithms is information theoretical based methods [Vergara and Est´evez, 2014]. Algorithms in this family mainly focus on exploiting feature evaluation criteria, such as feature relevance maximization and feature redundancy minimization [Peng et al., 2005], to access the importance of features. For implementation, they select candidate features one by one with heuristic search, until obtain a size-specific subset of relevant features. Nevertheless, these methods are easily trapped in local optima. Not surprisingly, they may be in trouble to find an optimal feature subset. Furthermore, such heuristic search is time-consuming while ineffective and repetitive calculations are involved in the criteria function.

In order to address the aforementioned problems, we propose a new multi-label feature selection method via global relevance and redundancy optimization, named GRRO. In particular, we present a global optimization method with the goal of considering feature relevance, label relevance (i.e., label correlation), and feature redundancy for feature evaluation. Allowing for achieving the goal efficiently, the proposed method only needs to go through the relevance and redundancy information one time, and can be easily solved for generating the optimal solution. By analyzing discriminative features for each label, we also give an extension of the proposed method to conduct label-specific feature selection. Extensive experiments on twenty multi-label data sets demonstrate the advantages of the proposed method.

2 RelatedWork

Towards information theoretical based methods for multilabel feature selection, one straightforward way for feature evaluation is to maximize the relevance of candidate feature (e.g., f +) with all labels on label set L [Li et al., 2018].

where I(., .) denotes the function for mutual information estimation. In Eq. (1), it describes the decreased uncertainty for f + while labeling information L is given, that is, their shared information. Based on this, some other feature evaluation criteria are proposed, which can be roughly categorized into two groups: Feature redundancy minimization and newly classification information maximization.

Methods in the first group is based on the assumption that good features should be strongly correlated with labels, but not be highly correlated with each other. Thus, the general framework to evaluate f + can be formulated as follow:

where S denotes the selected feature subset, and I(f +, S) denotes the redundant information between f + and S. Lots of methods in the first group focus on modeling feature redundancy to improve the performance. For example, many methods used multivariate mutual information to measure the conditional redundancy under multiple labels [Lee and Kim, 2013; Lin et al., 2015]. Besides, some authors give a concern for computational efficiency. For example, Lee and Kim [Lee and Kim, 2015] proposed a fast multilabel feature selection method by discarding unnecessary calculations and reusing pre-calculated entropy terms. They also proposed a scalable relevance criterion for large label set [Lee and Kim, 2017], which can estimate feature relevance and feature redundancy efficiently.

For the second group, methods in this group are expected to guarantee that the selected feature subset has a strong predictive ability with the smaller redundancy. Specially, the general framework of the methods can be defined as I(f +, L|S), which quantifies the new classification information provided by f + while S is given. For multi-label feature selection, some methods extended the criterion to the classification model [Sechidis et al., 2014], or directly adopted this criterion to achieve the purpose [Bermejo et al., 2018].

By employing the aforementioned criteria, heuristic strategy is widely used to rank features. Another strategy regards the feature selection process as an optimization problem, but the research is still lacking. A few methods tried to obtain the optimized feature weight using the aforementioned criteria [Lim and Kim, 2016; Sun et al., 2019]. However, these methods have the poor ability to exploit labeling information. Moreover, they utilize iterative optimization with the gradient descent strategy to approximate the solution, which may cause the inefficiency for large-scale data analysis.

3 The ProposedMethod

3.1 Preliminaries

We denote matrices with bold uppercase letters (e.g., A), vectors with bold lowercase letters (e.g., a), the (i,j)-th element of A as aij, and the i-th row and column of A as ai. and a.i respectively. The transpose of A is denoted by AT , and the trace of A is denoted by tr(A). Suppose that in the multi-label data set, there are d features, we denote the training data matrix as F = [f.1, f.2, ..., f.d], where f.i (1 ≤ i ≤ d) is the vector which contains the information of feature fi. Then each instance can be denoted by a d-dimensional feature vector. Additionally, each instance is associated with a finite set of q possible labels L = {l1, l2, ..., lq}. Let Y = [y.1 , y.2 , ..., y.q ] be the label matrix, y.j (1 ≤ j ≤ q) contains the ground-truth label information of all training data on label lj. Arbitrary element in Y whose value is 1 indicates that a label is relevant to an instance, otherwise the value is -1.

3.2 Global Relevance and Redundancy Optimization - GRRO

Aimed at seeking relevant features for multi-label feature selection, leveraging information theory to exploit feature evaluation criteria is a popular and effective way. In general, feature selection in this way is with heuristic search, which easily leads to a suboptimal feature subset. In addition, performing feature selection in a label-wise effective manner contributes to multi-label learning, hence the appropriate usage of labeling information (e.g., label correlation) is a crucial step during the feature selection process.

Considering that many feature evaluation criteria are proposed to maximize feature relevance and minimize feature redundancy [Brown et al., 2012] (Eq. (2) shows the general framework), we take the advantage to measure feature importance. Different to the heuristic search, we propose a global learning framework to achieve the purpose with optimization.

where Z ∈ Rd×c denotes the feature coefficient matrix, ziu ∈ Z denotes the importance of feature fi with respect to label lu. I(fi, lu) and I(fi, fj) denote the mutual information of feature fi with label lu and feature fj , respectively. From Eq. (3), we can see that the importance of a feature to a label is positively related to the relevance between the feature and the label (as shown in the first term), which is also limited by the redundancy of the feature with other features (as shown in the second term). Based on this, the importance of all features to each label can be identified by assigning feature weights, i.e., matrix Z. To provide a compact formulation in a quadratic form, Eq. (3) can infer to the following optimization problem.

where C is the matrix which preserves the correlation between features and labels. For arbitrary element cij ∈ C, cij = I(fi, lj). G is the symmetric matrix containing the correlation information of features, whose arbitrary element gij = I(fi, fj).

Next, we learn the global label relevance by exploiting second-order label correlation, thereby improving the generalization performance. According to the feature selection mechanism in Eq. (4), feature selection result for each label is determined by a feature weight vector of Z, such as vector z.u for label lu. For any two labels lu and lj, with the case that the two labels are strongly correlated, their feature selection results (i.e., the corresponding coefficients z.u and z.j) should be similar. Otherwise, the distribution of discriminative features indicated by z.u and z.j should be in difference, hence the newly classification information for label lu and label lj can be protected. To achieve the purpose, a regularizer for matrix Z is defined as follow:

where ruj = 1 - suj, suj denotes the correlation between label lu and label lj. For simplicity, suj is calculated by the Cosine similarity.

Integrating Eq. (4) with Eq. (5), we can obtain the optimization objective function of GRRO. In the light of that ∑qu=1 zT.uGz.u = ∑qu=1 (ZT GZ)uu = tr(ZT GZ) and ∑qu=1 ∑qj=1 rujzT.u z.j = tr(RZT Z), the optimization objective function can be further written as the following form:

where α and β are tradeoff parameters. It can be observed in Eq. (6) that feature coefficient matrix Z is involved in all the terms, which makes the optimized feature selection result affected by the feature relevance, feature redundancy, and label correlation simultaneously.

3.3 Discussions & Practical Issues

Several important issues are discussed to make the proposed GRRO method practical and complete.

We first introduce the solution of GRRO. From Eq. (6), we can see that matrices G and R are positive semidefinite, and ZT GZ ≥ 0 and RZT Z ≥ 0 for any nonzero Z hold. Thus, we can get the solution for Z by setting the derivative of the objective function in Eq. (6) w.r.t. Z to 0, as follow:

Both G and R are symmetric matrices, therefore, we can transform Eq. (7) into the following one:

where I denotes the identity matrix. Eq. (8) is the matrix equation with the form of AZ + ZB = C, where A = I + αG and B = βR. To solve this equation, some existing methods [Wu et al., 2014; Zhang et al., 2019] can be employed to obtain matrix Z. Here, we use the Lyapunov function 1 in Matlab to solve the mathematical problem. After that, the importance of each feature can be obtained based on the value of ||zi.||2 (1 ≤ i ≤ d).

Time complexity. GRRO first calculates the correlation in terms of features and labels, and then uses these calculations to generate the optimal solution for feature selection. In this process, the time cost is dominated by these correlation calculations, which lead to a complexity of O(d2 + q2 + dq). It can be seen that the time complexity is quadratic regarding the number of features d and the number of labels q.

1 https://www.mathworks.com/help/control/ref/lyap.html

Scalability. GRRO achieves multi-label feature selection across all labels while feature selection result for each label is available. By virtue of this property, GRRO is easily scalable for multi-label data understanding. For example, the proposed method enables label correlation exploitation with feature selection results of different labels. Moveover, it is flexible to utilize the inherent properties of multi-label data. In this next section, we consider label-specific features to further enhance the generalization performance.

3.4 Extension to Label-specific Feature Selection

For GRRO, the importance of each feature is determined by summing the weights of the feature to all labels. In the light of that different labels have their own inherent characteristics for distinguishing each other [Zhang andWu, 2015], a more reasonable manner is that selected features should be labelspecific. Following the principle, we extend GRRO with label-specific features, and call the extension as GRRO-LS.

Specially, the global optimization result, i.e., matrix Z generated by Eq. (6), is utilized as the priori knowledge to exploit label-specific feature selection locally. Considering that feature selection result for each label is available by employing matrix Z, label-specific feature learning can be modeled by a search on discriminative features for each label. Formally, for arbitrary label lu (1 ≤ u ≤ q), we define Tu as the index set to preserve the location of its label-specific features, which satisfies:max

From Eq. (9), we can see that index set Tu indicates the k features with the larger weight based on z.u, and these features are specified as the label-specific features with respect to label lu. As the index sets of all labels are found out, we construct a new feature coefficient matrix Znew ∈ Rd×c . For arbitrary element znew iu ∈ Znew , it is defined as follow:

Note that the generated Znew only contains the weight information of label-specific features. Then we estimate the importance of each feature by the value of ||znew i. ||2 (1 ≤ i ≤ d), thus achieving label-specific feature selection.

4 Experiments

4.1 Experimental Setup

Data sets. A total of twenty benchmarkmulti-label data sets are employed in the experiment 2 . Table 1 summarizes detailed characteristics of these data sets, which are mainly from the domains including text, multimedia, and biology. We use the same train/test splits of these data sets to report and compare the results.

Evaluation metrics. Six widely used multi-label evaluation metrics are employed for performance evaluation, including two label-based metrics macro-F1 and micro-F1, and four example-based metrics Hamming loss, ranking loss, coverage, and average precision. Concrete metric definitions can be found in [Wu and Zhou, 2017]. These metrics can evaluate the performance of multi-label algorithms from various aspects. For macro-F1, micro-F1 and average precision, the larger the values the better the performance. For the other metrics, the smaller the values the better the performance.

Comparing algorithms. Five multi-label feature selection methods are selected to compare. All of them are information theoretical based methods, including four heuristic methods PMU [Lee and Kim, 2013], MDMR [Lin et al., 2015], FIMF [Lee and Kim, 2015], and SCLS [Lee and Kim, 2017], and one optimization method MICO [Sun et al., 2019].

2 Public available at http://www.uco.es/kdis/mllresources/

Hyper-parameters. For the proposed method, both of α and β are searched in {10-3 , 10-2 , ..., 103 }, and k is searched in {5, 10, ..., 50}. The parameter of each comparing method (if any) is set as the corresponding reference suggested. ML-KNN [Zhang and Zhou, 2007] (with the default setting) is used as the classifier for performance evaluation. For the parameter-tuning, we adopt a grid-search strategy to seek the optimal parameter, which is determined by making the average classification result (ACR) on test data smallest. Here, we define the formula for the ACR as follow:

where para denotes the collection of algorithm parameter(s), U is the test set, and f denotes the classifier, i.e., ML-KNN. HLi(f, U) and RLi(f, U) output the result of Hamming loss and ranking loss respectively while selecting top-i features.

Computational device. Experiments are performed on a PC with an Intel i7-7700K 4.20GHz CPU and 32GB RAM.

4.2 Performance Evaluation

To evaluate the performance, we focus on top-50 features selected by each method, and the average result with 50 groups of feature subsets 3 is recorded to make a comparison. Due to space limit, we only present the average result of each method on macro-F1 and micro-F1 in this paper (as shown in Table 2), and the details on the other metrics are available on the web 4 . From Table 2, we have a couple of observations. (1) Compared with the selected comparing methods, GRRO and GRRO-LS achieve better performance on 11 and 14 out of 20 data sets with respect to macro-F1 respectively, while on micro-F1, both of them can win on 16 out of 20 data sets. (2) On all the 20 data sets, GRRO-LS is superior to GRRO on 13 data sets regarding macro-F1, 15 data sets regarding microF1. This suggests that exploiting label specific features is conducive to the performance improvement. (3) These comparing methods achieve the best performance on up to 2 out of 20 data sets. Thus, we conclude that the proposed method is effective for multi-label feature selection, and has the advantages compared with some other well-established methods.

3 The first group is composed of the top-1 feature, the second one is composed of the top-2 features, and so on.

To further analyze the performance among all the methods, Friedman test [Demsar, 2006] is used as the favorable statistical significance test for the method comparison on the 20 data sets. Table 3 illustrates the Friedman statistic FF and the corresponding critical value on each metric, and we can see that the null hypothesis, which follows the principle that all the methods have equal performance, is clearly rejected in terms of each metric at significance level α = 0.05. Thus, the posthoc Nemenyi test [Demsar, 2006] is utilized to complete the performance analysis. Here, GRRO or GRRO-LS is regarded as the control method respectively whose average rank difference against the comparing method is calibrated with the critical difference (CD). Accordingly, GRRO or GRRO-LS is deemed to have significantly different performance to one comparing method if their average ranks differ by at least one CD (CD = 2.0146 in this paper).

Fig. 1 shows the CD diagrams [Demsar, 2006] w.r.t. each metric. Specially, any comparing method whose average rank is within one CD to that of GRRO or GRRO-LS is connected. Otherwise, the method, which is not connected with GRRO or GRRO-LS, is considered to have the significant different performance with the control method. From Fig. 1, we can see that GRRO-LS and GRRO rank 1st and 2nd respectively among all the methods, which have no significant difference on all the metrics, and significantly perform better than PMU, FIMF, and MDMR. Compared with MICO, GRRO-LS

4 https://jiazhang-ml.pub/Supplement-GRRO.pdf

has significantly better performance on ranking loss, coverage, and macro-F1, which also significantly outperforms SCLS on Hamming loss and micro-F1. Thus, the proposed method (namely GRRO-LS) can achieve highly competitive performance against the selected comparing methods.

4.3 Influence of Selected Features

In this section, an experiment is conducted on the Medical date set to learn the influence of selected features.

The experimental result is shown in Fig. 2, in which the performance on each metric is figured out by varying the number of selected features. From Fig. 2, we observe: With the increasing of the number of selected features, the performance of all the methods first has a significant improvement, and then keeps stable or even degrades. It can be seen that feature selection benefits to the performance.

4.4 Running Time Comparison

Table 4 shows the timing results (in second) on multi-label feature selection. According to Table 4, we can observe that the proposed method performs the best in terms of average ranking (Ave. Rank.). To be specific, GRRO is obviously superior to PMU and MDMR. FIMF avoids ineffective and repetitive calculations to improve the computation efficiency, hence GRRO is slower than FIMF on some data sets. However, FIMF is less efficient than GRRO on large-scale data analysis, such as Bibtex, Corel16k001, and Corel16k002. SCLS designs feature evaluation criteria to handle large label sets. We can see from Table 4 that GRRO can achieve superior or at least comparable performance on such data sets against SCLS, such as Bibtex and Corel5k, and GRRO also achieves statistically superior to SCLS on most of the other data sets. Similar with GRRO, MICO adopts an optimization strategy to conduct multi-label feature selection, but it has a low convergence rate with iterative optimization. Thus, GRRO is more computationally efficient than MICO. Remark: GRRO-LS and GRRO have the similar result on running time.

4.5 Parameter Analysis

Our method includes three parameters: α and β are to reflect the influence of feature redundancy and label correlation respectively, and k is the number of label-specific features. We analyze these parameters on the Medical data set, and show the experimental result in Fig. 3. Fig. 3(a) shows the average classification result (ACR), which is calculated by Eq. (11), when different pairs of α and β are employed. From Fig. 3(a), we observe that ACR is going to change dramatically in some cases. Thus, the proposed method is sensitive to α and β. Fig. 3(b) shows the influence of parameter k, and it reflects that the performance is going to deteriorate while k becomes large, and the optimal result is obtained while k = 5. A similar phenomenon occurs on most of other data sets, as listed in Table 5. This suggests that generally a small value of k (e.g., k = 5) helps to the label-specific feature selection.

5 Conclusion

In this paper, we developed information theoretical based methods for multi-label feature selection. Our main contribution is to propose a general global optimization framework incorporating feature relevance, feature redundancy, and label correlation. In addition to label correlation exploitation, the proposed method is capable for exploiting the other properties of multi-label learning to further improve the performance, such as label-specific features. Experiments on twenty benchmark data sets in terms of six evaluation metrics showed that the proposed method can significantly improve the performance with feature selection.

In future work, we have interest in further study of labeling information exploitation considering the issues of the classimbalance and the relative labeling-importance, and will also pay attention to the analysis of genetic data with high dimensionality, such as the application on autism spectrum disorder.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (No. 61876159, No. 61806172, No. 61572409, No. U1705286, No. 61571188, No. 61772211 & No. U1811263), the National Key Research and Development Program of China (No.2018YFC0831402), Fujian Province 2011 Collaborative Innovation Center of TCM Health Management, Collaborative Innovation Center of Chinese Oolong Tea Industry-Collaborative Innovation Center (2011) of Fujian Province.