Title: ACCELERATING CONVOLUTIONAL NEURAL NET-WORKS USING ITERATIVE TWO-PASS DECOMPOSI-TION

Abstract: We present the iterative two-pass decomposition flow to accelerate existing convolutional neural networks (CNNs). The proposed rank selection algorithm can effectively determine the proper ranks of the target convolutional layers for the low rank approximation. Our two-pass CP-decomposition helps prevent from the instability problem. The iterative flow makes the decomposition of the deeper networks systematic. The experiment results shows that VGG16 can be accelerated with a 6.2× measured speedup while the accuracy drop remains only 1.2%.

1. INTRODUCTION:

Deep learning has become of vital importance in a variety of artificial intelligence applications. Recently, convolutional neural networks (CNNs) have been widely applied to have the breakthrough in improving the recognition accuracy for challenging computer vision tasks such as image classification, localization, object detection, and so on (Russakovsky et al. (2015) ; Krizhevsky et al. (2012) ; Simonyan & Zisserman (2014) ; He et al. (2015) ). However, those significant achievements using CNNs come with the cost of larger network size and higher computational complexity, which leads to an increasing difficulty for deploying to resource constrained edge devices, or even for the fast computation on the cloud servers. This paper addresses the acceleration of the existing CNN models to cope with such burden.

1.1. RELATIVE WORKS:

There have been research works on accelerating CNNs in many aspects. Several approaches have been proposed to simplify the convolution operations. Vasilache et al. (2014) uses Fast Fourier Transform to accelerate the convolution which is fast for large filters. In Lavin & Gray (2015) , Winograd's minimal filtering algorithms have been adopted to speed up small-size filters. Pruning aims at removing unessential weights in the filters to minimize the computation. Weights can be removed after the training (Han et al. (2015) ; Li et al. (2016) ; Yu et al. (2017) ) or during the training with the sparsity constraint (Wen et al. (2016) ; Park et al. (2017) ). Quantization reduces the precision from the 32-bit floating-point computations to the 8-bit fixed-point ones, or even the binary operations (Hubara et al. (2016) ; Rastegari et al. (2016) ). These approaches are efficient for implementing the hardware accelerators of the faster inference.

In addition to the attempts of accelerating pre-trained models, some works focus on designing new models with more efficient computation (Iandola et al. (2016) ; Wang et al. (2016); Howard et al. (2017) ; Zhang et al. (2017) ). In general, new models tend to gain more speedup than accelerating pre-trained models. However, constructing a new CNN from scratch might be difficult without using a large amount of computing resources.

In our approach, we aim at accelerating existing CNNs using the low rank approximation that a specific tensor can be represented with several simpler tensors. Jaderberg et al. (2014) has shown the redundancies in convolutional layers can be substituted by lower rank filters with the 4.5× speedup in a text recognition application using a simple four layer CNN. Denton et al. (2014) has presented a different low-rank decomposition and clustering approach. They reported the 2× speedup on the first layer of a 15-layer CNN for image classification. They also found that the low rank approximation has the potential to improve the generalization ability of the CNN.

Our work was inspired by Lebedev et al. (2014) which adopted the CP-ALS, one of the popular CP decomposition algorithms (Kolda & Bader (2009) ). However, only one layer in the network was decomposed. They also observed the instability problem which causes fine-tuning the decomposed networks a difficult problem. Later, Kim et al. (2015) successfully decomposed the whole network with the Tucker Decomposition (Kolda & Bader (2009) ). Zhang et al. (2016) took the nonlinear unit into account to obtain the decomposed filters and reduced the accumulated error. Their nonlinear asymmetric 3d reconstruction, combined with the technique in Jaderberg et al. (2014) to further decomposing spatial dimension, achieved the 5× speedup with the accuracy loss of 2% for VGG16. An additional fine-tuning was applied to improve the loss to 1%.

In Astrid & Lee (2017) , the iterative fine-tune has been proposed to overcome the CP instability. Instead of the decomposition of the entire network, each iteration decomposes one layer with the fine-tuning of the whole network. Their attempt gradually transforms the dense network into decomposed form layer by layer, which achieves the less accuracy drop. We also adopt and improve this concept to further improve the performance, which will be discussed later in 2.1.3.

