Year: 2020

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. It is believed that the number of these regions represents the expressivity 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 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.

heading: 1 INTRODUCTION
text: 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 et al., 2016; Silver et al., 2017; Devlin et 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 a 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 in one-to-one correspondence 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 a 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 optimization, such as the vanishing/exploding gradient problem (Bengio et 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 a DNN to randomly drop some nodes during training and work like an ensemble of 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.
can help the optimization during training (Wager et al., 2013; Santurkar et al., 2018; Bjorck et 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 an 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 input space into many more linear regions than the vanilla DNN.
2. The linear regions resulted from the BN model are more uniform in size than those from the dropout DNN.
3. Many transition boundaries of the dropout DNN share similar norm directions, and concentrate around the decision boundaries.
Figure 1 illustrates that different optimization techniques can lead to completely different linear regions even using the same DNN architecture, which may influence the behaviors of the DNN, such as its adversarial robustness (Biggio et al., 2013; Szegedy et al., 2014) or some other undiscovered ones (Appendix A shows another example on a two-dimensional toy dataset). Therefore, it is important to probe the properties of the linear regions introduced by these frequently-used optimization techniques, instead of just looking at the learning curves.
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.
3. Dropout makes regions in which data points lie less likely to contain the decision boundaries.
4. The gradient information of a linear region has high relevance to its surrounding regions; however, BN slightly reduces the relevance.
It 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 manifold 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 to 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.

heading: 2 LINEAR REGIONS
text: This section describes the detailed approach1 for searching for the linear regions of a given input, and introduces some basic concepts of convex polytopes.

heading: 2.1 SEARCH FOR THE LINEAR REGIONS
text: 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 to search for its corresponding halfspaces, which are determined by the activation state of the DNN.
Let’s consider a vanilla fully-connected DNN with L hidden layers and ReLU activation. Mathematically, let x ∈ Rd denote the d-dimensional vectorized input, hl(x) the pre-activation outputs of the l-th hidden layer with nl nodes (l = 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 relationship between a linear region and an activation state, its corresponding linear region is a set of inputs which lead to the same activation state of the DNN.
Let Sl denote a set of the inputs whose activation states of the first l hidden layers are the same as those of x∗. Obviously, Sl+1 ⊆ Sl. Consider the first layer. Since h1 : Rd → Rn1 is simply an affine transform of x, according to the activation state, S1 can be written as:
S1 = { x | wTi x+ bi ≥ 0, ∀i ∈ {1, ..., n1} } , (1)
where
wi = sgn(h1i (x ∗))∇xh1i (x∗), (2)
bi = sgn(h1i (x ∗)) [ h1i (x ∗)− (∇xh1i (x∗))Tx∗ ] . (3)
Next, we select the points from S1 to construct S2, which activate the same nodes of the second layer as x∗ does. Recall that the points in S1 lead to the same activation state of the first layer, hence h2 : S1 → Rn2 is also an affine transform of x. Therefore, S2 can be constructed by adding linear inequality constraints to S1, in the same way as (1). Due to the linearity of hl : Sl−1 → Rnl (where S0 = Rd) for all l, this procedure can be repeated till the last hidden layer. The detailed deduction is presented in Appendix B, and the depth-wise exclusion process to search for a linear region of x∗ is illustrated in Figure 2.
1We developed the approach for finding the linear regions independently, but later found that the same approach has been proposed in (Lee et al., 2019). However, the two papers use the linear regions for different purposes.
Let C∗ = {(wi, bi)} ∑L l=1 nl i=1 be the set of parameters of all the linear inequality constraints. Then
SL, which is the linear region that x∗ lies in, can be represented as the intersection of ∑L
l=1 nl halfspaces:
SL = { x | wTi x+ bi ≥ 0, ∀(wi, bi) ∈ C∗ } , (4)
where the DNN is a locally linear model, as z : SL → RM is an affine transform of x.
Though we mainly discuss the standard fully-connected DNNs, the form to describe a linear region can be extended to other situations with little modification. For instance, BN is just a reparameterization of the weights, a convolutional neural network (CNN) can be viewed as a sparse fully-connected DNN, and max-pooling is simply adding more linear inequalities to identify the maximum.

heading: 2.2 CONVEX POLYTOPES
text: A linear region can be represented as the set of solutions to a finite set of linear inequalities 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 polytopes2. We omit the word convex in the rest of the paper to avoid repetition.
A polytope can also be represented as a convex hull of a finite set of points, which is known as the V-representation. Different representations may lead to different complexities when dealing with the same problem; nevertheless, it is challenging to convert one representation into the other (Toth et al., 2017). As the dimensionality increases, it is even harder to calculate the number of vertices/facets with a single H-/V- representation (Linial, 1986), or to verify the equivalence between an H-representation and a V-representation (Freund & Orlin, 1985). More information about polyhedral computation can be found here3.
It should be noted that convex optimization is capable of probing the properties of the linear regions, because H-representation is a natural description of a convex feasible region, and a DNN’s behavior is completely linear in this feasible region.

heading: 3 PROPERTIES OF THE LINEAR REGIONS
text: This section presents various properties of the linear regions of DNNs, which were trained using different optimization settings.

heading: 3.1 MODELS
text: We used a fully-connected DNN as our 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
2Here we use the term polytope to denote a bounded polyhedron. 3https://inf.ethz.ch/personal/fukudak/polyfaq/polyfaq.html
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 (β1 = 0.9, β2 = 0.999) but different learning rates (1e-3 and 1e-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 it 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.
As shown in Section 2, the number of constraints in (4) equals the number of hidden nodes; hence, it 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 × 3 = 3, 072. In addition to the natural bounds for the 28× 28 = 784 pixel values (MINx ≤ x ≤ MAXx), each linear region is defined by 3, 072 + 784× 2 = 4, 640 linear inequalities. Our analysis of CNNs trained on the CIFAR-10 dataset is presented in Appendix E.

heading: 3.2 THE INSPHERES
text: 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, it does indicate a region’s narrowness.
The insphere of a polytope can be found by solving the following convex optimization problem:
max x,r r (5)
s. t. wTi x− r∥wi∥+ bi ≥ 0, ∀(wi, bi) ∈ C∗, MINx + r ≤ x ≤ MAXx − r,
where x is the center of the insphere, r the inradius, and C∗ the set of parameters of SL defined in (4). The main idea of the optimization is to find a point in a polytope, whose distance to the nearest facet is the largest.
As shown in Figure 1, linear regions vary according to their closeness to the decision boundaries, hence we studied the inspheres of three different categories of regions4, which are defined as follows:
Manifold region: The region in which the test points lie. Decision region: The region which contains the normal decision boundaries. We define a normal
decision boundary as the classification boundary between one test point and the mean point of another class. When we test our models, the mean point of a class is classified into the same class for the MNIST dataset.
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 xtarget the adversarial point or the mean point of another class. We searched for the maximum α ∈ [0, 1] which causes xα = α ·xtarget+(1−α) ·xtest to be classified into the same class as xtest, and the region in which xα lies contains the decision boundaries.
4These regions should not be confused with a classification region, which is partitioned according to the classes of the points in the input space.
As shown in Figure 3, different optimization settings introduce significantly different inradius distributions. Compared with the vanilla models, BN leads to the smallest inradiuses of the linear regions, whereas dropout, as 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 adversarial 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 to make the inradius distribution less sensitive to the learning rate, which is consistent with the observations in Bjorck et 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 manifold regions, which was also observed by Novak et al. (2018) that on-manifold regions are larger than off-manifold regions. It is reasonable because decision boundary curves need more sophisticated approximation.

heading: 3.3 DIRECTIONS OF THE HYPERPLANES
text: Another observation is that BN makes the directions of the hyperplanes of a linear region orthogonal, whereas dropout the opposite. Since it is time-consuming to eliminate the redundant hyperplanes, as explained in Appendix C, 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 are in the form of wTx+b ≥ 0. Figure 4 shows the angles between directions of every two different hyperplanes of a 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.
∥wi∥∥wj∥ , i.e., the angle between wi and wj . The models in the top row were trained with
a larger learning rate (1e-3), and the bottom row a smaller learning rate (1e-4).
We also observed an interesting phenomenon: the orthogonality of the weights vanished during training. We tried to explicitly decorrelate the directions at initialization by introducing an orthogonal initializer (Saxe et al., 2014), but the orthogonality was still broken after training. It is interesting to see if the properties of initialization can be preserved in training, which is one of our future research directions.

heading: 3.4 DECISION BOUNDARIES IN A MANIFOLD REGION
text: Adversarial examples are benign inputs with imperceptible perturbations, which can dramatically degrade the performance of a machine learning model (Biggio et al., 2013; Szegedy et al., 2014). Adversarial attacks aim to push a benign input across the nearest decision boundary (Szegedy et al., 2014; Goodfellow et al., 2015; Moosavi-Dezfooli et al., 2016; Carlini & Wagner, 2017), hence it is important to study the decision boundaries in a manifold region.
The most important question we may ask is: Do decision boundaries exist in a manifold region? To address this question, we seek the point x ∈ SL which has the maximum probability to be classified as Class t ∈ {1, 2, ...,M}, by solving the following optimization problem:
max x
zt(x)− log  M∑ j=1 exp(zj(x))  (6) s. t. wTi x+ bi ≥ 0, ∀(wi, bi) ∈ C∗,
MINx ≤ x ≤ MAXx, where M is the number of classes, and zj(x) the j-th entry of the logits z(x). When x satisfies the constraints, i.e., x ∈ SL, z : SL → RM is an affine function of x, hence zj(x) can be rewritten as:
zj(x) = (∇xzj(x∗))T (x− x∗) + zj(x∗), ∀x ∈ SL (7) which implies that the optimization objective in (6) is concave. The classification region of Class t exists in SL if and only if xt is classified into Class t.
xt lies on the faces of the polytope in most cases, as shown in Appendix D. Since computing the volume of a polytope given by only the V-/H- representation is known as a #P-hard problem (Dyer & Frieze, 1988), the distance between xt and the original test point x∗, called distortion
in this paper, is used to informally measure the size of a linear region:
distortion = max t∈{1,2,...,M}
∥xt − x∗∥. (8)
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 a manifold region may contain several classification regions, which contradicts the conjecture in Hanin & Rolnick (2019) that two points falling into the same linear 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 of xt, which implies a smaller size of the linear regions. Figure 5 shows a specific example of xt generated from models trained with different optimization techniques, which also demonstrates our observation.
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 a powerful adversarial attack approach (Madry et al., 2018).

heading: 3.5 RELEVANCE OF THE SURROUNDING REGIONS
text: 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
boundaries. Then we compare the gradient information between x and x∗. As the classification result of x is equal to argmaxj={1,2,...,M} zj(x), the directions of the decision boundaries can be written in the following form:
∇x (zj(x)− zk(x)) , j ̸= k. (9)
Therefore, to satisfy the orthogonality, we can sample an L2-normalized direction e from the nullspace of the matrix A = [∇xz1(x∗),∇xz2(x∗), ...,∇xzM (x∗)]:
N(A) = {e ∈ Rd | ATe = 0, ∥e∥ = 1}, (10)
and then x can be written as:
x = x∗ + βe, ∀β ∈ [0, ϵ], e ∈ N(A), (11)
so that
(∇x(zj(x∗)− zk(x∗)))T (x− x∗) = 0. (12)
Our experiments were performed on 1000 randomly selected test points. For each test point x∗, we randomly sampled 100 L2-normalized direction e ∈ N(A). As β varied from 0 to ϵ, x may belong to different regions. We searched for the linear regions along these directions (ϵ = 0.2) and counted the number of unique linear regions. As shown in Figure 6(a), models using BN or trained with a smaller learning rate can usually partition the input space into more linear regions.
Next, we checked the relevance of these unique surrounding regions. First, we chose an x = x∗+βe from each unique linear region and calculated g(x) as its decision direction:
g(x) = ∇x (zk1(x)− zk2(x)) , (13)
where k1 and k2 are the indices of the two largest elements of logits. We calculated the cosine similarity ρ = g(x)
T g(x∗) ∥g(x)∥∥g(x∗)∥ to measure the relevance of different linear regions. As illustrated in
Figures 6(b) and 6(c), a linear region has high relevance to its surrounding regions, which demonstrates the linearity 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, resulting in gradients that resemble the white noise, which is known as the shattered gradients problem (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).

heading: 4 DISCUSSIONS AND CONCLUSIONS
text: 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
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, even 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, it is still an open problem to define their linear regions with soft transition boundaries. One way to address the problem is to 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 a local linearity measure, like the one proposed by Qin et al. (2019), a 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 a 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 a theoretical framework to explain why different optimization techniques can result in different properties of the linear regions. Eventually, we will try to answer the following questions:
• What is the relationship between the properties of linear regions and the behaviors of a DNN?
• What kinds of linear regions can best approximate the data manifold? • How to design novel optimization techniques to achieve such linear regions?

heading: 5 ACKNOWLEDGMENTS
text: 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.

heading: B CALCULATE PARAMETERS OF THE INEQUALITIES
text: As mentioned in Section 2.1, the first l − 1 hidden layers serve as an affine transformation of x ∈ Sl−1. Besides, the pre-activation outputs of the l-th hidden layer hl(x) are also an affine transformation of the activation outputs of the (l − 1)-th layer, hence hl(x) is a linear function of x ∈ Sl−1, which means hln(x) = wTnx+ bn, where n denotes a node of the l-th layer. So, we have:
wn = ∇xhln(x), (14) bn = h l n(x)−wTnx = hln(x)− (∇xhln(x))Tx. (15)
Recall that according to the definition of Sl−1, x∗ shares the same linear function as other x ∈ Sl−1, therefore we have:
wn = ∇xhln(x∗), (16) bn = h l n(x
∗)− (∇xhln(x∗))Tx∗. (17) Then we should select x from Sl−1 to construct Sl, which means x satisfies sgn(hln(x
∗))hln(x) ≥ 0, i.e., x has the same activation state of Node n as x∗. For convenience, wn and bn are directly multiplied by sgn(hln(x ∗)) to obtain the form in (4).

heading: C REMOVE REDUNDANT INEQUALITIES
text: Every constraint in SL represents a halfspace, but some of them are redundant, i.e., they are completely 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∗:
y = min x
wTk x+ bk (18)
s. t. wTi x+ bi ≥ 0, ∀i ̸=k(wi, bi) ∈ C∗, wTk x+ bk + 1 ≥ 0, MINx ≤ x ≤ MAXx,
The constraint wTk x+ bk ≥ 0 is redundant if and only if y ≥ 0. Note that each and every constraint needs to be tested sequentially, resulting in very heavy computational cost when dealing with thousands of constraints.
D xt LIES ON THE FACES OF THE LINEAR REGION IN MOST CASES
Proposition 1 xt 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∗ ∈ Rd a given point lying in the bounded linear region S, ∂S the faces of S. Recall that the function fitted in a linear region is completely linear, hence the j-th logit zj(x) can be rewritten as:
zj(x) = w T j x+ bj , ∀j ∈ {1, 2, ...,M}. (19)
As defined in (6), let pt(x) = exp(wTt x+bt)∑ j exp(w T j x+bj) , then xt = argmaxx∈S log pt(x). If xt ∈ S \ ∂S, xt must be a maximum, which means:
∇x log pt(xt) = M∑ i=1 pi(x t)(wt −wi) = 0. (20)
Therefore,
wt = M∑ i=1 pi(x t)wi. (21)
Recall that wi ∈ Rd and d ≫ M , hence in most cases {wi}Mi=1 are linear independent, which means wt cannot be represented as the linear combination of {wi̸=t}Mi=1. Since 0 < pt(xt) < 1, there is no {pi(xt)}Mi=1 satisfying (21). Therefore, xt ∈ ∂S.

heading: E EXPERIMENTS ON THE CIFAR-10 DATASET
text: We also analyzed simple CNN models trained on the CIFAR-10 dataset. The results are presented in this Appendix.
E.1 MODELS
The base architecture of the CNN models is shown in Table 3. To simplify the analysis, the convolutional 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.
The models were trained with Adam optimizer (learning rate 1e-3, β1=0.9, β2=0.999) on the CIFAR10 dataset without data augumentation. The pixel values were rescaled to [-1, 1]. The batch size was 256, and early stopping was used to reduce overfitting. After training, the accuracies on the test 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 can result in models with similar classification accuracies but significantly different linear regions, we only trained our models with one learning rate (1e-3), because other learning rates (1e-2, 1e-4) led to models with significantly different classification accuracies.
E.2 PROPERTIES
As we have claimed in 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 a convolutional layer can only partition a subspace into linear regions (instead of the whole input space, like a node in fully-connected DNNs does). Therefore, the partition of the linear regions are relatively independent for the nodes in a CNN, as most subspaces do not intersect. A direct consequence of their independency is that the properties of the linear regions in a CNN are more stable than those in a fully-connected DNN, which will be shown in the following experiments.
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-10 dataset is more complicated and the mean point of a class is no longer classified into the same class, hence we randomly sampled a point from another class to replace the mean point described in Section 3 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 15× 15× 32+7× 7× 64+3× 3× 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.
∥wi∥∥wj∥ ,
i.e., the angle between wi and wj . (a) Vanilla; (b) BN; (c) Dropout.
Decision boundaries in the manifold regions of the CNNs seem less likely to be eliminated, compared with the fully-connected DNNs. As shown in 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 of the manifold regions. Figure 11 shows a specific example of xt, whose original point was classified as automobile. xt of the BN model had smaller distortion, which was also observed in fully-connected DNNs.
The numbers of unique surrounding regions of a 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 in 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 in Figure 12(b) was similar to fully-connected DNNs. BN still shattered the decision directions, as well as dropout, which was slightly different from the results for fully-connected DNNs.

Review summaries:
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.