On the Inflation of KNN-Shapley Value

## Abstract

Abstract Shapley value-based data valuation methods, originating from cooperative game theory, quantify the usefulness of each individual sample by considering its contribution to all possible training subsets. Despite their extensive applications, these methods encounter the challenge of value inflation—while samples with negative Shapley values are detrimental, some with positive values can also be harmful. This challenge prompts two fundamental questions: the suitability of zero as a threshold for distinguishing detrimental from beneficial samples and the determination of an appropriate threshold. To address these questions, we focus on KNN-Shapley and propose Calibrated KNN-Shapley (CKNN-Shapley), which calibrates zero as the threshold to distinguish detrimental samples from beneficial ones by mitigating the negative effects of small-sized training subsets. Through extensive experiments, we demonstrate the effectiveness of CKNN-Shapley in alleviating data valuation inflation, detecting detrimental samples, and assessing data quality. We also extend our approach beyond conventional classification settings, applying it to diverse and practical scenarios such as learning with mislabeled data, online learning with stream data, and active learning for label annotation.

## 1 Introduction

The significance of data as inputs in machine learning algorithms cannot be overstated for algorithmic performance [, ]. Beyond the development of sophisticated algorithms, there is a growing emphasis on the curation of high-quality training sets. Departing from the conventional practice of isolating data from the learning algorithm, a surge in data-centric learning has emerged to assess the valuation of data within the context of a learning task. This encompasses a spectrum of tasks, ranging from outlier detection [] to noisy label correction [], best subset selection [] to sample reweighting [], and antidote data generation [, ] to active labeling [, ].

Understanding the value of an individual data sample is fundamental in data-centric learning, often assessed by the shift in learning utility when the model is trained with and without that specific sample. Leave-one-out influence [], a straightforward method, offers an initial assessment of the relative influence of the specific sample compared to the rest of the training set. On the other hand, Shapley value-based data valuation methods [, ], originating from cooperative game theory, quantifies the usefulness of each individual sample towards the utility on a validation set by considering its contribution to all possible training subsets. Unlike the leave-one-out influence, Shapley value represents the weighted average utility change resulting from adding the point to different training subsets, showcasing greater robustness in diverse contexts [, , ]. Despite the absence of assumptions on the learning model, the retraining-based category mentioned above incurs significant computation costs, especially for large-scale data analysis and deep models [].

With the advent of KNN-Shapley [, ], a pragmatic tool enabling the computation of Shapley values without the need for costly model retraining, Shapley-based approaches have become feasible and widely applied. KNN-Shapley leverages the K-Nearest Neighbors classifier as a surrogate for the original learning model, recursively calculating the Shapley value for each training sample. Despite their promise, KNN-Shapley and its variants grapple with the issue of value inflation. While samples with negative Shapley values are recognized as detrimental, the dilemma arises as certain samples with positive values may also have harmful effects. This challenge gives rise to two pivotal questions: the appropriateness of zero as a threshold for distinguishing detrimental from beneficial samples and the identification of a suitable threshold.

Our Contributions. In this paper, we focus on addressing the value inflation issue observed in KNN-Shapley. To tackle this, we propose Calibrated KNN-Shapley (CKNN-Shapley), which calibrates zero as the threshold to distinguish detrimental samples from beneficial ones by mitigating the negative effects of small training subsets. Our contributions are summarized as follows:

- •
We unveil the value inflation issue of KNN-Shapley, which not only misidentifies a portion of detrimental samples as beneficial, but also distorts the interpretation of data valuation. Beyond the misidentified samples, value inflation further impacts the assessment of beneficial samples.
- •
We propose CKNN-Shapley to calibrate zero as the threshold to distinguish detrimental samples from beneficial ones. Our hypothesis attributes value inflation to improper subset selection in KNN-Shapley, and we address this issue through a straightforward yet effective strategy by imposing a constraint on the size of training subsets.
- •
We perform comprehensive experiments on various benchmark datasets, comparing CKNN-Shapley with KNN-Shapley-based methods. The results showcase the effectiveness of CKNN-Shapley in mitigating value inflation and improving classification performance. We also extend our approach beyond conventional classification settings, applying it to learning with mislabeled data, online learning with stream data, and active learning for label annotation.

Related Work. We introduce Shapley-based methods with a major focus on data valuation and KNN-Shapley. (i) Shapley-based Data Valuation. The Shapley value [, ] measures the weighted average utility change when adding a point to all possible training subsets, making it a primary tool for assessing the valuation of individual samples []. Shapley-value based methods have found extensive application in various domains, including variable selection [, ], feature importance [, , ], model valuation [], health care [, ], federated learning [], collaborative learning [], data debugging [], and distribution analysis [, ].
Building upon this concept, Beta Shapley [] and Banzhaf value [] are developed by relaxing the efficiency axiom of the Shapley value. While Shapley-based data valuation approaches are model-agnostic, exponential model retraining renders these methods computationally challenging even for small datasets  [, ]. Efforts to accelerate computation include efficient sampling [], utility learning [], and the assumption of independent utility []. In addition to data valuation. (ii) KNN-Shapley Data Valuation. KNN-Shapley [, ] emerges as one of the most promising solutions to mitigate the computational challenges associated with Shapley values. It leverages assumptions about the learning model by employing a KNN classifier as a surrogate, recursively computing the Shapley value for each training sample without the need for retraining. This high efficiency has spurred the development of numerous KNN-Shapley variants, such as weighted KNN [], soft KNN [], and threshold KNN[], tailored to enhance generalization, sample reuse, and privacy risks, respectively. In this paper, our focus is on the KNN-Shapley category, with the objective of addressing issues related to value inflation.

## 2 Preliminaries and Motivation

In this section, we introduce the preliminaries of Shapley-based valuation and reveal its value inflation.

Preliminaries. For a training set $\mathcal{D}$ with $N$ samples and a learning algorithm $\mathcal{A}$, let $U_{\mathcal{A},\mathcal{D}_{v}}(\mathcal{D})$ represent the model utility with all training data on the validation set $\mathcal{D}_{v}$. For simplicity, we use $U(\mathcal{D})$ in the following manuscript. The Shapley value [] of a training sample $z_{i}$$\in$$D,$$1$$\leq$$i$$\leq$$N$ is defined as follows:

$$ $\nu^{s}(z_{i})=\frac{1}{N}\sum_{\mathcal{S}\subseteq\mathcal{D}\backslash z_{i }}\frac{1}{{\binom{N-1}{|\mathcal{S}|}}}[U(\mathcal{S}\cup z_{i})-U(\mathcal{S })],$ (1) $$

where $\mathcal{S}$ is a training subset. The Shapley value gauges the average contribution of $z_{i}$ on all possible subsets of $\mathcal{D}$ without $z_{i}$ from the cooperative game perspective. Note that obtaining the exact Shapley value necessitates $2^{N}$ model trainings. Despite no assumption of the learning algorithm $\mathcal{A}$, for large models, this process consumes significant computational resources and time. The impracticality of the exact Shapley value’s expensive complexity, even with Monte Carlo approximation, becomes evident in large-scale data analysis with substantial models.

KNN-Shapley [] occurs as a pragmatic tool for computing Shapley values efficiently. It employs a KNN classifier as a surrogate for the learning algorithm $\mathcal{A}$. For a single validation sample $\mathcal{D}_{v}$$=$$\{z_{v}\}$, where $z_{v}$$=$$(x_{v},y_{v})$ contains $x_{v}$ in the feature space and $y_{v}$ in the label space, a KNN classifier sorts the whole training data and identifies $K$ nearest neighbors in the feature space $(z_{\alpha_{1}},z_{\alpha_{2}},\cdots,z_{\alpha_{K}})$ to $z_{v}$, where $\alpha_{k}$ represents the index of the training samples with the $k$-th neighbor to the validation sample $z_{v}$. If the predictive confidence is used as the model utility, i.e., $U(\mathcal{S})=\frac{1}{K}\sum_{k=1}^{\textup{min}\{K,|\mathcal{S}|\}}\mathbbm
{1}[y_{\alpha_{k}}$$=$$y_{v}]$, KNN-Shapley values can be calculated recursively as follows:

