Reducing Class Collapse in Metric Learning with Easy Positive Sampling
Authors: Elad Levi
Tete Xiao
Xiaolong Wang
trevor darrell
Venue:  (2021)

Abstract: Metric learning seeks perceptual embeddings where visually similar instances are close and dissimilar instances are apart, but learned representation can be sub-optimal when the distribution of intra-class samples is diverse and distinct sub-clusters are present. We theoretically prove and empirically show that under reasonable noise assumptions, prevalent embedding losses in metric learning, e.g., triplet loss, tend to project all samples of a class with various modes onto a single point in the embedding space, resulting in a class collapse that usually renders the space ill-sorted for classification or retrieval. To address this problem, we propose a simple modification to the embedding losses such that each sample selects its nearest same-class counterpart in a batch as the positive element in the tuple/triplet. This allows for the presence of multiple sub-clusters within each class. The adaptation can be integrated into a wide range of metric learning losses. Our method demonstrates clear benefits on various fine-grained image retrieval datasets over a variety of existing losses; qualitative retrieval results show that samples with similar visual patterns are indeed closer in the embedding space.


Under review as a conference paper at ICLR 2021
REDUCING CLASS COLLAPSE IN METRIC LEARNING WITH EASY POSITIVE SAMPLING
Anonymous authors Paper under double-blind review
ABSTRACT
Metric learning seeks perceptual embeddings where visually similar instances are close and dissimilar instances are apart, but learned representation can be sub-optimal when the distribution of intra-class samples is diverse and distinct sub-clusters are present. We theoretically prove and empirically show that under reasonable noise assumptions, prevalent embedding losses in metric learning, e.g., triplet loss, tend to project all samples of a class with various modes onto single point in the embedding space, resulting in class collapse that usually renders the space ill-sorted for classification or retrieval. To address this problem, we propose a simple modification to the embedding losses such that each sample selects its nearest same-class counterpart in batch as the positive element in the tuple. This allows for the presence of multiple sub-clusters within each class. The adaptation method demonstrates clear benefits on various fine-grained image retrieval datasets over a variety of existing losses; qualitative retrieval results show that samples with similar visual patterns are indeed closer in the embedding space.
be integrated into wide range of metric learning losses. Our
INTRODUCTION
Metric learning aims to learn an embedding function to lower dimensional space. in which semantic similarity translates to neighborhood relations the embedding space (Lowe 1995). Deep metric learning approaches achieve promising results in large variety of tasks such as face identification (Chopra et al., 20055 TTagmann al, 2014)55 (un et 2014), zero-shot learning (Frome et al. 2013). image retrieval (Hoffer & Ailon 2015 Gordo et al. 2016) and fine-grained recognition (Wang et al. 2014).
In this work we investigate the family of losses which optimize for embedding representation that enforces that all modes of intra-class appearance variation project to a single point in embedding space. Learning such embedding is very challenging when classes have diverse appearance. This happens especially in real-world scenarios where the class consists of multiple modes with diverse visual appearance. Pushing all these modes single point in the embedding space requires the network to memorize the relations between the different class modes, which could reduce the generalization capabilities of the network and result in sub-par performance.
Recently researchers observed that this phenomena, where all modes of class appearance "collapse" the same center, occurs in case of the classification SoftMax loss QQian al.). They proposed multi-center approach, where multiple centers for each class are used with the SoftMax loss to capture the hidden distribution of the data solve this issue. Instead of using SoftMax, it was shown that triplet loss may offer some relief from class collapsing (Wang et al. 2014) and this is certainly true forse-free environments. However, in this paper, we show that in real-world conditions with modest noise assumptions, triplet and other metric learning loss yet suffer from class collapse.
Rather than refine the loss, we argue the key lies an improved strategy for sampling and selecting the examples. Early work (Malisiewicz & Efros) 2008) proposed per-exemplar distance representation as a means to overcome class collapsing; inspired by this we introduce a simple sampling method to select positive pairs of training examples. Our method can be combined naturally with other popular sampling methods. In each training iteration, given an anchor and a batch of samples in the same category, our method selects the closest sample the anchor in the current embedding space the

---

Under review as a conference paper at ICLR 2021
h
L
u
P
A
h
L 4
P
CNN
5 20
B
5 4
Figure I: Given an anchor (circle with dark ring), our approach samples the closest positive example in the emhedding space the positive element. This results in pushing the anchor only towards the closest element direction (green arrow), which allows the emhedding have multiple clusters for each class.
positive sample. The metric learning loss is then computed based on the anchor and its positive paired sample.
We demonstrate the class collapsin phenomena
weal-world dataset, and show that method able to create more diverse embedding which result in a better generalization performance. We evaluate our method three standard zero-shot benchmarks: CARS199 (Krause al.] (013)). CUR200-2011 (Wah et al. 201T) and Omniglot (Lake et al.] 2015). Our method achieves a consistent performance enhancement with respect various baseline combinations of sampling methods and embedding losses.
2 RELATED WORK
Sampling methods. Designing a good sampling strategy is a key element in deep metric learning. Researchers have been proposed sampling methods when sampling both the negative examples as well as the positive pairs. For negative samples, studies have focused on sampling hard negatives
make training more efficient (Simo-Serra et al. 2015 Schroff al. 2013 Wang & Gupta 2015) Oh Song et al.) 2016)) Parkhi et | 2015). Recently, it has been shown that increasing the negative examples in training can significantly help unsupervised representation learning with contrastive
losses He et al. 2020 Wu et al., 2018 Chen et al. 2020).
Besides negative examples, methods for sampling hard positive examples have been developed in classification and detection tasks (Loshchilov & Hutter 2015 Shrivastaa et al., (2066] Arandjelovic al., 2016; [ubuk al., 2019) (inghh Leej 2017]] Wang et al.] The central idea to perform better augmentation improve the generalization in testing (Cubuk et al.) 2019). Apart from learning with SoftMax classification, |Arandjelovic et al. (2016) propose to perform metric learning by assigning the near instance from the same class as the positive instance. As the positive training set is noisy in their setting, this method leads to features invariant to different perspectives. Different from this approach, we use this method in clean setting, where the purpose is get the opposite result maintaining the inner-class modalities the embedding space. Xuan et al. (2020) also propose to use this positive sampling method with respect the N-pair loss (Sohn) 2016) in
order to relax the constraints of the loss on the intra-class relations. From a theoretic perspective, we prove that in a clean setting this relaxation is redundant for other popular metric losses like the triplet loss (Chechik et al. 2010) and margin loss (Wu et al., 2017). We formulate the noisy-environme setting and prove that in this case the triplet and margin losses also suffer from class-collapsing and using our purpose positive sampling method optimizes for solutions without class-collapsing. We also provide an empirical study that supports the theoretic analysis.
Noisy label problem. Learning with noisy labels is practical problem when applied to the real world (Scott et al.) 2013 Natarajan et al. 2013 (hen & Sanghavi 2019) Reed et al. 2014 Jiang et al. 2017 Khetan et al. 2017 Malach & Shalev-Shwarr (2017). especially when training with large-scale data (Sun et al. 2017). One line of work applies a data-driven curriculum learning approach where the data that most likely labeled correctly are used for learning in the beginning, and then harder data is taken into learning during a later phase (Jiang et al.) (017). Researchers have also tried on to
apply the loss only easiest top k-elements in the batch, determine by lowest current loss (Shen)
2

---

