Graph and Autoencoder Based Feature Extraction for Zero-shot Learning

1 Introduction

Image classification has made huge progress in recent years. With the emergence of large-scale databases, some supervised deep learning approaches show their great advantages in recognizing objects. Such methods generally train a model by hundreds of samples collected from each category and can only recognize a fixed number of classes. However, obtaining a large number of labeled samples is difficult and time consuming. In addition, the numbers of samples often follow a long-tailed distribution [Zhu et al., 2014] and it is usually impossible to collect sufficient samples for some rare categories.

∗Contact Author: Q. Gao. (qxgao@xidian.edu.cn)

Zero-shot learning (ZSL) [Palatucci et al., 2009] is designed to identify categories that have no labeled samples during the training phase with the aid of seen classes and semantic information, which is inspired by the process of human recognizing new objects. For example, even if a child has never seen a panda, if the child is told that the panda looks like a bear (seen classes) with black and white blocks (semantic information), he or she can recognize the panda correctly. In other words, ZSL primarily transfers learned knowledge from seen classes to unseen classes by establishing the relationship between seen and unseen classes during the training phase. In particular, one classic approach is to learn the mapping from the visual feature space to the semantic space during the training phase, and then use this mapping to project test samples into the semantic space during the testing phase [Akata et al., 2016]. In this case, the ZSL problem becomes a traditional classification problem, which can be achieved by common classification methods, such as the nearest neighbour (NN) method.

