Zero Shot Learning via Low-rank Embedded Semantic AutoEncoder

1 Introduction

In recent years, along with the explosive growth of web data, there has been significant progress in large-scale classification with aid of conventional frameworks, e.g. Deep Neural Networks (DNN) [Krizhevsky et al., 2012]. Conventional frameworks mainly depend on a large number of training samples to build robust models. However, as obtaining well-annotated training samples are labor-intensive and timeconsuming, sufficient labeled training samples are usually unavailable in many real-world situations. Meanwhile, the number of newly defined classes is ever-growing, indicating that training a particular model for each of them is unattainable.

Zero-shot learning (ZSL) [Palatucci et al., 2009] has been widely recognized as a feasible solution to deal with these problems. ZSL attempts to learn mechanism of human brain and recognize new classes which are not observed in the training stage. For instance, one can easily recognize a new species of objects after being told how it is similar to or different from other observed objects. The main reason is that humans can explore the relationship across different objects, and adapt the knowledge from seen classes to unseen ones. Likewise, ZSL aims to uncover the intrinsic relationship between seen and unseen classes. Specifically, the fundamental idea of ZSL is to learn a general mapping from the feature space to a semantic space using the labelled training samples consisting of seen classes only. This mapping is then used to project the visual representation of the unseen class images into the semantic space. Hereafter, the task of unseen class recognition becomes a typical classification problem which can be realized by a simple nearest neighbour (NN) search.

∗Corresponding author: Q. Gao. (qxgao@xidian.edu.cn)

However, most existing ZSL methods neglect the importance of reconstruction. They put much attention on learning a projection only from the feature space to a semantic space instead of considering reconstructing the original visual feature representation. This can lead to a projection domain shift problem [Fu et al., 2015a]. Sometimes this shift will adversely affect the final classification results. Recently, [Kodirov et al., 2017] proposed a model named Semantic AutoEncoder (SAE) which imposes a new constraint in learning a projection from the visual space to the semantic space so that the projection must also preserve all the information contained in the original visual features. However, this constraint cannot guarantee the reconstructed data has a low-rank structure, which is important for undercomplete autoencoders [Xie et al., 2016] like Principal Component Analysis (PCA) [Jolliffe, 1986]. In this paper, we proposed a model named Low-rank Embedded Semantic AutoEncoder (LESAE). We assume that the latent semantic space for unseen samples should share its majority with semantic space for the seen samples, which should be identified in the low-rank embedding space. Taking the encoder-decoder paradigm, the encoder part tries to learn a low-rank projection from the feature space to a semantic space as in the existing ZSL models. The decoder part aims to the learned mapping can reconstruct the original visual features precisely.

We summarize our main contributions as follows: (1) We build a bridge between reconstruction and Low-rank representation to capture shared discriminative features across seen and unseen classes. A robust model is proposed for zeroshot learning (ZSL) and generalized zero-shot learning (GZSL). (2) We formalize ZSL as the problem of learning a lowrank semantic representation of input data that can also be used for data reconstruction. (3) An efficient iterative algorithm based on Sylvester equation is introduced to solve this model and leads to state-of-the-art recognition performance on six benchmark datasets for ZSL and GZSL.

2 RelatedWorks

