Streaming Weak Submodularity: Interpreting Neural Networks on the Fly

By Ethan R. Elenberg, A. Dimakis, Moran Feldman, Amin Karbasi. 2017

92 citations recorded by the source corpus.

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].

Subfields: Artificial Intelligence, Safety, Robustness & Interpretability, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Safety, Robustness & Interpretability

In Algorithms & Complexity

Citations in the corpus

The Robust Manifold Defense: Adversarial Training using Generative Models (2017, background): “This relates to interpretability and trust [39, 29, 14] in modern complex models which is an important emerging topic.”
Unsupervised Learning of Neural Networks to Explain Neural Networks (2018, background): “Many studies for network interpretability mainly visualized image appearance corresponding to a neural unit inside a CNN [39, 22, 29, 7, 38, 6] or extracted image regions that were responsible for network output [24, 8, 14, 9, 27, 17].”
Fast Parallel Algorithms for Feature Selection (2019, methodology): “1, we use an example of a weakly submodular function from [12] where adaptive sampling techniques have an arbitrarily poor approximation guarantee.”
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications (2019, methodology): “…submodular optimization techniques have been used in feature selection [Das and Kempe, 2011, Khanna et al., 2017], anytime linear prediction [Hu et al., 2016], interpretation of deep neural networks [Elenberg et al., 2017], and high dimensional sparse regression problems [Elenberg et al., 2018].”
xGEMs: Generating Examplars to Explain Black-Box Models (2018, background): “Most closely related works to our approach are those that provide explanations by sub-selecting meaningful samples and/or semantically relevant features (like super-pixels) that highlight undesirable model behavior [13, 22].”