Empirical Studies on the Properties of Linear Regions in Deep Neural Networks
Authors: Xiao Zhang
Dongrui Wu
Venue:  (2020)
Keywords: deep learning
linear region
optimization

Abstract: A deep neural networks (DNN) with piecewise linear activations can partition the input space into numerous small linear regions, where different linear functions are fitted. It is believed that the number of these regions represents the expressivity of a DNN. This paper provides a novel and meticulous perspective to look into DNNs: Instead of just counting the number of the linear regions, we study their local properties, such as the inspheres, the directions of the corresponding hyperplanes, the decision boundaries, and the relevance of the surrounding regions. We empirically observed that different optimization techniques lead to completely different linear regions, even though they result in similar classification accuracies. We hope our study can inspire the design of novel optimization techniques, and help discover and analyze the behaviors of DNNs.

Published as a conference paper at ICLR 2020
EMPIRICAL STUDIES ON THE PROPERTIES OF LINEAR REGIONS IN DEEP NEURAL NETWORKS
Xiao Zhang & Dongrui Wu'
Ministry of Education Key Laboratory of Image Processing and Intelligent Control, School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan, China {xiao-zharr -aanng, drwu) edu. en
ABSTRACT
A deep neural network (DNN) with piecewise linear activations can partition the input space into numerous small linear regions, where different linear functions are fitted. is believed that the number of these regions represents the expressivi- ty of the DNN. This paper provides a novel and meticulous perspective to look into DNNs: Instead of just counting the number of the linear regions, we study their local properties, such as the inspheres, the directions of the corresponding hyper- planes, the decision boundaries, and the relevance of the surrounding regions. We empirically observed that different optimization techniques lead to completely d- ifferent linear regions, even though they result in similar classification accuracies. We hope our study can inspire the design of novel optimization techniques, and help discover and analyze the behaviors of DNNs.
INTRODUCTION
In the past few decades, deep neural networks (DNNs) have achieved remarkable success in various difficult tasks of machine learning (Krizhevsky et al., 2012: Graves et al., 2013; Goodfellow et al., 2014; He al., 2016; Silver et al., 2017; Devlin al., 2019). Albeit the great progress DNNs have made, there are still many problems which have not been thoroughly studied, such as the expressivity and optimization of DNNs.
High expressivity is believed to be one of the most important reasons for the success of DNNs. It is well known that standard deep feedforward network with piecewise linear activations can partition the input space into many linear regions, where different linear functions are fitted (Pascanu et al., 2014; Montufar et al., 2014). More specifically, the activation states are one-to-one correspon- dence with the linear regions, i.e., all points in the same linear region activate the same nodes of the DNN, and hence the hidden layers serve as a series of affine transformations of these points. As approximating complex curvature usually requires many linear regions (Poole et al., 2016), the expressivity of a DNN is highly relevant to the number of the linear regions.
Studies have shown that the number of the linear regions increases more quickly with the depth of the DNN than with the width (Montufar et al., 2014; Poole et al., 2016; Arora et al., 2018). Serra et al. (2018) detailed the trade-off between the depth and the width, which depends on the number of neurons and the size of the input. However, a deep network usually leads to difficulties in opti- mization, such the vanishing/exploding gradient problem (Bengio al., 1994; Hochreiter, 1998) and the shattered gradients problem (Balduzzi et al., 2017). Batch normalization (BN) can alleviate these by repeatedly normalizing the outputs to zero-mean and unit standard deviation, so that the scale of the weights can no longer affect the gradients through the layers (Ioffe & Szegedy, 2015). Another difficulty is that the high complexity caused by the depth can easily result in overfitting. Srivastava et al. (2014) proposed dropout to reduce overfitting, which allows DNN to randomly drop some nodes during training and work like an ensemble several thin networks during testing.
Despite the empirical benefits of these techniques, their effects on the trained model and the reasons behind their success are still unclear. Previous studies focused on explaining why these techniques
Dongrui Wu is the corresponding author.

---

Published as a conference paper at ICLR 2020
help the optimization during training (Wager et al., 2013; Santurkar al., 2018; Bjorck al., 2018). Different from theirs, our study is trying to answer the following question:
What properties do these techniques introduce to the linear regions after training?
We present intuitive view of different techniques' effects on the linear regions in Figure 1. We may observe that:
1. BN and dropout help the DNN partition the imput space into many more linear regions than the vamilla DNN.
2. The linear regions resulted from the BN model are more uniform size than those from the dropout DNNN
3. Many transition boundaries of the dropout DNN share similar norm directions, and con- centrate around the decision boundarics.
Figure illustrates that different optimization techniques can lead completely different linear re- gions even using the same DNN architecture, which may influence the behaviors of the DNN, such its adversarial robustness (Biggio al., 2013; Szegedy et al., 2014) or some other undiscovered ones (Appendix A shows another example on two-dimensional toy dataset). Therefore, it is impor- tant probe the properties of the linear regions introduced by these frequently-used optimization techniques, instead of just looking the learning curves.
Vanilla
BN
Dropout
Linear Regions
Classification Regions
Figure Linear regions and classification regions of models trained with different optimization techniques. The gray curves in the top row are transition boundaries separating different linear regions, and the color represents the activation rate the corresponding linear region. the bottom row, different colors represent different classification regions, separated by the decision boundaries. The models were trained the vectorized MNIST dataset, and this figure shows voo-dimensional slice of the input space. The vanilla model was a fully-connected ReLU network with three hidden layers. To make the figure more readable, each hidden layer only included 20 nodes. The BN model was the vanilla model with BN added after pre mreaactivations of every hidden layer, and the dropout model added dropout layers after the hidden layers, with drop rate 0.2.
This paper introduces mathematical tools of polyhedral computation into linear region analysis, and systematically compares various properties of the linear regions after DNNs being trained with different optimization techniques (BN, dropout). Though the models have similar classification accuracies, we do observe significant differences among their linear regions:
1. BN can help DNNs partition the input space into smaller linear regions, whereas dropout helps around the decision boundaries.
2. BN can make the norm directions of the hyperplanes orthogonal, whereas dropout the opposite.
2

---

