Zero-shot Metric Learning

1 Introduction

Metric learning aims to find appropriate similarity measurements of data points, whose core intuition is to preserve the distance between data points in embedding space. This topic is of important practice due to its wide applications in many related areas, such as face recognition [Guillaumin et al., 2009], clustering [Davis et al., 2007; Xing et al., 2003], and retrieval [Zhou et al., 2004].

Euclidean distance is one of the most common similarity metrics since it does not require priori information and training process. However, unsatisfactory results may be yielded as it treats all feature dimensions equally and independently, thus fails to capture the idiosyncrasies of data. In contrast, parametric Mahalanobis distance that can model the different dimension importance, has been adopted in many works. Some representative Mahalanobis approaches [Hoi et al., 2006; Xing et al., 2003] project data linearly and minimize Euclidean distance between positive pairs, while maximize it between negative pairs. Alternatively, one may also directly optimize the Mahalanobis metric for nearest neighbor classification, among which representative works include, but are not limited to, Neighborhood Component Analysis (NCA) [Roweis et al., 2004], Large Margin Nearest Neighbor (LMNN) [Weinberger and Saul, 2009], and Nearest Class Mean (NCM) [Mensink et al., 2013]. Priori information plays a pivotal role in the success of these metric learning schemes. Therefore, unsatisfactory results can be produced when the priori is not available.

∗Corresponding author.

In this paper, we are committed to a more challenging task: zero-shot metric learning, whose ambition is to learn an effective metric for unseen categories and datasets. It claims that the learned metric must measure the similarity without access to the target data. Powerful transferability can be obtained by capturing the multi-nonlinear and continuous relations, which is consistent with the innate character of data. Particularly, we first reformulates a set of specific-shaped convolutional kernels to discover various kinds of relations. It is well known that convolutional neural network (CNN) has great power in feature embedding[Lecun et al., 1998; Donahue et al., 2013; Toshev and Szegedy, 2014], while in this paper it is employed to reveal the correlation among data. Then, we design a crossupdate regression loss, which relax the binary supervision employed on the positive pairs (PPs) and negative pairs (NPs) to extend generalization capability. Specifically, we initialize a coarse continuous label as a weak supervision of the predicted similarity, and update the coarse label and the predicted similarity alternately till convergence. By doing so, we can learn the similarity order and improve transferability. To better demonstrate the superiority of ZSML, we present multi-level transfer tasks, which covers transferring to unseen category within one dataset (intra-dataset ZSML) and unseen datasets (inter-dataset ZSML). In a nutshell, the main contributions of our work can be summarized as follows:

• Departing from the traditional single and linear relation representation, we reformulate a family of specificshaped convolutional kernels which can capture the multi-nonlinear relations among data points.
• We devise a cross-update regression loss for learning continuous similarity to improve generalization capability, which is verified in our empirical study.
• Extensive transfer experiments demonstrate that our model can better measure the similarity of unseen cate-

gories and unseen dataset compared with the peer methods.

2 RelatedWork

The Mahalanobis metric is among the most commonly used linear metric learning methods, and a majority of methods have been developed based on the Mahalanobis metric. For instance, Davis proposed an information theoretical metric learning (ITML) method [Davis et al., 2007], which essentially minimized the differential relative entropy between two multi-variate Gaussians. LMNN [Weinberger and Saul, 2009] enforced a large margin of a Support Vector Machine (SVM) within the triplet data and depicted the relative relations among three individual examples. Recently, GMML [Zadeh et al., 2016] revisited the task of learning an Euclidean metric from weakly supervised data, where pairs of similar and dissimilar points building on geometric intuition are given. Furthermore, Ye [Ye et al., 2016] proposed a unified multi-metric learning approach (UM2L) to combine both spatial connections and rich semantic factors. Xiong [Xiong et al., 2012] proposed a single adaptive metric termed position dependence structure, which additionally incorporated the feature mean vector to encode the distance besides the feature difference vector. Thereon, Huang [Huang et al., 2016] proposed to encode the two linear structures of data pairs and then map the feature pair to a similarity space.