$$ $\nu^{k}_{\textup{}}(z_{\alpha_{N}})=\frac{\mathbbm{1}[y_{\alpha_{N}}=y_{v}]}{N },\ \ \nu^{k}_{\textup{}}(z_{\alpha_{i}})=\nu^{k}_{\textup{}}(z_{\alpha_{i+1}} )+\frac{\mathbbm{1}[y_{\alpha_{i}}=y_{v}]-\mathbbm{1}[y_{\alpha_{i+1}}=y_{v}]} {\max\{K,i\}}.$ (2) $$

The above Eq. (2) can be extended to multiple validation samples by summing up the KNN-Shapley value for each validation sample. This results in a time complexity of $\mathcal{O}(N\log N)$ for KNN-Shapley, significantly faster than the vanilla Shapley. It is worth noting that KNN is a lazy classifier without any training process; therefore, within the retrain-based Shapley framework, KNN-Shapley can directly conduct the inference process, significantly reducing the time complexity compared to other training-required classifiers. Moreover, for certain deep models, KNN-Shapley is compatible with the embedding of training/validation samples for data valuation [].

Figure: Figure 1: Illustration of KNN-Shapley value inflation. The bar plot displays the histogram of KNN-Shapley values for training samples in the SST-2 dataset []. For the purpose of visualization, we merge the samples with extremely small or large values into the leftmost or rightmost bars. With a segmentation of 20 equally-sized bins based on the ascending order of their values, the red line illustrates KNN performance with a specific bin removed from the training set, while the dashed green line represents KNN performance on the entire training set. By comparing the red and green lines, the detrimental bin can be identified, as the performance improves upon its removal. While samples with negative KNN-Shapley values are generally detrimental, a notable observation is the green shallow highlighted region, where samples are harmful to the learning task despite having positive KNN-Shapley values, indicating the issue of KNN-Shapley value inflation.

Inflation of KNN-Shapley Value.
Despite the wide range of applications and efficiency of KNN-Shapley, we have observed a phenomenon of value inflation during its practical usage. This occurs when, contrary to the expectation that samples with negative Shapley values are detrimental, some samples with positive values can also be harmful. Figure 1 illustrates this phenomenon on the SST-2 dataset []. The bar plot shows the histogram of KNN-Shapley values for training samples. According to the ascending order of their values, we segment the whole training set into 20 equally sized bins. To identify whether samples in a specific bin are detrimental or beneficial, we train the KNN classifier with that bin removed from the training set (denoted by the red line) and compare its performance with the complete training set (denoted by the green line). Due to the equal-size samples in each bin, the markers on the red line do not have uniform intervals and do not align with unevenly sized histograms. While samples with negative KNN-Shapley values are generally detrimental, the highlighted green shallow region reveals a noteworthy observation—samples in this region are harmful to the learning task despite having positive KNN-Shapley values, indicating the issue of KNN-Shapley value inflation. Note that the number of samples with negative KNN-Shapley values is 1,452, while 4,548 samples are in the misidentified region. Moreover, removing all the samples with negative KNN-Shapley values enhances performance from 0.7270 to 0.8160. Conversely, further improvement is achieved by removing samples in the misidentified region, boosting performance from 0.8160 to 0.8980 and underscoring the significance of addressing inflated samples.

Value inflation prompts two
fundamental questions: the suitability of zero as
a threshold for distinguishing detrimental from
beneficial samples and the determination of an
appropriate threshold. To address these questions, we propose Calibrated KNN-Shapley in the next section, which calibrates zero
as the threshold to distinguish detrimental samples
from beneficial ones.

## 3 Calibrated KNN-Shapley

To address the challenge of valuation inflation in KNN-Shapley, we first delve into its underlying mechanism and scrutinize potential factors contributing to negative effects on data valuation. Based on the analyzed reasons, we propose our Calibrated KNN-Shapley by mitigating the negative efforts from improper training subsets.

While the recursive formulation in Eq. (2) brings about efficient computation, it also introduces inevitable accumulated errors. Specifically, the valuation of a training sample distant from the validation sample can influence other training samples closer to the validation sample, emphasizing the importance of the first term $\nu^{k}_{\textup{}}(z_{\alpha_{N}})$. Upon closer examination of $z_{\alpha_{N}}$, the farthest sample from the validation sample, we observe its minimal impact on the validation sample. Considering the definition of the Shapley value, which measures the average contribution of a training sample across all possible subsets, we discuss two cases. Case I: when $|\mathcal{S}|$$>$$K$, $z_{\alpha_{N}}$ does not contribute to the utility of the KNN classifier since it is not among the neighbors of $z_{v}$. Case II: when $|\mathcal{S}|$$\leq$$K$, $\nu^{k}_{\textup{}}(z_{\alpha_{N}})$ is non-negative, i.e., $\nu^{k}_{\textup{}}(z_{\alpha_{N}})$$=$$1/N$ if $z_{\alpha_{N}}$ and $z_{v}$ share the same label; otherwise, $\nu^{k}_{\textup{}}(z_{\alpha_{N}})$$=$0 0. Notably, it is impractical and meaningless to have a training subset with only a few training samples. Furthermore, the number of occurrences in Case I significantly surpasses that in Case II, indicating that Case II is not representative for a learning model and data valuation.

Building on the above analyses, we hypothesize that value inflation stems from improper subset selection in KNN-Shapley. Certain subsets with only a few samples exhibit significant divergence from the original set, leading to an exaggeration of the contribution of a specific sample on these subsets. This, in turn, gives rise to the phenomenon of value inflation. To address the issue of value inflation, we introduce Calibrated KNN-Shapley (CKNN-Shapley) through the selection of suitable training subsets. The training subset in CKNN-Shapley should serve as an effective proxy for the original and complete training set. In this paper, we present a straightforward yet effective strategy by imposing a constraint on the size of training subsets, specifically $|\mathcal{S}|$$\geq$$T$, where $T$ represents the size of the smallest training subsets used to assess the contribution of each training sample. This allows us to compute the CKNN-Shapley value as follows:

$$ $\begin{split}&\nu^{c}_{\textup{}}(z_{\alpha_{N}})=\nu^{c}_{\textup{}}(z_{ \alpha_{N-1}})=\cdots=\nu^{c}_{\textup{}}(z_{\alpha_{N-T+1}})=0,\\ &\nu^{c}_{\textup{}}(z_{\alpha_{N-T}})=\frac{\mathbbm{1}[y_{\alpha_{N-T}}=y_{v }]}{N-T},\ \nu^{c}_{\textup{}}(z_{\alpha_{i}})=\nu^{c}_{\textup{}}(z_{\alpha_{ i+1}})+\frac{\mathbbm{1}[y_{\alpha_{i}}=y_{v}]-\mathbbm{1}[y_{\alpha_{i+1}}=y_ {v}]}{\max\{K,i\}}.\end{split}$ (3) $$

Compared to KNN-Shapley in Eq. (2), CKNN-Shapley follows a similar recursive fashion but more efficiently. This efficiency stems from directly assigning zero to $T$ samples that are far away from the validation sample. Additionally, in CKNN-Shapley, the selected training subsets consist of at least $T$ samples, preventing the inclusion of improper subsets that could contribute to the valuation.

Figure: Figure 2: Comparison of KNN-Shapley and CKNN-Shapley value on the SST-2 dataset [], where each dashed line represents a training sample associated with its KNN-Shapley and CKNN-Shapley values, respectively, and the green region is the misidentified detrimental samples from Figure 1. The red dashed lines denote the samples that are incorrectly identified by KNN-Shapley but correctly identified by CKNN-Shapley.

Figure 2 illustrates the comparison between KNN-Shapley and CKNN-Shapley values on the SST-2 dataset. Each dashed line represents a training sample associated with its KNN-Shapley and CKNN-Shapley values. Detrimental samples misidentified by KNN-Shapley, highlighted by red dashed lines, are assigned negative or zero values in CKNN-Shapley, suggesting that zero in CKNN-Shapley serves as a suitable threshold for distinguishing detrimental from beneficial samples. Additionally, the majority of lines from KNN-Shapley to CKNN-Shapley move from the top right to the bottom left. This indicates that KNN-Shapley not only has a negative effect on the misidentified samples but also tends to inflate the valuation of most samples. This inflation might be attributed to its recursive formulation, leading to the accumulation of errors within KNN-Shapley.

