Year: 2019

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.

heading: 1 INTRODUCTION
text: 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; MovshovitzAttias 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.

heading: 2 BACKGROUND
text: 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; Radenović 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.

heading: 3 TRIPLET SCATTER DIAGRAM
text: Triplet loss is trained with triplets of images, (xa, xp, xn), where xa is an anchor image, xp is a positive image of the same class as the anchor, and xn is a negative image of a different class. We consider a convolution neural network, f(·) that embeds the images on a unit hypersphere, (f(xa), f(xp), f(xn)). We use (fa, fp, fn) 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 Sap = fᵀa fp and anchor-negative pair San = f ᵀ a fn, 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 (Sap, San), 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 San = Sap 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 Sap 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 San 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 San 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.

heading: 4 DIAGRAMMING WHY SOME TRIPLETS ARE HARD TO OPTIMIZE
text: 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 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 as L1st to differentiate it from an updated loss function introduced later:
L1st(fa, fp, fn) = −log exp (Sap)
exp (Sap) + exp (San) (1)
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 L1st(fa, fp, fn) can be decomposed into two parts: a single gradient with respect to feature vectors fa, fp, fn:
∆L = ∂L
∂fa ∆fa +
∂L ∂fp ∆fp + ∂L ∂fn ∆fn, (2)
and subsequently being clear that these feature vectors respond to changes in the model parameters (the CNN network weights) θ:
∆L = ∂L
∂fa
∂fa ∂θ ∆θ + ∂L
∂fp
∂fp ∂θ ∆θ + ∂L
∂fn
∂fn ∂θ ∆θ. (3)
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 fa, fp, fn and use this gradient to update the feature locations where should decrease the error:
fp new = fp − αgp = fp − α
∂L ∂fp = fp + βfa (4)
fn new = fn − αgn = fn − α
∂L ∂fn = fn − βfa (5)
fa new = fa − αga = fa − α
∂L ∂fa = fa − βfn + βfp (6)
where β = α exp (San)exp (Sap)+exp (San) 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 fp and negative fn. 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):
Snewap = (1 + β 2)Sap + 2β − βSpn − β2San (7)
Snewan = (1 + β 2)San − 2β + βSpn − β2Sap (8)
These gradients ga, gp, gn have components that move them off the sphere, computing the cosine similarity requires that we compute the norm of fanew, fpnew and fnnew(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.
∆Sap = Snewap
‖fanew‖‖fpnew‖ − Sap (9)
∆San = Snewan
‖fanew‖‖fnnew‖ − San (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 fa, fp, and fn move depends on the relative position of the fa, fp, fn on the hypersphere. We use γ (fully defined in the Appendix) as a term to describe their relative orientation; when fa, fn, and fp are close enough so that locally the hypersphere is a plane, then γ is the dotproduct of normalized vector from fa to 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 γ = 0.5. There is an area along the right side of the ∆Sap plot highlighting locations where the anchor and positive are pushed farther apart(∆Sap < 0), and along the top of the ∆San plot highlighting locations where the anchor and negative are pulled closer together(∆San > 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 = √ SapSan to 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 q will increase the entanglement effect; when positive or negative is far away to anchor, one of Sap
and San will be small and q will reduce the entanglement effect. The total similarity changes with entanglement will modelled as follows:
∆Stotalap = ∆Sap + p √ SapSan∆San (11)
∆Stotalan = ∆San + p √ SapSan∆Sap (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 negative images become more similar for different parameters of the entanglement (San > 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 ∆Stotalap and ∆S total an 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 ∆Sap > 0 and ∆San > 0, the movement direction will point to up-right. When ∆Sap < 0 and ∆San < 0, the movement direction will point to bottom-left. When ∆Sap > 0 and ∆San > 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 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 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 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 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.

heading: 5 WEIGHT GRADIENT BY SIMILARITY
text: Triplets that have problem 1 or problem 2 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 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 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 Sap is close to 1.
A simple weighting strategy addresses both problems. We weight the gp and gn gradients with scalars wap = 1 − Sap and wan = San 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 gp by 1 − Sap. 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 gn with San. Our new gradients have the following form:
αgp w = −βwwapfa (13) αgn w = βwwanfa (14) αga w = βwwanfn − βwwapfp (15)
where βw = α exp ( 12S 2 an)
exp (Sap− 12S2ap)+exp ( 1 2S 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.
L2nd(fa, fp, fn) = −log exp (Sap − 12S 2 ap)
exp (Sap − 12S2ap) + exp ( 1 2S 2 an)
, (16)
The calculation of the terms needed to solve for ∆Sap or ∆San 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.

heading: 6 EXPERIMENTAL RESULTS
text: 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 20th and 30th 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 16 for the loss from
Equation 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.

heading: 6.1 VERIFICATION OF VECTOR FIELD
text: We implement two variants from EPHN paper (Xuan et al., 2019), Hard-Positive with HardNegative(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 L1st is top-right and for the L2nd is bottom-right, which fit the our proposal fix to the vector field 3) In the later phase, most of the movement for the L1st is bottom-right and for the L2nd 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. L1st move to top-right and L2nd move to bottom-right.

heading: 6.2 COMPARATIVE RESULTS FOR EPHN
text: 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 to 1. The negative is chosen as the closest negative, so San is more likely to be close to 1. This situation is similar to Problem 1. The L1st 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 L1st and L2nd 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 L2nd loss perform well on with the same setting.

heading: 6.3 COMPARISON: EPHN VS EPSHN
text: Semi-hard 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
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 L2nd 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.

heading: 6.4 COMPARING TO THE STATE OF ART
text: 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.

heading: 7 CONCLUSION
text: 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.

heading: A APPENDIX: SIMILARITY AFTER GRADIENT UPDATING FOR 1ST ORDER LOSS
text: The following derivation shows how to get Snewap and S new an in equation 7 and 8.
Snewap =fa newᵀfp new
=(1 + β2)fa ᵀfp + βfa ᵀfa + βfp ᵀfp − βfnᵀfp − β2fnᵀfa
=(1 + β2)Sap + 2β − βSpn − β2San
(17)
Snewan =fa newᵀfn new
=(1 + β2)fa ᵀfn − βfaᵀfa − βfnᵀfn + βfpᵀfn − β2fpᵀfa
=(1 + β2)Sap − 2β + βSpn − β2Sap
(18)
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: fa‖p (the direction along fa) and fa⊥p (the direction vertical to fa). On Pan, fn can be decomposed into two components: f a‖ n (the direction along fa) and fa⊥n (the direction vertical to fa). Then the Spn should be:
Spn = fp ᵀfn = (f a‖ p + f a⊥ p )(f a‖ n + f a⊥ n ) = SapSan + γ √ 1− S2ap √ 1− S2an (19)
where γ = fa⊥p f a⊥ n
‖fa⊥p ‖‖fa⊥n ‖ which represents the projection factor between Pap and Pan

heading: B APPENDIX: NORM OF UPDATED FEATURES FOR 1ST ORDER LOSS
text: The following derivation shows how to derive ‖fanew‖, ‖fpnew‖ and ‖fnnew‖ in equation 9 and 10. On Pap, gp can be decomposed into the direction along fp and the direction vertical to fp. On Pan, gn can be decomposed into the direction along fn and the direction vertical to fn. Then,
‖fpnew‖2 = (1 + βSap)2 + β2(1− S2ap) (20) ‖fnnew‖2 = (1− βSan)2 + β2(1− S2an) (21)
On Pap, ga can be decomposed into 3 components: component in the plane and along fa, component in the plane and vertical fa, and component vertical to Pap. Then,
‖fanew‖2 = (1+βSap−βSan)2+(β √ 1− S2ap−γβ √ 1− S2an)2+(β √ 1− γ2 √ 1− S2an)2 (22)

heading: C APPENDIX: SIMILARITY AFTER GRADIENT UPDATING FOR 2ND ORDER LOSS
text: The following derivation shows how to get Snewap and S new an after gradient update with L 2nd
Snewap = (1 + w 2 apβ 2 w)Sap + 2wapβw − wanβwSpn − wapwanβ2wSan (23)
Snewan = (1 + w 2 anβ 2 w)Sap − 2wanβw + wapβwSpn − wapwanβ2wSap (24)

heading: D APPENDIX: NORM OF UPDATED FEATURES FOR 2ND ORDER LOSS
text: The following derivation shows how to derive ‖fanew‖, ‖fpnew‖ and ‖fnnew‖ after gradient update with L2nd.
‖fpnew‖2 = (1 + wapβwSap)2 + w2apβ2w(1− S2ap) (25) ‖fnnew‖2 = (1− wanβwSan)2 + w2anβ2w(1− S2an) (26)
‖fanew‖2 = (1 + wapβwSap − wanβwSan)2
+(wapβw √ 1− S2ap − γwanβw √ 1− S2an)2
+(wanβw √ 1− γ2 √ 1− S2an)2 (27)

heading: E APPENDIX: GRADIENT UPDATES FOR VANILLA TRIPLET LOSS
text: 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 fa,fp,fn as:
L = max(‖fa − fp‖2 − ‖fa − fn‖2 + α, 0) = max(D, 0) (28)
gp = ∂L ∂fp = { −β(fa − fp) if D > 0 0 otherwise
(29)
gn = ∂L ∂fn = { β(fa − fn) if D > 0 0 otherwise
(30)
ga = ∂L ∂fa = { β(fn − fp) if D > 0 0 otherwise
(31)
where D = (‖fa − fp‖2 − ‖fa − fn‖2 + α) and β = 2. For simplicity, in the following discussion, we set D > 0 for vanilla triplet loss. Then we can get the fanew, fpnew and fnnew and their norm:
fp new = fp + β(fa − fp) = (1− β)fp + βfa (32) fn new = fn − β(fa − fn) = (1 + β)fn − βfa (33) fa new = fa − βfn + βfp (34)
‖fpnew‖2 = (1− β + βSap)2 + β2(1− S2ap) (35) ‖fnnew‖2 = (1 + β − βSan)2 + β2(1− S2an) (36)
‖fanew‖2 = (1+βSap−βSan)2+(β √ 1− S2ap−γβ √ 1− S2an)2+(β √ 1− γ2 √ 1− S2an)2 (37)
The updated similarity Snewap and S new an will be:
Snewap = (1− β + β2)Sap + 2β − β2 − β(1− β)Spn − β2San (38) Snewan = (1 + β + β 2)San − 2β − β2 + β(1 + β)Spn − β2Sap (39)
Comparing to the equation 7 and 8, vanilla triplet behavior is similar to the triplet-NCA. And we simulate the ∆Sap and ∆San with the vanilla triplet loss in figure 5.
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 L1st with entanglement in figure 2.

heading: F APPENDIX: NUMERICAL SIMULATION FOR SIMILARITY CHANGE AND THEIR ENTANGLEMENT RESULT FOR 1ST ORDER, VANILLA AND 2ND ORDER LOSS
text: Figure 5 shows the numerical simulation ∆Sap and ∆San with L1st, Lv and L2nd. These show that the problematic regions in terms are qualitatively similar for different values of p, the parameter in our model of entanglement.

heading: G APPENDIX: EPHN FOR 1ST AND 2ND ORDER LOSS
text: 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
dataset after each epoch training. We observe the dynamic movement to the singularity at the location (1,1) results for EPHN for n = 2. The L2nd loss for EPHN never has this problem because the weighted gradient approach more effectively separates hard negative pairs early on in the optimization.
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 Sap 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 San and get trapped in the part of the vector field that lead to (1,1).

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

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.