卷积神经网络的主动学习：核心集方法

摘要

卷积神经网络 (CNN) 已使用通用方法成功应用于许多识别和学习任务； 在非常大的监督示例数据集上训练深度模型。 然而，这种方法在实践中相当有限制，因为收集大量标记图像非常昂贵。 缓解这个问题的一种方法是提出智能方法，从一个非常大的集合中选择要标记的图像（即主动学习）。

我们的实证研究表明，文献中的许多主动学习启发式方法在批量设置中应用于 CNN 时并不有效。 受这些限制的启发，我们将主动学习的问题定义为核心集选择，即选择点集，使得在所选子集上学习的模型对于剩余数据点具有竞争力。 我们进一步提出了一个理论结果，该结果描述了使用数据点的几何形状的任何选定子集的性能。 作为主动学习算法，我们根据我们的特征选择预计会产生最佳结果的子集。 我们的实验表明，所提出的方法在图像分类实验中明显优于现有方法。

1简介

深度卷积神经网络 (CNN) 在计算机视觉和模式识别的许多研究领域（例如图像分类、对象检测和场景分割）取得了前所未有的成功。 尽管 CNN 在许多任务中普遍成功，但它们有一个主要缺点：他们需要大量的标记数据才能学习大量参数。 更重要的是，拥有更多数据几乎总是更好，因为 CNN 的准确性通常不会随着数据集大小的增加而饱和。 因此，人们一直渴望收集越来越多的数据。 尽管从算法的角度来看这是期望的行为（代表性能力通常越高越好），但标记数据集是一项耗时且昂贵的任务。 这些实际考虑提出了一个关键问题：“选择要标记的数据点的最佳方式是什么，以便在固定的标记预算下获得最高的准确性。”主动学习是常见的范例之一来解答这个问题。

主动学习的目标是找到有效的方法从未标记的数据点池中选择要标记的数据点，以最大限度地提高准确性。 尽管不可能获得普遍良好的主动学习策略（Dasgupta，2004），但存在许多启发式（Settles，2010），它们已被证明在以下方面有效：实践。 主动学习通常是一个迭代过程，其中在每次迭代中学习模型，并使用上述启发式方法从未标记点池中选择一组点进行标记。 我们在本文中尝试了许多启发式方法，发现它们在应用于 CNN 时并不有效。 我们认为，这种无效背后的主要因素是批量采集/采样引起的相关性。 在经典设置中，主动学习算法通常在每次迭代时选择一个点；然而，这对于 CNN 来说是不可行的，因为 i) 由于局部优化方法，单个点可能对准确性没有统计上的显着影响，并且 ii) 每次迭代都需要完整的训练直到收敛，这使得查询标签变得困难一对一。 因此，有必要在每次迭代时查询大子集的标签，即使对于适度小的子集大小也会产生相关样本。

为了针对批量采样情况定制主动学习方法，我们决定将主动学习定义为核心集选择问题。 核心集选择问题的目标是在给定大标记数据集的情况下找到一个小子集，以便在小子集上学习的模型在整个数据集上具有竞争力。 由于我们没有可用的标签，因此我们在不使用标签的情况下执行核心集选择。 为了解决 CNN 的未标记核心集问题，我们通过数据点的几何形状提供了数据集任何给定子集的平均损失与剩余数据点之间的严格界限。 作为主动学习算法，我们尝试选择一个子集以使该界限最小化。 此外，该界限的最小化结果相当于 k 中心问题（Wolf，2011），并且我们对该组合优化问题采用了有效的近似解决方案。 我们使用三个不同的数据集进一步根据经验研究了我们提出的算法针对图像分类问题的行为。 我们的实证分析充分证明了最先进的性能。

2相关工作

我们分别讨论以下类别的相关工作。 简而言之，我们的工作与现有方法的不同之处在于$i)$它将主动学习问题定义为核心集选择，$ii)$我们考虑完全监督和弱监督的情况，$iii)$ 我们直接严格解决 CNN 的核心集选择问题，没有额外的假设。

主动学习主动学习已被广​​泛研究，大部分早期工作可以在Settles (2010)的经典综述中找到。 它涵盖了信息理论方法（MacKay，1992）、集成方法（McCallumzy & Nigamy，1998；Freund等人，1997）和基于不确定性的方法（Tong＆Koller，2001；Joshi等人，2009；Li＆Guo，2013）。

贝叶斯主动学习方法通​​常使用高斯过程等非参数模型来估计每个查询的预期改进（Kapoor等人，2007）或一组查询后的预期误差（Roy和麦卡勒姆，2001）。 这些方法并不直接适用于大型 CNN，因为它们无法扩展到大规模数据集。 Gal & Ghahramani (2016) 最近的方法显示了 dropout 和近似贝叶斯推理之间的等价性，从而能够将贝叶斯方法应用于深度学习。 尽管贝叶斯主动学习已被证明对小型数据集有效（Gal等人，2017），但我们的实证分析表明，由于批量采样，它们无法扩展到大规模数据集。

一个重要的类别是基于不确定性的方法，它试图使用启发式方法找到困难的例子，例如最高熵（Joshi等人，2009）和到决策边界的几何距离（Tong＆Koller， 2001；布林克，2003）。 我们的实证分析发现它们对于 CNN 无效。

