🤖 machine learning

Efficient Banzhaf-Based Data Valuation for $k$ -Nearest Neighbors Classification

本文通过证明基于 Banzhaf 值的数据估值问题对于 $k$ -近邻分类器是\#P-难的，进而开发了具有伪多项式时间和线性时间复杂度的高效精确算法，以及蒙特卡洛估计方法，以解决该计算难题并实现实用且公平的数据贡献评估。

原作者： Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis

发布于 2026-05-21

📖 1 分钟阅读☕ 轻松阅读

原作者： Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你有一锅巨大的汤（你的机器学习模型），由成千上万种不同的食材（你的数据点）熬制而成。你想知道：究竟是哪种特定的食材让这锅汤的味道最好？ 那一撮盐重要吗？胡萝卜是必需的吗？还是说那种奇怪的香料只是在占地方？

在机器学习的世界里，这被称为数据估值。你提供的这篇论文解决了一个特定且棘手的问题：在使用一种名为**k-近邻（kNN）**的特定“烹饪方法”时，如何确定食材的价值。

以下是他们工作的简要分解：

1. 问题：计数是不可能的

要准确计算出单个食材（数据点）的贡献，最“公平”的方法是想象所有可能的食材组合，看看加入该食材时汤的味道如何，再看看不加它时汤的味道如何。

类比：假设你有 1,000 种食材。为了绝对公平，你必须品尝由这些食材组成的每一种可能组合（包含和不包含你的目标食材）熬制的汤。
现实：食材的组合数量比宇宙中的原子数量还要多。进行这种数学计算极其困难，计算机科学家称之为**#P-难**问题。这就像试图一颗一颗地捡起海滩上的每一粒沙子来计数。这需要的时间将超过宇宙的年龄。

2. 解决方案：一个聪明的捷径

作者们意识到，k-近邻（kNN）是一种特殊的“汤”。在 kNN 中，汤的味道仅取决于最近的几种食材（即“最近邻”），而不是整锅汤。

隐喻：如果你根据天气决定穿什么，你只关心当前的温度和风力。你不需要知道三天前或三英里外的天气。那些“遥远”的食材并不重要。
突破：由于 kNN 只关心“最近”的邻居，作者们构建了一种动态规划算法。你可以把它想象成一个智能计算器，它不需要品尝每一种汤的组合。相反，它构建了一张“食谱地图”，通过观察“最近邻”的变化，瞬间计算出每种食材的价值。

他们创建了这种智能计算器的三个版本：

针对加权 kNN：一种快速方法，能处理具有不同“强度”（权重）的食材。
针对非加权 kNN：一种更快的方法，将所有食材视为同等重要。这种方法效率极高，几乎呈线性扩展，意味着它可以处理其他方法会崩溃的海量数据集（数百万种食材）。
蒙特卡洛估计：如果数据集太大，连他们的智能计算器都无法处理，他们提供了一种“采样”方法。与其品尝每一锅汤，不如品尝几批随机样本并估算平均值。虽然不完美，但速度非常快。

3. 为什么要用 Banzhaf？（“投票权”类比）

这篇论文专注于一个特定的数学公式，称为Banzhaf 值。

类比：想象一个委员会正在对某项决定进行投票。Shapley 值（另一种流行方法）就像计算一个人在委员会所有可能的人员组合中作为“关键摇摆票”的频率，这会给极小和极大的群体赋予额外的权重。
Banzhaf 的区别：Banzhaf 值更简单。它只问：“在多少种情况下，这个人的投票实际上改变了结果？”
为何在此处重要：作者发现 Banzhaf 通常更稀疏且更稳健。
- 稀疏性：它对那些无关紧要的食材赋予零值，使得更容易识别出真正的“明星”食材。
- 稳健性：如果有人偷偷混入一堆糟糕的、随机的食材（噪声），Banzhaf 方法会完全忽略它们。而 Shapley 方法可能会感到困惑，并给这些糟糕的食材一点点信用，从而搞乱整个计算。

4. 他们测试了什么（现实世界的证明）

作者们不仅仅是在纸上做数学题；他们在真实数据（如识别手写数字或检测信用卡欺诈）上测试了他们的“智能计算器”。