1.2. CONTRIBUTIONS:

Our contributions include the following:

• The proposed two-pass decomposition can prevent from possible instability of CPdecomposition and improve the accuracy effectively. Training and fine-tuning can be done with vanilla parameter setting (e.g., learning rate). • Our iterative flow helps the decomposition of a deeper network in a systematic manner. The rank selection algorithm can be utilized to determine the target ranks for CP-decomposition.

The proposed approach can be applied to different kinds of deep convolutional networks, resulting in a general technique to improve the existing models. Our experiment shows that we can achieve the 6.2× speedup for VGG16 (Simonyan & Zisserman (2014) ) while with the classification accuracy loss of only 1.2% on ImageNet 2012 validation set. The size of the convolutional layers can be reduced by 85% as well. In addition, our approach can also speed up ResNet50 (He et al. (2015) ) by 1.35× faster with the accuracy loss of 1.51%, and the model size reduction of 48%.

1.3. LOW RANK APPROXIMATION:

In this section, we introduce the low rank approximation to accelerate convolutional layers with the CANDECOMP/PARAFAC (CP) decomposition technique (Kiers (2000) ; Kolda & Bader (2009) ).

1.3.1. CP DECOMPOSITION FOR CONVOLUTIONAL LAYERS:

The CP decomposition factorizes the tensors into a sum of series rank-one tensors. Assume W is a third-order tensor and a r , b r , c r for r = 1, . . . , R are vectors. A rank R decomposition can be expressed as

EQUATION

where

W ∈ R H×I×J , a r ∈ R H , b r ∈ R I , c r ∈ R J for r = 1, . . . , R, as shown in Figure 1.

In the case of CNNs, the filters are fourth-order tensors in general. Assume W is a fourth-order tensor and a r , b r , c r , d r for r = 1, . . . , R are vectors. A rank R decomposition can be expressed as follows:

EQUATION

where Let X be the input features, Y be the output features, W be the filter weights and

W ∈ R Cin×W f ×H f ×Cout , a r ∈ R Cin ,b r ∈ R W f , c r ∈ R H f and d r ∈ R Cout for r = 1, . . . , R.

x * = W f -1 2 , y * = H f -1

2 . Assume W f and H f are both odd numbers. A convolutional layer with C in input channels, C out output channels and filter shape of W f × H f , can be expressed as

Y (x, y, k) = Cin h=1 W f i=1 Hin j=1 W (h, i, j, k)X(i + x -x * , j + y -y * , h).

(3)

Then the weights in Eq. 3 can be substituted with the decomposed tensors in Eq. 2, i.e.,

EQUATION

Equation 5 can be rewritten as follows:

EQUATION

EQUATION

EQUATION

EQUATION

Y (1) and Y (4) perform the 1×1 convolutions on the input and output channels, respectively. In addition, Y (2) and Y (3) perform the depth-wise convolutions along the filters' width and height direction, respectively, as shown in Figure 3 . Therefore, the four layers can be applied to substitute the original convolution layer. 

C out C in (W f ×H f ×C in )×C out × C out

1.3.2. THE COMPLEXITY AND SPEEDUP:

Assume the size of the input features is W in × H in × C in , where W in and H in are the width and height of the features, and C in is the number of input channels. Let the number of output channels be C out , the filter shape be W f ×H f , and the stride be 1. The complexity of the original convolution is

EQUATION

O(C in W in H in C out W f H f ) from Eq. 3.

If the convolution layer is decomposed with Eq. 6-9, the complexity becomes

O(W in H in R(C in + W f + H f + C out )). The speedup of decomposing the single convolutional layer with rank R is O( C in W in H in C out W f H f W in H in R(C in + W f + H f + C out ) ) = O( C in C out W f H f R(C in + W f + H f + C out )

).

(10)

While substituting a layer, the smaller the rank R for the decomposed layers, the higher the speedup.

