Streaming Weak Submodularity: Interpreting Neural Networks on the Fly
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].
This paper proposes a new approach STREAK for maximizing weakly submodular functions. The idea is to collect several outputs of the Threshold Greedy algorithm, where the selection is based on a given threshold. The theoretical results of the Threshold Greedy algorithm and STREAK are verified sequentially. STREAK is also used to provide interpretable explanations for neural-networks and the empirical studies are given.
This is an interesting work. The streaming algorithm is novel and the analyses are elaborate. The problem constructed to prove the ineffectiveness of randomized streaming algorithms is ingenious. The experiments also show the superiority of STREAK. However, how to choose the proper \epsilon in STEAK? Figure 2(a) shows that by varying \epsilon, the algorithm can achieve a gradual tradeoff between speed and performance, but the result is trivial because with the increase of \epsilon, the time and space complexity will both increase and lead to better performance. 
I have checked all the proofs, and believe that most of them are correct. However, there are also some places which are not clear.
1. In the proof of Lemma A.1, the choice of appropriate arrival order is unclear and how to derive the inequality at the end of the proof?
2. In the proof of Lemma A.9, what is the meaning of the first paragraph? It seems to have nothing to do with the proof in the second paragraph.
3. In the proof of Theorem 5.6, why m=0 implies I=\ emptyset?