Efficient Data Shapley for Weighted Nearest Neighbor Algorithms

The Shapley value (SV) [Shapley, 1953], originating from game theory, stands out as a distinguished method for equitably distributing total profit among all participating players. Before diving into its definition, we first discuss a fundamental concept: the utility function.

Utility Function. A utility function maps an input dataset to a score indicating the utility of the dataset for model training. Often, this function is chosen as the validation accuracy of a model trained on the given dataset. That is, given a training set $S$, the utility function $v(S):=\texttt{ValAcc}(\mathcal{A}(S))$, where $\mathcal{A}$ represents a learning algorithm that trains a model on dataset $S$, and $\texttt{ValAcc}(\cdot)$ is a function assessing the model’s performance, e.g., its accuracy on a validation set.

In simple terms, the Shapley value is a weighted average of the marginal contribution $v(S\cup\{z\})-v(S)$, i.e., the utility change when the point $z$ is added to different $S$s. For simplicity, we often write $\phi_{z}$ when the utility function is clear from the context. The Shapley value uniquely satisfies several important axioms, including key fairness requirements like the null player and symmetry axioms, lending justification to its popularity. See Appendix A for detailed axiom definitions.

A well-known challenge of using the Shapley value is that its exact calculation is computationally infeasible in general, as it usually requires evaluating $v(S)$ for all possible subsets $S\subseteq D$. A surprising result in [Jia et al., 2019a] showed that when the learning algorithm $\mathcal{A}$ is unweighted KNN, there exists a highly efficient algorithm for computing its exact Data Shapley score.

K Nearest Neighbor Classifier. Given a validation data point $z^{(\mathrm{val})}=(x^{(\mathrm{val})},y^{(\mathrm{val})})$ and a distance metric $d(\cdot,\cdot)$, we sort the training set $D=\{z_{i}=(x_{i},y_{i})\}_{i=1}^{N}$ according to their distance to the validation point $d(x_{i},x^{(\mathrm{val})})$ in non-descending order. Throughout the paper, we assume that $d(x_{i},x^{(\mathrm{val})})\leq d(x_{j},x^{(\mathrm{val})})$ for any $i\leq j$ unless otherwise specified. A KNN classifier makes a prediction for the query $x^{(\mathrm{val})}$ based on the (weighted) majority voting among $x^{(\mathrm{val})}$’s $K$ nearest neighbors in the training set. Weight of data point: in KNN, each data point $z_{i}$ is associated with a weight $w_{i}$. The weight is usually determined based on the distance between $x_{i}$ and the query $x^{(\mathrm{val})}$. For example, a popular weight function is RBF kernel $w_{i}:=\exp(-d(x_{i},x^{(\mathrm{val})}))$. If $w_{i}$ is the same for all $z_{i}$s, it becomes unweighted KNN.

[Jia et al., 2019a] considers the utility function for the weighted, soft-label KNN:

where $\alpha_{x^{(\mathrm{val})}}^{(S,j)}$ denotes the index (among $D$) of $j$th closest data point in $S$ to $x^{(\mathrm{val})}$. “Soft-label” refers to the classifiers that output the confidence scores. The main result in [Jia et al., 2019a] shows that for unweighted KNN, we can compute the exact Shapley value $\phi_{z_{i}}\left(v(\cdot;z^{(\mathrm{val})})\right)$ for all $z_{i}\in D$ within a total runtime of $O(N\log N)$ (see Appendix B for details).

Since its introduction, KNN-Shapley has rapidly gained popularity in data valuation for its efficiency and effectiveness, and is being advocated as the ‘most practical technique for effectively evaluating large-scale data’ in recent studies [Pandl et al., 2021, Karlaš et al., 2022].

[Jia et al., 2019a] developed an efficient $O(N\log N)$ algorithm to calculate the exact unweighted KNN-Shapley. However, when it comes to the more general weighted KNN-Shapley, only an $O(N^{K})$ algorithm is given. While still in polynomial time (if $K$ is considered a constant), the runtime is impractically large even for small $K$ (e.g., 5). Here, we review the high-level idea of the baseline algorithms from [Jia et al., 2019a].

An $O(N^{K})$ algorithm for exact WKNN-Shapley computation. From Definition 1, the Shapley value for $z_{i}$ is a weighted average of the marginal contribution (MC) $v(S\cup\{z_{i}\})-v(S)$; hence, we only need to study those $S$ whose utility might change due to the inclusion of $z_{i}$. For KNN, those are the subsets $S$ where $z_{i}$ is within the $K$ nearest neighbors of $x^{(\mathrm{val})}$ after being added into $S$. Note that for KNN, the utility of any $S$ only depends on the $K$ nearest neighbors of $x^{(\mathrm{val})}$ in $S$. Given that there are only $\sum_{j=0}^{K}{N\choose j}$ unique subsets of size $\leq K$, we can simply query the MC value $v(S\cup\{z_{i}\})-v(S)$ for all $S$ of size $\leq K$. For any larger $S$, the MC must be the same as its subset of $K$ nearest neighbors. We can then compute the Shapley value as a weighted average of these MC values by counting the number of subsets that share the same MC values through simple combinatorial analysis. Such an algorithm results in the runtime of $\sum_{j=0}^{K}{N\choose j}=O(N^{K})$. The algorithm details can be found in Appendix B.

