Shreyas Saxena

Jakob Verbeek

Jakob Verbeek Inria

Coordinated Local Metric Learning

Keywords:

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Metric learning is a machine learning technique with a wide range of applications in computer vision, e.g. local descriptor matching [START_REF] Dosovitskiy | Discriminative unsupervised feature learning with convolutional neural networks[END_REF], fine-grained object comparison [START_REF] Nowak | Learning visual similarity measures for comparing never seen objects[END_REF], and face verification [START_REF] Köstinger | Large scale metric learning from equivalence constraints[END_REF]. Most work considers supervised learning of Mahalanobis metrics, see e.g. [START_REF] Davis | Informationtheoretic metric learning[END_REF][START_REF] Globerson | Metric learning by collapsing classes[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][START_REF] Mignon | PCCA: A new approach for distance learning from sparse pairwise constraints[END_REF][START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF]. The supervision comes as positive and negative pairs that should be close and far apart respectively. The Mahalanobis distance between two points is given by (x i -x j ) M (x i -x j ), where M is a positive definite matrix. Since M can always be factored as M = L L, Mahalanobis metrics are equivalent to the 2 metric after linear projection of the data. For complex class distributions, however, linear projection of the data might not be sufficient to obtain a suitable data representation.

To overcome this restriction, several routes have been explored. First, the linear projection in the Mahalanobis metric can be written in terms of kernel evaluations, see e.g. [START_REF] Globerson | Metric learning by collapsing classes[END_REF][START_REF] Guillaumin | Multiple instance metric learning from automatically labeled bags of faces[END_REF][START_REF] Mignon | PCCA: A new approach for distance learning from sparse pairwise constraints[END_REF]. Alternatively, (convolutional) neural networks with a siamese architecture can be learned to give (dis)similar outputs for positive and negative pairs, see e.g. [START_REF] Bromley | Signature verification using a siamese time delay neural network[END_REF][START_REF] Chopra | Learning a similarity metric discriminatively, with application to face verification[END_REF]. Approaches based on decision trees have also been explored, see e.g. [START_REF] Nowak | Learning visual similarity measures for comparing never seen objects[END_REF]. Finally, local metric learning uses a collection of Mahalanobis metrics, each operating in a different part of the input space, see e.g. [START_REF] Bhattarai | Some faces are more equal than others: Hierarchical organization for accurate and efficient large-scale identity-based face retrieval[END_REF][START_REF] Bohné | Large margin local metric learning[END_REF][START_REF] Frome | Learning globallyconsistent local distance functions for shape-based image retrieval and classification[END_REF][START_REF] Hong | Learning a mixture of sparse distance metrics for classification and dimensionality reduction[END_REF][START_REF] Huang | Reduced-rank local distance metric learning[END_REF][START_REF] Noh | Generative local metric learning for nearest neighbor classification[END_REF][START_REF] Shi | Sparse compositional metric learning[END_REF][START_REF] Wang | Parametric local metric learning for nearest neighbor classification[END_REF][START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF][START_REF] Zhan | Learning instance specific distances using metric propagation[END_REF]. The partitioning of the space is typically obtained using k-means or Gaussian mixture clustering.

In most existing local metric learning approaches, however, it is unclear how to compute distances between points assigned to different clusters, or distances are defined in an asymmetric manner. Unlike for global metric learning, they can not be interpreted as computing the 2 distance after a transformation of the data, which hinders data visualization and efficient 2 -based retrieval techniques, such as product quantization and multiple-assignment retrieval [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF].

In this paper we propose a solution by embedding the local metrics in a global representation. We use a Gaussian mixture model (GMM) to obtain a soft-partitioning of the data. With this partitioning we define a non-linear embedding of the input data vectors in a higher dimensional feature space. By learning a Mahalanobis metric over this embedding, we simultaneously learn local metrics for each cluster, and also obtain an alignment of the local metrics. This allows us (i) to compute distances between points regardless to which local cluster they belong, (ii) visualize data in a single view, and (iii) use efficient 2 -based retrieval methods. We refer to our approach as "coordinated local metric learning" (CLML).

We validate our approach in face verification and retrieval settings using the Labeled Faces in the Wild (LFW) [START_REF] Huang | Labeled faces in the wild: a database for studying face recognition in unconstrained environments[END_REF] dataset, and using image representations based on local binary patterns (LBP) [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF], convolutional neural networks (CNN) [START_REF] Yi | Learning face representation from scratch[END_REF], and Fisher vectors (FV) [START_REF] Simonyan | Fisher vector faces in the wild[END_REF]. For all tested representations our approach improves over global metric learning and other local metric learning approaches. For retrieval, the improvements over previous local metric learning approaches [START_REF] Bhattarai | Some faces are more equal than others: Hierarchical organization for accurate and efficient large-scale identity-based face retrieval[END_REF][START_REF] Shi | Sparse compositional metric learning[END_REF] are particularly large.

Related work

In this section we give an overview of related work that is most relevant to the material we present in this paper.

Mahalanobis metric learning. Many supervised Mahalanobis metric learning methods exist. Most are based on loss functions defined over pairs or triplets of data points, see e.g. [START_REF] Davis | Informationtheoretic metric learning[END_REF][START_REF] Globerson | Metric learning by collapsing classes[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][START_REF] Mignon | PCCA: A new approach for distance learning from sparse pairwise constraints[END_REF][START_REF] Wang | Two-stage metric learning[END_REF][START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF]. We refer the reader to recent survey papers [START_REF] Bellet | A Survey on Metric Learning for Feature Vectors and Structured Data[END_REF][START_REF] Kulis | Metric learning: A survey[END_REF] for a detailed review of these.

