Title: EXTREME TRIPLET LEARNING: EFFECTIVELY OPTI-MIZING EASY POSITIVES AND 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.

1. INTRODUCTION:

Deep metric learning optimizes an embedding function that maps semantically similar images to relatively nearby locations and maps semantically dissimilar images to distant locations. A number of approaches have been proposed for this problem (Schroff et al., 2015a; 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 a loss function based on triplets of images: an anchor image, a positive image from the same class, and a negative image from a different class. The loss penalizes cases where the anchor is mapped closer to the negative image than it is to the positive image.

One common variant of these functions (e.g. (Wang et al., 2018; Sohn, 2016) ), uses a Deep Learning framework to map images to a feature vector, and computes similarity between normalized feature vectors based on the dot-product. This approach forces the features to lie on a 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 to a hypersphere, a large part of the gradient is lost when points are re-projected back to the sphere, especially in the easy-positive/hard-negative 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 diagram the sets of triplets where standard gradient descent makes the loss increase. We find that this explains problems previously reported in the literature such as the difficulty in optimizing hardnegative triplets (Harwood et al., 2017) . Furthermore, these problems are mostly introduced because the loss-function of the triplets is based on the differences between the anchor-positive and anchornegative distances, so there is an equivalent effect of encouraging the positive image to be closer or the negative image to be further. We create a new loss function that breaks this symmetry and weights the importance of changing the anchor-positive and anchor-negative distances. Briefly, our main contributions are:

• A systematic characterization of triplet selection strategies and a visualization that highlights regions of bad gradient behavior. • A simple modification to a standard loss function to fix bad gradient behavior.

• Improvements to current state of the art results across a range of datasets. 

2. BACKGROUND:

There is a 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 as possible. Pairwise loss functions like contrastive divergence (Carreira-Perpinan & Hinton, 2005; Chopra et al., 2005; 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 to 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 a 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 to 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 et 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, (x a , x p , x n ), where x a is an anchor image, x p is a positive image of the same class as the anchor, and x n is a negative image of a different class. We consider a convolution neural network, f (•) that embeds the images on a unit hypersphere, (f (x a ), f (x p ), f (x n )). We use (f a , f p , f n ) to simplify the representation of the normalized feature vectors. When embedded on a hypersphere, the cosine similarity is a convenient metric to measure the similarity of anchor-positive pair S ap = f a f p and anchor-negative pair S an = f a f n , and this similarity is bounded in the range [-1, 1].

The triplet scatter diagram is an approach to characterizing a given set of triplets. Figure 1 represents each triplet as a 2D point (S ap , S an ), describing how similar the positive and negative images are to the anchor. This diagram is useful because the location on 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 S an = S ap diagonal. Dots representing triplets in 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 S ap tends to be close to 1. We circle these with a red ring. • Hard negatives are cases where the anchor is very similar to a negative example, so S an is close to 1, depicted as red dots circled with a blue ring. • Hard negatives are cases where the anchor is very similar to a negative example, so S an is close to 1, depicted as red dots circled with a blue ring. • One very selective mining strategy is "Easy-Positive, Semi-Hard Negative", where an anchor is matched with closest possible positive match, and a negative example which has a similar similarity. The blue dot circled with red dashed circle highlights one such example. • Another selective mining strategy is "Easy-Positive, Hard Negative", which selects, for an anchor, the most similar positive and negative examples. The red circle surrounded by a blue dashed circle represents one such example.

During the later discussion, we may show a subset area of Ω, Ω s = [0, 1] × [0, 1], because it is rare that the hardest negative or positive pairs have a similarity less than 0.

Figure 1 (right) calls out two specific regions of points that we analyze in the next section; the extremes of hard negatives and easy positives, and the region that only includes positive similarities Ω s = [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 scatter 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 a 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 a different class), encouraging S ap to be greater than S an . While there are several possible choices, we consider NCA (Goldberger et al., 2005) as the loss function, and denote this as L 1st to differentiate it from an updated loss function introduced later:

EQUATION

All of the following derivation can also be done for the triplet loss formulation used in (Schroff et al., 2015a) ; this has a very similar form and is derived in the Appendix.

The gradient of triplets loss L 1st (f a , f p , f n ) can be decomposed into two parts: a single gradient with respect to feature vectors f a , f p , f n :

EQUATION

and subsequently being clear that these feature vectors respond to changes in the model parameters (the CNN network weights) θ:

EQUATION

The gradient optimization only affects the feature embedding through variations in θ, but we 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 f a , f p , f n and use this gradient to update the feature locations where should decrease the error:

EQUATION

where

β = α exp (San)

exp (Sap)+exp (San) and α is the learning rate. This gradient update has a clear geometric meaning: the positive point f p is encouraged to move along the direction of the vector f a ; the negative point f n is encouraged to move along the opposite direction of the vector f a ; the anchor point f a is encouraged to move along the direction of the sum of f p and negative f n . All of these are weighted by the same weighting factor β. Then we can get the new similarity of anchor-positive and anchor-negative (The derivation is given in the Appendix):

EQUATION

EQUATION

These gradients g a , g p , g n have components that move them off the sphere, computing the cosine similarity requires that we compute the norm of f a new , f p new and f n 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.

EQUATION

∆S an =

S new an fa new fn new -S an (10)

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 to 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 f a , f p , and f n move depends on the relative position of the f a , f p , f n on the hypersphere. We use γ (fully defined in the Appendix) as a term to describe their relative orientation; when f a , f n , and f p are close enough so that locally the hypersphere is a plane, then γ is the dotproduct of normalized vector from f a to f p and f a to f n . Therefore, if f p , f a , f n are co-planer then γ = 1, and if moving from f a to f p is orthogonal to the direction from f a to f n , 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 γ = 0.5.

There is an area along the right side of the ∆S ap plot highlighting locations where the anchor and positive are pushed farther apart(∆S ap < 0), and along the top of the ∆S an plot highlighting locations where the anchor and negative are pulled closer together(∆S an > 0). This behavior arises because the gradient is pushing the feature off the hypersphere and therefore, after normalization, the effect is lost.

This discussion so far considers the derivative of the loss as a function of the position of the feature vectors, but the optimization can only control the feature vectors based on the network parameters θ. Changes the θ 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 θ 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 a scalar p and a factor q = S ap S an to quantify this entanglement. As for the factor q, when anchor, positive and negative are nearby to each other, both S ap and S an will be large and q will increase the entanglement effect; when positive or negative is far away to anchor, one of S ap and S an will be small and q will reduce the entanglement effect. The total similarity changes with entanglement will modelled as follows: with γ = 0.5 and p = 0.4, 0.8 settings and indicates the 3 types of movement direction for dots on the triplet scatter. When ∆S ap > 0 and ∆S an > 0, the movement direction will point to up-right. When ∆S ap < 0 and ∆S an < 0, the movement direction will point to bottom-left. When ∆S ap > 0 and ∆S an > 0, the movement direction will point to bottomright. In fact, the entanglement strength may be varied in different situation during the optimization. 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.

Problem 1: Hard Negative Mining For a given anchor image, hard negative mining chooses the negative example that maximizes S an . The vector field computed in the case of entanglement shows that most locations with large S an (near the top of the plot) have vectors with an upward component, meaning the gradient update for a hard negative triplet will push the negative even closer to anchor. The result is that a network cannot effectively separate the negative pairs and tending to make all points close to each other. Initializing a fine-grained visualization tasks (e.g. CARS196) with a generic pre-trained network like ImageNet often creates a 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.

Problem 2: Easy Positive Mining For a given anchor image, easy positive mining chooses the positive example that maximizes S ap . The vector field computed in the case of entanglement shows that most locations with large S ap (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 a kind of 'related'. In the later phase of the optimization, as the optimization proceeds the triplet scatter diagram will not effectively keep triplets close to the ideal (1,0) point.

5. WEIGHT GRADIENT BY SIMILARITY:

Triplets that have problem 1 or problem 2 create gradients that move f a , f p , f n in wrong directions. When the anchor is very close to either the positive or the negative points, the gradients defined by their interaction is largely lost because of the hypersphere normalization, and the remaining effective gradient is dominated by the entanglement.

Specifically, for problem 1, 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 is to emphasize more the part of gradient pushing the anchor and negative apart when S an 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 S ap is close to 1.

A simple weighting strategy addresses both problems. We weight the g p and g n gradients with scalars w ap = 1 -S ap and w an = S an respectively. When a negative pair in a 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 g p by 1 -S ap . Similarly, when a positive pair in a 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 g n with S an . Our new gradients have the following form:

EQUATION

)

where

β w = α exp ( 1 2 S 2 an ) exp (Sap-1 2 S 2 ap )+exp ( 1 2 S 2

an ) These can be integrated to find a loss function with these gradients. We call this a 2nd-order triplet loss because in the exponent the similarities are squared.

EQUATION

The calculation of the terms needed to solve for ∆S ap or ∆S an 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 is 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.

6. EXPERIMENTAL RESULTS:

We to run a set of experiments on CUB200 (Welinder et al., 2010) , CAR196 (Krause 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 PyTorch platform (Paszke et al., 2017) , using ResNet18 and ResNet50 (He et al., 2016) architectures, pre-trained on ILSVRC 2012-CLS data (Russakovsky et al., 2015) . Training images are re-sized to 256 by 256 pixels. We adopt a standard data augmentation scheme (random 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 20 th and 30 th epochs. The batch size is 128 and each batch of images contains n examples from c classes, randomly selected from the training data. Throughout the paper, we refer to the n examples per class as a group.

Comparing the performance of 1st order and 2nd order triplet loss only requires changing one line of code in a PyTorch implementation, substituting the loss from Equation 16for the loss from 1. Then we calculate Recall@K as the measurement for retrieval quality. In 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-Shop dataset, the query set and gallery set are 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 Easy-Negative(EPEH) to mimic the Problem 2 with CAR dataset and set n = 16 so that there will be enough positive and negative for easy or 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) at initial phase and later phase of the optimization. We set the learning rate very low(0.00001) so as to prevent the model updating too much in 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-left, 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 L 1st is top-right and for the L 2nd is bottom-right, which fit the our proposal fix to the vector field 3) In the later phase, most of the movement for the L 1st is bottom-right and for the L 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 1st move to top-right and L 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 S ap is more likely to be far away to 1. The negative is chosen as the closest negative, so S an is more likely to be close to 1. This situation is similar to Problem 1. The L 1st loss leads to a singularity at the location (1,1).

In addition, we re-implement the test in EPHN work to plot the recall@1 accuracy versus n across CUB, CAR, SOP, and In-shop dataset. Figure 4 shows a clear gap of L 1st and L 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 n = 2 and CAR when n = 2, 4, but L 2nd loss perform well on with the same setting.

6.3. COMPARISON: EPHN VS EPSHN:

Semi-hard negative mining samples triplets choosing the most similar negative where S ap > S an .

It is therefore most affected by the Problem 2. We compare the result of easy positive and semi-hard In-shop Method R@1 R@2 R@4 R@1 R@2 R@4 R@1 R@10 R@100 R@1 R@10 R@20 HTL Table 1 : Retrieval Performance on the CUB, CAR, SOP and In-shop datasets comparing to the best reported results for more complex approaches and/or ensembles. All test are trained with ResNet50 negative mining (EPSHN) and easy-positive hard-negative mining (EPHN) for both 1st order and 2nd order loss functions on CUB, CAR, SOP and In-shop dataset. Figure 4 shows a another gap of L 2nd with EPHN and EPSHN on CUB, CAR and In-shop dataset for most choices of the group size n of elements per class in each batch. This result indicates that both Problem 1 and 2 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 (Yuan et al., 2017; Ge, 2018; Cakir et al., 2019) and ensemble based 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 512. For CUB, CAR, SOP and In-shop, the optimal group size is 8,16,2 and 2. In Table 1 , 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, our result is comparable to the ensemble methods.

7. CONCLUSION:

This paper uses the triplet scatter diagram as a way to describe triplet selection strategies. The diagram offers the ability to characterize how triplets change as the Deep Metric Learning progresses, and we explore the behavior of the gradient descent optimization for the common case where points are normalized to a hypersphere. We find that important classes of triplets have an effective gradient forces negative examples closer to the anchor, or positive examples farther from the anchor, and situations that encourage triplets of images that are all similar to become even more similar. This explain previously observed bad behavior for hard-negative triplet mining. We suggest a simple modification to the desired gradients, and derive a loss function that gives those gradients. Experimentally we show that this improves the convergence for hard negative triplet selection strategies.

With this modification, we no longer observe challenges in optimization with the Easy-Positive Hard-Negative triplet mining strategies and show that easy-positive hard negative mining gives results that exceed or are competitive with state of the art approaches that including complicated network architectures and ensembles.

A APPENDIX: SIMILARITY AFTER GRADIENT UPDATING FOR 1ST ORDER

LOSS:

The following derivation shows how to get S new ap and S new an in equation 7 and 8.

EQUATION

We construct two planes: P ap spanned by f a and f p , and P an spanned by f a and f n . On P ap , f p can be decomposed into two components: f a p (the direction along f a ) and f a⊥ p (the direction vertical to f a ). On P an , f n can be decomposed into two components: f a n (the direction along f a ) and f a⊥ n (the direction vertical to f a ). Then the S pn should be:

EQUATION

)

where γ = The following derivation shows how to derive f a new , f p new and f n new in equation 9 and 10. On P ap , g p can be decomposed into the direction along f p and the direction vertical to f p . On P an , g n can be decomposed into the direction along f n and the direction vertical to f n . Then,

EQUATION

EQUATION

On P ap , g a can be decomposed into 3 components: component in the plane and along f a , component in the plane and vertical f a , and component vertical to P ap . Then, 

EQUATION

EQUATION

EQUATION

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 of f a ,f p ,f n as:

EQUATION

EQUATION

)

