🤖 machine learning

Active Learning with Low-Rank Structure for Data Selection

本文介绍了一种新的数据选择框架，该框架利用低秩近似和基于残差的采样来高效地选择加权数据子集，并针对具有全局代数结构的数据集，提供了相比于传统基于聚类的方法在理论保证和实证改进方面的优势。

原作者： Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

发布于 2026-06-16

📖 1 分钟阅读☕ 轻松阅读

原作者： Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你是一位试图创造世界上最棒的汤的厨师。你拥有一个巨大的仓库，里面装满了成千上万种不同的蔬菜、香料和高汤（这就是你的数据集）。为了做出完美的汤，你需要品尝并混合所有的食材。但问题在于：你的厨房很小，炉灶火力很弱，而且你只有几个小时的时间。用整个仓库来烹饪是不可能的。

你需要挑选出一小把完美的食材，它们能提供与整个仓库完全相同的风味。这就是**数据选择（Data Selection）**问题。

旧方法：按“距离”挑选

在很长一段时间里，顶尖厨师们使用一种叫做**聚类（Clustering）**的方法。想象你走进仓库，从每个不同的角落各取一种蔬菜。你从北边拿一个胡萝卜，从南边拿一个土豆，从东边拿一个辣椒，从西边拿一个西红柿。

其逻辑是：“如果我挑选彼此距离较远的物品，我就一定能涵盖所有基础。”这种方法对于简单的食谱效果尚可。但在现代世界，当数据变得巨大且复杂时（比如一个拥有数百万件物品的仓库），这种方法存在缺陷。它关注的是物品所处的位置，而不是它们实际发挥的作用。你最终可能会得到一袋看起来各不相同、但味道却完全一样的蔬菜，却遗漏了那个真正定义了汤之灵魂的神奇香料。

新方法：按“结构”挑选

本文的作者说：“别再盯着蔬菜站在哪里看。去观察风味的形状。”

他们提出了一种基于**低秩结构（Low-Rank Structure）**的新方法。
不要把你的汤料看作单个的物品，而要看作一个复杂的 3D 雕塑。尽管这个雕塑看起来很复杂，但它实际上可能仅仅是由几根主要的梁柱和支撑构成的。其余的部分只是装饰。

主梁（低秩）： 这些是风味最重要的方向。如果你掌握了这些，你就掌握了汤的精髓。
装饰（残差）： 这些是微小的、不重要的细节，它们不会显著改变味道。

作者的方法使用一种数学上的“X光检查”（称为低秩近似/Low-Rank Approximation）来寻找这些主梁。他们不再挑选距离较远的蔬菜，而是挑选那些支撑起风味结构主梁的特定食材。

他们是如何做的：“敏感度”量表

为了确定哪些食材是“主梁”，他们使用了一种名为**敏感度采样（Sensitivity Sampling）**的技术。

想象你有一个巨大的天平。你把一种蔬菜放上去，天平会告诉你：“如果你把这个留下来不吃，汤的味道会改变多少？”

如果味道变化很大，天平就会爆表。这种蔬菜具有高敏感度（非常重要）。
如果味道几乎没有变化，天平就保持低位。这种蔬菜是低敏感度（冗余的）。

他们的算法会计算仓库中每一项的得分，然后随机抽取一小组食材，但会根据它们的重要性进行加权。你更有可能选到那些“高敏感度”的物品。

实验结果：为什么这很重要

论文通过两种方式测试了这个想法：

信用卡测试： 他们尝试使用一个标准的金融数据集来预测谁会错过信用卡还款。他们的“低秩”方法挑选的一小组客户，在预测结果方面比传统的“聚类”方法或单纯的随机挑选表现得更好。
巨型大脑测试（大语言模型/LLMs）： 他们尝试教一个庞大的 AI（Llama3-8B）进行数学运算和回答问题。用整个数据集来训练 AI 需要耗费极长时间且成本高昂。通过使用他们的方法只挑选 6% 到 25% 的数据，他们训练出的 AI 比使用随机数据或旧的聚类方法得到的 AI 更加聪明。

