Streaming Weak Submodularity: Interpreting Neural Networks on the Fly
This work addresses the need for fast interpretability in machine learning applications, such as explaining neural network predictions, but it is incremental as it builds on existing streaming and submodular optimization ideas.
The paper tackles the problem of explaining black-box classifier predictions by formulating it as a combinatorial maximization problem and proposes an efficient streaming algorithm with a constant factor approximation guarantee for weakly submodular functions under random stream order, achieving explanations 10 times faster than the state-of-the-art LIME framework.
In many machine learning applications, it is important to explain the predictions of a black-box classifier. For example, why does a deep neural network assign an image to a particular class? We cast interpretability of black-box classifiers as a combinatorial maximization problem and propose an efficient streaming algorithm to solve it subject to cardinality constraints. By extending ideas from Badanidiyuru et al. [2014], we provide a constant factor approximation guarantee for our algorithm in the case of random stream order and a weakly submodular objective function. This is the first such theoretical guarantee for this general class of functions, and we also show that no such algorithm exists for a worst case stream order. Our algorithm obtains similar explanations of Inception V3 predictions $10$ times faster than the state-of-the-art LIME framework of Ribeiro et al. [2016].