{'fraction_non_alphanumeric': 0.03896153994522239, 'fraction_numerical': 0.015738919106584887, 'mean_word_length': 4.573855084927972, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Ranked List Loss for Deep Metric Learning

The objective of deep metric learning (DML) is to learn embeddings that can capture semantic similarity information among data points. Existing pairwise or tripletwise loss functions used in DML are known to suffer from slow convergence due to a large proportion of trivial pairs or triplets as the model improves. To improve this, rankingmotivated structured losses are proposed recently to incorporate multiple examples and exploit the structured information among them. They converge faster and achieve state-of-the-art performance. In this work, we present two limitations of existing ranking-motivated structured losses and propose a novel ranked list loss to solve both of them. First, given a query, only a fraction of data points is incorporated to build the similarity structure. Consequently, some useful examples are ignored and the structure is less informative. To address this, we propose to build a setbased similarity structure by exploiting all instances in the gallery. The samples are split into a positive set and a negative set. Our objective is to make the query closer to the positive set than to the negative set by a margin. Second, previous methods aim to pull positive pairs as close as possible in the embedding space. As a result, the intraclass data distribution might be dropped. In contrast, we propose to learn a hypersphere for each class in order to preserve the similarity structure inside it. Our extensive experiments show that the proposed method achieves state-of-the-art performance on three widely used benchmarks.


Introduction
Deep metric learning (DML) plays a crucial role in a variety of applications in computer vision, such as image retrieval [28,19], clustering [10], and transfer learning [20]. In addition, DML is a good solution for challenging extreme classification settings [22,40], in which there exist an enormous number of classes and only a few images per class. For example, by using DML, FaceNet [24] achieves superhuman performance on face verification with 260M face images of 8M identities. Loss function plays a key role in successful DML frameworks and a large variety of loss functions have been proposed in the literature. Contrastive loss [2,6] captures the relationship between pairwise data points, i.e., similarity or dissimilarity. Triplet-based losses are also widely studied [24,33,3]. A triplet is composed of an anchor point, a similar (positive) data point and dissimilar (negative) data point. The purpose of triplet loss is to learn a distance metric by which the anchor point is closer to the similar point than the dissimilar one by a margin. In general, the triplet loss outperforms the contrastive loss [20,24] because the relationship between positive and negative pairs is considered. Inspired by this, recent work [24,28,20,29,16,19] proposes to take into consideration the richer structured information among multiple data points and achieve impressive performance on many applications, e.g., image retrieval and clustering.
However, there are still certain limitations in current state-of-the-art DML approaches. Firstly, we notice that only a proportion of informative examples is incorporated to capture the structure in previous ranking-motivated loss functions. In this case, some non-trivial examples are wasted and the structured information is extracted from fewer data points. To address it, we propose to utilise all non-trivial data points to build a more informative structure and exploit it to learn more discriminative embeddings. Specifically, given a query, we obtain a ranked list by sorting all other data points (gallery) according to the similarities. Ideally, all the positive examples are supposed to be ranked before the negative samples in the feature space. To achieve this, we propose ranked list loss (RLL) to organise the samples of each query. Given a query, the optimisation of RLL is to rank all positive points before the negative points and forcing a margin between them. In other words, RLL aims to explore the set-based similarity structure, which contains richer information than the point-based approach, e.g., triplet loss.
Secondly, we observe that the intraclass data distribution is not considered in the previous structured losses. All algorithms [24,20,28,29,19,36] target to pull data points in the same class as close as possible. Consequently, these approaches try to shrink samples of the same class into one point in the feature space and may easily drop their similarity structure. To address this, we propose to learn a hypersphere for each class in RLL. Specifically, instead of pulling intraclass examples as compact as possible, we only force the distance of a positive pair smaller than a threshold, which is the diameter of each class's hypersphere. In this case, RLL can help preserve the similarity structure inside each class as much as possible.
Empirically, the convergence rate of DML methods highly depends on the possibility of seeing non-trivial samples [24]. Given an anchor (query), it is non-trivial to separate the positive and negative sets by a margin when all data points are considered. As a result, only a few ranked lists are perfectly optimized as the model improves during training. Therefore, our method can take advantage of a maximum of elements with non-zero losses and release the potentials for the learning procedure. The proposed RLL is illustrated in Figure 1.
Our contributions in this paper are listed as follows: • We propose a novel ranking-motivated structured loss (RLL) to learn discriminative embeddings. In contrast with previous ranking-motivated losses, we are the first to incorporate all non-trivial data points and exploit the structure among them. Besides, we learn a hypersphere for each class to preserve intraclass data distribution instead of shrinking each class into one point in the embedding space.

Preliminaries
where (x i , y i ) indicates i-th image and its corresponding class label. The total number of classes is C, i.e., y i ∈ [1, 2, ..., C]. The images from c-th class are represented as {x c i } Nc i=1 , where N c is the number of images in c-th class.

Ranking-Motivated Structured Losses
Triplet Loss [37,24] aims to pull the anchor point closer to the positive point than to the negative point by a fixed margin m: where Γ is the set of triplets, i, j and k are the indexes of anchor, positive and negative points, respectively. f is the embedding function, [·] + is the hinge function. N-pair-mc [28] exploits the structured relationship among multiple data points to learn the embedding function. Triplet loss pulls one positive point while pushing a negative one simultaneously. To improve the triplet loss by interacting with more negative classes and examples, Npair-mc aims to identify one positive example from N − 1 negative examples of N − 1 classes (one negative example per class): where are N pairs of examples from N different classes, i.e., y i = y j , ∀i = j. Here, x i and x + i are the query and the positive example respectively. i , x + j ) as close as possible and pushes all negative data points corresponding to x + i or x + j farther than a margin Figure 2: Illustration of different ranking-motivated structured losses. Different shapes (circle, triangle and square) represent different classes. For simplicity, only 3 classes are shown. The blue circle is an anchor (query). In triplet [24], the anchor is compared with only one negative example and one positive example. In N -pair-mc [28], Proxy-NCA [19] and Lifted Struct [20], α. Mathematically: where P and N respectively represent the sets of positive pairs and negative pairs. Given the query x i , Lifted Struct intends to identify one positive example from all corresponding negative data points.
Proxy-NCA [19] is proposed to address the sampling problem using proxies. The proxy W is a small set of data points that represent training classes in the original data. The proxy for u is chosen by: p(u) denotes the closest point to u from W. The Proxy-NCA loss is the traditional NCA loss defined over proxies instead of the original data points: ), (5) where Z is the negative set, p(u) and p(z) are the proxies of positive and negative points, respectively. a is the anchor and d(·, ·) is the Euclidean distance between two points. With static proxy assignment, i.e., one proxy per class, the performance is much better than dynamic proxy assignment. However, the proxies in the static proxy assignment are learned during training and similar to the class vectors of the fully connected layer in classification. Therefore, Proxy-NCA does not preserve the scalability of DML as the number of classes needs to be considered. The proposed RLL is ranking-motivated structured loss, which avoids two limitations of traditional methods by in-corporating all non-trivial data points and exploring intrinsic structured information among them. The illustration and comparison of different ranking-motivated losses and our method is presented in Figure 2.

