Sampling Permutations for Shapley Value Estimation
  Game-theoretic attribution techniques based on Shapley values are used to
interpret black-box machine learning models, but their exact calculation is
generally NP-hard, requiring approximation methods for non-trivial models. As
the computation of Shapley values can be expressed as a summation over a set of
permutations, a common approach is to sample a subset of these permutations for
approximation. Unfortunately, standard Monte Carlo sampling methods can exhibit
slow convergence, and more sophisticated quasi-Monte Carlo methods have not yet
been applied to the space of permutations. To address this, we investigate new
approaches based on two classes of approximation methods and compare them
empirically. First, we demonstrate quadrature techniques in a RKHS containing
functions of permutations, using the Mallows kernel in combination with kernel
herding and sequential Bayesian quadrature. The RKHS perspective also leads to
quasi-Monte Carlo type error bounds, with a tractable discrepancy measure
defined on permutations. Second, we exploit connections between the hypersphere
$\mathbb{S}^{d-2}$ and permutations to create practical algorithms for
generating permutation samples with good properties. Experiments show the above
techniques provide significant improvements for Shapley value estimates over
existing methods, converging to a smaller RMSE in the same number of model
evaluations.