Monte Carlo Approximation. Given the large runtime of this exact algorithm, [Jia et al., 2019a] further proposes an approximation algorithm based on Monte Carlo techniques. However, Monte Carlo-based approximation is randomized and may not preserve the fairness property of the exact Shapley value. Additionally, the sample complexity of the Monte Carlo estimator is derived from concentration inequalities, which, while suitable for asymptotic analysis, may provide loose bounds in practical applications.

While the algorithm introduced in Section 4.1 for calculating the exact WKNN-Shapley achieves $O(N^{2})$ runtime, a huge improvement from the original $O(N^{K})$ algorithm from [Jia et al., 2019a], there remains room for further improving the efficiency if we only require an approximation of the Shapley value. Contrary to the prevalent use of Monte Carlo techniques in existing literature, in this section, we develop a deterministic approximation algorithm for WKNN-Shapley.

Intuition. From Theorem 7, we know that in order to compute $\texttt{F}_{i}[m,\ell,\cdot]$ with $\ell\leq K-1$, we only need to know $\texttt{F}_{i}[t,\ell-1,\cdot]$ with $t\leq m-1$. Moreover, observe that the building blocks for $\texttt{G}_{i,\ell}$ (or $\texttt{R}_{i,m}$), $\sum_{s\in[-\widetilde{w}_{i},0)}\texttt{F}_{i}[t,\ell,s]$ (or $\sum_{s\in[-\widetilde{w}_{i},-\widetilde{w}_{m})}\texttt{F}_{i}[t,K-1,s]$), can be quite small as it only takes the summation over a small range of the weight space. Hence, we can use $\widehat{\texttt{F}}_{i}[m,\cdot,\cdot]=0$ as an approximation for $\texttt{F}_{i}[m,\cdot,\cdot]$ for all $m\geq M^{\star}+1$ with some prespecified threshold $M^{\star}$. Similarly, we can use $\widehat{\texttt{R}}_{i,m}=0$ as an approximation for $\texttt{R}_{i,m}$ for all $m\geq M^{\star}+1$. The resultant approximation for the Shapley value $\phi_{z_{i}}$ is stated as follows:

To calculate $\widehat{\phi}_{z_{i}}^{(M^{\star})}$, we only need to compute $\texttt{F}_{i}[m,\cdot,\cdot]$ and $\texttt{R}_{i,m}$ for $m$ from $1$ to $M^{\star}$ instead of $N$, thereby reducing the runtime of Algorithm LABEL:alg:efficient-wknn to $O(NM^{\star})$ with minimal modification to the exact algorithm’s implementation.

In particular, when $M^{\star}=\sqrt{N}$, we can achieve the runtime of $O(N^{1.5})$. The selection of $M^{\star}$ is discussed in Remark 5. In the following, we derive the error bound and point out two nice properties of this approximation.

Leveraging the error bound $\varepsilon(M^{\star})$ alongside the additional nice properties of $\widehat{\phi}_{z_{i}}^{(M^{\star})}$ stated in Theorem 12, we can obtain a deterministic interval within which $\phi_{z_{i}}$ always resides. Specifically, when $y_{i}=y^{(\mathrm{val})}$, we have $\phi_{z_{i}}\in\left[\widehat{\phi}_{z_{i}}^{(M^{\star})},\widehat{\phi}_{z_{i}}^{(M^{\star})}+\varepsilon(M^{\star})\right]$, and when $y_{i}\neq y^{(\mathrm{val})}$, we have $\phi_{z_{i}}\in\left[\widehat{\phi}_{z_{i}}^{(M^{\star})}-\varepsilon(M^{\star}),\widehat{\phi}_{z_{i}}^{(M^{\star})}\right]$. Unlike the commonly used Monte Carlo method for approximating the Shapley value, which only offers a high-probability interval and allows for a failure possibility that the exact value might fall outside of it, our deterministic approximation ensures that the exact value is always within the corresponding interval.

The approximated WKNN-Shapley preserves the fairness axioms. The Shapley value’s axiomatic properties, particularly the symmetry and null player axioms, are of great importance for ensuring fairness when attributing value to individual players (see Appendix A for the formal definitions of the two axioms). These fundamental axioms have fostered widespread adoption of the Shapley value. An ideal approximation of the Shapley value, therefore, should preserve at least the symmetry and null player axioms to ensure that the principal motivations for employing the Shapley value—fairness and equity—are not diminished. The prevalent Monte Carlo-based approximation techniques give randomized results and necessarily muddy the clarity of fairness axioms. In contrast, our deterministic approximation preserves both important axioms.

