少样本分类中基类选择的优化方法

4624少样本分类的基类选择学习周林军1、2彭翠1、徐佳2、杨世强1 、田琦2、1清华大学2、华为诺亚cuip@tsinghua.edu.cnjiayushenyang@gmail.comyangshq@tsinghua.edu.cnhuawei.comzhoulj16@mails.tsinghua.edu.cn摘要近年来，小样本学习引起了广泛的研究关注。已经提出了许多方法来将从提供的基类学习到的模型推广到新的类，但是以前的工作没有研究如何选择基类，或者甚至不同的基类是否会导致学习模型的不同推广性能。在本文中，我们利用一个简单而有效的措施，相似比，作为一个指标的泛化性能的少杆模型。然后，我们制定的基类选择问题作为一个子模块的相似比优化问题并对不同优化方法的优化下界进行了理论分析，为不同的实验环境选择最合适的优化算法提供了理论依据在ImageNet [4]，Caltech 256 [8]和CUB-200-2011 [27]上的大量实验1. 介绍少样本学习[6，13]是迁移学习的一个分支，它的基本设置是在由具有大量标记样本的基类组成的基础数据集上训练基础模型，然后使模型适应由具有少量样本的新类组成的新支持集，最后在由与新支持集相同的新类组成的新测试集上评估模型。传统上，许多研究都集中在如何从固定的数据集中学习Meta知识.基本数据集的生成过程通常依赖于随机选择或人类经验，这对于少拍学习来说并不一定完美由于新支持集上的微调机制不如新类上的大规模训练样本学习有效[25]，因此基础数据集对于少拍学习的性能起着关键作用。然而，到目前为止，我们对* 共同通讯作者。如何衡量基本数据集的质量，更不用说如何优化其选择过程。上述目标问题与课程学习[1，24]和迁移学习中的数据选择[19与课程学习旨在加快学习提供的类不同关于迁移学习中的数据选择方法，首先，我们的问题是基于类的选择而不是基于样本的选择问题，这显著减少了选择的搜索空间。第二，我们考虑了几次学习场景中的问题，其中没有关于新类的验证数据集，并且现代方法具有关于验证性能的反馈机制（例如，[21]中的贝叶斯优化，[19]中的强化学习）不适用。在这里，我们考虑一个现实和实际的设置，M个基类是从N个候选类中选择，每个候选类只包含少量的标记样本之前选择。一旦选择了M个类，就可以通过手动标记将这些选择的类的样本扩展到足够的大小，其进一步用于构建基础数据集和训练基础模型。甄选过程可以一次性进行，也可以逐步进行。为了解决这个问题，我们面临两个挑战。首先，该问题是一个离散优化问题。朴素枚举法的复杂度为O（NM），在实际情况下是难以处理的.其次，没有可触及的方法来直接优化新类别的分类性能，因此我们需要找到一个代理指标，既容易优化，又与新类别的分类性能高度相关在本文中，我们找到了一个简单而有效的指标相似度比，首先由我们以前的工作[30]提出。对于一个候选类，相似度比既考虑了它与新类的相似性，也考虑了基类的多样性。我们证明，这一指标是高度正相关的性能，少数拍摄学习的4625新的测试集。我们从理论上证明了该指标满足次模性质，这保证了我们在多项式时间复杂度内获得次优解。因此，基类选择问题可以通过优化相似比的变体来替代。我们对三种不同的情况进行了广泛的实验：预训练选择，冷启动选择和ImageNet，Caltech 256和CUB-200-2011数据集上的一般选择。实验结果表明，该方法在一般图像分类和细粒度图像分类中均能显著提高小样本学习的性能.无论支持集到查询集的分布转移、少拍模型的改变或少拍实验设置的改变，性能改进幅度都相当稳定。2. 相关工作One-shotLearning的概念是由[6]提出的，更一般的概念是Few-shot Learning。文献中确定了三种主流方法。第一组基于元学习方式，包括匹配网络[25]，MAML[7] ， Pro- totypical Network [22] ， Relation Network[23]，SNAIL [14]等，它们在基础数据集上学习端到端的任务相关模型，可以概括所有任务。第二组方法是通过某种传递机制学习图像分类器，同时保持表示空间不变。这些方法的优点是避免了对模型进行彻底的重新训练，并且对非常大的基础数据集和模型更友好 ， 例 如 ImageNet 上 的 分 类 。 常 见 的 方 法 有 MRN[29]、CLEAR [11]、Weight Imprinting [18]、VAGER[30]等。第三组方法是应用数据生成。其核心思想是使用预定义形式的生成函数来扩展未知类别的训练数据典型的工作包括[9]和[28]。数据选择数据选择的基本假设是，并非所有的训练数据都有助于学习过程;某些训练数据甚至可能产生负面影响。 因此，从坏的数据点，以提高收敛速度和模型的性能。大致有两个分支的工作：一个是假设训练数据和测试数据是从相同的分布中采样的，处理这个问题的一种常见另一个分支是以迁移学习的方式进行数据选择。主流方法包括[20]提出了一种基于启发式定义的距离度量的方法，以找到源域中与目标域最相关的数据点;[21]将数据选择过程对目标域分类最终性能的影响视为黑箱模型，并使用贝叶斯优化通过对验证数据集进行迭代调整选择，并进一步[19]将贝叶斯优化替换为强化学习，这更适合于引入深度模型，以鼓励设计选择算法的更大灵活性。3. 初步研究3.1. 相似比[30]首先提出了一个概念，称为相似比（SR）定义为每个新的类：与基类的平均Top-K相似度SR=.（一）与基类的平均相似性在这里，两个类的相似性由表示空间上的特定度量确定，例如两个类质心的余弦距离。在所有的基类中，我们将每个基类与相应的新类的相似性按下降顺序排序。分子通过平均前K个相似基类的相似性来计算，分母通过平均所有基类的相似性来计算。为了提高SR，分子表示应该有一些与相应的新类相似的基类，分母表示基类应该在每个新类的条件下多样化。[30]进一步指出，少拍性能与该指标呈正相关。3.2. 随机反应与少拍学习成绩在这一部分中，我们将从统计学的角度展示更多的证据来证明SR和少数学习成绩之间的关系。具体地，进行如下的初步实验：我们从ImageNet数据集中随机选择了500个类，并将它们进一步分为400个基类和100个新类。对于每个少镜头分类设置，我们随机选择400个以上的100个基本类作为基本数据集，并使用所有100个新类来执行100路5镜头分类。在基础数据集上训练ResNet-18 [10]，我们为新的支持集和新的测试集提取高级图像特征（conv5_x层后的我们计算新支持集中每个新类的平均特征作为类质心，直接使用基于1-最近邻的在表示空间上定义的余弦距离度量上，以获得每个新类别的Top-1准确度的测试集。基础数据集的选择，训练和评估过程重复100次，对于每个新类，我们运行回归模型：Acc=β1·x1+β2·x2+α+α（2）x1=与基类的平均Top-K相似度x2=与基类的平均相似度.4626≤∈·|≥|⊆⊆|∪−≤·∅其中Acc表示对应的新类别的Top-1准确度，α表示残差项，而α表示噪声。在这个回归模型中，两个类的相似度是通过在所有400个候选基类训练的ResNet-18的表示空间上定义的两个质心的余弦距离来计算的因此，我们总共可以获得100个回归模型，每个模型都针对一个新的类，3210-10 25 50 75 100新类别ID420-2-40 25 50 75 100新类别ID并且每个模型在与100个不同的基础数据集选择相关的100个数据点下学习。选择不同的K，回归模型可能会显示不同的属性。我们从图1、图2、图3中得出结论。我们计算所有新类别的β1和β2的平均值64200 25 50 75 100新类别ID5.02.50.0-2.5-5.0-7.50 25 50 75100新类别ID记为β<$1和β<$2。β1在K的所有选择中都是恒定的，证明了K与准确度相似图1显示了图2.我们绘制每个新类别的系数β1，β2，越来越多的排序红条表示95%置信区间，蓝点表示精确系数。顶部：结果对于K = 3的回归，β<$= 0。99，β<$= 0。29;底部：结果系数β<$/β<$与K。结果表明，K=5时，21for Regression with K = 10, β¯ = 1. 52，β<$=-0。39岁在这个特定的环境中。平均相似度的正效应（即x2）在K=5之后将变为负效应。原因是当K较小时，正类不足，需要增加更多的正类类来提高性能，并且随着K的增加，正类趋于饱和，并且越来越需要负类来增强多样性。在后面的主要实验中，我们将K设置为超参数。图2是K = 3和K = 10两种设置的快照，进一步证明了上述观点。 此外，图2给出了有关β1和β2分布的更多信息。图3显示，当K是一个小数字时，SR的两个分量是少数学习性能的相对较好的代理（即平均R2达到above 0.3 when K 第10段）。 当K = 1时，两个分量SR解释了约45%的因变量。1.00.50.0-0.5-1.00 20 40 60 80 100K图1.系数β<$/β<$随K的变化而变化1 20.70.60.50.40.30.20.10 20 40 60 80 100K图3. 100个回归模型的R2随K的变化，红色条表示从25分位数到75分位数的区间，蓝点表示平均R2。4. 算法4.1. 子模块性简介定义1. 给定一个有限集合V={1，2，· · ·，n}，一个集函数f：2 V→ R是次模的，如果对每个A，B ∈ V：f（A <$B）+f（A <$B）≤ f（A）+f（B）.更好地理解子模性的方法是收益递减：将f（u A）表示为f（A u）f（A），则我们有f（u A）f（uB）对于每个ABV和u/B。这两个定义被证明是等价的[15]。 已经证明，最大化次模目标函数f（）是NP-难问题。然而，由于多项式时间复杂度，已经提出了几种算法来获得次优解。一个函数是单调非减的，如果2 1B，f（A） f（B）. 如果f（）= 0，则f（）被称为归一化。本文主要介绍了一种次模优化方法，基于我们的发现，可以设计一个优化过程来选择核心基类。具有基数约束的mization设置 该问题被公式化为：|S|=kf（S），其中f（·）是sub，β 2/β 1beta1beta1beta2r平方beta2124627-≈e······∈···≥·||←∅←∅←← ←−K←∅≥−{··· }| |←∅≥·||模函数[15]表明，一个简单的贪婪算法可以用来最大化一个归一化的单调非减子模函数与基数约束，最坏情况下的近似因子为11/e0 的情况。六百三十二。[2]示出了归一化子模函数（可以不求绝对值，不求绝对值。实体约束|S|=k可以近似为下一个推论表明问题3等价于一个次模优化。推论4.1。考虑优化问题3，当λ=0时，问题3等价于具有精确基数约束的子模单调非减优化，当λ>0时，问题3等价于具有精确基数约束的子模单调非减优化。max{1−k/en−k，（1+n（n-k）k）−1−o（1）}，其中com-具有精确基数约束的模块优化。随机贪心算法与连续二重化的结合贪婪算法，其中k是所选元素的确切数量，n是元素的总数。所提出的算法保证了0.356的近似值，小于0.632.4.2. 制剂设Bu表示一个新基类的集合，Bs表示所选基类，N表示新类。选择过程是从Bu中选择具有m个元素的子集U，并且基础数据集由U和Bs组成。 对于每个类l，我们将 cl表示为某个类特征（例如，其高级特征的质心），并且对于每个类集合A，我们记为c A=[c l1，c l2，c l|一|]，l1，l2l|一|作为类功能的集合。接下来，我们定义一个运算符max-k-sum如下：4.3. 优化4.3.1情况1：λ= 0当λ = 0时，可以看作是一个标准的子模单调非减优化问题，因此我们可以直接对目标函数的值使用贪婪算法，如算法2所示。然而，对于这个特定的目标函数，需要进一步考虑具有m K N的平凡设置。对于这种设置，可以证明在新类上的贪婪算法（算法1）达到最优解，而算法2只能达到次优。因此，提出了两种不同的贪婪算法来分别处理平凡和非平凡的情况 对于我们下面对算法的描述，f（λ）表示相似性函数，h（λ）表示问题3的优化函数，其中λ =0。Mk（ y）：=max|K|=kΣi∈Kyi= Σkj=1y[j]，算法1新类（f，m）上的贪婪算法1：设U0，S N2：对于i=1到m，其中y是数值向量，[1]第一章，···，y[n]是yi3：设u∈Bu\Ui−1，n∈S是样本最大化f（cu，cn）.按非递增顺序排列根据我们的发现，与第3节中的新类的性能高度正相关，基类选择问题可以用公式表示为SR作为代理的优化过程。具体而言，我们有：4： 设U iUi−1+ u，SSn。5： 如果S=则6：SN。7：如果结束第八章： 端1MaxΣ1·M（f（cn，{cB，cU}））K第九章： 返回UmUBu|U|=mSn∈NλΣ1Σ（三）算法2目标函数（h，m）上的贪婪算法- -一种|N|·n∈N |+ m|+mu∈Bs <$Uf（cn，cu），1：设U为02：对于i=1到m，其中f（ca，c b1，，c bn）=[f（c a，c b1），f（c a，c bn）]是相似度函数（例如余弦距离）。最佳-最小化函数是等式2的相同形式，其中第一项是SR的分子，第二项是SR的分子。是分母）。 λ被视为超参数，其含义等于第3.2节中的β<$2/β<$1。 K也是一个超参数。 为了简单起见，我们可以假设λ 0，因为当λ <0时，优化函数3的两项具有强正相关性，实验结果表明，与直接设置λ=0相比没有太大的改进。U=m是需要选择m个基类的基数约束。3：设ui∈Bu\Ui−1最大化h（ui|Ui−1）.4： 设U iUi−1+ u i。第五章： 端第六章： 返回Um我们进一步给他们。1，2来显示这两个算法的优化界对于这个特定的问题，边界比[15]中的通用版本要严格得多。定理1. 对于Bs=且λ=0，当m KN，使用算法1求解优化问题3，解将是最优的。√|N|24628·∅·≥ −·∨ − ∧ −∈· || · ||←···· · ·||1||e−1eeRe定理2. 对于Bs=且λ=0，使用算法2求解优化问题3，设h（）为优化函数，设Q为Q=Eu<$Uniform（B），v<$Uniform（N）（f（cu，cv））表示基本类和新类之间的平均相似度，我们有h（U）（1 1/e）h（OPT）+1/e Q，其中h（OPT）是优化问题的全局最优值。4.3.2情况2：λ >0属于子集的是1，否则为0，与[2]一致。在双连续贪婪算法中，我们不需要计算F（x）的精确值，唯一的困难是计算F（x u）F（x （B uu））。定理3给出了一个快速计算的动态规划。定理3. 设S ∈ Bu是一个随机集，其中每个元素v都在Bu中i.i.d. 以概率（x <$（B u− u））采样v.对每个新类n ∈ N，按降序对每个基类b∈B=B u<$B s的相似函数 f （ cn ， c b ） 进 行 排 序 ， 记 为 qn ， [1] ， qn ，[2]，···qn，[|B|[1]，sn，[2]，···s n，[3]，···s n，[4]，···s n，[5]，···s n，[6]，···sn，[7]，···s n，[8]，···s n，[9]，···s n，[9]，···s n，[9]，··s n，[9]，··sn，[9]，··· s n，[9]·s n，[9]，··n，··n，[9·s n，n·s，[9]，·n·|S|+|BS|]，则我们有：F（x<$u）−F（x<$（Bu−u））当λ>0时，可以看作是一个非单调的子模优化问题，利用文献[2]中的技巧，我们将两者结合起来1=|N|·KΣΣ|B|n∈Ni=1P（sn，[K]=qn，[i]）max（f（cn，cu）−qn，[i]，0）（六）随机贪婪算法（算法3）和连续双贪婪算法（算法4），用于更好的优化。随机贪婪算法是1-λ|N|·mΣn∈Nf（cn，cu）标准贪婪算法（算法2），适用于m值极低的情况。算法的细节在算法3中给出。算法3随机贪婪算法（h，m）1：设U0←U在所有随机子集S上定义n N的概率项P（s n，[K]=qn，[i]），其中s n，[K]可以看作是随机变量。这个概率项可以使用动态规划在O（K B N）时间复杂度下通过以下递归方程求解：P（sn，[j]≥qn，[i]）=（1−x[i]）·P（sn，[j]≥qn，[i−1]）2：对于i=1到m，+x[i]·P（sn，[j−1]≥qn，[i−1]）forr[i]∈Bu（七）3：LetMiBu\Ui−1是大小为m的子集，u∈Mih（u|Ui−1）.4： 设ui是来自Mi的均匀随机样本。5： 设U iUi−1+ u i。第六章： 端第七章： 返回Um对于更大的m，我们将引入连续双贪婪算法。其核心思想是将问题3的离散优化转化为连续优化。设F（x）是优化函数h（·）的多线性扩展，如下：<$P（sn，[j]≥qn，[i]）=P（sn，[j−1]≥qn，[i−1]）for[i]∈BsP（sn，[j]=qn，[i]）=P（sn，[j]≥qn，[i]）−P（sn，[j]≥qn，[i−1]）其中j为1K和i跑1B. 1算法4显示了连续的完整过程双贪婪算法该算法首先使用基于梯度的方法来优化子模目标函数的代理多线性扩展，并返回次优连续向量x，其表示每个元素被选择的概率。然后，使用某些舍入技术（如Pipage Rounding [3，26]）将所得分数解转换为积分解。2ΣF（ x）=SBu|B|Yh（ S）xuu∈SY（1−xuu∈/S）（4）定理4给出了算法3和算法4的类似优化界分析。定理4.对于Bs=λ且λ>0，使用以下组合：其中x∈[0，1]u.给定一个向量x，F（x）表示给定Bu的随机子集的函数h的期望算法3和4用于求解优化问题3，λ>0，h和Q的定义与定理2相同，我们有其中每个元素u∈B ui.i.d. 概率抽样xu. 对于两个向量x和y，定义xy和xy为E（h（U））≥max（1−m/er·h（OPT）+Ce·Q，分别是坐标方向的最大值和最小值，即（1+R√2（r− m）m）−1·h（OPT）+C2·Q）（x<$y）u= max（xu，yu）和（x<$y）u= min（xu，yu）。一个多线性形式函数F重要性质是：对于0<λ1，我们有C=1+（1−1）m−（1−1）·F（x）λ>0且C2=2（1−λ）r（r-m）m+r-λ≥2（1−λ）>0，其中xu=F（x<$u）−F（x<$（Bu−u））（5）r= B u。第一项是算法3的下界而第二项用于算法4。√114629为了简单起见，在这一部分中，子集的符号也可以表示为0-1向量，其中对应的元素1详情见附录2.2和2.3。2见附录2.4。4630DTDTa′+b′DTa′+b′uu不DT算法4连续双贪婪算法（F，m）一曰： 初始化：x0←，y0←Bu第二章： 对于时间步长t∈[1，T]，3：对于每个u∈Bu做在第3节的初步实验中，将其进一步分为400个候选基类和100个新类。对于所有这三个任务，从这400个候选基类中选择基本数据集，并进一步评估generator。4：Letau←F（xt−1）xu，bu←F（yt−1）用Eq.六七在100个新颖的ImageNet类上的alization性能加州理工256和CUB-200-2011。5：设a′（l）<$max（au−l，0），b′（l）<$max（bu+l，0）u ua′b′对于所有实验，我们训练了一个标准的ResNet-18[10]。6：设dxu（l，t−1）<$u，dyu（l，t−1）<$−u-是的7：结束第8章：找到满足感uΣu∈Buu u udxu（l，t − 1）= m.在小说类的小样本学习任务中，我们使用了两种不同的头部：一种是表示上的余弦相似度9：对x和梯度执行梯度上升步骤空间（conv5_x层之后的512维特征），下降y：xt=xt−1+1·dxu（l，t−1），是匹配网络的简化版本[25]，y t=y t−1− 1·dyu（l，t −1）。Meta训练步骤，代表基于度量u u10：结束T dt在少数镜头学习的方法。 另一个是softmax十一： 使用xT处理某些舍入技术以得到U。十二： 返回U定理4指出，如果忽略Q项，则当m<0. 08r或m >0.92r，我们应该使用算法3，否则算法4通过比较两个界限。作为本节的结论，我们在表1中列出了不同算法对该特定问题5. 实验5.1. 实验设置基本上，我们设计了三种不同的设置来显示我们所提出的算法的优越性：预训练选择给出了一个预训练模型，并利用预训练模型进行基类选择。一般来说，我们可以使用预训练的模型来提取图像表示。该设置还假设我们知道新的支持集。在本文中，我们仅通过在选定的基类上训练的基本模型来评估广义性能，而在实践中，我们也可以使用这些选定的基类来进一步微调给定的预训练模型。冷启动选择没有给出预训练模型，因此基类选择以增量方式进行。对于每个回合，增量基类的选择基于来自前一回合的训练的基础模型并给出了新的支撑集。请注意，设置有点像课程学习[1]。一般选择新的支持集是未知的（即选择一个通用的基础数据集，在任何新的类的组合上表现良好）。在本文中，为了简单起见，我们还假设在预训练选择设置中给出了一个预训练模型。在我们的实验中，我们使用两个数据集来验证一般分类：ImageNet和Caltech256，回归的表示空间，这是一个简单的方法，从分支的学习为基础的方法。3我们使用不同的头来表明我们提出的选择方法是模型不可知的。至于实验的细节，我们采用了第一节中提到的主动学习方式。每个候选基类在被选中之前只包含50个图像。我们使用这些图像来计算类表示。 当选择一个基类时，这个类的训练图像的数量可以扩展到一个相对丰富的数量（对于这个实验，使用ImageNet中这个类的所有训练图像，其位于大约800到1，300的区间我们允许每个类的图像数量略有差异对于p路k-shot设置，我们随机选择p个新类，然后为每个新类选择k个样本作为新支持集;另外100、50、40个样本与每个新类的支持集不相交，作为ImageNet、Caltech和CUB-200-2011的新测试集。实验的流程是运行选择算法，扩展选定的类，在扩展的基础数据集上训练基础模型，并在测试集上评估性能。该过程以不同的随机化重复10次，并且我们报告了每个实验设置的平均Top-1准确度对于包含预训练模型的设置，本文中我们使用ResNet-18对从第3节中的候选基类中随机选择的100个类中的完整训练图像进行训练，这与本节中使用的基类和新类不相交。我们还强调，当在相同的设置下与不同的方法进行比较时，相同的新的支持集和新的测试集用于每轮实验，以进行公平的比较。我们在实验中考虑三个基线：第一种是随机选择，它均匀地绘制基类，这是一个相当简单的基线，但在实际场景中很常见，第二种是使用域相似性度量，通常在[17，20，21]中使用。 这个想法是为了最大化代表之间的预定义域相似性对于细粒度分类：CUB-200-2011。 对于图像-geNet中，我们使用了除3之外的其他500个类。softmax回归头的结果如4所示。在选定的基类上将主干作为基础模型为4631表1.不同算法的适用性结论参数算法适用性复杂性新类m> γ·K·上的λ = 0贪婪|N |10- 12 - 13 - 2000，10 - 2000，10 - 2000，10 - 2000，|B|·日志|B|·|N|）目标函数m <γ·K·上的λ = 0贪婪|N|（2）当γ =10（|B|+的|N|·logK））λ> 0随机贪婪m<0. 08·|B u|或m >0。92·|B u|O（m）·（|B|·logm + |N|·logK））λ> 0连续双贪婪0. 08·|B u|

下载后可阅读完整内容，剩余1页未读，立即下载