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):
 * Paper Summary This paper addresses the problem of learning a low rank tensor filter operation for filtering layers in deep neural networks (DNNs). It makes use of the CP or rank-1 tensor decomposition to define the meaning of rank for a tensor. When a tensor is decomposed as a sum of rank-1 tensors (outer products), the number of operations in a DNN forward pass decreases leading to a faster testing runtime. This form of network compression has been worked on before. The contribution of this paper seems to be the specific way the decomposition is used in training the DNN. It seems that this training process follows a projected gradient descent procedure, where the filter weights of the network are iteratively updated using regular (stochastic) gradient descent and then they are projected onto the set of rank-R tensors. The authors devise a heuristic way (based on an innovated measure that combines computational complexity with performance) to select the tensor rank to be used. Experiments are conducted on the task of image classification for a couple well-known DNN architectures (VGG and Resnet) to show a speedup of runtime in testing, significant compression of the network, and minimal degradation in performance. * Related Work The authors do a good job describing and listing the papers most related to the current submission. * Technical Novelty One main limitation of the paper is the lack of technical contribution. The idea of using rank-1 tensor decomposition for training low-rank filtering operations in DNNs has already been proposed and used in several other work. From what I understood from the paper, the only technical contribution is the use of a so called 2-pass decomposition, which is simply an implementation of projected gradient descent on the set of rank-R tensors. In particular, if we seek to minimize f(W) such that W belongs to asset that can be easily projected on, then projected gradient descent would apply traditional gradient descent on the current iterate, followed by a projection step onto this set. This paper seems to be applying this exact same strategy in training for a cross-entropy classification loss f(.). This iterative projection tends to perform better than iteratively optimizing f(W) and then applying the projection step only once at the very end of the optimization (assumedly the CP-ALS method that is used for comparison). Put in this light, the proposed paper does not contribute much. * Paper Presentation In the reviewer’s opinion, the primary limitation of the paper is how it is written and organized. The paper is badly written. It is riddled with grammar, choice of word, and spelling mistakes. The paper organization needs to be revamped with emphasis on the proposed ideas of the paper and how it differs from the rich related work. These issues make the paper hard to read. For example, the authors spend quite a bit of space focusing on the rank-1 (CP) decomposition, which is well known, as opposed to focusing on the merits of their technical contributions. Also, the experiments are not clearly explained. It is hard to understand the experimental setup of each experiment and what the conclusions are. For example, it is unclear whether the baseline in Table 3 also uses the two-pass decomposition or not. Also, the authors should provide a clear and standard description of the experimental setup for each experiment (e.g. which network, which dataset, which task/loss, which measure, etc.). * Experimental Results From what I understood from the experiments, it seems that using the “two-pass decomposition” (i.e. projected gradient descent) is better than CP-ALS (gradient descent ended with a single projection step). This conclusion seems to be intuitive and expected. However, as mentioned earlier, the paper writing and organization makes it hard to understand what exactly is being shown. For example, Table 1 shows that the baseline method uses less filters than the proposed method that selects the number of filters through an innovated heuristic measure. Then in Table 3, we see that the baseline is less stable (i.e. its performance decreases across the different iterations of projected gradient descent). Isn’t this expected since the baseline uses less filters? It is unclear from the text if this is the case. The authors should do a better job explaining and comparing the overall experimental results. For example, it seems that the proposed projected gradient descent method leads to better speedup results in VGG as opposed to Resnet, with very similar reduction in accuracy. The authors do not comment on this. It would be nice for them to explain the circumstances under which the proposed method is best suited and any potential failure cases (e.g. cases when the low-rank decomposition leads to a significant decrease in performance). All of this analysis provided more insight into the method and helps the reader understand its extents.