Pruning Convolutional Neural Networks for Resource Efficient Inference

Introduction

Convolutional neural networks (CNN) are used extensively in computer vision applications, including object classification and localization, pedestrian and car detection, and video classification. Many problems like these focus on specialized domains for which there are only small amounts of carefully curated training data. In these cases, accuracy may be improved by fine-tuning an existing deep network previously trained on a much larger labeled vision dataset, such as images from ImageNet (Russakovsky et al., 2015) or videos from Sports-1M (Karpathy et al., 2014). While transfer learning of this form supports state of the art accuracy, inference is expensive due to the time, power, and memory demanded by the heavyweight architecture of the fine-tuned network.

While modern deep CNNs are composed of a variety of layer types, runtime during prediction is dominated by the evaluation of convolutional layers. With the goal of speeding up inference, we prune entire feature maps so the resulting networks may be run efficiently even on embedded devices. We interleave greedy criteria-based pruning with fine-tuning by backpropagation, a computationally efficient procedure that maintains good generalization in the pruned network.

Neural network pruning was pioneered in the early development of neural networks (Reed, 1993). Optimal Brain Damage (LeCun et al., 1990) and Optimal Brain Surgeon (Hassibi & Stork, 1993) leverage a second-order Taylor expansion to select parameters for deletion, using pruning as regularization to improve training and generalization. This method requires computation of the Hessian matrix partially or completely, which adds memory and computation costs to standard fine-tuning.

In line with our work, Anwar et al. (2015) describe structured pruning in convolutional layers at the level of feature maps and kernels, as well as strided sparsity to prune with regularity within kernels. Pruning is accomplished by particle filtering wherein configurations are weighted by misclassification rate. The method demonstrates good results on small CNNs, but larger CNNs are not addressed.

Other approaches include combining parameters with correlated weights (Srinivas & Babu, 2015), reducing precision (Gupta et al., 2015; Rastegari et al., 2016) or tensor decomposition (Kim et al., 2015). These approaches usually require a separate training procedure or significant fine-tuning, but potentially may be combined with our method for additional speedups.

Method

The proposed method for pruning consists of the following steps: 1) Fine-tune the network until convergence on the target task; 2) Alternate iterations of pruning and further fine-tuning; 3) Stop pruning after reaching the target trade-off between accuracy and pruning objective, e.g. floating point operations (FLOPs) or memory utilization.

The procedure is simple, but its success hinges on employing the right pruning criterion. In this section, we introduce several efficient pruning criteria and related technical considerations.

During pruning, we refine a subset of parameters which preserves the accuracy of the adapted network, $\mathcal{C}(\mathcal{D}|\mathcal{W}^{\prime})\approx\mathcal{C}(\mathcal{D}|\mathcal{W})$. This corresponds to a combinatorial optimization:

Finding a good subset of parameters while maintaining a cost value as close as possible to the original is a combinatorial problem. It will require $2^{|\mathcal{W}|}$ evaluations of the cost function for a selected subset of data. For current networks it would be impossible to compute: for example, VGG-16 has $|\mathcal{W}|=4224$ convolutional feature maps. While it is impossible to solve this optimization exactly for networks of any reasonable size, in this work we investigate a class of greedy methods.

Minimizing the difference in accuracy between the full and pruned models depends on the criterion for identifying the “least important” parameters, called saliency, at each step. The best criterion would be an exact empirical evaluation of each parameter, which we denote the oracle criterion, accomplished by ablating each non-zero parameter $w\in\mathcal{W}^{\prime}$ in turn and recording the cost’s difference.

We distinguish two ways of using this oracle estimation of importance: 1) oracle-loss quantifies importance as the signed change in loss, $\mathcal{C}(\mathcal{D}|\mathcal{W^{\prime}})-\mathcal{C}(\mathcal{D}|\mathcal{W})$, and 2) oracle-abs adopts the absolute difference, $|\mathcal{C}(\mathcal{D}|\mathcal{W^{\prime}})-\mathcal{C}(\mathcal{D}|\mathcal{W})|$. While both discourage pruning which increases the loss, the oracle-loss version encourages pruning which may decrease the loss, while oracle-abs penalizes any pruning in proportion to its change in loss, regardless of the direction of change.

While the oracle is optimal for this greedy procedure, it is prohibitively costly to compute, requiring $||W^{\prime}||_{0}$ evaluations on a training dataset, one evaluation for each remaining non-zero parameter. Since estimation of parameter importance is key to both the accuracy and the efficiency of this pruning approach, we propose and evaluate several criteria in terms of performance and estimation cost.

