摘要
量化每个训练点对学习任务的重要性是机器学习中的一个基本问题，评估的重要性得分已被用于指导一系列数据工作流，如数据汇总和领域适应。一个简单的方法是使用每个训练点的留一误差来表示其重要性。最近的工作还提出了使用 Shapley 值，因为它定义了一个独特的值分布方案，满足了一组有吸引力的特性。然而，计算 Shapley 值通常很昂贵，这限制了它在实际应用中的大规模适用性。为了提高计算 Shapley 值的可扩展性，最近提出了多种启发式方法，但可能会影响其在现实应用中的实用性。
现有的数据量化方法对现有工作流程的效果如何?这些方法在经验上和理论上如何比较?在使用这些方法时，我们必须牺牲这些工作流中的可伸缩性来实现其效用吗?在这篇论文中，我们进行了一个新颖的理论分析，比较了不同重要性量化方法的效用，并报告了大量的实验研究，包括现有的和提出的工作流程，如有噪声的拉贝尔检测、水印去除、数据汇总、数据采集和域适应。我们表明，基于 KNN 代理预处理特征嵌入的 Shapley 值近似获得了与现有算法相当的效用，同时实现了显著的可扩展性改进，通常是数量级的改进。我们的理论分析也证明了它相对于留一误差的优势。
1 引言
相对于其他训练样例，理解单个训练样例对学习任务的重要性是机器学习(ML)中的一个基本问题，它可能对一系列应用产生深远影响，包括可解释性、鲁棒性、数据获取、数据估值等。
在本文中，我们围绕这个基本问题提出了两个问题。我们的贡献是通过新颖的理论分析和深入的实验研究理解这两个问题。
Q1:leave-one-out vs. Shapley：给定一个训练集 D，一个验证集 D_val 和学习算法 A，让实用程序 U_A，Dval(D)作为使用 A 对 D 进行训练的模型的验证准确性。最近已有两份工作来分配数据点 z 属于 D 的相对重要性。然而，有一个问题仍然存在：这两种方法在理论和经验上有什么联系和区别？
Q2:精确 Shapley vs. 基于代理的 Shapley：我们将在本文中展示，基于 Shapley 的方法在理论和实证上通常优于基于留一的方法。然而，基于 Shapley 的方法可能会很昂贵，因为对于一般分类器，需要训练指数级的多个模型。因此，许多最先进的方法采用基于抽样的方法来近似该分数。另一方面，Jia 等人最近的一项工作表明，对于某一类分类器，即 K-最近邻（KNN），可以在 O(|D|log|D |)时间内高效地计算该分数。
尽管如此，仍然存在一个问题：我们可以使用 K-最近邻分类器作为计算 Shapley 值的代理模型，与普通的精确 Shapley 值相比，它在现实应用程序中的性能如何？
在本文中，我们采用第一种方法逐步理解上述问题。我们在理论和实证方面都做出了贡献。
l 我们进行了一项新颖的理论分析，旨在严格分析基于 LOO 和基于 Shapley 的方法之间的差异。具体来说，我们形式化了两个特定于数据重要性的性能度量：一个关注数据重要性的预测能力，研究它是否指示训练点对随机集的贡献；另一个重点是数据区分“好”和“坏”训练点的能力。我们表明，对于这两种性能指标，在特定的技术条件下，基于 Shapley 的方法可以优于基于留一的方法。据我们所知，这是第一次对不同数据重要性量化技术的相对性能进行理论分析。
l 我们对一系列 ML 任务进行了深入的实证研究，包括噪声标签检测、水印去除、数据摘要、主动数据采集和不同基准数据集上的域自适应。在这些任务中，我们实证研究了（1）基于留一的方法和基于 Shapley 的方法，以及（2）基于精确 Shapley 的方法和基于 KNN 代理的 Shapley 方法之间的相对性能。
l 我们的实证研究表明，基于 KNN 代理的 Shapley 方法表现良好，取得了与所有其他方法相当的结果，并且通常在质量上优于所有其他方法，同时速度快了几个数量级。这为我们提供了第一个针对大规模数据集的实用算法，该算法返回一系列重要 ML 任务的有用数据重要性分数。
2 背景
2.1 留一法
量化数据重要性的一种简单方法是测量一个数据点对其余训练数据的贡献：
此数据重要性度量值称为 Leave-One-Out（LOO）值。准确评估训练点的 LOO 值需要对模型进行多次重复训练，对于大型训练数据集和大型模型，相关的计算成本是不允许的。对于深度神经网络，Koh 等人建议通过影响函数估计由于移除每个训练点而导致的模型性能变化。然而，为了获得影响函数，需要计算损失函数的 Hessian 倒数。有了训练点和模型参数，它需要 O（N_（p^2+p……3））操作。Koh 等人用 O（N_p）复杂度近似影响函数，这对于大型网络来说仍然很昂贵。
2.2 基于 Shapley 的方法
Shapley 值是合作博弈理论中的一个经典概念，用于分配所有参与者联盟产生的总收益。我们可以将监督学习问题视为训练数据实例之间的合作博弈，并应用 Shapley 值来评估每个训练点的贡献。给定性能度量，训练数据 z_i 的 Shapley 值定义为对由其他训练点形成的所有可能子集 D 的平均边际贡献 z_i：
然而，计算 Shapley 值可能很昂贵：评估精确的 Shapley 值涉及计算每个训练点对所有可能子集的边际贡献，其复杂性为 O（2^N）。这种复杂性对于评估大量训练点显然是不切实际的。更糟糕的是，对于 ML 任务，评估效用函数本身（例如验证精度）在计算上非常昂贵，因为它需要重新训练 ML 模型。
Ghorbani 等人介绍了两种基于蒙特卡罗近似的近似 Shapley 值的方法。这些方法背后的核心思想是将训练点的 Shapley 值视为其对随机子集的预期贡献，并使用样本平均值来近似期望值。在我们的实验中，我们发现 Ghorbani 等人中的方法可以为简单模型（如逻辑回归和浅层神经网络）管理多达 1000 个数据量，但无法在合理的时间内估计较大数据量和深网络的 Shapley 值。
Jia 等人开发了一种精确、高效的算法来计算 KNN 分类器的 Shapley 值。原则上，我们可以使用 KNN 分类器作为代理模型，并使用它代替目标学习算法。给定一个带有标签的单一验证点，最简单、未加权的 KNN 分类器首先找到与标签 x_val 最相似的顶部训练点（x_å1 ，…，x_åk），并输出将标签 y_val 视为
的 x_val 的可能性。我们将预测正确标签的置信度作为衡量性能的标准：
考虑到模型性能的衡量，每个训练点的 Shapley 值可以如下递归计算：
使用神经网络作为代理模型的一个问题是，神经网络通常在高维数据上表现不佳。正如许多工作已经说明了预训练嵌入在不同的新任务上的能力，我们通过使用预训练嵌入作为特征提取器并应用 KNN 来解决这个问题。
3 LOO 值和 Shapley 值的理论对比
我们现在关注第一个问题：这两种方法在理论和经验上有什么关系和区别？具体来说，我们定义了两个性能指标，并在不同的技术假设下进行了理论分析。
3.1 性能指标 1: 保序性
我们希望在将点与随机数据点集相结合时，点的数据重要性度量指示预期的性能提升。特别的，我们考虑两个点在给定的数据重要性度量下具有不同的分数，并研究由于加入这两个点所期望的模型性能改进是否将具有与重要性分数相同的顺序。在执行 ML 任务时使用相同的顺序，我们可以选择具有更高重要性的点以利于另一个点。我们在下面的定义中形式化了这个理想属性。
每一个训练点的 KNN-LOO 值可以由
得到。对于 KNN-LOO 值和 KNN-Shapley 值具有保序性的定理，我们认为：对于任意给定的 D={z_1,…,z_N}，其中 z_i=(x_i,y_i)，和任意给定的验证点 z_val=(x_val,y_val)，假设 z_1,…,z_N 按照它们的相似度排序。让 d(.,.)依据 D 的排序作为距离特征指标，并认为对于 i=1,…,N 来说
且 δ>0。然后，v_shap-knn 对 I 中所有的点对保序，v_LOO-KNN 仅对(z_i,z_j)保序，其中 i,j 的最大值小于 K。
上述定理表明，KNN-Shapley 值比 KNN-LOO 值具有更强的预测能力，KNN-Shapley 可以预测任意两个的相对效用，而 KNN-LOO 值只能正确预测 x 的 k 近邻的相对效用。同时，与单验证点类似，对与多个验证点来说，KNN-LOO 值保序的条件比 KNN-Shapley 值更严格。
3.2 性能指标 2: 价值区分度
在第二个性能指标中，我们关注的是基于 LOO 的方法和基于 Shapley 的方法无法区分不同数据点的情况，这与它们的重要性无关。我们作为示范使用的技术工具是考虑分类器以差分私有（DP）方式训练的设置。
差分私有学习算法隐藏了一个训练点对模型性能的影响。因此，对于不同的私有模型来说，区分“好”数据和“坏”数据可能更加困难。我们将证明，当学习算法满足 DP 时，Shapley 值比 LOO 值具有更强的辨别能力。
对于学习算法 A(.)来说，性能衡量指标
存在如下定理：
对于典型的差分私有学习算法，例如在随机梯度下降中添加随机噪声，如果我们减小训练集的大小，私有保证将变弱。换句话说，ϵ(n)和 δ(n)是 n 的单调递减函数，对于 ϵ‘(n)情况亦是如此。因此,它认为
对于上述定理，首先，所有训练点的最大分数直接为上界 ϵ’这一事实意味着更强的隐私保障会增加区分不同点重要性的难度。其次，ϵ‘对于 N 的单调依赖性表明，当训练规模很大时，LOO 和 Shapley 值都收敛于零。第三，通过比较 LOO 和 Shapley 值的上界，我们发现 Shapley 值的收敛速度较慢，因此与 LOO 值相比，它有更好的机会区分“好”数据和“坏”数据。
4 实证研究
4.1 数据重要性量化方法
这一节我们主要比较最新的数据重要性量化方法。
1) TMC-Shapley：该方法将 Shapley 值作为训练实例对随机集边际贡献的期望，然后用样本均值进行近似。
2) G-Shapley：G-Shapley 通过在该点处采取梯度下降步骤并计算性能差异，来近似由于添加一个训练点而导致的模型性能变化。该方法仅适用于梯度法训练的模型。因此，当使用梯度方法训练基础模型时，该方法将作为基线包含在我们的实验结果中。
3) Leave-one-out：我们使用 LOO 来指代由于移除训练点而计算精确模型性能的算法。评估 LOO 错误需要在每个训练点的简化数据集上重新训练模型，因此对于大型模型也是不切实际的。
4) KNN-LOO：为了使用 KNN-LOO 对数据进行估值，我们使用中提供的预训练模型为 KNN 提取特征，并计算提取特征的 KNN-LOO 值。
5) KNN-Shapley：我们首先使用预训练模型来提取特征。然后，我们在预先训练的特征变换上计算 Shapley 值。当预先训练的特征变换不可用时，我们直接计算原始数据上的特征变换，作为真实 Shapley 值的替代项。上述算法的复杂度为 O（Nd+NlogN），其中 d 是特征表示的维数。
6) 随机：随机基线不区分不同数据点之间的重要性，而是从训练集中随机选择数据来执行给定任务。
4.2 运行时间对比
图 1
根据图 1，我们可以观察到 KNN-Shapley 比其他方法的性能好几个数量级。
4.3 应用对比
我们研究了不同方法估计的数据重要性在一系列任务中的效果，包括噪声标签检测、水印去除、数据摘要、主动数据采集和域自适应。
4.3.1 噪声标签检测
由于自动标记、非专家标记或数据毒害对手造成的标签损坏，现实世界中的标签通常很嘈杂。我们认为，数据重要性的概念可以帮助确定验证过程的优先顺序，让专家只审查最有可能被污染的实例。关键思想是根据数据重要性对数据点进行排序，并对重要性得分最低的点进行优先级排序。我们在三种环境下进行了实验，并在正文中展示了在 fashion MNIST 数据集上训练的三层卷积网络的结果。此数据集的噪波翻转率为 10%。不同数据重要性度量的性能如图 2a 所示。我们检查得分最低的训练实例的标签，并用检查的训练数据的分数（百分比）绘制检测到的错误标记数据分数（百分比）的变化。我们可以看到，该方法的性能优于所有其他方法。此外，基于 Shapley 值的度量，包括 TMC Shapley、G-Shapley 和我们的 KNN Shapley，比基于 LOO 的度量更有效。
图 2
4.3.2 水印移除
图 3
声称拥有经过训练的深网的一种普遍方式是在模型中嵌入水印。水印技术分为两类，即基于模式的水印技术和基于实例的水印技术。水印示例显示在图 4 中。
在这个应用中，我们证明了模型训练器总是可以根据数据的重要性去除水印。其想法是，水印本质上应该具有较低的数据重要性，因为它们对预测正常验证数据贡献甚微。
我们考虑设置一个训练来自 MNIST 的 10000 个图像的逻辑回归模型以用于基于实例的水印去除。水印率为 10%。在本实验中，我们发现水印和良性实例在某些验证实例上的得分都较低；因此，就整个验证集的平均分数而言，它们并不完全可分离。相反，我们建议计算每个训练点（我们称之为 max-KNN-Shapley）的验证集的最大分数，并删除具有最低 max 值的实例。在绘制图 2b 时，我们检查具有最低分数的训练实例的标签，并用检查的训练数据的分数绘制检测到的水印分数的变化。该图显示，与所有其他基线相比，我们的 max-KNN-Shapley 在检测基于实例的水印方面更有效。
4.3.3 数据汇总
数据摘要的目的是从海量数据集中选择一个具有代表性的小子集，它可以保留与整个数据集相当的效用。这是数据重要性的自然应用，因为我们可以通过消除低重要性的数据直接减少数据集的大小。
我们使用在 UCI 成人普查数据集上训练的单隐层神经网络。在图 2c 中，我们绘制了预测精度随移除数据部分变化的曲线图。该图显示，基于 Shapley 值的数据重要性度量所选择的实例比基于 LOO 的度量更具代表性。虽然 TMC-Shapley 和 G-Shapley 的性能略优于 KNN-Shapley，但我们的方法在减少整个训练集的 50%后仍然保持了较高的性能，这是值得注意的。
4.3.4 主动数据采集
带注释的数据通常很难获得，成本也很高，特别是对于只有专家才能提供可靠标签的专业领域。主动数据采集旨在通过自动决定注释员应标记哪些实例来训练模型，从而促进数据采集过程。为了模拟这个场景，我们从一个小的训练集开始，然后训练一个随机林，根据新数据的特征预测它们的分数。我们重复这个过程，并迭代地向训练集中添加具有最高数据重要性的新数据。
我们选择 MNIST 作为数据集，并向其中的一部分注入噪声。我们从一个包含 100 幅图像的小训练集开始，将高斯白噪声添加到其中的一半。我们使用另外 100 张图像来计算训练数据的分数，并使用大小为 1000 的验证数据集来评估性能。在图 2d 中，我们绘制了预测精度随添加训练点数量的变化。显然，基于 KNN-Shapley 值选择的新数据比所有其他方法更快地提高了模型精度。
4.3.5 域适应
域适应旨在利用一个域中的数据集执行另一个域中的预测任务。我们首先计算源域中的数据相对于目标域中的保留集的重要性。然后，我们只使用源域中的正值点来训练模型，并在目标域中对模型进行评估。
表 1 在 MNIST 和 USPS 之间的域适应
我们首先训练一个多项式逻辑回归分类器。我们从源域随机抽取 1000 幅图像作为训练集，根据目标域的 1000 个实例计算训练数据的分数，并在另外 1000 个目标域实例上评估模型的性能。结果汇总在表 1 中。如表所示，KNN-Shapley 的表现最好。
4.3.6 结果总结
基于大量的经验观察，我们得出以下结论：（1）与其他基于大规模训练数据和模型的方法相比，基于 KNN-Shapley 的方法需要最少的运行时间（一些方法，如 TMC-Shapley，甚至不能在合理的时间内完成运行）；（2）对于不同的 ML 应用（例如，错误标记的数据检测、水印去除、数据摘要、主动数据采集和域自适应），基于 Shapley 的方法的不同变体始终优于基于 LOO 的方法；（3）与其他 Shapley 近似方法相比，基于 KNN-Shapley 的方法（包括 KNN-和 max-KNN-Shapley）总是获得最佳或至少可比的性能。
4.4 不同嵌入方式的对比
我们利用其他 4 个预训练分类器提取的不同嵌入进行评估：ResNet18、VGG11、Inception-V3 和 EfficientNet B7。
图 5
我们在图 5 中为选定的应用程序和数据集提供了部分结果。在每个图中，显然有两组曲线：一组用于 KNN-Shapley，另一组用于 KNN-LOO。我们可以看到，KNN-LOO 的效用与 random 大致相同，而 KNN-Shapley 对于不同的应用具有较高的效用。综上所述，与使用不同措施相比，使用不同嵌入所引起的差异是微小的。此外，我们基于 KNN-Shapley 的重要性度量对嵌入的选择不敏感，并且可以实现出色的性能。
5 结论
本文提供了第一个理论和大规模实证研究，旨在回答以下基本问题：应该使用什么方法来评估数据重要性，以及如何有效地进行评估。特别是，我们证明了基于 Shapley 的方法在评估数据重要性的预测能力以及数据识别能力方面比基于 LOO 的方法具有更高的效用。在五个应用程序上进行了大量实验，结果表明基于 Shapley 的方法在运行时和实验性能方面都优于基于 leave-one-out 的方法。具体而言，KNN-Shapley 方法提供了最有效的解决方案，通常在所有方法中实现了最佳或可比的性能。此外，我们是第一个利用数据重要性方法来执行水印移除的公司，这是目前一项具有挑战性的任务，并取得了显著的成果。这个特殊的应用程序将为未来的水印分析和其他相关任务的研究提供帮助。
致谢
本文由南京大学软件学院 2021 级硕士孙晨翻译转述，尹伊宁审核。