速度：他们的新算法比旧的“暴力”方法快数千倍。他们可以在几小时内处理包含数十万个点的数据集，而其他方法可能需要数天或完全失败。
清洗数据：他们表明，他们的方法非常擅长发现“坏苹果”。如果你移除他们的方法判定为“价值最低”的数据点，模型的性能会急剧下降。这证明他们正确地识别出了重要的数据。
发现错误：他们测试了该方法是否能发现标签错误的数据（例如，一张被标记为“狗”的猫的照片）。
- 软方法 vs. 硬方法：他们发现，“软”方法（查看概率）更适合发现随机错误。然而，他们的“硬”Banzhaf 方法在发现关键错误方面表现更好——即那些实际上最严重拖累模型性能的具体错误数据点。

总结

这篇论文解决了一个巨大的速度问题。它将一个数学上不可能完成的任务（公平地评估 kNN 模型中的每个数据点）转化为一种实用、快速的工具。

旧方法：尝试数清每一粒沙子（太慢，不可能）。
新方法：使用地图，只计算那些实际接触路径的沙子（快速、准确）。

他们证明，对于 kNN 模型，你不需要品尝宇宙中所有的汤组合，就能知道哪种食材最重要。你只需要观察邻居即可。

技术摘要：基于高效 Banzhaf 值的 k 近邻分类数据估值

问题陈述

数据估值，即量化单个数据点对模型性能的贡献，是机器学习中的一个根本性挑战。虽然博弈论方法（如 Banzhaf 值）提供了公平估值的原理性框架，但它们面临指数级的计算复杂度。具体而言，计算精确的 Banzhaf 值需要对数据集的所有可能子集评估价值函数，这一任务在一般情况下已被证明是 #P-难的。这种计算负担使得精确计算对于包含数千或数百万样本的真实世界数据集变得不可行，迫使大多数现有工作依赖以牺牲精度为代价换取效率的近似方法。

本文解决了为 k 近邻（kNN）分类器计算精确 Banzhaf 值的具体挑战。作者旨在通过开发利用 kNN 独特局部性属性的算法，在不依赖近似的情况下实现显著的计算改进，从而弥合合作博弈论的理论基础与真实世界机器学习的实际需求之间的差距。

方法论

本文提出了一套专为 kNN 分类场景设计的动态规划（DP）算法，以及高效的蒙特卡洛估计方法。

1. 理论难度

作者首先确立了该问题的理论难度。他们证明了为 kNN 分类模型计算 Banzhaf 值是 #P-难的。这一结论是通过从加权多数博弈（WMG）问题（合作博弈论中一个经典的 #P-难问题）进行归约得出的。该结果表明，在标准复杂度假设下，一般情况不存在强多项式时间算法。

2. 动态规划框架

尽管存在难度结果，作者利用 kNN 的局部性属性（即只有 k 个最近邻影响预测），开发了具有改进时间复杂度的精确算法。

加权 kNN 的标准动态规划：
作者首先提出了一种时间复杂度为 $O(W n^4)$ 的动态规划算法，其中 $n$ 是数据点数量， $W$ 是前 k 个权重的最大和。该方法定义了一个状态函数 $f_i(w, s, m)$ ，表示具有特定权重和 $w$ 和特定第 $m$ 近邻的大小为 $s$ 的子集数量。
加权 kNN 的改进动态规划：
为了降低复杂度，作者引入了新技术：
- 部分和预计算： 对于子集大小 $s \le k$ 的情况，他们预计算部分和以加速递推关系，从而减少该项的复杂度贡献。
- 二项式系数递推： 对于 $s > k$ ，他们利用二项式系数的递推关系来高效计算状态和。
- 结果： 这些优化产生了一个时间复杂度为 $O(W k n^2)$ 的算法。
无权重 kNN 的专用动态规划：
对于无权重情况（所有权重均为 1），作者提出了一种专用算法，实现了 $O(n k^2)$ 的时间复杂度。
- 状态空间重构： 他们通过消除跟踪第 $m$ 近邻具体身份的需求来减少状态空间。
- 前向与后向聚合： 他们利用前向函数（ $f_i$ ）和后向函数（ $b_i$ ），以及带符号的后向函数（ $b^+_i, b^-_i$ ）来处理标签符号。
- 结果： 由于 $k$ 通常是一个小常数，该算法相对于数据点数量运行在 近线性时间内。