As a variant of KNN-Shapley, our CKNN-Shapley inherently integrates several key axioms from KNN-Shapley, focusing on three fundamental principles: group rationality, fairness, and additivity, as emphasized in []. CKNN-Shapley prioritizes fairness, ensuring symmetry (where two identical samples receive identical Shapley values) and zero elements (no contribution, no payment). Additionally, it upholds additivity, where values across multiple utilities sum up to the value under a utility that is the aggregate of all these utilities. Enhancing group rationality, CKNN-Shapley refines this axiom by disregarding subsets with fewer than
$T$ samples, thereby distributing the utility difference between the entire dataset and the subset. Since the utility of a subset, according to the KNN classifier, expects only the nearest samples to contribute, the utility of such a subset is anticipated to be zero, a factor overlooked in KNN-Shapley. By addressing this, CKNN-Shapley mitigates the adverse impact of overemphasizing the cooperative game with samples distant from the target sample, rendering the axiom of group rationality more compatible with the KNN classifier.

**Table 1: Threshold for distinguishing detrimental from beneficial samples and the misidentification ratio of detrimental samples in Eq. (4) for KNN-Shapley-based methods. For the first metric, closer to zero is preferable; Regarding the second one, smaller values suggest better performance. The last column takes the absolute values for average. The best results are highlighted in bold. TKNN-Shapley does not return meaningful results on CIFAR10 with the default parameters, denoted by “N/A."**
| Datasets | MNIST | FMNIST | CIFAR10 | Pol | Wind | CPU | AGnews | SST-2 | News20 | Avg. |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Threshold for distinguishing detrimental from beneficial samples by $\times$ $1e$$-4$ |  |  |  |  |  |  |  |  |  |  |
| KNN-Shapley [] | 0.2744 | 0.2631 | 0.1632 | 2.0361 | 7.3705 | 6.4458 | 1.6264 | 1.3659 | 1.7215 | 2.3630 |
| KNN-Shapley-JW [] | 0.2544 | 0.2431 | 0.1432 | 0.5119 | 4.6543 | 3.7429 | 1.3763 | 0.8203 | 1.6780 | 1.4916 |
| TKNN-Shapley [] | 3.8641 | 1.0330 | N/A | -1.4990 | 1.0875 | 5.6960 | 1.1951 | 0.7143 | 5.2628 | 2.5440 |
| CKNN-Shapley (Ours) | 0.0152 | 0.0109 | 0.1163 | -0.3059 | -0.0245 | -2.9412 | 1.1955 | 0.1604 | 0.6715 | 0.6046 |
| Misidentification ratio of detrimental samples |  |  |  |  |  |  |  |  |  |  |
| KNN-Shapley [] | 0.8065 | 0.5145 | 0.4908 | 0.3333 | 0.3864 | 0.5714 | 0.7580 | 0.5600 | 0.6179 | 0.5599 |
| KNN-Shapley-JW [] | 0.7665 | 0.4367 | 0.3792 | 0.0000 | 0.2727 | 0.3846 | 0.6563 | 0.3421 | 0.5541 | 0.4214 |
| TKNN-Shapley [] | 0.3103 | 1.0000 | N/A | 0.0000 | 0.1818 | 0.4118 | 0.2273 | 0.1862 | 0.2000 | 0.3147 |
| CKNN-Shapley (Ours) | 0.2000 | 0.1686 | 0.0908 | 0.0000 | 0.0000 | 0.0000 | 0.1538 | 0.1143 | 0.1821 | 0.1011 |

**Table 2: Classification performance of KNN-Shapley-based methods. $\#$ denotes KNN’s performance trained on the training set excluding samples with negative valuations, while $+$ represents weighted KNN’s performance, where the weights are derived from data valuations.**
| Method$\backslash$Datasets | MNIST | FMNIST | CIFAR10 | Pol | Wind | CPU | AGnews | SST-2 | News20 | Avg. |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Vanilla KNN | 0.9630 | 0.8444 | 0.5956 | 0.9400 | 0.8700 | 0.9200 | 0.9060 | 0.7270 | 0.6920 | 0.8287 |
| KNN-Shapley []^# | 0.9682 | 0.8586 | 0.6456 | 0.9700 | 0.8750 | 0.9650 | 0.9250 | 0.8160 | 0.7580 | 0.8646 |
| KNN-Shapley-JW []^# | 0.9698 | 0.8574 | 0.6514 | 0.9700 | 0.8650 | 0.9600 | 0.9250 | 0.8498 | 0.7610 | 0.8677 |
| TKNN-Shapley []^# | 0.6644 | 0.8356 | N/A | 0.8150 | 0.8300 | 0.9100 | 0.8990 | 0.7982 | 0.6730 | 0.8032 |
| CKNN-Shapley (Ours)^# | 0.9828 | 0.8884 | 0.7164 | 0.9700 | 0.9000 | 0.9700 | 0.9420 | 0.8980 | 0.7960 | 0.8960 |
| KNN-Shapley []^+ | 0.9742 | 0.8680 | 0.6598 | 0.9650 | 0.8700 | 0.9300 | 0.9333 | 0.8480 | 0.7790 | 0.8697 |
| KNN-Shapley-JW []^+ | 0.9754 | 0.8658 | 0.6610 | 0.9650 | 0.8700 | 0.9300 | 0.9320 | 0.8555 | 0.7790 | 0.8704 |
| TKNN-Shapley []^+ | 0.8626 | 0.7900 | N/A | 0.8600 | 0.8200 | 0.8950 | 0.9110 | 0.8326 | 0.7160 | 0.8359 |
| CKNN-Shapley (Ours)^+ | 0.9890 | 0.9106 | 0.7404 | 0.9700 | 0.9050 | 0.9650 | 0.9450 | 0.8920 | 0.8130 | 0.9033 |

## 4 Experimental Results

In this section, we present the experimental results of KNN-Shapley, its variant TKNN-Shapley, and our proposed CKNN-Shapley on several widely used benchmark datasets in the data valuation domain. We begin by detailing the experimental setup, with a specific emphasis on the evaluation metric used to quantify value inflation. Subsequently, we showcase the algorithmic performance in addressing value inflation and enhancing classification performance. Finally, we delve into several in-depth explorations of CKNN-Shapley for practical applications.

Experimental Setup. Here we use 9 datasets for empirical evaluation. MNIST, FMNIST [], and CIFAR10 are image datasets with 50,000 samples; Pol, Wind, and CPU [] are from the telecommunication, meteorology, and computer hardware domains, respectively, with 2,000 samples each; AGnews, SST-2 [], and News20 [] are text datasets with 10,000 samples. For the CIFAR10 and text datasets, we employ the ResNet50 [] and Sentence Bert [] as embedding for the KNN classifier, respectively. Features/embeddings of these nine datasets are from 14 to 2,048. The detailed characteristics of these datasets can be found in Appendix A. For the baseline methods, we choose the KNN-Shapley [], KNN-Shapley-JW [], and TKNN-Shapley [] with default setting $K$$=$$10$ and $\tau$$=$$-0.5$. Besides, we set $T$$=$$N$$-$$2K$ in our CKNN-Shapley.

Figure: Figure 3: Execution time and parameter analysis. A shows the execution time by second in the logarithm of three KNN-Shapley-based data valuation approaches; B and C display the classification performance trend of our CKNN-Shapley with different values of $K$ and $T$.

In addition to the conventional predictive accuracy for classification, we introduce two metrics to assess valuation inflation: the threshold for distinguishing detrimental samples from beneficial ones and the misidentification ratio of detrimental samples. This approach is inspired by the illustration in Figure 2. The dataset is divided into 100 bins, and the goal is to find the intersection of the red and green lines to determine the threshold for distinguishing detrimental samples. The misidentification ratio is then calculated as the proportion of samples in the green region to all detrimental samples. The entire training dataset is segmented into 100 equal-size bins based on the ascending order of data valuation, denoted as $\nu_{i}$ for the data valuation of the $i$-th bin. Let $p_{i}$ represent the KNN classifier’s performance on the training set without samples in the $i$-th bin, and $p_{0}$ represent the performance on the entire training set. We define the threshold $t$ for distinguishing detrimental samples from beneficial ones and the misidentification ratio $r$ of detrimental samples as follows:

$$ $t=\nu_{j^{*}}\ \textup{and}\ r=(j^{*}-i^{*})/j^{*},$ (4) $$

where $j^{*}=\min_{j}\{p_{j}<p_{0}\ \&\ p_{j+1}<p_{0}\}$ and $i^{*}$ is the index of $i^{*}$-bin with $\nu_{i^{*}}=0$.

All experiments were conducted on a workstation with an AMD Ryzen Threadripper PRO 5965WX CPU and x86_64 architecture with 128 GB memory.

**Table 3: Classification performance of KNN-Shapley-based methods with fixed numbers of removed samples. $\#$, $+$, and $*$ denote KNN’s performance trained on the training set excluding samples with the smallest 10%, 20%, and 30% data valuations, respectively.**
| Method$\backslash$Datasets | MNIST | FMNIST | CIFAR10 | Pol | Wind | CPU | AGnews | SST-2 | News20 | Avg. |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Vanilla KNN | 0.9630 | 0.8444 | 0.5956 | 0.9400 | 0.8700 | 0.9200 | 0.9060 | 0.7270 | 0.6920 | 0.8287 |
| KNN-Shapley []^# | 0.9702 | 0.8590 | 0.6270 | 0.9750 | 0.8850 | 0.9550 | 0.9250 | 0.8016 | 0.7290 | 0.8585 |
| KNN-Shapley-JW []^# | 0.9702 | 0.8590 | 0.6270 | 0.9700 | 0.8850 | 0.9550 | 0.9250 | 0.8016 | 0.7280 | 0.8579 |
| TKNN-Shapley []^# | 0.9516 | 0.8368 | 0.5670 | 0.9450 | 0.8450 | 0.9200 | 0.9190 | 0.7878 | 0.7160 | 0.8320 |
| CKNN-Shapley (Ours)^# | 0.9812 | 0.8822 | 0.6566 | 0.9650 | 0.8950 | 0.9700 | 0.9370 | 0.8108 | 0.7450 | 0.8714 |
| KNN-Shapley []^+ | 0.9714 | 0.8548 | 0.6396 | 0.9650 | 0.8650 | 0.9550 | 0.9250 | 0.8314 | 0.7460 | 0.8615 |
| KNN-Shapley-JW []^+ | 0.9714 | 0.8548 | 0.6396 | 0.9650 | 0.8650 | 0.9550 | 0.9250 | 0.8303 | 0.7470 | 0.8615 |
| TKNN-Shapley []^+ | 0.8744 | 0.7724 | 0.5292 | 0.8850 | 0.8350 | 0.9300 | 0.9170 | 0.8005 | 0.7190 | 0.8069 |
| CKNN-Shapley (Ours)^+ | 0.9814 | 0.8874 | 0.6990 | 0.9700 | 0.9100 | 0.9800 | 0.9450 | 0.8830 | 0.7800 | 0.8929 |
| KNN-Shapley []^∗ | 0.9726 | 0.8536 | 0.6482 | 0.9650 | 0.8600 | 0.9450 | 0.9250 | 0.8452 | 0.7620 | 0.8641 |
| KNN-Shapley-JW []^∗ | 0.9726 | 0.8536 | 0.6482 | 0.9700 | 0.8600 | 0.9550 | 0.9250 | 0.8463 | 0.7600 | 0.8656 |
| TKNN-Shapley []^∗ | 0.8378 | 0.7130 | 0.4716 | 0.8400 | 0.8300 | 0.9100 | 0.9180 | 0.7982 | 0.7100 | 0.7810 |
| CKNN-Shapley (Ours)^∗ | 0.9814 | 0.8882 | 0.7174 | 0.9700 | 0.9100 | 0.9750 | 0.9450 | 0.8968 | 0.7990 | 0.8981 |

Algorithmic Performance. We present the algorithmic comparison of different KNN-Shapley-based methods, focusing on value inflation and classification performance. Table 1 displays the thresholds for distinguishing detrimental from beneficial samples and the misidentification ratio of detrimental samples. KNN-Shapley, KNN-Shapley-JW, and TKNN-Shapley exhibit thresholds far from zero, spanning a wide range across different datasets from 0.1632 to 6.4458, from 0.8203 to 4.6543, and from 0.7143 to 5.6960, respectively. This variability complicates the interpretation of their data valuation. In contrast, our CKNN-Shapley consistently achieves thresholds close to zero, enhancing the meaningfulness of data valuation in practical applications. The misidentification ratios of detrimental samples provide additional insights into these thresholds in terms of sample proportions. KNN-Shapley exhibits substantial misidentification ratios, surpassing 50% on 6 out of 9 datasets. KNN-Shapley-JW also surpasses 50% on 3 out of 9 datasets. TKNN-Shapley shows slightly better performance in terms of the threshold but still exceeds 41% inflation on CPU, while CKNN-Shapley with calibrated thresholds, averages only around 10% inflation of detrimental sets and achieves no inflation on Pol, Wind, and CPU.

In addition to evaluating value inflation, we analyze the impact of inflation on classification performance by removing samples with negative valuation and using weighted KNN. Table 2 compares the results. KNN-Shapley consistently improves performance on all datasets by removing samples with negative KNN-Shapley values, outperforming vanilla KNN with all training samples. However, TKNN-Shapley, designed for membership protection, does not yield desirable performance, possibly due to default parameter settings. In contrast, CKNN-Shapley mitigates the negative effects of inflation on detrimental sets, providing additional performance boosts on almost every dataset, except Pol where both KNN-Shapley and CKNN-Shapley achieve the same performance. Notably, on CIFAR10 and SST-2, CKNN-Shapley exhibits over 7% and 8% performance improvements over KNN-Shapley, addressing the 49% and 56% inflation in misidentification ratios observed in KNN-Shapley on these datasets. In addition to detrimental set inflation, Figure 2 reveals inflation in the beneficial set. We further conduct experiments with a weighted KNN classifier, using weights derived from data valuations, and observe similar phenomena. CKNN-Shapley achieves significant improvements with calibrated data valuations, underscoring the need to address value inflation issues. To address the potential impact of the number of removed samples, we further investigate the setting of removing a fixed amount of samples, as shown in Table 3. Our CKNN-Shapley consistently demonstrates superior performance over various KNN-Shapley-based methods. We extend our analysis by conducting additional experiments that explore misidentified samples and demonstrate the generalization of our CKNN-Shapley approach to other classifiers. Detailed results are presented in Appendix B.

Figure 3A shows the execution time of four methods, where TKNN-Shapley has the fastest speed due to its linear time complexity. For KNN-Shalpley, KNN-Shapley-JW, and our CKNN-Shapley, all of them have the $\mathcal{O}(N\log N)$; CKNN-Shapley is faster since $T/N$ percentage valuations are directly assigned to zero without the recursive calculation. Figure 3B and C display the classification performance trend of our CKNN-Shapley with different values of $K$ and $T$, where a small $K$ and large $T$ but not close to $N$ are preferred. A small $K$ excludes the samples from different categories. Besides, a large $T$ enforces the similar to the original one, while maintaining the diversity of selected training subset. We posit that the choice of $T$ is contingent upon the dataset characteristics. In Appendix B, we explore various settings of $T$ and ascertain that $N$$-$$2K$ serves as a suitable setting.

Figure: Figure 4: The classification performance of KNN on datasets MNIST, FMNIST, and CIFAR10 varies with different training sets and flip ratios. The standard KNN utilizes the full training set, including mislabeled data, whereas KNN-Shapley-based methods start by excluding samples having negative Shapley values from the training set, and then apply the KNN classifier.

Figure: Figure 5: In-depth exploration of CKNN-Shapley on CIFAR10 with 0.3 flip ratio. A depicts the sizes of detrimental and mislabelled samples, where $\mathcal{I}$ denotes the set of samples with non-positive Shapley values but not mislabeled, $\mathcal{II}$ presents the set of joint detrimental and mislabeled samples, and $\mathcal{III}$ is the set of mislabeled samples with positive Shapley values. B shows the value distribution of these three sets. C displays the visual examples of detrimental or mislabeled samples and normal samples.
Refer to caption: extracted/5619651/figures/neg_circle.png

