ORTHOGONAL PERMUTATION SAMPLING FOR SHAPLEY VALUES: UNBIASED STRATIFIED ESTIMATORS WITH VARIANCE GUARANTEES
Abstract
Shapley values for feature attribution suffer from high variance requiring thousands of model evaluations. We introduce Orthogonal Permutation Sampling (OPS), achieving provable variance reduction through: (i) exact position stratification, (ii) antithetic permutation coupling, and (iii) control variates. We prove finite-sample variance dominance over Monte Carlo and non-positive covariance under submodularity. Empirical validation across six benchmarks shows 5-26× variance reduction for typical dimensions (n=10-20) and 67× for n=50. OPS achieves 2-5× lower MSE than KernelSHAP at equivalent budgets with 7% runtime overhead (all p
Fields of Study & Subjects
Explainable Artificial Intelligence (XAI)
Stochastic Gradient Optimization Techniques
Privacy-Preserving Technologies in Data
Publication details
- Journal / source
- Journal of Intelligent Systems and Applied Data Science
- Volume
- 3
- Issue
- 2
- Publication date
- 11 January 2026
- Language
- EN