Low-rank embedding This technique aims to recover the low-rank clean data from the corruption data and has been successfully applied to many applications including image clustering [Chen et al., 2018; Li et al., 2018], image classification [Liao et al., 2018; Liu et al., 2018], object tracking [Zhang et al., 2015; Yang et al., 2017], hyperspectral image denoising [Fan et al., 2017] and dynamic MRI [Nakarmi et al., 2017]. Robust Principal Component Analysis (RPCA) [Cand`es et al., 2011] is of the most representative methods. This model was demonstrated that PCA can be made robust to outliers if exactly recovering the low-rank representation by solving a simple convex problem. Similarly, LowRank Representation (LRR) [Liu et al., 2013] aims to seek the lowest rank representation among all the candidates that can represent the data samples as linear combinations of the bases in a given dictionary. [Peng et al., 2012] proposed RASL to seek an optimal set of image domain transformations such that the matrix of transformed images can be decomposed as the sum of a sparse matrix of errors and a lowrank matrix of recovered aligned images. Recently, [Nie et al., 2017] proposed a novel model named Multi-view Learning with Adaptive Neighbours (MLAN). With the reasonable rank constrain, the obtained optimal graph can be partitioned into specific clusters directly. Inspired by these successful approaches, we apply low-rank embedding into zero-short learning in the paper.

Zero-short learning A variety of approaches for zero-shot learning have been recently proposed. To circumvent learning independent attributes, embedding-based ZSL frameworks are proposed to learn a projection that can map the visual space to semantic space at once. The class label is then determined in the semantic space using various relatedness measurements [Akata et al., 2013; Socher et al., 2013; Zhang and Saligrama, 2016]. In addition to directly using fixed semantic embedding, some work tries to map them into a different space by sparse coding [Zhang and Saligrama, 2015; Kodirov et al., 2015] and CCA [Fu et al., 2015a]. Recent work [Long and Shao, 2017; Ding et al., 2017; Long et al., 2017; Kodirov et al., 2017] combines the embeddinginferring procedure into a unified framework and empirically demonstrates better performance.

In our evaluation we choose following representative methods for comparison on several benchmark datasets. DAP [Lampert et al., 2014] and IAP [Lampert et al., 2014] are two of the most fundamental methods in ZSL research. Such models utilize semantic attributes as intermediate clues.

CONSE [Norouzi et al., 2014] is one of the most widely used representatives of learning a mixture of class proportions. SSE [Zhang and Saligrama, 2015] uses the mixture of seen class proportions as the common space and leverages similar class relationships both in the visual space and the semantic space. SJE [Akata et al., 2015] and ESZSL [RomeraParedes and Torr, 2015] learn the bilinear compatibility function between the visual and the semantic space optimizing the structural SVM loss and square loss respectively. ALE [Akata et al., 2016] and DEVISE [Frome et al., 2013] learn the bilinear compatibility with similar ranking loss functions. LATEM [Xian et al., 2016] gives non-linear extension to bilinear compatibility learning methods. CMT [Socher et al., 2013] aims to learn a non-linear projection from visual space to semantic space by a neural network. SYNC [Changpinyo et al., 2016] constructs classifiers for unseen classes by a linear combination of base classifiers. SAE [Kodirov et al., 2017] learns a low dimensional semantic representation of input data that can be used for data reconstruction. SS-Voc [Fu and Sigal, 2016] utilizes open set semantic vocabulary to help train better classifiers in supervised learning. AMP [Fu et al., 2015b] computes semantic manifold distance by a absorbing Markov chain process.

3 Approach

For ZSL task, we aim to classify the samples from unseen classes according to their class-level attributes, where both the samples and labels of unseen classes are totally independent from the training phase.

Suppose there are c seen classes with n labeled samples S = {X,A,Y} and cu unseen classes with nu unlabeled samples U = {Xu, Au, Yu}, where X ∈ Rm×n and Xu ∈ Rm×nu are m-dimensional visual features in the seen and unseen data, while their corresponding class labels are Y and Yu, respectively. The seen and unseen classes have no label overlap, i.e., Y ∩ Yu = ∅. A ∈ Rd×n and Au ∈ Rd×nu are d-dimensional semantic representations of instances in the seen and unseen datasets. In the zero-shot learning task, we aim to learn a classifier f : Xu → Yu, where the samples in Xu are completely unavailable during training.

The intuition behind ZSL is that the classifier would be able to capture the relationship between the visual space and the the semantic space. Inspired by the recent work [Kodirov et al., 2017] considering the transpose of projection matrix as a decoder to reconstruct the original visual feature, we develop an effective Low-rank Embedded Semantic AutoEncoder (LESAE) that integrates the merits of both low-rank discriminative embedding and semantic representation learning. Specifically, LESAE tries to learn a Low-rank projection matrix W ∈ Rd×m (d < m) from the feature space X to the semantic space A. At the same time, the semantic space can be projected back to the feature space with WT ∈ Rk×d to reconstruct the input data exactly. This can be achieved by optimising the following function:

where ‖·‖∗ denotes Frobenius norm of a matrix, β is the balance parameter, rank(·) is the rank operator of a matrix.

Rank minimization in Eq. (1) is a well-known NP hard problem, and considerable approaches have been proposed. One of appealing strategies is to adopt trace norm ‖W‖∗ as a surrogate of the term rank(W). Instead of adapting the traditional Singular Value Thresholding (SVT) [Cai et al., 2010] to solve the objective, we exploit a regularization term that guarantees that the low-rank feature of optimized W. Mathematically, we have following equation:

According to Eq. (1) and Eq. (2), the new formula with low-rank constraint can be rewritten as:

where H = (WWT )- 1 2 .

Solving the objective function (3) with a hard constraint such as WX = A is difficult. Therefore, we consider to relax the constraint into a soft one and rewrite the objective function (3) as:

3.1 Optimization Algorithms

The objective function (4) has two unknown variables. It is difficult to directly solve the solution. An algorithm can be developed for alternatively updating W (while fixing H) and H (while fixing W). Here we develop an efficient algorithm to solve this problem.

Update H: When W is fixed, H can be computed by H = (WWT )- 12 .

Update W: When H is fixed, taking the derivative of Eq. (4) with respective to W and setting it to zero, we have:

where

Before solving Eq. (5), we first introduce one definition and two theorems:

Definition 1 [Sylvester, 1884]: A Sylvester equation is a matrix equation of the form:

Theorem 1 [Lancaster and Tismenetsky, 1985]: The sufficient and unnecessary condition for Eq. (7) having a solution is that the matrices [ P 0 0 Q ] and [ P D 0 -Q ] are similar.

Theorem 2 [Lancaster and Tismenetsky, 1985]: The sufficient and unnecessary condition for Eq. (7) having a unique solution is that the eigenvalues λ1, λ2, · · · , λn of P and

Detailed explanation of Definition 1 and proofs of Theorem 1 and Theorem 2 can refer to [Lancaster and Tismenetsky, 1985].

According to Definition 1, it is easy to know Eq. (5) is a Sylvester equation. So Eq. (5) has a unique solution if it meets conditions of Theorem 1 and Theorem 2, which can be easily satisfied in the real-world zero-short learning.

Vectorizing the unknown matrixW, Eq. (5) can be transformed to a linear equation:

where ⊗ is the Kronecker product, Im ∈ Rm×m and Id ∈ Rd×d are identity matrices, vec(C) is the vectorization of the matrix C. Then, W can be obtained by following equation.

In MATLAB, it can be implemented with a single line of code: sylvester 1 .

So far, we have build the optimization rules for two variables. Then, we iteratively update them until converge. For clarity, Algorithm 1 lists the pseudo code of solving our model (4). In Algorithm 1, η is a small positive parameter to ensure H has a solution. We terminate the algorithm 1 when the Frobenius norm of relative changes of W is below 10-6 .

Algorithm 1:

Input Training set {X,A}.

Initialize W = I

repeat

2. UpdateWby solving the Eq. (5) and Eq. (6).

until converge

Output projection matrix W.

3.2 Zero-shot Recognition

Once we obtain the projection matrices W, the visual features of unseen classes can be easily synthesized from their semantic attributes Au by following equation:

It is noticeable that for image-level attributes, Xu contains as many instances as the test set. The zero-shot recognition task now becomes a typical classification problem. Thus, any existing supervised classifier can be applied. Since we focus on the quality of the synthesized features, we simply use Nearest Neighbour (NN) in the task.

4 Experiments

In this section, we will validate our proposed method on five small-scale datasets (SUN, CUB, AWA1, AWA2 and APY) and one large-scale dataset (ImageNet), compared with other state-of-the-art methods mentioned in related works.

1 https://uk.mathworks.com/help/matlab/ref/sylvester.html

4.1 Datasets Descriptions

Five small-scale datasets: SUN Attribute (SUN) [Patterson et al., 2014] is a fine-grained dataset, which contains 14,340 images coming from 717 types of scenes annotated with 102 attributes. Following [Lampert et al., 2014], 645 out of 717 classes are used for training and rest 72 classes for testing.

CUB-200-2011 Birds (CUB) [Wah et al., 2011] is a finegrained and medium scale dataset with respect to both number of images and number of classes, i.e. 11,788 images from 200 different types of birds annotated with 312 attributes. [Akata et al., 2016] introduces the first zero-shot split of CUB with 150 train classes and 50 test classes.

Animals with Attributes 1 (AWA1) [Lampert et al., 2014] is a coarse-grained dataset, which has totally 30,475 images and 85-dim class-level attributes, in which 40 classes are used for training and 10 others for testing.

Animals with Attributes 2 (AWA2) [Xian et al., 2017] uses the same 50 animal classes as AWA1 dataset, while 37,322 images are collected from the public open source. Compared to AWA1, AWA2 dataset contains more images, e.g. horse and dolphin among the test classes, antelope and cow among the training classes. Same as AWA1, 40 classes are used for training and 10 others for testing in AWA2 dataset.

A Pascal and Yahoo (aPY) [Farhadi et al., 2009] is a smallscale coarse-grained dataset with 64 attributes. Among the total number of 32 classes, 20 Pascal classes (we randomly select 5 for validation) and 12 Yahoo classes are used for training and testing, respectively.

One large-scale dataset: ImageNet [Russakovsky et al., 2015] has totally 218,000 images and 1000-dim class-level attributes. In this large-scale dataset, as in [Fu and Sigal, 2016], 1,000 classes of ILSVRC2012 are used as seen classes, while 360 classes of ILSVRC2010, which are not included in ILSVRC2012, for unseen classes.

4.2 Evaluations

For five small-scale datasets, we follow the settings of [Xian et al., 2017] to make sure the absence of any image from test classes during training. Then the 2048-dim feature of each image is extracted from the 101-layered ResNet [He et al., 2016]. As class embeddings, we use per-class attributes. All the features and attributes used in experiments are published for open access 2 .

To evaluate the performance of methods on five small-scale datasets, the Top-1 accuracy (the prediction is accurate when the predicted class is the correct one) is measured. Moreover, for GZSL task, the samples from seen/unseen classes are classified into all classes. In GZSL setting, the search space at evaluation time is not restricted to only test classes, but includes also the training classes. In our experiments, we computer the harmonic mean of seen and unseen classification accuracies by flowing function [Xian et al., 2017]:

where accs and accu represent the Top-1 accuracy of images from seen, and images from unseen classes respectively.

For fair comparison with published results, we follow the settings with [Kodirov et al., 2017] in ILSVRC2012/ILSVRC2010 dataset. In detail, we use GoogleNet features [Szegedy et al., 2015] which is the 1024-dim activation of the final pooling layer. As an image usually contains multiple objects, we measure the Top-5 accuracy in this large-scale dataset.

4.3 Parameter Settings

Our LESAE model has two free parameters: α and β (see Eq. (4)). Figure 1 shows that the value of α and β achieving the best performance in different datasets are concentrated in a small range. Specifically, from the parameter analysis on α (see Figure 1 (a)), our model can achieve better performance when the value of α approaches zero on SUN, CUB and aPY datasets, while performs better around α = 2.5 on other three datasets. From the parameter analysis on β (see Figure 1 (b)), our model can achieve better performance when the value of α approaches zero on SUN and CUB datasets, while performs better around β = 20 on other four datasets. Empirically, α can be set to 0 < α < 3, while β varies from 0 to 40.

4.4 ZSL and GZSL Results

Table 1 presents the ZSL Top-1 accuracy on five small-scale datasets. Table 2 shows the ZSL and GZSL Top-5 accuracy on ImageNet. Table 3 shows three evaluation indicators for the GZSL task on five small-scale datasets. Comparing the aforementioned experiments, we have several interesting observations:

2 The zero-shot learning benchmark can be found in the following link: http://www.mpi-inf.mpg.de/zsl-benchmark

(1) For zero-short learning, our model achieves the best results on all datasets except the CUB dataset although most of the compared methods apply complicated nonlinear models. Specifically, the accuracies on the AWA2 dataset increase 6% compared the strongest competitor. Our model and SAE have a similar result on SUN and CUB datasets. This is because our model achieve better performance when β approaches zero (see Figure 1 (b)), which means the low-rank constraint plays a small role on SUN and CUB datasets. On the largescale dataset ImageNet, our model and SAE have a similar result, which increases 12.5% compared the existing best one, i.e. SS-Voc. However, all the methods perform poorly which indicates that there is a large room for improvement in this large-scale dataset.

(2) For generalized zero-short learning, our approach achieves the highest "ts" value in all small-scale datasets, which demonstrates that a low-rank projection would benefit the GZSL task. Moreover, it is easy to see that the "ts" value and the "H" value for those baselines with big "tr" value are generally very small. The main reason is that a very big "tr" value reflects the over-fitting training for the seen classes, i.e. the trained model in these methods cannot be generalized to new classes. On the large-scale dataset ImageNet, same as the ZSL result, our model increases 0.4% than SAE.

4.5 Complexity and Convergence Analysis

Figure 2 shows the algorithm 1 converges within only 5 steps. Moreover, the complexity of Eq. (5) depends on the size of feature dimension O(m3 ) instead of the number of samples n. These demonstrate our algorithm has a good practical application for its low complexity and good convergence.

5 Conclusions

In this paper, a novel ZSL model named Low-rank Embedded Semantic AutoEncoder (LESAE) is proposed to learn a low-rank mapping to link visual features with their semantic representations. The encoder part tries to learn a low-rank projection from the feature space to a semantic space as in the existing ZSL models. The decoder part aims to the learned mapping can reconstruct the original visual features precisely. An optimization algorithm is also given to solve our model. Empirical results on five small-scale datasets and one largescale dataset showed our method is significantly better than several well-established ZSL approaches.

Acknowledgements

This work is supported by National Natural Science Foundation of China under Grant 61773302, the 111 Project of China (B08038), and NSFC No. 91748208.