【论文笔记02】Active Learning For Convolutional Neural Networks: A Core-Set Approch，ICLR 2018
本文探讨了在卷积神经网络（CNN）中使用主动学习进行核心集合选择的问题。传统主动学习方法在每次迭代中查询多个数据点导致冗余和高计算成本，因此提出了基于核心集合的选择框架来优化查询过程。该框架通过将核心集合选择问题转化为k-中心问题，并采用贪心算法和混合整数规划（MIP）求解，以最小化覆盖半径并提高模型性能。实验表明该方法显著优于现有图像分类技术，并且能够更高效地利用无标签数据进行训练。
目录导引
系列化传送
-
3 相关工作综述
- 3.1 主动学习策略
- 3.2 核心集选择方法
- 3.3 弱监督深度学习方法
- 3.1 主动学习策略
-
Approach
-
Problem Formulation
-
Active Learning Framework: Set Cover Approach
-
Core-Sets in Convolutional Neural Networks
-
Addressing the K-Center Challenge
-
4.3.1 K-Greedy Algorithm
-
Optimization Strategies
-
5 Experiments
-
- CIFAR-10 CIFAR-100 SVHN
-
Reference
-
系列传送
论文笔记01
论文笔记02
论文笔记03
论文笔记04
Active Learning
论文笔记01
论文笔记n
Transfer Learning
【Differential Privacy】
【Universum Learning】
A Core-Set Approach
该文章包含大量数学证明，对于对数学细节感兴趣的读者，建议访问原文附录部分以详细研究这些定理和引理的证明过程。此外，在本文中引用了许多关键性的结论，并其中一些结果源自其他文献中的相关论证。
从第四节开始是重点，笔者花费了一定时间才理解作者的优化思路。
1 Abstract
基于通用架构的方法，在充足的标注数据集上进行了训练
基于实证研究的方法表明，在将主动学习经验规则应用于基于批量查询的卷积神经网络（CNN）时会遇到效率问题。受到这些方法局限性的启发，在本文中我们将主动学习问题归类为核心集合选择 core-set selection问题。具体而言,文章将主动学习过程视为从一个数据集（data set）中选择具有很强代表性的子集（subset），使得模型在此子集上的训练结果能够在剩余的数据点上展现出很好的泛化能力（generalization capability）。
作者进一步提出了一个新的理论成果。通过分析数据点的几何结构（geometry of the datapoints），该理论模型能够有效地描述任意被选中子集的表现特性。在主动学习框架中设计算法时，在选定特征描述（characterization）下实现最优表现是关键目标。实验证明了该方法在图像分类任务中展现了显著优势。
2 Introduction
2.1 CNN
- 最主要的缺点： 大量参数需要大量有标记数据训练
2.2 AL
- 目标：在标记资源受限的情况下，在较高准确率的前提下完成任务所采用的数据收集与标注策略是什么。
- 特点：主动学习算法通过逐步推进的方式运行，在每一轮中从候选数据中选出一批进行标注。
- 局限：现有研究发现，在CNN架构下应用的主动学习算法效率较低。研究表明，在批量抽样的过程中导致了样本间的高度相关性。
在CNN上应用主动学习这一任务需要有组织地从大量数据中选择具有代表性的样本进行标注反馈。与传统分类方法不同之处在于，在这种情况下系统需要基于动态更新的知识库进行学习和优化。
- 由于采用的是局部优化策略（local optimization strategies），单一数据样本 的引入反而不会对卷积神经网络的精度产生具有统计显著性的提升。
- 每次迭代需要将模型在新的有标签数据集上被训练至收敛状态，并准备好进行下一轮查询。而对于CNNs而言，这种做法会导致计算成本过高。
关于数据相关性 ，我的理解是：
使模型在单次查询中处理多个样本点，并且倾向于选择处于模糊边界但又具有相似特性的数据点进行集中式查询。这种做法导致了一定程度上的冗余，并且这些数据点之间存在高度关联。
2.3 Tailor an al method
- 做法： 核心集选择方法
- 目标： 为了应对未标记核心集问题在CNN中的挑战，在数据点几何关系的基础上提供了一种平均损失在任意子集上的严格界限，并将其与剩余数据点联系起来。作为主动学习算法的一部分，在这种框架下选择了能够使这一界限最小化的子集。此外，在最小化这一界限方面等价于k-Center问题（Wolf, 2011），因此我们采用了组合优化问题的有效近似解法。
- 实证： 进一步研究了我们所提出的算法在图像分类问题中的行为表现。通过使用三个不同数据集进行实验分析，在实际应用中展现了显著的性能优势。
3 Related Works
3.1 Active Learning
3.2 Core-Set Selection
因为为了将主动学习任务归类为此类问题——核心集合选择问题（Core-Set Selection），文献中与之最接近的是核心集合选择这一概念。从一个完全标记的数据集中挑选出一个子集使得模型在该子集上的训练效果尽可能接近其在完整数据集上的表现。作者总结了相关的具体算法。
- 该方法中采用的核心集
- 该方法中采用的核心集同时适用于k均值聚类和k中心点聚类
- 目前并未开发出针对卷积神经网络（CNNs）的核心集
无监督子集选择算法 与作者的研究方向最为接近，在研究中它基于设施位置问题求解数据集的一个多样性覆盖方案。然而，在这一领域中作者提出了一种创新性方法：采用了与现有方法不同的公式进行计算。具体而言，在原先采用的是min-sum形式的基础上，
作者则采用了minimax的形式展开研究工作。
值得注意的是，
这是作者首次将该类方法应用于主动学习领域，
并在针对卷积神经网络（CNNs）方面提供了理论支持。
3.3 Weakly-Supervised Deep Learning
4 Method
4.0 Problem Definition
| Notation | Explanation | |
|---|---|---|
| X | 特征空间 | |
| Y={1,...,C} | 标签空间 | |
| l(·,·;w) : X \times Y -> R | 损失函数 | |
| \eta_c(x)=p(y=c|x) | 各类专用的回归函数，\lambda^\eta-Lipschitz连续 | |
| Z = X \times Y | 总体 | |
| \{x_i, y_i\}_{i\in[n]} | 从总体概率分布p_z中i.i.d抽出n个无标签数据 | |
| s^0=\{s^0(j)\in[n]\}_{j\in[m]} | 初始化有标签数据集，大小为m | |
| A_s | 用有标签数据集s进行训练得到的参数 | |
| b | 每一轮查询的预算，即查询的个数 |
在池化主动学习的第一阶段查询中，目标被明确为
其目标即为求解满足约束s^{k+1}：|s^{k+1}| \le b下的最小化问题：
\min_{S^{k+1}\subseteq Z} E_{x,y\in Z}[l(x,y; A_{S^0 \cup S^1 \dotsb S^{k+1}}}]\tag{2}
在每次查询完毕后，都需要对模型重新进行训练，并随后进行评估。其中的训练环节可采用以下两种方法：一种是基于批量数据的全量训练方式；另一种是分阶段微调策略。
- 纯监督
- 半监督，把 \in [n] and \notin s的无标签数据也拿来用
4.1 Active Learning as a Set Cover
该表达式表明，
E_{(x,y)\sim Z}[l(x, y; A_s)] \leq \\ \left| E_{(x,y)\sim Z}[l(x, y; A_s)] - E_{(x_i, y_i)\sim S}[l(x_i, y_i; A_s)] \\ \right| + \\ \text{{该样本集的平均损失}} + \\ \\left| E_{{(x_i, y_i)}_{{i=1}}}^{{n}}[l(x_{{i}}, y_{{i}} ; A_{{s}})] - E_{{(x_j, y_j)}_{{j=1}}}^{|s|} [l(x_{{j}}, y_{{j}} ; A_{{s}})] \\right| \tag {{3}} 第一部分：**generalization performance** 基于同分布假设，在本研究中表现出了良好的泛化能力。此外，在理论层面已有深入研究（Xu & Mannor, 2012），从而能够较为准确地界定这一类误差项的上界。 第二部分：**training loss** 其训练误差可以达到极低水平。 第三部分：**core-set discrepancy** 本文重点考察核心集的性质及其对模型性能的影响因素。 后文作者假设**training error == 0** ，**generalization error** 也忽略了 依据文中所述的定理基础之上，在此问题中我们能够为**core-set error** 设定一个相应的上限边界值。
|\frac{1}{n}\sum\limits_{i=1}^{n} l(x_i, y_i; A_s) - \frac{1}{|s|}\sum_{j \in s} l(x_j, y_j; A_s)|
\leqslant
\delta (\lambda^l + \lambda^\mu LC)
+
\sqrt{\frac{L^2 \log(1/\gamma)}{2n}}
\tag{4}
其中损失函数 l(·,y;w)，当 y 和 w 固定时符合 λ^l-Lipschitz 连续性要求；回归函数满足 λ^η-Lipschitz 连续性；s 是训练集 {x_i,y_i} 的 δ_s 网络覆盖，并且以概率 1−γ 满足 l(x_{s(j)},y_{s(j)};A_s)=0 对所有 j∈[m]成立。 基于假设 training error == 0 ，左边表达式即直接表示为 $\frac{1}{n}\sum\limits_{i \in [n]} {l({x_i},{y_i};{A_s})}$ 上界部分可以简略地写成阶的形式，文中还给出了这张可视化图：  这些蓝色标记的样本属于集合 $s$ 中。 而红色标记的样本则来自集合 $[n]$ 中。 对于每个蓝色样本，在其周围构建一个半径为 $\delta_s$ 的邻域区域，则这些邻域区域的并集即可覆盖整个样本空间。 该上界主要取决于参数 $\delta_s$ 和统计量 $\sqrt{\frac{1}{n}}$, 因此在实际问题中数据量通常固定（即$n$"是一个常数），因此我们只需关注如何选择合适的$\delta_s$"来最小化总体损失。 #### 4.2 Core-Sets for CNNs 最后目标就转化为使δ涵盖最小化：
\min _{{s1}:|{s1} \le b|}{\delta _{{s^0} \cup {s^1}}}
更具体地说，这一过程可以通过以下公式实现：
\mathop {\min }\limits_{{s1}:|{s1} \le b|} \mathop {\max }\limits_i \mathop {\min }\limits_{j \in {s^1} \cup {s^0}} \Delta ({x_i},{x_j}) \tag{5}
其中， - ${s^1}$表示满足$|{s^1}| \le b$的所有可能集合， - $\Delta ({x_i},{x_j})$代表数据点$x_i$与$x_j$之间的距离， - 公式旨在找到在约束条件下使最大最小距离最小化的最优解。 使覆盖半径δ达到最小值的过程就是使得无标签数据与有标签数据之间最近距离的上确界被最小化。 #### 4.3 Solving the K-Center Problem ##### 4.3.1 K-Greedy Algorithm 这个问题属于NP类型，在采用K-Greedy算法的情况下我们可以找到一个2-OPT解这种解法具有理论基础保证即最大最小距离不会超过两倍的最优值具体而言当设定OPT为min{ s^1:|s^1|≤b} max_i min_{j∈s^1∪s^0} Δ(x_i,x_j)时我们能够证明max min Δ(x_i,x_j) ≤ 2*OPT因此该方法在寻找最优解的过程中呈现出一种折中策略其结果在OPT与2OPT之间运行 贪心算法流程图：  在一个迭代周期内选择b个无标记样本，并依次进行b次选择操作。在每次操作中会选取当前具有最大距离的无标记样本并将其纳入现有标注样本集合中。需要注意的是，在这种机制下进行的选择方式与一次性选取b个样本存在本质区别。 ##### 4.3.2 Optimization 本研究涉及混合整数规划问题（MIP）。 其中包含参数$\delta$的该规划模型，在存在可行解时其最优值满足OPT ≤ δ。 此外，在这一框架下允许通过参数$\delta$确保标签数据覆盖$\Xi$个关键点而不遗漏。 同时以增强模型鲁棒性为目标，在一定程度上排除异常值的影响。 2. 利用二分查找算法（divide and conquer algorithm）确定OPT的精确值 3. 将OPT的精确值纳入规划问题中进行求解，并确定哪些点应作为带有标签的数据进行更新迭代 MIP具体形式如下：  对其中的符号做如下解释 |Notation|Explanation| |---|---| |$u_j$|当一个数是有标签的，$u_j=1$| |$\xi_{i,j}$|当数据 $i$ 离有标签数据 $j$ 最近且不在 $\delta$ 覆盖内 $\xi_{i,j}=1$| |$w_{i,j}$|数据 $i$ 离有标签数据 $j$ 最近，被覆盖或者属于上面那类| |$\Delta(x_i,x_j)$|两个数据输出的概率分布之间的$l_2$距离| |$\Xi$|可以当作$outlier$不被覆盖的个数| 算法结构如下：  首先利用贪心算法构建了一个初始查询集合$s_g$。随后采用二分查找的方法确定了OPT的真实值，并将其代入MIP模型中进行求解运算以获取所有满足条件的变量索引$\{i | u_i = 1\}$ 对其中所涉及的二分查找方法进行简要介绍。在算法流程中定义如下：其中 ub 被定义为 OPT 的 upper bound（即上界），同理 lb 则被定义为 OPT 的 lower bound（即下界）。由于采用贪心策略可得 δ_{2-OPT} ≤ 2OPT，则满足以下不等式关系：δ_{2-OPT}/(2) ≤ OPT ≤ δ_{2-OPT}。由此可得将上述两式中的两端分别设为 ub 和 lb 初始取值后，在满足 ub=lb 时确定了 OPT 值随后通过不断缩小区间范围执行二分查找，在满足 ub=lb 时确定了 OPT 值。 在查找过程中，在遇到一个可解的MIP问题时（即存在下界和上界的情况下），我们可以观察到当前最优解OPT位于区间[ lb , (lb + ub)/2 ]之间。因此，在这种情况下我们需要将上界ub减小；反过来也是如此。这种机制本质上就是条件判断的实现方式。 ### 5 Experiments #### CIFAR-10 CIFAR-100 SVHN  该对比图展示了作者提出的方法与其他现有方法的性能比较。具体而言，在上半部分展示的是弱监督学习框架，在标注数据集$s$的基础上还引入了$n$s的信息作为辅助训练素材；下半部分则为一种纯监督学习方案，在这种情况下仅依赖标注数据集$s$进行模型训练和优化。  通过可视化图示对比可知，在 $Feature Map$ 展现结果方面本文提出的方法相较于不确定性采样查询法具有显著优势。具体而言，在 $Feature Map$ 平面上我们的方法能够呈现出更为均衡的分布特征，并且有助于整体分布特征的展现。相较于传统方案而言本方法不仅在结果呈现上更为清晰而且视觉效果更加令人满意。 右下角的图说明对于贪心算法2-OPT solution的优化是有明显效果的。 ## Reference [1] Sener O, Savarese S. Active learning for convolutional neural networks: A core-set approach[J]. arXiv preprint arXiv:1708.00489, 2017. [2] https://arxiv.org/pdf/1708.00489.pdf),