Improving Cooperative Game Theory-based Data Valuation via Data Utility Learning
Published in
(2021)External Links:
TL
TL;DR
This work proposes to boost the efficiency in computing Shapley value or Least core by learning to estimate the performance of a learning algorithm on unseen data combinations by derived bounds relating the error in the predicted learning performance to the approximation error in SV and LC.
Abstract
The Shapley value (SV) and Least core (LC) are classic methods in cooperative game theory for cost/profit sharing problems. Both methods have recently been proposed as a principled solution for data valuation tasks, i.e., quantifying the contribution of individual datum in machine learning. However, both SV and LC suffer computational challenges due to the need for retraining models on combinatorially many data subsets. In this work, we propose to boost the efficiency in computing Shapley value or Least core by learning to estimate the performance of a learning algorithm on unseen data combinations. Theoretically, we derive bounds relating the error in the predicted learning performance to the approximation error in SV and LC. Empirically, we show that the proposed method can significantly improve the accuracy of SV and LC estimation.
References21 items
1
A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"
2
Scalability vs. Utility: Do We Have to Sacrifice One for the Other in Data Importance Quantification?
3
If You Like Shapley Then You'll Love the Core
4
A Principled Approach to Data Valuation for Federated Learning
5