Extreme Triplet Learning: Effectively Optimizing Easy Positives and Hard Negatives
Authors: Hong Xuan
Robert Pless
Venue:  (2020)
Keywords: Triplet Learning
Easy Positive
Hard Negatives

Abstract: The Triplet Loss approach to Distance Metric Learning is defined by the strategy to select triplets and the loss function through which those triplets are optimized.  During optimization, two especially important cases are easy positive and hard negative mining which consider, the closest example of the same and different classes.  We characterize how triplets behave based during optimization as a function of these similarities, and highlight that these important cases have technical problems where standard gradient descent behaves poorly, pulling the negative example closer and/or pushing the positive example farther away.  We derive an updated loss function that fixes these problems and shows improvements to the state of the art for CUB, CAR, SOP, In-Shop Clothes datasets.

Under review as a conference paper at ICLR 2020
EXTREME TRIPLET LEARNING: EFFECTIVELY OPTI- MIZING EASY POSITIVES AND HARD NEGATIVES
Anonymous authors Paper under double-blind review
ABSTRACT
The Triplet Loss approach to Distance Metric Learning is defined by the strategy select triplets and the loss function through which those triplets optimized. During optimization, two especially important cases are easy positive and hard negative mining which consider, the closest example of the same and different classes. We characterize how triplets behave based during optimization as func- tion of these similarities, and highlight that these important cases have technical problems where standard gradient descent behaves poorly, pulling the negative example closer and/or pushing the positive example farther away. We derive an updated loss function that fixes these problems and shows improvements to the state of the art for CUB, CAR, SOP, In-Shop Clothes datasets.
INTRODUCTION
Deep metric learning optimizes embedding function that maps semantically similar images to relatively nearby locations and maps semantically dissimilar images to distant locations. number of approaches have been proposed for this problem (Schroff al. [2015a] 5 Sohn 2016 Movshovitz-
Attias et al. 2017] Song et al. 2016. Xuan et al.] 2018 Kim et al. 2018 Ge 2018). A common way to learn the mapping is to define loss function based triplets of images: positive image from the same class, and negative image from a different class. The loss penalizes cases where the anchor is mapped closer the negative image than it is to the positive image.
anchor image,
One common variant of these functions (e.g. (Wang et al. 2018 Sohn 2016)), uses a Deep Learning framework map images feature vector, and computes similarity between normalized feature vectors based on the dot-product. This approach forces the features to lie on hypersphere and has advantages of making the feature comparison intuitive and efficient.
In this work we explore standard implementations of these loss functions and show there are two problems. First, when the gradient of the loss function does not consider the normalization hypersphere, a large part of the gradient is lost when points are re-projected back to the sphere, especially in the masy-positivehharr--eggaie cases of triplets including nearby points. Second, when optimizing the parameters (the weights) of the network, when points are already mapped close together, it may be difficult to find gradient directions that effectively separate nearby images.
We give systematic derivation showing when and where these challenging triplets arise, and di- agram the sets of triplets where standard gradient descent makes the loss increase. We find that this explains problems previously reported in the literature such the difficulty in optimizing hard- negative triplets (Harwood et al.) (0077). Furthermore, these problems are mostly introduced because the foss-function of the triplets is based on the differences between the anchor-positive and anchor- negative distances, so there is an equivalent effect of encouraging the positive image to be closer the negative image to be further. We create loss function that breaks this symmetry and weights the importance of changing the anchor-positie and anchor-negative distances. Briefly, our main contributions are:
A systematic characterization of triplet selection strategies and visualization that high- lights regions bad gradient behavior.
A simple modification to a standard loss function fix bad gradient behavior.
Improvements current state of the art results across range of datasets.

---

