SHAP@k:Efficient and Probably Approximately Correct (PAC) Identification
  of Top-k Features
Sanjay Kariyappa Leonidas Tsepenekas Freddy Lécué Daniele Magazzeni
The SHAP framework provides a principled method to explain the predictions of
a model by computing feature importance. Motivated by applications in finance,
we introduce the Top-k Identification Problem (TkIP), where the objective is to
identify the k features with the highest SHAP values. While any method to
compute SHAP values with uncertainty estimates (such as KernelSHAP and
SamplingSHAP) can be trivially adapted to solve TkIP, doing so is highly sample
inefficient. The goal of our work is to improve the sample efficiency of
existing methods in the context of solving TkIP. Our key insight is that TkIP
can be framed as an Explore-m problem--a well-studied problem related to
multi-armed bandits (MAB). This connection enables us to improve sample
efficiency by leveraging two techniques from the MAB literature: (1) a better
stopping-condition (to stop sampling) that identifies when PAC (Probably
Approximately Correct) guarantees have been met and (2) a greedy sampling
scheme that judiciously allocates samples between different features. By
adopting these methods we develop KernelSHAP@k and SamplingSHAP@k to
efficiently solve TkIP, offering an average improvement of $5\times$ in
sample-efficiency and runtime across most common credit related datasets.