Compressing Convolutional Neural Networks

Introduction

In the recent years convolutional neural networks (CNN) have lead to impressive results in object recognition , face verification and audio classification . Problems that seemed impossibly hard only five years ago can now be solved at better than human accuracy . Although CNNs have been known for a quarter of a century , only recently have their superb generalization abilities been accepted widely across the machine learning and computer vision communities. This broad acceptance coincides with the release of very large collections of labeled data . Deep networks and CNNs are particularly well suited to learn from large quantities of data, in part because they can have arbitrarily many parameters. As data sets grow, so do model sizes. In 2012, the first winner of the ImageNet competition that used a CNN had already 240MB of parameters and the most recent winning model, in 2014, required 567MB .

Independently, there has been another parallel shift of computing from servers and workstations to mobile platforms. As of January 2014 there have already been more web searches through smart phones than computershttp://tinyurl.com/omd58sq. Today speech recognition is primarily used on cell phones with intelligent assistants such as Apple’s Siri, Google Now or Microsoft’s Cortana. As this trend continues, we are expecting machine learning applications to also shift increasingly towards mobile devices. However, the disjunction of deep learning with ever increasing model sizes and mobile computing reveals an inherent dilemma. Mobile devices have tight memory and storage limitations. For example, even the most recent iPhone 6 only features 1GB of RAM, most of which must be used by the operating system or the application itself. In addition, developers must make their apps compatible with the most limited phone still in circulation, often restricting models to just a few megabytes of parameters.

In response, there has been a recent interest in reducing the model sizes of deep networks. Denil et al. use low-rank decomposition of the weight matrices to reduce the effective number of parameters in the network. Buciluǎ et al. and Ba et al. show that complex models can be compressed into 1-layer neural networks. Independently, the model size of neural networks can be reduced effectively through reduced bit precision .

In this paper we propose a novel approach for neural network compression targeted especially for CNNs. We build on recent work by Chen et al. , who show that weights of fully connected networks can be effectively compressed with the hashing trick . Due to the nature of local pixel correlation in images (i.e. spatial locality), filters in CNNs tend to be smooth. We transform these filters into frequency domain with the discrete cosine transform (DCT) . In frequency space, the filters are naturally dominated by low frequency components. Our compression takes this smoothness property into account and randomly hashes the frequency components of all CNN filters at a given layer into one common set of hash buckets. All components inside one hash bucket share the same value. As lower frequency components are more pronounced than higher frequencies, we allow collisions only between similar frequencies and allocate fewer hash buckets for the high frequencies (which are less important).

Our approach has several compelling properties: 1. The number of parameters in the CNN is independent of the number of convolutional filters; 2. During testing we only need to add a low-cost hash function and the inverse DCT transformation to any existing CNN code for filter reconstruction; 3. During training, the hashed weights can be learned with simple back-propagation —the gradient of a hash bucket value is the sum of gradients of all hashed frequency components in that bucket.

We evaluate our compression scheme on eight deep learning image benchmark data sets and compare against four competitive baselines. Although all compression schemes lead to lower test accuracy as the compression increases, our FreshNets method is by far the most effective compression method and yields the lowest generalization error rates on almost all classification tasks.

Background

As shown in , a key property of feature hashing is its preservation of inner product operations, where inner products after hashing produce the correct pre-hash inner product in expectation:

is the cosine basis function, and $s_{j}\!=\!\sqrt{\frac{1}{d}}$ when $j\!=\!0$ and $s_{j}\!=\!\sqrt{\frac{2}{d}}$ otherwise. We use the shorthand $f_{dct}$ to denote the DCT operation in Eq. (1), i.e. $\boldsymbol{\mathcal{V}}=f_{dct}({\boldsymbol{V}})$. The inverse DCT converts $\boldsymbol{\mathcal{V}}$ from the frequency domain back to the spatial domain, reconstructing ${\boldsymbol{V}}$ without loss:

We denote the inverse DCT function in Eq. (2) as $f^{-\!1}_{dct}$, i.e. ${\boldsymbol{V}}=f^{-\!1}_{dct}(\boldsymbol{\mathcal{V}})$.

Frequency-Sensitive Hashed Nets

