Member IEEE Thomas Mensink

Member, IEEE Jakob Verbeek

Florent Perronnin

Gabriela Csurka

Distance-Based Image Classification: Generalizing to new classes at near-zero cost

Keywords: Metric Learning, k-Nearest Neighbors Classification, Nearest Class Mean Classification, Large Scale Image Classification, Transfer Learning, Zero-Shot Learning, Image Retrieval

come

INTRODUCTION

I N this paper we focus on the problem of large-scale, multi- class image classification, where the goal is to assign automatically an image to one class out of a finite set of alternatives, e.g. the name of the main object appearing in the image, or a general label like the scene type of the image. To ensure scalability, often linear classifiers such as linear SVMs are used [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF], [START_REF] Lin | Large-scale image classification: Fast feature extraction and SVM training[END_REF]. Additionally, to speedup classification, dimension reduction techniques could be used [START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF], or a hierarchy of classifiers could be learned [START_REF] Bengio | Label embedding trees for large multi-class tasks[END_REF], [START_REF] Gao | Discriminative learning of relaxed hierarchy for large-scale visual recognition[END_REF]. The introduction of the ImageNet dataset [START_REF] Deng | ImageNet: A large-scale hierarchical image database[END_REF], which contains more than 14M manually labeled images of 22K classes, has provided an important benchmark for large-scale image classification and annotation algorithms. Recently, impressive results have been reported on 10,000 or more classes [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF], [START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF], [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF]. A drawback of these methods, however, is that when images of new categories become available, new classifiers have to be trained from scratch at a relatively high computational cost.

Many real-life large-scale datasets are open-ended and dynamic: new images are continuously added to existing classes, new classes appear over time, and the semantics of existing classes might evolve too. Therefore, we are interested in distance-based classifiers which enable the addition of new classes and new images to existing classes at (near) zero cost. Such methods can be used continuously as new data becomes available, and additionally alternated from time to time with a computationally heavier method to learn a good metric using all available training data. In particular we consider two distance-based classifiers.

The first is the k-nearest neighbor (k-NN) classifier, which uses all examples to represent a class, and is a highly nonlinear classifier that has shown competitive performance for image classification [START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF], [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF], [START_REF] Guillaumin | Tagprop: Discriminative metric learning in nearest neighbor models for image auto-annotation[END_REF], [START_REF] Boiman | In defense of nearestneighbor based image classification[END_REF]. New images (of new classes) are simply added to the database, and can be used for classification without further processing.

The second is the nearest class mean classifier (NCM), which represents classes by their mean feature vector of its elements, see e.g. [START_REF] Webb | Statistical pattern recognition[END_REF]. Contrary to the k-NN classifier, this is an efficient linear classifier. To incorporate new images (of new classes), the relevant class means have to be adjusted or added to the set of class means. In Section 3, we introduce an extension which uses several prototypes per class, which allows a trade-off between the model complexity and the computational cost of classification.

The success of these methods critically depends on the used distance functions. Therefore, we cast our classifier learning problem as one of learning a low-rank Mahalanobis distance which is shared across all classes. The dimensionality of the low-rank matrix is used as regularizer, and to improve computational and storage efficiency.

In this paper we explore several strategies for learning such a metric. For the NCM classifier, we propose a novel metric learning algorithm based on multi-class logistic discrimination (NCMML), where a sample from a class is enforced to be closer to its class mean than to any other class mean in the projected space. We show qualitatively and quantitatively the advantages of our NCMML approach over the classical Fisher Discriminant Analysis [START_REF] Webb | Statistical pattern recognition[END_REF]. For k-NN classification, we rely on the Large Margin Nearest Neighbor (LMNN) framework [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF] and investigate two variations similar to the ideas presented in [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF], [START_REF] Checkik | Large scale online learning of image similarity through ranking[END_REF] that significantly improve classification performance.

Most of our experiments are conducted on the Im-ageNet Large Scale Visual Recognition Challenge 2010 (ILSVRC '10) dataset, which consists of 1.2M training images of 1,000 classes. To apply the proposed metric learning techniques on such a large-scale dataset, we employ stochastic gradient descend (SGD) algorithms, which access only a small fraction of the training data at each iteration [START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF]. To allow metric learning on high-dimensional image features of datasets that are too large to fit in memory, we use in addition product quantization [START_REF] Gray | Quantization[END_REF], a data compression technique that was recently used with success for large-scale image retrieval [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF] and classifier training [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF].

As a baseline approach, we follow the winning entry of the ILSVRC'11 challenge [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF]: Fisher vector image representations [START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF] are used to describe images and one-vsrest linear SVM classifiers are learned independently for each class. Surprisingly, we find that the NCM classifier outperforms the more flexible k-NN classifier. Moreover, the NCM classifier performs on par with the SVM baseline, and shows competitive performance on new classes.

This paper extends our earlier work [START_REF] Mensink | Metric learning for large scale image classification: Generalizing to new classes at near-zero cost[END_REF], as follows. First, for the NCM classifier, in Section 3, we compare the NCMML metric learning to the classic FDA, we introduce an extension which uses multiple centroids per class, we explore a different learning objective, and we examine the critical points of the objective. Second, in Section 4, we provide more details on the SGD triplet sampling strategy used for LMNN metric learning, and we present an efficient gradient evaluation method. Third, we extend the experimental evaluation with an experiment where NCMML is used to learn a metric for instance level image retrieval.

The rest of the paper is organized as follows. We first discuss a selection of related works which are most relevant to this paper. In Section 3 we introduce the NCM classifier and the NCMML metric learning approach. In Section 4 we review LMNN metric learning for k-NN classifiers. We present extensive experimental results in Section 5, analyzing different aspects of the proposed methods and comparing them to the current state-of-the-art in different application settings such as large scale image annotation, transfer learning and image retrieval. Finally, we present our conclusions in Section 6.

RELATED WORK

In this section we review related work on large-scale image classification, metric learning, and transfer learning.

Large-scale image classification

The ImageNet dataset [START_REF] Deng | ImageNet: A large-scale hierarchical image database[END_REF] has been a catalyst for research on large-scale image annotation. The current state-of-the-art [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF], [START_REF] Lin | Large-scale image classification: Fast feature extraction and SVM training[END_REF] uses efficient linear SVM classifiers trained in a onevs-rest manner in combination with high-dimensional bagof-words [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF], [START_REF] Zhang | Local features and kernels for classification of texture and object categories: a comprehensive study[END_REF] or Fisher vector representations [START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF]. Besides one-vs-rest training, large-scale ranking-based formulations have also been explored in [START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF]. Interestingly, their WSABIE approach performs joint classifier learning and dimensionality reduction of the image features. Operating in a lower-dimensional space acts as a regularization during learning, and also reduces the cost of classifier evaluation at test time. Our proposed NCM approach also learns lowdimensional projection matrices but the weight vectors are constrained to be the projected class means. This allows for efficient addition of novel classes.

In [START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF], [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF] k-NN classifiers were found to be competitive with linear SVM classifiers in a very large-scale setting involving 10,000 or more classes. The drawback of k-NN classifiers, however, is that they are expensive in storage and computation, since in principle all training data needs to be kept in memory and accessed to classify new images. This holds even more for Naive-Bayes Nearest Neighbor (NBNN) [START_REF] Boiman | In defense of nearestneighbor based image classification[END_REF], which does not use descriptor quantization, but requires storage of all local descriptors of all training images. The storage issue is also encountered when SVM classifiers are trained since all training data needs to be processed in multiple passes. Product quantization (PQ) was introduced in [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF] as a lossy compression mechanism for local SIFT descriptors in a bag-of-features image retrieval system. It has been subsequently used to compress bag-of-words and Fisher vector image representations in the context of image retrieval [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] and classifier training [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF]. We also exploit PQ encoding in our work to compress high-dimensional image signatures when learning our metrics.

Metric learning

There is a large body of literature on metric learning, but here we limit ourselves to highlighting just several methods that learn metrics for (image) classification problems. Other methods aim at learning metrics for verification problems and essentially learn binary classifiers that threshold the learned distance to decide whether two images belong to the same class or not, see e.g. [START_REF] Nowak | Learning visual similarity measures for comparing never seen objects[END_REF], [START_REF] Guillaumin | Is that you? Metric learning approaches for face identification[END_REF], [START_REF] Köstinger | Large scale metric learning from equivalence constraints[END_REF]. Yet another line of work concerns metric learning for ranking problems, e.g. to address text retrieval tasks as in [START_REF] Bai | Learning to rank with (a lot of) word features[END_REF].

Among those methods that learn metrics for classification, the Large Margin Nearest Neighbor (LMNN) approach of [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF] is specifically designed to support k-NN classification. It tries to ensure that for each image a predefined set of target neighbors from the same class are closer than samples from other classes. Since the cost function is defined over triplets of points -that can be sampled in an SGD training procedure-this method can scale to large datasets. The set of target neighbors is chosen and fixed using the 2 metric in the original space; this can be problematic as the 2 distance might be quite different from the optimal metric for image classification. Therefore, we explore two variants of LMNN that avoid using such a pre-defined set of target neighbors, similar to the ideas presented in [START_REF] Checkik | Large scale online learning of image similarity through ranking[END_REF].

The large margin nearest local mean classifier [START_REF] Chai | Large margin nearest local mean classifier[END_REF] assigns a test image to a class based on the distance to the mean of its nearest neighbors in each class. This method was reported to outperform LMNN but requires computing all pairwise distances between training instances and therefore does not scale well to large datasets. Similarly, TagProp [START_REF] Guillaumin | Tagprop: Discriminative metric learning in nearest neighbor models for image auto-annotation[END_REF] suffers from the same problem; it consists in assigning weights to training samples based on their distance to the test instance and in computing the class prediction by the total weight of samples of each class in a neighborhood.

Other closely related methods are metric learning by collapsing classes [START_REF] Globerson | Metric learning by collapsing classes[END_REF] and neighborhood component analysis [START_REF] Goldberger | Neighbourhood component analysis[END_REF]. As TagProp, for each data point these define weights to other data points proportional to the exponent of negative distance. In [START_REF] Globerson | Metric learning by collapsing classes[END_REF] the target is to learn a distance that makes the weights uniform for samples of the same class and close to zero for other samples. While in [START_REF] Goldberger | Neighbourhood component analysis[END_REF] the target is only to ensure that zero weight is assigned to samples from other classes. These methods also require computing distances between all pairs of data points. Because of their poor scaling, we do not consider any of these methods below.

Closely related to our NCMML metric learning approach for the NCM classifier is the LESS model of [START_REF] Veenman | LESS: a model-based classifier for sparse subspaces[END_REF]. They learn a diagonal scaling matrix to modify the 2 distance by rescaling the data dimensions, and include an 1 penalty on the weights to perform feature selection. However, in their case, NCM is used to address small sample size problems in binary classification, i.e. cases where there are fewer training points (tens to hundreds) than features (thousands). Our approach differs significantly in that (i) we work in a multi-class setting and (ii) we learn a low-dimensional projection which allows efficiency in large-scale.

Another closely related method is the Taxonomyembedding method of [START_REF] Weinberger | Large margin taxonomy embedding for document categorization[END_REF], where a nearest prototype classifier is used in combination with a hierarchical cost function. Documents are embedded in a lower dimensional space in which each class is represented by a single prototype. In contrast to our approach, they use a predefined embedding of the images and learn low-dimensional classifies, and therefore their method resembles more to the WSABIE method of [START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF].

The Sift-bag kernel of [START_REF] Zhou | Sift-bag kernel for video event analysis[END_REF] is also related to our method since it uses an NCM classifier and an 2 distance in a subspace that is orthogonal to the subspace with maximum within-class variance. However, it involves computing the first eigenvectors of the within-class covariance matrix, which has a computational cost between O(D 2 ) and O(D 3 ), undesirable for high-dimensional feature vectors. Moreover, this metric is heuristically obtained, rather than directly optimized for maximum classification performance.

Finally, the image-to-class metric learning method of [START_REF] Wang | Image-to-class distance metric learning for image classification[END_REF], learns per class a Mahalanobis metric, which in contrast to our method cannot generalize to new classes. Besides, it uses the idea of NBNN [START_REF] Boiman | In defense of nearestneighbor based image classification[END_REF], and therefore requires the storage of all local descriptors of all images, which is impractical for the large-scale datasets used in this paper.

Transfer learning

The term transfer learning is used to refer to methods that share information across classes during learning. Examples of transfer learning in computer vision include the use of part-based or attribute class representations. Part-based object recognition models [START_REF] Fei-Fei | One-shot learning of object categories[END_REF] define an object as a spatial constellation of parts, and share the part detectors across different classes. Attribute-based models [START_REF] Lampert | Learning to detect unseen object classes by between-class attribute transfer[END_REF] characterize a category (e.g. a certain animal) by a combination of attributes (e.g. is yellow, has stripes, is carnivore), and share the attribute classifiers across classes. Other approaches include biasing the weight vector learned for a new class towards the weight vectors of classes that have already been trained [START_REF] Tommasi | The more you know, the less you learn: from knowledge transfer to one-shot learning of object categories[END_REF]. Zero-shot learning [START_REF] Larochelle | Zero-data learning of new tasks[END_REF] is an extreme case of transfer learning where for a new class no training instances are available but a description is provided in terms of parts, attributes, or other relations to already learned classes. Transfer learning is related to multi-task learning, where the goal is to leverage the commonalities between several distinct but related classification problems, or classifiers learned for one type of images (e.g. ImageNet) are adapted to a new domain (e.g. imagery obtained from a robot camera), see e.g. [START_REF] Saenko | Adapting visual category models to new domains[END_REF], [START_REF] Parameswaran | Large margin multi-task metric learning[END_REF].

In [START_REF] Rohrbach | Evaluating knowledge transfer and zero-shot learning in a large-scale setting[END_REF] various transfer learning methods were evaluated in a large-scale setting using the ILSVRC'10 dataset. They found transfer learning methods to have little added value when training images are available for all classes. In contrast, transfer learning was found to be effective in a zero-shot learning setting, where classifiers were trained for 800 classes, and performance was tested in a 200-way classification across the held-out classes.

In this paper we also aim at transfer learning, in the sense that we allow only a trivial amount of processing on the data of new classes (storing in a database, or averaging), and rely on a metric that was trained on other classes to recognize the new ones. In contrast to most works on transfer learning, we do not use any intermediate representation in terms of parts or attributes, nor do we train classifiers for the new classes. While also considering zero-shot learning, we further evaluate performance when combining a zeroshot model inspired by [START_REF] Rohrbach | Evaluating knowledge transfer and zero-shot learning in a large-scale setting[END_REF] with progressively more training images per class, from one up to thousands. We find that the zero-shot model provides an effective prior when a small amount of training data is available.

THE NEAREST CLASS MEAN CLASSIFIER

The nearest class mean (NCM) classifier assigns an image to the class c * ∈ {1, . . . , C} with the closest mean:

c * = argmin c∈{1,...,C} d(x, µ c ), (1)
µ c = 1 N c i:yi=c x i , (2)
where d(x, µ c ) is the Euclidean distance between an image x and the class mean µ c , and y i is the ground-truth label of image i, and N c is the number of training images in class c.

Next, we introduce our NCM metric learning approach, and its relations to existing models. Then, we present an extension to use multiple centroids per class, which transforms the NCM into a non-linear classifier. Finally, we explore some variants of the objective which allow for smaller SGD batch sizes, and we give some insights in the critical points of the objective function.

Metric learning for the NCM classifier

In this section we introduce our metric learning approach, which we will refer to as "nearest class mean metric learning" (NCMML). We replace the Euclidean distance in NCM by a learned (squared) Mahalanobis distance:

d M (x, x ) = (x -x ) M (x -x ), (3)
where x and x are D dimensional vectors, and M is a positive definite matrix. We focus on low-rank metrics with M = W W and W ∈ IR d×D , where d ≤ D acts as regularizer and improves efficiency for computation and storage. The Mahalanobis distance induced by W is equivalent to the squared 2 distance after linear projection of the feature vectors on the rows of W :

d W (x, x ) = (x -x ) W W (x -x ) = W x -W x 2 2 . (4)
We do not consider using the more general formulation of M = W W + S, where S is a diagonal matrix, as in [START_REF] Bai | Learning to rank with (a lot of) word features[END_REF]. While this formulation requires only D additional parameters to estimate, it still requires computing distances in the original high-dimensional space. This is costly for the dense and high-dimensional (4K-64K) Fisher vectors representations we use in our experiments, see Section 5.

We formulate the NCM classifier using a probabilistic model based on multi-class logistic regression and define the probability for a class c given an feature vector x as:

p(c|x) = exp -1 2 d W (x, µ c ) C c =1 exp -1 2 d W (x, µ c ) . (5)
This definition may also be interpreted as giving the posterior probabilities of a generative model where p(

x i |c) = N (x i ; µ c , Σ)
, is a Gaussian with mean µ c , and a covariance matrix Σ = W W -1 , which is shared across all classes 1 .

The class probabilities p(c) are set to be uniform over all classes. Later, in Eq. ( 21), we formulate an NCM classifier with non-uniform class probabilities.

To learn the projection matrix W , we maximize the loglikelihood of the correct predictions of the training images:

L = 1 N N i=1 ln p(y i |x i ). (6)
The gradient of the NCMML objective Eq. ( 6) is:

∇ W L = 1 N N i=1 C c=1 α ic W z ic z ic , (7)
1. Strictly speaking the covariance matrix is not properly defined as the low-rank matrix W W is non-invertible.

Fig. 1: Illustration to compare FDA (left) and NCMML (right), the obtained projection direction is indicated by the gray line on which also the projected samples are plotted. For FDA the result is clearly suboptimal since the blue and green classes are collapsed in the projected space. The proposed NCMML method finds a projection direction which separates the classes reasonably well.

where

α ic = p(c|x i ) -[[y i = c]], z ic = µ c -x i ,

and we use the Iverson brackets [[•]

] to denote the indicator function that equals one if its argument is true and zero otherwise.

Although not included above for clarity, the terms in the log-likelihood in Eq. ( 6) could be weighted in cases where the class distributions in the training data are not representative for those when the learned model is applied.

Relation to existing linear classifiers

First we compare the NCMML objective with the classic Fisher Discriminant Analysis (FDA) [START_REF] Webb | Statistical pattern recognition[END_REF]. The objective of FDA is to find a projection matrix W that maximizes the ratio of between-class variance to within-class variance:

L FDA = tr W S B W W S W W , (8)
where

S B = C c=1 Nc N (µ -µ c )(µ -µ c
) is the weighted covariance matrix of the class centers (µ being the data center), and

S W = C c=1
Nc N Σ c is the weighted sum of within class covariance matrices Σ c , see e.g. [START_REF] Webb | Statistical pattern recognition[END_REF] for details.

In the case where the within class covariance for each class equals the identity matrix, the FDA objective seeks the direction of maximum variance in S B , i.e. it performs a PCA projection on the class means. To illustrate this, we show an example of a two-dimensional problem with three classes in Figure 1. In contrast, our NCMML method aims at separating the classes which are nearby in the projected space, so as to ensure correct predictions. The resulting projection separates the three classes reasonably well.

To relate the NCM classifier to other linear classifiers, we represent them using the class specific score functions:

f (c, x) = w c x + b c , (9)
which are used to assign samples to the class with maximum score. NCM can be recognized as a linear classifier by defining f NCM with bias and weight vectors given by:

b c = -1 2 W µ c 2 2 , (10)
w c = W W µ c . (11)
This is because -1 2 d W (x, µ c ) in Eq. ( 5) can be written as:

-1 2 W x 2 2 -1 2 W µ c 2 2 + x W W µ c ,
where the first term is independent of the class c and therefore irrelevant for classification. These definitions allows us to relate the NCM classifier to other linear methods. For example, we obtain standard multi-class logistic regression, if the restrictions on b c and w c are removed. Note that these are precisely the restrictions that allow us adding new classes at near-zero cost, since the class specific parameters b c and w c are defined by just the class means µ c and the class-independent projection W .

In WSABIE [START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF] f WSABIE is defined using b c = 0 and,

w c = W v c , (12)
where W ∈ IR d×D is also a low-rank projection matrix shared between all classes, and v c is a class specific weight vector of dimensionality d, both learned from data. This is similar to NCM if we set v c = W µ c . As in multiclass logistic regression, however, for WSABIE the v c need to be learned from scratch for new classes.

The NCM classifier can also be related to the solution of ridge-regression (RR, or regularized linear least-squares regression), where the parameters b c and w c are learned by optimizing the squared loss:

L RR = 1 N i f RR (c, x i ) -y ic 2 + λ w c 2 2 , ( 13
)
where λ acts as regularizer, and where y ic = 1, if image i belongs to class c, and y ic = 0 otherwise. The loss L RR can be minimized in closed form and leads to:

b c = N c N , and
w c = N c N µ c (Σ + λI) -1 , ( 14
)
where Σ is the (class-independent) data covariance matrix. Just like the NCM classifier, the RR classifier also allows to add new classes at low cost, since the class specific parameters can be found from the class means and counts once the data covariance matrix Σ has been estimated. Moreover, if N c is equal for all classes, RR is similar to NCM with W set such that W W = (Σ + λI) -1 . Finally, the Taxonomy-embedding [START_REF] Weinberger | Large margin taxonomy embedding for document categorization[END_REF] scores a class by:

f TAX (c, x) = v c W W x -1 2 v c 2 2 , (15)
where W ∈ IR C×D projects the data to a C dimensional space, and is set using a closed-form solution based on ridge-regression. The class-specific weight vectors v c are learned from the data. Therefore, this method relates to the WSABIE method; it learns the classifier in low-dimensional space (if C < D), but in this case the projection matrix W is given in closed-form. It also shares the disadvantage of the WSABIE method: it cannot generalize to novel classes without retraining.

Non-linear NCM with multiple class centroids

In this section we extend the NCM classifier to allow for more flexible class representations, which result in nonlinear classification. The idea is to represent each class by a set of centroids, instead of only the class mean. Assume that we have a set of k centroids {m cj } k j=1 for each class c. The posterior probability for class c can be defined as:

p(c|x) = k j=1 p(m cj |x), (16)
p(m cj |x) = 1 Z exp -1 2 d W (x, m cj ) , (17)
where p(m cj |x) denotes the posterior of a centroid m cj , and Z = c j exp -1 2 d W (x, m cj ) is the normalizer. The value k offers a transition between NCM (k = 1), and a weighted k-NN (k equals all images per class), where the weight of each neighbor is defined by the soft-min of its distance, c.f . Eq. ( 17). This is similar to TagProp [START_REF] Guillaumin | Tagprop: Discriminative metric learning in nearest neighbor models for image auto-annotation[END_REF], used for multi-label image annotation.

This model also corresponds to a generative model, where the probability for a feature vector x, to be generated by class c, is given by a Gaussian mixture distribution:

p(x|c) = k j=1 π cj N (x i ; m cj , Σ) , (18)
with equal mixing weights π cj = 1/k, and the covariance matrix Σ shared among all classes. We refer to this method as the nearest class multiple centroids (NCMC) classifier.

A similar model was independently developed recently for image retrieval in [START_REF] Lucchi | Joint image and word sense discrimination for image retrieval[END_REF]. Their objective, however, is to discriminate between different senses of a textual query, and they use a latent model to select the sense of a query.

To learn the projection matrix W , we again maximize the log-likelihood of correct classification, for which the gradient w.r.t. W in this case is given by:

∇ W L = 1 N i,c,j α icj W z icj z icj , (19)
where z icj = m cj -x i , and

α icj = p(m cj |x i ) -[[c = y i ]] p(m cj |x i ) j p(m cj |x i ) . ( 20
)
To obtain the centroids of each class, we apply k-means clustering on the features x belonging to that class, using the 2 distance. Instead of using a fixed set of class means, it could be advantageous to iterate the k-means clustering and the learning of the projection matrix W . Such a strategy allows the set of class centroids to represent more precisely the distribution of the images in the projected space, and might further improve the classification performance. However the experimental validation of such a strategy falls beyond the scope of this paper.

Alternative objective for small SGD batches

Computing the gradients for NCMML in Eq. ( 7) and NCMC in Eq. ( 19) is relatively expensive, regardless of the number of m samples used per SGD iteration. The cost of this computation is dominated by the computation of the squared distances d W (x, µ c ), required to compute the m × C probabilities p(c|x) for C classes in the SGD update. To compute these distances we have two options. First, we can compute the m × C difference vectors (x -µ c ), project these on the d × D matrix W , and compute the norms of the projected difference vectors, at a total cost of O dD(mC) + mC(d + D) . Second, we can first project both the m data vectors and C class centers, and then compute distances in the low dimensional space, at a total cost of O dD(m+C)+mC(d) . Note that the latter option has a lower complexity, but still requires projecting all class centers at a cost O(dDC), which will be the dominating cost when using small SGD batches with m C. Therefore, in practice we are limited to using SGD batch sizes with m ≈ C = 1, 000 samples.

In order to accommodate for fast SGD updates based on smaller batch sizes, we replace the Euclidean distance in Eq. ( 5) by the negative dot-product plus a class specific bias s c . The probability for class c is now given by:

p(c|x i ) = 1 Z exp x i W W µ c + s c , (21)
where Z denotes the normalizer. The objective is still to maximize the log-likelihood of Eq. ( 6). The efficiency gain stems from the fact that we can avoid projecting the class centers on W , by twice projecting the data vectors: xi = x i W W , and then computing dot-products in high dimensional space xi , µ c . For a batch of m images, the first step costs O(mDd), and the latter O(mCD), resulting in a complexity of O dD(m) + mC(D) . This complexity scales linearly with m, and is lower for small batches with m ≤ d, since in that case it is more costly to project the class vectors on W than on the double-projected data vectors xi .

For clarity, we summarize the complexity of the different alternatives we considered in Table 1.

A potential disadvantage of this approach is that we need to determine the class-specific bias s c when data of a new class becomes available, which would require more training than just computing the data mean for the new class. However, we expect a strong correlation between the learned bias s c and the bias based on the norm of the projected mean b c , as shown in Figure 2.

Similarly, as for Eq. ( 5), we could interpret the class probabilities in Eq. ( 21) as being generated by a generative model where the class-conditional models p(x|c) are Gaussian with a shared covariance matrix. In this interpretation, the class Experimentally, we find that using this formulation yields comparable results as obtained with the Euclidean distance of Eq. ( 5). For example, on ILSVRC'10 with 4K dimensional features and 128 dimensional projection matrix W , the classification error decreases from 39.2% when using s c to 39.0% when using b c at evaluation time, c.f . Table 4. Thus, we can use the metric learned using Eq. ( 21), in combination with the norm of the projected mean as bias, which is easily computed for new classes.

Critical points of low rank metric learning

We use a low-rank Mahalanobis distance where M = W W , as a way to reduce the number of parameters and to gain in computational efficiency. Learning a full Mahalanobis distance matrix M , however, has the advantage that the distance is linear in M and that the multi-class logistic regression objective of Eq. ( 6) is therefore concave in M , see details in [40, page 74]. Using a low-rank formulation, on the other hand, yields a distance which is quadratic in the parameters W , therefore the objective function is no longer concave. In this section we investigate the criticalpoints of the low-rank formulation by analyzing W when the optimization reaches a (local) minimum, and considering the gradient for the corresponding full matrix M = W W .

The gradient of the objective of Eq. ( 6) w.r.t. to M is:

∇ M L = 1 N i,c α ic z ic z ic ≡ H, (22)
where

α ic = [[y i = c]] -p(c|x i )
, and z ic = µ c -x i . Then Eq. ( 7) follows from the matrix chain rule, and we re-define ∇ W L ≡ 2W H. From the gradient w.r.t. W we immediately observe that W = 0 leads to a degenerate case to obtain a zero gradient, and similarly for each row of W . Below, we concentrate on the non-degenerate case.

We observe that H is a symmetric matrix, containing the difference of two positive definite matrices. In the analysis we use the eigenvalue decomposition of H = V ΛV , with the columns of V being the eigenvectors, and the eigenvalues are on the diagonal of Λ.

We can now express the gradient for W as

∇ W L = 2W V ΛV ≡ G. ( 23
)
Thus the gradient of the i-th row of W , which we denote by g i , is a linear combination of the eigenvectors of H:

g i ≡ j λ j w i , v j v j , (24)
where w i and v j denote the i-th row of W and the j-th column of V respectively. Thus an SGD gradient update will drive a row of W towards the eigenvectors of H that (i) have a large positive eigenvalue, and (ii) are most aligned with that row of W . This is intuitive, since we would expect the low-rank formulation to focus on the most significant directions of the full-rank metric. Moreover, the expression for the gradient in Eq. ( 24) shows that at a critical point W * of the objective function, all linear combination coefficients are zero: ∀ i,j : λ j w * i , v j = 0. This indicates that at the critical point, for each row w * i and each eigenvector v j it holds that either w * i is orthogonal to v j , or that v j has a zero associated eigenvalue, i.e. λ j = 0. Thus, at a critical point W * , the corresponding gradient for the full rank formulation at that point, with M * = W * W * , is zero in the subspace spanned by W * .

Given this analysis, we believe it is unlikely to attain poor local minima using the low rank formulation. Indeed, the gradient updates for W are aligned with the most important directions of the corresponding full-rank gradient, and at convergence the full-rank gradient is zero in the subspace spanned by W . To confirm this, we have also experimentally investigated this by training several times with different random initializations of W . We observe that the classification performance differs at most ±0.1% on any of the error measures used in Section 5, and that the number of SGD iterations selected by the early stopping procedure are of the same order.

K-NN METRIC LEARNING

We compare the NCM classifier to the k-NN classifier, a frequently used distance based classifier. For successful k-NN classification, the majority of the nearest neighbors should be of the same class. This is reflected in the LMNN metric learning objective [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF], which is defined over triplets consisting of a query image q, an image p from the same class, and an image n from another class:

L qpn = 1 + d W (x q , x p ) -d W (x q , x n ) + , (25)
where [z] + = max(0, z). The hinge-loss for a triplet is zero if the negative image n is at least one distance unit farther from the query q than the positive image p, and the loss is positive otherwise. The final learning objective sums the losses over all triplets:

L LMNN = q p∈Pq n∈Nq L qpn , (26)
where P q and N q denote a predefined set of positive and negative images for each query image q. Also in this case we could weight the terms in the loss function to account for non-representative class proportions in the training data.

Choice of target neighbors.

In the basic version of LMNN the set of targets P q for a query q is set to the query's k nearest neighbors from the same class, using the 2 distance. The rationale is that if we ensure that these targets are closer than the instances of the other classes, then the k-NN classification will succeed. However, this implicitly assumes that the 2 -targets will also be the closest points from the same class using the learned metric, which in practice might not be the case. Therefore, we consider two alternatives to using a fixed set of target neighbors. First, we consider P q to contain all images of the same class as q, hence the selection is independent on the metric. This is similar to [START_REF] Checkik | Large scale online learning of image similarity through ranking[END_REF] where the same type of loss was used to learn image similarity defined as the scalar product between feature vectors after a learned linear projection.

Second, we consider dynamically updating P q to contain the k images of the same class that are closest to q using the current metric W , hence different target neighbors can be selected depending on the metric. This method corresponds to minimizing the loss function also with respect to the choice of P q . A similar approach was proposed in [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF], where every T iterations P q is redefined using target neighbors according to the current metric.

Triplet sampling strategy.

Here, we describe a sampling strategy which obtains the maximal number of triplets from m images selected per SGD iteration. Using a small m is advantageous since the cost of the gradient evaluation is in large part determined by computing the projections W x of the images, and, if used, the cost of decompressing the PQ encoded signatures.

To generate triplets, we first select uniformly at random a class c that will provide the query and positive images. When P q is set to contain all images of the same class, we sample 2 3 m images from the class c, and 1 3 m images across other classes. In this manner we can construct about 4 27 m 3 triplets, i.e. about 4 million triplets for m = 300 used in our experiments, see our technical report [START_REF] Mensink | Large scale metric learning for distance-based image classification[END_REF] for more details.

For other choices of P q we do the following:

• For a fixed set of target neighbors, we still sample 1 3 m negative images, and take as many query images together with their target neighbors until we obtain 2 3 m images allocated for the positive class.

• For a dynamic set of target neighbors we simply select the closest neighbors among the 2 3 m sampled positive images using the current metric W . Although approximate, this avoids computing the dynamic target neighbors among all the images in the positive class.

Efficient gradient evaluation.

For either choice of the target set P q , the gradient can be computed without explicitly iterating over all triplets, by sorting the distances w.r.t. query images. The sub-gradient of the loss of a triplet is given by:

∇ W L qpn = [[L qpn > 0]] 2 W x qp x qp -x qn x qn , (27)
1) Sort distances w.r.t. q in ascending order; for positive images use dW (xq, xp) + 1 to account for the margin. 2) Accumulate, from start to end, the number of negative images up to each position. 3) Accumulate, from end to start, the number of positive images after each position. 4) Read-off the number of hinge-loss generating triplets of image p or n.

