Landmark Selection for Zero-shot Learning

1 Introduction

When training a recognition model for a category, it is expected to have sufficient labeled samples for training in a standard supervised learning way. However, this requirement is too demanding in many real-world applications, such as Web image classification and fine-grained classification. In these scenarios, there are a large number of classes, in which some common ones have sufficient labeled examples while most uncommon ones have only few or no labeled data, since the number of labeled samples follows a long-tail distribution [Changpinyo et al., 2016]. To deal with this challenge, zero-shot learning (ZSL) [Farhadi et al., 2009; Lampert et al., 2014] has been demonstrated to be a promising solution. ZSL learns a compatibility function between image and class features by the data from seen classes. Then this function is transferred to the unseen ones for prediction.

ZSL is currently a hot research topic attracting considerable research interest. Many approaches have been proposed yielding promising performance [Xian et al., 2017]. Formally, most of representative approaches are formulated as a heterogeneous domain adaptation problem which aligns the image feature space and class feature space, such Water Water Water as the deep networks' output [He et al., 2016] and the class attributes [Lampert et al., 2014] or word2vec embeddings [Huang et al., 2012]. The alignment function, or the compatibility function, is learned from the seen classes and their labeled samples. By assuming the transferability of the function between classes, one can apply it to unseen classes even though they do not have labeled images for training.

Figure 1: The "polar bear" class has the attribute "water" in AwA dataset, while not all images contain it. It is clearly unreasonable to align all image features indiscriminately to the class attribute vector.

How to learn the compatibility function is the key problem in ZSL literatures [Xian et al., 2017]. Based on the properties of data, one-vs-all training is always utilized. In particular, each class has one class feature vector and many images. Therefore, the class vector is combined with each of the image vectors to compute the loss function, which indicates that all images contribute equally to the training procedure.

It is necessary to raise a question: is every image equally important for training? The answer has been given by many literatures, including active learning [Aggarwal et al., 2014] and hard example mining [Shrivastava et al., 2016], which demonstrates that using the most representative and informative samples may leads to better performance. In the scenario of ZSL, it is more reasonable to assign different weights to different images. In fact, each class has only one feature vector, like the attribute vector. This vector usually indicates the general characteristics of the class. On the other hand, different images may show different characteristics of a class due to the various occlusion, object size, orientation, and so on. For example, a "polar bear" class has the attribute "water". However, this attribute does not appear in all "polar bear" images since some images are captured on the ground. In this circumstance, it seems unreasonable to match a "non-water" image to the "water" attribute. Moreover, due to the missing attributes, the image-class pair yields large training loss. To minimize the total loss, the model will try to fit these mismatching pairs, resulting a biased model from a good one.

Here we show an illustration in Figure 1. The Animals with Attributes (AwA) [Lampert et al., 2014] uses an attribute vector for each class. The "polar bear" has the attribute "water". However, many "polar bear" images do not contain this attribute. Obviously not all "polar bear" images are representative for the class, especially when described by only one attribute vector. To learn a good compatibility function between class features and image features in the one-vs-all setting, it is necessary to find the most representative images which are the most compatible with the class feature for model training.

Based on this motivation, in this paper we propose a novel approach, Landmark Selection (LAST) for ZSL. Instead of regarding all images equally important for compatibility function learning, LAST exploits the representative images which are then associated to the class features. We jointly optimize the landmark selection and function learning from a cold start, which turns out to be an effective strategy. In addition, different from most existing ZSL approaches which use sample-wise or class-wise matching, we further introduce a global domain alignment term into the objective function, which is inspired by domain adaptation [Pan and Yang, 2010; Tsai et al., 2016]. Based on this global alignment term, the model is capable of generalizing better for unseen classes and images, which is desired for ZSL. Both global term and classspecific conditional term are formulated into a joint optimization function. It improves the performance of ZSL, especially for large-scale benchmarks which have many classes. In summary, we make the following contributions in this paper.

1. We notice that it is unreasonable to assign the same weight to all images during training a ZSL model in one-vsall strategy. To address this issue, we propose LAST which finds representative images to match the class features. The selected landmarks result in more effective ZSL models.
2. Inspired by domain adaptation, we further incorporate a global alignment term into the objective function together with the conditional term, making the model generalize better, especially for large-scale benchmarks with many classes.
3. We carry out extensive experiments on several benchmarks, including ImageNet [Russakovsky et al., 2015]. The results demonstrate the effectiveness of LAST for (generalized) ZSL in comparison with the state-of-the-art approaches.

