Title: A UNIFIED VIEW OF DEEP METRIC LEARNING VIA GRADIENT ANALYSIS Anonymous

Abstract: Loss functions play a pivotal role in deep metric learning (DML). A large variety of loss functions have been proposed in DML recently. However, it remains difficult to answer this question: what are the intrinsic differences among these loss functions? This paper answers this question by proposing a unified perspective to rethink deep metric loss functions. We show theoretically that most DML methods in deep metric learning, in view of gradient equivalence, are essentially weight assignment strategies of training pairs. Based on this unified view, we revisit several typical DML methods and disclose their hidden drawbacks. Moreover, we point out the key components of an effective DML approach which drives us to propose our weight assignment framework. We evaluate our method on image retrieval tasks, and show that it outperforms the state-of-the-art DML approaches by a significant margin on the CUB-200-2011, Cars-196, Stanford Online Products and In-Shop Clothes Retrieval datasets.

1. INTRODUCTION:

Deep metric learning (DML) approaches learn to project images to a discriminative embedding space via deep neural networks. The embedded vectors of similar samples are closer while that of dissimilar samples are further. We call a method pair-based when its loss function can be expressed in terms of pairwise cosine similarities1 . Most DML methods belong to this category, such as contrastive (Hadsell et al. (2006) ; Sohn (2016) ), triplet (Hoffer & Ailon (2015) ), quadruplet (Law et al. (2013) ), lifted structure (Oh Song et al. (2016) ), N-pairs (Sohn (2016) ), binomial deviance (Yi et al. (2014) ), histogram (Ustinova & Lempitsky (2016) ) and angular (Wang et al. (2017) ) losses.

One critical problem of these pair-based methods is how to discover and harness informative pairs, especially hard negative pairs because they pose two challenges for metric learning: (1) The number of negative pairs is second polynomial to the dataset size, thus utilizing all of the them is timeconsuming and infeasible. (2) As we will show in our experiment section, training with numerous easy pairs causes performance degradation if involving these easy instances in the training process.

Existing DML methods propose different strategies to mitigate this problem. Contrastive loss neglects the negative pairs whose dot products are below a given threshold, while triplet loss only utilizes the negative pairs whose similarities are higher than that of the positive minus a fixed margin. However, contrastive is too absolute while triplet is too sensitive. Both cannot make full use of all the informative pairwise relations as stated in Hoffer & Ailon (2015) ; Wu et al. (2017) . In contrast to employing a fixed margin, some other pair-based methods with log-exp formulation, like binomial deviance and N-pairs losses, solve this problem in a relative subtle way which will be detailed in Section 4.

In this paper, we establish a unified view of deep metric learning by theoretically proving all pairbased methods are equivalent to weight assignment strategies (Section 3). Thus, the intrinsic difference of these pair-based methods is that they assign pairs different weight coefficients, which leads us to rethink existing DML methods and discover their concrete pros and cons.

To seek an effective DML method, we posit two key factors of an suitable weight assignment (Section 5): (1) Assigning zero weight coefficients to easy pairs, since such pairs are already well taken care of by the current model. Assigning easy pairs with nonzero weight may lead performance degradation. (2) Assigning weight to a pair by considering its absolute similarity and relative similarity compared with other pairs sharing the same anchor.

To the best of our knowledge, none of existing methods satisfy these two factors simultaneously. Instead, we propose a novel weight assignment strategy (Section 5.2) to solve this problem. It distinguishes the uninformative pairs through valid triplet based hard mining (VTHM) and assigns suitable weights to pairs via relative and absolute similarity based weight assignment (RAW).

To demonstrate the effectiveness of our proposed unified weight assignment framework, we conduct experiments on CUB-200-2011 (Wah et al. (2011) ), Cars-196 (Krause et al. (2013) ), Stanford Online Product (Oh Song et al. (2016) ), and In-Shop Clothes Retrieval (Liu et al. (2016b) ) datasets for the task of image retrieval (Section 6). Experimental results show that our framework improves the stateof-the-art performance by a large margin. Moreover, existing methods, such as binomial deviance and lifted structure loss, can also be improved when they get rid of the side effect of easy samples guided by our framework.

