Title: NETWORK PRUNING FOR LOW-RANK BINARY INDEX

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.

1. INTRODUCTION:

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

IA = [ 0 2 2 5 7] JA = [ 0 3 0 1 3 0 1] 1 0 0 1 0 0 0 0 1 1 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 3 0 0 4 0 0 0 0 4 3 0 5 3 6 0 0

Dense Matrix after Pruning:



CSR Index Format:

Binary Index Format 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.

Binary Index Decomposition:

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.

2. BINARY MATRIX FACTORIZATION FOR PRUNING INDEX:

Suppose that a 5 × 5 weight matrix W is given as

EQUATION

)

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

EQUATION

)

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 I m×k p and I k×n z to approximate I as I ≈ I p ⊗ I z = I a , where k corresponds to the binary matrix factorization rank and ⊗ stands for binary matrix multiplication. A binary product of I p and I z is then defined as

(I a ) i,j = k l=1 (I p ) i,l ∧ (I z ) l,j .

(3)

While BMF should minimize the number of mismatched bits between I and I a , 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.

2.1. BINARY MATRIX FACTORIZATION BASED ON NON-NEGATIVE MATRIX FACTORIZATION:

Non-negative matrix factorization (NMF) factorizes a real-valued matrix H into two real-valued matrices H 1 and H 2 under the constraint that all three matrices consist of non-negative elements. Similar to singular-value decomposition (SVD), NMF attempts to minimize ||H -H 1 H 2 || 2 F , 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., M i,j = |W i,j |). and M is factorized by an NMF library (e.g., (Zitnik & Zupan, 2012 )) into two matrices M p and M z . For example, a magnitude matrix M of the matrix W of Eq. ( 1) can be factorized into

EQUATION

where rank k is 2.

The next step is to convert M p and M z into two binary matrices I p and I z using threshold values T p and T z (i.e., (I p ) i,j = 1 if (M p ) i,j ≥ T p , or 0 otherwise). The sparsity of I p and I z can each be controlled by T p and T z . Our goal is to achieve similar sparsity between I and I p ⊗ I z . Suppose that T p = 0.5 and T z = 0.6 are carefully chosen to produce similar sparsity as I. We obtain

I p =      0 1 1 0 0 1 0 1 1 0      , I z = 1 0 1 1 0 0 1 1 0 1 (5)

and the binary product of I p and I z becomes

EQUATION

)

Compared with the pruning-index matrix I in Eq. ( 2), there are 2 mismatched elements (underlined in Eq. ( 6)). The rationale behind this approach is as follows: 1) If M i,j is large, then its corresponding k components of M p and M z (i.e., (M p ) i,: and (M z ) :,j ) will also be large with high probability and, correspondingly, 2) Binary matrix conversion using T p and T z would yield a high probability of being '1' within I p and I z if the corresponding M i,j is large. Note that in order to match 'OR' operations in Eq. ( 3), negative values in M p or M z are not allowed. Thus, SVD is not applicable for our proposed scheme. Let S, S a , S p , and S z be the sparsity of I, I a , I p , and I z , respectively. From the dot product operation in Eq. ( 6), the expression for pruning rate S becomes

EQUATION

assuming that the probability of a bit being '0' in I p and I z follows S p and S z . Then, S z = (S 1/k -S p )/(1 -S p ), which needs to be fine-tuned in practice. If T p and associated S p are given, then T z and S z are automatically determined by the target pruning rate. Subsequently, given W and rank k, it is necessary to find a certain S p that produces the best masking layer for pruning.

In order to optimize S p , we define the cost function for pruning-index compression to be M i,j , where (I) i,j = 1 and (I a ) 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 S p by sweeping S p and monitoring Cost. Given the linear relationship between S a and S z , the algorithm can use binary search to expedite adjustment of S z .

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 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 S z , Cost, and test accuracy across a range of S p values. Pruning rate S for FC1 is 95% and rank k is 16, 64, or 256. As k increases, both I p and I z 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 60K th iteration using a masking layer I a . The test accuracy (the average of 20 runs) is measured at the 20K th (right after pruning), 40K th , 50K th , and 60K th 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 20K th 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 Table 3 : Memory footprint of FC1 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.

Method:

Index 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.

3. INDEX MATRIX TILING AND WEIGHT MANIPULATION TO LOWER RANK:

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).

