Adaptive Graph Guided Embedding for Multi-label Annotation

1 Introduction

In the real-world scenarios, each individual object could contain tens or hundreds of semantic descriptions, such as colors, materials and shapes. Different from single-label learning, multi-label learning assigns multiple labels for each sample [Liu et al., 2017], which is much more challenging compared with single-label scenario. First, the relevant datasets [Lampert et al., 2009; Patterson and Hays, 2012; Wah et al., 2011] are small due to high labeling cost. Second, the labels follow a long-tailed distribution, that means some labels show up more frequently than others. The situation makes label recovery dominated by the major labels, and it might hurt the label recovery performance. Third, labels such as stressful, cold and warm are subjectively assigned, and different people hold different standards, and thus the noise and outliers significantly appear in datasets compared with single label scenario.

Although the number of well-labeled data is limited, related unlabeled data are widely accessible. Thus, it is practical to utilize unlabeled samples to improve the learning performance. Consequently, semi-supervised learning [Zhu et al., 2003] especially graph-based approach [Zha et al., 2009] has attracted great attention. However, they still have limitations that these methods highly depend on the preconstructed graph but rarely optimize it online. In addition, most methods construct graph directly on feature space, which is sensitive to noise and outliers. Several work utilize adaptive graphs to handle the problem [Nie et al., 2012; 2016]. However, these methods mainly focus on single-label classification instead of multi-label scenario.

To this end, we propose a novel Adaptive Graph Guided Embedding (AG2E) for multi-label learning in semisupervised fashion. Figure 1 shows the framework of AG2E, whose core idea is learning a semi-supervised label propagation and an effective embedding simultaneously to seek a latent space, and thus unlabeled images can be well recovered. Our main contributions are summarized as follows:

• We seek an adaptive graph to automatically capture the latent structure of the data. Moreover, a pre-defined

locality-constrained graph is also utilized to preserve the intrinsic structure and guide the adaptive graph learning.

• A linear projection is jointly learned to obtain more effective and distinctive feature representations for better label propagation. It enhances the accuracy and robustness of our approach.
• Non-trivially, we propose an efficient optimization strategy to solve the model. Experimental results on five benchmarks demonstrate the effectiveness and the efficiency of our model.

2 RelatedWorks

Related work including Multi-label learning and Semisupervised learning are introduced in this section.

Multi-label learning learns patterns, which compose instances associating with multiple labels. It widely exists in real-world applications, such as visual annotation [Boutell et al., 2004] and image retrieval [Liu et al., 2018]. It is challenging since the possible label sets number is tremendous. The intuitive solution is to consider the task as several singlelabel problems. [Boutell et al., 2004] learns several classifiers responding for each label. However, since latent connections exist between labels, ignoring the connections would limit the learning performances. [Godbole and Sarawagi, 2004] proposes to leverage the correlations across labels by adding a contextual fusion step. [Liu and Tsang, 2015] explores metric learning paradigm to improve accuracy. However, most methods are in supervised learning scenario. Obtaining sufficient labeled data to achieve acceptable performance is costing which limits their practical applications.

Semi-supervised learning achieves well-trained models by using a few labeled data as well as a large number of unlabeled data. A comprehensive survey can be found in [Zhu, 2005]. Graph-based methods achieve high performance by constructing an affiliate graph to recover labels. [Zhu et al., 2003] proposes Gaussian random fields and harmonic function to obtain semi-supervised learning. [Sindhwani and Belkin, 2005] gives a semi-supervised kernel that is not limited to unlabeled points, but defined over all input spaces. [Nie et al., 2012] actively selects training sets to make the model be independent to initialization process. [Wang et al., 2018] aims to transfer well-label source video information to boost clustering performance on unlabeled target domain. However, these methods are highly depended on the pre-defined affiliate graph. It is difficult and tedious to tune the graph to an optimized structure. Moreover, real-world datasets always contain noise and outliers, which could impair the final performance. [Liu et al., 2006] designs a new scheme to generate an adaptive similarity graph. [Nie et al., 2016] proposes a graph optimization strategy on unsupervised feature selection scenario. [Nie et al., 2017] designs an optimal graph in clustering and classification settings. However, the graphs are optimized in unsupervised manner, which is hard to involve supervision information to enhance the learning performance. Moreover, it is still purely based on the similarity measurement in feature space, which is easily affected by noise and outliers.

Different from previous work, we deploy an adaptive graph for semi-supervised multi-label learning. Specifically, adaptive graph is more flexible to capture the intrinsic data structure and accurately predict the labels. Meanwhile, an effective embedding is jointly learned to align the different distribution data in a low-dimensional but distinctive common space.

3 The Proposed Approach

3.1 Notations

