On the Inflation of KNN-Shapley Value

174
Thank you for this insightful observation. We will clarify this intuition in future versions to improve the understanding of why CKNN-Shapley emphasizes the closest neighbors and downweights the distant points.

197
We will make sure to include a citation to [1] in future versions to properly reference this theoretical foundation.

231
See Appendix B.1. Following Wang et al. (2023), we also set the test data size to 10% of the training data size. As a result, the test data size for the Pol, Wind, and CPU datasets is 200, while the test sets for other datasets contain 1000 or 5000 samples.

273
The method of removing a fixed percentage of training points was suggested by reviewers in our previous submission. This approach originates from [2], and was included to enable more comprehensive and fair comparisons across multiple dimensions.

Regarding the use of the same test set for both Shapley value calculation and accuracy evaluation, we argue that this is appropriate given the research topic of our paper. Our primary focus is on data valuation and addressing the issue of value inflation. Using the same test set ensures consistency and aligns with our research question by providing a direct connection between Shapley value calculations and their impact on classification accuracy.

298
Results for $K = 3$ and $K = 1$ is in Table below:

In Figure 3B, results for $K = 10$ is 0.9000, which is also in line 239.
In the Pol, Wind, and CPU datasets, $T = N - 2K$ is calculated as $2000 - 2 \times 10 = 1980$, which aligns with the narrow range of T values shown in Figure 3C (1950 to 1990). We chose this range to closely examine the impact of T around the recommended setting. A broader range of T values is discussed in Appendix C.4, Table 8, where we explore how different T values affect performance across these datasets.

Sensitive and test set is too small same with Sensitive to K and T and 231.

317
This point is discussed in section 3 from lines 244 to 255, where we explain how having the empirically best threshold closer to zero ensures consistency with Shapley value axioms by preserving efficiency, treating identical samples equitably (symmetry), and assigning zero to non-contributory samples (zero elements), thereby avoiding arbitrary truncations.

651 and 728
Thank you for pointing out the typo and error. We will correct it in the next revision.

757
Thank you for the suggestion. We agree that Table 7 is important as it demonstrates how CKNN-Shapley can be applied in practice, and we will consider moving it to the main paper in the next revision. Regarding statistical significance, it is important to note that KNN-based methods, including CKNN-Shapley, do not inherently involve statistical significance testing, as they rely on deterministic accuracy values. We will clarify this in the paper to address any potential confusion.

References
[1] Dubey, Pradeep, Abraham Neyman, and Robert James Weber. Value theory without efficiency. Mathematics of Operations Research, 6(1), 122-128, 1981.

[2] Kevin Jiang, Weixin Liang, James Y Zou, and Yongchan Kwon. Opendataval: a unified benchmark for data valuation. Advances in Neural Information Processing Systems, 2023.

We would like to thank the reviewer for the deep analysis of our work, and the time, effort, and consideration. Below, we answer the questions raised by the reviewer:

Hyperparameter T
The CKNN variation indeed involves heuristic adjustments, with the primary motivation being to mitigate the inflation issue observed in KNN-based Shapley values. The hyperparameter $T$ is introduced as a means to exclude small, less reliable subsets from the evaluation process, as these subsets disproportionately contribute to value inflation. This heuristic is grounded in the intuition that small subsets often fail to represent meaningful contributions to the overall model performance.
The $T$ value is a hyperparameter in CKNN-Shapley. Similar to selecting different values of $K$ which impacts accuracy, the choice of $T$ in CKNN-Shapley also varies depending on the dataset. In Figure 3, we explore various $T$ values, demonstrating that an appropriate $T$ setting can effectively improve the accuracy of the KNN classifier. Table 8 provides further details, where we show that setting $T = N - 2K$ yields optimal results.

Ramifications
To clarify, in CKNN-Shapley, each subset effectively selects at least $T - 2K$ points due to the design of $T = N - 2K$.
This choice relaxes the efficiency axiom of Shapley value, meaning that the sum of CKNN-Shapley values no longer equals the total accuracy, as it would in a standard Shapley value setup. We will further elaborate on these implications in future versions to enhance the clarity and motivation behind this heuristic.

