Hierarchical Feature Selection with Recursive Regularization

1 Introduction

In the big data era, we are often confronted with classification tasks involving hundreds of classes, where there is a hierarchical structure among the classes. We call this kind of task hierarchical classification. Many real-world classification problems can be naturally cast as hierarchical classification [Silla and Freitas, 2011]. For example, ImageNet [Deng et al., 2009] is an image database organized according to the WordNet [Miller, 1995] hierarchy. These tasks become challenging when the number of classes is very large and testing against every possible class may become computationally infeasible [Bengio et al., 2010]. The hierarchical class structure is important side information for classification learning. Growing attention has been given to structured or hierarchical classification learning in recent years. Learning algorithms that exploit hierarchies have been developed for activities including lung disease classification, text categorization, visual categorization, gene function prediction, and plant species identification [Gopal and Yang, 2015].

� (Corresponding author: Qinghua Hu).

With the growth of big data, feature selection [Tang and Liu, 2014; Villela et al., 2015; Wang and Guo, 2017] has received much attention in machine learning. It aims to select a subset of features from the original data to obtain a compact representation of the classification task [Yang et al., 2011]. These feature selection algorithms assume that the classes are independent of each other. In addition, they search for a single feature subset to generate a classifier. However, it is known that some features are useful for distinguishing some classes, but useless for others [Freeman et al., 2013]. Thus we should select di�erent features for di�erent subtasks to construct an appropriate feature subset that leads to a compact and e�ective classification model.

Obviously, hierarchical class information is not only beneficial for training hierarchical classification models, but is also helpful for selecting a feature subset for each node. However, little work has been devoted to this problem. In hierarchical feature selection, we divide a large-scale classification task into a set of smaller classification problems, where each subtask uses an independent feature subset [Freeman et al., 2013]. Freeman et al. [Freeman et al., 2011] developed a method for joint feature selection and hierarchical classifier design using genetic algorithms. Song et al. [Song et al., 2015] then proposed a feature selection algorithm for hierarchical text classification. However, they did not consider the dependence between di�erent classes in the hierarchical tree, and independently selected features for each node. Classes in a hierarchical structure have both parent-children relationships and sibling relationships. Classes with a parentchildren relationship are similar to each other and may share common features for classification, while distinguishing between classes with a sibling relationship may require di�erent features. However, these algorithms evaluate the importance of features individually.

In this paper, we design a hierarchical feature selection method based on recursive regularization. This algorithm considers the hierarchical information of the class structure. First, we model the hierarchical information for parentchildren class relationship as a hierarchical regularization. We then use the Hilbert-Schmidt Independence Criterion (H- SIC) [Gretton et al., 2005] to measure the independence of the sibling classes, and penalize the dependence between the features selected at sibling nodes. Thus the final subsets are similar if the nodes have a parent-children relationship, while they are di�erent if there is sibling relationship. The contributions of this paper are summarized as follows.

• � We first attempt to conduct hierarchical feature selection by considering the hierarchical class structure of parentchildren and sibling relationships. These relationships are modeled by hierarchical recursive regularization, which is more reasonable for representing the relationships between nodes than flat approaches.
• � In contrast to existing flat algorithms, we model hierarchical feature selection as a convex objective function and explore an alternation minimization strategy to solve the optimization problem with guaranteed convergence.
• � Extensive experiments on six hierarchical datasets demonstrate the e�ectiveness of our approach in terms of e�ciency and accuracy.

2 The ProposedModel

In this section, we describe the hierarchical feature selection model with recursive regularization for tasks with hierarchical tree structure.

2.1 Hierarchical Tree Structure

A hierarchical tree is defined as a pair (D,�), where D = f1; 2; � � � g is the set of all classes and "�" represents the "ISA" relationship, which is the subclass-of relationship with the following properties [Kosmopoulos et al., 2015]:

1. Asymmetry: if i � j then j � i for every i; j 2 D.
2. Anti-reflexivity: i � i for every i 2 D.
3. Transitivity: if i � j and j � k, then i � k for every i; j; k 2 D.

In a hierarchical tree structure,

1. pi is the parent of node i 2 D;
2. S i is the set of all siblings of node i 2 D, and jS ij is the number of the siblings of i;
3. Ci is the set of all children of node i 2 D, and jCij is the number of the children of i.

Table 1 describes the most frequent symbols used throughout this paper.

2.2 Model

Let Xi 2 R mi�n be a data matrix, where mi is the number of the samples in subtree of node i, and n is the numbers of features. We use x1; x2; � � � ; xmi to represent the mi samples, xi 2 R n and Xi = [x1; x2; � � � ; xmi ]. Let Yi 2 R mi�dmax be a class matrix, where dmax is the largest number of sub-classes. We use yi 2 f0; 1g dmax to represent the class of sample yi, and Yi = [y1; y2; � � � ; ymi ].

Let k � kF denote the Frobenius norm of a matrix, and let k � k2;1 denote the '2;1-norm of a matrix. In the context of hierarchies, the primary optimization problem is estimating the parameters Wi at each node:

whereWi 2 R n�d is the feature weight matrix, the first term is the loss item, the second term is the regularization imposed on Wi, � is a positive constant, and N is the number of internal nodes.

Example 1 An example of a hierarchical class tree structure is shown in Figure 1. From this figure, we have

1. The parent category of class 1 is p1 = 0;
2. The set of child categories of class 0 is C0 = f1; 2g;
3. The set of sibling categories of class 3 is S 3 = f4g.

Hierarchical feature selection should compute the feature weight matrixWi for each node besides leaf nodes.

In the hierarchical class structure, there are parent-children relationship and sibling relationship. We impose these two kinds of relationship as regularization terms on W to select features.

Classes have a parent-children relationship means that they are neighboring nodes among all hierarchical classes. We expect that they are similar to each other and should share common features for classification. We first introduce this relationship in the hierarchy into the learning process by incorporating a recursive structure into the regularization term. The regularization term of parent-children relationship is

In addition, we expect the features at di�erent sibling nodes to be di�erent from each other. For example, the textural features can identify animals, but the edge features are representative for furniture. We measure the independence using a kernel dependence measure (the HSIC) by mapping variables into a reproducing kernel Hilbert space (RKHS). This criterion measures the high-order joint moments between the original distributions [Bach and Jordan, 2002]. We use the HSIC to penalize the dependence between the selected features at sibling nodes in an RKHS.

Let Ki and Kl be kernel spaces on Wi 2 R n�d and Wl 2 R n�d , where l 2 S i is the l-th sibling node of node i, and Wi andWl are the representation coe�cient matrices for the i-th node and the l-th node, respectively. Then

where Ki = WiW T i , Kl = WlW T l , and 1 � l � jS ij. H = I� 1 n 1n1 T n 2 R n�n centers the matrix to have zero mean, where 1n 2 R n is a column vector with all elements being 1.

In the context of hierarchies, the primary optimization problem considering the parent-children and sibling relationships is formulated as

where i = 0 indicates a root node with no parent node or sibling nodes. Therefore, the value of i in the two regularization terms starts at 1. We call this task hierarchical feature selection with recursive regularization (HiFSRR).

2.3 Optimization of HiFSRR

Because of the non-smoothness of the '2;1-norm, it is di�- cult to derive a closed solution to the optimization problem in Eq. (4) directly. According to [Nie et al., 2010], this problem can be solved in an alternative way. When wi , 0 for i = 1; � � � ; d, the derivative of jjWjj2;1 with respect toW is

where D 2 R d�d is a diagonal matrix with the i-th diagonal element as Dj j = 1 2jjwj jj2 . It can be easily verified that the derivative in Eq. (5) can also be regarded as the derivative of Tr(W T DW). Thus, the optimization problem is written as

The root node should be computed individually. Therefore, Algorithm 1 Hierarchical Feature Selection with Recursive Regularization (HiFSRR)

Input: Input data Xi 2 R mi�n and labels Yi 2 f0; 1g mi�dmax , where i = 0; 1; � � � ; N, and N is the number of internal nodes. To facilitate the calculation, we let dmax be the maximum number of classes of internal nodes. Regularization parameters �, �, and �.

Output: Matrix W 2 R n�dmax (N+1) .

• 1: Set t = 0 and initializeWi 2 R n�dmax randomly;
• 2: W= [W0;W1; � � � ;WN];
• 3: repeat
• 4: for i = 0 : N do
• 5: Compute the diagonal matrix D (t) i according to d i j j = 1 2kw i j k2 ;
• 6: end for

// Update the root node.