2. RELATED WORK:

Pair-based DML. Siamese network (Hadsell et al. (2006) ) that learns embedding via contrastive loss, is one of the first pair-based DML methods. It pulls positive pairs as close as possible, while keeps negative pairs farther than a give distance. Triplet loss (Hoffer & Ailon (2015) ) is based on triplets that consists of one positive pair and one negative pair sharing the same anchor point and targets learn an embedding space where the similarity of the negative pair is lower than that of the positive pair by a given margin. Inspired by triplet loss, methods using quadruplets emerged, e.g., PDDM (Law et al. (2013) ) and histogram loss (Ustinova & Lempitsky (2016) ).

Oh Song et al. (2016) argue that contrastive and triplet losses have not exploited all the pairwise relations of samples in one mini-batch, and propose lifted structure loss to utilize all the pairwise relations. However, it only subsamples approximately equal number of negative pairs of examples as positive randomly, thus, abandons a large number of informative negative pairs. Yi et al. (2014) propose binomial deviance loss using binomial deviance to evaluate the cost between labels and similarities, and pay more attention on hard pairs.

Hard Mining and Sampling:

The importance of hard mining in DML has been realized recently (Schroff et al. (2015) ; Harwood et al. (2017); Wu et al. (2017) ; Ge et al. (2018) ), since most pairs, especially negative pairs, are uninformative and cannot boost the model further. Schroff et al. (2015) propose semi-hard mining, which only uses semi-hard triplets whose negative pair is farther than its positive pair. Such valid semi-hard triplets are scarce thus semi-hard mining needs a large batchsize, 1800 in the paper, to seek informative pairs. Harwood et al. (2017) provide a framework named smart mining to search hard samples from the whole dataset, which suffers from off-line computation burden. HTL (Ge et al. (2018) ) builds a hierarchal tree of all the classes to find hard negative pairs. Wu et al. ( 2017) discuss the importance of sampling, and propose a sampling approach named distance weighted sampling which sample negative examples uniformly according to similarity.

Compared with these methods above only focusing on sampling, we propose a more generalized view: weight assignment view, and sampling is a special category of weight assignment whose weights are 0 or 1. Unlike some heuristically designed pair-based methods, our DML method is carefully designed driven by the instruction of the unified weight assignment view.

3. A UNIFIED WEIGHT ASSIGNMENT VIEW:

Notations. Let x i ∈ R d×1 be a real valued instance vector and y i ∈ {1, 2 . . . , C} denote the label of x i . Then we have the instance matrix X ∈ R m×d and the label vector y ∈ {1, 2, . . . , C} m for m training samples. An instance x i is projected to a unit sphere in an l dimension space by f (•; θ) : R d → S l-1 , where f is a learned function (a neural network) parameterized by θ.

In this paper, we use the cosine similarity s i,j =< f (x i ; θ), f (x j ; θ) > to measure the similarity between x i and x j , resulting an m × m similarity matrix S whose element at (i, j) is s i,j . Furthermore, P i (N i ) denotes the index set of positive (negative) samples of the anchor point x i (i.e., P i = {j|y j = y i ∧ j = i}, and N i = {j|y j = y i }). Given a pair-based DML loss L(X, y; θ), it can be expressed as a function in terms of S: H(S, y) according to the definition of pair-based.

To better understand our theorem, we define gradient equivalence as following: Definition 3.1. At the t-th iteration, given two loss functions F(X, y; θ) and G(X, y; θ), if

EQUATION

where ∂F (X,y;θ) ∂θ t

is the partial gradient of F(X, y; θ) w.r.t. θ at θ t , then we call F(X, y; θ) and G(X, y; θ) are gradient equivalent at the t-th iteration.

Gradient equivalence indicates these two functions have equal derivatives w.r.t. the model parameters at the t-th iteration, thus two gradient equivalent loss functions are the same for model training with gradient-based optimizer such SGD and Adam. Optimizing one loss function is equivalent to optimizing the other. Theorem 3.1. For any pair-based loss L(X, y; θ), there exists a loss function gradient equivalent to L with the following formulation:

EQUATION

