GIST智能采样算法：解决数据多样性与效用性平衡难题

我们推出了GIST算法，这是一种能够为选择高质量数据子集提供可证明保证的新颖算法，可以最大化数据多样性和数据效用性。

现代机器学习已经实现了前所未有的性能，但代价是需要处理日益庞大和复杂的数据集。从大语言模型到计算机视觉系统，都面临着一个共同挑战：如何处理大量成本高昂的数据。

这使得子集选择变得必要——即从完整数据集中选择一个较小的、具有代表性的数据点组用于典型的训练任务（而非微调）。问题在于：我们如何确保这个子集包含足够的信息来训练准确的模型？

在NeurIPS 2025上，我们介绍了贪婪独立集阈值算法GIST，这是一种新颖的算法，通过平衡数据"多样性"（确保所选数据不冗余）和数据"效用性"（与任务相关且有用的数据）来解决这个问题。GIST不仅在图像分类等最先进的基准任务上表现出色，而且在解决方案质量方面提供数学保证。

数据选择的核心挑战

在选择数据子集时，研究人员必须平衡两个经常冲突的目标：多样性和效用性。强调数据多样性确保所选点不冗余。效用性衡量所选子集的整体有用性或信息价值。

对于多样性，我们专注于最大化任意两个选定数据点之间的最小距离（通常在嵌入空间中），也称为最大最小多样性。如果你选择两个非常相似的数据点（例如，两张几乎相同的金毛猎犬图片），你的多样性就很低。最大最小多样性迫使你选择彼此尽可能远的点，最大限度地减少冗余并确保对数据景观的广泛覆盖。对于效用性，我们专注于单调子模函数类，旨在最大化子集覆盖的总独特信息。

困难在于结合这两个目标。纯粹的最大最小策略可能选择多样但最终无关的数据点，而纯粹的效用策略可能选择一个紧密、高度相关但冗余的点簇。找到既最大分散又最大信息化的子集是一个复杂的组合问题，已知为NP难题，意味着没有算法能够高效地找到最佳解决方案，特别是对于大规模数据集。

这种内在冲突需要巧妙的近似策略。

GIST的创新解决方案

由于找到完美子集不现实，目标转向找到具有可证明近似保证的算法——一个数学安全网，确保解决方案始终接近真正的最优解。这就是GIST提供突破性解决方案的地方。

GIST将多样性-效用性挑战分解为一系列更简单但相关的优化问题：

GIST首先暂时隔离多样性组件。GIST不是试图最大化所有点之间的最小距离（困难部分），而是解决一个更简单的问题："对于某个固定的最小距离，我们能选择的最佳数据子集是什么？"

通过固定所需的最小距离，GIST使用图处理数据，其中两点仅在距离小于指定距离时才连接。在这个图中，任何两个连接的点都被认为过于相似而无法进入最终子集。

GIST寻找尚未在其他人"泡泡"内的最高分数点。然后算法挑选得分最高的"VIP"数据点（带数字的点），并在其周围画一个"禁区"，以确保最终选择既高质量又多样。数字越高，该特定数据片段对学习越有价值。

GIST然后寻找可以选择的最大效用子集，其中该图中没有两个点连接：经典的最大独立集问题。想象规划一个晚宴，某些客人不能坐在一起。你的目标是邀请尽可能有趣的一群人，但必须遵循一个规则：餐桌上没有两个人可以有冲突。这是一个巨大的难题，因为选择一位客人可能"阻止"你邀请其他三位高兴趣的人。要找到最佳组合，你必须检查指数数量的分组，这就是为什么它被认为是计算中最困难的问题之一。

由于最大独立集问题本身是NP完全的（意味着广泛认为不存在高效算法为大规模数据集找到绝对"完美"答案）且不允许合理的近似算法，GIST使用精心构造的双标准贪婪算法来高效近似解决方案。它遍历许多可能的距离阈值，解决相应的独立集问题，并最终选择在所有阈值中找到的最佳解决方案。对于最优解实现的任何最小距离d，GIST在距离阈值d/2处实现与最优效用相当的效用。