Here we present FreshNets, a method for using weight sharing to reduce the model size (and memory demands) of convolutional neural networks. Similar to the work of Chen et al. , we achieve smaller models by randomly forcing weights throughout the network to share identical values. Unlike previous work, we implement the weight sharing and gradient updates of convolutional filters in the frequency domain. These sharing constraints are made prior to training, and we learn frequency weights under the sharing assignments. Since the assignments are made with a hash function, they incur no additional storage.

Gradients over Shared Frequency Weights. Typical convolutional neural networks learn filters in the spatial domain. As our shared weights are stored in the frequency domain, we derive the gradient with respect to filter parameters in frequency space. Following Eq. (2), we express the gradient of parameters in the spatial domain w.r.t. their counterparts in the frequency domain:

Comparing with Eq. (1), we see that the gradient in the frequency domain is merely the DCT of the gradient in the spatial domain:

where $[{\boldsymbol{A}}]_{j_{1}j_{2}}$ denotes the $(j_{1},j_{2})$ entry in matrix ${\boldsymbol{A}}$.

As components of different frequency groups tend to be of different magnitudes (and thereby varying importance to the spatial structure of the filter), we want to avoid collisions between high and low frequency components. Therefore, we assign separate hash spaces to different frequency groups. In particular, we partition the $K$ values of ${\boldsymbol{w}}$ into sub-vectors ${\boldsymbol{w}}^{0},\dots,{\boldsymbol{w}}^{2d-2}$ of sizes $K_{0},\dots,K_{2d-2}$, where $\sum_{j}K_{j}=K$. This partitioning allows parameters with the same frequency, corresponding to their index sum $j=j_{1}+j_{2}$, to be hashed into a corresponding dedicated hash space ${\boldsymbol{w}}^{j}$. We rewrite Eq. (3) with the new frequency sensitive shared weight assignments:

where $h^{j}(\cdot)$ maps an input key to a natural number in $\{1,\cdots,K_{j}\}$ and $j\!=\!j_{1}\!+\!j_{2}$.

We define a compression rate $r_{j}\!\in\!(0,1]$ for each frequency region $j$ and assign $K_{j}\!=\!r_{j}N_{j}$. A smaller $r_{j}$ induces more collisions during hashing, leading to increased weight sharing. Since lower frequency components tend to be of higher importance, making collisions more hurtful, we commonly assign larger $r_{j}$ (fewer collisions) to low-frequency regions. Intuitively, given a size budget for the whole convolutional layer, we want to squeeze the hash space of high frequency region to save space for low frequency regions. These compression rates can either be assigned by hand or determined programmatically by cross-validation, as demonstrated in Section 5.

Related Work

In each of these works, evaluation time is the main focus, with any resulting storage reduction achieved merely as a side effect. Other works focus entirely on compressing the fully-connected layers of CNNs . However, with the trend toward architectures with fewer fully connected layers and additional convolutional layers , compression of filters is of increased importance. Another technique for speeding up convolutional neural network evaluation is computing convolutions in the Fourier frequency domain, as convolution in the spatial domain is equivalent to (comparatively lower-cost) element-wise multiplication in the frequency domain . Unlike FreshNets, for a filter of size $d\times d$ and an image of size $n\times n$ where $n>d$, Mathieu et al. convert the filter to its frequency domain of size $n\times n$ by oversampling the frequencies, which is necessary for doing element-wise multiplication with a larger image but also increases the memory overhead at test time. Training in the Fourier frequency domain may be advantageous for similar reasons, particularly when convolutions are being performed over large 3-D volumes .

Most relevant to this work is HashedNets which compresses the fully connected layers of deep neural networks. This method uses the hashing trick to efficiently implement parameter sharing prior to learning, achieving notable compression with less loss of accuracy than the competing baselines which relied on low-rank decomposition or learning in randomly sparse architectures.

Experimental Results

In this section, we conduct several comprehensive experiments on benchmark datasets to evaluate the performance of FreshNets.