Methods based on pairwise loss terms learn a metric so that positive pairs (e.g. points having the same class label) have a distance that is smaller than negative pairs (e.g. points with different class labels). An example of such methods is the logistic discriminant metric learning (LDML) method of Guillaumin et al . [START_REF] Guillaumin | Is that you? Metric learning approaches for face identification[END_REF]. Their observation is that since Mahalanobis distances are linear in the entries of M , they can therefore be learned via standard logistic regression. In [START_REF] Guillaumin | Multiple instance metric learning from automatically labeled bags of faces[END_REF] they regularize by instead learning a low-rank factorization that projects the original data to a low dimensional space in which the 2 metric is used.

An example of a triplet-based approach is the largemargin nearest neighbor (LMNN) method [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF]. Instead of forcing all points of the same class to be close, LMNN requires that the nearest neighbors of each point are of the same class. The metric is learned by minimizing a sum of loss terms over triplets of points, where each loss term encourages the distance between x i and neighbors in the same class to be at least one distance unit smaller than the distance of x i to neighbors in different classes.

Local metric learning. To alleviate the limitations of Mahalanobis metric learning, many local metric learning methods have been proposed, see e.g. [START_REF] Bhattarai | Some faces are more equal than others: Hierarchical organization for accurate and efficient large-scale identity-based face retrieval[END_REF][START_REF] Bohné | Large margin local metric learning[END_REF][START_REF] Frome | Learning globallyconsistent local distance functions for shape-based image retrieval and classification[END_REF][START_REF] Hong | Learning a mixture of sparse distance metrics for classification and dimensionality reduction[END_REF][START_REF] Huang | Reduced-rank local distance metric learning[END_REF][START_REF] Noh | Generative local metric learning for nearest neighbor classification[END_REF][START_REF] Shi | Sparse compositional metric learning[END_REF][START_REF] Wang | Parametric local metric learning for nearest neighbor classification[END_REF][START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF][START_REF] Zhan | Learning instance specific distances using metric propagation[END_REF]. Here we limit our discussion to five recent state-of-the-art methods.

The R 2 LML method of Huang et al . [START_REF] Huang | Reduced-rank local distance metric learning[END_REF] jointly learns a set of local metrics and weights, g s i , that assign data points x i to the local metrics indexed by s. The distance between x i and x j is computed using the weighted sum of metrics, where metric s is weighted by the product g s i g s j . They iteratively learn the weights and the metrics, updating one while keeping the other fixed. To determine the weights over the metrics for test points that were not included during training, the weights of the nearest training point are used, which implies a costly lookup when large training sets are used.

Shi et al . [START_REF] Shi | Sparse compositional metric learning[END_REF] proposed SCML, a metric learning approach based on sparse combinations of a large base set of rank-1 base metrics. The base metrics are found by clustering the dataset, and then applying Fisher linear discriminant analysis (FLDA) in each cluster. For local metric learning, they take a similar approach as [START_REF] Noh | Generative local metric learning for nearest neighbor classification[END_REF][START_REF] Wang | Parametric local metric learning for nearest neighbor classification[END_REF], and measure the distance between a test point x and a training point x i by using a weighted combination of base metrics, where the weights are determined by x. During training, they learn a function that maps each data point to a set of weights over the base metrics. The advantage of their approach is that weights are easily evaluated for new test points. A limitation, however, is that a fixed set of base metrics given by FLDA restricts the class of metrics that can be learned. This is particularly detrimental for high-dimensional data.

Bohné et al . [START_REF] Bohné | Large margin local metric learning[END_REF] proposed LMLML, an approach based on GMM clustering, which learns a metric associated with each cluster. To compare two points x i and x j they use a weighted sum of the local metrics, where the weight of each metric is given by p(s|x i ) + p(s|x j ): the sum of the softassignments for x i and x j to the GMM components. If two points are far away, however, it is not clear that the local metric associated with either data point will be appropriate for a pair-wise comparison. Therefore, they also add a learned global metric to the weighted sum of metrics.

Bhattarai et al . [START_REF] Bhattarai | Some faces are more equal than others: Hierarchical organization for accurate and efficient large-scale identity-based face retrieval[END_REF] proposed a hierarchical method for efficient retrieval that learns a hierarchical clustering of the data by interleaving metric learning and k-means clustering. Each element in the training set is assigned to a leaf of the hierarchy based on the local metrics and clustering. A query is assigned to a leaf node, and retrieval is performed among the data in that leaf-node, using the associated metric. Their hierarchical decomposition speeds up the retrieval since only a fraction of the dataset is accessed for a given query. They report improved retrieval accuracy due to the use of local metrics, as compare to using global ones.

Unlike our proposed approach, none of these methods allow the local metrics to be expressed as the 2 distance after a non-linear data transformation. This means that the local metrics cannot be used for global data visualization, and do not support efficient retrieval techniques based on 2 -quantization, such as product quantization and multipleassignment retrieval [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF].

