Speeding up Convolutional Neural Networks with Low Rank Expansions

Max Jaderberg, Andrea Vedaldi, Andrew Zisserman

Introduction

Many applications of machine learning, and most recently computer vision, have been disrupted by the use of convolutional neural networks (CNNs). The combination of an end-to-end learning system with minimal need for human design decisions, and the ability to efficiently train large and complex models, have allowed them to achieve state-of-the-art performance in a number of benchmarks [Krizhevsky et al.(2012)Krizhevsky, Sutskever, and Hinton, Taigman et al.(2014)Taigman, Yang, Ranzato, and Wolf, Toshev and Szegedy(2013), Alsharif and Pineau(2014), Goodfellow et al.(2013a)Goodfellow, Bulatov, Ibarz, Arnoud, and Shet, Sermanet et al.(2013)Sermanet, Eigen, Zhang, Mathieu, Fergus, and LeCun, Razavian et al.(2014)Razavian, Azizpour, Sullivan, and Carlsson]. However, these high performing CNNs come with a large computational cost due to the use of chains of several convolutional layers, often requiring implementations on GPUs [Krizhevsky et al.(2012)Krizhevsky, Sutskever, and Hinton, Jia(2013)] or highly optimized distributed CPU architectures [Vanhoucke et al.(2011)Vanhoucke, Senior, and Mao] to process large datasets. The increasing use of these networks for detection in sliding window approaches [Sermanet et al.(2013)Sermanet, Eigen, Zhang, Mathieu, Fergus, and LeCun, Farabet et al.(2012)Farabet, Couprie, Najman, and LeCun, Oquab et al.(2014)Oquab, Bottou, Laptev, and Sivic] and the desire to apply CNNs in real-world systems means the speed of inference becomes an important factor for applications. In this paper we introduce an easy-to-implement method for significantly speeding up pre-trained CNNs requiring minimal modifications to existing frameworks. There can be a small associated loss in performance, but this is tunable to a desired accuracy level. For example, we show that a 4.5 $\times$ speedup can still give state-of-the-art performance in our example application of character recognition.

While a few other CNN acceleration methods exist, our key insight is to exploit the redundancy that exists between different feature channels and filters [Denil et al.(2013)Denil, Shakibi, Dinh, and de Freitas]. We contribute two approximation schemes to do so (Sect. 2) and two optimization methods for each scheme (Sect. 2.2). Both schemes are orthogonal to other architecture-specific optimizations and can be easily applied to existing CPU and GPU software. Performance is evaluated empirically in Sect. 3 and results are summarized in Sect 4.

There are only a few general speedup methods for CNNs. Denton et al\bmvaOneDot [Denton et al.(2014)Denton, Zaremba, Bruna, LeCun, and Fergus] use low rank approximations and clustering of filters achieving 1.6 $\times$ speedup of single convolutional layers (not of the whole network) with a 1% drop in classification accuracy. Mamalet et al\bmvaOneDot [Mamalet and Garcia(2012)] design the network to use rank-1 filters from the outset and combine them with an average pooling layer; however, the technique cannot be applied to general network designs. Vanhoucke et al\bmvaOneDot [Vanhoucke et al.(2011)Vanhoucke, Senior, and Mao] show that 8-bit quantization of the layer weights can result in a speedup with minimal loss of accuracy. Not specific to CNNs, Rigamonti et al\bmvaOneDot [Rigamonti et al.(2013)Rigamonti, Sironi, Lepetit, and Fua] show that multiple image filters can be approximated by a shared set of separable (rank-1) filters, allowing large speedups with minimal loss in accuracy.

Moving to hardware-specific optimizations, cuda-convnet [Krizhevsky et al.(2012)Krizhevsky, Sutskever, and Hinton] and Caffe [Jia(2013)] show that highly optimized CPU and GPU code can give superior computational performance in CNNs. [Mathieu et al.(2013)Mathieu, Henaff, and LeCun] performs convolutions in the Fourier domain through FFTs computed efficiently over batches of images on a GPU. Other methods from [Vanhoucke et al.(2011)Vanhoucke, Senior, and Mao] show that specific CPU architectures can be taken advantage of, e.g\bmvaOneDotby using SSSE3 and SSSE4 fixed-point instructions and appropriate alignment of data in memory. Farabet et al\bmvaOneDot [Farabet et al.(2011)Farabet, LeCun, Kavukcuoglu, Culurciello, Martini, Akselrod, and Talay] show that using bespoke FPGA implementations of CNNs can greatly increase processing speed.

