PaperlayerView exact revision on arXiv

Source-linked AI summary

Sampling Permutations for Shapley Value Estimation

Rory Mitchell, Joshua Cooper, Eibe Frank, Geoffrey Holmes

arXiv:2104.12199v2stat.MLcs.LGmath.CO

TL;DR

Shapley values are hard to compute exactly, and quasi-Monte Carlo methods had not been extended to permutation sampling. The paper develops kernel-based quadrature and hypersphere-based permutation sampling, finding improved convergence and smaller RMSE at equal model-evaluation budgets, while noting scope limitations for hypersphere methods.

  • Problem

    Exact Shapley-value computation is generally NP-hard, and standard Monte Carlo can converge slowly because quasi-Monte Carlo methods have not been extended to permutations.

  • Method

    The paper combines RKHS quadrature with the Mallows kernel and hypersphere-based methods, including orthogonal spherical codes and Sobol permutations.

  • Results

    The introduced sampling methods show improved convergence over existing methods in many cases, with kernel herding attaining O(1/n) versus O(1/√n) for ordinary Monte Carlo.

  • Takeaways & Limitations

    Permutation sampling can be improved through discrepancy-aware kernel methods and well-distributed hypersphere constructions for Shapley-value approximation.

  • Takeaways & Limitations

    Explicit Sobol discrepancy convergence rates on the unit cube do not translate to the hypersphere, and some kernel methods require expensive optimization.

Abstract

from arXiv · show

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.

1. Introduction

The paper addresses slow Shapley-value approximation by adapting quasi-Monte Carlo ideas to permutations. It develops kernel- and hypersphere-based sampling methods and evaluates their discrepancy and approximation error.

  • Motivation: Exact Shapley-value computation is generally NP-hard, while existing quasi-Monte Carlo guarantees for the unit cube do not extend to permutations.The paper therefore seeks well-characterized permutation samples for approximation.
  • Kernel methods: The RKHS approach uses permutation kernels, kernel herding, and sequential Bayesian quadrature to estimate Shapley values.The Mallows kernel yields an explicit O(1/n) convergence rate versus O(1/√n) for ordinary Monte Carlo.
  • Hypersphere methods: A second approach exploits an isomorphism between permutations and the hypersphere S^(d−2) to generate well-distributed samples.The proposed methods are orthogonal spherical codes and Sobol permutations.
  • Broader scope: The permutation discrepancy analysis may apply to statistics of functions of permutations beyond Shapley values.The derived quasi-Monte Carlo error bounds are not restricted to Shapley-value estimation.
  • Evaluation: The experiments compare discrepancy and Shapley-value approximation error on tabular and image datasets.They evaluate reduction in mean squared error against exact values and empirical variance for neural-network models.

2. Background and Related Work

This section introduces Shapley values, their permutation-based estimator, and established sampling alternatives. It frames the paper’s focus as selecting permutations carefully to improve approximation efficiency.

  • Shapley values: Shapley values distribute cooperative-game proceeds by measuring each coalition member’s marginal contribution.In machine learning, they attribute predictive-model outputs to input features.
  • Shapley values: The permutation formulation expresses each feature’s Shapley value as an average of marginal contributions along orderings.The ordering determines the lower-ranked players preceding the feature.
  • Monte Carlo: The standard Monte Carlo estimator samples uniformly from permutations and converges asymptotically at O(1/√n).A single sampled permutation can provide marginal contributions for all features using d + 1 function evaluations.
  • Existing alternatives: Antithetic sampling uses correlated permutation pairs, commonly a permutation and its reverse, to reduce variance when outputs are negatively correlated.The paper implements this reverse-permutation strategy in its experiments.
  • Existing alternatives: Other alternatives include multilinear extension sampling over feature subsets and stratified sampling over marginal contributions grouped by feature position.The paper implements versions with fixed q intervals and strata indexed by feature and position.

3. Kernel Methods

