DropNet: Reducing Neural Network Complexity via Iterative Pruning

The surprising effectiveness of neural networks in domains such as image recognition in ImageNet (Russakovsky et al., 2015) has inspired much recent research. Current state-of-the-art deep models include Transformers (Vaswani et al., 2017) for language modelling, InceptionNet (Szegedy et al., 2015) for image modelling, and ResNets (He et al., 2016) which include over 100 layers. In fact, the number of configurable parameters per model has risen significantly from hundreds to tens of millions. The increased computational complexity required for modern neural networks has made deployment in edge devices challenging.

Previous Work on Complexity Reduction: Current methods of reducing complexity include quantization to 16-bit (Gupta et al., 2015), group L1 or L2 regularization (Alemu et al., 2019), node pruning (Castellano et al., 1997; Zhang & Qiao, 2010; Alvarez & Salzmann, 2016; Wen et al., 2016), filter pruning for CNNs (Li et al., 2016; Wen et al., 2016; Alvarez & Salzmann, 2016; He et al., 2017; Liu et al., 2017), weight pruning using magnitude-based methods (Han et al., 2015) or second-order Hessian-based methods such as Optimal Brain Damage (LeCun et al., 1990) or Optimal Brain Surgeon (Hassibi et al., 1993).

Previous Work on Node/Filter Pruning: For node pruning, previous work includes introducing regularization terms based on input weights using group lasso to the loss function (Alvarez & Salzmann, 2016; Wen et al., 2016) and selecting the least important node to drop based on mutual information (Zhang & Qiao, 2010). In CNNs, previous work includes layer-wise pruning such as layer-wise lasso regression on filters (He et al., 2017), and global pruning methods such as pruning filters with the lowest sum of absolute input weights globally (Li et al., 2016), using second-order Taylor expansion to prune unimportant filters (Molchanov et al., 2016; Lin et al., 2018), introducing structured sparsity using a particle filter approach (Anwar et al., 2017), or to repeatedly perform an L1 regularization of the batch normalization layer’s scaling factor in CNNs (Liu et al., 2017).

Previous Work on Iterative Pruning: Most techniques that can perform one-shot pruning can also be applied recursively using iterative pruning. It has been shown that iterative pruning achieves better performance than one-shot pruning (Li et al., 2016). More notably, iterative pruning with reinitialization can reduce parameter counts by over 90% (Frankle & Carbin, 2018). Such iterative pruning methods shed new insight into how more effective pruning approaches might be developed.

Comparison with Similar Work: DropNet iteratively removes nodes/filters with the lowest average post-activation values across all training samples. Similar work to ours includes removing nodes with the highest average percentage of zero activation values across a validation set - Average Percentage of Zeros (APoZ) (Hu et al., 2016), which measures sparsity of a node’s activations. In contrast, DropNet (i) utilizes average magnitude of post-activation values, and (ii) does so over the training set. Another similar metric is to prune channels to a filter using variance of post-activation values (Polyak & Wolf, 2015). DropNet instead prunes the entire filter using average post-activation values.

Comparison with Dropout: Dropout (Srivastava et al., 2014) randomly drops a fraction $p$ of nodes during training, but keeps the entire network intact during test time. DropNet, however, drops nodes/filters permanently during training time and test time.

Our Contributions:

• •

  We propose DropNet, an iterative node/filter pruning approach with reinitialization, which iteratively removes nodes/filters with the lowest average post-activation value across all training samples (either layer-wise or globally) and, hence, reduces network complexity. To the best of our knowledge, our method is the first to prune both MLPs and CNNs based on the average post-activation values of nodes/filters, which utilizes both the information about the input weights as well as the input data to make an informed selection of the nodes/filters to drop.

• •

  DropNet achieves a robust performance across a wide range of scenarios compared to several benchmark metrics. DropNet achieves similar performance to an oracle which greedily removes nodes/filters one at a time to minimise training loss.

• •

  DropNet does not require special initialization of weights and biases (unlike (Frankle & Carbin, 2018)). It is shown in subsequent experiments that a random initialization of the pruned model will do just as well as original initialization. This means the architecture pruned by DropNet can be readily deployed using off-the-shelf machine learning libraries and hardware.

In this section, we describe the DropNet algorithm and discuss its properties.

Similar to the Lottery Ticket Hypothesis (Frankle & Carbin, 2018), which iteratively drops weights with reinitialization, DropNet applies iterative dropping for nodes/filters with reinitialization.

Model: Consider a dense feed-forward neural network $f(x;n)$ with initial configuration of weights and biases $\theta=\theta_{0}$ and initial configuration of nodes/filters $n$. Let $f$ reach minimum validation loss $l$ with test accuracy $a$ when optimizing with stochastic gradient descent (SGD) on a training set. Consider also training $f(x;m\odot n)$ with a mask $m\in\{0,1\}^{|n|}$ on its nodes/filters such that its initialization is $f(x;m\odot n)$, where $m\odot n$ is an element-wise multiplication between $m$ and $n$. Let $f$ with the mask reach minimum validation loss $l^{\prime}$ with with test accuracy $a^{\prime}$.