• 7: Update W0 by W (t+1) 0 = (X T 0 X0 + �D (t) 0 + �jC0jI) �1 (X T 0 Y0 + � P i2C0 W (t) i ); // Update the internal nodes.
• 8: for i = 1 : N do
• 9: Update Wi by W (t+1) i = (X T i Xi + �D (t) i + �I + � P l2S i (Ul + U T l )) �1 (X T i Yi + �W (t) pi );
• 10: end for
• 11: UpdateW (t+1) = [W0;W1; � � � ;WN];
• 12: t = t + 1;
• 13: until Convergence criterion satisfied;
• 14: returnW;

the objective function is rewritten as

For the root of the tree, by setting the derivative of Eq. (7) w.r.t. W0 to 0, we have

where i is the i-th child of root node C0, and jC0j is the number of all children of root node. Therefore, we have

Let Ul = HWlW T l H. By setting the derivative of Eq. (7) w.r.t. internal nodeWi to 0, we have

Finally, we have

The HiFSRR algorithm is formulated in Algorithm 1. With this algorithm, the weight vector W = [W0;W1; � � � ;WN] is obtained. We sort the n features for the i-th node according to jjwi jjjF( j = 1; � � � ; n) in the descending order and select the top ranked subsets at this node, where i = 0; � � � ; N and N is the number of internal nodes.

2.4 Convergence Analysis

Algorithm 1 monotonically decreases the value of the objective function for the problem in Eq. (6) in each iteration, and converges to the global optimum of the problem. The '2;1norm minimization problem has been studied and the convergence has been proved in [Nie et al., 2010]. The following experiments also show that the proposed algorithm converges quickly on Cifar and SUN datasets. We find the same phenomenon on other datasets.

Figure 2 shows the convergence curves of all the datasets, which shows that the objective function value decreases monotonically and converges within no more than ten iterations for all datasets.

3 Experiments

In this section, we introduce the datasets used in our experiments. We then analyze the parameter sensitivity and report e�ectiveness of regularization terms. Finally, we compare the proposed algorithm with some state of the art techniques.

3.1 Datasets

The experiments use protein and image datasets to test the proposed algorithm. All these tasks have the information of class hierarchy. Two protein tasks include: F194 [Wei et al., 2015] and DD [Ding and Dubchak, 2001]. Four image tasks include: CLEF [Dimitrovski et al., 2011], CIFAR100 [Krizhevsky and Hinton, 2009], PASCAL Visual Object Classes (VOC) [Everingham et al., 2010], and Scene UNderstanding (SUN) [Xiao et al., 2010]. There are multi-label objects in the SUN dataset. As we do not discuss this kind of tasks in this work, we remove these multi-label samples. A description of the datasets is given in Table 2.

3.2 ComparisonMethods

So far, little research has been devoted to developing feature selection algorithms for hierarchical classification. In [Freeman et al., 2011], only two toy hierarchical datasets were presented. In [Song et al., 2015], the algorithm was designed specifically for hierarchical text datasets. Therefore, we compare HiFSRR with the following flat feature selection algorithms.

1. Fisher Score: which depends on fully labeled training data to select features with the best discriminating ability [Duda et al., 2012].
2. FSNM: Feature Selection via Joint '2;1-norms Minimization [Nie et al., 2010] which employs joint '2;1-norm minimization on both loss function and regularization to realize feature selection across all data points.
3. mRMR: Minimal-redundancy-maximal-relevance criterion (mRMR) is an e�ective feature selection scheme which avoids the di�cult multivariate density estimation in maximizing dependency [Peng et al., 2005].
4. Relief: Relief is a classical feature selection algorithm inspired by instance-based learning [Kira and Rendell, 1992].

3.3 Parameter Setting

Features are selected individually for each internal class node by using the parent-children and sibling relationships simultaneously. For example, Figure 3 shows the class hierarchical tree for the VOC dataset. We select a feature subset for the nodes Objects, Vehicles, Household, and Animals. We select features on training sets and test them on test sets using 10fold cross validation. We report the average accuracy of SVM at internal nodes.

