Year: 2019

Abstract:
Pruning is an efficient model compression technique to remove redundancy in the connectivity of deep neural networks (DNNs). A critical problem to represent sparse matrices after pruning is that if fewer bits are used for quantization and pruning rate is enhanced, then the amount of index becomes relatively larger. Moreover, an irregular index form leads to low parallelism for convolutions and matrix multiplications. In this paper, we propose a new network pruning technique that generates a low-rank binary index matrix to compress index data significantly. Specifically, the proposed compression method finds a particular finegrained pruning mask that can be decomposed into two binary matrices while decompressing index data is performed by simple binary matrix multiplication. We also propose a tile-based factorization technique that not only lowers memory requirements but also enhances compression ratio. Various DNN models (including conv layers and LSTM layers) can be pruned with much fewer indices compared to previous sparse matrix formats while maintaining the same pruning rate.

heading: 1 INTRODUCTION
text: Numerous parameter pruning techniques have been introduced based on the observation that significant amounts of connectivity can be removed without sacrificing model accuracy. Current active research strives to enhance pruning rate at the cost of additional computations (Guo et al., 2016; Molchanov et al., 2017), to reduce computational complexity of pruning procedures (Zhu & Gupta, 2017; Han et al., 2015), and to find the underlying principles of pruning (Liu et al., 2019; Frankle & Carbin, 2019), to name a few.
Figure 1 shows a dense matrix after pruning redundant parameters and various masking index representations. Fine-grained parameter pruning (i.e., each parameter is evaluated to be pruned) results in sparse matrices which can be represented by various formats depending on how indices of non-zero weights are described (Lee et al., 2018a). A desirable index format in sparse DNNs should produce 1) low memory footprint for index and 2) high parallelism for index storage accesses. Unfortunately widely used compressed sparse row (CSR) format involves two index values for each non-zero weight while the number of bits to represent indices increases as the parameter size increases. Even though the binary index form is a regular structure that can utilize full memory bandwidth, sparsity does not reduce memory footprint. A critical concern on those previous sparse matrix formats (CSR format and binary index format) is that the relative amount of index increases if the number of bits to present non-zero weight shrinks due to advanced quantization techniques. Table 1 describes index size divided by the amount of non-zero weights assuming that sparsity is S and non-zero weights are quantized to be Q bits. It is clear that reducing quantization bits aggravates the issue of too large index portion even if a relative indexing scheme (Han et al., 2016b) is used for CSR format with 5 bits.
If pruning is performed in a fine-grained manner to improve overall pruning rate, then each row/column or block exhibits different sparsity. Consequently, row/column-wise or block-wise computations require vastly different computation latency leading to significantly degraded parallelism (Han et al., 2016a). Thus, some of recent pruning techniques suggest removing connectivity in a well-structured form, (Wen et al., 2016; He et al., 2017), or in a block-level (Yu et al., 2017; Narang et al., 2017).
In this paper, we propose a new fine-grained pruning method to find an efficient sparse matrix representation based on binary index-matrix factorization. As shown in Figure 1, our proposed index
compression scheme decomposes a binary index matrix into two small binary matrices in order to reduce index storage and maintain regular structure. Binary matrix multiplication is inherently parallelizable and sparse non-zero weights can be decoded with high parallelism using recent approaches (Ahn et al., 2019). Thus, decoding sparse matrices can be performed with high performance. In order to accomplish such a new indexing form, we propose an algorithm that finds a particular finegrained pruning result by generating a low-rank binary index matrix. Since factorization may not exactly reproduce the original binary index matrix, we investigate whether a low-rank binary index matrix produces a pruning result while maintaining allowable model accuracy. Our proposed binary matrix factorization technique significantly reduces the amount of index data compared to using CSR, as demonstrated in the next sections. We also introduce a tiling technique to alleviate on-chip memory size and the burden of on-chip binary matrix multiplication, and to further improve compression ratio.
Recently, a regular-structured index compression method has been proposed using the Viterbi algorithm (Lee et al., 2018a), which explores sequences to be used as pruning mask bits, decompressed by Viterbi encoders. Even though compression rate improves over CSR, for every one input bit, a large number of XOR gates and delay units is required. In comparison, our proposed decompression relies on simple binary matrix multiplications and achieves even higher compression.

