Title: DNN MODEL COMPRESSION UNDER ACCURACY CONSTRAINTS

Abstract: The growing interest to implement Deep Neural Networks (DNNs) on resourcebound hardware has motivated the innovation of compression algorithms. Using these algorithms, DNN model sizes can be substantially reduced, with little-to-no accuracy degradation. This is achieved by either eliminating components from the model, or penalizing complexity during training. While both approaches demonstrate considerable compressions, the former often ignores the loss function during compression while the latter produces unpredictable compressions. In this paper, we propose a technique that directly minimizes both the model complexity and the changes in the loss function. In this technique, we formulate compression as a constrained optimization problem, and then present a solution for it. We will show that using this technique, we can achieve competitive results.

1. INTRODUCTION:

Deep Neural Networks have been rapidly improving in many classification tasks, even surpassing human accuracy for some problems (Russakovsky et al., 2015) . This high accuracy, however, is obtained by employing wider Zagoruyko & Komodakis (2016) or deeper He et al. (2016) networks. Some prominent networks today even surpass 100 layers, store hundreds of millions of parameters, and require billions of operations per input sample He et al. (2016) ; Srivastava et al. (2015) . Such large networks are not well-suited for resource-bound, embedded and mobile platforms which are dominating the consumer market. This mismatch between computational requirements and available resources has motivated efforts to compress DNN models.

Compression techniques exploit the redundancy inherent to neural networks that emerges due to the considerable number of parameters in them. These many parameters help learn highly informative features during training. However, they simultaneously learn multitudes of unnecessary, ineffectual ones. Han et al. (2015) reduces these redundancies by pruning the network and quantizing the remaining parameters. Using these techniques, they were able to reduce the model size by more than an order of magnitude. Their success inspired other methodical approaches such as the soft weight-sharing (Ullrich et al., 2017) . This method encodes model parameters using Bayesian prior and then penalizes this prior during training. As a result, it performs both pruning and quantization simultaneously and achieves superior compressions with negligible loss in accuracy.

In this work, we take a similar, integrated approach with the twist that we directly minimize the complexity. Unlike soft weight-sharing, however, we encode the parameters using the k-means objective which imposes less computations. We further apply a hard constraint on the training loss to maintain sufficient accuracy. Such a constraint takes advantage of the fact that we have already obtained some information about the loss function during training. We then present a straightforward solution for this constrained optimization problem. Our solution iteratively minimizes the k-means objective, while satisfying the loss constraint. Consequently, it can compress the model progressively where the compression rate can be adjusted. Finally, we test the proposed technique on three popular datasets and show that this method can achieve state-of-the-art compression with minimal loss of accuracy.

2. RELATED WORK:

Robustness of DNNs to noisy parameters is a byproduct of their redundancy and has been utilized frequently to facilitate and accelerate their implementations. Limited precision representations which introduce quantization noise, for example, have been widely used to simplify computations (Gupta et al., 2015) and design neural network hardware (Jouppi et al., 2017) . Other works, take a different approach and eliminate most parameters (pruning) (Molchanov et al., 2016) , aiming to reduce the total number of computations instead. Finally, weight-sharing techniques (Han et al., 2015) encode the remaining parameters of the networks in a small dictionary, reducing the storage requirement of the network. In this paper, we will be focusing on the last two techniques (pruning and weight-sharing), which were proposed first by Han et al. (2015) . Our goal is to present a simple, unified method for compressing a trained DNN model. Han et al. (2015) first proposed Deep Compression which introduced pruning and weight-sharing as techniques to compress DNN models. Pruning eliminates unnecessary network connections identified by their magnitude. Weight-sharing then encodes parameters into a small dictionary, using the kmeans algorithm. This technique also employs an intermediate tuning step which offsets the effect of pruning on accuracy. However, the changes in the training loss function are, for the most part, ignored in this technique. Later studies demonstrated that taking this effect into account, either in pruning or quantization, can improve the compression. Guo et al. (2016) , for example, formulated pruning as an optimization problem. Their method essentially performs pruning and tuning simultaneously, but does not perform weight-sharing. Likewise, Choi et al. (2016) incorporate this effect by augmenting the k-means objective by the training loss Hessian. However, they only consider the Hessian at one point, and their method requires prediction of the compression ratio beforehand.

