Title: PROBABILISTIC CONNECTION IMPORTANCE INFER-ENCE AND LOSSLESS COMPRESSION OF DEEP NEU-RAL NETWORKS

Abstract: Deep neural networks (DNNs) can be huge in size, requiring a considerable amount of energy and computational resources to operate, which limits their applications in numerous scenarios. It is thus of interest to compress DNNs while maintaining their performance levels. We here propose a probabilistic importance inference approach for pruning DNNs. Specifically, we test the significance of the relevance of a connection in a DNN to the DNN's outputs using a nonparemetric scoring test and keep only those significant ones. Experimental results show that the proposed approach achieves better lossless compression rates than existing techniques.

1. INTRODUCTION:

Deep neural networks (DNNs) have many successful applications ranging from computer vision, natural language processing to computational biology. However, large DNNs usually require significant memory and storage overhead and sometimes a large network bandwidth, which hinges their usages on mobile devices. Running large-size neural networks also consumes a considerable amount of energy, making their deployments on battery-constrained devices difficult. Furthermore, the over-parameterization issue in DNN architectures can impair its performances. Recent works (Han et al. (2015) ; Ullrich et al. (2017) ; Louizos et al. (2017) and references therein) show ways to reduce the network complexity by using proper regularization or network pruning to significantly reduce the number of parameters. One way to convert a dense DNN into a sparse one is by applying L 0 /L 1 regularization on the model parameters. The L 1 penalty is computationally efficient, but it also introduces more bias on the large weights and may lead to significant degradation in model performances (Han et al., 2015) . In contrast, L 0 regularization shows better performance, but incurs much higher computational complexity due to its combinatorial nature. Pruning, as shown in Han et al. (2015) and Tartaglione et al. (2018) , is another promising strategy to sparsify DNNs by only keeping network connections more relevant to the final output. The importance of a network connection (i.e., the connection between two network nodes) can be approximated by the magnitudes or gradients of its weights. However, such an approximation may not be accurate since it does not consider the highly nonlinear relationships between network connections and the final output induced by the multi-layer convolutions of DNNs. Some available network compression methods improve the computational performance with moderate to high losses in accuracy, which can be highly undesirable in many critical missions (such as autonomous driving). In order to achieve lossless compression, we need to correctly decipher the relationships between the network connections and the final output. This is a challenging task because the structural nature of DNNs makes the dependence between a network connection and the network output highly nonlinear. In this paper, we propose a probabilistic connection importance inference (PCII) method for testing whether a connection in a DNN is relevant to the DNN output. Specifically, we introduce a new technique called probabilistic tensor product decomposition to decompose the association of two connected network nodes into two components: one related to the DNN output and the other independent of the DNN output. If the strength of the first component is high, we keep the network connection. Otherwise, we delete it. The inference is carried out by a nonparametric score test, which is based on modeling the log-transformed joint density of the connected nodes and the final output in a tensor product reproducing kernel Hilbert space (RKHS). We further derive the asymptotic distribution of the proposed test statistics, thus avoiding the computationally intensive resampling step encountered in most nonparametric inference settings. We implemented the method and tested it on image classification tasks, in which our approach achieved the highest lossless compression rates.

Section 2 reviews relevant literature; Section 3 introduces the PCII method and algorithm; Section 4 establishes theoretical properties for using the method to infer dependence between a network connection and the DNN output; and Section 5 shows the experimental results and concludes with a short discussion. Zhu & Gupta (2017) found that a DNN can be greatly sparsified with minimal loss in accuracy. One strategy for sparsifying DNNs is to shrink small weights to zero. Along this line of thinking, Louizos et al. (2017) introduced a smoothed version of L 0 regularization aiming to be both computationally feasible and beneficial to generalizability. There are also some regularization methods based on Bayesian formulations. Ullrich et al. (2017) proposed to add a Gaussian mixture prior to the weights. The sparsity is achieved by concentrating weights to cluster centers. Molchanov et al. (2017) proposed variational dropout, which learns individual dropout rate based on the empirical Bayes principle. Also, as shown in Han et al. (2015) , the performance of pruning and retraining is related to choice the correct regularization, such as L 1 or L 2 regularization. PCII offers a means to prune a DNN by keeping network connections that are the most relevant to the DNN output. This idea goes back to the optimal brain damage work by LeCun et al. (1990) . It shows that among the many parameters in the network, many are redundant and do not contribute significantly to the output. Later, Hassibi et al. (1993) proposed the optimal brain surgeon method, which leverages a second-order Taylor expansion to select parameters for deletion. Most recently, Han et al. (2015) proposed a three-step pruning method. Tartaglione et al. (2018) proposed to prune a DNN based on the sensitivity score. There are also several approaches targeting at sparsifying convolution layers. For example, Anwar et al. (2017) proposed to prune feature maps and kernels in convolution layers.