核心启示

该论文声称，对于现代的大规模数据集，数据的“形状”（其代数结构）比数据点之间的“距离”更为重要。

通过专注于数据的主要结构梁而非仅仅试图覆盖所有的角落，你可以丢弃 90% 的数据，却仍然能训练出一个表现与使用全部数据一样好、甚至更好的机器学习模型。这就像是你意识到，你不需要品尝海洋中的每一粒盐才能知道汤有多咸；你只需要品尝那一勺能代表海洋真实特性的汤即可。

技术摘要：基于低秩结构的活跃学习数据选择

问题定义

本文探讨了机器学习中的数据选择问题，特别是如何识别一个规模较小且具有代表性的数据子集（即核心集/coreset），从而在不显著损害性能的前提下实现高效的模型训练。虽然现代数据集和基础模型推动了技术进步，但其训练和微调过程也带来了高昂的计算成本。

现有的方法（如 Sener 和 Savarese [SS18] 以及 Axiotis 等人 [ACH+24]）依赖于应用于数据嵌入（embeddings）的基于聚类的启发式算法（例如 $k$ -center 或 $k$ -means）。这些方法假设数据具有内在的几何结构，其中多样性和点之间的距离是驱动信息量的主要因素。然而，作者认为，许多现代数据集（特别是在高维空间中）表现出更符合低秩近似（如主成分分析 PCA）的全局代数结构，而非局部几何聚类。聚类方法可能无法捕捉到主要的方差方向，从而可能遗漏对模型训练至关重要的组成部分。

方法论

本文提出了一种基于低秩近似和基于残差的敏感度采样的新型数据选择框架。其核心思想是优先保留数据的占主导地位的光谱方向，而非仅仅最大化几何多样性。

理论框架

该方法建立在行子集选择（Row Subset Selection）问题和保损失核心集构建（loss-preserving coreset construction）的基础之上。作者引入了假设 2.1，该假设认为对于一个具有嵌入矩阵的数据集 $D$ ，损失函数 $\ell$ 可以相对于一个 $k$ 维子空间 $V$ （由前 $k$ 个奇异向量或主成分构成）进行分解：

正交惩罚： 对于位于子空间 $V$ 之外的点 $y$ ，其损失偏差受其相对于 $V$ 的正交残差分量 $r(y)$ 的范数平方限制，并由常数 $\lambda$ 进行缩放。
子空间近似： 在子空间 $V$ 内，损失可以被近似为沿基方向的加权损失之和，并由常数 $\gamma$ 进行缩放。

这一假设形式化了这样一种直觉：即与主导低秩子空间正交的方向对损失的贡献较小或信息量较低，这一特性在 PCA、矩阵补全和低秩自适应（LoRA）等任务中均有观察。

算法：敏感度采样

所提出的算法（算法 2）通过以下步骤构建加权核心集 $S$ ：

低秩草图（Low-Rank Sketch）： 计算数据集的秩- $k$ 近似（例如通过 SVD），以定义子空间 $V$ 及其基 $\{v_1, \dots, v_k\}$ 。
分解： 对于每个数据点 $x$ ，将其分解为在 $V$ 上的投影 $v(x)$ 以及与其正交的残差 $r(x)$ 。
敏感度得分计算： 为每个点计算一个结合了以下内容的敏感度得分 $\sigma(x)$ $σ (x)$ ：
- 沿基方向的加权损失： $(\gamma + 1)\sum \alpha_i^2 \ell(v_i)$ 。
- 针对残差的惩罚： $\lambda \|r(x)\|_2^2$ 。
- 与基中最大损失相关的常数项。
采样： 按归一化后的敏感度得分 $p(x) = \sigma(x) / \sum \sigma(y)$ 对数据集进行有放回采样。
加权： 为采样的点分配权重 $w(x) = 1/(s \cdot p(x))$ ，以确保估计量是无偏的。