Clustering-Motivated Structured Losses
Struct Clust [29] is recently proposed to learn the embedding function f by optimising the clustering quality metric. The proposed structured loss function is defined as: whereŷ and y are the predicted and ground-truth clustering assignments respectively. F measures the quality of the clustering on X with the label assignment and distance metric. NMI(y,ŷ) is the normalised mutual information [25]. NMI is 1 if the predicted clustering assignment is as good as the ground-truth and 0 if it is the worst.ŷ is predicted based on the learned distance metric f and Struct Clust [29] aims to learn f such that the F of the ground-truth assignment is larger than any other predicted clustering assignment. However, this algorithm is NP-hard as we need to optimise both the clustering medoids and the distance metric simultaneously. As a result, the loss augmented inference and refinement are applied to select facilities (clustering medoids) based on the greedy algorithm [18]. Large enough greedy search iterations are needed to find a local optimum, which might be costly.
Spectral Clust [16] also aims to optimise the quality of the clustering. Spectral Clust relaxes the problem of clustering with Bregman divergences [1] and computes the gradient in a closed-form, which reduces the algorithmic complexity of existing iterative methods, e.g., Struct Clust [29]. However, it is still non-trivial to learn deep models based on mini-batch implementation. Large batch size (1260 = 18 classes x 70 per class) is required for the clustering in the mini-batch. As a result, Spectral Clust iteratively computes submatrices and concatenates them into a single matrix for computing the loss and gradient, which might be expensive.
Both ranking-motivated and clustering-motivated structured loss functions exploit the structured similarity information among multiple data points. However, in general, clustering-motivated losses are more difficult to optimise than ranking-motivated losses.

