Title: TERNARY WEIGHT DECOMPOSITION AND BINARY AC-TIVATION ENCODING FOR FAST AND COMPACT NEU-RAL NETWORK

Abstract: This paper aims to reduce test-time computational load of a deep neural network. Unlike previous methods which factorize a weight matrix into multiple real-valued matrices, our method factorizes both weights and activations into integer and noninteger components. In our method, the real-valued weight matrix is approximated by a multiplication of a ternary matrix and a real-valued co-efficient matrix. Since the ternary matrix consists of three integer values, {-1, 0, +1}, it only consumes 2 bits per element. At test-time, an activation vector that passed from a previous layer is also transformed into a weighted sum of binary vectors, {-1, +1}, which enables fast feed-forward propagation based on simple logical operations: AND, XOR, and bit count. This makes it easier to deploy a deep network on low-power CPUs or to design specialized hardware.
In our experiments, we tested our method on three different networks: a CNN for handwritten digits, VGG-16 model for ImageNet classification, and VGG-Face for large-scale face recognition. In particular, when we applied our method to three fully connected layers in the VGG-16, 15× acceleration and memory compression up to 5.2% were achieved with only a 1.43% increase in the top-5 error. Our experiments also revealed that compressing convolutional layers can accelerate inference of the entire network in exchange of slight increase in error.

:

It is widely believed that deeper networks tend to achieve better performance than shallow ones in various computer vision tasks. As a trade-off of such impressive improvements, deeper networks impose heavy computational load both in terms of processing time and memory consumption due to an enormous amount of network parameters. For example, VGG-16 model (Simonyan & Zisserman, 2015) requires about 528 MBytes to store the network weights where fully connected layers account for 89% of them. A large number of multiplications and additions must also be processed at each layer which prevent real-time processing, consume vast amounts of electricity, and require a large number of logic gates when implementing a deep network on a FPGA or ASIC. This article addresses the above issues. Specifically, we aimed to reduce the test-time computational load of a pre-trained network. Since our approach does not depend on a network configuration (e.g. a choice of an activation function, layer structures, and a number of neurons) and acts as a post-processing of network training, pre-trained networks shared in a download site of MatConvNet (Vedaldi & Lenc, 2015) and Model Zoo (BVLC) can be compressed and accelerated. Our method is outlined in Figure 1 . The main idea is to factorize both weights and activations into integer and non-integer components. Our method is composed of two building blocks, as shown below.

Ternary weight decomposition for memory compression: We introduce a factored representation where the real-valued weight matrix is approximated by a multiplication of a ternary basis matrix and a real-valued co-efficient matrix. While the ternary basis matrix is sufficiently informative to reconstruct the original weights, it only consumes 2 bits per element. The number of rows of the coefficient matrix is also smaller than that of the original weight matrix. These compact representations result in efficient memory compression.

Binary activation encoding for fast feed-forward propagation: It has been reported that an inner product between a ternary and binary vector can be computed extremely fast by using three logical operations: AND, XOR, and bit count (Ambai & Sato, 2014) . To use this technique, we approximate the activation vector by a weighted sum of binary vectors. This binary encoding must be processed as fast as possible at test-time. To overcome this issue, we use a fast binary encoding method based on a small lookup table.

1.1. RELATED WORK:

There have been extensive studies on accelerating and compressing deep neural networks, e.g., on an FFT-based method (Mathieu et al., 2014) , re-parameterization of a weight matrix (Yang et al., 2015) , pruning network connection (Han et al., 2015; 2016) , and hardware-specific optimization (Vanhoucke et al., 2011) . In the following paragraphs, we only review previous studies that are intimately connected to ours.

It was pointed out by Denil et al. (2013) that network weights have a significant redundancy. Motivated by this fact, researchers have been involved in a series of studies on matrix/tensor factorization (Jaderberg et al., 2014; Zhang et al., 2015) . In these studies, a weight matrix (or tensor) was factorized by minimizing an approximation error of original weights or activations. Jaderberg et al. (2014) exploited 1-D separable filter decomposition to accelerate feed-forward propagation. Zhang et al. (2015) proposed low-rank approximation based on generalized SVD to compress an entire deep network. Taking into account the lessons learned from these best practices, we also exploit the redundancy of the weights.