最近有一些基于优化的方法，可以权衡不确定性和多样性，以便在批处理模式主动学习设置中获得一组不同的困难示例。 Elhamifar 等人 (2013) 和 Yang 等人 (2015) 为此目的设计了一个离散优化问题，并使用其凸代理。 类似地，Guo (2010)提出了一个与矩阵划分类似的问题。 然而，这些论文中提出的优化算法使用 $n^2$ 变量，其中 $n$ 是数据点的数量。 因此，它们无法扩展到大型数据集。 还有许多针对特定类别的机器学习算法设计的基于池的主动学习算法，例如 k 最近邻和朴素贝叶斯 (Wei 等人, 2015)、逻辑回归 Hoi 等人 ( 2006）； Guo & Schuurmans (2008)，以及高斯噪声线性回归(Yu 等人, 2006)。 即使在与算法无关的情况下，也可以设计一种集合覆盖算法来使用子模块性（Guillory & Bilmes，2010；Golovin & Krause，2011）来覆盖假设空间。 另一方面，Demir 等人 (2011) 使用启发式方法，首先根据不确定性过滤池，然后使用多样性选择点进行标记。 我们的算法可以认为属于此类；但是，我们不使用任何不确定性信息。 我们的算法也是第一个应用于 CNN 的算法。 与我们最相似的是（Joshiy等人，2010）和（Wang＆Ye，2015）。 Joshiy 等人 (2010) 使用类似的优化问题。 然而，他们没有提供理论依据或分析。 Wang & Ye（2015）提出像我们一样使用经验风险最小化；然而，他们试图最小化两个分布之间的差异（iid 之间的最大平均差异）。 数据集中的样本和主动选择的样本）而不是核心集损失。 此外，这两种算法也都没有在 CNN 上进行实验。 在我们的实验研究中，我们与（Wang & Ye，2015）进行比较。

最近，针对域转移设置中的 k-NN 类型算法，提出了一种与我们的方法类似的基于离散优化的方法（Berlind & Urner，2015）。 尽管我们的理论分析借鉴了他们的一些技术，但他们的结果仅对 k-NN 有效。

CNN 的主动学习算法最近也在（Wang 等人，2016；Stark 等人，2015）中提出。 Wang等人(2016)提出了一种基于启发式的算法，该算法直接为置信度高的数据点分配标签，并为置信度低的数据点查询标签。 此外，Stark等人(2015)专门针对识别验证码图像。 尽管他们的结果对于验证码识别很有希望，但他们的方法对于图像分类并不有效。 我们在第 5 节中讨论这两种方法的局限性。

在理论方面，研究表明贪婪主动学习在算法和数据不可知的情况下是不可能的（Dasgupta，2005）。 然而，依赖于数据的结果表明，确实可以获得比查询所有点具有更好样本复杂性的查询策略。 这些结果要么使用关于假设空间的数据依赖可实现性的假设，如（Gonen等人，2013），要么使用概念空间的数据依赖度量，称为不一致系数（Hanneke，2007）. 还可以通过重要性采样使用贪婪算法在批量设置中执行主动学习（Ganti & Gray，2012）。 尽管上述算法享有理论保证，但它们不适用于大规模问题。

核心集选择 与我们的工作最接近的文献是核心集选择问题，因为我们将主动学习定义为核心集选择问题。 该问题考虑完全标记的数据集，并尝试选择它的子集，以便在所选子集上训练的模型将尽可能接近在整个数据集上训练的模型。 对于具体的学习算法，有SVM的核心集（Tsang等人，2005）和k-Means和k-Medians的核心集（Har-Peled & Kushal， 2005）。 然而，我们还不知道 CNN 有这种方法。

与我们最相似的算法是（Wei等人，2013）中的无监督子集选择算法。 它使用设施位置问题来找到数据集的多样化覆盖。 我们的算法的不同之处在于它使用稍微不同的设施位置问题表述。 我们使用极小极大 (Wolf, 2011) 形式，而不是最小和。 更重要的是，我们首次将该算法应用于主动学习问题，为CNN提供了理论保证。

弱监督深度学习 我们的论文也与半监督深度学习相关，因为我们在全监督和弱监督方案中都试验了主动学习。 早期的弱监督卷积神经网络算法之一是梯形网络（Rasmus等人，2015）。 最近，我们看到了对抗性方法，可以通过两人非合作游戏来学习数据分布（Salimans 等人，2016；Goodfellow 等人，2014；Radford 等人，2015）。 这些方法进一步扩展到特征学习（Dumoulin等人，2016；Donahue等人，2016）。 我们在实验中使用梯形网络；然而，我们的方法与弱监督学习算法的选择无关，并且可以利用任何模型。

3问题定义

在本节中，我们正式定义批量设置中的主动学习问题，并为本文的其余部分设置符号。 我们对在紧凑空间 $𝒳$ 和标签空间 $𝒴=\{1,\mathrm{\dots },C\}$ 上定义的 $C$ 类分类问题感兴趣。 我们还考虑在假设类 ($𝐰$) 上参数化的损失函数 $l(\cdot ,\cdot ;𝐰):𝒳\times 𝒴\to ℛ$，例如深度学习算法的参数。 我们进一步假设特定于类的回归函数 ${\eta }_c(𝐱)=p(y=c|𝐱)$ 对于所有 $c$ 都是 ${\lambda }^{\eta }$-Lipschitz 连续的。

我们考虑采样的大量数据点$i.i.d.$ $𝒵=𝒳\times 𝒴$ 上方的空间为 ${\{{𝐱}_i,y_i\}}_{i\in [n]}\sim p_{𝒵}$，其中 $[n]=\{1,\mathrm{\dots },n\}$。 我们进一步考虑随机均匀选择的初始数据点池作为${𝐬}^0={\{s^0(j)\in [n]\}}_{j\in [m]}$。

主动学习算法只能访问${\{{𝐱}_i\}}_{i\in [n]}$和${\{y_{s(j)}\}}_{j\in [m]}$。 换句话说，它只能看到初始子采样池中点的标签。 此外，还给出了可向神谕询问的查询预算 $b$，以及学习算法 $A_{𝐬}$，该算法可在给出标记集 $𝐬$ 的情况下输出一组参数 $𝐰$。 池问题的主动学习可以简单地定义为

$$\underset{{𝐬}^1:|{𝐬}^1|\le b}{\min }{E}_{𝐱,y\sim p_{𝒵}}[l(𝐱,y;A_{{𝐬}^0\cup {𝐬}^1})]$$ (1)

换句话说，主动学习算法可以选择$b$个额外点并让它们由预言机标记，以最小化未来的预期损失。 我们的表述与主动学习的经典定义之间存在一些差异。 经典方法考虑预算为 1 ($b=1$) 的情况，但单点在深度学习机制中的影响可以忽略不计，因此我们考虑批量情况。 考虑多轮比赛也是很常见的。 我们还通过解决单轮标签的短视方法来遵循多轮公式：

$$\underset{{𝐬}^{k+1}:|{𝐬}^{k+1}|\le b}{\min }{E}_{𝐱,y\sim p_{𝒵}}[l(𝐱,y;A_{{𝐬}^0\cup \mathrm{\dots }{𝐬}^{k+1}})]$$ (2)

尽管我们将其应用于多轮，但为了简洁起见，我们仅讨论第一次迭代，其中 $k=0$ 。

在每次迭代中，主动学习算法有两个阶段：1. 识别一组数据点并将它们呈现给要标记的预言机，2. 使用新的和先前标记的数据点训练分类器。 第二阶段（训练分类器）可以以完全或弱监督的方式完成。 完全监督是仅使用标记的数据点来训练分类器的情况。 弱监督是指训练还利用尚未标记的点的情况。 尽管现有文献仅关注全监督模型的主动学习，但我们考虑了这两种情况并进行了实验。

4方法

4.1 以主动学习为背景

在经典的主动学习设置中，算法通过查询预言机（即 $b=1$)来一一获取标签。 遗憾的是，这在训练 CNN 时并不可行，因为由于局部优化算法，$i)$ 单个点不会对模型产生显著的统计影响。 $ii)$ 由于许多感兴趣的实际问题规模非常大，因此训练与点数一样多的模型是不可行的。 因此，我们关注批量主动学习问题，其中主动学习算法在每次迭代时选择一个中等大的点集由预言机标记。