Under review as a conference paper at ICLR 2020
Triplet Scatter
Triplet Scatter
14
100
0.8
Problem Hardd Negative
24-
0.
02-
0.0
-02
-02
Problem Easy
Offferant Labal
bome
Easy
-04
Prodtiu Semi-hest Negatioe
-02
Hard Negative
-0.8
Bay Powiive Hand Nagalon
10
-35
-06
04
-02
0.0
04
0.
0.
-10
-08
-06
-04
-02
90
0.2
0.4
0.6
0.0
3.0
ap
Sap
Figure 1: The triplet scatter diagram plots triplet as a point defined by the Inchor-Positive sim- ilarity Sap and the Anchor-Negative similarity San- (left) Points below the diagonal correspond to triplets that are "correct" in the sense that the anchor image could get the correct label because the same class example is closer than the different class example. Triplets along the top of the diagram are candidates for hard- regativee mining, triplets along the right edge are candidates for easy-positive mining, and triplets mapped near but below the diagonal are candidates for semi hard triplet mining. (right) Two important cases are the extremes of the hardest negatives and the posiitt-pssstives.
2 BACKGROUND
There is large body of work in distance metric learning and they are leading with two main ideas. One of the idea is to increase the intra-class cluster density and keep the inter-class clusters as far possible. Pairwise loss functions like contrastive divergence (Carreira- Perpiinn & Hinton| 2005 Chopra et al. 2205 Radenović et al. (2016) directly optimize for this constraint, and "No fuss metric
learning" (Movshovitz-Attias et al. 2017), implicitly optimizes for this constraint by assigning each class to different location and penalizes the failure of any example to go to its assigned location.
The other approach more directly reflects the fact that for image retrieval applications, it is not necessary for all elements of a class to be clustered, but instead that the distance to elements of the same class should be smaller than the distance elements of different classes. Directly optimizing for this is based on triplets of images. The triplets are drawn from the training data and include an anchor image, a positive image from the same class, and negative image from a different class.
Key questions for these approaches explore how to select the triplets that are used, Choices such as hard or semi-hard triplet mining (Schroff et al. 2015b; Simo-Serra et al. 2015 Wang et al. 2014) focus on triplets with negative examples that are closest (hard negative mining) or nearly as close the anchor as positive images (semi-hard negative mining) and emphasize creating separations between classes in the embedding space. Recent work such as easy positive triplet mining (Xuan jt al. 2019) selects the closest anchor-positive pairs and ensures that at least they are closer than the nearest negatives.
The next section introduces a diagram to systematically organize these triplet selection approaches, and to explore where different loss functions fail to improve the triplets.
3 TRIPLET SCATTER DIAGRAM
Triplet loss is trained with triplets of images, (Ia, Tp. Un), where is an anchor image, Tp is positive image of the same class as the anchor, and Fn is a negative image of a different class. We consider convolution neural network. f(-) that embeds the images f(xx,),(xx)) f(x,)). We use (f,, fp. f,) to simplify the representation of the normalized feature vectors. When embedded on hypersphere, the cosine similarity is convenient metric measure
unit hypersphere,
2

---

