Approximating Shapley Values for Scalable Model Explanation

This direction is merged into another direction: efficient Shapley value approximation. Its last version stays readable and citable here.

Version 1 of 1112 papers119 conceptsfrozen 2026-10-04

In the effort to peer inside the "black box" of modern machine learning, researchers have increasingly turned to a 70-year-old concept from cooperative game theory: the Shapley value. Originally developed by Lloyd Shapley to fairly distribute a total prize among players in a game, it has become the gold standard for feature attribution.

The intuition is simple: if a model predicts a high risk of heart disease for a patient, the Shapley value tells us exactly how much of that risk score is "owned" by their age, their blood pressure, or their cholesterol. Unlike simple heuristics, the Shapley value is uniquely "fair"—it is the only distribution method that satisfies key mathematical axioms, such as ensuring that the sum of all feature contributions perfectly equals the model's output.

However, calculating these values is notoriously difficult. As Haris Aziz and Bart de Keijzer note in Shapley Meets Shapley, the problem is generally #P-complete. To find the exact contribution of one feature, you must evaluate how it changes the model's output across every possible combination of all other features. For a model with $N$ features, this requires $2^N$ evaluations—an exponential explosion that makes exact calculation impossible for anything beyond the simplest datasets.

The Intuition of Sampling

The core breakthrough in this field is the realization that we do not need to see every possible "team" of features to understand a single player's impact. Just as a scout can estimate a baseball player's value by watching a representative sample of games, researchers use Monte Carlo sampling to estimate marginal contributions.

By drawing random permutations of features and observing how the model's output shifts when a specific feature is added, we can converge on the true Shapley value with high probability. This approach is central to the Quantitative Explainability Framework (QEF) developed by Thanveer Shaik and Xiaohui Tao. They demonstrate that even in high-dimensional medical data, a sampled subset of feature coalitions can provide the transparency clinicians need for real-time decision-making without the exponential wait.

From Sampling to Sketching

While Monte Carlo methods are robust, they can still be slow. Recent work has moved toward more sophisticated mathematical "shortcuts." In A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values, Tyler Chen and colleagues frame the estimation of feature importance as a "sketched" regression problem. By using randomized sketching techniques from numerical linear algebra, they provide the first non-asymptotic bounds for popular estimators like KernelSHAP, allowing these methods to scale to complex datasets like CIFAR-10.

Other researchers, such as Marco Ancona and Cengiz Öztireli, have proposed bypassing sampling entirely. Their algorithm, Deep Approximate Shapley Propagation (DASP), treats feature coalitions as random variables and propagates their probability distributions through the layers of a neural network. This reduces the complexity from exponential to polynomial, allowing for theoretically grounded explanations at a fraction of the cost.

Applications Beyond Interpretability

The ability to approximate Shapley values efficiently has opened doors beyond just explaining a single prediction:

  • Feature Selection: Shay B Cohen and Eytan Ruppin introduced the Contribution-Selection Algorithm (CSA), which uses Shapley values to identify the most critical features in a dataset, accounting for complex multi-variable dependencies that traditional methods miss.
  • Data Valuation: In the age of generative AI, Jiachen T. Wang and Zhun Deng suggest using Shapley-based sampling to fairly compensate creators whose copyrighted data was used to train a model.
  • Reinforcement Learning: Daniel Beechey and Özgür Şimşek have adapted these tools to Reinforcement Learning, using Monte Carlo sampling to pinpoint which environmental features drive an agent's success in high-dimensional state spaces.

Why It Works

The success of these approximation methods rests on a fundamental property of high-dimensional spaces: the "law of large numbers" for feature interactions. While the total number of feature combinations is vast, the average marginal contribution of a feature tends to stabilize relatively quickly. By strategically sampling the space—whether through the hybrid exact/sampling approach of the kernelshap package by Michael Mayer or the multi-layer sampling of BSED—we can achieve a "rigorous enough" explanation that satisfies both mathematical axioms and practical engineering constraints.

Papers in this version

Showing 60 of 112 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_approximating_shapley_values_for_scalabl_b9a97de9,
  title = {Approximating Shapley Values for Scalable Model Explanation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/approximating-shapley-values-for-scalable-model-explanation/rdr_b9a97de9e5e34e0880b1c55e8b243b7d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_approximating_shapley_values_for_scalabl_b9a97de9_v1,
  title = {Approximating Shapley Values for Scalable Model Explanation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/approximating-shapley-values-for-scalable-model-explanation/rdr_b9a97de9e5e34e0880b1c55e8b243b7d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}