# The Vanishing Decision Boundary Complexity and the Strong First Component

Hengshuai Yao
Sony AI
University of Alberta
<EMAIL_ADDRESS>
###### Abstract

We show that unlike machine learning classifiers, there are no complex
boundary structures in the decision boundaries for well-trained deep models.
However, we found that the complicated structures do appear in training but
they vanish shortly after shaping. This is a pessimistic news if one seeks to
capture different levels of complexity in the decision boundary for
understanding generalization, which works well in machine learning.
Nonetheless, we found that the decision boundaries of predecessor models on
the training data are reflective of the final model’s generalization. We show
how to use the predecessor decision boundaries for studying the generalization
of deep models. We have three major findings. One is on the strength of the
first principle component of deep models, another about the singularity of
optimizers, and the other on the effects of the skip connections in ResNets.
Code is at https://github.com/hengshu1/decision_boundary_github.

##  1 Introduction

Decision boundary is very useful for understanding the generalization of
machine learning classifiers. A decision boundary that can explain the
generalization of deep neural networks is an attractive and long-standing
challenge. Many efforts are related to this problem [25, 30, 21, 48, 2, 9, 53,
39, 40, 10, 62, 54, 51, 7]. We are going to review and discuss in details
later in Section 5. In a nutshell, most works rely on the adversarial samples
to characterize the decision boundary structures of deep neural networks.

We aim to understand the decision boundary on the training samples. Not only
is our method much simpler in methodology and computation, but also
understanding the test performance of classifiers from the training samples is
a fundamental problem. We found that, surprisingly, the decision boundaries of
well trained deep models are approximately linear. It is well known that for
the decision boundaries of machine learning classifiers, their complexity
grows as fitting more closely to the training data. However, such complex
structures do not exist for well trained deep models. The first plot of Figure
1 shows the case for VGG19 [61]. 111Following [62], we use the CIFAR-10 data
set [34] to visualize the decision boundary. Li et. al. [38] also used this
data set to understand generalization by visualization (via loss contour
plots). Near the end of training, the decision boundary is indeed shaping but
the complex boundary structures vanish shortly after they are formed.
Interestingly, the predecessor models (especially those achieving over 99.0%
training accuracy) demonstrate an evolutionary process in the decision
boundary, as shown by the rest of the plots. 222A video of the full evolution
of the decision boundary is provided in the supplementary materials. The
boundary complexity vanishing behavior has not been observed before in both
deep learning and machine learning to the best of our knowledge.

The major contributions of this paper are as follows.

Figure 1:  The decision boundary undergoes an evolutionary process. The
boundaries are plotted for the final model and a number of predecessor models,
using the first two principle components found by running PCA over the
embedding features of all the training  cats and  dogs. The heat map is
plotted by first building a mapping from PCA(2) to the embedding space. See
the flowchart in equation 1. The Yellow/Dark-purple corresponds to the
probability of CAT/DOG close to one. Model: VGG19. Optimizer: SGD-anneal-lr.

  * •

Our results show that the predecessor decision boundaries on the training set
are indicative of the final model’s generalization performance. Visually, the
models that are more self-centered, compact and have few overlapping samples
near the boundaries generalize better.

  * •

We found that deep networks decide only with the first principle component in
the end. The first principle component (out of hundreds of PCA components)
grows stronger and stronger during training. Eventually, the first component
itself supports a wholly 100% training accuracy. This indicates that the first
principle component is associated with overfitting.

  * •

There is a singularity phenomenon for optimizers. We observed that just a
little reduction in the rank of an auto-correlation matrix leads to a
significant generalization improvement when comparing deep learning
optimizers. For training the same model, the optimizers with a low rank of
this matrix generalize better than the optimizers with full-rank ones.

  * •

The explained variance of the first component is much larger for VGG19 than
for ResNet18 and DLA. This shows the skip connections (used in both ResNets
and DLA) have an effect of balancing the dominance of the first component to
reduce the variances in label prediction. Furthermore, VGG19’s auto-
correlation matrix is singular, while for ResNets and DLA, the matrix is full
rank. This shows the skip connections effectively use all the feature
dimensions and extract more linearly independent features.

There are other interesting observations in this paper. In particular, there
is a trade-off between cluster size and class splitting for the learning rate
of the SGD optimizer. Adam has similar variances in the first two principle
directions to SGD with small learning rates. This explains why Adam has an
inferior generalization to SGD with the annealed learning rate.

##  2 Decision Boundary Evolution

###  2.1 The Decision Boundary Complexity Disappears

Let us start with how Figure 1 is plotted. The VGG19 model [61] is trained
with 200 epochs of SGD and a batch size of 128. The learning rate starts with
0.1 and decays according to the Cosine rule [44]. This leads to models that
are very well trained. The training accuracy is 100% and the test accuracy is
always above 93% across many runs in our experiments. For VGG19, the CAT class
has the lowest test accuracy, about 87%, while the highest of the other
classes is about 96%. For ResNet18, CAT is 91.5% while the best of the other
classes is about 97%. DOG is the second most mis-classified class on the test
set. The mis-classification rates between CAT and DOG are the highest among
all the class pairs, e.g., see [12]. It thus makes sense to focus on the
boundary between CAT and DOG.

Given a final and well-trained model, Principle Component Analysis (PCA) [70,
1] is performed on the joint feature matrix of cats and dogs. The feature
matrix is generated using the embedding features from the last layer of VGG19.
We visualize the training cats and dogs according to their two major
components in the first plot of Figure 1. To understand how the decision
changes in this space, we need to know the likelihood of any point in this
space being CAT or DOG.

Let PCA(2) $\subset\mathcal{R}^{2}$ be the space of the first two principle
components. Denote a vector in PCA(2) by $x$. We generate a feature vector
$\psi(x)\in\mathcal{R}^{d}$ such that it is the mean of the nearest neighbors
of $x$ in PCA(2):