## 5 Applications Beyond Conventional Classification

We extend the conventional classification in the previous section by conducting extensive experiments for various practical scenarios, and demonstrate the effectiveness of our proposed CKNN-Shapley in resisting mislabeled data, mitigating distribution shift, and identifying beneficial samples.(^1^11We omit KNN-Shapley-JW in this section due to its similar performance with KNN-Shapley.)

Learning with Mislabeled Data.
We manually simulate mislabeled data by randomly flipping its original label into another category and conduct experiments on MNIST, FMNIST, and CIFAR10 with different flip ratios. In Figure 4, we observe the KNN performance with different training sets, where vanilla KNN runs on the complete training set with mislabeled data, and KNN-Shapley-based methods first remove samples with negative Shapley values from the training set before training the KNN classifier. In general, KNN-Shapley and CKNN-Shapley effectively resist the negative impact of mislabeled data, outperforming vanilla KNN. Unfortunately, TKNN-Shapley performs poorly, significantly worse than vanilla KNN, and provides no meaningful results on CIFAR10. Due to CKNN-Shapley addressing the value inflation of KNN-Shapley, its performance is further improved and consistently achieves the best results across all three datasets. Notably, CKNN-Shapley maintains similar performance across different flip ratios, demonstrating its resilience to mislabeled data.

Furthermore, we delve into the details of CKNN-Shapley on CIFAR10 with a 0.3 flip ratio, as shown in Figure 5. In Figure 5A, we examine the Shapley values of mislabeled samples, separating the detrimental and mislabeled sets into three categories: $\mathcal{I}$ denotes the set of samples with non-positive Shapley values but not mislabeled, $\mathcal{II}$ represents the set of joint detrimental and mislabeled samples, and $\mathcal{III}$ is the set of mislabeled samples with positive Shapley values. We observe that the majority of mislabeled samples are associated with negative Shapley values, indicating their detrimental nature. Figure 5B presents the value distribution of the three sets, revealing a small portion of mislabeled data with very small positive values. From Table 1, we find that the threshold for distinguishing detrimental and beneficial samples on CIFAR10 is around $0.11\times$$e-$$4$. Several visual examples in Figure 5C illustrate the significant distinction between samples $\mathcal{I},\mathcal{II}$, and $\mathcal{III}$ and normal samples. Samples in $\mathcal{I},\mathcal{II}$, and $\mathcal{III}$ have a dark background, making them difficult to recognize.

Figure: Figure 6: Performance of online learning. A-C depict the online learning performance of KNN-Shapley-based data valuation approaches by removing samples with negative Shapley values on the three text datasets across different batches, where the dashed lines present the performance of vanilla KNN without removing any samples. D displays the remaining training samples in each batch, combining samples from the last batch and new arrivals in the current batch by removing detrimental samples. E provides details of involved training samples for CKNN-Shapley on News20 across different batches, followed by the Shapley value changes of some representative samples in F.

Online Learning.
In addition to static datasets, we further evaluate our approach in the context of online stream data. Specifically, we use three text datasets—AGnews, SST-2, and News20—in this experiment. We segment these datasets into 10 equal-sized batches and gradually feed them into the KNN classifier to simulate stream data. KNN-Shapley-based data valuation approaches are employed to remove detrimental samples with negative Shapley values. Figures 6A-C depict the online learning performance of three KNN-Shapley-based data valuation approaches on the three text datasets across different batches. CKNN-Shapley consistently outperforms other methods with large margins, resolving the value inflation issue and showing more effectiveness in identifying detrimental samples in the stream context. Note that an increasing margin of CKNN-Shapley over others can be observed on AGnews. Figure 6D displays the remaining training samples in each batch, combining samples from the last batch and new arrivals in the current batch by removing detrimental samples. KNN-Shapley involves more training samples compared to others, indicating severe inflation issues. In contrast, CKNN-Shapley removes a significant portion of detrimental samples, enhancing learning performance with fewer training samples. Figure 6E provides details of involved training samples for CKNN-Shapley on News20 across different batches. The blue color denotes a sample included in a batch, while the pink color denotes its removal from the current and subsequent batches. Additionally, Figure 6F shows the Shapley value change for representative samples. The pink line represents a sample included in all batches, while other lines represent samples initially associated with positive Shapley values in the initial batches, which later become negative and are subsequently removed.

Active Learning.
To demonstrate the advantages of Shapley value in improved data utilization efficiency, we further evaluate our approach in the context of active learning. Specifically, to select the unlabeled data for labeling, we use a 2-layer fully connected neural network to fit the relationship between features and Shapley values of labeled training data. Then we use that neural network to predict Shapley values of unlabeled training data and choose the data with highest predicted Shapley values to label. In this experiment, we choose three chemical datasets —Pol, Wind, and CPU. We segment these datasets into two parts, 20 percent of them are used as labeled data, other 80 percent are used as unlabeled data. The unlabeled data will be taken out 8 times through the prediction of neural network. Figure 7 shows the performance of three
KNN-Shapley-based data valuation approaches and three baselines of active learning (i.e., random sampling, entropy sampling [], margin sampling [], uncertainty sampling []) on three chemical datasets. Random sampling involves the completely random selection of unlabeled samples for labeling; entropy sampling chooses samples with high prediction uncertainty, measured by entropy; margin sampling focuses on the gap between the two highest probabilities in the model’s predictions; Uncertainty sampling prioritizes annotation of samples with high nearest neighbor inconsistency. From Figure 7, CKNN-Shapley outperforms other methods and is more effective in identifying useful samples in the unlabeled data, extending the application context of Shapley value and providing a new way to select data for active learning.

Figure: Figure 7: Active learning of different annotation strategies on Pol, Wind, and CPU, where the initial stage has 400 samples and each subsequent step annotates 200 samples into the training set.

## 6 Conclusion

In this paper, we revealed the value inflation of KNN-Shapley, which not only misidentifies a large portion of detrimental samples as beneficial, but also overestimates the value for the majority of samples. To address these issues, we proposed Calibrated KNN-Shapley to calibrate zero as the threshold for distinguishing detrimental samples from beneficial ones, via mitigating the negative effects of small training subsets when calculating data valuation. Through extensive experiments, we demonstrated the effectiveness of CKNN-Shapley in alleviating data valuation inflation and detecting detrimental samples. Furthermore, we extended our approach beyond conventional classification settings to the context of learning with mislabeled samples, online learning, and active learning.

## Appendix

## Appendix A Dataset

A comprehensive list of datasets and sources is summarized in Table 4. Following [], the validation data size we use is also 10% of the training data size. For Pol, Wind, and CPU datasets, we subsample the dataset to balance positive and negative labels. For the image dataset CIFAR10, we apply a ResNet50 [] that is pre-trained on the ImageNet dataset as the feature extractor. This feature extractor produces a 1024-dimensional
vector for each image. We also employ Sentence BERT [] as embedding models to extract features for the text classification dataset AGNews, SST-2, and News20. This feature extractor also produces a 1024-dimensional
vector for each text instance. This method of using a foundation model as a feature extractor can make CKNN-SV well applied to data valuation of deep learning. For other datasets, we do not use any extractor.

**Table 4: A summary of datasets used in experiments**
| Dataset | # Sample | #Dimension | #Class | Embeddings |
| --- | --- | --- | --- | --- |
| MNIST | 50000 | 784 | 10 | None |
| FMNIST | 50000 | 784 | 10 | None |
| CIFAR10 | 50000 | 2048 | 10 | ResNet50 |
| Pol | 2000 | 48 | 2 | None |
| Wind | 2000 | 14 | 2 | None |
| CPU | 2000 | 21 | 2 | None |
| AGnews | 10000 | 384 | 4 | Sentence BERT |
| SST-2 | 10000 | 384 | 2 | Sentence BERT |
| News20 | 10000 | 384 | 2 | Sentence BERT |

## Appendix B Additional Experiments