Under review as a conference paper at ICLR 2020
the similarity of anchor-positinn pair Sap fp and anchor-negative pair San fg and this similarity is bounded in the range [-1,
The triplet scatter diagram is approach to characterizing given set of triplets. Figure represents each triplct as a 2D point (Sap, San). describing how similar the positive and negative images are to the anchor. This diagram is useful because the location the diagram describes important features of the triplet:
Triplets that are already in the correct configuration, where the similarity between anchor and positive is greater than the similarity between anchor and negative images are below the San Sap diagonal. Dots representing triplets the correct configuration are drawn in blue, dots where the negative is closer are drawn in red.
Triplets that include an anchor and the most similar of the possible positive examples are the "Easy Positives" and are on the right side of the diagram because Sep tends to be close to 1. We circle these with red ring.
Hard negatives are cases where the anchor is very similar to a negative example, so San is close to I, depicted as red dots circled with a blue ring.
Hard negatives are cases where the anchor is very similar to a negative example, so San is close to I, depicted as red dots circled with a blue ring.
One very selective mining strategy is "Easy-Positive Semi-Hard Negative", where an an- chor is matched with closest possible positive match, and a negative example which has similar similarity. The blue dot circled with red dashed circle highlights one such example.
Another selective mining strategy "Easy-Positive Hard Negative". which selects, for an anchor, the most similar positive and negative examples. The red circle surrounded by blue dashed circle represents one such example.
During the later discussion, we may show a subset area of Ω, Ω2 = [0, x [0, 1J, because it is rare that the hardest negative or positive pairs have a similarity less than 0.
Figure D (right) calls out two specific regions of points that analyze in the next section; the extremes hard negatives and easy positives, and the region that only includes positive similari- ties Ω2 [0, 1] [0, 1], that includes nearly all triplets constructed with easy positives and hard negatives.
4 DIAGRAMMING WHY SOME TRIPLETS ARE HARD TO OPTIMIZE
The triplet seatter diagram offers the ability to understand when the gradient based optimization of the network parameters is effective and when it fails. The triplets are used to train network whose loss function encourages the anchor to be more similar to its positive example (drawn from the same class) than to its negative example (drawn from different class), encouraging Sap to be greater than San- While there are several possible choices, we consider NCA (Goldberger et al. 2005) as the loss function, and denote this L lst differentiate it from an updated loss function introduced later:
exp (Sap)
L 1st (fa, fp. fn) = -log
exp (S.p) + exp (S..)
All of the following derivation can also be done for the triplet loss formulation used in (Schroff et al. 2015a); this has very similar form and is derived in the Appendix.
The gradient of triplets loss L (fa, fn) can be decomposed into two parts: a single gradient with respect to feature vectors fa. fp. f.:
ØL Af. +
aL Af, Ot
OL
AL =
+ Af,
Of, Af..
(2)
Dr.
and subsequently being clear that these feature vectors respond to changes in the model parameters (the CNN network weights) A:
ØL df,
ØL 0r
aL or, AO.
A T.
2O +
A0 +
(3)
Of, 00
Of p 00 df, 00
3

---

Under review as a conference paper at ICLR 2020
The gradient optimization only affects the feature embedding through variations in 8, but first highlight problems with hypersphere embedding assuming that the optimization could directly affect the embedding location. To do this we derive the loss gradient with respect to the feature vector fa. fp. fn and use this gradient to update the feature locations where should decrease the error:
0L
P
new
= fp
agp
=pp
fp
= fp
+ ifa
(4)
Otp p
ØL.
f
new
= fn
0gn
= fn a
fn
ffa
(5)
Öf,
ÔL.
a
f.
.ga
fa
fa 3fn + 8fp
(6)
Hr,
where 3 = a exp Hoxp (S...) and is the learning rate. This gradient update has a clear geometric meaning: the positive point fp is encouraged to move along the direction of the vector fa; the negative point fn is encouraged to move along the opposite direction of the vector fa: the anchor point fa is encouraged to move along the direction of the sum of f, and negative fn- All of these are weighted by the same weighting factor 3. Then we can get the new similarity of anchor-positive and anchor-negative (The derivation is given in the Appendix):
exp (San)
Snew = (1 + SSp + 2,3 35pm - -SPann
S = (1 + S2)Saan - 2,3 + 335pp Sap
(8)
These gradients ga. Ep. En have components that move them off the sphere, computing the cosine similarity requires that we compute the norm of fa new fp new and fn new (the derivation for them is shown in Appendix). Given the norm of updated feature vector, we can calculate the similarity change after the gradient update.
Snew
ASap
Sap
Fp
AS
gnew
San
(10)
new
Because the gradient of the loss function does not consider this normalization, following the negative gradient can actually cause some triplets to push the anchor closer the negative example or push the anchor away from the positive example, even assuming that you can directly push the anchor, positive and negative features vectors in any direction.
The direction in which fa. fp. and fn move depends on the relative position of the fa, fp, fn on the term describe their relative orientation; hypersphere. We use (fully defined in the Appendix) hypersphere is a plane, then y is the dot- when fa. fn. and fp are close enough so that locally the product of normalized vector from fa fp and fa to fn. Therefore, if fp. fa. fn are co-planer then 1, and if moving from fa to fp is orthogonal to the direction from fa to fn. then = 0. Given this description of the relative positions of the anchor, positive and negative points, Figure 2 shows calculations of the change in similarity between the anchor positive and anchor negative for y 0.5. There is an area along the right side of the ASS.p plot highlighting locations where the anchor and positive are pushed farther apart( aSS.p < 0), and along the top of the AS.,. plot highlighting locations where the anchor and negative are pulled closer together( > 0). This behavior arises because the gradient is pushing the feature off the hypersphere and therefore, after normalization, the effect is lost.
This discussion far considers the derivative of the loss function of the position of the feature vectors, but the optimization can only control the feature vectors based on the network parameters 8. Changes the 8 are likely to affect nearby points in similar ways. For example, if there is a hard negative example with easy positive where the anchor is close to both the positive and the negative image, then changing 0 to move the anchor closer to the positive is likely to pull the negative example along with it. We call this effect "entanglement" and propose a simple model to capture its effect on how the gradient update affects the similarities.
We use scalar p and factor 9 / Sap quantify this entanglement. As for the factor q, when anchor, positive and negative are nearby to each other, both Sap and San will be large and will increase the entanglement effect; when positive or negative is far away anchor, one of Sap
4

---

Under review as a conference paper at ICLR 2020
1tt order Loss
2nd order Loss
Afuly 0.51
Aygeny a 0.5. 4.44
10 0.5.p
Afgly 0.5)
68g 0.S.p ASgeny - 0.5 p p=008
45 0.31
Arge
Aogerty
65 0.5)
by 0.5.p
Figure 2: First two rows: numerical simulation for ASaps AS.n. A A.Stotal in equation 9 ap and of of = 0.5 and = 0.4, 0.8. Thrid row: Vector field of y 0.5 and = 0.4, 0.8.
and San will be small and will reduce the entanglement effect. The total similarity changes with entanglement will modelled follows:
A Sttooal
aap + PV Sap. Aan
(11)
up
Stotal
= ASan + PP Sap ASap
(12)
Figure 2 shows (in color) problematic regions where this model of gradient entanglement indicates that anchor and positive images become less similar (Sap 0) and regions where the anchor nega- tive images become more similar for different parameters the entanglement (S >> 0).
While figure 2 captures problematic regions the scatter diagram, description. The bottom row plots of figure2|shoss the vector field on the scatter diagram, indicating that triplets move based the gradient of their loss function. The figure shows several vector field plots with A and Attttal with y = 0.5 and = 0.4, 0.8 settings and indicates the types of movement direction for dots the triplet scatter. When ASap >> O and AS... O, the movement direction will point to up-right. When A < and A.S.. < O, the movement direction will point bottom-left. When AS 0 and AS > O. the movement direction will point to bottom- right. In fact, the entanglement strength may be varied in different situation during the optmization. The exact value will not be discussed in this paper. We only use the entanglement phenomenon to demonstrate problems that happen optimizing triplets with Easy Positives and Hard Negatives.
create more complete
Problem 1: Hard Negative Mining For a given anchor image, hard negative mining chooses the negative example that maximizes San The vector field computed in the case of entanglement shows that most locations with large San (near the top of the plot) have vectors with an upward component, meaning the gradient update for hard negative triplet will push the negative The result is that a network cannot effectively separate the negative pairs and tending to make all points close each other. Initializing a fine-grained visualization tasks (e.g. CARS196) with generic pre-trained network like ImageNet often creates starting conditions where all points are mapped nearby to begin with, leading to an optimization failure where all triplets move towards (1,1) on the triplet scatter diagram and all images are mapped to the same feature location.
closer to anchor.
Problem Easy Positive Mining For a given anchor image, easy positive mining chooses the positive example that maximizes Sap- The vector field computed in the case of entanglement shows that most locations with large Sap (near the right of the plot) have vectors with a strong downward component, meaning the gradient updates pushes the anchor and negative to be negative related, which leads over-training. A general idea for a pair of images to be different is their similarity to be zero, the negative similarity value still means the pair of images are kind of 'related'. In the later
5

---

Under review as a conference paper at ICLR 2020
phase of the optimization, the optimization proceeds the triplet scatter diagram will not effectively keep triplets close to the ideal (1.0) point.
WEIGHT GRADIENT BY SIMILARITY
Triplets that have problem 1 or problem create gradients that move fa. fp. fn in wrong directions. When the anchor is very close to either the positive or the negative points, the gradients defined by their interaction largely lost because of the hypersphere normalization, and the remaining effective gradient is dominated by the entanglement.
Specifically, for problem I, the anchor and the negative image are close together, and not effectively encouraged to move apart, and pull of the anchor image towards the positive pulls the negative image in the same direction. The fix for this problem to emphasize more the part of gradient pushing the anchor and negative apart when San is close to 1.
For problem 2, the anchor and positive image are close together, and there is a more distant negative example. The effect of the distant negative example may push the anchor and positive example further apart. The fix for this problem is to emphasize decrease the weight of the gradient related to the distant negative example Sup is close to I.
A simple weighting strategy addresses both problems. We weight the gp and gn gradients with scalars Wap 1 Sap and Wan = S.n respectively. When negative pair in triplet is close but the positive in the triplet is relative distant to anchor, we want to emphasize pushing the negative pair apart, so we weight Ep by 1 Sap- Similarly, when a positive pair in triplet is close but the negative in the triplet is distant to anchor, we want to decrease the effect of the negative example, then we weight gn with San. Our new gradients have the following form:
ogp
Wapa
(13)
ogn = Wan Fn
(14)
agn = Ber Waw fn Wap
(15)
exp S
where Bw exp (Sup ( (1 ) These can be integrated to find a loss function with these gradients. We call this 2nd-order triplet loss because in the exponent the similarities are squared.
n (fa, Eg, fm) = -log
exp (Sap
2 ap)
(16)
exp (Sap S2 op)
+ exp
S an
The calculation of the terms needed to solve for AS or AS.n for the new loss function in the Appendix, and Figure 2 (the right column) shows that how vector field for the new loss function. In the area near (1,1), there no longer the challenge that triplets are always moved towards (1,1) even when including the effects of entanglement. This helps overcome the problem that the optimization pushes all points towards the same place and we will show this effect in the experimental section.
EXPERIMENTAL RESULTS
We to run a set of experiments on CUB200 WWelinder al. 2010). CAR196 KKruuse et al. 2013),
Stanford online products (Song et al. 2016 and In-shop cloth (Ziwei Liu & Tang 2016) datasets.
All tests are run on the Py Torch platform (Paszke et al. 2017). using ResNet18 and ResNet50 (He
et al. 2016) architectures, pre- trained on ILSVRC 2012- data (Russakovsky et al. 2015). Train- ing images are re- sized 256 by 256 pixels. We adopt a standard data augmentation scheme (ran- dom horizontal flip and random crops padded by 10 pixels on each side). For pre-processing, we normalize the images using the channel means and standard deviations. All networks are trained using stochastic gradient descent (SGD) with 40 epochs. We set initial learning rate 0.005 for CAR, SOP and In-shop cloth dataset and 0.0025 for CUB dataset, and divided by 10 after 20th and 30th epochs. The batch size is 128 and each batch of images contains examples from classes, ran- domly selected from the training data. Throughout the paper, we refer to the n examples per class group.
Comparing the performance of 1st order and 2nd order triplet loss only requires changing one line of code in PyTorch implementation, substituting the loss from Equation 16 the loss from

---

Under review as a conference paper at ICLR 2020
1st order loss
2nd order loss
Loter
Figure 3: The locations of dots moves top-right, top-left, bottom-left and bottom-right. blue color represents the initial phase iterations and the red color represents the later phase iterations
Equation| [ Then we calculate Recall@K K as the measurement for retrieval quality. the CUB, CAR and SOP datasets, both the query set and gallery set refer to the testing set. During the query process, the top-K retrieved images exclude the query image itself. In the In- In-Shop dataset, the query set and gallery set predefined by the original paper.
6.1 VERIFICATION OF VECTOR FIELD
We implement two variants from EPHN paper (Xuan et al., 2019). Hard-Positive with Hard- Negative(HPHN) to mimic the Problem 1 and Easy- Positive with (ea=-eegative(EPEH)) to mimic the Problem 2 with CAR dataset and set n = 16 so that there will be enough positive and negative for easy hard selecting. Also, in the batch, we only allow each feature vector can only be in one triplet to prevent the affection among the triplet. Figure 3 shows two sets experiment results of training a network with 2 epochs(73 batches per epoch) initial phase and later phase of the optimization. We set the learning rate very low(0.00001 so to prevent the model updating too much this experiment and better observe the problem happen in the wrong area.
We plot where the triplet dot move to all possible 4 direction(top-right, top-lcft, bottom-left and bottom-right). This result highly match our proposal model. 1) there is no top-left movement which is not possible in our model. 2) In the initial phase, most of the movement for the I, is top-right and for the 2nd is bottom-right, which the our proposal fix to the vector field 3) In the later phase, most of the movement for the L is bottom-right and for the 2nd is bottom-right, bottom-left and top-right, 4Although the learning rate is small, there is still a patter change with the dot in early phase. L move top-right and 2nd move to bottom-right.
6.2 COMPARATIVE RESULTS FOR EPHN
Hard-Negative mining optimization problem depicts the specific cause of the challenges reported (for example (Harwood et al. 2017 ) for optimizing with hard negative examples. Also, in the EPHN work (Xuan et al., 2019). when n = 2, there is only one positive example to choose from, so Sap is more likely to be far away 1. The negative is chosen the closest negative, San is more likely to be close to 1. This situation is similar to Problem 1. The I loss leads to a singularity at the location (1,1).
In addition, re-implement the test in EPHN work to plot the recall@ @ accuracy CUB, CAR, SOP, and In-shop dataset. Figure 4 shows a clear gap of L 1st and 2nd with EPHN mining. We hypothesize that the small number of examples in most classes in SOP leads to the inconsistent behavior we observe. Moreover, the figure shows Problem 1 happened on the CUB when 2 and CAR when 2, 4, but I 2 loss perform well on with the same setting.
acTOss
6.3 COMPARISON: EPHN Vs EPSHN
Semi- negative mining samples triplets choosing the most similar negative where Sap > San- It is therefore most affected by the Problem 2. We compare the result of easy positive and semi-hard
7

---

Under review as a conference paper at ICLR 2020
shop 532
Figure 4: Recall @ 1 accuracy vs group size CUB, CAR, SOP and In-shop datasets with 1st/2nd order EPHN/EPSHN
Dataset
CUB
CAR
SOP
In-shop
Method
@@L
@@2
@@4
@@L
R@2
R@4
R@
@ 10
R@ 100
R@I R@ 10
@@20
HTL
57.1
68.8
78.7
81.4
88.0
92.7
74.8
88.3
94.8
ABE512
60.6
71.5
79.8
85.2
90.5
94.0
76.3
88.4
94.8
87.3
96.7
97.9
DREML 376
63.9
75.0
83.1
86.0
91.7
95.0
FastA
76.4
89.0
95.1
90.9
97.7
98.5
EP
64.9
75.3
83.5
82.7
89.3
93.0
78.0
90.6
96.3
87.1
96.9
97.9
EPHN-2nd" S12
65.2
75.3
82.9
83.2
89.2
93.2
78.8
90.8
96.3
89.0
96.9
97.8
Table 1: Retrieval Performance the CUB, CAR, SOP and In-shop datasets comparing the best reported results for more complex approaches and/or ensembles. All test are trained with ResNet50
negative mining (EPSHN) and posiiivv hard-negative mining (EPHN) for both 1st order and 2nd order loss functions on CUB, CAR, SOP and In-shop dataset. Figure shows another gap of I,and with EPHN and EPSHN on CUB, CAR and In-shop dataset for most choices of the group size of elements per class in each batch. This result indicates that both Problem and are important for metric learning.
6.4 COMPARING TO THE STATE OF ART
Finally we compare our results with current state-of-the-art embedding approaches, including more complex triplet loss approaches (uaan et al.] approaches (Opitz et al. 2017, Kim et al. 2018 Xuan et al. 2018). Our embeddings are trained with ResNet50 and an output embedding size of 12. For CUB, CAR, SOP and In-shop, the optimal group size is 1,2 and 2. In T the 2nd order Easy Positive Hard Negative approach achieves a new record on the CUB and SOP dataset. On the CAR and In-shop dataset, result is comparable to the ensemble methods.
2017 Ge 2018 Cakir et al., 2019) and ensemble based
CONCLUSION
This paper uses the triplet scatter diagram as a way to describe triplet selection strategies. The dia- gram offers the ability characterize how triplets change the Deep Metric Learning progresses, and we explore the behavior of the gradient descent optimization for the common case where points are normalized forces negative examples closer to the anchor, or positive examples farther from the anchor, and situ- ations that encourage triplets of images that are similar become even more similar. This explain previously observed bad behavior for hard-negate tion to the desired gradients, and derive a loss function that gives those gradients. Experimentally show that this improves the convergence for hard negative triplet selection strategies.
hypersphere. We find that important classes of triplets have an effective gradient
triplet mining. We suggest simple modifica-
With this modification, we no longer observe challenges in optimization with the Easy- eosy-Posi Hard- Negative triplet mining strategies and show that easy- casy-positive hard negative mining gives sults that exceed or are competitive with state of the art approaches that including complicated network architectures and ensembles.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Fatih Cakir, Kun He. Xide Xia, Brian Kulis, and Stan Sclaroff. Deep metric learning to rank. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
Miguel A Carreira-Perping and Geoffrey Hinton. On contrastive divergence learning. In A/S-
TATS, volume 10, pp- 33-40, 2005.
Sumit Chopra, Raia Hadsell, and Yann LeCun. Learning a similarity metric discriminatively, with application to face verification. In Proc. IEFE Conference Computer Vision and Pattern Recog- nition (CVPR), volume pp. 539-546, 2005.
Weifeng Ge. Deep metric learning with hierarchical triplet loss. In Proc. European Conference on Computer Vision (ECCV). September 2018.
Jacob Goldberger, Geoffrey E Hinton, Sam T. Roweis, and Ruslan Salakhutdinov. Neighbour- hood components analysis. In L. K. Saul, Y. Weiss, and L.. Bottou (eds.), Advances in Neural Information Processing Systems 17, pp. 513-520. MIT Press, 2005. URL http::/:///pppr wwt.e//pppppe wwwpc/apprr/aeee www.aperr/6666--e 256.//266622000 neighbooooighh wwwponents-aanaaaaooooooo
nips. cc/
Ben Harwood, BG Kumar, Gustavo Carneiro, Ian Reid, Tom Drummond, et al. Smart mining for deep metric learning. In Proceedings of the IEEE International Conference Computer Vision, pp. 2821-2829 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
Wonsik Kim, Bhavya Goyal, Kunal Chawla, Jungmin Lee, and Keunjoo Kwon. Attention-based ensemble for deep metric learning. In Proc. European Conference on Computer Vision (ECCV), September 2018.
Jonathan Krause, Michael Stark, Jia Deng, and Fei-Fei. 3d object representations for fine fine-graing grained categorization. In 4th International IEEE Workshop 3D Representation and Recognition (3dRR-13) 13), Sydney, Australia, 2013.
Yair Movshovitz-Attias, Alexander Toshev, Thomas K. Leung, Sergey loffe, and Saurabh Singh. No fuss distance metric learning using proxies. Proc. International Conference on Computer Vision (ICCV), Oct 2017.
Michael Opitz, Georg Waltner, Horst Possegger, and Horst Bischof. Bier boosting independent embeddings robustly. In Proc. International Conference on Computer Vision (ICCV), Oct 2017.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS-W, 2017.
Filip Radenović, Giorgos Tolias, and Ondřej Chum. CNN image retrieval learns from bow: Unsu- pervised fine-tuning with hard examples. In European Conference on Computer Vision, pp. 3-20. Springer, 2016.
Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei- ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJV), 115(3):111-253 2015.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proc. IEEE Conference on Computer Vision and Pattern Recogni- tion (CVPR), June 2015a.
Florian Schroff. Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proc. IEEE Conference on Computer Vision and Pattern Recogni- fion (CVPR), pp. 815-823, 2015b.

