Shapley-Based Data Valuation for Weighted $k$-Nearest Neighbors

We thank the reviewer for reviewing our paper, and recognizing our contributions. We also thank the reviewer for pointing out the typo in line 140. We answer your questions below.

Q1: Not a serious one but should you still call your method data Shapley in this case? Just like how Jia's other work on Data Banzhaf, isn't your work some kind of Data Owen that's trying to approximate Data Shapley for weighted KNN?

A1: While it is popular to create new names for proposed methods for easy recognition, we didn't make an effort to do so. Thank you for suggesting a candidate, and we are thinking of using "kNN-GroupShapley" if a name is needed.

Q2: How would your work extend to regression settings? I suppose you might have to bin the differences between y_obs and y_tests in order to still use the counting trick? Do you have any other smarter ideas on this?

A2: Extending to regression is exactly one of the possible future works we mentioned in the conclusion. If the reviewer is interested in this, we recommend taking a look at Section E.1 of [13], where they define a utility function for regression with unweighted kNN as the negative mean squared error, and develop a similar recurrence relation for the Shapley values.

We thank the reviewer for reviewing our paper. We answer your questions below.

Q1: In section 4, the authors assume weights are integral. This is a severe restriction, as weights are typically numerical. The authors mention that assumptions could be removed through weight scaling, but do not provide the specific operation.

A1: We want to emphasize that the assumption of integral weights is made without loss of generality. We now explain how to do weight scaling in detail. Suppose the weights are real numbers $w_1, \ldots, w_n$. We can scale the weights to integers by multiplying a constant factor $c$ such that $c w_i$ is an integer for all $i$. Note that since real-valued weights are stored in the computer with finite precision, such an integer $c$ always exists, and the scaling does not change the prediction or the utility function of the $k$-NN classifier. In practice, we set $c$ to a sufficiently large numeric integer and perform rounding afterwards.

Q2: In section 7, the comparison of the algorithms is insufficient. To further verify the effectiveness of the proposed algorithm, the authors should incorporate additional comparison algorithms about noisy label detection.

A2: We understand the reviewer's concern. However, the main goal of this paper is not to claim that kNN-Shapley is the best approach for noisy label detection. Instead, we aim to show that the proposed weighted kNN-Shapley method is effective in comparison to the unweighted counterpart and other kNN-based approaches. We hope the reviewer will agree that we have made sufficient comparisons for this purpose.

Q3: In section 7, the experimental results present standard deviation values but lack the significance test. This leads to the inability to confirm whether the performance differences between algorithms are statistically significant.

A3: Following the advice of the reviewer, we added a significance test to the experimental results. We choose the Wilcoxon signed-rank test, which is a non-parametric test that does not assume a normal distribution of the F1 scores. Taking the F1 scores of each method over 11 datasets as input and using a significance level of 0.05, the performance of our weighted kNN-Shapley method is statistically significantly better than all baselines except for the unweighted kNN-Shapley method and the Monte Carlo sampling method with 1000 samples. However, if we slightly raise the significance level to 0.06, our method outperforms the unweighted kNN-Shapley method in the test. Note that it is not expected that our method can defeat the Monte Carlo sampling method with a large number of samples, because the latter is also based on weighted kNN-Shapley, but is much slower. We hope that this test helps to justify the effectiveness of our method.

Q4: In section 7, the datasets used in the experiments are not sourced. This makes me confused about the reason why the authors chose these datasets.

A4: We adopt most datasets that are used in the previous work [29,30] on kNN-Shapley. We added a few new datasets with a larger size (e.g., poker), which is a popular dataset available in UCI Machine Learning Repository.

We thank the reviewer for the thorough review, and the constructive suggestions on improving the presentation of the paper. We answer your questions below.

Q1: I feel the theoretical contribution falls on the low end. For example, Proposition 2 appears to be a straightforward observation. Theorem 3 merely restates standard Shapley axioms with minor adaptation.

A1: Our main idea about data duplication is indeed a simple one, but it is effective and has been overlooked by prior work. Other reviewers consider the simplicity of our approach as a strength with clear benefits (e.g., see Reviewer KFsJ). Besides, we propose techniques to avoid the computational burden caused by data duplication, and provide theoretical analysis of the difference from other approaches. We believe these contributions together establish a complete theoretical and practical foundation for our proposed approach.