2. RELATED WORKS:

Comparing with existing pruning methods based on the magnitude or gradient of weights, our approach directly models the relationship between a network connection and the network output in a nonparametric way. In addition, our inference is based on a statistical hypothesis testing, which outputs p-values to quantify the dependence strength of each network connection to the DNN output. The use of p-values allows network connections to be treated in a unified way and alleviates the need of ad hoc weights normalization required in some existing approaches.

3. PROBABILISTIC CONNECTION IMPORTANCE INFERENCE:

In this section, we establish a general procedure for building the probabilistic connection structure, in which the connections are inferred by the nonparametric score test in tensor product RKHS. As shown in our experiments (see Section 5), our technique not only sparsifies the network but improves its generalization ability.

3.1. PCII ON FULLY CONNECTED LAYERS:

Without loss of generality, we let a feed-forward acyclic DNN (Figure 1 ) be composed of T layers with X t being the input of the t-th network layer, where t = 0, 1, . . . , T . Let t = 0 and t = T indicate the input and output layers, respectively, and let 0 < t < T index the hidden layers. The collection of all the nodes is denoted as G and the collection of all network connections is denoted as E. We use a pair of nodes to denote a connection in E. For example, (X t,1 , X t+1,1 ) denotes an edge from the 1 st node in the t-th layer to the 1 st node in the (t + 1)-th layer. For simplicity, we use Y to denote the output layer, who takes on categorical values for a classification task, and takes on continuous values for regression. Figure 1 : Flowchart for probabilistic connection inference. We have two nodes α and β from a fully connected neural network. The connection of α and β is expressed as η α,β + η α,β,y . The importance of the connection is inferred by testing whether the three way interaction η α,β,y is zero or not.

The output of the (t + 1)-th layer can be described as

X t+1,j = g t+1 ( mt i=1 w i,j t,t+1 X t,i ), for j = 1, . . . , m t+1 ,

where m t denotes the number of nodes in the t-th layer, and g t+1 is the activation function. It should be noted that the magnitude of weights is not necessarily the best indication of the impact of the corresponding network connection. A more preferable way is to directly model the relationship between a network connection and the final output of a DNN. For simplicity, we use (α, β) to denote an arbitrary network connection. Due to the high non-linearity of a DNN, we use the nonparametric function to model the relationship among α, β and Y .

Let us denote the joint density of α, β and Y as f (α, β, y) and the log-transferred density as η(α, β, y).

We assume that η(α, β, y) can be deposed as

η(α, β, y) = η α + η β + η y + η α,y + η β,y + η α,β + η α,β,y

interaction between α and β ,

where η α , η β , and η y are marginal effects, η α,y , η β,y , and η α,β are the two-way interaction terms, η α,β,y is the three-way interaction term. Here, we interpret the connection as the interaction of α and β, i.e. η α,β + η α,β,y . Specifically, η α,β is the interaction effect of α and β without the impact of y, and η α,β,y characterizes the interaction of α, β impacted by y. Our aim is to measure the significance of the connection by how much it is related to Y . To model this problem mathematically, we measure the association between the connection and Y by the significance of the three-way interaction η α,β,y . Therefore, inferring whether the connection is related to the final output Y or not is equivalent to testing whether η α,β,y = 0 or not. As shown in Figure 1 , the connection is important for the network model if and only if the three-way interaction η α,β,y = 0. We propose a score test to qualify the significance of this term. The detailed construction of the statistical test is explained in Section 4.2.

3.2. PCII ON CONVOLUTIONAL LAYERS:

For different activation functions and type of layers, we have modifications to adopt the specific structure. Here, we generalize the proposed PCII test to handle convolutional layers, which are critical in many modern neural network architectures such as VGG16 Simonyan & Zisserman (2014) .

As demonstrated in Li et al. (2016) , sparsifying the filter has little effect on reducing the computation cost. Nevertheless, reducing the volume of filters can greatly increase computing efficiency. For example, the volume of a filter is 3 × 3 × 4. There are four 3 × 3 slices. PCII can be generalized to infer the importance of the slices, which can be treated as the connection between one channel in the current layer and one channel in the next layer. (shown as one slice with the red border). The importance of this connection is inferred by testing whether the three way interaction η α,β,y is zero or not.

Convolutional filters can be applied to transform channels in the t-th layer to channels in the (t + 1)-th layer. We denote the j-th channel in the t-th layer as X t,j for j = 1, . . . , m t , where m t is the number of channels in t-th layer and t = 0, . . . , T . Each filter connects all channels in the t-th layer to one channel in the t + 1-th layer. Let h i,j t,t+1 denote a convolution operator that connects two channels X t,i and X t+1,j . Then, the filter connected to X t+1,j is {h i,j t,t+1 } mt i=1 where we denote each h i,j t,t+1

as a slice of the filter. For example, when we choose a 3 × 3 × 4 filter and set stride as one, this operator is the filter convolved (slided) across the width and height of the input {X t,i } mt i=1 and offset with the bias. For one slice in the t + 1-th layer, we can write its connection with the slices in the previous layer as

X t+1,j = g t+1 ( mt i=1 h i,j t,t+1 (X t,i ) + b j t,t+1 )

where g t+1 is an activation function and b j t,t+1 is the bias for the j-th filter. As illustrated in Figure 2 , the red arrow from X t,1 to X t+1,mt+1 represents h 1,mt+1 t,t+1 , which is one slice of the filter {h i,mt+1 t,t+1 } mt i=1 connecting the channels in the t-th layer to channel X t+1,mt+1 in the t + 1-th layer. For simplicity, we denote α as one channel in the current layer and β as one channel in the next layer. Since the relationship among the triplet (α, β, Y ) is highly nonlinear, we model its log-transformed joint density as a nonparametric function η(α, β, y). Similar to the fully connected layers, we assume that η(α, β, y) has a decomposition as in (1). As shown in Figure 2 , the connection between α and β is decomposed to two parts: one unrelated to the output Y , η α,β , and another related to the output Y , η α,β,y . We aim to select connections that have greater contributions to Y , which is mathematically translated into the task of assessing the significance of the three-way interaction term η α,β,y against the null hypothesis η α,β,y = 0.

3.3. ALGORITHM:

In real applications, both fully connected layers and convolutional layers are used in a complex neural network architecture. We integrate the PCII procedure described in the previous two subsections to simultaneously infer the connections in both fully connected and convolutional layers, as summarized in Algorithm 1. We use p (t) ij to denote the p-value for testing the i-th node in t-th layer and j-th node in (t + 1)-th layer for the fully connected layers. For convolutional layers, p Step 2: (a). Importance inference of connections in fully connected layers: infer the three-way dependence effect of a network connection by testing the hypothesis H 0 : η α,β,y = 0 v.s H 1 : η α,β,y = 0, and calculate the test statistics (or p-values) for all network connections as p f = {p t,t+1 i,j , i = 1, . . . , m t , j = 1, . . . , m t+1 | t and t + 1 layers are fully connected}. (b). Importance inference of connections in convolutional layers: infer the three-way dependence effect of a network connection by testing the hypothesis H 0 : η α,β,y = 0 v.s H 1 : η α,β,y = 0, and calculate the test statistics (or p-values) for all network connections as p c = {p t,t+1 i,j , i = 1, . . . , m t , j = 1, . . . , m t+1 | t and t + 1 layers are convolutionally connected}.

Step 3: Rank all network connections by their test statistics (or p-values), and select a threshold ρ f for deleting network connections in fully connected layers and ρ c in convolutional layers to achieve the desired model compression rate (Strategies for choosing ρ f and ρ c are given in Section 5).

Step 4: Set the same initial value for non-zero weights and filters. Retrain the sparsified DNN.

