# Representations of Language Varieties Are Reliable
Given Corpus Similarity Measures

Jonathan Dunn
Department of Linguistics
University of Canterbury
<EMAIL_ADDRESS>
###### Abstract

This paper measures similarity both within and between 84 language varieties
across nine languages. These corpora are drawn from digital sources (the web
and tweets), allowing us to evaluate whether such geo-referenced corpora are
reliable for modelling linguistic variation. The basic idea is that, if each
source adequately represents a single underlying language variety, then the
similarity between these sources should be stable across all languages and
countries. The paper shows that there is a consistent agreement between these
sources using frequency-based corpus similarity measures. This provides
further evidence that digital geo-referenced corpora consistently represent
local language varieties.

##  1 Introduction

This paper evaluates whether digital geo-referenced corpora are consistent
across registers (web data vs. tweets). This question is a part of validating
the use of digital data to represent local language usage in specific places
around the world. In other words, recent work has taken samples of varieties
like New Zealand English from social media (Twitter) and the web (Common
Crawl). But how closely do these two sources actually match up, both with one
another and with New Zealand English in offline settings? The first question
is about the reliability of geo-referenced corpora and the second is about
their validity. The question of reliability and validity becomes important
when we use geo-located digital corpora to model both lexical variation
Eisenstein et al. (2010); Grieve et al. (2011); Kondor et al. (2013);
Eisenstein et al. (2014); Donoso and Sánchez (2017) and the difference between
language varieties Lui et al. (2014); Gamallo et al. (2016); Dunn (2018,
2019b); Rangel et al. (2020); Zampieri et al. (2020). These computational
approaches are quickly refining our understanding of language variation and
change. At the same time, though, both of these lines of work depend on large,
reliable sources of geographic language data. This paper evaluates these data
sources across nine languages and 84 language varieties in order to determine
how reliable they are. The data can be explored further alongside demographic
information at earthLings.io.

##  2 Reliability and Validity

If digital geo-referenced corpora are reliable, then both web corpora and
Twitter corpora from one location should exhibit similar patterns (as
quantified by corpus similarity measures). In other words, no matter how many
samples we observe of tweets or web pages from New Zealand, we expect a
reliable similarity among samples. If digital corpora are not reliable, then
it follows that they are not suitable for modelling linguistic variation. This
is because a model of a variety like New Zealand English would depend on
arbitrary differences in the specific samples being obeserved.

The further question is whether digital geo-referenced corpora are valid
representations of an underlying population. In other words, if we observed
lexical choices by interviewing speakers in New Zealand, we would expect those
same lexical choices to be observed in tweets. If these digital corpora are
not reliable, then they are also not valid. But reliability itself does not
guarantee a valid representation of the underlying population Nunnally (1994).
For example, it is possible that register differences lead to different
linguistic behaviour, so that lexical choices in written language may never
correspond to lexical choices in spoken language. If this were the case, then
it would of course never be possible to generalize from patterns in written
language to patterns in spoken language.

##  3 Related Work on Validity

There have been three distinct approaches to the broader problem of validating
digital representations of dialects and varieties. First, a linguistic
approach starts with survey-based dialect studies as a ground-truth. These
dialect surveys provide a point of comparison for an underlying variety like
American English, one which does not rely on digital language data at all.
This line of work has shown that there is a strong correspondence between
traditional studies of dialectal variation and both tweets Grieve et al.
(2019) and web-crawled corpora Cook and Brinton (2017). This family of results
shows that, if we accept dialect surveys as a gold-standard, there is
significant justification for substituting digital corpora (like tweets) for
much more expensive survey-based data. The correspondence between dialect
surveys and tweets, however, is far from perfect. This raises a question: when
is the relationship strong enough to justify a purely digital approach to
language varieties?

A second demographic approach compares digital corpora with ground-truth
census data in order to triangulate the similarity between represented
populations. For example, given a corpus of tweets from around the world, the
geographic density should correspond to some degree with population density
Graham et al. (2014); Dunn (2020). Otherwise, some locations would be over-
represented in the data, thus given more influence. In the same way, a corpus
drawn equally from around the world should represent local language use that
corresponds to some degree with a census-based study of what languages are
used in each country Dunn and Adams (2019). The basic idea here is that geo-
referenced corpora which correspond with census data are more likely to
represent actual local populations, rather than representing non-local
populations like tourists or short-term workers Dunn et al. (2020). This line
of work has also shown a strong relationship between demographics and digital
corpora. But, again, when is that relationship strong enough to justify using
geo-referenced corpora alone to model language varieties?

A third computational approach leverages some model of language variation to
measure relationships between different partitions of linguistic data. For
example, recent work has measured the linguistic similarity between varieties
of English, like New Zealand English vs. Australian English Dunn (2019a);
Szmrecsanyi et al. (2019). When expanded across aligned corpora, these models
can be used to determine if there is a consistent pattern of variation: does
New Zealand English have the same distinctive lexical choices on the web that
it has in tweets? The basic idea is that if two sources of data (the web and
tweets) accurately represent New Zealand English, both should produce similar
models of that variety. On the one hand, even if the models agree
(reliability) it remains possible that both sources of data are distorting the
underlying population (validity). But it is more likely that such reliability
confirms the validity of a purely digital approach to language varieties. This
kind of work has also been systematically evaluated across different
similarity measures, with a ground-truth derived from studies in perceptual
dialectology Heeringa et al. (2002, 2006).

This paper expands on these three approaches by systematically experimenting
with the reliability of geo-referenced data (i) across register boundaries,
(ii) across geographic boundaries, and (iii) across language boundaries. The
more reliable the relationship between web data and tweets, the more
confidence we can have in computational models of language varieties and
linguistic variation.

##  4 Measuring Corpus Similarity

The approach in this paper is to measure where digital geo-located corpora
diverge from one another, across languages and across countries. Unlike
previous work, this does not rely on a comparison with an external ground-
truth (i.e., dialect surveys, census data, or pre-trained models of
variation). First, we collect geo-referenced web data and tweets across 84
varieties of nine languages. Each variety is represented using aligned corpora
drawn from web pages and from tweets. These representations are distributed
across many individual samples of 1 million words each.

This design allows us to make a direct comparison between samples that have
been drawn from the same varieties. Thus, for example, we can measure the
similarity of a single variety across register boundaries: New Zealand English
on the web and in tweets. And we can also measure the similarity between
varieties within a single register: New Zealand English and Australian English
in tweets. This is related, for example, to the problem of measuring
similarity within a single language variety over time Pichel Campos et al.
(2018). The ultimate goal of the experiments described in this paper is to
examine the reliability of digital representations of language varieties.

Lang. | Varieties | Samples tw | Samples cc
---|---|---|---
ara | 13 | 185 | 150
deu | 7 | 76 | 124
eng | 14 | 259 | 262
fra | 15 | 186 | 283
ind | 3 | 45 | 56
nld | 2 | 43 | 46
por | 4 | 53 | 71
rus | 9 | 99 | 216
spa | 17 | 336 | 322
Total | 84 | 1,282 | 1,530
Table 1: Varieties and Samples by Language

We start by drawing on measures of corpus similarity, which calculate the
distance between two corpora Kilgarriff (2001); Kilgarriff and Rose (1998).
Previous work has shown that frequency-based measures out-perform more
sophisticated approaches that make use of language models or topic models
Fothergill et al. (2016). The highest-performing frequency models work by
ranking word or character frequencies and using either the Spearman $rho$ or
the $\chi_{2}$ measure between frequency ranks. The $\chi_{2}$ performs
slightly better for samples with the same number of features, but the Spearman
$rho$ has more flexibility for dealing with unattested features while
experiencing only a minimal impact on performance Kilgarriff (2001).

Based on these previous evaluations, we rely on two variants of the Spearman
frequency-based similarity measure: one variant uses unigram frequencies and
one variant uses character trigram frequencies (motivated by related work on
language identification). The experiments in this paper are performed using
equal-sized samples, where each sample contains 1 million words. These two
measures are labelled as Word and Char in the tables that follow. The
inventory of features (i.e., words or character trigrams) consists of the most
common 100k features across all samples from a given language. A higher
Spearman value indicates a higher similarity between samples.

In the ideal case, there would be a consistent level of similarity across
samples representing all languages and all countries. In other words, we would
see a similar impact of register variation (web vs. tweets) regardless of
which specific language variety is involved. A result like this would suggest
that both sources of geo-located language are representing a single underlying
linguistic object (i.e., offline New Zealand English).

The alternate outcome is that there is an arbitrary fluctuation between web
usage and tweet usage. For example, it could be the case that New Zealand
English is very similar on the web and in tweets, but Australian English shows
a wide divergence between the two, with different lexical choices being
represented. If this were the case, the digital representation of New Zealand
English would be more reliable than the representation of Australian English.
This work is related to previous explorations of noise in social media Baldwin
et al. (2013), but with a focus on the interaction between geographic
variation and register variation. The question is: how consistent are language
varieties when sampled from different digital sources?

##  5 Data and Experimental Design

The experiments draw on existing geographic corpora from the web (ultimately
derived from the Common Crawl data) and from tweets Dunn and Adams (2020);
Dunn (2020). Both of these data sources are aligned by language and country:
for example, each variety like Cuban Spanish or New Zealand English is present
from both sources of data. The experiments include nine languages: Arabic
(ara), German (deu), English (eng), French (fra), Indonesian (ind), Dutch
(nld), Portuguese (por), Russian (rus), and Spanish (spa). These languages
each have a different number of varieties, as shown in Table 1, ranging from
just 2 (nld) to 17 (spa). In this table, Varieties refers to the number of
national dialects or varieties (like New Zealand English) that are
represented. Samples refers to the total number of observations for that
language, across all varieties. Finally, TW refers to tweets and CC to web
data.

Each sample contains 1 million words. Some varieties are very well
represented, with hundreds of samples (and thus hundreds of millions of
words); but other varieties are less well represented, with only a few
samples. We restrict the maximum number of samples per variety per register to
20. As shown in Table 2 for Spanish, there is variation in the number of
samples per data source. For example, some countries like Mexico have many
samples for both tweets and web data (20 and 20, respectively, because of the
cap). But other countries are imbalanced: for example, the Dominican Republic
has 20 samples from the web but only 4 drawn from tweets. Overall, these
experiments are based on approximately 1.2 billion words from tweets and 1.5
billion words from web corpora.

Country | Samples tw | Samples cc
---|---|---
Argentina | 20 | 16
Bolivia | 20 | 16
Chile | 20 | 20
Colombia | 20 | 20
Costa Rica | 20 | 20
Cuba | 20 | 20
Dom. Rep. | 4 | 20
Ecuador | 20 | 20
El Salvador | 20 | 20
Guatemala | 20 | 20
Honduras | 20 | 20
Mexico | 20 | 20
Paraguay | 20 | 2
Peru | 20 | 20
Spain | 20 | 20
United States | 12 | 20
Uruguay | 20 | 19
Venezuela | 20 | 9
Table 2: Number of Samples by Variety for Spanish

The question behind the experiments in this paper is whether there is a
consistent relationship between corpora drawn from the web and from tweets,
across many different language varieties. If there is a significantly stable
relationship, this increases our confidence that digital corpora accurately
represent the underlying geographic language varieties. In other words, the
stable relationship would be a result of two different sources that are
measuring the same real-world entity (e.g., a single language variety). But,
in contexts where this relationship breaks down, we can have less confidence
in the validity of digital corpora for modelling language varieties. We
present five sets of experiments, each focused on a specific part of this
problem.

The first experiment (Section 6), focuses on the internal consistency of each
variety-register combination: given similarity relationships between many
samples of Mexican Spanish tweets, how stable is the internal similarity
between samples? The basic idea is that any variety-register combination with
a low internal similarity is less reliable.

The second experiment (Section 7) evaluates the accuracy of both word-
frequency and character-frequency measures. The idea in these experiments is
to validate the underlying similarity measure to ensure that the later
experiments are also valid.

The third experiment (Section 8) is the main part of the paper: measuring the
difference between registers (web vs. tweets) for each language variety. Our
hypothesis is that only a significantly stable relationship supports the use
of digital corpora for representing language varieties.

The fourth experiment (Section 9) looks for differing results by language. It
may be the case, for instance, that varieties of English and Spanish are
adequately represented by digital corpora, but not varieties of Dutch.

The fifth experiment (Section 10) creates an average frequency vector for each
language across all varieties and registers. This average is used to situate
each national variety according to its relative distance from that center,
creating a rank of which varieties are the most divergent or the most unique.
There is one rank for each register and the experiment tests where there is a
significant relationship between ranks for each language. Taken together, this
set of experiments is designed to evaluate the suitability of digital geo-
referenced corpora for representing language varieties, building on the
validation work discussed in Section 3.

##  6 Experiment 1: Consistency Across Samples

The first question is the degree to which each language variety-register
combination (e.g., Mexican Spanish tweets) is internally consistent. We take
50 observations of unique pairs of samples, each representing the same
variety-register combination. Then we measure the similarity between the two
samples and look at the distribution of similarity values for each variety-
register combination. Varieties with a high average similarity are more
internally consistent than varieties with a low average similarity.

The results are shown in Table 3 by language, divided into Word and Character
features as discussed in Section 4. Data from tweets (TW) is shown on the left
and from the web (CC for Common Crawl) is shown on the right. These measures
show the stability by language, where each value is drawn from approximately
50 random comparisons between different samples representing the same context.
As throughout this paper, higher values indicate higher similarity (here,
meaning more internal similarity).

First, this table shows that character representations are more consistent
across languages, although the accuracy of each type of feature is not
evaluated until Section 7. In other words, the average internal similarity for
tweets ranges from 0.82 to 0.85 for character features but from 0.63 to 0.71
for word features. At the same time, a smaller range of variation also could
mean that character features are less able to discriminate between varieties.

Language | TW | TW | CC | CC
---|---|---|---|---
| Word | Char | Word | Char
ara | 0.71 | 0.84 | 0.70 | 0.76
deu | 0.66 | 0.85 | 0.57 | 0.72
eng | 0.68 | 0.83 | 0.63 | 0.71
fra | 0.68 | 0.82 | 0.64 | 0.72
ind | 0.71 | 0.83 | 0.64 | 0.73
nld | 0.63 | 0.82 | 0.53 | 0.71
por | 0.67 | 0.82 | 0.64 | 0.72
rus | 0.70 | 0.83 | 0.60 | 0.71
spa | 0.65 | 0.82 | 0.61 | 0.71
Table 3: Consistency Within Language Varieties

Second, this table shows that tweets from a particular variety have a higher
internal similarity than web data from that variety. This is true for all
languages and for both word and character features. While this experiment does
not indicate why this is the case, we can offer some potential reasons: (i) it
could be that tweets are more similar in terms of discourse functions, while
web data represents a range of different communication purposes; (ii) it could
be that tweets represent a more restricted subset of local populations (e.g.,
Twitter users), which have been shown to be more influenced by demographic
attributes like per capita GDP.

Third, all of these Spearman correlations are highly significant, which means
that there is at least a strong relationship between representations of each
variety drawn from the web and from tweets. At the same time, as discussed in
Section 3 in regards to alternate methods of evaluation, it is not clear what
threshold for similarity is sufficient. This question is what the remainder of
the experiments attempt to address.

##  7 Experiment 2: Word vs Character Features

The next question is two-fold: First, which frequency-based measure of
similarity is more reliable in this setting: words or characters? Previous
work on corpus comparison has largely conducted evaluations using only English
data and has not included multiple language varieties. Second, regardless of
which feature is best, how reliable are the measures? Because the samples are
each 1 million words, this is a significantly easier problem than identifying
varieties in small samples.

In this experiment we look at the average accuracy for each language for each
type of feature. For each variety, we take 100 pairs that come from the same
register (tweets against tweets) and 100 pairs that come from different
registers (tweets against web pages). If the similarity for a pair is closest
to the average similarity for same-register pairs, we predict that each sample
comes from the same register (and so on for cross-register pairs). This is a
simple framework for evaluating each measure: the percent of correct
predictions. This is similar to previous evaluation methods for corpus
similarity measures Kilgarriff (2001).

Language | Word | Character
---|---|---
ara | 99.0% | 99.1%
deu | 95.7% | 98.9%
eng | 93.9% | 98.9%
fra | 98.1% | 99.8%
ind | 100.0% | 100.0%
nld | 94.3% | 100.0%
por | 98.4% | 96.3%
rus | 94.7% | 98.7%
spa | 96.7% | 97.5%
Table 4: Feature Evaluation by Accuracy

The results, shown in Table 4, have a high accuracy in general, as we expect
given that each sample is 1 million words. The important question is which
similarity measure has the highest accuracy: in every case except for
Portuguese the character features are more accurate. For simplicity, we report
only the character-based measure in the remainder of the experiments. This
experiment also provides a ground-truth confirmation that the measures are
meaningful on this data.

Figure 1: Cross-Register Similarity (Arabic) Figure 2: Cross-Register
Similarity (German) Figure 3: Cross-Register Similarity (English)

##  8 Experiment 3: Differences in Register

Now that we have established that there is a significant relationship between
registers across all varieties and that the character-based measure is
generally more accurate, we proceed to the main question: how robust is the
relationship between registers? There are two competing hypotheses here:
First, it could be the case that one or both sources of digital data only
poorly represent a given language variety. In this case, there would be wide
fluctuations in similarity values across varieties and across languages
(because the similarity would not be driven by shared populations and shared
linguistic patterns). Second, it could be the case that both sources of
digital data consistently represent a given language variety. Because of
register-based variation, the similarity between sources may not be perfect;
but it should be consistent.

We use the samples described above to create a population of cross-register
pairs, where each pair consists of two samples from the same variety. For
instance, we take 100 random comparisons of Mexican Spanish with other Mexican
Spanish samples from a different source (i.e., web vs tweets). This provides a
population of between-register scores for each language variety. If the
distance between registers is consistent across all contexts, this is evidence
for the second hypothesis: that both sources of data are related
representations of a single underlying language variety.

The first set of results, for Arabic, is shown in Figure 1 as a violin plot of
the distribution of cross-register similarity scores for each country. In the
case of Arabic, the average similarity by country ranges from 0.43 (Iraq, IQ)
to 0.53 (United States, US). Note the combination here of native varieties and
non-native or immigrant varieties. This violin plot shows the distribution of
scores, most of which are contained within a tight central band (i.e., are
relatively consistent across varieties). Arabic in Iran (IR) and Morocco (MA)
have broader distributions, showing that there is more variety within samples
from these countries. The US, a non-native variety, has outliers, resulting in
thin lines on either side of the plot. There are also differing numbers of
samples by country, so that Egypt (EG) and Tunisia (TN) are located in the
center but, with few samples, have a small footprint.

Moving on to German, in Figure 2, we see a similar pattern: the distribution
(with somewhat higher scores) is centered within the same values across
countries. What matters for the hypothesis in this paper is the range of
values for cross-register similarity, here with averages ranging from 0.52
(Czechia, CZ) to 0.56 (Germany, DE). This constrained range indicates that
there is a stable relationship between digital sources for these varieties.

Figure 4: Cross-Register Similarity (French)

We next evaluate varieties of English (Figure 3) and French (Figure 4). Both
of these languages are more widely used in digital contexts, thus having a
larger number of varieties. English ranges from an average of 0.43 (Hong Kong,
HK) to 0.51 (Nigeria, NG). French ranges from an average of 0.42 (Algeria, or
DZ) to 0.52 (Gabon, GA, and the Democratic Republic of Congo, CD). In both
languages we see a somewhat wider range, with outliers like Hong Kong English
or Algerian and Tunisian French; but still the gap between registers remains
largely consistent for most varieties.

Figure 5: Cross-Register Similarity (Russian)

The results for Russian (Figure 5) and Spanish (Figure 6) continue the same
pattern of relative consistency. The figures for Dutch, Indonesian, and
Portuguese are excluded because they each have a small number of varieties
that largely overlap. The figures for Russian and Spanish show greater
consistency across countries, although Russian does have a few outliers for
each country (i.e., the narrow tails). Russian averages range from 0.49
(Ukraine, UA) to 0.52 (Estonia, EE). Spanish shows a slightly larger range of
averages, from 0.48 (Argentina, AR) to 0.55 (El Salvador, ES). Once again,
however, the relationship between registers remains stable.

