利用模型局部性,大幅减少数据价值计算的重训练次数。
Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation
- 基于模型计算路径定义影响集,将全局计算转为局部子集处理。
- 实验显示重训练次数降低90%以上,速度提升5倍以上,精度不降。
- 适合需要高效数据价值评估的机器学习系统,如联邦学习、模型审计。
Shapley值为数据估值提供了理论基础,但精确计算因联盟空间指数级增长而难以实现。现有加速方法仍为全局视角,忽略了现代预测器的关键特性:对特定测试样本,仅有少量训练点影响预测结果。本文通过模型计算路径(如KNN的邻域、树模型的叶节点、GNN的感受野)定义支持集,形式化了模型诱导的局部性,并证明当局部性精确时,可将Shapley计算投影到这些支持集上而不丢失信息。这将Shapley评估重构为在重叠支持集族上的结构化数据处理问题,而非穷举联盟。我们证明局部Shapley的内在复杂度由不同影响子集数量决定,建立了重训练操作的信息论下界。基于此,提出LSMR算法——通过支持映射与枢纽调度,每个影响子集仅训练一次,实现最优复用。对于更大支持集,提出LSMR-A,一种无偏且具有指数集中性的重用感知蒙特卡洛估计器,运行时间取决于采样到的不同子集数,而非总抽样次数。跨多种模型架构的实验表明,该方法显著减少重训练量并实现数倍加速,同时保持高估值保真度。
原文摘要 · Abstract (English)
The Shapley value provides a principled foundation for data valuation, but exact computation is #P-hard due to the exponential coalition space. Existing accelerations remain global and ignore a structural property of modern predictors: for a given test instance, only a small subset of training points influences the prediction. We formalize this model-induced locality through support sets defined by the model's computational pathway (e.g., neighbors in KNN, leaves in trees, receptive fields in GNNs), showing that Shapley computation can be projected onto these supports without loss when locality is exact. This reframes Shapley evaluation as a structured data processing problem over overlapping support-induced subset families rather than exhaustive coalition enumeration. We prove that the intrinsic complexity of Local Shapley is governed by the number of distinct influential subsets, establishing an information-theoretic lower bound on retraining operations. Guided by this result, we propose LSMR (Local Shapley via Model Reuse), an optimal subset-centric algorithm that trains each influential subset exactly once via support mapping and pivot scheduling. For larger supports, we develop LSMR-A, a reuse-aware Monte Carlo estimator that remains unbiased with exponential concentration, with runtime determined by the number of distinct sampled subsets rather than total draws. Experiments across multiple model families demonstrate substantial retraining reductions and speedups while preserving high valuation fidelity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。