Mining Non-trivial Examples
Example mining strategies are widely applied in existing methods [24,35,27,11,41,26,3,20,28,36] to provide non-trivial examples for faster convergence and better performance. In FaceNet [24], they propose to mine semi-hard negative samples. In N -pair-mc [28], hard negative class mining is proposed to provide informative negative examples. In Lifted Struct [20], harder negative examples are emphasized. In our work, we simply mine examples which have non-zero losses.

Methodology
Our objective is to learn a discriminative function f (a.k.a. deep metric) such that the similarity between positive pairs is higher than the similarity between negative pairs in the feature space. There exist at least two images in each class so that all classes can be evaluated. In this case, given a query from any class, we aim to identify its matching samples from all other examples.

Pairwise Constraint
Inspired by the former work on pairwise similarity constraint [6,38], we aim to pull positive examples closer than a predefined threshold (boundary). In addition, we intend to separate the positive and negative sets by a margin m. To achieve this, we choose the pairwise margin loss [38] as our basic pairwise constraint to construct the set-based similarity structure.
Given an image x i , we aim to push its negative point farther than a boundary α and pull its positive one closer than another boundary α − m. Thus m is the margin between two boundaries. Mathematically,

Ranked List Loss
Given a query x c i , we rank all other data points (gallery) according to their similarities to the query, which is illus-trated in Figure 1. In each ranked list, there are N c − 1 positive points in the positive set and k =c N k points in the negative set. The positive set with respect to the query Mining informative examples is widely adopted [24,41,3,20,28,36,9] because it allows fast convergence and good performance. By informative examples, we mean non-trivial data points which have non-zero losses, i.e., violating the pairwise constraint with respect to the query. Since they have zero gradients, including them for training will 'weaken' the contribution of non-trivial examples during gradient fusion as the model improves [9].
We mine both non-trivial positive and negative examples. For the query x c i , the non-trivial positive set after mining is represented as P We notice that the gradient magnitude with respect to any embedding is always one in Eq. (8). Mathematically, Consequently, the gradient magnitude of any embedding is only determined by our weighting strategy w ij . In this case, it is also convenient to evaluate its influence, which is studied in section 4.3. In Eq. (9), T ≥ 0 is the temperature parameter which controls the degree (slope) of weighting negative examples. If T = 0, it treats all non-trivial negative examples equally. If T = +∞, it becomes the hardest negative example mining. Optimisation Objective. For each query x c i , we propose to make it closer to its positive set P c,i than to its negative set N c,i by a margin m. At the same time, we force all negative examples to be farther than a boundary α. Consequently, we pull all samples from the same class into a hypersphere. The diameter of each class hypershpere is α − m.
In order to pull all non-trivial positive points in P * c,i together and learn a class hypersphere, we minimise: In RLL, we treat the two minimisation objectives equally and optimise them jointly: where λ controls the balance between positive and negative sets. We fix λ = 1 without tuning, which works well in our practice. In the ranked list of x c i , we regard the features of other examples as constants. Therefore, only f (x c i ) is updated based on the influence of weighted combination of other elements.

Learning Deep Models Based on RLL
To learn deep models, we implement our RLL based on mini-batch and stochastic gradient descent. Each minibatch is a randomly sampled subset of the whole training classes, which can be regarded as a simplified ranking problem with a smaller gallery (identifying the matching examples from a smaller number of classes).
Every image x c i in the mini-batch acts as the query (anchor) iteratively and the other images serve as gallery. The RLL of each mini-batch is represented as: N is the batch size. The learning of the deep embedding function f based on RLL is illustrated in Algorithm 1. The overall pipeline is shown in Figure 3. Computational Complexity. As illustrated in Algorithm 1, our proposed method does not require the input data to be prepared in any rigid format, e.g., triplets, n-pair tuplets. Instead, it takes random input images with multiclass labels. We conduct online iterative ranking and loss computation , the embedding function f , the learning rate β. 4: Output: Updated f . 5: Step 1: Step 2: Online iterative ranking and loss computation. 7: Mine non-trivial positive set P * c,i .

