加权k近邻回归与软标签预测的精确且经认证的数据沙普利值

# 加权 k-近邻回归与软标签预测的精确且可认证的数据 Shapley 值  
来源：https://arxiv.org/html/2607.11956  
\\setkeys Ginkeepaspectratio Zongye Lyu（Zongye Lyu 任职于莫纳什大学信息技术学院，澳大利亚维多利亚州墨尔本 3800，电子邮件：[email protected]；ORCID：0009-0005-2037-256X）。  
本文已提交至 IEEE 待发表。版权可能在未通知的情况下转移，之后此版本可能不再可访问。  

###### 摘要  
数据 Shapley 值是回答“哪些训练点值得多少”这一问题的标准原则性方案，其 k-近邻 (KNN) 特化版本是实际部署的版本：它是数据估值工具包（如 pyDVL 和 OpenDataVal）所附带的精确、可计算估值器。关于未加权 KNN 分类与回归的精确算法已有研究（Jia 等人，2019），近期的研究则扩展到*加权* KNN *分类*（Wang 等人，2024；Zhang 等人，2025）。加权 KNN *回归*与*软标签*预测一直未被攻克：唯一的精确方法是 Jia 等人提出的 O(N^K) 暴力枚举法，其复杂度随邻域大小 K 呈指数增长。阻碍是具体的，且之前的研究者已明确陈述：加权回归预测是两个依赖于联盟的加权和的*比值*，这种依赖于联盟的归一化分母破坏了之前三个多项式算法各自依赖的可加性、阈值和复制结构。我们填补了这一空白。我们提出：(i) 首个伪多项式时间*精确*算法（在固定晶格精度下对 N 和 K 呈多项式），用于加权 KNN 回归数据 Shapley 值，该算法基于联合整数状态 (∑w, ∑wy) 的计数动态规划，并在 12,716 个对抗性实例上经穷举枚举验证，零偏差；(ii) 一个认证的完全多项式时间近似方案 (FPTAS)，适用于连续权重和目标值，带有可机器检查的每值误差证书，在 86,400 次检查中从未违反；(iii) 一幅复杂性景观，精确指出了该问题的难度，包括一个*无条件*的 Ω(D_w) 输出规模下界和访问模型复杂度结果；(iv) 一个加权软标签多类扩展。我们发布一个开源、仅 CPU 的库，并附上首个精确加权回归数据 Shapley 值基准。在下游错误标签检测中，我们的精确值与蒙特卡洛数据 Shapley 值统计等价（数据集级 TOST，n=8，±0.02 AUC 带，p<10^{-4}），这是预先注册的预期结果；精确性的价值反而在于确定性、认证的误差界、用于审计估值器的精确参考，以及*不*精确的量化代价：蒙特卡洛估值器在我们测试的任何预算下（最多 3,000 次排列，约 1.28×10^6 次效用评估）都未能重现精确的前 10% 排名以达到我们预注册的容差。  

