Efficient Data Shapley for Weighted Nearest Neighbor Algorithms
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929217950711808 |
|---|---|
| author | Wang, Jiachen T. Mittal, Prateek Jia, Ruoxi |
| author_facet | Wang, Jiachen T. Mittal, Prateek Jia, Ruoxi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_11103 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Data Shapley for Weighted Nearest Neighbor Algorithms Wang, Jiachen T. Mittal, Prateek Jia, Ruoxi Data Structures and Algorithms Machine Learning 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. |
| title | Efficient Data Shapley for Weighted Nearest Neighbor Algorithms |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2401.11103 |