Shapley Value Approximation Based on k-Additive Games
This addresses a computational bottleneck for researchers and practitioners using Shapley values in machine learning for feature or data point contribution analysis, representing an incremental improvement.
The paper tackles the computational complexity of the Shapley value, which scales exponentially with the number of entities, by proposing SVA$k_{\text{ADD}}$, a novel approximation method based on $k$-additive surrogate games, and evaluates its efficacy empirically against competing methods.
The Shapley value is the prevalent solution for fair division problems in which a payout is to be divided among multiple agents. By adopting a game-theoretic view, the idea of fair division and the Shapley value can also be used in machine learning to quantify the individual contribution of features or data points to the performance of a predictive model. Despite its popularity and axiomatic justification, the Shapley value suffers from a computational complexity that scales exponentially with the number of entities involved, and hence requires approximation methods for its reliable estimation. We propose SVA$k_{\text{ADD}}$, a novel approximation method that fits a $k$-additive surrogate game. By taking advantage of $k$-additivity, we are able to elicit the exact Shapley values of the surrogate game and then use these values as estimates for the original fair division problem. The efficacy of our method is evaluated empirically and compared to competing methods.