where D = ( f a -f p 2 -f a -f n 2 + α) and β = 2. For simplicity, in the following discussion, we set D > 0 for vanilla triplet loss. Then we can get the f a new , f p new and f n new and their norm: Comparing to the equation 7 and 8, vanilla triplet behavior is similar to the triplet-NCA. And we simulate the ∆S ap and ∆S an with the vanilla triplet loss in figure 5 .

f p new = f p + β(f a -f p ) = (1 -β)f p + βf a (32) f n new = f n -β(f a -f n ) = (1 + β)f n -βf a (33) f a new = f a -βf n + βf p (34)

We show results for EPHN for n = 2 and n = 8 on CAR dataset when the hard negative mining problem happens during the optimization. In both cases, all points are initially pushed towards the same location (1,1), which matches our predicted movement on the vector field of L 1st with entanglement in figure 2 . 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 a p will be closer to 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 S an and get trapped in the part of the vector field that lead to (1,1).

:



Figures and Tables:

Figure 1: The triplet scatter diagram plots a triplet as a point defined by the Anchor-Positive similarity S ap and the Anchor-Negative similarity S an . (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-negative 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 easiest-positives.

Figure 2: First two rows: numerical simulation for ∆S ap , ∆S an , ∆S total ap , ∆S total an in equation 9, 10, 11 and 12 of γ = 0.5 and p = 0.4, 0.8. Thrid row: Vector field of γ = 0.5 and p = 0.4, 0.8.

Figure 2 shows (in color) problematic regions where this model of gradient entanglement indicates that anchor and positive images become less similar (S ap < 0) and regions where the anchor negative images become more similar for different parameters of the entanglement (S an > 0). While figure 2 captures problematic regions on the scatter diagram, we can create a more complete description. The bottom row plots of figure2 shows the vector field on the scatter diagram, indicating that triplets move based on the gradient of their loss function. The figure shows several vector field plots with ∆S total ap and ∆S total an

Figure 3: The locations of dots moves top-right, top-left, bottom-left and bottom-right.The blue color represents the initial phase iterations and the red color represents the later phase iterations

Figure 4: Recall@1 accuracy vs group size n on CUB, CAR, SOP and In-shop datasets with 1st/2nd order EPHN/EPSHN Dataset CUB CAR SOPIn-shop Method R@1 R@2 R@4 R@1 R@2 R@4 R@1 R@10 R@100 R@1 R@10 R@20 HTL512  57.1 68.8 78.7 81.4 88.0 92.7 74.8 88.3 94.8 ---ABE 512 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 576 63.9 75.0 83.1 86.0 91.7 95.0 ------FastAP 512 ------76.4 89.0 95.1 90.9 97.7 98.5 EPHN-1st 512 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 512 65.2 75.3 82.9 83.2 89.2 93.2 78.8 90.8 96.3 89.0 96.9 97.8

4 89.0 95.1 90.9 97.7 98.5 EPHN-1st 512 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 512 65.2 75.3 82.9 83.2 89.2 93.2 78.8 90.8 96.3 89.0 96.9 97.8

projection factor between P ap and P an B APPENDIX: NORM OF UPDATED FEATURES FOR 1ST ORDER LOSS

Figure 5: Numerical simulation for ∆S ap , ∆S an , ∆S total ap and ∆S total an change of L 1st , L v and L 2nd with γ = 0.2, 0.5, 0.8 and p = 0.4, 0.8.

β + βS ap ) 2 + β 2 (1 -S 2 ap )(35)f n new 2 = (1 + β -βS an ) 2 + β 2 (1 -S 2 an ) (36)f a new 2 = (1+βS ap -βS an ) 2 +(β 1 -S 2 ap -γβ 1 -S 2 an ) 2 +(β 1 -γ 2 1 -S 2an ) 2 (37) The updated similarity S new ap and S new an will be:S new ap = (1 -β + β 2 )S ap + 2β -β 2 -β(1 -β)S pn -β 2 S an(38)S new an = (1 + β + β 2 )S an -2β -β 2 + β(1 + β)S pn -β 2 S ap (39)