Figure 6: Cross-Register Similarity (Spanish) Language | TW | TW | CC | CC
---|---|---|---|---
| Same Varieties | Different Varieties | Same Varieties | Different Varieties
ara | 0.84 | 0.81 | 0.76 | 0.67
deu | 0.85 | 0.83 | 0.72 | 0.68
eng | 0.83 | 0.80 | 0.71 | 0.66
fra | 0.82 | 0.77 | 0.72 | 0.66
ind | 0.83 | 0.80 | 0.73 | 0.68
nld | 0.82 | 0.80 | 0.71 | 0.69
por | 0.82 | 0.80 | 0.72 | 0.64
rus | 0.83 | 0.80 | 0.71 | 0.68
spa | 0.82 | 0.80 | 0.71 | 0.67
Table 5: Variation Within and Across Countries

The results in this section suggest that both web data and tweets provide
reliable representations for a large number of language varieties, regardless
of the specific language or country involved. The distance between samples
from each source is stable across both categories (language and country). This
pattern is what we expect if both sources adequately represent the underlying
language variety. This reliability converges with the previous work discussed
in Section 3 to suggest that digital geo-referenced corpora do in fact
represent local language use. As with previous evaluations, however, it is
difficult to define a threshold for reliability.

##  9 Experiment 4: Differences by Language

Our next set of experiments further explores the interaction between dialect
variation (e.g., New Zealand vs. Australian English) and register variation
(e.g., web data vs. tweets). As we compare a large number of samples for each
language, how much of the variation comes from register-effects and how much
from geographic-effects? The experiments shown in Table 5 compare the
similarity of samples drawn from the same variety (thus controlling for
geographic effects) with the similarity of samples drawn from different
varieties (thus adding geographic effects). The additional similarity of
within-variety comparisons can be attributed to geographic variation.

For example, Arabic tweets have 0.03 increased similarity when compared within
varieties instead of between varieties. The difference for web data is larger
in most cases. We test for significance using a t-test with 50 observed pairs
in each condition for each language. In each case there is a highly
significant difference. This confirms that we are observing geographic
variation across varieties in addition to the register variation that is
quantified in the previous section.

This geographic variation is a secondary finding, however, in the sense that
much more precise methods of modelling geographic variation exist. The purpose
here is simply to confirm that each language shows a significant geographic
effect given this measure applied to these sources of data.

##  10 Experiment 5: Relations Between Varieties

Our final experiment looks at relationships between national varieties or
dialects. A final piece of evidence comes from ranks of varieties: if both the
web and tweets make Singapore English most similar to Malaysian English, this
confirms the reliability digital sources of geo-referenced data.

First, we create an average representation across all samples for a given
language using the mean feature frequency. Second, we estimate the average
feature frequency for each variety-register combination (like Mexican Spanish
tweets). Third, we compare the similarity between (i) the language-based mean
feature value and (ii) the average for a specific variety (like Mexican
Spanish tweets).

This provides a rank of distance from the average frequency for each variety.
For example, what is the most unusual variety of English? We do this for both
registers, TW and CC in Table 6. The question is, do these two sources of data
agree about relationships between dialects as well as between registers? The
Spearman rank correlations are used to measure how well each register ranks
varieties in the same manner.

Figure 7: Average cross-domain similarity by country.

The results for all languages taken together is highly significant, with a
correlation of 0.453. Taken individually, some languages are also significant:
German, French, Portuguese, and Russian. Given the small number of
observations when constrained to individual languages, the lack of
significance at that level is not particularly important. What this shows,
however, is that even a simple similarity measure can produce, overall,
significantly related ranks of varieties. The importance is not the specific
ranks, because we know that better methods for modelling language varieties
exist. The importance is that we have additional evidence for stability in the
relationship between registers and varieties. This is precisely what we would
see if both sources of digital data were valid representations of a single
underlying linguistic object.

Language | Spearman $rho$ | Significance
---|---|---
All | 0.453 | *
ara | 0.291 | NS
deu | 0.785 | *
eng | 0.428 | NS
fra | 0.561 | *
ind | 0.399 | NS
nld | 0.799 | NS
por | 0.899 | *
rus | 0.797 | *
spa | 0.051 | NS
Table 6: Correlation between rankings by register

##  11 Geographic Trends

The focus so far has been on varieties of languages. A different way of
framing the question of register similarity is by country: is there a
geographic pattern to where the web and tweets are more or less similar? Here
we take cross-register similarity values as described above in Section 8. When
we bring all languages together, these experiments represent 66 countries. Of
these, 10 are represented by two or more languages; the map in Figure 7
averages the values by country to show geographic trends in cross-register
similarity.

When we focus on countries, the average cross-register similarity value is
0.855. Most countries fall with the range of 0.80 to 0.89 (62 out of 66). Only
two countries fall below 0.80, meaning that they show a low agreement between
registers: Bahrain and Brazil. And only two countries are above 0.90, meaning
that they show a higher agreement between registers: Nigeria and New Zealand.
Note that the lower value for Brazil likely results from the lower accuracy of
character-based measures for Portuguese (c.f., Table 4).

This kind of geographic analysis does not show larger trends. For example, one
common trend in digital corpora is that wealthy western countries like the US,
Canada, Western Europe, and Australia and New Zealand pattern together. But
this is not the case here, with Canada and New Zealand contrasting with the US
and Australia. Thus, a geographic analysis further confirms the reliability of
geo-referenced corpora in the sense that what little variation we do see does
not correspond with expected geographic patterns.

##  12 Conclusions

The experiments in this paper have shown that there is a consistent
relationship between the representation of language varieties across two
sources of geo-referenced digital corpora: the web and tweets. In other words,
these digital corpora are reliable. This finding is important because it
disproves the alternate hypothesis that one or both sources is a poor or
arbitrary representation of the underlying language varieties. This kind of
unreliability would lead to an inconsistent relationship between registers.
Reliability is not the same as validity. However, the reliability shown here
converges with evidence from dialect surveys and census data and computational
models of language varieties, all of which do evaluate the validity of digital
corpora.

This robust reliability gives us confidence in the use of digital corpora to
study linguistic variation. And this evaluation of both reliability and
validity is important because it justifies the use of computational modelling
which, in turn, enables global-scale experiments that help us better
understand language variation and change.

## References

  * Baldwin et al. (2013) Timothy Baldwin, Paul Cook, Marco Lui, Andrew MacKinlay, and Li Wang. 2013.  How Noisy Social Media Text, How Diffrnt Social Media Sources? In _Proceedings of the Sixth International Joint Conference on Natural Language Processing_ , pages 356–364.
  * Cook and Brinton (2017) Paul Cook and Laurel Brinton. 2017.  Building and Evaluating Web Corpora Representing National Varieties of English.  _Language Resources and Evaluation_ , 51(3):643–662.
  * Donoso and Sánchez (2017) Gonzalo Donoso and David Sánchez. 2017.  Dialectometric analysis of language variation in twitter.  In _Proceedings of the Fourth Workshop on NLP for Similar Languages, Varieties and Dialects_ , pages 16–25. Association for Computational Linguistics.
  * Dunn (2018) Jonathan Dunn. 2018.  Finding Variants for Construction-Based Dialectometry: A Corpus-Based Approach to Regional CxGs.  _Cognitive Linguistics_ , 29(2):275–311.
  * Dunn (2019a) Jonathan Dunn. 2019a.  Global Syntactic Variation in Seven Languages: Toward a Computational Dialectology.  _Frontiers in Artificial Intelligence_ , 2:15.
  * Dunn (2019b) Jonathan Dunn. 2019b.  Modeling global syntactic variation in english using dialect classification.  In _Proceedings of the Sixth Workshop on NLP for Similar Languages, Varieties and Dialects_ , pages 42–53. Association for Computational Linguistics.
  * Dunn (2020) Jonathan Dunn. 2020.  Mapping languages: The Corpus of Global Language Use.  _Language Resources and Evaluation_ , 54:999–1018.
  * Dunn and Adams (2019) Jonathan Dunn and Benjamin Adams. 2019.  Mapping Languages and Demographics with Georeferenced Corpora.  In _Proceedings of Geocomputation 2019_ , pages 1–16.
  * Dunn and Adams (2020) Jonathan Dunn and Benjamin Adams. 2020.  Geographically-balanced gigaword corpora for 50 language varieties.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 2528–2536. European Language Resources Association.
  * Dunn et al. (2020) Jonathan Dunn, Tom Coupe, and Benjamin Adams. 2020.  Measuring linguistic diversity during covid-19.  In _Proceedings of the Fourth Workshop on Natural Language Processing and Computational Social Science_ , pages 1–10. Association for Computational Linguistics.
  * Eisenstein et al. (2010) Jacob Eisenstein, Brendan O’Connor, Noah Smith, and Eric Xing. 2010.  A latent variable model for geographic lexical variation.  In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ , pages 221–227. Association for Computational Linguistics.
  * Eisenstein et al. (2014) Jacob Eisenstein, Brendan O’Connor, Noah Smith, and Eric Xing. 2014.  Diffusion of lexical change in social media.  _PloSOne_ , 10:1371.
  * Fothergill et al. (2016) Richard Fothergill, Paul Cook, and Timothy Baldwin. 2016.  Evaluating a Topic Modelling Approach to Measuring Corpus Similarity.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation_ , pages 273–279. European Language Resources Association.
  * Gamallo et al. (2016) Pablo Gamallo, Iñaki Alegria, José Ramom Pichel, and Manex Agirrezabal. 2016\.  Comparing Two Basic Methods for Discriminating Between Similar Languages and Varieties.  _Proceedings of the Third Workshop on NLP for Similar Languages, Varieties and Dialects_ , pages 170–177.
  * Graham et al. (2014) Mark Graham, Scott Hale, and Devin Gaffney. 2014.  Where in the World are You? Geolocation and Language Identification on Twitter.  _The Professional Geographer_ , 66(4):568–578.
  * Grieve et al. (2019) Jack Grieve, Chris Montgomery, Andrea Nini, Akira Murakami, and Diansheng Guo. 2019\.  Mapping Lexical Dialect Variation in British English Using Twitter.  _Frontiers in Artificial Intelligence_ , 2:11.
  * Grieve et al. (2011) Jack Grieve, Dirk Speelman, and Dirk Geeraerts. 2011.  A statistical method for the identification and aggregation of regional linguistic variation.  _Language Variation & Change_, 23(1):1–29.
  * Heeringa et al. (2006) Wilbert Heeringa, Peter Kleiweg, Charlotte Gooskens, and John Nerbonne. 2006.  Evaluation of String Distance Algorithms for Dialectology.  In _Workshop of the Workshop on Linguistic Distances_ , pages 51–62. Association for Computational Linguistics.
  * Heeringa et al. (2002) Wilbert Heeringa, John Nerbonne, and Peter Kleiweg. 2002.  Validating Dialect Comparison Methods.  In _Classification, Automation, and New Media_ , pages 445–452. Springer, Berlin.
  * Kilgarriff (2001) Adam Kilgarriff. 2001.  Comparing Corpora.  _International Journal of Corpus Linguistics_ , 6(1):97–133.
  * Kilgarriff and Rose (1998) Adam Kilgarriff and Tony Rose. 1998.  Measures for Corpus Similarity and Homogeneity.  In _Proceedings of the Third Conference on Empirical Methods for Natural Language Processing_ , pages 46–52. Association for Computational Linguistics.
  * Kondor et al. (2013) Dániel Kondor, István Csabai, László Dobos, János Szüle, Norbert Barankai, Tamás Hanyecz, Tamás Sebők, Zsófia Kallus, and Gábor Vattay. 2013\.  Using Robust PCA to Estimate Regional Characteristics of Language-use from Geotagged Twitter Messages.  In _Proceedings of IEEE 4th International Conference on Cognitive Infocommunications_ , pages 393–398. IEEE.
  * Lui et al. (2014) Marco Lui, Ned Letcher, Oliver Adams, Long Duong, Paul Cook, and Timothy Baldwin. 2014.  Exploring Methods and Resources for Discriminating Similar Languages.  In _Proceedings of the First Workshop on Applying NLP Tools to Similar Languages, Varieties and Dialects_ , pages 129–138. Association for Computational Linguistics.
  * Nunnally (1994) Jum Nunnally. 1994.  _Psychometric Theory_ , 3rd edition.  McGraw-Hill Education.
  * Pichel Campos et al. (2018) Jose Ramom Pichel Campos, Pablo Gamallo, and Iñaki Alegria. 2018.  Measuring language distance among historical varieties using perplexity. application to european portuguese.  In _Proceedings of the Fifth Workshop on NLP for Similar Languages, Varieties and Dialects_ , pages 145–155. Association for Computational Linguistics.
  * Rangel et al. (2020) Francisco Rangel, Paolo Rosso, Wajdi Zaghouani, and Anis Charfi. 2020.  Fine-grained analysis of language varieties and demographics.  _Natural Language Engineering_ , 26(6):641–661.
  * Szmrecsanyi et al. (2019) Benedikt Szmrecsanyi, Jason Grafmiller, and Laura Rosseel. 2019.  Variation-Based Distance and Similarity Modeling: A Case Study in World Englishes.  _Frontiers in Artificial Intelligence_ , 2:23.
  * Zampieri et al. (2020) Marcos Zampieri, Preslav Nakov, and Yves Scherrer. 2020.  Natural language processing for similar languages, varieties, and dialects: A survey.  _Natural Language Engineering_ , 26(6):595–612.