We provide additional experiments of our CKNN-Shapley in terms of exploration of misidentified samples, generalization on other classifiers, and various values of $T$.

### B.1 Misidentified Samples

Our CKNN-Shapley method exhibits significantly lower false positives compared to other prevalent methods. Since the over-identification of samples as detrimental (FP) is a primary source of value inflation in data valuation, the number of FP samples is much larger than the number of FN samples in all three methods.

**Table 5: False positive and false positive of misidentified samples**
| Method$\backslash$Datasets | MNIST | FMNIST | CIFAR10 | Pol | Wind | CPU | AGnews | SST-2 | News20 | Sum. |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| False positive |  |  |  |  |  |  |  |  |  |  |
| KNN-Shapley | 47 | 21 | 30 | 68 | 71 | 72 | 52 | 55 | 45 | 409 |
| TKNN-Shapley | 17 | 37 | 0 | 47 | 62 | 64 | 15 | 7 | 14 | 263 |
| CKNN-Shapley | 14 | 9 | 7 | 21 | 28 | 22 | 22 | 8 | 17 | 148 |
| False negative |  |  |  |  |  |  |  |  |  |  |
| KNN-Shapley | 0 | 1 | 0 | 1 | 1 | 0 | 2 | 0 | 1 | 6 |
| TKNN-Shapley | 41 | 5 | 55 | 11 | 6 | 8 | 11 | 19 | 18 | 174 |
| CKNN-Shapley | 0 | 5 | 1 | 1 | 2 | 2 | 0 | 2 | 2 | 15 |

### B.2 Generalization

Traditional Shapley values have no constraint on the base classifier, but have to require retraining the base classifier $2^{N}$ times. Therefore, even for a small dataset, $2^{N}$ times model training is inflexible for the traditional Shapley values. KNN-Shapley and its variants including our CKNN-Shapley work a series of pragmatic tools computing Shapley values efficiently in a recursive manner with $O(N\log N)$ or $O(N)$ time complexity. For practice, if the base classifier is not KNN, a routine solution employs the KNN classifier as a surrogate.

To test the generalization of our CKNN-Shapley on different models, we conduct extra experiments with non-KNN classifiers, including Multilayer Perceptron (MLP), Logistic Regression (LR), and Support Vector Machine (SVM). Specifically, we train the non-KNN classifiers with the whole training set, apply KNN-Shapley variants to identify detrimental samples, and finally retrain the non-KNN classifiers with the identified detrimental samples removed. Table 6 reports the accuracy on three datasets. We can see that our CKNN-Shapley can effectively boost the performance of non-KNN classifiers in most cases, indicating a good generalization of CKNN-Shapley across different models.

**Table 6: Generalizability on other classifier**
| Method$\backslash$Datasets | Pol | Wind | CPU |
| --- | --- | --- | --- |
| Vanilla MLP | 0.9909 | 0.8735 | 0.9475 |
| MLP with negative KNN-Shapley value samples removed | 0.9949 | 0.8939 | 0.9455 |
| MLP with negative TKNN-Shapley value samples removed | 0.8515 | 0.8269 | 0.9085 |
| MLP with negative CKNN-Shapley value samples removed | 0.9915 | 0.8979 | 0.9669 |
| Vanilla LR | 0.8700 | 0.8500 | 0.9300 |
| LR with negative KNN-Shapley value samples removed | 0.8800 | 0.8800 | 0.9400 |
| LR with negative TKNN-Shapley value samples removed | 0.8250 | 0.8250 | 0.9200 |
| LR with negative CKNN-Shapley value samples removed | 0.8850 | 0.9350 | 0.9600 |
| Vanilla SVM | 0.9650 | 0.8750 | 0.9400 |
| SVM with negative KNN-Shapley value samples removed | 0.8650 | 0.8850 | 0.9350 |
| SVM with negative TKNN-Shapley value samples removed | 0.8450 | 0.8250 | 0.8900 |
| SVM with negative CKNN-Shapley value samples removed | 0.9600 | 0.8850 | 0.9450 |

### B.3 Rationality of T 𝑇 T italic_T

We consider two aspects when setting $T$. On one aspect, we believe the value inflation comes from the subset with too small sizes, which leads the sizes of subsets to be close to the whole training set (Large $T$). On another aspect, we expect the subsets to be diverse and the number of subsets to be large enough (Small $T$). By considering both, we give a default setting of $T=N-2K$, which makes the subset size large enough and consider $2^{N-2K}\times(2^{2K}-1)$ different subsets.

Moreover, we provide extra experiments of our CKNN-Shalpey with different values of $T$ below. In Table 7, we set $T$ to be $0.95N,0.75N,0.5N$ and report the accuracy performance of removing samples with negative values (Larger value means better performance), threshold for distinguishing detrimental from beneficial samples (Closer to zero value means better performance), and misidentification ratio of detrimental samples (Smaller value means better performance). In general, the setting with $N-2K$ achieves the best average performance on all three metrics. For accuracy, the setting with $N-2K$ achieves the best performance on all datasets compared with other settings. For other metrics, the setting with $N-2K$ delivers competitive results. Therefore, we chose $T=N-2K$ as the default setting.

**Table 7: Performance of CKNN-Shapley with different values of $T$**
| Method$\backslash$Datasets | MNIST | FMNIST | CIFAR10 | Pol | Wind | CPU | AGnews | SST-2 | News20 | Avg./Abs. |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| T | 0.9630 | 0.8444 | 0.5956 | 0.9400 | 0.8700 | 0.9200 | 0.9060 | 0.7270 | 0.6920 | 0.8287 |
| Acc after remove samples with negative Shapley values |  |  |  |  |  |  |  |  |  |  |
| N-2K | 0.9828 | 0.8884 | 0.7164 | 0.9700 | 0.9000 | 0.9700 | 0.9420 | 0.8980 | 0.7960 | 0.8960 |
| 0.95N | 0.9698 | 0.8444 | 0.6556 | 0.9700 | 0.8850 | 0.9650 | 0.9270 | 0.8612 | 0.7700 | 0.8719 |
| 0.75N | 0.9696 | 0.8444 | 0.6520 | 0.9650 | 0.8600 | 0.9450 | 0.9250 | 0.8463 | 0.7610 | 0.8632 |
| 0.5N | 0.9630 | 0.8444 | 0.6498 | 0.9650 | 0.8650 | 0.9500 | 0.9250 | 0.8474 | 0.7590 | 0.8631 |
| Threshold for distinguishing detrimental from beneficial samples by $\times$ $1e$$-4$ |  |  |  |  |  |  |  |  |  |  |
| N-2K | 0.0152 | 0.0109 | 0.1163 | -0.3059 | -0.0245 | -2.9412 | 1.1955 | 0.1604 | 0.6715 | 0.6046 |
| 0.95N | 0.3888 | 0.2097 | 0.1389 | 0.3889 | 3.6552 | 1.1062 | 1.1398 | 1.7674 | 1.2325 | 1.1141 |
| 0.75N | 0.1970 | 0.2222 | 0.1294 | -0.1216 | 0.4348 | 3.8879 | 1.7923 | 0.6662 | 1.8334 | 1.0316 |
| 0.5N | 0.2352 | 0.2177 | 0.0718 | 0.4385 | 4.3249 | 2.4663 | 1.7139 | 0.8520 | 1.7043 | 1.3361 |
| Misidentification ratio of detrimental samples |  |  |  |  |  |  |  |  |  |  |
| N-2K | 0.2000 | 0.1686 | 0.0908 | 0.0000 | 0.0000 | 0.0000 | 0.1538 | 0.1143 | 0.1821 | 0.1011 |
| 0.95N | 0.1250 | 0.3333 | 0.3736 | 0.1250 | 0.0833 | 0.2727 | 0.5172 | 0.2895 | 0.4737 | 0.2811 |
| 0.75N | 0.6325 | 0.4566 | 0.3600 | 0.0000 | 0.1000 | 0.4615 | 0.5493 | 0.2500 | 0.5800 | 0.3767 |
| 0.5N | 0.7107 | 0.4385 | 0.3404 | 0.1111 | 0.1429 | 0.3333 | 0.6739 | 0.2432 | 0.5680 | 0.3985 |