Most methods only learn the mapping from the visual feature space to the semantic space, but do not consider the reconstruction of visual features. This can lead to the domain shift problem [Fu et al., 2015] that adversely affects the final classification results. An effective semantic autoencoder (SAE) [Kodirov et al., 2017] is proposed to solve the problem by adding the reconstruction constraint on the representation of visual features. However, SAE does not guarantee that the learned projection can preserve the underlying sub-manifold of the samples. For example, in the visual space, the horse and the zebra are similar and the blue whale looks more like a dolphin than a horse or a zebra. Thus, the distance between the horse and the zebra should be close in the visual space. We hope such a local structure can be preserved in the semantic space as well (See Figure 1). In the meantime, we hope the projected data have a low-rank structure, which can be achieved by minimizing the nuclear norm regularization [Cand`es et al., 2011]. Moreover, L21-norm regularization is proved to be an effective method for feature selection across all samples with joint sparsity [Nie et al., 2010]. Inspired by these three points, we propose a framework named Graph and Autoencoder Based Feature Extraction method (GAFE) to learn a low-rank embedding to preserve the local structure of the data and thus has more discriminating power.

The novelty of the proposed model lies in three aspects: (1) The graph is constructed to guarantee the learned projection can preserve the local intrinsic structure of the projected data, which allows the model to have more discriminating power. (2) The shared discriminative features across unseen and seen classes can be captured by the low-rank embedding space. (3) The L21-norm regularization can help to select representative features that are more conducive to classification. We perform experiments on five popular datasets and excellent results demonstrate the effectiveness of the proposed model.

2 RelatedWorks

ZSL aims to recognize unseen classes with no training samples by transferring knowledge from seen classes with abundant training samples. The semantic space is used to associate the seen and unseen classes. There are various semantic representations available, such as attributes, word vector and text description. Many experiments show that the attribute is a valid semantic representation for ZSL [Akata et al., 2015], which indicates the intrinsic characteristic (e.g., has wings) of each class or instance. In this paper, we use attributes as semantic representations of classes.

Based on semantic embedding of class prototypes, existing ZSL models can be generally categorized as four groups: (1) Bayesian models. The Bayesian formulation is used to learn embedding models with the prior knowledge of each type of attribute. For example, DAP and IAP [Lampert et al., 2014] first learn per-attribute classifiers using supervised learning methods and then carry out recognition with Bayesian formulation. (2) Semantic embedding. Semantic embedding aims to learn the mapping from the visual feature space to the semantic space with different semantic representations. ALE [Akata et al., 2016] is an effective model and takes attribute-based classification as a label-embedding problem by minimizing the loss function between the label and image embedding. SAE [Kodirov et al., 2017] can effectively solve the projection domain shift problem by adding the reconstruction constraint on the representation of visual features. Motivated by SAE, many models are proposed recently and show good performance[Liu et al., 2018b]. (3) Embedding into common spaces. Different from the semantic embedding, a common intermediate space can be exploited to learn the relationship between the visual feature space and the semantic space. SJE [Akata et al., 2015] aims to learn a common space including multiple semantics, such as text, attributes and hierarchical relationships. Other methods such as [Romera-Paredes and Torr, 2015; Li et al., 2019] also aim to learn common spaces in different ways. (4) Deep embedding. ZSL can also be implemented by deep learning methods. DeViSE [Frome et al., 2013] is first proposed to solve the problem by pretraining deep language and visual models. In recent years, more and more deep learning networks [Norouzi et al., 2014; Wu et al., 2019] have been proposed to solve ZSL tasks.

3 Approach

3.1 ProblemDefinition

Suppose there are n labeled samples with c seen classes {X, S,Y} and nu unlabeled samples with cu unseen classes {Xu,Su,Yu}, where X ∈ Rd×n and Xu ∈ Rd×nu are d-dimensional visual features, while the corresponding labels are Y and Yu respectively. The seen and unseen classes are disjoint, i.e., Y ∩ Yu = ∅. S ∈ Rk×n and Su ∈ Rk×nu are k-dimensional semantic representations of samples in the seen and unseen classes. The ZSL task aims to learn a classifier f : Xu → Yu, where classes of testing data Xu are unseen in the training phrase.

3.2 The ProposedModel

As explained earlier in the introduction, the SAE model [Kodirov et al., 2017] does not guarantee that the learned projection can preserve the underlying manifold of the samples. Then we have the following formulation:

(1)

where W is the projection from visual feature space to semantic space and L is the Laplacian matrix. L is defined as L = P - Q, where Q is the similarity matrix and P is the degree matrix, which is a diagonal matrix whose i-th diagonal element is ∑j qij . α and β are weighting coefficients that balance these terms.

According to Eq. (1), our motivation can be explained as follows: (1) The first and the second terms indicate the SAE model, which can be described as a bidirectional loss between the feature and semantic representations of samples. (2) The third term is the graph regularization based on the Locality Preserving Projection (LPP) [He et al., 2003], which constructs a graph and preserves the local structure of data manifold. It allows the model to have more discriminating power. (3) The fourth term is the low-rank constraint based on nuclear-norm, which integrates the merits of both semantic representation learning and low-rank discriminative embedding. In this way, the shared discriminative features across unseen and seen classes can be captured by the low-rank embedding space. (4) The last term is the L21-norm regularization for feature selection, which can help to select representative features that are more conducive to classification.

3.3 Optimization Algorithm

In order to solve the objective function, we rewrite the Eq. (1) as follows:

Eq. (2) can be solved effectively by Alternating Direction Method of Multipliers (ADMM) method [Boyd et al., 2011]. The augmented Lagrangian function of Eq. (2) is formulated by

where Y1 is the estimate of the Lagrange multiplier and 〈·, ·〉 is defined as the inner product operator. µ is a positive scalar. It is not easy to minimize the Larangian function directly. An effective method to solve Eq. (3) is the alternating direction method by optimizing each variable alternatively while fixing others. Then the optimization problem can be solved by optimizing several subproblems as follows.

Step 1: Update B while fixing the other variables. Problem (3) is reduced to solve problem (4):

where M = 2S+µWX-Y1 2+µ , Ωα/(2+µ) (M) = USα/(2+µ) (∑)VT , U ∑ VT is the singular value decomposition (SVD) of M and the scale shrinkage operator [Cand`es et al., 2011] is defined as Sε (Z) = sign (z) · max (|z| - ε, 0).

Step 2: Update Wwhile fixing the other variables. In this

Algorithm 1 : ADMM algorithm for GAFE

Input: Data matrix X, semantic matrix S Parameter: µmax = 106 , ρ = 1.1, ε = 10-3 , α and β Output: W