为了设计在批量设置中有效的主动学习策略，我们考虑在(1)中正式定义的主动学习损失的以下上限：

$E_{𝐱,y\sim p_{𝒵}}[l(𝐱,y;A_{𝐬})]$ $\le \underset{\text{Generalization Error}}{\underbrace{\left|E_{𝐱,y\sim p_{𝒵}}[l(𝐱,y;A_{𝐬})]-{\displaystyle \frac{1}{n}}{\displaystyle \sum _{i\in [n]}}l({𝐱}_i,y_i;A_{𝐬})\right|}}+\underset{\text{Training Error}}{\underbrace{{\displaystyle \frac{1}{|𝐬|}}{\displaystyle \sum _{j\in 𝐬}}l({𝐱}_j,y_j;A_{𝐬})}}$ (3)

$+\underset{\text{Core-Set Loss}}{\underbrace{|{\displaystyle \frac{1}{n}}{\displaystyle \sum _{i\in [n]}}l({𝐱}_i,y_i;A_{𝐬})-{\displaystyle \frac{1}{|𝐬|}}{\displaystyle \sum _{j\in 𝐬}}l({𝐱}_j,y_j;A_{𝐬}),|}}$

我们感兴趣的数量是使用小标记子集 ($𝐬$) 学习的模型的总体风险。 总体风险由模型在标记子集上的训练误差、整个数据集 ($[n]$) 上的泛化误差和项来控制我们将其定义为核心集损失。 核心集损失只是有标签的点集的平均经验损失与包括未标记点的整个数据集的平均经验损失之间的差异。 根据经验，人们广泛观察到 CNN 具有很高的表达能力，导致训练误差非常低，并且它们通常能够很好地泛化各种视觉问题。 此外，CNN 的泛化误差也得到了理论研究，并显示其受 Xu & Mannor (2012) 限制。 因此，主动学习的关键部分是核心集损失。 根据这一观察，我们将主动学习问题重新定义为：

$$\underset{{𝐬}^1:|{𝐬}^1|\le b}{\min }\left|\frac{1}{n}\sum _{i\in [n]}l({𝐱}_i,y_i;A_{{𝐬}^0\cup {𝐬}^1})-\frac{1}{|{𝐬}^0+{𝐬}^1|}\sum _{j\in {𝐬}^0\cup {𝐬}^1}l({𝐱}_j,y_j;A_{{𝐬}^0\cup {𝐬}^1})\right|$$ (4)

非正式地，给定初始标签集 (${𝐬}^0$) 和预算 ($b$)，我们试图找到一组点来查询标签 (${𝐬}^1$)这样当我们学习一个模型时，模型在标记子集上的性能和在整个数据集上的性能将尽可能接近。