# Essentially No Barriers in Neural Network Energy Landscape

Felix Draxler  Kambis Veschgini  Manfred Salmhofer  Fred A. Hamprecht

###### Abstract

Training neural networks involves finding minima of a high-dimensional non-
convex loss function. Relaxing from linear interpolations, we construct
continuous paths between minima of recent neural network architectures on
CIFAR10 and CIFAR100. Surprisingly, the paths are essentially flat in both the
training and test landscapes. This implies that minima are perhaps best seen
as points on a single connected manifold of low loss, rather than as the
bottoms of distinct valleys.

Machine Learning, ICML

##  1 Introduction

Neural networks have achieved remarkable success in practical applications
such as object recognition (He et al., 2016; Huang et al., 2017), machine
translation (Bahdanau et al., 2015; Vinyals & Le, 2015), speech recognition
(Hinton et al., 2012; Graves et al., 2013; Xiong et al., 2017) etc.
Theoretical insights on why neural networks can be trained successfully
despite their high-dimensional and non-convex loss functions are few or based
on strong assumptions such as the eigenvalues of the Hessian at critical
points being random (Dauphin et al., 2014), linear activations (Choromanska et
al., 2014; Kawaguchi, 2016) or wide hidden layers (Soudry & Carmon, 2016;
Nguyen & Hein, 2017).

In the current literature, minima of the loss function are typically depicted
as points at the bottom of a strictly convex valley of a certain width that
reflects the generalisation of the network, with network parameters given by
the location of the minimum (Keskar et al., 2016). This is also the picture
obtained when the loss function of neural networks is visualised in low
dimension (Li et al., 2017).

In this work, we conjecture that neural network loss minima are not isolated
points in parameter space, but essentially form a connected manifold. More
precisely, we argue that the part of the parameter space where the loss
remains below a certain low threshold forms one single connected component.

We support the above claim by studying the energy landscape of several ResNets
and DenseNets on CIFAR10 and CIFAR100: For random pairs of minima, we
construct continuous paths through parameter space for which the loss remains
very close to the value found directly at the minima. An example for such a
path is shown in Figure 1.

Figure 1: Left: A slice through the one million-dimensional training loss
function of DenseNet-40-12 on CIFAR10 and the minimum energy path found by our
method. The plane is spanned by the two minima and the mean of the nodes of
the path. Right: Loss along the linear line segment between minima, and along
our high-dimensional path. Surprisingly, the energy along this path is
essentially flat.

Our main contribution is the finding of paths

  1. 1.

that connect minima trained from different initialisations which are not
related to each other via known loss-conserving operations like rescaling,

  2. 2.

along which the training loss remains essentially at the same value as at the
minima,

  3. 3.

along which the test loss remains essentially constant while the test error
rate slightly increases.

The existence of such paths suggests that modern neural networks have enough
parameters such that they can achieve good predictions while a big part of the
network undergoes structural changes. In closing, we offer qualitative
justification of this behaviour that may offer a handle for future theoretical
investigation.

##  2 Related Work

In discussions about why neural networks generalise despite the extremely
large number of parameters, one often finds the argument that wide minima
generalise better (Keskar et al., 2016). This picture is confirmed when
visualising the parameter space on a random plane around a minimum (Li et al.,
2017). We draw a completely different image of the loss landscape: Minima are
not located in finite-width valleys, but there are paths through the parameter
space along which the loss remains very close to the value at the minima. A
similar view had previously been conjectured by (Sagun et al., 2017). They
find flat linear paths between minima that are close in parameter space by
construction. We extend their work by constructing flat paths between
arbitrary minima.

It has previously been shown that minima of networks with ReLU activations are
degenerate (Dinh et al., 2017): One can scale all parameters in one layer by a
constant $\alpha$ and in following layer by $\alpha^{-1}$ without changing the
output of the network. Here, we provide evidence for a different kind of
degeneracy: We construct paths between independent minima that are essentially
flat.

(Freeman & Bruna, 2016) showed that local minima are connected without large
barriers for a CNN on MNIST and an RNN on PTB next word prediction. On
CIFAR10, they found a more frustrated landscape. We extend their work in two
ways: First, we consider ResNets and DenseNets that outperform plain CNNs by a
large margin. Second, we apply a state of the art method for connecting minima
from molecular statistical mechanics: The Automated Nudged Elastic Band
(AutoNEB) algorithm (Kolsbjerg et al., 2016) which in turn is based on the
Nudged Elastic Band (NEB) algorithm (Jónsson et al., 1998). We additionally
systematically replace paths that contain relatively high loss barriers.
Combining the above we find paths with essentially no energy barrier.

NEB has so far been applied to a multi-layer perceptron with a single hidden
layer (Ballard et al., 2016). High energy barriers between the minima of
network were found when using three hidden neurons, and disappeared upon
adding more neurons to the hidden layer. In follow-up work, (Ballard et al.,
2017) trained a multi-layer perceptron with a single hidden layer on MNIST.
They found that with $l^{2}$-regularisation, the landscape had no significant
energy barriers. However, for their network they report an error rate of
$14.8\%$ which is higher than the $12\%$ achieved even by a linear classifier
(LeCun et al., 1998) and the 0.35% achieved with a standard CNN (Ciresan et
al., 2011).

In this work, we apply AutoNEB to a nontrivial network for the first time, and
make the surprising observation that different minima of state of the art
networks on CIFAR10 and CIFAR100 are connected through essentially flat paths.

After submission of this work to the International Machine Learning Conference
(ICML) 2018, (Garipov et al., 2018) independently reported that they also
constructed paths between neural network minima. They study the loss landscape
of several architectures on CIFAR10 and CIFAR100 and report the same
surprising observation: minima are connected by paths with constantly low
loss.

##  3 Method

In the following, we use the terms energy and loss interchangeably.

###  3.1 Minimum Energy Path

A neural network loss function depends on the architecture, the training set
and the network parameters $\theta$. Keeping the former two fixed, we simply
write $L(\theta)$ and start with two parameter sets $\theta_{1}$ and
$\theta_{2}$. In our case, they are minima of the loss function, i.e. they
result from training the networks to convergence. The goal is to find the
continuous path $p^{*}$ from $\theta_{1}$ to $\theta_{2}$ through parameter
space with the lowest maximum loss:

$\displaystyle p(\theta_{1},\theta_{2})^{*}=\operatorname*{arg\,min}_{p\text{
from }\theta_{1}\text{ to }\theta_{2}}\big{\\{}\max_{\theta\in
p}L(\theta)\big{\\}}.$

For this optimisation to be tractable, the loss function must be sufficiently
smooth, i.e. contain no jumps along the path. The output and loss of neural
networks are continuous functions of the parameters (Montúfar et al., 2014);
only the derivative is discontinuous for the case of ReLU activations.
However, we cannot give any bounds on how steep the loss function may be. We
address this problem by sampling all paths very densely.

Such a lowest path $p^{*}$ is called the minimum energy path (MEP) (Jónsson et
al., 1998). We refer to the parameter set with the maximum loss on a path as
the “saddle point” of the path because it is a true saddle point of the loss
function.