1.3.3. THE CP INSTABILITY:

As Lebedev et al. (2014) mentioned, training the network with CP decomposition may suffer from the instability problem that leads to the gradient explosion. The small learning rate is used to cope with the problem. In addition, part of the decomposed layer is fixed for training. However, with a small learning rate, the accuracy may improve slowly for decomposing deeper networks. Fixing decomposed layers also makes the accuracy hard to improve because only a few parameters could be fine-tuned.

2. PROPOSED FLOW OF ACCELERATING CNNS:

In this section, we present the Two-Pass Decomposition to avoid the CP Instability. In addition, the Iterative Two-Pass Decomposition flow can be applied to improve the accuracy loss when accelerating the deeper networks.

2.1. TWO-PASS DECOMPOSITION:

Our two-pass decomposition consists of four steps to compute the decomposed layer.

Step 1: The 1 st Decomposition: Apply the CP decomposition on the original filter tensor to get the decomposed tensor. In this work, we adopt the CP-ALS algorithm in Kolda & Bader (2009) .

Step 2: Restoration: Restore the decomposed tensor back to the dense form.

Step 3: Optimization: Replace the original filter tensor with the restored filter tensor in the target convolutional layer. Optimize the updated networks with fine-tuned filter weights.

Step 4: The 2 nd Decomposition: Decompose the optimized filter tensor again.

The concept to restore the decomposed tensor back to the dense form is to prevent from the CP instability. We observed that if the network is trained in the restored dense form, the training result can be more stable because of its smoother convex. In addition, the structure of the restored dense form tends to be closer to the second low rank form, which also leads to a less decomposition error.

Figure 4 compares the accuracy between our two-pass decomposition and the original CP-ALS decomposition of VGG16. The CNN layers from Conv1 2 to Conv3 1 are evaluated, with Conv1 2 to Conv2 2 decomposed and fixed. The first layer, Conv1 1, is not computationally intensive and not decomposed. The ranks of Conv1 2 Conv2 1, and Conv2 2 are 24, 25, and 28, respectively. In this experiment, different ranks of Conv3 1 are applied to observe the accuracy change. The comparison shows that the two-pass CP decomposition retains the relatively high accuracy even with smaller ranks, i.e., the ranks of 24 and 32 in the figure. On the contrary, with the original CP decomposition, the accuracy drops significantly when decreasing the rank. Such result leaves our two-pass CP decomposition more room to speed up the network with lower ranks while maintaining the accuracy. 

2.1.1. PROPOSED ITERATIVE TWO-PASS DECOMPOSITION FLOW FOR DNNS:

Traditionally, the filter weights of the decomposed layers are fixed during the fine-tuned phase to prevent from the gradient explosion. Our two-pass decomposition provides the better result as compared with the original CP decomposition. However, the accuracy will still degrade for decomposing the deeper networks, since there will be little room for fine-tuning.

For a DNN with many convolution layers, we propose the Rank Selection algorithm to effectively determine the rank for each layer. Then our two-pass decomposition technique is applied iteratively to one group of the layers at a time. The overall flow to decompose the whole CNN is shown in Figure 5 .

For the decomposition, target rank of each layer is a hyperparameter to decide. Our flow takes a given set of ranks as the input to perform the initial decomposition. After the initial decomposition, the fitness of each decomposed layer can be calculated. Based on the initial ranks and corresponding fitnesses, we propose the Rank Selection algorithm to optimize the target ranks for the decomposition, which will be discussed in Sec. 2.1.2.

The second part of the flow performs the two-pass decomposition iteratively, by grouping the CNN layers. At the end of each iteration, the whole network will be fine-tuned with the decomposed layers fixed. The accuracy of the fine-tuning can be further improved with a few more epochs until the loss is converged. The details will be discussed in Sec. 2.1.3.

Initial:



Rank Rank Selection Two-Pass Decomposition Decomposition:

Selected Rank

Compressed Network:



Iterative Two-Pass Decomposition:



Fine-tune:



Fitness:

Figure 5 : The proposed iterative two-pass decomposition flow.