4.2 CNN 核心集

我们在 (4) 中定义的优化目标不可直接计算，因为我们无法访问所有标签（即 $[n]\setminus ({𝐬}^0\cup {𝐬}^1)$ 未标记）。 因此，在本节中，我们给出了可以优化的目标函数的上限。

我们首先给出任何损失函数的这个界限，即固定真实标签 $y$ 和参数 $𝐰$ 的 Lipschitz 函数，然后证明具有 ReLu 非线性的 CNN 的损失函数满足以下条件：财产。 我们还依赖于零训练误差假设。 尽管零训练误差并不是一个完全现实的假设，但我们的实验表明所得的上限非常有效。 我们陈述以下定理；

Theorem 1。

给定 $n$ i.i.d. 从$p_{𝒵}$抽取的样本作为${\{{𝐱}_i,y_i\}}_{i\in [n]}$，以及点集$𝐬$。 如果损失函数$l(\cdot ,y,𝐰)$对于所有$y,𝐰$是${\lambda }^l$-Lipschitz连续并且以$L$为界，则回归函数为${\lambda }^{\eta }$-Lipschitz，$𝐬$ 是 ${\{{𝐱}_i,y_i\}}_{i\in [n]}$ 的 ${\delta }_{𝐬}$ 覆盖，以及 $l({𝐱}_{s(j)},y_{s(j)};A_{𝐒})=0\forall j\in [m]$；概率至少为 $1-\gamma$，

$$\left|\frac{1}{n}\sum _{i\in [n]}l({𝐱}_i,y_i;A_{𝐬})-\frac{1}{|𝐬|}\sum _{j\in 𝐬}l({𝐱}_j,y_j;A_{𝐬})\right|\le \delta ({\lambda }^l+{\lambda }^{\mu }LC)+\sqrt{\frac{L^2\log (1/\gamma )}{2n}}.$$

由于我们假设核心集的训练误差为零，因此核心集损失等于整个数据集的平均误差$\left|\frac{1}{n}{\sum }_{i\in [n]}l({𝐱}_i,y_i;A_{𝐬})-\frac{1}{|𝐬|}{\sum }_{j\in 𝐬}l({𝐱}_j,y_j;A_{𝐬})\right|=\frac{1}{n}{\sum }_{i\in [n]}l({𝐱}_i,y_i;A_{𝐬})$。 我们以这种形式陈述定理与（3）一致。 我们在图 1 中可视化这个定理，并将其证明推迟到附录。 在该定理中，“集合$𝐬$是集合$s^{\star }$的$\delta$覆盖”表示以为中心的半径为$\delta$的一组球$𝐬$的每个成员都可以覆盖整个$s^{\star }$。 非正式地，该定理表明我们可以将核心集损失与覆盖半径限制在一起，并且速率为零的项仅取决于 $n$。这是一个有趣的结果，因为这个界限不依赖于标记点的数量。 换句话说，提供的标签不会减少核心组的损失，除非它减少了覆盖半径。

图1： 定理1的可视化。 考虑选定点的集合 $𝐬$ 以及数据集中其余部分的点 $[n]\setminus 𝐬$，我们的结果表明，如果 $𝐬$ 是数据集的 ${\delta }_{𝐬}$ 封面，则 $\left|\frac{1}{n}{\sum }_{i\in [n]}l({𝐱}_i,y_i,A_{𝐬})-\frac{1}{|𝐬|}{\sum }_{j\in 𝐬}l({𝐱}_j,y_j;A_{𝐬})\right|\le 𝒪\left({\delta }_{𝐬}\right)+𝒪\left(\sqrt{\frac{1}{n}}\right)$

为了证明这个界限适用于 CNN，我们通过以下引理证明了 CNN 损失函数相对于输入图像的 Lipschitz 连续性：固定真实标签，其中最大池和受限线性单元是非线性度和损失定义为所需类别概率与 soft-max 输出之间的 $l_2$ 距离。 文献中，CNN 通常与交叉熵损失一起用于分类问题。 事实上，尽管我们在理论研究中使用 $l_2$ 损失，但我们也使用交叉熵损失进行实验。 尽管我们的理论研究没有扩展到交叉熵损失，但我们的实验表明，所得算法对于交叉熵损失非常有效。

Lemma 1.

损失函数定义为类概率与卷积神经网络的 softmax 输出之间的 2-范数，其中定义了 $n_c$ 卷积层（带有 max-pool 和 ReLU）和 $n_{fc}$ 全连接层C 类别上的模型是 $\left(\frac{\sqrt{C-1}}{C}{\alpha }^{n_c+n_{fc}}\right)$-固定类别概率和网络参数的输入的 Lipschitz 函数。

这里，$\alpha$是每个神经元输入权重的最大总和（正式定义见附录）。 虽然它通常是无界的，但它可以任意小，而不改变损失函数的行为（即保持任何数据点 $𝐬$ 的标签不变）。 我们将证明推迟到附录，并得出结论：CNN 具有我们在定理 1 中提出的界限。

为了通过计算执行主动学习，我们使用这个上限。 换句话说，感兴趣的实际问题变成${\min }_{{𝐬}^1:|{𝐬}^1\le b|}{\delta }_{{𝐬}^0\cup {𝐬}^1}$。 该问题相当于 k 中心问题（也称为最小-最大设施位置问题）（Wolf，2011）。 在下一节中，我们将解释如何在实践中使用贪心近似来解决 k 中心问题。

算法1 k中心贪心

