关系挖掘的非对称度量学习方法的研究及其在深度度量学习中的应用

Xinyi Xu1, Yanhua Yang1, Cheng Deng1∗, Feng Zheng2xyxu.xd@gmail.com, yanhyang@xidian.edu.cn, chdeng.xd@gmail.com, zhengf@sustc.edu.cnand retrieval [57, 49, 51, 50, 22, 10]. Conventional Ma-halanobis metric learning approaches learn a linear trans-formation of the data and measure the similarity based onEuclidean distance, which fail to capture the high-ordercorrelation[15, 42, 47]. Riding on the development of deepneural network [21, 33, 37], deep metric learning (DML)has gained a lot of attention. Guided by a metric loss, DMLprojects data into an embedding space with rich semanticinformation through convolutional neural network. It showspotential capability even in challenging tasks, such as fine-grained classification [8, 41, 55, 25], large-category classi-fication [2, 31, 46], and zero-shot learning [28, 56, 6, 26].140760通过丰富的关系挖掘进行深度非对称度量学习01 西安电子科技大学电子工程学院，中国西安 710071 2 南方科技大学计算机科学与工程系0摘要0学习有效的数据距离度量在各种任务中越来越受欢迎，例如人脸验证、零样本学习和图像检索。一系列的研究采用了困难数据挖掘的方法，致力于搜索一部分重要的数据。然而，基于困难数据挖掘的方法仅依赖于一小部分数据，容易过拟合。这激发我们提出了一种新的框架，名为通过丰富的关系挖掘进行深度非对称度量学习（DAMLRRM），以在满足采样大小的情况下挖掘丰富的关系。DAMLRRM构建了两个不同结构和不等长度的非对称数据流。非对称结构使得这两个数据流能够交错，从而允许在迭代过程中对新的数据对进行信息比较。为了提高泛化能力，我们进一步放宽了类内关系的约束。DAMLRRM不是贪婪地连接所有可能的正样本对，而是在每个类别内构建了一个最小成本生成树，以确保形成一个连通区域。因此，任意正样本对之间至少存在一条直接或间接路径，以建立类内相关性。在包括CUB-200-2011、Cars196和斯坦福在线产品在内的三个基准数据集上进行了大量实验，结果表明DAMLRRM有效地提升了现有深度度量学习方法的性能。01. 引言0度量学习旨在找到数据的适当相似度度量，其主要思想是在嵌入空间中保持相似实例之间的距离较近，不相似实例之间的距离较远。由于其广泛的应用，包括人脸识别[12, 52,45]、聚类[9, 44, 53]和检索[57, 49, 51, 50, 22,10]，这个主题具有重要的实际意义。传统的马氏度量学习方法学习数据的线性变换，并基于欧氏距离来度量相似度，无法捕捉高阶相关性[15, 42,47]。借助深度神经网络的发展[21, 33,37]，深度度量学习（DML）引起了很多关注。在度量损失的指导下，DML通过卷积神经网络将数据投影到具有丰富语义信息的嵌入空间中。它在挑战性任务中显示出潜在的能力，例如细粒度分类[8, 41, 55, 25]、大类别分类[2, 31, 46]和零样本学习[28, 56, 6, 26]。0� 通讯作者。0根据损失类型，DML可以大致分为对比和三元组方法。然而，枚举所有可能的配对或三元组会导致近乎指数级的采样大小，即使对于适度数量的实例来说也是不可行的。一个常见的解决方案是将一部分实例作为训练池进行采样。事实上，当采样的训练池仅覆盖对优化贡献较小的简单实例时，只能得到一个弱嵌入模型。因此，旨在找出混淆实例的困难数据挖掘成为一个重要的课题，并且提出了大量的方法[35, 34,16, 11, 43, 54,14]。这些方法在一定程度上解决了这个问题，但在以下三个方面仍然存在不足。首先，涉及到复杂的数据预处理来选择困难数据，而难度水平随着模型的演化而变化[34]。其次，只利用了一小部分关系。第三，难度水平难以控制。当选择的实例不够困难时，学到的模型就不具有区分性。相反，当选择的实例过于困难时，往往会出现过拟合问题[43]。0在这项工作中，我们提出了一种名为深度不对称度量学习通过丰富关系挖掘（DAMLRRM）的新框架。DAMLRRM首先构建了两个不对称的数据流，它们交织在一起，以便在迭代过程中进行连续的新对比。与传统的单流度量学习方法相比，DAMLRRM可以挖掘更丰富的关系。240770通过构建每个类别的最小连接树而不是考虑一个小批量内的所有正样本对，我们构建了正样本对训练池。因此，任何正样本对之间都存在直接或间接的路径，从而确保它们之间的相关性被桥接。这个灵感来自于在流形上的排名[58]，它逐一将相关性传播到它们附近的邻居。连接图损失可以帮助保持数据的固有分布并实现良好的泛化能力。在实验中，我们在CUB200-2011 [39]、Cars196[1]和Stanford在线产品[35]数据集上展示了最先进的聚类和检索任务结果。简而言之，本文的贡献如下：i）我们摒弃了传统的基于硬数据挖掘的技术，提出了一种新颖的基于两个不对称流的深度学习框架用于度量学习，这与只涉及一个流的传统方法不同。ii）我们设计了一种放松正样本对约束的技术，以提高模型的泛化能力，在我们的实证研究中得到了验证。iii）与包括提升方法[35]和N-pair[34]在内的同行方法相比，我们提出的模型在使用少于百分之十的采样大小时获得更好的准确性。02. 相关工作0Siamese网络[5]是对比度DML的开创性工作。它首先使用双子网络将两个签名实例非线性映射到特征空间中。然后，使用对比损失来优化映射过程。对比损失最小化正样本对之间的距离，并在负样本对之间的距离小于预定边界时扩大距离。基于Siamese网络，提出了一系列方法来解决降维和人脸验证任务[13, 7, 36,38]。尽管取得了很大的进展，但对比度度量学习方法存在一个缺点，即它们关注绝对距离，而对于大多数任务来说，相对距离更为重要[30, 31, 35]。Tripletloss是对比损失的一种演化形式，用于解决这个问题。它在三元组训练池上训练模型，其中每个三元组由一个锚点、一个正样本和一个负样本组成。锚点和正样本具有相同的标签，而锚点和负样本具有不同的标签。训练过程鼓励网络找到一个嵌入，其中正样本对之间的距离小于负样本对之间的距离，并且有一定的间隔。0然而，对比损失和三元组损失往往在实践中很难优化，主要受到训练池选择方式的影响。混淆实例对于优化来说非常重要，应该给予大量关注。FaceNet[31]针对在线困难数据生成，使用了几千个实例的大批量，并且仅在一个小批量内计算argmin和argmax。然而，批量大小为1800，在实现时是一个很大的内存障碍。为了充分利用相对关系，Song等人[35]允许从左右数据对中挖掘负样本，而不仅仅根据锚点定义负样本。Chen等人[16]引入了一种位置相关的深度度量单元，可以用来选择困难实例，以在线和稳健的方式指导深度嵌入学习。Sohn等人[34]指出，基于少数负样本的损失函数容易陷入局部最优。因此，他们提出了一个(N+1)-tuplet损失，该损失优化从N-1个负样本中识别一个正样本，取得了一些性能改进。最近，Duan等人[11]提出了一种深度对抗度量学习框架，用于从观察到的负样本中生成合成的困难负样本。0硬数据挖掘背后的基本理念是，对于一对正实例，通过离线或在线选择一个显著的负样本，并在它们违反约束时对相对距离进行惩罚。然而，离线和在线的硬数据挖掘策略都存在缺陷。离线方法在训练之前选择困难实例，这些实例不会随着更新的模型而更新。这是不合理的，因为困难关系是由不同的模型动态决定的。在线方法在训练过程中在一个小批次中决定困难的负样本，这使得在一个非常小的实例子集中进行比较。困难的质量无法保证。这两种形式的一个共同缺点是由于对成对或三元组的低利用率，学到的度量是不充分的。因此，在本文中，我们努力在控制采样大小的同时利用更多的成对样本。0图是用于建模对象之间的成对关系的数学结构[4,3]。图在上下文中由顶点和由边连接的点组成。图知识在许多应用中用于表达相关网络，例如图像检索[32]，语言处理[17]和显著性检测[48]。最近，Iscen等人[18]利用无向图在没有标签的情况下挖掘有效的训练池，验证了图在建立相关性方面的优先级。在本文中，我们利用图来放松正对之间的约束，这对于提高泛化能力非常有帮助。Bx = {x11, · · · , xk1; x22, · · · , xk2; · · · ; x1m, · · · , xkm}Bs = {s1, s2, · · · , sb/2}B = {Bx, Bs}.(1)̸B1 = {Bx1; Bs1},Bl = {Bx1; Bsl }Bx1 ̸= Bxl ,Bs1 = Bsl .(2)340780CNN + 一个全连接层0随机打乱的样本0图损失0打乱的损失 ��  每类样本0�� 1 10�� 1 20�� 1 ��0�� 2 10�� 2 20�� 2 ��0�� �� 10�� �� 20�� �� ��0��类别/批次0图1.我们提出的非对称深度度量学习框架。使用两个不同结构的批次对两个流网络进行训练，其中上面的批次是整齐排列的，下面的批次是打乱的。通过两个共享网络映射，获得实例的特征嵌入，并通过两个损失函数进行监督学习。03. 提出的方法0图1展示了我们提出的方法DAMLRRM的框架。我们采用两个权重共享的网络来映射两个非对称的数据批次，其中上面的流接受整齐排列的数据（整齐流），下面的流以打乱的数据作为输入（打乱流）。我们的模型为整齐流中的每个类别构建了一个最小成本生成树，建立了一个稳定的类内流形。此外，通过采用打乱流为整齐流提供各种负实例，实现了强大的区分能力。我们在下面的子节中详细介绍我们提出的模型。03.1. 准备工作0设 X = { x i | i  = 1 ,  2 ,  ∙ ∙ ∙  , N x } 和 S = { s i | i  = 1 ,  2,  ∙ ∙ ∙  , N s } 是两个流的训练池，其中 N x 和 N s 分别是 X和 S中实例的数量。DML的目标是学习一个非线性变换到语义嵌入空间 f  :  R � d  →  R d ，它是一个具有参数  θ的可微深度网络。我们通过在嵌入空间中计算欧氏距离 D ij=  ∥ f ( x i )  −  f ( x j ) ∥ 2 来衡量 ( x i ,  x j )的相似性。此外，我们构建每个类别作为一个无向加权子图G  = ( V ,  E ,  D ) ，其中 V 中的每个节点对应一个样本，E中的边连接正对，D 存储边的权重。03.2. 使用非对称结构进行丰富的关系挖掘0为了获得丰富的关系，我们提出了一种度量学习的非对称框架。非对称性体现在0结构和数量。在结构上，分别为两个流构建两个完全不同的结构化数据批次。上游流的数据批次是整洁的，而另一个是随机洗牌的。这可以在图1的左侧清楚地显示，并且公式为0整洁的数据批次  B x 由 m 个类别组成，每个类别有 k个实例。而洗牌的数据批次  B s 包含 b/ 2个随机实例，其中 b/ 2 =  m  �  k。因此，对于每次迭代，训练批次 B由两部分组成：一个整洁的数据批次  B x和一个洗牌的数据批次  B s。在数量上，两个流的训练池的大小不相等，即  N x � =  Ns。数量的非对称性使得同一数据流中的相同实例在不同的迭代次数中与另一个数据流中的不同实例进行比较。例如，图2中的  B s 1 ，  B s l 和  B s n包含不同迭代次数的相同实例，而它们与流1中的不同实例进行比较。具体来说，  B 1  和  B l  由以下组成0通过这样做，我们的模型可以利用丰富的关系，同时不增加采样大小。非对称度量学习的直观动机来自两个方面：1）整洁的流主要关注通过最小成本生成树建立一致的类内关系，这限制了正样本。������������1������������������������������������������������������������������������������������������������1������������������������������������������������������������������������������������PP = {(x1, x2); (x2, x3); (x2, x4); (x4, x5); (x4, x6)},(3)where PP is the connected positive pairs pool. Notably,this minimum-cost spanning tree is quite different fromsimply choosing the nearest positive pairs which does notensure a connected field within a category.The objective function is defined based on the built pos-itive pairs pool. Predefine a boundary α and a margin β,the optimize goal is limiting the distance of positive pairssmaller than α − β. For the negative instances, we hopethey will not break into the tree, so the distance is forced tobe bigger than α + β. The graph loss function is defined asLg = 1Pg �i,j∈P P[Di,j−α+β]2+ +�i,j∈NP[−Di,j+α+β]2+ ,(4)440790流10流20流1的训练池 流2的训练池0�� 1 �� , �� �� ��  和  �� ����  包含相同的实例0迭代 迭代  1 迭代  �� 迭代  ��0图2. 交错的批次。两个数据流的长度各不相同，使得流2中包含的相同实例与流1中的不同实例进行交互。在相同的采样大小下，这样的交错批次可以挖掘更多的配对相关性。0形成一个统一的流形。然而，这样的类内关系不够稳定，因为它观察到的负实例有限；2）洗牌流为整洁流产生多样且大量的负实例，旨在建立有区分度的类间关系。值得注意的是，这两个批次不会导致额外的内存或计算成本，因为我们只是分割了之前方法使用的批次大小的一半，并且两个网络共享所有权重。03.3. 基于连接图的损失函数0以往的方法在一个小批次中约束所有可能的正对，这太严格了，会导致过拟合问题。受到数据流形上的排序方法的启发[58]，通过逐个将源点的相关性传播到其最近的邻居，我们放松了正对的约束。我们不是连接所有的正对，而是为每个类别建立一个最小成本生成树。通过这样做，获得了一个类内的连接域，确保任意正对之间存在直接或间接的路径，并且对于不太相似的对不施加太大的压力。换句话说，原始视觉空间中分布较远的实例允许间接关联，并且它们之间的距离大于阈值。核心思想是在最大程度上保留数据的内在分布，同时确保语义一致性。我们使用了一个简单的最小生成树算法，名为  prim  [27]，来构建连接图。  prim算法是一种贪心算法，它为加权无向图找到一个最小生成树。它找到一组边来形成一棵包含每个顶点的树，其中树中所有边的总权重最小。  prim  算法的步骤总结如下：0(1) 构建一个加权图 G = ( V ,  E ,  D ) ，其中 D 是由欧几里得距离测量的。设置 Vvisited = {�} 和 V unvisited = V 。用一个任意的顶点 V start ∈ V初始化一棵树。将 V start 添加到 V visited 中，并从 V unvisited 中删除。0然后重复步骤2，直到所有顶点都包含在树中（ Vvisited = V ）。0(2) 通过一条边扩展树：选择一条最小权重的边 E minimum∈ E ，它连接 V visited 和 V unvisited，然后将其附加到树上。将最小权重连接的顶点添加到 Vvisited 中，并从 V unvisited 中删除。0图3给出了一个具体的例子。假设起始顶点是点1（图3(a)），那么下一个顶点将通过选择连接到点1的最小权重到达点2（图3(b)）。然后找出连接到点1和点2的所有边的最小权重，从而到达点4。重复此过程，直到所有顶点都包含在树中，如图3(c)所示。对于图3中的情况，46532113.5344521.51.5546532113.5344521.51.5546532113.531.51.5Ls= 1Ps �i,j∈NN[Di,j−α+β]2+ +�i,j∈NP[−Di,j+α+β]2+ ,L = Lg + Ls,(6)540800(a) 无向加权图0(b) 无向加权图0(c) 最小代价生成树0图3.最小代价生成树的构建过程。通过最小的权重成本将相关性从一个实例桥接到另一个实例，直到该类别内的所有实例直接或间接地连接起来。0其中 P g 是违反约束条件的对数对的数量，NP是负对数对池。对于洗牌流中的实例，期望正实例加入到prim树中，我们强制它连接到树中最近的点。负实例被约束为远离树。因此，洗牌损失 L s 定义为0(5) 其中 P s 是违反约束条件的对数对的数量，NN是两个流之间的最近的正对数对池。将这两个损失函数结合起来，最终的目标函数可以表示为：0在组合这两个损失函数时，我们不使用任何平衡参数，因为它们背后的动机是相同的。我们设计目标函数的原则是尽可能尊重数据分布，只要语义一致性得到满足。通过连接两个流的最近正对数对并在一个整洁的流中建立 prim树，我们放松了约束并实现了泛化能力。04. 实验0在本节中，我们评估了我们提出的DAMLRRM在三个公共基准数据集上对图像检索和聚类任务的有效性。实验中使用了Caffe包[20]。首先将所有图像调整为256×256。对于数据增强，训练实例进行标准的随机裁剪和水平镜像，测试时进行单个中心裁剪。所有嵌入向量的嵌入大小设置为 d = 512[40, 11]。使用在ImageNetILSVRC数据集[29]上预训练的GoogLeNet[37]进行初始化，并添加一个随机初始化的全连接层。基础0学习率设置为10的-4次方，并且对于新添加的全连接层，学习率设置为原来的10倍。我们使用SGD进行训练，每个流程进行40k次训练迭代，每个迭代的mini-batch大小为60。04.1. 基准数据集0我们在CUB-200-2011 [39]、Cars196 [1]和StanfordOnline Products[35]上进行实验。对于所有数据集，我们遵循传统的训练和测试协议[35]：CUB-200-2011[39]数据集包含200种鸟类，共有11,788个实例，其中前100种鸟类（5,864张图像）用于训练，其余100种鸟类（5,924张图像）用于测试。Cars196[1]数据集由196个类别的16,185张汽车图像组成。我们使用前98个类别（8,054张图像）进行训练，其余98个类别（8,131张图像）进行测试。Stanford Online Products[35]数据集总共包含22,634个类别和120,053个产品图像，其中前11,318个类别（59,551张图像）用于训练，剩余的11,316个类别（60,502张图像）用于测试。在构建整洁流中的树时，我们对CUB-200-2011和Cars196设置k =5，对Stanford Online Products设置k =3，因为每个产品只有大约5.3张图像。04.2. 基线方法0为了验证我们提出的方法的优越性，我们与八种基线深度度量学习算法进行比较，它们分别是：1）DDML[23]；2）对比嵌入损失（Contrastive）[13]；3）三元组嵌入损失（Triplet）[42]；4）带有N-pair采样的三元组损失（Triplet+N-pair）；5）Lifted[35]；6）N-pair损失（N-pair）[34]；7）角度损失（Angular）[40]；8）对抗度量损失（AML）[11]。由于本工作的核心问题是在小样本采样下进行充分关系挖掘，我们没有采用任何复杂的硬负样本挖掘策略来复杂化比较。1R@8DDML[23]47.313.131.241.654.767.1Contrastive[13]47.212.527.236.349.862.1Triplet[42]49.815.035.947.759.170.0Triplet+N-pair54.120.042.854.966.277.6Lifted[35]56.422.643.656.668.679.6N-pair[34]60.228.251.964.374.983.2Angular[40]61.030.253.665.075.383.7AML[11]61.329.552.765.475.584.3OURS61.731.255.166.576.885.31R@8DDML[23]41.710.932.743.956.568.8contrastive[13]42.310.527.638.351.063.9Triplet[42]52.917.945.157.469.779.2Triplet+N-pair54.319.646.359.971.481.3Lifted[35]55.125.148.361.171.881.1N-pair[34]62.731.868.978.985.890.9Angular[40]62.431.871.380.787.091.8AML[11]63.131.972.582.188.592.9OURS64.233.573.582.689.193.51@100DDML[23]83.410.742.157.873.7Contrastive[13]82.410.137.553.971.0Triplet[42]86.320.253.972.185.7Triplet+N-pair86.421.058.176.089.1Lifted[35]87.225.362.680.991.2N-pair [34]87.927.166.482.992.1Angular[40]87.826.567.983.292.2AML[11]89.131.766.382.892.5OURS88.230.569.785.293.2R@1R@2R@4R@8α = 2652.965.476.185.1α = 2853.165.376.184.7α = 3055.166.576.885.3α = 3254.566.076.485.3R@1R@2R@4R@8β = 0.151.964.575.884.9β = 0.352.764.975.684.4β = 0.555.166.576.885.3β = 0.753.965.776.285.3β = 1.053.266.376.885.4640810表1. 在CUB 200 2011 [39]数据集上进行聚类和检索的比较0方法 聚类(%) Recall@a(%)0表2. 在Cars196 [1]数据集上进行聚类和检索的比较0方法 聚类(%) Recall@a(%)0表3. 在Stanford Online Products[35]数据集上进行聚类和检索的比较0方法 聚类(%) Recall@a(%)0然而，我们的方法可以轻松与任何硬负样本挖掘方法相结合。04.3. 评估指标0根据[35,34]中使用的标准协议，我们计算检索任务的Recall@a指标[19]。具体来说，对于每个查询图像，将基于欧氏距离返回前a个最近的图像，如果返回的a个图像中至少有一张正样本图像，则召回分数为1，否则为0。对于聚类评估，我们采用k-means算法对测试实例进行聚类，并以标准的F1和NMI指标报告质量。详细公式请参考[35]。0表4. CUB-200-2011 [39]数据集上不同边界  α  的比较0变化的α0召回率@a(%)0表5. CUB-200-2011 [39]数据集上不同间隔  β  的比较0变化的β0召回率@a(%)04.4. 结果分析0检索和聚类。表1、2和3分别报告了CUB-200-2011、Cars196和Stanford OnlineProducts的聚类和检索结果。我们用红色标记最佳结果，用蓝色标记第二佳结果。对比传统的对比或三元组与Lifted或N-pair的结果表明，硬数据挖掘确实有助于提升性能。N-pair可以与许多度量学习方法合作，并主要通过其批次构建的改进来实现改进。在所有基线方法中，我们提出的方法DAMLRRM在大多数情况下都达到了最先进的性能。值得一提的是，DAMLRRM不需要复杂的离线数据预处理和来自硬数据挖掘的释放。图4和5展示了CUB-200-2011和Cars196的可视化结果，其中使用降维算法t-SNE[24]实现。我们放大了四个区域，以突出几个代表性类别，边界框的不同颜色对应于不同的类别。其中两个放大区域用于展示类内紧凑特征嵌入，其余两个用于说明不同类别之间的区分度。尽管姿态和外观变化很大，我们的方法有效地生成了一个保持语义相似性的显著特征映射。图6展示了Stanford OnlineProducts的一些查询和前5个排名图像的实例。尽管视点、配置和光照发生了巨大变化，我们的方法可以成功地从同一类中检索实例。消融研究：边界  α  和间隔  β的影响。我们的方法涉及两个超参数，分别是边界  α和间隔  β。表4和5研究了CUB-200-2011数据集上不同参数对检索任务的影响。我们将  β  设置为 0 . 5R@1R@2R@4R@8@8R@16740820图4. 在CUB-200-2011数据集上使用t-SNE计算的我们方法的特征嵌入可视化结果。0图5. 在Cars196数据集上使用t-SNE计算的我们方法的特征嵌入可视化结果。0表6. CUB-200-2011[39]数据集上单流数据批次构建和非对称数据批次构建的比较0方法 # 采样大小0召回率@a(%)0Lifted[35] 700K 46.9 59.8 71.2 81.5 N-pair[34] 500K 51.063.3 74.3 83.2 我们的 1 36K 52.3 65.5 76.2 85.50当改变  α  的值，并在讨论  β  时将  α  设置为 0 . 5。可以看出，当  α  = 30 ， β  = 0 . 5时获得了最佳性能。此外，DAMLRRM0表7. CUB-200-2011[39]数据集上完整组合正对和prim树连接正对的比较0方法 召回率@a(%)0完整PPs 48.2 61.3 72.8 84.3 90.1 我们的 2 51.263.5 74.6 84.5 91.20在我们的实验中，该方法对这两个参数不敏感，我们将边界设置为 30 ，将间隔设置为 0 . 5。消融研究：非对称批次的效果。为了验证非对称结构的有效性，我们QueryRetrievalQueryRetrievalFigure 6. Examples of successful queries on our Stanford Online Products dataset using our embedding (size 512). Images in the firstcolumn are query images and the rest are five nearest neighbors.remove the graph loss and keep the shuffled loss only, whichis denoted as OURS1. We compare it with conventional onestream data batch construction methods: Lifted and N-pairalgorithms. Table 6 reports the retrieval metrics of CUB-200-2011 and demonstrates the priority of two asymmet-ric stream batches construction. Notably, our method onlysamples about 36K images which are about ten percentageof Lifted and N-pair.Ablation study: effect of graph pairs construction. Toillustrate the difference between two positive training poolsestablished by minimum-cost spanning tree and fully com-bination, we remove the shuffled loss from DAMLRRM andkeep graph loss. We denote them as OURS2 and Full PPsrespectively. Table 7 reports the retrieval result of CUB-200-2011. We can observe that minimum-cost tree basedpositive pairs training pool is significant for improving theperformance, which is mainly because relaxing the con-straint employed on positive pairs and the generalizationability is enhanced.Algorithmic complexity analysis.Compared withLifted[35] and N-pair[34], our proposed method builds aprim tree within each category additionally. The computa-tional complexity of prim tree is: Op = �k−1i=1 i · (k − i),where k is the number of instances in a tree. The compar-ison of training time cost is shown in Table 8, we believethat the additional offline training time is worthy given thesignificantly improved accuracy. For testing, all instancesare mapped by one stream model, and the time cost is thesame.5. ConclusionIn this paper, we propose a novel asymmetric loss fordeep metric learning, which targets at mining the rich rela-tionship and enhance generalization ability at the same time.Table 8. Comparison of training time on CUB 200 2011[39]dataset.MethodLifted[35]N-pair[34]OURSIterations/Sec2.22.20.84Training Time5.1 h5.1 h13.2 hTo min the rich relationship, we construct two structuredand quantified asymmetric data streams, which interlace toeach other during iterations. Such an asymmetric structureenables continuous newly combined pairs to be comparedwhen optimizing the model, and hence a rich relationship ismined under a small amount of sampling size. To enhanceits generalization ability, we relax the constraint on posi-tive pairs. Instead of connecting all possible positive pairs,we build a minimum-cost spanning tree within one cate-gory to ensure the form of connected field. Minimum-costspanning tree based sampling algorithm obeys the inherentdistribution of data, where not all positive instances are as-sociated directly. Our proposed model releases from harddata mining and achieves higher accuracy while even at thecost of fewer than ten percents sampling images comparedwith the peer methods including the lifted method [35] andN-pair [34].6. AcknowledgmentOur work was also supported by the National NaturalScience Foundation of China under Grant 61572388 and61703327, Key R&D Program-The Key Industry Innova-tion Chain of Shaanxi under Grant 2017ZDCXL-GY-05-04-02, 2017ZDCXL-GY-05-02, and 201