Probabilistic Connection Importance Inference and Lossless Compression of Deep Neural Networks
Authors: Xin Xing
Long Sha
Pengyu Hong
Zuofeng Shang
Jun S. Liu
Venue:  (2020)

Abstract: Deep neural networks (DNNs) can be huge in size, requiring a considerable a mount 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 nonparemtric scoring testand keep only those significant ones. Experimental results show that the proposed approach achieves better lossless compression rates than existing techniques

Published as a conference paper at ICLR 2020
PROBABILISTIC CONNECTION IMPORTANCE INFER- ENCE AND LOSSLESS COMPRESSION OF DEEP NEU- RAL NETWORKS
Xin Xing Harvard University
Long Sha Brandeis University
Pengyu Hong
Brandeis University
Zuofeng Shang
Jun S. Liu
New Jersey Institute of Technology
Harvard University
ABSTRACT
Deep neural networks (DNNs) can be huge in size, requiring considerable amount of energy and computational resources to operate, which limits their applications in numerous scenarios. It is thus of interest 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.
INTRODUCTION
Deep neural networks (DNNss) have many successful applications ranging from computer vision, natural language processing to computational biology. However, large DNNs usually require sig- nificant 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, issue in DNN architectures can impair its performances. Recent works (Han et al. 2015); Ullrich et al. (017 : Louizos et al. (2017) and references therein) show ways to reduce the network complexity by using proper regu larization or network pruning to significantly reduce the number of parameters. One way to convert a dense DNN into sparse one by applying Lo/L, Li regularization on the model parameters. The Li 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, Lo regularization shows better performance, but incurs much higher computational complexity due to its combinatorial nature. Pruning. as shown in Han et al. (2015) and Tarttglione al. 2018), is another promising strategy 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.
the over-parameteriziee
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 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, propose a probabilistic connection importance inference (PCII) method for testing whether a connection in a DNN is relevant to the DNN output. Specifically, introduce 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

---

Published as a conference paper at ICLR 2020
network connection. Otherwise, we delete it. The inference is carried out by nonparametric score test, which is based on modeling the log- oog-tranfforme 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 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 showws shows the experimental results and concludes with a
short discussion.
2 RELATED WORKS
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
ctt al. (2017) introduced smoothed version of Lo regularization aiming to be both computationally feasible and beneficial to generalizability. There are also some regularization methods based on
Bayesian formulations. [Uliich et al. (017)) proposed to add Gaussian mixture prior 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 L1 or L2 regularization.
PCII offers means to prune 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.) (1900). 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. TTartgllione et al. (2018) proposed to prune 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.
Comparing with existing pruning methods based on the magnitude or gradient of weights, our approach directly models the relationship between 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 quantify the dependence strength of each network connection the DNN output. The use of p-values allows network connections to be treated in unified way and alleviates the need of ad hoc weights normalization required in some existing approaches.
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 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 acyelic DNN (Figure 1 be composed of T layers with X, being the input of the t-th network layer, where = 0.1...., T. Let f = 0 and = T indicate the input and output layers, respectively, and let < < index the hidden layers. The collection of all the nodes is denoted as G and the collection of all network connections is denoted E. For example, (Xt,1, X241,1) denotes an
as E. We use a pair of nodes to denote a connection edge from the 1s node in the t-th layer to the 1st node in the (t + 1)-th layer. For simplicity, Y to denote the output layer, who takes on categorical values for a classification task, and takes on continuous values for regression.
2

---

Published as a conference paper at ICLR 2020
1u, is not zero
X2011
Xea2
Xe-12
Connection is
Ma. Maay
:
Connection
XLt (c)
Xresotees (P)
Xmme
Figure I: Flowchart for probabilistic connection inference. We have two nodes a and from a fully connected neural network. The connection of and 3 is expressed as T/a,, + 0a,,0,y The importance of the connection is inferred by testing whether the three way interaction Na,9.y is zero or not.
The output of the (t + 1)-th layer can be described as
Xe+1. = 90+1 C
We wib+i w for j 1,,,..,,4++1 M++1,
where m, denotes the number of nodes in the t-th layer, and gr+11 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 network connection and the final output a DNN. For simplicity, we use (a, B) to denote an arbitrary network connection. Due the high non-linearity of DNN, function to model the relationship among o,, 3 and Y.
the nonparametric
Let denote the joint density of a, 3 and Y f(a, B,y) and the log-transferred density 17(a, G, v). We assume that n7,a, B, y) can be deposed as
n) 3, v) Ta + Th + Bl + fa.yy + 10 + Na.8 + flo,8.y
interaction between c and |
where Na. 18, and f7y are marginal effects, Ma.y. 78 and 70.8 are the two-way interaction terms. B.,8.y is the three-way interaction term. Here, we interpret the connection as the interaction of a and B, i.e. Na.8 + 0,. Specifically, TJo,8 is the interaction effect of a and B without the impact of y. and 17,,8,y characterizes the interaction of impacted by y. Our aim is to measure the significance of the connection by how much it 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 7o,8.. Therefore, inferring whether the connection is related to the final output or not equivalent to testing whether Na.8. 0 or not. As shown in Figure [] the connection is important for the network model if and only if the three-way way interaction Na.9.. * 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 al. (016)) sparsifying the filter has little effect reducing the computation cost. Nevertheless, reducing the volume of filters can greatly increase computing efficiency. For example, the volume of filter is 3 3 4. There four 3 x 3 slices. PCII can be generalized to infer the importance the slices, which can be treated as the connection between one channel the current layer and one channel in the next layer.
3