2 Preliminary and RelatedWork

2.1 Notations

Following the definition in [Xian et al., 2017], we describe ZSL problem as follows. There are two disjoint class sets Cs = {cs1 , ..., csks } and Cu = {cu1 , ..., cuku } with Cs ∩ Cu = ∅, denoted as seen classes and unseen classes respectively. Each image is represented by an image feature vector x ∈ Rp and each class is represented by a label feature vector y ∈ Rq . There is a training set Dtr = {(xi, yi)}ns i=1 where the each class feature yi corresponds to a seen class from Cs. A compatibility function F(x, y;W) between image and class features is trained based on the training set. Then, it is applied to a test sample, which is from unseen classes Cu in the conventional ZSL setting, or Cs ∪ Cu in the generalized ZSL setting. The classification is performed by selecting the class which has the largest compatibility to the test sample by F (x, y; W).

2.2 Zero-shot Learning

The key component in ZSL is the compatibility function F (x, y; W). Given an unseen class, we can use F to compute its relationship to any images even though no visual example of this class is available for training. Most ZSL approaches focus on the learning algorithm and the specific form for F .

One widely used definition is the bilinear model F(x, y;W) = xWy′ . It has been used in Attribute Label Embedding (ALE) [Akata et al., 2016], Deep Visual Semantic Embedding (DEVISE) [Frome et al., 2013], Structured Joint Embedding (SJE) [Akata et al., 2015], Embarrassingly Simple ZSL (ESZSL) [Romera-Paredes and Torr, 2015], and so on [Guo et al., 2016; Zhang and Saligrama, 2016]. To train the model, different loss functions are utilized, including ranking loss, triplet loss, Euclidean loss, cross-entropy loss, and etc. Besides, some other compatibility functions are equivalent to the bilinear function. For example, Euclidean distance based function, like F(x, y;W) = -‖xWx - y‖2 or F(x, y;W) = -‖x - yWy‖2 [Kodirov et al., 2017]. Latent Embedding (LATEM) [Xian et al., 2016] uses multiple compatibility function with latent variables F(x, y;W) = max1≤i≤K xWiy. Moreover, some approaches try to learn image-specific feature transformation and/or class-specific feature transformation to improve the non-linearity of the function. Cross-modal Transfer (CMT) [Socher et al., 2013] utilizes tanh(xWx) for image feature transformation. Semantic Similarity Embedding (SSE) [Zhang and Saligrama, 2015] uses sparse coding for image transformation and ReLU for class transformation. Implicit Non-linear Similarity Scoring (ICINESS) [Guo et al., 2018] uses deep convolutional networks for image transformation and multi-layer perceptron for class transformation. Discriminative Semantic Representation Learning (DSRL) [Ye and Guo, 2017] uses sparse non-negative matrix factorization and max-margin semantic alignment for class transformation. Though they have different details, they basically follow the bilinear model.

Besides, some ZSL approaches use other ideas. For example, sample transfer [Guo et al., 2017b] and sample synthesis [Guo et al., 2017a] focus on bring in pseudo examples for unseen classes. Direct/Indirect Attribute Prediction (DAP/IAP) [Farhadi et al., 2009; Lampert et al., 2014] consider to recognize the attributes from images and compare them to the class attributes. Convex Semantic Embedding (CONSE) [Norouzi et al., 2013] firstly compute the probability of an image belonging to a seen class. Then based on the similarity between class features, the probability is propagated to the unseen classes. Semantic Manifold Distance (SMD) [Fu et al., 2015] further utilizes a similarity graph constructed from class features and hidden Markov process to propagate the probability. Synthesized Classifier (SYNC) [Changpinyo et al., 2016] and Shared Model Space (SMS) [Guo et al., 2016] learn a mapping from class features to the classifier parameter space. Semantics-Preserving Adversarial Embedding Networks (SP-AEN) [Chen et al., 2018] uses generative adversarial networks to construct visual examples for the unseen classes. Cycle-consistent Generalized ZSL [Felix et al., 2018] considers to adopt multi-modal cycleconsistent GAN to generate image representations.

3 The Proposed Approach

3.1 Objective Function

In this paper, we regard ZSL as a domain adaptation problem, which learns a transformation matrix W to align image feature x and class feature y. We base our approach on the ideas of autoencoder [Kodirov et al., 2017] and cycle-GAN [Felix et al., 2018]. The base objective function is:

We hope the compatibility matrix W can well align heterogeneous features such that our objective is to minimize the distortion of both image-to-class projection and class-to-image projection. This function can be regarded as the base model.

Obviously, Eq. (1) is class aware and it connects image features and class features belonging to the same class. Therefore, we can regard Eq. (1) as minimizing the difference between the conditional distribution of image features and class features. Inspired by the basic idea of domain adaptation [Pan and Yang, 2010], we propose to further consider the marginal distribution difference between image features and class features. In fact, one goal of learning the compatibility matrix W is to align the image feature space and class feature space. Based on this motivation, we propose to further minimize the maximum mean discrepancy (MMD) [Wang and Deng, 2018] between the projected image features and the projected class features as follows,

If Eq. (1) is regarded as the class-specific alignment, Eq. (2) can be regarded as the global alignment. By reviewing existing ZSL literatures, it is observed that Eq. (2) is always ignored. In fact, ZSL focuses more on the unseen classes instead of the seen ones. Therefore, when using seen classes for training, the generalization ability of the model is an important issue. To improve the generalization ability, it seems reasonable to consider the global alignment between heterogeneous feature spaces. In the experiments, we will show the effectiveness of this term. By combining Eq. (1) and Eq. (2), we obtain an objective function based on domain adaptation.

As discussed above, Eq. (1) andmany other ZSL approaches adopt a one-vs-all strategy where each of the ks class features is combined with all image features belonging to this class. In this way, all images belonging to this class have the same training weight. However, not all of them are representative for this class, as illustrated in Figure 1. To improve the performance, it seems reasonable to identify the adaptation ability of each image with a proper weight. These images are the landmarks for adaptation which indicates that they are the most representative to reflect the properties (attributes) of the class like the class feature. As introduced, each class has only one class feature, which shows the most general characteristics of this class. Therefore, it is also desired that the selected images could contain general characteristics such that they can be correctly aligned to the class feature. To do so, we introduce a learnable non-negative weight µi for each image. Taking the weight for each image into account, the objective function of the proposed LAST is:

where the first two terms consider the conditional alignment, the third and the fourth terms consider the marginal alignment, and the fifth term is a regularization to control the complexity. The weight parameter µi indicates if xi a representative image. A non-zero weight means that this image is selected as a landmark. Theoretically, using 0-1 binary weight seems more compatible with "landmark selection". However, binary weight makes the optimization complicated. Therefore we use continuous value in [0, 1] as soft selection. This value can reflects the importance of an image and its contribution to the alignment. The parameter δ ∈ [0, 1] determines the portion of the selected landmarks. For example, we can set δ = 0.5 to softly use half of images.

It is easy to observe the difference between LAST and previous ZSL approaches. Firstly, unlike the other approaches regarding all images equally important, we propose to use (soft) landmark selection to find the representative images for cross-domain adaptation. Since each class has only one class feature, it is more reasonable to use the representative images instead of the ones with micro and specific characteristics. Secondly, for domain adaptation, LAST not only considers the conditional alignment like previous approaches, but it also utilizes the marginal alignment between image feature space and class feature space. This strategy is capable of aligning two heterogeneous spaces from a global perspective, making the model generalize better for previously unseen classes.

3.2 Optimization

Eq. (3) has two variables to optimize, the compatibility matrix W and the selection weight µi. One simple strategy is to use an iterative optimization algorithm which alternatively updates one of them while keeping the other variable fixed.

Optimizing W. Denote Ω = diag(µ1, ..., µns ), µ = [µ1, ..., µns ] and fix µ. We can rewrite Eq. (3) as follows,

where eks is a ks-long row vector whose all elements are 1, X = [x1; ...; xns ] ∈ Rns×p , Y = [y1; ...; yns ] ∈ Rns×q , and YC = [y1 ; , , , ; yks ] ∈ Rks×q . Now we need to take a derivative of the loss function above with respect to W and set it to zero to solve W, which leads to the problem below,

where

Eq. (4) is a Sylvester equation which can be efficiently solved by the Bartels-Stewart algorithm [Bartels and Stewart, 1972]. For example, it can be solved in MATLAB by a build-in function sylvester1 . The complexity of the solver depends on the dimensionality of features, and is independent of the number of samples, making it feasible for large-scale datasets.

