NEUROCHAINS: EXTRACT LOCAL REASONING CHAINS OF DEEP NEURAL NETS
Year: 2020

Abstract:
We study how to explain the main steps/chains of inference that a deep neural net (DNN) relies on to produce predictions in a local region of data space. This problem is related to network pruning and interpretable machine learning but the highlighted differences are: (1) fine-tuning of neurons/filters is forbidden: only exact copies are allowed; (2) we target an extremely high pruning rate, e.g., ≥ 95%; (3) the interpretation is for the whole inference process in a local region rather than for individual neurons/filters or on a single sample. In this paper, we introduce an efficient method, NeuroChains, to extract the local inference chains by optimizing a differentiable sparse scoring for the filters and layers to preserve the outputs on given data from a local region. Thereby, NeuroChains can extract an extremely small sub-network composed of filters exactly copied from the original DNN by removing the filters/layers with small scores. We then visualize the sub-network by applying existing interpretation technique to the retained layer/filter/neurons and on any sample from the local region. Its architecture reveals how the inference process stitches and integrates the information layer by layer and filter by filter. We provide detailed and insightful case studies together with three quantitative analyses over thousands of trials to demonstrate the quality, sparsity, fidelity and accuracy of the interpretation within the assigned local regions and over unseen data. In our empirical study, NeuroChains significantly enriches the interpretation and makes the inner mechanism of DNNs more transparent than before.