$\psi(x)=\frac{1}{n}\sum_{i=1}^{n}\phi(x_{i}(x)),\quad
x_{i}(x)\in\mbox{PCA(2)},$

where $\\{x_{i}(x)\\}$ are the nearest neighboring training samples of $x$ in
the PCA(2) space. Note that $\phi(\cdot)$ is an inverse mapping of the
dimension reduction by PCA. For the training samples $\\{x_{i}\\}$, their
embedding feature vectors can be queried from the networks. We take their
original feature vectors for the mapping of $\phi(\cdot)$, instead of the
results from the inverse transform by PCA which have large approximation
errors instead. In this way, we build a mapping $F$ that generalizes $\phi$.
In particular, $F:$ PCA(2) $\to\mathcal{R}^{d}$, which is able to map any $x$
in PCA(2) back to the embedding space.

The dimension $d$ is just that of the embedding space. For example, $d$ is 512
for VGG19. This gives a way of querying the neural networks model for any
point in PCA(2). This process can be summarized by the flow

$x\stackrel{{\scriptstyle F}}{{\to}}\psi(x)\to classifier(\psi(x)),$ (1)

where the last step is simply performed by a linear operation,
$\psi(x)W^{T}+b$. Here $W,b$ are the parameters of the last layer. The softmax
operation over CAT and DOG is also performed in the $classifier$ function. The
probability of CAT is thus computed for each point in PCA(2). These
probabilities generate a heat map, which is plotted in the same space with the
training samples. This finishes the process of generating the first plot of
Figure 1. The rest of the plots in the figure are produced in the same way for
some immature models during training. We call them the predecessor models in
the view that they are earlier states of the final model.

There are a few observations of this figure. For the final model (100%
training accuracy), there is no complex structure in the decision boundary.
Instead, the boundary is approximately linear. Going back in training, we can
see that there are some blurry regions in the decision boundaries of the
predecessor models. These regions correspond to where the decision is
ambiguous. Especially note that they are located near where the cats and dogs
overlap with each other. Even though the overall training accuracy is descent
(e.g., 99.48%), there are still a significant number of dogs in the CAT area,
and vice versa. The objects of the same classes become more and more centered
and their spread size has a decreasing trend. This is especially true when
training is near the end (e.g., over 99% training accuracy) in our
observation.

The first observation is quite surprising given what we know for machine
learning classifiers. Usually classifiers that overfit have complex boundary
structures. 333See
https://en.wikipedia.org/wiki/Overfitting#/media/File:Overfitting.svg for an
illustration of how overfitting contributes to the complexity of the decision
boundary in machine learning. How come the well-trained deep models do not
have such complexity in their decision boundaries? It did not make sense to us
in the beginning. We further plotted the cats and dogs in the decision space,
which is shown by Figure 9 (see Appendix 7.1). This confirms the decision
boundary undergoes an evolution (in both the PCA space and the decision
space), and finally the boundary has no complicated structures indeed.

###  2.2 Predecessor Boundaries are Indicative

We have shown so far that the final model has no complex decision boundary
structures but during training they do appear when training is near the end.
Why is it important? We found that the decision boundaries of the predecessor
models are indicative of the final model’s generalization performance.

Figure 2 shows the decision boundaries of CAT versus all the other classes in
the PCA(2) space. For each class pair, a joint feature matrix is formed by
querying the network’s embedding feature output using the training samples of
the two classes and PCA is performed afterwards. The model is the 99.87%
predecessor model, which is the same one as used in Figure 1 and Figure 9.
Previously [12] showed that CAT and DOG have the poorest generalization on the
test set. Here this figure shows the CAT-DOG decision boundary is the most
crowded. In particular, this plot shows that there are many cats near the
boundary (the more cats in an area the more solid is the blue color because
the color is plotted using alpha equal to 0.6 transparency). Especially note
that many cats cross into the area of DOG. The CAT-DOG plot in Figure 1 (the
last plot in the first row; dogs are in the foreground instead there) shows
there are a significant number of dogs that cross the boundary with CAT too.

All the other classes have some sort of boundary with CAT. In particular, CAT
has a significant number of samples near the boundary with BIRD (fluffy vs.
feather), DEER (four-leg), HORSE (four-leg), and FROG (pointy ears vs. eyes
atop). This explains their interference on the test set [12] hereby using the
training data.

Figure 2: Decision boundaries between CAT and all the other classes. This is
plotted using the 99.87%-model (in Figure 1) and all the training objects.
Model: VGG19. Optimizer: SGD-anneal-lr. See the text in Section 2.2 for
details.

The above method can be extended to compare the decision boundaries of the
classes in a 3D space. This is shown in Appendix 7.2.

###  2.3 Rethinking the Decision Boundary for DL

One myth in deep learning is why deep neural networks overfit with such a
level of over-parameterization but they still generalize so much better than
machine learning classifiers. This seems to contradict with the common belief
in machine learning that over-parameterized models are usually more complex
and they easily catch the noises in data, leading to a low bias but a high
variance and thus a poor generalization. This dilemma seems odd indeed. See
[62] for a similar feel.

Belkin et. al. [3] has a nice study on the bias-variance trade-off especially
for deep learning. They uncovered a double descent phenomenon for deep
learning. The classical bias-variance trade-off for machine learning is
described by the well-known “U” shape of the test risk in terms of the
capacity of the model. Belkin et. al.’s discovery is a double-“U” shape.
Following the first “U” shape, as the capacity of the model keeps growing into
over-parameterization, the test risk deceases again due to the combined effect
of a decreasing variance and a low bias. Somepalli et. al. [62] confirmed this
finding with a study of the width parameter of network layers. They also
studied in particular the transition between under- and over-parameterized
models. Their finding is that the “instabilities” in the decision boundary are
the main reason of double descent. Note, though, the decision boundary they
used is in the space of individual samples, which is different from ours. See
Section 5 for detailed discussions.