2.1.2. OUR RANK SELECTION ALGORITHM:

Given any initial ranks for the CNN and a target speedup, the proposed Rank Selection algorithm determines the optimized rank configuration. Let N l denote the operation complexity of the l th layer in the CNN, and N l be its complexity of the decomposed form with the rank of R l . Therefore,

N l = C (l) in W (l) in H (l) in C (l) out W (l) f H (l) f and N l = W (l) in H (l) in R l (C (l) in + W (l) f + H (l) f + C (l)

out ) (see Sec. 1.3.2). The overall theoretical speedup S of the CNN can be defined as

EQUATION

CP-ALS decomposition in Nickel ( 2016) is adopted for our approach. According to Kolda & Bader (2009) ; Nickel (2016) , the fitness (as the decomposition quality) of a convolutional layer can be defined as

F l = 1 - X l -X l 2 X l 2 (12)

where X l is the original tensor of the l th layer and X l is the approximated tensor.

The product of the fitness F l and the operation complexity N l is used to estimate the profit to improve a specific layer l. If a layer has higher fitness and complexity, we tend to reduce its rank for the speedup. Otherwise, its ranks can be increased for the accuracy. Algorithm 1 shows the proposed Rank Selection to help determine the optimized rank configuration. Note that the CP decomposition with a large rank is time-consuming. So a linear approximation is used to predict the fitness in this stage.

Algorithm 1 Rank Selection Input: R l , F l , N l , N l for l ∈ all convolutional layers, S target : target speedup, : speedup margin Output: Selected Ranks for each layer

1: Calculate Initial Speedup S 2: while |S -S target | > do 3: if S < S target then 4:

Let T be the layer with the largest F T × N T among all layers for the speedup.

5:

F T = F T × (R T -1) R T

Linear approximation of the new fitness.

6:

R T = R T -1 7: else 8:

Let T be the layer with the smallest F T × N T among all layers for the accuracy. 9:

F T = F T × (R T +1) R T

Linear approximation of the new fitness. Update N l , S 13: end while

2.1.3. ITERATIVE TWO-PASS DECOMPOSITION FLOW:

To prevent from the accuracy degradation, our two-pass decomposition approach can be performed iteratively, based on the concept from Astrid & Lee (2017) . Figure 6 illustrates the three iterations applied to VGG16 model. Each iteration consists of five steps. The first four steps perform the proposed two-pass decomposition of the target group. E.g., the group of Conv1 2, Conv2 1, Conv2 2 is decomposed and restored back to the dense form in the first iteration (see Figure 6 ). Then the whole network is fine-tuned to optimize the weights. Afterward, the three target layers are decomposed again. In the fifth step, the whole network is fine-tuned again with these decomposed layers fixed. This additional step can improve the degraded accuracy further.

The second iteration deals with the group of Conv3 1, Conv3 2, and Conv3 3. Note that the previously decomposed layers remain fixed in the Optimization and Fine-tuning steps. The process continues until all the target layers are decomposed.

3. EXPERIMENTAL RESULTS AND DISCUSSIONS:



3.1. DECOMPOSING VGG16:

The VGG16 model modified from machrisaa ( 2016) is applied to verify our iterative two-pass decomposition flow. ImageNet 2012 training set is used for training and the validation set is used highest measured speedup with the lowest accuracy drop among the works utilizing decomposition techniques, as shown in Table 5 . Note that the asymmetric 3d approach in Zhang et al. (2016) results in a 2.0% accuracy drop. An additional fine-tuning is explicitly applied to meet the final 1.0% accuracy drop with 5 more epochs and the learning rate of 10 -5 . Our method only relies on vanilla fine-tuning to reach the low accuracy drop. The learning rate we used is 10 -3 .

The CP decomposition can also compress the filter size effectively. With the Rank-Selection configuration, our approach reduces 85% of the convolutional layers (from 57MB to 8.3MB). However, due to the large size of fully connected layers (about 470MB) in VGG16, the overall reduction of the entire networks is 9% (from 528MB to 480MB) after the two-pass decomposition flow. 

