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

Marco Ancona, Cengiz Oztireli, Markus Gross
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:272-281, 2019.

Abstract

The problem of explaining the behavior of deep neural networks has recently gained a lot of attention. While several attribution methods have been proposed, most come without strong theoretical foundations, which raises questions about their reliability. 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. 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-ancona19a, title = {Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Value Approximation}, author = {Ancona, Marco and Oztireli, Cengiz and Gross, Markus}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {272--281}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/ancona19a/ancona19a.pdf}, url = {https://proceedings.mlr.press/v97/ancona19a.html}, abstract = {The problem of explaining the behavior of deep neural networks has recently gained a lot of attention. While several attribution methods have been proposed, most come without strong theoretical foundations, which raises questions about their reliability. 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. 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.} }
Endnote
%0 Conference Paper %T Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Value Approximation %A Marco Ancona %A Cengiz Oztireli %A Markus Gross %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-ancona19a %I PMLR %P 272--281 %U https://proceedings.mlr.press/v97/ancona19a.html %V 97 %X The problem of explaining the behavior of deep neural networks has recently gained a lot of attention. While several attribution methods have been proposed, most come without strong theoretical foundations, which raises questions about their reliability. 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. 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.
APA
Ancona, M., Oztireli, C. & Gross, M.. (2019). Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Value Approximation. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:272-281 Available from https://proceedings.mlr.press/v97/ancona19a.html.

Related Material