Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values

arXiv:2506.11849v3 Announce Type: replace-cross Abstract: With origins in game theory, probabilistic values like Shapley values, Banzhaf values, and semi-values have emerged as a central tool in explainable AI. They are used for feature attribution, data attribution, data valuation, and more. Since exact computation can require exponential time, research has focused on efficient approximation methods using two techniques: Monte Carlo sampling and linear regression formulations. In this work, we present a new way of combining both of these techniques. Our approach is more flexible than prior algorithms, allowing for linear regression to be replaced with any function family whose probabilistic values can be computed efficiently. This allows us to harness the accuracy of tree-based models like XGBoost; with cross-fitting, the method also produces unbiased estimates. From experiments across eight datasets, we find that our methods give state-of-the-art performance for estimating probabilistic values. For Shapley values, the error of our methods can be 11imes lower than Permutation SHAP (the most popular Monte Carlo method), 6.5imes lower than Kernel SHAP (the most popular linear regression method), and 3.4imes lower than Leverage SHAP (the prior state-of-the-art Shapley value estimator). For more general probabilistic values, we can obtain error 390imes lower than the best estimator from prior work.

Related

• Provably Accurate Shapley Value Estimation via Leverage Score Sampling
• TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions
• Explaining BiomedCLIP with Weighted Banzhaf Interactions Supported by Tree-Gram Parsing

Source: arXiv cs.AI | 2026-10-12