Input: data ${𝐱}_i$, existing pool ${𝐬}^0$ and a budget $b$

Initialize $𝐬={𝐬}^0$

repeat

$u=\arg {\max }_{i\in [n]\setminus 𝐬}{\min }_{j\in 𝐬}\mathrm{\Delta }({𝐱}_i,{𝐱}_j)$

$𝐬=𝐬\cup \{u\}$

until $|𝐬|=b+|{𝐬}^0|$

return $𝐬\setminus {𝐬}^0$

4.3 解决k中心问题

到目前为止，我们已经为核心集选择问题的损失函数提供了一个上限，并表明最小化它相当于k-Center问题（最小最大设施位置（Wolf，2011） )) 可以直观地定义如下；选择 $b$ 中心点，使数据点与其最近中心之间的最大距离最小化。 从形式上来说，我们正在尝试解决：

$$\underset{{𝐬}^1:|{𝐬}^1|\le b}{\min }\underset{i}{\max }\underset{j\in {𝐬}^1\cup {𝐬}^0}{\min }\mathrm{\Delta }({𝐱}_i,{𝐱}_j)$$ (5)

不幸的是这个问题是 NP-Hard (Cook 等人, 1998)。 然而，使用算法1中所示的贪婪方法可以有效地获得$2-OPT$解决方案。 如果$OPT={\min }_{{𝐬}^1}{\max }_i{\min }_{j\in {𝐬}^1\cup {𝐬}^0}\mathrm{\Delta }({𝐱}_i,{𝐱}_j)$，则算法1中所示的贪心算法被证明有一个解决方案(${𝐬}^1$)，使得； ${\max }_i{\min }_{j\in {𝐬}^1\cup {𝐬}^0}\mathrm{\Delta }({𝐱}_i,{𝐱}_j)\le 2\times OPT$。

尽管贪心算法给出了很好的初始化，但实际上我们可以通过迭代查询最优值的上限来改进 $2-OPT$ 解决方案。 换句话说，我们可以设计一个算法来判断是否$OPT\le \delta$。 为此，我们定义了一个由$\delta$参数化的混合整数程序（MIP），其可行性表明${\min }_{{𝐬}^1}{\max }_i{\min }_{j\in {𝐬}^1\cup {𝐬}^0}\mathrm{\Delta }({𝐱}_i,{𝐱}_j)\le \delta$。 一种直接的算法是使用此 MIP 作为子例程，并在贪婪算法的结果与其一半之间执行二分搜索，因为保证最优解包含在该范围内。 在构造这个 MIP 的同时，我们还尝试解决 k-Center 算法的弱点之一，即鲁棒性。 为了使 k 中心问题具有鲁棒性，我们假设离群值 $\mathrm{\Xi }$ 的数量有上限，这样我们的算法就可以选择不覆盖最多 $\mathrm{\Xi }$ 个无监督数据点。 这个混合整数程序可以写成：

$Feasible(b,{𝐬}^0,\delta ,\mathrm{\Xi }):$ ${\displaystyle \sum _j}{u}_j,=|{𝐬}^0|+b,$ ${\displaystyle \sum _{i,j}}{\xi }_{i,j}\le \mathrm{\Xi }$ (6)

${\displaystyle \sum _j}{\omega }_{i,j}=1\forall i,$ ${\omega }_{i,j}\le u_j\forall i,j$

$u_i=1\forall i\in {𝐬}^0,$ $u_i\in \{0,1\}\forall i$

${\omega }_{i,j}={\xi }_{i,j}\forall i,j\mid$ $\mathrm{\Delta }({𝐱}_i,{𝐱}_j)>\delta .$

在此公式中，如果 $i^{th}$ 数据点被选为中心，则 $u_i$ 为 1；如果 $i^{th}$ 点被 $j^{th}$ 点覆盖，则 ${\omega }_{i,j}$ 为 $1$；如果 $i^{th}$ 点是离群点，且被 $j^{th}$ 点覆盖，而没有 $\delta$ 约束，则 ${\xi }_{i,j}$ 为 1；否则为 $0$。 并且，变量是二进制的 $u_i,{\omega }_{i,j},{\xi }_{i,j}\in \{0,1\}$。 我们在图2中进一步可视化这些变量，并在算法2中给出该方法的细节。

算法2 强大的 k 中心

Input: data ${𝐱}_i$, existing pool ${𝐬}^0$, budget $b$ and outlier bound $\mathrm{\Xi }$

Initialize ${𝐬}_g=$ k-Center-Greedy(${𝐱}_i,{𝐬}^0,b$)

${\delta }_{2-OPT}={\max }_j{\min }_{i\in {𝐬}_g}\mathrm{\Delta }({𝐱}_i,{𝐱}_j)$

$lb=\frac{{\delta }_{2-OPT}}{2}$, $ub={\delta }_{2-OPT}$

repeat

if $Feasible(b,{𝐬}^0,\frac{lb+ub}{2},\mathrm{\Xi })$ then

$ub={\max }_{i,j\mid \mathrm{\Delta }({𝐱}_i,{𝐱}_j)\le \frac{lb+ub}{2}}\mathrm{\Delta }({𝐱}_i,{𝐱}_j)$

else

$lb={\min }_{i,j\mid \mathrm{\Delta }({𝐱}_i,{𝐱}_j)\ge \frac{lb+ub}{2}}\mathrm{\Delta }({𝐱}_i,{𝐱}_j)$

end if

until $ub=lb$