There is an another series of studies, integer decomposition (Hare et al., 2012; Yuji et al., 2014; Ambai & Sato, 2014) , which involved accelerating test-time speed of a classifier by using fast logical operations. Although their contributions are limited to a shallow architecture such as a linear SVM, they achieved a noticeable acceleration. In these approaches, a real-valued weight vector is approximated by a weighted sum of a few binary or ternary basis vectors. To use fast logical operations, they extracted binary features from an image. Hare et al. (2012) and Yuji et al. (2014) exploited binary basis vectors, and Ambai & Sato (2014) investigated a case of ternary basis to improve approximation quality.

In a manner of speaking, our method is a unified framework of matrix/tensor factorization and integer decomposition reviewed in the above and inherits both their advantages. While the weight matrix is factorized to exploit low-rank characteristics, the basis matrix is restricted to take only three integer values, {-1, 0, +1}. In contrast to recent binary weighted networks such as XNOR-Net (Rastegari et al., 2016) which quantizes both activations and weights during backpropagation, it is not necessary for our method to change training algorithms at all. We can benefit from recent sophisticated training techniques, e.g. batch normalization (Ioffe & Szegedy, 2015) , in combination with our method. Furthermore, our method does not need (iterative) end-to-end retraining which is needed for several previous studies such as network pruning (Han et al., 2015; 2016) and distillation (Hinton et al., 2014) .

2. NETWORK COMPRESSION MODEL:

In this section, we introduce our compression model and discuss time and space complexity. We consider a convolutional layer with a filter size of w x × w y × c, where w x and w y are the spacial size and c is a number of input channels. If w x = w y = 1, we can regard this layer as a fully connected layer. This three dimensional volume is reshaped to form a D I dimensional vector where D I = w x × w y × c. The filter weights and biases can be formulated by W ∈ R D I ×D O and b ∈ R D O , where D O is a number of output channels. Let x ∈ R D I denote an activation vector obtained by 

D I D O 0 0 0 proposed (C w M w M x c x ) k x k w + k w D O (D I k x k w )/B (D I k x k w )/B (D I k x k w )/B

C w c x , b x size (bits) 32 • D I D O 2 • D I k w 32 • k w D O 32 • (k x + 1)

vectorizing the corresponding three dimensional volume. In test-time, we need to compute W x + b followed by a non-linear activation function.

In our compressed network, W is decomposed into two matrices before test-time as follows:

EQUATION

where

M w ∈ {-1, 0, +1} D I ×kw is a ternary basis matrix, C w ∈ R kw×D O is a co-efficient matrix,

and k w is the number of basis vectors, respectively. Since M w only takes the three values, it consumes only 2 bits per element. Setting a sufficiently small value to k w further reduces total memory consumption. From the viewpoint of approximation quality, it should be noted that a large number of elements in W takes close to zero values. To fit them well enough, a zero value must be included in the basis. The ternary basis satisfies this characteristic. In practice, the ternary basis gives better approximation than the binary basis, as we discuss in Section 3.

The activation vector x is also factored to the following form:

EQUATION

where M x ∈ {-1, +1} D I ×kx is a binary basis matrix, c x ∈ R kx is a real-valued co-efficient vector, b x ∈ R is a bias, and k x is the number of basis vectors, respectively. Since elements of x are often biased, e.g., activations from ReLU take non-negative values and have a non-zero mean, b x is added to this decomposition model. While c x and b x reflect a range of activation values, M x determines approximated activation values within the defined range. This factorization must be computed at test-time because the intermediate activations depend on an input to the first layer. However, in practice, factorizing x into M x , c x , and b x requires an iterative optimization, which is very slow. Since a scale of activation values within a layer is almost similar regardless of x, we pre-computed canonical c x and b x in advance and only optimized M x at test-time. As we discuss in Section 4, an optimal M x under fixed c x and b x can be selected using a lookup table resulting in fast factorization.

