- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes ShapleyOG, a faster method for adaptive Shapley value estimation. It combines an odd Gaussian process with less frequent hyperparameter fitting, incremental updates, and quadrature computations. The experiments show substantial reductions in computational overhead while generally maintaining estimation accuracy.
Critical strengths
1.The method has clear theoretical support. Under fixed hyperparameters and paired observations, the paper proves equivalence of the Shapley posterior and the information gain criterion between the full and odd GPs. These results provide a sound basis for reducing computation. 2.I found the paper clearly written. The problem is well defined, and the presentation makes it easy to understand the motivation behind each component and how it contributes to the overall method.
Critical weaknesses
1.The practical runtime advantage still needs direct validation. Total runtime is constructed from measured algorithm overhead and an assumed cost per value function evaluation. Experiments with an actual expensive model would help establish whether the gains hold when batching, parallel evaluation, and varying evaluation costs are taken into account. 2.I would like to see a comparison using the same odd GP, initialization, fitting strategy, and evaluation budget, but replacing information gain selection with random paired sampling. This would help separate the accuracy gains from GP modeling and active selection, and clarify when the additional cost of active selection is worthwhile. 3.The evaluation also omits the complementary contribution sampling methods of Zhang et al. (2023)[1]. These methods estimate Shapley values using differences between complementary coalitions, which are directly related to the odd targets used here. Although OddSHAP and other paired methods are included, a comparison with these direct sampling estimators under equal evaluation budgets and total runtime would better establish the additional benefits of GP modeling and information gain selection.
[1] Efficient sampling approaches to shapley value approximation
Questions for authors
please see weaknesses
2 comments
Thank you for your detailed response. It addressed my concerns, and I have increased the score.
We thank the reviewer for the concrete suggestions; all additions are in the revised PDF.
W1 (runtime validation with batched evaluation and varying costs). We agree that this relationship was not made explicit in the paper; the revised PDF now does so and adds a live experiment.
ShapleyOG is exactly equivalent to a batched acquisition approach (Section 3.3): between the refits at 2i and 2i+1, the coalitions selected via EIG form a deterministic sequence that depends only on the previously selected coalitions, not on their observed values. They can thus be evaluated in parallel as one batch, with identical estimates and overhead for the coalition selection. Consequently, for a fixed evaluation time, the total computation time perspective of Figure 2 (left) also covers parallel evaluation with k evaluations at a time, by reading the assumed cost per evaluation as the time of one evaluation round divided by k (Section 4.2, App. E.4), e.g., one minute per round with k=64 corresponds to about 1 s. Since the figure spans three orders of magnitude of this cost, i.e., many combinations of round times and parallelization factors, it already characterizes that, on the considered games and budgets, ShapleyOG is beneficial in batched settings wherever the round time divided by k exceeds a tenth of a second, a regime that is common in ML applications and in particular for the expensive models the reviewer mentions. Deviating settings (random evaluation times, coalition-dependent costs) are discussed in App. E.4.
To further validate this perspective, we ran ShapleyOG in batched mode on a live TabPFN v2 model (details in App. F.8): 10 players, 8 parallel evaluations, measured evaluation costs of 6 to 61 seconds that grow with the coalition size, 10 seeds, against OddSHAP as the strongest competitor. After 32, 64 and 128 evaluations, with measured end-to-end wall-clock times (overhead and evaluations) of 1.9, 3.6 and 7.0 min that differ by at most 0.1 min between the two methods, the geometric mean NMSE of ShapleyOG is 37, 3.9 and 1.8 times lower, and the batched run selects exactly the coalitions of a sequential one. At larger budgets, which on a 10-player game quickly cover a substantial fraction of all coalitions, non-adaptive estimators narrow the gap, as observed for the small games in Section 4.2.
W2 (same odd GP without active selection). We have added an ablation of the adaptive coalition selection to the revised PDF (Section 4.2, App. E.5 and F.6). On the same games, budgets, and seeds as in the main experiment, we benchmark a non-adaptive counterpart of ShapleyOG: the same odd GP and hyperparameter fitting procedure, but based on random, paired coalition sampling (uniform over coalition sizes, the standard and stronger choice, with the border trick of Fumagalli et al. (2023) for sufficiently large budgets).
At equal evaluation budget, the counterpart is outperformed by ShapleyOG (NMSE pooled across games, relative to the counterpart; Table 12):
ShapleyOG thus reduces the NMSE to 56–65%, while the counterpart in turn is more accurate than the best baseline estimator of the main experiment per game by a factor of 1.27 to 1.70 in the geometric mean over games, i.e., the GP surrogate and the adaptive selection contribute comparably to the advantage of ShapleyOG. While the overhead of ShapleyOG is mostly higher than that of its counterpart, ShapleyOG is still more accurate at equal total computation time from 0.1 seconds per evaluation on. For cheaper value functions, the counterpart is itself dominated by OddSHAP except at the smallest total times (Figure 7, right, App. F.6), so that it only pays off in a narrow regime of evaluation costs.
W3 (complementary contribution sampling of Zhang et al., 2023). We have added these estimators to the main experiment (Section 4.2, App. F): we ran all three variants (CC, CCN, CCB) on all games, seeds, and budgets and report the one with the lowest pooled NMSE, CCN (App. F.7). Its NMSE is up to almost three orders of magnitude higher than that of ShapleyOG (NMSE pooled across games by the geometric mean; see also Figure 1, left, and Table 14):
The same holds at equal total runtime (Figure 2, left).
We hope that these additions resolve the three concerns. Given the strengths the reviewer lists, we would be grateful if the reviewer adjusted the overall rating and the soundness score accordingly.