In low-dimensional spaces, it is easy to construct the exact minimum energy
path between two minima, for example by using dynamic programming on a densely
sampled grid.

This is not possible for present day’s neural networks with parameter spaces
that have millions of dimensions. We thus must resort to methods that
construct an approximation of the MEP between two points using some local
heuristics. In particular, we resort to the Automated Nudged Elastic Band
(AutoNEB) algorithm (Kolsbjerg et al., 2016). This method is based on the
Nudged Elastic Band (NEB) algorithm (Jónsson et al., 1998).

NEB bends a straight line segment by applying gradient forces until there are
no more gradients perpendicular to the path. Then, as for the MEP, the highest
point of the resulting path is a critical point. While this critical point is
not necessarily the saddle point we were looking for, it gives an upper bound
for the energy at the saddle point.

In the following, we present the mechanical model behind and the details of
NEB. We then proceed to AutoNEB.

#### Mechanical Model

A chain of $N+2$ pivots (parameter sets) $p_{i}$ for $i=0,\dots,N+1$ is
connected via springs of stiffness $k$. The initial and the final pivots are
fixed to the minima to connect, i.e. $p_{0}=\theta_{1}$ and
$p_{N+1}=\theta_{2}$. Using gradient descent, the path that minimises the
following energy function is found:

$\displaystyle
E(p)=\sum_{i=1}^{N}L(p_{i})+\sum_{i=0}^{N}\frac{1}{2}k\left\lVert
p_{i+1}-p_{i}\right\rVert^{2}$ (1)

The problem with this energy formulation lies in the choice of the spring
constant: If, on the one hand, $k$ is too small, the distances between the
pivots become larger in areas with high energy. However, identifying the
highest point on the path and its energy is the very goal of the algorithm, so
the sampling rate should be high in the high-energy regions. If, on the other
hand, $k$ is chosen too large, it becomes energetically advantageous to
shorten and hence straighten the path as the spring energy grows quadratically
with the total length of the path. This cuts into corners of the loss surface
and the resulting path can miss the saddle point.

#### Nudged Elastic Band

Inspired by the above model, (Jónsson et al., 1998) presented the Nudged
Elastic Band (NEB). For brevity, we directly present the improved version by
(Henkelman & Jónsson, 2000). The force resulting from Equation 1 consists of a
force derived from the loss and a force originating from the springs:

$\displaystyle F_{i}=-\nabla_{p_{i}}E(p)=F_{i}^{L}+F_{i}^{S}$

For NEB, the physical forces are modified, or nudged, so that the loss force
only acts perpendicularly to the path and the spring force only parallelly to
the path (see also Figure 2):

$\displaystyle F_{i}^{\text{NEB}}$
$\displaystyle=F_{i}^{L}\big{|}_{\perp}+F_{i}^{S}\big{|}_{\parallel}.$

The direction of the path is defined by the local tangent $\hat{\tau}_{i}$ to
the path. The two forces now read:

$\displaystyle\begin{split}F_{i}^{L}\big{|}_{\perp}&=-(\nabla L(p_{i})-(\nabla
L(p_{i})\cdot\hat{\tau}_{i})\hat{\tau}_{i})\\\
F_{i}^{S}\big{|}_{\parallel}&=(F_{i}^{S}\cdot\hat{\tau}_{i})\hat{\tau}_{i}\end{split}$
(2)

where the spring force opposes unequal distances along the path:

$\displaystyle F_{i}^{S}=-k(\left\lVert p_{i}-p_{i-1}\right\rVert-\left\lVert
p_{i+1}-p_{i}\right\rVert)$ (3)

Figure 2:  Two dimensional loss surface, with two minima connected by a
minimum energy path (MEP) and a nudged elastic band (NEB) at iteration 0, 10
and converged. Construction of NEB update $\Delta p_{i}$ for one pivot. The
tangent points to the neighbouring pivot with higher energy. Re-distribution
$\Delta p_{i}^{s}$ acts parallelly and the loss force $\nabla_{i}L$
perpendicularly to the tangent.

In this formulation, high energy pivots no longer “slide down” from the saddle
point. The spring force only re-distributes pivots on the path, but does not
straighten it. Pivots can be spaced unequally by introducing target distances
or unequal spring constants into Equation 3.

The local tangent is chosen to point in the direction of one of the adjacent
pivots ($\mathcal{N}$ normalises to length one):

$\displaystyle\hat{\tau}_{i}=\mathcal{N}\begin{cases}p_{i+1}-p_{i}&\text{if
}L(p_{i+1})>L(p_{i-1})\\\ p_{i}-p_{i-1}&\text{else.}\end{cases}$

This particular choice of $\hat{\tau}$ prevents kinks in the path and ensures
a good approximation near the saddle point (Henkelman & Jónsson, 2000).

The above procedure requires the following hyperparameters: The spring
stiffness $k$ and number of pivots $N$.

(Sheppard et al., 2008) claim that a wide range of $k$ leads to the same
result on a given loss surface. However, if chosen too large, the optimisation
can become unstable. If it is too small, an excessive number of iterations are
needed before the pivots become equally distributed. We did not find a value
for $k$ that worked well across different loss surfaces and number of pivots
$N$. Instead, we re-distribute the pivots in each iteration $t$ and set the
actual spring force to zero. The loss force is still restricted to act
parallelly to the path. In the literature, this is sometimes referred to as
the string method (Sheppard et al., 2008).

Algorithm 1 shows how the initial path is iteratively updated using the above
forces. As a companion, Figure 2 visualises the forces in one update step for
a two dimensional example. In this formulation, we use gradient descent to
update the path. Any other gradient based optimiser can be used. It typically
introduces additional hyperparameters, for example a learning rate $\gamma$.
The number of iterations $T$ should be chosen large enough for the
optimisation to converge.

Algorithm 1 NEB

Input: initial path $p^{(0)}$ with $N+2$ pivots, $p_{0}^{(0)}=\theta_{1}$ and
$p_{N+1}^{(0)}=\theta_{2}$.

for t = $1,\dots,T$ do

Redistribute pivots on path $p^{(t-1)}$ and store as $p$.

for i = $1,\dots,N$ do

Compute projected loss force $F_{i}=F^{L}_{i}\big{|}_{\perp}$.

Store pivot $p_{i}^{(t)}=p_{i}+\gamma F_{i}$.

end for

end for

return final path $p^{(T)}$

The evaluation time of Algorithm 1 rises linearly with the number of
iterations and the number of pivots on the path. Computing the NEB forces can
trivially be parallelised over the pivots.

The number of pivots $N$ trades off between computational effort on the one
hand and subsampling artefacts on the other hand. In neural networks, it is
not known what sampling density is needed for traversing the parameter space.
We use an adaptive procedure that inserts more pivots where needed:

#### AutoNEB

The Automated Nudged Elastic Band (AutoNEB, Algorithm 2) wraps the above NEB
algorithm (Kolsbjerg et al., 2016). It runs NEB only for a small number of
iterations $T$ at a time, initially with a small number of pivots $N$. It is
then checked if the current pivots accurately sample the path. If sampling is
not dense enough, new pivots are added at locations where it is estimated that
the path requires more accuracy, see Appendix A. This procedure is repeated
several times.

Algorithm 2 AutoNEB

Input: Minima to connect $\theta_{1},\theta_{2}$.

Initialise $N$ pivots equally spaced on line segment
$(\theta_{1},\theta_{2})$.

for $t^{\prime}=1,\dots,T^{\prime}$ do

Optimise path using NEB (see Algorithm 1).

Evaluate loss along NEB.

Insert pivots where residuum is large.

end for

return path after final iteration.

###  3.2 Local minimum energy paths

AutoNEB is not guaranteed to find the true MEP. Instead, it can get stuck in
local minimum energy paths (local MEPs) with spuriously high saddle point
losses. The good news is that the graph of minima and local MEPs has an
ultrametric property: Suppose some local MEPs from a minimum $A$ to $B$ and
from $B$ to $C$ are known. We call them $p_{AB}$ and $p_{BC}$. The respective
saddle point energies give an upper bound for the true saddle point energies
(marked with an asterisk):

$\displaystyle L_{AB}^{*}$ $\displaystyle\leq L_{AB}=\max_{\theta\in
p_{AB}}L(\theta)$ $\displaystyle L_{BC}^{*}$ $\displaystyle\leq
L_{BC}=\max_{\theta\in p_{BC}}L(\theta)$

The concatenation of the two paths yields an upper bound for the true saddle
point energy between $A$ and $C$ (ultrametric triangle inequality):

$\displaystyle L_{AC}^{*}\leq\max\\{L_{AB},L_{BC}\\}$

Figure 3:  Overview over Algorithm 3 and examples for the first nine
iterations and some later iteration. First, all minima are connected to one
particular minimum. Then, AutoNEB computes new local MEPs to circumvent the
worst local MEPs in the minimum spanning tree. This is repeated until local
MEPs are known between all pairs of minima or the procedure is stopped early.
Whenever the algorithm stops, an upper bound for each pair of minima is
available via the minimum spanning tree.

###### Proof.

Concatenating the paths $p_{AB}$ and $p_{BC}$ gives a new path $p_{AC}$
connecting $A$ to $C$. The saddle point is located at the maximum loss along a
path and hence the saddle point energy of $p_{AC}$ is
$L_{AC}=\max\\{L_{AB},L_{BC}\\}$. ∎

This has three consequences:

  1. 1.

As soon as the minima and computed local MEPs form one connected graph, upper
bounds for all saddle energies are available. We can hence very quickly get
upper bounds for all pairs of minima by connecting one minimum to all others.

  2. 2.

When AutoNEB finds a bad local MEP, this can be addressed by computing paths
between other pairs of minima. As soon as a lower path is found by
concatenating other paths, the bad local MEP can be removed. This means that
the bad local paths can easily be corrected for.

  3. 3.

When we evaluate the saddle point energies of a set of computed local MEPs, we
can ignore paths with higher energy than the concatenation of paths with a
lower maximal energy.
These lowest local MEPs form a minimum spanning tree in the available graph
(Gower & Ross, 1969). A Minimum Spanning Tree (MST) can be found efficiently,
e.g. using Kruskal’s algorithm.