Algorithm 1: Compute coefficients A qn and A qp .

where x qp = x q -x p , x qn = x q -x n . We can write the gradient w.r.t. L LMNN in matrix form as:

∇ W L LMNN = 2 W XAX , (28)
where X contains the m feature vectors used in an SGD iteration, and A is a coefficient matrix. This shows that once A is available, the gradient can be computed in time O(m 2 ), even if a much larger number of triplets is used. When P q contains all images of the same class, A can be computed from the number of loss generating triplets:

A qn = 2 p [[L qpn > 0]], A pq = -2 n [[L qpn > 0]].
Once A qp and A qn are known, the coefficients A qq , A pp , and A nn are obtained from the former by summing, e.g. A qq = p A qpn A qn , see [START_REF] Mensink | Large scale metric learning for distance-based image classification[END_REF] for more details.

In Algorithm 1 we describe how to efficiently compute the coefficients. The same algorithm can be applied when using a small set of fixed, or dynamic target neighbors. In particular, the sorted list allows to dynamically determine the target neighbors at a negligible additional cost. In this case only the selected target neighbors obtain non-zero coefficients, and we only accumulate the number of target neighbors after each position in step 3 of the algorithm.

The cost of this algorithm is O(m log m) per query, and thus O(m 2 log m) when using O(m) query images per iteration. This is significantly faster than explicitly looping over all O(m 3 ) triplets.