where w i,j ≥ 0 denoting the weight assigned to pair {x i , x j }.

Proof. Since L is pair-based, L can be expressed as a function of S: H(S, y). Thus the partial gradient of L w.r.t. θ at t-th iteration is:

EQUATION

where I i,j = 1 when {x i , x j } is a positive pair, otherwise 0.

Let

w i,j = 1 2 (1 -2I i,j ) ∂H(S,y) ∂si,j t

, then in Equation (2),

F(S, y) = m i=1   k∈Ni 1 2 (1 -2I i,k ) ∂H(S, y) ∂s i,k t s i,k - j∈Pi 1 2 (1 -2I i,j ) ∂H(S, y) ∂s i,j t s i,j   (4)

is gradient equivalent to L.

Theorem 3.1 unifies all existing pair-based approaches as weight assignment scheme and sheds light on the dark side of them. In the next section, we unveil their vital drawbacks that are undetectable if only analyzing their loss functions by studying their respective weight assignments.

4. RETHINKING EXISTING METHODS:

In this section, we revisit several classic pair-based DML loss functions: contrastive, triplet, binomial deviance and lifted structure losses in the weight assignment scenario. (2005) propose Siamese network, which encourages positive pairs to be closer, and negative pairs to be further when their cosine similarity is higher than a fixed threshold. Its loss function formulates as below:

EQUATION

where λ is the threshold. According to Equation ( 4), its weight assignment can be formulated as below:

w i,j = I A ({x i , x j }), (6) where I A is indicator function of a subset A = {{x i , x j }|j ∈ P i } {{x i , x j }|s i,j > λ ∧ j ∈ N i }.

The curves of weight assigned to pairs vs. similarities are shown in Figure (1a ). The weight of any positive pair is 1. The weight of a negative pair is 1 if its similarity is higher than λ, otherwise is 0.

From the weight assignment, we find one drawback of contrastive loss that it treats all selected pairs equally, while neglecting their different hardness.

Triplet Loss. Hoffer & Ailon (2015) learn a discriminative model based on a triplet, which consists of an anchor x i , a positive instance x p and negative instance x n :

EQUATION

where λ is the given margin. Weight assignment of triplet loss is:

EQUATION

where Two problems come to light when we rethink triplet approach from our unified view: One is the same with contrastive loss in assigning equal weights to selected pairs without considering their different hardness. Moreover, for triplet loss, whether a positive pair is selected into B only depends on one randomly sampled negative pair, and vice versa. This makes triplet loss tend to miss large amount of informative pairs and to be unstable during the training process.

I B is indicator function of a subset B = {{x i , x p }|s i,n -s i,p + λ > 0} {{x i , x n }|s i,n - s i,p + λ > 0}.

Lifted Structure Loss. Oh Song et al. (2016) propose lifted structure loss whose objective is to exploit all the pairwise distances in a mini-batch, but the original version of lifted structure approach has not utilized all the negative pairs of one anchor. Hermans* et al. ( 2017) put forward a generalized form of lifted structure loss which leverages all anchor-positive and anchor-negative pairs as following:

L lif ted := 1 m m i=1 log k∈Pi exp (-s i,k ) -log k∈Ni exp (λ -s i,k ) + (9)

When the hinge function w.r.t. x i in above equation returns nonzero value, we get its weight w i,j assignment by calculating the gradient of L lif ted w.r.t. s i,j and s i,k :

EQUATION

When the hinge function returns zero value, the weights assigned to all involved pairs are zeros.

Its weight distribution is illustrated in Figure (1c ). From Equation (11) and Figure (1c), we find that lifted structure has important improvement compared to contrastive and triplet approaches: It assigns pairs with different weight coefficients based on their similarities, while contrastive and triplet methods only think of pairs or triplets at instance level and assign pairs with 0 or 1 weight values. However, lifted structure is still confronted with two drawbacks from our weight assignment perspective: (1) It evaluates the overall state of all pairs with the same anchor to determine whether assigning all these pairs with zero or nonzero weights. In consequence, it ignores some informative pairs or assigns nonzero weights to numerous uninformative pairs. (2) In Equation ( 11), the weight of one pair only depends on its relative hardness (s i,j -s i,k ) compared with other pairs, while neglects its absolute similarity.