heading: 2 BINARY MATRIX FACTORIZATION FOR PRUNING INDEX
text: Suppose that a 5× 5 weight matrix W is given as
W =  −0.1 0.9 1.2 −0.2 −0.6
1.8 0.2 −0.7 −1.6 0.6 −0.1 −1.7 0.1 −0.3 1.2 −0.4 1.4 −0.9 0.6 1.4 −1.1 0.5 1.0 1.0 −0.3  . (1) Following the magnitude-based pruning method (Han et al., 2015), all weights with magnitude smaller than a certain threshold value are pruned to zero. For example, for a threshold of 0.7, we obtain the following pruning index (i.e., binary masking layer) matrix I as
I =  0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0  . (2)
It is important to note that magnitude-based pruning is not an optimal solution (Lee et al., 2018a; LeCun et al., 1990; Han et al., 2016b) to maximize the pruning rate, i.e., a variety of masking layers exist for the same pruning rate.
Binary matrix factorization (BMF) (Zhang et al., 2007) is a reasonable approach to compress I . For I ∈ {0, 1}m×n, BMF tries to find the best Im×kp and Ik×nz to approximate I as I ≈ Ip ⊗ Iz = Ia, where k corresponds to the binary matrix factorization rank and ⊗ stands for binary matrix multiplication. A binary product of Ip and Iz is then defined as
(Ia)i,j = k∨ l=1 (Ip)i,l ∧ (Iz)l,j . (3)
While BMF should minimize the number of mismatched bits between I and Ia, such an optimization is NP-hard. Hence, several heuristic methods for BMF have been proposed in the literature (Zhang et al., 2007). Moreover, BMF using I (without referring to W ) lacks weight magnitude information. Yet, in the context of magnitude-based pruning, weights of small magnitude should be pruned with higher probability (i.e., lower importance). Therefore, we explore a method that preserves the importance of each weight when it is not possible to exactly reproduce I through matrix factorization.