Implementation Details
In each mini-batch, we randomly sample C classes and K images per class. We set C = 60, K = 3. Thus N = 180, N c = K = 3, ∀c. In this case, there are 2 positive images and 177 negative images in the ranked list corresponding to each query, which simulates the global set-based similarity structure. More precisely, only a few matching examples exist in a large gallery. We use the same data preprocessing and augmentation as in [20]. Specifically, the input images are first resized to 256 × 256 and then cropped at 227 × 227. During training, we use random crop and random horizontal mirroring for data augmentation. For testing, we only use a single center crop without mirroring. We set the embedding size to 512 on all datasets following the setting in [16,28]. As done in [29,19], the features are L 2 normalised before computing their distance during training and testing.
We use GoogLeNet V2 [12] as our backbone network for fair comparison with [29,19,16]. In this net, there are three fully connected layers used in different layers. We re-fer them based on their relative locations as follows: L for low-level layer (inception-3c/output), M for mid-level layer (inception-4e/output) and H for high-level layer (inception-5b/output). Following [29,19,16], the pretrained model on ImageNet [23] is used for initialisation in our experiments. Three original 1000-neuron fully connected layers followed by the softmax layer and cross-entropy loss are changed to three 512-neuron fully connected layers followed by our proposed ranked list loss. According to [20], the new layers are randomly initialised and optimised with 10 times larger learning rate than the others for faster convergence.
We use GoogLeNet V2 [12] (with batch normalization) as our backbone network for fair comparison with [29,19,16]. Following them, the pretrained model on Im-ageNet [23] is used for initialisation in our experiments. Three original 1000-neuron fully connected layers followed by the softmax layer and cross-entropy loss are changed to three 512-neuron fully connected layers followed by our proposed ranked list loss. According to [20], the new layers are randomly initialised and optimised with 10 times larger learning rate than the others for faster convergence.
We implement our method in the Caffe deep learning framework [13]. We will release the source code and trained models for the ease of reproduction.  [20]. For CUB-200-2011 and CARS196, our method is evaluated on the original images (without using the bounding box information). Metrics. Following the standard [20], we report the image retrieval performance and the image clustering quality in terms of Recall@K and NMI [25] respectively. Training Settings. We run our experiments on a single Tesla V100 GPU with 32 GB RAM. The standard stochastic gradient descent (SGD) optimiser is used with a momentum of 0.9, a weight decay rate of 1e −5 . We set the base learning rate to 1e −2 for CARS196 and SOP. Smaller base learning rate 1e −3 is better for CUB as it overlaps a little with Im-ageNet and contains fewer images [15,34]. On CARS and CUB, the training procedure converges at 10k iterations, while 16k iterations for SOP. We set hyper-parameters empirically as follows m = 0.4, T = 10, α = 1.2.

Comparison with the State-of-the-art Methods
Competitors. We compared our method with the following methods which are implemented and tested under the same setting: Triplet Semihard, Lifted Struct, N-pair-mc, Struct Clust, Spectral Clust, and Proxy NCA 1 . The methods have been described in Section 2 except for Triplet Semihard [24] that mines semihard negative examples to improve the conventional triplet loss. Results. The comparison between our method and other competitors on both small datasets (CUB-200-2011 and CARS196) and large dataset (SOP) is presented in Table 1 and Table 2 respectively. As stated in Section 3.4, we have three fully connected layers in GoogLeNet V2. We report two sets of results. For fair comparison, we report the results of the high-level embedding, which is denoted as RLL-H. In addition, we find emperically that the multilevel embedding (RLL-(L,M,H) in short) by concatenating the lowlevel, mid-level and high-level embeddings can achieve better performance. We have the following observations from Table 1 and 2: • Overall, our method outperforms all the compared methods. This validates the effectiveness of our proposed loss function. all the previous methods in the image retrieval task. Specifically, the Recall@1 is higher than Proxy NCA by 2.4%. However, our method slightly underperforms with comparison to Proxy NCA. Interestingly, all methods perform similarly when this metric is used. This may indicate that NMI is not a good metric for a large-scale dataset. • RLL-(L,M,H) works much better than RLL-H on every dataset. This indicates that the multilevel embedding is more discriminative than the single-level feature representation in our method.
Discussion. It is worth to mention that although the performance of Proxy NCA is also good on CARS196 and SOP,  Proxy NCA does not preserve the scalability of deep metric learning as the number of classes needs to be considered. Proxy NCA learns one proxy per class, which also requires more learning parameters. Our method not only achieves better performance, but also preserves the scalability of deep metric learning, as shown in Table 2.