Problem: Find a subnetwork $f(x;m\odot n)$ such that $a^{\prime}\approx a$ (similar accuracy) and $||m||_{0}\ll n$ (fewer parameters).

Algorithm: The proposed iterative pruning algorithm is shown in Algorithm 1. DropNet applies Algorithm  1 with the following metric: the lowest average post-activation value across all training samples (either layer-wise or globally). An example of the training cycle using Algorithm  1 is shown in Fig. 1.

Expected Absolute Value of a Node: Unlike weights, which can be of the same value for all training samples, nodes will change their post-activation values according to the input training samples. Hence, we use a node’s expected absolute value across all training samples ($x_{1},x_{2},...,x_{t}$) to evaluate its importance. For each node $a_{i},i\in\mathbb{Z^{+}},1\leq i\leq n$, out of all $n$ nodes in the network, we have its expected absolute value as:

where $V(a_{i}|x_{j})$ is the post-activation value of the node $a_{i}$ with input sequence $x_{j}$.

Expected Absolute Value of a Filter: For CNNs, the filters are comprised of a set of constituent nodes. Choosing which filter to drop is thus equivalent to choosing a set of constituent nodes to drop. Hence, in order to evaluate the importance of each filter $f_{i},i\in\mathbb{Z^{+}},1\leq i\leq n$, out of all $n$ filters in the network, we take the average of the expected absolute value of all its constituent nodes $a_{1},a_{2},...,a_{r}$, $r\in\mathbb{Z}^{+}$. That is:

where $E(f_{i})$ is the expected absolute value of the filter $f_{i}$ across all training samples $x_{1},x_{2},...,x_{t}$.

Intuition: We propose two reasons for the competitiveness of dropping nodes/filters with lowest average post-activation value across all training samples. (i) Firstly, Rectified Linear Unit ($ReLU$) activation will lead to inactive nodes which do not “fire” once the value of node reaches 0 or below. Hence, if a node does not fire most of the time, it will have a low expected absolute value and removing it will affect only a small amount of classifications when its post-activation value is non-zero. (ii) Secondly, during backpropagation, the input weights of a node with low expected absolute value will be updated by only a small amount, which means that the node is less adaptive to learning from the inputs. Removing these less adaptive nodes should impact classification accuracy less than removing more adaptive ones.

In order to evaluate the effectiveness of the DropNet algorithm, we test it empirically using MLPs and CNNs on MNIST (LeCun et al., 2010), CIFAR-10 (Krizhevsky et al., 2009) and Tiny ImageNet (taken from https://tiny-imagenet.herokuapp.com, results in Supplementary Material) datasets.

Q5. How competitive is the DropNet algorithm compared to an oracle?

There are numerous node/filter pruning methods and algorithms available, hence, rather than comparing the performance of DropNet with these individual methods and algorithms, we utilize an oracle in order to establish the competitiveness of DropNet. We define the oracle as the algorithm which greedily drops a node/filter out of all remaining node/filters available at every iteration of Algorithm 1 such that the overall training loss is minimized. In order to provide a fair comparison with the oracle, nodes/filters are also pruned one at a time when using the various metrics.

In order to perform a “stress” test on the various metrics compared to the oracle, we analyze their performance on a smaller scale model, listed as follows:

1. 5.1)

   Model A: FC20 - FC20. The plot of test accuracy against fraction of nodes remaining when compared against an oracle on MNIST is shown in Fig. 14.

2. 5.2)

   Model B: Conv20 - Conv20. The plot of test accuracy against fraction of filters remaining when compared against an oracle on MNIST is shown in Fig. 14.

For 5.1), it can be seen (Fig. 14) that the oracle performs the best, followed closely by minimum, then random and lastly maximum metrics. The random metric used here is actually the random_layer metric, as it provides a stronger baseline performance. Although not shown, minimum_layer has similar performance to minimum.

For 5.2), it can be seen (Fig. 14) that the oracle, minimum and random perform equally well. The worst performing is the maximum metric, with poor performance with 0.4 or less fraction of filters remaining.

Evaluation: The results indicate that overall, the minimum metric is competitive even to an oracle which minimizes training loss. This shows that the minimum metric is indeed a competitive criterion to drop nodes/filters.

We note that Algorithm 1 with a pruning metric runs in linear time. The oracle runs in polynomial time, as it has to iterate through all possible node/filter selections at the end of each iteration of Algorithm 1.

Q6. Is the starting initialization of weights and biases important?

We compare the performance of a network retaining its initial weights and biases $\theta_{0}$ when performing iterative node/filter pruning, as compared to a network with the pruned architecture but with a random initialization (randominit). We conduct the following experiments:

1. 6.1)

   Model A: FC20 - FC20. The plot of test accuracy against fraction of nodes remaining for original and random initialization is shown in Fig. 17.

2. 6.2)

   Model B: Conv64 - Conv64. The plot of test accuracy against fraction of filters remaining for original and random initialization is shown in Fig. 17.

3. 6.3)

   Model C: Conv64 - Conv64 - Conv128 - Conv128. The plot of test accuracy against fraction of filters remaining for original and random initialization is shown in Fig. 17.

It can be seen (Figs. 17, 17, and 17) that unlike the Lottery Ticket Hypothesis (see Figure 4 in (Frankle & Carbin, 2018)), DropNet does not suffer from loss of performance when randomly initialized for up to 70% to 80% of the nodes/filters being dropped.

Evaluation: This means that for DropNet, only the final pruned network architecture is important, and not the initial weights and biases of the network. One reason that the original initialization is not important may be because the learning rate is high enough (0.1) for the network to retrain sufficiently given just the model architecture. This concurs with the finding that the ’winning ticket’ in the Lottery Ticket Hypothesis does not confer significant advantages over random reinitialization if a larger learning rate of 0.1 is used instead of 0.01 (Liu et al., 2018).

Similar results are also obtained for larger models such as ResNet18 and VGG19 (details in Supplementary Material), which shows that this finding is a general one.

Q7. Can we drop more nodes/filters at a time to reduce number of training cycles and prune the model faster without affecting accuracy?

We explore this question by analyzing the performance of the minimum metric. We compare the performance of the model using different values of the pruning fraction $p=0.2,0.3,0.4,0.5$ and $0.9$. The experiments performed are as follows:

1. 7.1)

   Model A: FC20 - FC20. The plot of test accuracy against fraction of nodes remaining for various pruning fractions $p$ on MNIST is shown in Fig. 20.

2. 7.2)

   Model B: Conv64 - Conv64. The plot of test accuracy against fraction of filters remaining for various pruning fractions $p$ on MNIST is shown in Fig. 20.

3. 7.3)

   Model C: Conv64 - Conv64 - Conv128 - Conv128. The plot of test accuracy against fraction of nodes remaining for various pruning fractions $p$ on CIFAR-10 is shown in Fig. 20.

Evaluation: Overall, it can be seen (Figs. 20, 20, and 20) that dropping a greater fraction $p$ of nodes/filters per training cycle leads to poorer performance. For one-shot pruning methods which attempt to remove 90% of nodes/filters, it is not ideal as it generally leads to worse performance. This further reinforces the competitiveness of iterative pruning as compared to one-shot pruning.

The results also show that larger $p$ has similar performance when dropping up to 70% of the nodes/filters. Hence, it may be possible to iterate faster through Algorithm 1 by adopting a larger $p$ under certain conditions. Further experiments need to be done to determine the optimal pruning fraction $p$, but $p=0.2$ seems to be competitive.

Reflections: In this paper, we propose DropNet, which iteratively drops nodes/filters and, hence, reduces network complexity. We illustrate how DropNet can potentially reduce network size by up to 90% without any significant loss of accuracy. Also, there does not need to be a particular initialization required when dropping up to 70% of the nodes/filters. DropNet also has similar performance to an oracle which greedily removes nodes/filters one at a time to minimise training loss, which shows its competitiveness.

DropNet, utilizing either the minimum or minimum_layer metric, proves to be competitive over a variety of model architectures. The minimum metric seems to work robustly well for smaller models such as Models A and B, while the minimum_layer metric appears to be better for larger models such as Model C, ResNet18 and VGG19, in the configurations we considered.

We conjecture that one reason for the better performance of the minimum_layer metric in larger models is that as the number of layers increases, the statistical properties of the post-activation values of the nodes/filters may be significantly different in each layer. Hence, using a single metric to prune globally may not be as good as pruning layer-wise. The exception is when using skip connections, as empirical results suggest that the minimum metric is also competitive for larger models for ResNet18. This seems to suggest that skip connections work well with DropNet.

Additional Experiments: In our Supplementary Material, we show that DropNet is scalable and achieves similar results on Tiny ImageNet . Furthermore, we also compare DropNet with another data-driven approach, APoZ, and show that DropNet outperforms APoZ and can achieve better test accuracy for the same amount of pruning.

Future Work: To further show DropNet’s generalizability, more experiments can be done on i) alternative neural network architectures such as RNNs, as well as ii) other domains such as NLP and reinforcement learning. DropNet has been shown to work well empirically with $ReLU$ activation functions, and it remains to be seen whether other metrics may be required for other activation functions such as $sigmoid$, $tanh$ and $ReLU$ variants.

Source Code: To encourage further research on iterative pruning techniques, the source code used for our experiments is publicly available at https://github.com/tanchongmin/DropNet.

Acknowledgements

This research is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG-GC-2019-002). Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore.