type
status
date
slug
summary
tags
category
icon
password
🤔 摘要
度量学习需要在训练过程中识别远距离相似对和近距离不相似对，但使用未标记数据很难实现，因为如果一对数据接近，通常会假定它们相似。本文提出了一种新的度量学习方法，通过在关联矩阵中删除连接数据对的边后，通过标签传播（LP）识别硬负样本对的方式来解决此问题。这样，即使负样本对相邻，也可以确定其不相似，我们能够利用这些信息显著提高LP识别远距离正样本对和近距离负样本对的能力。这导致半监督度量学习性能显著提高，具体表现为在基于内容的信息检索（CBIR）应用程序中的召回率、精度和归一化互信息（NMI）性能指标。
📝1. 引言
随着普及的相机拥有率、广泛的互联网连接以及广泛的软件应用程序，图像数据不断增加。设计高效的CBIR系统在管理信息内容方面至关重要。传统的图像检索系统使用文本注释，但这种方法需要手动劳动，可能不划算。另一方面，CBIR从图像查询中检索相关内容，减少了对人工注释的需求。度量学习通过学习将相似的数据映射到比不相似的数据更近的转换，使得聚类数据[37]和通过接近查询来列出类似数据更容易。因此，度量学习算法是大多数最先进的CBIR设计[23]的基石。由于CBIR系统中处理的数据量非常大，因此有兴趣利用大量现成的未标记数据来改进度量学习训练过程。最近的进展强调了在训练可推广表示中保留类内方差的重要性[27]，特别是因为在区分训练标签之间没有影响的表示中所包含的信息可能在区分看不见的测试类之间很重要。由于接近的正样本对产生的损失很小，因此需要识别远距离的正样本对进行训练。[43]使用来自[9]的方法沿流形传播标签，以此来识别这些点，假定最近邻对但不是互相最近邻的数据对是接近的不相似对。然而，这种方法不使用标签信息，可能不能准确地识别硬负样本[3,17,39,40]，即那些接近但标签不同的数据对。使用错误地标识的边的标签传播（LP）会导致训练的模型不准确。本文提出了一种在半监督设置中识别硬负样本对的新方法。具体而言，给定每个类的少量标记点和大量未标记数据，我们建议在亲和力矩阵中删除链接数据对的边时，将通过标签传播获得不同标签的数据对识别为硬负样本对。我们可以快速高效地在此假设下获得边的不相似性权重，而无需重复使用标签传播计算这些权重。我们在一种新的混合标签传播算法中使用这个负边信息，该算法能够利用正负边信息。具体而言，该方法鼓励由正边链接的数据具有相同的伪标签，由负边链接的数据具有不同的伪标签。像标签传播一样，我们的混合标签传播优化问题可以用共轭梯度（CG）解决，使其能够扩展到大型数据集。 由于我们获得的伪标签捕捉远距离正样本对和接近负样本对的信息，它们在半监督度量学习中产生了显着的改进。我们在召回率、精确度和归一化互信息（NMI）性能指标下展示了这一点。这表明我们的方法能够更有效地排名与查询相关的数据库，并在列表的前面返回相关文章。
🤗2 相关工作
2.1 半监督度量学习
考虑一个训练集，由一组个标记示例组成，其中对应的标签为，以及一组个未标记示例，带有不可见的标签。其中，one-hot标签矩阵定义如下：
许多半监督度量学习算法[2,28]采用三元组损失：
其中是一个间距参数，是将样本映射到嵌入中的函数。然而，计算数据库中所有三元组的损失是棘手的，难以抽取引起损失的三元组[35]。此外，三元组损失鼓励相似点尽可能接近，鼓励相同类别的数据折叠成一个点。这会降低数据之间关键的差异性，而差异性对于在零样本设置中保持相似性嵌入至关重要。
代理[23]可以用于解决这种情况，具体是通过为每个类分配一个单个锚点作为代表性代理来实现。这也可以降低计算复杂度，因为每个数据点只需要与少量的代理进行比较。此外，由于代理仅强制执行数据点比其他代理更接近其预测类别的代理的要求，因此不会过度减少内部类方差。这允许嵌入保留关键差异，这些差异可以用于区分在训练期间看不到的类别。近似度常用于识别相似对[28，30]，但靠近的对产生的损失很小，难以可靠地识别远距离的相似对。该论文[43]建议构建一个图，使互相最近邻的数据对连接成边，并沿它们所在的流形传播给定的标签。通过这样做，他们希望识别远离代理的相似数据，同时还识别可能接近代理但与代理不在同一流形上的不相似点。实际上，该论文使用假设[9]：最近邻对但不是互相最近邻的数据对是负对。然而，此假设未利用提供的标签，我们展示出通过在关联矩阵中删除连接数据对的边缘后通过标签传播（LP）识别通过获得不同标签的数据对来确定硬负样本对，以提高远距离正对和接近负对的识别能力。我们的新型混合标签传播方法中使用这些负边缘信息，可以显著提高半监督度量学习的CBIR性能。
2.2 标签传播
标签传播旨在训练一个分类函数，使得i) 通过边连接的顶点受到鼓励具有相同的标签，ii) 带标签节点上的原始标签在中得到保留。为此，标签传播[42]利用以下形式的目标函数：
其中，是平滑项，有助于相关的点具有相同的标签；是标注节点的损失函数，惩罚输出标签与实际标签的差异；而是正的超参数，平衡两个项之间的折衷关系。
平滑项通常是以下形式：
其中，L是图拉普拉斯算子,
是对称的、非负的关联矩阵，1是每个元素都等于1的向量。 标签损失函数通常是以下形式：
而总体损失函数可以写作：
其中，，并且表示类别的传播标签。
对进行微分，并将导数设置为零，我们得到最小化的:
由于对于任意的，是正定的，因此可以通过共轭梯度法从线性系统中高效地获取
伪标签通常被分配为[42]：
2.3 难负样本挖掘
通常使用k近邻构建亲和性矩阵。直接在这些图上执行LP可能会导致数据彼此紧密的情况下被分配相同的伪标签。识别硬负样本对可以改善LP中标签的传播，从而使其能够更有效地将正确的伪标签分配给远离的正对和紧密的负对，并进而产生更好的半监督度量学习性能。
硬负样本不能直接使用LP类别预测进行识别。这是因为LP假定通过其平滑项，紧密的对具有相同的标签——LP断言每个“难”样本都是“正”样本。我们通过比较两个点的传播标签来克服这个限制，如果在LP亲和矩阵中省略了它们之间的边缘，则允许移除这个边，从而使传播的标签可以属于不同的类别，并且允许识别硬负样本。
利用负样本对于许多度量学习方法至关重要[14，24，29]，并且这些作品中的采样策略已经得到了广泛研究。然而，这些方法具有完整的标签信息。在半监督设置中，很难找到硬负样本，因为较近的对更可能是相似的。近年来，人们对利用硬负样本进行无监督对比学习产生了兴趣[1，12，31]。这些方法通常会将模型已经认为不相似的点识别为负样本。相比之下，我们的方法能够识别模型认为相似的负对，从而对模型产生显着的影响。
论文[9]建议将最近邻对但不是互为最近邻的点识别为负样本。然而，该方法并未利用标签信息，我们表明我们的方法能够显著优于[9]。
2.4 混合标签传播
将负边信息纳入LP并不容易。据我们所知，有五篇著名的混合LP论文[4、5、33、41、44]。其中[44]利用负标签信息而非负边信息，[33]在二元分类任务上执行混合LP，不能直接扩展到多类分类。
另外两种方法的复杂度很高，限制了它们在非常小的数据集中的实用性。[4]中提出的二次规划有大量的不等式约束，在使用内点法[38]求解时需要 的时间复杂度。同样，[5]的时间复杂度为 ，因为该论文建议将边缘信息传播到其他边缘上。
另一方面，正如我们在第3.2节中讨论的那样，LPDR [41]可能会鼓励错误的标签分配[4]。在同一节中，我们制定了一种可扩展的 LP 算法，可以有效利用我们生成的不相似信息。
3 方法
3.1 获取困难样本权重
我们使用具有参数的神经网络从每个输入中提取 规范化特征 ：
用欧几里得距离度量表示的前k个最近邻居，我们构造一个稀疏的亲和力矩阵，其元素为：
利用 faiss 库[11]，我们可以高效地构建这个矩阵，对于大的，复杂度为 O(log2N)。设置 后，我们执行一个稍微改进版本的 LP，在（10）中，被一个对角线为 矩阵 替换，其中：
实际上，我们将原始 LP 中未标记的数据点的 正则化项移除了。通过这个改变，未标记数据上的 LP 目标函数减少到仅有光滑项（6）。对 求导并令其等于零，我们得到：
因此，未标记的 是它的邻居标签的加权平均。我们可以计算 ，即所有 的不包括邻居的邻居的加权平均，如图1所示：
由于从 LP 中获取的标签可以被证明是其一阶邻居的加权平均，而 是第一阶邻居的加权平均，不包括 ，因此我们可以将 视为一个近似，即如果删除边 ，我们从 LP 中获得的传播标签的近似值。
我们估计类别概率为：
其中是一个温度缩放的超参数。
节点 i 和节点 j 不相似的概率可以计算为：
我们定义置信权重为：
其中 是熵函数，我们得到了不相似边缘权重：
如和的一阶邻居确信地属于不同的类别，则会分配高度不相似的边缘权重。
3.2. 提出的混合标签传播算法
给定两个代表相似边缘权重和不相似边缘权重的正矩阵和，我们提出以下优化问题作为我们的混合 LP 方法：
其中
是不相似损失。
LPDR [41] 中使用的不相似性损失函数为:
即使我们的损失函数看起来与 LPDR 的相似，但仍存在重要差异。
考虑两个带有不同标签的点i和j。正确的分配是：对于，有。然而，我们可以看到，LPDR损失函数在这种情况下错误地强制执行了。
另一方面，对于任何，我们的损失函数不会对进行惩罚，如果或等于1，会给出一个小的惩罚，但是如果，则会给出一个指数级的大惩罚，这是不相似损失的主要目的。因此，我们的不相似性目标能够避免对预期结果进行强烈的惩罚，同时有效地强制执行。
我们混合LP公式的整体优化问题可以通过共轭梯度在时间内高效解决，与[4]中制定的二次规划形式相比，后者涉及大量的不等式约束，并具有高时间复杂度。也从未创建过一个密集的矩阵，这使得我们的方法保留了的记忆复杂度，而[5]中创建了一个密集的矩阵。
3.3. 深度半监督度量学习
在每个epoch中，我们使用(22)中的不相似边缘权重在我们的混合LP方法(23)中获得传播标签，进而获得标准化的类别概率,带有置信权重。
生成并维护了一组归一化的代理，其中是嵌入的维度，作为神经网络顶部的最终输出给出。然后，伪标签和置信权重在来自[43]的以下损失函数中被用来更新模型:
其中ϵ和b为超参数。
给定使用faiss构建的初始相似性矩阵，如果使用完全向量化的代码，则我们的空间复杂度是，但是可以通过循环将其缩减为，时间复杂度为。我们的方法在空间和时间复杂度上都是线性的，因此相当可扩展。
4 实验
4.1 数据集
我们主要使用6个图像数据集：FGVC-Aircraft [19]、Cars-196 [15]、CIFAR100 [16]、CUB-200-2011 [34]、Stanford Dogs [13]和Oxford-IIIT Pets [26]。在表3中的准确性比较中，我们还包括了德国交通标志识别基准（交通标志）[7]和vgg flowers [25]的结果。 在所有实验中，对于每个类别，我们都会给出5个数据点的标签。对于超参数，除非另有说明，否则我们在所有实验中使用，学习率和k = 50。 我们使用BN-Inception [8]架构作为基本模型来获取特征。该架构常用于度量学习[43]。对于我们的方法和DSSML，使用AdamW优化器 [18]，权重衰减设置为。
4.2 CBIR实验
对于图2、图3和表1中使用我们的度量学习方法进行的CBIR实验，我们使用与DSSML [43]相同的设置。我们合并数据集的训练、验证和测试集，并使用40%的类别作为训练集，20%作为验证集，剩余40%的类别作为测试集。因此，训练、验证和测试集的类别是不相交的。
我们将结果与半监督算法DSSML [43]和SDEC [30]，全监督算法Proxy-Anchor [14]、SoftTriple [29]和ProxyNCA ++[32]，以及无监督算法DEC [36]进行比较。
所有深度方法都使用预训练的BN-Inception [8]作为基本架构，在批量大小为32的情况下运行20个时期，其中SDEC使用了批量大小为90。在运行这20个时期之前，我们的方法和DSSML进行了5个时期的微调，仅使用提供的标记数据。采用所有竞争方法的默认超参数设置和优化器。选择在验证集上给出最佳P@8（精度为8）的时期作为所有方法的最佳时期。使用维度的嵌入。
我们使用三个评估指标：标准化互信息（Normalized Mutual Information，NMI）、Top K 的召回率（recall at k，R@k）和 Top K 的精确率（precision at k，P@k）[43]。 NMI 用于评估聚类的质量。设 为基于数据真实标签的聚类分配。我们使用嵌入的K-Means聚类得到一个类似的聚类分配，其中qj是样本j所在的聚类数。设测试样本的数量为，则根据[20]计算NMI:
其中我们定义了互信息：
和熵
记为第 i 个样本中第 j 个检索到的物品的类别标签。令：
该指标衡量的是在 Top k 检索结果中，至少有一个结果与查询具有相同的类别标签的平均概率。
另外，
该指标衡量的是 Top k 检索结果中与查询具有相同类别标签的结果占比的平均值。
从图 2 和图 3 可以看出，我们的负样本挖掘方法和混合 LP 方法结合使用，比半监督度量学习领域现有的最优方法表现要好。表 1 中的 NMI 结果也支持这种观察，即我们的方法在半监督度量学习领域的性能有了大幅度的提高。这些结果表明，我们的方法在半监督度量学习等重要且实用的领域能够显著提升现有的最优结果。
4.3. 与最新技术的进一步比较
Dutta 等人[2]也考虑了一种半监督度量学习方法。然而，主要的不同点在于：1）[2] 的论文需要创建和反转一个密集的 矩阵，这需要采样，而我们的方法不涉及创建这样的矩阵，并且能够避免直接矩阵求逆。因此，我们能够利用所有提供的数据。2） [2] 的论文假设亲和力排名相差 的样本是不相似的。然而，适当设置 k 可能需要了解数据集的分布，因为很小的 k 可能会错误地将同类样本声明为负样本，而大的 k 可能只意味着仅使用相距很远的负样本对三元组进行形成。如果数据集类别不平衡，则选择 k 可能也很困难。与 [2] 不同，我们的方法不需要知道数据集的分布，即使对于类别不平衡的数据集也能很好地工作。 为了与 [2] 进行比较，我们使用 [2] 中的实验设置，在 CUB-200 上运行我们的方法。我们使用 BN-Inception，它与 [2] 使用的 GoogLeNet with R-MAC 相当。我们还仅使用了 20 个 epoch，而 [2] 运行了 200 个 epoch。我们在 10 次试验中平均了结果，并在表 2 中呈现了它们。我们优越的结果支持我们的方法可以缓解 [2] 中提到的问题的说法。 由于我们的伪标记方法可以用于[2]中三元组的形成，因此我们的方法是互补的。
4.4. 我们的负样本挖掘方法的消融研究
我们展示了我们挖掘的负样本对于提高 LP 性能是有效的。我们比较了四种方法：1）原始 LP，这是[42]实现的方法。2）MoM [9]将最近邻但不是互为最近邻的点视为不同的对，对于这样的对，W(dis)ij = 1。3）Control 实现了我们的方法，但将 ˜Zi,j 替换为 L1 归一化 Fi，对于所有的 j[10,43]，这是计算数据点的类别概率的常规方法[10,43]。这相当于直接计算成对样本之间的不相似性，而不是它们的一阶邻居。4）Ours 是我们的方法。 对于方法2、3和4，不相似性权重用于我们的混合 LP 方法来获得准确性。这个准确性被计算为：
整个数据集在每个实验中都被使用。实验重复进行了十次，并使用不同的随机选择的五个带标签数据点，给出了 95% 的置信区间。表 3 显示我们的方法在所有比较方法中都获得了一致和显著的改进。 MoM 的表现比原始 LP 方法有所下降，因为它不利用标签，可能会混淆使用标签并能够生成更可靠预测的原始 LP 方法的预测结果。 ‘Control’ 是直接扩展到使用其预测结果生成不相似性权重的原始 LP 方法。它能够比原始 LP 方法获得轻微的改进。这可能是由于它考虑了所有传播的标签并且允许略微增加准确性，而 LP 仅能考虑每个类别标签单独的传播。 我们的方法能够削弱潜在不相似边缘之间的标签平滑约束，并提供与 LP 预测相矛盾的不相似边缘权重，从而导致 LP 目标的显著变化和准确性的显著提高。表 3 中我们方法的巨大准确性提高反映了这一点。
4.5. 我们混合 LP 方法的消融研究
由于[4]和[5]提出的方法具有高的时间复杂度，不能在合理的时间内运行数据集，因此我们的结果主要与LPDR[41]进行比较。 在图4中的实验中，一个神谕随机识别KNN邻居之间的紧密负边缘，这些负边缘没有被标签给出。准确性的计算方式如公式（36）所示。 使用LPDR的符号，使用了LPDR的默认超参数，我们将LPDR的设置为等同于我们的超参数。
从图4中，我们可以看出我们的混合LP方法获得了比LPDR显着更高的准确性。LPDR无法有效地使用提供的负边缘权重，因为当正确的分配为时，它错误地强制对于任何。我们的方法能够避免强烈惩罚这种预期的结果。
4.6. 关于超参数的消融研究
我们对 cub、cars 和 dogs 数据集中的两个超参数 β 和 λ 进行消融研究。在每个实验中，保持 或 的默认设置，而被测试的超参数则是变量。使用我们的方法（22）计算不相似性权重， 并将其与混合LP方法（23）一起使用。精度从（36）中计算。
图5显示了精度对两个超参数 和 的敏感性。精度对 不太敏感，但对 敏感。在本工作中，我们将 固定为中等值 4，但是通过使用更复杂的校准方法（如[6,21]）来调整每个数据集的 值，结果可能进一步得到改善。
5 结论
本论文旨在通过识别远距离的正对和近距离的负对，以提高半监督度量学习在CBIR性能上的表现。我们通过假设边缘间相似度标签在移除边缘时得到相异的k-NN对作为难负样本对，将其纳入一种新的混合LP方法中，实现了这一目标。研究表明，所得到的伪标签在半监督度量学习CBIR应用中取得了最好的结果。
- 作者:VON
- 链接:https://baisihan.asia/article/168e02f8-840f-4334-b7d6-cc15272552ef
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。