Statistical tests
Statistical tests demonstrate that CKNN significantly outperforms KNN in classification accuracy. Specifically, we performed paired t-tests (t = 2.909, p = 0.0196) and Wilcoxon signed-rank tests (statistic = 1.5, p = 0.0117) to compare the performance of our method with the second-best method on each dataset as presented in Table 2. The results indicate that the differences are statistically significant (p < 0.05), demonstrating the superiority of our method. This analysis highlights the consistent and significant improvements achieved by CKNN across multiple datasets.

Sensitive to $K$ and $T$
The role of hyperparameters is to control and adapt the method to specific datasets and tasks, and it is not inherently better for the results to be insensitive to them. If a hyperparameter had no impact, it would lack significance and fail to serve its intended purpose. Additionally, we ensured consistent and fair default settings for all experiments, and for hyperparameters deemed sensitive, we conducted experiments to analyze their effects. In our experiments, we provided the parameter analysis experiments and a recommended setting of $K$ and $T$. With the fixed setting, there is no sensitivity issue. Indeed, we acknowledge that in practical applications, these hyperparameters need to be tuned using the validation set to achieve optimal performance.

012
Thank you for highlighting this important point. We will revise the abstract and introduction in future versions to more clearly specify that our motivation is centered on the inflation issue in KNN-based Shapley value methods.

019
Same with Ramifications.

046
Thank you for pointing out these issues. We acknowledge the errors in the references and appreciate your detailed feedback. We will revise the citations to correctly attribute the methods to their original sources.

134
Thank you for the suggestion. We put significant effort into designing Figure 1, aiming to present as much information as possible. This is why the figure includes a detailed caption to explain its elements. The reason we do not remove all bins to the left of the current bin is that our objective is to determine whether removing the current bin alone increases or decreases accuracy. This allows us to identify whether the samples in the bin are beneficial or detrimental to the model’s performance. This approach directly aligns with our research question, which is focused on understanding the impact of individual samples (bins) on accuracy and demonstrating the value inflation issue in KNN-based Shapley methods.

However, we agree with your point that using consistent binning for the red and blue plots could improve clarity. In the next version of the paper, we will simplify the figure by removing the blue binning to enhance readability.

153
The detrimental samples refer to those that, when removed, lead to an increase in KNN accuracy. Importantly, the evaluation of accuracy is conducted on the test set. Therefore, whether a sample is detrimental depends on its relationship with the training set, the test set, and the KNN classifier itself. Additionally, many inflation samples in KNN-Shapley are calibrated by CKNN-Shapley to have values closer to 0, which redistributes their contributions more realistically.

I have increased my score to 6 given the additional experimental results. For every seed and each of the three datasets, the new method yields better accuracy than the second-best method, so the improvement is clearly statistically significant.

Minor point: p = 0.020 for POL is surprising given that 0.963 is less than one standard deviation away from 0.949 ± 0.018, i.e., a naive z-score is less than one. In the final version, please describe exactly how the T-test was applied.

The central contribution is to use only the 2K nearest neighbors. No theory is needed, just a clear statement that this is the contribution, and a direct informal argument why it is better to use only a small number of nearest neighbors.

I do not find the "Root of inflation" argument persuasive. Yes, "none of the samples in the sub training set plays a decisive role in predicting the validation sample." But you haven't explained why that causes Shapley values to be too high, as opposed to merely noisy.

I agree that "overfitting to the validation/test set is not the focus of this paper." But Table 7 is the highlight for practitioners who may use the new method (it should be moved to the final version from the appendix), so the accuracy results in it must not be misleading. My request is to use an appropriate (routine and standard) training/validation/test methodology and to state this methodology clearly. This request is not a request for additional research.

We are very delighted to see the increased score. Appreciated! Below is our response for the follow up questions.

p = 0.020 for Pol
Thank you for the comment. The p-value is derived from a paired t-test, which compares CKNN-Shapley against the second-best method for each seed. Unlike a z-score comparison based on means and standard deviations, the paired t-test focuses on the differences between paired observations across seeds, accounting for both the magnitude and consistency of the improvements. Notably, CKNN-Shapley outperforms the second-best method by a margin of at least 0.005 across all seeds, with differences up to 0.020 in some cases. This leads to a statistically significant p-value of 0.020, reflecting CKNN-Shapley's consistent advantage across seeds. We will describe the t-test more clearly in the final version.