Zero-shot learning aims for the learning of a task without training samples [Huang et al., 2015; Lampert et al., 2014]. Usually, this involves transferring the knowledge either by the model parameters or by shared features. Numerous models have been proposed to focus on descriptive attributes to represent object classes [Lampert et al., 2014; Farhadi et al., 2010]. Some other models exploit the hierarchical semantics of data [Griffin and Perona, 2008; Marszalek and Schmid, 2007]. The sample space is imposed by a general-to-specific order either based on an existing hierarchy [Marszalek and Schmid, 2007] or learned from visual features [Griffin and Perona, 2008]. Scalability is achieved by associating classifiers with each hierarchy node. In this paper, we focus on an analogous yet different issue: a zero-shot metric. The main purpose of our zero-shot metric learning is to measure the similarity between instances which are never seen before.

3 Proposed Approach

Figure 1 shows the framework of our proposed ZSML. The relation mining function R is first employed to project data pairs from feature space to relation space, in which each kind of relation is encoded as an vector. We then employ a similarity function S to map the relation vector into a scalar similarity space, where each scalar implies how similar two data points is. Finally a regression loss guides the whole optimization procedure under the supervision of a continuous label.

3.1 Preliminaries

Let χ = {xi|i = 1, 2, · · · , n} be the training set, where xi is an m-dimensional vector. P is a data pair set, which contains N pairs randomly built up within χ. Given a random data pair (xi, xj), (rij 1 , rij 2 , · · · , rij k ) indicate the corresponding k relation vectors produced by a relation function R, and sij ∈ s is the predicted similarity generated by a similarity function S. To achieve continuous supervision, we encode available binary label information yb ∈ RN into continuous form yc ∈ RN . For PPs (NPs), the binary label yb = 1 (yb = 0) while the continuous label yc ∈ (β, 1) (yc ∈ (0, α)), where α and β are two boundaries for NPs and PPs respectively.

3.2 Multi-Nonlinear Relations Mining

Traditional Mahalanobis metric learning algorithms usually employ a linear projection A to map the original data points as Ax, and compute a simple Euclidean distance ‖Axi - Axj‖2 to imply the similarity extent of data pair. However, it fails to describe inherently complex relations among data, and we tackle this problem by adopting a family of specificshaped convolutional kernels to project data pair from feature space into relation space. As illustrated in Figure 2, four different convolutional kernels, whose width are all 2, slide on the m×2 feature matrix vertically, and thus produce four various relation vectors (distinguished by color). By doing this, we can unearth multiple relations among data. Taking a data pair (xj, xj) as input, k relation vectors are computed by

where (rij 1 , rij 2 , · · · , rij k ) are k relation vectors, R is a relation function implemented by a convolutional layer (Conv) and a rectified linear unit layer (ReLU), and (WC 1 , bC1 ) are the parameters of R.

We employ a similarity function S to project the above relation vectors into a one-dimensional similarity space, in which the larger value indicates the more similar is. S is implemented by three fully connected (FC) layers, which the last layer contains one neuron. Therein, the predicted similarity sij of data pair (xi, xj) is computed by

where {WI1 , bI1 ;WI2 , bI2 ;WI3 , bI3 } are the parameters of the three fully connected layers. All projection parameters are V = {WC , bC ,WI , bI }. Notably, the neural network serves as a tool for correlation uncovering, which is quite different from the traditional feature extracting.

3.3 Regression Loss

Conventional metric learning algorithms usually adopt a binary label as supervision, which is prone to be over-fitting for trying to individually push the similarity in terms of two single points [Huang et al., 2016]. As depicted in Figure 3, binary labels consider data points in the same class with the same similarity extent, and neglect the intra-class data manifold. To better preserve the original data similarities, we propose a regression loss to learn continuous similarity, which enables data points from the same category to reside on a manifold, and also maintain a distance between data points from different categories. The regression loss is implemented in two steps: 1) generate an N-dimensional vector according to binary label yb , which serves as an initialization of continuous label yc ; 2) a cross-update strategy is employed to alternately optimize predicted similarity s and yc by forcing the consistency of them.

The binary essence of yb is a obstacle towards guiding continuous similarity learning. Therein, we encode yb into a continuous form yc , which contributes in a certain range. As shown in Figure 4, the Euclidean distances are mapped into (β, 1) for PPs and (0, α) for NPs. Concretely, we adopt the following mapping functions:

where dij is the normalized Euclidean distance, α and β are the boundaries for the continuous labels.

Another problem is that the initialized continuous label is coarse and needs to be finely tuned. ZSML achieves this goal by adopting a cross-update strategy to optimize the predicted similarity s and continuous labels yc alternatively. We design our objective function to consist of two parts, and the intuition is to make s and yc close:

• The loss of the similarity Ls is

As similarity s is obtained by our model parameterized by V, the target optimization variables of Equation (4) are s and Vwhen yc is fixed.

• The loss of the continuous labels Lyc is

Combining Ls and Lyc , we can get the overall objective function as:

where λ is the hyper-parameter to balance Ls and Lyc . yc is the initialized continuous label according to the binary label, which meets the two constraints: the values range in (β, 1) for positive pairs and (0, α) for negative pairs. We only finely tune yc and thus λ is set to a small value (0.1 for our experiments). The continuous supervised regression loss can relax the binary supervision employed on PPs and NPs and then extend generalization capability efficiently.

4 Optimization

To optimize this model, we first apply a hinge-loss function to transform the constrained optimization problem to an unconstrained one [Hadsell et al., 2006]. For the similarity s in Equation (4), we have

where the operator [·]+ indicates the hinge function max(0, ·). For the continuous label yc in Equation (5), we have

Algorithm 1 Learning of the proposed ZSML model.

Input: Training set {xi}. Initialized parameters {WC , bC } of the convolution layer, {WI , bI } of the fully connected layers, and yc = {yc ij |(xi, xj) ∈ P} of the loss layer. hyper-parameters λ, α, β and learning rate µt . The number of iterations t ← 0.

Output: The parameters V = {WC , bC ,WI , bI }.

• 1: while not converge do
• 2: t ← t + 1.
• 3: Compute the joint loss by Lt = Lts +λLtyc.
• 4: Fix s. Update yc by yt+1 = yt -µt ·λ· ∂Lty ∂yt . Record yc as y for the conflict of superscripts c and t.
• 5: Fix y. Compute backpropagation error ∂Lts ∂st for all the data points.
• 6: Update V by Vt+1 =Vt -µt · ∂Lts ∂st · ∂st ∂Vt .
• 7: end while

We employ a cross-optimization strategy, fixing s when optimize yc and vice versa. The gradients of the loss function with regard to s, V, and yc are computed by Equation (9) and (10) as

We adopt a quadratic form of the hinge loss to transform the objective functions (4) and (5) into an unconstrained problem. It can derive penalty from the original loss with back propagation, referring to Equation (9) and (10). That is the further violation of constraints is, the larger gradient is. The procedure is depicted in Algorithm 1.

5 Experiments

In this section, we evaluate the efficiency of our proposed ZSML by multi-level transfer setting on four public benchmark datasets, transferring to unseen categories (intra-dataset ZSML) and unseen datasets (inter-dataset ZSML). We evaluate the clustering performance of all experiments, by three metrics: Accuracy (ACC), Normalized Mutual Information (NMI), and Purity [Cai et al., 2008].

5.1 Implementation Details

The Caffe package [Jia et al., 2014] is used throughout the experiments. The base learning rate is set to 0.002 and iteration times are set to 20, 000. It takes about 6 minutes for training on an NVIDIA TITAN X GPU, since our model only requires 26.4 million FLOPS, as summarized in Table 1. There are four hyper-parameters λ, k, α, and β and we set them to 0.1, 96, 0.3, and 0.7 respectively. β always equals to 1 - α. As depicted in Figure 5, we randomly pick 400 points in Caltech, and plot the distribution between predicted similarity and continuous label after training 20, 000 times. We can observe that the predicted similarity resides on two smooth manifolds respectively for NPs and PPs.

We conduct our experiments on Caltech-101 [Wah et al., 2011b], COIL-20 [Nene et al., 1996], ImageNet-20 1 [Deng et al., 2009], and MSRC-v1, of which the details are summarized in Table 2. All images are represented by concatenating three popular descriptors, which are histogram of oriented gradient (HOG), GIST, and local binary pattern (LBP) respectively. The dimensions of three descriptors are 1152, 512 and 944 separately and then each data point is represented by a 2608-dimensional vectors. In the following parts, we refer to the four datasets as Caltech, COIL, ImageNet, and MSRC for brief.