3.2. DECOMPOSING RESNET50:

The deeper CNN, ResNet50, is also evaluated. The accuracy of the pre-trained model which is modified from ethereon ( 2016) is 92.02% with the same training environment of the previous experiment, except for the learning rate of 10 -5 .

In this experiment, the 1×1 convolutional layers are excluded for the decomposition. The initial rank is set to 50 for all target layers. The result of our iterative decomposition is shown in Table 6 . Each iteration is trained with one epoch. After the iterative two-pass decomposition, the measured speedup is 1.35× and the model size reduces by 48% (98MB→51MB). Astrid & Lee (2017) suggests that freezing layers make the fine-tuning greedy, which might cause the optimization to be stuck in a local minimal. However, our approach works efficiently by iteratively decomposing a group of layers with previously layers frozen. The attempt also makes the optimization converge faster and prevents from the gradient explosion.

Our first evaluation in Table 3 shows that the In-Order grouping scheme performs better in a typical training and fine-tuning, especially for the Baseline rank configuration. The In-Order scheme may be suitable for the decomposition with smaller rank configuration. Because the Fitness-Based approach decomposes those layers of smaller ranks first. But it also makes the accuracy drop quickly in the former layers of small ranks.

For the Rank-Selection configuration, the Fitness-Based scheme does not lead to a significant accuracy drop due to the relatively higher ranks and fitnesses. The layers of lower fitness are decomposed first. Their accuracy drop can be compensated by fine-tuning the latter layers with higher fitness. The result in Table 4 also shows that a better accuracy drop may be achieved with a proper convergence constraint.

4. CONCLUSION:

The iterative two-pass decomposition flow has been presented to accelerate existing deep CNNs. Our two-pass decomposition effectively prevents from the CP instability. The Rank Selection algorithm provides the fine-grained rank configuration to achieve the target speedup while maintaining the accuracy. The experiment results show that VGG16 can be accelerated by 6.2 times with the accuracy drop of only 1.20% and the size reduction of 85%. In addition, ResNet50 can be speeded up by 1.35 times with the accuracy drop of 1.51% and the size reduction of 48%.

The future works include the improvement of the grouping scheme and the decomposing order, and a smarter rank selection with non-linear fitness estimation. In addition, accelerating 1×1 convolutional layers will also be considered for the further improvement on the advanced CNNs.

:



Figures and Tables:

Figure 1: The CP decomposition.

Figure 2: The original convolution.

Figure 3: The decomposed convolution.

Figure 4: The comparison between the two-pass decomposition and the original CP decomposition, with 500 batches.

Accuracy comparison among different configurations for VGG16 (%).

Table content: <table><tr><td/><td/><td colspan="2">Iteration 1</td><td colspan="2">Iteration 2</td><td colspan="2">Iteration 3</td></tr><tr><td/><td/><td colspan="6">Optimize Fine-tune Optimize Fine-tune Optimize Fine-tune</td></tr><tr><td>Baseline</td><td>In-Order</td><td>88.76</td><td>88.74</td><td>85.34</td><td>84.54</td><td>80.62</td><td>80.06</td></tr><tr><td/><td>Fitness-Based</td><td>85.59</td><td>85.06</td><td>82.55</td><td>82.34</td><td>80.75</td><td>70.34</td></tr><tr><td>Rank Selection</td><td>In-Order Fitness-Based</td><td>90.05 89.11</td><td>90.04 88.97</td><td>89.17 88.52</td><td>89.08 88.44</td><td>88.25 88.13</td><td>88.12 87.95</td></tr></table>

Comparison of the accuracy drop among different configurations with the convergence constraint for VGG16 (%).

Table content: <table><tr><td/><td/><td colspan="2">Iteration 1</td><td colspan="2">Iteration 2</td><td colspan="2">Iteration 3</td></tr><tr><td/><td/><td colspan="6">Optimize Fine-tune Optimize Fine-tune Optimize Fine-tune</td></tr><tr><td>In-Order (rs)</td><td>Accuracy Drop Epochs</td><td>-0.15 1</td><td>-0.14 1</td><td>0.47 4</td><td>0.57 2</td><td>1.48 1</td><td>1.59 1</td></tr><tr><td>Fitness-Based (rs)</td><td>Accuracy Drop Epochs</td><td>0.32 8</td><td>0.44 2</td><td>0.97 1</td><td>1.04 1</td><td>1.17 2</td><td>1.20 2</td></tr></table>

