Revisiting of the BT-inverse of matrices

1.   Introduction

Object recognition aims at detecting the objects and predicting the class label of a given image, which has been widely used in classification ^[1,2], localization ^[3,4,5,6,7], segmentation ^[8,9], retrieval ^[10,11,12] and natural language processing ^[13,14], etc. The significant advances have been reported in a large number of deep learning literatures ^{[15,16,17,18,19]}. Despite the exciting success, most methods proposed in those papers are based on supervised learning, which is driven by the availability of manually annotated instances with powerful low-level visual features ^[7]. However, the frequencies of objects in the wild follow a long-tailed distribution that consist of a few common classes and most rare classes ^[20]. On one hand, it is difficult for rare classes without sufficient representative labeled instances to train a classifier effectively. Moreover, it is extremely challenging to collect large-scale labeled instances, even if the performance of the model is improved by adding more instances. Taking the large-scale dataset ImageNet ^[21] as an example, it contains a total of 14M images in 21,841 classes. It is unrealistic to exhaustively annotate hundreds of instances for each class. On the other hand, the labeled instances of certain classes are precious and difficult to obtain significant amount of the corresponding annotated instances, e.g., endangered bird breed in fine-grained datasets, which is hard to annotate images without expert knowledge ^[22], let alone collecting instances. In addition, new objects emerge over time that are not covered by known classes and have no labeled instances beforehand, e.g., the high-quality radiology images of the patients infected by COVID-19 are not available before 2019. As a result, the conventional approaches cannot tackle above problems. There are increasing efforts to address the problem of insufficient or even no labeled instances, such as one-shot and few-shot learning ^[23] deal with the classes of few labeled instances; open world recognition performs the tasks: detecting the novelty of the test classes via open set recognition that was initially proposed by ^[24], progressively labeling instances of novel unseen classes by class-incremental learning, and adapting the model to classify the acquired labeled instances ^[25]. The above-mentioned techniques reduce the dependence on labeled instances and improve the accuracy, but still require at least some labeled instances for model learning. Unfortunately, the aforementioned strategies fail to determine the class labels of the instances belonging to unseen classes that have no labeled data.

In contrary, humans have the ability to recognize unseen classes by intelligently utilizing the previously learned knowledge extracted from the seen classes. For example, a learner can easily recognize the Persian fallow deer, if he/she has ever seen fallow deer and is aware that it resembles the fallow deer with bigger antlers and white spots around the neck. Therefore, they are capable of distinguishing beyond 30,000 objects ^[26] as well as varieties of the subordinates. Inspired by the mechanism of human's ability to recognize new objects without seeing all classes in advance, Zero-Shot Learning (ZSL) ^{[27,28,29,30,31]}has drawn significant attention and is proposed to recognize the entirely novel classes omitted from training instances by extrapolation from the knowledge contained in the observed classes ^[32]. More specifically, given labeled training instances of seen classes in the source domain, ZSL aims to establish a model to classify the instances of unseen classes in the target domain, which increasingly reduces the resources in labor and time expenses. In addition to computer vision related to images, the applications of ZSL has been emerging in various fields, such as zero-shot translation ^[33], bilingual dictionary induction ^[34] and molecular compound analysis ^[35].

In the absence of the labeled instances of unseen classes, the key idea underpinning ZSL methods is to explore the knowledge that transfer via shared auxiliary information. Seen classes are associated with unseen classes in a common space, i.e., semantic space, and the high-level semantic representations are considered as auxiliary information among these classes. Thereby, they can act as a bridge to guarantee the feasibility of ZSL. Generally, there are multiple types of semantic information: attributes ^[36], word vectors ^[37,38,39], textual descriptions ^[40], hierarchical ontology ^[41,42], etc. The commonly used semantic space nowadays is attribute space ^[27]. Each class is endowed with a unique semantic prototype ^[43] in this space. The prototype is specified by a binary or continuous attribute vector that indicates the class properties manually designed by experts. The relatedness of the classes is represented by the similarity of the semantic prototypes, e.g., the semantic prototype of zebra is closer to that of horse instead of pig, which is agreement to the reality that zebra is semantically related to horse. Therefore, ZSL can learn a model properly with the aid of semantic representations. Most existing ZSL approaches ^{[27,40,41,44,45,46]} exploit a visual-semantic projection to reflect the relationship among the classes. Specifically, the projection is learned to map the low-level visual features of the labeled instances consisting of seen classes only to semantic space during training. At test stage, the learned projection function is applied to map the target instances of unseen classes to the same semantic embedding space where seen and unseen classes reside. Then, the similarities of the predicted semantic presentations and prototypes are measured by certain matric. Employing the nearest neighbor (NN) search, the classification of the target instance is realized by aligning the semantic prototype of unseen class that yields the highest score.

Despite the success of those semantic embedding models, the largest challenge in ZSL is the projection domain shift problem ^[43] among the disjoint seen and unseen classes and is manifested through the following aspects. On the one hand, the visual feature space is mutually independent of semantic space, and they have distinct distributions. Hence, there is great difficulty in learning an effective and compatible projection function between the two spaces. On the other hand, the visual appearance of the same attributes in seen and unseen classes are fairly different. The discrepancy is analyzed empirically in ^[43]. It can be seen that shared characteristic "has tail" in target unseen class Pig is visually different from the source seen class Zebra. Thus, there are significant differences in the underlying distributions of the classes that leads to poor performance on novel classes. In other words, if the projection functions learned with the training instances in seen classes are directly adopted to the unseen classes without adaptation, the target instance tends to be shifted far away from the corresponding class prototype, resulting in the unsatisfactory recognition by NN search at test stage.