Under review as a conference paper at ICLR 2021
& Sanghavi 2019).
Inspired by these works, our method focuses selecting only the top easiest positive relations in the batch.
Beyond memorization. Deep networks shown to be extremely easy to memorize and over-fit to the training data (Zhang et al. 2016 Recht et al. 2018 2019). For example, is shown the network can be trained with randomly assigned labels on the ImageNet data, and obtain 100% training accuracy if augmentations are not adopted. Moreover, even the CIFAR-10 classifier performs well in the validation set, shown that it does not really generalize new collected data which is visually similar to the training and validation set (Recht et al. 2018). In this paper, we show that when allowing the network the freedom not to have to learn inner-class relation between different class modes, we can achieve much better generalization, and the representation can be applied in zert-shot setting.
PRELIMINARIES
Let X {I1,,., Zn be set of samples with labels E mm.. The objective of metric learning to learn an embedding f(:, 0) + R* in which the neighbourhood of each sample in the embedding space contains samples only from the same class. One of the common approaches for metric learning using embedding losses in which at each iteration, samples from the same class and samples from different classes chosen according to same sampling heuristic. The objective of the loss is push away projections of samples from different classes, and pull closer projections of samples from same class. In this section, introduce few popular embedding losses.
Notation: Let 2y E X, define: Df D1,2,, 11
2.1 In cases where there is no ambiguity
if y/ = y/ Lastly, we omit f and simply write Du,a, We also define the function 82,,2, otherwise
for every a E R, denote (a)+ == max (a, 0).
The Contrastive loss (Hadsell et al.) takes sample embeddings and pushes the samples from the different classes apart and pulls samples from the same class together.
c. (2i, xzy) 62, D/
D4 - ),,,,,)) (a D a
Here a margin parameter which defines the desired minimal distance between samples from different classes.
While the Contrastive loss imposes a constraint on pair of samples, the Triplet loss (Chechik et al. 2010) functions on triplct of samples. Given triplet Tas Zp: In X, the triplet loss is defined by
Clrip(aas Fp, F.r))
Sxantp (1 (1-82 Sr.. (Df -
DJ 2p Dppr
+ +a++
The Margin loss (Wu al. 2017) aims exploit the flexibility of Triplet loss while maintaining the computational efficiency of the Contrastive loss. This done by adding variable which determines the boundary between positive and negative pairs; given an anchor Ha E X the loss is defined by
f.B nargin (Ka, IT) Sxa.xx (Di Brn + aa+ + (1 D (B.. - Df D + +a++
4 CLASS-COLLAPSING
The contrastive loss objective is to pull all the samples with the same class to a single point in the embedding space. We call this the Class-collapsing property. Formally, embedding f : X - R has the collaacal property, if there exists a label y and point p E R" such that {f(x,) =
)} {p).
4.1 EMBEDDING LOSSES OPTIMAL SOLUTION
It is easy to see that an embedding function f that minimizes:
Ocon (f) n²
Σ
Loan (2t, x4g)
3

---

Under review as a conference paper at ICLR 2021
has the clals-collapsing property with respect to all classes. However, this is not necessarily true for the Triplet loss and the Margin loss.
For simplification for the rest of this subsection will assume there only two classes. Let C X a subset of elements such that all the elements A belongs to one class and all the element in A belong to the other class.
Recall some basic set definitions.
Definition 1. For all Y, 1 define:
1. The diameter of Y is defined by:
diam(Y) = -uuflll 2 1 EY}
2. The distance between Y and 7. is:
YY ~ = inf 21 y Y, 2 z}
is easy to see that if f X IR" is an embedding, such that diam (A)) <-a++ then:
(s)
1
Σ
Clrip (11, T3, = 0.
n
Moreover, fixing Br, a for every 24 E then:
O Marrgin (f,8)
Σ
f.8 margin (2i, 2z))
= 0.
n²
can be seen that indeed, the family of embedding which induce the global-minimum with respect to the Triplet loss and the Margin loss, is rich and diverse. However, as we will prove in the next subsection, this does not remain true noisy environment scenario.
4.2 NOISY ENVIRONMENT ANALYSIS
For simplicity will also discuss in this section the binary of two labels, however this could be extended easily to the multi- case.
The noisy environment scenario can be formulated by adding uncertainty to the label class. More formally, let = (Yi..., 0.5 p such that: [A,l and
.i, Y, be a set independent binary random variables. Let A1,.., Ag C X,
E A
P(Y k)
0= 1- & Ak
We can also reformulate 8 as a binary random variable such that:
8y,, 1y;
For the Triplet loss define:
E. (Ira, 2y, 2x) E (ōx., (1 (r) (D&
DJ. Des.e2 +
We searching for embedding function which minimize
10
Σ
ECtripp (3,,
Theorem 1. Let f. O - RM be an embedding, which minimize EDtrip then f has the class- collapsing property with respect to all classes.
4

---

Under review as a conference paper at ICLR 2021
Similarly, define:
E. (Ii, [5}) Edy,y; (D -s,, +a)+ + B(1 101--11111yh -8r,))) (Bx; D D2 +a)+
Theorem 2. Let f : Rm be an embedding, which minimize
ma (f.
Σ
ELmargin (Ii, xz),
Tt
then I has the class-collapsing property with respect to all classes.
The proof of the last two theorems can be find in Appendix A.
In conclusion, although theorctically in clean environments the Triplet loss and Margin loss should allow more flexible embedding solutions, this does not remain true when noise considered. On a real-world data, where mislabeling and ambiguity can be usually be found, the optimal solution with respect to both these losses becomes degenerate.
4.3 EASY POSITIVE SAMPLING (EPS)
Using standard embedding losses for metric learning can result in an embedding space in which visually diverse samples from the same class are all concentrated in a single location in the embedding space. Since the standard evaluation and prediction method for image retrieval tasks are typically based on properties of the K-nearest neighbours in the embedding space, the class-collapsing property a side-effect which is not necessarily in order to get optimal results. the next section, we will show experimental results, which support the assumption that complete class-collapsing hurt the generalization capability of the network.
To address the class-collapsing issue propose simple method for sampling, which results in weakening the objective penalty on the inner-class relations, by applying the loss only on the closest positive sample. Formally we define the EPS sampling in the following way; given mini-batch with N samples, for each sample a, let C. be the set of elements from the same class as a in the mini-batch, we choose the positive sample Pa to be
min (llf(t) - f(a)l)) tEC.
choose according various options. In this paper we use the following methods: (a) Choosing randomly from all the elements which are not in C.. (b) Using distance sampling (Wu et al. 2017). (c) semi-hard sampling (Schroff al. 2015). (d) MS hard-mining sampling (Wang et al. 2019). We then apply the loss on the triplets (a, Pa; na). Using such sampling changes the loss objective such that instead of pulling all samples in the mini-batch from the same class to be close to the anchor, it only pulls the closest sample to the anchor (with respect to the embedding space) in the mini-batch, see Figure T
For negative samples na
In Appendix B, we formalize this method in the noisy environment framework. We prove (Claim 1,2) that every embedding which has the class collapsing property is nor minimal solution with respect to both the margin and the triplet loss with the easy positive sampling. Furthermore, in Claim 3,4 we prove that the objective of the losses with EPS on tuples/triplets is to push away every element (including positive elements), that is not in the k-closest elements to the anchor, where k is determined by the noise level p. Therefore, we apply the EPS method on a mini-batch which has small numbers of positive elements from each modality, in such case adding the EPS to the losses not only relax the constraints on the embedding, allowing the embedding to have multiple inner-clusters. also optimizes the embedding to have this form.
EXPERIMENTS
We test our EPS method on image retrieval and clustering datasets. We evaluate the image retrieval quality based on the recall@k k metric (Jégou et al.) (011)) and the clustering quality by using the normalized mutual information score (NMI) (Manning et al.) 2008). The NMI measures the quality of clustering alignments between the clusters induced by the ground truth labels and clusters induced by applying clustering algorithm the embedding space. The common practice to choose the NMI
5

---

Under review as a conference paper at ICLR 2021
Triplct
EPS+Triplet
Figure 2: Embedding examples from the MNIST validation set, after training using only even/odd labels. Different colors indicate different digits. Left: Using Triplet-loss, class collapsing pushes intra-class digits overlapping clusters. Right: With EPS, different digits form separate clusters. Retrieval or classification using the odd-vs-even task/metric is more effectively implemented using the embedding on the right, even though the embedding the left is learned with loss that more strictly optimizes for the task.
Table 1: Recall @k evaluated on MNIST dataset. The train classes are digits 0-5 and the test classes are digits 6-9
MNIST Train Digits
MNIST Test Digits
model
R@ 1
R@5
R@ 10
R@1
R@5
R@ 10
Triplet
42.01
87.51
96.56
35.16
80.86
93.26
EPS Triplet [ours]
65.78
93.57
97.38
42.31
83.86
93.61
clusters is by using K- algorithm on the embedding space, with K equal to the number of classes. However, this prevents from the measurement capturing more diverse solutions in which homogeneous clusters appear only when using larger amount of clusters. Regular NMI prefers solutions with closs-coll.psing. Therefore, we increase the number of clusters the NMI evaluation (denote it by NMI+) we also report the regular NMI score.
5.1 MNIST EVEN/ODD EXAMPLE
To demonstrate the class-collapsing phenomena, we take the MNIST dataset (Lecun et al. 1998). and split the digits according to odd and even. From visual perspective this an arbitrary separation. We took the first 6 digits for training and left the remaining 4 digits for testing. We used a simple shallow architecture which result in embedding function from the image space R (For implementation details see Appendix C).
We train the network using the triplet loss. We compare our sampling method to random sampling of positive examples (the regular loss). As can be seen in Figure 2 the regular training without EPS suffers from class-collapsing. Training with EPS creates richer embedding which there is a clear separation not only between the two-classes, but also between different digits from the same class. As expected, the class-collapsing embedding preforms worse on the test data with the unseen digits, see Table MI
5.2 FINE-GRAINED RECOGNITION EVALUATION
We compare our approach to previous popular sampling methods and losses. The evaluation is conducted on standard benchmarks for zero-shot learning and image retrieval following the common splitting and evaluation practice (Wu et al., 2017 Movshovitz-Attias et al., 2017 Brattoli et al. 2019) We build our implementation on top the framework Roth et al.) which allow us have a fair comparison between all the tested methods with an embedding of fix size (128). For more implementation details and consistency of the results, see Appendix C.
5.2. DATASETS
We evaluate model the following datasets.

---

Under review as a conference paper at ICLR 2021
Table Recall@k and NMI performance on Cars and CUB200- 2011. NMI+ indicate the NMI measurement when using 10 (number of classes) clusters. Our EPS method improves in all cases. t: Our re-implemented version with the same embedding dimension.
Cars- 196
CUB-200
model
R@2
R @4
NMI
NMI+
R@
R@2
R@4
NMI
NMI+
Trip. SH
51.5
63.8
73.5
53.4
42.6
55.0
66.4
55.4
Trip. + SH
76.1
84.4
90.0
65.1
68.5
61.5
73.4
82.5
66.2
68.1
ProxyNCA
73.2
82.4
86.4
64.9
49.2
61.9
67.9
64.9
Pro
77.1
85.2
91.2
65.6
68.9
63.1
74.8
83.8
67.2
68.7
Dist-Margin
79.6
86.5
91.9
69.1
70.4
63.6
74.4
83.1
69.0
68.7
MS
77.3
85.3
90.5
57.4
69.8
80.0
MSI
81.2
89.1
93.5
60.5
71.1
62.3
73.3
82.1
59.8
68.0
EPS + Trip. + SH
78.3
85.9
91.4
59.8
69.8
61.8
73.6
82.4
62.4
68.0
EPS Dist-Margin
83.6
89.5
93.6
67.3
72.4
64.7
75,2
84.3
68.2
69.4
EPS MS
82.9
89.4
93.2
60.0
72.0
82.5
61.2
68.2
Table 3: Recall@k and NMI performance on Omniglot dataset. In both cases the training was done with only language labels. Right: evaluation on language labels. Left:: evaluation on letter labels. NMI+ indicate the NMI measurement when using 30mmeee of classes) clusters. Our EPS method improves in both cases.
Omniglot-letters
Omniglot-languagee
model
R@1
R@2
R@4
R@g
NMI
R@D 1
R@2
R@4
R@8
NMI+
Trip. + SH Pro
49,4
60.0
69.2
76.9
66.2
71.0
80.2
87.6
92.4
38.7
49.1
60.4
70.9
78.9
69.0
73.0
82.1
88.8
93.5
43.3
Dist- Dist-Margin
49.4
61.1
70.1
79.2
68.9
73.2
82.3
89.1
94.0
43,5
MS
57.7
68.5
77.3
83.8
69.2
78.8
92.0
95.4
46.0
EPS + Trip. + SH
68.4
79.3
86.9
92.1
79.6
85,2
91.1
94.9
97.3
52.6
EPS Dist-Margin
66.2
76.7
84.8
90.3
77.9
83.0
89.4
93.6
96.4
50.7
EPS + MS
68.7
79.1
86.9
92.2
77.3
86.2
91.7
94.9
97.2
53.8
Cars-196 Krause et al., 2013), which contains 16,185 images of 196 car models. We follow the split in Wu et al. (2017), using 98 classes for training and 98 classes for testing.
CUB200-2011 Wah et 2011), which contains 11,788 images of 200 bird species. We also follow Wu et al. (2017). using 100 classes for training and 100 for testing.
Omniglot (Lake et al. 2013). which contains 1623 handwritten characters from 50 alphabet. our experiments we only use the alphabets labels during the training process, i.e, all
characters from the same alphabet has the same class. We follow the split in Lake et al. (015)) using 30 alphabets for training and for testing.
5.2.2 RESULTS
We tested our sampling method with different losses: Triplet (Chechik al. 2010), Margin (Wul et al. (2017) and Multi-Similarity (MS) (Wang et al. 2019). ). For the Margin loss experiment, we combine our sampling method with distance sampling (Wu et 2017); this could be done because the distance sampling only constrains on the negative samples, where our method only constrains on the positive samples. We set the margin a 0.2 and initialized 8 1.2 in (Wu al., 2017). For the Triplet we combine our method with semi-hard sampling (Schroff et al. (015) by fixing the positive according to EPS and then using semi-hard sampling for choosing the MS loss replace the positive hard-mining method with EPS and use the same hard-negative method. We use the same hyper--prennnn paremeters as in (Wang et al. 2019) a = 2, À = 1, 50.
negative examples. For
Results are summarized in Tables 2 and We can see that our method achieves the best performance on all tested datasets. is important to note that in the baseline models, when using Semi-har sampling, the sampling strategy was done also the positive part suggest in the original papers. We see that replacing the semi-hard positive sampling with easy posiitiv sampling, improve results in all the experiments. The improvement gain becomes larger as the dataset classes can be partitioned
7

---

Under review as a conference paper at ICLR 2021
Distance-margin
0.80
EPS Semi-hard negalive
Semi-hard
0.75
0.7-
Distance margin
0.70
Recal@
e0.63
0.5
0.5-
0.55
Recall@1
0.4-
0.3
0.4
10
10
d0
Epoch (a)
Number of positive samples in batch
Figure 3: Results on Omniglot-letters. (a) Recall@1 I performance of each model per epoch. (b) performance of EPS distance-margin model on the Omniglot dataset, function of the number of positive samples in hatch (where zero is equivalent to only using only distance sampling). Increasing the number the number of positive samples enhances the model performance.
Query
EPS+Dist-Margin
Dist-Margin
Figure 4: Retrieval results for randomly chosen query images in Cars196 dataset. Using EPS creates more homogeneous neighbourhood relationships with respect to the car viewpoint.
more naturally to small number of sub-clusters which are visually homogeneous. In Cars dataset it is the car viewpoint, where in Omniglot it is the letters each language. As can be seen in Table using EPS on the Omniglot dataset result in creating nearest neighbor in the embedding consists of element of the same letter, although the network was trained without these labels. In Figure we see qualitatively comparison of CARS16 models results. EPS seems to create more homogeneous neighbourhood relationships with respect to the the viewpoint of the car. More results and comparisons be find in Appendix C.
embedding in which in most cases the
5.2.3 POSITIVE BATCH SIZE EFFECT
An important hyperparameter in our sampling method is the number of positive batch samples, from which we select the closest one in the embedding space to the anchor. If the class is visually diverse and the number of positive samples batch is low, than with high probability the set of all the positive samples will not contain any visually similar image the anchor. In case of the Omniglot experiment, the effect this hyperparameter is clear; It determines the probability that the set of positive samples will include sample from the same letter the anchor letter. As can be seen in Figure Bbb), the performance of the model increases as the probability of having another sample with the same letter the anchor increases.
CONCLUSION
In this work we demonstrate the importance of positive sampling strategies when using embedding losses for metric learning. We investigate the class collapsing phenomena with respect to popular embedding losses such as the Triplet loss and the Margin loss. While clean environments there is a diverse and rich family of optimal solutions, when noise is present, the optimal solution collapses
8

