A Rate-Distortion Framework for Explaining Neural Network Decisions

Abstract

We formalise the widespread idea of interpreting neural network decisions as an explicit optimisation problem in a rate-distortion framework. A set of input features is deemed relevant for a classification decision if the expected classifier score remains nearly constant when randomising the remaining features. We discuss the computational complexity of finding small sets of relevant features and show that the problem is complete for ${\mathsf{NP}}^{\mathsf{PP}}$, an important class of computational problems frequently arising in AI tasks. Furthermore, we show that it even remains $\mathsf{NP}$-hard to only approximate the optimal solution to within any non-trivial approximation factor. Finally, we consider a continuous problem relaxation and develop a heuristic solution strategy based on assumed density filtering for deep ReLU neural networks. We present numerical experiments for two image classification data sets where we outperform established methods in particular for sparse explanations of neural network decisions.

References in corpus (7)

• Methods for Interpreting and Understanding Deep Neural Networks
• Learning Important Features Through Propagating Activation Differences
• SmoothGrad: removing noise by adding noise
• Tractable Inference for Complex Stochastic Processes
• MAP Complexity Results and Approximation Methods
• iNNvestigate neural networks!
• The Computational Complexity of Understanding Network Decisions

Cited by in corpus (8)

• Explaining Deep Neural Networks and Beyond: A Review of Methods and Applications
• Explainable Machine Learning for Scientific Insights and Discoveries
• Learning Diverse and Discriminative Representations via the Principle of Maximal Coding Rate Reduction
• ReduNet: A White-box Deep Network from the Principle of Maximizing Rate Reduction
• Fast Hierarchical Games for Image Explanations
• In-Distribution Interpretability for Challenging Modalities
• The Computational Complexity of Understanding Network Decisions
• Scaling Symbolic Methods using Gradients for Neural Model Explanation