There is a recent surge of interest in building a better generalizable projection function on the novel classes to be less susceptible to domain shift. Firstly, a large volume of the literatures belongs to inductive setting are published to overcome this problem ^{[27,32,47,48,49]}. The most representative one is SAE ^[48] and it learns the linear projection function from visual feature space to semantic space based on auto-encoder paradigm, in which the decoder is the transpose of encoder and imposed by a reconstruction constraint of the original visual features. However, inductive methods only have access to the seen data, the projection is likely to capture the characteristics of the seen classes rather the unseen ones. As a result, it hinders the effective generalization. Secondly, the generative models are proposed to compensate for the visual features of target unseen data. The two prominent members are Generative Adversarial Networks (GANs) ^{[50,51,52,53,54]} and Variational Auto-Encoders (VAEs) ^[55] that synthesize visual features by utilizing the semantic prototypes of unseen classes. While, it is noticed that the choice of the semantic prototype is essential, as low quality may degrade the effectiveness of the generator. Afterwards, various methods resort to transductive learning ^{[43,56,57,58,59,60,61,62]} leverage the unlabeled target instances during training. The existing transductive learning methods are classified into three categories. The first one is label propagation. For example, Fu et al. ^[43] combines multiple semantic representations with visual features of unseen classes to learn a joint embedding space, in which the target data are aligned with the label embeddings and then the recognition is performed via label propagation. The second one is self-training that progressively improves the classification capacity in an iterative refining process ^[59]. The last one termed domain adaptation is the most relevant method to our model and has been well-investigated to uncover the common knowledge of the source and target domains ^[63,64,65]. Different from the above first two strategies, ^[65] simultaneously utilize the visual features and semantic prototypes of unseen classes, our model only utilizes the visual features of the unlabeled instances. Furthermore, our model is not concerned with the distribution alignment of the projected and original domains ^[63] or that of the features in the immediate space ^[64], whereas the latent space in our model is semantically meaningful and encourages learning the generalizable semantics containing sufficient information of the visual features through a reconstruction task.

In this paper, we develop a novel model by exploiting the idea of autoencoder framework to solve zero-shot challenges and reveal the relationship between visual features and semantic representations. We assume that the majority semantic properties of the unseen classes are shared with that of seen classes. Following the previous work, we adopt the semantic space as the latent embedding space to preserve the semantic relatedness between the classes. Motivated by ^[48,63], our model takes advantage of the bi-shifting linear auto-encoder framework. In specific, the common encoder shared by source and target domains tries to learn the projection from visual feature space to semantic space. Considering the distribution divergence of the disjoint domains, the original features are reconstructed by two different decoders based on the learned semantic representations. It is worth mentioning that there are two regularization terms in our model. Inspired by ^[48], the first term is designed to inherit the properties of semantic space by incorporating the semantic prototypes of the seen classes and then the projections are constrained to force the learned semantics of unlabeled target instances as close as possible to their class prototypes. Consequently, the semantic mismatch between visual features and semantic representations can be refined. The second regularization term is adopted to enforce that the decoder in target domain is derived from, rather than the same as the decoder supervised learned via semantics of instances in source domain, resulting in truthfully reconstruct the visual features. To that end, we design a novel Bi-shifting Semantic Auto-Encoder (hereafter referred as BSAE) architecture that integrates the merits of both domain adaptation and discriminative ability of class semantics, as shown in Figure 1. However, BSAE is based on linear auto-encoder and quite shallow, experimental results reported in section 4 prove its outstanding performance. For example, the average accuracy on five benchmark datasets under different protocols are whopping 6.9% improvement over the current state-of-the-art. In conclusion, the main contributions are three-fold:

● A simple and effective ZSL model termed BSAE is developed in an auto-encoder framework. Our model not only alleviates the domain shift problem, but also recovers the interaction between visual feature and semantic representation.

● We consider ZSL as the problem of learning the projection functions to explore shared discriminative semantic representations of instances, which are supervised by the semantic prototypes of the seen instances. Meanwhile, the generalizable capability of the learned semantics are enhanced by exploiting the visual features of unlabeled instances.

● An iterative algorithm with high computational efficiency is introduced to solve the problem. Extensive experimental results demonstrate that our approach achieves superior performance on five benchmark datasets, even if the class prototypes of the unseen classes are not available.

The remainder of the paper is organized as follows. In Section 2, we briefly review the related work proposed to overcome the challenges in ZSL. In Section 3, we describe the proposed model and deduce an efficiently iterative algorithm. The results are reported and discussed in Section 4. Finally in Section 5, we present the conclusion and propose several research directions to be investigate.

2.   Related work

In this section, we firstly introduce a review about the semantic space exploited in current zero-shot learning. Then, we briefly review of projection learning concerned with our work. Finally, we present the related advances to relive the domain shift problem.

2.1.   Semantic space

Semantic representation shared between classes bridges the gap in ZSL and enables the transmission of common knowledge from seen to unseen classes. There are various semantic spaces formed by different class embeddings. Attribute space ^[27] is the most popular and effective one ^[46,66,67], in which the properties of the classes are described as attributes. However, manually collecting and annotating attributes are heavy reliance on the efforts of experts. The word vector ^[38,39] and text description ^[40] based semantic space are proposed because of relatively less labor intensive. The semantic representations are automatically extracted by embedding models from text corpus (e.g., Wikipedia). In spite of the inconvenience for humans to incorporate the knowledge of the classes into the semantics, as reported in ^[40], 10 sentence descriptions are collected for each image to construct the semantic space, which is even more expensive than annotating attributes. Moreover. SJE ^[41] and ESZSL ^[47] have shown that attribute space is more effective than word vector space. Besides, several ZSL methods take advantage of them via combining the aforementioned semantic spaces ^[50,60,68]. In our work, we consider the attribute space as semantic space.

