aiqbench analysis
This research introduces a novel hybrid framework that integrates Monte Carlo sampling with flexible linear regression formulations to significantly improve the efficiency of Shapley value estimation. By leveraging tree-based models like XGBoost and cross-fitting, the method achieves unbiased estimates with error rates up to 390 times lower than existing state-of-the-art estimators across diverse datasets. This advancement directly addresses the computational bottlenecks in explainable AI, enabling more scalable feature attribution and data valuation for complex machine learning systems.
Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values
arXiv:2506.11849v3 Announce Type: replace 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 $11\times$ lower than Permutation SHAP (the most popular Monte Carlo method), $6.5\times$ lower than Kernel SHAP (the most popular linear regression method), and $3.4\times$ lower than Leverage SHAP (the prior state-of-the-art Shapley value estimator). For more general probabilistic values, we can obtain error $390\times$ lower than the best estimator from prior work.
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 $11\times$ lower than Permutation SHAP (the most popular Monte Carlo method), $6.5\times$ lower than Kernel SHAP (the most popular linear regression method), and $3.4\times$ lower than Leverage SHAP (the prior state-of-the-art Shapley value estimator). For more general probabilistic values, we can obtain error $390\times$ lower than the best estimator from prior work.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2506.11849 [cs.LG]
(or arXiv:2506.11849v3 [cs.LG] for this version)
From: R. Teal Witter [view email] [v1] Fri, 13 Jun 2025 14:57:38 UTC (1,276 KB) [v2] Tue, 13 Jan 2026 02:37:05 UTC (1,280 KB) [v3] Thu, 8 Oct 2026 23:11:50 UTC (698 KB)
Full text under the publisher's open licence · 245 words
Related coverage
First-Order Efficiency for Probabilistic Value Estimation via A Statistical Viewpoint
arXiv · Sep 1, 2026
Bayesian Deck-of-cards-based Ordinal Regression with Sequential Preference Elicitation
arXiv · Sep 22, 2026
Priority-Aware Shapley Value
arXiv · Jun 16, 2026
Probabilistic electrical power demand forecasting with uncertainty quantification
arXiv · Sep 30, 2026