Note that while this algorithm enables fast computation of the sub-gradient of the loss, the value of the loss itself cannot be determined using this method. However, this is not a problem when using an SGD approach, as it only requires gradient evaluations, not function evaluations.

EXPERIMENTAL EVALUATION

In this section we experimentally validate our models described in the previous sections. We first describe the dataset and evaluation measures used in our experiments, followed by the presentation of the experimental results.

Experimental Setup and Baseline Approach

Dataset: In most of our experiments we use the dataset of the ImageNet Large Scale Visual Recognition 2010 challenge (ILSVRC'10) 2 . This dataset contains 1.2M training images of 1,000 object classes (with between 660 2. See http://www.image-net.org/challenges/LSVRC/2010/index to 3047 images per class), a validation set of 50K images (50 per class), and a test set of 150K images (150 per class).

In some of the experiments, we use the ImageNet-10K dataset introduced in [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF], which consists of 10,184 classes from the nodes of the ImageNet hierarchy with more than 200 images. We follow [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF] and use 4.5M images as training set, 50K as validation set and the rest as test set.

Image representation: We represent each image with a Fisher vector (FV) [START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF] computed over densely extracted 128 dimensional SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] and 96 dimensional local color features [START_REF] Clinchant | XRCE's participation to ImagEval[END_REF], both projected with PCA to 64 dimensions. FVs are extracted and normalized separately for both channels and then combined by concatenating the two feature vectors. We do not make use of spatial pyramids.