return $\{is.t.u_i=1\}$

图2： 变量的可视化。 在此解决方案中，选择 $4^{th}$ 节点作为中心，节点 $0,1,3$ 位于其周围的 $\delta$ 球中。 $2^{nd}$ 节点被标记为异常值。

4.4实现细节

关键的设计选择之一是距离度量$\mathrm{\Delta }(\cdot ,\cdot )$。 我们使用最终全连接层激活之间的 $l_2$ 距离作为距离。 对于弱监督学习，我们使用梯形网络（Rasmus等人，2015），对于所有实验，我们使用VGG-16（Simonyan & Zisserman，2014）作为CNN建筑学。 我们根据He等人(2016)初始化所有卷积滤波器。 我们使用 RMSProp 优化了所有模型，使用 Tensorflow （Abadi 等人，2016），学习率为 $1\mathrm{e}-3$。 我们在每次迭代后从头开始训练 CNN。

我们使用 Gurobi (Inc., 2016) 框架来检查 (6) 中定义的 MIP 的可行性。 作为异常值的上限，我们使用 $\mathrm{\Xi }=1\mathrm{e}-4\times n$，其中 $n$ 是未标记点的数量。

5实验结果

我们使用三个不同的数据集测试了我们的算法的分类问题。 我们在 CIFAR (Krizhevsky & Hinton, 2009) 数据集上进行图像分类实验，在 SVHN(Netzer 等人, 2011) 数据集上进行数字分类实验。 CIFAR (Krizhevsky & Hinton, 2009) 数据集有两个任务；一种是超过 10 个类的粗粒度，一种是超过 100 个类的细粒度。 我们对两者都进行了实验。

我们将我们的方法与以下基线进行比较：$i)$随机：从未标记的池中随机选择要均匀标记的点。 $ii)$最佳经验不确定性： 遵循（Gal等人，2017）中的经验设置，我们使用最大熵、BALD和变异比率进行主动学习，将软最大输出视为概率。 我们只报告每个数据集表现最好的一个，因为它们的表现彼此相似。 $iii)$ 深度贝叶斯主动学习（DBAL）（Gal 等人，2017）： 我们执行蒙特卡罗 dropout 以获得改进的不确定性度量，并仅报告每个数据集的最大熵、BALD 和变异比率中表现最佳的采集函数。 $iv)$ 最佳 Oracle 不确定性： 我们还报告了一种性能最佳的预言机算法，该算法使用整个数据集的标签信息。 对于所有未标记的示例，我们用 $l({𝐱}_i,y_i,A_{{𝐬}^0})$ 替换不确定性。 我们通过将选择要查询的 $i^{th}$ 点的概率设置为 $p_i=\frac{l({𝐱}_i,y_i,A_{{𝐬}^0})}{{\sum }_{j}l({𝐱}_j,y_j,A_{{𝐬}^0})}$ 来从此函数的标准化形式中对查询进行采样。 $v)$k-Median：选择要标记的点作为k-Median（k等于预算）算法的聚类中心。 $vi)$批处理模式判别-代表性主动学习（BMDR）（Wang & Ye，2015）： 基于 ERM 的方法利用不确定性并最小化独立同分布之间的 MMD。 来自数据集和主动选择的点的样本。 $vii)$CEAL （王等人，2016）： CEAL (Wang 等人, 2016) 是一种专门针对 CNN 提出的弱监督主动学习方法。 我们将其纳入弱监督分析中。

我们对全监督模型的主动学习和弱监督模型的主动学习进行了实验。 在我们的实验中，我们从数据集中均匀随机采样的一小组图像作为初始池。 弱监督模型可以访问标记的示例以及未标记的示例。 完全监督的模型只能访问标记的数据点。 我们对初始标记点池进行五次随机初始化来运行所有实验，并使用平均分类精度作为指标。 我们绘制准确性与标记点数量的关系。 我们还将误差线绘制为标准差。 我们迭代地运行查询算法；换句话说，我们解决了精度与标记示例数量图上每个点的离散优化问题${\min }_{{𝐬}^{k+1}:|{𝐬}^{k+1}|\le b}{E}_{𝐱,y\sim p_{𝒵}}[l(𝐱,y;A_{{𝐬}^0\cup \mathrm{\dots },{𝐬}^{k+1}})]$。 我们在图4和4中展示了结果。

图3： 弱监督模型主动学习的结果（误差线为标准偏差）

图4： 全监督模型主动学习的结果（误差线为标准偏差）

图4和4表明我们的算法在所有实验中都优于所有其他基线；对于弱监督模型的情况，有很大的差距。 我们相信我们的方法在弱监督情况下的有效性归因于更好的特征学习。 弱监督模型提供更好的特征空间，从而产生准确的几何形状。 由于我们的方法是几何的，因此它在更好的特征空间下表现得更好。 我们还观察到，与 CIFAR-10 和 SVHN 相比，我们的算法在 CIFAR-100 中的效果较差。 使用我们的理论分析可以很容易地解释这一点。 我们对核心集损失的限制随着类别的数量而变化，因此类别越少越好。

一个有趣的观察是，最先进的批处理模式主动学习基线（BMDR （Wang & Ye，2015）)不一定比贪婪的表现更好。 我们认为这是因为它仍然使用不确定性信息，并且软最大概率不能很好地代表不确定性。 我们的方法不使用任何不确定性。 而且，以有原则的方式将不确定性纳入我们的方法是一个悬而未决的问题，也是一个富有成效的未来研究方向。 另一方面，基于纯聚类的批量主动学习基线（k-Medoids）也不是有效的。 我们相信这是相当直观的，因为簇句子很可能是初始 iid 很好地覆盖的点。 样品。 因此，这种基于聚类的方法无法对数据分布的尾部进行采样。

