# A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"

arXiv: https://arxiv.org/abs/2304.04258 · HTML: https://mlsanity.com/paper/2304.04258/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 33 references that are in the map.
- First posted on arXiv 9 Apr 2023.

## Builds on (most cited first, 18 of 18)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms](https://mlsanity.com/paper/1908.08619/) (2019)
- [A Principled Approach to Data Valuation for Federated Learning](https://mlsanity.com/paper/2009.06192/) (2020)
- [Sampling Permutations for Shapley Value Estimation](https://mlsanity.com/paper/2104.12199/) (2021)
- [A Distributional Framework for Data Valuation](https://mlsanity.com/paper/2002.12334/) (2020)
- [Measuring the Effect of Training Data on Deep Learning Predictions via Randomized Experiments](https://mlsanity.com/paper/2206.10013/) (2022)
- [Approximating the Shapley Value without Marginal Contributions](https://mlsanity.com/paper/2302.00736/) (2023)
- [A Multilinear Sampling Algorithm to Estimate Shapley Values](https://mlsanity.com/paper/2010.12082/) (2020)
- [Data Debugging with Shapley Importance over End-to-End Machine Learning Pipelines](https://mlsanity.com/paper/2204.11131/) (2022)
- [Estimation of the Shapley value by ergodic sampling](https://mlsanity.com/paper/1906.05224/) (2019)
- [Collaborative Machine Learning Markets with Data-Replication-Robust Payments](https://mlsanity.com/paper/1911.09052/) (2019)
- [A Note on "Towards Efficient Data Valuation Based on the Shapley Value''](https://mlsanity.com/paper/2302.11431/) (2023)
- [Energy-Based Learning for Cooperative Games, with Applications to Valuation Problems in Machine Learning](https://mlsanity.com/paper/2106.02938/) (2021)

## Built on by (most cited first, 11 of 11)

- [Data Shapley in One Training Run](https://mlsanity.com/paper/2406.11011/) (2024)
- [Capturing the Temporal Dependence of Training Data Influence](https://mlsanity.com/paper/2412.09538/) (2024)
- [Rethinking Data Shapley for Data Selection Tasks: Misleads and Merits](https://mlsanity.com/paper/2405.03875/) (2024)
- [Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation](https://mlsanity.com/paper/2308.15709/) (2023)
- [Efficient Data Shapley for Weighted Nearest Neighbor Algorithms](https://mlsanity.com/paper/2401.11103/) (2024)
- [Improving Retrieval-Augmented Large Language Models via Data Importance Learning](https://mlsanity.com/paper/2307.03027/) (2023)
- [Addressing Budget Allocation and Revenue Allocation in Data Market Environments Using an Adaptive Sampling Algorithm](https://mlsanity.com/paper/2306.02543/) (2023)
- [On the Inflation of KNN-Shapley Value](https://mlsanity.com/paper/2405.17489/) (2024)
- [Faithful Group Shapley Value](https://mlsanity.com/paper/2505.19013/) (2025)
- [Efficient Banzhaf-Based Data Valuation for k-Nearest Neighbors Classification](https://mlsanity.com/paper/2605.21033/) (2026)
- [Validation-Induced Shapley Shifts: How Validation Structure Distorts Data Valuation](https://mlsanity.com/paper/2607.03675/) (2026)

## Abstract (arXiv)

Data valuation is a growing research field that studies the influence of individual data points for machine learning (ML) models. Data Shapley, inspired by cooperative game theory and economics, is an effective method for data valuation. However, it is well-known that the Shapley value (SV) can be computationally expensive. Fortunately, Jia et al. (2019) showed that for K-Nearest Neighbors (KNN) models, the computation of Data Shapley is surprisingly simple and efficient. In this note, we revisit the work of Jia et al. (2019) and propose a more natural and interpretable utility function that better reflects the performance of KNN models. We derive the corresponding calculation procedure for the Data Shapley of KNN classifiers/regressors with the new utility functions. Our new approach, dubbed soft-label KNN-SV, achieves the same time complexity as the original method. We further provide an efficient approximation algorithm for soft-label KNN-SV based on locality sensitive hashing (LSH). Our experimental results demonstrate that Soft-label KNN-SV outperforms the original method on most datasets in the task of mislabeled data detection, making it a better baseline for future work on data valuation.