In our experiments we use FVs extracted using a vocabulary of either 16 or 256 Gaussians. For 16 Gaussians, this leads to a 4K dimensional feature vector, which requires about 20GB for the 1.2M training set (using 4-byte floating point arithmetic). This fits into the RAM of our 32GB servers.

For 256 Gaussians, the FVs are 16 times larger, i.e. 64K dimensional, which would require 320GB of memory. To fit the data in memory, we compress the feature vectors using product quantization [START_REF] Gray | Quantization[END_REF], [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF]. In a nutshell, it consists in splitting the high-dimensional vector into small subvectors, and vector quantizing each sub-vector independently. We compress the dataset to approximately 10GB using 8-dimensional sub-vectors and 256 centroids per subquantizer, which allows storing each sub-quantizer index in a single byte, combined with a sparse encoding of the zero sub-vectors, see [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF]. In each iteration of SGD learning, we decompress the features of a limited number of images, and use these (lossy) reconstructions to compute the gradient.

Evaluation measures: We report the average top-1 and top-5 flat error used in the ILSVRC'10 challenge. The flat error is one if the ground-truth label does not correspond to the top-1 label with highest score (or any of the top-5 labels), and zero otherwise. The motivation for the top-5 error is to allow an algorithm to identify multiple objects in an image and not being penalized if one of the objects identified was in fact present but not included in the ground truth of the image which contains only a single object category per image.

Baseline approach: For our baseline, we follow the state-of-the-art approach of [START_REF] Perronnin | Towards good practice in large-scale learning for image classification[END_REF] and learn weighed one-vsrest SVMs with SGD, where the number of negative images in each iteration is sampled proportional to the number of positive images for that class. The proportion parameter is cross validated on the validation set. The results of the baseline can be found in Table 4 andTable 7. We observe that the performance when using the 64K dimensional features (28.0) is significantly better than the 4K ones (38.2), despite the lossy PQ compression.

In Table 4 the performance using the 64K features is slightly better than the ILSVRC'10 challenge winners [START_REF] Lin | Large-scale image classification: Fast feature extraction and SVM training[END_REF] (28.0 vs. 28.2 flat top-5 error), and close to the results of [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF] (25.7 flat top-5 error), wherein an image representation of more than 1M dimensions was used. In Table 7 our baseline shows state-of-the-art performance on ImageNet-10K when using the 64K features, obtaining 78.1 vs 81.9 flat top-1 error [START_REF] Perronnin | Towards good practice in large-scale learning for image classification[END_REF]. We believe that this is due to the use of the color features, in addition to the SIFT features used in [START_REF] Perronnin | Towards good practice in large-scale learning for image classification[END_REF].

