The Shapley value is the gold standard for fair attribution in cooperative game theory. Whether you are allocating credit to features in a machine learning model, data points in a training set, or clients in federated learning, the Shapley value provides a unique, axiomatically justified solution.
But it comes with a fatal flaw: computing it exactly is an NP-hard problem. To find the exact Shapley value of a single feature, you must calculate its marginal contribution across every possible subset of the remaining features. For $N$ features, this requires evaluating the model $2^N$ times. If $N=100$, the number of required evaluations exceeds the number of atoms in the observable universe.
To make Shapley values practical, a massive body of research focuses on efficient approximation. Rather than treating the model as an impenetrable black box and computing every combination, modern techniques scale this game-theoretic tool to high-dimensional spaces by exploiting three core intuitions: statistical sampling, surrogate models, and structural propagation.
Intuition 1: Shapley as an Expected Value
The first breakthrough in scaling the Shapley value comes from reframing what it actually represents. Mathematically, the Shapley value of a feature is simply its expected marginal contribution when added to a coalition of features chosen uniformly at random from all possible permutation orders.
Because it is an expectation, we do not need to compute every single permutation to find the truth. Instead, we can estimate it using statistical sampling. By the Law of Large Numbers, averaging the marginal contributions across a small, randomly sampled subset of permutations will converge to the true Shapley value.
Exact Shapley: Sum over ALL 2^N coalitions (Exponential)
|
v
Stochastic Sampling: Sample a representative subset of permutations (Linear/Polynomial)
To minimize the number of samples needed for a stable estimate, researchers focus on reducing variance:
- Stratified and Adaptive Sampling: Not all coalitions contribute equally to the variance of the estimate. Mark Alexander Burgess et al. introduce the Stratified Empirical Bernstein Method in Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling. By using concentration inequalities, their approach dynamically allocates a sampling budget to the specific "strata" (coalition sizes) that exhibit the highest statistical variance, drastically reducing approximation error with fewer model evaluations.
- Deterministic Priority Sampling: Instead of purely random sampling, Michele Cafagna et al. demonstrate in Interpreting Vision and Language Generative Models with Semantic Visual Priors that prioritizing high-impact coalitions based on domain-specific priors yields significantly lower error rates than standard Monte Carlo methods.
- Decoupling Marginal Contributions: Traditional sampling requires paired model evaluations (evaluating the model with and without the feature) for every sample. Patrick Kolpaczki et al. challenge this in Approximating the Shapley Value without Marginal Contributions with their framework, SVARM. They prove that the Shapley value can be mathematically reformulated as the difference between two weighted averages of coalition values. This insight allows a single model evaluation to update the importance scores of all features simultaneously, breaking the requirement for paired evaluations and tightening variance bounds.
Intuition 2: Bypassing Retraining via Surrogates
While feature attribution requires evaluating a pre-trained model multiple times, data valuation (measuring the worth of a specific training data point) introduces a much harsher bottleneck. To evaluate a subset of data points exactly, you must retrain the entire machine learning model from scratch on that subset. This turns an already exponential problem into a double-exponential computational nightmare.
To solve this, researchers replace the expensive model with a computationally cheap surrogate or leverage intermediate representations that bypass retraining entirely.
Data Valuation Bottleneck: Subset S -> Retrain Deep Network -> Evaluate (Impossible)
Surrogate Acceleration: Subset S -> Look up in KNN Surrogate -> Analytical Score (O(N log N))
- KNN Surrogates on Frozen Embeddings: Fan Wu et al. tackle this in Scalability vs. Utility: Do We Have To Sacrifice One for the Other in Data Importance Quantification?. They pass the dataset through a frozen, pre-trained deep network to extract embeddings, and then construct a K-Nearest Neighbor (KNN) classifier on top of those embeddings. Because the decision boundaries of a KNN model are purely geometric, the exact Shapley values for data points can be computed analytically using a recursive algorithm in just $O(N \log N)$ time, completely avoiding model retraining.
- Exploiting Training Artifacts: In collaborative environments like Vertical Federated Learning, where different parties hold different features for the same individuals, retraining models for every combination of participants is impossible. Zhenan Fan et al. show in Fair and Efficient Contribution Valuation for Vertical Federated Learning that participant contributions can be approximated linearly by analyzing intermediate training embeddings and gradients generated during the primary training run. The shared representations act as a proxy for data quality, allowing fair value distribution without a single round of combinatorial retraining.
Intuition 3: Exploiting Structural and Statistical Propagation
If we open up the "black box" and look at the internal architecture of a model, we can often bypass sampling entirely. By exploiting the mathematical structure of neural networks or relational graphs, we can propagate values deterministically.
- Analytical Uncertainty Propagation: Instead of sampling discrete feature combinations, Marco Ancona et al. introduce Deep Approximate Shapley Propagation (DASP) in Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Value Approximation. They treat the presence or absence of features in a coalition as a random variable. By leveraging uncertainty propagation techniques, they analytically track the mean and variance of these coalition distributions directly through the layers of a Deep Neural Network. This converts an exponential combinatorial search into a single, polynomial-time forward pass.
- Locality and Graph Motifs: In relational data, features are not independent; they are bound by topology. Alan Perotti et al. exploit this in GRAPHSHAP: Motif-based Explanations for Black-box Graph Classifiers. Instead of marginalizing over every arbitrary subset of graph edges, their depth-based approximation restricts the game to localized subgraphs or "motifs." Because distant nodes have exponentially decaying impacts on local predictions, focusing purely on local feature neighborhoods reduces the computational complexity from exponential to linear relative to the number of features.
Summary
The exact calculation of the Shapley value remains fundamentally intractable, but its practical application is not. By treating the attribution as a statistical expectation to be sampled, substituting heavy models with geometric surrogates, or propagating statistical distributions directly through network architectures, modern approximation frameworks make game-theoretic fairness accessible to large-scale, real-world machine learning systems.