Improved Deep Metric Learning with Multi-class N-pair Loss Objective
Deep metric learning has gained much popularity in recent years, following the success of deep learning. However, existing frameworks of deep metric learning based on contrastive loss and triplet loss often suffer from slow convergence, partially because they employ only one negative example while not interacting with the other negative classes in each update. In this paper, we propose to address this problem with a new metric learning objective called multi-class N -pair loss. The proposed objective function firstly generalizes triplet loss by allowing joint comparison among more than one negative examples -more specifically, N -1 negative examples -and secondly reduces the computational burden of evaluating deep embedding vectors via an efficient batch construction strategy using only N pairs of examples, instead of (N +1)×N . We demonstrate the superiority of our proposed loss to the triplet loss as well as other competing loss functions for a variety of tasks on several visual recognition benchmark, including fine-grained object recognition and verification, image clustering and retrieval, and face verification and identification.
Update: My review remains the same after rebuttal. The rebuttal did help to clear some questions. I think the paper can be accepted, provided the authors include the comments and points discussed in the revised manuscript.   Summary of the paper: The paper proposed a new multi-class pair/triplet loss for metric learning with CNN. The novelty of their work lies in the proposed loss function and the efficient construction of the mini-batches for it.  Their method improves over the standard triplet loss, which pushes the impostor of  one offending class at a time. In contrast their loss pushes impostors of multiple classes for each update. They claim, that learning while pushing multiple impostor classes leads to a better metric. They verify their claim experimentally and benchmark their methods against relevant baselines. Overall the paper is well written, well-presented and provides clear experimental results supporting their claim.  Advantages: - Novel loss function for metric learning, which works well over standard approaches - Easy to implement and understand - Simple method for efficient mini-batch construction   Disadvantages:  - Method might not be extensible to cases where we only have similar and dissimilar constraints as it needs labels for constructing the tuple in an efficient manner. 
Novelty/Originality: The novelty of the paper is two fold. First, they analyze the widely used triplet loss and its variants. Doing so, they propose a modification for the triplet loss, coined as the tuplet loss. Second, for the proposed tuplet loss, they propose and efficient method for forming the mini-batch of and SGD. This is quite simple and straightforward to implement, and does not come at a high computational cost which come into play when people use strategies like hard negative mining.   There are few things which I would like the authors to respond to: Q1: Strong usage of "Slow Convergence issue"  In line 047, they mention that people have evaluated combining softmax loss with contrastive or triplet loss for overcoming Slow Convergence issue. This is  mentioned in the abstract and other places as well. However,  this is not entirely true. There are other reasons for which this combination  has been tried.  For example, in [24], it was shown that while training the CNN for  face dataset, using both classification and identification (pairwise loss) gave superior performance than using either alone. They showed that using both losses  they could obtain a regularization and hence a better solution, but their goal was not to correct "slow convergence". Also, the statement in conclusion at L427 is too bold stating performance of triplet loss as "unsatisfactory convergence". This is too strong and should be revised, given in their own results the triplet loss performs quite decently in some cases.  Q2: In section 3.2.2 they perform regularization on the embedding vectors to be $\ell_2$ regularized. I was curious, if they tried using cosine similarity directly to avoid this explicit regularization?   Q3: In Table 1, I would like to see the results when negative mining is added for ovo and mc, the same way it was done in Table 2.   Q4: Just to be clear, in section 4.2 when the authors discuss results in Table 2, they mention negative data mining. I am assuming this refers to negative class mining. If that is the case, it should be mentioned as that to avoid confusion given in L222 a clear distinction was made between them. Also, in the methods where no negative class mining is mentioned, how is it replaced? by random classes. This should be made explicit if that is the case?  Q5: In table 2, why were all the methods stopped at 20k iterations? I find it strange that the optimal number of early stopping iterations is the same for all these different loss functions? Can the authors explain which method was chosen to set this 20k iteration? Also, I think this should be revised and the number of iterations should be set by cross-validation for each loss independently.