Our results indicate that the standard understanding of decision boundary in
machine learning explains deep neural networks with some differences. 444This
is implied by the double descent phenomenon too. Recall our results show that
the final decision boundary is approximately linear and there is no complex
boundary structures. Linear decision boundary is the simplest and it
generalizes well with good features. Perceptrons [46, 49], Support Vector
Machine [11, 65], Kernel methods [6, 58, 29] and Logistic Regression [47, 22]
all greatly advanced Artificial Intelligence and some of them are still widely
used in practice. Multi-layered Perceptrons [56], LSTM [17] and convolution
neural networks [35, 61, 24, 18] all use linear operation as an elementary
composition at layers. Before the recent success of deep reinforcement
learning, reinforcement learning algorithms with linear function approximation
have supported the field for decades [68, 67, 5, 36, 64, 66, 4], and it has
shown excellent generalization with sparse and CMAC encoded features [63].
Silver’s Ph.D thesis is built on Computer Go programs from linear value
function approximation [59]. Some program evaluates the Go game board from a
linear combination of millions of binary features [60]. There is nothing wrong
with linear methods across fields and in fact they generalize very well. Their
limitation is the requirement of good features.

For deep neural networks, the linearity of the final decision boundary is
surprising given the huge number of parameters. We think this is the most
fascinating part of deep neural networks: the excessive over-parameterization
does not lead to highly complex decision boundary structures. This finding
suggests that deep neural networks are structured in a way that enables
learning very good features who finally land in a linear space.

For the final model, the large margins between classes like CAT and DOG
indicate that all the classes are linearly separable in both the embedding
space and the decision space thanks to the deeply learned features. Thus the
decision boundary of the final well-trained model has a very simple linear
structure. This can be observed from the final model in Figure 1 and in Figure
9 for the CAT-DOG plot, and the 99.87% model for the CAT-PLANE, CAT-CAR and
CAT-SHIP in Figure 2. All the class pairs 555Other class pairs are not shown
because their boundaries look more clean. can be easily separated by a
straight line in the PCA(2) space for the corresponding model.

DL decision boundary != ML decision boundary: Overfitting in deep learning has
a very different effect on the decision boundary from machine learning.

Overfitting in machine learning leads to complex decision boundaries. As the
complexity grows to some level, the generalization of machine learning
classifiers deteriorates. However, our results show that the decision boundary
of the final well-trained model by deep learning is linear in the embedding
space. In our opinion this is one reason that deep neural networks generalize
much better than machine learning classifiers in many application areas. In
fact, “overfitting” in deep learning has a beneficial effect for
generalization as discussed in Section 3.2.

It is common to examine the final models for machine learning classifiers once
training finishes. However, the decision boundary of the final well-trained
deep models cannot explain class interference [12], e.g., why CAT and DOG
generalize much more poorly than the other classes even though they are also
linearly separable in the PCA(2) space. Our main result is that the
predecessor boundaries are indicative of the final model’s generalization. The
slowness in carving a clear separation between classes in training is strongly
correlated with the poor generalization between them at test time. We will dig
deeper into this slowness remark when studying the auto-correlation matrix in
Section 3.2.

##  3 Insights into Optimizer Generalization

###  3.1 From the Predecessor Boundary

Creating algorithms and models that generalize better is the heartbeat of deep
learning. We show that comparing the predecessor decision boundaries on the
training data gives us insights into their generalization performance. This
section compares the effects of optimizers on models, and the next section is
focused on the architectures.

We start with comparing models trained with different optimizers. SGD-anneal-
lr. The learning rate starts with an initial value of 0.1, and then decays
according to a Cosine rule. This is the optimizer used for the results
presented in Section 2. The momentum rate is 0.9, and the weight decay is
$0.0005$. The same momentum rate and weight decay are also used in the
following optimizers. For SGD-big-lr and SGD-small-lr, the learning rate is
0.01 and 0.0001, respectively. Adam [33]: with default parameters in PyTorch.
The model generating the results presented in this section is VGG19.

Figure 3:  This shows the effect of the learning rate for SGD, in shaping the
decision boundary between CAT and DOG. The Adam optimizer is also compared.
Model: VGG19. See the text in Section 3.1 for details.

Figure 3 shows that the effect of the learning rate on the decision boundary.
The overall test accuracy and the recall rates of CAT and DOG are shown in the
plots as well. All optimizers are trained 200 epochs.

First, let’s take a look at the plots using the training data in the first
column. Small learning rates are very good at splitting classes with clean
boundaries. However, the resulting cluster per class is much larger in size
than using the big learning rate. Note the different ranges in the $x,y$ axes.
Though, for the big learning rate, the splitting is poorer. The annealed
learning rate leads to much smaller clusters with a good splitting and an even
much better generalization. Note the large CAT areas behind the foreground DOG
in the second-row plots. It is well known that small learning rates generalize
poorly in deep learning. The reason was previously explained by the sharpness
of the minima [28, 32, 13, 31, 23, 12]. This is the first time uncovering the
effect of the learning rate on the cluster size.