---

Under review as a conference paper at ICLR 2020
Edgar Simo-Serra, Eduard Trulls, Luis Ferraz, lasonas Kokkinos, Pascal Fua, and Francesc Moreno- Noguer. Discriminative learning of deep convolutional feature point descriptors. In Proc. Inter- national Conference Computer Vision (ICCV), pp. 118-126, 2015.
Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. In D. D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 1857-1865, 2016. URL http::/paperaaaaata//p//aaa pttppaapppaaaaaaa nips. cC papee/ 6200 1et0--immrove--eee mettrccc---ee-mii-------- metrietteiiii. leeieeeraninnnn with wwwmmmuliiiam -
n
loss ob jeceiii..
pdf
Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese. Deep metric learning via lifted structured feature embedding. Proc. IEEE Conference on Computer Vision and Pattern Recog- nition (CVPR), 2016.
Hao Wang, Yitong Wang, Zheng Zhou, Xing Ji, Zhifeng Li, Dihong Gong, Jingchao Zhou, and Wei Liu. Cosface: Large margin cosine loss for deep face recognition. CoRR, abs//801..00 1801.099144, 2018. http:::///aaxi
org/ abs/ / 11101111.111 09414
Jiang Wang, Yang Song, Thomas Leung Chuck Rosenberg, Jingbin Wang. James Philbin, Bo Chen, and Ying Wu. Learning fineggrined image similarity with deep ranking. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1396, 2014.
Welinder, Branson, Mita, C. Wah, Schroff, Belongie, and P. Perona. Caltech-UCSD Birds 200. Technical Report TR-2010-001, California Institute of Technology, 2010.
Hong Xuan, Richard Souvenir, and Robert Pless. Deep randomized ensembles for metric learning. In Proc. European Conference Computer Vision (ECCV), September 2018.
Hong Xuan, Abby Stylianou, and Robert Pless. Improved embeddings with easy positive triplet mining. arXiv preprint Deti:v9904043377 2019.
Yuhui Yuan, Kuiyuan Yang, and Chao Zhang. Hard-aware deeply cascaded embedding. In Proc. International Conference Computer Vision (ICCV), Oct 2017.
Shi Qiu Xiaogang Wang Ziwei Liu, Ping Luo and Xiaoou Tang. Deepfashion: Powering robust clothes recognition and retrieval with rich annotations. In Proc. IEEE Conference on Computer Vision and Puttern Recognition (CVPR), June 2016.
A APPENDIX: SIMILARITY AFTER GRADIENT UPDATING FOR 1ST ORDER LOSS
The following derivation shows how to get Snew and Snew in equation 7 and g
=fa new
fp
ap
=(1 + ) fp + 5f, + Tf - Sf, Tfp -32f, Tf,
(17)
=(1 + 88 SSp +3 - BSpm S
Snew
=fa now fn new
=(1 + 82) T.. Gr. ffa 3f, Tf, + Sf. Tf, -f Tfa
(18)
=(1+ 32) 2,3 + 35pm 832 S.p
We construct two planes: Pap spanned by fa and fp. and Pan spanned by fa and fn. On Pap- fp can be decomposed into two components: fp!) (the direction along f,) and fthe direction vertical to fa). On Pan. fn can be decomposed into two components: fn (the direction along fa) and fn (the direction vertical to f.). Then the Spm should be:
S Spm
fp Tf, -fpl) +
(L
Sap + 7 T S2 V $2
(19)
where 7
which represents the projection factor between Pap and Pan
FA
10

---

Under review as a conference paper at ICLR 2020
B APPENDIX: NORM OF UPDATED FEATURES FOR 1ST ORDER LOSS
The following derivation shows how to derive |ffa "ea [|Ep new and [ new || in equation and 10 On aps 8p can be decomposed into the direction along fp and the direction vertical to f.. On an gn can be decomposed into the direction along fn and the direction vertical to fn. Then,
||cp 2 (1+ ap )² 32 - Sap)
(20)
fn 1 1| = -11-55 + 5 San)
(21)
On Pap, Sa can be decomposed into 3 components: component in the plane and along fa, component in the plane and vertical fa, and component vertical Pap. Then,
lif new 1
-p (3 (B 1- 5 --31I- ) ( +
San) (22)
C APPENDIX: SIMILARITY AFTER GRADIENT UPDATING FOR 2ND ORDER LOSS
The following derivation shows how get Snew and Snew after gradient update with L,and
Snew (1 w 8
Sap 2ap Wan Sw pm Wap Wan WapWan San
(23)
SnEW = (1 + waa Sup - 2wan Bu + uw - W WapWan S2.app Sap an
(24)
D APPENDIX: NORM OF UPDATED FEATURES FOR 2ND ORDER LOSS
The following derivation shows how to derive ||fa new]], (|fp=eee)
new and ||fn new after gradient update
with L 2nd
| new l| (1 W Sw )2 + 2 32 (1 5%
(25)
op
fn new || = (1 - Wan Sw 12 + w² 92
5
(26)
on 2
Fra new
1| = (1 Wap Sn
3 Sw S )²
+ (Wapp / S2p -Wan Bu
82
(27)
+(Wan Bu v 72
S2
E APPENDIX: GRADIENT UPDATES FOR VANILLA TRIPLET LOSS
The main paper uses NCA to define the loss. Another common vanilla triplet-loss function is derived to guarantee a specific margin. This can be expressed in terms fp.fp.fn as:
L max - fpll 112
l|fa
fn + a, max D,0)
(28)
{ -f((f fp)
if D otherwise
8p
aL 0f,
0
(29)
Bfa - f.)
if > 0 otherwise
gn
81.
(30)
0
[f,
fp)
if D D>> otherwise
gA
(31)
0
where =[Ilfa ffpp1 22 I|fa - 11 + a) and 2. For simplicity, in the following discussion,
we set D > 0 for vanilla triplet loss. Then we can get the fa new fp new and fn new and their norm:
fp fp + (f, - fp)
= =(1- B) 3f,
(32)
f, new
fn [f, fa)
+1 8) Bf
(33)
fg new
f, 3r, + Bf
(34)

---

Stotal Under review as a conference paper at ICLR 2020
1st order Loss
Vanilla Loss
2nd order Less
2007
Figure 5: Numerical simulation for Aap, ASan. 1,2nd with 0.2, 0.5, 0.8 and 0.4, 0.8.
Stotal ap
and A an
change L lat
L" and
||Ep 2
(1- 35 (2 p
(35)
| new 2 = (1+ B 32 )
(36)
[r ne = (1+BSap -B0 -BSan) ((B (B
S x3 -2 )2 (3 72
)
(37)
on
The updated similarity Snew and Snew will be:
Snew 3 32) 23 32 -3(1 -3) - 32 San
(38)
ap
Snew
+ 3 B²)
- 2B - 32 + B(1 + 3).pp - -82
(39)
Comparing to the equation 7 and g vanilla triplet behavior is similar to the triplet-NCA. And we simulate the ASap and A.S.. with the vanilla triplet loss figure
We show results for EPHN for = 2 and n = on CAR dataset when the hard negative mining problem happens during the optimization. In both cases, all points initially pushed towards the same location (1,1), which matches our predicted movement on the vector field of L 1st with entanglement in 22
F APPENDIX: NUMERICAL SIMULATION FOR SIMILARITY CHANGE AND THEIR ENTANGLEMENT RESULT FOR 1ST ORDER, VANILLA AND 2ND ORDER LOSS
Figure shows the numerical simulation ASap and AS.n with L L and 2nd These show that the problematic regions in terms are qualitatively similar for different values of p, the parameter in our model of entanglement.
G APPENDIX: EPHN FOR 1ST AND 2ND ORDER LOSS
Figure 6 shows the training of the embedding function observed through the triplet scatter diagram, showing for each point the triplet containing the closest positive and the closest negative from whole
12

---

Under review as a conference paper at ICLR 2020
Selochhopd
10
Sellery
Serteity
Figure 6: Triplet scatter plots after training epoch 1,,,,o. O represents the output of imagenet initialization). 1st row: 1st order EPHN with n 2:2nd row: 1st order EPHN with n 8:3rd row: 2nd order EPHN with n 2:4th row: 2nd order EPHN with n =
dataset after each epoch training. We observe the dynamic movement to the singularity at the loca- tion (1.1) results for EPHN for 2. The 2nd loss for EPHN never has this problem because the weighted gradient approach more effectively separates hard negative pairs early in the optimiza- tion.
When n = 8, the easy-positive part of the triplet is easier because each can pick the closest of 7 neighbors from the same class instead of the randomly assigned same class element and S.P will be closer 1. Meanwhile, the negative is likely to be less similar because there are fewer other examples to choose from. Therefore optimization recovers because triplets are less likely to have large Son and get trapped in the part of the vector field that lead to (1,1).
13


Reviews:
[{"review_id": "rklqVPTmqB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Authors analyze the gradient of easy positive and hard negative pairs and propose a second-order loss for metric learning. Here are my concerns.\n1.\tThe idea of weighting different pairs is not new and can be found in [1].\n2.\tThe comparison is not convincing. Most of existing methods apply Inception as the backbone while this work adopts ResNet50, which has a better performance than Inception. Authors should adopt the same backbone for the fair comparison.\n3.\tThe results in comparison are outdated. Please include the SOTA results, e.g., those in [1].\n4.\tThe improvement from the second order term seems not significant. Besides, the second order term works as a data-dependent margin. Authors should compare it to a fixed margin to illustrate the effectiveness.\n\n\n[1] CVPR’19: Multi-Similarity Loss With General Pair Weighting for Deep Metric Learning\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BylhzTwy5r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 uses the triplet scatter plot as a way to describe triplet selection strategies. The authors explain previously observed bad behavior for hard-negative triplet mining showing that it tends to make all points close to each other. The authors propose a simple modification to the desired gradients and derive a loss function that gives those gradients. With this modification, they show that easy positive hard negative (EPHN) gives results that exceed or are competitive with state of the art approaches. The paper is well-written and makes a convincing argument which will be of interest to a broad community.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJxNpWDatS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Summary: The authors propose a new loss function as well as an adjoining visualization for improved performance of hard negative / easy positive mining for deep triplet metric learning. The authors note that under the NCA loss, if one selects an easy positive / hard negative and computes the gradient with respect to this example, this can lead to the negative example also being pulled closer to the anchor which is undesired. Similar phenomena can also be observed for easy positive / semi-hard negative mining as well. Motivated by this, the authors begin by designing a visualization to make this issue with NCA loss more apparent. Then they design what they refer to as an “entanglement factor” to quantify this issue more precisely. Using the desired dynamics of the gradients for the easy positive / hard negative mining and integrate to form what they refer to as the “second order loss.” Using this loss, they compare against the standard NCA loss on several datasets, showing modest performance gains. They also compare against a variety of other deep triplet embedding frameworks and show competitive results.\n \nComments, questions, and concerns:\n- Overall the paper is well written and clear.\n- The authors do a good job selecting reasonable baselines upon which to compare their method.\n- It is worth noting, though not stated in the paper, that this trade-off between pushing away hard negatives and pulling in easy positives has actually previously been considered in the linear metric learning setting, though the terminology was different then. See the “Large Margin Nearest Neighbors” algorithm by Weinberger and Saul, for example which trains on “target neighbors” and “imposters.”\n- Is projecting back to the hypersphere actually an issue? If the modelling assumption is truly that the learned representation should lie on the hypersphere, then this amounts to projected gradient descent and is a standard tool. In fact, projecting back to the sphere is correct under the model. If magnitude is truly important, then enforcing that the data be on the sphere is incorrect.\n- The claim of a “systematic characterization for triplet selection strategies…” seems overly broad. It seems more correct to state this with respect to NCA loss specifically.\n- NCA loss is just logistic loss penalizing the difference of similarities. The second order loss is the logistic loss penalizing (1/2 times) the squared difference of similarities, hence the cross term. Might be good to state this explicitly.\n- The figures throughout are difficult to read due to the small font size.\n- The y-axis in figure 4 is very different for each plot, which makes the effect seem much larger than it is.\n- There are no error bars on plots or a discussion about how much variance a practitioner should expect running these experiments. If every single training run ever takes the same amount of time, who cares, but otherwise, we have one sample from each distribution and it’s hard to infer from that.\n- Additionally, in Table 1, since there are no confidence regions, it is difficult to know if when the algorithm does perform well if these differences are significant. Especially important since on several datasets, the model does not perform as well as others. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a novel distance metric learning approach. Reviews were mixed, and while the discussion was interesting to follow, some issues, including novelty, comparison with existing approaches, and impact, remain unresolved, and overall, the paper does not seem quite ready for publication. 
Decision: Reject