3.1. TILE-BASED BINARY MATRIX FACTORIZATION:

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 X 1 , X 2 , . . ., X n 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, M p and M z also show larger variance with longer tails in the distribution with more blocks as shown in Figure 5 . Such increased variance of M p and M z 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 p and S z (and hence, increases the chance to further optimize the cost function). Each submatrix is factorized by NMF using different rank depending on the tiling plan to present the same overall compression ratio. Rank 128, 64 or 32 is used for (1 × 1), (2 × 2), or (4 × 4) tiling, respectively.

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.

3.2. WEIGHT MAGNITUDE MANIPULATION:

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. M i,j → M 2 i,j , Method 3: M i,j is amplified by 1/(1-S) if M i,j is larger than a threshold value (given by a magnitude-based pruning), where S is the sparsity of W .

4. EXPERIMENTAL RESULTS:

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

5. CONCLUSION:



:

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.

Figures and Tables:

Figure 1: Comparison on various sparse matrix representation formats.

Binary pruning-index-data matrix factorization input : W ∈ R m×n , rank k, target sparsity S output: I p ∈ {0, 1} m×k , I z ∈ {0, 1} k×n 1: Generate the magnitude matrix M using W 2: M p , M z = NMF(M , k) 3: Cost min ← ∞, S min p ← 0.0, S min z ← 0.0 4: for S p = 0.0 to 1.0 do 5:Compute S z using Eq. (7) 6:

p ,M z ) into (I p ,I z ) w/ (S p , S z ) 8: Adjust S z depending on (S a -S) 9: until S a ≈ S 10: Cost ← Ii,j =1,(Ia)i,j =0 M i,j 11: if Cost min > Cost then 12: Cost min ← Cost, S min p ← S p , S min z ← S z 13: end if 14: end for 15: Convert (M p , M z ) into (I p , I z ) w/ (S min p , S min z ) 16: Return I p , I z

Figure 2: S z , Cost, and test accuracy for various S p when the FC1 layer's pruning-index data of LeNet-5 model is factorized by Algorithm 1 using S=0.95, k = 16, 64, or 256.

Figure 3: Histogram of unpruned weights of FC1 layer at 20K th iteration using LeNet-5 model. Higher k results in more near-zero weights pruned.

Figure 4: (Left): (n × m) binary matrix factorization using one or four tiles when the compression ratio is the same. (Right): Weight histogram before and after NMF using different number of tiles.

Figure 5: Histogram of M p and M z values using different number of tiles.

