Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Value Approximation

The problem of explaining the behavior of Deep Neural Networks has gained a lot of attention over the last years. While several attribution methods have been proposed, most methods are based on heuristics without clear strong theoretical foundations. This raises the question of whether the resulting attributions are reliable. On the other hand, the literature on cooperative game theory suggests Shapley Values as a unique way of assigning relevance scores such that certain desirable properties are satisfied. Previous works on attribution methods also showed that explanations based on Shapley Values better agree with the human intuition. Unfortunately, the exact evaluation of Shapley Values is prohibitively expensive, exponential in the number of input features. In this work, by leveraging recent results on uncertainty propagation, we propose a novel, polynomial-time approximation of Shapley Values in deep neural networks. We show that our method produces significantly better approximations of Shapley Values than existing state-of-the-art attribution methods.