4. SCORE TEST AND THEORETICAL PROPERTIES:

4.1 BACKGROUND ON TENSOR PRODUCT RKHS Consider two random variables α and β for fully connected layers or two random vectors α and β for convolutional layers. Let Y be a random variable as the final output. The domains for α, β and Y are A, B, and Y, respectively. Here, we assume that the log-transformed joint density function η belongs to a tensor product RKHS H = H α ⊗ H β ⊗ H Y where ⊗ denotes the tensor product of two linear space.

For marginal RKHS, H l with an inner product •, • H l for l = α, β, Y , there exists a symmetric and square integrable function K l such that

f, K l (x, •) H l = f (x), for all f ∈ H l (2)

where K l is called the reproducing kernel of H l for l = α, β, Y . By Mercer's theorem, any continuous kernel has the following decomposition

EQUATION

where the µ ν 's are non-negative descending eigenvalues and the φ ν 's are eigen-functions. For the discrete domain {1, . . . , a}, we define the kernel as K(x, y) = 1{x = y} for x, y ∈ {1, . . . , a}. For a continuous domain, there are different choice of kernels such as Gaussian kernels and Sobolev kernels. Note that the eigenvalues for different kernels on continuous domain have different decay rate. For example, the eigenvalues of the Gaussian kernel have the exponential decay rate, i.e., there exists some c > 0 such that µ ν exp(-cν) (Sollich & Williams, 2004) ; and the eigenvalues of the m-th Sobolev kernels have the polynomial decay rate, i.e., µ ν ν -2m (Gu, 2013) .

4.2. PROBABILISTIC DECOMPOSITION OF TENSOR PRODUCT RKHS:

Next we propose the probabilistic tensor sum decomposition for each marginal RKHS, H l , for l = α, β, Y . We first use Euclidean space as a simple example to illustrate the basic idea of tensor sum decomposition. Recall that the tensor sum decomposition is often called ANOVA decomposition in linear model. For example, for the d-dimensional Euclidean space, we denote f as a vector and let f (x) be the x-th entry of the vector for x = 1, . . . , d. We denote A as an average operator defined as Af (x) = 1 d 1, f . The tensor sum decomposition of the Euclidean space R d is

R d = R d 0 ⊕ R d 1 := span{ 1 d 1} ⊕ {f ∈ R d | d i=1 f (d) = 0} (4)

where the first space is called the grand mean and the second space is called the main effect. Then, we construct the kernel for R d 0 and R d 1 in the following lemma. Lemma 1. For a RKHS space H, there corresponds a unique reproducing kernel K, which is non-negative definite. Based on the tensor sum decomposition H = H 0 ⊕ H 1 , where H 0 = {1/d1} and H 1 = {g ∈ H : E X (g(X)) = 0}, we have the kernel for H 0 as k 0 (x, y) = 1/d

(5)

and kernel for H 1 as k 1 (x, y) = 1 {x=y} -1/d where 1 denotes the indicator function.

However, in RKHS with infinite dimension, the grand mean is not a single vector. Here, we set the average operator A as

A := f → E x f (x) = E x k x , f H = Ek x , f H

where k is the kernel function in H and the first equality is due to the reproducing property. E x k x plays the same role as 1 d 1 in Euclidean space. Then, we have the tensor sum decomposition in a functional space defined as

EQUATION

Following the same fashion, we call H 0 as the grand mean space and H 1 as the main effect space.

Notice that E x k x is also known as the kernel mean embedding which is well established in the statistics literature Berlinet & Thomas-Agnan (2011) . Then we introduce the following lemma to construct the kernel function for H 0 and H 1 . Lemma 2. For RKHS space H, there corresponds an unique reproducing kernel K, which is nonnegative definite. Based on the tensor sum decomposition

H = H 0 ⊕ H 1 where H 0 = {E x k x } and H 1 = {g ∈ H : E x (g(x)) = 0}

, we have the kernel for H 0 as

EQUATION

and the kernel for H 1 as

k 1 (x, y) = k x -Ek x , k y -Ek y H = k(x, y) -E x [k(x, y)] -E y [k(x, y)] + E x,y k(x, y).