Optimizing µ. By fixing W, we can rewrite Eq. (3) as

where

Eq. (6) is a standard quadratic programming problem, which can be solved efficiently and easily by many well-established QP solvers, such as the quadprog2 function in MATLAB.

3.3 Discussion

Since we use an iterative algorithm to solve Eq. (3), we need to initialize variables at first. In this paper, we simply initialize µi = δ and optimize W first. Since our goal is to find the representative images for cross-domain alignment. At first, no cross-domain alignment function is available, and thus we have to initialize them with the same weight. In fact, besides the self-initialization, we can also consider a warm-start method by using other ZSL approaches to find the representative images and initialize µi accordingly.

As introduced above, the complexity of solving Eq. (4) is irrelevant to ns. However, the QP solver for Eq. (6) has polynomial complexity of ns. In this case, training a model on a large-scale dataset, like ImageNet is quite challenging. To address this issue, we propose a mini-batch based strategy. For a dataset with ns training samples, we divide it into M mini batches and each batch has ns/M samples. We use one batch to solve Eq. (6) to obtain the weights for samples in this batch and then we process each batch in the same way. In

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

2 https://www.mathworks.com/help/optim/ug/quadprog.html

Algorithm 1 Landmark Selection for ZSL

Input: Training set {xi, yi}ns i=1 , parameter λ, α, β, γ, δ; Output: The compatibility matrixW; Initialize: µi = δ; repeat Update W by solving Eq. (4); for one mini batch in training set do Update µi for this batch by solving Eq. (6); end for until Convergence; Return W ;

this way, the complexity of solving Eq. (6) is reduced from poly(ns) to ns ×poly(b) where b the the size of a mini batch which is much smaller than ns. This strategy turns out to be effective and efficient in practice.

At test stage, given a test sample and a set of unseen classes, the compatibility function is defined as:

which considers the embedding in image feature space and class feature space like the training objective function, and normalizes them for addition by a softmax-like operation.

4 Experiment

4.1 Setting

We use five widely used ZSL benchmark datasets for evaluation. The first dataset is Animals with Attributes2 (AwA2) [Xian et al., 2017] which has 50 animal categories. In AwA2, 40 categories are used as seen classes and the other 10 as unseen classes. The second dataset is aPascal-aYahoo (aPY) [Farhadi et al., 2009]. It has 20 classes from Pascal VOC challenge like "person" and "dog" as the seen classes, and 12 related classes like "centaur" and "wolf" collected from Yahoo search engine. The third dataset is SUN [Patterson and Hays, 2012] scene recognition dataset which has 717 different scenes of which 645 are used as seen classes and the other 72 as unseen classes. The fourth dataset is CUB [Wah et al., 2011] bird fine-grained recognition dataset with 200 kinds of birds of which 150 are used as seen classes and the other 50 as unseen classes. The last dataset is ImageNet [Russakovsky et al., 2015] which is a large-scale dataset with a large number of classes. The widely used 1, 000 classes with about 1.3 images are used as training set. There are another about 20k classes with about 14 million images, which are utilized as the test set. To comprehensively evaluate on ImageNet, we consider different subset of the test set, including classes that are 2-hops (denoted as 2H, 1, 509 classes) and 3-hops (3H, 7, 678 classes) away from the 1, 000 seen classes, the most popular 500 (M500), 1k (M1K), and 5k (M5k) classes, and the least popular 500 (L500), 1k (L1K), and 5k (L5K) classes. For each dataset, some seen class images are used for model training and the other seen class images together with all unseen class images are utilized as the test set. For each image, the ResNet-101 [He et al., 2016] pre-trained on ImageNet is employed as feature extractor producing 2, 048-dimensional image feature. For each class, the class attribute vector is regarded as the label feature vector for the first four datasets. For ImageNet, we use the 500-dimensional word2vec representations for all classes [Changpinyo et al., 2016]. For fair comparison, we make use of the same seen-unseen split, train-test split, image feature, and label feature given by Xian et al. [2017]. To evaluation the performance, we consider two tasks. The first task is standard ZSL where a test image comes from only unseen classes. The second task is generalized ZSL where a test image may come from both seen and unseen classes. To evaluate performance, we use the average per-class top-1 accuracy and the harmonic mean for two tasks respectively. Please refer to [Xian et al., 2017] details.