Soft weight-sharing, proposed by Ullrich et al. (2017) , minimized both training loss and model size simultaneously. Unlike the previous attempts, they encoded the network parameters using a Bayesian prior. This prior is then penalized when optimizing the training loss function and the mixing ratio controls the trade-off between accuracy and model size. This is then optimized using a SGD method. The limitation of this technique is the complexity of the Bayesian prior. Due to this limitation, in this paper, we will focus on k-means encoding of the weights, even though our method can be easily extended to Bayesian encoding as well. p

3. METHOD:

The proposed algorithm compresses a trained neural network model by minimizing its complexity while constraining its loss function. Here, we first review the optimization process for the loss function during the training process. Then, we discuss the k-means encoding, which we use to measure the model complexity. Finally, we will present our compression algorithm.

3.1. TRAINING NEURAL NETWORKS:

Training neural networks involves minimizing a loss function that quantifies the dissimilarity between the model output distribution and the ideal distribution. This optimization problem is formally written as:

EQUATION

Here, X and y define a set of samples and ideal output distributions we use for training. W is the learnt model and is the concatenation of all model parameters,

(W = [w 1 w 2 . . . w N ] T ∈ R N

where N is the number of parameters). W is the final, trained model. Also, L(W, X , y) represents the average loss over the dataset ({X , y}) corresponding to the model W . This function is typically chosen as Cross entropy or hinge square loss. In the rest of this paper, we represent L(W, X , y) as L(W ) for simplicity. The local optimum for W in this problem is usually found iteratively, using a SGD method.

3.2. K-MEANS ENCODING:

The weight-sharing techniques proposed by Han et al. (2015) and Guo et al. (2016) use the k-means algorithm to encode the network parameters. Each parameter is then replaced by the nearest of the k centroids. This procedure can also be defined as the following optimization problem:

EQUATION

where

M = [m 1 m 2 . . . m N ] T ∈ R N

is the concatenated array of all centroids m i corresponding to the parameters w i . The set C = {c 1 , c 2 , . . . , c k } ⊂ R also defines the set of cluster centroids.

The commonly used heuristic solution to this problem is to iteratively find M and update centroids accordingly. In each iteration t this update is performed by:

c t+1 j = 1 |J| i∈J w i (4) J = {i|m i = c t j } (5)

3.3. PROPOSED COMPRESSION METHOD:

Similar to weight-sharing in Deep Compression (Han et al., 2015) , we minimize the k-means objective function to reduce the model complexity. Further, similar to soft weigh-sharing (Ullrich et al., 2017) , we minimize the changes in the loss function. However, we control these changes through a hard constraint to take advantage of the information already learnt through the training phase. In the rest of this section, we will formulate the problem of minimizing the complexity of the model and propose a solution for it.

As previously discussed, we use the k-means objective to represent the complexity of the model. The goal is to learn the network parameters as well as the centroids that minimize this objective. Specifically, we would like to learn a small set of centroids and encourage the network parameters to populate a small region about these centroids only.

min

EQUATION

Ψ(W, M ) = N i=1 w i -m i 2 (7)

We note that the centroids m i are correlated to w i by equation 2 with the difference that the number of centroids k is also obtained through the compression process.

In the absence of any additional constraints, this optimization problem reverts back to one solved by Han et al. (2015) for Deep Compression. The solution to this problem is simply w i = m i . However, this might result in significant changes in the accuracy. We address this issue by introducing a constraint on the loss function.

L(W ) ≤ (8)

Here, is the hard constraint derived based on the optimal value of the loss function. We will discuss how we determine this hyper-parameter later in this section. While solving our optimization problem, we will make sure that this condition is always satisfied.

