Exact and Certified Data Shapley for Weighted Nearest Neighbor Regression

Abstract

Data Shapley can be computed exactly and efficiently for unweighted K-nearest-neighbor (KNN) models, the basis of the popular KNN-Shapley. For weighted KNN, however, efficient exact algorithms are known only for hard-label classification. In regression, the prediction is a weighted average whose normalization term changes with every subset. The best exact algorithm then takes O(N^K) time for N training points. We show that this normalization term is not an obstacle. A subset affects the prediction only through two numbers: the total weight of its K nearest neighbors and their total weighted target. Once the weights are discretized, subsets with equal total weight share their normalization term and can be summed as a group. This gives an exact algorithm that is near-linear in N and polynomial in K and the number of weight levels, for real targets under the squared loss. The same idea gives exact values for soft-label classifiers in the same time, and speeds up the earlier exact algorithm for hard labels by a factor of N. For continuous weights, we give a deterministic approximation with a certified error bound, without discretizing the weights. On the downside, we prove that some exact values take exponentially many bits to write down, so the dependence on weight precision cannot be removed in general. In experiments on real datasets with up to 100,000 training points and with 10 or 100 validation points, we compare the exact values with Monte Carlo estimates computed in the same time. Monte Carlo ranks the points less and less like the exact values as the training set grows. Two of its runs also disagree on a large share of the top 10% of points.