SGD training and early stopping: To learn the projection matrix W , we use SGD training and sample at each iteration a fixed number of m training images to estimate the gradient. Following [START_REF] Bai | Learning to rank with (a lot of) word features[END_REF], we use a fixed learning rate and do not include an explicit regularization term, but rather use the projection dimension d, as well as the number of iterations as an implicit form of regularization. For all experiments we proceed as follows:

1) run for a large number of iterations (≈ 750K-2M), 2) validate every 50K (k-NN) or 10K (NCM) iterations, 3) select metric with lowest top-5 error.

In case of a tie, the metric with the lowest top-1 error is chosen. Similarly, all hyper-parameters, like the value of k for k-NN, are validated in this way. Unless stated otherwise, training is performed using the ILSVRC'10 training set, and validation on the provided 50K images of the validation set.

Training and testing complexity: In Table 2 we give an overview of the training times and number of images seen during training for the different algorithms. While the training times are difficult to compare due to the use of different implementations (Matlab and C/C++) and different machines, it is interesting to see that the the number of training images used to convergence is roughly of the same order for the different algorithms. We compare the methods in terms of (i) the number of models that is learned: SVM learns C = 1, 000 different classifiers, while the NCM/k-NN methods both learn a single projection matrix (C = 1), (ii) the number of images I per iteration: for SVM we use 64 negative images per positive image (I = 65), for NCM we use I = 1, 000, and for k-NN we use I = 300, and (iii) the number of iterations T .

While it is straightforward to parallelize the learning of the SVMs (e.g. each machine learns a single classifier), it is more complex for the proposed methods where a shared projection matrix is learned for all classes. Nevertheless, the core components of these methods can be written as matrix products (e.g. projections of the means or images, the gradients of the objectives, etc.), for which we benefit from optimized multi-threaded implementations.

At test time, evaluation of the classifiers is expensive for the k-NN classifiers, but cheap for the NCM and SVM classifiers. For the SVMs, the cost is O(M CD), where C is the number of classes, D the dimensionality of the feature vector and M the number of images in the test set. The NCM classifier, can be evaluated at the same cost by precomputing the double projection of the means, similar to the approach discussed in Section 3.4. If the dimensionality of the projection matrix d is smaller than C, then it may be more efficient to project the test images in O(M Dd), and to compute the distances in the projected space in O(M Cd).

k-NN metric learning results

We start with an assessment of k-NN classifiers in order to select a baseline for comparison with the NCM classifier.

Given the cost of k-NN classifiers, we focus our experiments on the 4K dimensional features, and consider the impact of the different choices for the set of target images P q (see Section 4), and the projection dimensionality.

We initialize W as a PCA projection, and determine the number of nearest neighbors to be used for classification on the validation set; typically 100 to 250 neighbors are optimal.

Target selection for k-NN metric learning.

In the first experiment we compare the three different options of Section 4 to define the set of target images P q , while learning projections to 128 dimensions. For LMNN and dynamic targets, we experimented with various numbers of targets on the validation set and found that using 10 to 20 targets yields the best results.

The results in Table 3 show that all methods lead to metrics that are better than the 2 metric in the original space, or after a PCA projection to 128 dimensions. Furthermore, we can improve over LMNN by using all within-class images as targets, or even further by using dynamic targets. The success of the dynamic target selection can be explained by the fact that among the three alternatives, the learning objective is the most closely related to the k-NN classification rule. The best performance on the flat top-5 error of 39.7 using 10 dynamic targets is, however, slightly worse than the 38.2 error rate of the SVM baseline.

Impact of projection dimension on k-NN classification.

Next, we evaluate the influence of the projection dimensionality d on the performance, by varying d between 32 and 1024. We only show results using 10 dynamic targets, since this performed best among the evaluated k-NN methods. From the results in Table 4 we see that a projection to 256 dimensions yields the lowest error of 39.0, which still remains somewhat inferior to the SVM baseline.

Nearest class mean classifier results

We now consider the performance of NCM classifiers and the related methods described in Section 3. For all experiments we use the NCM with Euclidean distance according to Eq. ( 5). In Table 4 we show the results. We first consider the results for the 4K dimensional features. As observed for the k-NN classifier, also for NCM using a learned metric outperforms using the 2 distance (68.0); which is worse than using 2 distances for the k-NN classifier (55.7, see Table 3). However, unexpectedly, with metric learning we observe that our NCM classifier (37.0) outperforms the more flexible k-NN classifier (39.0), as well as the SVM baseline (38.2) when projecting to 256 dimensions or more. Our implementation of WSABIE [START_REF] Weston | WSABIE: Scaling up to large vocabulary image annotation[END_REF] scores slightly worse (38.5) than the baseline and our NCM classifier, and does not generalize to new classes without retraining.

We also compare our NCM classifier to several other algorithms which do allow generalization to new classes. First, we consider two other supervised metric learning approaches, NCM with FDA (which leads to 50.5) and ridge-regression (which leads to 54.6). We observe that NCMML outperforms both methods significantly. Second, we consider two unsupervised variants of the NCM classifier where we use PCA to reduce the dimensionality. In one case we use the 2 metric after PCA. In the other, inspired by ridge-regression, we use NCM with the metric W generated by the inverse of the regularized covariance matrix, such that W W = (Σ + λI) -1 , see Section 3.2. We tuned the regularization parameter λ on the validation set, as was also done for ridge-regression. From these results we can conclude that, just like for k-NN, the 2 metric with or without PCA leads to poor results (68.0) as compared to a learned metric. Also, the feature whitening implemented by the inverse covariance metric leads to results (43.8) that are better than using the 2 metric, and also substantially better than ridge-regression (54.6). The results are however significantly worse than using our learned metric, in particular when using low-rank metrics. When we use the 64K dimensional features, the results of the NCM classifier (30.8) are somewhat worse than the SVM baseline (28.0); again the learned metric is significantly better than using the 2 distance (63.2). WSABIE obtains an error of 29.2, in between the SVM and NCM.

Illustration of metric learned by NCMML.

In Figure 3 we illustrate the difference between the 2 and the Mahalanobis metric induced by a learned projection from 64K to 512 dimensions. For two reference classes we show the five nearest classes, based on the distance between class means. We also show the posterior probabilities on the reference class and its five neighbor classes according to Eq. ( 5). The feature vector x is set as the mean of the reference class, i.e. a simulated perfectly typical image of this class. For the 2 metric, we used our metric learning algorithm to learn a scaling of the 2 metric to minimize Eq. ( 6). This does not change the ordering of classes, but ensures that we can compare probabilities computed using both metrics. We find that, as expected, the learned metric has more visually and semantically related neighbor classes. Moreover, we see that using the learned metric most of the probability mass is assigned to the reference class, whereas the 2 metric leads to rather uncertain classifications. This suggests that using the 2 metric many classes are placed at comparable distances.

Non-linear classification using multiple class centroids.

In these experiments we use the non-linear NCMC classifier, introduced in Section 3.3, where each class is represented by a set of k centroids. We obtain the k centroids per class by using the k-means algorithm in the 2 space.

Since the cost of training these classifiers is much higher, we run two sets of experiments. In Figure 4, we show the performance of the NCMC-test classifier, where only at test time k = [2, . . . , 30] is used, while using a metric obtained by the NCM objective (k = 1). In Table 5 performance of the NCMC classifier, trained with the NCMC objective, using the 4K features, compared to the NCM method and the best NCMC-test method.