Why is a big cluster bad? A big cluster due to small learning rates means the
variances of the training samples are high (along the first two principle
components). Intuitively, a big class cluster means that there are lots of
gaps among the training samples and on the edges. Such gaps are areas where
there are no training samples and thus the uncertainty is high there. At
testing time, the samples are likely to slip into these gaps, which incur high
variances in the label predictions. To validate this, we generate the same
plot using the test data, shown at the second column of the figure (except the
last row, which will be detailed later). For SGD-small-lr, there are many test
samples on and across the decision boundary, which is very different from the
plot on the training set. The color plot is generated using the transparency
parameter alpha equal to 0.2 for DOG (foreground) and 0.6 for CAT
(background). So intense red color means there are lots of dogs for the areas.
The big-lr optimized model, instead, has much fewer dogs (and cats) near the
test boundary. The SGD-anneal-lr optimizer further gathers most test cats and
dogs in two corners, leading to the highest recall rates for the test cats and
dogs as well as the overall test accuracy.

The Adam optimizer has an interesting boundary structure. In particular, the
spread range of the training cats (in blue) is small in the $x$-axis (the
first component direction), similar to the annealed learning rate. Note the
different ranges in the $x$-axis. However, the spread of both cats and dogs in
the $y$-axis and the spread of dogs in the $x$-axis are both much wider, in
fact, similar to SGD-small-lr. In addition, the boundaries of all the SGD
optimizers are roughly aligned with the axes. However, for Adam, the training
samples are instead rotated. There are also lots of overlapping samples near
the boundary for the test data. These observations help understand why the
final model by Adam is inferior to SGD-anneal-lr in generalization.

Finally, the last row shows two predecessor models of Adam. This shows that
the predecessor models on the training data are reflective of the decision
boundary on the test data for Adam optimizer too. First, as shown by the last
second row, the final model has very clear boundary structures on the training
data, which is quite different from on the test data. Second, the testing plot
is more similar to the training plot of the 99.5%-model than to that of the
final model. This means predecessor models give us more clues about
generalization than the final model, which is consistent with the case of the
SGD optimizer. This is another verification that the predecessor models are
indicative of generalization.

###  3.2 The Singularity of Optimizers

In Section 3.1, we plotted the predecessor boundaries for understanding the
generalization capabilities of SGD and Adam optimizers. This section presents
deeper insights into the generalization of the optimizers in terms of spectral
properties. This draws on the “slowness remark” at the end of Section 2.3.
Quantifying the spectral properties of the last layer gives us insights into
how fast the training has converged. It appears that, as we will show later,
the rate of convergence in training is strongly correlated with the
generalization performance.

Figure 4:  Optimizer profiling in terms of generalization and the spectrum of
singular values of the auto-correlation matrix. The colored text number is the
test accuracy of a VGG19 model trained by a corresponding optimizer. The
snapshot in the middle shows the first two singular values. See the text in
Section 3.2 for the description of the “singularity” phenomenon and other
observations.

Let a feature matrix be $\Phi\in\mathcal{R}^{n,d}$, where $n$ and $d$ are the
numbers of samples and embedding features, respectively. The squared singular
values of $\Phi$ are just the eigenvalues of matrix $A=\Phi^{T}\Phi$. This
matrix $A$ is fairly important. In fact, $A$ is often called the auto-
correlation matrix, which is often used for studying the convergence rate of
SGD with linear function approximation in neural networks (known as the
Widrow-Hoff or the Delta rule) [69] and signal processing (known as the least-
mean-squares filter) [43].

Optimizing the networks up to convergence reveals the generalization
capabilities of the optimizers because at convergence the data is also
overfit. Thus we cover all the optimizers (in torch.optim) that can be trained
to converge by learning rate annealing. Optimizers that can not be well
trained may be at a random state even training finishes. For example, SGD-big-
lr is in an oscillation state at the end of training. Taking the auto-
correlation matrix of such models thus compares different states of the
optimizers, which is not good and thus it was avoided by us at first.

We train the same model (VGG19) using different optimizers. Each optimizer is
applied with learning rate annealing in 200 epochs with a mini-batch size of
128. Figure 4 profiles ten optimizers in terms of the final test accuracy. For
each optimizer, we also plot the spectrum of the singular values of the auto-
correlation matrix for the CAT and DOG samples in the training set. The
majority of the optimizers are on the right side. RMSprop [27] and NAdam [14]
(combining Nesterov accelerated gradient [52] with Adam) are on the left side.
If we follow the green arrows from both sides, there is a trend of
generalization improving whilst the rank of this matrix gets close to some
intermediate number. (We will discuss the RAdam optimizer later).

There is an interesting singularity phenomenon. Reducing the rank just a
little (by Adadelta [72] and Adam [33]) leads to a significant generalization
improvement (91.9% and 92.6%) over the full-rank cases (ASGD and Adagrad, both
90.6% test accuracy). AdamW [45] and the SGD-anneal-lr further reduce the
rank, which leads to more generalization improvement. The RMSProp optimizer
reduces the rank to less than 10% of the feature dimension and yet the
generalization is descent. A large first singular value ($\sigma_{1}$) is a
strong indicator of poor generalization, e.g., see ASGD [55], Adagrad [15], as
shown by the small blue window that sits in the middle of the plot.

Figure 5:  Similar to Figure 4, except all the non-SGD optimizers are their
default settings without learning rate annealing. Every optimizer generalizes
worse than their counterpart in Figure 4. Note the optimizers in Figure 4 are
aided with learning rate annealing and they have higher training accuracies
(all above 99.9%). Thus this shows that all the (non-SGD) optimizers
generalize better when the data is overfit. The observations for Figure 4
follow similarly for the green arrow trend and the singularity of optimizers.

In general, this figure shows when comparing different optimizers on the same
model architecture, the rank of the auto-correlation matrix of the most
interfering class pair is indicative of the generalization performance, and so
is the $\sigma_{1}$. In fact, for SGD-anneal-lr, AdamW, NAdam and RMSprop, the
tailing singular values are all very close to zero. This suggests these
optimizers automatically filters out a significant number of noisy components
in the embedding space. This is interesting because in machine learning, it is
well known that dimension reduction captures major features in the data [8,
57, 16, 22, 42], which leads to models that are more robust with better
generalization.