To speed up test-time in a sliding window context for a CNN, [Iandola et al.(2014)Iandola, Moskewicz, Karayev, Girshick, Darrell, and Keutzer] shows that multi-scale features can be computed efficiently by simply convolving the CNN across a flattened multi-scale pyramid. Furthermore search space reduction techniques such as selective search [van de Sande et al.(2011)van de Sande, Uijlings, Gevers, and Smeulders] drastically cut down the number of times a full forward pass of the CNN must be computed by cheaply identifying a small number of candidate object locations in the image.

Note, the methods we proposed are not specific to any processing architecture and can be combined with many of the other speedup methods given above.

Filter Approximations

One way to exploit this redundancy is to approximate the filter set by a linear combination of a smaller basis set of $M$ filters [Rigamonti et al.(2013)Rigamonti, Sironi, Lepetit, and Fua, Song et al.(2012)Song, Zickler, Althoff, Girshick, Fritz, Geyer, Felzenszwalb, and Darrell, Song et al.(2013)Song, Darrell, and Girshick]. The basis filter set $S=\{s_{i}\}~{}\forall i\in[1\dots M]$ is used to generate basis feature maps which are then linearly combined such that $y_{i}\simeq\sum_{k=1}^{M}a_{ik}s_{k}*x$ . This can lead to a speedup in feature map computation as a smaller number of filters need be convolved with the input image, and the final feature maps are composed of a cheap linear combination of these. The complexity in this case is $\mathcal{O}((d^{2}M+MN)H^{\prime}W^{\prime})$ , so a speedup can be achieved if $M<\frac{d^{2}N}{d^{2}+N}$ .

The separable filters of [Rigamonti et al.(2013)Rigamonti, Sironi, Lepetit, and Fua] are a low-rank approximation, but performed in the spatial filter dimensions. Our key insight is that in CNNs substantial speedups can be achieved by also exploiting the cross-channel redundancy to perform low-rank decomposition in the channel dimension as well. We explore both of these low-rank approximations in the sequel.

Note that the FFT [Mathieu et al.(2013)Mathieu, Henaff, and LeCun] could be used as an alternative speedup method to accelerate individual convolutions in combination with our low-rank cross-channel decomposition scheme. However, separable convolutions have several practical advantages: they are significantly easier to implement than a well tuned FFT implementation, particularly on GPUs; they do not require feature maps to be padded to a special size, such as a power of two as in [Mathieu et al.(2013)Mathieu, Henaff, and LeCun]; they are far more memory efficient; and, they yield a good speedup for small image and filter sizes too (which can be common in CNNs), whilst FFT acceleration tends to be better for large filters due to the overheads incurred in computing the FFTs.

We now propose two schemes to approximate a convolutional layer of a CNN to reduce the computational complexity and discuss their training in Sec. 2.2. Both schemes follow the same intuition: that CNN filter banks can be approximated using a low rank basis of filters that are separable in the spatial domain.

The first cost term $CMd^{2}H^{\prime}W^{\prime}$ would also suggest that efficiency requires the condition $M\ll N$ ; however, this can be considerably ameliorated by using separable filters in the basis. In this case the approximation cost is reduced to $O(MC(d+N)H^{\prime}W^{\prime})$ ; together with the former condition, Scheme 1 is then efficient if $M\ll d\min\{d,N\}$ .

Note that this scheme uses $C$ filter basis $S^{1},S^{2},\dots,S^{C}$ as each operates on a different input channel. In practice, we choose $S^{1}=S^{2}=\dots=S^{C}=S$ because empirically there is no actual gain in performance and a single channel basis is simpler and more compact.

