Exact and Certified Data Shapley for Weighted k-Nearest-Neighbor Regression and Soft-Label Prediction

Abstract:Data Shapley answers which training points are worth what, and its nearest-neighbor specialization is the version actually deployed, shipped by toolkits such as pyDVL and OpenDataVal. Exact algorithms exist for unweighted nearest-neighbor classification and regression, and recently for weighted classification; weighted regression and soft-label prediction have resisted, the only exact method being enumeration exponential in the neighborhood size. The obstruction, in the prior authors' own words, is that the weighted regression prediction is a ratio of two coalition-dependent weighted sums: its normalization denominator blocks the additive and threshold routes, and leaves the counting route exponential in the target resolution. We close this gap with a counting dynamic program over the joint integer state of accumulated weight and weighted target, a minimal sufficient statistic for the ratio; it is exact, pseudo-polynomial, and matched exhaustive enumeration with zero mismatch. We add a certified approximation scheme for continuous weights and targets carrying a machine-checkable per-value certificate, a complexity landscape delimiting the exact problem, and a soft-label extension. We release an open-source, CPU-only library and the first exact weighted-regression ground truth. On mislabel detection our exact values are statistically equivalent to Monte-Carlo Data Shapley; exactness instead buys determinism, a certified bound, and an auditing reference, and it puts a measured price on approximation.

Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS)

I.2.6; H.2.8; F.2.2; G.1.2

arXiv:2607.11956 [cs.LG]

(or arXiv:2607.11956v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2607.11956 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.