2 Criteria for pruning

Activation.

Mutual information.

Taylor expansion.

where $\mathcal{C}(\mathcal{D},h_{i}=0)$ is a cost value if output $h_{i}$ is pruned, while $\mathcal{C}(\mathcal{D},h_{i})$ is the cost if it is not pruned. While parameters are in reality inter-dependent, we already make an independence assumption at each gradient step during training.

To approximate $\Delta\mathcal{C}(h_{i})$, we use the first-degree Taylor polynomial. For a function $f(x)$, the Taylor expansion at point $x=a$ is

where $f^{(p)}(a)$ is the $p$-th derivative of $f$ evaluated at point $a$, and $R_{p}(x)$ is the $p$-th order remainder. Approximating $\mathcal{C}(\mathcal{D},h_{i}=0)$ with a first-order Taylor polynomial near $h_{i}=0$, we have:

The remainder $R_{1}(h_{i}=0)$ can be calculated through the Lagrange form:

where $\xi$ is a real number between and $h_{i}$. However, we neglect this first-order remainder, largely due to the significant calculation required, but also in part because the widely-used ReLU activation function encourages a smaller second order term.

Intuitively, this criterion prunes parameters that have an almost flat gradient of the cost function w.r.t. feature map $h_{i}$. This approach requires accumulation of the product of the activation and the gradient of the cost function w.r.t. to the activation, which is easily computed from the same computations for back-propagation. $\Theta_{TE}$ is computed for a multi-variate output, such as a feature map, by

where $M$ is length of vectorized feature map. For a minibatch with $T>1$ examples, the criterion is computed for each example separately and averaged over $T$.

Independently of our work, Figurnov et al. (2016) came up with similar metric based on the Taylor expansion, called impact, to evaluate importance of spatial cells in a convolutional layer. It shows that the same metric can be applied to evaluate importance of different groups of parameters.

Relation to Optimal Brain Damage.

The Taylor criterion proposed above relies on approximating the change in loss caused by removing a feature map. The core idea is the same as in Optimal Brain Damage (OBD) (LeCun et al., 1990). Here we consider the differences more carefully.

As an additional benefit, we avoid the computation of the second-order Taylor expansion term, or its simplification - diagonal of the Hessian, as required in OBD.

We found important to compare proposed Taylor criteria to OBD. As described in the original papers (LeCun et al., 1990; 1998), OBD can be efficiently implemented similarly to standard back propagation algorithm doubling backward propagation time and memory usage when used together with standard fine-tuning. Efficient implementation of the original OBD algorithm might require significant changes to the framework based on automatic differentiation like Theano to efficiently compute only diagonal of the Hessian instead of the full matrix. Several researchers tried to tackle this problem with approximation techniques (Martens, 2010; Martens et al., 2012). In our implementation, we use efficient way of computing Hessian-vector product (Pearlmutter, 1994) and matrix diagonal approximation proposed by (Bekas et al., 2007), please refer to more details in appendix. With current implementation, OBD is 30 times slower than Taylor technique for saliency estimation, and 3 times slower for iterative pruning, however with different implementation can only be 50% slower as mentioned in the original paper.

Average Percentage of Zeros (APoZ).

Hu et al. (2016) proposed to explore sparsity in activations for network pruning. ReLU activation function imposes sparsity during inference, and average percentage of positive activations at the output can determine importance of the neuron. Intuitively, it is a good criteria, however feature maps at the first layers have similar APoZ regardless of the network’s target as they learn to be Gabor like filters. We will use APoZ to estimate saliency of feature maps.

3 Normalization

4 FLOPs regularized pruning

One of the main reasons to apply pruning is to reduce number of operations in the network. Feature maps from different layers require different amounts of computation due the number and sizes of input feature maps and convolution kernels. To take this into account we introduce FLOPs regularization:

where $\lambda$ controls the amount of regularization. For our experiments, we use $\lambda=10^{-3}$. $\Theta^{flops}$ is computed under the assumption that convolution is implemented as a sliding window (see Appendix). Other regularization conditions may be applied, e.g. storage size, kernel sizes, or memory footprint.

Results

We empirically study the pruning criteria and procedure detailed in the previous section for a variety of problems. We focus many experiments on transfer learning problems, a setting where pruning seems to excel. We also present results for pruning large networks on their original tasks for more direct comparison with the existing pruning literature. Experiments are performed within Theano (Theano Development Team, 2016). Training and pruning are performed on the respective training sets for each problem, while results are reported on appropriate holdout sets, unless otherwise indicated. For all experiments we prune a single feature map at every pruning iteration, allowing fine-tuning and re-evaluation of the criterion to account for dependency between parameters.

