提出分层对比数据估值方法，高效评估海量异构数据样本价值。
From Points to Coalitions: Hierarchical Contrastive Shapley Values for Prioritizing Data Samples
- 通过对比学习构建几何保持表示，分层聚类组织数据并局部估算联盟贡献。
- 在多个基准上提升准确率最高达+5个百分点，估值速度加快100倍。
- 适合数据清洗、流式更新和公平报酬分配等实际场景使用。
当数据集规模大、异质性强且具有几何结构时，如何量化每个训练样本的价值？经典数据沙普利值理论上可行，但其O(n!)复杂度与点级视角难以适应现代数据规模。我们提出分层对比数据估值（HCDV），一个三阶段框架：(i) 学习对比性、几何保持的表示；(ii) 将数据组织为由粗到细的平衡层次聚类；(iii) 通过局部蒙特卡洛博弈为联盟分配沙普利风格收益，预算自上而下传播。HCDV将计算复杂度从阶乘级降至O(T sum_l K_l) = O(T K_max log n)，奖励能增强决策边界的样本，并通过曲率正则化处理异常值。我们证明HCDV近似满足四个沙普利公理，盈余误差为O(eta log n)，联盟偏差服从tilde O(1/sqrt{T})，在顶k选择中最多产生k epsilon_infty的误差。在四个基准任务——表格数据、视觉、流式数据及4500万样本的点击率预测任务——以及OpenDataVal套件上的实验表明，HCDV可提升准确率最高达+5个百分点，估值时间减少高达100倍，并直接支持数据增强过滤、低延迟流式更新与公平市场支付等应用。
原文摘要 · Abstract (English)
How should we quantify the value of each training example when datasets are large, heterogeneous, and geometrically structured? Classical Data-Shapley answers in principle, but its O(n!) complexity and point-wise perspective are ill-suited to modern scales. We propose Hierarchical Contrastive Data Valuation (HCDV), a three-stage framework that (i) learns a contrastive, geometry-preserving representation, (ii) organizes the data into a balanced coarse-to-fine hierarchy of clusters, and (iii) assigns Shapley-style payoffs to coalitions via local Monte-Carlo games whose budgets are propagated downward. HCDV collapses the factorial burden to O(T sum_{l} K_{l}) = O(T K_max log n), rewards examples that sharpen decision boundaries, and regularizes outliers through curvature-based smoothness. We prove that HCDV approximately satisfies the four Shapley axioms with surplus loss O(eta log n), enjoys sub-Gaussian coalition deviation tilde O(1/sqrt{T}), and incurs at most k epsilon_infty regret for top-k selection. Experiments on four benchmarks--tabular, vision, streaming, and a 45M-sample CTR task--plus the OpenDataVal suite show that HCDV lifts accuracy by up to +5 pp, slashes valuation time by up to 100x, and directly supports tasks such as augmentation filtering, low-latency streaming updates, and fair marketplace payouts.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。