The work of Hauberg et al . [START_REF] Hauberg | A geometric take on metric learning[END_REF] is an exception in this respect: they show that if local metrics vary smoothly in the input space, then they form a Riemannian metric on the data manifold. They define a smoothly varying local metric as a linear combination of a fixed set of local metrics, which are learned separately using any local metric learning algorithm. They perform PCA in the Riemannian metric to obtain a global Euclidean data representation. They show their framework improves w.r.t. Euclidean PCA. Our approach differs in that (i) we learn the local metrics and their alignment in a joint manner, and (ii) to project a point to the global representation [START_REF] Hauberg | A geometric take on metric learning[END_REF] requires solving a system second-order ODE's with size quadratic with the data dimension, whereas our approach requires only averaging local linear projections.

Our work is also related to the local linear manifold learning technique of Teh and Roweis [START_REF] Teh | Automatic alignment of local representations[END_REF]. They use a mixture of factor analyzers (MFA) [START_REF] Ghahramani | The EM algorithm for mixtures of factor analyzers[END_REF] to map data points to local low dimensional coordinate systems associated with the mixture components. To align the local coordinates, they minimize the Locally Linear Embedding (LLE) [START_REF] Roweis | Nonlinear dimensionality reduction by locally linear embedding[END_REF] objective function. Our work differs in that we learn coordinated local linear projections in a supervised manner. Also, in our work we use a diagonal covariance GMMswhich are faster to train than MFA-and learn local linear maps directly from the original feature space to the global representation instead of mapping from the local MFA subspaces. Since the MFA is learned by optimizing a different cost function, the obtained subspaces might be suboptimal.

Globally aligning local Mahalanobis metrics

Since any positive definite D × D matrix M can be decomposed as M = L L, the Mahalanobis distance between two points x i and x j can be written as the 2 distance between these points after projection with L, i.e.

(x i -x j ) M (x i -x j ) = Lx i -Lx j 2 2 .
(1)

Note that L can be a D × D matrix, or a d × D matrix with d < D. In the latter case

(Lx i ) ∈ IR d is a low dimensional projection of x i ∈ IR D , and rank(M ) ≤ d .
To obtain a more general class of metrics, we define several local Mahalanobis metrics. We cluster the data using a k-component Gaussian mixture model (GMM), which defines a soft-assignment of the data over the k clusters.

We can compute distances between points assigned to the same cluster s using a local metric learned for that cluster, defined by a local projection matrix L s . It is, however, not clear how to compare vectors that are assigned to different clusters. In order to combine the local metrics, we define a global representation in which we integrate the local projections given by the different L s . Similar to global Mahalanobis metric learning, and unlike previous work, our formulation amounts to projecting the data (in a locally linear way) to a new representation, and computing the 2 metric in this new representation. This allows us to compute distances between any pair of samples, regardless of their cluster assignments.

Figure 1 gives an illustration on a synthetic dataset. The dataset (left panel) is constructed in such a way that a global linear projection cannot bring all points of each class close together, while keeping points of different classes apart. This is observed in the data projected using a global Mahalanobis metric (middle panel). Using our "coordinated local metric learning" (CLML) approach, which we describe below, we obtain a data representation that respects the pairwise training constraints much better (right panel).

Coordinated local metric learning

As pointed out above, we can interpret a Mahalanobis metric as computing the 2 distance after linear projection of the data. Local Mahalanobis metrics can therefore be interpreted as locally mapping the data points x to several different, local, coordinate systems via projections L s x.

Since the 2 metric is invariant to translation, rotation, and reflection of the coordinates, we can arbitrarily modify the projection of x i to a local coordinate system to

z is := R s L s x i + b s , (2)
where R s denotes an orthonormal matrix, i.e. for which R s R s = I, which can implement rotations and reflections, and b s denotes a translation. Using these transformations we can coordinate the local projections so that they align across different local models. In particular, given that x i and x j are assigned to different clusters r and t respectively, we can set the {R s , b s } to ensure that z ir and z jt are close if x i and x j form a positive pair, and far away if they form a negative pair. Instead of learning the {R s , b s } for fixed L s that were learned in advance, we will learn both the local metrics and their alignment in a joint manner. To that end, we can absorb R s into L s without loss of generality, and define a mapping of the data points x i to a global coordinate system as

z i := k s=1 q is z is = k s=1 q is L s x i + b s , (3)
where q is := p(s|x i ) is the soft-assignment of x i to cluster s. In the case of hard-assignments z i is given by the local projection of the cluster to which it is assigned. In the case of soft-assignments, z i is the weighted average of the local projections to the global representation. Our goal is now to learn {L s , b s } so that z i and z j are close for positive pairs, and far away for negative pairs. We assume the GMM clustering is fixed. Note that we can re-write this weighted average of locally linear projections as a single linear projection

z i = Lx i , (4)
where L = (L 1 , b 1 , . . . , L k , b k ) collects the local linear projections, and xi = q i1 (x i , 1), . . . , q ik (x i , 1) contains k copies of x i appended with a one, each weighted by the corresponding soft-assignment. The projection matrix L defines the local metrics used to compare points that are assigned to the same cluster, but also the rotations, reflections, and translations to globally align the local representations.

For a given partitioning of the data, the z i are obtained as a linear projection of the transformed input vectors xi , the 2 distance between z i and z j is therefore equivalent to a Mahalanobis distance between xi and xj . The problem of learning a globally aligned ensemble of local metrics therefore takes the same form of learning a global Mahalanobis metric; be it using the expanded high-dimensional data representation given by the xi . As a result, existing Mahalanobis metric learning methods can be used to learn the projection matrix L for CLML.