We experiment with eight benchmark datasets: cifar10, cifar100, svhn and five challenging variants of mnist. The cifar10 dataset contains $60000$ images of $32\times 32$ pixels with three color channels. Images are selected from ten classes with each class consisting of $6000$ unique instances. The cifar100 dataset also contains $60000$ $32\times 32$ images, but is more challenging since the images are selected from $100$ classes (each class has 600 images). For both cifar datasets, $50000$ images are designated for training and the remaining $10000$ images for testing. To improve accuracy on cifar100, we augment by horizontal reflection and cropping , resulting in $0.8$M training images. The svhn dataset is a large collection of digits ($10$ classes) cropped from real-world scenes, consisting of $73257$ training images, $26032$ testing images and $531131$ less difficult images for additional training. In our experiments, we use all available training images, for a total of $604388$ training samples. For the mnist variants , each variation either reduces the training size (mnist-07) or amends the original digits by rotation (rot), background superimposition (bg-rand and bg-img), or a combination thereof (bg-rot). We preprocess all datasets with whitening (except cifar100 and svhn which were prohibitively large).

Baselines.

We compare the proposed FreshNets with four baseline methods: HashedNets , low-rank decomposition (LRD) , filter dropping (DropFilt) and frequency dropping (DropFreq). HashedNets was first proposed to compress fully-connected layers in deep neural networks via the hashing trick. In this baseline, we apply the hashing trick directly to the convolutional layer by hashing filter weights in the spatial domain. This induces random weight sharing across all filters in a single convolutional layer. Additionally, we compare against low-rank decomposition of the convolutional filters . Following the method in , we unfold the four-dimensional filter tensor to form a two dimensional matrix on which we apply the low-rank decomposition. The parameters of the decomposition are fine-tuned via back-propagation. DropFreq learns parameters in the DCT frequency domain but sets high frequency components to to meet the compression requirement. DropFilt compresses simply by reducing the number of filters in each convolutional layer.

All methods were implemented using Torch7 and run on NVIDIA GTX TITAN graphics cards with $2688$ cores and $6$GB of global memory. Model parameters are stored and updated as $32$ bit floating-point values.The compression rates of all methods could be further improved by learning and storing parameters in lower precision .

Comprehensive evaluation.

We adopt the network network architecture shown in Table 1 for all datasets. The architecture is a deep convolutional neural network consisting of five convolutional layers (with $5\times 5$ filters) and one fully-connected layer. Before convolution, input feature maps are zero-padded such that output maps remain the same size as the (un-padded) input maps after convolution. Max-pooling is performed after convolutions in layers $2$, $4$ and $5$ with filter size $2\times 2$ and stride $2$, reducing both input map dimensions by half. Rectified linear units are adopted as the activation function throughout. The output of the network is a softmax function over labels.

In this architecture, the convolutional layers hold the majority of parameters ($1.2$ million in convolutional layer v.s. $40$ thousand in the fully connected layer with $10$ output classes). During training, we optimize parameters using mini-batch gradient descent with batch size $64$ and momentum $0.9$. We use $20$ percent of the training set as a validation set for early stopping. For FreshNets, we use a frequency-sensitive compression scheme which increases weight sharing among higher frequency components.We evaluate several frequency-sensitive schemes later in this section, but for this comprehensive evaluation we set frequency compression rates by a rescaled beta distribution with $\alpha=0.25$ and $\beta=2.5$ for all layers. For all baselines, we apply HashedNets to the fully connected layer at the corresponding level of compression. All error results are reported on the test set.

Table 2(a) and (b) show the comprehensive evaluation of all methods under compression ratios $1/16$ and $1/64$, respectively. We exclude DropFilt and DropFreq in Table 2(b) because neither supports $1/64$ compression in this architecture for all layers. For all methods, the fully connected layer (top layer) is compressed by HashedNets at the corresponding compression rate. In this way, the final size of the entire network respects the specified compression ratio. For reference, we also show the error rate of a standard convolutional neural network (CNN, columns 2 and 8) with the fully-connected layer compressed by HashedNets and no compression in the convolutional layers. Excluding this reference, we highlight the method with best test error on each dataset in bold.