Substituting Eqs.( 1) and ( 2) into W x + b, approximated response values are obtained as follows:  and b x are fixed at test-time. It should be noted that M w M x is a multiplication of the ternary and binary matrix, which is efficiently computable using three logical operations: XOR, AND, and bit count, as previously investigated (Ambai & Sato, 2014) . After computing M w M x , the two co-efficient components, c x and C w , are multiplied from the right and left in this order. Since c x and C w are much smaller than W, the total number of floating point computations is drastically reduced.

W x + b ≈ (M w C w ) (M x c x + b x 1) + b = C w M w M x c x + b x C w M w 1 + b. (3) A new bias b x C w M w 1 + b in Eq.(3) is pre-computable in advance, because C w , M w ,

The time and space complexity are summarized in Tables 1 and 2 . As can be seen from Initialize

m (i)

w by three random values {-1, 0, +1}.

4: Minimize ||R -m (i) w c (i)

w || 2 F by repeating the following two steps until convergence.

5:

[Step 1] c (i) w ← m (i) w R/m (i) w m (i) w 6: [Step 2] m ij ← arg min α∈{-1,0,+1} ||r j -αc (i) w || 2 2 , for j = 1, • • • , D I 7: R ← R -m (i) w c (i) w 8: end for 3 TERNARY WEIGHT DECOMPOSITION

To factorize W, we need to solve the following optimization problem.

EQUATION

However, the ternary constraint makes this optimization very difficult. Therefore, we take an iterative approach that repeats rank-one approximation one by one, as shown in Algorithm 1. Let m

(i) w ∈ {-1, 0, +1} D I ×1 denote an i-th column vector of M w and c (i)

w ∈ R 1×D O denote an i-th row vector of C w . Instead of directly minimizing Eq. ( 4), we iteratively solve the following rank-one approximation,

EQUATION

where R is a residual matrix initialized by W. We applied alternating optimization to obtain m

EQUATION

w can be updated using a least squares method, as shown in line 5 of Algorithm 1. If c

(i) w is fixed, m ij , the j-th element of m (i)

w , can be independently updated by exhaustively verifying three choices {-1, 0, +1} for each j = 1, • • • , D I , as shown in line 6 of Algorithm 1, where r j is a j-th row vector of R. After the alternating optimization is converged, R is updated by subtracting m

(i) w c (i)

w and passed to the next (i + 1)-th iteration. Comparison of binary constraints with ternary constraints can be seen in Appendix A.

4. BINARY ACTIVATION ENCODING:

Binary decomposition for a given activation vector x can be performed by minimizing

EQUATION

)

In contrast to the case of decomposing W, a number of basis vectors k x can be set to a very small value (from 2 to 4 in practice) because x is not a matrix but a vector. This characteristic enables an exhaustive search for updating M x . Algorithm 2 is an alternating optimization with respect to M x , c x , and b x . By fixing M x , we can apply a least squares method to update c x and b x (in lines 3-4 of Algorithm 2). If c x and b x are fixed, m

x , the j-th row vector of M x , is independent of any other m (j )

x , j = j. We separately solve D I sub-problems formulated as follows:

EQUATION

where x j is a j-th element of x. Since k x is sufficiently small, 2 kx possible solutions can be exhaustively verified (in line 5 of Algorithm 2).

Our method makes this decomposition faster by pre-computing canonical c x and b x from training data and only optimizing M x at test-time using lookup table. This compromise is reasonable because of the following two reasons: (1) scale of activation values is similar regardless of vector elements 3:

[

Step 1] Update c x and b x using a least squares method.

4:

c x ← (M x M x ) -1 M x (x -b x 1), b x ← 1 (x -M x c x )/D I 5: [Step 2] Update m (j)

x for each j = 1, • • • D I by an exhaustive search that minimizes Eq.( 7).

within a layer, and (2) c x and b x reflect a scale of approximated activation values. Knowing these properties, c x and b x are obtained by minimizing J x ( Mx , c x , b x ; x) ,where x is constructed as follows. First, N T different activation vectors T ∈ {x i } N T i=1 are collected from randomly chosen N T training data. Second, n elements are randomly sampled from x i . The sampled nN T elements are concatenated to form a vector x ∈ R nN T . We use c x and b x as constants at test-time, and discard Mx .