We begin by explicitly computing the oracle for a single pruning iteration of a visual transfer learning problem. We fine-tune the VGG-16 network (Simonyan & Zisserman, 2014) for classification of bird species using the Caltech-UCSD Birds 200-2011 dataset (Wah et al., 2011). The dataset consists of nearly $6000$ training images and $5700$ test images, covering $200$ species. We fine-tune VGG-16 for $60$ epochs with learning rate $0.0001$ to achieve a test accuracy of $72.2\%$ using uncropped images.

To compute the oracle, we evaluate the change in loss caused by removing each individual feature map from the fine-tuned VGG-16 network. (See Appendix A.3 for additional analysis.) We rank feature maps by their contributions to the loss, where rank $1$ indicates the most important feature map—removing it results in the highest increase in loss—and rank $4224$ indicates the least important. Statistics of global ranks are shown in Fig. 3 grouped by convolutional layer. We observe: (1) Median global importance tends to decrease with depth. (2) Layers with max-pooling tend to be more important than those without. (VGG-16 has pooling after layers $2$, $4$, $7$, $10$, and $13$.) However, (3) maximum and minimum ranks show that every layer has some feature maps that are globally important and others that are globally less important. Taken together with the results of subsequent experiments, we opt for encouraging a balanced pruning that distributes selection across all layers.

Next, we iteratively prune the network using pre-computed oracle ranking. In this experiment, we do not update the parameters of the network or the oracle ranking between iterations. Training accuracy is illustrated in Fig. 3 over many pruning iterations. Surprisingly, pruning by smallest absolute change in loss (Oracle-abs) yields higher accuracy than pruning by the net effect on loss (Oracle-loss). Even though the oracle indicates that removing some feature maps individually may decrease loss, instability accumulates due the large absolute changes that are induced. These results support pruning by absolute difference in cost, as constructed in Eq. 1.

2 Evaluating proposed criteria versus the oracle

To evaluate computationally efficient criteria as substitutes for the oracle, we compute Spearman’s rank correlation, an estimate of how well two predictors provide monotonically related outputs, even if their relationship is not linear. Given the difference between oracleWe use Oracle-abs because of better performance in previous experiment and criterion ranks $d_{i}=rank(\Theta_{oracle}(i))-rank(\Theta_{criterion}(i))$ for each parameter $i$, the rank correlation is computed:

where $N$ is the number of parameters (and the highest rank). This correlation coefficient takes values in $$, where$-1$implies full negative correlation, no correlation, and$1$ full positive correlation.

3 Pruning fine-tuned ImageNet networks

We now evaluate the full iterative pruning procedure on two transfer learning problems. We focus on reducing the number of convolutional feature maps and the total estimated floating point operations (FLOPs). Fine-grained recognition is difficult for relatively small datasets without relying on transfer learning. Branson et al. (2014) show that training CNN from scratch on the Birds-200 dataset achieves test accuracy of only $10.9\%$. We compare results to training a randomly initialized CNN with half the number of parameters per layer, denoted "from scratch".

Fig. 4 shows pruning of VGG-16 after fine-tuning on the Birds-$200$ dataset (as described previously). At each pruning iteration, we remove a single feature map and then perform $30$ minibatch SGD updates with batch-size $32$, momentum $0.9$, learning rate $10^{-4}$, and weight decay $10^{-4}$. The figure depicts accuracy relative to the pruning rate (left) and estimated GFLOPs (right). The Taylor criterion shows the highest accuracy for nearly the entire range of pruning ratios, and with FLOPs regularization demonstrates the best performance relative to the number of operations. OBD shows slightly worse performance of pruning in terms of parameters, however significantly worse in terms of FLOPs.

In Fig. 5, we show pruning of the CaffeNet implementation of AlexNet (Krizhevsky et al., 2012) after adapting to the Oxford Flowers $102$ dataset (Nilsback & Zisserman, 2008), with $2040$ training and $6129$ test images from $102$ species of flowers. Criteria correlation with oracle-abs is summarized in Table 1. We initially fine-tune the network for $20$ epochs using a learning rate of $0.001$, achieving a final test accuracy of $80.1\%$. Then pruning procedes as previously described for Birds-$200$, except with only $10$ mini-batch updates between pruning iterations. We observe the superior performance of the Taylor and OBD criteria in both number of parameters and GFLOPs.

We observed that Taylor criterion shows the best performance which is closely followed by OBD with a bit lower Spearman’s rank correlation coefficient. Implementing OBD takes more effort because of computation of diagonal of the Hessian and it is 50% to 300% slower than Taylor criteria that relies on first order gradient only.

