Clustering-Based Joint Feature Selection for Semantic Attribute Prediction

1 Introduction

Recent literature has witnessed fast development of representations using semantic attributes, whose goal is to bridge the semantic gap between low-level feature representation and high-level semantic understanding of visual objects. Attributes refer to visual properties that help describe visual objects or scenes such as "natural" scenes, "fluffy" dogs, or "formal" shoes. Visual attributes exist across object category boundaries and many methods have been employed in applications including object recognition [Farhadi et al., 2010], face verification [Song et al., 2012], image search [Kovashka et al., 2012; Scheirer et al., 2012] and sentiment analysis [Wang et al., 2015].

⇤The work was supported in part by ONR grant N00014-15-12344 and ARO grant W911NF1410371. Any opinions expressed in this material are those of the authors and do not necessarily reflect the views of ONR or ARO.

Good representations of semantic attributes are often built on top of high-dimensional, low-level features. Attribute learning directly based on such raw, high-dimensional features may suffer from the curse of dimensionality curse. Further, often it is reasonable to assume that not all the low-level features would have equal contribution to all the attributes. Feature selection, selecting a subset of most relevant features for a compact and accurate presentation, is proven to be an effective and efficient way to handle high-dimensional data [Tang et al., 2014].

Multi-task joint feature selection has been introduced by [Chen et al., 2014] for attribute ranking by exploring the correlation among attributes. However, this work assumes that all attributes are correlated by sharing the same subset of features, which is not always accurate. For example, as shown in Figure 1, a "high-heel" shoe is usually considered as a "formal" shoe as well. It is reasonable to assume these attributes share the same subset of features, e.g., shape-related descriptors. However, it is hard to identify whether "high heel" or "formal" shoes are in red, which suggests the attribute "color" may not share the same subset of features with the other attributes but is determined by, e.g., color-related descriptors. In other words, attributes are usually related in clustering structures. [Jayaraman et al., 2014] first explores such clustered relatedness on attribute prediction. However, their approach requires manually specified group structure as prior. To our knowledge, there is still lack of a feature selection approach being able to identify grouping/clusering structures among attributes for improved attribute prediction.

In this paper, we propose a regularization-based multi-task feature selection approach that aims at automatically partitioning the attributes into groups while simultaneously utilizing such group information for attribute-dependent feature selection. We employ a clustering regularizer for attribute partition, where strong attribute relatedness is assumed to exist within each cluster. Besides, a group-sparsity regularizer is imposed on the objective function to encourage intra-cluster feature sharing and inter-cluster feature competition. Under this formulation, we propose an alternating structure optimization algorithm, which efficiently solves the relaxed form of the proposed formulation. We verify the effectiveness and generalization capability of our approach on both synthetic and real-world benchmark datasets. The results show that our approach outperforms the state-of-the-art approaches on feature selection, attribute prediction and zero-shot learning.

2 Methodology

Let F = ¶f1↪ f2↪ ▷ ▷ ▷ ↪ fd♦ be the set of d features and then we can represent a set of n instances by the feature set F as X = [x1↪ x2↪ ▷ ▷ ▷ ↪ xn] 2 Rd⇥n . Let C = ¶c1↪ c2↪ ▷ ▷ ▷ ↪ cm♦ be the set of m attribute labels and Y = [y1↪ y2↪ ▷ ▷ ▷ ↪ yn] 2 ¶0↪ 1♦m⇥n denotes the label matrix where yi 2 Rm(i = 1↪ 2↪ ▷ ▷ ▷ ↪ n) is the label vector of the i-th instance. We aim to select K(Kd) most relevant features from F by leveraging X, Y and the attribute correlation in C. Let s = K

⇡( 0↪ ▷ ▷ ▷ ↪ 0↪ 1↪ ▷ ▷ ▷ ↪ 1), where ⇡(·) is the permutation function and K is the number of features to select where si = 1 indicates that the i-th feature is selected. The original data can be represented as diag(s)X with K selected features where diag(s) is a diagonal matrix. We assume that a linear projection matrix W = [w1↪w2↪ ▷ ▷ ▷ ↪wm] 2 Rd⇥m maps the data X to its label matrix Y where wi 2 Rd is the projection vector for the i-th class ci. If we do not consider attribute correlation, we can select K features via solving the following optimization problem:

d-K z }| { z }| {

where L(·) is the loss function and typical choices of loss functions include least square and logistic regression.

2.1 Modeling Label Correlation

Based on the assumption that correlated attributes would share the same features, we propose to model attribute correlation via learning the clustering structures through k-means. Let E be a permutation partition matrix, then a partition of the projection matrix W into k clusters can be formed as:

where Wi 2 Rd⇥ni (i = 1↪ 2↪ ▷ ▷ ▷ ↪ k) is the i-th partitioned group includes ni projection vectors (or attribute labels). The associated sum-of-squares cost function for the partition can be formulated as

where mi denotes the mean vector of the i-th cluster. Let ei = [1↪ 1↪ ▷ ▷ ▷ ↪ 1]> 2 Rni⇥1 , then Eq. (1) can be derived as

Let F = diag( e1 pn1 ↪ e2 pn2 ↪ ▷ ▷ ▷ ↪ ek pnk ) 2 Rm⇥k be an orthonormal matrix, then Eq. (2) can be rewritten as

To make the problem tractable, we ignore the special structure of F and let it be an arbitrary orthonormal matrix. By adding a global penalty Tr(W >W) measuring how large the weight vectors are, capturing label correlation is to partition W into k clusters, which can be achieved by solving the following optimization problem:

2.2 Feature Selection

With the model component to capture attribute correlation in Eq. (3), the proposed feature selection framework is to solve the following optimization problem:

where β controls the contribution from modeling label correlation and γ controls the generalization performance.

The constraint on s makes Eq. (4) a mixed integer programming problem, which is difficult to solve. We observe that diag(s) and W are in the form of W T diag(s). Since s is a binary vector and d -K rows of the diag(s) are all zeros, W T diag(s) is a matrix where the elements of many rows are all zeros. This motivates us to absorb diag(s) into W as W = W T diag(s), and add `2↪1-norm on each grouped Wi to encourage sparse-based group-wise joint feature selection. With this relaxation, Eq. (4) can be rewritten as:

where ↵ controls the sparsity of W. The key idea lying here is that we use the clustering regularizer to partition the tasks into groups where strong correlation exists among tasks in the same group; and feature selection based on such group structures would make sure appropriate feature subsets are selected to represent the respective semantic attributes.

3 Algorithm

In this section, we first introduce an optimization algorithm to seek an optimal solution (summarized in Algorithm 1) for Eq. (5). Then we propose an approach to estimate the attribute assignment (summarized in Algorithm 2).

3.1 Optimization

The optimization problem in Eq. (5) is non-convex nonsmooth, which makes the formulation difficult to solve in its original form. Thus we adopt several relaxations to make it solvable.

The attribute correlation regularization in Eq. (3) can be rewritten as:

where ⌘ = γ◁β > 0. Let M = FF >, according to [Zhou et al., 2011] the previous regularizer can be relaxed into the following convex form:

where Sm+ is the set of m⇥m positive semidefinite matrices. Following a similar idea in [Bach, 2008], we reformulate Eq. (5) by squaring the `2↪1 norm. Since the `2↪1 norm is positive, the squaring represents a smooth monotonic mapping. Without loss of the generality, we adopt the traditional least square loss for demonstration in this paper. Then we get the following jointly convex smooth objective function regarding to W and M.

Since it is difficult to optimize the linear projection matrix W and attribute correlation matrix M simultaneously, we employ Alternating Structure Optimization (ASO), which has been shown to be effective in many practical applications [Blitzer et al., 2006; Quattoni et al., 2007] and is guaranteed to converge to a global optimal solution.

Optimizing M when fixing W

Given a fixed W, the optimization problem is decoupled into the following optimization problem:

We solve the problem based on the following Lemma due to [Zhou et al., 2011]:

Lemma 1 For the optimization problem in Eq. (8), let W = U⌃V be the singular value decomposition of W where ⌃ = diag([σ1↪ σ2↪ ▷ ▷ ▷ ↪ σm]), M = Q⇤Q> be the Eigen decomposition of M where ⇤ = diag([λ1↪ λ2↪ ▷ ▷ ▷ ↪ λq]) and q be the rank of ⌃. Then the optimal Q⇤ is given by Q⇤ = V and the optimal ⇤⇤ is given by solving the following optimization problem:

Eq. (9) can be solved using the similar technology in [Jacob et al., 2009].

Algorithm 1 Feature Selection Optimization

Input:

1. Multiple attribute data ¶X↪ Y ♦;
2. Parameters ↵, β, k(optional) and the number of selected features K;
3. The initial projection matrix W0;

Procedure:

• 1: Set W =W0;
• 2: repeat
• 3: Update M according to Eq. (8);
• 4: Update r according to Alg. 2;
• 5: Update δ according to Eq. (10);
• 6: Update W according to Eq. (11);
• 7: until Converges
• 8: Sort each feature according to kwi k2 in descending order of each group;
• 9: return The group-wise top-K ranked features;

Algorithm 2 Cluster Assignment Estimation

Input: M; Procedure:

• 1: Approximate F by top-ranked eigenvector of Q;
• 2: Calculate R11↪ R12 by applying QR decomposition with column pivoting on F by Eq. (12);
• 3: Calculate ˆR by Eq. (13);
• 4: calculate r by Eq. (14) for each attribute;
• 5: return Cluster assignment vector r;

Optimizing W When Fixing M

The squared group-wise `2↪1 norm in Eq. (7) is still difficult to derive directly. To alleviate that, we introduce some positive dummy variables δij 2 R+ which satisfies Pi Pj δij = 1. [Argyriou et al., 2008] proves an upper bound of the squared `2↪1 norm in terms of the positive dummy variables

where wi↪j 2 R1⇥m is the row vector of Wi. Thus δij can be updated by holding the equality:

Given a fixed M, each projection vector w can then be updated by optimize the following problem

which can be solved by gradient-type approach.

3.2 Estimating Attribute Assignment

The group-wise feature selection is conducted by the clustering structure of the attribute. However, given the M optimized by the previous algorithm, it is not readily possible to observe the cluster assignment of the attributes because M is spectrally relaxed. In this subsection, we propose an approach to acquire the cluster structure.

We first need to obtain a good approximation of the cluster indicator matrix F . Given M, we first apply Eigen decomposition M = Q⇤Q> where each column of Q is the eigenvector and each diagonal element of ⇤ is the eigenvalue. Then we rank the columns of Q in decreasing order according to its corresponding eigenvalues, and the top-ranked k columns give an approximation of the cluster assignment matrix F. The number of the cluster k can be either manually specified or automatically explored by setting a threshold (10e - 8 in our experiment) regarding to the absolute value of the eigenvalue.

After obtaining F, without loss of generality, we assume the optimized W = [W1↪W2↪ · · · ↪Wk]T where the submatrix Wi includes all attributes belonging to the i-th cluster. Let ti = [ti1↪ ti2↪ ▷ ▷ ▷ ↪ tini ]T denote the largest eigenvector of Wi T Wi, [Zha et al., 2002] showed that F can be reformulated as

where V T = [v1↪ v2↪ · · · ↪ vk] 2 Rk⇥k is an orthogonal matrix.

Since vi is orthogonal to each other, the cluster structure can be acquired by picking up a column of F which has the largest norm as the first cluster, and orthogonalizing the other columns against this column. Then the same process is executed on the rest of columns until all clusters are identified. This process is identical to a QR decomposition with column pivoting on F

where Q 2 Rk⇥k is an orthogonal matrix, R11 2 Rk⇥k is an upper triangular matrix and P 2 Rm⇥m is a permutation matrix. Then we calculate the cluster assignment matrix ˆR 2 Rk⇥m by

where Ik 2 Rk⇥k is an identity matrix. The cluster assignment information can then be inferred from ˆR. The cluster membership of each attribute (column) is determined by the row index of the largest element (in absolute value) of the corresponding column in ˆR. Denote r 2 Rm as the cluster identification vector where ri records which cluster the i-th class belongs to, then r can be calculated by

where ˆ rij is the (i↪ j)-th entry of ˆR.

4 Experiments

In this section, we first verify the effectiveness of our proposed approach on one synthetic dataset. Since the proposed approach can be generalized to general multi-label problem, we evaluate the feature selection capability on various benchmark datasets. At last we evaluate the attribute prediction and zero-shot learning capabilities on image benchmark datasets. All the datasets are standardized to zero-mean and normalized by the standard deviation. For all approaches, the super parameters are selected via cross-validation. We cannot get the number of cluster k without any prior knowledge for realworld, thus we also select k by the prediction accuracy on a small subset of datasets.

4.1 Simulation Study

Since it is difficult to obtain the groundtruth cluster structure for real applications, we first verify the effectiveness of the proposed approach in obtaining the cluster structures on simulated dataset. Following [Jacob et al., 2009; Zhou et al., 2011], we construct the synthetic data containing 5 clusters with 10 learning tasks in each cluster, generating a total number of 50 tasks. For the i-th task, a dataset Xi2Rd⇥n is randomly drawn from a normal distribution N(0↪ 1) for learning, with the dimension d = 30 and the sample size n = 60.

The projection model is constructed as follows. For the ith cluster, we generate a cluster weight vector wci 2Rd drawn from the normal distribution N(0↪ 900). Then 15 dimensions of wci are randomly but carefully selected and assigned to zeros, to ensure all wc are orthogonal to each other. Similarly, for the j-th task belonging to cluster i, we generate a taskspecific weight vector wsj 2Rd drawn from the normal distribution N(0↪ 16) with the same dimensions of wci assigned to zeros. Thus, the ultimate weight vector of the j-th task is the linear combination of the cluster and task-specific weight vector wj = wci + wsj .

The corresponding response yi of the i-th samples xi of task j is then obtained by yi = wTj xi + "i where " is the noise vector drawn from N(0↪ 0▷1). We choose 0▷5 as the threshold to assign binary label to each sample.

We verify the effectiveness of our proposed approach by comparing the learned cluster structure and the selected features with the groundtruth. Based on the prior knowledge implied by the construction of the groundtruth, We set k = 5 and the number of selected features as K = 15. Figure 2 shows one example of the learned projection matrix 2(b) with the comparison of the groundtruth 2(a) where the white part represents zeros and the black part represents non-zeros. The result shows that our approach is able to roughly capture the correct group sparse structures.

4.2 Feature Selection

We verify the feature selection capability on general multilabel datasets in this section. The experiment is conducted on 6 public benchmark feature selection datasets including one object image dataset COIL100 [COI, 1996], one handwritten digit image dataset USPS [Hull, 1994], one spoken letter speech dataset Isolet [Fanty and Cole, 1991], three face image dataset YaleB [Georghiades et al., 2001], ORL [Samaria and Harter, 1994] and PIX10P 1 . The statistics of the datasets are summarized in Table 2. We compare the proposed approach with the following representative feature selection algorithms: Fisher Score [Duda et al., 2001], mRMR [Peng, 2005], Relief-F [Liu and Motoda, 2008], Information Gain [Cover and Thomas, 1991], MTFS [Argyriou et al., 2008].

Following the common way to evaluate supervised feature selection, we assess the quality of selected features in terms of the classification performance [Han et al., 2013; Cai et al., 2013]. The larger classification accuracy is, the better performance the corresponding feature selection approach achieves. In our experiments, we employ linear Support Vector Machine (SVM) and k-nearest neighbors (kNN) classifier with k = 3 for evaluation. How to determine the optimal number of selected features is still an open question for feature selection; hence we vary the number of selected features as ¶10,30, 50 . . . ,90♦ in this work. In each setup 50% samples are randomly selected for training and the remaining is for testing. Specific constrains are imposed to make sure the class labels of the training set are balanced. The whole experiment is conducted 10 rounds and average accuracies are reported.

Figure 1 shows the comparison results for SVM and kNN on the 6 benchmark datasets when 50 features are selected. The result shows that MTFS and the proposed framework outperform Fisher Score, mRMR and Information Gain. The performance gain comes from that Fisher Score, mRMR and Information Gain select features one by one while MTFS and FSMC select features in a batch model. It is consistent with what was suggested in [Tang and Liu, 2012] that it is better to analyze features jointly for feature selection. Besides, in most cases, the proposed framework outperforms MTFS. Better performance gain is usually achieved when fewer number of features are selected. This performance gain suggests that modeling label correlation can significantly improve feature selection performance for multi-class data.

4.3 Attribute Prediction

We then compare our approach with state-of-the-art attribute learning work [Chen et al., 2014] (referred as MTAL) and [Jayaraman et al., 2014] (referred as DSVA). Since MTAL is initially proposed for attribute ranking, we replace the original loss function with the one adopted in this paper for fair comparison. DSVA requires attribute groups as prior, thus we run k-means offline to obtain the clusters for datasets do not have such information.

1 PIX10P

is publicly available from

https://featureselection.asu.edu/datasets.php The experiments are conducted on three benchmark datasets: aYahoo [Farhadi et al., 2009], Animals with Attributes (AwA) [Lampert et al., 2009] and SUN attribute [Patterson and Hays, 2012] and the statistics of the datasets are summarized in Table 4. To obtain a good representation of the high-level attributes, we require that the features can capture both the spatial and context information. Thus, we constructed the features by pooling a variety types of feature histograms including GIST, HoG, SSIM. For aPascal/aYahoo and AwA datasets we use predefined seen/unseen split published with the datasets. For SUN dataset, 60% of categories are randomly split out as "seen" categories in each round with the rest as "unseen" categories. During training 50% of samples are randomly and carefully drawn from each seen categories to ensure the balance of the positive and negative attribute labels. The rest samples from "seen" classes and all samples from "unseen" classes are used for testing.

Table 3 shows the average prediction accuracy of each approach over all attributes by running the experiment 10 rounds. The result shows that for both "seen" and "unseen" categories, DSVA outperforms MTAL in prediction accuracy and our proposed approach further outperforms DSVA by 2%⇠4%. DSVA decorrelates low-correlated attributes compared with MTAL thus achieves better prediction performance. However, the manually specified or off-line learned group structures are not able to achieve the optimal result. Our approach iteratively optimizes the clustering structure and the projection model, which achieves the best performance.

4.4 Zero-shot Learning

We also experiment on the zero-shot learning problem on all three datasets. Zero-shot learning aims to learn a classifier based on training samples from some seen categories, and classify some new samples to a new unseen category. We adopt the Direct Attribute Prediction (DAP) framework proposed in [Lampert et al., 2009] with attribute prediction probability from each approaches as input. Since only continuous image level attribute labels are provided on the SUN dataset, we construct the class level attribute labels by thresholding the average attribute label values of all samples from the class. Same "Seen"∩"Unseen" categories splits are adopted as previous experiments.

The Average classification accuracies of 10 rounds experiment are reported in Table 5. The result shows that on aYahoo and AwA, our approach achieves significant performance gains than the baseline approaches. The large number of categories in SUN dataset make the classification problem very hard which leads to all low performance of all approaches. Our approach still works better than the baseline approaches.

4.5 On Choosing the Parameters

The proposed framework has three important parameters - ↵ controlling the sparsity of W, β controlling the contribution of modeling label correlation and gamma controls the global penalty. We study the effect of each parameter by fixing the other to see how the performance of the proposed approach varies with the number of selected features. Due to the page PIX10P 94.56◦1.91 86.45◦2.22 96.00◦1.81

Table 1: Classification results (ACC%◦std) of different feature slection algorithm on different datasets. (the higher the better).

limitation, we only report the result on the Isolet dataset with SVM but we have similar observations in other datasets.

Figure 3 demonstrates the performance variance w.r.t. different parameters and the number of selected features. With the increase of β, the performance first increases, demonstrating the importance of modeling label correlation, and then decreases. This property is practically useful because we can use this pattern to set β. When ↵ increases, the performance also increases dramatically, which suggests the capability of `2↪1-norm for feature selection. The performance also increases with γ and then decrease, but relatively stable. The best performance is achieved around 0▷1.

5 Conclusions

In this paper, we proposed a clustering-base multi-task joint feature selection framework for semantic attribute prediction. Our approach employs both clustering and group-sparsity regularizers for feature selection. The clustering regularizer partitions the attributes into different groups where strong correlation lies among attributes in the same group while weak correlation exists between groups. The group-sparsity

86.04◦2.04

97.81◦1.54 99.34◦1.22

regularizer encourages intra-group feature-sharing and intergroup feature competition. With an efficient alternating optimization algorithm, the proposed approach is able to obtain a good group structure and select appropriate features to represent semantic attributes. The proposed approach was verified on both synthetic and real-world benchmark datasets with comparison with state-of-the-art approaches. The result shows effective group structure identification capability of our method, as well as its significant performance gains on feature selection, attribute prediction and zero-shot learning.