---

output Y, Published as a conference paper at ICLR 2020
3*3 Filter connected to Xga1,miu
A 1,101
If 1a,99 is not zero
X11
Xe+11
Xessa
X1a
Connection associated with
Xame
Wayl B.y
Connection
X1a (e)
X (I)
Y
Figure 2: Flowchart for probabilistic connection inference for convolutional layers. Without loss generality, we use same notation of and / denote two channels from convolutional neural network. The connection between a and corresponding to the convolutional operator h (shown as one slice with the red border). The importance of this connection is inferred by testing whether the three way interaction B.,. is zero or not.
L.M++3
Convolutional filters can be applied to transform channels in the t-th layer to channels in the (++ 1)-th layer. We denote the j-th channel in the (-th layer as Xt, for j = 1,..., my, where my is the number of channels in 1-th layer and O,..., T. Each filter connects all channels in the /-th layer one
channel in the + 1-th layer. Let h denote convolution operator that connects two channels
Xt, and X, X++ Then, the filter connected to X is [#1,441 J==] where we denote each N as a slice of the filter. For example, when we choose a operator is the filter convolved (slided) across the width and height of the input (X Li and offset
4 filter and set stride as one, this
with the bias. For one slice in the + 1-th layer, we can write its connection with the slices in the previous layer
X 96+1 (1.4+(X1,,) + 6/ bl,441)
where I++1 an activation function and b/,441 the bias for the j-th filter. As illustrated in Figure the red arrow from X to Xe+1,m--1 represents h 1.m.e which is one slice of the filter ( 1 connecting the channels in the f-th layer to channel X X441m in the + 1-th layer. For simplicity, we denote a one channel in the current layer and 8 one channel in the next layer. Since the relationship among the triplet (a, 3, Y) is highly nonlinear, we model its log-transformed joint density as nonparametric function 17( oc, (.y). Similar the fully connected layers, we assume that 7(a,3 3. y) has a decomposition as in (1.. As shown in Figure 2 the connection between a and |9 is decomposed to two parts: one unrelated the output Y, 1o,,3, and another related
J==1
Na,8..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 way interaction term Ja. against the null hypothesis Na.B.y 0.
3.3 ALGORITHM
In real applications, both fully connected layers and convolutional layers used in 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 We use p! to denote the p-value for testing the i-th node in f-th layer and j-th node
in (t + 1)-th layer for the fully connected layers. For convolutional layers, p denotes the p-value
(t)
for inferring the importance of the filter connecting the i-th slice in the (-th layer and the j-th slice in
4

---

Published as a conference paper at ICLR 2020
the t + 1-th layer. The calculation of the p-values are given in Section 4 based our proposed Score test.
Algorithm PCII: Probabilistic Connection Importance Inference for Lossless Neural Network Compression
Input: A training dataset, DNN architecture, and the desired model compression rate
Step 1: Use the training dataset to train a DNN of the given architecture.
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 Ho fl,,8. = 0 v.s H1
Na.88, * 0, and calculate the test statistics (or p-values) for all network connections as p {p. ii= m,.j I...., M4+1 t and + layers are fully connected).
(b). Importance inference of connections in convolutional layers: infer the three-way dependence
effect of network connection by testing the hypothesis Ho "Ja,8,y 0 H1 9.a.9.v * and calculate the test statisties (or p-values) for all network connections as p {P4s 1.6-1
;
1..... ] = ,,..,,,.,..... m tt and t + 1 layers are convolutionally connected).
Step 3: Rank all network connections by their test statisties (or p-values), and select threshold pf for deleting network connections in fully connected layers and p in convolutional layers to achieve the desired model compression rate (Strategies for choosing of and pc 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 a and 3 for fully connected layers or two random vectors a and , for convolutional layers. Let Y be random variable as the final output. The domains for o, B and Y are A, B, and V, respectively. Here, we assume that the log-transformed joint density function vj belongs to tensor product RKHS H ((a) ss H()) s H() where & denotes the tensor product of two linear space.
For marginal RKHS, 00 with an inner product (,, (g0) for I = ax, 3, Y, there exists a symmetric and square integrable function K2 such that
(f, K2 1) Man =(x), for all f E H(
(2)
where K₁ is called the reproducing kernel of H(" for I = ar U,B,Y. Y. By Mercer's theorem, any continuous kernel has the following decomposition
K(x, v) = Σ (1)o()))))))
1000--nne ==0
where the n.y. 's are non non-negative descending eigenvalues and the e 's are funeen-fnntions.. For the discrete domain (1.....() a), we define the kernel as K (x. y) = f- = y} for x. E (1,...,a)) a). For continuous domain, there are different choice of kernels such as Gaussian kernels and Sobolev kernels. Note that the cigenvalues for different kernels on continuous domain have different decay rate. For example, the cigenvalues of the Gaussian kernel have the exponential decay rate, i.c., there exists some e > 0 such that μ4, x exp(-ce) (Sollich & Williams 2004); and the eigenvalues of the m-th Sobolev kernels have the polynomial decay rate, i.e., Bv X
Gu 2013
4.2 PROBABILISTIC DECOMPOSITION OF TENSOR PRODUCT RKHS
Next we propose the probabilistic tensor sum decomposition for each marginal RKHS, H()), for I 1= a. 3, Y. We first use Euclidean space 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 vector and let f(x) be the x-th entry of the vector for æ 1,..., d. We denote A as an average operator defined as Af(x) = f). The tensor sum decomposition of the Euclidean space IR is
d
Rd = Rd + R == spant [ e Σ
f(d) = 0}
(4)
5

