Exact and Certified Data Shapley for Weighted Nearest Neighbor Regression

Excerpt

arXiv:2607.11956v3 Announce Type: replace-cross 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 normalizat