Fig. 7 shows pruning with the Taylor technique and a varying number of fine-tuning updates between pruning iterations. Increasing the number of updates results in higher accuracy, but at the cost of additional runtime of the pruning procedure.

During pruning we observe a small drop in accuracy. One of the reasons is fine-tuning between pruning iterations. Accuracy of the initial network can be improved with longer fine tunning and search of better optimization parameters. For example accuracy of unpruned VGG16 network on Birds-200 goes up to $75\%$ after extra 128k updates. And AlexNet on Flowers-102 goes up to $82.9\%$ after 130k updates. It should be noted that with farther fine-tuning of pruned networks we can achieve higher accuracy as well, therefore the one-to-one comparison of accuracies is rough.

4 Pruning a recurrent 3D-CNN network for hand gesture recognition

Molchanov et al. (2016) learn to recognize $25$ dynamic hand gestures in streaming video with a large recurrent neural network. The network is constructed by adding recurrent connections to a 3D-CNN pretrained on the Sports-1M video dataset (Karpathy et al., 2014) and fine tuning on a gesture dataset. The full network achieves an accuracy of $80.7\%$ when trained on the depth modality, but a single inference requires an estimated $37.8$ GFLOPs, too much for deployment on an embedded GPU. After several iterations of pruning with the Taylor criterion with learning rate $0.0003$, momentum $0.9$, FLOPs regularization $10^{-3}$, we reduce inference to $3.0$ GFLOPs, as shown in Fig. 7. While pruning increases classification error by nearly $6\%$, additional fine-tuning restores much of the lost accuracy, yielding a final pruned network with a $12.6\times$ reduction in GFLOPs and only a $2.5\%$ loss in accuracy.

5 Pruning networks for ImageNet

We also test our pruning scheme on the large-scale ImageNet classification task. In the first experiment, we begin with a trained CaffeNet implementation of AlexNet with $79.2\%$ top-5 validation accuracy. Between pruning iterations, we fine-tune with learning rate $10^{-4}$, momentum $0.9$, weight decay $10^{-4}$, batch size $32$, and drop-out $50\%$. Using a subset of $5000$ training images, we compute oracle-abs and Spearman’s rank correlation with the criteria, as shown in Table 1. Pruning traces are illustrated in Fig. 8.

We observe: 1) Taylor performs better than random or minimum weight pruning when $100$ updates are used between pruning iterations. When results are displayed w.r.t. FLOPs, the difference with random pruning is only $0\%\!-\!4\%$, but the difference is higher, $1\%\!-\!10\%$, when plotted with the number of feature maps pruned. 2) Increasing the number of updates from $100$ to $1000$ improves performance of pruning significantly for both the Taylor criterion and random pruning.

For a second experiment, we prune a trained VGG-16 network with the same parameters as before, except enabling FLOPs regularization. We stop pruning at two points, $11.5$ and $8.0$ GFLOPs, and fine-tune both models for an additional five epochs with learning rate $10^{-4}$. Fine-tuning after pruning significantly improves results: the network pruned to $11.5$ GFLOPs improves from $83\%$ to $87\%$ top-5 validation accuracy, and the network pruned to $8.0$ GFLOPs improves from $77.8\%$ to $84.5\%$.

6 Speed up measurements

During pruning we were measuring reduction in computations by FLOPs, which is a common practice (Han et al., 2015; Lavin, 2015a; b). Improvements in FLOPs result in monotonically decreasing inference time of the networks because of removing entire feature map from the layer. However, time consumed by inference dependents on particular implementation of convolution operator, parallelization algorithm, hardware, scheduling, memory transfer rate etc. Therefore we measure improvement in the inference time for selected networks to see real speed up compared to unpruned networks in Table 2. We observe significant speed ups by proposed pruning scheme.

Conclusions

We propose a new scheme for iteratively pruning deep convolutional neural networks. We find: 1) CNNs may be successfully pruned by iteratively removing the least important parameters—feature maps in this case—according to heuristic selection criteria; 2) a Taylor expansion-based criterion demonstrates significant improvement over other criteria; 3) per-layer normalization of the criterion is important to obtain global scaling.

References

Appendix A Appendix

To compute the number of floating-point operations (FLOPs), we assume convolution is implemented as a sliding window and that the nonlinearity function is computed for free. For convolutional kernels we have:

where $H$, $W$ and $C_{in}$ are height, width and number of channels of the input feature map, $K$ is the kernel width (assumed to be symmetric), and $C_{out}$ is the number of output channels.

