Streaming Weak Submodularity: Interpreting Neural Networks on the Fly

2017/03/08 by Ethan R. Elenberg, Elenberg, Ethan R., Alexandros G. Dimakis +5 · 1 citation
Computer Science · #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1703.02647

openalex publication_date 2017/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Cited by

• DynaAct: Large Language Model Reasoning with Dynamic Action Spaces

Related

• Fairness in Streaming Submodular Maximization over a Matroid Constraint
• Do Less, Get More: Streaming Submodular Maximization with Subsampling
• Streaming Methods for Restricted Strongly Convex Functions with Applications to Prototype Selection
• Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints
• Submodularity In Machine Learning and Artificial Intelligence