which is the sum of separable filters $h_{n}^{k}*v_{k}^{c}$ . The computational cost of this scheme is $O(KCdH^{\prime}W)$ for the first vertical filters and $O(NKdH^{\prime}W^{\prime})$ for the second horizontal filter. Assuming that the image width $W\gg d$ is significantly larger than the filter size, the output image width $W\approx W^{\prime}$ is about the same as the input image width $W^{\prime}$ . Hence the total cost can be simplified to $O(K(N+C)dH^{\prime}W^{\prime})$ . Compared to the direct convolution cost of $O(NCd^{2}H^{\prime}W^{\prime})$ , this scheme is therefore convenient provided that $K(N+C)\ll NCd$ . For example, if $K$ , $N$ , and $C$ are of the same order, the speedup is about $d$ times.

In both schemes, we are assuming that the full rank original convolutional filter bank can be decomposed in to a linear combination of a set of separable basis filters. The difference between the schemes is how/where they model the interaction between input and output channels, which amounts to how the low rank channel space approximation is modelled. In Scheme 1 it is done with the linear combination layer, whereas with Scheme 2 the channel interaction is modelled with 3D vertical and horizontal filters inducing a summation over channels as part of the convolution.

2 Optimization

This section deals with the details on how to attain the optimal separable basis representation of a convolutional layer for the schemes. The first method (Sec. 2.2.1) aims to reconstruct the original filters directly by minimizing filter reconstruction error. The second method (Sec. 2.2.2) approximates the convolutional layer indirectly, by minimizing reconstruction error of the output of the layer.

The first way that we can attain the separable basis representation is to aim to minimize the reconstruction error of the original filters with our new representation.

This minimization is biconvex, so given ${s_{m}}$ a unique $a_{n}$ can be found, therefore a minimum is found by alternating between optimizing $s_{m}$ and $a_{n}$ . For full details of the implementation of this optimization see [Rigamonti et al.(2013)Rigamonti, Sironi, Lepetit, and Fua].

The set of horizontal and vertical filters can be learnt by explicitly minimizing the $L_{2}$ reconstruction error of the original filters. From (1) we can see that the original filter can be approximated by minimizing the objective function

This optimization is simpler than for Scheme 1 due to the lack of nuclear norm constraints, which we are able to avoid by modelling the separability explicitly with two variables. We perform conjugate gradient descent, alternating between optimizing the horizontal and vertical filter sets.

2.2 Data Reconstruction Optimization

The problem with optimizing the separable basis through minimizing original filter reconstruction error is that this does not necessarily give the most optimized basis set for the end CNN prediction performance. As an alternative, one can optimize a scheme’s separable basis by aiming to reconstruct the outputs of the original convolutional layer given training data. For example, for Scheme 2 this amounts to

where $l$ is the index of the convolutional layer to be approximated and $\Phi_{l}(x_{i})$ is the evaluation of the CNN up to and including layer $l$ on data sample $x_{i}\in X$ where $X$ is the set of training examples. This optimization can be done quite elegantly by simply mirroring the CNN with the un-optimized separable basis layers, and training only the approximation layer by back-propagating the $L_{2}$ error between the output of the original layer and the output of the approximation layer (see Fig. 2). This is done layer by layer.

There are two main advantages of this method for optimization of the approximation schemes. The first is that the approximation is conditioned on the manifold of the training data – original filter dimensions that are not relevant or redundant in the context of the training data will by ignored by minimizing data reconstruction error, but will still be penalised by minimizing filter reconstruction error (Sec. 2.2.1) and therefore uselessly using up model capacity. Secondly, stacks of approximated layers can be learnt to incorporate the approximation error of previous layers by feeding the data through the approximated net up to layer $l$ rather than the original net up to layer $l$ (see Fig. 2 (b)). This additionally means that all the approximation layers could be optimized jointly with back-propagation.

An obvious alternative optimization strategy would be to replace the original convolutional layers with the un-optimized approximation layers and train just those layers by back-propagating the classification error of the approximated CNN. However, this does not actually result in better classification accuracy than doing $L_{2}$ data reconstruction optimization – in practice, optimizing the separable basis within the full network leads to overfitting of the training data, and attempts to minimize this overfitting through regularization methods like dropout [Hinton et al.(2012)Hinton, Srivastava, Krizhevsky, Sutskever, and Salakhutdinov] lead to under-fitting, most likely due to the fact that we are already trying to heavily approximate our original filters. However, this is an area that needs to be investigated in more detail.

Experiments & Results