双标准贪婪算法就像一个系统的"调节旋钮"，找到数据多样性和价值之间的正确平衡。它不是猜测，而是分析所有数据点之间的实际距离来创建潜在间距规则列表。然后逐一测试这些规则：对于每个规则，它"贪婪地"抓取能找到的最有价值的点，前提是它们与已选择的点不太接近。通过在每个相关距离上运行此过程并比较结果，算法识别出特定的"最佳点"，该点捕获最有用的信息，同时确保数据尽可能分散。

通过巧妙地近似一系列这些最大独立集问题，GIST成功地满足了效用目标，同时尊重最小多样性要求。

理论保证和实验结果

我们的理论结果是最重要的发现：GIST是第一个为这种多样性-效用权衡提供强有力、可证明保证的算法。GIST算法保证找到一个数据子集，其价值至少是绝对最优解价值的一半（详见论文）。这种强保证为从业者提供了必要的数学安全网，确保算法在最大化效用的同时确保多样化之间做出高效权衡。此外，我们证明找到超过最优值0.56分数的子集是NP难的。

我们还在各种机器学习应用中针对最先进基准评估了GIST，重点关注多样性和效用性都至关重要的场景。

在使用ResNet-56模型在ImageNet等数据集上的实验中，GIST在单次子集选择中表现出显著优势。单次数据下采样一步减少数据集的体积——通常是图像、信号或高维数据——同时保留关键信息。与迭代或多阶段过程不同，这种方法最大化速度和效率，通常用于减少计算负担或优化图形相关任务中的渲染性能。

尽管底层问题复杂，GIST的实际子集选择步骤非常快：其运行时间相比训练最终机器学习模型所需的数小时甚至数天通常可以忽略不计。这种速度使GIST在具有数十亿数据点的大规模训练管道中集成变得实用。

我们还在YouTube首页排名团队中观察到最大最小多样性方法的价值，该团队采用了类似原理来增强视频推荐的多样性，从而改善了长期用户价值。

智能采样的未来

结合竞争优化目标的挑战——如最大化总效用同时保持最大多样性——一直是计算科学中的长期障碍。GIST算法通过提供单一、高效的框架成功解决了数据选择的这一基本权衡。

通过将具有挑战性的多样性-效用权衡问题分解为一系列更简单、可近似的任务，GIST为机器学习社区提供了一个可证明有效的工具。这项研究为下一代可扩展AI系统建立了强大基础，保证随着数据继续增长，我们仍然可以在既最大信息化又最小冗余的子集上训练模型。要点是，GIST确保我们智能地采样数据。

Q&A

Q1：GIST算法是什么？它能解决什么问题？

A：GIST是贪婪独立集阈值算法，是一种新颖的数据子集选择算法。它能够在数据多样性和效用性之间找到最佳平衡，确保选择的数据子集既不冗余又具有高信息价值，并提供可证明的数学保证，其解决方案价值至少是绝对最优解的一半。

Q2：GIST算法的运行速度如何？是否适用于大规模数据？

A：GIST算法运行非常快，其子集选择步骤的运行时间相比机器学习模型训练所需的数小时甚至数天通常可以忽略不计。这种高效性使得GIST非常适合集成到具有数十亿数据点的大规模训练管道中，为实际应用提供了很好的可行性。

Q3：GIST在实际应用中表现如何？有哪些成功案例？

A：GIST在多个基准测试中表现出色，特别是在ImageNet数据集上使用ResNet-56模型的实验中，GIST在单次子集选择任务中显著优于现有方法，持续选择出能够提高模型准确性的子集。YouTube首页排名团队也采用了类似的最大最小多样性原理来增强视频推荐多样性，改善了长期用户价值。