Binomial Deviance Loss. Yi et al. (2014) propose the binomial deviance approach, whose loss function is:

EQUATION

)

where γ is a hyper-parameter which serves as a soft threshold similar as λ in contrastive loss, α and β represent the sensitivities of positive and negative pairs to the threshold γ, respectively.

Its weight assignment strategy follows:

EQUATION

)

EQUATION

We display its weight distribution in Figure (1d ). Binomial deviance approach utilizes the sigmoid function to replace the unit step function in contrastive loss, thus provides smoother weights. The main drawback of binomial deviance is similar with lifted structure: It assigns all pairs with nonzero weights, especially the numerous uninformative negative pairs, which brings side effect to model training. Another drawback is that it solely takes the pair's absolute similarity (s i,j -γ) into consideration, while ignoring the relative similarity compared with other pairs, which is contrary to lifted structure loss.

To summarize, contrastive and triplet approaches are impeded by assigning all hard pairs with the same weight without being aware of their different hardness. Lifted structure and binomial deviance approaches mitigate the problem by assigning pairs with weights dynamically based on pairwise similarities. However, they suffers from serious side effects e.g., numerous easy pairs, only considering the absolute or relative similarities of pairs.

5. WEIGHT ASSIGNMENT DESIGN:

Theorem 3.1 bridges all the pair-based DML methods with weight assignment strategies of pairs, which instructs that designing a powerful DML approach is equivalent to seeking a suitable weight assignment. From the review of existing DML methods, we argue that an effective weight assignment strategy should have two desirable properties: (1) Not involving uninformative pairs in the learning process.

(2) Assigning weight coefficients to pairs base on their both absolute and relative similarities. In the following, we elaborate how to design such a DML method.

5.1. VALID TRIPLET BASED HARD MINING:

As the model converges, most pairs, especially negative pairs, have been well addressed and cannot further improve the model. In fact, these easy pairs without any useful information may bring side effect to the training process. That is to say, only samples that can provide useful information should be involved in the training. Then, it comes the problem mentioned frequently in recent papers: hard mining, which is to exploit informative samples to promote the learning of an effective network. Here we propose our hard mining approach that takes the local distribution of all the pairs of one anchor into consideration. First, for every sample x i as the anchor, and the hardest positive sample of x i is defined as x p * := arg min x k :k∈Pi s i,k , similarly, the hardest negative sample is x n * := arg max x k :k∈Ni s i,k . Second, we compare each negative sample x j with x p * . It is treated as informative when s i,j > s i,p * -λ, and for any positive pair {x i , x j }, it is considered as informative when s i,j < s i,n * + λ. The sampling process is shown in Figure ( 2). We call it valid triplet based hard mining (VTHM), since only triplets involving these pairs may have nonzero triplet loss. The index set of informative positive (or negative) samples of x i is denoted as P i (or N i ).

Compared with the triplet approach selecting one pair only based on another randomly sampled pair, our VTHM selects positive (negative) pair by comparing it with all the negative (positive) pairs with the same anchor, which is stable and exploits more informative pairs. Compared with the hard mining method in (Harwood et al. (2017) ), VTHM doesn't need off-line computation and can be directly combined with existing pair-based losses to improve their performances. Compared with the distance weighted sampling in Wu et al. (2017) that targets to select a wide range of negative examples w.r.t. similarity, our method focuses on mining pairs with information.

We assign zero weights to these uninformative pairs which don't belong to P i N i . Next, we describe our weight assignment strategy for the informative pairs in P i N i .

5.2. RELATIVE AND ABSOLUTE SIMILARITY BASED WEIGHT ASSIGNMENT (RAW):

Our weight assignment strategy takes advantage of lifted structure and binomial deviance approaches as below:

EQUATION

)

EQUATION

where α, β, γ are hype-parameters.

