A Multilinear Sampling Algorithm to Estimate Shapley Values
  Shapley values are great analytical tools in game theory to measure the
importance of a player in a game. Due to their axiomatic and desirable
properties such as efficiency, they have become popular for feature importance
analysis in data science and machine learning. However, the time complexity to
compute Shapley values based on the original formula is exponential, and as the
number of features increases, this becomes infeasible. Castro et al. [1]
developed a sampling algorithm, to estimate Shapley values. In this work, we
propose a new sampling method based on a multilinear extension technique as
applied in game theory. The aim is to provide a more efficient (sampling)
method for estimating Shapley values. Our method is applicable to any machine
learning model, in particular for either multi-class classifications or
regression problems. We apply the method to estimate Shapley values for
multilayer perceptrons (MLPs) and through experimentation on two datasets, we
demonstrate that our method provides more accurate estimations of the Shapley
values by reducing the variance of the sampling statistics.