2.2.   Projection learning

The existing ZSL models can be sub-categorized into three groups, depending on how the projection function is established.

2.2.1.   Visual-semantic projection

The first group learns a forward projection from visual feature space to semantic space. Lampert et al. ^[27] proposed two attribute-based classifiers includes direct attribute predictor (DAP) and indirect attribute predictor (IAP) that exploit the attributes to predict the class labels of instances in a two-stage schema. SOC ^[32] firstly projects the visual features into the semantic space, and then determines the class label through KNN. CONSE ^[37] exploits a probabilistic model and then predicts the unseen classes via the convex combination of the class-embeddding vectors. DeViSE ^[38] applies linear corresponding function by combining similarity and hinge ranking loss. ESZSL ^[47] learns the bilinear compatibility function by optimizing square loss. To optimize the ranking loss, ALE ^[58] employs a bilinear mapping compatibility function.

2.2.2.   Semantic-visual projection

The second group learns a reverse projection from the semantic space to the visual space to rectify the hubness problem ^[69]. The hubness refers to the phenomenon of some semantic prototypes are nearest neighbors of instances from different classes, which is a curse of demensionality. Zhang et al. ^[70] proposed a deep end-to-end neural network to embed the class prototypes into the visual feature space that suffer much less from the hubness problem, as discussed in ^[71]. In addition to the embedding models, generative-based methods are proposed recently to generate instances for unseen classes by leveraging the semantic prototypes, then the ZSL problem is converted into a traditionally supervised problem. f-CLSWGAN ^[50] and LisGAN ^[68] explore the conditional generator on semantics to synthesize the visual features. However, it is hard to train generative models because of the min-max optimization. Auto-encoder is an effective framework to extract the representative features in a unsupervised manner and alleviate the domain shift problem. Xu et al. ^[52] construct visual feature space as latent layer and learns two different regressors for semantic reconstructions. The latent layer of ^[48] is semantic space and the linear projection between the visual feature and semantic space is learned with the semantic constraint of seen classes to reconstruct the original data. ^[72] improves the model in ^[48] by adding a regularization constraint of the projection function, thereby ensuring that the structural risk of the model is minimized.

2.2.3.   Immediate projection

In the last group, both visual features and semantic representations are projected into a common space. SYNC ^[49] learns classifiers of unseen classes by linearly combining base classifiers. Zhang and Saligrama ^[67] leverage similar class relationships in the common space, which is defined by the seen classes proportions.

Taking full advantage of the first two groups, our model is close to ^[63] in which a bi-shifting auto-encoder is employed for reconstructing visual features in different domains. Different with ^[63] that apply nonlinear projections to learn the representations in latent space, our model reinforces the latent space as semantic space with class semantic prototypes and exploits the linear projection functions to fit the distributions of visual and semantic spaces, respectively.

2.3.   Domain shift problem

Domain shift problem was firstly reported in ^[43] and is an open issue in ZSL. It describes that the projection functions learned from the seen classes are biased when exploit them to map instances of unseen classes from visual feature space to semantic space. It is essentially caused by the disjoint seen and unseen classes with different underlying data distributions. The researchers have investigated how to rectify the domain shift problem and obtain competitive results, for instance, SAE ^[48] imposes an additional reconstruction constraint to the training seen data, resulting in the learned projection function more generalizable across seen and unseen classes. LisGAN ^[68] refines the domain shift via generating the soul instances related to the semantic representations. However, as the unseen class data are not involved in the model learning, the generalizable ability of the inductive methods is limited. Transductive ZSL is an emerging topic to mitigate the domain shift problem where not only labeled seen class data are available, but also has access to unlabeled unseen class data, which potentially leads to improvements in classification performance. Fu et al. ^[43] first propose a transductive multi-view embedding framework, and then generate the class labels for unseen class data via label propagation. Kodirov et al. ^[65] formulate a regularized sparse coding framework to solve the domain shift problem. A measure of inter-class semantic consistency is proposed by ^[73] to explore the relation between the semantic manifold and visual-semantic projection on seen classes. VCL ^[56] proposes a visual structure constraint on class centers. Unlike SAE ^[48] exploits one decoder to reconstruct the features without domain adaptation, our model employs transductive setting and adopts two decoders to reconstruct the visual features in the source and target domains. Additionally, we restrict the similarity constraint of the two different decoders as a regularizer by considering the amount of adaptation from the labeled seen class data rather than being deviated freely. Although we only use the visual features of unseen data rather than the combination of the visual features and semantic representations of target unseen data like others ^[41,70], our model boosts ZSL performance.

3.   Methodology

In this section, we describe the procedures and methods used in this paper. we firstly set up the zero-shot learning problem, then develop our novel model BSAE for this task, and finally derive an efficient algorithm to solve it. Subsequently, the classification of unseen classes can be performed in the original feature space and semantic space.

3.1.   Problem definition