We noted that the RAdam optimizer [41] is an exception. It has a full-rank
auto-correlation matrix and yet the generalization is very good (93%). We
think this is due to that the first and second singular values are of similar
magnitudes, and the second principle component helps with the generalization.
Out of the ten compared optimizers, RAdam is the only one that has large and
close first two singular values. Adamax [33] is also more balanced between the
first and second singular values than ASGD and Adagrad and generalizes better
than them.

We did run another experiment of training all the non-SGD optimizers without
learning rate annealing. None of them is able to train to 100% accuracy. Their
training accuracies are typically between 99.3% to 99.7%, except Adagrad
reaches 99.91%. This means all of them are not overfit comparing to SGD-lr-
anneal (100% training accuracy). Their test accuracy is shown in Figure 5.
Surprisingly, the overfitting SGD-lr-anneal model beats all these less
overfitting optimizers in generalization.

Note that Figure 4 has learning rate annealing applied to all the non-SGD
optimizers. They typically reach a training accuracy higher than 99.99%, which
is very much overfitting. Comparing the test accuracy numbers across the two
figures, we can see that for each of the non-SGD optimizers, the overfitting
implementation (Figure 4) has a better generalization than the less
overfitting one (Figure 5). This verifies that overfitting in deep learning is
distinctive — many optimizers generalize better when they are trained very
close to 100% accuracy. “Overfitting” in deep learning has a different effect
from machine learning, and perhaps we need a better name for it in deep
learning. See Section 2.3 for more discussions about this.

The relation of the test accuracy versus the rank of the auto-correlation
matrix (as indicated by the two arrow directions) in Figure 5 is similar to
that in Figure 4, except that there is randomness for the ordering of AdamW
and RAdam due to the models are not convergent. Without learning rate
annealing, Adam reduces the rank significantly. It generalizes better than
ASGD and Adagrad (both are full rank). However, it is still inferior to SGD-
lr-anneal, which has a larger rank. This suggests that there may be an
intermediate, optimal rank number, and it’s not like “the lower the rank, the
better generalization”.

Figure 6: Comparing the 99.5% predecessor decision boundaries of VGG19,
ResNet18 and DLA on the training data. For the VGG19 model, the samples are
less compact, while for the ResNet18 and DLA models, the samples are
distributed in a much more oval shape. The boundary complexity of ResNet18 is
lower than DLA.

##  4 Understanding ResNet

The Residual network (ResNet) is an extremely popular architecture for making
deep layered network models. At the time of writing, the ResNet paper [24]
received 136837 citations. The skip connection proposed in ResNet is widely
adopted in designing deep models for many applications nowadays. However, why
ResNets generalize well is still poorly understood. This section provides a
study into this question starting from the predecessor decision boundaries. In
particular, we compare VGG19, ResNet18 and DLA [71], optimized with SGD-
anneal-lr. DLA is included because it extends ResNets into a tree structured
hierarchy of layers with skip connections both within and across trees. We aim
to understand the effects of the skip connections on the decision boundary and
generalization.

Figure 6 shows the decision boundaries of VGG19, ResNet18 and DLA, plotted
using their predecessor model at the 99.5% training accuracy. The overall
accuracy and the CAT and DOG recall rates on the test set are shown in the
figure as well. The test accuracy of the final models is also summarized in
the table. In terms of the generalization performance, ResNet18 is better than
DLA, and DLA is better than VGG19. Both ResNet18 and DLA models have better
self-centerness in that the samples are more clustered, while for VGG19 the
samples form a less oval shape. The ResNet18 model has cleaner boundaries than
DLA.

Figure 7:  Evolution of the largest explained variances $\sigma_{1}^{2}$,
$\sigma_{2}^{2}$ and $\sigma_{3}^{2}$ for the training cats and dogs.
Optimizer: SGD-anneal-lr.

We were wondering why ResNets and DLA have nicer boundaries. How does the skip
connection help with the decision boundary in particular? Figure 7 shows the
evolution of the explained variance during training for VGG19, ResNet18 and
DLA. The plot confirms that the first component becomes very much dominant in
the end because the feature variances are mainly explained by $\sigma_{1}$ .
In particular, $\sigma_{1}$ grows larger and larger for each model in
training. Eventually the first component itself supports 100% training
accuracy for all the three models.

VGG19 has a much bigger $\sigma_{1}$ than ResNet18 and DLA. The growth curve
of $\sigma_{1}$ is also much more steep for VGG19. This shows that skip
connections have an effect of reducing the dominance of the first component.
Between ResNet18 and DLA, the explained variances are fairly close.

Figure 8: Spectral profiling of ResNet18 with different optimizers. One
difference from VGG19 (in Figure 4) is that here all the auto-correlation
matrices are full rank. Bringing the auto-correlation matrix close to
singularity in general still leads to better generalization. For example, SGD-
anneal-lr continues to perform the best due to that it brings the matrix near-
singular.

Figure 8 shows the spectral profile of ten optimizers for ResNet18. Note that
for VGG19, the majority of the optimizers have a singular auto-correlation
matrix, as shown in Figure 4. However, with ResNet18, this matrix is full rank
for most of the optimizers. This shows that the skip connections in ResNets
have an effect of extracting more linearly independent features. This
indicates that the feature dimension quota (512) is not effectively used by
VGG19; and many features are linearly dependent on each other. For example,
for SGD-anneal-lr, ResNet18’s smallest singular value is several orders larger
than VGG19. We checked the rank of the auto-correlation matrix. For VGG, it is
439 for all class pairs. For ResNet18, it is 512 (full rank) for all pairs.
Note this is reverse to the comparison of optimizers on the same model. In
that case, reducing the rank of the auto-correlation matrix tends to improve
the generalization of optimizers. However, for different architectures, it
appears models that extract more linearly independent features generalize
better.