In this section we demonstrate the application of both proposed filter approximation schemes and show that we can achieve large speedups with a very small drop in accuracy. We use a pre-trained CNN that performs case-insensitive character classification of scene text. Character classification is an essential part of many text spotting pipelines such as [Quack(2009), Posner et al.(2010)Posner, Corke, and Newman, Yang et al.(2012)Yang, Quehl, and Sack, Neumann and Matas(2010), Neumann and Matas(2011), Neumann and Matas(2012), Wang et al.(2011)Wang, Babenko, and Belongie, Neumann and Matas(2013), Alsharif and Pineau(2014), Bissacco et al.(2013)Bissacco, Cummins, Netzer, and Neven].

We first give the details of the base CNN model used for character classification which will be subject to speedup approximations. The optimization processes and how we attain the approximations of Scheme 1 & 2 to this model are given, and finally we discuss the results of the separable basis approximation methods on accuracy and inference time of the model.

For scene character classification, we use a four layer CNN with a softmax output. The CNN outputs a probability distribution $p(c|x)$ over an alphabet $C$ which includes all 26 letters and 10 digits, as well as a noise/background (no-text) class, with $x$ being a grey input image patch of size $24\times 24$ pixels, which has been zero-centred and normalized by subtracting the patch mean and dividing by the standard deviation. The non-linearity used between convolutional layers is maxout [Goodfellow et al.(2013b)Goodfellow, Warde-Farley, Mirza, Courville, and Bengio] which amounts to taking the maximum response over a number of linear models e.g\bmvaOneDotthe maxout of two feature channels $z^{1}_{i}$ and $z^{2}_{i}$ is simply their pointwise maximum: $h_{i}(z_{i}(u,v))=\max\{z^{1}_{i}(u,v),z^{2}_{i}(u,v)\}$ . Table 1 gives the details of the layers for the model used, which is connected in the linear arrangement Conv1-Conv2-Conv3-Conv4-Softmax.

The training dataset consists of 163,222 collected character samples from a number of scene text and synthesized character datasets [icd(), Lucas(2005), Shahab et al.(2011)Shahab, Shafait, and Dengel, Karatzas et al.(2013)Karatzas, Shafait, Uchida, Iwamura, Mestre, Mas, Mota, Almazan, de las Heras, et al., kai(), de Campos et al.(2009)de Campos, Babu, and Varma, Wang et al.(2012)Wang, Wu, Coates, and Ng]. The test set is the collection of 5379 cropped characters from the ICDAR 2003 training set after removing all non-alphanumeric characters as in [Wang et al.(2011)Wang, Babenko, and Belongie, Alsharif and Pineau(2014)]. We evaluate the case-insensitive accuracy of the classifier, ignoring the background class. The Test Model achieves state-of-the-art results of 91.3% accuracy compared to the next best result of 89.8% [Alsharif and Pineau(2014)].

The CNN framework we use is the CPU implementation of Caffe [Jia(2013)], where convolutions are performed by constructing a matrix of filter windows of the input, im2col, and using BLAS for the matrix-matrix multiplication between the filters and data windows. We found this to be the fastest CPU CNN implementation attainable. CNN training is done with SGD with momentum of 0.9 and weight decay of 0.0005. Dropout of 0.5 is used on all layers except Conv1 to regularize the weights, and the learning rate is adaptively reduced during the course of training.

For filter reconstruction optimization, we optimize a separable basis until a stable minimum of reconstruction error is reached. For data reconstruction optimization, we optimize each approximated layer in turn, and can incorporate a fine-tuning with joint optimization.

For the CNN presented, we only approximate layers Conv2 and Conv3. This is because layer Conv4 has a $1\times 1$ filter size and so would not benefit much from our speedup schemes. We also don’t approximate Conv1 due to the fact that it acts on raw pixels from natural images – the filters in Conv1 are very different to those found in the rest of the network and experimentally we found that they cannot be approximated well by separable filters (also observed in [Denton et al.(2014)Denton, Zaremba, Bruna, LeCun, and Fergus]). Omitting layers Conv1 and Conv4 from the schemes does not change overall network speedup significantly, since Conv2 and Conv3 constitute 90% of the overall network processing time, as shown in Table. 1.