We start by introducing some notations and problem definition of our interest. Considering $m$ labeled source instances $\mathcal{S} = \{(x_{i}^{s}, y_{i}^{s}, s_{i}^{s})|x_{i}^{s} \in\mathcal{X}, y_{i}^{s}\in\mathcal{C}_{s}\}_{i = 1}^{m}$ are given as training data, where $x_{i}^{s} \in \mathbb{R}^{d}$ denotes the $d$-dimensional visual feature, $y_{i}^{s}$ is the corresponding class label in $\mathcal{C}_{s}$ consisting of $\tau$ discrete seen classes, $s_{i}^{s}$ is the semantic representation of $i$th instance. In addition, given $p$ unlabeled target data $\mathcal{T} = \{(x_{i}^{t}, y_{i}^{t}, s_{i}^{t})|x_{i}^{t}\in\mathcal{X}, y_{i}^{t}\in\mathcal{C}_{t}\}_{i = 1}^{p}$ of unseen classes, where $x_{i}^{t} \in \mathbb{R}^{d}$ denotes the $d$-dimensional visual feature, $y_{i}^{t}$ is the corresponding label and belongs to the $\mu$ unseen classes set $\mathcal{C}_{t}$. While the seen and unseen classes are disjoint, i.e., $\mathcal{C}_{s}\cap\mathcal{C}_{t} = \emptyset$, the semantic space $\mathcal{A}$ are associated with mitigating this challenge, which is spanned by attribute vector or word vector derived from text for each class. The $k$-dimensional semantic prototypes of seen and unseen classes are denoted as $A_{s} = [a_{1}^{s}, a_{2}^{s}, \ldots, a_{\tau}^{s}] \in \mathbb{R}^{k \times \tau}$ and $A_{t} = [a_{1}^{t}, a_{2}^{t}, \ldots, a_{\mu}^{t}] \in \mathbb{R}^{k \times \mu}$. Therefore, $S_{tr} = [s_{1}^{s}, s_{2}^{s}, \ldots, s_{m}^{s}]\in \mathbb{R}^{k \times m}$ is given because the source data $X_{s} = [x_{1}^{s}, x_{2}^{s}, \ldots, x_{m}^{s}]\in \mathbb{R}^{d \times m}$ are labeled by either binary or continuous attributes indicating the corresponding class labels $Y_{s} = \{y_{i}^{s}\}_{i = 1}^{m}$. On the contrary, as the target instances $X_{t} = [x_{1}^{t}, x_{2}^{t}, \ldots, x_{p}^{t}]\in \mathbb{R}^{d \times p}$ are unlabeled, $S_{te} = [s_{1}^{t}, s_{2}^{t}, \ldots, s_{p}^{t}]\in \mathbb{R}^{k \times p}$ that stands for the semantic prototypes and $Y_{t} = \{y_{i}^{t}\}_{i = 1}^{p}$ that denotes the class labels have to be predicted.

The goal of standard zero-shot learning is to predict the correct class of $X_{t}$ by learning a classifier $f: \mathcal{T} \rightarrow \mathcal{C}_{t}$. The key notations used in this paper are listed in Table 1.

3.2.   Model formulation

We begin our discussion with auto-encoder (AE) for it being the basis of our model. The simplest form of AE is linear and has one hidden layer ^[48] that is responsible to truthfully reconstruct the input data as similar as possible. We force the semantic space in hidden layer as ^[48] so that the latent space is semantically meaningful, e.g., each column of $S_{tr}$ stands for the attribute vector of the corresponding labeled source instance.

Assume that labeled seen-class training set $\mathcal{S}$ and unlabeled target data $X_{t}$ are available. The proposed BSAE aims to learn a model to estimate the discriminative semantic representations $S_{te}$ and reconstructed features $\hat{X}^{t}$ of the target instances and then obtain their class labels $Y_{t}$ in semantic space and visual feature space, respectively. Specifically, considering the seen classes and unseen classes are related in the same class embedding space (e.g., attribute), BSAE consists of three components: (1) It attempts to learn the encoder parameterized by $W_{0}\in \mathbb{R}^{k\times d}$ ($k < d$) to project both domains from visual feature space $\mathcal{X}$ to the common semantic space $\mathcal{A}$. In order to guarantee whether the learned semantic representations capture sufficient discriminative information, in terms of the distribution discrepancy between domains, (2) on one hand, the decoder $W_{1}\in \mathbb{R}^{d\times k}$ reconstructs the original visual features of source domain exactly. (3) On the other hand, the mapped class embeddings of target domain are projected to the visual features by decoder $W_{2}\in \mathbb{R}^{d\times k}$. We simultaneously minimize the reconstruction errors in different domains by utilizing the unlabeled instances from unseen classes to narrow down the domain gap. Therefore, it is applicable to better generalize the learned regression model to unseen classes. As observed from Figure 2, our model preserves enough discriminative information across unseen classes, even in the low dimensional semantic space that exacerbates the hubness problem.

Our model is learned by optimizing the following objective:

where $\|\cdot\|_{F}$ is the Frobenius norm of a matrix. Eq 3.1 denotes the loss of the autoencoder. It is difficult to solve the objective Eq 3.1 with a hard constraint. To fight off the constraint $W_{0}X_{s} = S_{tr}$ efficiently, we relax the constraint through incorporating a semantic similarity term into Eq 3.1:

and $\lambda_{1}$ is the hyper-parameter. The first two terms are regarded as the losses of different decoders. The last term is the loss of encoder. $W_{2}$ is unsupervised because of the unknown semantic representation $S_{te}$ of target data and ^[65] proves that $W_{2}$ adapted from $W_{1}$ is efficient to this issue. To this end, we adds the regularization term $\|W_{2}-W_{1}\|_{F}^{2}$ to Eq 3.2 to restrict the amount of adaptation of the two projections. It is worth noting that $W_{1}$ is considered as a basis to ensure $W_{2}$ cannot deviate freely from $W_{1}$. The full objective of our proposed model then becomes:

where $\lambda_{2}$ is a hyper-parameter used to balance the importance of different terms.

3.3.   Optimization

Next, we will formulate our solver as a novel gradient-based algorithm to alternately update projection functions $W_{0}$, $W_{1}$ and $W_{2}$. Note that the conventional iterative algorithms (e.g., Gradient Descent) have been widely exploited to directly solve such problems without computationally efficiency. Whilst our solver depends on the dimension of the features, not the number of instances and hence is more effective than the conventional iterative algorithms. To solve the Eq 3.3, we calculate the partial derivative of it and set it to zero:

and optimize the following sub-problems through alternative optimization methods.

3.3.1.   Fix $W_{2}$, update $W_{0}$

Setting Eq 3.4 to zero, we obtain:

Let $M_{0} = W_{2}^{T}W_{2}, H_{0} = \lambda_{1}X_{s}X_{s}^{T}(X_{t}X_{t}^{T})^{-1}, Q_{0} = W_{2}^{T}+\lambda_{1}S_{tr}X_{s}^{T}(X_{t}X_{t}^{T})^{-1}$, we have the Sylvester equation:

where $M_{0}\in \mathbb{R}^{k\times k}$ and $H_{0}\in \mathbb{R}^{d\times d}$ are square matrices, $Q_{0}\in \mathbb{R}^{k\times d}$ is a rectangle matrix. The above matrix function has a unique solution if it satisfies conditions of the Theorem 3.1 quoted in ^[74]. Obviously, it is easy to meet in practical applications.

Theorem 3.1. Eq 3.8 has a unique solution if and only if the matrices $M_{0}$ and $H_{0}$ have distinct eigenvalues, that is, the eigenvalues $\gamma_{1}, \gamma_{2}, \ldots, \gamma_{k}$ of $M_{0}$ and $\zeta_{1}, \zeta_{2}, \ldots, \zeta_{d}$ of $H_{0}$ satisfy $\gamma_{i} + \zeta_{j} \neq 0$ ($i = 1, ..., k; j = 1, ..., d$).

As a result, Eq 3.8 can be easily solved by Bartels-Stewart algorithm, which is implemented with a single line of code: sylvester in MATLAB:

3.3.2.   Fix $W_{2}$, update $W_{1}$

Setting Eq 3.5 to zero, then we have the following Sylvester equation:

Let $M_{1} = \lambda_{2}I_{k}$, $I_{k}$ is the $k\times k$ identity matrix, $H_{1} = S_{tr}S_{tr}^{T}$, $Q_{1} = X_{s}S_{tr}^{T}+\lambda_{2}W_{2}$. The Eq 3.10 can be efficiently solved in MATLAB:

3.3.3.   Fix $W_{1}$, $W_{0}$, update $W_{2}$

Similarly, we set Eq 3.6 to zero, and have the following formulation:

If we denote $M_{2} = M_{1}, H_{2} = W_{0}X_{t}X_{t}^{T}W_{0}^{T}, Q_{2} = X_{t}X_{t}^{T}W_{0}^{T}+\lambda_{2}W_{1}$, the above Sylvester equation (3.12) can be solved in MATLAB:

Algorithm 1 summarizes the implementation of our algorithm. We simply initialize $W_{2}$ with all elements of 0.1 for coarse-grained datasets (e.g., AWA1) and all elements of 0.01 for fine-grained datasets (e.g., CUB). The hyper-parameters $\lambda_{1}$ and $\lambda_{2}$ are selected by cross-validations. Details are listed in section 4. The iterations will terminate when the Eq 3.3 converges or reaches a fixed number of iterations.

3.3.4.   Complexity and convergence analysis

To this end, we propose to briefly explain the analysis of the time complexity and convergence of our algorithm. As mentioned in Algorithm 1, optimizing the objective function Eq 3.3 is actually the process of solving three Sylvester equations. The time complexity of computing each Sylvester equation, e.g., Eq 3.8, given $M_{0}$ and $H_{0}$, is $\mathcal{O}(k^{3}+d^{3})(d, k\ll \min (m, p))$, which is independent of number of instances. In other words, it can be effectively applied to large-scale datasets. As can be observed from Eq 3.7 to Eq 3.13, due to linear formulations, it is easier to solve three sub-problems with respect to three projection functions $W_{0}$, $W_{1}$ and $W_{2}$ in our proposed model. Concretely, updating each projection function is regarded to solve Sylvester equation. Hence, the objective function Eq 3.3 is non-increasing with a lower bound during the alternative optimization.

3.4.   Classification

According to Algorithm 1, we obtain the optimal projection functions $W_{0}$ and $W_{2}$. We measure the similarity score between the estimated value of target instance and its prototype, and then predict the class label.

In the semantic space, considering a target instance ${x}_{i}^{t}$, we could firstly calculate the estimated semantic representation with $({S}_{te})_{i} = W_{0}x_{i}^{t}$, then compare with the prototypes ${A_{t}}$ of classes in $\mathcal{C}_{t}$ by calculating the cosine distance between them:

where $j\in [\mu]$, $({A_{t}})_{j}$ is the prototype attribute vector of $j$–th unseen class and $d(\cdot, \cdot)$ is a distance function. $l(\cdot)$ returns the class label of a target instance.