It is easy to see that CLML generalizes Mahalanobis metrics. For k ≥ 1, if each cluster s uses the same projection given by L s = L and b s = b, then for arbitrary soft-assignments z i = Lx i + b is a linear projection of x i , and the 2 distance between z i and z j is a Mahalanobis distance between x i and x j given by L(x i -x j ) 2 . With proper regularization, we therefore expect performance that is at least on par with global metric learning.

Implementation

Optimization. We use the LDML [START_REF] Guillaumin | Is that you? Metric learning approaches for face identification[END_REF] objective function to learn our local metrics parameterized by L. Let the label y ij ∈ {-1, +1} denote whether (x i , x j ) is a positive or a negative pair. LDML then minimizes the log-loss

L( L, b) = i,j ln 1 + exp -y ij (b -||z i -z j || 2 ) , ( 5
)
where b is a scalar (estimated along with L) that determines at which distance pairs are considered positive or negative. We add a Frobenius norm regularizer over L to avoid overfitting, and cross-validate the regularization weight. We use a global LDML metric to initialize the local metrics.

In our implementation we use the sum formulation of Eq. ( 3), which avoids explicitly storing the xi . Compared to global metric learning, we only need to additionally store the soft-assignments. In practice this is a negligible overhead, in addition the assignments can be thresholded to be sparse. The cost to compute the z i increases sub-linearly with k because of this sparsity.

Clustering. To partition the input space in CLML, we learn diagonal covariance GMMs. In our experiments we consider two alternatives for the data on which the GMMs are learned. We either learn the mixture in the original feature space, or learn the mixture in the projection space obtained by global LDML metric learning. The rationale for the latter option is that the GMM clustering will be more meaningful in the global metric learning space.

Efficient retrieval. For efficient face retrieval we use the multiple assignment approach of [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF]. The z i in the retrieval set are clustered using k-means, and each z i is assigned to the nearest center. A query z is assigned to the m closest k-means centers. Only points assigned to these m centers are returned, ranked by their distances to the query z.

Experimental Evaluation

Dataset, protocols, and features

For our experiments we use the Labeled Faces in the Wild (LFW) [START_REF] Huang | Labeled faces in the wild: a database for studying face recognition in unconstrained environments[END_REF] dataset. It contains a total of 13,233 faces of 5,749 people collected from the web. The dataset was designed for verification experiments, where we have to determine for a pair of face images if they depict the same person or not. In our experiments, we use the standard "unrestricted" training protocol, that allows the use of all pairs in the training set. The verification accuracy is measured using ten-fold cross-validation. The train set is used to learn a metric, and to estimate a threshold on the metric. Using these, the pairs in the test set is classified as positive or negative, and the accuracy of this classification is reported.

Since the LFW verification accuracy is saturating in recent years [START_REF] Liao | A benchmark study of largescale unconstrained face recognition[END_REF], we focus on the more challenging retrievalbased evaluation of Bhatterai et al . [START_REF] Bhattarai | Some faces are more equal than others: Hierarchical organization for accurate and efficient large-scale identity-based face retrieval[END_REF]. The set of 423 queries consists one image of each person in LFW with five or more images. All images not in the query set form the retrieval set, and are used to learn the metric. We augment the retrieval set with up to one million distractor faces provided by Bhatterai et al ., which belong to people not present in the LFW dataset. The 1-call@n performance measure is the fraction of queries for which at least one of the top n ranked result faces is of the same person. We also use the mean average precision (mAP) measure, which gives us a single number per setting instead of a full 1-call@n curve.

We align face images with a similarity transform based on detection of points on the eyes, nose, and mouth, see [START_REF] Everingham | Taking the bite out of automatic naming of characters in TV video[END_REF]. We consider three representations. The first is the LBP features of Bhattarai et al . [START_REF] Bhattarai | Some faces are more equal than others: Hierarchical organization for accurate and efficient large-scale identity-based face retrieval[END_REF], which allows direct comparison to their work. We compute a 9,860 dimensional descriptor by concatenating 58 dimensional LBPs [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF] each cell of a 10 × 17 grid over the face. The second is similar to the Fisher vector (FV) features of Simonyan et al . [START_REF] Simonyan | Fisher vector faces in the wild[END_REF]. We densely compute at each pixel a root-SIFT descriptor [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF], using 24 × 24 pixel patches. The descriptors are projected to 64 dimensions using PCA. Spatial layout information is incorporated by appending the 2D image coordinates of the patch center to the descriptors [START_REF] Sánchez | Modeling the spatial layout of images beyond spatial pyramids[END_REF], providing a 66 dimensional local feature. We represent the face by computing a 16,896 dimensional FV [START_REF] Sánchez | Image classification with the Fisher vector: Theory and practice[END_REF] using 128 Gaussian components. The third feature is derived from the penultimate layer of a convolutional neural network trained on the CASIA WebFace dataset [START_REF] Yi | Learning face representation from scratch[END_REF], which contains 494,414 faces of 10,575 subjects. The network architecture is similar to the one proposed in [START_REF] Yi | Learning face representation from scratch[END_REF] and the dimensionality of the extracted feature is 320.

Experimental evaluation results