Assume we have labeled data Xl and Yl. Xl ∈ Rd×nl is the labeled feature matrix, where each column xi is an instance, nl is the sample number, d is the feature dimension. Yl ∈ Rdl×nl is the label matrix, where dl denotes the label dimension. Xu ∈ Rd×nu represents unlabeled feature matrix, where nu is the instance number. Our approach aims to utilize Xl, Yl, and Xu to jointly seek an effective transformation for better feature extraction and recover the multiple labels of Xu.

3.2 AG2E Approach

AG2E approach enlarges the multi-label distribution by utilizing the labeled data to the unlabeled data through an adaptive graph. Previous methods usually achieve label propagation based on pre-defined adjacency matrix [Guo et al., 2016]. This strategy assumes samples which are close in feature space shall share the similar labels. The objective function is shown below:

where fi and fj are the corresponding labels of i-th and j-th instances. F = [Fl, Fu], where Fl ∈ Rdl×nl , Fu ∈ Rdl×nu are the recovered label matrices of Xl and Xu. We set Fl = Yl since Fl is expected to be the same as the ground truth Yl. S ∈ Rn×n is the similarity matrix, where n = nl + nu. Each entry sij is the similarity metric between feature points xi and xj . Several methods are proposed to obtain S such as [Ng et al., 2001; Ding and Fu, 2014; Wang et al., 2018], with the definition as follows:

where NK(xi) denotes the K-nearest neighbors of xi. And 1 ≤ (i, j) ≤ n. The quality of S affects learning performance significantly. If S is obtained directly in feature space, it is challenging for S to reveal the intrinsic structure within the data since the noise and outliers are high. To this end, we propose an adaptive graph instead of a fixed graph. Our approach obtains the similarity matrix and simultaneously recovers the labels to achieve the best results. Compared with fixed graph, adaptive graph could be more robust and accurate. We extend Eq. (1) and utilize label correlation information to learn an adaptive graph in learning process. The objective function is shown as below:

where ‖xi - xj‖22 sij constrains the graph optimization that similar features correspond to high similarities and vice versa. µ is a trade-off parameter to balance weights between feature space and label space. F and S are optimized simultaneously.

However, directly learning S in feature space would involve errors due to high-level noise and label outliers. Therefore, we jointly seek a linear projection P ∈ Rr×d to project original features into a low-dimensional common space, where r regulates the space dimension [Ding and Fu, 2014]. By this way, the graph quality would be improved, which would help the label recovery performance. The expression is below:

where tr(·) indicates the trace of a matrix. LS is graph Laplacian matrix [Merris, 1994], where LS = DS - S+S⊤ 2 . And DS ∈ Rn×n is a diagonal matrix and each element DSii = ∑j sij+sji 2 . µ is the trade-off parameter. Simply learning S cannot obtain clear local structure information of the data. Thus, we propose to further utilize a pre-defined graph ¯ S associating with a structure regularizer to pull S be close to ¯ S. By this strategy, our model can obtain the detailed locality structure from ¯ S and still learn an accurate and robust graph S at the same time. Moreover, ¯ S guides the optimization process which could reduce the computational cost. The objective function is below:

Eq. (5) contains a simple solution that only the points of nearest data are assigned as 1 which could eliminate the learning performance. Thus, we further supplement constraints. First, S1 = 1, where 1 is a all-one vector. It means that the sum of S entries in each row is 1. Second, PXHX⊤P ⊤ = I (I is an identity matrix), and it implies and introduces additional data discriminating ability into our model. Third, H = I - 1n I where I ∈ Rn×n is all-one matrix. Then, the objective function can be written as follow:

3.3 Optimization

Since we have three variables to be optimized in Eq. (6), we adopt the popular method, i.e., Alternative directions method of multipliers (ADMM) [Ding and Fu, 2014; Boyd et al., 2011], to obtain our solution. Specifically, we iteratively optimize each variable by fixing other variables. In the optimization process, other variables are fixed and update one each time until it converges.

Update F: While other variables are fixed, the equation can be rewritten as follows:

The differentiate of Eq. (7) is shown below:

Then we have Fu = -FlLluL-1 uu . Since we set Fl = Yl, thus F can be updated as Fu = -YlLluL-1 uu .

Update S: Since S is difficult to optimized directly. We fix other variables and optimize S row by row. The equation can be written as follow:

We separately discuss the equations. The first term can be written as follow:∑i ‖fi - fj‖22 sij = ∑i ais⊤i , (10)

where ai = {aij , 1 ≤ j ≤ n} ∈ R1×n with aij = ‖fi-fj‖22 , si is the i-th row of S. We obtain the same format of the second term as follow:

where bi = {bij, 1 ≤ j ≤ n} ∈ R1×n with bij = ‖Pxi - Pxj‖22 . For the third term, we can write the format as follow:

To minimize ‖S - ¯ S‖2F , we have the following format:

Following the same strategy, we can convert the term in Eq. (13) into the following format:

Then we can transform the objective function into the following format:

The optimization problem of Eq. (15) is simple and the accelerated projected gradient approach is utilized to linearly solve the problem. The core process of the projected gradient approach is solving the proximal equation shown below:

The KKT approach is used to solve this proximal problem. After each si is solved, we concatenate the result together and obtain the updated graph S.

Update P: While other variables are fixed, we can obtain the equation shown below:

and the generalized Eigen-decomposition approach can be used to solve Eq. (17) as shown in Eq. (18).

in which γ is the eigenvalue corresponding to the eigenvector ρ for Eq. (18). Specifically, we could achieve p eigenvectors ρi(i = 0, 1, · · · , p - 1), given by the minimum eigenvalue solutions to the generalized Eigen-decomposition problem. Thus, we have P = [ρ0, · · · , ρp-1]⊤.

3.4 Discussion

We iteratively optimize all variables until the objective function is convergent. Specifically, Fu is initialized through Eq. (1) and it reduces iteration times and avoids local optimal solution.

There are two time consuming optimization steps. The first is updating F, which uses Bartels Stewart algorithm and the complexity is O(n3 ). The second is updating P and its Eigendecomposition process costs O(d3 ). These steps can be reduced to O(d2.37 ) using Coppersmith-Winograd algorithm [Coppersmith and Winograd, 1987]. Then the total computational complexity is O(td2.37 + tn2.37 ) where t is the iteration number. Since the initialization approach reduces the iteration times significantly, thus, our model is applicable to large-scale real-world applications.

4 Experiment

Evaluation datasets, experimental settings, results and discussions are introduced in this section.

4.1 Datasets

Three image, one acoustic and one emotion datasets are evaluated in our experiments. Brief introductions are as follows:

SUN Dataset [Patterson and Hays, 2012] is a large-scale scene multi-label dataset. There are 14, 000 images come from 700 classes. Each instance contains a 102-dimensional label vector with averagely 6.3 labels. The label entries are continuous values range in [0, 1].

CUB Dataset [Wah et al., 2011] contains bird 11, 788 images captured from 200 species. All images are extracted to 312-dimensional attribute labels. Each instance has roughly 28 annotations. The label entries are binary values (0 or 1).

AWA Dataset [Lampert et al., 2014] contains more than 30, 000 images from 50 animals. Each label vector contains 85 continuous values range from 0 to 120 corresponding to 85 semantic attribute labels such as habits, colors, and shapes. Each instance has roughly 15 labels.

BIRD Dataset [Briggs et al., 2013] is an acoustic dataset, which contains 645 ten-second audio recordings from 19 species of bird. Each recording is labeled by several experts along with their confidence.

EMO Dataset [Trohidis et al., 2008] is designed to evaluate automated music emotion detection methods. It collects songs from 233 musical albums and conducted to a set of 30seconds 593 songs with 6 clusters of music emotions. Sound clips were annotated by experts in music.

4.2 Experimental Setup

For image datasets, we utilize Very Deep Convolution Networks [Simonyan and Zisserman, 2014] to extract 4, 096dimensional features. For BIRD dataset, we directly use the features provided by [Briggs et al., 2013]. For EMO dataset, we utilize both Rhythmic and Timbre features provided by [Trohidis et al., 2008]. In Multi-label annotation setting, we randomly and evenly split samples into labeled and unlabeled subset. We run our model five times with the randomly generated subsets and report the average performance. 5-fold cross-validation is utilized to select the parameters µ and λ. ris empirically set to 120. While since EMO dataset contains 72-dimensional features, we manually set r = 50 for EMO dataset. The parameter sensitivity will be discussed in the following sections. Our approach is compared with several state-of-the-art multi-label learning methods, with the brief introductions as follows:

Least Squares Regression (Regression) is a ridge regression method, partial subset of tags labels are utilized to learn a graph and recovery the tags.

Semi-Supervised Multi-Label Dimensionality Reduction (SSMLDR) [Guo et al., 2016] designs a special label propagation method, which transfers the multi-label information across labeled and unlabeled data.

FastTag [Chen et al., 2013] utilizes two linear mappings that are co-regularized in a joint convex loss function. It is able to infer the full list of incomplete tags.

Multi-Label with a Mixed Graph (ML-PGD) [Wu et al., 2015] proposes a uniform approach of label dependencies by generating a graph based on hierarchy structure. This approach simultaneously considers the class co-occurrence as well as the sample-level similarity as non-directive edges. The hierarchy-free version is called ML-PGD.

4.3 Performance Comparison

We utilize the same metrics adopted in [Guillaumin et al., 2009] for fair comparison. In our experiments, we report averaged performance across all instances. To evaluate the result easier, we calculate the F1-score where F1 = 2 P×R P+R and the non-zero recall number N-R. In all metrics, higher values indicate better performances.

