# A Rate-Distortion Framework for Explaining Neural Network Decisions

arXiv: https://arxiv.org/abs/1905.11092 · HTML: https://mlsanity.com/paper/1905.11092/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2019.

## Built on by (most cited first, 24 of 24)

- [ReduNet: A White-box Deep Network from the Principle of Maximizing Rate Reduction](https://mlsanity.com/paper/2105.10446/) (2021)
- [On the Principles of Parsimony and Self-Consistency for the Emergence of Intelligence](https://mlsanity.com/paper/2207.04630/) (2022)
- [This looks more like that: Enhancing Self-Explaining Models by Prototypical Relevance Propagation](https://mlsanity.com/paper/2108.12204/) (2021)
- [ProtoVAE: A Trustworthy Self-Explainable Prototypical Variational Model](https://mlsanity.com/paper/2210.08151/) (2022)
- [Fast Hierarchical Games for Image Explanations](https://mlsanity.com/paper/2104.06164/) (2021)
- [Cartoon Explanations of Image Classifiers](https://mlsanity.com/paper/2110.03485/) (2021)
- [Learning Fair Representations via Rate-Distortion Maximization](https://mlsanity.com/paper/2202.00035/) (2022)
- [A Rate-Distortion Framework for Explaining Black-box Model Decisions](https://mlsanity.com/paper/2110.08252/) (2021)
- [New Definitions and Evaluations for Saliency Methods: Staying Intrinsic, Complete and Sound](https://mlsanity.com/paper/2211.02912/) (2022)
- [Interpretability Guarantees with Merlin-Arthur Classifiers](https://mlsanity.com/paper/2206.00759/) (2022)
- [Explaining Image Classifiers with Multiscale Directional Image Representation](https://mlsanity.com/paper/2211.12857/) (2022)
- [Prototypical Self-Explainable Models Without Re-training](https://mlsanity.com/paper/2312.07822/) (2023)
- [Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings](https://mlsanity.com/paper/2110.08105/) (2021)
- [Training Characteristic Functions with Reinforcement Learning: XAI-methods play Connect Four](https://mlsanity.com/paper/2202.11797/) (2022)
- [A Rigorous Study Of The Deep Taylor Decomposition](https://mlsanity.com/paper/2211.08425/) (2022)
- [I Bet You Did Not Mean That: Testing Semantic Importance via Betting](https://mlsanity.com/paper/2405.19146/) (2024)
- [Sparsest Univariate Learning Models Under Lipschitz Constraint](https://mlsanity.com/paper/2112.13542/) (2021)
- [A Complete Characterisation of ReLU-Invariant Distributions](https://mlsanity.com/paper/2112.06532/) (2021)
- [A classification performance evaluation measure considering data separability](https://mlsanity.com/paper/2211.05433/) (2022)
- [Interpreting Global Perturbation Robustness of Image Models using Axiomatic Spectral Importance Decomposition](https://mlsanity.com/paper/2408.01139/) (2024)
- [On Interpretable Approaches to Cluster, Classify and Represent Multi-Subspace Data via Minimum Lossy Coding Length based on Rate-Distortion Theory](https://mlsanity.com/paper/2302.10383/) (2023)
- [Hardness of Deceptive Certificate Selection](https://mlsanity.com/paper/2306.04505/) (2023)
- [On the Interplay of Subset Selection and Informed Graph Neural Networks](https://mlsanity.com/paper/2306.10066/) (2023)
- [RW-Net: Enhancing Few-Shot Point Cloud Classification with a Wavelet Transform Projection-based Network](https://mlsanity.com/paper/2501.03221/) (2025)

## Abstract (arXiv)

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 mathsfNP^mathsfPP, an important class of computational problems frequently arising in AI tasks. Furthermore, we show that it even remains mathsfNP-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.