📊 statistics

Approximate Shapley value estimation using sampling without replacement and variance estimation via the new Symmetric bootstrap and the Doubled half bootstrap

This paper proposes an enhanced KernelSHAP algorithm that utilizes Wallenius' noncentral hypergeometric distribution for sampling without replacement and introduces the Symmetric bootstrap for variance estimation, demonstrating performance comparable to or better than existing state-of-the-art methods in simulation studies.

Original authors: Fredrik Lohne Aanes

Published 2026-01-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Fredrik Lohne Aanes

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Sharing the Pie Fairly

Imagine you and a group of friends bake a giant cake (this is your AI model's prediction). You want to know exactly how much each friend contributed to the final taste. Did the baker add the most flour? Did the decorator add the most sugar?

In the world of data science, this is called calculating Shapley values. It's a mathematical way to fairly split the "credit" for a prediction among different features (like age, income, or health stats).

The problem is that calculating the exact contribution of every single friend is incredibly slow. If you have 20 friends, there are over a million different ways they could combine to bake the cake. You can't taste every single combination.

The Old Way: The "With Replacement" Lottery

The standard method (called KernelSHAP) tries to solve this by taking a shortcut. It acts like a lottery:

It puts all possible friend-groups (coalitions) into a giant hat.
It pulls out a few groups to taste.
The Catch: It pulls them out with replacement. This means if you pull out "Baker + Decorator," you put them back in the hat. You might pull that same pair out again, or you might never pull out "Baker + Chef."

Because of this, you might taste the same group twice and miss other groups entirely. It's like trying to collect a full set of trading cards by drawing from a deck and putting the card back every time; you might keep drawing the same common card and never find the rare ones.

The New Method: The "Without Replacement" Tasting

The author, Fredrik Lohne Aanes, proposes a smarter way to sample these groups.

1. The Wallenius' Distribution (The Weighted Hat)
Instead of a random draw, the author uses a special mathematical rule (Wallenius' noncentral hypergeometric distribution) to decide how many groups of each size to taste.

Analogy: Imagine the hat has different colored balls. Some colors are "heavier" (more important) than others. The author calculates exactly how many of each color should be in your sample to get a fair picture, rather than just hoping luck works out.

2. Sampling Without Replacement
Once the author decides how many groups to taste, they pull them out of the hat without putting them back.

Why this matters: If you pull out "Baker + Decorator," you know you won't pull them out again. This guarantees you get a diverse set of unique combinations. It's like dealing a hand of cards; once a card is dealt, it's gone. This makes the data more efficient and less "noisy."

The New Problem: How Confident Are We?

When you estimate something using a sample, you need to know how much you can trust it. In statistics, this is called the variance or standard deviation. It's like asking, "If I did this experiment again, would I get the same result?"

The author argues that the old way of checking this confidence (using standard "bootstrap" methods) is flawed for this specific type of sampling.

The Flaw: Traditional bootstrapping assumes you are drawing from an infinite pool where you can pick the same item over and over. But since the author is sampling without replacement from a finite list of possibilities, the old math breaks down. It's like trying to use a rule for an infinite ocean to measure a small, finite swimming pool.

The Solution: Two New "Confidence Checkers"

To fix the confidence check, the author introduces two new methods:

1. The Doubled Half Bootstrap (The "Old Reliable" Upgrade)
This is a known method adapted for this specific problem. It's like taking your sample, splitting it in half, and then doubling the half that wasn't picked to create a new "fake" sample to test against.

2. The Symmetric Bootstrap (The New Star)
This is the author's new invention.

How it works: Imagine you have a list of the groups you tasted. To create a new test sample, you decide for each group: "Do we include this group 0 times, 1 time, or 2 times?"
The Symmetry: The magic is that the method ensures that, on average, the number of groups you pick 0 times equals the number of groups you pick 2 times.
The Analogy: It's like a balanced seesaw. If you remove a group from the left side (0 times), you must add a duplicate of a different group to the right side (2 times) to keep the scale perfectly balanced. This ensures the math stays accurate for "without replacement" sampling.

The Results: Did It Work?

The author tested these ideas using real-world data about life expectancy (factors like GDP, schooling, and infant mortality).

The Tasting (Estimation): The new method (sampling without replacement) performed just as well as the best existing tool (called shapr). It gave the same accurate answers about who contributed what to the prediction.
The Confidence Check (Variance):
- The old "Doubled Half" method was okay but sometimes struggled with the math (the numbers didn't always add up perfectly).
- The new Symmetric Bootstrap worked very well. It was fast, easy to understand, and gave very accurate estimates of how confident we should be in the results. In fact, it performed slightly better than the built-in confidence checker in the existing shapr software.

The Conclusion

The paper doesn't claim to cure diseases or predict the stock market. It simply says:

We can calculate AI explanations more efficiently by sampling unique groups of features (without replacement) using a specific mathematical rule.
We can trust those results more by using a new, balanced way (Symmetric Bootstrap) to calculate the margin of error.

The new approach is just as good as the current industry standard for getting the answer, but it offers a better, faster, and more mathematically sound way to check how sure we are about that answer.

Technical Summary: Approximate Shapley Value Estimation Using Sampling Without Replacement and New Bootstrap Variance Estimators

1. Problem Statement

The classical KernelSHAP framework (Lundberg and Lee, 2017) aims to reduce the computational cost of Shapley value estimation by sampling a subset of coalitions rather than evaluating the contribution function for all $2^p$ possible subsets. However, existing implementations typically sample coalitions with replacement. This approach introduces specific statistical challenges:

Sampling Inefficiency: Sampling with replacement leads to a weighted version of the Coupon Collector's Problem, where obtaining unique coalitions becomes increasingly difficult as the sample size grows, particularly for low-weight coalitions.
Variance Estimation Limitations: Traditional bootstrap methods assume independent and identically distributed (i.i.d.) samples. This assumption is violated when sampling without replacement from a finite population (the set of all possible coalitions). Consequently, standard bootstrap techniques may yield incorrect variance estimates for Shapley values, failing to account for the finite population constraint where the variance should theoretically approach zero if all coalitions are evaluated.

The paper addresses these issues by proposing a framework that utilizes sampling without replacement and introduces new bootstrap methodologies compatible with finite population theory to accurately estimate the variance of approximated Shapley values.

2. Methodology

2.1 Sampling Without Replacement via Wallenius' Distribution

The proposed algorithm modifies the KernelSHAP procedure to sample coalitions without replacement. The process involves two main steps:

Stratification: Coalitions are grouped by the number of features (size) they contain.
Determining Sample Sizes: Instead of sampling coalitions one by one stochastically, the algorithm calculates the expected number of coalitions to be drawn from each group using the Wallenius' noncentral hypergeometric distribution. This distribution models biased sampling without replacement where items have different weights.
- The algorithm uses the expected values of this distribution, rounded to the nearest integer, to determine the number of coalitions to sample from each stratum.
- Once the counts are determined, coalitions are sampled without replacement within each group.
- Pairing Strategy: To further reduce variance, the method employs a pairing strategy (Kroese et al., 2013). If a coalition $S$ is sampled, its complement $S^c$ is also included in the computation, ensuring that the sum of features in paired groups remains constant.

2.2 Variance Estimation via Bootstrap Methods

The paper evaluates three approaches for estimating the standard deviation of Shapley values under the new sampling design:

Invalid Intuitive Method: A standard Horvitz-Thompson variance estimator applied directly to the weighted least squares problem. The author demonstrates this is invalid because it fails to account for the specific dependencies introduced by the pairing strategy and the structure of the $Z^T W Z$ matrix in the KernelSHAP context.
Doubled Half Bootstrap (Antal and Tillé, 2014): A known method for finite populations where units are selected via Bernoulli sampling, and non-selected units are randomly selected twice. This method is implemented for comparison.
Symmetric Bootstrap (New Contribution): A novel bootstrap method developed specifically for this context.
- Mechanism: In each bootstrap sample, every unit from the original sample can appear 0, 1, or 2 times.
- Symmetry: The method ensures that the total number of units appearing 0 times equals the total number of units appearing 2 times.
- Probabilities: The probabilities for a unit $k$ $k$ appearing $S_k$ $S_{k}$ times are defined as:
  - $Pr(S_k = 0) = Pr(S_k = 2) = \frac{1}{2}(1 - \frac{n}{N})$
  - $Pr(S_k = 1) = \frac{n}{N}$
- Properties: This construction ensures the expected value $E(S_k) = 1$ and the variance $Var(S_k) = 1 - \frac{n}{N}$ , satisfying the necessary conditions for valid variance estimation in finite population sampling (Horvitz-Thompson consistency).
- Handling Non-Integers: When the expected number of "0" or "2" occurrences is non-integer, a Bernoulli random variable is introduced to alternate between adjacent integer values, ensuring the procedure remains fully automatic.

2.3 Computational Implementation

The contribution function $v(S)$ is estimated using regression on the sampled coalitions. The implementation leverages sparse matrices and Cholesky decomposition (Matrix package) to handle linear models efficiently, capable of estimating means over 65,000 linear models on a single core within minutes (Aanes, 2025).

3. Key Contributions

Sampling Framework: Integration of the Wallenius' noncentral hypergeometric distribution into the KernelSHAP framework to enable efficient sampling without replacement, avoiding the inefficiencies of the Coupon Collector's Problem inherent in with-replacement sampling.
Symmetric Bootstrap: The introduction of a new, computationally efficient bootstrap method tailored for finite population sampling without replacement. It satisfies the necessary moment conditions (mean and variance) for unbiased variance estimation in this context.
Variance Estimation Analysis: A rigorous comparison of variance estimators, demonstrating that standard bootstrapping is invalid for this specific design and that the new Symmetric bootstrap outperforms or matches the existing Doubled half bootstrap (Antal and Tillé, 2014).

4. Results

Two simulation studies were conducted using the "Life Expectancy" dataset from Kaggle, comparing the new method against the state-of-the-art shapr R-package (version 1.0.7), which samples with replacement.

Small Simulation Study (5 features, 16 coalitions):
- The new sampling method produced Shapley value estimates with standard deviations comparable to shapr.
- The Antal-Tillé bootstrap performed poorly, frequently resulting in non-full-rank matrices ( $Z^T W Z$ ) and inaccurate variance estimates.
- The Symmetric bootstrap performed significantly better than Antal-Tillé, though it occasionally produced slightly "liberal" (smaller) standard deviations compared to the ground truth (resampling all coalitions).
Large Simulation Study (16 features, 402 coalitions):
- The Symmetric bootstrap and Antal-Tillé methods produced indistinguishable estimates of standard deviation.
- Both new bootstrap methods performed slightly better than the built-in bootstrap procedure in shapr, which tended to underestimate standard deviations for several variables.
- The new sampling algorithm (without replacement) performed similarly to the shapr method (with replacement) in terms of the accuracy of the Shapley value estimates themselves.

5. Significance and Conclusion

The paper concludes that the proposed algorithm, which combines sampling without replacement via Wallenius' distribution with the new Symmetric bootstrap, offers a robust alternative to existing KernelSHAP implementations.

Performance: The new method performs "similarly" to the improved KernelSHAP method in the shapr package regarding point estimates.
Variance Estimation: The Symmetric bootstrap is highlighted as a "very computationally fast, easy to understand" method that performs well, particularly in larger simulation studies. It addresses the gap in the literature for a "go-to" bootstrap method for random sampling without replacement in finite populations.
Limitations: The author notes modestly that in the smallest study, the Symmetric bootstrap occasionally produced standard deviations that were slightly too small (liberal) for certain variables, though it consistently captured the largest standard deviations.
Applicability: The method is designed for scenarios where the contribution function is estimated via linear or generalized linear models (where predictions are linear on a transformed scale), leveraging fast computation techniques.

The work establishes that finite population theory can be successfully applied to Shapley value estimation to improve sampling efficiency and provide valid variance estimates, overcoming the theoretical limitations of traditional i.i.d. bootstrap assumptions in this domain.