Network Pruning for Low-Rank Binary Index
Authors: Dongsoo Lee
Se Jung Kwon
Byeongwook Kim
Parichay Kapoor
Gu-Yeon Wei
Venue:  (2020)
Keywords: Pruning
Model compression
Index compression
low-rank
binary matrix decomposition

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 fine-grained 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.

Under review as a conference paper at ICLR 2020
NETWORK PRUNING FOR LOW-RANK BINARY INDEX
Anonymous authors
Paper under double-blind review
ABSTRACT
Pruning is an efficient model compression technique to remove redundancy in the connectivity of deep neural networks (DNNs). A critical problem to repre- sent 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 new network pruning tech- nique that generates a low-rank binary index matrix to compress index data sig- nificantly. Specifically, the proposed compression method finds a particular fine- grained pruning mask that can be decomposed into two binary matrices while de- compressing index data performed by simple binary matrix multiplication. We also propose a tile-based factorization technique that not only lowers memory re- quirements 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.
INTRODUCTION
Numerous parameter pruning techniques have been introduced based on the observation that signif- icant 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 2016
Molchanov et al. (2017). to reduce computational complexity of pruning procedures (Zhu & Gupta
2017 Han et al. 2015). and find the underlying principles of pruning (Liu al., 2019 Frankle & Carbin 2019), to name few.
Figure shows a dense matrix after pruning redundant parameters and various masking index repre- sentations. 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 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 the number of bits to present non-zero weight shrinks due to advanced quantization techniques. Table [ 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. is clear that reducing quantization bits aggravates the issue of too large index portion even a relative indexing scheme (Han et al., 2016b) is used for CSR format with 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-wiss. or block-wise com- putations require vastly different computation latency leading to significantly degraded parallelism (Han et al. 2016a)). Thus, some of recent pruning techniques suggest removing connectivity in
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 pruming method to find an efficient sparse matrix rep- resentation based binary index-matrix factorization. As shown in Figure | proposed index

---