Figure5shows the numerical simulation ∆S ap and ∆S an with L 1st , L v and L 2nd . These show that the problematic regions in terms are qualitatively similar for different values of p, the parameter in our model of entanglement.

Figure 6: Triplet scatter plots after training epoch 0,5,10,15,40(epoch 0 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 = 8

ap + 2w ap β w -w an β w S pn -w ap w an β 2 ap -2w an β w + w ap β w S pn -w ap w an β 2

Table content: <table><tr><td/><td/><td/><td/><td>an ) 2 (22)</td></tr><tr><td colspan="5">C APPENDIX: SIMILARITY AFTER GRADIENT UPDATING FOR 2ND ORDER</td></tr><tr><td>LOSS</td><td/><td/><td/></tr><tr><td colspan="5">The following derivation shows how to get S new ap and S new an after gradient update with L 2nd</td></tr><tr><td colspan="5">S new ap = (1 + w 2 ap β 2 w )S w S an</td><td>(23)</td></tr><tr><td colspan="5">S new an = (1 + w 2 an β 2 w )S w S ap</td><td>(24)</td></tr><tr><td colspan="5">D APPENDIX: NORM OF UPDATED FEATURES FOR 2ND ORDER LOSS</td></tr><tr><td colspan="2">The following derivation shows how to derive f a</td><td>new , f p</td><td>new and f n</td><td>new after gradient update</td></tr><tr><td>with L 2nd .</td><td/><td/><td/></tr><tr><td>f p</td><td>new 2</td><td/><td/></tr></table>

Peer review (iclr2020):
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. Comments, questions, and concerns: - Overall the paper is well written and clear. - The authors do a good job selecting reasonable baselines upon which to compare their method. - 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.” - 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. - 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. - 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. - The figures throughout are difficult to read due to the small font size. - The y-axis in figure 4 is very different for each plot, which makes the effect seem much larger than it is. - 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. - 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.