In Equation ( 15), k∈ Pi exp (α (s i,j -s i,k )) captures relative similarity between the positive pair {x i , x j } and other informative positive pairs, and exp (α (s i,j -γ)) utilizes a fixed threshold γ to evaluate its absolute similarity. Analysis is the same for negative pairs. We call it relative and absolute similarity based weight assignment (RAW). Though RAW seems a simple combination of lifted structure and binomial deviance, it is not trivial to derive without our unified view.

To avoid the computation of w i,j for each pair {x i , x j }, we obtain the loss function L RAW that is gradient equivalent to our proposed weight assignment: 2016)) and In-shop Slothes (In-shop) (Liu et al. (2016b) ) . We follow the data split protocol proposed in Oh Song et al. (2016) . For every mini-batch, we randomly choose a certain number of classes, and then randomly sample K instances from each class. We set K = 5 for CUB and Cars196, K = 4 for SOP and In-shop. The margin λ in VTHM is 0.1, and α = 2 , β = 50 and γ = 0.5 in both Equation (13) and Equation (17). Our proposed method is verified on image retrieval task and evaluated by the standard performance metric: Recall@K as Oh Song et al. (2016) .

LRAW = 1 m m i=1    1 α log   1 + k∈ P i exp (-α(s i,k -γ))   + 1 β log   1 + k∈ N i exp (β(s i,k -γ))      (17)

6.1. ABLATION STUDY:

We conduct an ablation study by comparing the following methods: Binomial applies binomial deviance loss to all the pairs in the mini-batch. VTHM gives equal weights to the pairs selected by our VTHM strategy. Binomial and RAW assign weights to all the pairs via binomial deviance and RAW respectively. Binomial+VTHM utilizes the weight assignment of binomial deviance to the selected pairs by our hard mining. RAW+VTHM represents our full method that assigns weights to informative pairs via Equation ( 17) with VTHM. RAW+DW and RAW+SemiHard denote methods that assign weight given by RAW to pairs sampled through distance weighted sampling (Wu et al. ( 2017)) and semi-hard mining (Schroff et al. (2015) ) respectively. For simplicity, only Recall@1 are reported as shown in Table 1 .

Sampling. From this table, VTHM leads to improvement on all datasets for Binomial and RAW. It offers 3.8% improvement on SOP and 4.4% on In-shop for binomial deviance loss. For RAW, it increases the Recall@1 by more than 2% on , while other sampling methods like semi-hard and distance weight sampling do not have such a positive impact. This is because VTHM mines as many informative pairs as possible. Therefore, we conclude that though Binomial and RAW have already assigned easy pairs with small weight values, these samples still do harms to the learning process because of their large number.

Weight Assignment. In Table 1 , we find that Binomial+VTHM outperforms VTHM on all datasets simultaneously through assigning pairs with weight base on their absolute similarity. Moreover, our RAW+VTHM further improves the performance by considering the relative hardness of pairs. For instance, on Cars-196, Binomial+VTHM achieves 6% higher Recall@1 than VTHM, and RAW+VTHM further increases 2%.

:

For simiplicity, we use cosine similarity instead of euclidean distance, since we assume the embedding vector is L2 normalized.

Figures and Tables:

Figure 1: Weight coefficient vs. pairwise cosine similarity. The solid green lines show the weight assigned for positive pairs, the dotted blue for negative pairs.Contrastive Loss.Hadsell et al. (2006);Chopra et al. (2005) propose Siamese network, which encourages positive pairs to be closer, and negative pairs to be further when their cosine similarity is higher than a fixed threshold. Its loss function formulates as below:

The weight curves of triplet loss are exhibited in Figure (1b), where we find only pairs in B are assigned with weight 1.

Figure 2: Valid triplet based hard mining: for any anchor point, every positive pair is compared with the hardest negative pair, and vice versa.

Ablation study on SOP, Only Recall@1 is given. use PyTorch to implement our model. For the network architecture, we use the Inception network with batch normalization(Ioffe & Szegedy (2015)) pretrained on ImageNet. We add an FC layer at the top of the network following the global pooling layer. L 2 normalization is applied to the embedding vectors. All the input images are first resized to 256×256 and then cropped to 227×227. For data augmentation, we used random crop with random horizontal mirroring for training and only one center crop for testing. The embedding dimension is set to 512. We use the Adam optimizer with a fixed 10 -5 learning rate for all experiments. We conduct the experiments on four standard datasets:

