Building a Bridge Between the Shapley Value, Prime Implicants and Counterfactual Explanations: a Theoretical Analysis

摘要

Since the introduction of SHAP, many methods adapted the idea of using the Shapley value formula as a way to measure the importance of a feature in the decision of a model. However, computing this value theoretically imply to relearn the model with and without the feature for all subsets of features. To avoid this, the methods rely on sampling to compute an expectation to measure a mean impact of a feature. In this paper we investigate theoretically if we could, and under which conditions, build and use a textbook cooperative game with the help of other explanation techniques, Prime Implicants and Counterfactual explanations, for computing Shapley values for interpretability. We propose detailed and iterative analysis of the number of remaining explanations during the enumeration of the explanations, alongside the computation of the Shapley value and its upper and lower bounds.