Comparison among different works.

Table content: <table><tr><td>Method</td><td colspan="2">Actual Speedup Accuracy Drop (%)</td></tr><tr><td>Jaderberg et al. (2014) (reported in Zhang et al. (2016))</td><td>4×</td><td>9.70%</td></tr><tr><td>Zhang et al. (2016)</td><td>4×</td><td>3.84%</td></tr><tr><td>Zhang et al. (2016) 3d</td><td>5×</td><td>2.00%</td></tr><tr><td>Zhang et al. (2016) 3d (fine-tuned)</td><td>5×</td><td>1.00%</td></tr><tr><td>In-Order (rs)</td><td>6.2×</td><td>1.59%</td></tr><tr><td>Fitness-Based (rs)</td><td>6.2×</td><td>1.20%</td></tr></table>

Accuracy of ResNet50 using the iterative two-pass decomposition (%)

Table content: <table><tr><td>Accuracy</td><td colspan="6">Iteration 1 Optimize Fine-tune Optimize Fine-tune Optimize Fine-tune Iteration 2 Iteration 3</td></tr><tr><td>In-Order</td><td>91.40</td><td>91.42</td><td>90.84</td><td>90.90</td><td>90.32</td><td>90.51</td></tr><tr><td>3.3 DISCUSSION</td><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2018):
 General comment ============== Low-rank decomposing convolutional filters has been used to speedup convolutional networks at the cost of a drop in prediction performance. The authors a) extended existing decomposition techniques by an iterative method for decomposition and fine-tuning convolutional filter weights, and b) and algorithm to determine the rank of each convolutional filter. The authors show that their method enables a higher speedup and lower accuracy drop than existing methods when applied to VGG16. The proposed method is a useful extension of existing methods but needs to evaluated more rigorously. The manuscript is hard to read due to unclear descriptions and grammatical errors. Major comments ============= 1. The authors authors showed that their method enables a higher speedup and lower drop in accuracy than existing methods when applied to VGG16. The authors should analyze if this also holds true for ResNet and Inception, which are more widely used than VGG16. 2. The authors measured the actual speedup on a single CPU (Intel Core i5). The authors should measure the actual speedup also on a single GPU. 3. It is unclear how the actual speedup was measured. Does it correspond to the seconds per update step or the overall training time? In the latter case, how long were models trained? 4. How and which hyper-parameters were optimized? The authors should use the same hyper-parameters for all methods (Jaderberg, Zhang, Rank selection). The authors should also analyze the sensitivity of speedup and accuracy drop depending on the learning rate for ‘Rank selection’. 5. Figure 4: the authors should show the same plot for more convolutional layers at varying depth from both VGG and ResNet. 6. The manuscript is hard to understand and not written clearly enough. In the abstract, what does ‘two-pass decomposition’, ‘proper ranks’, ‘the instability problem’, or ‘systematic’ mean? What are ‘edge devices’, ‘vanilla parameters’? The authors should also avoid uninformative adjectives, clutter, and vague terms throughout the manuscript such as ‘vital importance’ or ‘little room for fine-tuning’. Minor comments ============= 1. The authors should use ‘significantly’ only if a statistical hypothesis was performed. 2. The manuscript contains several typos and grammatical flaws, e.g. ‘have been widely applied to have the breakthrough’, ‘The CP decomposition factorizes the tensors into a sum of series rank-one tensors.’, ‘Our two-pass decomposition provides the better result as compared with the original CP decomposition’. 3. For clarity, the authors should express equation 5 in terms of Y_1, Y_2, Y_3, and Y_4. 4. Equation 2, bottom: C_in, W_f, H_f, and C_out are undefined at this point.