The kernel methods impose similarity structure on permutations, select samples through greedy quadrature procedures, and derive an RKHS discrepancy bound for approximation error.

  • Permutation kernels: Because permutation distances are not implicit, the method imposes similarity through kernels and selects samples with favorable kernel-relative distributions.The paper considers Kendall, Mallows, and Spearman-based kernels.
  • Permutation kernels: The Kendall and Mallows kernels compare permutations through concordant and discordant pairs, while the Mallows kernel normalizes distance by permutation length.The normalized distance supports consistent λ selection across different lengths.
  • Kernel herding: Kernel herding greedily selects unweighted permutation samples while converging toward the uniform distribution.For Shapley estimation, the target distribution assigns p(σ) = 1/d! to every permutation.
  • Kernel herding: Under universality and mild argmax assumptions, kernel herding achieves O(1/n) convergence instead of O(1/√n) for standard Monte Carlo.Among the considered kernels, only the Mallows kernel has the universal property.
  • Sequential Bayesian quadrature: Sequential Bayesian quadrature selects weighted samples greedily by minimizing posterior variance and solves a reweighting system for the estimate.Its variance propagates uncertainty to the final estimate, and its stated complexity is O(n^3) when argmin evaluation is constant-time.
  • Error analysis: The RKHS analysis bounds quadrature error by the product of function variation and a tractable discrepancy of the weighted permutation sample set.The Mallows kernel’s universality places bounded Shapley component functions in the RKHS.

4. Sampling Permutations on Sd−2

The paper maps permutations onto the hypersphere S^(d−2), enabling uniform, orthogonal, and low-discrepancy permutation sampling. These methods provide unbiased estimators, relate spherical geometry to permutation distances, and trade stronger guarantees against computational cost.

  • 4.1 Spheres, Permutohedrons, and the Cayley Graph: Permutations are represented as vertices of a Cayley graph inscribing the hypersphere S^(d−2), with adjacent vertices differing by one adjacent transposition.The graph connects permutation geometry to Kendall’s tau and Spearman’s rho distances.
  • 4.1 Spheres, Permutohedrons, and the Cayley Graph: Mapping a hypersphere point to its nearest permutation is performed by sorting its coordinates, yielding the permutation with maximum inner product.The nearest-neighbor candidates are Cayley-graph vertices, and the sorting operation is implemented with argsort.
  • 4.2 Uniform Sampling on the Sphere: Uniform hypersphere sampling produces uniformly distributed permutations because all coordinate orderings, and therefore all associated Voronoi cells, are equally likely.Algorithm 2 samples normalized Gaussian vectors and is proved to generate uniform permutations; the corresponding Voronoi cells have equal measure.
  • 4.3 Orthogonal Spherical Codes: Orthogonal spherical codes select well-spaced hypersphere points whose associated permutations are separated in graph distance and tend to be negatively correlated.The experiments report greater estimator accuracy than standard Monte Carlo and antithetic sampling in all evaluations.
  • 4.4 Sobol Sequences on the Sphere: Sobol permutations project low-discrepancy Sobol points from the unit cube onto the hypersphere, producing unbiased uniform permutation samples in linear time.The reported d = 4 sample distribution is clearly uniform, while the hypersphere methods have linear complexity in the number of samples.
  • 4.5 Discussion: Compared with kernel herding and sequential Bayesian quadrature, hypersphere-based methods offer cheaper sampling but fewer explicit quadrature-error guarantees.The paper frames this as a trade-off between expensive discrepancy optimization and practical linear-time generation.

5. Evaluation

The evaluation compares existing and proposed permutation-sampling methods across tabular and image models using Shapley-value error, discrepancy, runtime, and variance measures. Performance depends on model, dimensionality, and sampling method.

  • Evaluation design: The study evaluates permutation sampling on tabular, image, and data-independent discrepancy tasks across GBDT, MLP, and convolutional neural-network models.The tabular datasets mix classification and regression problems with varying dimensionality; high-dimensional natural-language problems are excluded.
  • Existing methods: MC-antithetic is the most effective existing algorithm in all tabular GBDT experiments and serves as the subsequent baseline.The experiments measure mean squared error against exactly calculated Shapley values, with shaded 95% confidence intervals.
  • GBDT models: Kernel herding and SBQ perform well on lower-dimensional regression datasets but are outperformed by MC-antithetic on higher-dimensional adult and year datasets.Where herding and SBQ are effective, SBQ has lower mean squared error than herding.
  • GBDT models: The orthogonal method improves over MC-antithetic as sample counts increase across all six GBDT problems, while Sobol is outperformed by the baseline in four of six cases.The orthogonal method extends antithetic sampling by increasing correlated samples from 2 to 2(d −1).
  • MLP models: MLP experiments show similar low-dimensional herding and SBQ behavior, while orthogonal sampling consistently outperforms MC-antithetic across datasets.More tightly clustered results for some MLP datasets may indicate fewer higher-order feature interactions and lower Shapley-value variance.
  • Discrepancy and runtime: For d = 10 and n = 1000, herding nearly halves discrepancy relative to antithetic sampling, whereas orthogonal and Sobol methods are most effective at d = 200.At large sample counts, herding and SBQ become impractical; herding takes 242s to generate n = 1000 permutations at d = 200.
  • Discrepancy and runtime: Discrepancy measures provide a reference for selecting permutation samples for any bounded function f : Sd →R, not only Shapley-value approximation.The corresponding quasi-Monte Carlo error bounds therefore extend beyond the machine-learning applications evaluated here.
  • Image models: In the ResNet50 image experiments, Sobol has the lowest error estimate in every case, while herding, orthogonal, and SBQ generally have lower sample variance than plain Monte Carlo.Exact baselines are intractable, so image-model errors are estimated from repeated trials.