We resort to a heuristic (Figure 3, Algorithm 3) to systematically sample edge
costs from a latent graph to find or approximate its MST. Since running
AutoNEB is computationally expensive (comparable to training the corresponding
network once), we stop the iteration when the lightened spanning tree found so
far contains only similar saddle point energies.

Algorithm 3 Energy Landscape Exploration

Input: set of minima $\theta_{i}$.

Connect $\theta_{1}$ to all $\theta_{i},i\neq 1$, yielding a spanning tree.

repeat

Remove edge $p_{o}$ with highest loss from spanning tree.

From each resulting tree, try to select one minimum, so that no local MEP is
known for the pair.

if search failed then

Re-insert $p_{o}$ and ignore it when searching for the highest edge in the
future.

else

Compute new path $p_{n}$ using AutoNEB.

if $L_{p_{n}}<L_{p_{o}}$ then

Add $p_{n}$ to the tree, making tree “lighter”.

else

Re-insert $p_{o}$ to the tree (no better path was found).

end if

end if

until one local MEP is known for each pair of minima or computational budget
is exceeded.

return saddle points in minimum spanning tree.

##  4 Experiments

We connect minima of different CNNs, ResNets (He et al., 2016) and DenseNets
(Huang et al., 2017) on the image classification tasks CIFAR10 and CIFAR100
(Krizhevsky & Hinton, 2009) using AutoNEB. Per architecture, we consider ten
minima.111Source code is available at https://github.com/fdraxler/PyTorch-
AutoNEB.

The minima are constructed from multiple random initialisations and are truly
distinct: On the test data, the set of misclassified images differs between
the minima. More precisely, on the ResNet and DenseNet architectures, we
observe a maximum 70% overlap of the samples that are misclassified at two
minima, proving their distinctiveness.

We report the average cross-entropy loss and misclassification rates over the
full training and test data for the minima found. For the final evaluation, we
reduce the saddle points to the minimum spanning tree with the saddle training
loss as weight.

Figure 4:  Typical snapshots of the loss along a path connecting two minima,
as pivots are inserted into a nudged elastic band: (1) After the first cycle,
typically one or two corners are cut. New pivots are inserted at high loss
values, here between the second and the third pivot. (2) After four cycles of
high learning rate, the highest loss on the path is reduced by a factor of
five. Between pivots we find low energy regions that we attribute to the high
learning rate of $0.1$. (3) The first round with low learning rate of $0.01$
reduces the energy by another factor of two. (4) After 14 cycles, no major
energy bumps exist between the pivots, the procedure is converged. Results
shown are for a ResNet-20 on CIFAR10.

###  4.1 AutoNEB schedule

The set-up is identical for all network architectures, except for the batch
sizes which we note in each case.

The minimum pairs to connect are ordered by Algorithm 3. For each minimum
pair, AutoNEB (see Algorithm 2) is run for a total of 14 cycles of NEB. The
loss is evaluated for each pivot on a random batch.

After each cycle, new pivots are inserted at positions where the loss exceeds
the energy estimated by linear interpolation between pivots by at least 20%
compared to the total energy difference along the path. Comparing to the total
loss difference prioritises big errors which is beneficial as each additional
pivot implies one more loss evaluations per iteration. The energy is evaluated
on nine points between each pair of neighbouring pivots.

As optimiser, we use SGD with momentum $0.9$ and $l^{2}$-regularisation with
$\lambda=0.0001$.

The NEB cycles are configured with a learning rate decay:

  1. 1.

Four cycles of 1000 steps each with learning rate 0.1.

  2. 2.

Two cycles with 2000 steps and learning rate 0.1. The number of steps was
increased as it did not prove necessary inserting new pivots after 1000 steps.

  3. 3.

Four cycles of 1000 steps with learning rate 0.01. The loss drops
significantly in this phase.

  4. 4.

No big improvement was seen in the last four cycles of 1000 steps each with a
learning rate of 0.001.

Figure 4 shows typical snapshots of the loss-along-path between the above
cycles.

###  4.2 Architectures

We consider a wide range of architectures, from shallow CNNs to recent deep
networks with skip connections.

#### Basic CNN

We analyse CNNs without skip connections with a variety of depths and widths
on both CIFAR10 and CIFAR100. We name them
“CNN-$W{\mkern-2.0mu\times\mkern-2.0mu}D$” where $W$ corresponds to the width
of each layer (number of channels) and $D$ to the number of convolutional
layers. Each convolution is $5\times 5$, a max pooling layer of 2 is attached
to each convolution, and a single hidden fully connected layer of width 256
and batch normalisation (Ioffe & Szegedy, 2015) are used. We consider the one-
layer CNN-$12{\mkern-2.0mu\times\mkern-2.0mu}1$,
CNN-$24{\mkern-2.0mu\times\mkern-2.0mu}1$,
CNN-$36{\mkern-2.0mu\times\mkern-2.0mu}1$,
CNN-$48{\mkern-2.0mu\times\mkern-2.0mu}1$ and
CNN-$96{\mkern-2.0mu\times\mkern-2.0mu}1$, and the multi-layer
CNN-$48{\mkern-2.0mu\times\mkern-2.0mu}2$ and
CNN-$48{\mkern-2.0mu\times\mkern-2.0mu}3$.

#### ResNet

We train ResNets on both CIFAR10 and CIFAR100 (ResNet-20, -32, -44 and -56)
following the training procedure in (He et al., 2016). For ResNet-20 and
ResNet-32, the best local MEPs were found using a batch size of 512 training
samples. For ResNet-44 and ResNet-56, this number was decreased to 256.

#### DenseNet

We train a DenseNet-40-12 and a DenseNet-100-12-BC on both CIFAR10 and
CIFAR100 following the training procedure in (Huang et al., 2017). The AutoNEB
batch size was set to 256.

###  4.3 Saddle point losses

Figure 5:  Core result: Minimum ($\blacksquare$) and saddle point ($\bullet$)
losses on training and test set. The training (orange) saddle losses are
almost identical to the minima on CIFAR10 on the deep architectures (middle
and right). On CIFAR100, a small gap remains that vanishes in comparison to
the loss of a randomly initialised network. On a simple architecture (left),
increasing width and especially depth closes the gap between the barriers and
the minima. On the test set (blue), the points of the minima and the saddle
points are very close. Error bars are omitted since they would be smaller than
the markers.

The saddle point losses for both training and test sets found by AutoNEB are
shown in Figure 5, and listed in detail in Appendix B in Appendix B. They are
small for the shallow networks and almost negligible for the deep residual
networks.

Compare the saddle point loss to the loss at the minima on the training and on
the test set. For the shallow CNNs on the one hand, the saddle loss is found
quite close to the test loss. On the other hand, the saddle loss of the
ResNets and DenseNets lies very close to the training loss.

Further, we measure how late during training the learning curve crosses the
saddle loss, as visualised in Figure 6. The learning curve falls below the
saddle point energy only after the first learning rate decay and an additional
significant drop of the loss for all architectures. For the wider CNNs on
CIFAR10 and the majority of ResNets and DenseNets, the losses meet even after
the second decay, i.e. in the final phase of learning.

We observe the following trend: The deeper and wider an architecture, the
lower are the saddles between minima until they essentially vanish for
current-day deep architectures. The more complex dataset CIFAR100 raises the
barriers.

At the same time, the test accuracy is preserved: The classification error
only increases slightly by maximally $0.5\%$ ($2.2\%$) for all deep
architectures on CIFAR10 (CIFAR100) compared to the minima.

Figure 6:  Learning curves illustrating how late in training the loss drops
below the saddles. The training loss passes the mean saddle point energy at
about 205 (72) epochs or 78% (52%) of training. Among all deep architectures
considered, the average saddle point crosses the training loss last for
DenseNet-100-12-BC and earliest for ResNet-56, both on CIFAR100. The crossing
for the DenseNet had to be identified in a log plot.

We conclude that the saddle points have surprisingly low loss with respect to
the metrics above. In other words, there are essentially no loss barriers in
current-day deep architectures.

###  4.4 Properties of obtained local MEPs

Figure 7:  Network parameters follow a smooth trajectory along the MEPs. For
each coordinate, the distance to the linear interpolation is shown (negative
means closer to origin). The largest deviations from the linear path occur
near the saddle point. The upper plots show those ten coordinates that deviate
most from the linear interpolation. The ten coordinates in the lower row are
chosen randomly. Also shown is the training loss along the two paths. The
dataset is CIFAR100.

The local MEPs between the minima not only have very low loss, they also
follow simple trajectories. Figure 7 shows some coordinates of two local MEPs
in a parallel coordinate plot. We find that each coordinate has a smooth path.
The largest deviations occur near the saddle point of the path. The paths are
between $50\%$ to $2.5$ times longer than the direct connection between the
minima.

##  5 Discussion

We have pointed out an intriguing property of the loss surface of current-day
deep networks, by upper-bounding the saddle points between the parameter sets
that result from stochastic gradient descent, a.k.a. “minima”. These empirical
upper bounds are astonishingly close to the loss at the minima themselves. The
experiments on the CNNs suggest that the disappearance of barriers emerges as
the networks get wider and especially deeper. At this point, we cannot give a
formal characterization of the regime in which this finding holds. A formal
proof is also complicated by the fact that the loss surface is a function not
only of the parameters and the architecture, but also of the training set; and
the distribution of real-world structured data such as images or sentences
does not lend itself to a compact mathematical representation. That said, we
want to make two related arguments that may help explain why we observe no
substantial barrier between minima.

###  5.1 Resilience

State of the art neural networks have dozens or hundreds of neurons / channels
per layer, and skip connections between non-adjacent layers. Assume that by
training, a parameter set with low loss has been identified. Now if we perturb
a single parameter, say by adding a small constant, but leave the others free
to adapt to this change to still minimise the loss, it may be argued that by
adjusting somewhat, the myriad other parameters can “make up” for the change
imposed on only one of them. After this relaxation, the procedure and argument
can be repeated, though possibly with the perturbation of a different
parameter.

This type of resilience is exploited and encouraged by procedures such as
Dropout (Srivastava et al., 2014) or ensembling (Hansen & Salamon, 1990). It
is also the reason why neural networks can be greatly condensed before a
substantial increase in loss occurs (Liu et al., 2017).

