摘要
数据Shapley为训练样本的价值提供了标准的原则性答案，其k近邻(KNN)特化版本被广泛应用于实际中：这是由pyDVL和OpenDataVal等工具包提供的精确估计器。虽然已有精确算法用于无权KNN和加权KNN分类，但加权KNN回归和软标签预测却一直未能解决：现有的唯一精确方法是一个O(N^K)的暴力搜索，随着邻域大小K的增加呈指数增长。
问题分析
加权回归预测是依赖于两个联盟相关求和的比率，其归一化分母破坏了先前多项式算法所依赖的加法、阈值和重复结构。我们成功填补了这一空白。
主要贡献
- 我们提出了首个伪多项式时间的精确算法（在固定的格点精度下，对N和K的多项式），用于加权KNN回归数据Shapley，这是一个在联合整数状态下进行计数的动态规划，经过对12,716个对抗实例的全面枚举验证，零错误匹配。
- 提供了一个针对连续权重和目标的认证FPTAS，具有一个机器可检查的每个值的误差证明，在86,400次检查中从未违反。
- 描绘了复杂性全景，包括无条件的Omega(D_w)输出大小下界和访问模型的难度结果。
- 提供了加权软标签多类扩展。
我们发布了一个开源的仅限CPU的库以及首个精确的加权回归数据Shapley真值。在下游的错误标记检测中，我们的精确值与蒙特卡洛数据Shapley在统计上等效（数据集级TOST，n=8，p）。
博主点评： 这项研究在加权KNN回归的精确数据Shapley算法上取得了重要进展，解决了此前方法的局限性，为未来的研究和应用提供了强有力的工具。开放源代码的发布也将促进社区的进一步探索与创新。