In the experiments, we set � = 1, � = 1, and � = 1 for the CLEF dataset, and set � = 10, � = 0:1, and � = 0:1 for the other datasets. We set the number of selected features to be f48, 40, 32, 24g for F194 and DD datasets. We set the number of selected features to be f400, 300, 200, 100g and f200, 160, 120, 80, 40g for the VOC and SUN datasets, respectively. We set the number of selected features to be f256, 205, 154, 103, 52g for the Cifar dataset which are 50%, 40%, 30%, 20%, and 10% of the features.

We analyze the parameter sensitivity, as shown in Figure 4. We fix the value of one parameter (with 1) and tune the others. Due to the space limit, we report the results on Vehicles node of VOC dataset with fixed � and �, respectively. The results show that our method is not sensitive to parameters.

3.4 E�ectiveness of Regularization Terms

We investigate experimentally the performance of regularization terms in our HiFSRR. We compare the e�ectiveness of HiFSRR with two parameter settings using di�erent datasets.

(1) � = 1 and � = 1 mean that HiFSRR with hierarchical relationships.

(2) � = 0 and � = 0 mean that HiFSRR without hierarchical relationships.

Figure 5 shows the average accuracy of SVM on each node of a dataset. The results demonstrate that the regularization terms of parent-children and sibling relationships work well with di�erent numbers of selected features. The advantage of two regularization terms is most obvious when small features are selected.

3.5 Experimental Results and Discussion

First, we compare the e�ciency of the four flat feature selection algorithms and the HiFSRR algorithm according to running time. We then compare the performance of di�erent algorithms that are dominated by SVM. Finally, we use two large datasets, Cifar and SUN, to test the performance of our method on large datasets.

All experiments are executed on an Intel Core i7-3770 running at 3.40 GHz with 12.0 GB memory and 64-bit Windows 7 operating system. The results presented in Table 3 demonstrate that the HiFSRR algorithm has a significantly shorter running time than the other algorithms except for the Fisher algorithm. Neither FSNM nor Relief can process the Cifar and SUN datasets with running out of memory.

We compare HiFSRR with the four flat feature selection algorithms on two protein datasets and two image datasets.

Results on protein datasets. Comparisons of the feature selection algorithms for the F194 and DD datasets are shown in Table 4. We select a feature subset for each internal node of the class hierarchical tree. The results in Table 4 give the average accuracy at each internal node using SVM. It is clear that, in most cases, HiFSRR performs better than other approaches given a di�erent number features, especially when small feature subsets are selected. For example, the classification of the DD dataset with 24 features achieves good accuracy.

Results on CLEF dataset. A comparison of the feature selection algorithms for the CLEF dataset is shown in Table 5. The results demonstrate that the classification results for di�erent internal nodes using the HiFSRR algorithm with 40 features are generally better than those using the flat feature selection algorithms except for Relief.

Results on VOC dataset. The experimental results on VOC dataset are shown in Figure 6. We can see from Figure 6 that the classification results for di�erent internal nodes using the HiFSRR algorithm are in general better than those using the flat feature selection algorithms. The advantage of our algorithm is most obvious when 100 features are selected.

Results on large datasets. Finally, we test our algorithm on two large datasets. Tables 6(a) and 6(b) compare the results of the performance of the HiFSRR algorithm with the Fisher algorithm and mRMR on the Cifar and SUN datasets, respectively. The results demonstrate that HiFSRR algorithm obtains superior performance in di�erent feature subsets.

Moreover, the number of features is significantly reduced by HiFSRR, leading to much faster classification, especially for large datasets.

4 Conclusions and FutureWork

We have proposed a hierarchical feature selection approach based on recursive regularization to exploiting the parentchildren and sibling relationships of hierarchical class struc-

Table 6: Accuracy of SVM on two large datasets with di�erent numbers of selected features.

(b) SUN

tures. In contrast to existing feature selection approaches, we take advantage of the hierarchical class structure, which provides significant information for classification learning. We have also provided an e�cient HiFSRR algorithm to select di�erent feature subsets for each node in a hierarchical tree structure. Compared with the flat feature selection approach, HiFSRR achieves competitive results for both classification accuracy and computational e�ciency. The current implementation of the algorithm only deals with a tree structure for class labels in which case each node (class) has a single parent. In the future, we will design feature selection approaches for graph structures which is more general than tree structure.

Acknowledgments

This work was supported by the National Program on Key Basic Research Project under Grant 2013CB329304, and the National Natural Science Foundation of China under Grant Nos. 61432011, U1435212, 61502332, and 61379049.