For comparability with Bhattarai et al . [START_REF] Bhattarai | Some faces are more equal than others: Hierarchical organization for accurate and efficient large-scale identity-based face retrieval[END_REF], we use projections to d = 32 dimensions unless stated otherwise.

Comparison of CLML with global metric learning. In Table 1 we compare CLML using GMMs trained either in the original FV features, or on data projected to d = 32 dimensions by a global LDML metric, c.f . Section 3.2. In all cases, the clustering obtained LDML projections leads to better results. Where the difference between the two clustering approaches is only 0.05 for k = 2 local metrics, it increases for larger numbers of clusters, up to 1.67 for k = 8 local metrics. In all subsequent experiments we therefore use clustering using LDML projections. Clustering in the LDML projected space is also much faster: in this case it takes about 0.5 secs. to learn the GMM on 10,000 points.

In Table 2 we evaluate CLML on the three features, while varying the number of local metrics. We also state results obtained when cross-validating the number of local metrics, as well as results of global LDML metrics and the 2 metric. The results lead to the following observations. (i) CLML generally improves when using more local metrics. (ii) Cross-validation over the number of local metrics successfully selects a (near) optimal number of local metrics.

In subsequent experiments we cross-validate the number of local metrics for CLML. (iii) The FV features lead to better results than the LBP and CNN features. (iv) For all tested settings, CLML consistently improves over LDML.

In Figure 2 we compare CLML and LDML for the three features across a range of projection dimensions. The results show that CLML consistently improves over LDML for all projection dimensions with the three features. The improvements are particularly large for the CNN and LBP features. For the LBP and FV features, the best results are obtained with CLML at d = 128, with k = 16 set by cross-validation: 61.6% and 82.2% mAP respectively. LDML with the same number of parameters, i.e. with d = 128 × 16 = 2048, obtains 53.0% and 80.9% respectively. This shows that the improvement of CLML is not simply because it has more parameters. In the case of CNN descriptors, the best performance is obtained with CLML at d = 128 and k = 64 set by cross-validation: 76.95% mAP. Since the descriptors are only 320 dimensional, we cannot compare to LDML with the same number of parameters. Using a full-rank 320 × 320 Mahalanobis metric, however, yields 63.71% mAP, which is significantly worse.

Large-scale face retrieval experiments. In our second set of retrieval experiments we add up to one million additional distractor images to the LFW images.

In Figure 3 we evaluate the results of CLML and LDML for the three features, while increasing the number of distractors from zero to one million. We observe that performance degrades gracefully, and that the improvement of CLML over LDML is stable as a function of the number of distractors for all three features.

In Figure 4 we make a direct comparison to Bhattarai et al . [START_REF] Bhattarai | Some faces are more equal than others: Hierarchical organization for accurate and efficient large-scale identity-based face retrieval[END_REF]: re-plotting the 1-call@n curves reported there. From the other state-of-the-art methods discussed in Section 2 we compare to SCML [START_REF] Shi | Sparse compositional metric learning[END_REF]. 1 For LMLML [START_REF] Bohné | Large margin local metric learning[END_REF] code 1 Code available at http://mloss.org/software/view/553. is not available, while for R 2 LML [START_REF] Huang | Reduced-rank local distance metric learning[END_REF] we found the code too inefficient to use with our high dimensional features.

For Bhattarai et al . we report the results for their "256D4" setting, which they found to give best results and uses eight local metrics, and also include their global metric learning results obtained with PCCA [START_REF] Mignon | PCCA: A new approach for distance learning from sparse pairwise constraints[END_REF]. Our CLML results substantially improve over the results of Bhattarai et al ., e.g. from under 40% to over 70% 1-call@n for n = 10 for the case without distractors (Figure 4, left panel). Interesting we also obtained large improvements over Bhattarai et al . using global LDML metrics.

To understand the large performance difference, we reimplemented their approach (Figure 4, left panel, green curve), and obtained improvements of about 10 points w.r.t. their results. We found that most of this improvement is due to the 2 regularization that we use, but Bhattarai et al . did not. We also implemented a non-hierarchical variant of their approach, based on "flat" k-means clustering, but which is otherwise the same (Figure 4, left panel, black curve). This leads to another improvement of about 10 points, which suggests that flat clustering leads to clusters that are better suited for retrieval. Our global metric learning results obtained with LDML (Figure 4, left panel, red dashed curve) are yet another 10 points better. This shows that the benefit of using local metrics is counterbalanced by only retrieving points assigned to the same cluster as the query, as is done by Bhattarai et al . and for the green and black curves.

Using SCML [START_REF] Shi | Sparse compositional metric learning[END_REF] we obtained the worst retrieval results. This is because SCML learns metrics using a limited set of base metrics, which is detrimental for high-dimensional data. To improve results we tuned the number of base metrics (600 gave best results), and also excluded faces of people with less than 3 images to compute the base metrics with FLDA, which also improved the results. The number of clusters used to produce the base metrics in SCML is another hyper-parameter that might require further tuning.

Efficient retrieval with CLML metrics.

CLML projects all data in a single representation in which the 2 distance is used. Therefore we can decouple the clustering used for local metric learning, and the clustering used for the efficient quantization-based multiple-assignment retrieval method discussed in Section 3.2.

In Figure 5 we consider the trade-off between the retrieval mAP and search speed. The speed is measured as number of distance computations relative to the number needed for exhaustive search. Each curve shows, for a quantization into p cells, the performance using multiple assignment to m = 1, 2, 4, . . . , p clusters, where m = 1 corresponds to the lower-left point of each curve.