We empirically assess the computational efficiency of our exact and deterministic approximation algorithms for WKNN-Shapley, comparing them to the $O(N^{K})$ exact algorithm and the Monte Carlo approximation presented in [Jia et al., 2019a]. We examine various training data sizes $N$ and compare the execution clock time of different algorithms at each $N$. In data size regimes where the baseline algorithms from [Jia et al., 2019a] are infeasible to execute ($>10$ hours), we fit a polynomial curve to smaller data size regimes and plot the predicted extrapolation for larger sizes.

Figure 2 shows that the exact algorithm from [Jia et al., 2019a] requires $\geq 10^{3}$ hours to run even for $N=100$, rendering it impractical for actual use. In contrast, our exact algorithm for computing WKNN-Shapley achieves a significantly better computational efficiency (e.g., almost $\mathbf{10^{6}}$ times faster at $\mathbf{N=10^{5}}$). Our deterministic approximation algorithm is compared to the Monte Carlo approximation from [Jia et al., 2019a]. For a fair comparison, both algorithms are aligned for the same theoretical error bounds. Note that the error bound for the Monte Carlo algorithm is a high-probability bound, subject to a small failure probability. In contrast, our error bound always holds, offering a more robust guarantee compared to the Monte Carlo technique. Nonetheless, from Figure 2 we can see that our deterministic approximation algorithm not only provides a stronger approximation guarantee but also achieves significantly greater efficiency (e.g., also almost $\mathbf{10^{6}}$ times faster at $\mathbf{N=10^{5}}$). This showcases the remarkable improvements of our techniques.

Due to the superior computational efficiency of our newly developed algorithms, WKNN-Shapley has become a practical data valuation technique for actual use. In this section, we evaluate its effectiveness in discerning data quality for common real-world applications. Tasks: we consider three applications that are commonly used for evaluating the performance of data valuation techniques in the prior works [Ghorbani and Zou, 2019, Kwon and Zou, 2022, Wang and Jia, 2023a]: mislabeled data detection, noisy data detection, and data selection. Due to space constraints, we only present the results for mislabeled data detection here, and defer the results for the other two tasks to Appendix LABEL:appendix:eval. Mislabeled data usually detrimentally impacts model performance. Hence, a reasonable data valuation technique should assign low values to these data points. In our experiments for mislabeled data detection, we randomly select 10% of the data points to flip their labels. Baselines & Settings & Hyperparameters: We evaluate the performance of both the exact and approximated WKNN-Shapley. We use $\ell_{2}$ distance and the popular RBF kernel $w_{i}=\exp(-\left\lVert x_{i}-x^{(\mathrm{val})}\right\rVert)$ to determine the weights of training points. We discretize the weights to 3 bits, as we find this level of precision offers a balance between good performance and computational efficiency, with a weight space size, $W$, of merely $2^{3}=8$. In Appendix LABEL:appendix:eval, we conduct ablation studies on the choice of the number of bits for discretization. For approximated WKNN-Shapley, we set $M^{\star}=\sqrt{N}$. Our primary baseline is the unweighted, soft-label KNN-Shapley from [Jia et al., 2019a]. Since our WKNN-Shapley corresponds to hard-label KNN, we also include unweighted, hard-label WKNN-Shapley in comparison for completeness. Note that it can be computed by simply setting the weights of all data points as a constant.

Results. We use AUROC as the performance metric on mislabeled data detection tasks. Unweighted vs weighted KNN-Shapley: Table 1 shows the AUROC scores across the 13 benchmark datasets we experimented on when $K=5$. Notably, both exact and approximated WKNN-Shapley markedly outperform the unweighted KNN-Shapley (either soft-label or hard-label) across most datasets. This can likely be attributed to WKNN-Shapley’s ability to more accurately differentiate between bad and good data based on the proximity to the queried example. In Appendix LABEL:appendix:eval-comparison, we present a qualitative study highlighting why WKNN-Shapley outperforms unweighted KNN-Shapley in discerning data quality. Exact vs Approximated WKNN-Shapley: From Table 1, we can see an encouraging result that the approximated WKNN-Shapley achieves performance comparable to (and sometimes even slightly better than) the exact WKNN-Shapley across the majority of datasets. This is likely attributable to its favored property in preserving the fairness properties of its exact counterpart. Robustness to the choice of $K$: In Figure 3, we show that, compared to unweighted KNN-Shapley, WKNN-Shapley maintains notably stable performance across various choices of $K$, particularly for larger values. This is because those benign data points—though within the $K$ nearest neighbors of the query example and possessing different labels—may not receive a very low value due to their likely distant positioning from the query example. Conversely, unweighted KNN-Shapley tends to assign these benign points lower values.