In the feature space, it is worth mentioning that the predicted visual features $\hat{X}^{t}$ of unseen classes are easily synthesized by embedding the semantic prototypes of $\mathcal{C}_{t}$ to the visual feature space with $\hat{X}^{t} = W_{2}{A_{t}}$. Hence, the ZSL is converted to a conventional classification problem. Empirically, any supervised classifier can be utilized. We simply exploit k-Nearest Neighbor (KNN) to demonstrate the capability of our decoder $W_{2}$. Similar to the process in 1), the class label of target instance can be inferred by calculating the cosine distance between the prototype projections and the original visual feature $x_{i}^{t}$:

where $\hat{X}_{j}^{t}$ is the $j$–th unseen class prototype projected into the visual feature space.

4.   Experiment

In this section, we firstly introduce our experimental protocols in detail, then we present our results that are compared with the state-of-the-art approaches on five small-scale benchmark datasets (AWA1, AWA2, CUB, SUN, aP & Y) for conventional zero-shot learning (CZSL) task.

4.1.   Experimental setup and metrics

4.1.1.   Datasets

Five benchmark datasets are selected from the widely used datasets for ZSL: AwA1 (Animals with Attributes 1) ^[27], AWA2 (Animals with Attributes 2) ^[75], aP & Y (Attribute Pascal and Yahoo) ^[76], CUB (Caltech-UCSD-Birds 200-2011) ^[22] and SUN (Scene UNderstanding) ^[77]. We exploit two typical protocols to evaluate the performance of our model: standard splits (SS) ^[27] and proposed splits (PS) ^[75]. More concretely, SS is widely used in previous works, but the weakness is that unseen classes are subset of ImageNet during training, resulting in violating the true zero-shot rule. On the contrary, PS ensures that none of the unseen classes used for pre-training the ResNet belong to 1K classes of ImageNet. The fact that PS is much more difficult than SS on account of low correlation between seen and unseen classes. For clarity, the statistics of these datasets are briefly reported in Table 2.

We take advantage of semantic space spanned by continuous attributes like the pioneering works ^[27,47,48]. Each instance is associated with the corresponding continuous class-level attribute. The dimension of the semantic space equals to that of the attributes, e.g., the semantic space of AWA1 is formed by 85-dim attributes. The dimensions of the attributes of all datasets are listed in Table 2.

4.1.2.   Visual feature space

Following the general procedure in other literatures, we use visual features extracted by deep convolutional neural networks (CNNs) and GoogleNet features ^[78] which is the 1024-dim activation of the final pooling layer as in ^[41]. Furthermore, the latest works adopt the pre-trained 2048-dim ResNet features, which are extracted by 2048-dim top layer pooling units of the 101-layered ResNet, to achieve improved performance ^[75]. It is worth noting that the ResNet features has two protocols, namely, SS and PS. For GoogleNet features, only SS is provided. For fair comparison, we do not perform any image pre-processing or any other data augmentation techniques, and conduct extensive experiments on the above two types of features.

4.1.3.   ZSL settings

To demonstrate the capability of BSAE, we evaluate on the conventional ZSL (CZSL) setting: Assume that the search space is restricted to the unseen classes, the goal is to predict the class labels of $\mathcal{C}_{t}$ at test stage. We use SS and PS protocols in this setting.

4.1.4.   Parameter settings

Our BSAE model has two hyper-parameters: $\lambda_{1}$ and $\lambda_{2}$ (see Eq 3.3). We select $\lambda_{1}$ and $\lambda_{2}$ from $\{10^{-2}, 10^{-1}, 1, 10, 10^{2}, 10^{3}, 10^{4}\}$ for cross-validation. Considering the two split protocols, we propose tuning these parameters in different ways. For SS protocol, the parameters are chosen by means of class-wise cross-validation on $\mathcal{C}_{s}$ as in ^[67], that is, two seen classes are randomly selected form a validation set in each iteration to choose the best hyper-parameter $\{ \lambda_{1}$, $\lambda_{2}\}$ and use them for testing on unseen classes. For PS protocol, we perform hyper-parameter search on a disjoint set of validation set of 13 (AWA1/AWA2), 5 (AP & Y), 50 (CUB) and 65 (SUN) classes respectively ^[75]. Note that we report the average performance for ensuring the significance of the results.

4.1.5.   Evaluation metric

Most ZSL methods use Top-1 accuracy (e.g., ^[48]) averaged for all images, where the prediction is correct for the predicted class is coincide with ground-truth. However we are concentrated on high performance of both densely and sparsely populated classes. Therefore, under CZSL setting, we evaluate our method on the benchmark datasets by using per-class top-1 accuracy proposed in ^[75]. We compute the top-1 accuracy independently for each class, and then average for all unseen classes:

4.2.   Comparative results

We evaluate our proposed framework for zero-shot learning on several benchmark datasets. The competitors are representative, competitive state-of-the-art and recently published that encompass a wide range in zero-shot learning.

4.2.1.   Zero-shot learning

In these experiments, the test instances only come from $\mathcal{C}_{t}$ disjoint with the seen classes $\mathcal{C}_{s}$. We use both SS and PS protocols for more convincing results and the qualitative results are shown in Table 3 and Table 4.

For SS protocol, the SAE ^[48] is close to our model while lacks of the results of per-class top-1 accuracy with GoogleNet features. For fair comparison, we recreate SAE by following the settings in their original paper and exploit the same classifier to predict the class labels. Leveraging the code available online, we re-implement GFZSL ^[62] and SYNC ^[49] to obtain the recognition results. Note that the first 10 methods in Table 3 are cited from ^[75] and the rest are copied from the original paper. To further verify that our method is not only effective to specific visual features, we implement our model under the SS protocol with 1024-dim GoogleNet features (G) and 2048-dim ResNet features (R).