6. Conclusion

The paper introduces two families of permutation-sampling methods for Shapley-value approximation and finds that their relative effectiveness depends on problem dimensionality. It also identifies conditions requiring further study.

  • Conclusion: The paper proposes RKHS-based kernel methods and hypersphere-based sampling methods for approximating Shapley values from carefully selected permutations.The methods are evaluated on GBDT, neural-network, tabular, and image problems, alongside data-independent discrepancy scores.
  • Conclusion: Kernel-based methods may be more effective for lower-dimensional problems, while methods sampling from Sd−2 may be more effective for higher-dimensional problems.This dimensionality-dependent pattern is reported as an empirical conclusion rather than a universal rule.
  • Conclusion: Further work is needed to identify when Mallows-kernel discrepancy optimisation is effective and how dimensionality determines the preferred sampling algorithm.

A. Proof of Theorem 2 (See page 18)

The proof analyzes permutation distances through adjacent transpositions, inversion structure, and weighted graph edges. These bounds support the theorem’s characterization of permutation geometry.

  • Permutation length: The inversion count of a permutation equals the minimum number of adjacent transpositions needed to construct it.This quantity is also the permutation’s length and the distance in the permutohedron’s 1-skeleton.
  • Permutation length: A bubble-sort decomposition produces adjacent transpositions whose associated graph edges are distinct because each pair of entries switches places at most once.
  • Permutation length: Each transposition in the decomposition decreases the auxiliary quantity ν, because the sequence only increases the number of inversions.The proof tracks ν through successive products πj and πj+1.
  • Graph bounds: The distinct transposition edges form a weighted complete graph, allowing lower and upper bounds on ν through greedy selection of high- or low-weight edges.
  • Graph bounds: Summing edge weights yields the polynomial bounds used to bracket the relevant index k and define the parameter α.The proof uses separate sums for the smallest and largest edge weights.
  • Asymptotic control: The proof controls approximation error in these sums using f(s ± 1) = f(s) + O(d2) when s = O(d).
  • Permutation geometry: The identity ν(σ′ ◦σ−1) = IT(σ′ ◦σ−1) = σTσ′ connects the permutation quantity to inversion structure and vector inner products.The proof then represents permutations as σ = ρx + µ and σ′ = ρx′ + µ.
  • Permutation geometry: For random permutations, σTσ′ is approximately d3(1/4 + o(1)), corresponding to A(σ)T A(σ′) ≈0.

B. Selection of parameters for the Mallows kernel

Parameter studies examine the Mallows-kernel λ value, the number of argmax trials, and alternative permutation kernels. The results support fixed practical settings but show that optimal choices vary by problem.

  • Mallows-kernel parameter: The experiments fix the Mallows-kernel parameter at λ = 4 rather than tuning it separately for each dataset, to avoid an unfair performance reflection.The same value is used for kernel herding, SBQ, and discrepancy calculations.
  • Mallows-kernel parameter: No consistently effective λ is identified across tabular GBDT, tabular MLP, and image ResNet50 settings.For some dataset/model combinations smaller λ values are preferable, while for others larger values perform better.
  • Mallows-kernel parameter: For 256-dimensional image data, varying λ has little average impact on herding performance.
  • Argmax trials: Using 25 argmax trials is chosen as a compromise between accuracy and runtime because increasing trials improves accuracy with diminishing returns.Five to ten trials are insufficient for optimal performance in the reported GBDT tabular experiments.
  • Kernel comparison: The Mallows kernel performs at least as well as the other non-universal kernels and often better in tabular GBDT herding experiments.The Spearman kernel is clearly outperformed by both Mallows and Kendall tau, while Kendall tau is effective on four of six datasets.
Loading 2104.12199v2…