Year: 2020

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 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. 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.

heading: 1 INTRODUCTION
text: Metric learning aims to learn an embedding function to lower dimensional space, in which semantic similarity translates to neighborhood relations in the embedding space (Lowe, 1995). Deep metric learning approaches achieve promising results in a large variety of tasks such as face identification (Chopra et al., 2005; Taigman et al., 2014; Sun et al., 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 an embedding representation that enforces that all modes of intra-class appearance variation project to a single point in embedding space. Learning such an embedding is very challenging when classes have a diverse appearance. This happens especially in real-world scenarios where the class consists of multiple modes with diverse visual appearance. Pushing all these modes to a 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” to the same center, occurs in case of the classification SoftMax loss (Qian et al.). They proposed a multi-center approach, where multiple centers for each class are used with the SoftMax loss to capture the hidden distribution of the data to 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 in noise-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 in 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 to the anchor in the current embedding space as the
positive sample. The metric learning loss is then computed based on the anchor and its positive paired sample.
We demonstrate the class-collapsing phenomena on a real-world dataset, and show that our method is able to create more diverse embedding which result in a better generalization performance. We evaluate our method on three standard zero-shot benchmarks: CARS196 (Krause et al., 2013), CUB200-2011 (Wah et al., 2011) and Omniglot (Lake et al., 2015). Our method achieves a consistent performance enhancement with respect to various baseline combinations of sampling methods and embedding losses.

heading: 2 RELATED WORK
text: 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 to make training more efficient (Simo-Serra et al., 2015; Schroff et al., 2015; Wang & Gupta, 2015; Oh Song et al., 2016; Parkhi et al., 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; Shrivastava et al., 2016; Arandjelovic et al., 2016; Cubuk et al., 2019; Singh & Lee, 2017; Wang et al., 2017). The central idea is to perform better augmentation to 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 a clean setting, where the purpose is to get the opposite result of maintaining the inner-class modalities in the embedding space. Xuan et al. (2020) also propose to use this positive sampling method with respect to 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-environment 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 a practical problem when applied to the real world (Scott et al., 2013; Natarajan et al., 2013; Shen & Sanghavi, 2019; Reed et al., 2014; Jiang et al., 2017; Khetan et al., 2017; Malach & Shalev-Shwartz, 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 are 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., 2017). Researchers have also tried on to apply the loss only on easiest top k-elements in the batch, determine by lowest current loss (Shen
& Sanghavi, 2019). Inspired by these works, our method focuses on selecting only the top easiest positive relations in the batch.
Beyond memorization. Deep networks are 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, it 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, it is shown that it does not really generalize to 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 a zero-shot setting.

heading: 3 PRELIMINARIES
text: Let X = {x1, .., xn} be a set of samples with labels yi ∈ {1, ..,m}. The objective of metric learning is to learn an embedding f(·, θ) −→ Rk, 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 is using embedding losses in which at each iteration, samples from the same class and samples from different classes are chosen according to same sampling heuristic. The objective of the loss is to push away projections of samples from different classes, and pull closer projections of samples from a same class. In this section, we introduce a few popular embedding losses.
Notation: Let xi, xj ∈ X , define: Dfxi,xj = ‖ f(xi)−f(xj)‖ 2. In cases where there is no ambiguity we omit f and simply write Dxi,xj . We also define the function δxi,xj = {
1 if yi = yj 0 otherwise . Lastly,
for every a ∈ 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.
Lfcon(xi, xj) = δxi,xj ·Dfxi,xj + (1− δxi,xj ) · (α−D f xi,xj )+
Here α is the margin parameter which defines the desired minimal distance between samples from different classes.
While the Contrastive loss imposes a constraint on a pair of samples, the Triplet loss (Chechik et al., 2010) functions on a triplet of samples. Given a triplet xa, xp, xn ∈ X , the triplet loss is defined by
Lftrip(xa, xp, xn) = δxa,xp · (1− δxa,xn) · (D f xa,xp −D f xp,xn + α)+
The Margin loss (Wu et al., 2017) aims to exploit the flexibility of Triplet loss while maintaining the computational efficiency of the Contrastive loss. This is done by adding a variable which determines the boundary between positive and negative pairs; given an anchor xa ∈ X the loss is defined by
Lf,βmargin(xa, x) = δxa,x · (D f xa,x − βxa + α)+ + (1− δxa,x) · (βxa −D f xa,x + α)+

heading: 4 CLASS-COLLAPSING
text: 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, an embedding f : X −→ Rm has the class-collapsing property, if there exists a label y and a point p ∈ Rm such that {f(xi)| yi = y} = {p}.

heading: 4.1 EMBEDDING LOSSES OPTIMAL SOLUTION
text: It is easy to see that an embedding function f that minimizes:
Ocon(f) = 1
n2  ∑ xi,xj∈X Lfcon(xi, xj) 
has the class-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 we will assume there are only two classes. Let A ⊂ X be a subset of elements such that all the elements in A belongs to one class and all the element in Ac belong to the other class.
Recall some basic set definitions. Definition 1. For all sets Y,Z ⊂ Rm define:
1. The diameter of Y is defined by:
diam(Y ) = sup{‖y − z‖ |y, z ∈ Y }
2. The distance between Y and Z is:
‖Y − Z‖ = inf{‖y − z‖ |y ∈ Y, z ∈ Z}
It is easy to see that if f : X −→ Rm is an embedding, such that diam(f(A)) < 2·α+‖f(A)−f(B)‖, then:
Otrip(f) = 1
n3  ∑ xi,xj ,xk∈X Lftrip(xi, xj , xk)  = 0. Moreover, fixing βxi = α for every xi ∈ X , then:
Omargin(f, β) = 1
n2  ∑ xi,xj∈X Lf,βmargin(xi, xj)  = 0. It 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 in a noisy environment scenario.

heading: 4.2 NOISY ENVIRONMENT ANALYSIS
text: For simplicity we will also discuss in this section the binary case of two labels, however this could be extended easily to the multi-label case.
The noisy environment scenario can be formulated by adding uncertainty to the label class. More formally, let Y = {Y1, .., Yn} be a set of independent binary random variables. Let A1, .., At ⊂ X , 0.5 < p < 1 such that: |Aj | = nt and
P(Yi = k) = { p xi ∈ Ak q′ := 1−pt−1 xi /∈ Ak
We can also reformulate δ as a binary random variable such that:
δYi,Yj := 1Yi=Yj
For the Triplet loss define: ELftrip(xi, xj , xk) = E ( δ̄Yi,Yj · (1− δ̄Yi,Yk) ) · ( Dfxi,xj −D f xi,xk + α ) + .
We are searching for an embedding function which minimize
EOtrip(f) = 1
n3 ∑ xi,xj ,xk∈X ELftrip(xi, xj , xk)
Theorem 1. Let f : O −→ Rm be an embedding, which minimize EOtrip(f), then f has the classcollapsing property with respect to all classes.
Similarly, we can define:
ELfmargin(xi, xj) = Eδ̄Yi,Yj · (D f xi,xj − βxi + α)+ + E(1− δ̄Yi,Yj ) · (βxi −D f xi,xj + α)+
Theorem 2. Let f : O −→ Rm be an embedding, which minimize
EOmargin(f, β) = 1
n2 ∑ xi,xj∈X ELfmargin(xi, xj),
then f 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 theoretically in clean environments the Triplet loss and Margin loss should allow more flexible embedding solutions, this does not remain true when noise is 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.

heading: 4.3 EASY POSITIVE SAMPLING (EPS)
text: 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 is a side-effect which is not necessarily in order to get optimal results. In the next section, we will show experimental results, which support the assumption that complete class-collapsing can hurt the generalization capability of the network.
To address the class-collapsing issue we propose a 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 a mini-batch with N samples, for each sample a, let Ca be the set of elements from the same class as a in the mini-batch, we choose the positive sample pa to be
arg min t∈Ca
(‖f(t)− f(a)‖)
For negative samples na we can choose according to various options. In this paper we use the following methods: (a) Choosing randomly from all the elements which are not in Ca. (b) Using distance sampling (Wu et al., 2017). (c) semi-hard sampling (Schroff et 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 1.
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 not a 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, if 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. It also optimizes the embedding to have this form.

heading: 5 EXPERIMENTS
text: We test our EPS method on image retrieval and clustering datasets. We evaluate the image retrieval quality based on the recall@k metric (Jégou et al., 2011) , 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 on the embedding space. The common practice to choose the NMI
clusters is by using K-means 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 class-collapsing. Therefore, we increase the number of clusters in the NMI evaluation (denote it by NMI+) we also report the regular NMI score.

heading: 5.1 MNIST EVEN/ODD EXAMPLE
text: 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 a visual perspective this is 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 an embedding function from the image space to R2 (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 a richer embedding in 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 1.

heading: 5.2 FINE-GRAINED RECOGNITION EVALUATION
text: 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 of the framework of Roth et al., which allow us to 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.

heading: 5.2.1 DATASETS
text: We evaluate our model on the following datasets.

heading: 5.2.2 RESULTS
text: We tested our sampling method with 3 different losses: Triplet (Chechik et al., 2010), Margin (Wu 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 al., 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 α = 0.2 and initialized β = 1.2 as in (Wu et al., 2017). For the Triplet we combine our method with semi-hard sampling (Schroff et al., 2015) by fixing the positive according to EPS and then using semi-hard sampling for choosing the negative examples. For the MS loss we replace the positive hard-mining method with EPS and use the same hard-negative method. We use the same hyper-paremeters as in (Wang et al., 2019) α = 2, λ = 1, β = 50.
Results are summarized in Tables 2 and 3. We can see that our method achieves the best performance on all tested datasets. It is important to note that in the baseline models, when using Semi-hard sampling, the sampling strategy was done also on the positive part as suggest in the original papers. We see that replacing the semi-hard positive sampling with easy-positive sampling, improve results in all the experiments. The improvement gain becomes larger as the dataset classes can be partitioned
more naturally to a small number of sub-clusters which are visually homogeneous. In Cars196 dataset it is the car viewpoint, where in Omniglot it is the letters in each language. As can be seen in Table 3, using EPS on the Omniglot dataset result in creating an embedding in which in most cases the nearest neighbor in the embedding consists of element of the same letter, although the network was trained without these labels. In Figure 4 we can see a 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 can be find in Appendix C.

heading: 5.2.3 POSITIVE BATCH SIZE EFFECT
text: 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 in batch is low, than with high probability the set of all the positive samples will not contain any visually similar image to the anchor. In case of the Omniglot experiment, the effect of this hyperparameter is clear; It determines the probability that the set of positive samples will include a sample from the same letter as the anchor letter. As can be seen in Figure 3(b), the performance of the model increases as the probability of having another sample with the same letter as the anchor increases.

heading: 6 CONCLUSION
text: 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 in clean environments there is a diverse and rich family of optimal solutions, when noise is present, the optimal solution collapses
to a degenerate embedding. We propose a simple solution to this issue based on ’easy’ positive sampling, and prove that indeed adding this sampling results in non-degenerate embeddings. We also compare and evaluate our method on standard image retrieval datasets, and demonstrate a consistent performance boost on all of them. While our method and results have been limited to metric learning frameworks, we believe that our sampling scheme will also be useful in other related settings, including supervised contrastive learning, which we leave to future work.

heading: A: PROOFS FOR THE THEOREMS IN SUBSECION 4.2
text: Theorem 1. Let f : O −→ Rm be an embedding, which minimize EOtrip(f), then f has the class-collapsing property with respect to all classes.
Proof. Define a new random variables such that for every 1 ≤ r1, r2 ≤ t:
hr1,r2(Y,Z) = { 1 Y = r1 ∧ Z = r2 0 else
observe that δ̄Y1,Y2 · (1− δ̄Y1,Y3) = ∑
1≤r1,r2≤t r16=r2
1Y1=r1 · hr1,r2(Y2, Y3) = ∑
1≤r1,r2≤t r16=r2
1Y1=r2 · hr1,r2(Y3, Y2)
Since the variables are independent
E(δ̄Y1,Y2 · (1− δ̄Y1,Y3)) = 1
2 · ∑ 1≤r1,r2≤t
r16=r2
E(1Y1=r1) · E(hr1,r2(Y2, Y3)) + E(1Y1=r2) · E(hr1,r2(Y3, Y2)).
Define: D̄(x1, x2, x3) := (Dx1,x2 −Dx1,x3 + α)+ Rearranging the terms we get
n3 · EOtrip(f) = ∑
x1,x2,x3∈X (E(δ̄Y1,Y2 · (1− δ̄Y1,Y3)) · D̄(x1, x2, x3) =∑ x1,x2,x3∈X 1≤r1 6=r2≤t (E(1Y1=r1) · E(hr1,r2((Y2, Y3)) + E(1Y1=r2) · E(hr1,r2(Y3, Y2))) · D̄(x1, x2, x3) =
∑ x1,x2,x3∈X 1≤r1 6=r2≤t (hr1,,r2(Y2, Y3)) · ( E(1Y1=r1) · D̄(x1, x2, x3) + E(1Y1=r2) · D̄(x1, x3, x2) ) =
Therefore, if K(i, j, k, r1, r2) = · ( E(1Y1=r1) · D̄(xi, xj , xk) + E(1Y1=r2) · D̄(x1, xk, xj) ) ,
then EOtrip(f) can be written as
EOtrip(f) = 1
n3 ∑ 1≤i,j,k≤n 1≤r1 6=r2≤t E(hr1,r2(Yj , Yk)) ·K(i, j, k, r1, r2)
For every xi ∈ X , define:
(EOtrip(f))xi = 1
n2 · ∑ 1≤j,k≤n
1≤r1 6=r2≤t
(E(hr1,r2(Yj , Yk)) ·K(xi, xj , xk, r1, r2)
Let f : X −→ Rm be an embedding, fix 1 ≤ r ≤ t and xi ∈ Ar, xj , xk ∈ X with
‖ f(xi)− f(xj)‖ = w, ‖ f(xi)− f(xk)‖ = h.
By definition:
K(i, j, k, r1, r2) =  p · (h− w + α)+ + q(w − h+ α)+ r1 = r ∧ r2 6= r q · (h− w + α)+ + p(w − h+ α)+ r2 = r ∧ r1 6= r p · (h− w + α)+ + p(w − h+ α)+ r1 = r ∧ r2 = r q · (h− w + α)+ + q(w − h+ α)+ r1 6= r ∧ r2 6= r
Since 0 < p < 1, in order to get minimal K(i, j, k, r1, r2) value, h and w must satisfy |h− w| ≤ α. In this case we have
K(i, j, k, r1, r2) =  (p+ q) · α+ (h− w)(p− q) r1 = r ∧ r2 6= r (p+ q) · α+ (w − h)(p− q) r2 = r ∧ r1 6= r 2 · α r1 = r ∧ r2 = r 2 · α r1 6= r ∧ r2 6= r
Therefore,∑ r2∈{1,.r−1,r+1,.t} (E(hr,r2(Yj , Yk)) ·K(xi, xj , xk, r1, r2) + (E(hr2,r(Yj , Yk)) ·K(xi, xj , xk, r1, r2) =
= (p+ q) · α( ∑
r2∈{1,.r−1,r+1,.t}
(E(hr,r2(Yj , Yk) + (E(hr2,r(Yj , Yk)))+
(h− w)(p− q))( ∑
r2∈{1,.r−1,r+1,.t}
E(hr,r2(Yj , Yk))− E(hr2,r(Yj , Yk))
We split to three cases:
1. If xj , xk ∈ Ar or xj , xk /∈ Ar then: E(hr,r2(Yj , Yk)) = E(hr2,r(Yj , Yk)). Hence, (h− w)(p− q))( ∑
r2∈{1,.r−1,r+1,.t}
E(hr,r2(Yj , Yk))− E(hr2,r(Yj , Yk)) = 0
2. If xj ∈ Ar and xk /∈ Ar , then E(hr,r2(Yj , Yk)) > E(hr2,r(Yj , Yk)), therefore (h− w)(p− q))( ∑
r2∈{1,.r−1,r+1,.t}
E(hr,r2(Yj , Yk))− E(hr2,r(Yj , Yk))
Since p > 0.5 and |h− w| ≤ α,the minimal value is achieved whenever h = 0 and w = α.
3. In the same way if xk ∈ Ar and xj /∈ Ar , then E(hhr2,r (Yj , Yk)) = E(hr,r2(Yj , Yk)) and the minimal value is achieved whenever h = α and w = 0.
In conclusion, if xi ∈ Ar , an embedding f∗ satisfies (EOtrip(f∗))xi = min{(EOtrip(f))xi |f : X −→ R
m} iff f∗(xj) = f∗(xi) for every xj ∈ Ar , and ‖ f∗(xj)− f∗(xi)‖ = α for every xj /∈ Ar .
We will now prove the same theorem with respect to the margin loss. Theorem 2. Let f : O −→ Rm be an embedding, which minimize
EOmargin(f, β) = 1
n2 ∑ xi,xj∈X ELfmargin(xi, xj),
then f has the class-collapsing property with respect to all classes.
Proof. Observe that if xi, xj ∈ Ar , then
ELfmargin(xi, xj) = p · (Dxi,xj − βxi + α)+ + (1− p) · (βxi −Dxi,xj + α)+ Since 0 < p < 1, then the maximal value is achieved whenever |Dxi,xj − βxi | ≤ α, in this case:
ELfmargin(xi, xj) = (2p− 1) · (Dxi,xj − βxi).
In the same way in case xi ∈ Ar and xj /∈ Ar then:
ELfmargin(xi, xj) = (2p− 1) · (βxi −Dxi,xj ). Combining both directions we get:
∑ xj∈X ELfmargin(xi, xj) = (2p− 1) · ∑ Yj∈A Dxi,xj − ∑ Yj /∈A Dxi,xj  Since: p > 0.5 and |Dxi,xj − βxi | ≤ α, the minimal value is achieved whenever Dxi,xj = 0, Dxi,xk = 2α and βxi = α, for every xi, xj ∈ Ar, xk /∈ Ar .

heading: B: EASY POSITIVE SAMPLING IN NOISY ENVIRONMENT
text: In this subsection we analyse the EPS method from the theoretical prospective, using the framework defined in Section 4. We use the same notions as in sections 3 and 4.
Define: Φ(yi, yj) = { 1 yi = yj ∧Dxi,xj = min{Dxi,xk | yk = yi} 0 else . Then, the easy positive sampling loss
can be defined by: 1
n ∑ 1≤i,j,k≤n Φ(yi, yj) · Lftrip(xi, xj , xk)
for the triplet loss and
1
n ∑ 1≤i,j≤n (Φ(yi, yj) · Lf,βmargin(xi, xj)) + 1yi 6=yjL f,β margin(xi, xj)
for the margin loss.
In the noisy environment stochastic case, using section 4 notions, Φ become a random variable:
Φ̄(Yi, Yj) = { 1 Yi = Yj ∧ ∀t ((Dxi,,xt < Dxi,xj )→ Yt 6= Yi) 0 else
Therefore, the triplet loss with EPS in the noisy environment case, become:
ELfEPStrip(xi, xj , xk) = E ( Φ̄(Yi, Yj) · δ̄Yi,Yj · (1− δ̄Yi,Yk ) ) · ( Dfxi,xj −D f xi,xk + α ) +
and for the margin loss with EPS we have:
ELfEPSmargin(xi, xj) = E(Φ̄(Yi, Yj) · δ̄Yi,Yj ) · (D f xi,xj −βxi +α)+ +E(1− δ̄Yi,Yj ) · (βxi −D f xi,xj +α)+
As in section 4.2 we assume that Y = {Y1, .., Yn} is a set of independent binary random variables. Let A1, .., At ⊂ X , 0.5 < p < 1 such that: |Aj | = nt and
P(Yi = k) = { p xi ∈ Ak q′ := 1−p
t−1 xi /∈ Ak
For simplicity we assume that every 1 ≤ i ≤ n t satisfies xn·i t +1, .., xn·i t +t ∈ Ai
We prove first that the minimal embedding with respect to both losses does not satisfy the class collapsing property. Let f1 be an embedding function such that:
Df1xi,xj = { 0 (∃r)(xi, xj ∈ Ar) α else
and f2 an embedding such that:
Df1x1,x2 =
{ 0 (∃r)(xi, xj ∈ Ar)∧ ∼ ((i < t2n ∧ j > t 2n ) ∨ (i > t 2n ∧ j < t 2n )
α else
f1 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 to prove that
1
n ∑ 1≤i,j,k≤n Lf2EPStrip(xi, xj , xk) < 1 n ∑ 1≤i,j,k≤n Lf1EPStrip(xi, xj , xk)
and 1
n ∑ 1≤i,j≤n Lf2EPSmargin(xi, xj) < 1 n ∑ 1≤i,j≤n Lf1EPSmargin(xi, xj).
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 between set A1 are closer then set Ac1 in both embeddings. For simplification we neglect this infinitesimal constants in the proofs.
Claim 1. There exists M such that if n ≥M , then: 1
n ∑ 1≤i,j,k≤n Lf2EPStrip(xi, xj , xk) < 1 n ∑ 1≤i,j,k≤n Lf1EPStrip(xi, xj , xk)
Proof. Fix x1, WOLOG we may assume in both embeddings that D fj x1,xi < D fj x1,xk for every j ∈ {1, 2} and 1 ≤ i < k ≤ n. It suffice to prove that
1
n ∑ 1≤j,k≤n (Lf1EPStrip(x1, xj , xk)− L f2 EPStrip(x1, xj , xk)) > 0
Let q = (1− p), observe that P( ∧
1≤t<j
Yi 6= Yt) = pm+1 · qj−2−m + pj−2−mqj+1 ≤ 2pj−1
where m = |{t | t ≤ j, Yt ∈ A1}| . Thus if j ≥ n2t , we have Lf2EPStrip(x1, xj , xk) ≤ P( ∧
1≤t<j
Yi 6= Yt) · 2 · α ≤ 4 · αpj−1.
Therefore,
1
n ∑ j> n
2t ,1≤k≤n
Lf2EPStrip(x1, xj , xk) ≤ ∑ j> n
2t
4·αpj = 4·n·αp n 2t · n(2t−1) 2t∑ j=0 pj = 4·αp n 2t ·1− q n(2t−1)/2t 1− q n→∞→ 0
For j ≤ n 2t and k ≤ n 2t of k > n t , we have Lf1EPStrip(x1, xj , xk) = L f2 EPStrip(x1, xj , xk). Hence, the only case left is j ≤ n 2t and n 2t < k ≤ n t . In this case: Lf2EPStrip(x1, xj , xk) = 0, where
Lf1EPStrip(x1, xj , xk) = (p 2 · qj−1 + q2 · pj−1) · α ≥ qj+1α
and we get:
1 n · ∑ j≤ n
2t , n 2t ≤k≤n t
Lf1EPStrip(x1, xj , xk)− L f2 EPStrip(x1, xj , xk) ≥
α · q2 · n 2t∑ j=0 qi = α · q2 · 1− q n/2t 1− q n→∞→ αq2 · 1 1− q
Choosing M such that
α · q2 · 1− q M/2t 1− q > 4 · αp M 4 · 1− q
M(2t−1)/2t
1− q will satisfy that for every n > M :
1
n ∑ 1≤i,j,k≤n Lf2EPStrip(xi, xj , xk) < 1 n ∑ 1≤i,j,k≤n Lf1EPStrip(xi, xj , xk)
Claim 2. There exists M such that if n ≥M then: 1
n ∑ 1≤i,j≤n Lf2EPSmargin(xi, xj) < 1 n ∑ 1≤i,j≤n Lf1EPSmargin(xi, xj)
Proof. For every 1 ≤ j ≤ n 2t or n t < j ≤ n we have:
Lf1EPSmargin(xi, xj) = L f1 EPSmargin(xi, xj)
For n 2t < j ≤ n 2 :
Lf2EPSmargin(xi, xj) = 2 · p · q · βxi + (p 2qj−2 + q2pj−2) · (2 · α− βxi)
while: Lf2EPSmargin(xi, xj) = 2 · p · q · (βxi + α) + (p 2qj−2 + q2pj−2) · (α− βxi)
Since j > n 2t the second therm tend to zero. Therefore, taking M such that
2qp > (p2q M 2t −2 + q2p M 2t −2)
will satisfy that for each n ≥M 1
n ∑ 1≤i,j≤n Lf2EPSmargin(xi, xj) < 1 n ∑ 1≤i,j≤n Lf1EPSmargin(xi, xj)
In the previous two claims we prove that the class collapsing solution is not minimal with respect to both the EPSmargin and theEPStriplet. In the following claims we prove that not only it is not the 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 an embedding in which the distance between the sample to the anchor is equal to the margin hyperparameter.
Claim 3. Let f be an embedding. For every i, let i1, .., in be such that Dfxi,xi1 < D f xi,xi2 < ... < Dfxi,xn , Then there exists M such that for every j > M the minimal embedding for LfEPSmargin(xi, xj) is achived whenever Dfxi,xj = βxi + α.
Proof. Fix x1, as in the previous claims we will assume:
Dfx1,x1 < D f x1,x2 < ... < D f x1,xn As was prove in in Claim 1 P( ∧
1≤t<j Yi 6= Yt) ≤ 4p j , thus
E(Φ̄(Yi, Yj) · δ̄Yi,Yj ) ≤ P( ∧
1≤t<j
Yi 6= Yt) ≤ 4pj−1 j→∞→ 0
Since the minimal solution for
E(Φ̄(Yi, Yj) · δ̄Yi,Yj ) · (D f xi,xj − βxi + α)+ + E(1− δ̄Yi,Yj ) · (βxi −D f xi,xj + α)+
satisfies |βxi −Dfxi,xj | ≤ α, we have:
Lf1EPSmargin(x1, xj) = α · (E(Φ̄(Y1, Yj) · δ̄Y1,Yj ) + E(1− δ̄Y1,Yj ))+
(Dfx1,xj − βx1) · (E(Φ̄(Y1, Yj) · δ̄Y1,Yj )− E(1− δ̄Yi,Yj ))
Since E(1− δ̄Y1,Yj ) ≥ 2pq, there exists M such every j > M satisfies
(E(Φ̄(Y1, Yj) · δ̄Y1,Yj )− E(1− δ̄Yi,Yj )) < 0
Therefore the minimal value is achieved whenever Dfx1,xj = α+ βx1 .
The proof in the EPStriplet loss case is similar.
Claim 4. Let f be an embedding. For every i, let i1, , .., in be such that Dfxi,xi2 < ... < D f xi,xn . Then there exists M such that for every j > M the minimal embedding for:
LfEPStrip(xi, xt, xt+j) + L f EPStrip(xi, xt+j , xt)
is achieved whenever Dxi,xt+j = Dxi,xt + α. Proof. Define K(Yi, Yi, Yk) := E ( Φ̄(Yi, Yj) · δ̄Yi,Yj · (1− δ̄Yi,Yk ) ) . Fixing x1, assuming Dfx1,x1 < Dfx1,x2 < ... < D f x1,xn , We have:
LfEPStrip(x1, xt, xt+j) + L f EPStrip(x1, xt+j , xt) = K(Y1, Yt, Yt+j) · ( Dfx1,xt −D f x1,xt+j + α ) +
+K(Y1, Yt+j , Yt) · ( Dfx1,xt+j −D f x1,t + α ) +
As in the previous claim, the minimal value is achieved whenever |Dfx1,xt+j −D f x1,xt | ≤ α in this case:
LfEPStrip(x1, xt, xt+j) + L f EPStrip(x1, xt+j , xt) = α · (K(Y1, Yt, Yt+j) +K(Y1, Yt+j , Yt))Yt))+
(Dfx1,xt −D f x1,xt+j ) · (K(Y1, Yt, Yt+j)−K(Y1, Yt+j , Yt))
On the one hand: K(Y1, Yt, Yt+j) = ( ∏ i∈{1,2,..,t,t+j} p tiq1−ti)+( ∏ i∈{1,2,..,t,t+j} p 1−tiqti) ≥ qt+1 where
tk = { 1 Yk /∈ A 0 else for k ∈ {2, .., t − 1, t + j} and tk = { 1 Yk ∈ A 0 else for k ∈ {1, t}. On the other hand
K(Y1Yt+j , Yt) ≥ Prob( ∧ 1≤k<t+j Y1 6= Yk) ≤ 4p t+j−1. Taking j large enough such that qt+1 ≤ 4pt+j−1, we have:
(E ( Φ̄(Y1, Yt) · δ̄Y1,Yt · (1− δ̄Y1,Yt+j ) ) − E ( Φ̄(Y1, Yt+j) · δ̄Y1,Yt+j · (1− δ̄Y1,Yt) ) ) > 0
therefore in such case the minimum is archived whenever Dfx1,xt+j = D f x1,xt + α.

heading: C: MORE EXPERIMENTS AND IMPLEMENTATION DETAILS
text: EMBEDDING BEHAVIOR ON TRAINING SETS
The class-collapsing phenomena also occur in the training process of the image retrieval datasets. Figure 5 visualise the t-SNE embedding (van der Maaten & Hinton, 2008) of Cars196 training classes. As can be seen, when training without EPS each class fits well to a bivariate normal-distribution with small variance and different means. Training with EPS result in more diverse distributions and in some of the classes fits batter to a mixture of multiple different distributions.
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 fine-grained task are significantly inferior comparing to training with the EPS (Table 4). It is also important to note the low NMI score when using EPS with the number of clusters equal to the number of languages, and the increment of this score when increasing the
number of clusters to the number of letters. This indicates that training with EPS results in more homogeneous small clusters, which are more blended 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 a (2,2) max-pooling follows by 2 dense layers with 128 and 2 neurons respectively.
RECOGNITION DATASETS ARCHITECTURE DETAILS
We use an embedding of size 128, and an input size of 224X224 for the first two datasets, and 80X80 for the Omniglot dataset. For all the experiments we used the original bounding boxes without cropping around the object box. As a backbone for the embedding, we use ResNet50 (He et al., 2016) with pretrained weights on imagenet. The backbone is followed by a global average pooling and a linear layer which reduces the dimension to the embedding size. Optimization is performed using Adam with a learning rate of 10−5, and the other parameters set to default values from Kingma & Ba (2014).
STABILITY ANALYSIS
Following Musgrave et al. (2020); Fehervari et al. (2019), it was important to us to have a fair comparison between all tested models. Therefore, for all the experiments we use the same framework (Roth et al.), with the same architecture and embedding size (128). We also did not change the default hyper-parameters in 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@1 results of all experiments can be seen in Table 5. In all cases the differences between the results with and without the EPS are significance.
MULTI-SIMILARITY COMPARISON
From our experiments, the Multi-similarity loss is highly affected by the batch size. Using Resnet50 backbone, we restrict the number of batch size to 160 for all tested model, which cause to the inferior results of the multi-similarity 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. (2019), and batch size of 260. As can be seen in Table 6, also in these cases the results improve when using EPS instead of semi-hard sampling on the positive samples.
TRIMMED LOSS COMPARISON
The situation where a class consists of multiple modes can also be seen as a noisy data scenario with respect to the embedding loss, where positive tuples consisting of examples from different modes are considered as ‘bad‘ labelling. One approach to address noisy labels is by back-propagating the loss only on the k-elements 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 on random sampled triplets with different level of trimming percentage. As can be seen in Figure 6, there is only a minor improvement when applying the loss on top of the distance-margin loss on the Omniglot-letters dataset. This emphasizes the importance of constraining the trimming to the positive sampling only.

Review summaries:
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.

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.