---

Under review as a conference paper at ICLR 2021
to degenerate embedding. We propose simple solution this issue based 'easy' positive sampling, and prove that indeed adding this sampling results in non-degenerate embeddings. We also compare and evaluate method standard image retrieval datasets, and demonstrate consistent performance boost on all of them. While our method and results have been limited to metric learning frameworks, we believe that sampling scheme will also be useful in other related settings, including supervised contrastive learning, which we leave to future work.
REFERENCES
Relja Arandjelovic, Petr Gronat, Akihiko Torii, Tomas Pajdla, and Josef Sivie. Netvlad: Can architecture for weakly supervised place recognition. In Proceedings the IEEE conference computer vision and pattern recognition, pp. 5297-5307, 2016.
Biagio Brattoli, Karsten Roth, and Björn Ommer. Mic: Mining interclass characteristics for improved metric learning. In Proceedings of the Intl. Conf. Computer Vision (ICCV), 2019.
Gal Chechik, Varun Sharma, Uri Shalit, and Samy Bengio. Large scale online learning of image similarity through ranking. Journal of Machine Learning Research, 11:1 109-1135, 2010. doi: 10.1 145/1756006. 1756042.
Ting Chen, Simon Komblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. 2020.
Sumit Chopra, Raia Hadsell, and Yann LeCun. Learning similarity metric discriminatively. with application to face verification. In 2005 IEEE Computer Society Conference Computer Vision and Pottern Recognition (CVPR'OL 05), volume pp. 339-546. IEEE, 2005.
Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaugment: Learning augmentation strategies from data. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 113 123, 2019.
Istvan Fehervari, Avinash Ravichandran, and Srikar Appalaraju. Unbiased evaluation of deep metric learning algorithms, 2019.
Andrea Frome, Greg S Corrado, Jon Shiens, Samy Bengio, Jeff Dean, Mare' Aurelio Ranzato, and Tomas Mikolov. Devise: A deep visual-semantic emhedding model. Advances neural information processing systems, pp. 2121-2129, 2013.
Albert Gordo, Jon Almazán, Jerome Revaud, and Diane Larlus. Deep image retrieval: Learning global representations for image search. In European conference on computer vision, pp. 241-257. Springer, 2016.
R. Hadsell, S. Chopra, LeCun, Dimensionality reduction by learning an invariant mapping. In 2006 IEEE Computer Society Conference on Computer Vision and Pottern Recognition Volume 2 (CVPR06). IEEE. doi: 10.1 20.1 100. htttp: orriioorgioo 10. 1109/cvpr 2006. 100
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In Computer Vision ECCV 2016, pp. 635-645. Springer International Publishing. 2016. doi: 10.1007/
978-3-319-44493-00_
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2020.
Elad Hoffer and Nir Ailon. Deep metric learning using triplet network. In International Workshop Similarity- Based Pattern Recognition, pp. 84-92. Springer, 2015.
H Jégou, M Douze, and C Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117-128 jan 2011. doi: 10. 10.11099ppami.2011 2010..57
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning data data-driven curriculum for very deep neural networks corrupted labels. arXiv preprint 172.v:171..05055. 2017.
Ashish Khetan, Zachary C Lipton, and Anima Anandkumar. Learning from noisy singly-labeled data, arXiv preprint arXiv: arxiv: 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014. URL http:
//arxiv.ore wtgg/bs//////oooooo/ooo/...b.aaa /tos//411... 1412. 6980 cite the 3rd International Conference for Learning Representations, San Diego, 2015.
Published as a conference paper

---

Under review as a conference paper at ICLR 2021
Jonathan Krause, Michael Stark. Jia Deng, and Li Fei-Fei. 3d object representations for fine-grained catego- rization. In 4th International IEEE Workshop on 3D Representation and Recognition (3dRR-13), Sydney, Australia, 2013.
B. M. Lake, R. Salakhutdinov, and J. B. Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 333 1338,, dec 2015. doi: 10.1 10.11266cceemee.aub30000
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-basse learning applicd to document recognition. Proceedings of the IEEE, 86(1 1):2278 2324, 1998. doi: 10.1 199.5777777
Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. arXiv preprint arXiv:1511.0633 2015.
David G. Lowe. Similarity metric learning for a variable-kernel classifier. Neural Computation, 7(1):72-85, jan 1995. doi: 00.116//neco.11955..111
Eran Malach and Shai Shalev-Shwartz. Decoupling" when to update" from" how to update", In Advances in Neural Information Processing Systems, pp. 960-970, 2017.
Tomasz Malisiewiez and Alexei A. Efros. Recognition by association learning per-exemplar distances. In CVPR, June 2008.
Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schutze. Introduction to Information Retrieval. Cambridge University Press, 2008. doi: 10. 10.10///60978005 1881991077511111.11111 1809071.
Yair Movshovitz Alexander Toshev, Thomas K. Leung. Sergey loffe, and Saurabh Singh. No fuss distance metric learning using proxies. In 2017 IEEF International Conference on Computer Vision (ICCV). [EEE, oct 2017. doi: 10. 1099ccccccc............
Kevin Musgrave, Serge Belongie, and Ser-Nam Lim. A metric learning reality check, 2020.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep Ravikumar, and Ambuj Tewari, Learning with noisy labels.
In Advances in neural information processing systems, pp. 1196-1204, 2013.
Hyun Oh Song. Yu Xiang. Stefanie Jegelka, and Silvio Savarese. Deep metric learning via lifted structured fcature embedding. In Proceedings of the IEFE conference on computer vision and pattern recognition, pp- 4004-4012, 2, 2016.
Omkar M Parkhi, Andrea Vedaldi, and Andrew Zisserman. Deep face recognition. 2015.
Qi Qian, Lei Shang, Baigui Sun, Juhua Hu, Hao Li, and Rong Jin. Softtriple loss: Deep metric learning without triplet sampling.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do cifar- 10 classifiers generalize c0f arXiv preprint (00.::8800000555/ 2018.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. imagenet classifiers generalize to imagenet? arXiv preprint arXiv:1902.1081/ 1,
Scott Reed, Honglak Lee. Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabinovich. Training deep neural networks on noisy labels with bootstrapping. arXiv preprint arXiv: 1412.6596, 2014.
Karsten Roth, Timo Milbich, Samarth Sinha, Prateek Gupta, Björn Ommer, and Joseph Paul Cohen. Revisiting training strategies and generalization performance deep metric learning.
Florian Schroff, Dmitry Kalenichenko, and James Philbin, FaceNet: unified emhedding for face recognition and clustering. In 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEFF, jun 2015. doi:
Clayton Scott, Gilles Blanchard, and Gregory Handy. Classification with asymmetric label noise: Consistency and maximal denoising. Conference On Learning Theory, pp. 489-511, 2013.
Yanyao Shen Sujay Sanghavi. Learning with bad training data iterative trimmed loss minimization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. Beach, Califomia, USA, 09-15 Jun 2019. PMLR. URL http: httt:://prrceee// in sshen 9e. h
Long press/v97/
10

---

Under review as a conference paper at ICLR 2021
Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick. Training region-based object detectors with online hard example mining. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 761-769, 2016.
Edgar Simo--eera, Eduard Trulls, Luis Ferraz, lasonas Kokkinos, Pascal Fua, and Francesc Moreno- Moreno-Noguer.. Dis- criminative learning deep convolutional feature point descriptors. In Proceedings of the IEEE International Conference on Computer Vision, pp. 118-126, 2015.
Krishna Kumar Singh and Yong Jae Lee. Hide and-seck: Forcing network to be meticulous for weakly- supervised ohject and action localization. In 2017 IEEE international conference computer vision (ICCV), pp. 3544-3553. IEFE, 2017.
Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Gameet (eds.), Advances Neural Information Processing Systems, volume 29, pp. 1857-1865. Curran Associates, Inc.. 2016. URL/itttps//ppoceeeiie www.:ngsssnrrrrs.ccccooo.eee cctpppprr 2016/ Le/ 2. Pap.
Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. Revisiting unreasonable effectiveness of data in deep learning era. In Proceedings of the IEEE international conference on computer vision, pp. 843-852, 2017.
Yi Sun, Yuheng Chen, Xiaogang Wang, and Xiaoou Tang. Deep learning face representation by joint identification-verifeee veriiicainn.......iiin..... Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and Q. Wein- berger (eds.). Advances in Neural Information Processing Systems 27, pp. 1988-1988988 1996. Curran Associates, Inc., 2014.
Yaniv Taigman, Ming Yang, Marc' Aurelio Ranzato, Lior Wolf. Deepface: Closing gap to human-leve performance face verification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1701-1708, 2014.
L.I.P. van der Maaten and G.E. Hinton. Visualizing high-dimensional data using t-sne. 2008.
C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongic. The Caltech-UCS Birds-200-2011 Datasct. Technical Report ONS-TRR-201-000 California Institute of Technology, 2011.
Jiang Wang, Yang Song. Thomas Leung, Chuck Rosenberg, Jingbin Wang. James Philbin, Bo Chen, and Ying Wu. Learning fine-graines image similarity with deep ranking. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1386 1393, 2014.
Xiaolong Wang and Abhinav Gupta. Unsupervised learning of visual representations using videos. In ICCV, 2015.
Xiaolong Wang, Abhinav Shrivastava, and Abhinav Gupta. f-ssstrenn:: Hard positive generation via adversary for ohject detection. In CVPR, 2017.
Xun Wang, Xintong Han, Weilin Huang, Dengke Dong, and Matthew R Scott. Multi-similarity loss with general pair weighting for deep metric learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5022-5030, 2019.
Chao-Yuan Wu, R. Manmatha, Alexander J. Smola, and Philipp Krahenbuhl. Sampling matters in deep embedding learning. In 2017 IEEE International Conference Computer Vision (ICCV), IEEE, oct 2017. doi: 10.1 1099//cv.2017.3099
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via paramermetriic instance discrimination. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 3733-3742, 2018
Hong Xuan, Abby Stylianou, and Robert Pless. Improved embeddings with easy positive triplet mining. In IEEE Winter Conference Applications of Computer Vision. WACV 2020, Snowmass Village, CO. USA, March 1-5, 2020, pp. 2463-24422 2471. IEEE, 2020. doi: 101110/WACCV5577220000009.4 https: pttps://dci... wtw.aci...ggo.oooooooooooooooo.. 10. 1109/ 1tt.:/....1////44557777
URL
2020. 9093432
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530 2016.
11

---

Under review as a conference paper at ICLR 2021
APPENDIX
A: PROOFS FOR THE THEOREMS IN SUBSECION 4.2
Theorem 1. Let f O + I be embedding, which minimize RDtrsplf), then f has the class-collapsing properry with respect all classes.
Proof. Define new random variables such that for every 1 S 11, $
= =2
M1 (X,
else
observe that
0y1.32 (1 11-dxy or) =
Σ
1y (22,)
E
1y (V3, Y2)
Since the variables are independent
B( (1 - -x, =
Σ
B(1y B(hm..r Y2)) + BB(y o2 Y2))
15 r1gling
Define: D(11, x2) = (D2j.a2 Dal,ag + a)
Rearranging the terms we get
n [f)r E
(B(or,, ry), 12,
Σ
(B(1y)=m) B(hrr ((Y2, Ys)) + (1( (Y,, D(11,
Σ
122, Ys)) (B)) 2x) E(1y) -00l),
((11,
41.42
Therefore, if
k(i.j.k;r,ra)) (E((1))))) +
B(1n=r2) + D(a1,
then B0:rip (f) be written
EDerip
Σ
(YG. K(i.jkk)rr.r)))
12
For every æi E X, define:
(BOurip n2
(Y,, K K(r, 14,
Let f X I be embedding, fix 1 1 and Ar, æj X with
|| fxx)) f(xs))l =m, [1 f(xx)] = h.
By definition:
(h a)+ + q(w h a)+
ri r A
(h a) + p h a)+
n2 =rAm Ar
m,, =
p (h w a)+ --pppwwae -
Fi m=AAmE =r
8. (h w + a) + h+
12

---

Under review as a conference paper at ICLR 2021
Since p < 1. in order get minimal (i.j, r1, value, h and w must satisfy 1/ case we have
S In this
(p + q) a (h w)(p 9) ri = F #
4p+ a (w 6) r2 = a #
2.
T== 12
a.
Therefore,
Σ
(e (x)) K 12, (B((h (Y,, Yx)) K
= -p
Σ
(B( (Y,, Y2) (B( (Y,, (x,)))))) Yu)))++
(h (p 9))(
Σ
B(hrr, Yx)) E( (Y,, Yk))
We split to three cases:
If Fy E A, or 2h & A, then: R(hr.r (Y,, V&)) = 1B(h V&)). Hence, B(h (Y,, Yk)) B(hraa (K, Yz)) 0
(h (h-w 4))
Σ
"26(1,.--1,44
2. If 2, A, and 24 Ar. then E(hroz (Y,, Yk)) > B(h (Y,, Yx)), therefore
(p 2))(
Σ
B(h (Y,, Yk)) (Y,,,, Yx))
r2E(L.rr-L++1.))
Since p > 0.5 and w| S a, minimal value achieved whenever = and w a.
same way if æx E A, and xy é Ar, then E(lon (8,, E(hr,ra (Y,, Vx)) and minimal value is achieved whenever h = a and w = O.
In conclusion, if x: E Ar, an embedding f" satisfics
R ift (a;;) (x:)) for every æy E Ar, and ("xx (x:))l for every æe & Ar.
(BDrrip (f)),, = min((BB
We will now prove the same thcorem with respect to the margin loss. Theorem 2. Let f: O Th be embedding, which minimize
EDmargin
Σ
T.
(Ii, Tz);
then f has the class-collapsing property with respect to all classes.
Proof. Observe that if 21, T. E Ar, then
E.J. E. (2,, xT) = p (Deyay - 3w; + aa) (1 p) (Bm: Daçan a)+
Since < < 1, then the maximal value is achieved whenever Daries 32,1 S a. in this case:
ECJ Eaargnn (21, 2,) (2p 1) (Day.y B2,)
the same way in case x, E A, and x, & A, then:
yarggn (2), (2p 1) (Bor, Daniry))
Combining both directions we get:
Σ ELí Eaaggnn (21, = (2p - 1). X
Σ
Dasay Σ Danay
YGEA
Y,RA
Since: 0.5 and Dan,,y 32, S a, the minimal value is achieved whenever DzLaA 0, Dar,n 20 and 32, a. for every 34, Jjj E Ar; 2% A..
13

---

Under review as a conference paper at ICLR 2021
B:
EASY POSITIVE SAMPLING NOISY ENVIRONMENT
this subsection we analyse the EPS method from the theoretical prospective, using the framework defined in
Scction 4. We use the same notions as sections 3 and
Define: (yt, Ms)
{
Us Dav..y min DaLaa Dk =v}.. Then, the easy positive sampling loss
else
can be defined by:
Σ
(2yt Cyrip 22,,
for the triplct loss and
Lh finergm ( (11, + lusts fi fiaagon (2i, U,)
for the margin loss.
In the noisy environment stochastic case, using section 4 notions, d become a random variable:
{
=
A < Dacwr)) + Y, Yi)
(Y,, (
else
Therefore, the triplet loss with EPS in the noisy environment case, become:
EC (t 2y 2x) (&(Y, Y,) 8y,,y - -vr..))))) (Dbr.s Disian + aa) for the margin loss with EPS we have:
El''rmmarriin (zi, x2,) = E( Y,) Sy.x,) ( - B2, + E((1-orx))) (B,, DEuir +a)+
As in section 4.2 we assume that Y = (Yi, Yn) is set of independent binary random variables. Let
Ai,.,,A C 0.5 < < 1 such that: |A,l and
J; E A
ii & As P(Y. = k) =
For simplicity assume that every 1 i satisfies en +1 to ao A,
We prove first that the minimal embedding with respect to both losses does not satisfy the class collapsing property. Let fi be embedding function such that:
DD = -so (3r) E Ar)
else
and fo embedding such that:
D = So (3r) E AA) ~ (li 2n AJ
4)
V
(1>
Aj
2m
else
fi represent the case of class collapsing, where f2 represent the case where there are two modalities for the first class. In order to show that the minimal embedding does not satisfy the class collapsing property it suffice prove that
Chrsttio Σ 154JAAn
Σ
IT.)
15LJAA5
and
Σ
cla C
(Z,,
Σ 15AJ5h
C (D:, 2,).
n
n
15tJ5N
Remark: For both losses the definition requires a strict order between the elements, therefore by distance zero, we meant infinitesimal close, the order between the elements inside the sub-clusters is random, and element hetween set A₁ are closer then set Ai in both embeddings. For simplification neglect this infinitesimal constants in the proofs.
14

---

Under review as a conference paper at ICLR 2021
Claim 1. There exists M such that if M, then:
Σ
C (1,,
Σ
L (1,,
Proof. Fix æ1, WOLOG we may assume in both embeddings that DMA < D for everyy j E (1,2) and
isich S n. It suffice to prove that
1
Σ
(EP - C (1i, >
It ISAASR
Let (1 p). observe that
P( A x =p m+ of 2-m + x 2- m < 2pp ISKj
where = 1 Y E Ai)l. Thus i we have
Ee 25, mz) SP( A xi) a.a S $4.00 4.c0p"1
15t3)
Therefore,
mf2t-1)
1 1-22121-12/24 p/ d.p 1-9
Σ J5hgn
(2
S Σ 4-pp' = 4n-ap
Σ 5mu
For j S क and k S 22 of k we have C kpssiap (11, 2x) = L Sp (1,,
Tz. #z. Hence, the only
case left j S 27 and <k n. In this case: C ps (1), 2x) = 0, where
Erstrip (T1, )x, = (p² ---1+ + o² pf 4 a 2 9 ++
and we get:
Σ
Lt ch (11. Epstrip (11, Tz xz) 2
15 ft # 5
a q
9' = a 9².
1 gm
n aq²
1
1 1-9
1 -
Choosing M such that
1 - q M/21
M - q
a q
> 4
a.ap
1
will satisfy that for every n > M:
1
Σ
Capstrig T3,
Σ
Chpstrip (1,)
Claim
There exists such that in 2 M then:
Σ
Σ
Cersmergm (21,
15
156j5a
Proof. For every 1 S
R or p<r we have:
ch C Ch CEPSmarya
<iSs B:
c C (Rn,2;) = 2.p. Br, + (p-9g-2 + (2 (2.a Bas)
while:
C 21) =2.p.q p. (8,, + a) 1 + (2 (a Bz))
15

---

Under review as a conference paper at ICLR 2021
Since > the second therm tend to zero. Therefore, taking M such that
2qp > (p 21 -2
+
will satisfy that for each n 2 M
? Σ
Σ
gm (21,
71
156.5m
previous two claims we prove that the class collapsing solution is not minimal with respect to both the PPSarrgin and the Ptttipplt.. the following claims we prove that not only is not minimal solution, looking locally on the direct effect of the EPS losses on a sample which is not one of the closest elements to to the anchor. We prove that the optimal solution in this case is embedding in which the distance between the sample the anchor is equal to the margin hyperparameter.
Let f be an embedding. For every i, let i1,,,, be such that Dessery < Then there exists M such that for every j M the minimal embedding for C whenever DL B2;
Claim 3.
<Di <.. De
L'EPSmargin (I; is achived
Proof. Fix æı, as the previous claims we will assume:
D < DL D/ < D D
As was prove in in Claim P(Auguy Y, + Y)) S 4p',thus thus
E(6(Y,, 8y,,,) SP( A Ys s -1 0
15/43
Since the minimal solution for (( or,,y)) (D/y.ag - 8eg + +a) + +E1 )y,,,) . (Bz, D' Desves + a)+
satisfics 10x. - Dbu S a, we have:
Ch (011)margin(11123)) a. (V, Yj) ,r,,,, E(1 ,r+
(D Be,) (B((((, Yj), ,y,,)) E(1 - xy,,))
Since 1B(1- - -dy,,,) 2 2pg. there exists M such every j > M satisfies
(Y) dy,,)) - B(1 8x.,))) < 0 Therefore the minimal value is achieved whenever D',,, = a + 8mg
The proof in the EPStriplet loss case is similar.
Claim 4. f be an embedding. every i, let fh,5..,b, in be such that DJ Di <.. ... D Then there exists M such that for every > M the minimal embedding for:
Cepstrsp (1 (1,,,1, + L C (IC.
is achieved whenever Dujaiis Dejir
Proof. Define K(Y,, Ys, Ye) (Y),,, - (1 dr.r)a)). Fixing assuming D Dig Df. Dly <
DJ D We have:
Cleps (11, (11,01 Cepsin (11, K(Y, Yets) (Dh DL Dig + +a)
KYY,, Yi) (Dhiauts DL,, 1 +a)
As in the previous claim, the minimal value achieved whenever D - D I S a this case:
C'essurp (11, Re, 21,45) + C (I1, (I1, xe) = a (K(Y,, Yt, Ye+s) + K K(M, Ye+j, X+)) Y:))
(D/ Df Dey (K,Y, Y,, Yets)
16

---

Under review as a conference paper at ICLR 2021
Dist-margin
EPS+ Dist-Daa-mrriinn
Figure 5: t-SNE visualization of Cars196 training classes (each class has a different color). Training with EPS results in more diverse classes appearance.
Table 4: Results of semi-hard with/without EPS on the Omniglot training dataset. Without EPS the network feet almost perfectly to the training set. However, using EPS results in batter performances on the letters fine-graine task.
Language
Letters
Semi- hard
Semi- hard+EPS
Semi- hard
Semi- hard+EPS
NMI
93.6
67.3
78.4
87.1
R@D
99.9
94.5
70.3
77.5
R@2
96.8
80.4
86.3
R @4
100
98.1
87.9
92.4
R@8
100
99.2
93.3
96.0
On the one hand: K(Y,, Y,, Ye+s) = (T + (aaeaaaa p' (²="t 2 g where
Yx &
1 Ys E for {1,t). On the other hand else
for & E (2, 1,t o} and to
else
K(YiY++5, Y.) 2 Prob(/igaeet) Yi Yx)= s 4p + Taking j large enough such that 4*+1 1 I 4p 41-1
we have:
(E (o Yi) ōn.. (1 X..,)) ) E (#(Y,, Ye4s) dy,, (1- or,,)))))
therefore in such case the minimum archived whenever D Di = DL DL + a
C: MORE EXPERIMENTS AND IMPLEMENTATION DETAILS EMBEDDING BEHAVIOR ON TRAINING SETS
The class class-collas collapsing phenomena also occur in the training process of the image retrieval datascts. Figure visualise the t-SNE embedding (van der Maaten & Hinton] (008) when training without EPS each class fits well to bivariate normal-din -iital-distribution with small variance and different means. Training with EPS result in diverse distributions and in some of the classes fits batter mixture multiple different distributions.
(200)) of Cars196 training classes. As can be seen,
This can also be measured qualitatively on the Omniglod detest: although training without the EPS results in batter overfitting to training samples. the results on the letters tine-graine task are significantly inferior comparing to training with the EPS (Table It is also important to note the low NMT score when using EPS with the number of clusters equal the number of languages, and the increment of this score when increasing the
17

---

Under review as a conference paper at ICLR 2021
Table Std of Recall @ results. Each model was trained times with different random seeds.
Without EPS
With EPS
dataset
model
std
std
cars
Margin
0.17
0.27
cars196
MS
0.24
0.29
cars 196
Trip+SH
0.20
0.47
cub200
Margin
29.8
0.33
cub200
MS
0,43
0.36
cub200
Trip+SH
0.52
0.35
Omniglot-letters
Margin
0.73
0.58
Omniglot-letten
MS
0.52
0.71
Omniglot-letters
Trip+SH
0.34
0.61
Table 6: Results of Multi Multi-similarrty loss with Embedding size 512 (as in EPS improve results both cases.
Wang et al. 2019)). Using
Cars196
CUB200
MS
MS+EPS
MS
MS+EPS
R @ 1
84.1
85.5
65.7
66.7
@
90.4
90.7
77.0
77.2
R @4
94.0
94.3
86.3
86.4
96.5
96.7
91.2
90.9
number of clusters to number letters. This indicates that training with EPS results more homogeneous small clusters, which are more hlended in the embedding space comparing to training without EPS.
MNIST ARCHITECTURE DETAILS
For the MNIST even/odd experiment we use a model consisting of two consecutive convolutions layer with (3,3) kernels and 32,64 (respectively) filter sizes. The two layers are followed by Relu activation and batch normalization layer, then there is (2,2) max- max-pooling follows by dense layers with 128 and 2 neurons respectively.
RECOGNITION DATASETS ARCHITECTURE DETAILS
We use embedding of size 128, and input size of 224X224 for the first two datasets, and 80X80 for the Omniglot dataset. all the experiments we used the original bounding boxes without cropping around object box. As a backbone for the embedding, we use ResNet50 (He et al. (016) with pretrained weights on imagenet. The backbone is followed by global average pooling and linear layer which reduces the dimension the embedding size. Optimization performed using Adam with learning rate of 10-5, and the other parameters to default values from Kingma & Ba 2014).
STABILITY ANALYSIS
Following Musgrave et al. 2020 Fehervari al. 2019), between tested models. Therefore, the same architecture and embedding size (128). We also did not change the default hyper parameters all tested methods. We run each experiment 8 times with different random seeds, the reported results are the mean of all the experiments. The std of the Recall@e & 1 results of all experiments can be seen in Tahle In all cases the differences between the results with and without the EPS are significance.
important to have fair comparison the experiments we use the same framework (Roth et al.), with
MULTI- SILUI-RIMILARTYY COMPARISON
From experiments, the Multi-similarity loss is highly affected by the batch size. Using Resnet50 backbone, we restrict the number of batch size 160 multi timilarim loss comparing to other methods. For the sake of completeness we provide the results also on inception backbone with embedding size of 512 as in Wang et al. (201)), and batch size of 260. As can be seen in T also in these cases the results improve when using EPS instead of semi-hard sampling on the positive samples.
tested model, which cause to the inferior results the
18

---

Under review as a conference paper at ICLR 2021
Onniglot-eteer resuls with trimmed loss
Cars196 96 results with trimmed loss
50-
62-
Receigh
Recalla1
60
50-
Destnoo-marrg
Degance-mrrgi
ab
s/0
dp
Trimming procentage
Trtmming procentage
Figure 6: Recall@ performance with Trimmed loss across varying trimming percentage. Except for small improvement in the Distance-margin case on the Omniglot dataset, in all other cases there is no improvement when applying the Trimmed loss.
TRIMMED LOsS COMPARISON
The situation where class consists of multiple modes can also be seen noisy data scenario with respect to the embedding loss, where positive tuples consisting of examples from different modes considered as 'bad" labelling. One approach address noisy labels by back proppaaopggtting the loss only the k-clements in the batch with the lowest current loss (Shen Sanghavi 2019). Although this approach resembles Malisiewicz Efros (2008), the difference is that in Malisiewicz & Efros 2008) they apply the trimming only on the positive tuples. We test the effect of using Trimmed Loss Loss random sampled triplets with different level of trimming percentage. As can be seen Figure there only minor improvement when applying the loss on top of the distance-margin loss on the Onniglot-letters dataset. This emphasizes the importance constraining trimming to the positive sampling only.
19


Reviews:
[{"review_id": "otggLWTgbPt", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Motivated by the theoretical results on class collapse problems, this paper proposes a simple positive sampling mechanism called EPS for metric learning. The method is simple -- each sample selects its nearest same-class counterpart in a batch as the positive element. The authors provide both theoretical motivations and empirical studies on the proposed method. \n\nStrengths: \n+ Theoretical analysis on the existing class collapse problem for triplet and margin loss\n+ well-motivated and simple solutions that are proven to be effective in theory\n\nWeaknesses:\n- there is a gap between theoretical analysis and empirical studies. In the analysis, the paper shows in the noisy label setting, margin and triplet loss also induce the class collapse problem but in the empirical study, the paper only conducted analysis on dataset with clean labels. \n- the theoretical analysis based on the assumption that the function f can approximate any functions. However for any fixed deep nets, it does not satisfy the requirement \n\nOverall, the EPS method is simple and supported by theoretical analysis. I would find it more convincing if the paper can provide empirical analysis on noisy labeled data. In addition, I wonder how different architectures can affect the difference between previous methods and EPS.", "extra_scores": {}, "extra_text": {}}, {"review_id": "gN1R94iJ9jP", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Post-rebuttal: The rebuttal partly addresses my concerns, so I would like to change my score to 4.\n------------------------------------------------------\nThis paper proposes an easy positive sampling method for deep metric learning which aims to reduce the class collapse problem which is found to harm the performance of existing DML methods.\n\nPros: \n1. This paper is well-written and easy to follow. \n2. The idea is simple but makes good sense. The author also provide solid theoretical analysis of the flaw of existing methods and the advantage of the proposed easy positive sampling strategy. \n\nCons:\n1. The idea of sampling easy positive for deep metric learning is actually not new. [1] already proposed an easy positive sampling method and the motivation is quite similar (to relax the constraints of intra-class variations). [1] should be cited in this paper.\n2. The authors only provide theoretical analysis on the binary case and claims it can be easily extended to the multi-label case, which I find not trivial.\n3. A concern is the limited batch size, which might cause the easy positive sample of one particular sample at different iterations to be different (and possibly from different subcluster). This might lead to inconsistent effect of pushing the same sample to different subclusters. \n4. Similar to the last one, a more general problem is the theoretical analysis only consider the optimal situation but neglects the nature of batch-based training, which might bring unexpected problems.\n5. For the experiments, the performance improvement using the proposed easy positive sampling is not strong. Specifically, the best performance on the Cars196 and CUB200 dataset is achieved with EPS + margin, but the authors did not report the performance of margin loss  with distance-weighted sampling. Comparisons with other sampling methods on the same loss should be provided.\n6. The authors should design an experiment to better demonstrate the class collapsing problem on a regular dataset like CUB. The toy experiment on the MNIST dataset is not convincing.\n\nIn summary, I think this paper is solid and well-motivated, but I find the idea not new and the experiments not satisfying. The latter weighs more in my decision. \n\n[1] Xuan H, Stylianou A, Pless R. Improved embeddings with easy positive triplet mining[C]//The IEEE Winter Conference on Applications of Computer Vision. 2020: 2474-2482.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Lamsa4rf62j", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes/adopts a simple positive sampling scheme in metric learning: only sampling the easiest positive for each anchor. Authors give a theoretical analysis of how the proposed sampling scheme can reduce class collapse. Experiments on fine-grain retrieval datasets show the effectiveness of the sampling scheme. Using the sampled easiest positive, nearly all current metric learning methods got improved performance.\n\nPros:\n\n1. propose/adopt a simple easiest positive sampling scheme, and show its usefulness in fine-grain retrieval task;\n2. Extensive theoretical analysis of how the proposed sampling scheme can reduce class collapse.\n\nCons:\n\n1. I don't think this easiest positive sampling scheme is a contribution, though authors give a theoretical analysis of why this scheme can reduce class collapse. Specifically,  Arandjelovic et al. (2016) used exactly the same easiest positive sampling scheme. Though authors explicitly show the difference between Arandjelovic et al. (2016) and the proposed method (Equation in section 4.3), I found no difference.\n\nIn the paper of Arandjelovic et al. (2016), they don't clean the positive set (only minor negatives could be included) for efficient training. This is good for practical usage.\n\n2. For section 4, it is good to analyze the Class-collapsing property. However, I would suggest using three classes to derive theorems, rather than using two classes. As a metric-learning problem usually has multiple classes, having two or three classes are usually different stories.\n\n3. While I trust the effectiveness of the easiest positive sampling scheme in the fine-grain image retrieval datasets, I strongly suspect its effectiveness in a broad image retrieval task.\n\nFor example, in the following paper:\n\nRadenović, Filip, Giorgos Tolias, and Ondřej Chum. \"CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples.\" European conference on computer vision. Springer, Cham, 2016.\n\nThis easiest positive sampling scheme falls short in performance.\n\nCombining the conclusions from the above paper and the paper under review, I would say this easiest positive sampling scheme has limited contribution, as it is not broadly applicable.\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "38RwnwiLlqQ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors find that the popular triplet loss will force all same-class instances to a single center in a noisy scenario, which is not optimal to deal with the diverse and distinct sub-classes. After some analyses, the authors propose a simple sampling strategy, EPS, where anchors only pull the most similar instances. The method achieves good visualization results on MNIST and gets promising performance on benchmarks.\n\nAvoiding class collapse is meaningful and important in metric learning when dealing with some tasks. The analyses in the paper provide insights. Here are some possible issues of this paper.\n1. The authors should discuss when we need to avoid such class collapse. Maybe in some cases, pulling all similar instances to a single point leads to more discriminative embeddings. Even some methods are designed following that consideration. Some examples and demonstrations are required.\n2. It's better to write a sketch of the analysis on how to extend it to multi-class cases and analyze will the definition of the noise influence the final results.\n3. Maybe the authors need to find another real-world dataset with multiple meanings in one class and show the advantage of the proposed method. We can find the improvement of performance on the benchmarks, but the numbers are hard to illustrate the effect of the method.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is truly borderline. On one hand, the theoretical contribution seems novel and interesting, however, there appears to be somewhat of a gap between theory and practice. 

There is unfortunately another problem. According to the authors, the main contribution of this publication is arguably the introduction of the nearest neighbor as the positive example in the triplet loss. However, the authors seem to be unaware of the history of the triplet loss. It was originally introduced by Schultz & Joachims 2004 as a loss over all triplets.  Weinberger et al. 2005 changed it and use the nearest neighbor as "target neighbor", which is called "easy positives" here, as the objective of LMNN. In 2009 Chechik et al. subsequently relaxed this positive neighbor formulation to any similarly labeled sample (going back to the Schultz & Joachims formulation) but sampling triplets. The re-introduction of the nearest neighbor as "easy positive" was then covered by Xuan et al. 2020.  

Unfortunately all of this diminishes the novelty significantly and it is clear that the paper in its current form does not have a strong enough contribution. I do encourage the authors to take a close look at the original LMNN publication and Xuan et al and write an improved re-submission for the next conference that maybe focuses more on the theoretical contribution. 
Good luck,

AC
Decision: Reject