Skip to yearly menu bar Skip to main content


Efficient Data Valuation for Weighted Nearest Neighbor Algorithms

Jiachen T. Wang · Prateek Mittal · Ruoxi Jia

MR1 & MR2 - Number 185
[ ]
Oral presentation: Oral: Trustworthy ML
Sat 4 May 5 a.m. PDT — 6 a.m. PDT

Abstract: This work aims to address an open problem in data valuation literature concerning the efficient computation of Data Shapley for weighted $K$ nearest neighbor algorithm (WKNN-Shapley). By considering the accuracy of hard-label KNN with discretized weights as the utility function, we reframe the computation of WKNN-Shapley into a counting problem and introduce a quadratic-time algorithm, presenting a notable improvement from $O(N^K)$, the best result from existing literature. We develop a deterministic approximation algorithm that further improves computational efficiency while maintaining the key fairness properties of the Shapley value. Through extensive experiments, we demonstrate WKNN-Shapley's computational efficiency and its superior performance in discerning data quality compared to its unweighted counterpart.

Live content is unavailable. Log in and register to view live content