The blue curves show performance using 16 clusters: either using a k-means clustering computed over the z i (solid), or using the GMM clustering used for the local metrics (dashed). Using the GMM clustering (dashed blue curve), a speedup factor 10 relative to exhaustive search can be achieved by single assignment (m = 1), but at the cost of a drop of around 10 points in mAP. Using k-means clustering over the z i (solid blue curve) we obtain larger speedups and higher mAP values. The results show that it is more effective to dissociate the clustering used for the local metrics from the one used for retrieval, unlike the approach taken by Bhattarai et al . [START_REF] Bhattarai | Some faces are more equal than others: Hierarchical organization for accurate and efficient large-scale identity-based face retrieval[END_REF].

Moreover, dissociating the clusterings, allows more flexibility in choosing the speed-vs.-accuracy operating point. By using k-means clustering with more than 16 centers we can substantially improve the search results: as seen by the red, black, and green curves for p equal to 64, 256, and 1024 respectively. For example, with p = 1024 clusters (green curve) and assignment to m = 64 clusters we can reduce the search time by a factor 14, without compromising the mAP. Our speedup is comparable to the factor of 10 reported by Bhatterai et al . [START_REF] Bhattarai | Some faces are more equal than others: Hierarchical organization for accurate and efficient large-scale identity-based face retrieval[END_REF] for 16 clusters in their hierarchical approach, but our approach leads to better retrieval results. With p = 1024 and m = 8, a speedup factor larger than 100 can be obtained while loosing less than 5 mAP points.

Face verification experiments. In Table 3 we compare our results obtained using local CLML metrics and global LDML ones to the state-of-the-art using the LFW face verification evaluation.

When using no outside training data, the results of Chen et al . [START_REF] Chen | Blessing of dimensionality: high dimensional feature and its efficient compression for face verification[END_REF] (93.2 ± 1.1) and Simonyan et al . (93.0 ± 1.1) are sate-of-the-art. Using the 2 metric as a baseline we obtain 78.9 ± 0.9, which is improved using global LDML metrics to 92.1 ± 0.5 and 91.6 ± 0.4 for d = 128 and d = 32 dimensional projections respectively. For both projection dimensions, CLML improves over LDML, to 92.8 ± 0.4 and 92.4 ± 0.5 respectively. We also observe a consistent improvement when comparing LDML (d = 128 and d = 768) with CLML (d = 32, k = 4 and d = 128, k = 6) using the same number of parameters. This underlines once more that the improvements by CLML are not simply due a larger number of parameters.

Our results differ slightly from those of Simonyan et al . [START_REF] Simonyan | Fisher vector faces in the wild[END_REF] due to a more efficient implementation: (i) They used GMMs with 512 components for the FV, while we use only (iii) Besides a Mahalanobis metric, they also learn a similarity of the form x T i M x j , which they average with the Mahalanobis metric, similar to Cao et al . [START_REF] Cao | Similarity metric learning for face recognition[END_REF].

In the bottom part of Table 3 we report results obtained using CNN features. Using the CNN features with the 2 metric we obtain 96.2 ± 0.8 verification accuracy, similar to the results of Yi et al . [START_REF] Yi | Learning face representation from scratch[END_REF] (96.3 ± 0.3) which used the same training data for their network. Surprisingly, using our CNN descriptors we found that metric learning, either with LDML or CLML, gives only small improvements over the 2 baseline. The reason for this might be that the performance of the 2 distance over the CNN features is already very high for the face verification task, or that the pair-wise loss function of LDML is less suitable for verification than the triplet-based loss used by Parkhi et al . [START_REF] Parkhi | Deep face recognition[END_REF], or the weighted chi-squared metric used by Taigman et al . [START_REF] Taigman | DeepFace: Closing the gap to human-level performance in face verification[END_REF]. Yi et al . [START_REF] Yi | Learning face representation from scratch[END_REF] used a multi-task learning objective to train their CNN jointly for both verification and recognition.

The quoted results from the literature other than [START_REF] Yi | Learning face representation from scratch[END_REF], are using CNNs trained on datasets that are 5 to 400 times larger, and therefore not directly comparable. Taigman et al . [START_REF] Taigman | DeepFace: Closing the gap to human-level performance in face verification[END_REF] use 4.4 million images and combine the output of three different CNNs and use 3D face alignment. Using only 2D aligned images (as we do in our work), they reported slightly worse than ours before metric learning (94.3 ± 0.4). Parkhi et al . [START_REF] Parkhi | Deep face recognition[END_REF] recently reported results using a deeper convolutional architecture [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] and 2D face alignment over 2.6 million images (99.0). The state of the art results of Schroff et al . [START_REF] Schroff | Facenet: A unified embedding for face recognition and clustering[END_REF] are based on an extremely large proprietary dataset of 200 million images, for which no alignment was used.

Data visualization. To illustrate the benefit of CLML for data visualization we plot LFW images projected using CLML and LDML in Figure 6. We learned d = 256 dimensional projections on the FV features, and map these to 2D by PCA. For CLML the number of local metrics was set to k = 12 by cross-validation. CLML leads to a much better separation of the faces of different people, despite the limited improvement of CLML (81.9) over LDML (80.8) in mAP for d = 256. Using CLML we can more clearly see the two groups corresponding to male and female faces. We used the LFW gender labels from the BeFIT website. 2

