Abstract
Data Shapley provides a principled answer to the value of training points, with its k-nearest-neighbor (KNN) specialization being widely deployed in practice. The exact estimator is provided by toolkits like pyDVL and OpenDataVal. While exact algorithms exist for unweighted KNN and weighted KNN classification, weighted KNN regression and soft-label prediction have remained unresolved: the only exact method is an O(N^K) brute force, which grows exponentially with neighborhood size K.
Problem Analysis
The weighted regression prediction is a ratio of two coalition-dependent sums, and its normalization denominator disrupts the additive, threshold, and duplication structures that prior polynomial algorithms rely on. We successfully close this gap.
Key Contributions
- We present the first pseudo-polynomial-time exact algorithm (polynomial in N and K at fixed lattice precision) for weighted KNN-regression Data Shapley, a counting dynamic program over the joint integer state, verified against exhaustive enumeration with zero mismatch on 12,716 adversarial instances.
- We provide a certified FPTAS for continuous weights and targets, with a machine-checkable per-value error certificate never violated across 86,400 checks.
- We outline a complexity landscape, including an unconditional Omega(D_w) output-size lower bound and access-model hardness results.
- We provide a weighted soft-label multi-class extension.
We release an open-source, CPU-only library and the first exact weighted-regression Data Shapley ground truth. On downstream mislabel detection, our exact values are statistically equivalent to Monte-Carlo Data Shapley (dataset-level TOST, n=8, p).
Blogger's Review: This research marks a significant advancement in the exact Data Shapley algorithm for weighted KNN regression, addressing previous limitations and providing a powerful tool for future research and applications. The release of open-source code will further foster exploration and innovation within the community.