Q2: Theorem 6's runtime analysis omits the dependency on $K'$, with only a brief mention that "partial sum of the harmonic series can be accurately approximated by the Euler-Maclaurin formula [2], or retrieved from a precomputed table." This is problematic because: If approximation is used, it introduces an additional layer of error that should be characterized If pre-computed tables are used, this significantly increases memory requirements Algorithm 1 should explicitly include these details in the pseudocode and acknowledge any limitations.

A2: We thank the reviewer for pointing out the missing details. Asymptotically, the Euler-Maclaurin formula $F(j)$ below converges to the harmonic series $H_j = \sum_{i=1}^{j} \frac{1}{i}$ as $j \to \infty$.

where $\gamma \approx 0.5772156649$ is the Euler-Mascheroni constant. In practice, we adopt the following more accurate approximation scheme. When $j$ is a small constant (e.g., $j \le 1000$), we can afford to compute $H_j$ exactly. Otherwise, we use $F(j) - F(1000) + H_{1000}$ as an approximation (in $O(1)$ time where $H_{1000}$ is pre-computed) to eliminate the noticeable error when $j$ is relatively small. We verify the absolute error is at most $4.167 \times 10^{-8}$ for $j$ up to 1 million and continues to decrease as $j$ increases. We believe this approximation is sufficient for our purpose.

Q3: For experiments, the most relevant baseline—hard-label weighted kNN-Shapley by Wang et al. [1]—is omitted with insufficient justification. The authors claim it "fails to finish within 5 hours on small datasets," but after reviewing [1] I do not think this explanation is sufficient: Runtime of hard-label WKNN-Shapley can be controlled by adjusting discretization bits for weights. [1] also offers a deterministic approximation algorithm with sub-quadratic complexity (Section 4.2 of [1]).

A3: In our experiments, we use the default discretization bits ($n_{bits}=3$) for this baseline, which only enables at most 8 different weight values. We believe no significant saving in time can be expected when using fewer bits.

Instead of resorting to the approximate version, we choose to compare with the exact version over small datasets. We set the data size to be 300 by randomly sampling from the original datasets. Very surprisingly, the hard-label WKNN-Shapley is only slightly better than random guessing, and is far behind the performance of the unweighted kNN-Shapley and our method. To make sure this is not caused by bugs in the code, we further verify that its values are indeed consistent with those by Monte-Carlo sampling with a hard-label utility function.

After careful inspection, we identify the key reason: a hard-label utility function is not suitable for the task of noisy label detection. Unlike the soft-label utility, it is unable to capture the fine-grained contribution of a data point. It requires the noisy point to be a game changer for the prediction of its neighbors in order to be considered harmful, which is not the case for most mislabeled points. A mislabeled point is often surrounded by well-labeled points, and its ability to change the prediction of its neighbors is often negligible. Note that resorting to a hard-label utility function is the key modification that enables the DP algorithm in [1] to work.

We thank the reviewer for suggesting further comparison with this baseline, which leads to insightful observations. We will add this comparison in the revised version of the paper. We hope the reviewer will consider raising the score.

We thank the reviewer for reviewing our paper and recognizing our contributions. We answer your questions below.

Q1: [Major] Could you discuss in further detail the impact of the dimensionality $d$ compared to unweighted variants, on the scalability of the proposed approach?

A1: As far as we know, the dimensionality $d$ plays no special role in the comparison between the weighted and unweighted kNN-Shapley. It only affects the sorting stage, which is required for both the weighted and unweighted kNN-Shapley. When given a test point $z_{test}$, we need to compute the distance between $z_{test}$ and all the training points in $D$ before we can sort $D$ by non-decreasing distance to $z_{test}$. Thus, the time complexity of distance computation (e.g., Euclidean distance) is $O(d)$ for each pair of points, which leads to $O(dn)$ in total.

Q2: [Minor] $K$ is not defined in (3), I believe it is $k$?

A2: Yes, you are correct. We will fix the typo. Thanks.