###  5.2 Redundancy

Figure 8: Network capacity for XOR dataset: The continuous transition from one
minimum (left) to another minimum (right) is not possible without
misclassifying at least one instance (upper middle). (Lower middle) Adding one
helper neuron makes the transition possible while always predicting the right
class for all data points, i.e. by turning off the outgoing weight of Bob.

Consider the textbook example of a two-layer perceptron that can fit the XOR
problem. The two neurons traditionally used in the first hidden layer – let’s
call them Alice and Bob – are shown in Figure 8 on the left. We can obtain an
equivalent network by exchanging Alice and Bob (and permuting the weights of
the neuron in the second hidden layer, not shown). This network, also
corresponding to a minimum of the loss surface, is shown in Figure 8 on the
right. Now, any path between these two minima will entail parameter sets such
as the one in the upper centre of Figure 8 that incur high loss.

If, on the other hand, we introduce an auxiliary neuron, Charlie, we can play
a small choreography: Enter Charlie. Charlie stands in for Bob. Bob
transitions to Alice’s role via Figure 8, lower centre. Alice takes over from
Charlie. Exit Charlie. If the neuron in the second hidden layer adjusts its
weights so as to disregard the output from the neuron-in-transition, the
entire network incurs no higher loss than at the two original minima.

We have constructed a perfect minimum energy path through increasing the
width. Similarly, it is possible to construct a zero-loss path by adding a
second two-neuron layer to the network, that is by increasing the depth of the
network.

##  6 Conclusion

We find that the loss surface of deep neural networks contains paths with
constantly low loss. The paths connect the minima so that they form one single
connected component in the loss landscape. The barriers are especially low
with increasing depth and width.

We put forth two closely related explanations in the above. Both hold only if
the network has some extra capacity, or degrees of freedom, to spare.
Empirically, this seems to be the case for modern-day architectures applied to
standard problems.

This has the profound implication that low Hessian eigenvalues exist apart
from the eigenvectors with analytically zero eigenvalues due to scaling.

We introduce AutoNEB for the characterisation of current-day architectures for
the first time. The method opens the door to further empirical research on the
energy landscape of neural networks. When the hyperparameters of AutoNEB are
further refined, we expect to find even lower paths up to the level where the
true saddle points are recovered. It is then interesting to see if certain
minima have a higher barrier between them than others. This makes it possible
to recursively form clusters of minima, i.e. using single-linkage clustering.
In the traditional energy landscape literature, this kind of clustering is
summarised in disconnectivity graphs (Wales et al., 1998) which can help
visualise very high-dimensional surfaces.

On the practical side, we envisage using the resulting paths as a large
ensemble of neural networks (Garipov et al., 2018), especially given that we
observe marginally lower test loss along the path.

More importantly, we hope these observations will stimulate new theoretical
work to better understand the nature of the loss surface, and why local
optimisation on such surfaces results in networks that generalize so well.

## Acknowledgements

FAH gratefully acknowledges support by DFG under grant no. HA 4364/9-1.

## References

  * Bahdanau et al. (2015) Bahdanau, D., Cho, K., and Bengio, Y.  Neural machine translation by jointly learning to align and translate.  In _ICLR_ , 2015.
  * Ballard et al. (2016) Ballard, A. J., Stevenson, J. D., Das, R., and Wales, D. J.  Energy landscapes for a machine learning application to series data.  _J. Chem. Phys._ , 144(12):124119, Mar 2016.  ISSN 1089-7690.  doi: 10.1063/1.4944672.  URL http://dx.doi.org/10.1063/1.4944672.
  * Ballard et al. (2017) Ballard, A. J., Das, R., Martiniani, S., Mehta, D., Sagun, L., Stevenson, J. D., and Wales, D. J.  Energy landscapes for machine learning.  _Physical Chemistry Chemical Physics (Incorporating Faraday Transactions)_ , 19:12585–12603, 2017.  doi: 10.1039/C7CP01108C.
  * Choromanska et al. (2014) Choromanska, A., Henaff, M., Mathieu, M., Arous, G. B., and LeCun, Y.  The loss surface of multilayer networks.  _CoRR_ , abs/1412.0233, 2014.  URL http://arxiv.org/abs/1412.0233.
  * Ciresan et al. (2011) Ciresan, D. C., Meier, U., Masci, J., Maria Gambardella, L., and Schmidhuber, J.  Flexible, high performance convolutional neural networks for image classification.  In _IJCAI Proceedings-International Joint Conference on Artificial Intelligence_ , volume 22, pp. 1237. Barcelona, Spain, 2011.
  * Dauphin et al. (2014) Dauphin, Y., Pascanu, R., Gülçehre, Ç., Cho, K., Ganguli, S., and Bengio, Y.  Identifying and attacking the saddle point problem in high-dimensional non-convex optimization.  _CoRR_ , abs/1406.2572, June 2014.  URL http://arxiv.org/abs/1406.2572.
  * Dinh et al. (2017) Dinh, L., Pascanu, R., Bengio, S., and Bengio, Y.  Sharp minima can generalize for deep nets.  In Precup, D. and Teh, Y. W. (eds.), _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pp. 1019–1028, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR.  URL http://proceedings.mlr.press/v70/dinh17b.html.
  * Freeman & Bruna (2016) Freeman, C. D. and Bruna, J.  Topology and Geometry of Half-Rectified Network Optimization.  _ArXiv e-prints_ , November 2016.  URL http://arxiv.org/abs/1611.01540.
  * Garipov et al. (2018) Garipov, T., Izmailov, P., Podoprikhin, D., Vetrov, D. P., and Wilson, A. G.  Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs.  _ArXiv e-prints_ , February 2018.  URL http://arxiv.org/abs/1802.10026.
  * Gower & Ross (1969) Gower, J. C. and Ross, G. J. S.  Minimum spanning trees and single linkage cluster analysis.  _Journal of the Royal Statistical Society. Series C (Applied Statistics)_ , 18(1):54–64, 1969.  ISSN 00359254, 14679876.  URL http://www.jstor.org/stable/2346439.
  * Graves et al. (2013) Graves, A., Mohamed, A.-r., and Hinton, G.  Speech recognition with deep recurrent neural networks.  In _Acoustics, speech and signal processing (icassp), 2013 ieee international conference on_ , pp. 6645–6649. IEEE, 2013.
  * Hansen & Salamon (1990) Hansen, L. K. and Salamon, P.  Neural network ensembles.  _IEEE transactions on pattern analysis and machine intelligence_ , 12(10):993–1001, 1990.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Henkelman & Jónsson (2000) Henkelman, G. and Jónsson, H.  Improved tangent estimate in the nudged elastic band method for finding minimum energy paths and saddle points.  _The Journal of chemical physics_ , 113(22):9978–9985, 2000.
  * Hinton et al. (2012) Hinton, G., Deng, L., Yu, D., Dahl, G. E., Mohamed, A.-r., Jaitly, N., Senior, A., Vanhoucke, V., Nguyen, P., Sainath, T. N., et al.  Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups.  _IEEE Signal Processing Magazine_ , 29(6):82–97, 2012.
  * Huang et al. (2017) Huang, G., Liu, Z., Weinberger, K. Q., and van der Maaten, L.  Densely connected convolutional networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , volume 1, pp. 3, 2017.
  * Ioffe & Szegedy (2015) Ioffe, S. and Szegedy, C.  Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift.  _ArXiv e-prints_ , February 2015.
  * Jónsson et al. (1998) Jónsson, H., Mills, G., and Jacobsen, K. W.  Nudged elastic band method for finding minimum energy paths of transitions.  In _Classical and quantum dynamics in condensed phase simulations_ , pp. 385–404. World Scientific, 1998.
  * Kawaguchi (2016) Kawaguchi, K.  Deep learning without poor local minima.  In _Advances in Neural Information Processing Systems_ , pp. 586–594, 2016.
  * Keskar et al. (2016) Keskar, N. S., Mudigere, D., Nocedal, J., Smelyanskiy, M., and Tang, P. T. P.  On large-batch training for deep learning: Generalization gap and sharp minima.  _arXiv preprint arXiv:1609.04836_ , September 2016.  URL http://arxiv.org/abs/1609.04836.
  * Kolsbjerg et al. (2016) Kolsbjerg, E. L., Groves, M. N., and Hammer, B.  An automated nudged elastic band method.  _The Journal of chemical physics_ , 145(9):094107, 2016.
  * Krizhevsky & Hinton (2009) Krizhevsky, A. and Hinton, G.  Learning multiple layers of features from tiny images.  2009\.
  * LeCun et al. (1998) LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Li et al. (2017) Li, H., Xu, Z., Taylor, G., and Goldstein, T.  Visualizing the loss landscape of neural nets.  _arXiv preprint arXiv:1712.09913_ , 2017.
  * Liu et al. (2017) Liu, Z., Li, J., Shen, Z., Huang, G., Yan, S., and Zhang, C.  Learning efficient convolutional networks through network slimming.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 2736–2744, 2017.
  * Montúfar et al. (2014) Montúfar, G., Pascanu, R., Cho, K., and Bengio, Y.  On the number of linear regions of deep neural networks.  In _Advances in neural information processing systems_ , pp. 2924–2932, 2014.
  * Nguyen & Hein (2017) Nguyen, Q. and Hein, M.  The loss surface of deep and wide neural networks.  In _ICML_ , 2017.
  * Sagun et al. (2017) Sagun, L., Evci, U., Ugur Guney, V., Dauphin, Y., and Bottou, L.  Empirical Analysis of the Hessian of Over-Parametrized Neural Networks.  _ArXiv e-prints_ , June 2017.  URL http://arxiv.org/abs/1706.04454.
  * Sheppard et al. (2008) Sheppard, D., Terrell, R., and Henkelman, G.  Optimization methods for finding minimum energy paths.  _The Journal of Chemical Physics_ , 128(13):134106, Apr 2008.  ISSN 1089-7690.  doi: 10.1063/1.2841941.  URL http://dx.doi.org/10.1063/1.2841941.
  * Soudry & Carmon (2016) Soudry, D. and Carmon, Y.  No bad local minima: Data independent training error guarantees for multilayer neural networks.  _ArXiv e-prints_ , May 2016.  URL http://arxiv.org/abs/1605.08361.
  * Srivastava et al. (2014) Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R.  Dropout: A simple way to prevent neural networks from overfitting.  _The Journal of Machine Learning Research_ , 15(1):1929–1958, 2014.
  * Vinyals & Le (2015) Vinyals, O. and Le, Q. V.  A neural conversational model.  _CoRR_ , abs/1506.05869, 2015.  URL http://arxiv.org/abs/1506.05869.
  * Wales et al. (1998) Wales, D. J., Miller, M. A., and Walsh, T. R.  Archetypal energy landscapes.  _Nature_ , 394(6695):758, 1998.
  * Xiong et al. (2017) Xiong, W., Droppo, J., Huang, X., Seide, F., Seltzer, M. L., Stolcke, A., Yu, D., and Zweig, G.  Toward human parity in conversational speech recognition.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 25(12):2410–2423, Dec 2017.  ISSN 2329-9290.  doi: 10.1109/TASLP.2017.2756440.

