B0943
Title: Fast approximation of the Shapley values based on order-of-addition experimental designs
Authors: Wei Zheng - University of Tennessee (United States) [presenting]
Liuqing Yang - Central South University (China)
Yongdao Zhou - Nankai University (China)
Haoda Fu - Eli Lilly and Company (United States)
Min-Qian Liu - Nankai University (China)
Abstract: Shapley value is originally a concept in econometrics to fairly distribute both gains and costs to players in a coalition game. In recent decades, its application has been extended to other areas, such as marketing, engineering and machine learning. However, its heavy computational burden has been long recognized but rarely investigated. Specifically, in a $d$-player coalition game, calculating a Shapley value requires the evaluation of $d!$ or $2^d$ marginal contribution values, depending on whether we are taking the permutation or combination formulation of the Shapley value. Hence it becomes infeasible to calculate the Shapley value when $d$ is reasonably large. A common remedy is to take a random sample of the permutations to surrogate for the complete list of permutations. We find 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 for the study of 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. Both theoretical and simulation results show that our DOE-based sampling scheme outperforms SRS in terms of estimation accuracy.