From the results we observe that a significant performance improvement can be made by using the non-linear NCMC classifier, especially when using a low number of projection dimensions. When learning using the NCMC classifier we can further improve the performance of the non-linear classification, albeit for a higher training cost. When using as little as 512 projection dimensions and k = 10 centroids, we obtain a performance of 34.6 on the top-5 error. This is an improvement of about 2.4 absolute points over the NCM classifier (37.0), and 3.6 absolute points over SVM classification (38.2), c.f . Table 4.

For the 64K features, the NCMC (with k = 10 and d = 512) yields to a top-5 error 29.4, which is about 1.3 points improvement over the NCM classifier.

Generalizing to new classes with few samples

Here we explore the ability of the distance based classifiers to generalize to novel classes. For the NCM we also consider its performance as a function of the number of training images available to estimate the mean of novel classes.

Generalization to classes not seen during training.

In this experiment we split the ILSVRC'10 dataset into a training set consisting of approximately 1M images from 800 classes, and an evaluation set of the 200 held-out classes. The error is evaluated in a 1,000-way classification task, and computed over the 30K images in the test set of the heldout classes. Performance on the test images of the 800 train classes changes only marginally and including them would obscure the changes among the test images of the 200 heldout classes. The early stopping strategy uses the validation set of the 800 training classes.

In Table 6 we show the performance of NCM and k-NN classifiers, and compare it to the control setting where the metric is trained on all 1,000 classes. The results show that both classifiers generalize remarkably well to new classes. For comparison we also include the results of the SVM baseline, and the k-NN and NCM classifiers using the 2 distance, evaluated over the 200 held-out classes. In particular for 1024 dimensional projections of the 4K features, the NCM classifier achieves an error of 40.0 over classes not seen during training, as compared to 36.5 when using all classes for training. For the 64K dimensional features the drop in performance is larger, but still surprisingly good considering that training for the novel classes consists only in computing their means. Generalization to the ImageNet-10K dataset: In this experiment we demonstrate the generalization ability of the NCM classifier on the ImageNet-10K dataset. We use projections learned and validated on the ILSVRC'10 dataset, and only compute the means of the 10K classes. The results in Table 7 show that, even in this extremely challenging setting, the NCM classifier performs remarkably well compared to methods which require training of 10K classifiers. We note that, to the best of our knowledge, our baseline results (78.1 top-1 error) exceed the previously known state-of-the-art (81.9 and 80.8) [START_REF] Perronnin | Towards good practice in large-scale learning for image classification[END_REF], [START_REF] Le | Building high-level features using large scale unsupervised learning[END_REF].

Training our SVM baseline system took 9 and 280 CPU days respectively for the 4K and 64K features, while the computation of the means for the NCM classifier took approximately 3 and 48 CPU minutes respectively. This represents roughly a 8,500 fold speed-up as compared to the SVMs, given a learned projection matrix.

Accuracy as function of sample size of novel classes.

In this experiment we consider the error as a function of the number of images that are used to compute the means of novel classes. Inspired by [START_REF] Rohrbach | Evaluating knowledge transfer and zero-shot learning in a large-scale setting[END_REF], we also include a zero-shot learning experiment, where we use the ImageNet hierarchy to estimate the mean of novel classes from related classes. We estimate the mean of a novel class µ z using the means of its ancestor nodes in the ILSVRC'10 class hierarchy:

µ z = 1 |A z | a∈Az µ a , (29)
where A z denotes the set of ancestors of node z, and µ a is the mean of ancestor a. The mean of an internal node, µ a , is computed as the average of the means of all its descendant training classes.

If we view the estimation of each class mean as the estimation of the mean of a Gaussian distribution, then the mean of a sample of images µ s corresponds to the Maximum Likelihood (ML) estimate, while the zero-shot estimate µ z can be thought of as a prior. To obtain a maximum aposteriori (MAP) estimate µ p , we combine the prior and the ML estimate as follows:

µ p = nµ s + mµ z n + m , (30)
where the ML estimate is weighed by n the number of images that were used to compute it, and the prior mean obtains a weight m determined on the validation set [START_REF] Gauvain | Maximum a posteriori estimation for multivariate Gaussian mixture observations of Markov chains[END_REF]. In Figure 5 we analyze the performance of the NCM classifier trained on the images of the same 800 classes used above, with a learned projection from 4K and 64K to 512 dimensions. The metric and the parameter m are validated using the images of the 200 held-out classes of the validation set. We again report the error on the test images of the held-out classes in a 1,000-way classification as above. We repeat the experiment 10 times, and show error-bars at three times standard deviation. For the error to stabilize we only need approximately 100 images to estimate the class means. The results show that the zero-shot prior can be effectively combined with the empirical mean to provide a smooth transition from the zero-shot setting to a setting with many training examples. Inclusion of the zero-shot prior leads to a significant error reduction in the regime where ten images or less are available. Also, the results show that the validation on the 200 hold-out classes or on the 800 training classes yields comparable error rates (40.1 vs 39.9, using 4K and 512d, c.f . Table 6 and Figure 5).

In [START_REF] Rohrbach | Evaluating knowledge transfer and zero-shot learning in a large-scale setting[END_REF] a zero-shot error rate of 65.2 was reported in a 200-way classification task. Using the NCM with our prior mean estimates leads to comparable error rates of 66.5 (4K) and 64.0 (64K). Note that a different set of 200 hold-out classes were used, as well as different features. However their baseline performance of 37.6 top-5 error is comparable to our 4K features (38.2).

Instance level image retrieval. Query-by-example image retrieval can be seen as an image classification problem where only a single positive sample (the query) is given and negative examples are not explicitly provided. Recently, using classifiers to learn a metric for image retrieval was considered in [START_REF] Gordo | Leveraging category-level labels for instance-level image retrieval[END_REF]. They found the Joint Subspace and Classifier Learning (JSCL) method to be the most effective. It consists of learning jointly a set of classifiers and a projection matrix W using WSABIE, Eq. ( 12) on an auxiliary supervised dataset. After training, the learned projection matrix W is used to compute distances between queries and database images.

Similarly, we propose to learn a metric using our NCM classifier on the auxiliary supervised dataset and to use the learned metric to retrieve the most similar images for a given query.

For this experiment we use the same public benchmarks as in [START_REF] Gordo | Leveraging category-level labels for instance-level image retrieval[END_REF]. First, the INRIA Holidays data set [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF], which consists of 1,491 images of 500 scenes and objects. For TABLE 8: Results of instance level image retrieval on the Holidays and UKB dataset, using 4K features. NCMML is compared to a PCA baseline and the JSCL method of [START_REF] Gordo | Leveraging category-level labels for instance-level image retrieval[END_REF]. evaluation, one image per scene / object is used as query to search within the remaining images, and accuracy is measured as the mean average precision (mAP) over the 500 queries. Second, the University of Kentucky Benchmark dataset (UKB) [START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF], which contains 4 images of 2,550 objects (10,200 images). For evaluation, each image is used as query and the performance is measured by 4×recall@4 averaged over all queries, hence the maximal score is 4. For both datasets we extract the 4K image features used in our earlier experiments, these are also used in [START_REF] Gordo | Leveraging category-level labels for instance-level image retrieval[END_REF]. To compute the distance between two images, we use the cosine-distance, i.e. the dot-product on 2 -normalized vectors.

INRIA
We use NCMML to train a metric on the ILSVRC'10 data set, while using early stopping based on retrieval performance, similar as in [START_REF] Gordo | Leveraging category-level labels for instance-level image retrieval[END_REF]. To avoid tuning on the test data, the validation is performed on the other dataset, i.e. when testing on UKB we regularize on Holidays and vice versa. In Table 8 we compare the performance of the NCM based metric with that of JSCL, with a baseline PCA method, and with the performance using the original highdimensional descriptors. Finally, for the Holidays dataset we included the NCM metric optimized for classification performance on the ILSVRC'10 validation data set (NCM*).

