A0650
Title: Fast approximation of the Shapley values
Authors: Wei Zheng - University of Tennessee (United States) [presenting]
Abstract: The Shapley value has been widely used in game theory, local model explanation and sensitivity analysis. However, its calculation is an NP-complete problem. Specifically, calculating a $d$-player Shapley value requires evaluating $d!$ or $2^d$ marginal contribution values, each associated with permutations of the $d$ players. Hence it becomes infeasible to calculate the Shapley value when $d$ is too large. A common remedy is to take a random sample of the permutations as a surrogate for the complete list of permutations. An advanced sampling scheme can be designed to yield a much more accurate estimation of the Shapley value than simple random sampling (SRS). Our sampling scheme is based on combinatorial structures in the field of design of experiment (DOE), particularly the order-of-addition experimental designs, to study how the orderings of the components would affect the output. We show that the obtained estimates are unbiased and consistent, sometimes even deterministically recover the original Shapley value based on the full permutation. Both theoretical and simulations results show that our DOE based sampling scheme outperforms SRS.
