Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling
Authors: Mark A. Burgess, Archie C. Chapman
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate our sampling method on a suite of test cooperative games, and our results demonstrate that it outperforms or is competitive with existing stratified sample-based estimation approaches to computing the Shapley value. We numerically demonstrate the value of the SEBM by using it to compute the Shapley value in a suite of benchmark cooperative games. Our comparisons to existing sample-based approaches to computing the Shapley value show that our method is almost uniformly superior. |
| Researcher Affiliation | Academia | 1Australian National University, Canberra, Australia 2The University of Queensland, Brisbane, Australia mark.burgess@anu.edu.au, archie.chapman@uq.edu.au |
| Pseudocode | Yes | Algorithm 1 Stratified Empirical Bernstein Method (SEBM) with replacement |
| Open Source Code | Yes | 1see: https://github.com/markopolo141 /Stratified Empirical Bernstein Sampling |
| Open Datasets | No | The paper defines four "Example Games" (cooperative game definitions with characteristic functions and weights) used for evaluation within the paper itself (e.g., "Example Game 1 (Airport Game)"). These are custom-defined scenarios rather than publicly available datasets with external access information. |
| Dataset Splits | No | The paper does not explicitly mention training, validation, or test dataset splits in the context of machine learning. It describes sampling from defined cooperative games for evaluation, stating "For each game, we compute the exact Shapley value, and then the average absolute errors in the approximated Shapley value for a given budget of marginal-contribution samples across multiple computational runs." There are no specific train/validation/test splits of a pre-existing dataset. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to run the experiments, such as GPU or CPU models. |
| Software Dependencies | No | The paper does not provide specific version numbers for any software dependencies or libraries used in the experiments. |
| Experiment Setup | Yes | Algorithm 1 (Stratified Empirical Bernstein Method) lists required inputs such as "probability p, strata number N, stratum sizes ni, initial sample numbers mi, initial stratum sample variances ˆˆσ2i, weights τi, widths Di, sample budget B". These parameters define the experimental setup for the proposed sampling method. |