用动态规划统一数据选择，提升效率与准确性
Unifying and Optimizing Data Values for Selection via Sequential Decision-Making
- 将数据选择建模为序贯决策问题，利用动态规划求解最优序列
- 在子模性下，方法比现有近似方法更优，尤其在高曲率场景
- 提出双分图代理模型，支持可扩展贪婪选择并有理论保证
数据选择已成为数据估值的重要下游应用，但其理论基础仍不充分。本文将数据选择重新构建为序贯决策问题，最优选择序列由动态规划决定，数据价值可视为该最优序列的编码。这一框架通过近似动态规划的视角，统一并重新诠释了如Data Shapley等现有方法，揭示它们是对此序贯问题的短视线性近似。我们进一步分析了在子模性假设下，效用曲率如何导致选择最优性的下降，解释了这些近似方法失效的条件。为弥合理论与实践的差距，我们提出一种基于二分图的高效代理模型，在保持子模结构的同时，支持可扩展的贪心选择，并具备可证明的性能保证。在经典机器学习基准和大规模大模型微调数据选择任务上，实验表明该方法显著优于现有方法。代码已公开于 https://github.com/frankhlchi/SeqDataVal。
原文摘要 · Abstract (English)
Data selection has emerged as a crucial downstream application of data valuation, yet the theoretical foundations for using data values in selection remain underexplored. We reformulate data selection as a sequential decision-making problem where the optimal selection sequence arises from dynamic programming, and data values can be understood as encodings of this optimal sequence. This framework unifies and reinterprets existing methods like Data Shapley through the lens of approximate dynamic programming, revealing them as myopic linear approximations to the sequential problem. We further analyze how selection optimality degrades with utility curvature under submodularity, explaining when and why these approximations fail. To bridge theory and practice, we propose an efficient bipartite graph-based surrogate that preserves submodular structure while enabling scalable greedy selection with provable guarantees. Experiments on classical ML benchmarks and large-scale LLM fine-tuning data selection demonstrate substantial improvements over existing methods. Code is publicly available at https://github.com/frankhlchi/SeqDataVal
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。