heading: 1 INTRODUCTION
text: Deep neural networks (DNNs) greatly reshape a variety of tasks — object classification, semantic segmentation, natural language processing, speech recognition, robotics, etc. Despite its success on a vast majority of clean data, DNNs are also well-known to be sensitive to small amounts of adversarial noises. The lack of sufficient interpretability about their success or failure is one major bottleneck of applying DNNs to important areas such as medical diagnosis, public health, transportation systems, financial analysis, etc.
Interpretable machine learning has attracted growing interest in a variety of areas. The forms of interpretation vary across different methods. For example, attribution methods (Bach et al., 2015; Sundararajan et al., 2017; Shrikumar et al., 2017; Montavon et al., 2017; Kindermans et al., 2017; Smilkov et al., 2017) produce the importance score of each input feature to the output prediction for an given sample, while some other methods (Zeiler & Fergus, 2014; Simonyan et al., 2013; Erhan et al., 2009) aim to explain the general functionality of each neuron/filter or an individual layer regardless of the input sample. Another line of works (Ribeiro et al., 2016; Wu et al., 2018; Hou & Zhou, 2018) explain DNNs in a local region of data space by training a shallow (e.g., linear) and easily interpretable model to approximate the original DNN on some locally similar samples. Thereby, they reduces the problem to explaining the shallow model. These methods essentially reveal the neuron to neuron correlations (e.g., input to output, intermediate layer/neuron to output, etc), but they cannot provide an overview of the whole inference process occurring inside the complicated structure of DNNs.
In this paper, we study a more challenging problem: Can we unveil the major hidden steps of inference in DNNs and present them in a succinct and human-readable form? Solving this problem helps to answer many significant questions, e.g., which layer(s)/neuron(s) plays the most/least im-
portant role in the inference process? Do two similar samples really share most inference steps? Do all samples need the same number of neurons/layers to locate the key information leading to their correct predictions? How/when/where does a failure happen during the inference on a DNN? Which neuron(s)/layer(s)/feature(s) are shared by different samples from the same region even when their labels differ? Are DNNs using entirely different parts for data from different local regions? Some of them are related to other problems such as network pruning (Han et al., 2015; Li et al., 2016) and neural architecture search (NAS) (Zoph & Le, 2017). For example, are winning tickets (Frankle & Carbin, 2018; Liu et al., 2018) universal over different local regions and classes? Does the weight sharing scheme in recent NAS methods (Pham et al., 2018; Liu et al., 2019; Ying et al., 2019) limit the searching space or quality?
We develop an efficient tool called NeuroChains to extract the underlying inference chains of a DNN for a given local data region. Specifically, we aim to extract a much smaller sub-network composed of a subset of neurons/filters exactly copied from the original DNN and whose output for data from the local region stays consistent with that of the original DNN. In experiments, we assume the data from the same classes reside in a local region. While the selected filters explain the key information captured by the original DNN when applied to data from the local region, the architecture of the sub-network stitches these information sequentially, i.e., step by step and layer by layer, and thus recover the major steps of inference that lead to the final outputs. Despite its combinatorial nature, we parameterize the sub-network as the original DNN with an additional score multiplied to each filter/layer’s output featuremap. Thereby, we formulate the above problem of sub-network extraction as optimizing a differentiable sparse scoring of all the filters and layers in order to preserve the outputs on all given samples.
The above problem can be solved by an efficient back-propagation that only updates the scores with fixed filter parameters. The objective is built upon the Kullback–Leibler (KL) divergence between the sub-network’s output distribution and that of the original DNN, along with an `1 regularization for sparse scores over filters. We further use a sigmoid gate per layer to choose whether removing the entire layer. The gate plays an important role in reducing the sub-network size since most local regions do not rely on all the layers. In practice, we further apply a thresholding to the sparse scores to obtain an even smaller sub-network and employ an additional fine-tuning to the filter scores on the sub-network. We illustrate the subnetwork’s architecture and visualize its filters and intermediate-layers’ featuremaps by exist-
ing methods (Mundhenk et al., 2019; Erhan et al., 2009).
NeuroChains is a novel pruning technique specifically designed for interpreting the local inference chains of DNNs. As aforementioned, it potentially provides an efficient tool to study other problems in related tasks. However, it has several fundamental differences to network pruning and exist-
ing interpretation tasks, which deter methods developed for these two problems from addressing our problem. Comparing to network pruning: (1) fine-tuning is not allowed in NeuroChains; (2) it targets a much larger pruning rate for succinct visualization, e.g., ≥ 95% for VGG-19 and ≥ 99% for ResNet-50 on ImageNet with ≤ 200 filters remained; (3) it is for data from a local region instead of the whole data distribution. Comparing to mainstream interpretation tasks: (1) NeuroChains produces an interpretation of the entire inference process in a local region (which may contain different classes) rather than of one neuron/filter or output on/around a single sample; (2) the sub-network’s architecture provides orthogonal information to the importance of individual neurons/filters.

heading: 2 RELATED WORKS
text: Interpretable machine learning methods can be mainly categorized into the ones aiming to evaluate the importance of each input feature of a single sample and the ones explaining individual neurons/filters. Approaches in the first category usually rely on certain back-propagation from the DNN’s output to derive an importance score for each input feature or hidden node. Earlier works are based on the back-propagated gradients, e.g., deconvolution (Zeiler & Fergus, 2014), backpropagation (Simonyan et al., 2013) and guided back-propagation (Springenberg et al., 2014). Sundararajan et al. (2017) proposed to (approximately) calculate the integral of the gradients along a path between a baseline point and the input sample, which ensures the sensitivity and implementation invariance lacking in some previous methods. More recent methods propose novel backpropagation rules to directly derive the attribution scores of neurons from output to input, e.g., DeepLIFT (Shrikumar et al., 2017), deep Taylor decomposition (Montavon et al., 2017), and layerwise relevance propagation (LRP) (Bach et al., 2015).
Methods in the second class treat DNNs as black boxes and seek a simple model to explain how the DNN’s output changes in a local region. For example, they add perturbations to different parts of the input to evaluate how the perturbations change the output (Ancona et al., 2017), which reflect the importance of different parts. Zeiler & Fergus (2014) covered different parts of the input image with a gray square, which led to different prediction probabilities on the true class. Instead, Zintgraf et al. (2017) replaced each patch in the input image with the surrounding patch and tracked the induced changes in the output. In LIME (Ribeiro et al., 2016), Ribeiro et al. trained a sparse linear model on noisy input-output pairs as a local surrogate approximating the original DNNs, where the sparse weights are used to explain the importance of input features. As mentioned before, our main difference to the above methods are we explain DNNs for a local region of multiple samples and we further explain how DNNs step by step integrate the information of important filters/neurons.
Network pruning (Han et al., 2015; Li et al., 2016) remove redundant neurons/nodes or connections/weights from a pre-trained DNN and fine-tune the sub-network. Structural pruning removes whole layers/channels/filters/neurons according to a certain norm of the associated weights (Li et al., 2016) or sparsity (Hu et al., 2016). In contrast, Frankle & Carbin (2018); Liu et al. (2018) prune a DNN during its training. Luo et al. (2017) apply pruning to two adjacent convolution layers at each time to take the dependency between the two layers into account. Several recent works empirically verify “lottery ticket hypothesis”, i.e., there exists sub-networks (i.e., winning tickets) that can reach comparable generalization performance as the original DNN if re-trained. In contrast, the sub-network extracted by NeuroChains cannot be fully re-trained since it has to preserve the original DNN’s filters, and our goal is to retain the generalization performance only for a local region.

heading: 3 NEUROCHAINS

heading: 3.1 PROBLEM: EXTRACT LOCAL INFERENCE CHAINS AS SUB-NETWORKS
text: Although the DNNs widely used nowadays are usually composed of hundreds of layers and millions to billions of hidden nodes. When applied to samples from a local region in data space, it is plausible that its inference process mainly relies on a small subset of layers/neurons/filters. In this paper, we verify this conjecture by developing an efficient and practical algorithm, i.e., NeuroChains, to extract the subset and its underlying architecture as a sub-network whose weights/filters are selected and exactly copied from the original DNN while its outputs in a given local region retain the ones
produced by the original DNN. Although DNNs are usually non-smooth in definition if using a nonsmooth piece-wise activation such as ReLU, when trained with the commonly used techniques, e.g., data augmentation, mix-up, dropout, the resulted DNNs are relatively smooth in a sufficiently small local region.
In order to preserve the original inference chains, we do not allow any fine-tuning or re-training on any filter or the the weight vector corresponding to any neuron: they can only be exactly copied from the original DNN. Let F (·; {W `}`=1:L) (a mapping from input to output) denote the original DNN, W ` represents the set of filters/weight vectors in layer-`, and W `[i] represents the ith filter/weight vector in layer-`. Any sub-network fulfilling our above requirement can be defined and parameterized by an indicator vector M ` per layer, whose each entry is a {0, 1} value indicating whether retaining the associated filter/neuron in W `. We further define operator ◦ as
(W ` ◦M `)[i] , { W `[i], M `[i] = 1; 0, M `[i] = 0.
(1)
Thereby, {M `}`=1:L defines a qualified sub-network for inference chain and its weights are {W ` ◦ M `}`=1:L, where we extend the operator ◦ to make W ◦M = {W ` ◦M `}`=1:L given the original DNN’s weights W = {W `}`=1:L. Given a set of samples X drawn from a local region of data space, we can formulate the problem of finding an inference chain as the following combinatorial optimization, which aims to find the most sparse indicator M (i.e., the sub-network with the fewest filters retained) that does not change the outputs of the original DNN for ∀x ∈ X , i.e.,
min {M`}`=1:L L∑ `=1 ‖M `‖1 s.t. F (x;W ) = F (x;W ◦M), ∀x ∈ X . (2)
However, directly solving this combinatorial optimization is impractical since the possible choices forM ` is of exponential number. In this paper, we relax the 0-1 indicator vectorM ` to a real-valued score vector S` of the same size. We define an operator applied to W ` and its associated scores S` as (W ` S`)[i] , S`[i] ·W `[i]. (3) Note we do not limit entries in S` within [0, 1] due to the possible redundancy among filters in the original DNN, i.e., there might be filters of similar functionality for the given samples and a preferred pruning should be able to only preserve one of them and multiply it by the number of those redundant filters in the sub-network. In addition, less constrains are easier to handle in optimization and helpful to find sub-network whose outputs are closer to that of the original DNN, since the class of sub-networks with parameters W S includes all the sub-networks with parameters W ◦M . Hence, we relax the challenging combinatorial optimization to the following unconstrained continuous optimization, i.e.,
min {S`}`=1:L
1 |X | ∑ x∈X l(F (x;W ), F (x;W S)) + λ L∑ `=1 ‖S`‖1, (4)
where l(·, ·) is a loss function aiming to minimize the distance between the original DNN’s output F (x;W ) and the sub-network’s output F (x;W S). In our experiments, for classification, we use KL-divergence between the output distributions over classes, where the two output distributions are computed by applying softmax to F (x;W ) and F (x;W S) respectively, i.e.,
l(F (x;W ), F (x;W S)) = DKL(softmax(F (x;W ))||softmax(F (x;W S))). (5) In addition, empirical evidences (Krueger et al., 2017; Singh et al., 2016) show that for most samples there exist some layers that can be entirely removed without changing the final prediction. Hence, only a few hard and confusing samples need more delicate features, while most other samples can be correctly classified based on simple patterns from shallower layers. Therefore, in NeuroChains, we apply a sigmoid function with input score α` as a gate G` determining whether removing the entire layer-` during pruning, i.e.,
G` = 1/ [ 1 + exp(−α`/T ) ], (6)
where T is a temperature parameter. With a gate G` applied after each layer-` whose input and output has the same size (which is common in many DNNs), we can recursively define the input
H`+1(·) to the next layer-(`+ 1), i.e., H`+1(x; {W `′ S`′ , α`′}`′=1:`) ={ G` · F `(H`;W ` S`) + (1−G`) ·H`(x; {W `′ S`′ , α`′}`′=1:`−1), if input size = output size F `(H`;W ` S`) otherwise
(7) where F `(H`;W ` S`) denotes the output of layer-`. The reason to use a gate here is that we expect to either remove the whole layer or retain it without adding an extra shortcut (which will change the original DNN’s architecture). We apply a T < 1 to sharpen the gate values. Since we prefer to remove non-informative layers, in the objective, we add another regularization α` to encourage the removal of entire layers (because decreasing α reduces G` and thus increase the chance of layer removal). Therefore, the final optimization for NeuroChains is
min {S`,α`}`=1:L
1 |X | ∑ x∈X l(F (x;W ), HL+1(x; {W ` ′ S` ′ , α` ′ }`′=1:L))+λ L∑ `=1 ‖S`‖1+λg L∑ `=1 α`, (8)
Our objective above is similar to the one used in Network Slimming (Liu et al., 2017) but we optimize it for a local region (so we can consider to remove layers) and we do not allow fine tuning on weights W .
3.2 ALGORITHM
Our algorithm is simply a standard back-propagation for the optimization problem in Eq. (8), which produces sparse scores for filters and gate values for layers. Note the weights in W are fixed and the backpropagation only updates S. We initialize the filter scores S = 1 so
W S = W at the beginning of optimization. We initialize the gate score α` = 0 for all ` = 1 : L so G` = 0.5 at the beginning, i.e., the probabilities to remove or to retain a layer is equal. For classification, we set loss l(·, ·) to be the KL-divergence between the output distributions of the original DNN and the sub-network. After convergence of the optimization, we then apply a simple thresholding to these scores to further remove more filters and layers: (1) we remove the filters with score under a threshold τ ; (2) we remove layer-` if G` < 0.5. This yields a sufficiently small sub-network architecture but the scores might be sub-optimal in preserving the original DNN’s outputs within the local region. Therefore, we further fine-tune the nonzero scores in S (note filters are always fixed), i.e, the scores for the retained filters/layers, by minimizing Eq. (8) without the two regularizations, if the first term in Eq. (8) exceeds a threshold t. Given a sub-network produced by NeuroChains, we then visualize its architecture and scores as the structure of the inference chains. Moreover, we visualize the retained filters and layers on the chains by their activation patterns and featuremaps, respectively, using existing interpretation methods (Mundhenk et al., 2019; Erhan et al., 2009).

heading: 4 EXPERIMENTS
text: In experiments, we apply NeuroChains to extract the inference chains of two widely-adopted CNNs pre-trained on ImageNet, i.e., VGG-19 and ResNet-50. We provide the basic information of the two DNNs in Table 1. In the following, We will present three quantitative analyses over hundreds of case studies, which show that (1) NeuroChains is capable to produce sub-networks retaining only < 5% of filters and meanwhile preserve the outputs of the original DNN in most cases; (2) every filter selected by NeuroChains is important to preserving the outputs since removing one will leads to considerable drop in performance; (3) the sub-network extracted based on a finite number of samples can be generalized to unseen samples in nearby regions. To demonstrate the effectiveness of NeuroChains in local regions in the non-smooth raw-input space, we evaluate the sub-network on the adversarial examples of each sample. We also study the firing behaviour of filters in the original network and the sub-network. We will then provide several detailed and insightful case studies and visualizations of extracted sub-networks for different local regions.
4.1 IMPLEMENTATION DETAILS
We implement NeuroChains by PyTorch (Paszke et al., 2017). In every case study, we firstly randomly sample 2 classes and then randomly sample 10 images from each class’s images that the original DNN has high confidence, e.g., ≥ 95%. Note high confidence does not guarantee the correctness since it can be associated with a wrong class. We choose images with high confidence since the inference on them mostly represent the original DNN’s inference chains in the region. We apply inference on those 20 images and their outputs are used in solving the optimization of Eq (8) in order to extract the local inference chain in the form of a sub-network. For models with shortcuts, e.g., ResNet-50, the sigmoid gate is applied to prune a bottleneck block rather than a layer. A layer inside a block will be removed if the scores of all filters in the layer are nearly 0.
We use Adam optimizer for both the optimization of Eq (8) and fine-tune phases for fil-
ter/layer scores. We use a fixed learning rate 0.005 in the former and 0.01 in the latter. We set temperature T = 0.2 in the sigmoid gate (Eq. (6)) to encourage the gate valueG` close to either 0 or 1, and the threshold τ to goal scores is set to 0.1 so that the outputs of sub-networks are as consistent as possible. We only tried a limited number of choices on tens of experiments, and chose the best combination balancing the fidelity and sub-network size, and then applied it to all other experiments without further tuning. In particular, we tried τ ∈ {0.01, 0.1, 0.5}, λ ∈ {0.001, 0.005, 0.01, 0.1}, and λg ∈ {1, 2, 5}. For different models, the weights of two penalties in Eq. (8) are different. For VGG-19, we use λ = 0.007 and λg = 2. While we choose λ = 0.0065 and λg = 0.9 for ResNet-50.
This choice performs consistently well and robust on all other experiments. We fine-tune S in the pruned network if the KL-divergence after training is greater than threshold t = 0.1. The iteration steps of training and fine-tune is 300 and 50 respectively. We stop training or fine-tuning when the loss difference is less than 0.02. It costs only ∼ 90s for VGG-19 and ∼ 55s for ResNet50 to extract a sub-network on a single GPU since we only optimize a few number of scores.

heading: 4.2 QUANTITATIVE ANALYSES
text: In Melis & Jaakkola (2018), they propose three criteria to evaluate the interpretation methods for DNNs, i.e., faithfulness, stability and explicitness. In this paper, we extend some of their notations and present three quantitative analyses of NeuroChains over 1500 case studies for different local regions, i.e., (1) Fidelity: does the sub-network preserve the original DNN’s outputs on the given samples? how does it change for sub-networks of different sizes? (2) Faithfulness: how much degeneration on the fidelity will be caused if removing one filter from the sub-network? (3) Stability: what is the fidelity (the accuracy of preserving the original DNN’s prediction) of the sub-network on unseen test images from nearby regions? In this paper, we evaluate the fidelity and faithfulness by the decreasing amount of probability on the original DNN’s predicted class when using the subnetwork for inference; we evaluate the stability by evaluating the test fidelity of the sub-network over an image’s K-nearest neighbor images from an validation set (details below Figure 14). All the above metrics are averaged over 1500 sub-networks and across all the images used to extract each sub-network.
The left plot of Figure 2 shows the fidelity for sub-networks of different sizes (measured by the number of filters) that are extracted by NeuroChains. Note most sub-networks only retain ≤ 1% of ResNet-50 for succinct visualization but they preserve the outputs of ResNet-50 with high fidelity.
The right plot in Figure 2 reports the faithfulness of extracted sub-networks, i.e., how a subnetwork’s performance in preserving the original DNN’s output degrade if removing one filter from it, and what is the relationship between this degeneration and the score of the removed filter. The
statistics on 1500 sub-networks in Figure 2(right) show that removing even only one filter from the sub-network can significantly degrade the explanation performance. Hence, NeuroChains usually find the smallest sub-networks without redundancy among retained filters/layers, i.e., every critical inference step is retained. Moreover, the degeneration and the score are strongly and positively correlated, indicating that our optimized scores faithfully reflect the importance of filters in explaining the original DNN. We also present another faithfulness study based on a quotient metric defined below. Let p, q ∈ ∆c (∆c is the probability simplex for c classes) be the output probability vectors of the original neural net and the extracted sub-network respectively for a same input. We define a quotient metric to measure the change of class prediction between p and q, i.e.,
Q(p, q) = q[y]−maxz∈[c],z 6=y q[z] p[y]−maxz∈[c],z 6=y p[z] , y ∈ arg max z∈[c] p[z], (9)
where y is the predicted class by the original neural net, andQ(p, q) is the quotient of two probability differences computed respectively on the original neural net and the sub-network. In particular, it computes the difference of probabilities for class y and the highest-rated other class. The sign of Q(p, q) indicates whether the predicted class changes (e.g., it changes if Q(p, q) < 0) while the magnitude of Q(p, q) measures the change in prediction confidence. The result is given in Figure 8 of Appendix.
We report the average stability of 1500 sub-networks extracted by NeuroChains in Figure 14 of Appendix. It shows that each sub-network can still achieve a high fidelity (the accuracy of preserving the original DNN’s output) within a relatively large local region (e.g., 100 unseen samples) around the 20 samples used to extract the sub-network. It therefore indicates that the inference chains extracted for a finite number of samples by NeuroChains can be applied and generalized to other unseen samples from the same region or even the nearby regions. So NeuroChains is an effective solution to the problem raised in the introduction.
In order to evaluate NeuroChains on the local regions in the raw input space, we extract sub-networks for uniformly random drawn samples and then evaluate the sub-networks on these samples’ adversarial examples generated by two types of attacks: fast gradient sign method (FGSM) and projected gradient descent (PGD). Figure 5 compares the robustness of the original neural net (LEFT plot) and the extracted sub-networks (RIGHT plot) under different attacks: each of the plots show the histogram of the output probability for the ground-truth class on those samples (original and adversarial). The left plot shows that the two types of adversarial attack are very effective on the original neural net in reducing the probability of ground truth class. In contrast, the right plot shows that the NeuroChains extracted sub-networks are much more robust to the attacks, because the optimization in NeuroChains not only removes the irrelevant filters but also strengthens the important filters by assigning them weights > 1. This demonstrates the effectiveness of NeuroChains when applied to local regions in the non-smooth raw-input space, and the extracted sub-networks in this case significantly improves the robustness of the original model in defending adversarial attacks.
Figure 6. It shows that each featuremap of the original network’s filter only represents one part of the object, while the featuremap of the preserved filter in the sub-network combines all the parts to form a complete representation of the object in the image. More complete quantitative analyses for both VGG-19 and ResNet-50 can be found in the Appendix.
We present three case studies of the sub-networks extracted by NeuroChains . For Figure 1 and Figure 4, the data points are from classes which are easy to tell apart while in Figure 7 images are always mis-classified. More case studies are given in Appendix. The visualization in each case study is composed of five parts: (1) the sub-network’s architecture and filter scores; (2) the 20 images from 2 classes used to extract the sub-network. The sub-network is supposed to explain the inference chains on images from the same local region of those 20 images; (3) one image from each class and the visualization of the image’s per-layer featuremaps in the sub-network, which is produced by SMOE (Mundhenk et al., 2019); (4) for comparison, we also present the interpretations produced by two recent works (Wang et al., 2019; Nam et al., 2019) on the two images; (5) visualization of each filter retained in the sub-network using Erhan et al. (2009) after zoomed-in. In the caption below each case study, we highlight some filters/featuremaps and their related class. We also provide examples of inference chains composed of filters stitched by the sub-network’s architecture. They show that NeuroChains considerably enrich the explanation details of DNN’s inference process in a local data region. By connecting the important filters from different layers, the extracted subnetwork highlights the main steps leading to the output prediction.

heading: 5 APPENDIX

heading: 5.1 QUANTITATIVE ANALYSIS
text: We performed 783 experiments each using 20 samples uniformly drawn from two classes (not only the high-confidence samples) and achieved 783 new sub-networks by NeuroChains on VGG-19. We evaluated these newly generated sub-networks using the quotient metric “A quotient of ”diff to highest scoring other class (extracted)” / ”diff to highest scoring other class (original)” Eq. (9). We visualized the result in Figure 8: The left plot is the histogram of the quotient computed over all the 783×20 samples. The histogram shows that most samples keep the original predicted label after pruning, i.e., NeuroChains can preserve the original DNN’s outputs in most cases. Moreover, the number of filters preserved in these sub-networks is 157(mean) ± 43(std), which is small enough to explain. The right plot reports the Faithfulness of NeuroChains in terms of the quotient’s sign. We remove each filter from each sub-network and report how many samples’ predicted labels are changed after the removal, i.e., the quotient is negative. Each point in the scatter plot corresponds to a sub-network, the x-axis is the score of the removed filter given by NeuroChains, and the y-axis is the proportion of samples with negative quotients. The plot shows a strong linear correlation between the score of the removed filter and the degradation of faithfulness. Since removing filters with high scores results in more samples with predicted class changing after pruning, the score given by NeuroChains measures the importance of filters in DNN inference.
We evaluate the stability of NeuroChains using the nearest neighbours from the penultimate-layer representation space. Because ReLU pattern does not provide an ideal metric to measure the distance of samples, even in the raw input space: (1) the number of ReLU linearity zones grows exponentially with the number of hidden nodes. Most ReLU linearity zones are empty and do not contain any real sample; (2) For the few ReLU linearity zones that do contain samples, each only contains one sample and by large chance its neighboring linearity zones are empty, and this is true for most practical cases as empirical studies suggested. So it is almost impossible to find two samples sharing the same ReLU linearity zone or even close in their ReLU patterns of the first layer; (3) For two ReLU linearity zones that are only different in one facet of their polyhedra (i.e., only one digit of their ReLU patterns flips), their corresponding linear models can still be very different (the linear model is an extreme case of sub-network). Therefore, we speculate that samples close to each other in terms of their ReLU patterns do not share a sufficiently small sub-network preserving their original predictions.
That being said, we evaluated each NeuroChains extracted sub-network of VGG-19 using 20 samples randomly drawn from two classes on the K-th nearest neighbour (NN) of each sample by sorting the Hamming distance on their ReLU patterns. The K-NN samples’ prediction cannot be well pre-
served on the sub-networks, because the nearest neighbors in terms of ReLU patterns have very different semantic concepts or classes from the samples that the sub-networks are extracted for. Hence, the local region of ReLU patterns is not a local region on the smooth data manifold. To see this, in Figure 9, for each sample, we computed its L2 distance to the ReLU pattern K-NN sample’s penultimate-layer representation for K = 1, 2, · · · , 10 (the red curve reports mean±std), and we compared them with the L2 distance to the K-NN in the penultimate-layer representation space (the blue curve reports mean±std). It shows that the ReLU pattern K-NN has a much larger L2 distance in the semantic space (i.e., penultimate-layer representation), so it is very different in concepts to the original sample. Moreover, we show some examples of the ReLU pattern K-NN images and the penultimate-layer K-NN images for the sample in Figure 10, which show that ReLU pattern K-NN images are much less related to the original sample.
In Figure 11, we show two case studies of comparing SMOE generated heatmaps for the original network and the NeuroChains extracted sub-network. We can see that the patterns extracted by the two networks are consistent and are all critical patterns for the class, e.g., the eyes and fists of kangaroos and the feet and face of the horse. However, compared with the original network, these patterns are strengthened in much shallower layers of the sub-network, producing better interpretations. This observation is also consistent with the result of analysis on adversarial attacks in Figure 5.
In Figure 12, we compare the capability of preserving the original neural network’s outputs between NeuroChains and magnitude-based pruning (removing the filters whose output featuremaps’ average magnitude (L2 norm) over all considered samples is small). In particular, under the same setting of each experiment in the paper, we prune the original VGG-19 and retain the filters with the largest featuremap magnitude in each layer, 180 in total (more than 157(mean) ± 43(std) filters for subnetworks extracted by NeuroChains), and we then fine-tune the filters’ scores/weights as we did for NeuroChains. Figure 12 shows the histogram of the KL divergence between the original output class distribution and the one produced by the sub-networks. For sub-networks generated by NeuroChain, the KL-divergence in most cases stays close to 0, while the output preserving capability of simple pruning is much worse.

heading: 5.2 MORE DETAILS ABOUT CASE STUDIES
text: On the sub-network’s architecture, we use “L0” to denote the corresponding convolution layer in VGG-19 and “L0 1” to denote the first filter from this layer. For ResNet-50, we further use “L1B1” to denote the first sub-block in the first bottleneck block, “SC” for the shortcut connection and “C1” for the first convolution layer in the sub-block. The redder the node in the sub-network, the larger the scaling score, conversely, the bluer the node, the lower the score. More case studies can be found in the Appendix. In SMOE, Mundhenk et al. propose to measure information at the end of every feature scale and then combined them into a saliency map. We apply this technique to each layer of the sub-network since each layer may prefer different features. In each of our case study, a featuremap-overlaid input image is shown for each layer and for the whole sub-network which is marked as ”Combine All”. The visualization of each selected filter is achieved by maximizing its activation w.r.t. the input. Afterward, we shows the patterns that the filter aims to detect which is independent of the input image.
5.3 CASE STUDIES

heading: L0 L10 L19 L23L21 L32 L34 Combine ALLL5Input image
text: L1B1 Combine ALLInput image Conv1 L2B1 L4B3L3B1 L4B1 L4B2
L4B3C3_1726
L4B3C2_487
L4B3C2_467
L4B2SC_570
L4B2SC_1747
L4B2SC_1796
L4B1C2_232
L4B1C2_323
L4B1C1_278L3B1C2_165
L3B1C3_488
L3B1C3_774
L2B1SC_145
L2B1SC_185
L2B1SC_396
L1B1C1_34
L1B1C2_6
L1B1C3_160
Conv1_0
Conv1_36
Conv1_45
ScoreCam[36] RAP[37]
Baselines
Figure 20: Inference chain by NeuroChains for ResNet-50 when applied to images of “chain” and ”volcano”. Top: The sub-network retains only 18/67 layers and 114/26560 filters. Middle: In the SMOE featuremaps, not only the main body of the volcano, but the crater is also highlighted as key features to identify volcanos. Bottom: In the first several layers, L3B1C2 165, L3B1C3 774 and L3B1C3 488 extract basic patterns such as curved steel bars and the arc of mountains, whilst deeper layers focus on more global patterns such as different orientations of the folded strata (L4B1C1 278 and L4B2SC 570) and chains (L4B2SC 1796 and L4B3C2 467). L4B3C2 487 captures the features when lava erupts from volcanos as in the penultimate image. It reveals an inference chain for volcano: L2B1SC 145 → L3B1C3 488 → L4B1C1 278 → L4B2SC 570 → L4B3C2 487.

Review summaries:
The paper proposes a method called NeuroChains for extracting a sub-network from a deep neural network (DNN) that can accurately match the outputs of the full network for inputs in a small region of the input space. The goal is to be able to explain the important steps that a DNN takes to get from inputs in a small region of the input space, to its predictions for those inputs. NeuroChains initialises the sub-network as the original DNN except each weight/filter is multiplied with a real-valued score. The L1 norm of these scores is minimised while penalising any deviation of the output of the sub-network from the output of the original network. After the minimisation, weights/filters with a score below some threshold value are removed, leaving a sub-network. In the paper there are experiments that aim to verify three claims: (1) NeuroChains can find sub-networks containing less than 5% of the filters in a deep convolutional neural network while preserving its outputs in some small region of the input space; (2) every filter selected by NeuroChains is important for preserving the outputs and removing one of them leads to considerable drop in performance; (3) the sub-networks extracted for small regions of the input space can be generalized to unseen samples in nearby regions.

The submission considers the task of extracting a small sub-network of a pre-trained neural network that can explain a local region of the data space (a small number of the same classes). The resulting sub-network can be interpreted as the inference path moving from the input to the prediction and the filters and associated weights along this path can be visualised. The key of the proposed approach is to apply a multiplicative weight to each filter and layer in the network and enforce these weights to be sparse. The subnetwork is then selected by thresholding the weights. Some quantitative and qualitative analyses were provided.