At test-time, we only need to solve the optimization of Eq. ( 7) for each x j . This can be regarded as the nearest neighbour search in one-dimensional space. We call βc x + b x a prototype. There are 2 kx possible prototypes because β takes 2 kx possible combinations. The nearest prototype to x j and an optimal solution m (j)

x can be efficiently found using a lookup table as follows.

Preparing lookup table : We define L bins that evenly divide one-dimensional space in a range from the smallest to largest prototype. Let xl denote a representative value of the l-th bin. This is located at the center of the bin. For each xl , we solve Eq. ( 7) and assign the solution to the bin.

Activation encoding: At test-time, x j is quantized into L-levels. In other words, x j is transformed to an index of the lookup table. Let p max and p min denote the largest and smallest prototype, respectively. We transform x j as follows: q = (L -1)(x j -p min )/(p max -p min ) + 1, (8) l = min(max( q + 1/2 , 1), L).

(9)

The range from p min to p max is linearly mapped to the range from 1 to L by Eq. ( 8). The term q is rounded and truncated from 1 to L by the max and min function in Eq. ( 9). If L is sufficiently large, the solution assigned to the l-th bin can be regarded as a nearly optimal solution because the difference between x j and the center of the bin xl becomes very small. We found that L = 4096 is sufficient. The time complexity of this encoding is O(D I ).

5. EXPERIMENTS:

We tested our method on three different convolutional neural networks: CNN for handwritten digits (LeCun et al., 1998) , VGG-16 for ImageNet classification (Simonyan & Zisserman, 2015) , and VGG-Face for large-scale face recognition (Parkhi et al., 2015) . To compute memory compression rate, a size of W and a total size of M w and C w were compared. To obtain a fair evaluation of computation time, a test-time code of forward propagation was implemented without using any parallelization scheme, e.g., multi-threading or SIMD, and was used for both compressed and uncompressed networks. The computation time includes both binary activation encoding and calculation of Eq. ( 3).

We used an Intel Core i7-5500U 2.40-GHz processor.

5.1. CNN FOR HANDWRITTEN DIGITS:

MNIST is a database of handwritten digits which consists of 60000 training and 10000 test sets of 28 × 28 gray-scale images with ground-truth labels from 0 to 9. We trained our CNN by using an example code in MatConvNet 1.0-beta18 (Vedaldi & Lenc, 2015) . Our architecture is similar to LeNet-5 (LeCun et al., 1998) but has a different number of input and output channels. Each layer's configuration is shown below: where the parameters of a convolutional layer are denoted as (conv<receptive field size>-<number of output channels>), and parameters of a fully connected layer are denoted as (fc<number of input channels>-<number of output channels>). The (maxpool) is 2 × 2 subsampling without overlapping.

EQUATION

The error rate of this network is 0.86%.

We applied our method to the first fully connected layer (fc1024-640) and set n = 10 and N T = 1000 to learn c x and b x from randomly chosen nN T activations. The cases of k x = 1, 2, 3, 4 and

k w = D O , D O /2, D O /5

were tested. This means that k w was set to 640, 320, and 128.

Figures 2(a ) and (b) show the relationships among the increases in error rates, memory compression rates, and acceleration rates. It was observed that error rates basically improved along with increasing k x and saturated at k x = 4. It is interesting that k x = 2, only 2 bits per element for encoding an activation x, still achieved good performance. While the smaller k w achieved better compression and acceleration rate, error rates rapidly increased when k w = D O /5. One of the well balanced parameters was (k x , k w ) = (4, D O /2) which resulted in 1.95× faster processing and a 34.4% memory compression rate in exchange of a 0.19% increase in the error rate.

5.2. VGG-16 FOR IMAGENET CLASSIFICATION TASK:

A dataset of ILSVRC2012 (Russakovsky et al., 2015) consists of 1.2 million training, 50,000 validation, and 100,000 test sets. Each image represents one of 1000 object categories. In this experiment, we used a network model of VGG-16 (model D in (Simonyan & Zisserman, 2015) ) that consists of 13 convolutional layers and 3 fully connected layers followed by a softmax layer. The architecture is shown below:

EQUATION

where layers before the first fully connected layer are omitted.

First, all three fully connected layers were compressed with our algorithm. We set n = 10 and N T = 1000 to learn c x and b x from randomly chosen nN T activations. The cases of k x = 2, 3, 4 and k w = D O /2, D O /4, D O /8, D O /16 were tested. The case of k x = 1 was omitted because this setting resulted in a very high error rate. Note that each of the fully connected layers has different D O . The k w was independently set for each layer according to its D O . The top-5 error rates were evaluated on the validation dataset. The top-5 error rate of the original network is 13.4%.

The three lines with circles in Figure 3 show these results. It should be noted that much higher acceleration rates and smaller compression rates with small loss of accuracies were achieved than the case of the network for MNIST. Interestingly, the case of k w = D O /4 still performed well due to the low-rank characteristics of weights in the VGG-16 network.

Although the error rates rapidly increased when k w took much smaller values, we found that this could be improved by tuning k w of the third layer. More specifically, we additionally tested the 3 . In this way, the memory compression rate and acceleration rate noticeably improved. Setting appropriate parameters for each layer is important to improve the total performance. Table 3 shows the details of the best balanced case in which 15× faster processing and 5.2% compression rate were achieved in exchange of a 1.43% increase in error rate.

Next, we also tested to compress convolutional layers. In this experiment, k w and k x were set to D O and 4. This setting accelerates each of the layers averagely 2.5 times faster. Table 4 shows positions of compressed layers, top-5 errors, and acceleration rates of the entire network. Although k w and k x must be larger than those of fully connected layers to avoid error propagation, it is still beneficial for entire acceleration. In summary, while compressing fully connected layers is beneficial for reducing memory, compressing convolutional layers is beneficial for reducing entire computation time.

5.3. VGG-FACE FOR FACE RECOGNITION TASK:

The VGG-Face (Parkhi et al et al., 2015) . Following the evaluation protocol introduced in a previous paper (Parkhi et al., 2015) , we used Labeled Faces in the Wild dataset (LFW) (Huang et al., 2007) , which includes 13,233 face images with 5,749 identities. The LFW defines 1200 positive and 1200 negative pairs for testing. We used the 2400 test pairs to compute ROC curve and equal error rate (EER). The EER is defined as an error rate at the ROC operating point where the false positive and false negative rates are equal. The EER of the original network is 3.8%.

First, the two fully connected layers were compressed using our algorithm. We set n = 10 and N T = 1000 to learn c x and b x from randomly chosen nN T activations. We tested the cases of k x = 1, 2, 3, 4, and k w = D O /2, D O /4, D O /8, D O /16. Figure 4 reveals an interesting fact that even the fastest and smallest network configuration, k x = 1 and k w = D O /16, had less impact on the EER, in contrast to the previous ImageNet classification task in which the recognition results were corrupted when k x = 1. This indicates that the 4096-dimensional feature space is well preserved regardless of such coarse discretization of both weights and activations.

Next, we also tested to compress convolutional layers. In this experiment, k w and k x were set to D O and 4 which are the the same setting used in Table 4 . Table 5 shows positions of compressed layers and EERs. The acceleration rates were almost the same as the results shown in Table 4 . This is because architecture of VGG-face is the same as VGG-16 and we used the same parameter for k w and k x . Interestingly, compressing multiple layers from 2nd to 10th still preserves the original EER.

As can be seen from this table, our method works very well depending on a certain kind of machine learning task.

6. CONCLUSION:

We proposed a network compression model that consists of two components: ternary matrix decomposition and binary activation encoding. Our experiments revealed that the proposed compression model is available not only for multi-class recognition but also for feature embedding. Since our approach is post-processing for a pre-trained model, it is promising that recent networks designed for semantic segmentation, describing images, stereo matching, depth estimation, and much more can also be compressed with our method. For future work, we plan to improve approximation error further by investigating the discrete optimization algorithm.



Figures and Tables:

Figure 1: Our network compression model