## Appendix C Limitations and Broader Impact

Our research focuses on overcoming challenges associated with value inflation in the application of KNN-Shapley for data valuation influence estimation. By introducing a method that enables accurate assessment of training samples’ impact on model performance, we provide a tool for practitioners to determine the positive or negative effects of these samples. Through comprehensive testing across various problem scenarios, our Shapley value removal strategy has been proven superior to existing methods, enhancing model efficiency by eliminating harmful data points. Consequently, our contributions have the potential to drive substantial societal benefits, particularly as the use of more complex and expansive neural networks, like Large Language Models, becomes more prevalent. For the limitations, we do not provide a theoretical analysis on the selection of $T$, where we posit
that the choice of $T$ is contingent upon the dataset characteristic. To tackle this limitation, we recommend $T=N-2K$ as the default setting for its satisfactory performance on the datasets in our experiments.

## Appendix D Code and Reproducibility

We will release the code soon.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: See 1) in weaknesses
soundness: 3
strengths: 1) The paper is very well written,very well explained and self-contained. I was not familiar with the KNN shapley technique and was able to catch up quickly by reading the paper and looking at the provided references. The plots are very helpful as well.

2) The solution is proposed is very simple and arguable incremental but I think the impact of the small change makes the KNN-Shapley algorithm significantly better when using it in real-life applications. This is one of these cases where Ocham's razor's apply.  The fact that the change makes the KNN-based calculation faster is a plus as well.
 
3) Extensive experimental results in differensettings are helpful to see the potential of the proposed approach.
summary: There have been recent work focussed on providing tools to explore, quantify and curate data sets used for training learning algorithms. Several of the of widely used existing algorithms are based on the calculation of Shapley values from cooperative game theory.
The main difficulty for calculating Shapley values comes with the fact that it involves calculation involving training models with 2ˆN combinations of the training data which makes it intractable in real-life applications. In order to overcome this difficulty, a more practical variation have been proposed (2019,2021)  KNN -Shapley that enables the calculation of shapley values with a O(NlogN) complexity. The new calculation takes advantage of the nature and simplicity of the lazy NN algorithm as a surrogate substitution for more complex learning algorithms. 

The KNN algorithm can be greatly affected from the issue of inflation, which calls for a  proposed variation  by the authors call calibrated KNN-Shapley or CKNN-Shapley that the authors show that deals efficiently with the aforementioned inflation problem.
weaknesses: 1) Since KNN is not an state-of-the-art algorithm in the modern practitioner toolbelt, my understanding of how this is used in real life would be that you would use CKNN-Shapley to clean the data and improve your training set quality and then go from there and use a more high performing algorithm e.g. GBM, XGboost, SVM etc. Is this the case? if it so can you add experiments where this two step is applied and see how this can improve the performance of these widely used algorithms?

2) Based on the provided experimental results The CKNN-Shapley  performance is better on almost all of the datasets where it was compared to other methods. It would be great to add p values that statistically shoe the significance. 

3) Minor: indentation is weird in some places e.g line 154. seems like the long Figure 1 caption gets "merged"with the main text.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: This paper proposed Calibrated KNN-Shapley (CKNN-Shapley), a semi-value method that calibrates zero as the threshold to distinguish detrimental samples from beneficial ones by mitigating the negative effects of small training subsets, addressing the value inflation issue observed in KNN-Shapley. The novelty is weak as it’s an improved version of KNN-Shapley. The detailed questions are listed below:
-
Could you provide more detailed guidelines or heuristics for selecting the subset size parameter T across different datasets? Specifically, how sensitive is CKNN-Shapley to T, and what considerations should practitioners have in choosing an appropriate threshold?
-
While CKNN-Shapley offers improvements in computational efficiency over traditional KNN-Shapley, what optimizations could make CKNN-Shapley scalable for very large or high-dimensional datasets? Could further modifications make CKNN-Shapley feasible for real-time data valuation in dynamic environments?
-
Since CKNN-Shapley relies on the KNN classifier as a surrogate model, how would CKNN-Shapley perform in contexts with complex decision boundaries or on tasks where KNN is not ideal? Is there a potential to generalize this approach beyond KNN, or could the calibrated approach be adapted for other surrogate models in Shapley-based data valuation?
-
Did you consider benchmarking CKNN-Shapley against other semi-value or cooperative game-theoretic approaches, such as Banzhaf values or alternatives in data valuation? If so, how does CKNN-Shapley perform relative to these methods, and in what contexts is it most advantageous?
-
Given the paper’s focus on simulated scenarios (e.g., mislabeled data, online learning, active learning), how would CKNN-Shapley perform in real-world applications where data is inherently noisy and highly variable? Are there specific real-world use cases (e.g., medical, financial data) where CKNN-Shapley has been tested, or do you have any recommendations for its deployment in production settings?
-
In your online learning and active learning experiments, how sensitive is CKNN-Shapley to hyperparameters like batch size and sample removal thresholds? How would you recommend setting these parameters for optimal performance in dynamic environments with streaming data?
-
CKNN-Shapley addresses value inflation effectively, yet inflation issues still exist to some extent. Are there additional strategies or constraints you would suggest for further reducing value inflation, particularly for beneficial samples that might still be overvalued?
-
In your experiments, how do you characterize the types of samples that CKNN-Shapley misidentifies, and are there common patterns or features among them? Could further insights into these misidentified samples help refine CKNN-Shapley or improve its robustness?
-
What are the significant contributions and connections of compared with existing studies for KNN-Shapley such as Threshold KNN-Shapley (Wang et al. 2023), KNN-Shapley (Wang and Jia 2023)?
-
More theoretical benefits and pitfalls need to be discussed in Section 3. How does CKNN-Shapley method work needs to be comprehensively elaborated in this section.
soundness: 2
strengths: (1) The paper introduces Calibrated KNN-Shapley (CKNN-Shapley) as a novel solution to address value inflation in data valuation using KNN-Shapley. This approach is significant as it recalibrates the threshold, effectively distinguishing between beneficial and detrimental samples, which is critical for robust data valuation.
(2) The paper conducts extensive experiments across various benchmark datasets, demonstrating CKNN-Shapley’s ability to outperform traditional KNN-Shapley and its variants. By testing on both image and text data, the paper validates CKNN-Shapley's broad applicability.
(3) CKNN-Shapley offers computational efficiency by directly assigning zero to certain sample subsets, reducing the recursive calculations required by the original KNN-Shapley. This efficiency makes it feasible for larger datasets, addressing a significant limitation of Shapley value-based methods in general.
(4) The paper’s calibration method and constraints on subset sizes provide a theoretical foundation that enhances the interpretability of data valuations. By setting a meaningful zero threshold and ensuring subsets closely resemble the original dataset, CKNN-Shapley offers more reliable and interpretable sample valuations.
summary: The paper aims to address the issue of value inflation in Shapley value-based data valuation methods. The proposed Calibrated KNN-Shapley (CKNN-Shapley) is to recalibrate the threshold to distinguish detrimental from beneficial samples, aiming to correct inflation that misidentifies some harmful samples as beneficial. CKNN-Shapley implements constraints on training subset sizes to mitigate inflation effects, which arise from the improper selection of small-sized subsets in the original KNN-Shapley approach. Through experiments, CKNN-Shapley demonstrates improved performance in classification and robustly adapts to applications like mislabeled data handling, online learning, and active learning.
weaknesses: (1) Despite improvements over traditional Shapley calculations, CKNN-Shapley still incurs notable computational costs, particularly on large datasets or complex deep learning tasks. While more efficient than the original KNN-Shapley, the method may not yet be scalable for very large or high-dimensional datasets without further optimization.
(2) CKNN-Shapley, like KNN-Shapley, relies on K-Nearest Neighbors as a surrogate model, which may limit its applicability to contexts where KNN is less effective. This
assumption may restrict CKNN-Shapley’s performance in tasks with more complex decision boundaries, where a KNN-based approach may not be ideal.
(3) The paper does not extensively explore or benchmark CKNN-Shapley against other semi-value methods or recent alternatives in data valuation, like Banzhaf values or other cooperative game-theoretic approaches. This lack of comparison limits understanding of CKNN-Shapley’s relative effectiveness and could benefit from further analysis of its competitive positioning.
(4) While CKNN-Shapley is tested on simulated scenarios like mislabeled data and online learning, the paper lacks a real-world deployment case study to validate its robustness. Moreover, CKNN-Shapley’s sensitivity to hyperparameters in dynamic environments, such as varying batch sizes in streaming data, remains under-explored.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: - What exactly does "semi-value" mean in the paper? It appears three times but does not a clear definition.
soundness: 3
strengths: - The paper considers a problem setting (data evaluation) and a representative method (kNN Shapley value) that has high pratical importance.
- The paper is well motivated and the proposed approache is simple and effective.
- The paper also discusses the application of the proposed method in various applications.
summary: This paper considers of the promblem of data evalution methods. Specifically, for a Shapely-value based method (kNN Shapley Value), the paper finds that it has some positive value miscalculated for some harmful datasets, thus resulting misunderstanding for some data points. The paper proposes to limit the calculation of kNN Shapley values only on data set whose size is above a specific value.
weaknesses: - The motivation seems only exist for the kNN based Shapley value, not other approaches of Shapley value. The sentence in abstract and introduction seems exaggerated that the problem exists for all Shapley value methods.
- The link between the motivation and the proposed method is vague. Specifically, does using the proposed $T$ value is designed to only solve the misclassified values? Is there probability that there are still misclassified values exist even using the probposed $T$? This also relates to the important problem of how to systematically assign the $T$ value, which is not theretically explored in the paper but just noted "the choice of T is contingent upon the dataset characteristics".

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: 012: Inflation is shown only for KNN-Shapley values, not for non-KNN values. So this sentence in the abstract is too strong.

