  Game-theoretic attribution techniques based on Shapley values are used
extensively 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 are not well defined on 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 to obtain explicit convergence rates of $O(1/n)$, improving on
$O(1/\sqrt{n})$ for plain Monte Carlo. 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.