我们的结果表明，预言机不确定性信息和不确定性的贝叶斯估计都是有帮助的，因为它们比经验不确定性基线有所改进；然而，它们在批量设置中仍然无效，因为随机采样优于它们。 我们认为这是由于批量设置中主动学习所导致的查询标签的相关性。 我们通过 tSNE （Maaten & Hinton，2008） 嵌入进行定性分析，进一步研究这一点。 我们使用通过标记示例学习的特征来计算所有点的嵌入，并可视化通过我们的方法采样的点以及预言不确定性。 该可视化表明，由于样本之间的相关性，基于不确定性的方法无法覆盖证实我们假设的大部分空间。

k-中心解的最优性： 我们提出的方法使用 k-Center 问题的贪婪 2-OPT 解决方案作为初始化，并检查混合整数规划 (MIP) 的可行性。 我们使用定义的 MIP 的 LP 松弛并使用分支定界来获得整数解。 应该研究解决这个昂贵的 MIP 所获得的效用。 我们比较了 MIP与表5中2-OPT解决方案的运行时间。 我们还在 CIFAR-100 数据集上比较了最佳 k-Center 解决方案和图 6 中的 2-OPT 解决方案获得的精度。

(a) Uncertainty Oracle

(b) Our Method

Figure 5: tSNE embeddings of the CIFAR dataset and behavior of uncertainty oracle as well as our method. For both methods, the initial labeled pool of 1000 images are shown in blue, 1000 images chosen to be labeled in green and remaining ones in red. Our algorithm results in queries evenly covering the space. On the other hand, samples chosen by uncertainty oracle fails to cover the large portion of the space.

Table 1: Average run-time of our algorithm for $b=5k$ and $|{𝐬}^0|=10k$ in seconds.

Distance	Greedy	MIP	MIP
Matrix	(2-OPT)	(iteration)	(total)	Total
104.2	2	7.5	244.03	360.23

Figure 6: We compare our method with k-Center-Greedy. Our algorithm results in a small but important accuracy improvement.

如表5所示；尽管 MIP 的运行时间在最坏情况下不是多项式，但实际上对于 50k 图像的数据集，它会在易于处理的时间内收敛。 因此，我们的算法可以很容易地应用于实践。 图6表明，使用 2-OPT 解决方案时，精度会出现小幅但显着的下降。 因此，我们得出的结论是，除非数据集的规模限制太大，否则需要使用我们提出的最佳求解器。 即使准确性下降，我们使用 2-OPT 解决方案的主动学习策略仍然优于其他基线。 因此，我们可以得出结论，即使求解 MIP 不可行，我们的算法也可以扩展到任何数据集大小，且精度下降很小。

6结论

我们研究 CNN 的主动学习问题。 我们的实证分析表明，由于批量采样引起的相关性，基于经典不确定性的方法对 CNN 的适用性有限。 我们将主动学习问题重新表述为核心集选择，并研究 CNN 的核心集问题。 我们通过广泛的实证研究进一步验证了我们的算法。 三个数据集的实证结果显示了大幅度的最先进性能。

附录 A 引理 1 的证明

证明。

我们将首先证明在 $C$ 类上定义的 softmax 函数是 $\frac{\sqrt{C-1}}{C}$-Lipschitz 连续的。 很容易证明对于任何可微函数$f:{ℝ}^n\to {ℝ}^m$，

$${\Vert f(𝐱)-f(𝐲)\Vert }_2\le {\Vert J\Vert }_F^{\ast }{\Vert 𝐱-𝐲\Vert }_2\forall 𝐱,𝐲\in {ℝ}^n$$

其中${\Vert J\Vert }_F^{\ast }=\underset{𝐱}{\max }{\Vert J\Vert }_F$和$J$是$f$的雅可比矩阵。

Softmax 函数定义为

$$f{(x)}_i=\frac{\exp (x_i)}{\sum _{j=1}^C\exp (x_j)},i=1,2,\mathrm{\dots },C$$

为了简洁起见，我们将 $f_i(x)$ 表示为 $f_i$。 雅可比矩阵将是，

现在，上述矩阵的弗罗贝尼乌斯范数将是，

$${\Vert J\Vert }_F=\sqrt{\sum _{i=1}^C\sum _{j=1,i\ne j}^C{f}_i^2{f}_j^2+\sum _{i=1}^C{f}_i^2{(1-f_i)}^2}$$

很容易看出$f_i=\frac{1}{C}$是${\Vert J\Vert }_F^{\ast }=\underset{x}{\max }{\Vert J\Vert }_F$的最优解，因此，将$f_i=\frac{1}{C}$代入上式，我们得到${\Vert J\Vert }_F^{\ast }=\frac{\sqrt{C-1}}{C}$。

现在，考虑两个输入 $𝐱$ 和 $\widetilde{𝐱}$，这样它们在层 $d$ 的表示是 ${𝐱}^d$ 和 ${\widetilde{𝐱}}^d$ 。 让我们将任何卷积层或全连接层视为${𝐱}_j^d={\sum }_i{w}_{i,j}^d{𝐱}_i^{d-1}$。 如果我们假设${\sum }_i|w_{i,j}|\le \alpha \forall i,j,d$，对于任何卷积层或全连接层，我们可以说：