Table content: <table><tr><td/><td colspan="4">CUB-200 Cars-196 SOP In-shop</td></tr><tr><td>Binomial</td><td>64.45</td><td>80.78</td><td>73.4</td><td>84.78</td></tr><tr><td>RAW</td><td>65.06</td><td>81.27</td><td>77.0</td><td>88.38</td></tr><tr><td>VTHM</td><td>61.55</td><td>76.61</td><td colspan="2">76.82 88.72</td></tr><tr><td>Binomial+VTHM</td><td>65.34</td><td>81.48</td><td colspan="2">77.22 88.87</td></tr><tr><td>RAW+DW</td><td>65.67</td><td>80.70</td><td colspan="2">77.39 88.79</td></tr><tr><td>RAW + SemiHard</td><td>64.97</td><td>80.48</td><td colspan="2">77.12 88.66</td></tr><tr><td>RAW+VTHM (ours )</td><td>66.85</td><td>83.69</td><td colspan="2">78.18 89.64</td></tr><tr><td>6 EXPERIMENTS</td><td/><td/><td/><td/></tr></table>

Peer review (iclr2019):
 The paper analyses the gradients some deep metric learning (DML) approaches. Most of them optimize over pair-wise or triplet-wise constraints. The main claim of the paper is that, during training, most DML approaches ignore some informative pairs of examples or do not take into account the value of the distance gap between similar and dissimilar pairs. A specific weighting strategy is then proposed to address those problems. The main strength of the paper are the strong experimental results on different transfer learning benchmarks. The proposed approach seems to significantly outperform existing methods thanks to the proposed strategy. However, the theoretical aspect is weak. I have some concerns about the paper. - My first concern is about terminology: I disagree with the claims of the paper that there is any theoretical demonstration in the paper. I do not see the novelty of the gradient equivalence theorem (Theorem 3.1). It was already explained in (Law et al., ICCV 2013) (that is cited in the paper) that pairwise and triplet-wise constraints are just specific formulations of quadruplet-wise constraints. Pair-wise and triplet-wise can then be written in their quadruplet-wise formulation: we then obtain the induced gradient formulation that depends on positive and negative pairs (as formulated in Eq. (4)). The derivation of the proof is very straightforward once we have a formulation that generalizes both triplet-wise and pairwise constraints. Moreover, the gradient equivalence definition (in Definition 3.1) is not applicable to most deep learning optimization frameworks that use momentum-based optimizers (e.g. Adam which is a momentum solver, and SGD which is often optimized with momentum). Indeed, definition 3.1 only considers the value of theta at some given iteration, but not at the previous iterations. However, momentum-based approaches keep a history of the gradients from previous iterations and will then return different gradients. - One of the main claims of the paper against the triplet loss is that the sampling strategy ignores some informative pairs. This is mainly due to the fact that the triplet loss is generally used in the context of very large datasets and large mini-batches (Schroff et al., CVPR 2015) where it is computationally expensive to generate all the possible triplet constraints. Triplet sampling strategies are formulated to ensure fast convergence while avoiding degenerate solutions induced by the chosen triplet sampling strategy. The submitted approach does not deal with very large datasets and then does not need to consider such sampling strategies. Although some sampling strategy is proposed, it is unclear if it would be scalable (i.e. trainable in reasonable time on the same dataset as FaceNet). Moreover, as mentioned in Section 5.1, the proposed strategy is a straightforward extension of lifted structure. - Why did you only report the recall@K evaluation when many methods report the normalized mutual information (NMI)? (Hyun Oh Song et al., CVPR 2017) Could you please include NMI scores? - If the problem of the contrastive loss is the fact that the gradient considers all pairs equally, why can it not be adapted to depend on the hardness of the constraint (e.g. by taking the squared of the loss for each pair)? In conclusion, my opinion is borderline but only leans towards acceptance because the experimental results are strong. Nonetheless, the reported results of baselines are often for different network architectures and using different output dimensions. Can the authors try their method with the same architecture and same output dimensionality as baselines?