From comprehensive comparison in Table 3, we witness that: (1) our model achieves the best four of the five evaluations, i.e., AWA1, AWA2, SUN and aP & Y. Specifically, the improvements over the strongest competitor achieve 0.7%, 0.4% and 6.9% on AWA1, AWA2 and aP & Y. For fine-grained dataset SUN that contains more classes and relatively fewer instances per class, while our result of 67.1% is 2.8% higher than the strongest competitor ^[60]. The accuracy boost can be attributed to the combination of semantic representations and domain adaptation constraints significantly improving the ability for classification. (2) Meanwhile, from Figure 3, we can observe that the overlap between unseen classes of CUB, which is regarded as the well-known complicated dataset, is particularly striking. Moreover, it is hard to learn the visual-semantic projection for the reason that the sparsity of training instances ($\sim$ 60 instances per class). However, our model still performs well on this dataset. It is worth pointing out that our model learns a more effective and stable visual-semantic relation from seen data for unseen data analysis. (3) ^[73] and ^[75] demonstrate that VggNet and ResNet features lead to improved results in ZSL than GoogleNet features. While our model using GoogleNet features consistently performs favorably against state-of-the-art on the five benchmarks, especially the best result of 91% on AWA1 and 67.1% on SUN. This provide further evidence that our model achieves good performance on coarse-grained and fine-grained datasets even if the features are not the strongest.

For PS protocol, we keep the same setting as in ^[75] to make sure the unseen classes at test time do not overlap with the 1K training classes of ImageNet. The first 12 reported results are cited from ^[75] and others copied from their original paper. Generally, the performance is expected degrade under this stricter settings. From the comparative results listed in Table 4, we can make the observation that the average top-1 per-class accuracy of our model performs 4.8% higher than all others and drops least on coarse-to-fine grained datasets among all methods, which illustrates more significant. Due to the similar idea between auto-encoder and GAN-based model, we compare several representative methods, e.g., LisGAN ^[68] and SRGAN ^[53]. Our model outperforms these competitors on four of five datasets, while 3.6% less than SRGAN ^[53] under the challenging split of SUN. We conjecture that our regression model is over-fitted in terms of scarce training instances of each class.

It is noting that there is no single approach claims the best results on all datasets simultaneously ^[60]. The aforementioned improvements actually create new baselines in the area of ZSL, given that most of the compared models utilize more complicated nonlinear formulations and some of them combine complementary semantic spaces or even generate richer features for unseen classes. In contrast, we apply only one type of semantic space as well as computational fast linear projection functions, but gain a significant performance boost.

4.2.2.   Zero-shot retrieval

We aim to evaluation the effectiveness of the decoder of BSAE via the image retrieval task, which is defined as searching top matched images by taking the provided semantic prototypes of unseen classes as queries. The ratio of the number of accurately retrieved images to that of all retrieved images, namely precision, is regarded as the measurement. Table 5 reports 5 out of 50 classes in CUB and 5 out of 65 classes in SUN and depicts the qualitative results of our designed model with highest anterior and posterior scores for each unseen class. Specifically, each column is a category, with class name and precision are shown at the top. The first three rows in the middle are the top-3 correctly retrieved instances. The following three rows are the top-3 misclassified instances in each unseen class. Observing form the top correct images, BSAE reasonably captures discriminative visual information only using its semantic prototype. It suggests that the adaptation regularization helps make approxiamate inference of unseen instances. Meanwhile, taking the class in the second column as an example, Pomarine Jaeger and Rhinoceros Auklet are visually similar to Pacific Loon, the discriminative ability of the decoder is not enough to distinguish the visual appearances between them. Due to the strong visual similarity and only a few different attributes among the classes, we further notice that it is hardly recognize these classes without expert knowledge, even for humans.

4.3.   Further evaluation

4.3.1.   Visualization

For straightforward illustration of BSAE in ZSL. We explore t-SNE visualization ^[83] to compare the visual features with genuine class label (left) and semantic representations with the predicted class labels (right) in Figure 4. Each color represents clustering in the same class and all the features are embedding into two dimensions using t-SNE. It suggests that our model captures the underlying global distribution in the semantic space and performs better on the dataset. It is worth that our model alleviates the hubness problem in the lower dimensional semantic space. Moreover, the instances of the same class are grouped into one cluster in Figure 4, which confirms that the discriminative semantic representations learned by our model are able to cluster visually similar instances. Therefore, our proposed model preserves the local information of target unseen classes that the closeness are kept in the projected semantic representations.

The ROC curve and AUC value depict the tradeoff between specificity (False Positive Rate) and sensitivity (True Positive Rate) as a metric of the performance of our proposed BSAE. Figure 5 shows the results of the ROC curve and AUC value on AWA1 under PS protocol. We can observe that the ROC curve of the 10 unseen classes are close to the top-left corner of the plot, even though using the simplest KNN classifier.

We observed that almost all methods performed worst on aP & Y compared to other datasets. In order to show our experimental results in a more fine-grained manner, we take the PS protocol of aP & Y dataset as an example, compared with the best competitor LisGAN ^[68]. Figure 6 shows the confusion matrix of LisGAN and our model i.e., BSAE on the 12 unseen classes. The value in the diagonal of the confusion matrix indicates the ratio of the correctly predicted of each class. The darker color represents the higher class-wise accuracy. It can be seen that BSAE generally performs better on the most classes. Concretely, we boosts 38%, 10%, 24%, 49%, 41%, 3% and 3% on "horse", "motorbike", "person", "sheep", "goat", "jetski" and "statue" against LisGAN respectively. Although the GAN model directly handle zero-shot problem by converting it to a supervised task, we find that our model perform better than GAN-based model, i.e., LisGAN. In addition, it is common that one model does not have the highest accuracy on each unseen class. There will be great improvement in the future.

