We propose a method that substantially improves the efficiency of deep
distance metric learning based on the optimization of the triplet loss
function. One epoch of such training process based on a naive optimization of
the triplet loss function has a run-time complexity O(N^3), where N is the
number of training samples. Such optimization scales poorly, and the most
common approach proposed to address this high complexity issue is based on
sub-sampling the set of triplets needed for the training process. Another
approach explored in the field relies on an ad-hoc linearization (in terms of
N) of the triplet loss that introduces class centroids, which must be optimized
using the whole training set for each mini-batch - this means that a naive
implementation of this approach has run-time complexity O(N^2). This complexity
issue is usually mitigated with poor, but computationally cheap, approximate
centroid optimization methods. In this paper, we first propose a solid theory
on the linearization of the triplet loss with the use of class centroids, where
the main conclusion is that our new linear loss represents a tight upper-bound
to the triplet loss. Furthermore, based on the theory above, we propose a
training algorithm that no longer requires the centroid optimization step,
which means that our approach is the first in the field with a guaranteed
linear run-time complexity. We show that the training of deep distance metric
learning methods using the proposed upper-bound is substantially faster than
triplet-based methods, while producing competitive retrieval accuracy results
on benchmark datasets (CUB-200-2011 and CAR196).

本文提出了一种新的线性损失函数来优化深度距离度量学习中的三元组损失函数，无需使用类别中心点最优化步骤，并有了实际运行时间复杂度为线性的算法。该方法在基准数据集上达到了竞争性的检索准确性结果。

理论上完整的三元组损失上界，以提高深度距离度量学习的效率

A Theoretically Sound Upper Bound on the Triplet Loss for Improving the  Efficiency of Deep Distance Metric Learning

Deep distance metric learning (DDML), which is proposed to learn image
similarity metrics in an end-to-end manner based on the convolution neural
network, has achieved encouraging results in many computer vision
tasks.$L2$-normalization in the embedding space has been used to improve the
performance of several DDML methods. However, the commonly used Euclidean
distance is no longer an accurate metric for $L2$-normalized embedding space,
i.e., a hyper-sphere. Another challenge of current DDML methods is that their
loss functions are usually based on rigid data formats, such as the triplet
tuple. Thus, an extra process is needed to prepare data in specific formats. In
addition, their losses are obtained from a limited number of samples, which
leads to a lack of the global view of the embedding space. In this paper, we
replace the Euclidean distance with the cosine similarity to better utilize the
$L2$-normalization, which is able to attenuate the curse of dimensionality.
More specifically, a novel loss function based on the von Mises-Fisher
distribution is proposed to learn a compact hyper-spherical embedding space.
Moreover, a new efficient learning algorithm is developed to better capture the
global structure of the embedding space. Experiments for both classification
and retrieval tasks on several standard datasets show that our method achieves
state-of-the-art performance with a simpler training procedure. Furthermore, we
demonstrate that, even with a small number of convolutional layers, our model
can still obtain significantly better classification performance than the
widely used softmax loss.

本文提出了一种基于余弦相似度的 DDML 方法，以更好地利用 L2 归一化，并提出了一种基于 von Mises-Fisher 分布的新型损失函数来学习子空间结构，加上一种新的高效学习算法可以更好地捕捉嵌入空间的整体结构，并在几个标准数据集上进行分类和检索实验，证明我们的方法具有良好的性能和较简单的训练过程。