Decompose x into M x , c x , and b x Require: x, k x Ensure: factorized components M x , c x , and b x . 1: Initialize M x by three random values {-1, +1}. 2: Minimize ||x -(M x c x + b x 1)|| 2 2 by repeating the following two steps until convergence.

Figure 2: Results of MNIST. The first fully connected layer was decomposed.

Figure 3: Results of VGG-16. The last three fully connected layers were decomposed.

Figure 4: Results of VGG-Face. The last two fully connected layers were decomposed.



Table content: <table><tr><td/><td colspan="2">: Number of operations</td><td/></tr><tr><td>operation</td><td>floating point</td><td/><td>logical</td></tr><tr><td/><td>multiply-adds</td><td>AND</td><td>XOR</td><td>bit count</td></tr><tr><td>original (W x)</td><td/><td/><td/></tr></table>

Memory consumption. Real value is represented in single precision (32 bits/element).

Table content: <table><tr><td/><td>original</td><td>proposed</td></tr><tr><td>variables</td><td>W</td><td>M w</td></tr></table>

Decompose W into M w and C w Require: W, k w Ensure: factorized components M w and C w .

Table content: <table/>

Best balanced parameters for decomposing three fully connected layers of VGG-16. While k w was set to D O /2, D O /4, D O /8, and D O /16 for the first and second layers, k w was fixed to D O for the third layer. The k x was set to 4. This is plotted with a red line in Figure

Table content: <table><tr><td/><td colspan="2">Original</td><td/><td/><td colspan="2">Proposed</td><td/><td/></tr><tr><td>Top-5 error (%)</td><td>13.4</td><td/><td/><td/><td/><td>14.8</td><td/><td/></tr><tr><td/><td colspan="2">MBytes msec</td><td>k w</td><td colspan="2">k x MBytes</td><td>ratio</td><td/><td>msec</td><td>ratio</td></tr><tr><td>fc25088-4096</td><td>392.0</td><td colspan="3">142.4 D O /8 4</td><td>11.1</td><td colspan="2">2.8%</td><td>6.1</td><td>23.5×</td></tr><tr><td>fc4096-4096</td><td>64.0</td><td colspan="3">22.8 D O /8 4</td><td>8.5</td><td colspan="2">13.3%</td><td>3.0</td><td>7.5×</td></tr><tr><td>fc4096-1000</td><td>15.6</td><td>5.7</td><td>D O</td><td>4</td><td>4.8</td><td colspan="2">30.7%</td><td>2.3</td><td>2.5×</td></tr><tr><td>total</td><td>471.6</td><td>170.9</td><td/><td/><td>24.4</td><td colspan="2">5.2%</td><td colspan="2">11.4 15.0×</td></tr><tr><td colspan="9">Table 4: Reults of decomposing convolutional layers of VGG-16.</td></tr><tr><td colspan="3">Compressed convolutional layers</td><td>2nd</td><td colspan="6">2nd-4th 2nd-6th 2nd-8th 2nd-10th</td></tr><tr><td colspan="3">Increase in top-5 error (%)</td><td>0.37</td><td>1.64</td><td colspan="2">2.79</td><td/><td>4.13</td><td>6.42</td></tr><tr><td colspan="5">Acceleration rate of entire network 1.08× 1.22×</td><td colspan="2">1.41×</td><td colspan="2">1.68×</td><td>2.15×</td></tr><tr><td>following cases.</td><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Reults of decomposing convolutional layers of VGG-Face.

Table content: <table><tr><td colspan="6">Compressed convolutional layers 2nd 2nd-4th 2nd-6th 2nd-8th 2nd-10th</td></tr><tr><td>Increase in EER (%)</td><td>0.28</td><td>0.47</td><td>0.66</td><td>0.47</td><td>0.75</td></tr><tr><td colspan="6">them. In our experiment, we did not apply a descriptor embedding technique based on triplet loss</td></tr><tr><td>minimization (Parkhi</td><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2017):
This paper addresses to reduce test-time computational load of DNNs. Another factorization approach is proposed and shows good results. The comparison to the other methods is not comprehensive, the paper provides good insights.