• 1: Initialize B=W=Y1= 0, and µ = 0.1.
• 2: while ‖B-WX‖∞ < ε do
• 3: Update B using Eq. (4).
• 4: UpdateWusing Eq. (6) by Bartels-Stewart method.
• 5: Update Y1 and the parameter µ using Eq. (9) and Eq. (10).
• 6: end while
• 7: returnW

case, Eq. (3) becomes

Taking a derivative of Eq. (5) and set it zero, we have

It is worth noting that the derivative of ‖W‖2,1 is defined as

where D is a diagonal matrix with the i-th diagonal element as

where wi is defined as the i-th column of W.

Eq. (6) is a Sylvester equation which can be solved efficiently by the Bartels-Stewart algorithm [Bartels and Stewart, 1972].

Step 3: Update Y1 and the parameter µ. They are updated by Eq. (9) and Eq. (10)

where ρ > 1 and µmax are constants.

The procedure of solving Eq. (2) is listed in Algorithm 1.

The classification process can be performed in the visual feature space or the semantic space. In this paper, we use the first method. That is, when the projection matrix W is well learned, we use WT to project prototypes of unseen classes Su to the visual feature space. Then the label of the testing sample Xiu can be classified by Nearest Neighbour (NN) search with the help of following equation:

where Xiu and Sju are the i-th column of Xu and j-th column of Su. And d (·, ·) represents the distance between two vectors. In this paper, we use cosine distance to calculate the similarity.

4 Experiments

4.1 Datasets

The statistics of the five benchmark datasets are shown in Table 1.

SUN Attribute (SUN) [Patterson et al., 2014] is a finegrained dataset, containing 14,340 samples from 717 categories and 102 attributes. According to [Lampert et al., 2014], 645 classes are used for training and others for testing.

CUB-200-2011 Birds (CUB) [Welinder et al., 2010] is a fine-grained dataset. It has 11,788 samples from 200 different types of birds and the number of attributes is 312. Following [Welinder et al., 2010], the training and testing classes are 150 and 50 respectively.

Animals with Attributes 1 (AWA1) [Lampert et al., 2014] is a coarse-grained dataset, containing 30,475 visual features and 85 class-level attributes. The number of seen and unseen classes are 40 and 10 respectively.

Animals with Attributes 2 (AWA2) [Xian et al., 2018] consists of 37,322 visual features and 85 class-level attributes. Similarly, 40/10 classes are used for training/testing and all of the 50 categories are the same as AWA1 dataset.

A Pascal and Yahoo (aPY) [Farhadi et al., 2009] is a small scale coarse-grained dataset, containing 15,339 samples and 64 semantic features, in which 20 classes are used for training and 12 others for testing.

To make fair comparisons, the class semantics and image features provided by [Xian et al., 2018] are used in our experiments. Specifically, the visual features are extracted by the 101-layered ResNet [He et al., 2016] and the attribute vectors are utilized as the class semantics.

4.2 EvaluationMetrics and ComparisonMethods

The average per-class Top-1 accuracy is used for the evaluation criteria, which is formulated by

where Υ and ‖Υ‖ are defined as the set of categories and number of categories respectively. In other words, Υ consists of all the unseen classes, i.e. the testing classes.

The generalized zero-shot learning (GZSL) is another evaluation criteria, whose search space at testing time is not restricted to only testing categories (Υts ), but consists of the training ones (Υtr ). In this case, we can compute acc (Υts )

and acc (Υtr ) by Eq. (12). In addition, the harmonic mean can be computed as follows

In the experiment, we compare the proposed model with many competitive or representative methods, including shallow methods DAP [Lampert et al., 2014], IAP [Lampert et al., 2014], SSE [Zhang and Saligrama, 2015], SJE [Akata et al., 2015], ESZSL [Romera-Paredes and Torr, 2015], LatEm [Xian et al., 2016], ALE [Akata et al., 2016], SYNC [Changpinyo et al., 2016], SAE [Kodirov et al., 2017], GFZSL [Verma and Rai, 2017], ZSKL [Zhang and Koniusz, 2018] and deep methods DeViSE [Frome et al., 2013], CMT [Socher et al., 2013], CONSE [Norouzi et al., 2014], SP-AEN [Chen et al., 2018], PSR [Annadani and Biswas, 2018], DCN [Liu et al., 2018a], CCSS [Liu et al., 2019].