3. 蒙特卡洛估计

认识到即使是二次复杂度对于大规模数据集也可能难以承受，本文提供了两种高效的基于采样的方法：

基于联盟的采样： 通过仅在排序列表中维护前 $k+1$ 个参与者进行优化，将 $m$ 次采样的复杂度降低至 $O(m n \log k)$ 。
基于排列的采样： 通过重加权方案调整 Banzhaf 值的排列公式，同样实现了 $O(m n \log k)$ 的复杂度。

主要贡献

难度证明： 本文证明了为 kNN 分类器计算 Banzhaf 值是 #P-难的。
首个加权 kNN 精确动态规划算法： 提出了首个用于计算加权 kNN 分类器中精确 Banzhaf 值的动态规划算法，具有伪多项式时间复杂度。
优化的加权算法： 通过涉及部分和二项式递推的新颖算法技术，将加权算法的时间复杂度显著提升至 $O(W k n^2)$ 。
近线性无权重算法： 引入了一种针对无权重 kNN 的专用算法，时间复杂度为 $O(n k^2)$ ，这是首个用于计算硬标签 kNN 基于博弈论值的近线性时间算法。
高效采样： 提供了优化的基于联盟和基于排列的蒙特卡洛方法，利用 kNN 局部性以实现更快的近似估计。

实验结果

作者在 12 个真实世界数据集（范围从 5,404 到 1,000,000 个数据点）和合成数据上进行了广泛的实验。

计算效率：
- 暴力算法在数据集小至 30 个点时，10 小时内未能完成。
- 无权重动态规划算法（bv-uw）表现出几乎线性的扩展性，在时间预算内处理了高达 $10^6$ 个点的数据集。
- 改进的加权动态规划（bv-fast）扩展至 $10^4$ 个点，优于现有的硬标签 Shapley 基线（sv, sv-uw），后者无法完成 $n \ge 10^4$ 的运行。
- 当接受约 0.02 的偏差时，蒙特卡洛方法比加权动态规划快达 25 倍。
实际应用：
- 数据点移除： 移除具有最高 Banzhaf 值的数据点导致的模型精度下降比其他方法（如留一法 LOO 或影响函数）更剧烈，表明这些点对性能至关重要。
- 数据选择： 增量选择具有最高值的点比随机选择或其他基线更快地提高了模型精度。
- 错误标签检测： 研究突出了估值类型之间的权衡。软标签 Shapley 值在检测随机翻转的标签方面表现更好（较高的 $F_1$ 分数）。然而，硬标签 Banzhaf 值在识别决定性低质量点方面更为优越，这些点的修正能显著提高模型性能。硬标签值对噪声更具鲁棒性，更适合于旨在修复实际改变预测的数据点的清洗任务。

意义与主张

本文声称提供了 kNN 中硬标签 Banzhaf 估值的最快算法，甚至超过了其硬标签 Shapley 对应物的效率。其意义在于使精确的博弈论数据估值在大规模数据集上变得计算可行，而此前该任务仅限于近似方法。

作者强调，虽然 Banzhaf 值在不归一化的情况下不满足效率公理（值的总和等于总价值），但它提供了独特的实际优势：

稀疏性： 它产生更稀疏的值，突出显示一组集中的有影响力的点，这有利于基于示例的可解释性。
鲁棒性： 与对极端子集过于敏感的 Shapley 值相比，它对噪声和重复数据点更具鲁棒性。
实用性： 开发的算法使得严格的数据估值能够应用于数据获取、清洗和协作学习等场景，在这些场景中，理解数据点重要性的相对顺序至关重要。

本文结论指出，虽然该框架由于不可分解的归一化项而无法直接扩展到 kNN 回归，但它成功弥合了合作博弈论与分类任务实际机器学习应用之间的差距。