Efficient Data Valuation with Exact Shapley Values

利用精确Shapley值实现高效数据估值

Efficient Data Valuation with Exact Shapley Values

利用精确Shapley值实现高效数据估值

Produce Better Models with Less Data.

用更少的数据打造更好的模型

This post is an overview of the work done in the paper — ‘Efficient task-specific data valuation for nearest neighbour algorithms’.

本文概述了论文《面向最近邻算法的高效任务特定数据估值》中所做的工作。

Does more data always produce better results? Given the trends in machine learning, you would expect as much. More data seems king given the recent rise in larger and larger machine learning models with exceptional performance.

更多数据总是能带来更好的结果吗？根据机器学习的趋势，你可能会这么认为。鉴于近期规模越来越大、性能卓越的机器学习模型的兴起，更多数据似乎就是王道。

This pattern is exemplified in advances in Machine learning like OpenAIs GPT-3 model, trained on over 45 terabytes of data from books and the internet to support its 175 billion parameters. But this model is effectively dwarfed by Google’s new switch Transformer architecture with 1.6 trillion parameters. So it appears that bigger and bigger models with more and more data are inevitable.

这种模式在机器学习的进展中得到了充分体现，比如OpenAI的GPT-3模型，它使用来自书籍和互联网的超过45TB数据进行训练，以支撑其1750亿个参数。但这个模型在Google新的Switch Transformer架构面前相形见绌，后者拥有1.6万亿个参数。因此，模型越来越大、数据越来越多似乎是不可避免的趋势。

If data is so valuable, should we aim to gather more? Why shouldn’t we have more of what is so valuable?

如果数据如此有价值，我们是否应该致力于收集更多？为什么不多收集一些这么有价值的东西呢？

There is a problem with this approach. What if the additional data you gather is irrelevant to your problem. What if it is purely noise? Then any additional data will actively hurt the performance of your model. So what can you do to mitigate this problem?

如果数据如此有价值，我们是否应该致力于收集更多？为什么不多收集一些这么有价值的东西呢？

Well, for one, you can painstakingly look through your data. This approach is probably one of the most effective tools but is highly time-consuming when you have a lot of data. For computer vision tasks, there are a lot of different techniques that you can use. This post shows some exciting techniques for precisely that.

一方面，你可以费力地仔细检查你的数据。这种方法可能是最有效的工具之一，但当数据量很大时，它非常耗时。对于计算机视觉任务，有许多不同的技术可以使用。本文展示了一些针对这类问题的有趣技术。

For many cases, the applicable data is relatively easy to identify. However, for others, it is an unclear task at best. Often part of the problem is that the relationships between the data and the outcome are what we’re trying to model. Then identifying what data is most applicable is an arduous task.

在许多情况下，适用的数据相对容易识别。然而在其他情况下，这充其量是一项不清晰的任务。问题的一部分往往在于，数据和结果之间的关系正是我们试图建模的内容。这时，识别哪些数据最适用就成为一项艰巨的任务。

Fortunately, there is a new method that is perfect for this scenario based on Shapley values.

幸运的是，有一种基于Shapley值的新方法非常适合这种场景。

SHAP Values

SHAP值

SHapley Additive exPlanations (SHAP) is a game-theoretic approach to explain the output of any machine learning model. This method is fairly well known, but the attribution is based solely on the features.

SHAP（SHapley Additive exPlanations）是一种基于博弈论的方法，用于解释任何机器学习模型的输出。这种方法相当知名，但其归因完全基于特征。

The method provides attribution values from features to the output of the model. SHAP values are based on the Shapley values, which determine how to distribute payment among multiple players in a game fairly. For SHAP values, the coalitions of players are based on the features.

该方法提供从特征到模型输出的归因值。SHAP值基于Shapley值，后者用于确定如何在博弈中的多个参与者之间公平分配收益。对于SHAP值，参与者的联盟是基于特征构建的。

SHAP values are incredibly flexible. For example, in computer vision tasks, SHAP values represent the attribution of different pixels to the model’s output. There are many different methods to calculate SHAP values, including a KernelSHAP method which is model-independent.

SHAP值具有极大的灵活性。例如，在计算机视觉任务中，SHAP值表示不同像素对模型输出的归因贡献。有多种计算SHAP值的方法，其中包括与模型无关的KernelSHAP方法。

For each variation of SHAP values, the attributions are always related to the features of the models. However, there is an alternative. Use the instances as the players and calculate attribution for each instance.

对于SHAP值的每种变体，归因总是与模型的特征相关。然而，还有一种替代方案：将样本实例作为参与者，并计算每个实例的归因值。

Data Valuation

数据估值

‘Efficient task-specific data valuation for nearest neighbour algorithms’ is a recent paper providing novel algorithms to calculate exact Shapley values. For the rest of this post, I refer to the Shapley values produced for each instance as Data Shapley Values.

《面向最近邻算法的高效任务特定数据估值》是一篇近期论文，提供了计算精确Shapley值的新算法。在本文的剩余部分，我将为每个实例生成的Shapley值称为数据Shapley值。

Data Shapley Values are a recent innovation that utilizes Shapley values to determine the attribution of different data instances. The motivation of the research was inspired by optimizing records selected from a data market for privacy-preserving machine learning. The data market consists of many different medical records. Therefore, the data buyer chooses a subset of records to purchase from the data market. Because of the data cost, the buyer aim’s to select an optimal subset of patients for their model.