$${\Vert {𝐱}^d-{\widetilde{𝐱}}^d\Vert }_2\le \alpha {\Vert {𝐱}^{d-1}-{\widetilde{𝐱}}^{d-1}\Vert }_2$$

另一方面，使用 $|a-b|\le |\max (0,a)-\max (0,a)|$ 以及最大池层可以写成卷积层，这样只有一个权重是 $1$，其他权重是 $0$ ，我们可以说明 ReLU 和 max-pool 层，

$${\Vert {𝐱}^d-{\widetilde{𝐱}}^d\Vert }_2\le {\Vert {𝐱}^{d-1}-{\widetilde{𝐱}}^{d-1}\Vert }_2$$

结合soft-max层的Lipschitz常数，

$${\Vert CNN(𝐱;𝐰)-CNN(\widetilde{𝐱};𝐰)\Vert }_2\le \frac{\sqrt{C-1}}{C}{\alpha }^{n_c+n_{fc}}{\Vert 𝐱-\widetilde{𝐱}\Vert }_2$$

使用倒三角不等式作为

$$|l(𝐱,y;𝐰)-l(\widetilde{𝐱},y;𝐰)|=|{\Vert CNN(𝐱;𝐰)-y\Vert }_2-{\Vert CNN(\widetilde{𝐱};𝐰)-y\Vert }_2|\le {\Vert CNN(𝐱;𝐰)-CNN(\widetilde{𝐱};𝐰)\Vert }_2,$$

我们可以得出结论，对于任何固定的$y$和$𝐰$，损失函数是$\frac{\sqrt{C-1}}{C}{\alpha }^{n_c+n_{fc}}$-Lipschitz。 ∎

附录B定理1的证明

在开始证明之前，我们先陈述 Berlind & Urner (2015) 的权利要求 1。 修复一些$p,p^{\prime }\in [0,1]$和$y^{\prime }\in \{0,1\}$。 然后，

$$p_{y\sim p}(y\ne y^{\prime })\le p_{y\sim p^{\prime }}(y\ne y^{\prime })+|p-p^{\prime }|$$

证明。

我们将从边界 $E_{y_i\sim \eta ({𝐱}_i)}[l({𝐱}_i,y_i;A_{𝐬})]$ 开始证明。 我们有一个条件，表明 $\delta$ 球中 ${𝐱}_i$ 周围存在 ${𝐱}_j$，使得 ${𝐱}_j$ 具有 $0$ 损失。

$E_{y_i\sim \eta ({𝐱}_i)}[l({𝐱}_i,y_i;A_{𝐬})]$ $={\displaystyle \sum _{k\in [C]}}{p}_{y_i\sim {\eta }_k({𝐱}_i)}(y_i=k)l({𝐱}_i,k;A_{𝐬})$

$\stackrel{(d)}{\le }{\displaystyle \sum _{k\in [C]}}{p}_{y_i\sim {\eta }_k({𝐱}_j)}(y_i=k)l({𝐱}_i,k;A_{𝐬})+{\displaystyle \sum _{k\in [C]}}|{\eta }_k({𝐱}_i)-{\eta }_k({𝐱}_j)|l({𝐱}_i,k;A_{𝐬})$

$\stackrel{(e)}{\le }{\displaystyle \sum _{k\in [C]}}{p}_{y_i\sim {\eta }_k({𝐱}_j)}(y_i=k)l({𝐱}_i,k;A_{𝐬})+\delta {\lambda }^{\eta }LC$

由于滥用符号，我们用 $y_i\sim {\eta }_k({𝐱}_i)$ 表示 $\{y_i=k\}\sim {\eta }_k({𝐱}_i)$。 我们在$(d)$中使用权利要求1，在$(d)$中使用回归函数的Lipschitz性质和损失界。 然后，我们可以进一步将剩余项限制为：

${\displaystyle \sum _{k\in [C]}}{p}_{y_i\sim {\eta }_k({𝐱}_j)}(y_i=k)l({𝐱}_i,k;A_{𝐬})=$ ${\displaystyle \sum _{k\in [C]}}{p}_{y_i\sim {\eta }_k({𝐱}_j)}(y_i=k)[l({𝐱}_i,k;A_{𝐬})-l({𝐱}_j,k;A_{𝐬})]$

$+{\displaystyle \sum _{k\in [C]}}{p}_{y_i\sim {\eta }_k({𝐱}_j)}(y_i=k)l({𝐱}_j,k;A_{𝐬})$

$\le \delta {\lambda }^l$

其中最后一步来自这样一个事实：经过训练的训练分类器假设在点上有 $0$ 损失。 如果我们将它们结合起来，

$$E_{y_i\sim \eta ({𝐱}_i)}[l({𝐱}_i,y_i,A_{𝐬})]\le \delta ({\lambda }^l+{\lambda }^{\mu }LC)$$

我们进一步使用 Hoeffding’s Bound 并得出结论，概率至少为 $1-\gamma$，

$$\left|\frac{1}{n}\sum _{i\in [n]}l({𝐱}_i,y_i;A_{𝐬})-\frac{1}{|𝐬|}\sum _{j\in 𝐬}l({𝐱}_j,y_j;A_{𝐬})\right|\le \delta ({\lambda }^l+{\lambda }^{\mu }LC)+\sqrt{\frac{L^2\log (1/\gamma )}{2n}}$$

∎