🤖 AI

Unifying and Optimizing Data Values for Selection via Sequential Decision-Making

本文通过将问题重新表述为可通过动态规划解决的序列决策任务，统一了数据选择与数据估值，揭示了现有方法（如 Data Shapley）仅为近视近似，并提出了一种可扩展的基于二分图的代理方法，该方法在经典机器学习和大规模大语言模型微调中均实现了可证明的性能提升。

原作者： Hongliang Chi, Qiong Wu, Zhengyi Zhou, Jonathan Light, Emily Dodwell, Yao Ma

发布于 2026-06-01

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Hongliang Chi, Qiong Wu, Zhengyi Zhou, Jonathan Light, Emily Dodwell, Yao Ma

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

大局观： “数据自助餐”问题

想象你是一位正在准备盛大宴会的厨师。你拥有大量的食材（你的数据），但你只有时间烹饪几道菜肴（你的模型）。你想挑选出最完美的食材，以做出最美味的佳肴。

问题在于：并非所有食材都是平等的。 有些新鲜且至关重要；有些则陈旧或冗余。在人工智能领域，我们把弄清楚哪些数据点是“最好的”这一过程称为数据估值（Data Valuation）。

长期以来，科学家们一直使用复杂的数学方法（基于博弈论）来为每种食材分配一个“分数”。他们认为：“如果我只挑选得分最高的 100 种食材，我就能做出最好的餐点。”

这篇论文指出，这种方法是有缺陷的。 这就像是在通过观察单个食材本身来挑选汤里的最佳配料，却完全没有考虑它们在锅里是如何协同作用的。

核心思想：是一个序列，而非一个列表

作者认为，挑选数据并不像制作一份静态的购物清单。它更像是搭建积木塔或者一步步攀登高山。

旧方法（静态列表）： 你给每个积木打分，按重量从重到轻排序，然后抓取前 10 个。
新方法（序列）： 你意识到挑选积木的顺序至关重要。你选的第一个积木奠定了基础。第二个积木取决于第一个。如果你先选了一个重的积木，可能会让后面较轻的积木变得毫无意义。

作者将此重新定义为一个**序列决策（Sequential Decision-Making）**问题。他们问道：“挑选这些数据点的完美顺序是什么，才能让我的模型在每一个阶段（1 个点、2 个点、10 个点、100 个点）都表现得尽可能出色？”

“近视”错误（只看下一步）

论文解释说，流行的算法（如 Data Shapley）是“近视”的。

类比： 想象你正在黑暗的森林中寻找宝藏。一个“近视”的人只看脚下的地面，看看有没有闪亮的硬币。他捡起硬币就走，从不抬头看前方，从而错过了如果向左走三步就能发现一个金库的机会。
论文的观点： 现有的数据估值方法就像那个近视的步行者。他们只看一个数据点的眼前价值，并假设这就是全部。他们没能看到，现在挑选这个点可能会破坏你稍后挑选一个更好的数据点的能力。

作者展示了这些“近视”的方法实际上只是线性近似。它们试图用一条直线去解决一个复杂的曲线问题。如果地形是平坦的（简单数据），这种方法还可以；但当地形变得崎岖复杂时（复杂数据），它就会彻底失效。

解决方案：“二分图”地图

由于计算对于海量数据集而言，寻找每一个可能的组合的“完美顺序”在数学上是不可能的（这会耗费比宇宙年龄还要长的时间），作者需要一个捷径。

他们构建了一个二分图（Bipartite Graph）。

类比： 想象你有一组实习生（你的数据）和一组测试题（你希望模型学习的内容）。
你不需要去猜测哪个实习生更“聪明”，而是画出线条，将实习生连接到他们能够正确回答的特定测试题上。
策略： 你不是先选最“聪明”的实习生，而是先选那个能回答最多独特问题（即其他人尚未覆盖的问题）的实习生。
- 实习生 A 知道 5 道题。
- 实习生 B 也知道 5 道题，但其中 4 道与实习生 A 知道的一样。
- 实习生 C 知道 3 道题，但这些题都是其他人都不懂的题目。
获胜者： 你首先选择实习生 C，因为他们为团队增加了最多的新价值。然后，你再选择下一个能填补剩余空白的人。

这种方法被称为覆盖率（Coverage）。它确保你在建立一个多样化、全方位的团队，而不是仅仅挑选那些可能都在做同样几件事的“高分选手”。

研究发现（结果）

作者在许多不同的数据集上，将这种新方法与旧的“近视”方法进行了对比测试，包括：

标准机器学习： 挑选数据来训练预测电价或识别手写数字的模型。
大语言模型 (LLMs)： 挑选指令来微调大型 AI（如 Llama 3）。

结果显示：

差距： 旧方法明显逊色于理论上的“完美”顺序。它们浪费了很多性能潜力。
修复方案： 他们的“二分图”方法缩小了这一差距。它找到了表现更好的数据子集，尤其是在早期阶段（当你拥有的数据点非常少时）。
为什么重要： 在现实世界中，你通常无法负担使用所有数据。你需要的是那最精华的 10% 或 1%。这种方法能比以往更有效地帮你找到那顶尖的 10%。

一句话总结

这篇论文证明了挑选最佳数据是一个循序渐进的拼图问题，而非简单的排名列表，并提供了一种新的“基于覆盖率”的地图，帮助你挑选最具独特性和价值的数据点，从而更快地构建出更聪明的 AI。

技术摘要：通过序列决策统一并优化数据选择的数值

问题陈述

数据选择是数据估值的一个关键下游应用，旨在识别能够最大化模型性能的最优训练数据子集。虽然现有的数据估值方法（如 Data Shapley、Banzhaf、Beta Shapley）提供了基于合作博弈论的量化样本贡献值的原则性方法，但其在“选择”方面的理论基础仍有待深入探索。具体而言，这些方法并未针对选择目标进行显式优化，而选择目标要求最大化所有可能子集规模下的累积性能（选择曲线）。本文指出，在存在高数据冗余或收益递减（次模性）的情景下，现有估值方法的实际表现与选择序列的理论最优性之间存在差距。

方法论

作者将数据选择重新表述为一个建模为确定性马尔可夫决策过程（DMDP）的序列决策问题。

序列化表述：
- 状态： 已选择的数据点集合 ( $s_t \subseteq D$ )。
- 动作： 下一个要添加的数据点 ( $a_t \in D \setminus s_t$ )。
- 奖励： 结果子集的效用， $U(s_t \cup \{a_t\})$ 。
- 目标： 最大化所有前缀规模下的期望累积效用（等价于选择曲线下的面积，AUSC）。
通过动态规划（DP）求解精确解：
- 最优选择序列是通过贝尔曼最优方程（Bellman optimality equation）推导出来的。这产生了一个精确解，其中最优策略同时考虑了即时奖励和未来价值（全前瞻）。
- 局限性： 状态空间呈指数级增长 ( $O(n \cdot 2^n)$ )，使得大规模数据集上的精确 DP 在计算上变得不可行。
通过近似动态规划（ADP）对现有方法进行重新解释：
- 本文证明，现有的博弈论数据值（Shapley、Banzhaf、Beta Shapley）对应于 ADP 框架内的近视线性近似（myopic linear approximations）。
- 这些方法隐式地拟合了一个线性替代效用函数 $\hat{U}(S) = \hat{b} + \sum_{i \in S} \theta_i$ ，并采用一种近视策略（基于即时边际增益 $\theta_i$ 的贪婪选择）。
- 理论分析表明，这些近似方法的有效性取决于效用函数的曲率 ( $c$ )。对于线性效用（ $c=0$ ），这些方法是最优的。然而，随着曲率增加（表示收益递减/次模性），性能保证会以 $(1-c)^2$ 的速度进行二次方衰减。
提出的解决方案：基于二部图的替代方案：
- 为了弥合理论最优性与计算效率之间的差距，作者提出了一个使用训练集与验证集之间二部图的新型近似方案。
- 效用建模： 替代效用被定义为验证点被选中的训练点所实现的“覆盖率”。该覆盖函数被证明是归一化的、单调的且是次模的。
- 选择策略： 对该替代方案应用贪婪选择算法。
- 理论保证： 在替代方案均匀近似真实效用的“夹逼”（sandwich）条件下，该方法提供了 $(1-\epsilon)(1-1/e)$ 的端到端近似保证。

核心贡献

理论统一： 本文建立了一个将数据估值与序列决策相统一的框架，揭示了流行的半值方法（semi-value methods）是 ADP 中近视线性近似的具体实例。
最优性分析： 提供了新的理论见解，刻画了现有方法失效的时间和原因，特别是将性能下降与效用函数的曲率联系起来。
高效算法： 作者开发了一种保留次模结构的基于二部图的替代方案，从而实现了具有理论保证的可扩展贪婪选择。
实证验证： 全面的实验表明，现有方法始终表现逊于最优序列选择，而提出的二部图方法显著缩小了这一差距。

实验结果

作者将该方法与九种基准方法（包括 Data Shapley、Beta Shapley、Banzhaf、影响函数以及基于学习的方法）在八个经典机器学习基准测试和一个大规模 LLM 微调任务上进行了评估。

与最优性的差距： 现有方法在累积选择性能方面比最优动态规划解低 8.39% 至 23.76%。在具有高冗余度的结构化数据集上观察到了最大的差距。
曲率影响： 通过操纵数据可替代性（作为曲率的代理指标）进行的实验证实，随着可替代性的增加，博弈论方法的性能会下降并趋于收敛，这与 $(1-c)^2$ 的理论界限一致。
二部图性能： 提出的二部图方法在所有数据集上均取得了最高的平均准确率。
- 在 bbc-embeddings 数据集上，它实现了 0.878 的准确率，而表现最好的基准方法为 0.809。
- 在 digits 数据集上，它达到了 0.764 的准确率，而次优方法为 0.680。
- 在大规模 LLM 微调（DATE-LM 基准）中，该方法（BipCov）实现了 63.89% 的平均准确率，超过了强基准 RDS+ (62.88%) 和 Random (62.82%)。
效用近似： 二部图替代方案展示了显著较低的近似误差（MSE: 0.019），相比之下，线性回归基准的 MSE 为 0.089，验证了其捕捉底层效用关系的能力。

意义与主张

本文声称提供了一个理论框架，将数据估值与序列决策统一起来，为当前博弈论方法的局限性提供了严谨的解释。通过将数据值重新定义为源自动态规划的最优选择序列的编码，作者认为现有方法从根本上受限于其近视性和线性本质。

这项工作的意义在于：

诊断失败： 为数据估值方法在冗余数据集上表现不佳提供了一个基于原理的解释（曲率）。
实际改进： 提供了一种计算高效的方法（二部图替代方案），在保留理论保证的同时，显著优于现有的最先进选择策略。
可扩展性： 证明了原则性的数据选择可以扩展到大规模数据集和 LLM 微调任务，而无需承担精确动态规划的高昂成本。

作者对其理论界限保持谦逊，指出 $(1-c)^2$ 保证是一个用于解释失败而非预测典型成功的最坏情况界限，并且他们的实验结果通常高于这些保守的界限。