The results shown in Table 1 indicate that the proposed AG2E approach obtains the highest performance in most of the metrics. Our approach leads to a 3.5% improvement on precision, 6% on recall. The results demonstrate the robustness and high accuracy of our approach. Furthermore, our approach is general, which is not limited for image datasets. Our approach fails to achieve significant improvements in AWA dataset, where we consider that AWA dataset labels are continuous value range between 0 to more than 100 with different metrics across class labels. It allows our model to learn an inaccurate affinity graph. While least squares approach finds a mapping to recover the label values rather than labels, thus it is less affected by this situation.

4.4 Training Data Analysis

To analyze the source data, we randomly remove partial labeled samples and train our model based on 10%, 20% to 100% of the data. Each setting is tested 5 times and we report the average performance. The results are shown in Figure 3, where we notice that our approach cannot achieve the best performance if only 10% to 20% data is available. As the training sample increases, our approach stably improves the accuracy and achieves the best performance. Moreover, our approach still has potential improvements if more labeled data are available. We assume that since our model mainly depends on P and S, and it cannot perform well if any of the two variables are not well trained. Due to this reason, a minimal number of labeled samples are required to achieve accurate performance.

4.5 Image Sample Annotations

Figure 2 shows samples of SUN dataset and their corresponding recovered labels. Considering in some cases there are more than 15 labels from some instances, we only show the labels which have top highest scores in the recovered labels. The red font denotes incorrect labels. And the blue font denotes labels recovered by our approach. These labels don't exist in ground truth, however, they are still reasonable based on our judgments. From the result, we conclude that our approach is effective, which reliably recovers the vast majority of labels in high accuracy. Moreover, our model also recovers missing labels in the original datasets. This property is crucial and useful in real-world applications since missing labels and outliers always happen in existing datasets.

4.6 Zero-shot Learning

We extend our approach to Zero-Shot Learning (ZSL) scenario [Lampert et al., 2009; Antol et al., 2014; Ding et al., 2017]. ZSL tries to recognize classes which do not exist in the training set. To achieve this goal, middle level semantic information is utilized to align unseen classes and visual features. It is a more challenging task due to the larger distribution gap across classes. In our experiments, each sample is assigned for one class label and several attribute labels. In experiments, we split the dataset into three subsets including labeled set, unlabeled set and test set. Test set contains nonoverlapped classes compared with other two sets. Our approach recovers the labels of the test data and jointly trains a classifier based on the recovered labels to recognize the classes. We normalize the AWA feature vector yi based on equation zi = yi/max(yi) where zi is the normalized label. In the implementation, we calculate ¯ S based on class labels. That means ¯ sij = 1 if xi and xj belong to the same class, and otherwise ¯ sij = 0. KNN is used to classify unseen classes.

The experimental results are shown in Table 2. We observe that the recovered labels can improve the ZSL performance except from linear regression. Since linear regression only recovers labels without considering the existence of missing labels or inner connections. Thus, the performance is as the same as only based on labeled data. Compared with other methods, our method obtains the highest performance in all three datasets. Since the visual feature distributions of seen and unseen classes have larger difference, the result denotes that our AG2E model can obtain more general and compatible feature structures from limited labeled and unlabeled data. It is more accurate and robust than other methods.

4.7 Parameter Analysis

Our approach contains three major parameters, i.e., projection size r, trade-off parameters µ and λ. λ constraints the similarity level between S and ¯ S. µ balances the weight of projected feature space and label space. We adopt different values to evaluate the performance on SUN dataset. The results are shown in Figure 4. We observe that our approach can achieve accurate results when r ≥ 50, µ is in the range of [100, 500] and λ is in the range of [100, 500]. r ≥ 50 is required since the learned feature space needs to have enough dimension to make the samples distinctive enough to represent diverse samples. From the experimental results, we conclude that the parameter ranges are wide and our approach is robust and parameter insensitive.

5 Conclusion

In this work, we designed an Adaptive Graph Guided Embedding (AG2E) approach in semi-supervised multi-label learning scenario. AG2E utilized limited labeled data associating with unlabeled data to improve multi-label learning performance. In our model, a label propagation and an effective embedding were jointly learned to seek a latent space, where unlabeled information can be fully utilized. Moreover, a locality structure regularizer was explored to preserve intrinsic information and accelerate the optimization procedure. Extensive experimental results demonstrated that our approach was effective and outperformed other methods on several datasets. Our model was robust and parameter insensitive. In the future, more experiments for large-scale image annotation, image retrieval and other applications will be evaluated.

Acknowledgments

This research is supported in part by the NSF IIS award 1651902, ONR Young Investigator Award N00014-14-10484, and U.S. Army Research Office Award W911NF-171-0367.