In neural networks, A, B are in a continuous domain. The final output Y can be either in continuous domain or discrete domain, which depends on the tasks. Here, we construct the tensor sum decomposition for discrete domain and continuous domain based on Lemma 1 and Lemma 2 respectively. Specifically, we have spaces H α , H β and H Y decomposed as tensor sums of subspaces

H α = H α 0 ⊕ H α 1 , H β = H β 0 ⊕ H β 1 , H Y = H Y 0 ⊕ H Y 1 .

Following Gu (2013), we apply the distributive law and have the decomposition of H as

EQUATION

)

where

H ijk = H α i ⊕ H β j ⊕ H Y k . Lemma 3. Suppose K 1 is the reproducing kernel of H 1 on X 1 , and K 2 is the reproducing kernel of H 2 on X 2 . Then the reproducing kernels of H 1 ⊗ H 2 on X = X 1 × X 2 is K(x, y) = K 1 (x 1 , y 1 )K 2 (x 2 , y 2 ) with x = (x 1 , x 2 ) and y = (y 1 , y 2 ).

Lemmas 3 can be easily proved based on Theorems 2.6 in Gu (2013) . Lemma 3 implies that the reproducing kernels of the tensor product space is the product of the reproducing kernels. Based on these three lemmas, we can construct kernel for each subspace defined in (8).

4.3. SCORE TEST:

Based on (8), the log-transformed density function η ∈ H can be correspondingly decomposed as (1). Thus, η α,β,Y = 0 if and only if η * ∈ H 0 := H 000 ⊕ H 100 ⊕ H 010 ⊕ H 001 ⊕ H 110 ⊕ H 101 ⊕ H 011 where η * is the underlying truth. Hence, we focus on the following hypothesis testing problem:

EQUATION

where H\H 0 denotes set difference of H and H 0 . We next propose a likelihood-ratio based procedure to test (9). Suppose that t = (α, β, y) and t i = (α i , β i , y i ), i = 1, . . . , n, are iid observations generated from T = (A, B, Y). Let LR n be the likelihood ratio functional defined as

EQUATION

)

where P H0 is a projection operator from H to H 0 . Using the reproducing property, we rewrite (10) as

EQUATION

)

where K is the kernel for H and K 0 is the kernel for H 0 .

Then we calculate the Fréchet derivative of the likelihood ratio functional as

DLR n (η)∆η = 1 n n i=1 (K ti -K 0 ti ), ∆η H = 1 n K 1 ti , ∆η H (12)

where K 1 is the kernel for H 111 . We define our test statistics as the squared norm of the score function of the likelihood ratio functional as

EQUATION

)

By the reproducing property, we can expand the left hand side of (13) as

EQUATION

We observe an interesting phenomenon that S 2 n has a similar expression with the MMD (Gretton et al., 2012) when Y is a binary variable. When Y ∈ {0, 1}, the kernel on

EQUATION

EQUATION

EQUATION

EQUATION

)

If we replace K α,β 11

with K α,β , i.e., the kernel on the H α ⊗ H β , the right hand side of ( 15) is the MMD measuring the distance between the joint distribution of α and β in the group with y = 0 and the joint distribution of α and β in the group with y = 1.

EQUATION

Since we want to infer the importance of the connection between the α and β, we are only interested in comparing whether the interaction effect between α and β changes or not in the two groups. The main effects of α and β only contribute to the importance of the nodes or slices and are not relevant to the connection between α and β.

4.4. CALCULATION OF THE TEST STATISTICS:

We introduce a matrix form of the squared norm of score function for manifesting the computation process. In ( 14), S 2 n is determined by the kernel on th

H α 1 ⊗ H β 1 ⊗ H Y 1 .

By Lemma 1 and Lemma 2, we replace the expectation by the sample average and get the kernel function for H l l as

k l 1 (x, y) = k l (x, y) - 1 n n i=1 k l (x i , y) - 1 n n i=1 k l (x, y i ) + 1 n 2 n i=1 n j=1 k l (x i , y j )

where k l is the kernel function for H l for l = α, β, Y . Some popular choices of the kernel functions are Gaussian kernel, Laplace kernel and polynomial kernel. Let K l be the empirical kernel matrix. We can rewrite (14) as