About the ordering of the optimizers, in this full-rank case, though certain
optimizers (ADAMW and NADAM) in the rectangle are not exactly ordered in the
traversal direction of the upper green arrow in Figure 4, their test
accuracies are close. If we view the optimizers in the rectangle as a group,
the green arrow traversal ordering of the generalization still holds the same
as VGG19. RMSProp still outperforms ASGD and Adagrad with a much lower rank.
Thus in general, for optimizing the same model, the optimizers that have a
(near-)singular or low-rank auto-correlation matrix tend to generalize well.
The largest singular values may play a role too. For example, the zoom view in
Figure 8 shows that ASGD and Adagrad have the top-2 $\sigma_{1}$s and they
have the poorest generalization. The ordering of $\sigma_{1}$ is not the same
as the generalization performance though. Adagrad (with a larger $\sigma_{1}$)
actually generalizes better than ASGD. Note that Adamax is more balanced
between the first and second largest singular values than ASGD and Adagrad for
a better generalization. This was also observed for RAdam in the VGG19
experiment. In a summary, the generalization performance of optimizers is
strongly correlated with the spectral properties of this correlation matrix,
and a due evaluative measure is yet to be discovered.

##  5 Related Work

The popular approach in characterizing the decision boundary of deep neural
networks is by adversarial attacks, which applies some perturbation to input
images such that the label predictions are changed. This technique is known as
Generative Adversarial Networks (GAN) [19, 20, 50]. The connection between GAN
and decision boundary is that in order to generate adversarial samples, they
need to cross the decision boundary.

This fact has been used in a few works on the decision boundary of deep
classifiers, e.g., see [25, 30, 48, 39]. For example, Karimi et. al. [30]
generated adversarial samples, which are ambiguous to classifiers, i.e., with
equal probabilities of label predictions given an object. Mickisch et. al.
[48] used DeepFool [50] to generate adversarial samples and study the decision
boundary.

Guan and Loew [21] proposed a metric to evaluate the complexity of decision
boundary using adversarial samples that are generated near the boundary. The
key of this metric is to form a feature matrix of the adversarial samples, and
then compute the Shannon Entropy of its eigenvalues.

Lei et. al. [37] presented a theoretical analysis on the decision boundary
(DB) variability by ($\epsilon,\eta$)-data DB variability using a subset of
training data ($\eta\%$) for a reconstruction error of $\epsilon$. They also
studied the DB variability with respect to algorithms, such as training time,
sample sizes, and label noise ratios.

Somepalli et. al. [62] proposed a special decision boundary, which is defined
by plotting the predicted labels of synthetic samples in a 2D plane spanned by
three (real) basis images.

The decision boundary is useful beyond understanding the generalization of
deep neural networks. See Appendix 7.3 for other use cases.

##  6 Conclusion

The decision boundary structure is transient for deep models. Our major
findings are: (1) The tail of the boundary evolution is indicative of the
generalization performance of deep models. (2) The first component of deep
models tend to grow dominant in training and in the end, it suffices to fit
the data very well by itself. (3) Optimizers have a singularity phenomenon of
rank reduction in the auto-correlation matrix and improved generalization. (4)
The skip connections have the effects of balancing the dominance of the first
principle component and effectively using all feature dimensions.

##  7 Appendix

###  7.1 Decision Boundary in the Decision Space

The decision boundary evolution in the decision space is shown in Figure 9.
With the final model, the samples are not only separated well but the model is
very affirmative — almost all the dogs and cats are predicted with a
probability close to one. Thus studying the final model entails no decision
boundary structure, and at a moment it seemed impossible to us to use the
training data for studying the decision boundary. Indeed, Ortiz-Jimenez et.
al. [53] showed that “the decision boundaries of a neural networks can only
exist when the classifier is trained with some features that hold them
together”. It is common to define the decision boundary as the set of samples
for which the label prediction is equiprobable [48, 30]. The problem of
applying this definition is that there are no training samples that are
ambiguous.

Figure 9: The decision boundary vanishing phenomenon illustrated in the
decision space. The $x$-$y$ plane shows the predicted probabilities of CAT and
DOG for the training cats and dogs (5000 each class). The final classifier
clearly separates the two classes without ambiguity and there is no complex
decision boundary structure. However, the complexity does appear for the
predecessor models. Model: VGG19. Optimizer: SGD-anneal-lr.

###  7.2 Decision Boundary in 3D Space

Visualization in 3D is convenient because it allows to zoom and rotate when
inspecting the boundaries between classes. We form a feature matrix from the
training objects of a class triple. Then PCA is applied to give three major
components, which are the space to plot the samples. Figure 10 shows a few
triples. The complexity of the boundaries in terms of the overlapping of
training samples near the boundaries are consistent with the generalization
performance on the test set.

Figure 10: Decision boundaries in the PCA(3) space from the feature matrix of
the class triples in the training set. In particular, plot (1) shows planes
are clearly separated from both cats and dogs. (2) CAT-DOG boundary is more
crowded than CAT-FROG boundary, and CAT-FROG boundary is more complex than
DOG-FROG boundary. (3) Cars are clearly separated from cats and dogs. (4) CAR-
TRUCK is more complex than CAR-PLANE. (5) Cats are clearly separated from cars
and trucks. (6) SHIP-TRUCK boundary is more complex than SHIP-CAR boundary,
probably because SHIP is closer in size to TRUCK than CAR. These triples were
chosen to show because CAR, TRUCK, PLANE, and SHIP are all metallic bodies and
they interfere. These observations are consistent with the cross-class
generalization between classes on the test set [12].

###  7.3 Use Cases of Decision Boundary

