Minimal Explanations for Neural Network Predictions
  Explaining neural network predictions is known to be a challenging problem.
In this paper, we propose a novel approach which can be effectively exploited,
either in isolation or in combination with other methods, to enhance the
interpretability of neural model predictions. For a given input to a trained
neural model, our aim is to compute a smallest set of input features so that
the model prediction changes when these features are disregarded by setting
them to an uninformative baseline value. While computing such minimal
explanations is computationally intractable in general for fully-connected
neural networks, we show that the problem becomes solvable in polynomial time
by a greedy algorithm under mild assumptions on the network's activation
functions. We then show that our tractability result extends seamlessly to more
advanced neural architectures such as convolutional and graph neural networks.
We conduct experiments to showcase the capability of our method for identifying
the input features that are essential to the model's prediction.