Next, we present our method for solving the problem of minimizing the complexity of a trained model. This method iteratively solves the equation 6 for W and then calculates M based on equation 2, as presented in algorithm 1. This algorithm first initializes k random centroids. The value of k is provided to the algorithm as a hyper-parameter and can be large. During the compression this algorithm eliminates or merges unnecessary centroids and reduces k. At the end of each iteration, if a centroid has not been assigned to any network parameter or is close to another centroids, it is eliminated.

Each iteration t of the compression, finds the nearest centroid to each network parameter and solves the constrained optimization problem by finding a displacement for the model parameters like ∆W t which solves:

EQUATION

This way, the model update for the next iteration would be:

W t+1 = W t + ∆W t .

The solution of this constrained optimization problem should satisfy the KKT condition.

∇ ∆W Ψ(W t + ∆W * , M t ) + µ∇ ∆W L(W t + ∆W * ) = 0 (11) L(W t + ∆W * ) -≤ 0 (12) µ ≥ 0 (13)

This system has two solutions. When µ = 0, the solution is ∀i : w * i = m i . If ∆W * satisfies the constraint in equation 8, this solution is valid. Otherwise:

∇ ∆W Ψ(W t + ∆W * , M t ) + µ∇ ∆W L(W t + ∆W * ) = 0 (14) ⇒ 2(W t -M t ) + µ∇ ∆W L((W t + ∆W * )) = 0 (15) L(W t + ∆W * ) -= 0 (16) µ > 0 (17)

The difficulty of solving this system is the unknown value and gradient of the loss function at the solution which we want to obtain. We get around this issue by locally estimating the loss function using its linear Taylor expansion and replacing that in the system.

L(W + ∆W ) = L(W ) + ∇ W L(W ) T ∆W (18)

We then approximately calculate the displacement of the weights (∆W ) with regards to W 0 , representing the trained parameters, as below:

       2(W 0 + ∆W -M ) + µ∇ W L(∆W ) = 0 L(∆W ) = L(W 0 ) + ∇ W L(W 0 ) T ∆W L(W 0 + ∆W ) -= 0 µ > 0 (19)

This system has a closed form solution:

∆W = - µ 2 ∇ W L(W 0 ) + M -W (20) µ = 2 L(W 0 ) + ∇ W L T (M -W 0 ) - ∇ W L(W 0 ) 2 (21)

This solution is of course valid only in a neighborhood around W 0 where ∆W is an accurate estimation of L(W 0 + ∆W ). We denote this region by the radius ρ. That is, when ∆W ≤ ρ. This technique is similar to local modeling of objective functions as done in Trust Region optimization methods. We also adopt a similar method as trust region techniques to initialize and update the value of ρ in each iteration of the algorithm. Thus, we summarize the algorithm to solve this problem in algorithm 2.