From these results we observe that the NCM metric yields similar performance as the JSCL method on both datasets. A projection to only 128 dimensions or more yields an equal or better retrieval performance as using the original features or the PCA baseline. On the Holidays dataset the NCM metric outperforms the JSCL metric, while on the UKB dataset JSCL slightly outperforms NCM. Both the NCM and JSCL methods are effective to learn a projection metric for instance level retrieval, while employing class level labels.

Note that it is crucial to use retrieval performance for early stopping; the results of NCM* are in fact worse than using the original descriptors. Thus, the classification objective determines a good "path" through the space of projection matrices, yet to obtain good retrieval performance the number of iterations is typically an order of magnitude smaller than for classification. We explain this discrepancy by the fact that instance level retrieval does not require the suppression of the within class variations. This suggests also that even better metrics may be learned by training NCM on a large set of queries with corresponding matches.

CONCLUSIONS

In this paper we have considered large-scale distance-based image classification, which allow integration of new data (possibly of new classes) at a negligible cost. This is not possible with the popular one-vs-rest SVM approach, but is essential when dealing with real-life open-ended datasets.

We have introduced NCMML, a metric learning method for NCM classification, which maximizes the log-likelihood of correct class prediction, with class probabilities using the soft-min over distances between a sample and the class means. The extended non-linear NCMC classifier offers a trade-off in the complexity, from the linear NCM to the nonparametric k-NN, by the number of used class-centroids.

We have experimentally validated our models and compared to a state-of-the-art baseline of one-vs-rest SVMs using Fisher vector image representations. Surprisingly we found that the NCM outperforms the more flexible k-NN and that its performance is comparable to a SVM baseline, while projecting the data to as few as 256 dimensions.

Our experiments on the ImageNet-10K dataset show that the learned metrics generalize well to unseen classes at a negligible cost. While only computing class means, as opposed to training 10,000 SVM classifiers, we obtain competitive performance at roughly a 8,500 fold speedup.

Finally we have also considered a zero-shot learning setting and have shown that NCM provides a unified way to treat classification and retrieval problems.

Fig. 2 :W µ c 2 2 2 W µ c 2 2

 2222 Fig. 2: The learned class-specific biases s c and the norm of the projected means b c are strongly correlated.

Fig. 4 :

 4 Fig. 4: Results of the NCMC-test classifier, which uses k = 1 at train time and k > 1 at test time, for the 4K (left) and 64K (right) features, for several values of k during evaluation.

Fig. 3 :

 3 Fig. 3: The nearest classes for two reference classes using the the 2 distance and metric learned by NCMML. Class probabilities are given for a simulated image that equals the mean of the reference class, see text for details.

Fig. 5 :

 5 Fig. 5: Results of NCM as a function of the number of images used to compute the means for test classes. Comparison of the ML (blue) and MAP (red ) mean estimates, for the 4K (left) and 64K (right) features, in a 1,000-way classification task, including baseline (black ) when trained on all classes.

TABLE 1 :

 1 Comparison of complexity of the considered alternatives to compute the class probabilities p(c|x).

	Distances in D dimensions	O dD(mC) + mC(d + D)
	Distances in d dimensions	O dD(m + C) + mC(d)
	Dot product formulation	O dD(m)	+ mC(D)

TABLE 2 :

 2 Complexity comparison of classifier training.

			Training times in CPU days
			4K		64K
	Method 128 256 512 Full	128 256 512 Full
	SVM			2.7		21.3
	NCM	1.9 4.5 12.1	32.9 80.3 141.2
	k-NN	4.6 5.1 10.1
	Number of images seen during training
			C	I	T	Total
	SVM		1,000	65	120k 7,800M
	NCM	1	1,000 500k	500M
	k-NN	1	300	2M	600M

TABLE 3 :

 3 Comparison of results for different k-NN classification methods using the 4K dimensional features. For all methods, except those indicated by 'Full', the data is projected to a 128 dimensional space.

				k-NN classifiers
	SVM	2	2	LMNN	All	Dynamic
	Full Full + PCA	10	20		10	20
	Top-5 38.2 55.7	57.3	50.6 50.4 44.2 39.7 40.7

TABLE 4 :

 4 Comparison on ILSVRC'10 of the k-NN and NCM classifiers with related methods, using the 4K and 64K dimensional features and for various projection dimensions.

		4K dimensional features
	Projection dim.	32 64 128 256 512 1024	Full
	SVM baseline		38.2
	k-NN, dynamic 10	47.2 42.2 39.7 39.0 39.4 42.4
	NCM, NCMML	49.1 42.7 39.0 37.4 37.0 37.0
	NCM, FDA	65.2 59.4 54.6 52.0 50.8 50.5
	NCM, PCA + 2	78.7 74.6 71.7 69.9 68.8 68.2	68.0
	NCM, PCA + inv. cov.	75.5 67.7 60.6 54.5 49.3 46.1	43.8
	Ridge-regression, PCA	86.3 80.3 73.9 68.1 62.8 58.9	54.6
	WSABIE	51.9 45.1 41.2 39.4 38.7 38.5
		64K dimensional features
	SVM baseline		28.0
	NCMML and 2	31.7 31.0 30.7	63.2
	WSABIE	32.2 30.1 29.2

TABLE 5 :

 5 Results of the NCMC classifier using the 4K features, compared to the NCM classifier and the best NCMC-test classifier (with k in brackets).

		NCM	NCMC-test		NCMC
	Proj. Dim.			(k)	5	10	15
	128	39.0	36.3	(30)	36.2	35.8	36.1
	256	37.4	36.1	(20)	35.0	34.8	35.3
	512	37.0	36.2	(20)	34.8	34.6	35.1

  , we show the

						L2
		shopping cart 1.07%	unicycle 0.84%	covered wagon 0.83%	garbage truck 0.79%	forklift 0.78%
	Gondola					Mah.
	L2 4.4% -Mah. 99.7%	dock 0.11%	canoe 0.03%	fishing rod 0.01%	bridge 0.01%	boathouse 0.01%
						L2
		crane 0.87%	stupa 0.83%	roller coaster 0.79%	bell cote 0.78%	flagpole 0.75%
	Palm					Mah.
	L2 6.4% -Mah. 98.1%	cabbage tree 0.81%	pine 0.30%	pandanus 0.14%	iron tree 0.07%	logwood 0.06%

TABLE 6 :

 6 Results for 1,000-way classification among test images of 200 classes not used for metric learning, and control setting when learned on all classes.

			4K dimensional features
		SVM	NCM	k-NN
	Projection dim.	Full 128 256 512 1024 2 128 256 2
	Trained on all	37.6 38.6 36.8 36.4 36.5	39.0 38.4
	Trained on 800		42.4 40.5 40.1 40.0 66.6 42.7 42.6 54.2
			64K dimensional features
	Trained on all	27.7 31.7 30.8 30.6
	Trained on 800		39.2 38.1 37.8	61.9

TABLE 7 :

 7 Comparison of the results on the ImageNet-10K dataset: the NCM classifier with metrics learned on the ILSVRC'10 dataset, the NCM using 2 distance, the baseline SVM, and previously reported SVM results[START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF],[START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF],[START_REF] Perronnin | Towards good practice in large-scale learning for image classification[END_REF] and the Deep Learning results of[START_REF] Le | Building high-level features using large scale unsupervised learning[END_REF].

		4K dimensional features		64K dimensional features	Previous Results
	Method	NCM		SVM	NCM		SVM	[7] [1] [44] [45]
	Proj. dim.	128 256 512 1024	2	4K	128 256 512	2	64K	21K 131K 128K
	Top-1 error 91.8 90.6 90.5 90.4 95.5 86.0	87.1 86.3 86.1 93.6 78.1	93.6 83.3 81.9 80.8
	Top-5 error 80.7 78.7 78.6 78.6 89.0 72.4	71.7 70.5 70.1 85.4 60.9