Why that causes Shapley values to be too high
We focus on Eq. (2) in this paper, the inflation arises due to the following reasons:

1. The initialization of $\nu_k(z_{\alpha_{i+1}})$ is inherently biased towards positive values.
   The Shapley value computation starts from
   $$ \nu_k(z_{\alpha_N}) = \frac{1[y_{\alpha_N} = y_v]}{N} $$,
   which is always non-negative. This positive bias propagates through the recursive computation and influences all subsequent values. The reason this initialization value is positive lies in the definition of Shapley values, which evaluate the marginal contribution of adding a single sample to a subset. Even when the subset is empty, any match in labels contributes positively to the value.

2. The cumulative effect of the adjustment term is biased towards retaining positive contributions.
   In most cases, the adjustment term
   $1[y_{\alpha_i} = y_v] - 1[y_{\alpha_{i+1}} = y_v]$ equals 0 because both y_{\alpha_i} \neq y_v $ and $ y_{\alpha_{i+1}} \neq y_v occur frequently in multi-class classification. This zero adjustment does not neutralize the initial positive bias, and any non-zero adjustment (though rare) is more likely to accumulate positive contributions than negative ones.

Together, these factors explain why the Shapley values are inflated rather than merely noisy, as the structure of the recursive computation inherently leans towards positive accumulation. We hope this addresses your concern, and we are happy to provide additional clarifications if needed.

We would like to thank the reviewer for the deep analysis of our work, and the time, effort, and consideration. Below, we answer the questions raised by the reviewer:

Abstract
Thank you for highlighting this important point. We will revise the abstract and introduction to more clearly specify that our motivation is centered on the inflation issue in KNN-based Shapley value methods.

Link Between Motivation and Proposed Method
In Section 3, we provide the analysis on the value inflation, which leads to our proposed method. We would like to restate the rationality here. Recall the nature of the KNN classifier, which only makes the prediction based on the neighbors, 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 this, our CKNN-Shapley mitigates the negative effects of small-sized training subsets.

$T$ Only for Addressing Misclassified Samples?
$T$ in CKNN-Shapley controls the subsets to be considered in data valuation and mitigates the inflation. By this means, it not only corrects misclassified samples, but also calibrates the values of beneficial samples. See Figure 2, where KNN-Shapley not only has a negative effect on the misidentified samples but also tends to inflate the valuation of most samples.

Could misclassified samples still exist even with $T$ applied?
While setting the $T$ value does not guarantee the calibration of all misclassified samples, our experimental results show that CKNN-Shapley significantly reduces inflation effects and the misclassification rate across multiple datasets, indicating that it effectively addresses the issue in most cases.

Systematic assignment of $T$ value
$T$ is a hyperparameter in CKNN-Shapley. Similar to selecting different values of $K$ which impacts accuracy, the choice of $T$ in CKNN-Shapley also varies depending on the dataset. In Figure 3, we explore various $T$ values, demonstrating that an appropriate $T$ setting can effectively improve the accuracy of the KNN classifier. Table 8 provides further details, where we show that setting $T = N - 2K$ yields optimal results.

Semi-value
Semi-value refers to a family of cooperative game theory methods that satisfy all the axioms of the Shapley value except for the efficiency axiom. This relaxation allows semi-values to allocate rewards based on the marginal contributions of each player while providing greater flexibility in value distribution, which can be beneficial for computational efficiency in certain applications.
We will make sure to include a citation to [1] in future versions to properly reference this theoretical foundation.

[1] Dubey, Pradeep, Abraham Neyman, and Robert James Weber. Value theory without efficiency. Mathematics of Operations Research, 6(1), 122-128, 1981.

We would like to thank the reviewer for the deep analysis of our work, and the time, effort, and consideration. Below, we answer the questions raised by the reviewer:

Scalability for very large or high-dimensional dataset
We would like to emphasize that the primary focus of our research is to address the inflation issue in KNN-Shapley (a well-known method in the field of data valuation), rather than optimizing computational costs or specifically targeting high-dimensional datasets. Our goal was to improve the data valuation by mitigating the inflation observed in KNN-Shapley, where the acceleration of our proposed CKNN-Shapley over KNN-Shapley is a byproduct. Additionally, we have demonstrated CKNN-Shapley’s effectiveness on real-world image and text datasets, including CIFAR-10, AGnews, SST-2, and News20, which include both high-dimensional data and large sample sizes. It is worthy noting that we follow the literature [1] to analyze the data valuation for deep models, where deep embeddings are taken as inputs for KNN-Shapley-based methods. For very large and high-dimensional datasets, techniques such as Locality Sensitive Hashing (LSH) can be utilized for faster KNN computation [1].

Every method has its limitations, and no one can address all limitations in one paper. Here we sincerely invite Reviewer oxte to evaluate our paper by judging whether our targeted research question is meaningful and our proposed method can tackle our targeted challenge. Thank you!

Limitations contexts where KNN is less effective
We acknowledge that, inheriting from KNN-Shapley, CKNN-Shapley relies on KNN as a surrogate model, which may limit its applicability in some contexts. Again following the response from the above question, this potential limitation is not our primary research question. Our main focus is on mitigating the value inflation observed in KNN-Shapley.

Lack of compare with other semi-value methods or recent alternatives in data valuation
Since retraining costs are prohibitive for various Shapley value-based semi-value methods, KNN-based approaches are indeed more suitable for practical use, where we also focus on this category. We have made every effort to include relevant KNN-based methods for comparison and even implemented KNN Beta Shapley ourselves. In response to your suggestion, we also implemented Banzhaf following [2], using KNN as the utility function to provide a more comprehensive analysis. The results are shown in the table below, indicating that our CKNN-Shapley achieves the best performance in terms of average accuracy by removing negative Shapley values:

If you believe additional methods would be beneficial for comparison, please feel free to recommend relevant literature, and we would like to add more comparisons.

Parameter T
Practitioners should aim to select a relatively large T, and we recommend T=N-2K. We invite Reviewer oxte to check our detailed analysis on selecting the subset size parameter T in Figure 3 and Table 8 in Appendix C.4, where a large range of T is tested on all datasets.

Large, high-dimensional, and real-time data valuation
We believe some fast neighbor calculations by cluster analysis and dimension reduction techniques including deep embedding can be used to tackle very large and high-dimensional datasets. For real-time data valuation in dynamic environments, we cannot figure out a real scenario in practice. Since the data valuation aims to analyze the importance of training samples, where a retraining is needed with cleaned or weighted samples. Usually, the retraining takes a long time and is difficult to be real-time.

We would like to grasp the last minute to learn from the reviewer to improve the quality of our paper and address your concerns.

We would like to thank the reviewer for the deep analysis of our work, and the time, effort, and consideration. Below, we answer the questions raised by the reviewer:

Two-Step Procedures for Other Classifiers
We invite Reviewer M8bW to check Table 7 in the appendix, where we showed the results of applying CKNN-Shapley to clean the training set and applying other classifiers (MLP, LR, and SVM) on the clean training set for the learning task. These experiments highlight CKNN-Shapley’s general applicability beyond KNN models, demonstrating that it can effectively improve learning performance by removing detrimental samples even for non-KNN-based classifiers.

P values
Since all methods compared in our study are based on the deterministic accuracy of KNN, there is no inherent randomness in the results. To show the significance, we performed paired t-tests (t = 2.909, p = 0.0196) and Wilcoxon signed-rank tests (statistic = 1.5, p = 0.0117) to compare the performance of our method with the second-best method on each dataset as presented in Table 2. The results indicate that the differences are statistically significant (p < 0.05), demonstrating the superiority of our method. This analysis highlights the consistent and significant improvements achieved by CKNN across multiple datasets.

Line 154
Thank you for noting this. We apologize for the formatting inconsistencies. The issues of line 154 will be addressed in the next revision.