Vocabulary-informed Zero-shot and Open-set Learning

The term “open set recognition” was initially defined in [65, 66] and formalized in [6, 63, 7] which mainly aim at identifying whether an image belongs to a seen or unseen classes. The problem is also known as class-incremental learning. However, none of these methods can further identify classes for unseen instances. The exceptions are [53, 24] which augment zero-shot (unseen) class labels with source (seen) labels in some of their experimental settings. Similarly, we define the open set image recognition as the problems of recognizing the class name of an image from a potentially very large open set vocabulary (including, but not limited to source and target labels). Note that methods like [65, 66] are orthogonal but potentially useful here – it is still worth identifying seen or unseen instances to be recognized with different label sets. Conceptually similar, but different in formulation and task, open-vocabulary object retrieval [32] focused on retrieving objects using natural language open-vocabulary queries.

While most of machine learning-based object recognition algorithms require a large amount of training data, one-shot learning [20] aims to learn object classifiers from one, or very few examples. To compensate for the lack of training instances and enable one-shot learning, knowledge must be transferred from other sources, for example, by sharing features [5], semantic attributes [27, 43, 58, 60], or contextual information [74]. However, none of the previous work had used the open set vocabulary to help learn the object classifiers.

Mapping between visual features and semantic entities has been explored in three ways: (1) directly learning the embedding by regressing from visual features to the semantic space using Support Vector Regressors (SVR) [18, 43] or neural network [68]; (2) projecting visual features and semantic entities into a common new space, such as SJE [3], WSABIE [80], ALE [2], DeViSE [24], and CCA [25, 28]; (3) learning the embeddings by regressing from the semantic space to visual features, including [38, 1, 49, 10].

Assume a labeled source dataset $\mathcal{D}_{s}=\{\mathbf{x}_{i},z_{i}\}_{i=1}^{N_{s}}$ of $N_{s}$ samples, where $\mathbf{x}_{i}\in\mathbb{R}^{p}$ is the image feature representation of image $i$ and $z_{i}\in\mathcal{W}_{s}$ is a class label taken from a set of English words or phrases $\mathcal{W}$; consequently, $|\mathcal{W}_{s}|$ is the number of source classes. Further, suppose another set of class labels for target classes $\mathcal{W}_{t}$, also taken from $\mathcal{W}$, such that $\mathcal{W}_{s}\cap\mathcal{W}_{t}=\emptyset$, for which no labeled samples are available. We note that potentially $|\mathcal{W}_{t}|>>|\mathcal{W}_{s}|$.

Learning Embedding: To learn the function $f(\mathbf{x})$, one needs to establish the correspondence between visual feature space and semantic space. Particularly, in the training step, each image sample $\mathbf{x}_{i}$ is regressed towards its corresponding class prototype $\mathbf{u}_{z_{i}}$ by minimizing

where $L\left(\mathbf{x}_{i},\mathbf{u}_{z_{i}}\right)=\|g\left(\mathbf{x}_{i}\right)-\mathbf{u}_{z_{i}}\|_{2}^{2}$ ; and $g:\mathbb{R}^{p}\rightarrow\mathbb{R}^{d}$ is the mapping from image features to semantic space; $\parallel\cdot\parallel_{F}$ indicates the Frobenius Norm. If $g\left(\mathbf{x}\right)=W^{T}\mathbf{x}$ is a linear mapping, we have the closed form solution for Eq. (1). The loss function in Eq. (1) can be interperted as a variant of SVR embedding. However, this is too limiting. To learn the linear embedding matrix $W$, we introduce and discuss two sets of methods in Section 3.3 and Section 3.4.

Recognition: The recognition step can be formulated using the nearest neighbor classifier. Given a testing instance $\mathbf{x}^{\star}$,

Eq. (2) measures the distance between predicted vector and the class prototypes in the semantic space. In terms of different label set, we can do supervise, zero-shot, generalized zero-shot or open set recognition without modifications.

where the Nearest Neighbor (NN) classifier measures distance between the predicted semantic vectors and a function of prototypes in the semantic space, e.g., $\omega\left(\mathbf{u}_{i}\right)=\mathbf{u}_{i}$ is equivalent to Eq (2). In practice, we employ semantic vector prototype averaging to define $\omega\left(\cdot\right)$. For example, sometimes, there might be more than one positive prototype, such as pig, pigs and hog. In such the circumstance, choosing the most likely prototype and using NN may not be sensible, hance we introduce the averaging strategy to consider more prototypes for robustness. Note that this strategy is known as Rocchio algorithm in information retrieval. Rocchio algorithm is a method for relevance feedback that uses more relevant instances to update the query for better recall and possibly precision in the vector space (Chap 14 in [51]). It was first suggested for use in ZSL in [27]; more sophisticated algorithms [25, 58] are also possible.