Fig. 3 shows the output reconstruction error of each approximated layer with the test data. It is clear that the reconstruction error worsens as the speedup achieved increases, both theoretically and practically. As the reconstruction error is that of the test data features fed through the approximated layers, as expected the data reconstruction optimization scheme gives lower errors for the same speedup compared to the filter reconstruction. This generally holds even when completely random Gaussian noise data is fed through the approximated layers – data from a completely different distribution to what the data optimization scheme has been trained on.

Looking at the theoretical speedups possible in Fig. 3, Scheme 1 gives better reconstruction error to speedup ratio, suggesting that the Scheme 1 model is perhaps better suited for approximating convolutional layers. However, when the actual measured speedups are compared, Scheme 1 is actually slower than that of Scheme 2 for the same reconstruction error. This is due to the fact that the Caffe convolution routine is optimized for 3D convolution (summing over channels), so Scheme 2 requires only two im2col and BLAS calls. However, to implement Scheme 1 with Caffe style convolution involving per-channel convolution without channel summation, means that there are many more costly im2col and BLAS calls, thus slowing down the layer evaluation and negating the model approximation speedups. It is possible that using a different convolution routine with Scheme 1 will bring the actual timings closer to the theoretically achievable timings.

Fig. 4 (b) & (c) show the overall drop in accuracy as the speedup of the end-to-end network increases under different optimization strategies. Generally, joint data optimization of Conv2 and Conv3 improves final classification performance for a given speedup. Under Scheme 2 we can achieve a 2.5 $\times$ speedup with no loss in accuracy, and a 4.5 $\times$ speedup with only a drop of 1% in classification accuracy, giving 90.3% accuracy – still state-of-the-art for this benchmark. The 4.5 $\times$ configuration is obtained by approximating the original 128 Conv2 filters with 31 horizontal filters followed by 128 vertical filters, and the original 512 Conv3 filters with 26 horizontal filters followed by 512 vertical filters.

This speedup is incredibly useful for sliding window schemes, allowing fast generation of, for example, detection maps such as the character detection map shown in Fig. 5. There is very little difference with even a 3.5 $\times$ speedup, and when incorporated in to a full application pipeline, the speedup can be tuned to give an acceptable end pipeline result.

Comparing to an FFT based CNN [Mathieu et al.(2013)Mathieu, Henaff, and LeCun], our method can actually give greater speedups. With the same layer setup (5 $\times$ 5 kernel, $16\times 16\times 256$ input, 384 filters), Scheme 2 gives an actual 2.4 $\times$ speedup with 256 basis filters (which should result in no performance drop), compared to $2.2\times$ in [Mathieu et al.(2013)Mathieu, Henaff, and LeCun]. Comparing with [Denton et al.(2014)Denton, Zaremba, Bruna, LeCun, and Fergus], simply doing a filter reconstruction approximation with Scheme 2 of the second layer of OverFeat [Sermanet et al.(2013)Sermanet, Eigen, Zhang, Mathieu, Fergus, and LeCun] gives a 2 $\times$ theoretical speedup with only 0.5% drop in top-5 classification accuracy on ImageNet, far better than the 1.2% drop in accuracy for the same theoretical speedup reported in [Denton et al.(2014)Denton, Zaremba, Bruna, LeCun, and Fergus]. This accuracy should be further improved if data optimization is used.

Conclusions

In this paper we have shown that the redundancies in representation in CNN convolutional layers can be exploited by approximating a learnt full rank filter bank as combinations of a rank-1 filter basis. We presented two schemes to do this, with two optimization techniques for attaining the approximations. The resulting approximations require significantly less operations to compute, resulting in large speedups observed with a real CNN trained for scene text character recognition: a 4.5 $\times$ speedup, only a drop of 1% in classification accuracy.

In future work it would be interesting to experiment with other arrangements of separable filters in layers, e.g\bmvaOneDota horizontal basis layer, followed by a vertical basis layer, followed by a linear combination layer. Looking at the filter reconstructions of the two schemes in Fig. 4 (a), it is obvious that the two presented schemes act very differently, so the connection between different approximation structures could be explored. Also it should be further investigated whether these model approximations can be effectively taken advantage of during training, with low-rank filter layers being learnt in a discriminative manner.