Figure 7: Histogram of unpruned FC1 layer weights of LeNet-5 with different weight magnitude manipulation methods (Method 1: no manipulation, Method 2: M i,j → M 2i,j , Method 3: M i,j is amplified by 1/(1-S) if M i,j is larger than a threshold value (given by a magnitude-based pruning), where S is the sparsity of W .

Index size divided by weight data size when weights are quantized to be Q bits and pruned to obtain sparsity S.

Table content: <table><tr><td/><td colspan="2">CSR Index</td><td/><td colspan="2">Binary Index</td><td/></tr><tr><td/><td colspan="6">16-bit Index 5-bit Index S=0.6 S=0.7 S=0.8 S=0.9</td></tr><tr><td>Q=1</td><td>16.0×</td><td>5.0×</td><td>2.5×</td><td>3.3×</td><td colspan="2">5.0× 10.0×</td></tr><tr><td>Q=2</td><td>8.0×</td><td>2.5×</td><td>1.3×</td><td>1.7×</td><td>2.5×</td><td>5.0×</td></tr><tr><td>Q=3</td><td>5.3×</td><td>1.7×</td><td>0.8×</td><td>1.1×</td><td>1.7×</td><td>3.3×</td></tr><tr><td>Q=4</td><td>4.0×</td><td>1.3×</td><td>0.6×</td><td>0.8×</td><td>1.3×</td><td>2.5×</td></tr></table>

(MNIST LeNet-5 accuracy using different rank k. At the 20K th iteration, we prune all layers using magnitude-based pruning method(Han et al., 2015) except FC1 layer where pruning is performed by using Algorithm 1. Retraining is completed at the 60K th iteration. The test accuracy of pre-trained model is 99.2%.

Table content: <table><tr><td colspan="2">Rank</td><td/><td/><td colspan="2">Accuracy(%)</td><td>Comp.</td></tr><tr><td colspan="2">(k)</td><td colspan="5">20K th 40K th 50K th 60K th</td><td>Ratio</td></tr><tr><td>4</td><td/><td colspan="5">33.69 98.96 99.03 99.07 76.9×</td></tr><tr><td>8</td><td/><td colspan="5">34.52 98.98 99.05 99.09 38.5×</td></tr><tr><td>16</td><td/><td colspan="5">30.28 99.01 99.09 99.13 19.2×</td></tr><tr><td>32</td><td/><td colspan="5">32.52 99.01 99.08 99.13</td><td>9.6×</td></tr><tr><td>64</td><td/><td colspan="5">36.02 99.04 99.10 99.14</td><td>4.8×</td></tr><tr><td colspan="2">128</td><td colspan="5">34.22 99.04 99.10 99.16</td><td>2.4×</td></tr><tr><td colspan="2">256</td><td colspan="5">42.86 99.07 99.14 99.19</td><td>1.2×</td></tr><tr><td colspan="2">1200</td><td/><td/><td/><td/></tr><tr><td colspan="2">1000</td><td/><td/><td/><td/></tr><tr><td/><td>800</td><td/><td/><td/><td/></tr><tr><td>Count</td><td>600</td><td/><td/><td/><td/></tr><tr><td/><td>400</td><td/><td/><td/><td/></tr><tr><td/><td>200</td><td/><td/><td>rank 16 rank 64</td><td/></tr><tr><td/><td>0</td><td/><td/><td>rank 256</td><td/></tr><tr><td/><td/><td>-0.3</td><td>-0.2</td><td>-0.1</td><td>0</td><td>0.1</td><td>0.2</td></tr><tr><td/><td/><td/><td/><td colspan="2">Weight Value</td></tr></table>

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 as well). 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.

Table content: <table><tr><td colspan="3">Pre-trained Model</td><td colspan="4">Pruned Model using the Proposed Method</td></tr><tr><td>Model</td><td># of Weights</td><td>Accuracy</td><td>S</td><td>Rank</td><td>Index Data Comp. Ratio</td><td>Accuracy</td></tr><tr><td>ResNet32 on CIFAR-10</td><td>460.76K</td><td>92.5%</td><td>0.70</td><td>8/16/32 1 8/8/8</td><td>3.09× 5.12×</td><td>91.8% 91.5 %</td></tr><tr><td>AlexNet on ImageNet (FC5, FC6)</td><td>9K×4K (FC5) 4K×4K (FC6)</td><td>80.3% (top5) 57.6% (top1)</td><td>0.91</td><td>32 tiled 2 64 tiled 2</td><td>8.20× 4.14×</td><td>80.4% (top5) 57.1% (top1) 80.3% (top5) 57.2% (top1)</td></tr><tr><td>LSTM on PTB</td><td>6.41M</td><td>89.6 PPW</td><td>0.60</td><td>145</td><td>1.82×</td><td>89.0 PPW</td></tr><tr><td>1</td><td/><td/><td/><td/><td/><td/></tr></table>

Compression results on FC5 and FC6 layers of AlexNet with various index formats when S is to be the same as 0.91 for both layers and non-zero weights are 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.

Table content: <table><tr><td>Method</td><td colspan="2">Index Size Non-Zero Weights</td><td>Sum</td><td>Comment</td></tr><tr><td>Binary</td><td>6656KB</td><td>1198KB</td><td>7854KB (100%)</td><td/></tr><tr><td colspan="2">CSR(16bit) 10061KB</td><td>1198KB</td><td>11259KB (143.3%)</td><td/></tr><tr><td>CSR(5bit)</td><td>3144KB</td><td>1198KB</td><td>4342KB (55.3%)</td><td>Relative Indexing</td></tr><tr><td>Viterbi</td><td>1331KB</td><td>1198KB</td><td>2529KB (32.2%)</td><td>5X Encoder</td></tr><tr><td>Proposed</td><td>812KB</td><td>1198KB</td><td>2010KB (25.6%)</td><td>k=32, tiled</td></tr></table>

Peer review (iclr2020):
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 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 could 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). An empirical or theoretical analysis of the algorithm*s computational complexity would help in this sense. Also, 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. Questions: - 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 )? - Is there any intuitive justification of why thresholding the matrix before and after the factorization leads to consistent results? - 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? - 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?