The maximum margin vocabulary-informed embedding learns the mapping $g(\mathbf{x}):\mathbb{R}^{p}\rightarrow\mathbb{R}^{d}$, from low-level features $\mathbf{x}$ to the semantic word space by utilizing maximum margin strategy. Specifically, consider $g(\mathbf{x})=W^{T}\mathbf{x}$, where¹¹1Generalizing to a kernel version is straightforward, see [76]. $W\subseteq\mathbb{R}^{p\times d}$. Ideally we want to estimate $W$ such that $\mathbf{u}_{z_{i}}=W^{T}\mathbf{x}_{i}$ for all labeled instances in $\mathcal{D}_{s}$. Note that we would obviously want this to hold for instances belonging to unobserved classes as well, but we cannot enforce this explicitly in the optimization as we have no labeled samples for them.

Data Term: The easiest way to enforce the above objective is to minimize Euclidian distance between sample projections and appropriate prototypes in the embedding space,

Where we need to minimize this term with respect to each instance $\left(\mathbf{x}_{i},\mathbf{u}_{z_{i}}\right)$, where $z_{i}$ is the class label of $\mathbf{x}_{i}$ in $\mathcal{D}_{s}$. Such embedding is also known, in the literature, as data embedding [35] or compatibility function [3].

where $\mathcal{L}_{\epsilon}\left(\mathbf{x}_{i},\mathbf{u}_{z_{i}}\right)=\mathbf{1}^{T}\mid\xi\mid_{\epsilon}^{2}$; $\lambda$ is regularization coefficient.

$|\xi|_{\epsilon}\in\mathbb{R}^{d}$; $\left(\right)_{j}$ indicates the $j$-th value of corresponding vector; $W_{\star j}$ is the $j$-th column of $W$, and $w_{z_{i}}$ is the scaling weight derived from the density of class $z_{i}$ and it’s neighboring classes. In our conference version [29], equal weight $w_{z_{i}}$ is used for all classes. Here we notice that it is beneficial to use the density/coverage of each labeled training class as the constraint in learning the projection from visual feature space to semantic space. We introduce a specific weighting strategy to compute $w_{z_{i}}$ in Section 3.4.

Triplet Term: Data term above only ensures that labelled samples project close to their correct prototypes. However, since it is doing so for many samples and over a number of classes, it is unlikely that all the data constraints can be satisfied exactly. Specifically, consider the following case, if $\mathbf{u}_{z_{i}}$ is in the part of the semantic space where no other entities live (i.e., distance from $\mathbf{u}_{z_{i}}$ to any other prototype in the embedding space is large), then projecting $\mathbf{x}_{i}$ further away from $\mathbf{u}_{z_{i}}$ is asymptomatic, i.e., will not result in misclassification. However, if the $\mathbf{u}_{z_{i}}$ is close to other prototypes then minor error in regression may result in misclassification.

We note that the form of rank hinge loss in Eq. (7) and (8) is similar to DeViSE [24], but DeViSE only considers loss with respect to source/auxiliary data and prototypes.

Maximum Margin Vocabulary-informed Embedding: The complete combined objective can now be written as:

where $\alpha\in[0,1]$ is the coefficient that controls contribution of the two terms. One practical advantage is that the objective function in Eq. (10) is an unconstrained minimization problem which is differentiable and can be solved with L-BFGS. $W$ is initialized with all zeros and converges in $10-20$ iterations.

Margin Distribution: The concept of margin is fundamental to maximum margin classifiers (e.g., SVMs) in machine learning. The margin enables an intuitive interpretation of such classifiers in searching for the maximum margin separator in a Reproducing Kernel Hilbert Space. Previous margin classifiers [92] aim to maximize a single margin across all training instances. In contrast, some recent studies [90, 62, 64, 17] suggest that the knowledge of margin distribution of instances, rather than a single margin across all instances, is crucial for improving the generalization performance of a classifier.

The “instance margin” is defined as the distance between one instance and the separating hyperplane. Formally, for one instance $i$ in the semantic space $g\left(\mathbf{x}_{i}\right)$ and sufficiently many⁴⁴4In our experiments, we use all available training instances here. samples $g\left(\mathbf{x}_{j}\right)$ ($z_{i}\neq z_{j}$) drawn from well behaved class distributions⁵⁵5The well behaved indicates that the moments of the distribution should be well-defined. For example, Cauchy distribution is not well-behaved [39].. We define the distance $d_{ij}=\left\|g\left(\mathbf{x}_{i}\right)-g\left(\mathbf{x}_{j}\right)\right\|$. For instance $i$, we can obtain a set of distances $D_{i}=\left\{d_{ij},z_{j}\neq z_{i}\right\}$ with the minimal values $\bar{d}_{i\star}=\underset{}{\mathrm{min}}{\displaystyle}D_{i}$. As shown in [62], the distribution for the minimal values of the margin distance is characterized by a Weibull distribution. Based on this finding, we can express the probability of $g\left(\mathbf{x}\right)$ being included in the boundary estimated by $g\left(\mathbf{x}_{i}\right)$:

where $\kappa_{i}$ and $\lambda_{i}$ are Weibull shape and scale parameters obtained by fitting $D_{i}$ using Maximum Likelihood Estimate (MLE), which is summarized⁶⁶6codes released in https://github.com/xiaomeiyy/WMM-Voc. in Alg. 1. Equation (11) quantitatively describes the margin of one specific class, probabilistically, in our semantic embedding space. Note that Eq. (11) requires $\psi\left(\cdot\right)$ to be non-degenerate margin distribution, which is essentially guaranteed by Extreme Value Theorem [40].

Margin Distribution of Prototypes: Consider a class $z_{i}$ which in the embedding space is represented by a prototype $\mathbf{u}_{z_{i}}$. In accordance with above formalism, we can also assume sufficiently many samples $g\left(\mathbf{x}_{j}\right)$ drawn from other ($z_{i}\neq z_{j}$) well behaved class distributions. We can also consider the prototypes of vast open vocabulary $\mathbf{u}_{z_{j}}$ ($z_{i}\neq z_{j}$, $z_{j}\in\mathcal{W}_{t}$). Under these assumptions, we can obtain a set of distances $D_{\mathbf{u}_{z_{i}}}=\{\left\|\mathbf{u}_{z_{i}}-\mathbf{g}_{z_{j}}\right\|,z_{j}\neq z_{i},\mathbf{g}_{z_{j}}\in\left\{g\left(\mathbf{x}_{j}\right),\mathbf{u}_{z_{j}}\right\}\}$ for the prototype $\mathbf{u}_{z_{i}}$. As a result, the distribution for the minimal values of the margin distance for $\mathbf{u}_{z_{i}}$ is given by a Weibull distribution. The probability that $\mathbf{g}_{z_{i}}$ is included in the boundary estimated by $\mathbf{u}_{z_{i}}$ is given by

The above equation models the distribution of minimum value; thus it can be used to estimate the boundary density (or more specifically, the boundary distribution) of class $z_{i}$.

Coverage Distribution of Prototypes: Now, for class $z_{i}$ consider the nearest instance from another class $g\left(\mathbf{x}_{j}\right)$ where $z_{i}\neq z_{j}$; with sufficient many instances $g\left(\mathbf{x}_{k}\right)$ from class $z_{i}$, we have pairwise unique ("within class") distance:

We consider outliers those instances $g\left(\mathbf{x}_{k}\right)$ that have larger distance to $\mathbf{u}_{z_{i}}$ than the nearest instance $g\left(\mathbf{x}_{j}\right)$ ($z_{i}\neq z_{j}$) of another class. To remove the outliers we hence consider $C_{\mathbf{u}_{z_{i}}}=\left\{c_{\mathbf{u}_{z_{i}}k}|c_{\mathbf{u}_{z_{i}}k}\leq\min_{{z}_{j}\neq{z}_{k}}\|g\left(\mathbf{x}_{j}\right)-\mathbf{u}_{z_{i}}\|\right\}$. As illustrated in Figure 2, we only consider positive instances within the orange circle and all other instances with larger distance are removed. Then the distribution of the largest distance $\bar{c}_{\mathbf{u}_{z_{i}}\star}=\underset{}{\max C_{\mathbf{u}_{z_{i}}}}$ will follow a reversed Weibull distribution. This allows us to get the probability distribution to describe positive instances,

where $\kappa_{i}^{{}^{\prime}}$ and $\lambda_{i}^{{}^{\prime}}$ are reverse Weibull shape and scale parameters individually obtained from fitting the largest $C_{\mathbf{u}_{z_{i}}}$, $\bar{c}_{\mathbf{u}_{z_{i}}\star}$ is the distance between instance and prototype, $\phi$ is the probability that the instance is in the class.

The learning process of parameters: The process could be interpreted as a form of block coordinate descent where we estimate the embedding/mapping; then density within that embedding and so on. In practice, the weights $w_{z_{i}}$ are initially randomized. But they do not play an important role at the beginning of the optimization, since $\left|W_{\star j}^{T}\mathbf{x}_{i}-\left(\mathbf{\mathbf{u}}_{z_{i}}\right)_{j}\right|$ is very large in the first few iterations. In other words, the optimization is initially dominated by the data term and maximum margin terms play little role. However, once we can get a relative good mapping (i.e., smaller $\left|W_{\star j}^{T}\mathbf{x}_{i}-\left(\mathbf{\mathbf{u}}_{z_{i}}\right)_{j}\right|$) after several training iterations, the weight $w_{z_{i}}$ starts becoming significant. By virtue of such an optimization, the weighted version can achieve better performance than the previous non-weighted version in our conference paper [29].

Deep Weighted Maximum Margin Voc Embedding (Deep WMM-Voc). In practice, we extend WMM-Voc to include a deep network for feature extraction. Rather than extracting low-level features using an off-the-shelf pre-trained model in Eq. (10), we use an integrated deep network to extract $\mathbf{x}_{i}$ from the raw images. As a result, the loss function in Eq. (10) is also used to optimize the parameters of the deep network. In particular, we fix the convolutional layers of corresponding network and fine-tune the last fully connected layer in our task. The network was trained using stochastic gradient descendent.

We conduct our experiments on Animals with Attributes (AwA) dataset, and ImageNet $2012$/$2010$ dataset.

AwA dataset: AwA consists of 50 classes of animals ($30,475$ images in total). In [43] standard split into 40 source/auxiliary classes ($|\mathcal{W}_{s}|=40$) and 10 target/test classes ($|\mathcal{W}_{t}|=10$) is introduced. We follow this split for supervised and zero-shot learning. We use ResNet101 features (downloaded from [54]) on AwA to make the results more easily comparable to state-of-the-art.

ImageNet $2012$/$2010$ dataset: ImageNet is a large-scale dataset. We use $1000$ ($|\mathcal{W}_{s}|=1000$) classes of ILSVRC $2012$ as the source/auxiliary classes and $360$ ($|\mathcal{W}_{t}|=360$) classes of ILSVRC 2010 that are not used in ILSVRC $2012$ as target data. We use pre-trained VGG-19 model [12] to extract deep features for ImageNet.

Recognition tasks: We consider several different settings in a variety of experiments. We first divide the two datasets into source and target splits. On source classes, we can validate whether our framework can be used to solve one-shot and supervised recognition. By using both the source and target classes, transfer learning based settings can be evaluated.

1. 1.

   Supervised recognition: learning is on source classes; test instances come from the same classes with $\mathcal{W}_{s}$ as recognition vocabulary. In particular, under this setting, we also validate the one- and few-shot recognition scenarios, i.e., classes have one or few training examples.

2. 2.

   Zero-shot recognition: In ZSL, learning is on the source classes with $\mathcal{W}_{s}$ vocabulary; test instances come from target dataset with $\mathcal{W}_{t}$ as recognition vocabulary.

3. 3.

   General-zero-shot recognition: G-ZSL uses source classes to learn, with test instances coming from either target $\mathcal{W}_{t}$ or original $\mathcal{W}_{s}$ recognition vocabulary.

4. 4.

   Open-set recognition: Again source classes are used for learning, but the entire open vocabulary with $|\mathcal{W}|\approx 310K$ atoms is used at test time. In practice, test images come from both source and target splits (similar to G-ZSL); however, unlike G-ZSL there are additional distractor classes. In other words, chance performance for open-set recognition is much lower than for G-ZSL.

We test both our Voc variants – MM-Voc and WMM-Voc. Additionally, we also validate the Deep WMM-Voc by fine-tuning the WMM-Voc on VGG-19 architecture and optimizing the weights with respect to the loss in Eq. (10).

Competitors: We compare to a variety of the models in the literature, including:

1. 1.

   SVM: SVM classifier trained directly on the training instances of source data, without the use of semantic embedding. This is the standard (Supervised/One-shot) learning setting and the learned classifier can only predict the labels within the source classes. Hence, SVM is inapplicable in ZSL, G-ZSL, and open-set recognition settings.

2. 2.

   SVR-Map: SVR is used to learn $W$ and the recognition is done, similar to our method, in the resulting semantic manifold. This corresponds to only optimizing Eq. (5).