数据Shapley值是一项近期创新，利用Shapley值来确定不同数据实例的归因贡献。该研究的动机源于为隐私保护机器学习从数据市场优化选择记录的启发。数据市场包含许多不同的医疗记录。因此，数据购买者从数据市场中选择一部分记录进行购买。由于数据成本，购买者的目标是为他们的模型选择最优的患者子集。

The Shapley values in this problem configuration measure the marginal improvements of the utility attributed to each data point average overall possible data subsets.

在此问题配置中，Shapley值衡量每个数据点对所有可能数据子集的平均边际效用改进。

The most significant issue for computing Shapley values is the high degree of complexity. Generally, this is on the level of O(2^N) for exact calculations.

计算Shapley值的最大问题是其高复杂度。一般来说，精确计算的时间复杂度为O(2^N)级别。

However, the researchers have developed a novel algorithm for exact Shapley values designed for K-NN classifiers using a KNN utility. This algorithm relies on the fact that the KNN utility satisfies a piecewise utility difference property.

然而，研究人员开发了一种针对K最近邻（K-NN）分类器的新型精确Shapley值算法，该算法使用KNN效用函数。该算法依赖于KNN效用满足分段效用差属性这一事实。

I’ll leave the exact mathematical formulation for the paper and the curious readers. But here is the result. The algorithm performs exact computation with O(N log N) complexity.

我将把精确的数学公式留给论文和好奇的读者。但结果是这样的：该算法以O(N log N)的复杂度执行精确计算。

Experiments

实验

The structure of the experiments follows a simple format. First, the data is separated into training, validation, and test sets. Then, the exact Shapley values are calculated based on the attribution of the training instances to the validation instances.

实验结构遵循简单的格式。首先，将数据划分为训练集、验证集和测试集。然后，基于训练实例对验证实例的归因贡献计算精确Shapley值。

Then the training instances are ordered according to their Shapley values. This setup provides the user with the attributions of each instance to the validation set. Next, the user can select only those instances with the highest Shapley value, providing the user with a smaller subset of data.

然后根据Shapley值对训练实例进行排序。这种设置向用户提供了每个实例对验证集的归因值。接下来，用户可以选择仅保留那些具有最高Shapley值的实例，从而获得一个较小的数据子集。

As this process selects data that contributes the most to the performance on the validation set, removing instances will low Shapley values often removes the noisiest instances within the data. And, at the same time, maintaining the most representative examples.

由于该过程选择的是对验证集性能贡献最大的数据，移除Shapley值较低的实例通常会移除数据中噪声最大的样本，同时保留最具代表性的样本。

The experiments use the diamonds dataset. This dataset contains almost 54,000 diamonds. The features include diamond attributes such as the carat of the diamond, the cut, the colour, and several other features. Some of the features are categorical, and for these experiments, I transform these features into boolean features for each category.

实验使用diamonds数据集。该数据集包含近54,000颗钻石。特征包括钻石的属性，如克拉数、切工、颜色以及其他几个特征。其中一些特征是分类变量，在这些实验中，我将这些特征转换为每个类别的布尔特征。

The target is the price of the diamonds.

目标是预测钻石的价格。

I’ve taken 5000 instances for validation and testing. The remainder of the data is used for training.

我取5000个实例用于验证和测试，其余数据用于训练。

The aim is to produce a model to predict the price of diamonds using less data. I’ve evaluated the performance with a single decision tree regressor. The data is ordered based on the Shapley value, and the performance is measured with an R² score.

目标是使用更少的数据构建一个预测钻石价格的模型。我使用单棵决策树回归器评估性能。数据根据Shapley值排序，性能用R²分数衡量。

Next, the Shapley values are calculated for the validation. The chunk of code also sequentially fits a model on smaller amounts of data. The data is considering according to decreasing Shapley Values.

接下来，计算验证集的Shapley值。代码块还按顺序在较少数据量上拟合模型。数据按Shapley值降序排列。

Once the model is trained on the subset of training data, the model is evaluated on the test dataset.

一旦模型在训练数据子集上训练完成，就在测试数据集上评估该模型。

The experiment results show that with less data, the model performs better on the test data. The peak of the test performance occurs when almost 50% of the training data is removed.

实验结果表明，使用更少的数据时，模型在测试数据上表现更好。测试性能的峰值出现在移除近50%的训练数据时。

What is also intriguing is that the model performance on the validation set peaks when over 60% of the training data is removed. Since the instances are removed based on the Shapley values on the validation set, this pattern makes some sense.

同样有趣的是，当移除超过60%的训练数据时，模型在验证集上的性能达到峰值。由于实例是根据验证集上的Shapley值移除的，这种模式在一定程度上是合理的。

Conclusion

结论

Despite the increasing availability of a massive amount of data, the quality of the data is crucial. Building your models on low-quality data produces low-quality models.

尽管大量数据的可获得性日益增加，但数据的质量至关重要。在低质量数据上构建模型只会产生低质量的模型。

Utilizing Shapley values on instances offer an alternative approach. You can create your models with fewer instances and get improved performance. The experiments show that less data can improve the model performance even with a dramatically smaller subset of data.

在实例上利用Shapley值提供了一种替代方法。你可以使用更少的实例构建模型并获得更好的性能。实验表明，即使数据子集大幅缩小，更少的数据也能提升模型性能。

Data is the new oil, but the quality of that oil matters.

数据是新的石油，但石油的质量至关重要。

Consider using data Shapley values in your next machine learning model.

考虑在你的下一个机器学习模型中使用数据Shapley值。