EQUATION

where H = I n -1 n 11 T , I n is a n × n identity matrix and 1 n is a n × 1 vector of ones, and

[A] ++ = n i=1 n j=1 A ij .

This test statistics is also related to three-way Lancaster's interaction measure (Lancaster, 2002) .

Fortunately, the computation of ( 17) only involves the matrix multiplication, the computational procedure can be executed in parallel on GPU. In our experiment, the highly parallelized matrix operation tremendously alleviated the computing time: essentially reducing from quadratic to almost linear. In addition, we can reduce the sample size by sub-sampling r << n data points. Sub-sampling the dataset is a popular technique to reduce computational burden and can efficiently approximate the full data likelihood in a regression setting (Ma et al., 2015; Drineas et al., 2011) . However, for very large data set, the sub-sampling is not efficient. We consider a mini-batch algorithm to calculate the score in each batch and used the averaged score as the final test statistics. This is also related to the divide-and-conquer method which is widely used in kernel-based learning (Zhang et al., 2013; Shang & Cheng, 2017; Liu et al., 2018) .

4.5. ASYMPTOTIC DISTRIBUTION:

The asymptotic distribution of S 2 n depends on the decay rate of the kernel of the product of RKHS. Suppose that {µ

α ν , φ α ν } ∞

ν=1 is a series of eigenvalue and eigenfunction pairs for

H α 1 , {µ β ν , φ β ν } ∞ ν=1 is a sequence of basis for H β 1 . If Y is continuous, we suppose that H Y has the eigensystem, {µ Y ν , φ α ν } ∞ ν=1 . If Y is categorical, we suppose that H Y has the eigensystem, {µ Y ν , φ α ν } a-1

ν=1 . Then we have the eigenvalue eigenfuntion pair for the tensor product space

H α 1 ⊗ H β 1 ⊗ H Y 1 as {µ α να µ β ν β µ Y ν Y , φ α να φ β ν β φ Y ν Y } where ν α = 1, . . . , ∞, ν β = 1, . . . , ∞, ν Y = 1, . . . , ∞ (Y is continuous)

, and ν Y = 1, . . . , a -1 (Y is categorical with a categories). For simplicity, we order the pairs in the decreasing order of µ ρ , ρ = 1, . . . , ∞. The null hypothesis could be interpreted as factorization hypothesis, i.e., (X, Y ) ⊥ Z ∨ (X, Z) ⊥ Y ∨ (Y, Z) ⊥ X or X, Y, Z are mutually independent. Theorem 1. Suppose the kernel on H 111 is square integrable. If Y is continuous variable, then under H 0 , we have

nS 2 n d -→ ∞ ρ=1 µ ρ 2 ρ (18)

where ρ are i.i.d. standard Gaussian random variables.

The proof of this theorem is shown in the Supplementary Materials A.1. The asymptotic distribution of nS 2 n only depends on the eigenvalues of the kernel. Theorem 1 is related to Wilks' phenomenon demonstrated in the classic nonparametric/semiparametric regression framework (Fan et al., 2001; Shang & Cheng, 2013) , i.e., the asymptotic distribution is independent of the nuisance parameters. In practice, we fix the same kernel for the fully connected layers and the same kernel for the convolutional layers. Thus, it provides a unified importance measure for all connections in the same type of layer, which avoids the scaling problem faced by those pruning methods that use magnitudes of weights as an importance measure. In addition, we can use the value of the test statistics as an importance measure for pruning and bypass the effort of calculating the p-values since the order is the same according to either of these two measures.

5. RESULTS:

We conducted experiments to test out the PCII method in two supervised image classification tasks: MNIST and CIFAR10. We used TensorFlow to train DNNs. The back-end of PCII was implemented in Fortran and R language. Programming interfaces were implemented to connect the back-end calculations to TensorFlow. The experiments were run on a computer with one Nvidia Titan V GPU and 48 CPU cores.