Ablation study 4.3.1 Mining Non-trivial Examples
As presented in Section 3.2, for each query, RLL mines examples which violate the pairwise constraint with respect to the query. Specifically, we mine negative examples whose distance is smaller than α in Eq. (12). Simultaneously, we mine positive examples whose distance is larger than α − m in Eq. (11). As a result, a margin m is established between negative and positive examples in each ranked list. Since the sample mining range is determined by the constraint parameters α, m, we conduct experiments on the large dataset SOP to analyse their influence. Impact of α. To study the impact of α, we set the tempera-ture T = 10 and the margin m = 0.4 in all experiments.
The results are presented in Table 3. We observe that a proper negative constraint α is important for RLL to learn discriminative embeddings. This is consistent with our intuition as α controls how much the negative examples are pushed away. Impact of m. To see the impact of m, we fix α = 1.2 and T = 10. The results of different margin values are presented in Table 4. We have three important observations: • When m > 0, RLL performs much better by around 3% than m = 0. It shows that the margin is important for improving the generalisation capability of RLL. • The margin-based RLL is insensitive to the margin value. The performance difference is smaller than 1% when m ranges from 0.2 to 1.2. • When m = α = 1.2, there is no mining over positive

Weighting Negative Examples
In this section, we conduct experiments to evaluate the influence of different temperatures T for weighting negative examples in Eq. (9). We fix m = 0.4 and α = 1.2 in all experiments. The temperature parameter T (T > 0) controls the slope of weighting. The results are presented in Table 5. We find: • When T = 0, RLL treats all non-trivial negative examples equally, i.e., no weighting is applied. The Recall@1 result is 78.8%, which is only 1% lower than the best performance using proper weighting. This demonstrates the superiority of RLL even without weighting. • RLL is insensitive to the setting of T . The performance gap is around 1% when T ranges from 0 to 20. In addition, the performance drops when T is large. This is because 'very' hard examples exist in the training data (e.g., outliers) [24,3].

Single-level versus Multilevel Embeddings
As demonstrated in Section 4.2, we find that RLL performs better using the multilevel embedding. To compare different single-level embeddings with the multilevel embedding, we conduct experiments on SOP. The results are reported in Table 6. We observe that: • All single-level embeddings perform worse than the multilevel embedding by around 3%. • The low-level embedding also performs very well in contrast with mid-level and high-level embeddings. The performance gap of different single-level embeddings is smaller than 1%. Note that the low-level embedding can be used for fast inference, which is essential for resource-constrained computational devices, e.g., mobile phones.

The Impact of Batch Size
The batch size is usually important in deep metric learning. It determines the size of problem we are going to solve every iteration during training. As presented in Section 3.3 and 3.4, the batch size decides the number of negative classes in the gallery. We conduct experiments on SOP to evaluate the influence of batch size in our approach. Specifically, we fix the number of images per class (∀c, N c = K = 3) and only change the number of classes (C ∈ {40, 50, 55, 60, 65}) in each mini-batch. The results are reported in Table 7. We can see that the batch size does not play a crucial role in RLL. The performance gap is only 0.6% when C changes from 120 to 195.

Conclusion
In this paper, the ranked list loss is proposed to exploit all informative data points in order to build a more informative structure for learning discriminative embeddings, which is not considered in the previous rankingmotivated losses. Given a query, RLL splits its positive and negative sets and forces a margin between them. In addition, non-trivial samples mining and negative examples weighting are exploited to make better use of all informative data points. The proposed RLL achieves stateof-the-art performance on three popular benchmarks using the single-level embedding. In addition, we find that RLL works better when using the multilevel embedding empirically.