heading: 2.1 BINARY MATRIX FACTORIZATION BASED ON NON-NEGATIVE MATRIX FACTORIZATION
text: Non-negative matrix factorization (NMF) factorizes a real-valued matrix H into two real-valued matrices H1 and H2 under the constraint that all three matrices consist of non-negative elements. Similar to singular-value decomposition (SVD), NMF attempts to minimize ||H−H1H2||2F , where ||H||F denotes the Frobenius norm of the matrix H . The property of non-negativity in NMF is useful for analysis of various multivariate data. Numerous numerical approximations of NMF have been suggested since an exact solution of NMF is not generally available (Lee & Seung, 1999; Zhang et al., 2007).
In our proposed technique, we take the magnitude of each element of W to generate M (i.e., Mi,j = |Wi,j |). and M is factorized by an NMF library (e.g., (Zitnik & Zupan, 2012)) into two matrices Mp and Mz . For example, a magnitude matrix M of the matrix W of Eq. (1) can be factorized into
Mp =  0.2 0.5 1.3 0.0 0.0 0.9 0.3 0.8 0.8 0.2  , Mz = [ 1.3 0.1 0.7 1.2 0.3 0.0 1.8 0.7 0.2 1.3 ] , (4)
where rank k is 2.
The next step is to convert Mp and Mz into two binary matrices Ip and Iz using threshold values Tp and Tz (i.e., (Ip)i,j = 1 if (Mp)i,j ≥ Tp, or 0 otherwise). The sparsity of Ip and Iz can each be controlled by Tp and Tz . Our goal is to achieve similar sparsity between I and Ip ⊗ Iz . Suppose that Tp = 0.5 and Tz = 0.6 are carefully chosen to produce similar sparsity as I . We obtain
Ip =  0 1 1 0 0 1 0 1 1 0  , Iz = [ 1 0 1 1 0 0 1 1 0 1 ] (5)
and the binary product of Ip and Iz becomes
Ia = Ip ⊗ Iz =  0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0  . (6) Compared with the pruning-index matrix I in Eq. (2), there are 2 mismatched elements (underlined in Eq. (6)).
Algorithm 1: Binary pruning-index-data matrix factorization input : W ∈ Rm×n, rank k, target sparsity S output: Ip ∈ {0, 1}m×k, Iz ∈ {0, 1}k×n
1: Generate the magnitude matrix M using W 2: Mp, Mz = NMF(M , k) 3: Costmin ←∞, Sminp ← 0.0, Sminz ← 0.0 4: for Sp = 0.0 to 1.0 do 5: Compute Sz using Eq. (7) 6: repeat 7: Convert (Mp,Mz) into (Ip,Iz) w/ (Sp, Sz) 8: Adjust Sz depending on (Sa − S) 9: until Sa ≈ S
10: Cost← ∑
Ii,j=1,(Ia)i,j=0
Mi,j
11: if Costmin > Cost then 12: Costmin ← Cost, Sminp ← Sp, Sminz ← Sz 13: end if 14: end for 15: Convert (Mp,Mz) into (Ip, Iz) w/ (Sminp , S min z ) 16: Return Ip, Iz
The rationale behind this approach is as follows: 1) If Mi,j is large, then its corresponding k components of Mp and Mz (i.e., (Mp)i,: and (Mz):,j) will also be large with high probability and, correspondingly, 2) Binary matrix conversion using Tp and Tz would yield a high probability of being ‘1’ within Ip and Iz if the corresponding Mi,j is large. Note that in order to match ‘OR’ operations in Eq. (3), negative values in Mp or Mz are not allowed. Thus, SVD is not applicable for our proposed scheme. Let S, Sa, Sp, and Sz be the sparsity of I , Ia, Ip, and Iz , respectively. From the dot product operation in Eq. (6), the expression for pruning rate S becomes
S = ((1− (1− Sp)(1− Sz))k, (7)
assuming that the probability of a bit being ‘0’ in Ip and Iz follows Sp and Sz . Then, Sz = (S1/k − Sp)/(1 − Sp), which needs to be fine-tuned in practice. If Tp and associated Sp are given, then Tz and Sz are automatically determined by the target pruning rate. Subsequently, given W and rank k, it is necessary to find a certain Sp that produces the best masking layer for pruning.
In order to optimize Sp, we define the cost function for pruning-index compression to be ∑ Mi,j , where (I)i,j = 1 and (Ia)i,j = 0 (i.e., a sum of all unintentionally pruned weights’ magnitude by binary matrix decomposition). Algorithm 1 describes a method to find the best Sp by sweeping Sp and monitoringCost. Given the linear relationship between Sa and Sz , the algorithm can use binary search to expedite adjustment of Sz .

heading: 2.2 MNIST CASE STUDY
text: We applied our proposed pruning-index compression technique to the LeNet-5 model with the MNIST dataset. LeNet-5 consists of two convolutional layers and two fully-connected layers (Han et al., 2015; Lee et al., 2018b). Since the FC1 layer dominates the memory footprint (93%), we focus on the FC1 layer to investigate the effectiveness of our proposed method, but all layers are pruned with the same rates as in (Han et al., 2015). FC1 involves a (800 × 500) weight matrix, where full rank is 500. Figure 2 plots Sz , Cost, and test accuracy across a range of Sp values. Pruning rate S for FC1 is 95% and rank k is 16, 64, or 256. As k increases, both Ip and Iz become more sparse and both Cost and test accuracy improve.
After pre-training for 20K iterations, pruning via BMF is performed as described in Algorithm 1. Then, retraining runs until the 60Kth iteration using a masking layer Ia. The test accuracy (the average of 20 runs) is measured at the 20Kth (right after pruning), 40Kth, 50Kth, and 60Kth iterations, as shown in Table 2 along with the compression ratio computed as mn/(k(m + n)). Compared with
other binary pruning index formats (such as ternary quantization), our proposed binary index factorization yields much higher index compression ratios while maintaining reasonable test accuracy.
In general, the histogram of a weight matrix of a pre-trained model follows a Gaussian distribution (Goodfellow et al., 2016). For magnitude-based pruning, the count of near-zero values is significantly reduced after pruning. To investigate which weights are pruned by different rank, Figure 3 presents the histogram of unpruned weight values of the FC1 layer of LeNet-5 model at the 20Kth iteration right after performing Algorithm 1 using the same pruning rate of 95%. Results show the count of near-zero weights reduces as rank increases. Since the total count is the same in Figure 3 for different rank k, a low count of near-zero weights in the histogram implies that fewer weights of large magnitude are pruned. As such, there is a trade-off between the rank k and accuracy even though accuracy drop is reasonable for a wide range of rank values as shown in Table 2. Note that
regardless of the rank k, large weights are avoided to be pruned and accuracy is not significantly compromised.
Table 3 compares parameter storage for the FC1 layer using different formats while keeping pruning rate at 95.0%. Reduction in index size for CSR can be achieved using a relative index scheme as described in (Han et al., 2016b). In the case of Viterbi-based pruning, we assume the Viterbi decompressor has 40 outputs, 10-bit comparators, and a skip state of 1 (Lee et al., 2018a). Our proposed pruning method using binary matrix factorization yields the best compression ratio.

heading: 3 INDEX MATRIX TILING AND WEIGHT MANIPULATION TO LOWER RANK
text: In this section, we propose two techniques to improve pruning quality for a fixed rank k (or to lower rank k for the same pruning quality).

heading: 3.1 TILE-BASED BINARY MATRIX FACTORIZATION
text: Weight matrix size increases quadratically with the number of neurons. If the whole binary matrix multiplication were to be performed within a chip, then on-chip memory size would be prohibitively large. In order to enhance scalability of our proposed factorization method, we propose tile-based factorization as illustrated in Figure 4. A (n ×m) binary matrix is first tiled into multiple blocks. Then, each block is factorized independently with the same rank. Note that tiling size and/or reshaping the original binary index matrix can be varied to match the underlying parallel computing resources. Because NMF is solved by an iterative method in general, tiling not only reduces the required on-chip memory size but also reduces NMF computation time.
Tiling also affects the quality of binary matrix factorization. Note that when X1, X2, . . ., Xn are random samples of size n from a distribution with mean µ and variance σ2, the sample mean X̄ shows E(X̄) = µ and V ar(X̄) = σ2/n. Indeed, Figure 4 depicts large variance of weight values after NMF when the number of tiles increases (a random Gaussian weight distribution is first assumed). Correspondingly, Mp and Mz also show larger variance with longer tails in the distribution with more blocks as shown in Figure 5. Such increased variance of Mp and Mz with smaller sample size is desirable for binary conversion from the NMF result. For example, compared with {0.98, 1.0, 1.2}, {0.5, 1.0, 1.5} presents larger spectrum of binary conversion threshold values for Sp and Sz (and hence, increases the chance to further optimize the cost function).
Figure 6 plots histograms of unpruned FC1 layer weights of the LeNet-5 model on MNIST across different tiling methods. FC1 weight matrix (of 500 × 800 size) is tiled into 1(1 × 1), 4(2 × 2), or 16(4 × 4) submatrices while the index compression ratio is the same for all three tiling cases. Since the size of a submatrix differs for each partitioning plan, the rank for factorizing a submatrix is accordingly adjusted in Figure 6. Notice that increasing the number of blocks yields deeper drops of near-zero weights. However, if submatrices have different properties (e.g., an embedding matrix in natural language models) by tiling, each submatrix can optimally choose a different rank.

heading: 3.2 WEIGHT MAGNITUDE MANIPULATION
text: If Cost is given as a magnitude-sum of unintentionally pruned weights, then it is still possible that a large weight can be pruned. To prevent large weights from being pruned and to keep the definition of Cost, the magnitude of weights can be pre-processed. For example, in the context of magnitude-based pruning, artificially increasing already large weight values can futher lower their probability of being pruned. Note that such weight magnitude manipulation is only temporarily used for pruning-index data compression, and not for normal training or inference steps.
Figure 7 plots histograms of unpruned weights of the FC1 layer of LeNet-5 using different weightmagnitude manipulation methods. In Method 3, weights larger than a threshold are multiplied by 1/(1− S). We observe the sharpest drop of weights around the threshold value and higher count of large weights in Method 3. Finding the best weight manipulation method is an open problem.

heading: 4 EXPERIMENTAL RESULTS
text: We verify our index data compression technique using ResNet32 (He et al., 2016) on CIFAR-10, AlexNet (Krizhevsky et al., 2012) on ImageNet, and a recurrent neural network (RNN) model on the PTB dataset (Marcus et al., 1994), as shown in Table 4. We do not apply binary matrix factorization to layers if their parameter size is relatively small. Such layers usually present small pruning rates (Han et al., 2015; Zhu & Gupta, 2017) and index compression ratio is also small (Yu et al., 2017). For example, Viterbi-based index compression techniques yield 1× compression ratios for the index data of convolutional layers in AlexNet (Lee et al., 2018a).
For ResNet32 mainly consisting of convolutional layers, our pruning-index compression achieves a 70% pruning rate with 91.8% accuracy, providing over 3× index compression as shown in Table 4 (experimental data using various rank selections id provided in Appendix). Note that binary pruning-index matrix decomposition is performed after multiplying the weights (exceeding the pruning threshold) by 1/(1− S), as a method to drop more near-zero weights. For AlexNet, we focus on compressing index data of FC5 and FC6 layers occupying ∼90% of the total model size. Both layers are pruned to a pruning rate of 91% (Han et al., 2015) using Algorithm 1. We achieve over 8× compression in the pruning-index data while maintaining full-precision accuracy. FC5 and FC6 weights are tiled into small blocks, given their large matrix size. BMF of Algorithm 1 is performed on those blocks with ranks 32 and 64, resulting in speed up and reduced Cost.
An RNN model with one long-short term memory (LSTM) layer of size 300 (Xu et al., 2018) on the PTB dataset, with performance measured using Perplexity Per Word (PPW), is pruned by our pruning-index-compression method. Note that the embedding and softmax matrices usually take a major memory footprint because of increasing vocabulary size in a neural language model while these two matrices have several distinguished properties compared with general weight matrices (Chen et al., 2018).
To compare the compression ratio of various sparse matrix representation schemes, we choose AlexNet FC5 and FC6 layers and Table 5 shows the index size of a binary matrix representation, CSR format with 16-bit indexing, CSR format with 5-bit indexing (relative indexing as introduced in (Han et al., 2016b)), Viterbi-based representation (Lee et al., 2018a), and our proposed representation. Our proposed network pruning algorithm and index representation using binary matrix factorization significantly reduce the amount of indexing data while maintaining sparsity at the same level as fine-grained pruning. Lastly, while Viterbi-based compression only allows for integer-valued
1 Different ranks are applied to 3 groups of layers according to the number of input channels (16, 32, or 64). 2 The FC5 and FC6 layers are tiled to 16×8 blocks (of 576×512 size) and 8×8 blocks (of 512×512 size), respectively.
compression ratios, our proposed compression technique enables a much wider range of compression ratios (as rational numbers) by controlling the rank for index pruning. Note that more advanced quantization techniques should be supported by stronger index data compression methods. Otherwise, index size would limit the available compression ratio when we combine pruning and quantization schemes.

heading: 5 CONCLUSION
text: This paper proposes a fine-grained network pruning technique to produce low-rank binary index matrices. We confirm various DNN models can be pruned by our low-rank indexing scheme while preserving sparsity. Such binary matrix multiplication enables not only high compression ratios, but highly parallel operations of sparse networks. Our proposed tiling method and weight magnitude manipulation schemes further lower rank. Unlike previous studies, this work demonstrates that finegrained pruning can be represented by a highly regular structured format.

heading: A SUPPLEMENTARY EXPERIMENTAL RESULTS ON RESNET32 USING
text: CIFAR-10
Table 6 lists the accuracy of ResNet32 using various ranks and pruning rates. The pruned models using our proposed binary matrix decomposition show slightly degraded accuracy compared to the baseline pruning method (the bottom row of Table 6). It can be observed that in general, there exists a trade-off between the ranks and compression ratios.

Review summaries:
The paper addresses the problem of reducing the computational complexity of neural network pruning. Main idea is to compute a low-rank approximation of the binary index matrix used to represent the structure of the pruned network. In the considered setup, the binary index matrix is the (sparse) boolean matrix associated with the nonzero network's weights. As low-rank decomposition of binary matrices is a hard problem, the authors propose a method to approximate the solution by computing a more standard non-negative matrix factorization. 

This paper proposed a new network pruning method that generates a low-rank binary index matrix to compress index data, and a tile-based factorization technique to save memory. The binary index can achieve larger compression ratio than the CSR index, and the  low-rank binary index can further reduce memory usage. The results for various networks, including DNN, CNN and LSTM, have shown the effectiveness of the propsoed method. The paper is well-written and easy to follow.