Published as a conference paper at ICLR 2020
3. Dropout makes regions in which data points lie less likely to contain the decision bound- aries.
4. The gradient information of a linear region has high relevance to its surrounding regions; however, BN slightly reduces the relevance.
should be noted that our approach can also be applied to analyzing the preferences introduced by other optimization techniques, such as different initialization approaches (Glorot & Bengio, 2010; He et al., 2015), different optimizers (Duchi et al., 2011; Kingma & Ba, 2014), some widely-used operators like skip-connection (He et al., 2016), and even different hyperparameters. Since training deep learning models is related to the complex interaction among the training dynamics, data man- ifold and model architectures, we believe it is better to decouple it into two subtasks: 1) figure out what kinds of linear regions can best approximate the data manifold; and. 2) design optimization techniques achieve such linear regions. Our work provides tools to analyze the linear regions, which helps study both subtasks.
The remainder of the paper is organized as follows: Section 2 presents the details of the linear regions of DNNs with ReLU activation. Section 3 shows how BN and dropout influence the linear regions. Section 4 draws conclusions.
2
LINEAR REGIONS
This section describes the detailed approach' for searching for the linear regions of a given input, and introduces some basic concepts of convex polytopes.
2.1 SEARCH FOR THE LINEAR REGIONS
A linear region is the intersection of a finite number of halfspaces. Therefore, to search for the linear region in which a given input point lies, we only need search for its corresponding halfspaces, which are determined by the activation state of the DNN.
Let's consider vanilla fully-connected DNN with I. hidden layers and ReLU activation. Mathe- matically, let x E Rdd denote the d-dimensional vectorized input, h' h'(x) the pre-activation outputs of the (-th hidden layer with ny nodes (I 1,2,.... .... L). z(x) the logits of the output layer, and M the number of classes. Given an input example x", because of the one-to-one correspondence relation- ship between a linear region and an activation state, its corresponding linear region a set inputs which lead to the same activation state of the DNN.
Let St denote a set of the inputs whose activation states of the first hidden layers are the same as those of x" Obviously, S1+1 S Sy. Consider the first layer. Since ht Rdd -> I is simply an affine transform of x, according to the activation state, S1 can be written as:
S = x
by 2 O,
Vi E m1]...,]]]..
(1)
where
W;
(x*), b. = sgn(h: (x") - (Vxh (x (x*))xx*}
(2)
(3)
Next, we select the points from S1 to construct 52, which activate the same nodes of the second layer as x" does. Recall that the points in 51 lead to the same activation state of the first layer, hence h² 5 + _R is also an affine transform of x. Therefore, S2 can be constructed by adding linear inequality constraints to S,, in the same way as (1). Due to the linearity of h' S - RT (where So = =R4) for all I, this procedure can be repeated till the last hidden layer. The detailed deduction presented in Appendix B, and the depth-wise -hite exclusion process to search for a linear region of x" is illustrated in Figure 2.
We developed the approach for finding the linear regions independently. but later found that the same approach has heen proposed in (Lee et al., 2019). However, the two papers use the linear regions for different purposes.
3

---

Published as a conference paper at ICLR 2020
Let C* = ((w,, ((w,,))) be the set of parameters of all the linear inequality constraints. Then SL. which is the linear region that x" lies in, be represented the intersection of Σ n halfspaces:
S = fx w x + be 2 0, ((w,,)) }
(4)
where the DNN is locally linear model, St. R-M is an affine transform of x.
S, f
Layer 1
Layer 2
* Point x"
Input node
Activated node
Inactivated node
Norm direction the hyperpiane
Figure 2:
Depth-wise exclusion process to search for the linear region of x*. Each node in each layer provides hyperplane to cut the polytope defined by the preceding layers.
Though we mainly discuss the standard fully-connected DNNs, the form to describe a linear region can be extended other situations with little modification. For instance, BN is just a reparameteriza- tion of the weights, a convolutional neural network (CNN) can be viewed as a sparse fully fully-connected DNN, and max-pooling is simply adding more linear inequalities identify the maximum.
2.2 CONVEX POLYTOPES
A linear region can be represented the set of solutions finite set of linear incqualities in (4), which is exactly the H-representation of a convex polyhedron. With the natural bounds of the input value, these linear regions are convex polytopes?. We omit the word convex in the rest of the paper to avoid repetition.
A polytope also be represented convex hull of finite set of points, which is known as the V-reprexentation. Different representations may lead to different complexities when dealing with the problem; nevertheless, it is challenging to convert er (Toth et al., 2017). As the dimensionality increases, it is even harder to calculate the number of vertices/facets with single H-/V- representation (Linial, 1986), or verify the equivalence be- tween an H-representation and V-representation (Freund & Orlin, 1985). More information about polyhedral computation can be found here?.
representation into the oth-
It should be noted that convex optimization is capable of probing the properties of the linear regions, because H-representation is natural description of a convex feasible region, and a DNN's behavior is completely linear in this feasible region.
3 PROPERTIES OF THE LINEAR REGIONS
This section presents various properties of the linear regions of DNNs, which were trained using different optimization settings.
3.1
MODELS
We used fully-connected DNN as vanilla model, which consisted of three hidden layers with 1,024 rectified linear nodes in each. The BN model was the vanilla model with BN added after the
Here we use the term polytope to denote a bounded polyhedron.
4

---

Published as a conference paper at ICLR 2020
pre-activations of each hidden layer, and the dropout model added dropout after the activations. We trained our models on the vectorized MNIST dataset, which were rescaled to [-1,1].
All models were trained using Adam optimizer (Kingma & Ba, 2014) with the default setting (31 0.9, f2 = 0.999) but different learning rates (1e-3 and le-4), and the batch size was 256. We used the Xavier uniform initializer for weight initialization, with biases set to zero (Glorot & Bengio, 2010). Early stopping was used to reduce overfitting. The classification accuracies are shown in Table 1. Since is unlikely to explore the influence of all optimization settings, this paper emphasizes two optimization techniques, i.e., BN and dropout, and compares the influence of different learning rates.
Table Test accuracies (%) of different DNN models.
Learning Rate
Vanilla
BN
Dropout
le-3
97.8
97.9
97.5
le-4
98.0
98.3
98.2
As shown in Section 2, the number of constraints in (4) equals the number of hidden nodes; hence, is hard to handle the constraints as the scale of DNN increases, such as removing the redundant inequalities. In our experiments, the number of constraints was 1, 024 x 3 3, 072. In addition to the natural bounds for the 28 x 28 = 784 pixel values (MIN, S. x & MAX,), ) each linear region is defined by 3, 072 784 2 640 linear inequalities.
Our analysis of CNNs trained on the CIFAR-10 dataset is presented in Appendix E.
3.2
THE INSPHERES
We first probed the inspheres of the linear regions, which are highly related to the expressivity of a DNN. Though we cannot make a definite statement that a small insphere always leads to a small linear region, does indicate region's narrowness.
The insphere of a polytope can be found by solving the following convex optimization problem:
(5)
W - r/:ll/ + 2,200 0, S. L.
b:w, EC"
MIN, - - < MAX, - -r,
where X is the center of the insphere, r the inradius, and C* the set of parameters S₁ defined in (4). The main idea of the optimization to find point polytope, whose distance the nearest facet is the largest.
As shown in Figure linear regions vary according to their closeness the decision boundaries, hence we studied the inspheres of three different categories of regions", which are defined as follows:
Manifold region: The region in which the test points lic.
Decision region: The region which contains the normal decision bowndaries. We define normal decision boundary as the classification boundary between one test point and the mean point of another class. When we test models, the mean point of a class is classified into the same class for the MNIST dataset.
Ad Adversarial region:
The region which contains the adversarial decision boundaries. We define the adversarial decision boundary as the classification boundary between a test point and its adversarial example. The adversarial examples were generated by the projected gradient descent (PGD) method (Madry et al., 2018).
Linear interpolation was used to search for regions which contain the decision boundaries. Let Xtest denote the test point, and Xtarger the adversarial point or the mean point of another class, We searched for the maximum a E [0, 1] which causes X,, = a Xtorget + (1 - Qr) Xtest to be classified into the same class Xtest, and the region in which x. lies contains the decision boundaries.
'These regions should not he confused with classification region, which is partitioned according to the classes of the points the input space.
5

---

Published as a conference paper at ICLR 2020
As shown in Figure 3, different optimization settings introduce significantly different inradius dis- tributions. Compared with the vanilla models, BN leads to the smallest inradiuses of the linear regions, whereas dropout, shown in the second column of Figure 3, makes the decision regions narrower. It also shows that the inradius distributions of the adversarial regions are more similar to those of the manifold regions, which demonstrates the fundamental differences between the adver- sarial and the normal decision boundaries. Comparing the two rows in Figure 3, we can observe that a larger learning rate increases the variance of the distributions. However, BN seems make the inradius distribution less sensitive to the learning rate, which is consistent with the observations in Bjorck al. (2018) that BN enables training with larger learning rates. Comparing the first two columns of Figure 3, we can also find that the decision regions are usually narrower than the man- ifold regions, which was also observed by Novak et (2018) that on-manifold regions are larger than off aff-foaifold regions. It is reasonable because decision boundary curves need more sophisticat- ed approximation.
Manifold
Decision
Adversarial
BN
50
LR=1e-3
Density
40
Dropout
Density
40
Dropout
Density
40
Dropout
30-
30
30-
20
10
10
10
0.0
Inradlus
Inradius
Inradius
60
60
60
Vanilla
Venilla
Venila
BN
50
BN
BN
LR=1e-4
Density
Deapout
Density
40
Density
30-
30-
30-
20
20
10
0
0.0
0.1
0.2
0.3
0.0
0.2
0.3
0.0
0.1
0.2
0.3
Inradius
Inradius
Inradius
Figure 3: Inradius distributions for different learning rates and optimization techniques. The models in the top row were trained with larger learning rate (1e-3), and the bottom row a smaller learning rate (Ic-4). The three columns show the inradius distributions of the manifold regions, the decision regions, and the adversarial regions, respectively.
3.3 DIRECTIONS OF THE HYPERPLANES
Another observation is that BN makes the directions of the hyperplanes of linear region orthogonal, whereas dropout the opposite. Since it is time-consuming to eliminate the redundant hyperplanes, as explained in Appendix we calculated the angles using all hyperplanes.
The direction w of a hyperplane is pointing to the interior of the linear region, because all constraints in the form of w" x-b 2 O. Figure 4 shows the angles between directions of every two different hyperplanes of manifold region. The directions of the hyperplanes become more consistent as the layer goes deeper. Dropout and large learning rates amplify this trend, whereas BN makes the directions more orthogonal. Though we only present one example here, the patterns can be observed for almost all manifold regions.
As shown in (2), the direction w is actually the gradient of the corresponding hidden node with respect to the input, hence the angle between the directions can be viewed as the correlation between the gradients. However, it should be noted that the shattered gradients problem (Balduzzi et al., 2017) cannot explain the decorrelation characteristics of BN, though they look similar. The shattered gradients problem studies the correlation between the gradients with respect to different inputs, whereas our observation is about the gradients of different hidden nodes with respect to a fixed input.

---

Published as a conference paper at ICLR 2020
Vanilla
BN
Dropout
3072
180
3072
180
3072
180
150
150
LR=1e-3
120
2048
120
120
90
90
90
1074
60
1324
1024
60
1024
2048
3D72
1024
2048
3072
1024
2040
3072
2072
100
3072
100
3072
180
150
150
LR=1e-4
120
2040
2048
120
90
1024
60
1024
60
1024
60
30
1024
2048
3072
1024
2048
3072
1024
2048
3072
Figure 4: Angles between the directions of different hyperplanes of particular manifold region. The indices on both axes indicate different hyperplanes: 0-1,023 represent the hyperplanes of the first hidden layer, 1,024-2,047 the second layer, and 2,048-3,071 the third layer. The value of pixel w w. ww i.e., the angle between w, and w,. The models in the top were trained with larger learning rate (1e-3), and the bottom row smaller learning rate (le-4).
is arccos
We also observed interesting phenomenon: the orthogonality of the weights vanished during training. We tried to explicitly decorrelate the directions at initialization by introducing an orthogo- nal initializer (Saxe et al., 2014), but the orthogonality was still broken after training. It interesting to see if the properties of initialization can be preserved in training, which one of our future re- search directions.
3.4 DECISION BOUNDARIES MANIFOLD REGION
Adversarial examples are benign inputs with imperceptible perturbations, which can dramatically degrade the performance
machine learning model (Biggio et al.. 2013; Szegedy et al., 2014). Adversarial attacks aim to push benign input across the nearest decision boundary (Szegedy et al., 2014; Goodfellow et al., 2015; Deosavi-Dezfooli al., 2016; Carlini Wagner, 2017), hence is important to study the decision boundaries in a manifold region.
The most important question we may ask is: Do decision boundaries exist manifold region? To address this question, we seek the point E Sy, which has the maximum probability to be classified as Class E 21,2,.... M). by solving the following optimization problem:
A
max (x(x) - log
Σ
exp exp(z, (x))
(6)
S. t. w x + by 2 0, V(w, b.) C*,
MIN S x MAX.
where M the number of classes, and 2, (x) the j-th entry of the logits z(x). When x satisfies the constraints, i.e., St. z Sr. - M is an affine function of x, hence 2, (x) can be rewritten as:
(x) Vxzz((') )) (x xx) 2x(x),
Vx St
which implies that the optimization objective in (6) is concave. The classification region of Class t exists in St and only if x' is classified into Class f.
x" lies the faces of the polytope in most cases, shown in Appendix D. Since computing the volume of polytope given by only the V-/H- representation is known as a #P-hard prob- lem (Dyer & Frieze, 1988), the distance between x" and the original test point x", called distortion

---

Published as a conference paper at ICLR 2020
in this paper, is used to informally measure the size of linear region:
distortion tE tE(1......M)
max ||x x"1
We randomly selected 1000 test points to search for the classification regions in their manifold regions. The average number of classification regions and the average distortions are shown in Table 2. The results show that manifold region may contain several classification regions, which contradicts the conjecture region are unlikely to be classified differently. We can also find that training with a large learning rate, using dropout or BN can make the manifold regions less likely to contain decision boundaries. However, this is not the case for BN in CNNs (see Appendix E for more information). In addition, BN can significantly decrease the distortion x', which implies a smaller size the linear regions. Figure shows specific example of x' generated from models trained with different optimization techniques, which also demonstrates our observation.
Hanin & Rolnick (2019) that two points falling into the same linear
Table Average number of classification regions a manifold region, and the average distortions.
Measure
Learning Rate
Vanilla
BN
Dropout
le-3
1.116
1.083
1.012
Number
le-4
8.766
2.622
1.048
le-3
26.35
14.90
25.28
Distortion
le-4
23.81
07.61
25.41
Vanilla-L
Vanilla-S
BN-L
BN-S
Dropout-L
Dropout-S
Figure 5: Different x' of the point x", which is classified into Class 10 (number 9). From left to right, varies from 1 to 10 (number 0 to number 9). Images with green borders are correctly classified into Class 10, and red borders misclassified into Class t. Different rows represent models trained with different optimization techniques learning rates. The models whose names end with "LL" were trained with a larger learning rate (Ie-3), and "-S" a smaller learning rate (1c-4).
Probing decision boundaries from the linear region perspective can bring many potential advantages for analysis. Due to the linearity of the manifold regions, high-order adversaries are not guaranteed to be better than first-order ones. Besides, adding random noise may help generate adversarial examples since more linear regions can be included during searching, which may explain why PGD with random restarts is powerful adversarial attack approach (Madry et al., 2018).
3.5 RELEVANCE OF THE SURROUNDING REGIONS
The expressivity of a DNN depends on the number of the linear regions, but it makes optimization challenging when the gradient information of the surrounding regions has little relevance.
Given an example x", we try to find an x from a different region, with x x" parallel to all the decision boundaries of the region in which x" lies, i.e., orthogonal to the directions of the decision
8

---

Published as a conference paper at ICLR 2020
boundaries. Then we compare the gradient information between and x'. As the classification result of x is equal to arg max)=(112,..... Z, (x)x, the directions of the decision boundaries can be written in the following form:
Vx (2,((x) - 24 (x)), j * k.
Therefore, to satisfy the orthogonality, we can sample an Ln-normalized direction from the nullspace of the matrix A = [x21 (x*), Vxxz(x"); ... Vx
N(A) = fe E F A = 0, ||e|| 1}.
(10)
and then can be written as:
= + Se,
AE (0c
(11)
so that
-xx(2(xx))2zx66 (x-x') =0
(12)
Our experiments were performed 1000 randomly selected test points. For each test point x", randomly sampled 100 Ig-normalized direction e E (A). As B varied from 0 to c, x may belong different regions. We searched for the linear regions along these directions the number of unique linear regions. As shown in Figure 6(a), models using BN or trained with smaller learning can usually partition the input space into more linear regions.
0.2) and counted
Surrounding Regions
Linearity (LR=1e-3)
Linearity (LR=1e-4)
3000
8000
Vanilla
BN
6000
BN
Number
102
Number
2000
Drapout
Number
Drapout
4000
10!
1000
LR=1e-3
2000
LR-1e-4 4
Vanilla
Dropout
0.996
0.998
1.000
0.97
0.98
0.99
1.00
Model
P
(a)
(b)
(c)
Figure 6: (a): boxplot of the number of unique surrounding regions for 1000 test points. Different colors represent different learning rates (LRs). (b) and (c): distributions the cosine similarity p of all unique surrounding regions. Models in (b) were trained with larger learning rate (Ie-3), and (c) a smaller learning rate (Ic-4).
Next, we checked the relevance of these unique surrounding regions. First, we chose an x xx" Be from each unique linear region and calculated g(x) as its decision direction:
g(x)
V (Zk, (x) Zko (x))
(13)
where k, and hi are the indices of the two largest elements of logits. We calculated the cosine similarity g g(x)))((x)
[lg(x)]ll x(x")]l to measure the relevance of different linear regions. As illustrated in
g(x")
Figures 6(b) and 6(c), linear region has high relevance to its surrounding regions, which demon-
strates the lincarity of DNNs. It also shows that BN slightly reduces the relevance.
However, it was found that this relevance decreases rapidly with the depth of the DNN, result- ing in gradients that resemble the white noise, which is known as the shattered gradients prob- lem (Balduzzi et al., 2017). The low relevance also makes it hard to perform adversarial attacks because of the limited information of the local gradients (Athalye et al., 2018).
4 DISCUSSIONS AND CONCLUSIONS
This paper proposes novel tools to analyze the linear regions of DNNs. We explored the linear regions of models trained with different optimization settings, and observed significant differences of
9

---

Published as a conference paper at ICLR 2020
their inspheres, directions of the hyperplanes, decision boundaries, and relevance of the surrounding regions. Our empirical observations illustrated that different optimization techniques may introduce different properties of the linear regions, though they have similar classification accuracies. This phenomenon indicates that a more meticulous perspective is needed to study the behaviors of DNNs.
For DNNs with smooth nonlinear activations, is still an open problem to define their linear regions with soft transition boundaries. One way to address the problem is approximate the activation function by a piecewise linear function, in which case our approaches can directly be utilized to analyze the linear regions. By choosing local linearity measure, like the one proposed by Qin al. (2019), soft linear region may also be precisely described by a set of inequalities, which require that the local linearity of each neuron is larger than certain threshold. However, our approaches cannot be applied to these linear regions since their convexity is not guaranteed.
Our future research will reduce the high computational cost of our approach when applied to deeper and larger DNNs, and formulate theoretical framework to explain why different optimization tech- niques can result different properties of the linear regions. Eventually, we will try to answer the following questions:
Whut is the relationship between the properties of linear regions and the behaviors of DNN?
What kinds of linear regions can best approximate the data manifold?
How to design novel optimization techniques to achieve such linear regions?
ACKNOWLEDGMENTS
This research was supported by the National Natural Science Foundation of China under Grant 61873321 and Hubei Technology Innovation Platform under Grant 2019AEA171, The authors would like to thank Guang-He Lee from MIT for pointing out the connection of our paper to theirs.
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In Proc. Int'l Conf. on Learning Representations, Vancouver, Canada, May 2018
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses adversarial examples. In Proc. 35th Int'l Conf. Machine Learning, pp. 274-283, Stockholm, Sweden, July 2018.
David Balduzzi, Marcus Frean, Lennox Leary. JP Lewis, Kurt Wan-Duo Ma, and Brian McWilliams. The shattered gradients problem: If resnets are the answer, then what is the question? In Proc. 34th Int'l Conf. on Machine Learning, volume 70, pp. 342-350, Sydney, Australia, August 2017.
Yoshua Bengio, Patrice Simard, Paolo Frasconi, et al. Learning long-term dependencies with gradi- ent descent is difficult. IEEE Trans. on Neural Networks, 5(2):157-166, 1994.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šmdii Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Proc. Joint European Conf. Machine Learning and Knowledge Discovery in Databases, pp. 387-402, Berlin, Germany, September 2013. Springer.
Nils Bjorck, Carla P Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normal- ization. In Proc. Advances in Neural Information Processing Systems, pp. 7694-7705. Montreal, Canada, December 2018.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In Proc. IEEE Symposium Security and Privacy, pp. 39-57, San Jose, CA, May 2017.
10

---

Published as a conference paper at ICLR 2020
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-tre Pre-training of deep bidirectional transformers for language understanding. In Proc. of the Conf. of the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, volume 1, pp. 4171 14166, Minneapolis, MN, June 2019.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120ul):212122159 2011.
Martin E. Dyer and Alan M. Frieze. On the complexity of computing the volume of polyhedron.
SIAM Journal on Computing, 17(5):67--974 1988.
Robert M Freund and James B Orlin. On the complexity of four polyhedral set containment prob- lems. Mathematical programming, 33(2):139-145, 1985.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proc. of the 13th Inf'l Conf. on Artificial Intelligence and Stafistics, pp- 249-256,
Sardinia, Italy, May 2010.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Proc. Advances in Neural Information Processing Systems, pp. 2672-2680, Montreal, Canada, December 2014.
lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Proc. Int'l Conf. on Learning Representations, San Diego, CA, May 2015.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recur- rent neural networks. In Proc. IEEE Int'l Conf. on Acoustics, Speech and Signal Processing, pp- 6645-6649, Vancouver, Canada, May 2013.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In Proc. 36th Int' I Conf. on Machine Learning, pp. 2596-2604, Long Beach, CA, May 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proc. the IEEE Int'l Conf. on Computer Vision, pp. 1026-1034, Santiago, Chile, December 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 770-778, Las Vegas, NV, June 2016.
Sepp Hochreiter. The vanishing gradient problem during learning recurrent neural nets and problem solutions. Int'l Journal of Uncertainty, Fuzziness and Knowledge- Bassed Systems, 6002):107-116, 1998.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proc. 32nd Int'l Conf. on Machine Learning, pp. 448-456, Lile, France, July 2015.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proc. Int'l Conf. on Learning Representations, Banff, Canada, April 2014.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. In Proc. Advances in Neural Information Processing Systems, pp. 1097-1105, Lake Tahoe, NE, December 2012.
Guang-He Lee, David Alvarez-Melis, and Tommi S Jaakkola. Towards robust, locally linear deep networks. In Proc. Int'l Conf. on Learning Representations, New Orleans, LA, May 2019.
Nathan Linial. Hard enumeration problems in geometry and combinatories. SIAM Journal on Algebraic Discrete Methods, 7(2):331-333 1986.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In Proc. Int'l Conf. on Learning Representations, Vancouver, Canada, May 2018

---

Published as a conference paper at ICLR 2020
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions deep neural networks. In Proc. Advances in Neural Information Processing Systems, pp. 1924-29332 Montreal, Canada, December 2014.
Seyed-Mohsen Moosavi-Dezfooli Alhussein Fawzi, and Pascal Frossard. Deepfool: A simple and accurate method to fool deep neural networks. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 2574 2582,, Las Vegas, NV, June 2016.
Roman Novak, Yasaman Bahri, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Sensitivity and generalization in neural networks: An empirical study. In Proc. Int'l Conf. on Learning Reprexentations, Vancouver, Canada, May 2018.
Razvan Pascanu, Guido Montufar, and Yoshua Bengio. On the number of response regions of deep feed forward networks with piece-wise linear activations. CoRR, abs/1312.6098,, 2014. URL https: /ttpxvaxivv//v.////v///ee/a..av. org/ abs 111... 6098.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponen- tial expressivity deep neural networks through transient chaos. In Proc. Advances in Neural Information Processing Systems, pp. 3360-3368, Barcelona, Spain, December 2016.
Chongli Qin, James Martens, Sven Gowal, Dilip Krishnan, Krishnamurthy Dvijotham, Alhussein Fawzi, Soham De, Robert Stanforth, and Pushmeet Kohli. Adversarial robustness through local linearization. In Proc. Advances in Neural Information Processing Systems, pp. 13824-1333 13833,, Vancouver, Canada, December 2019.
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch nor- malization help optimization? In Proc. Advances Neural Information Processing Systems, pp. 2483,,493, Montreal, Canada, December 2018.
Andrew M. Saxe, James I.. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics learning in deep linear neural networks. In Proc. Int'l Conf. on Learning Representations, Banff, Canada, April 2014.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In Proc. 35th Int'l Conf. on Machine Learning, pp. 4565-4573, Stockholm, Sweden, July 2018
David Silver, Julian Schrittwesser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, and Adrian Bolton. Mastering the game of Go without human knowledge. Nature, 550(7676):354, 2017.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1):1929-195) 2014.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In Proc. Int'l Conf. on Learning Representations, Banff, Canada, April 2014.
Csaba D Toth, Joseph O' Rouure,, and Jacob E Goodman. Handbook of discrete and computational geometry. Chapman and Hall/CRC, third edition, 2017.
Stefan Wager, Sida Wang, and Percy S Liang. Dropout training as adaptive regularization. In Proc. Advances in Neural Information Processing Systems, pp. 351-359, Lake Tahoe, NE, December 2013.
12

---

Published as a conference paper at ICLR 2020
A ILLUSTRATION ON A TOY DATASET
Figure shows a two-dimensional slice of a high-dimensional input space, which may not be con- vincing enough to describe the properties of línear regions through the entire input space. To address the problem, we trained three models (vanilla, BN, dropout) on two-dimensional toy dataset to see the properties still remain.
Figure visualizes the toy dataset we constructed, which consists of two separate spirals, represent- ing two different classes. The vanilla model used here was fully-comnecto DNN which consisted of three hidden layers with 10 rectified linear nodes in each. The BN model was the vanilla model with BN added after the pre-activations of each hidden layer, and the dropout model added dropout after the activations (the drop rate was 0.2). The models were trained with Adam optimizer (LR=le- 3, 31 =0.9, 8z=0.999).
1.0
0.5
0.0
-0.5
1..
11.
-0.5
0.0
0.5
1.0
Figure 7: Visualization of the toy dataset. Different colors represent different classes.
The test accuracies for the three models were all 100%. Figure 8 plots linear regions and classifica- tion regions in the input space, illustrating the same properties Figure shows.
Vanilla
BN
Dropout
Linear Regions
Classification Regions
Figure 8: Linear regions and classification regions of models trained with different optimization techniques. The gray curves in the top transition boundaries separating different linear regions, and the color represents the activation rate the corresponding linear region. the bottom row, different colors represent different classification regions, separated by the decision boundary.
13

---

Published as a conference paper at ICLR 2020
B CALCULATE PARAMETERS OF THE INEQUALITIES
As mentioned Section 2.1, the first E St-1- Besides, the pre-activation outputs of the 1-th hidden layer h'(x) are also an affine
hidden layers serve as an affine transformation of
transformation of the activation outputs of the (t- 1) layer, hence h' hx()) is a linear function of E S which means h (x) = w x bn. where n denotes a node of the (-th layer. So, we have:
Wa = (x),
(14)
bn (x) x hx()) (xx)"
(15)
Recall that according the definition of St-1, x" shares the same linear function as other St-1, therefore we have:
w (x"),x")),
(16)
b, (x') h
(17)
Then we should select from S to construct St, which means x satisfies sgn(h", (x" ))b, (x) > 0. ie., x has the same activation state of Node n as x". For convenience, Wn and b,, are directly multiplied by sgn(h", (x*)) to obtain the form in (4).
C REMOVE REDUNDANT INEQUALITIES
Every constraint in Sy. represents a halfspace, but some them are redundant, i.e., they are com- pletely overrode by others. To eliminate the redundant constraints, we need to successively solve the following linear programming problem for each untested constraint and sequentially remove the redundant constraint from C*:
= min
W +
(18)
S. w x + b; 2 0, (i, EC,
W x + b7 +1 0,
MIN, X MAXx;
The constraint wº'x by 0 is redundant if and only y 2 0.
Note that each and every constraint needs to be tested sequentially, resulting in very heavy compu- tational cost when dealing with thousands of constraints.
D x² LIES ON THE FACES OF THE LINEAR REGION IN MOST CASES
Proposition 1 x" defined in Section 3.4 lies on the faces of its linear region in most cases.
Proof Let M denote the number of classes, x" E Rd given point lying in the bounded linear region S. as the faces of S. Recall that the function fitted a linear region is completely linear, hence the j-th logit zj (z) can be rewritten as:
2x(x) = x by, Vj (1,2,..., M}.
(19)
exp(w? As defined in (6), let (x() Σ, exp(w) x+b,), then x" = arg maxxes log 1fx E S (S,, x² must be a maximum, which means:
M
V log
Σ
=0
(20)
Therefore,
M W. = Σ pi(x') 1=1
(21)
Recall that w, E Rd and >> M, hence in most cases {wil are linear independent, which means we cannot be represented as the linear combination of ( Since 0 px(x!) 1, there is no M, satisfying (21). Therefore, x E as.
M.
14

---

Published as a conference paper at ICLR 2020
E EXPERIMENTS ON THE 10 DATASET
We also analyzed simple CNN models trained on the CIFAR-10 dataset. The results are presented in this Appendix.
E
MODELS
The base architecture of the CNN models is shown in Table 3. To simplify the analysis, the convo- lutional layers were not padded, and large strides were used to replace the max-pooling layers. For the BN model, BN was added before ReLU activations. For the dropout model, dropout layers were added after ReLU activations.
Table 3: Architecture of the vanilla CNN model.
Layers
Parameters
Activation
Input Conv filters=(3, 3)2 strides=(2, 2)
input size=(32, 32)x3
ReLU
Conv filters=(3, 3)x64; strides=(2, 2)
ReLU
Conv
filters=(3, 3)x 128; strides=(2, 2)
ReLU
Flatten
Dense
nodes=1024 nodes=10
ReLU
Dense
Softmax
The models were trained with Adam optimizer (learning rate le-3, 31=0.9, $2=0.999) on the CIFAR- 10 dataset without data augumentation. The pixel values were rescaled to [-1, 1]. The batch size was 256, and early stopping set of the vanilla, BN and dropout models were 68.2%, 70.1% and 69.2%, respectively. Since the goal of this paper is to show that different optimization techniques classification accuracies but significantly different linear regions, we only trained our models with one learning rate (Ie-3), because other learning rates (Ie-2, le-4) led to models with significantly different classification accuracies.
used to reduce overfitting. After training, the accuracies
the test
result in models with similar
E.2 PROPERTIES
As we have claimed Section 2, a CNN model can be regarded as a highly sparse fully-connected DNN, which means we can analyze the properties of its linear regions in the same way. However, a convolutional layer may introduce some other properties into the linear regions. For example, considering the sparsity of the weights, a node of convolutional layer only partition subspace into linear regions (instead of the whole input space, like node in fully-connected DNNs does). Therefore, the partition of the linear regions most subspaces do not intersect. A direct consequence of their independency is that the properties of the linear regions in CNN more stable than those in fully-connected DNN, which will be shown in the following experiments.
relatively independent for the nodes in CNN, as
We randomly selected 1000 test points to perform the analysis. The inspheres of the linear regions in the CNNs are shown in Figure 9. Compared with the MNIST dataset, the CIFAR-IO dataset is more complicated and the mean point of class no longer classified into the same class, hence we randomly sampled a point from another class to replace the mean point described in Section when constructing the decision regions. The experimental results show that both BN and dropout can narrow the linear regions. For dropout, the effect is more obvious on the decision boundaries than on the manifold regions.
Figure 10 shows the angles between different hyperplanes of a linear region. According to the architecture of the models, the first x 15 x 32 + 7 7 x 64 +3+33 3 x 128 11, 488 hyperplanes were provided by the convolutional layers, and the last 1, 024 by the fully-connected hidden layer. Since a node in a convolutional layer only partitions a certain subspace into regions, most of the pixel values are 0 in Figure 10 because there is no intersection between two subspaces. However, we can still observe that BN can orthogonalize the directions of the hyperplanes, whereas dropout the opposite.
15

---

Published as a conference paper at ICLR 2020
100
100
100
Vanilla
Vanilla Dropoutt
Vanilla Dropouut
80
80
80
Drepout
Demsity
Demsity
Density
40
40
40
20
20
20
0.00
0.03
0.06
0.09
0.12
0.00
0.03
0.06
0.09
0.12
0.00
0.03
0.06
0.09
0.12
Inradius
Inradius
Inradius
(a)
(b)
(c)
Figure 9: Inradius distributions of different optimization techniques for CNN models.(a) Manifold
region; (b) Decision region; (c) Adversarial region.
12000
180
12000
180
12000
180
150
150
150
8000
120
8000
120
8000
120
90
90
90
4000
4000
4000
4000
12000
4000
12000
4000
12000
(a)
(b)
(c)
Figure 10: Angles between directions different hyperplanes of single manifold region. The dices on both axes indicate different hyperplanes: 0-7,199 represent the hyperplanes of the first con- volutional layer, 2200-1,,33 the second convolutional layer, 10,336- 11,487 the third convolutional layer, and 11, 11,488-12,51 the fully-connected hidden layer. The value of pixel is arccos i.e. the angle between w, and Wy- (a) Vanilla; (b) BN; (c) Dropout.
w w,
[w.
16

---

Published as a conference paper at ICLR 2020
Decision boundaries in the manifold regions of the CNNs seem less likely to be eliminated, com- pared with the fully-coneected DNNs. As shown Table 4, dropout can eliminate the decision boundaries in the manifold regions of CNNs, but BN did not work anymore. However, according to the distortions of the three models, BN still showed its ability to reduce the size the manifold re- gions. Figure 11 shows specific example of x', whose original point classified automobile. x" of the BN model had smaller distortion, which was also observed in fully-connected DNNs.
Table 4: Average numbers of the classification regions in manifold region, and the average distor- tions.
Measure
Vanilla
BN
Dropout
Number
7.811 27.08
9.984 20.85
2.901
Distortion
25.25
Vanilla
BN
Dropout
Figure 11: Different x² of a point which is classified into Class (automobile). From left to right, t varies from to 10 (airplane, automobile, bird, cat, deer, dog, frog, horse, ship, truck). Images with green borders are correctly classified into Class 2, and red borders misclassified into Class Different rows represent models trained with different optimization techniques.
The numbers of unique surrounding regions manifold region are shown in Figure 12(a). Though BN showed its strength in increasing the number of the linear regions, the effect was less obvious compared with those Figure 6(a) for fully-connected DNNs. As we have pointed out before, the sparsity of the weights in the convolutional layers contributes to the stability of the properties of the linear regions. The relevance of the surrounding regions shown Figure 12(b) was similar to fully-connected DNNs. BN still shattered the decision directions, well as dropout, which was slightly different from the results for fully-connected DNNs.
12000
50000
Number of regions
Vanilla
10000
40000
BN
8000
Number
Dropout
30000
6000
4000
20000
2000
10000
Vanilla
BN
Dropout
0.94
0.96
0.98
1.00
Model
P
(a)
(b)
Figure 12: (a) Boxplot of the number unique surrounding regions for 1000 test points; (b) Distri- butions of the cosine similarity p of all unique surrounding regions for the 1000 test points.
17


Reviews:
[{"review_id": "SJx9dS5oFr", "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": "First, I believe that the acknowledgements in the manuscript give identifying information which could stand in conflict with a double blind review process. I’ll leave it to the area chairs/program chairs to make a decision on this. The following review will be contingent on the fact that the authors did not break the submission rules.\n\nThis paper aims to give new insights into deep neural networks by presenting a number of approaches to analyse the linear regions in such networks. The authors define a linear region around a point x* as the intersection between a number of half spaces that are defined through linear approximations of a DNN (tangents) around that point x*. The authors show that points within these regions can be found using convex optimization with a number of linear constraints that are equal or less than the number of nodes in a DNN. In experiments with a fully connected network the authors analyse different properties of these linear regions: (1) How big is the biggest sphere that we can fit in a linear region? (2) How much do the hyperplanes that define a region correlate with each other? (3) How reliably does a linear region represent a single class? And (4), How does a linear region interact with neighbouring regions? In their presentation, the authors focus on comparing these properties between models that were either trained without regularisation, with batch normalisation, or with dropout and with different learning rates. This allows them to draw insightful conclusions about the difference between linear regions in these models. The authors hope that their work will enable new ways of analysing DDNs that will inspire new architectures and optimization techniques.\n\nI vote to accept this paper. The authors present a large array of methods to analyse the linear regions of DNNs. Their insights into the differences of BN and Dropout are useful (figure 1 & 2) and sensible (figure 3). The implications of linear regions on adversarial robustness can have an impact in the future. Because the paper relies on geometrical reasoning, I wished there would be more visualisations that guide the reader.\n\nHere are a number of comments and questions that I have on the manuscript:\n- Figure 1 Top: What do the different colour represent in the linear regions plot?\n- Section 2.1: maybe add a toy graph that visualises the depth-wise ‘exclusion’ process of feasible “neighbours” of x*?\n- Eq. (2) & (3): Explain where these equations come from.\n- Sec 3.2, first sentence. The authors claim that inspheres of linear regions are highly relate to the expressivity of DNN. Can they elaborate on that claim? Is this claim a result of their experiments?\n- What is the relationship between the number of constraints in eq. (5) and the radius of an insphere? Does the insphere size decrease with more constraints? What implications would that have on deeper networks than the one that was presented?\n- Why should distortion be a good measure of the size of a linear region?\n- The authors claim that it is expensive to run their approach, and that they will aim to improve speed in the future. Can the authors give a more concrete example of runtimes in their current approach?\n", "extra_scores": {"experience_assessment": "I do not know much about 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": {}}, {"review_id": "H1xyI5totr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work presents an array of analytical tools to characterize linear regions of deep neural networks (DNNs). Using the tools the work analyzes the effect of dropout and batch normalization (BN) on the linear regions of trained DNNs; namely, by assessing the properties such as inspheres, orientation of hyperplanes, decision boundaries and relevance of surrounding regions, the authors highlight the differences and similarities of linear regions induced by vanilla SGD as compared to SGD with dropout or BN.   \n\nThe paper is clearly written and is easy to follow for the most part. The paper indeed presents a number properties for analyzing the nature of linear regions in DNNs; however it falls short of connecting them with an improvement in the optimization or interpretability of DNNs. \n\nEven with respect to providing support for general applicability, the work does not go very far: without enough variation in data (not just image benchmarks), tasks and architecture, it is hard to determine if the analysis tools presented in the paper generalize beyond the chosen setup. For instance just the optimization techniques compared in the paper have their own hyperparameters and it is not clear how the results might vary with them. \n\nI am not sure what to take away from figure 1 since it's only a two-dimensional slice of very high-dimensional input space. Maybe the authors could instead choose an example with a low-dimensional input space for illustration purposes.\n\nAlso, how much can be perceived from distributions shown in figure 2, since inradius (Eq. 5) may turnout to be a very coarse representation of linear regions, especially for deeper networks. Can the authors clarify this? Moreover, how would the figures look if we were using a different objective, dataset or architecture?\n \nIn figure 3, is it not possible to show the average results instead of just one example?\n \nI would further like to know how the authors would deal with scalability issues if their analysis were to applied to more realistic (i.e. large) network architectures.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Byg1GC30tH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 addresses the following: how do batch normalization and dropout affect the number of linear regions present in a deep network? It does so by devising a search procedure for enumerating a set of linear inequalities that define the linear region around a particular input. The linear region is defined as the region of input space that activates the same units/nodes in the network. The authors compute these linear regions for three different types of fully connected networks trained with: vanilla (nothing added), batch norm, and dropout. Given these linear regions, the authors studied a number of their properties, such as the radii of inscribed spheres, angles between hyperplanes, and number of unique surrounding regions.\n\nComments\n- This paper enumerates a number of interesting findings, all of which seem to raise intriguing questions about the properties of trained networks. However, after reading the paper, I am left a little unsure of what to make of the results. However, I do not think this is a fault of the paper, instead I enjoyed that this paper raises so many interesting questions. Still, some more discussion and interpretation of the results is perhaps warranted.\n- I especially enjoyed the writing, the problem statement and exposition were clear and easy to follow.\n- Perhaps the authors could comment, in the discussion, if they think their methods could be extended to networks with smooth nonlinearities (such as tanh), or what aspects of their results are also apply to networks with different nonlinearities.\n- I was also curious if the authors could comment on similarities and differences between their findings and this relevant paper (https://arxiv.org/abs/1802.08760) by Novak et al. that empirically computes linear regions for 2D slices through input space.\n\nMinor edits\n- After introducing the definition of the insphere (eq 5), it would be helpful to remind the reader that this is for a particular region defined by the set of inequalities C^\\*.\n- Typo in footnote 2 on page 5: partitioned", "extra_scores": {"experience_assessment": "I have read many 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 carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the properties of regions where a DNN with piecewise linear activations behaves linearly. They develop a variety of techniques to chracterize properties and show how these properties correlate with various parameters of the network architecture and training method.

The reviewers were in consensus on the quality of the paper: The paper is well written and contains a number of insights that would be of broad interest to the deep learning community.

I therefore recommend acceptance.
Decision: Accept (Poster)