For fully connected layers we compute FLOPs as:

where $I$ is the input dimensionality and $O$ is the output dimensionality.

We apply FLOPs regularization during pruning to prune neurons with higher FLOPs first. FLOPs per convolutional neuron in every layer:

A.2 Normalization across layers

A.3 Oracle computation for VGG-16 on Birds-200

We compute the change in the loss caused by removing individual feature maps from the VGG-16 network, after fine-tuning on the Birds-200 dataset. Results are illustrated in Fig. 11(a)-11(b) for each feature map in layers $1$ and $13$, respectively. To compute the oracle estimate for a feature map, we remove the feature map and compute the network prediction for each image in the training set using the central crop with no data augmentation or dropout. We draw the following conclusions:

The contribution of feature maps range from positive (above the red line) to slightly negative (below the red line), implying the existence of some feature maps which decrease the training cost when removed.

There are many feature maps with little contribution to the network output, indicated by almost zero change in loss when removed.

Both layers contain a small number of feature maps which induce a significant increase in the loss when removed.

A.4 Comparison with weight regularization

A comparison between pruning based on regularization and our greedy scheme is illustrated in Fig. 12. We observe that our approach has higher test accuracy for the same number of remaining unpruned feature maps, when pruning $85\%$ or more of the feature maps. We observe that with high regularization all weights tend to zero, not only unimportant weights as Han et al. (2015) observe in the case of ImageNet networks. The intuition here is that with regularization we push all weights down and potentially can affect important connections for transfer learning, whereas in our iterative procedure we only remove unimportant parameters leaving others untouched.

A.5 Combination of criteria

One of the possibilities to improve saliency estimation is to combine several criteria together. One of the straight forward combinations is Taylor and mean activation of the neuron. We compute the joint criteria as $\Theta_{joint}(\mathbf{z}_{l}^{(k)})=(1-\lambda)\hat{\Theta}_{Taylor}(\mathbf{z}_{l}^{(k)})+\lambda\hat{\Theta}_{Activation}(\mathbf{z}_{l}^{(k)})$ and perform a grid search of parameter $\lambda$ in Fig.13. The highest correlation value for each dataset is marked with with vertical bar with $\lambda$ and gain. We observe that the gain of linearly combining criteria is negligibly small (see $\Delta$’s in the figure).

A.6 Optimal Brain Damage implementation

OBD computes saliency of a parameter by computing a product of the squared magnitude of the parameter and the corresponding element on the diagonal of the Hessian. For many deep learning frameworks, an efficient implementation of the diagonal evaluation is not straightforward and approximation techniques must be applied. Our implementation of Hessian diagonal computation was inspired by Dauphin et al. (2015) work, where the technique proposed by Bekas et al. (2007) was used to evaluate SGD preconditioned with the Jacobi preconditioner. It was shown that diagonal of the Hessian can be approximated as:

where $\odot$ is the element-wise product, v are random vectors with entries $\pm 1$, and $\nabla$ is the gradient operator. To compute saliency with OBD, we randomly draw v and compute the diagonal over 10 iterations for a single minibatch for 1000 mini batches. We found that this number of mini batches is required to compute close approximation of the Hessian’s diagonal (which we verified). Computing saliency this way is computationally expensive for iterative pruning, and we use a slightly different but more efficient procedure. Before the first pruning iteration, saliency is initialized from values computed off-line with 1000 minibatches and 10 iterations, as described above. Then, at every minibatch we compute the OBD criteria with only one iteration and apply an exponential moving averaging with a coefficient of $0.99$. We verified that this computes a close approximation to the Hessian’s diagonal.

A.7 Correlation of Taylor criterion with gradient and activation

The Taylor criterion is composed of both an activation term and a gradient term. In Figure 14, we depict the correlation between the Taylor criterion and each constituent part. We consider expected absolute value of the gradient instead of the mean, because otherwise it tends to zero. The plots are computed from pruning criteria for an unpruned VGG network fine-tuned for the Birds-200 dataset. (Values are shown after layer-wise normalization). Figure 14(a-b) depict the Taylor criterion in the y-axis for all neurons w.r.t. the gradient and activation components, respectively. The bottom $10\%$ of neurons (lowest Taylor criterion, most likely to be pruned) are depicted in red, while the top $10\%$ are shown in green. Considering all neurons, both gradient and activation components demonstrate a linear trend with the Taylor criterion. However, for the bottom $10\%$ of neurons, as shown in Figure 14(c-d), the activation criterion shows much stronger correlation, with lower activations indicating lower Taylor scores.