3. 3.

   Deep-SVR: This is a variant SVR, which further allows fine-tuning of the underlying neural network generating the features. In this case, $W$ is expressed as the last linear layer and the entire network is fine-tuned with respect to the loss encoding only the data term (Eq. (5)).

4. 4.

   SAE: SAE is a semantic encoder-decoder paradigm that projects visual features into a semantic space and then reconstructs the original visual feature representation [38]. The SAE has two variants in learning the embedding space, i.e., semantic space to feature space (S$\rightarrow$F), and feature space to semantic space (F$\rightarrow$S). By default, the best result of these two variants are reported.

5. 5.

   ESZSL: ESZSL first learns the mapping between visual features and attributes, then models the relationship between attributes and classes [61].

6. 6.

   DeVise, ConSE, AMP: To compare with state-of-the-art large-scale zero-shot learning approaches we implement DeViSE [24] and ConSE [53]⁷⁷7Codes for [24] and [53] are not publicly available.. ConSE uses a multi-class logistic regression classifier for predicting class probabilities of source instances; and the parameter T (number of top-T nearest embeddings for a given instance) was selected from $\{1,10,100,1000\}$ that gives the best results. ConSE method in supervised setting works the same as SVR. We use the AMP code provided on the author webpage [31].

Metrics: Classification accuracies are reported as the evaluation metrics on most of tasks. In our conference version [29], we further introduce an evaluation setting for Open-set tasks where we do not assume that test data comes from either source/auxiliary domain or target domain. Thus we split the two cases (i.e., Supervised-like, and Zero-shot-like settings), to mimic Supervised and Zero-shot scenarios for easier analysis. Particularly, in G-ZSL task, this newly introduced evaluation setting is corresponding to the evaluation metrics defined in [85]: (1) $\mathbb{S}\rightarrow\mathbb{T}$: Test instances from seen classes, the prediction candidates include both seen and unseen classes; (2) $\mathbb{U}\rightarrow\mathbb{T}$: Test instances from unseen classes, the prediction candidates include both seen and unseen classes. (3) The harmonic mean is used as the main evaluation metric to further combine the results of both $\mathbb{S}\rightarrow\mathbb{T}$ and $\mathbb{U}\rightarrow\mathbb{T}$:

Setting of Parameters: For the recognition tasks, we learn classifiers by using various number of training instances. We compare relevant baselines with results of our method variants: MM-Voc, WMM-Voc, Deep WMM-Voc. Each setting is repeated/tested 10 times. The averaged results are reported to reduce the variance. For each setting, our Voc methods are trained by a single model to be capable of solving the tasks of supervised, zero-shot, G-ZSL and open-set recognition. Specifically,

1. 1.

   In Deep WMM-Voc, we fix $\lambda$ to $0.01$ and $\alpha=0.6$ with the learning rate initially set to $1e-5$ and is reduced by $\frac{1}{2}$ every $10$ epochs. $A_{V}$ and $B_{S}$ are set to $5$ in order to balance performance and computational cost of pairwise constraints.

2. 2.

   To solve Eq. (10) at a scale, one can use Stochastic Gradient Descent (SGD) which makes great progress initially, but often is slow when approaching convergence. In contrast, the L-BFGS method mentioned above can achieve steady convergence at the cost of computing the full objective and gradient at each iteration. L-BFGS can usually achieve better results than SGD with good initialization, however, is computationally expensive. To leverage benefits of both of these methods, we utilize a hybrid method to solve Eq. (10) in large-scale datasets: the solver is initialized with few instances to approximate the gradients using SGD first; then gradually more instances are used and switch to L-BFGS is made with iterations. This solver is motivated by Friedlander et al. [23], who theoretically analyzed and proved the convergence for the hybrid optimization methods. In practice, we use L-BFGS and the Hybrid algorithms for AwA and ImageNet respectively. The hybrid algorithm can save between $20\sim 50\%$ training time as compared with L-BFGS.

Open set vocabulary. We use Google word2vec to learn the open set vocabulary set from a large text corpus of around $7$ billion words: UMBC WebBase ($3$ billion words), the latest Wikipedia articles ($3$ billion words) and other web documents ($1$ billion words). Some rare (low frequency) words and high frequency stopping words were pruned in the vocabulary set: we remove words with the frequency $<300$ or $>10\ million$ times. The result is a vocabulary of around 310K words/phrases with $openness\approx 1$, which is defined as $openness=1-\sqrt{\left(2\times|\mathcal{W}_{s}|\right)/\left(|\mathcal{W}|\right)}$ [66].