## I 引言  
数据估值提出了一个对机器学习实践至关重要的核心问题：给定一个训练好的模型和一批训练点，每个点贡献了多少？主流的原则性答案是*数据 Shapley* 值 [1 (https://arxiv.org/html/2607.11956#bib.bib1), 2 (https://arxiv.org/html/2607.11956#bib.bib2)]——这是唯一满足经典 Shapley 公理 [3 (https://arxiv.org/html/2607.11956#bib.bib3), 4 (https://arxiv.org/html/2607.11956#bib.bib4)] 的属性分配方案。它支撑着数据定价和数据市场 [5 (https://arxiv.org/html/2607.11956#bib.bib5), 6 (https://arxiv.org/html/2607.11956#bib.bib6)]、错误标签和噪声点检测，以及数据采集决策 [7 (https://arxiv.org/html/2607.11956#bib.bib7), 8 (https://arxiv.org/html/2607.11956#bib.bib8)]。其主要障碍在于计算成本：定义需要对所有 2^{N-1} 个联盟的边际贡献取平均，因此对于通用模型，精确值在计算上难以处理，实践者退而求助于蒙特卡洛排列采样 [9 (https://arxiv.org/html/2607.11956#bib.bib9), 10 (https://arxiv.org/html/2607.11956#bib.bib10)] 或更廉价的替代方法，如 Data-OOB [11 (https://arxiv.org/html/2607.11956#bib.bib11)]、影响力函数 [12 (https://arxiv.org/html/2607.11956#bib.bib12)] 或强化学习估值器 [13 (https://arxiv.org/html/2607.11956#bib.bib13)]。  

### I-A KNN-Shapley：精确、已部署的特例  
使数据 Shapley 变得实用的例外是 k-近邻替代模型。Jia 等人 [14 (https://arxiv.org/html/2607.11956#bib.bib14)] 观察到，当效用函数是查询点处的 KNN 预测质量时，所有 N 个训练点的 Shapley 值可以在 O(N log N) 时间内*精确*计算，而非近似。这就是为什么 KNN-Shapley（而非模型重训练数据 Shapley）成为生产级数据估值库中打包的版本：pyDVL [15 (https://arxiv.org/html/2607.11956#bib.bib15)] 中的 knn_shapley 例程和 OpenDataVal 基准 [16 (https://arxiv.org/html/2607.11956#bib.bib16)] 中的 KNN 估值器。这种替代模型在整个研究领域中是标准做法 [17 (https://arxiv.org/html/2607.11956#bib.bib17), 18 (https://arxiv.org/html/2607.11956#bib.bib18), 19 (https://arxiv.org/html/2607.11956#bib.bib19)]：用点对 KNN 模型的贡献来估值（速度快），然后用该值对下游模型的点进行排序。  

精确 KNN-Shapley 的可计算边界已经向外推移，但不均衡。表 I (https://arxiv.org/html/2607.11956#S1.T1) 总结了现状。未加权 KNN *分类*、*回归*和*软标签*预测都有精确的 O(N log N) 算法 [14 (https://arxiv.org/html/2607.11956#bib.bib14), 17 (https://arxiv.org/html/2607.11956#bib.bib17)]。对于*加权* KNN（每个邻居根据其距离的核函数贡献），进展止步于分类：Wang、Mittal 和 Jia [20 (https://arxiv.org/html/2607.11956#bib.bib20)] 给出了一种精确的 O(N^2) 算法，用于具有离散化权重的加权*硬标签分类*；Zhang、Liu 和 Gionis [21 (https://arxiv.org/html/2607.11956#bib.bib21)] 针对同一分类问题的*复制变体*给出了近线性算法。加权 KNN *回归*和*软标签*预测目前没有多项式算法。唯一的精确方法是 Jia 等人在附录中提到的 O(N^K) 暴力法，其复杂度随邻域大小 K 呈指数增长。  

表 I：按 KNN 设置分类的*精确*数据 Shapley 算法的最佳已知结果。本文填补了加粗的两行。  

### I-B 为什么加权回归是一个新问题  
这一空白并非疏忽；它有确切的原因，且之前的研究者已经指明。对于一个联盟 S，在查询点处的加权 KNN 回归预测为：  
ŷ(S) = [∑_{j∈topK(S)} w_j y_j] / [∑_{j∈topK(S)} w_j] (1)  
这是一个依赖于联盟的两个和的*比值*，其分母 D(S) = ∑_{j∈topK(S)} w_j 正是*归一化项*。这个分母破坏了之前所有多项式方法（我们在第 III 节 (https://arxiv.org/html/2607.11956#S3) 的定位引理中精确指出了每种失败之处）：  
- • Jia 等人的 O(N log N) 算法要求效用函数在邻居上是*分段可加*的；比值将它们耦合在一起，因此递归不适用。（未加权回归*可以由他们解决；困难在于加权本身，而非回归。）  
- • Wang 等人的 O(N^2) 计数动态规划要求效用函数是*单个有符号加权和的阈值*（加权多数投票），它没有归一化项；他们明确表示，这正是他们将自身限制于硬标签分类的原因，并将连续权重软标签 KNN 称为一个“相当大的挑战”。回归预测是两个和的比值，而非一个和的阈值。  
- • Zhang 等人通过利用分类效用将加权问题简化为多重性问题，但这无法保留固定 K 的回归比值；作者本人将回归留作未来工作。  

因此，这个问题在一个强意义上是开放的：两个主要来源明确将其搁置（Wang 等人称连续权重软标签 KNN 是一个相当大的挑战；Zhang 等人将回归留作未来工作），而记录在案的唯一精确方法是 Jia 等人的 O(N^K) 枚举，其复杂度关于 K 呈指数增长。原因是一个结构特征——依赖于联盟的分母——回归和软标签效用函数共享此特征，而已解决的分类效用函数则没有。  

### I-C 贡献  
我们通过一对匹配的算法和一幅复杂性地图解决了加权回归和软标签情况，该地图精确指出了精确性能被推到多远。在整个过程中，权重位于分辨率为 δ_w 的晶格上（因此 w_r = a_r δ_w，a_r ∈ Z_{>0}），D_w = 1 + ∑_r a_r 是总整数权重；D_y 是类似的目标值范围。我们的贡献包括：  
- • 首个伪多项式时间精确算法（定理 1 (https://arxiv.org/html/2607.11956#Thmtheorem1)）。我们针对一个查询点*精确*计算所有 N 个加权 KNN 回归 Shapley 值，时间复杂度为 O(N^2 K D_w^2 D_y^2)，空间复杂度为 O(N K D_w D_y)，方法是在联合整数状态 (W = ∑_{top} a_j, M = ∑_{top} a_j b_j) 上进行大小索引的计数动态规划。关键步骤是将方程 (1) (https://arxiv.org/html/2607.11956#S1.E1) 的分子和分母一起跟踪为整数，因此规模抵消，计算在晶格输入上保持零误差。这在 N 和 K 上都是多项式，替代了先前的 O(N^K) 复杂度。正确性通过在 12,716 个随机和对抗性实例上对穷举枚举的零偏差得到认证，并与一个独立的精确实现交叉验证。经验运行时间约为 N^{2.5} (图 1 (https://arxiv.org/html/2607.11956#S5.F1))。  
- • 针对连续权重的认证 FPTAS（定理 2 (https://arxiv.org/html/2607.11956#Thmtheorem2)）。对于连续的 w > 0 和 y，以及任意 ε > 0，通过舍入到晶格并运行定理 1 (https://arxiv.org/html/2607.11956#Thmtheorem1)，可得到值 φ̂_i，附带一个*可机器检查的每值证书* ε_i，保证 |φ̂_i - φ_i| ≤ ε_i 且 max_i ε_i ≤ ε，时间在 N、K 和 1/ε 上呈多项式。该证书对下有界核（高斯核、裁剪逆距离核）成立，此时分母不会消失。在 86,400 次检查中从未违反（Clopper-Pearson 95% 上限的违反率为 3.47×10^{-5}），实际误差约为认证最大值的 1/28–1/44 倍。Wang 等人只是*离散化*权重并附带了经验偏差说明；带认证的近似保证是全新的。  
- • 复杂性地图（定理 3 (https://arxiv.org/html/2607.11956#Thmtheorem3)，经校准）。我们证明*精度*（而非 N 或 K）才是真正的复杂度驱动力。 (a) 存在实例使得精确值的约分分数*无条件*占用 Ω(D_w) 比特，因此精确输出本质上具有伪多项式长度，而定理 1 (https://arxiv.org/html/2607.11956#Thmtheorem1) 在显式输出算法中，在多项式因子下是关于 D_w 最优的。 (b) 除非 P = NP，否则没有多项式时间算法能判断精确值需要多少二进数字。 (c) 除非 FP = #P，否则没有简洁精确表示支持多项式时间模（2-进数字）访问；#SUBSET-SUM 可归约于少数此类查询。我们在整个论述中加上访问模型限定词：实际相关的*阈值*问题（是否 φ_i ≥ q，等价于 2^{-poly} 的实数近似）仍然是开放的，并且我们指出了障碍，即回归效用函数是联盟权重和的平滑有理核，因此 #P 内容存在于价值的算术精细结构中，而非其量级。粗略 (1/poly) 近似是容易的，由定理 2 (https://arxiv.org/html/2607.11956#Thmtheorem2) 保证。  
- • 加权软标签扩展（定理 4 (https://arxiv.org/html/2607.11956#Thmtheorem4)）。对于 C 个类别，预测是概率向量 p(S) = ∑_{top} w · onehot(y) / ∑_{top} w，共享相同的归一化分母。在晶格 DP 中跟踪每类加权计数向量，可得到伪多项式时间内精确的软标签 Shapley 值（Brier 或硬 0/1 效用），复杂度关于 C 呈指数增长，因此适用于较小的 C。通过在 5,112 个合成晶格实例上，与穷举软标签 oracle 的零偏差（最大偏差 1.5×10^{-13}）验证。  
- • 开源库及首个精确加权回归基准。我们发布一个仅 CPU、与 pyDVL 兼容的库，并用它生成了之前不存在的东西：可作为审计蒙特卡洛估值器基准的精确加权回归数据 Shapley 值。在八个回归数据集上的错误标签检测中，我们的精确值与蒙特卡洛数据 Shapley 值*统计等价*（平均 AUC 0.964 vs 0.965；数据集级 TOST 等价性在 ±0.02 AUC 带内，n=8，p<10^{-4}；配对 Wilcoxon p=0.74），两者均低于基于装袋的 Data-OOB 代理（0.986）。我们并不声称检测状态最优。精确性带来的好处是确定性、认证的误差界以及一个可以对采样定价的参考：蒙特卡洛估值器在我们测试的任何预算下（最多 3,000 次排列，约 1.28×10^6 次效用评估）都*未能*恢复精确的前 10% 排名以达到我们预注册的容差（Kendall τ ≥ 0.95 且前 10% Jaccard ≥ 0.9），并且在该预算下，其前 10% 集合在多次运行中平均仍会翻转 2.8 个成员。所有理论都在精确有理算术中通过枚举 oracle 进行了机器验证，所有经验声明都遵循预注册协议，偏差在第 V 节（实验）中披露。论文的其余部分形式化设定和定位引理（第 III 节 (https://arxiv.org/html/2607.11956#S3)），发展定理 1–4（第 IV-B–IV-E 节），并报告实验（第 V 节 (https://arxiv.org/html/2607.11956#S5)），然后在第 VI 节 (https://arxiv.org/html/2607.11956#S6) 讨论范围和局限性。  

## II 相关工作  

### II-A 数据估值和数据 Shapley  
将单个训练点对模型性能的贡献归因是*数据估值*的核心问题。Shapley 值 [3 (https://arxiv.org/html/2607.11956#bib.bib3)] 是规范答案：它是唯一满足效率、对称性、零参与者和可加性公理 [4 (https://arxiv.org/html/2607.11956#bib.bib4)] 的属性分配