Conclusion

We have presented our coordinated local metric learning (CLML) approach which learns local Mahalanobis metrics, and integrates them in a global representation where the 2 distance is used. This allows data visualization in a single view, and the use of efficient 2 -based retrieval methods. Our low-dimensional global representation is obtained as a linear projection of an expanded data representation, defined using the input data and a Gaussian mixture clustering. We have presented results of extensive face retrieval and verification experiments on the Labeled Faces in the Wild dataset. In all settings CLML improves over global LDML metrics, or gives comparable results. For face retrieval we obtain substantial improvements over global metrics and previously reported local metric learning results. Our approach also allows efficient multiple-assignment retrieval, which gives a better speed-accuracy trade-off than earlier work for face retrieval in a large-scale dataset with a million distractor faces.

Figure 1 .

 1 Figure 1. Synthetic dataset with color coded class labels, and the GMM used by our CLML local metric (left). Data projection given by a global Mahalanobis metric (middle) and our local CLML metric (right). The pairwise training constraints are better respected by CLML.

Figure 2 .

 2 Figure 2. Performance in mAP of local and global metrics for the three features, using projection dimensions from 16 to 256.

Figure 4 .Figure 3 .

 43 Figure 4. Retrieval using LFW images only (left), and using LFW plus 100,000 distractor faces (right). The results marked with[START_REF] Bhattarai | Some faces are more equal than others: Hierarchical organization for accurate and efficient large-scale identity-based face retrieval[END_REF] correspond to those reported therein. Results for SCML and LDML have been produced using publicly available code. See text for details.

Figure 5 .

 5 Figure 5. Retrieval mAP and speed on LFW plus one million distractor faces, using CLML with d = 32 and FV feaures. Varying the number of quantization cells p, and number of assignments m.

Figure 6 .

 6 Figure 6. Visualization of the data projections learned by LDML (left) and CLML (right). Data points of the 40 most frequent people in the dataset have been color coded. Other data points are plotted in blue and pink for males and females respectively. On the sides of the CLML visualization we show outliers faces (marked with black circles) of males in the female cluster (right), and vice-versa (left). Interestingly, male outlier faces are mostly young boys, while female outlier faces mostly display extreme poses or expressions. Best viewed on screen.

Table 1 .

 1 Evaluation of CLML over FV features using different GMM clustering methods. Performance is measured in mAP.

	on

Table 2 .

 2 Performance of CLML in retrieval mAP for the three features, while varying the number of local metrics.

	Features

Table 3 .

 3 Comparing CLML using FV features with other metric learning methods. Performance as LFW verification accuracy.

	Using LFW training data
	Guillaumin et al . [15]	12K	87.5 ± 0.4
	Chen et al . [7]	12K	93.2 ± 1.1
	Simonyan et al . [35]	12K	93.0 ± 1.1
	Ours, FV, without metric learning	12K	78.9 ± 0.9
	Ours, FV, LDML, d = 768	12K	92.3 ± 0.5
	Ours, FV, LDML, d = 128	12K	92.1 ± 0.5
	Ours, FV, CLML, d = 128 (k = 6)	12K	92.8 ± 0.4
	Ours, FV, LDML, d = 32	12K	91.6 ± 0.4
	Ours, FV, CLML, d = 32 (k = 4)	12K	92.4 ± 0.5
	Using external training data
	Taigman et al . [37]	4.4M	97.4 ± 0.3
	w/o metric learning, 2D alignment 4.4M	94.3 ± 0.4
	Yi et al . [42]	500K	97.7 ± 0.3
	w/o metric learning	500K	96.3 ± 0.3
	Parkhi et al . [29]	2.6M	99.0
	w/o metric learning	2.6M	97.3
	Schroff et al . [33]	200M 99.6
	Ours, CNN, w/o metric learning	500K	96.2 ± 0.8
	Ours, CNN, LDML, d = 128	500K 96.5 ± 1.0
	Ours, CNN, CLML, d = 128 (k = 2)	500K 96.4 ± 0.9

See http://fipa.cs.kit.edu/431.php


Amir Aly

Adriana Tapus

Gestures Imitation with a Mobile Robot in the Context of Human-Robot Interaction (HRI) for Children with Autism

In human-robot interaction, gestures play an important role in transferring messages from the human to the robot and vice versa. The robot has to be able to properly understand the gestures in order to respond in an appropriate manner. This research work focuses on dynamic gestures' recognition using robot's cameras, which capture the performed gestures in a certain interactional scenario. The gestures are processed and classified to a pre-defined category of gestures. Our gesture recognition system is currently part of a robot behavior control architecture developed for children with autism.

I. INTRODUCTION

Gestures are a form of non verbal communication that can be used not only for human-human interaction but also for human-machine interaction. In this work, dynamic gestures are classified into two categories: small and large amplitude gestures due to differences in speed between persons performing the gestures. Each of these categories has a specific classification method. These classification approaches are linked together using the optical flow so as to directly determine the nature of a gesture as part of one of the two predefined gesture categories.

II. SMALL AMPLITUDE GESTURES

A. Key frames Extraction

Key frames are important frames in a video stream, which indicate more details than the other neighbouring frames. These key frames could be specified by comparing the histogram of each frame to the histograms of its neighboring frames (figure 1) [START_REF] Shao | Motion histogram analysis based key frame extraction for human action/activity representation[END_REF].