---

Published as a conference paper at ICLR 2020
where the first space is called the grand mean and the second space is called the main effect. Then, we construct the kernel for Ri and Ri the following lemma.
Lemma 1. For a RKHS space H. there corresponds unique reproducing kernel K, which is non-negative definite. Based on the tensor sum decomposition H. = "oo @ H1, where Ho = {1/d1} and Hi {g E H. Ex(g(X)) = 0}, we have the kernel for Ho as
ko 1/d
(5)
and kernel for Hi as
kn (x, {m=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 (x) = Es (ka, f' (Ekz, f)x where & is the kernel function in H and the first equality is due to the reproducing property. Eg plays the same role as 1 in Euclidean space. Then, have the tensor decomposition in a functional space defined as
H = Ho @ Hi := span (Egka) @ (S E e AS=
(6)
Following the same fashion, we call Ho as the grand mean space and Hi as the main effect space. Notice that E is also known the kernel mean embedding which is well established in the statisties literature Berlinet & Thomas-Agma Agnan (2011). Then we introduce the following lemma to construct the kernel function for Ho and Hi.
Lemma 2. For RKHS space H. there corresponds an unique reproducing kernel K, which is non- negative definite. Based the tensor sum decomposition H Ho Hi where Ho {E and Hi = (g E H: (g()))) = 0}, we have the kernel Ho as
ko(o,y) v) = (er v)] [0]++ + Fry (y( v)1 Fa,,k(I,,))
and the kernel for Hi
k1 (x, = (kk - Ekg, k, ky Ekyy
k(x,,)) E. (k(x w)1 (x(x, u)] + En,,
In neural networks, A, B are in a continuous domain. The final output Y can be either in con- tinuous 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 I and Lemma 2 respectively. Specifically, we have spaces H(a), H(3) and H(Y) decomposed as tensor sums of subspaces (a) H(() + H("),, H(3)
H/(5) H((), H(Y) H, H())) Following Gu
(2013), we apply the distributive law and have the decomposition of H as
=(H
H((") & (H6 + H())
(H)) + H
Honm @ H1on Horo Hom @ Hno Him Hon @ Hmn
(8)
where Hijk H + H
+ !
Lemma 3. Suppose (1) is the reproducing kernel of (1) on X1, and K(2) is the reproducing
kernel of (22) on X2. Then the reproducing kernels of (1) @ H22) on X1 X2 is K (xx
(()) (1 ( ) (2) (2(2) (2()) with (1) x (2) and y (1) (y())
Lemmas 3 can be easily proved based on Theorems 2.6 in Gu (013). Lemma 3 implies that the reproducing kernels of the tensor product space 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 1) E H. can be correspondingly decomposed as (I] Thus, No,8.Y = 0 if and only if 17' Ho Hooo H100 @ Holo @ Hoo1 @ Hi e Hiol @ Holl where 77" is the underlying truth. Hence, we focus on the following hypothesis testing problem:
Ho : 17" E Ho Hi: nn" H.Ho.

---

Published as a conference paper at ICLR 2020
where H. denotes set difference of H. and Hg. We next propose likelihood-ratin based procedure to test (9) Suppose that t = (a, B. y) and t; = (a,, B, W.) = 1,.... n, are iid observations generated from T (A. Let LR, be the likelihood ratio functional defined as
(n) (n) - (n(PHo -
7 Σ (n((.) PHo ((4)) n E H, n
(10)
where Pro is projection operator from H to Ho- Using the reproducing property, we rewrite (10) as
( - a
((Ke, 1)x (K,, 7)
(11)
where K is the kernel for H and KD is the kernel for Ho.
Then we calculate the Fréchet derivative of the likelihood ratio functional as
-(2 K An
DLR,(T))
Ke.
K2), An
(12)
12
1=1
where Ka is the kernel for Hi11. We define our test statistics as the squared norm of the score function of the likelihood ratio functional as
$h - Σ K
(13)
1=1
By the reproducing property, we can expand the left hand side of as
$ n1
K (tr,t,)
(14)
j=1
We observe an interesting phenomenon that S% has a similar expression with the MMD (Gretton
al. 2012 when Y is a binary variable. When Y E [[0,1, the kernel on H(Y) is (( (y), v,)
1
1/2. Assume that the kernel for H( & H1S)
(8) is k/a,8) (),x)) for E A x B, By
Lemma 3 we have KJ (t,,tt) = ( (1). (1) (a..9) (xt; v)). Then we have 8.5?, as
85
K/C (x) -2
Σ K(a (t. woFt))
(x:, m.)
Σ (i. [=
K (;)) (15)
[1. =)
If we replace k((0,0) with K (o,00), i.e., the kernel on the H()) @ (8) the right hand side of 15
the MMD measuring the distance between the joint distribution of a and B in the group with and the joint distribution of and 3 in the group with y =
(a,
Ex (I,, xT) - 2
Σ K(awel (I,, + Ex (2,, x))
n² (t.j ==
H
(b. ==
(16)
Since we want to infer the importance of the connection between the a and B, we are only interested in comparing whether the interaction effect between and 3 changes or not in the two groups The main effects of and 3 only contribute to the importance of the nodes or slices and are not relevant to the connection between a and B3.
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). S2 is determined by the kernel on th Haaa) H
H,Y), By Lemma and Lemma 2 we replace the expectation by the sample average and get the kernel function for H,, as
k((z,v) k2 (2.
1 n k
1 Σ (t 9i)
1
ΣΣ
"
k (a Mz)
7

---

Published as a conference paper at ICLR 2020
where k is the kernel function for 79 for = a, Y. Some popular choices of the kernel functions are Gaussian kernel, Laplace kernel and polynomial kernel. Let K" be the empirical kernel matrix. We can rewrite [4 as
HHK* (HK* (H H)]++ S n n 11
(17)
where H [A]++
L, is a x identity matrix and 1, is aan n x 1 vector of ones, and A.j. 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. sampling the dataset is a popular technique to reduce computational burden and can efficiently approximate the full data likelihood in regression setting (Ma et al. 2015 Drineas et al. (00T)) 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 the final test statistics. This is also related to the divide-and-conquee method which is widely used in kernel- learning (Zhang et al. 2013 Shang
& Cheng 2017 Liu et al. 2018).
4.5 ASYMPTOTIC DISTRIBUTION
The asymptotic distribution of S. depends on the decay rate of the kernel of the product of RKHS. Sup- pose that {ub²) aba) 1
1==1 is series of eigenvalue and eigenfunction pairs for H:!a), (ull) oe I==1 a sequence of basis for (((0) If Y is continuous, we suppose that 7((*) has the eigensystem, (ul _ab } J-= Y is categorical, we suppose that HC(0) has the eigensystem, {ul olone= I-=l- Then we have the eigenvalue eigenfuntion pair for the tensor product space H @ H((0) @ H as
(9)
(p (o) Meg pby (fo) o (1)) 6
where vn 1,..., oc, Uy ".....,,0,, 00, By 1,..., (Y is continuous), and by 1, 1,..,, a (Y is categorical with a categories). For simplicity, we order the pairs in the decreasing order of up. P = 1, ......... The null hypothesis could be interpreted as factorization hypothesis. i.c.. (X 1 Z v ZX LY V (Y, 2) 1 X or X, Y, Z are mutually independent.
Theorem 1. Suppose the kernel on Hin is square integrable. If Y continuous variable, then under Ho, we have
n
> P
(18)
where Ep 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 n.5% only depends on the eigenvalues of the kernel. Theorem related to Wilks' phenomenon demonstrated in the classic vonparameticcsemipaaaeette 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 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.
8

---

Published as a conference paper at ICLR 2020
PCII offers convenient way to adjust compression rate by changing the p-value threshold p. For other compression methods in consideration, the compression rate is usually controlled by some syper-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 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 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. addition, we did not include methods that are not able to achieve the I.CR 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. (198)). We trained LeNet-300-100 for 100 epochs to achieve 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 Table |
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 MLP via compression (i.c., the MTE is better than the LCR).
Dataset: MNIST, Network: LeNet-300-100
Criterion
Method
Error %
Compression Rate
Original
1.69%
1x
PCIT
1.70%
26x
Han et al.
2015
1.69%
15.1x
LCR
Louizos ct al.
2017
1.70%
3.3x
Guo et al.
2016
1.70%
15x
PCI
1.58%
10x
Han et al.
2015
1.59%
12.2x
MTE
Louizos et al.
2017
1.70%
3.3x
Guo et al.
20116
1.70%
15x
Table 1: Experimental results for LeNet-300-100 on MNIST dataset.
0
50
100
150
200
250
300
100
200
300
400
500
600
700
Figure 3: The heatmap showing the PLR test result of the 784 x 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 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.
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, visualize the importance of the features in the input layer. Figure plots the values of the

---

Published as a conference paper at ICLR 2020
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 the first and last few channels are less relevant to the final output (i.e., have large y-values). This phenomenon is observed because written digit is usually located in the central part of a image.
Dataset: MNIST,
Network: LeNet-5
Criterion
Method
Error %
Compression Rate
Original
0.70%
1x
PCII
0.69
38x
Han et al.
2015
0.71%
12.1x
LCR
Louizos et al.
2017
0.69%
1.4x
Guo et al.
2016
0.70%
32x
PCI
0.65%
10.7x
Han et al.
20155)
0.70%
6x
MTE
Louizos et al.
2017
0.68%
1.1x
Guo al.
(0116)
0.70%
32x
Table 2: Experimental results for LeNet-5-caffe MNIST dataset.
The LeNet-5 model httt:p:::/go.../////// includes two convolutional layers with 20 and 50 filters, respectively, and a fully connected layer with 500 nodes. The results are summarized in Table 2 PCT 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.
a modified version of LeCun et al. (1998).
5.2 CIFARIO DATASET
To demonstrate the applicability of PCII complex DNNs, we applied it to VGG16 (Zagorukko 2015), which was adapted for the CIFAR-10 dataset (Krizhessky & 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 eтror of the uncompressed VGG16. For this dataset, we only include the result for PCII due to the limited resources. In fact, could not obtain the results for other methods in comparison in three days' computing time.
Dataset: CIFARIO,
Network: VGGI6
Criterion
Method
Error
Compression Rate
Original
7.55%
Ix
LCR
PCII
7.56%
10x
MTE
PCII
6.01%
3x
Table Experimental results for VGG16 on CIFARIO dataset.
DISCUSSION
We propose statistically principled strategy directly infer the importance of connection in neural network via PCII, hypothesis testing framework. The proposed PCII test provides p-value based measure on the importance the connection through the connection's '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 connection types including the skip layer connections in RNN.
10

---

Published as a conference paper at ICLR 2020
7 ACKNOWLEDGEMENT
XX and JL would like to acknowledge NSF and NIH for providing partial support or this work. PH and LS would like acknowledge NSF (NSF OAC 1920147) for providing partial support of this work.
REFERENCES
Sajid Anwar, Kyuyeon Hwang, and Wonyong Sung, Structured pruning of deep convolutional neural networks. ACM Journal on Emerging Technologies in Computing Systems (JETC), 13(3):32, 2017.
Alain Berlinet and Christine Thomas-Agnan, Reproducing kernel Hilbert spaces probability and statistics. Springer Science & Business Media, 2011.
Petros Drineas, Michael W Mahoney, S Muthukrishnan, and Tamás Sarlós. Faster least squares approximation. Numerische mathematik, 117(2)221-249)) 2011.
Jianqing Fan, Chunming Zhang, and Jian Zhang. Generalized likelihood ratio statistics and wilks phenomenon. Annals of statistics, 29:153- 199113993,, 2001.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(Ma7):723-773, 2012.
Chong Gu. Smoothing spline ANOVA models, volume 297. Springer Science & Business Media, 2013.
Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient dnns. In Advances In Neural Information Processing Systems, pp. 1379-1387, 2016.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network, In Advances neural information processing systems, pp. 1135-1143, 2015.
Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruning. In Neural Networks, 1993., IEEE International Conference on, pp. 293-299, IEEE, 1993.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Lancaster. 0.(1969). the chi-squared distribution. Wiley, New York. MR, 40:6667, 2002.
Yann LeCun, John S Denker, and Sara Solla. Optimal brain damage. In Advances neural information processing systems, pp. 598-605, 1990.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11)2228-2322, 1998.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. arXiv preprint arXiv:1608.087/00 2016.
Meimei Liu, Zuofeng Shang, and Guang Cheng. How many machines we in parallel computing for kernel ridge regression? arXiv preprint arXiv:1805.0900 2018.
Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through 1_0 regularization. arXiv preprint arXiv:1712.01312. 2017.
Ping Ma, Michael W Mahoney, and Bin Yu. A statistical perspective on algorithmic leveraging. The Journal of Machine Learning Research, 16(1):861-911, 2015.
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. arXiv preprint arXiv: 2017.
Zuofeng Shang and Guang Cheng. Local and global asymptotic inference in smoothing spline models. The Annaly of Statistics, 41(5):2608-26) 26388, 2013.

---

Published as a conference paper at ICLR 2020
Zuofeng Shang and Guang Cheng. Computational limits of a distributed algorithm for smoothing spline. The Journal of Machine Learning Research, 18(1):3809-388 3845, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1556, 2014.
Peter Sollich and Christopher KI Williams. Understanding gaussian process regression using the equivalent kernel. In International Workshop on Deterministic and Statistical Methods in Machine Learning, pp. 211 1-288. Springer, 2004.
Enzo Tartaglione, Skjalg Lepsøy, Attilio Fiandrotti, and Gianluca Francini. Learning sparse neural networks via censittivity-driver regularization. In Advances in Neural Information Processing Systems, pp. 3882-3892, 2018.
Karen Ullrich, Edward Meeds, and Max Welling. Soft weight-sharing for neural network compression. arXiv preprint 170..0000000008 2017.
Sergey Zagoruyko. 92.45 on cifar- 10 in torch. Technical report, 2015.
Yuchen Zhang, John Duchi, and Martin Wainwright. Divide and conquer kernel ridge regression. In Conference Learning Theory, pp. 592-617, 2013.
Michael Zhu and Suyog Gupta. To prune, not prune: exploring the efficacy of pruning for model compression. arXiv preprint arXi:: 2017.
A SUPPLEMENTARY MATERIALS
A.I POOF OF THEBRRE
6p) Let [/4p: [Ap:0pp2c p= be the eigenvalues and eigenvectors for the tensor product space H11) oH & &H
By the dedomposition defined (8), we have
(t)) 0,
(19)
for p I,.., i... the mean of the eigenfunction o, is zero. By simple calculation, we have
Hp 00
(20)
for the exponential decayed kernels and polynomal decayed kernel with decay rate as i-m for m > 1. Thus, the commonly used kernels such Gausssian kernel, Laplase Kernel and linear qudratic Solblev kernel satisfy this requirement.
By Mercer's 's theorem, have the decomposition
n
K (t;, tz)
n
i=1
(t)opt)
((t)))
MPEp
where Cp are i..dd standard normal random variables. The last row is proved by applying the Lindeberg- -évy CLT to have Σ p(t,) 4 c, since (1) and (2) holds. Then, by the Kolmogorov's inequality and Ep Mp < oo, have the last row holds.
12


Reviews:
[{"review_id": "Byxg4B70KB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "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.\n\nPruning 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.\n\nOn the other hand, I also have the following concerns:\n- 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.\n- 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.\n- The asymptotic distribution can be seen as a corollary of existing researches for MMD and HSIC.\n\nFor these reasons, I was not completely convinced with the effectiveness of the proposed method.\n\n\nMinor comment:\n- The test statistics is more like HSIC. It would be nice if there were comments on the connection to HSIC.\n\n===\nUpdate: 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.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByefJP6lqH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 proposes a new way of evaluating the importance of neural connections which can be used for better model compression. The approach uses a non-parametric statistical test to detect the three way interaction among the two nodes and final output. Some small scale experiments show that the approach achieves better compression rate given the same test error.\n\nThe approach seems interesting in the sense that, unlike existing techniques, it explicitly measures the three way interaction among the two nodes and the output. Also, it removes the average effects and only considers (non-linear) correlation after removing the mean. The explicit link to the final output and removing average effects allows the method to remove more weights without decreasing the loss by much.\n\nHowever, the drawback of the approach is the significantly increased computation due to 1) quadratic complexity for the kernel methods; 2) unable to cache computation among different pairs of nodes (for example, gradient-based approach can compute importance for all node connections in one forward-backward pass). This limits the applicability of the approach to more interesting cases of larger models (for example, models that work on ImageNet) where model compression is of more urgent need. As a result, the significance and impact of the approach is also limited.\n\nThe experiment results are interesting in that it shows the proposed approach can achieve better compression rates given the same test error tolerance on a few small datasets. However, as mentioned above, these experiments are less convincing than more complicated models on larger datasets, such as ImageNet where model compression has greater impact. In addition, the test errors on smaller datasets are easier to achieve, sometimes tuning the optimization settings such as learning rates can result in significant improvement. Therefore, such results are more like preliminary.\n\nThe paper is general clear and well written. The experiment section should include more important information such as what kernel bandwidth is used for Gaussian kernel, which greatly affects performance. Also, the main text introducing the proposed statistical test is a bit verbose, and dense in unnecessary notations. I think it can be made more succinct by presenting a high level idea (removing mean, three way correlations) first and then the final results. Some intermediate results can be put into Appendix.", "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": {}}, {"review_id": "BJlTymjYcH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 introduces a nonparametric score test to estimate the importance of network connections on the final output of Deep Neural Networks. They derive this by modeling the log-transformed joint density of each connection and final output in a tensor product reproducing kernel Hilbert space. They finally derive an asymptotic distribution of the proposed test statistics which only depends on the eigenvalues of the kernel. This importance test is applied to ranking the importance of each connection in Multilayer Perceptron Networks, and Convolutional Networks and sparsifying the networks by removing the least important connections. The method is applied post-training to fully trained networks but evaluated by retraining the sparsified network from scratch. The method is demonstrated in experiments on compressing three networks. \n\nI believe this paper is a borderline accept. It provides a more statistically principled method to examine the importance of connections in a Neural Network and rank them compared to existing compression methods. Due to this ranking, there is a clear method to easily adjust the target compression rate. They are able to achieve high lossless compression rates. However, the benefits shown in the empirical results could be more convincing. It lacks baselines on more complex networks and could benefit from more empirical analysis of the theoretical benefits and properties of this approach.\n\nPros: \nThe method is able to maintain accuracy while achieving high compression rates on MNIST and CIFAR10. It does better than the baselines compared to the small networks. They show a capability for increasing generalizability by decreasing error rates. \n\nIt provides a well derived statistically principled method to examine the importance of connections and rank them.\n\nIndicates an additional use to visualize the importance of features.\n\nCons:\nThe empirical results could be clearer. It lacks baselines for larger models on Cifar10. Could you compare it with the published results of other algorithms? How does it do on larger networks like Imagenet?\nComputational efficiency is mentioned but could be examined in greater detail.  How long does it take to run and how is that affected by model size?\n\nThe experimental setting is somewhat unclear. The baseline Louizos et al. (2017)  was designed to optimize group sparsity/speed, but the experimental results here only examine the compression rate. Was the baseline run to optimize speed or sparsity?\n\nIt would be interesting to examine the correlation of importance score with actual impact on network performance. This might be done with a comparison with random pruning or pruning higher importance connections. It might be useful to examine the performance of the networks after pruning nodes of differing importance without full retraining or just fine-tuning. It is unclear how important full retraining is in this method.\n\nIt would be interesting to visualize the importance of features at different depths in the deep convolutional networks.\n\nMinor suggestions: In the introduction, you mention l0 and l1 norm methods, but cite Han et al. (2015) which compares l1 and l2 norm and found l2 norm to be better overall.\n\ntypos:\nIn Abstract: nonparemtric scoring test  -> nonparametric scoring test  \nIn 4.4: sample averarge -> sample average\nIn 4.5: ASYMPTOTICALLY DISTRIBUTION  ->   ASYMPTOTIC DISTRIBUTION ", "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 carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel approach for pruning deep neural networks using non-parametric statistical tests to detect 3-way interactions among two nodes and the output. While the reviewers agree that this is a neat idea, the paper has been limited in terms of experimental validation. The authors provided further experimental results during the discussion period and the reviewers agree that the paper is now acceptable for publication at ICLR-2020. 
Decision: Accept (Poster)