Besides understanding the generalization of deep neural networks, there are
also other use cases for the decision boundary. For example, Heo et. al. [26]
used boundary samples from adversarial attacks to train a student network for
the purpose of knowledge distillation.

Alfarra et al. [2] found that the decision boundary of a simplest networks
(affine-relu-affine) is a polytope, and showed how to use this geometric
representation of the decision boundary for network pruning (i.e., reducing
number of parameter by sparse matrices) and adversarial attacks.

Choi et. al. [10] generated synthetic boundary supporting samples for the
purpose of model quantization without access to the original training data.

## References

  * [1] Hervé Abdi and Lynne J Williams.  Principal component analysis.  Wiley interdisciplinary reviews: computational statistics, 2(4):433–459, 2010.
  * [2] Motasem Alfarra, Adel Bibi, Hasan Hammoud, Mohamed Gaafar, and Bernard Ghanem.  On the decision boundaries of neural networks: A tropical geometry perspective, 2020.
  * [3] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal.  Reconciling modern machine-learning practice and the classical bias–variance trade-off.  Proceedings of the National Academy of Sciences, 116(32):15849–15854, jul 2019.
  * [4] Dimitri Bertsekas.  Dynamic programming and optimal control: Volume I, volume 1.  Athena scientific, 2012.
  * [5] Dimitri P Bertsekas and John N Tsitsiklis.  Neuro-dynamic programming.  Athena Scientific, 1996.
  * [6] Bernhard E Boser, Isabelle M Guyon, and Vladimir N Vapnik.  A training algorithm for optimal margin classifiers.  In Proceedings of the fifth annual workshop on Computational learning theory, pages 144–152, 1992.
  * [7] Xiaofeng Cao.  High-dimensional cluster boundary detection using directed markov tree.  Pattern Analysis and Applications, 24(1):35–47, 2021.
  * [8] Miguel A Carreira-Perpinán.  A review of dimension reduction techniques.  Department of Computer Science. University of Sheffield. Tech. Rep. CS-96-09, 9:1–69, 1997.
  * [9] Jinyin Chen, Zhen Wang, Haibin Zheng, Jun Xiao, and Zhaoyan Ming.  Roby: Evaluating the robustness of a deep model by its decision boundaries.  arXiv preprint arXiv:2012.10282, 2020.
  * [10] Kanghyun Choi, Deokki Hong, Noseong Park, Youngsok Kim, and Jinho Lee.  Qimera: Data-free quantization with synthetic boundary supporting samples.  In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
  * [11] Corinna Cortes and Vladimir Vapnik.  Support vector machine.  Machine learning, 20(3):273–297, 1995.
  * [12] Dongcui Diao, Hengshuai Yao, and Bei Jiang.  Class interference of deep neural networks, 2022.
  * [13] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio.  Sharp minima can generalize for deep nets.  CoRR, abs/1703.04933, 2017.
  * [14] Timothy Dozat.  Incorporating nesterov momentum into adam.  2016\.
  * [15] John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  J. Mach. Learn. Res., 12(null):2121–2159, July 2011.
  * [16] Imola K Fodor.  A survey of dimension reduction techniques.  Technical report, Lawrence Livermore National Lab., CA (US), 2002.
  * [17] Felix A Gers, Jürgen Schmidhuber, and Fred Cummins.  Learning to forget: Continual prediction with lstm.  Neural computation, 12(10):2451–2471, 2000.
  * [18] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio.  Deep learning, volume 1.  MIT Press, 2016.
  * [19] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks, 2014.
  * [20] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples, 2014.
  * [21] Shuyue Guan and Murray Loew.  Analysis of generalizability of deep neural networks based on the complexity of decision boundary.  In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA). IEEE, dec 2020.
  * [22] Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman.  The elements of statistical learning: data mining, inference, and prediction, volume 2.  Springer, 2009.
  * [23] Haowei He, Gao Huang, and Yang Yuan.  Asymmetric valleys: Beyond sharp and flat local minima.  CoRR, abs/1902.00744, 2019.
  * [24] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition, 2015.
  * [25] Warren He, Bo Li, and Dawn Song.  Decision boundary analysis of adversarial examples.  In International Conference on Learning Representations, 2018.
  * [26] Byeongho Heo, Minsik Lee, Sangdoo Yun, and Jin Young Choi.  Knowledge distillation with adversarial samples supporting decision boundary.  CoRR, abs/1805.05532, 2018.
  * [27] Geoffrey Hinton.  Lecture 6e rmsprop: Divide the gradient by a running average of its recent magnitude (pdf). p. 26., Retrieved September 2021.
  * [28] Sepp Hochreiter and Jürgen Schmidhuber.  Flat minima.  Neural computation, 9(1):1–42, 1997.
  * [29] Thomas Hofmann, Bernhard Schölkopf, and Alexander J Smola.  Kernel methods in machine learning.  The annals of statistics, 36(3):1171–1220, 2008.
  * [30] Hamid Karimi, Tyler Derr, and Jiliang Tang.  Characterizing the decision boundary of deep neural networks.  arXiv preprint arXiv:1912.11460, 2019.
  * [31] Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio.  Generalization in deep learning.  arXiv preprint arXiv:1710.05468, 2017.
  * [32] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang.  On large-batch training for deep learning: Generalization gap and sharp minima.  CoRR, abs/1609.04836, 2016.
  * [33] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization, 2017.
  * [34] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [35] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Communications of the ACM, 60(6):84–90, 2017.
  * [36] Michail G Lagoudakis and Ronald Parr.  Least-squares policy iteration.  The Journal of Machine Learning Research, 4:1107–1149, 2003.
  * [37] Shiye Lei, Fengxiang He, Yancheng Yuan, and Dacheng Tao.  Understanding deep learning via decision boundary, 2022.
  * [38] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein.  Visualizing the loss landscape of neural nets.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * [39] Qian Li, Yong Qi, Qingyuan Hu, Saiyu Qi, Yun Lin, and Jin Song Dong.  Adversarial adaptive neighborhood with feature importance-aware convex interpolation.  IEEE Transactions on Information Forensics and Security, 16:2447–2460, 2020.
  * [40] Aishan Liu, Xianglong Liu, Jun Guo, Jiakai Wang, Yuqing Ma, Ze Zhao, Xinghai Gao, and Gang Xiao.  A comprehensive evaluation framework for deep model robustness.  arXiv preprint arXiv:2101.09617, 2021.
  * [41] Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han.  On the variance of the adaptive learning rate and beyond.  CoRR, abs/1908.03265, 2019.
  * [42] Raymond Liu and Duncan F Gillies.  Overfitting in linear feature extraction for classification of high-dimensional image data.  Pattern Recognition, 53:73–86, 2016.
  * [43] Lennart Ljung.  System identification.  In Signal analysis and prediction, pages 163–173. Springer, 1998\.
  * [44] Ilya Loshchilov and Frank Hutter.  Sgdr: Stochastic gradient descent with warm restarts, 2016.
  * [45] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization, 2017.
  * [46] Warren S McCulloch and Walter Pitts.  A logical calculus of the ideas immanent in nervous activity.  The bulletin of mathematical biophysics, 5(4):115–133, 1943.
  * [47] Scott Menard.  Applied logistic regression analysis.  Number 106. Sage, 2002.
  * [48] David Mickisch, Felix Assion, Florens Greßner, Wiebke Günther, and Mariele Motta.  Understanding the decision boundary of deep neural networks: An empirical study.  CoRR, abs/2002.01810, 2020.
  * [49] Marvin Minsky and Seymour A Papert.  Perceptrons, Reissue of the 1988 Expanded Edition with a new foreword by Léon Bottou: An Introduction to Computational Geometry.  MIT press, 2017.
  * [50] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard.  Deepfool: a simple and accurate method to fool deep neural networks, 2015\.
  * [51] Adhyyan Narang.  Overparameterized classification problems: How many support vectors do I have, and do increasing margins always bode well for generalization? PhD thesis, Department of Electrical Engineering and Computer Sciences, University of …, 2020.
  * [52] Y. Nesterov.  Introductory lectures on convex optimization - a basic course.  In Applied Optimization, 2004.
  * [53] Guillermo Ortiz-Jimenez, Apostolos Modas, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard.  Hold me tight! influence of discriminative features on deep network boundaries, 2020.
  * [54] Mohamed Ouriha, Youssef El Habouz, and Omar El Mansouri.  Decision boundary to improve the sensitivity of deep neural networks models.  In International Conference on Business Intelligence, pages 50–60. Springer, 2022.
  * [55] Boris T Polyak and Anatoli B Juditsky.  Acceleration of stochastic approximation by averaging.  SIAM journal on control and optimization, 30(4):838–855, 1992.
  * [56] David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams.  Learning representations by back-propagating errors.  nature, 323(6088):533–536, 1986.
  * [57] Christian Schittenkopf, Gustavo Deco, and Wilfried Brauer.  Two strategies to avoid overfitting in feedforward networks.  Neural networks, 10(3):505–516, 1997.
  * [58] John Shawe-Taylor, Nello Cristianini, et al.  Kernel methods for pattern analysis.  Cambridge university press, 2004.
  * [59] David Silver.  Reinforcement learning and simulation-based search in computer go.  2009\.
  * [60] David Silver, Richard S Sutton, and Martin Müller.  Reinforcement learning of local shape in the game of go.  In IJCAI, volume 7, pages 1053–1058, 2007.
  * [61] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In International Conference on Learning Representations, 2015.
  * [62] Gowthami Somepalli, Liam Fowl, Arpit Bansal, Ping Yeh-Chiang, Yehuda Dar, Richard Baraniuk, Micah Goldblum, and Tom Goldstein.  Can neural nets learn the same model twice? investigating reproducibility and double descent from the decision boundary perspective.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13699–13708, 2022.
  * [63] Richard S Sutton.  Generalization in reinforcement learning: Successful examples using sparse coarse coding.  In D. Touretzky, M.C. Mozer, and M. Hasselmo, editors, Advances in Neural Information Processing Systems, volume 8. MIT Press, 1995.
  * [64] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  MIT press, 2nd edition, 2018.
  * [65] Johan AK Suykens and Joos Vandewalle.  Least squares support vector machine classifiers.  Neural processing letters, 9(3):293–300, 1999.
  * [66] Csaba Szepesvári.  Algorithms for reinforcement learning.  Synthesis lectures on artificial intelligence and machine learning, 4(1):1–103, 2010.
  * [67] J.N. Tsitsiklis and B. Van Roy.  An analysis of temporal-difference learning with function approximation.  IEEE Transactions on Automatic Control, 42(5):674–690, 1997.
  * [68] Christopher JCH Watkins and Peter Dayan.  Q-learning.  Machine learning, 8(3):279–292, 1992.
  * [69] Bernard Widrow and Marcian E Hoff.  Adaptive switching circuits.  Technical report, Stanford Univ Ca Stanford Electronics Labs, 1960.
  * [70] Svante Wold, Kim Esbensen, and Paul Geladi.  Principal component analysis.  Chemometrics and intelligent laboratory systems, 2(1-3):37–52, 1987\.
  * [71] Fisher Yu, Dequan Wang, Evan Shelhamer, and Trevor Darrell.  Deep layer aggregation, 2017.
  * [72] Matthew D. Zeiler.  Adadelta: An adaptive learning rate method, 2012.