B. Difference image

The extracted key frames from a video stream are, usually, about 6 or 7 frames (for a video of duration 4 seconds and 140 frames). As long as the amplitude of this category of gestures is small (e.g., like waving Bye-Bye using one or two hands), it is required to choose just two key frames that well present the gesture performed. Thereafter, it is useful to subtract the extracted final two key frames (the less correlated) in order to eliminate unnecessary details like background and static parts of the body (figure 2) [START_REF] Rigoll | High performance real time gesture recognition using hidden markov models[END_REF].

Amir Aly is a PhD student in the Cognitive Robotics Lab, Ecole Nationale Superieure de Techniques Avancees (ENSTA-ParisTech), France (email: amir.aly@ensta-paristech.fr)

Prof. Adriana Tapus is with Cognitive Robotics Lab, Ecole Nationale Superieure de Techniques Avancees (ENSTA-ParisTech), France (email: adriana.tapus@ensta-paristech.fr)

C. Characteristic vector and Classification

The characteristic vector could be presented by an ellipse occupying the span between the initial and the final hand positions (figure 2) [START_REF] Rigoll | High performance real time gesture recognition using hidden markov models[END_REF].

D. Results

The database of the small amplitude gestures is composed of 6 gestures for 9 persons which are in turn: Bye-Bye 2 hands, Bye-Bye right hand, Bye-Bye left hand, Stop, Yes, and No. The classification system used is the K-nearest neighbor (KNN) supported by the cross validation. The total average recognition score is about 95 % (see figure 3).

III. LARGE AMPLITUDE GESTURES

The processing procedures of large amplitude gestures are the same as in the small amplitude gestures. However, these gestures are characterized in terms of consequent difference images (4 or 5 according to the total number of frames in the video) to compensate the effect of speed differences between persons performing gestures. Each difference image will be characterized as in the small amplitude gestures [START_REF] Rigoll | High performance real time gesture recognition using hidden markov models[END_REF].

The database of the large amplitude gestures is composed of 9 gestures for 9 persons, which are in turn: kowtow, walk The classification system used is the same K-nearest neighbor (KNN) supported be the cross validation, but it has a different approach in processing the database by using 4 or 5 characteristic vectors for each gesture instead of one characteristic vector as in the small amplitude gestures system. The total average recognition score is about 93 % (see figure 5).

IV. OPTICAL FLOW

It is necessary for a gesture recognition system to respond in real time in order to precisely decide online the category of a performed gesture. Optical flow could be useful in this concern by tracking the dynamic part of the body using velocity fields that wrap consequent images in a video. Figure 6, indicates the tracked dynamic part of the body surrounded by the green rectangle. The main idea here is to

V. SOCIAL ROBOTS AND AUTISM

Social robots play an important role in ameliorating the social interactional behavior of autistic children. In this study, we try to observe whether the robot can induce imitation in the user, and sustain an imitation game over time. Mimicry and imitation are considered powerful tools of human engagement and we are currently testing them in the HRI context.

Motor imitation problems are common in autism. Imitation is a combination of cognitive-representational and visual perceptual-motor components. Motor imitation can be divided into meaningful transitive and intransitive gestures versus non-meaningful single and sequential hand postures. Meaningful gestures are symbolic and language related. In this study, we focus only on intransitive gestures, e.g. wave goodbye, which are communicative gestures. Imitation of meaningful gestures requires a proper visual perceptual discrimination of the action, comprehension of the meaning of the action, and linkage to previous information about the 'timespace' formulas of a to-be-performed action. The imitation of meaningful gestures requires cognitiverepresentational as well as perceptual-motor processes [START_REF] Rogers | A theoretical approach to the deficits in infantile autism[END_REF].

Teaching imitation, and demonstrating the behavior of an autistic child through imitation, have both led to improved social responsiveness. Use of language and gestures within the zone of proximal development (i.e., made possible in collaboration with others) may encourage the child to use the same form themselves.

The purpose of this study is to use the triadic interaction between child, robot and therapist/family member so as to help and improve childrens performance on the imitation on meaningful gestures and to be more precise on intransitive gestures which are known as communication gestures (see Figure 7). In our work, the Nao humanoid robot is used. A video of the imitation system is available at: http://www.youtube.com/watch?v=2b8CkK ghvU. This reserach work present a new methodology for gesture recognition that is used in a scenario designed for children with autism. The robot has to be able to understand and classify the perceived gestures in order to perform an appropriate interactional reaction. Two dynamic gesture categories are involved in this study according to their amplitude as being small or large. Moreover, tracking the dynamic part of the body by the optical flow is an important element in differentiating between the two categories for any test gesture. The total average recognition score for the whole system of small and large amplitude gestures is about 94% More results will be available by the time of the workshop, as this paper reports ongoing work in progress.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Final extracted two key frames

Fig. 3 :

 3 Fig. 3: Small amplitude gestures' recognition score

Fig. 5 :Fig. 6 :

 56 Fig. 5: Large amplitude gestures' recognition score

Fig. 7 :

 7 Fig. 7: Triadic interaction: Child, Robot, Therapist

VII. ACKNOWLEDGMENTS

This work is supported by French National Research Agency (ANR) through Chaire d'Excellence program 2009 (project HRIAA -Human-Robot Interaction for Assistive Applications).