##  Appendix A AutoNEB insertion

New pivots are inserted at locations where the loss values resulting from
evaluations rise higher than a certain threshold above the the estimate given
the adjacent pivots, see Figure A.1. More formally, the loss curve between
pivots $i$ and $i+1$ can be approximated by interpolating the pivot values:

$\displaystyle L_{\text{guess}}^{i,i+1}(\alpha)$
$\displaystyle=L(p_{i})(1-\alpha)+L(p_{i+1})\alpha$ where $\alpha\in[0,1]$
interpolates between the pivots. The true loss value a the same position is:
$\displaystyle L^{i,i+1}(\alpha)$
$\displaystyle=L\big{(}p_{i}(1-\alpha)+p_{i+1}\alpha\big{)}.$ Denote the
difference as: $\displaystyle\Delta L^{i,i+1}(\alpha)$
$\displaystyle=L^{i,i+1}(\alpha)-L_{\text{guess}}^{i,i+1}(\alpha)$

If the true loss rises too high above the estimated loss, a new pivot should
be inserted. It is beneficial to first insert pivots at the highest residuum:
Each new pivot requires more expensive gradient evaluations. The deviation
between true loss and estimate is evaluated at discrete positions
$\alpha\in\mathcal{A}\subset(0,1),~{}|\mathcal{A}|<\infty$. The differences
$\Delta L^{i,i+1}(\alpha)$ are normalised to the range of values of
$L(p_{i})$. When this normalised deviation rises above a certain threshold
$\vartheta$, a new pivot is inserted, i.e. insert a pivot between $i$ and
$i+1$ when:

$\displaystyle\vartheta>\frac{\Delta
L^{i,i+1}(\alpha)}{\max_{i}L(p_{i})-\min_{i}L(p_{i})}=:{\Delta
l}^{i,i+1}(\alpha)$ (4)

Only one pivot is inserted per line segment per AutoNEB iteration. If several
$\alpha$ for one line segment fulfil the above condition, only the position
with the highest residuum is chosen. Additionally, the total number of pivots
to insert per iteration is limited so that the highest deviations are
prioritised.

Figure A.1: New items are inserted in each cycle of AutoNEB when the true
energy at an interpolated position between two points rises too high compared
to the interpolated energy. Between $i$ and $i+1$, a new pivot is inserted.
Between $i-1$ and $i$, the difference is small enough that no additional pivot
is needed.

##  Appendix B Quantitative minimum and saddle point losses

Appendix B shows the full list of results. Here, we compare the numbers in
detail to characteristic metrics of a neural network, with error margins below
$10\%$ for all energy and error rate values:

The loss of an untrained network amounts to $-\log(0.1)=2.3$ on CIFAR10 and
$-\log(0.01)=4.6$ on CIFAR100.
The saddle point energies are between $1/3$ to $1/20$ of the initial loss for
the shallow networks (all CNNs and ResNet-8) and _about two orders of
magnitude smaller_ for the deep residual networks.

The test loss at the saddle points of the smallest one-layer CNNs comes close
to the test loss of the minima. The wider and especially deeper the CNN, the
closer the saddle loss approaches the minima. The saddle point energies of the
deep residual networks (not ResNet-8) on CIFAR10 are about one order of
magnitude smaller than the average minimum loss on the test set. On CIFAR100,
the saddle point energies of the ResNets are smaller than a third of the value
on the test set. For the DenseNets, they are at least one order of magnitude
smaller.

The training loss at the saddle points is at most eight times as large as the
training loss of the minima. This ratio, reported as “factor” in Appendix B,
is hard to interpret directly as it can approach zero when the network fits
the data perfectly. Instead, we report that all saddle losses are closer to
the training than the test loss for all but the smallest three basic CNNs. For
all deeper architectures, the saddle loss is much closer to the training than
to the test loss, see Figure 5.

The classification performance does not decrease significantly along the
paths. On the ResNets, the error rises by maximally 0.7% on CIFAR10 and 2.9%
on CIFAR100. For the DenseNets, the error rises by up to 0.4% on CIFAR10 and
1.5% on CIFAR100. These differences are small compared to the error rate at
the minima.

Table B.1:  Quantitative results. “Min.” denotes the average value at the
minima. For the saddle point values (“Sadd.”), the maximum value of each
metric along the local MEPs is computed and the results are averaged. The
“epoch” is measured at the point where the loss falls below the saddle point
loss for the first time. It is noted in bold if it belongs to the third part
of training with learning rate $\gamma=10^{-3}$. Basic CNNs and ResNets are
trained for 136 epochs, DenseNets for 266 epochs. The “factor” is the ratio
between average saddle point and minima loss. The standard deviations of all
values at the minima and saddle are smaller than 10% when averaged over the
instances or over the mini-batches.
|  | Train energy | Test energy | Test error rate [%]
---|---|---|---|---
|  | Min. | Sadd. | Factor | Epoch | Min. | Sadd. | Min. | Sadd. | $\Delta$
dataset | architecture |  |  |  |  |  |  |  |  |
C10+ | CNN-12 | 0.5428 | 0.6381 | 1.2 | 78 | 0.63 | 0.69 | 21.4 | 23.6 | 2.2
| CNN-24 | 0.4403 | 0.5390 | 1.2 | 84 | 0.59 | 0.64 | 19.8 | 21.8 | 2.0
| CNN-36 | 0.3982 | 0.4814 | 1.2 | 91 | 0.57 | 0.61 | 19.0 | 20.8 | 1.8
| CNN-48 | 0.3750 | 0.4331 | 1.2 | 103 | 0.56 | 0.59 | 18.6 | 19.9 | 1.2
| CNN-96 | 0.3324 | 0.3900 | 1.2 | 103 | 0.55 | 0.57 | 17.9 | 19.3 | 1.4
| CNN-48x2 | 0.1402 | 0.1564 | 1.1 | 136 | 0.45 | 0.46 | 13.4 | 14.2 | 0.8
| CNN-48x3 | 0.0918 | 0.1164 | 1.3 | 110 | 0.46 | 0.50 | 13.4 | 15.2 | 1.7
| ResNet-8 | 0.2045 | 0.2086 | 1.0 | 136 | 0.37 | 0.38 | 12.0 | 12.5 | 0.4
| ResNet-20 | 0.0162 | 0.0324 | 2.0 | 104 | 0.36 | 0.38 | 8.5 | 8.9 | 0.5
| ResNet-32 | 0.0057 | 0.0097 | 1.7 | 107 | 0.36 | 0.37 | 7.5 | 7.8 | 0.3
| ResNet-44 | 0.0031 | 0.0060 | 1.9 | 122 | 0.36 | 0.36 | 7.1 | 7.4 | 0.3
| ResNet-56 | 0.0022 | 0.0141 | 6.5 | 85 | 0.35 | 0.36 | 6.9 | 7.4 | 0.5
| DenseNet-40-12 | 0.0008 | 0.0046 | 5.9 | 205 | 0.25 | 0.25 | 5.6 | 6.0 | 0.3
| DenseNet-100-12-BC | 0.0005 | 0.0026 | 4.8 | 205 | 0.21 | 0.22 | 4.9 | 5.1 | 0.2
C100+ | CNN-12 | 1.6167 | 1.9029 | 1.2 | 69 | 2.00 | 2.11 | 51.0 | 54.2 | 3.2
| CNN-24 | 1.3854 | 1.6930 | 1.2 | 70 | 1.90 | 1.99 | 48.2 | 51.5 | 3.3
| CNN-36 | 1.2670 | 1.5801 | 1.2 | 71 | 1.87 | 1.95 | 47.2 | 50.2 | 3.0
| CNN-48 | 1.1977 | 1.5002 | 1.3 | 73 | 1.87 | 1.94 | 46.6 | 49.5 | 2.9
| CNN-96 | 1.0549 | 1.3304 | 1.3 | 82 | 1.85 | 1.91 | 45.6 | 48.4 | 2.8
| CNN-48x2 | 0.6579 | 0.8372 | 1.3 | 91 | 1.71 | 1.73 | 41.0 | 42.6 | 1.6
| CNN-48x3 | 0.4393 | 0.6124 | 1.4 | 91 | 1.88 | 1.89 | 43.7 | 45.5 | 1.8
| ResNet-8 | 1.0894 | 1.1547 | 1.1 | 103 | 1.46 | 1.49 | 39.6 | 40.6 | 1.0
| ResNet-20 | 0.3528 | 0.5442 | 1.5 | 79 | 1.42 | 1.48 | 33.3 | 34.7 | 1.4
| ResNet-32 | 0.1422 | 0.3576 | 2.5 | 77 | 1.53 | 1.57 | 31.5 | 33.7 | 2.2
| ResNet-44 | 0.0753 | 0.2117 | 2.8 | 85 | 1.60 | 1.62 | 30.8 | 32.5 | 1.7
| ResNet-56 | 0.0428 | 0.2978 | 7.0 | 71 | 1.64 | 1.66 | 30.3 | 32.4 | 2.0
| DenseNet-40-12 | 0.0101 | 0.0808 | 8.0 | 166 | 1.30 | 1.31 | 26.3 | 27.7 | 1.4
| DenseNet-100-12-BC | 0.0050 | 0.0223 | 4.4 | 205 | 1.12 | 1.13 | 23.7 | 24.6 | 0.8