We measure the inter-class and intra-class distances to investigate BSAE can alleviate domain shift and hubness problem. We follow the two measurements provided by ^[84]:

Where $n_{c}$ represents the data size of the $c$th class. $C$ means the number of the classes. $\varphi(\cdot)$ and $\psi(\cdot)$ denote the two dimensional outputs of t-SNE ^[83]. $D(\cdot)$ is the cosine distance, which reflects the degree of similarity between actual and the compared one ^[81]. $D_{intra}^{c}$ stands for the mean distance between the $c$th class prototype $A_{c}$ and semantic representations of instances in that class. $D_{inter}^{c}$ stands for the mean distance between the $c$th class prototype $A_{c}$ and all other classes. We compare our proposed model with TSTD ^[59], which is the best competitor under SS protocol on AWA1 dataset. For consideration of fairness, we re-implement the experiments of the two methods under the same settings in AWA1, i.e., use ResNet-101 features and take continuous class-level attributes as semantic representations. Different from TSTD ^[59] that applies the attributes of unseen classes during training to improve the performance, BSAE obtains smaller intra-class distances and larger inter-class distances with a large margin as illustrated in Table 6. Thus, BSAE is capable of alleviate domain shift problem as well as hubness problem in lower dimensional semantic space.

4.3.2.   Complexity and convergence analysis

In this section, we analyze the complexity and convergence of BSAE. It is remarkable that the operation of Algorithm 1 mostly comes from matrix multiplication. Obviously, it can accelerate the training process greatly. Additionally, we set 200 as the maximum iterations. The F-norm of the parameter variation with respect to the iteration on fine-grained datasets are reported.

From Figure 7a, it is notable that our model reaches 80% of the accuracy within 4 iterations and is close to the highest accuracy around 10 iterations on coarse-grained dataset, e.g., AWA1 and around 20 iterations on fine-grained datasets. These demonstrate that our algorithm has a good practical application for its low complexity and good performance.

Figure 7b and 7c shows that the algorithm converges within 40 iterations. It is obvious that the decoder $W_{2}$ of the target domain is well restricted by the decoder $W_{1}$ of the source domain, which verifies the significance of the adaptation regularization. Moreover, these observations finally support the theoretical analysis of complexity and convergence in Section 3.3.

4.3.3.   Ablation study

To provide further insights into the role of the two regularization terms: $\|W_{0}X_{s}-S_{tr}\|_{F}^{2}$ and $\|W_{2}-W_{1}\|_{F}^{2}$ in our proposed objective function in helping the model to achieve better performance, we simplify our full model BSAE with various stripped-down versions of the model on the PS protocol of CZSL. Specially, for ${\lambda}_{1} = 0$, when the similarity constraint of he predicted and actual semantic representations are not exploited to encoder, i.e, Eq 3.3 without $\|W_{0}X_{s}-S_{tr}\|_{F}^{2}$ term (denoted BSAE-SR), BSAE degrades to only contain adaptation regularization. The encoder does not ensure that the learned semantic representations of each instance is close to its class prototype. For ${\lambda}_{2} = 0$, i.e., BSAE without the adaptation regularization $\|W_{2}-W_{1}\|_{F}^{2}$ (denoted BSAE-DR), the decoder in the target domain is not restricted to derive from the decoder in the source domain, which is supervised by the semantic prototypes of the source instances. Figure 8 shows clearly that the two terms contribute to the superior performance of proposed model. We achieved up to around 10% improvements on five datasets. It is reasonable to believe that the learning of semantics will help the learning of domain adaptation among seen and unseen classes.

5.   Conclusions

In this paper, we have proposed a novel model called Bi-shifting Auto-Encoder to perform efficient zero-shot recognition in semantic and visual space by taking advantage of autoencoder network. Our model learns the generalizable and computationally fast projection functions in transductive settings, which leverages the labeled source data and the visual features of the unlabeled target data. In particular, to improve the discriminability of the semantic embeddings, the encoder is constrained by aligning the semantic representations of the labeled source instances with their corresponding prototypes of the seen classes. Furthermore, to guarantee the generalizability of the projected semantic representations, two different decoders reconstruct the visual features of the instances in source and target domain simultaneously with the adaptation regularization. Thus, our model recovers the interactions between visual features and semantics, and is able to alleviate the projection shift problem. Extensive experiments are conducted on five benchmark datasets and comparative evaluations demonstrate that our model yields superior performance on zero-shot learning. The major limitation of our model lies in the fact that each class is represented by one attribute prototype in the semantic space, which is insufficient to completely characterize the features of the class, resulting in the semantics of the instances may be misplaced from the class prototype. Therefore, our research work will put effort in exploring different types of semantic representations to investigate the relationships between classes, especially the subtle differences among the classes of fine-grained datasets. An additional limitation of this study is that the full set of unlabeled target instances are utilized, ignoring their distinctive effects on the model learning. A natural processing of this work is to explore the most useful unseen instances that facilitate the zero-shot classification.

Acknowledgments

This work was supported by the Fundamental Research Funds for the Central Universities.

Conflict of interest

The authors declare there is no conflicts of interest.