019: It is misleading to mention small-sized training subsets, because with T = N-2K, in fact the training subset that is used for each target point is very small, of size 2K only. The benefit is that for each target point, this small subset is focused.

046: The reference (Jia et al., 2019b) to "Towards Efficient Data Valuation Based on the Shapley Value" is not correct, because KNN-Shapley does not appear in this paper. The reference to "Scalability vs. utility: Do we have to sacrifice one for the other in data importance quantification?" (CVPR, 2021) is also inappropriate, because the method is due to page 9 of "Efficient task-specific data valuation for nearest neighbor algorithms" (VLDB, 2019) .

Also, the formatting of the bibliography must be fixed, so that labels such as " (Jia et al., 2019b)" are visible in the PDF.

134: Figure 1 would be more clear using the same binning for the red and blue plots. The redline shows accuracy with a single bin removed. It would be more intuitive to remove this bin and also all bins to its left.

Maybe more important: The red line measures accuracy. This should be measured on an independent test set. The points that are removed are those that have a negative or small Shapley value as measured on the training set. It is not surprising that removing these points increases accuracy on the training set, because they have been identified as detrimental on precisely this set. The more interesting question is whether they are also detrimental on a separate i.i.d. test set.

153: The green region contains about half the entire dataset. Discuss why half of all points are harmful. It is not surprising if a few points are harmful, for example because their training labels are wrong. But it is surprising that so many points are. Is this true only because "harmful" is relative to the training set itself? Many fewer points may be harmful when the test set is independent.

174: It is not obvious that the first term is impactful, because it is small, since its denominator is N, which is much larger than K. Here is an alternative intuition: The reason to ignore the early terms is that their points are the most distant from the test point, so they are the most irrelevant to it. Even if they have the same label, that is accidental, so whether their labels are the same merely introduces noise. Moreover, the second and later terms include the denominator K << N, so they are much more heavily weighted than the first term.

197: Define "semi-value."

231: In Table 2, why are so many accuracies multiples of 0.01 or of 0.005? Because test sets contain only 100 or 200 data points? If this is true, then differences in accuracy are not statistically significant.

273: Why remove a fixed % of training points, when the advantage of CKNN is supposedly that the threshold zero tells us approximately how many points to remove?

Clarify the meaning of "KNN’s performance trained on the training set excluding samples". A fixed separate i.i.d. test set should be used. If accuracy is also measured on the training set excluding samples, this is not meaningful.

298: In Figure 3B, results for K < 5 must be included, since K=5 is best for the Wind dataset. The numerical values for Wind in Table 2 (0.8950 and 0.9100) are different from those in Figure 3B; why? 

In Figure 3C, T varies in the range 1950 to 1990. Why this range? Why is it so narrow? Explain how it is consistent with the recommendation T = N - 2K on line 377. 

More broadly, Figures 3B and 3C show that accuracy is highly sensitive to the choice of K and T. Why? Because training and test set sizes are small.

317: One goal of the CKNN method is for the empirically best threshold to be closer to zero. But why is this an important goal? Instead of the hyperparameter, we could use a validation set to determine the value of a non-zero threshold for standard kNN Shapley values, such as 0.8e-4 in Figure 1.

Note: I have not evaluated Section 5 carefully.

651: Typo.

728: Error in table title.

757: Table 7 is important and should be in the main paper, because this is how CKNN-Shapley might be used in practice. The same criticisms as above apply: test sets should be bigger and statistical significance should be reported.
soundness: 3
strengths: The evidence for the phenomenon of inflation is believable. The experimental improvements in accuracy are large enough to be likely valid despite concerns about experimental methodology (test sets too small, not independent, no measure of statistical significance). The new heuristic kNN Shapley values can therefore be valuable in real-world applications.
summary: Note added on December 4: I appreciate the authors' additional comments dated November 25 and 26. These confirm my overall evaluation and score of 6. I would emphasize that the central idea is the heuristic to use only the 2K nearest neighbors, and the simplicity of this idea should not be obscured. I appreciate the informal argument why inflation exists when too many neighbors are used.

The updated Table 7 shows that, sadly but not surprisingly, there is no free lunch, i.e., no clearly better test accuracy across the board. The main conclusion from this table is that it is harmful to remove samples based on the TKNN method. The benefits of other methods are unclear. The test sets used are just too small, as is the number and variety of datasets.

============

Shapley values can be used to measure the contribution of each point in a training set towards making a trained classifier more accurate. Ruoxi Jia et al. previously published an efficient method to calculate these Shapley values using k-nearest neighbor (kNN) classification. This paper shows empirically that those Shapley values tend to be too optimistic, and many data points with positive such values are actually harmful if used in training. The paper then proposes a heuristic improved version of kNN Shapley values, namely to use only the 2K nearest neighbors for each target point. Experimental results show that these new Shapley values lead to improved accuracy for trained classifiers.
weaknesses: The CKNN variation suggested for Shapley values is heuristic, with little evidence for any type of optimality. The paper should explain the motivation for introducing the hyperparameter T with more clarity and persuasiveness. 

The paper should explain better that because T = N-2K is used, in fact the method picks only the 2K nearest points. This is intuitively a good idea, but its ramifications must be explained.

It is not clear which experiments used an independent test set. The paper should report the statistical significance of differences in accuracy, using McNemar tests or something similar. Many differences may be not significant, because the test set is too small. 

Accuracy achieved with the CKNN method is highly sensitive to hyperparameters K and T. This makes the method less useful in practice.

Meta-review: The paper introduces an improvement for computing the KNN-Shapley value which can be used for assessing the importance of individual training examples. 

The Reviewers have underlined that the paper is well-written and self-contained. The solution is rather simple and incremental, but with a significant impact on applicability of the KNN-Shapley approach. The experimental results are also extensive, showing improvements of the proposed modification over the original approach. 

Nevertheless, the message of the paper and arguments used are often misleading. The Authors seem to motivate their approach by analyzing training errors on subsets of training data (Figure 1). This calls for explanation and justification as "this should be measured on an independent test set." When presenting the results on test sets, it still seems "harmful to remove training examples based on [the proposed] method." Moreover, the test sets used seem to be too small, as well as its number and variety, so the final conclusions are not clear. One should also underline that the paper concerns a topic of rather limited audience. 

The paper is a borderline and as an AC I needed to properly weigh the strengths and the weaknesses in order to make the final decision. The insights and the proposed solution are indeed interesting and worth attention. Nevertheless, the paper can be significantly improved to send a clear message without any controversy. Therefore, I have decided to reject it.

Decision: Reject