We compare our method with five metric learning algorithms, i.e., 1) The Euclidean metric; 2) Information-theoretic metric learning (ITML) [Davis et al., 2007]; 3) Distance metric learning for large margin nearest neighbor classification

1 We randomly choose 20 categories and 150 images per category from ImageNet, referred to as ImageNet-20.

(LMNN) [Weinberger and Saul, 2009]; 4) Geometric mean metric learning (GMML) [Zadeh et al., 2016]; 5) Closedform training of Mahalanobis distance for supervised clustering (MLCA) [Law et al., 2016].

5.2 Result Analysis

In this part, we will demonstrate our quantitative results and give some analysis about the figures. In all of the tables, we underline the best performance, and bold the second best.

In intra-dataset ZSML task, we train our model on some categories and test the learned metric on the other categories which belong to the same dataset. We conduct two group of experiments, including Caltech → Caltech and ImageNet → ImageNet. For both of them, we randomly pick 7 classes (more than 1, 000 data points) for testing and the remaining for training. Table 3 reports the ACC, NMI and purity metrics, and we can see that our approach outperforms peer methods by a large margin for all the three metrics. In inter-dataset ZSML task, we train our model on source dataset, and measure the similarity of target dataset. We conduct four groups of experiments, which are Caltech → COIL, Caltech → ImageNet, Caltech → MSRC, and ImageNet → Caltech respectively. When Caltech and ImageNet serve as source datasets, we pick all examples of them for training. When Caltech and ImageNet serve as target datasets, we pick the categories used in the testing phase of intra-dataset ZSML for testing. We use all examples in COIL and MSRC for testing, when COIL and MSRC are the target datasets. Table 4 and 5 reports the ACC, NMI and purity metrics. We can see that our method achieves strong transferability, although the great gap exists in different datasets. Furthermore, the Euclidean distance performances moderately in most cases, as it requires no training phase and the over-fitting problem will not occur.

We further concatenate our model after the Lifted algorithm [Oh Song et al., 2016] to verify the effectiveness on large scale image dataset CUB 200 2011 [Wah et al., 2011a]. Following the experiment protocol and evaluation metrics used in Lifted, we conduct the experiment and Table 6 reports the results, from which we can see that our model can significantly improve the representation power under zero-shot setting.

5.3 Ablation Study

We fix α = 0.3 (β = 1 - α = 0.7), and change the number of convolution kernels k to 16, 64, 96, and 128 respectively. On the other hand, parameter α varies in four values: {0.1, 0.2, 0.3, 0.4} when fix k = 96. As illustrated in Table 7 and Table 8, k and α shows a positive tendency until k = 96 and α = 0.3. Hence, we fix α to 0.3 and k to 96 throughout our experiments.

To verify the priority of our proposed regression loss (Reloss), we switch the multi-nonlinear relations (MR) to linear relation (LR). For LR, we first minus two feature vectors of two data points, and employ S to project into similarity space. Table 9 reports the ACC, NMI and Purity metrics of LR + Reloss compared to LMNN and GMML. We can observe that Reloss based optimization is significant for improving the performance, mainly because of it relaxes the binary constraint employed on data pairs and the generalization capability is enhanced.

6 Conclusion

In this paper, we investigated zero-shot metric learning issue, which aims at measuring the similarity of data points from unseen categories or even unseen datasets. We reformulated a family of specific-shaped convolutional kernels to combine the data pair, which is capable capturing the multi-nonlinear relations. Furthermore, we designed a novel continuoussupervised regression loss, which can effectively preserve the continuous intra-data manifold. To sum up, our model greatly extends the transferability by learning the multi-nonlinear yet continuous relations. Extensive experiments, including intradataset ZSML and inter-dataset ZSML, verified the rationality and effectiveness of our proposed method.

Acknowledgments

Our work was also supported by the National Natural Science Foundation of China under Grant 61572388 and 61703327, Key R&D Program-The Key Industry Innovation Chain of Shaanxi under Grant 2017ZDCXL-GY-0504-02, 2017ZDCXL-GY-05-02, and 2018ZDXM-GY-176, and the National Key R&D Program of China under Grant 2017YFE0104100.