# Sampling Permutations for Shapley Value Estimation

arXiv: https://arxiv.org/abs/2104.12199 · HTML: https://mlsanity.com/paper/2104.12199/

## Key facts

- Cited by 102 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 58 references that are in the map.
- First posted on arXiv 25 Apr 2021.

## Builds on (most cited first, 9 of 9)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Explaining by Removing: A Unified Framework for Model Explanation](https://mlsanity.com/paper/2011.14878/) (2020)
- [A Multilinear Sampling Algorithm to Estimate Shapley Values](https://mlsanity.com/paper/2010.12082/) (2020)
- [Antithetic and Monte Carlo kernel estimators for partial rankings](https://mlsanity.com/paper/1807.00400/) (2018)
- [On kernel methods for covariates that are rankings](https://mlsanity.com/paper/1603.08035/) (2016)

## Built on by (most cited first, 30 of 102)

- [What does a platypus look like? Generating customized prompts for zero-shot image classification](https://mlsanity.com/paper/2209.03320/) (2022)
- [FastSHAP: Real-Time Shapley Value Estimation](https://mlsanity.com/paper/2107.07436/) (2021)
- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [The Shapley Value in Machine Learning](https://mlsanity.com/paper/2202.05594/) (2022)
- [Data Shapley in One Training Run](https://mlsanity.com/paper/2406.11011/) (2024)
- [Faith-Shap: The Faithful Shapley Interaction Index](https://mlsanity.com/paper/2203.00870/) (2022)
- [Measuring the Effect of Training Data on Deep Learning Predictions via Randomized Experiments](https://mlsanity.com/paper/2206.10013/) (2022)
- [Approximating the Shapley Value without Marginal Contributions](https://mlsanity.com/paper/2302.00736/) (2023)
- [Rethinking Data Shapley for Data Selection Tasks: Misleads and Merits](https://mlsanity.com/paper/2405.03875/) (2024)
- [Stochastic Amortization: A Unified Approach to Accelerate Feature and Data Attribution](https://mlsanity.com/paper/2401.15866/) (2024)
- [CoRTX: Contrastive Framework for Real-time Explanation](https://mlsanity.com/paper/2303.02794/) (2023)
- [Using Shapley Values and Variational Autoencoders to Explain Predictive Models with Dependent Mixed Features](https://mlsanity.com/paper/2111.13507/) (2021)
- [Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation](https://mlsanity.com/paper/2308.15709/) (2023)
- [An Economic Solution to Copyright Challenges of Generative AI](https://mlsanity.com/paper/2404.13964/) (2024)
- [HarsanyiNet: Computing Accurate Shapley Values in a Single Forward Propagation](https://mlsanity.com/paper/2304.01811/) (2023)
- [TextGenSHAP: Scalable Post-hoc Explanations in Text Generation with Long Documents](https://mlsanity.com/paper/2312.01279/) (2023)
- [Joint Shapley values: a measure of joint feature importance](https://mlsanity.com/paper/2107.11357/) (2021)
- [A Comparative Study of Methods for Estimating Conditional Shapley Values and When to Use Them](https://mlsanity.com/paper/2305.09536/) (2023)
- [Efficient XAI Techniques: A Taxonomic Survey](https://mlsanity.com/paper/2302.03225/) (2023)
- [Accelerating Shapley Explanation via Contributive Cooperator Selection](https://mlsanity.com/paper/2206.08529/) (2022)
- [DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation](https://mlsanity.com/paper/2306.02071/) (2023)
- [IG2: Integrated Gradient on Iterative Gradient Path for Feature Attribution](https://mlsanity.com/paper/2406.10852/) (2024)
- [A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"](https://mlsanity.com/paper/2304.04258/) (2023)
- [Unifying Feature-Based Explanations with Functional ANOVA and Cooperative Game Theory](https://mlsanity.com/paper/2412.17152/) (2024)
- [Stabilizing Estimates of Shapley Values with Control Variates](https://mlsanity.com/paper/2310.07672/) (2023)
- [Time to Focus: A Comprehensive Benchmark Using Time Series Attribution Methods](https://mlsanity.com/paper/2202.03759/) (2022)
- [SHAP values via sparse Fourier representation](https://mlsanity.com/paper/2410.06300/) (2024)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Statistical Significance of Feature Importance Rankings](https://mlsanity.com/paper/2401.15800/) (2024)
- [Fast Data Attribution for Text-to-Image Models](https://mlsanity.com/paper/2511.10721/) (2025)

## Abstract (arXiv)

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 mathbbSd-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.