PCII offers a convenient way to adjust compression rate by changing the p-value threshold ρ. For other compression methods in consideration, the compression rate is usually controlled by some hyper-parameters, which need to be tuned via an ad hoc trial and error strategy. Two types of comparisons were carried out. In the first type, we adjust the compression rate of a method while requiring its compressed DNN to achieve the test accuracy of the original uncompressed DNN. We term this the lossless compression rates (LCR). Since it is very time-consuming to obtain an exact test accuracy, we allow a 0.01% deviation from the desired test error rates. In the second type, we compared the minimum testing error (MTE) of the compressed DNNs produced by different model compression methods. MTE shows how a compression method can help increase the generalizability and robustness of a DNN. We only included the results of the tested methods that we could obtain their working codes to reproduce the results reported in their original papers. In addition, we did not include methods that are not able to achieve the LCR of the corresponding test dataset.

5.1. MNIST DATASET:

We tried two network architectures for MNIST (60k training images and 10k test images): a multilayer perceptron (MLP) with two hidden layers of sizes 300 and 100, respectively, and a convolutional neural network LeNet-5 (LeCun et al. (1998) ). We trained LeNet-300-100 for 100 epochs to achieve a test error of 1.69%. These approaches include two regularization based methods in Louizos et al. (2017) , as well as several pruning based methods in Han et al. (2015) , and Guo et al. (2016) . The results are summarized in Table 1 . PCII achieved the lowest MTE when the compression rate was 10x. Then, we further increased the compression rate until the error rate reached 1.70%. The results show that PCII not only compressed a medium-sized MLP better than existing methods but also was able to improve generalizability of a MLP via compression (i.e., the MTE is better than the LCR). Interestingly, our inference results can also help in interpreting the fitted neural network. For example, through inferring the importance of the connections between input layer and the the first hidden layer, we can visualize the importance of the features in the input layer. Figure 3 

5.2. CIFAR10 DATASET:

To demonstrate the applicability of PCII to complex DNNs, we applied it to VGG16 (Zagoruyko, 2015) , which was adapted for the CIFAR-10 dataset (Krizhevsky & Hinton, 2009) . The network consists of 13 convolutional and two fully-connected layers. The results are summarized in Table 3 . The test error gradually decreases as the compression rate increases from 1x to 3x, and achieves the MTE at 6.01%. When the compression rate is further increased, the test error begins to increase.

As the compression rate reaches 10x, the test error increases to 7.56% that is comparable to the test error of the uncompressed VGG16. For this dataset, we only include the result for PCII due to the limited resources. In fact, we could not obtain the results for other methods in comparison in three days' computing time.

Dataset: CIFAR10, Network: VGG16 

6. DISCUSSION:

We propose a statistically principled strategy to directly infer the importance of a connection in a neural network via PCII, a hypothesis testing framework. The proposed PCII test provides a p-value based measure on the importance of the connection through the connection's association with the final output. This type of direct quantification cannot be easily accomplished by the magnitude-based pruning method. Although the two examples are relatively small in size, they demonstrated the broad applicability of the PCII method and its improved power in network compression. Last but not least we note that the PCII testing method can be easily generalized to a broad class of connection types including the skip layer connections in RNN.

:



Figures and Tables:

(t) ij denotes the p-value for inferring the importance of the filter connecting the i-th slice in the t-th layer and the j-th slice in the t + 1-th layer. The calculation of the p-values are given in Section 4 based on our proposed Score test.Algorithm 1 PCII: Probabilistic Connection Importance Inference for Lossless Neural Network CompressionInput: A training dataset, a DNN architecture, and the desired model compression rateStep 1: Use the training dataset to train a DNN of the given architecture.

Figure 3: The heatmap showing the PLR test result of the 784 × 300 connections between the input layer and the first FC layer in Lenet-300-100. Each pixel represents a p-value of the corresponding pair. The brighter color representing a smaller p-value. The width and height of the heatmap correspond to the input dimension (784) and the size (300) of the first FC layer.

Experimental results for LeNet-300-100 on MNIST dataset.

