Shapley Values: Paired-Sampling Approximations
This work provides incremental improvements to Shapley value approximations, benefiting researchers and practitioners in explainable AI by enhancing computational efficiency and theoretical guarantees.
The paper tackles the computational bottleneck of approximating Shapley values for explaining machine learning predictions by analyzing paired-sampling methods, showing they achieve exact results for interactions up to order two and that PermutationSHAP recovers additive properties while KernelSHAP does not.
Originally introduced in cooperative game theory, Shapley values have become a very popular tool to explain machine learning predictions. Based on Shapley's fairness axioms, every input (feature component) gets a credit how it contributes to an output (prediction). These credits are then used to explain the prediction. The only limitation in computing the Shapley values (credits) for many different predictions is of computational nature. There are two popular sampling approximations, sampling KernelSHAP and sampling PermutationSHAP. Our first novel contributions are asymptotic normality results for these sampling approximations. Next, we show that the paired-sampling approaches provide exact results in case of interactions being of maximal order two. Furthermore, the paired-sampling PermutationSHAP possesses the additive recovery property, whereas its kernel counterpart does not.