4.3 Zero-Shot Learning Classification

We compare our proposed GAFE with other methods under the same experimental conditions in Table 2.

It can be seen from Table 2, our proposed GAFE outperforms the other models on all datasets except the CUB dataset. We owe the success of GAFE to the maintenance of the manifold structure. Especially on the AWA1 and aPY datasets, the accuracy has been significantly improved compared with SAE. As a fine-grained dataset, most classes are very similar in CUB, so less discriminative manifold structure could be obtained in the visual space by the GAFE. While PSR or DCN model learns more complicated classifiers to enhance the discriminative property in the visual space.

4.4 Generalized Zero-Shot Learning Classification

To demonstrate the effectiveness of the proposed model, we also apply our method to the GZSL task.

It can be seen from Table 3, most compared approaches get low accuracy on the acc (Υts ) and H because of overfitting the seen classes, while the GAFE method achieves more balanced results between the unseen and seen classes especially on AWA1, AWA2 and aPY datasets and is comparable to the best approach on the other datasets. In addition, our proposed model achieves better results than SAE in all datasets. Specifically, on the AWA1 dataset, the GAFE increases 7.2% and 8.4% in acc (Υts ) and H than the existing best method respectively, which demonstrates the maintenance of manifold structure and selection of effective features benefit the GZSL task.

4.5 Parameter Settings and Convergence Analysis

Our proposed model has two free parameters: α and β (see Eq. (1)). Figure 2 shows the variation of the best results for these two parameters over a small range. From the parameter analysis on α (see Figure 2 (a)), our GAFE achieves the best result when α = 1.4 on the AWA2 dataset while the value of α approaches one on other four datasets. From the parameter analysis on β (see Figure 2 (b)), our GAFE achieves the best result when β = 1 on aPY and AWA2 datasets while the value of β approaches three other three datasets. Empirically, α can be set to 1 < α < 1.4, while β varies from 1 to 3.

The convergence curve of all datasets is shown in Figure 3. It is clear that our algorithm converges within only 160 steps on the AWA2 dataset and 80 steps on other four datasets. The good convergence guarantees the reliability of our model.

4.6 Visualized Results

We further provide some visualized results for the proposed method. Figure 4 shows the confusion matrices of unseen classes on the AWA2 dataset. For each confusion matrix, the column represents the ground truth and the row denotes the predicted results.

According to Figure 4, it is clear that the proposed model GAFE can identify most of unseen categories, except "bat", "dolphin", "seal" on the AWA2 dataset. Considering the fact that no samples from these unseen classes are used to train the model, it strongly supports the superiority of GAFE for effective zero-shot learning.

The prototype of each class usually locate near the samples that belongs to the corresponding class. In order to check whether the prototypes are properly learned, we visualize the prototypes and corresponding samples in the semantic space with the help of t-SNE method [Der Maaten and Hinton, 2008]. We select 7 seen classes and 5 unseen classes from the AWA2 dataset. Figure 5 shows the visualization results.

Although the testing classes are unseen in the training phrase, Figure 5 shows that most samples locate near the prototypes of the corresponding classes. It demonstrates our model can learn a proper projection from the visual feature space to the semantic space.

5 Conclusions

In this paper, we propose a Graph and Autoencoder Based Feature Extraction (GAFE) method for zero-shot learning. Extensive experiments on five attribute datasets show the effectiveness of the proposed method. Our approach can be summarized as three advantages. First, our model can select features to establish the relationship with the semantic space. Second, the learned projection can well preserve the local intrinsic structure of the projected data. Third, the shared discriminative features across unseen and seen classes can be captured by the low-rank embedding space. In general, the above three advantages can improve the recognition performance and makes our model outperforms existing ZSL models.

Acknowledgements

This work is supported by China Postdoctoral Science Foundation (Grant 2019M653564), National Natural Science Foundation of China under Grant 61773302, 61432014, 61772402 and the Fundamental Research Funds for the Central Universities.