Table content: <table><tr><td/><td colspan="3">Dataset: MNIST, Network: LeNet-300-100</td></tr><tr><td>Criterion</td><td colspan="3">Method Error % Compression Rate</td></tr><tr><td/><td>Original</td><td>1.69%</td><td>1x</td></tr><tr><td/><td>PCII</td><td>1.70%</td><td>26x</td></tr><tr><td>LCR</td><td>Han et al. (2015) Louizos et al. (2017)</td><td>1.69% 1.70%</td><td>15.1x 3.3x</td></tr><tr><td/><td>Guo et al. (2016)</td><td>1.70%</td><td>15x</td></tr><tr><td/><td colspan="2">PCII 1.58%</td><td>10x</td></tr><tr><td>MTE</td><td>Han et al. (2015) Louizos et al. (2017)</td><td>1.59% 1.70%</td><td>12.2x 3.3x</td></tr><tr><td/><td>Guo et al. (2016)</td><td>1.70%</td><td>15x</td></tr></table>

plots the p-values of the associations between the network connections in the first layer and the final output. The heatmap shows that a banded structure repeated 28 times, in which the central region tends to have smaller p-values. The left and right margins of the heatmap show that the connections on the first and last few channels are less relevant to the final output (i.e., have large p-values). This phenomenon is observed because a written digit is usually located in the central part of a image. Experimental results for LeNet-5-caffe on MNIST dataset.The LeNet-5 model (https://goo.gl/4yI3dL) is a modified version ofLeCun et al. (1998). It includes two convolutional layers with 20 and 50 filters, respectively, and a fully connected layer with 500 nodes. The results are summarized in Table2. PCII achieved both the lowest MTE and highest LCR, again, for this model, demonstrating the broad applicability of the PCII strategy for various neural network architectures.

Table content: <table><tr><td/><td colspan="2">Dataset: MNIST, Network: LeNet-5</td><td/></tr><tr><td>Criterion</td><td colspan="3">Method Error % Compression Rate</td></tr><tr><td/><td>Original</td><td>0.70%</td><td>1x</td></tr><tr><td/><td colspan="2">PCII 0.69 %</td><td>38x</td></tr><tr><td>LCR</td><td>Han et al. (2015) Louizos et al. (2017)</td><td>0.71% 0.69%</td><td>12.1x 1.4x</td></tr><tr><td/><td>Guo et al. (2016)</td><td>0.70%</td><td>32x</td></tr><tr><td/><td colspan="2">PCII 0.65%</td><td>10.7x</td></tr><tr><td>MTE</td><td>Han et al. (2015) Louizos et al. (2017)</td><td>0.70% 0.68%</td><td>6x 1.1x</td></tr><tr><td/><td>Guo et al. (2016)</td><td>0.70%</td><td>32x</td></tr></table>

Experimental results for VGG16 on CIFAR10 dataset.

Table content: <table><tr><td colspan="3">Criterion Method Error Compression Rate</td></tr><tr><td/><td>Original 7.55%</td><td>1x</td></tr><tr><td>LCR</td><td>PCII 7.56%</td><td>10x</td></tr><tr><td>MTE</td><td>PCII 6.01%</td><td>3x</td></tr></table>

Peer review (iclr2020):
In this paper, the authors propose a new pruning technique that utilizes the statistical dependency between the corresponding nodes and outputs. The dependency is measured by a kernel based dependency measure which is closely related to MMD. The test statistics derived from the dependency measure have an asymptotic distribution which can be written as a weighted sum of chi-square random variables. The proposed method is numerically investigated using some datasets such as MNIST and CIFAR 10. Pruning is one of important problems for practical deep learning operations. This paper gives an interesting idea for the pruning techniques. I think the idea is novel. On the other hand, I also have the following concerns: - Although applying the kernel type information measure is an interesting idea, its computational complexity would be large. It is not obvious that it works for large datasets such as ImageNet even if the sub-sampling technique is applied. - The numerical experiments are conducted in small datasets. How it works in larger datasets such as ImageNet and (more importantly) how it is compared with SOTA pruning methods in more difficult datasets. Actually, performance comparison is not done for the CIRAR10-VGG16 setting. - The asymptotic distribution can be seen as a corollary of existing researches for MMD and HSIC. For these reasons, I was not completely convinced with the effectiveness of the proposed method. Minor comment: - The test statistics is more like HSIC. It would be nice if there were comments on the connection to HSIC. === Update: The computational cost for this method seems not so much demanding, and could be applied to large data-set. The resultant performance also seems useful. I think more convincing comparisons are needed. However, its idea seems interesting and its practicality is ensured to some extent. Thus, I have raised my score.