Algorithm 2 Calculate the displacement of W for iteration t n ← 0 Initialize ρ 0 t while True do Solve the constrained optimization problem using equation 20 and find ∆W n λ ← min(1,

ρ n t ∆W n if < L(W t + λ * ∆W n ) then ρ n+1 t ← 1 2 ρ n t else W t+1 ← W t + λ * ∆W n ρ 0 t+1 ← 2 * ρ n t break end if end while

In this algorithm, each iteration receives a trust region radius as input and finds the displacement for W t based on equation 20. Then, if this displacement is larger than the trust region radius, the algorithm scales it. Finally, it checks if the loss function corresponding to this displacement satisfies the loss constraint. If not, it will shrink the trust region radius and retries the condition. Otherwise, it will update the parameters and expands the trust region radius. This new radius will be provided to the next iteration of Algorithm 1. Lastly, we discuss how we obtain the value of . We initialize this value to the loss value corresponding to the original model = L(W 0 ). After the compression is done, we can test the accuracy of the compressed model. If this accuracy is sufficient, we can increase it. In our technique, each time we achieved a sufficient accuracy for the compressed model, we increase by 20%.

4. MODELS:

We test our compression technique on three datasets: MNIST (LeCun et al., 1998b) , CIFAR-10 (Krizhevsky & Hinton, 2009) , and SVHN (Netzer et al., 2011) . MNIST is a collection of 6000 28 × 28 black-and-white images of handwritten digits. CIFAR-10 is a set of 60000 images of object from 10 different classes. Finally, SVHN contains 60000 images of digits captured by google street view. We train a LeNet-5 on the MNIST dataset and a smaller version of the VGG network (Hubara et al., 2016) for both CIFAR-10 and SVHN. The model size and accuracy of these baseline networks are presented in table 1. 

5. EXPERIMENTS:

In this section, we experimentally study the convergence of the proposed algorithm and show that it achieves state-of-the-art compression rates. We confirm that the parameters of the compressed model cluster about the learnt centroids and evaluate the effect of this clustering on the accuracy. We then present a more in-depth study of the trade-off between accuracy and the compressed model size on our benchmarks. Finally, we compare the optimal model obtained through the trade-off analysis with the previous techniques.

The proposed compression algorithm encourages parameters to gravitate towards a set of centroids, which it learns simultaneously. We verify this on MNIST by initializing 256 random centroids. These centroids are eliminated or optimized according to Algorithm 6. Figure 1a illustrates the optimization of the centroids. In each iteration t, this figure shows the accuracy gap between the current model, W t , and its compression using the current centroids, C t . We observe that this gap decreases as the centroids are adjusted. In addition, we observe little uncompressed model accuracy degradation, despite the parameter updates. We confirm these updates cause meaningful changes to the parameters in Figure 1b . This figure depicts the distribution of the parameters before and after the compression. We can see that the parameters approach 4 centroids, with 86% of them gathered around 0. Overall, the compression results in 112× reduction in the model size with only 0.53% drop in accuracy. We note that the number of pruned parameters in this result are lower compared to previous works such as Deep Compression. However, the model size reduction is higher due to the smaller dictionary. The loss bound (section 2) controls the final model size, introducing a trade-off between accuracy and compression. We study this trade-off by incrementing the loss bound and optimizing the model size using Algorithm 1. In the analysis for each of the benchmark datasets we initialize 256 random centroids and depict the results in Figure 2 . We can see that for small reductions in size, the accuracy remains generally the same. During this stage, most clusters are quickly eliminated due to being empty. As the model size becomes small however, the error starts to increase quickly. We also observe clusters being eliminated less often. These eliminations are a result of merging clusters.

Using these analyses, we can find the optimal trade-off between the accuracy and model size.

Table 2 summarizes the optimal trade-offs obtained from the previous analysis and compares them with previous works. With little drop in accuracy, the proposed method achieves state-of-the art accuracy for the MNIST dataset. It also achieves similar reductions in model size for the SVHN and CIFAR-10 datasets using the much larger network model. 

6. CONCLUSION:

In this paper, we presented a method for compressing trained neural network models that directly minimizes its complexity while maintaining its accuracy. For simplicity of calculations, we chose to represent the complexity using the k-means objective which is frequently used in previous works.

In doing so, we maintain the accuracy by introducing a hard constraint on the loss function. This constraint incorporates the information learnt during the training process into the optimization. We then present an algorithm that iteratively finds the optimal complexity. We test this solution on several datasets and show that it can provide state-of-the-art compression, with little accuracy loss.

:



Figures and Tables:

(a) Effect of reducing the complexity and learning the centroids on the uncompressed and compressed model accuracies. (b) Final distribution of network parameters.

Figure 1: Compression of LeNet-5 using the proposed method

Figure 2: The trade-off between accuracy and model compression for MNIST, SVHN, and CIFAR-10, using the constrained compression method.

Baseline models

Table content: <table><tr><td>Dataset</td><td>Model</td><td colspan="2">Model Size Error Rate</td></tr><tr><td>MNIST</td><td>LeNet-5 (LeCun et al., 1998a)</td><td>12M b</td><td>0.65%</td></tr><tr><td colspan="2">CIFAR-10 (Hubara et al., 2016)</td><td>612M b</td><td>13.07%</td></tr><tr><td>SVHN</td><td>(Hubara et al., 2016)</td><td>110M b</td><td>2.73%</td></tr></table>

Baseline models

Table content: <table><tr><td>Dataset</td><td>Compression Technique</td><td colspan="2">Compression Ratio Accuracy Loss</td></tr><tr><td/><td>Constrained Compression</td><td>112</td><td>0.53</td></tr><tr><td>MNIST</td><td>Deep Compression</td><td>39</td><td>-0.06</td></tr><tr><td/><td>Iterative ECSQ</td><td>49</td><td>-0.02</td></tr><tr><td/><td>Soft Weight-Sharing</td><td>64</td><td>-0.05</td></tr><tr><td colspan="2">CIFAR-10 Constrained Compression</td><td>42</td><td>0.78</td></tr><tr><td>SVHN</td><td>Constrained Compression</td><td>128</td><td>2.37</td></tr></table>

Peer review (iclr2018):
 1. Summary This paper introduced a method to learn a compressed version of a neural network such that the loss of the compressed network doesn*t dramatically change. 2. High level paper - I believe the writing is a bit sloppy. For instance equation 3 takes the minimum over all m in C but C is defined to be a set of c_1, ..., c_k, and other examples (see section 4 below). This is unfortunate because I believe this method, which takes as input a large complex network and compresses it so the loss in accuracy is small, would be really appealing to companies who are resource constrained but want to use neural network models. 3. High level technical - I*m confused at the first and second lines of equation (19). In the first line, shouldn*t the first term not contain .Delta W ? In the second line, shouldn*t the first term be .tilde{.mathcal{L}}(W_0 + .Delta W) ? - For CIFAR-10 and SVHN you*re using Binarized Neural Networks and the two nice things about this method are (a) that the memory usage of the network is very small, and (b) network operations can be specialized to be fast on binary data. My worry is if you*re compressing these networks with your method are the weights not treated as binary anymore? Now I know in Binarized Neural Networks they keep a copy of real-valued weights so if you*re just compressing these then maybe all is alright. But if you*re compressing the weights _after_ binarization then this would be very inefficient because the weights won*t likely be binary anymore and (a) and (b) above no longer apply. - Your compression ratio is much higher for MNIST but your accuracy loss is somewhat dramatic, especially for MNIST (an increase of 0.53 in error nearly doubles your error and makes the network worse than many other competing methods: http://rodrigob.github.io/are_we_there_yet/build/classification_datasets_results.html#4d4e495354). What is your compression ratio for 0 accuracy loss? I think this is a key experiment that should be run as this result would be much easier to compare with the other methods. - Previous compression work uses a lot of tricks to compress convolutional weights. Does your method work for convolutional layers? - The first paper to propose weight sharing was not Han et al., 2015, it was actually: Chen W., Wilson, J. T., Tyree, S., Weinberger K. Q., Chen, Y. "Compressing Neural Networks with the Hashing Trick" ICML 2015 Although they did not learn the weight sharing function, but use random hash functions. 4. Low level technical - The end of Section 2 has an extra *p* character - Section 3.1: "Here, X and y define a set of samples and ideal output distributions we use for training" this sentence is a bit confusing. Here y isn*t a distribution, but also samples drawn from some distribution. Actually I don*t think it makes sense to talk about distributions at all in Section 3. - Section 3.1: "W is the learnt model....hat{W} is the final, trained model" This is unclear: W and .hat{W} seem to describe the same thing. I would just remove "is the learnt model and" 5. Review summary While the trust-region-like optimization of the method is nice and I believe this method could be useful for practitioners, I found the paper somewhat confusing to read. This combined with some key experimental questions I have make me think this paper still needs work before being accepted to ICLR.