Under review as a conference paper at ICLR 2020
1 0011 100
0000
IA [0225]]
0
1101
JA= [0301301]
1
3 6
1100
Dense Matrix after Pruning
Binary Index Format
CSR Index Format
Binary Index Decomposition
Figure 1: Comparison various sparse matrix representation formats.
Table 1: Index size divided by weight data size when weights are quantized to be Q bits and pruned obtain sparsity S.
CSR Index
Binary Index
16-bit Index
5-bit Index
S=0.6
S=0.7
S=0,8
S=0.9
Q=1
16.0x
5,0x
2.5x
3.3x
5.0x
10.0x
Q-2
8.0x
2.5x
1.3x
1.7x
2.5x
5.0x
Q=3
5.3x
1.7x
0.8
1.1x
1.7x
3.3x
Q-4
4.0x
1.3x
0.6x
0.8x
1.3x
2.5x
compression scheme decomposes binary index matrix into small binary matrices in order to reduce index storage and maintain regular structure. Binary matrix multiplication inherently paral- lelizable and sparse non-zero weights be decoded with high parallelism using recent approaches (Ahn et al. 2019). Thus, decoding sparse matrices can be performed with high performance. In order accomplish such new indexing form, we propose an algorithm that finds a particular fine- grained 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 dex 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, demonstrated in the next sections. We also introduce a tiling technique alleviate on-chip memory size and the burden of on-chip binary matrix multiplication, and to further improve compression ratio.
Recently, a regular-structurre index compression method has been proposed using the Viterbi algo- rithm (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, proposed decompression relies on simple binary matrix multiplications and achieves even higher compression.
2 BINARY MATRIX FACTORIZATION FOR PRUNING INDEX
Suppose that 5 x 5 weight matrix Wi is given as
-0.1
0.9
1.2
-0.2
-0.67
1.8
0.2
-0.7
-1.6
0.6
W
0.1
-1.7
0.1
-0.3
1.2
(1)
0.4
1.4
-0.9
0.6
1.4
1.1
0.5
1.0
1.0
003
Following the magnitude-based pruning method (Han et al. 2015). all weights with magnitude smaller than certain threshold value pruned to For example, for threshold of 0.7, we obtain the following pruning index (i.e., binary masking layer) matrix I as
0
1
1
0
1
0
1
0
I
0
1
0
0
(2)
0
1
1
0
1
0
2

---

Under review as a conference paper at ICLR 2020
It is important note that magnitude-basee pruning is not optimal solution (Lee al. 201 8a
LeCun et al. 1990, Han et al. 2016b) to maximize the pruning rate, i.c., a variety of masking layers exist for the same pruming rate.
Binary matrix factorization (BMF) Zhangg et al. 2007) is a reasonable approach to compress I. For I E {0, 1, BMF tries to find the best Ip m and I I to approximate I as I @ Is La where & corresponds the binary matrix factorization rank and @ stands for binary matrix multiplication. binary product Ip and I is then defined as
(L)).,) V (Ip)a (L2)..
While BMF should minimize the number of mismatched bits between I and Las such an optimiza- tion 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 pruning, weights of small magnitude should be
information. Yet, in the context of magnitude-basee pruned with higher probability (i.e., lower importance). Therefore, we explore a method that pre- the importance of each weight when it is not possible exactly reproduce through matrix factorization.
2.1 BINARY MATRIX FACTORIZATION BASED ON NON-NEGATIVE MATRIX FACTORIZATION
Non-negative matrix factorization (NMF) factorizes 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 H1 H2ll where ||]|] 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 NMF have been suggested since exact solution of NMF is not generally available (Lee & Seung 1999 Zhang et al. 2007).
In proposed technique, take the magnitude of each element of W generate M (i.e., M., = [W. and M is factorized by an NMF library (e.g., (Zitnik Zupan 2012)) into two matrices M, and M,. For example, a magnitude matrix M of the matnx W of Eq. T can be factorized into
0.2
0.5
1.3
0.0
1.3
0.1
0.7
1.2
0.3
M,
0.0
0.9
M.
0.0
1.8
0.7
0.2
1.3
0.3
0.8
0.8
0.2
where rank
The next step is to convert M, and M. into two binary matrices Ip and I, using threshold values Tp and T- (i.e., (Tp)..j
if (Mp)..) 2 Tp. or otherwise). The sparsity of I and I, can each be controlled by T, and T,. Our goal is to achieve similar sparsity between I and I, & Ig. Suppose that T, = 0.5 and T. 0.6 are carefully chosen to produce similar sparsity as We obtain
0
0
1
0
1
0 1
I
0 1
I
(5)
0
1
1 0
and the binary product of Ip and Ig becomes
17
1
0
0
I, I, 1.
0
(6)
0
1
1
0
Compared with the pruning-ined index matrix I in Eq. in Eq. (6)).
(2), there are mismatched elements (underlined

---

Under review as a conference paper at ICLR 2020
Algorithm 1: Binary pruning-index -ata matrix factorization
input : W RRxx rank k target sparsity S
output: I E {0, 1)mx, I& E {0, 1
Generate the magnitude matrix M using W
2: Mp. M2 NMF(M, k)
3: Cost t- oo, Sprin + 0.0, S + 0.0
4: for S, 0.0 to do
5: Compute S₂ using Eq.
6: repeat
7: Convert (M, into (1 w/ (Sps St)
8: Adjust S₂ depending on (S. - S)
9: until S. R S
10:
Cost
Σ
Mys
11:
if Costmin > Cost then
12: Cost Cost, Spinn + Sp, Smmin +- S
13:
end if
14:
end for
15:
Convert (M,, M2) into (Ip, I2) w/ (Spri, Smii)
Return I,. I.
The rationale behind this approach is follows: 1) If M,,j is large, then its corresponding & com- ponents of Mp and M, (i.e.. (Mp)s, and (M.)..)) will also be large with high probability and, correspondingly,
Binary matrix conversion using T, and T3 would yield high probability of being '1' within I and I, if the corresponding M. is large. Note that in order to match 'OR' operations in Eq. (.. negative values in M, or M2 are not allowed. Thus, SVD is not applicable for our proposed scheme. Let S. S., Sp, and Sg be the sparsity of I, Ia. I, and I,, respectively. From the dot product operation in Eq. (6). the expression for pruning rate S becomes
S = ((1 (1- -S))**
assuming that the probability of bit being '0' in Ip and I, follows Sp and S.. Then, (51/k Sp)/(1 Sp), which needs to be fine-tuned in practice. If T. and associated Sp are given, then T, and Sg 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-inde -indxx compression to be Σ M.js where (T), = 1 and (La)i, = 0 (i.e., sum of all unintentionally pruned weights' magnitude by binary matrix decomposition). Algorithm describes method find the best S, by sweeping Sp and monitoring Cost. Given the linear relationship between S, and S., the algorithm can use binary search to expedite adjustment of Sz.
2.2 MNIST CASE STUDY
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 FCT 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 (800 500) weight matrix, where full rank is 500. Figure 2 plots Sg Cost, and test accuracy across range of Sp values. Pruning rate S for FCI is 95% and rank & is 16, 64, or 256. As & increases, both I, and Ig become more sparse and both Cost and test accuracy improve.
After pre- pre-training for 20K iterations, pruning via BMF performed as described in Algorithm I Then, retraining runs until the t0K iteration using masking layer I,. The test accuracy (the aver- age of 20 runs) is measured at the th (right after pruning), 40Kth 50K and 60K iterations, as shown in Table 2 along with the compression ratio computed as mn/ [k[m + n)). Compared with
4

---

Under review as a conference paper at ICLR 2020
1.0
5250.0
0.993
rank 16
0.992
5000.0
Test Accurscy
0.991
0.8
4750.0
0.990
0.7
4600.0
0.989
4250.0
rank
0.988
rank 256
rank 256
0.5
4000.0
0.987
0.25
0.5
0.75
0.25
0.5
0.75
0.2
0.4
0.5
0.8
%p
Figure 2: Sg, Cost, and test accuracy for various Sp when the FC1 layer's gruning-indes data of LeNet-5 model is factorized by Algorithm using S=0.95, k == 16, 64, or 256.
Table 2: (MNIST LeNet-5 accuracy using different rank k. At the 20K iteration, we prune all
layers using magnitude-based pruning method (Han et al. 2015) except FC1 layer where pruning is performed by using Algorithm Retraining is completed at the 60K iteration. The test accuracy of pre-trained model is 99.2%.
Rank
Accuracy (%)
Comp.
(k)
20K
40K
50K
60K
Ratio
33.69
98.96
99.03
99.07
76.9x
34.52
98.98
99.05
99.09
38.5 x
16
30.28
99.01
99.09
99.13
19.2x
32
32.52
99.01
99.08
99.13
9.6x
64
36.02
99.04
99.10
99.14
4.8x
128
34.22
99.04
99,10
99.16
2.4x
256
42.86
99.07
99.14
99.19
1,2x
1200
1000
800
Count
400
200
rank
rank 256
-0.3
-0.2
-0.1
Weight Value
Figure 3: Histogram of unpruned weights of FCI layer at 20 iteration using LeNet-5 model. Higher l results in more near-zero weights pruned.
other binary pruning index formats (such as ternary quantization), our proposed binary index factor- ization yields much higher index compression ratios while maintaining reasonable test accuracy.
In general, the histogram of a weight matrix of pre-trained model follows Gaussian distribution [Goodfellow et al.] 2016). For magnitude-baser pruning, the count of near-zero values is signifi- cantly reduced after pruning. To investigate which weights are pruned by different rank, Figure presents the histogram of unpruned weight values the FCI layer of LeNet-5 model at the 20K in iteration right after performing Algorithm Jusing the same pruning rate of 95%. Results show the count of near-zero zero weights reduces as rank increases. Since the total count is the same in Figure for different rank k. 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 & and accuracy even though accuracy drop reasonable for wide range of rank values shown in Table Note that
5

---

Under review as a conference paper at ICLR 2020
Memory footprint of FCI layer is compared with various index formats assuming that weights are quantized to be 2 bits (note that index size takes substantial memory footprint for the previous schemes). Accuracy is higher than 99.0% for all formats.
Table 3:
Method
Index Size
Non-Zero Weights
Sum
Comment
Binary
50.0KB
5KB
55KB (100%)
S=0.95
CSR(16bit)
45.8KB
5KB
50.8KB (92.4%)
CSR(5bit)
14.3KB
5KB
19.3KB (35.1%)
Relative 5X encoder 16
Viterbi
10.0KB
5KB
15KB (27.3%)
Proposed
2.6KB
5KB
7.6KB (13.8%)
15000
(1 X Tiling
x2 Tiling
No NMF NMF, (128 128) tiling
10000
NMF, 8) tiling
Count
NMF, 1) tiling
S000
(oxm)
(nxx)). ()
(n/2 x m22)
{ (n/2 o2). (r2 x mi2)
3
Magnitude of Weight Value
Figure 4: (Left): (n x m) binary matrix factorization using one or four tiles when the compression ratio the same. (Right): Weight histogram before and after NMF using different number of tiles.
regardless of the rank k large weights are avoided to be pruned and accuracy is not significantly compromised.
Table 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 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 al., (0188). Our proposed pruning method using binary matrix factorization yields the best compression ratio.
3 INDEX MATRIX TILING AND WEIGHT MANIPULATION TO LOWER RANK
In this section, we propose two techniques to improve pruning quality for fixed rank A: (or to lower rank l for the same pruning quality).
3.1 TILE- BAESBA BINARY MATRIX FACTORIZATION
Weight matrix size increases quadratically with the number of neurons. the whole binary matrix multiplication were be performed within 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 re- shaping the original binary index matrix can be varied 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. X, are random samples of size from a distribution with mean μ and variance σ², the sample mean X shows E(X) f and Var(X) values after NMF when the number of tiles increases (a random Gaussian weight distribution is first assumed). Correspondingly, M, and Mg also show larger variance with longer tails in the distribution with more blocks as shown in Figure 3 Such increased variance of M, and M, 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 S, and S. (and hence, increases the chance to further optimize the cost function).
o² /n. Indeed, Figure 4 depicts large variance of weight

---

Under review as a conference paper at ICLR 2020
10000
NMF (128 128) tiling
NMF Z, (128 128) tiling
7500
NMF (8 B) tiling
2000
NMF Z. (8 8) tiling
Count
tiling
Count
NMF (1 1) tiling
1000
2500
0.0
0.5
1.0 Value
1.5
2.0
Value 6
Figure Histogram M, and M, values using different number of tiles.
800
B 1x1
700
B 2x2
B 4x4
600
500
Count
400
300
200
100
0
-0.3
-0.2
-0.1
0
0.1
0.2
Weight Value
Figure 6: Histogram of unpruned FC1 layer weights LeNet-5 with different block configurations. Each submatrix is factorized by NMF using different rank depending on the tiling plan to present same overall compression ratio. Rank 128, or 32 used for (1 x 1), (2 2), or (4 4) tiling. respectively.
Figure plots histograms of unpruned FCI layer weights of the LeNet-5 model on MNIST across different tiling methods. FC1 weight matrix (of 500 x 800 size) is tiled into 1(1 1), 4(2 x 2), 16(4 4) submatrices while the index compression ratio is the same for all three tiling cases. Since the size submatrix differs for each partitioning plan, the rank for factorizing a submatrix accordingly adjusted in Figure 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 different rank.
3.2 WEIGHT MAGNITUDE MANIPULATION
If Cost is given as magnitude-sune sum of unintentionally pruned weights, then it 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 weights can be pre-processed. For example, in the context of magnitude-bast pruning, artificially increasing already large weight values futher lower their probability being pruned. Note that such weight magnitude manipulation only temporarily used for pruning-index data compression, and not for normal training inference steps.
Figure plots histograms of unpruned weights of the FC1 layer of LeNet-5 using different weight- magnitude manipulation methods. In Method 3, weights larger than threshold are multiplied by 1/(1 - 5). We observe the sharpest drop weights around the threshold value and higher count of large weights in Method 3. Finding the best weight manipulation method is open problem.

---

Under review as a conference paper at ICLR 2020
2000
method
1800
method 2
1600
method 3
1400
Count
1200
1000
800
600
400
200
0
-0.3
-0.2
-0.1
0
0.1
0.2
Weight Value
Figure 7: Histogram of unprumed FC1 layer weights of LeNet-5 with different weight magnitude manipulation methods (Method I: no manipulation, Method 2: Ma, + Mf Method 3: M,, is amplified by 1)(1-5) if M..j is larger than threshold value (given by magnitude-based pruning), where S is the sparsity of W.
EXPERIMENTAL RESULTS
We verify index data compression technique using ResNet32 (He et al. (016) CIFAR-IO. AlexNet (Krizhevsky et al. 2012) on ImageNet, and recurrent neural network (RNN) model on the PTB dataset (Mareus al. 1994). shown in Table 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 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 index compression as shown in Ta- ble [ (experimenal data using various rank selections id provided in Appendix). Note that binary gruming-indes matrix decomposition is performed after multiplying the weights (exceeding the prun- ing threshold) by 1/(1 S), 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 pruning rate of 191% (Han al. 2015) using Algorithm
1. We achieve over 8x compression in the pruning-index data while maintaining full-precision accuracy. FC5 and FC6 weights tiled into small blocks, given their large matrix size. BMF of Algorithm 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 muning-index-comee index-compesssion method. Note that the embedding and softmax matrices usually take major memory footprint because of increasing vocabulary size in neural language model while these two matrices have several distinguished properties compared with general weight matrices (Cen et 2018).
To compare the compression ratio of various sparse matrix representation schemes, we choose AlexNet FC5 and FC6 layers and Table shows the index size of a binary matrix representation, CSR format with 16-bit indexing, CSR format with 5-bit indexing (relative indexing introduced in (Han et al. 2016b)), Viterbi-based representation (Lee et al. 2018a), and our proposed repre- sentation. 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 fine-grained pruning. Lastly, while Viterbi-based compression only allows for integer-valued
8

---

Under review as a conference paper at ICLR 2020
Table 4: Index compression ratio (compared with binary index scheme) and accuracy of the proposed pruning-index compression method on various DNN models (involving convolutional layers and LSTM layers well).
Pre- trained Model
Pruned Model using the Proposed Method
# of Weights
Index Data
Model
Accuracy
S
Rank
Accuracy
Comp. Ratio
ResNer32
8/16/32'
3.09x
91.8%
460.76K
92.5%
0.70
on CIFAR-10
8/8/8
5.12x
91.5 %
9Kx4K
32
80.4% (top5)
AlexNet
8.20
(FC5)
80.3%
(top5)
tiled
57.1% (topl)
on ImageNet
0.91
4Kx4K
57.6% (topl)
64
80.3% (top5)
(FC5, FC6)
4.14x
(FC6)
tiled
57.2% (top1)
LSTM PTB
6.41M
89.6 PPW
0.60
145
1.82x
89.0 PPW
Different ranks applied to groups of layers according the number of input channels (16, 32, or 64).
The FC5 and FC6 layers are tiled 16x8 blocks (of 576x512 size) and 8x8 blocks (of 512x512 size), respectively.
Table Compression results on FC5 and FC6 layers of AlexNet with various index formats when to be the same as 0.91 for both layers and non-zero weights quantized to be 2 bits. Other than the propose scheme, index size is much larger than non-zero weight size. Top-1 accuracy is higher than 57.0% for all formats.
Method
Index Size
Non-Zero Weights
Sum
Comment
Binary
6656KB
I198KB
7854KB (100%)
CSR(16bit)
K0
1198KB
11259KB
(143.3%)
CSR(5bit)
3144KB
1198KB
4342KB (55.3%)
Relative Indexing
Viterbi
1331KB
1198KB
2529KB
(32.2%)
5X Encoder
Proposed
812KB
1198KB
2010KB (25.6%)
k=32, tiled
compression ratios, our proposed compression technique enables a much wider range of compres- sion ratios (as rational numbers) by controlling the rank for index pruning. Note that more ad- vanced quantization techniques should be supported by stronger index data compression methods. Otherwise, index size would limit the available compression ratio when combine pruning and quantization schemes.
5 CONCLUSION
This paper proposes a fine-grained network pruning technique to produce low-rank binary index matrices. 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 fine- grained pruning can be represented by a highly regular structured format.
REFERENCES
Dachyun Ahm, Dongsoo Lee, Taesu Kim, and Jac-Joon Kim. Double Viterbi: Weight encoding for high com- pression ratio and fast on-chip reconstruction for deep neural network. International Conference on Learning Representations (ICLR), 2019.
Patrick Chen, Si Si. Yang Li, Ciprian Chelba, and Cho-Jui Hsieh. GroupReduce: Block- wise low-rank ap- proximation for neural language model shrinking. In Advances in Neural Information Processing Systems, 2018.

---

Under review as a conference paper at ICLR 2020
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks.
In International Conference on Learning Representations (ICLR), 2019.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http::/wwwz deepLearningbook. org
Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient DNNs. In Advances in Neural Information Processing Systems, 2016.
Song Han, Jeff Pool, John Tran, and William J. Dally. Learning both weights and connections for efficient neural networks. In Advances in Neural Information Processing Systems, pp. 1135-1143, 2015.
Song Han, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark A. Horowitz, and William J. Dally. EIE: efficient inference engine on compressed deep neural network. Proceedings of the 43rd International Symposium on Computer Architecture, pp. 243-254, 2016a.
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and Huffman coding. In International Conference on Learning Representations (ICLR), 2016b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778. 2016.
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In The
IEEE International Conference on Computer Vision (ICCV), Oct 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 25, pp. 1097-1105. Curran Associates, Inc., 2012.
Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. In Advances in Neural Information Processing Systems, pp. 598-605, 1990.
Daniel D. Lee and H. Sebastian Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 40166755):788-791, 1999.
Dongsoo Lec, Dachyun Ahn, Taesu Kim, Pierce I. Chuang, and Jac-Joon Kim. Viterbi-based pruning for sparse matrix with fixed and high index compression ratio. In International Conference on Learning Representa- tions (ICLR), 2018a.
Dongsoo Lee, Parichay Kapoor, and Byeongwook Kim. Deeptwist: Learning model compression via occa- sional weight distortion. V.Xiv:1810.1282. 2018b.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrel. Rethinking the value of network pruning. International Conference on Learning Representations (ICLR), 2019.
Mitchell Marcus, Grace Kim, Mary Ann Marcinkiewicz, Robert MacIntyre, Ann Bies, Mark Ferguson, Karen Katz, and Britta Schasberger. The penn treebank: Annotating predicate argument structure. In Proceedings of the Workshop on Humun Language Technology, pp. 114-119, 1994.
Dmitry Molchanov, Arsenii Ashukha, and Dmitry P. Vetrov. Variational dropout sparsifies deep neural net- works. In International Conference on Machine Learning (ICML), pp. 2498-2507, 2017.
Sharan Narang, Eric Undersander, and Gregory F. Diamos. Block-sparse recurrent neural networks.
arXiv:1711.02788. 2017.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In Advances in Neural Information Processing Systems, pp. 2082-2090, 2016.
Chen Xu, Jianqiang Yao, Zhouchen Lin, Wenwu Ou, Yuanbin Cao, Zhirong Wang. and Hongbin Zha. Al- ternating multi-bit quantization for recurrent neural networks. In International Conference on Learning Representations (ICLR), 2018
Jiecao Yu, Andrew Lukefahr, David Palframan, Ganesh Dasika, Reetuparna Das, and Scott Mahlke. Scalpel: Customizing DNN pruning to the underlying hardware parallelism. In Proceedings of the 44th Annual International Symposiun on Computer Architecture, pp. 548-560, 2017.
Zhongyuan Zhang, Tao Li, Chris H. Q. Ding, and Xiangsun Zhang. Binary matrix factorization with applica- tions. In IEEF International Conference Data Mining, 2007.
10

---

Under review as a conference paper at ICLR 2020
Michael Zhu and Suyog Gupta. To prune, not to prune: exploring the efficacy of pruning for model com- pression. CoRR, abs/1710.01878, 2017.
Marinka Zitnik and Blaz Zupan. Nimfa: A python library for nonnegative matrix factorization. Journal of Machine Learning Research, 13:849-855 853, 2012.

---

Under review as a conference paper at ICLR 2020
A SUPPLEMENTARY EXPERIMENTAL RESULTS ON RESNET32 USING CIFAR-10
list the accuracy of ResNet32 using various ranks and pruning rates. The pruned models using our pro- posed 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 trade-off between the ranks and compression ratios.
Table Model accuracy of ResNet32 with CIFAR-IO using different ranks and pruning rates. The bottom row presents the results of baseline pruning method without binary matrix factorization.
Index
Pruning Rate (S)
Rank!
Comp. Ratio
0.60
0.70
0.80
4/4/4
10.29 x
92.0%
91.5%
90.5%
4/8/16
6.74x
92.2%
91.5%
90.9%
8/8/8
5.12x
92.0%
91.5%
90.9%
8/16/32
3.09x
92.4%
91.8%
91.1%
16/16/16
2.56x
92.2%
91.8%
91.0%
16/32/64
1.55
92.3%
91.7%
91.2%
w/o BMF
1x
92.4%
92.2%
92.0%
Different ranks applied to 3 groups of layers ac- cording to the number of imput channels (16, 32, or 64).
2 Retraining is performed for 65K iterations.
12


Reviews:
[{"review_id": "rye0hcA15H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nIn addition, I have some concerns:\n- Discussion about the relationship between your method with binary neural networks [1,2], especially the networks with binary weights [1].\n- There are no comparison with the state-of-art methods on pruning and index saving, such as deep compression [3] and CNNPack [4].\n- The experiments are not convincing, e.g. only pruning FC5 and FC6 layers in AlexNet on ImageNet dataset.\n\n[1] Courbariaux, Matthieu, Yoshua Bengio, and Jean-Pierre David. \"Binaryconnect: Training deep neural networks with binary weights during propagations.\" Advances in neural information processing systems. 2015.\n[2] Hubara, Itay, et al. \"Binarized neural networks.\" Advances in neural information processing systems. 2016.\n[3] Han, Song, Huizi Mao, and William J. Dally. \"Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.\" arXiv preprint arXiv:1510.00149 (2015).\n[4] Wang, Yunhe, et al. \"Cnnpack: Packing convolutional neural networks in the frequency domain.\" Advances in neural information processing systems. 2016.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "rJeAsR7iYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThis is a nice problem and the proposed approach is interesting  but I would tend to reject the paper. The main problem, in my opinion, is a substantial lack of theoretical justifications.  What are the intuitive motivations for considering the proposed method? It is hard to understand why the approach should be preferred to others.  The idea of converting the binary low-rank factorization problem into a real-valued non-negative factorization problem is interesting but \ncould have been better justified (from an intuitive/theoretical and computational perspective). For example, why is it convenient to convert a hard matrix factorization problem (BMF) into another hard matrix factorization problem (NMF). \nAn empirical or theoretical analysis of the algorithm's computational complexity would help in this sense.\n\nAlso, it is not completely clear what is the relationship of the proposed approach with the neural network framework. Would the impact of the paper increase if presented as a method for binary matrix factorization without links to neural networks pruning? Perhaps a quantitative comparison between gains associated with sparse matrix storage versus other computational costs (related to training or pruning) would help to better collocate the proposed approach in the deep learning framework.\n\nQuestions:\n- The general idea of approximating BMF with NMF is interesting and could be investigated independently and more deeply. Have the problem and the proposed solution appeared before in the matrix factorization literature (without connections to neural network pruning )?\n- Is there any intuitive justification of why thresholding the matrix before and after the factorization leads to consistent results?\n- The cost of the proposed approach seems to depend on the rank. Could such explicit dependence be estimated quantitatively and compared with the computational complexity of solving the problem (BMF) directly? \n\n- In the experiments, the value of the pruning objective seems to decrease as the rank of the factorization increases. Is this an expected result? What is even less clear to me is the behaviour of the test accuracy. Is it normal for the pruned network accuracy to increase with sparsity? And why does the performance look independent from the rank?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SyxuPw3RFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an algorithm to compress index data representing the sparsity of a (deep) neural network. The ultimate goal is to reduce the storage requirements for the masks.\n\nThe algorithm is based on non-negative matrix factorization so the original mask is decomposed into two smaller matrices leading to memory savings depending on the rank of the matrices.\nIn addition, the paper proposes a tiling approach to further reduce storage requirements. \nResults on selected architectures and datasets show some improvements compared to naive binary index representations\n\nOn the positive side, I see an interesting approach to pruning a neural network, assuming the storage cost is guiding the pruning algorithm. If this was integrated into the training process, the optimizer could lead to an optimal solution. \n\n\nOn the negative side, I find the paper not easy to follow/read. A few comments on this regard:\n\n- The motivation is not clear. The paper mostly targets unstructured sparsity (thus the need for sparse matrix representation). However, not really sure if just addressing the storage requirements would have the proper impact. In the end, the original matrix needs to be recovered from the factorization.\n- The organization of the paper is also confusing.  Section 2 is about factorization, NMS, then the MNIST case study \n- I missed a clear algorithmic section. The title/ conclusions suggest pruning, while the introduction suggests index compression (to me quite different). \nAlgorithm 1 is for the matrix factorization part but how is this integrated into the entire training / fine-tuning process? That is very confusing to me.  \n\n- Interestingly, page 3 starts by suggesting magnitude-based pruning is sub-optimal. However, during the experimental section and the last part of section 2, the paper suggests pruning weights with a large magnitude will damage the performance. That is unclear to me.\n\n- To my understanding, the experiments are not very convincing. Why only those selected architectures and within those pruning only FC layers (AlexNet)? Or, according to table 2 caption, part of the network is pruned using magnitude-based methods and the rest based on the new pruning. That is very confusing. This means the proposal is for pruning or for representing the indexes? If for pruning, why not applying to all the layers in the network? How do we distinguish between the relevance of magnitude pruning and the proposed method?\n- How are the different hyperparameters set (S, Sp, k..). \n- How does section 3.2 fits with the rest? Methods are vaguely described and then one of them used in the experimental section. Very confusing.\n- Table 5 suggests non-zero weights are quantized... I guess I am completely lost now :).  ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission proposes a method to improve over a standard binary network pruning strategy by the inclusion of a structured matrix product to encourage network weight sparsification that can have better memory and computational properties.  The idea is well motivated, but there were reviewer concerns about the quality of writing and in particular the quality of the experiments.  The reviewers were unanimous that the paper is not suitable for acceptance at ICLR, and no rebuttal was provided.
Decision: Reject