核心贡献

理论保证（定理 2.2 & 2.3）： 本文证明了一个大小为 $\tilde{O}(k + 1/\varepsilon^2)$ 的加权子集可以在 $(1 \pm \varepsilon)$ 的相对误差范围内逼近全数据集的平均损失，该误差包含一个与最优秩- $k$ 近似代价 $\Phi_k(D)$ 成正比的加性项。
- 定理 2.2 保证了这对于一般的加权子集成立。
- 定理 2.3 将其扩展到行子集选择，确保所选子集由输入数据集中的实际数据点组成。
- 误差界限显式地依赖于 $\Phi_k(D)$ ，这表明具有强低秩结构的数据集会产生更紧凑的界限和更准确的核心集。
算法创新： 作者引入了一种利用低秩结构来计算重要性得分的敏感度采样算法，这与基于几何距离度量的聚类方法不同。
实证验证： 该框架在表格数据（信用卡违约数据集）以及大规模语言模型微调（在 GSM8k、ViGGO 和 SQL 任务上的 Llama3-8B 和 Qwen2.5-3B）上得到了验证。

实验结果

论文将所提出的**低秩敏感度采样（Low-rank SS）**与几种基准方法进行了对比：均匀采样、 $k$ -Center、基于聚类的敏感度采样以及图割（Graph Cut）。

表格数据（信用卡数据集）：
- Low-rank SS 实现了最低的平方和近似误差，在小样本量（ $s=1000$ ）下，其误差比随机采样降低了一个数量级，比聚类方法降低了约 50%。
- 在下游逻辑回归任务中，Low-rank SS 在 $s=5000$ 时达到了高达 74% 的测试准确率，优于聚类方法（70%）和随机采样（67%）。
LLM 微调（Llama3-8B & Qwen2.5-3B）：
- 在 GSM8k、ViGGO 和 SQL 任务上，Low-rank SS 一致优于均匀采样和基于聚类的采样方法。
- 例如，在 25% 数据压缩率下的 ViGGO 任务（使用 Llama3-8B）中，Low-rank SS 实现了 77.6% 的准确率，而基于聚类的 SS 为 74.9%。
- 可迁移性： 使用较大模型（Llama3-8B）选出的子集成功迁移到了较小模型（Qwen2.5-3B）中，甚至优于直接由目标模型选出的子集，这表明低秩准则捕捉到了数据的内在属性。
- 消融实验： 该方法对基选择的选取表现出鲁棒性，其中杠杆得分（leverage score）采样表现最佳，但即使是均匀基选择也能产生极具竞争力的结果。
结构分析： 在 GSM8k 上的实验表明，与聚类相比，该数据集在低秩假设下的近似误差更低，验证了假设 2.1 的适用性。

重要性与主张

本文声称提供了一种稳健且高效的替代方案，用于取代朴素的下采样和基于聚类的数据选择，特别是在高维和大规模场景下。

理论贡献： 它建立了在低秩损失假设下的数据选择严谨保证，将核心集质量直接与数据集与低秩结构的对齐程度（ $\Phi_k(D)$ ）联系起来。
实际影响： 作者证明，使用预训练模型（如 BERT）生成的简单嵌入足以近似进行选择信息点所需的低秩结构，即使对于更大的目标模型（LLMs）也是如此。
效率： 该方法避免了在整个数据集上计算不确定性得分的计算限制（这是主动学习中常见的做法），也避免了基于聚类的批处理选择中的冗余问题。
谦逊态度： 作者承认聚类在某些情况下仍有价值，但他们的低秩方法在数据呈现全局代数结构的关键的大规模模型训练中，提供了更可靠的基础。他们并非声称具有普遍的最优性，而是在数据具有显著低秩结构的设定下实现了显著提升。