We discern several general trends. In Table 2(a), we observe the performance of the DropFilt and DropFreq at $1/16$ compression. At this compression rate, DropFilt corresponds to a network $1/16$ filters at each layer: $2$, $4$, $4$, $8$, $16$ at layers $1\!-\!5$ respectively. This architecture yields particularly poor test accuracy, including essentially random predictions on three datasets. DropFreq, which at $1/16$ compression parameterizes each filter in the original network by only $1$ or $2$ low-frequency values in the DCT frequency space, performs with similarly poor accuracy. Low rank decomposition (LRD) and HashedNets each yield similar performance at both $1/16$ and $1/64$ compression. Neither explicitly considers the smoothness inherent in learned convolutional filters, instead compressing the filters in the spatial domain. Our method, FreshNets, consistently outperforms all baselines, particularly at the higher compression rate as shown in Table 2(b). Using the same model in Table 1, Figure 3 shows more complete curves of test errors with multiple compression factors on the cifar10 and rot datasets.

Varying compression by frequency.

As mentioned in Section 2, we allow a higher collision rate in the high frequency components than in the low frequency components for each filter. To demonstrate the utility of this scheme, we evaluate several hash compression schemes. Systematically, we set the compression rate of the $j^{th}$ frequency band $r_{j}$ with a parameterized function, i.e. $r_{j}=f(j)$. In this experiment, we use the beta distribution: $f(j;\alpha,\beta)=Zx^{\alpha-1}(1-x)^{\beta-1}$, where $x\!=\!\frac{j+1}{2k-1}$ is a real number between 0 and 1, $k$ is the filter size, and $Z$ is a normalizing factor such that the resulting distribution of parameters meets the target parameter budget $K$, i.e. $\sum_{j=0}^{2k-2}r_{j}N_{j}=K$. We adjust $\alpha$ and $\beta$ to control the compression rate for each frequency region. As shown in Figure 4, we have multiple pairs of $\alpha$ and $\beta$, each of which results in a different compression scheme. For example, if $\alpha=0.25$ and $\beta=2.5$, the compression rate monotonically decreases as a function of component frequency, meaning more parameter sharing among high frequency components (blue curve in Figure 4).

To quickly evaluate the performance of each scheme, we use a simple four-layer FreshNets where the first two layers are DCT-hashed convolutional layers (with $5\times 5$ filters) containing $32$ and $64$ feature maps respectively, and the last two layers are fully connected layers. We test FreshNets on cifar10 with each of the compression schemes shown in Figure 4. In each, weight sharing is limited to be within groups of similar frequencies, as described in Section 2, however number of unique weights shared within each group is varied. We denote the compression scheme with $\alpha,\beta=1$ (red curve) as a frequency-oblivious scheme since it produces a uniform compression independent of frequency. In the inset bar plot in Figure 4, we report test error normalized by the test error of the frequency-oblivious scheme and averaged over compression rates $1$, $1/2$, $1/4$, $1/16$, $1/64$, and $1/256$. We can see that the proposed scheme with fewer shared weights allocated to high frequency components (represented by the blue curve) outperforms all other compression schemes. An inverse scheme where the high frequency regions have the lowest collision rate (purple curve) performs the worst. These empirical results fit our assumption that the low frequency components of a filter are more important than the high frequency components.

Filter visualization.

We investigate the smoothness of the learned convolutional filters in Figure 5 by visualizing the filter weights (first layer) of (a) a standard, uncompressed CNN, (b) FreshNets, and (c) HashedNets (with weight sharing in the spatial domain). For this experiment, we again apply a four layer network with two convolutional layers but adopt larger filters ($11\times 11$) for better visualization. All three networks are trained on mnist, and both FreshNets and HashedNets have $1/16$ compression on the first convolutional layer. When plotting, we scale the values in each filter matrix to the range $$. Hence, white and black pixels stand for large positive and negative weights, respectively. We observe that, although more blurry due to the compression, the filter weights of FreshNets are still smooth while weights in HashedNets appear more chaotic.

Conclusion

In this paper we present FreshNets, a method for learning convolutional neural networks with dramatically compressed model storage. Harnessing the hashing trick for parameter-free random weight sharing and leveraging the smoothness inherent in convolutional filters, FreshNets compresses parameters in a frequency-sensitive fashion such that significant model parameters (e.g. low-frequency components) are better preserved. As such, FreshNets preserves prediction accuracy significantly better than competing baselines at high compression rates.

References