To implement LAST, we use the following settings. We set the parameters in Eq. (3) as: λ = 1, α = β = ns/10, γ = 0.01 and δ = 0.5. When using mini-batch based optimization, we set the mini batch size to 1, 024. For both image features and class features, we further perform dimensionwise centralization such that these features have zero mean.

4.2 Result

The comparison between LAST and several state-of-the-art ZSL approaches on four small-scale benchmark datasets is summarized in Table 1, and the comparison on ImageNet is shown in Table 2 and Figure 2. It is clearly observed from the results that LAST outperforms the state-of-the-art ZS- L approaches with significant and consistent margin, which demonstrates the effectiveness of LAST for ZSL. Besides, we can also obtain the following observations from the results.

Firstly, among all approaches, LAST is the only one which does not use all images for training. In fact, since each class has only one class feature, it is not reasonable to use unrepresentative images to fit the class feature, which will result in biased model. LAST combines model training and landmark selection such that it is capable of finding the most representative images for model training. In this way, the model can focus on the most important and general properties for aligning heterogeneous spaces, making it perform better for ZSL.

Secondly, not only the conditional alignment which performs alignment for each class, LAST also takes into account the marginal distribution such that it can align heterogeneous feature spaces globally. This property is very important for ZSL. As introduced, ZSL is to build recognition model for previously unseen classes. Therefore, it is necessary that the ZSL model should generalize well. If only conditional distribution is considered, the model may pay too much attention to the details between image feature space and class feature space such that it does not well align two spaces. We notice that ZSL can be regarded as a alignment problem between image feature space and class feature space. Therefore, aligning them globally is essential for building an effective model. One may argue that image feature space and class feature space has zero MMD after feature centralization since W is a simple linear transformation. This is true in a usual case. However, with the landmark selection, it is not guaranteed that the weighted samples still have zero mean. Therefore, it is necessary to combining this term to the objective function.

4.3 Analysis

The parameter δ controls the power of landmark selection. It is interesting to investigate its influence on LAST. Here we use 2H and ALL of ImageNet for analysis. The top 1 accuracy of LAST with respect to different values of δ is shown in Figure 3. When δ is small (say, 0.1), the performance drops because too many images are ignored. In this case, the alignment between heterogeneous spaces is imperfect since too much information is lost. On the other hand, when δ is large (say, 1), the performance is worse than the best performance too. This phenomenon is very important to verify the motivation of LAST. When δ = 1, all images are used with the same weight and no landmark selection is performed. We can observe that any smaller value for δ leads to better performance than the case when δ = 1. This result clearly demonstrates the basic idea of LAST that selecting representative images, instead of using all indiscriminately, is beneficial for ZSL.

In addition, we propose to incorporate a marginal alignment term into LAST by minimizing a MMD loss. To investigate its effectiveness, we compare LAST to the version with only conditional alignment denoted as LAST-C. The comparison one four benchmarks and eight subsets of ImageNet is shown in Figure 4. It can be observe that the marginal alignment significantly and consistently promote the performance, which validates the efficacy of the marginal alignment.

5 Conclusion

In this paper we focus on ZSL. We notice that previous ZSL approaches are mostly based heterogenous feature matching and the matching/compatibility function is constructed from one-vs-all training in which each class feature is combined with all image features for loss computation. However, this operation seems unreasonable since some images may focus on details that the class feature does not reflects. Therefore, the mismatching between them leads to biased ZSL model. To address this issue, we propose a novel approach, termed as LAST. In particular, during model training, LAST simultaneously perform landmark selection which assigns different weights to different samples, aiming at finding the representative cross-domain data instead of using all. In addition, a marginal alignment term is incorporated into LAST to improve its generalization ability. LAST is capable of identifying representative cross-domain features which further lead to better image-class compatibility function. Experiments on several benchmark datasets including ImageNet demonstrate that LAST significantly outperforms the state-of-the-arts.

Acknowledgements

This work was supported by the National Key R&D Program of China (No. 2018YFC0807500), National Natural Science Foundation of China (No. 61571269, 61671196, 61525206), 111 Project (No. D17019), National Natural Science Major Foundation of Research Instrumentation of China (No. 61427808), National Postdoctoral Program for Innovative Talents (No. BX20180172), and the China Postdoctoral Science Foundation (No. 2018M640131). Email: yuchen.w.guo@gmail.com. Corresponding author: Guiguang Ding, dinggg@tsinghua.edu.cn.