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.

本文将神经网络决策解释为速率失真框架下的显式优化问题，并探讨了寻找小的相关特征集的计算复杂性，发展了一种基于密度过滤的启发式解决策略，并在两个图像分类数据集上进行了数字实验，特别是在神经网络决策的稀疏解释方面，优于现有方法。

用速率失真框架解释神经网络决策