# The Lévy Flight of Cities: Analyzing Social-Economical Trajectories with
Auto-Embedding

LFTLinfang Tian  KZKai Zhao  JMYJiaming Yin  HVHuy Vo  WXRWeixiong Rao  School
of Software Engineering, Tongji University, Caoan Road, 201804 Shanghai,
China,
‡Linfang Tian and Kai Zhao contributed equally to the paper  Robinson College
of Business, Georgia State University, Gilmer Street, Atlanta, USA  the City
College of the City University of New York, and the Center for Urban Science
and Progress, New York University, New York, USA

###### Abstract

It has been found that human mobility exhibits random patterns following the
Lévy flight, where human movement contains many short flights and some long
flights, and these flights follow a power-law distribution. In this paper, we
study the social-economical development trajectories of urban cities. We
observe that social-economical movement of cities also exhibit the Lévy flight
characteristics. We collect the social and economical data such as the
population, the number of students, GDP and personal income, etc. from several
cities. Then we map these urban data into the social and economical factors
through a deep-learning embedding method Auto-Encoder. We find that the
social-economical factors of these cities can be fitted approximately as a
movement pattern of a power-law distribution. We use the Stochastic
Multiplicative Processes (SMP) to explain such movement, where in the presence
of a boundary constraint, the SMP leads to a power law distribution. It means
that the social-economical trajectories of cities also follow a Lévy flight
pattern, where some years have large changes in terms of social-economical
development, and many years have little changes.

Lévy Flight,

Movement Trajectories,

Urban Development,

###### keywords:

Research

## Introduction

Urban studies seek to understand and explain regularities observed in the
world’s major urban systems. Cities are complex systems [1, 2, 3, 4, 5, 6, 7,
8] with many people living in and complex relationships among various factors.
Previous works have studied the mobility of people [9] and show that the
movement of human society is statistically random. A lot of studies are about
the rank-order of cities [10, 11, 12, 13, 3, 14], Pareto law [11, 15] and
Zipf’s law [16, 4, 17]. In this paper, we study the development trajectories
of cities to contribute to the sustainability and innovation of cities [2, 18,
19, 20, 18]. This paper will aid policymakers, city planners and government
officials to understand the nature of urban development and design a
sustainable smart cities using computational social science models.

In this paper, we follow the urban dynamics model above and assume that cities
move in two directions [21]: one is economic growth, the other is the
development of social civilization. We study the datasets of four Asian
cities: two in China including Hong Kong and Shanghai, the third is Singapore,
the fourth is Tokyo, Japan. (see Table 1) All of them have economic factors
such as GDP, GDP of secondary industry and GDP of tertiary industry, and
social factors such as population, education and publication. It covers the
most commonly used data types for measuring urban development [10]. Firstly,
it is clear that the research object is urban mobility [22], namely the change
amount of urban economic and social development, and the change amount of
social and economic factors is obtained. Then, we apply the recently popular
artificial neural network embedding technique, namely Auto-Encoder [23], on
all economic factors to extract a low-dimensional latent vector. Min-max
normalization is performed on the data first, and the same was done on the
data of social factors. Next, we determine the step size distribution of the
city movement. According to Akaike Information Criterion [24], the
distribution model is fitted to get the optimal probability distribution. The
results show that the movement of Hong Kong is more in line with the truncated
power law [25] distribution, Shanghai city and Tokyo move more power law, and
Singapore moves in the pattern of exponential distribution. To the best of our
knowledge, this article is the first work that examines the movement of urban
social-economical developments using computational social science models and
explain the generalization model behind it.

The contribution of this paper is as follows. First, we extract the increment
distribution function of city’s society according to city’s economy. Second,
we demonstrate that log-normal processes [26, 27, 28] in the presence of a
boundary constraint, approximately yields a generative process with a power
law distribution. This result is a step towards explaining the emergence of
Lévy flight patterns in city development. Thirdly, we use the stochastic
multiplicative processes [29, 30, 31, 32, 33, 34] to explain the urban
development trajectory, regarding city as an organism growing theory [35].

## Results

Power-law fit for city trajectory flight. First, we draw the social-economical
trajectories (see Figure 1) of cities and get the histograms (see Figure 2) of
walk lengths. We fit the walk length distribution (see Figure 3) of the
Shanghai city, the Hong Kong City, Singapore and the Tokyo city. We fit
truncated power law [9], log-normal, power law [30, 26, 36, 25, 37], and
exponential distribution [38]. (see Table 2) Then use Akaike weights (see
Table 3) to choose the best fitted distribution. We find that the urban
development step size of Hong Kong fits Truncated power-law distribution with
$\alpha=1.3547$, and the walk distributions of the other three cities fit
Power-law distributions. The exponent $\alpha$ is 2.2829 for Shanghai, 2.6075
for Singapore and 2.6016 for Tokyo. Assuming that urban development satisfy
the stochastic multiplicative processes, we draw the walk length change rate
(see Figure 4) and logarithm of change rate (see Figure 5). The deducted
exponents $\alpha$ by SMP are similar to those of the fitted values of
$\alpha$. (see Table 4)

Mechanisms behind the Power law pattern. A city should be considered an ever
changing organism instead of a static one. At each step $t$, the organism may
grow or shrink [2], according to a random variable $R_{t}$, so that the change
of the city $l_{t}=r_{t-1}l_{t-1}$. This is stochastic multiplicative
processes [31] $l_{t}=r_{t}r_{t-1}...r_{1}l_{0}$. The idea is that the random
growth of an organism is expressed as a percentage of its current increment,
and is independent of its current actual size. Then we find

$\displaystyle\ln l_{t}$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{t}\ln
r_{i}+\ln l_{0}$ (1)

Assuming the random variables $\ln R_{i}$ satisfy independent and identical
distributions with mean $v$ and variance $D$, the Central Limit Theorem says
that $\ln L_{t}=\sum_{i=1}^{t}\ln R_{i}+\ln l_{0}$ converges to a normal
distribution with mean $vt$ and variance $Dt$ for sufficiently large $t$,
which means $L_{t}$ converges to a log-normal distribution. In this paper, we
use Kolmogorov-Smirnov test to verify that all the datasets $lnr$ of four
cities can be reasonably assumed satisfy normal distributions (see Figure 5
and Table 5). Note here that $l_{t}$ is the length of the flight between time
$t-1$ and time $t$. The probability density function of the flight length with
the same change variable is log-normal.

$\displaystyle f(l_{t})$ $\displaystyle=$ $\displaystyle\frac{1}{\sqrt{2\pi
Dt}}\frac{1}{l_{t}}exp\left[-\frac{1}{2Dt}(\ln l_{t}-vt)^{2}\right]$ (2)
$\displaystyle=$ $\displaystyle\frac{1}{\sqrt{2\pi
Dt}}l_{t}^{-1+\frac{v}{D}}exp\left[-\frac{1}{2Dt}(\ln^{2}l_{t}+v^{2}t^{2})\right]$

Given

$f(l_{t})=\frac{1}{l_{t}\sqrt{2\pi Dt}}exp[-\frac{(\ln l_{t}-vt)^{2}}{2Dt}]$
$=\frac{1}{l_{t}\sqrt{2\pi Dt}}exp[-\frac{(\ln l_{t})^{2}-2vt\ln
l_{t}+v^{2}t^{2}}{2Dt}]$ $=\frac{1}{l_{t}\sqrt{2\pi Dt}}exp[-\frac{(\ln
l_{t})^{2}+v^{2}t^{2}}{2Dt}]exp(\frac{v\ln l_{t}}{D})$

$=\frac{1}{l_{t}\sqrt{2\pi Dt}}l_{t}^{\frac{v}{D}}exp[-\frac{(\ln
l_{t})^{2}+v^{2}t^{2}}{2Dt}]$

$=\frac{1}{\sqrt{2\pi Dt}}l_{t}^{-1+\frac{v}{D}}exp[-\frac{(\ln
l_{t})^{2}+v^{2}t^{2}}{2Dt}]$

This form shows that the log-normal distribution can be mistaken for an
apparent power law. If $\sigma\to\infty$, then $\frac{(\ln l_{t})^{2}}{2Dt}\to
0$.

$f(l_{t})\to\frac{1}{\sqrt{2\pi
Dt}}exp[-\frac{v^{2}t}{2D}]l_{t}^{-1+\frac{v}{D}}\to Cl_{t}^{\alpha}$

The Probability Density Function of log-normal distribution is
indistinguishable from that of power law distribution
$f(l_{t})=Cl_{t}^{-\alpha}$, where $1<\alpha\leq 3$.

If there exists a lower bound $l_{min}$,

$l_{t}=max(l_{min},r_{t-1}l_{t-1})$

then $L_{t}$ converges to a power law distribution, log-normal easily pushed
to a power law model.

Here the $v$ and the $D$ are the normalized mean and variance of $\ln R$.

If there exists a lower bound $l_{min}$, such that
$l_{t}=max(l_{min},r_{t-1}l_{t-1})$, then the random variable $L_{t}$
converges to a power law distribution, log-normal easily pushed to a power law
model.

## Discussion

Previous research suggests that power laws widely exist in city population,
financial markets and city-size [11, 14]. However, the rank-size distribution
between cities [13] is mostly static, The dynamic urban power-law distribution
focuses on the change of specific indicators over time, while the systematic
change [1] among urban factors has not been studied. By using a recently
popular neural network embedding technique to reduce the dimension of urban
factor data-sets into two dimensions: economy and society, we explore the city
development trajectory of Hong kong, Shanghai, Singapore and Tokyo. The urban
development of Hong Kong tends to be truncated power law distribution. This is
probably because the rapid development of China’s reform and opening up has
weakened Hong Kong’s status as an important city in Southeast Asia, and Hong
Kong is no longer the uniquely preferred city in the allocation of various
resources in China.

## Methods

Data Sets. We collected the official data-sets of Hong kong (see Table 6),
Shanghai (see Table 7), Singapore (see Table 8) and Tokyo (see Table 9) in our
work, The data-sets of the four cities were collated and matched. Using the
embedding technique to reduce the dimensions of those data-sets into two
dimensions: economy and society. Then, we draw the urban development
trajectory (see Figure 1) with economy as $x$-coordinates and society as
$y$-coordinate. we extract the following information from the graph: flight
lengths.

Obtaining Flight Length of each factor. To the best of our knowledge, this
article is the first work that examines the flight length distribution of
urban development. Firstly, we get raw data of each year’s flight length for
each factor. The GDP factor ranges from dozens to thousands, while Proportion
of industry ranges between 0 and 4, the range of values of raw data varies
widely. To avoid the flight length being governed by large value data, we use
min-max normalization to scale the range of each factor in [0, 1].

Obtaining Flight length of urban development by Embedding. The Manifold
Hypothesis states that real-world high-dimensional data lie on low-dimensional
manifolds embedded within the high-dimensional space. In this paper, we try to
get embedding layer through training Auto-encoder (AE), which is a type of
artificial neural network. Firstly, we classifies the data into two classes,
for example, regarding GDP, per capita GDP and primary GDP as economic
variables, regarding population and General higher education as social
variables. Secondly, we use min-max scaling to make sure variables that are
measured at different scales contribute equally to the model fitting. Thirdly,
in the AE, the input feature,the dataset of economic variables or social
variables, is transformed into one latent space with the encoder and then
reconstructed from latent space with decoder. The encoder is used as a
dimensionality reducer. To train this AE, an Adam algorithm was applied as an
optimizer and mean square error (MSE) as a loss function. We use two-layer
fully connected networks as the encoder and decoder, and the loss function is

$\displaystyle\mathcal{L}(\textbf{x},\textbf{x}^{\prime})$ $\displaystyle=$
$\displaystyle\left\|\textbf{x}-\textbf{x}^{\prime}\right\|^{2}$ (3)
$\displaystyle=$ $\displaystyle\left\|\textbf{x}-f(h(\textbf{x}))\right\|^{2}$

where $\textbf{x}\in\mathbb{R}^{n}$ is the input feature of one year and $n$
is the number of variables. The data from $m$ years construct $m$ training
samples. $\textbf{x}^{\prime}$ is the output of the decoder. The computation
of the encoder and decoder is defined as

$\displaystyle h(\textbf{x})$ $\displaystyle=$
$\displaystyle\sigma(W_{2}\sigma(W_{1}\textbf{x}+b_{1})+b_{2}),$
$\displaystyle f(\textbf{y})$ $\displaystyle=$
$\displaystyle\sigma^{\prime}(W_{2}^{\prime}\sigma^{\prime}(W_{1}^{\prime}\textbf{y}+b_{1}^{\prime})+b_{2}^{\prime})$
(4)

where
$W_{1},W_{2},W_{1}^{\prime},W_{2}^{\prime},b_{1},b_{2},b_{1}^{\prime},b_{2}^{\prime}$
are learnable parameters of the network, and $\sigma,\sigma^{\prime}$ are the
activation functions. We train the AE by minimizing the MSE of the input
feature and the output of the decoder. And the output of the encoder
$h(\mathbf{x})$ is the embedding of the original input.

Identifying the Scale Range. To fit a heavy tailed distribution such as a
power law distribution, we need to determine what portion of the data to fit
$x_{min}$ and the scaling parameter $\alpha$. We use the methods from [39] to
determine $x_{min}$ and $\alpha$. We create a power law fit starting from each
value in the dataset. Then we select the one that results in the minimal
Kolmogorov-Smirnov distance between the data and the fit, as the optimal value
of $x_{min}$. After that, the scaling parameter $\alpha$ in the power law
distribution is given by

$\displaystyle\alpha$ $\displaystyle=$ $\displaystyle
1+n\left(\sum_{i=1}^{n}\ln\frac{x_{i}}{x_{min}}\right)^{-1}$ (5)

where $x_{i}$ are the observed values of $x_{i}>x_{min}$ and $n$ is the number
of samples.

Exponential transformation The probability density function of exponential
distribution can be transformed into power law distribution. Let $X$ be an
exponential random variable whose probability density function is given by
$P(X=x)=\lambda e^{-\lambda x},\lambda>0,x>0$, then the cumulative probability
function is given by

$\displaystyle P(X\leq x)$ $\displaystyle=$ $\displaystyle\int_{0}^{x}\lambda
e^{-\lambda t}dt$ (6) $\displaystyle=$ $\displaystyle 1-e^{-\lambda
x},\lambda>0,x>0$

and let $Y$ be the random variable obtained through the transformation
$Y=ke^{X}$, $k>0$, we can express the cumulative density function of $Y$ in
terms of the cumulative density function of $X$ as

$\displaystyle P(Y\leq y)$ $\displaystyle=$ $\displaystyle P(ke^{X}\leq y)$
$\displaystyle=$ $\displaystyle P\left[X\leq\ln(\frac{y}{k})\right]$
$\displaystyle=$ $\displaystyle 1-e^{-\lambda\ln(\frac{y}{k})}$
$\displaystyle=$ $\displaystyle 1-(\frac{y}{k})^{-\lambda}$ $\displaystyle=$
$\displaystyle 1-k^{\lambda}y^{-\lambda}$ $\displaystyle P(Y=y)$
$\displaystyle=$ $\displaystyle\lambda k^{\lambda}y^{-(1+\lambda)}$ (7)

which corresponds to the Probability Density Function of the Power-law
distribution with shape factor $\alpha=1+\lambda$.

Akaike weights. We use Akaike weights to choose the best fitted distribution.
An Akaike weight is a normalized distribution selection criterion. Its value
is between 0 and 1. A larger value indicates a better fitted distribution.

Akaike’s information criterion (AIC) is used in combination with Maximum
likelihood estimation (MLE). MLE finds an estimator of $\hat{\theta}$ that
maximizes the likelihood function $L(\hat{\theta}|data)$ of one distribution.
AIC is used to describe the best fitting one among all fitted distributions,

$\displaystyle AIC$ $\displaystyle=$
$\displaystyle-2log\left(L(\hat{\theta}|data)\right)+2K.$ (8)

Here $K$ is the number of estimable parameters in the approximating model.

After determining the AIC value of each fitted distribution, we normalize
these values as follows. First of all, we extract the difference between
different AIC values called $\Delta_{i}$,

$\displaystyle\Delta_{i}$ $\displaystyle=$ $\displaystyle AIC_{i}-AIC_{min}.$
(9)

Then Akaike weights $W_{i}$ are calculated as follows,

$\displaystyle W_{i}$ $\displaystyle=$
$\displaystyle\frac{exp(-\Delta_{i}/2)}{\sum_{r=1}^{R}exp(-\Delta_{i}/2)}.$
(10)

The statistics can be see in Table 3.

A List of abbreviations

HK: Hong Kong

SHA: Shanghai

SG: Singapore

TYO: Tokyo

pdf: probability density function

SMP: Stochastic Multiplicative Processes

AE: Auto-encoder

MSE: mean square error

AIC: Akaike’s information criterion

MLE: maximum likelihood estimation

## Availability of data and material

The data can be collected from official websites, which are listed in Table 6,
Table 7, Table 8 and Table 9.

## Funding

This work is partially supported by National Natural Science Foundation of
China (Grant No. 61972286).

## Competing interests

The authors declare that they have no competing interests.

## Author’s contributions

Weixiong Rao and Kai Zhao conceived the experiments, Linfang Tian and Jiamin
Yin conducted the experiments, Linfang Tian analysed the results. All authors
reviewed the manuscript.

## Acknowledgements

Not applicable.

## References

  * [1] Chronéer, D., Ståhlbröst, A., Habibipour, A.: Urban living labs: Towards an integrated understanding of their key components. Technology Innovation Management Review 9(3), 50–62 (2019)
  * [2] Slach, O., Bosák, V., Krtička, L., Nováček, A., Rumpel, P.: Urban shrinkage and sustainability: Assessing the nexus between population density, urban structures and urban sustainability. Sustainability 11(15), 4142 (2019)
  * [3] Frick, S.A., Rodríguez-Pose, A.: Big or small cities? on city size and economic growth. Growth and Change 49(1), 4–32 (2018)
  * [4] Jiao, L., Xu, Z., Xu, G., Zhao, R., Liu, J., Wang, W.: Assessment of urban land use efficiency in china: A perspective of scaling law. Habitat International 99, 102172 (2020)
  * [5] Alves, L.G., Ribeiro, H.V., Rodrigues, F.A.: Crime prediction through urban metrics and statistical learning. Physica A: Statistical Mechanics and its Applications 505, 435–443 (2018)
  * [6] Ozdemir, O., et al.: Distributional effects of human capital in advanced economies: Dynamics of economic globalization. Business and Economics Research Journal 11(3), 591–607 (2020)
  * [7] Topirceanu, A., Udrescu, M., Marculescu, R.: Weighted betweenness preferential attachment: A new mechanism explaining social network formation and evolution. Scientific reports 8(1), 1–14 (2018)
  * [8] Beare, B.K., Toda, A.A.: On the emergence of a power law in the distribution of covid-19 cases. Physica D: Nonlinear Phenomena 412, 132649 (2020)
  * [9] Corral, Á., Udina, F., Arcaute, E.: Truncated lognormal distributions and scaling in the size of naturally defined population clusters. Physical Review E 101(4), 042312 (2020)
  * [10] González-Val, R.: The spanish spatial city size distribution. Environment and Planning B: Urban Analytics and City Science, 2399808320941860 (2020)
  * [11] Luckstead, J., Devadoss, S.: Pareto tails and lognormal body of us cities size distribution. Physica A: Statistical Mechanics and its Applications 465, 573–578 (2017)
  * [12] Luckstead, J., Devadoss, S., Danforth, D.: The size distributions of all indian cities. Physica A: Statistical Mechanics and its Applications 474, 237–249 (2017)
  * [13] Wu, H., Levinson, D., Sarkar, S.: How transit scaling shapes cities. Nature Sustainability 2(12), 1142–1148 (2019)
  * [14] Bee, M., Riccaboni, M., Schiavo, S.: Distribution of city size: Gibrat, pareto, zipf. The Mathematics of Urban Morphology, 77 (2019)
  * [15] Toda, A.A.: A note on the size distribution of consumption: More double pareto than lognormal. Macroeconomic Dynamics 21(6), 1508–1518 (2017)
  * [16] Wei, J., Zhang, J., Cai, B., Wang, K., Liang, S., Geng, Y.: Characteristics of carbon dioxide emissions in response to local development: Empirical explanation of zipf’s law in chinese cities. Science of The Total Environment 757, 143912 (2021)
  * [17] Sun, X., Yuan, O., Xu, Z., Yin, Y., Liu, Q., Wu, L.: Did zipf’s law hold for chinese cities and why? evidence from multi-source data. Land Use Policy 106, 105460 (2021)
  * [18] Bibri, S.E.: Big data science and analytics for smart sustainable urbanism. Unprecedented Paradigmatic Shifts and Practical Advancements; Springer: Berlin, Germany (2019)
  * [19] Visvizi, A., Lytras, M.D., Damiani, E., Mathkour, H.: Policy making for smart cities: Innovation and social inclusive economic growth for sustainability. Journal of Science and Technology Policy Management (2018)
  * [20] Durán-Sánchez, A., del Río-Rama, M.C., Sereno-Ramírez, A., Bredis, K., et al.: Sustainability and quality of life in smart cities: Analysis of scientific production. Innovation, Technology, and Knowledge Management, 159–181 (2017)
  * [21] Bharath, H., Chandan, M., Vinay, S., Ramachandra, T.: Modelling urban dynamics in rapidly urbanising indian cities. The Egyptian Journal of Remote Sensing and Space Science 21(3), 201–210 (2018)
  * [22] Jiang, R., Song, X., Fan, Z., Xia, T., Chen, Q., Miyazawa, S., Shibasaki, R.: Deepurbanmomentum: An online deep-learning system for short-term urban mobility prediction. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32 (2018)
  * [23] Bengio, Y., Lamblin, P., Popovici, D., Larochelle, H.: Greedy layer-wise training of deep network. Advances in Neural Information Processing Systems 19, 153–160 (2007)
  * [24] Sakamoto, Y., Ishiguro, M., Kitagawa, G.: Akaike information criterion statistics. Dordrecht, The Netherlands: D. Reidel 81(10.5555), 26853 (1986)
  * [25] Chen, J., Shiyomi, M.: A power law model for analyzing spatial patterns of vegetation abundance in terms of cover, biomass, density, and occurrence: derivation of a common rule. Journal of plant research 132(4), 481–497 (2019)
  * [26] Feng, M., Deng, L.-J., Chen, F., Perc, M., Kurths, J.: The accumulative law and its probability model: an extension of the pareto distribution and the log-normal distribution. Proceedings of the Royal Society A 476(2237), 20200019 (2020)
  * [27] Montebruno, P., Bennett, R.J., Van Lieshout, C., Smith, H.: A tale of two tails: Do power law and lognormal models fit firm-size distributions in the mid-victorian era? Physica A: Statistical Mechanics and its Applications 523, 858–875 (2019)
  * [28] Newberry, M.G., Savage, V.M.: Self-similar processes follow a power law in discrete logarithmic space. Physical review letters 122(15), 158303 (2019)
  * [29] Sornette, D., Cont, R.: Convergent multiplicative processes repelled from zero: power laws and truncated power laws. Journal de Physique I 7(3), 431–444 (1997)
  * [30] Mitzenmacher, M.: A brief history of generative models for power law and lognormal distributions. Internet mathematics 1(2), 226–251 (2004)
  * [31] Guerrero, F.G., Garcia-Baños, A.: Multiplicative processes as a source of fat-tail distributions. Heliyon 6(7), 04266 (2020)
  * [32] Hodgkinson, L., Mahoney, M.W.: Multiplicative noise and heavy tails in stochastic optimization (2020)
  * [33] Zanette, D.H., Manrubia, S.: Fat tails and black swans: Exact results for multiplicative processes with resets. Chaos: An Interdisciplinary Journal of Nonlinear Science 30(3), 033104 (2020)
  * [34] Fenner, T., Levene, M., Loizou, G.: A multiplicative process for generating the rank-order distribution of uk election results. Quality & Quantity 52(3), 1069–1079 (2018)
  * [35] Shultz, A.J., Adams, B.J., Bell, K.C., Ludt, W.B., Pauly, G.B., Vendetti, J.E.: Natural history collections are critical resources for contemporary and future studies of urban evolution. Evolutionary applications 14(1), 233–247 (2021)
  * [36] Sakiyama, T.: A power law network in an evolutionary hawk–dove game. Chaos, Solitons & Fractals 146, 110932 (2021)
  * [37] Pang, G., Taqqu, M.S.: Nonstationary self-similar gaussian processes as scaling limits of power-law shot noise processes and generalizations of fractional brownian motion. High Frequency 2(2), 95–112 (2019)
  * [38] Miyaguchi, T., Uneyama, T., Akimoto, T.: Brownian motion with alternately fluctuating diffusivity: stretched-exponential and power-law relaxation. Physical Review E 100(1), 012116 (2019)
  * [39] Clauset, A., Shalizi, C.R., Newman, M.E.: Power-law distributions in empirical data. SIAM review 51(4), 661–703 (2009)

## Figures and Tables

(a) HK Auto-Encoder

(b) SHA Auto-Encoder

(c) SG Auto-encoder

(d) TYO Auto-Encoder

Figure 1: Auto-Encoder The economical and social trajectory of urban
development.As can be seen from the figure(a), before the opening up of the
Pudong District in 1990, the development step size of Shanghai was relatively
small.The 2010 Shanghai World Expo has led to a rapid economic development. As
can be seen from the figure(b), after Hong Kong’s return to China in 1997, it
enjoyed social and economical stability and prosperity, and successfully
fended off the Asian financial crisis in 1998. After 2010, Hong Kong’s
economic and social development was sluggish.

(a) HK histogram

(b) SHA histogram

(c) SG histogram

(d) TYO histogram

Figure 2: Histogram of flight length.As can be seen from both the figure(a),
(b), (c) and (d), all of the histograms are positive skewed. The statistical
analysis of the step size of the random walk shows obvious ”heavy tail”
feature, which satisfies the walking characteristics of frequent short-
distance walk and occasional long-distance jump.

(a) HK Truncated power-law (b) SHA Power-law (c) SG Exponential (d) TYO Power-
law

Figure 3: Fitted distributions. Hong Kong has experienced rapid development
and sharp decline. The urban development step size is relatively rich, with
more long-distance jump. The fitted Truncated power-law distribution has a
thicker tail, with alpha 1.3547. The development step size of Shanghai has
more short-distance walk and less long-distance jump. It is still in a stable
development period. The $\alpha$ of the fitted Power-law distribution is
2.2829. Singapore has been developing with relatively constant multiplicative
factor, the fitted Exponential distribution with $\lambda=1.6075$. With the
Exponential Transformation, the exponential distribution can deducted to
Power-law distribution with $\alpha=1+\lambda=2.6075$. Tokyo has been
developing relatively earlier than Shanghai, the fitted Power-law distribution
has a larger $\alpha$ 2.6016.

(a) HK r value

(b) SHA r value

(c) SG r value

(d) TYO r value

Figure 4: The relative change rates. The change rate is defined as the
relative change of length between two consecutive flights. From these figures
we observe that the change rate are uncorrelated from one time interval to the
other.

(a) HK $\ln r$ value

(b) SHA $\ln r$ value

(c) SG $\ln r$ value

(d) TYO $\ln r$ value

Figure 5: $\ln r$ of four cities Table 1: The analysis of Hongkong, Shanghai, Singapore and Tokyo Datasets Class | Description | HK | SHA | SG | TYO
---|---|---|---|---|---
Economy | GDP | 1981-2019 | 1978-2018 | 1960-2019 | 1968-2019
| Primary industry | 1981-2019 | 1978-2018 | NA | NA
| Secondary industry | 1981-2019 | 1978-2018 | 1960-2019 | NA
| Tertiary industry | 1981-2019 | 1978-2018 | 1960-2019 | NA
| Share of Primary industry | 1981-2019 | 1978-2018 | NA | NA
| Share of Secondary industry | 1981-2019 | 1978-2018 | 1960-2019 | NA
| Share of Tertiary industry | 1981-2019 | 1978-2018 | 1960-2019 | NA
| Per capita GDP | 1981-2019 | 1978-2018 | NA | NA
| Government revenue | 1981-2019 | 1978-2018 | NA | NA
| Government expenditure | 1981-2019 | 1978-2018 | 1960-2019 | NA
| Personal income | NA | NA | NA | 1960-2019
| Original insurance income | NA | 1978-2018 | NA | NA
| Original insurance pays out | NA | 1978-2018 | NA | NA
| Total fixed asset investment | NA | 1978-2018 | 1960-2019 | NA
| Industry | NA | 1978-2018 | 1960-2019 | 1968-2019
| GDP per capita(Dollar) | NA | 1978-2018 | NA | NA
| Proportion of industry | NA | 1978-2018 | 1960-2019 | NA
| Gross agricultural production | NA | 1978-2018 | NA | NA
| Gross industrial production | NA | 1978-2018 | 1960-2019 | 1968-2019
Society | Population | 1981-2019 | 1978-2018 | 1960-2019 | 1968-2019
| Labor | NA | NA | NA | 1968-2019
| General Tertiary education | 1981-2019 | 1978-2018 | 1960-2019 | 1968-2019
| Ordinary secondary school | 1981-2019 | 1978-2018 | 1960-2019 | 1968-2019
| Ordinary primary school | 1981-2019 | 1978-2018 | 1960-2019 | 1968-2019
| Book print run | NA | 1978-2018 | NA | NA
| Journal print run | NA | 1978-2018 | NA | NA
| Newspaper print run | NA | 1978-2018 | NA | NA
Table 2: Fitted distributions. With $1<\alpha\leq 3$, the Power-law distribution has infinite variance. It has infinite mean as $1<\alpha\leq 2$ and finite mean as $2<\alpha\leq 3$. Distribution | Probability density function (pdf)
---|---
Exponential | $\lambda e^{-\lambda x}$
Power-law | $Cx^{-\alpha}$
Lognormal | $\frac{1}{x\sigma\sqrt{2\pi}}exp[-\frac{(\ln(x)-\mu)^{2}}{2\sigma^{2}}]$
Truncated power-law | $Cx^{-\alpha}e^{-\gamma x}$
Table 3: Akaike weights of fitted distributions in the four cities datasets. Cities | Exponential | Power-law | Lognormal | Truncated Power-law
---|---|---|---|---
HK | 0.1979 | 0.2568 | 0.2226 | 0.3227
SHA | 0.0401 | 0.4603 | 0.2163 | 0.2814
SG | 0.6717 | 0.0014 | 0.1283 | 0.1985
TYO | 0.1594 | 0.4132 | 0.1979 | 0.2295
Table 4: The calculated and estimated parameters for consecutive flights length in the four cities datasets, with $\ln R_{i}$ taken in the interval [0.48, 1.48][29]. The mean is noted as $v^{\prime}$, and variance is $D^{\prime}$, $\hat{\alpha}$ is calculated, and $\alpha$ is the fitted exponent. Here the walk lengths of Hong kong is fitted Truncated power-law rather than Power-law distribution. Cities | $l_{min}$ | $v^{\prime}$ | $D^{\prime}$ | $v^{\prime}/D^{\prime}$ | $\hat{\alpha}$ | $\alpha$
---|---|---|---|---|---|---
HK* | 0.0752 | -0.1904 | 0.1443 | -1.3200 | 2.3200 | 1.3547
SHA | 0.0216 | -0.1010 | 0.0751 | -1.3453 | 2.3453 | 2.2829
SG | 0.0262 | -0.1310 | 0.1145 | -1.1445 | 2.1445 | 2.6075
TYO | 0.0033 | -0.11716 | 0.0875 | -1.3390 | 2.3390 | 2.6016
Table 5: The $p$ value of Kolmogorov-Smirnov test for four city datasets. Cities |  $p$ value
---|---
HK | 0.9804
SHA | 0.9477
SG | 0.7399
TYO | 0.9933
Table 6: The URL of HK dataset. Description | URL
---|---
GDP | https://www.censtatd.gov.hk/sc/web_table.html?id=31#
Per capita GDP | https://www.censtatd.gov.hk/sc/web_table.html?id=31#
Primary industry | https://www.censtatd.gov.hk/sc/web_table.html?id=35#
Secondary industry | https://www.censtatd.gov.hk/sc/web_table.html?id=35#
Tertiary industry | https://www.censtatd.gov.hk/sc/web_table.html?id=35#
Proportion of primary industry | https://www.censtatd.gov.hk/sc/web_table.html?id=36#
Proportion of secondary industry | https://www.censtatd.gov.hk/sc/web_table.html?id=36#
Proportion of tertiary industry | https://www.censtatd.gov.hk/sc/web_table.html?id=36#
Government revenue | https://www.censtatd.gov.hk/sc/web_table.html?id=193#
Government expenditure | https://www.censtatd.gov.hk/sc/web_table.html?id=194#
Population | https://www.censtatd.gov.hk/sc/web_table.html?id=1A#
Labour force | https://www.censtatd.gov.hk/sc/web_table.html?id=6#
Primary school | https://www.censtatd.gov.hk/sc/scode370.html#section6
Secondary school | https://www.censtatd.gov.hk/sc/scode370.html#section6
University | https://www.censtatd.gov.hk/sc/scode370.html#section6
Table 7: The URL of SHA dataset. Description | URL
---|---
GDP | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0401.htm
Primary industry | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0401.htm
Secondary industry | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0401.htm
Tertiary industry | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0401.htm
Industry | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0401.htm
General public budget revenue | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0501.htm
General public budget expenditure | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0501.htm
Proportion of primary industry | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0404.htm
Proportion of Secondary industry | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0404.htm
Proportion of Tertiary industry | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0404.htm
Proportion of industry | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0404.htm
Total fixed asset investment | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0701.htm
General public budget revenue | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0501.htm
General public budget expenditure | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0501.htm
Gross agricultural production | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C1201.htm
Gross industrial production | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C1301.htm
Original insurance income | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C1801.htm
Original insurance pays out | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C1801.htm
Resident population at year-end | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0201.htm
Registered population at year-end | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C0201.htm
General higher education | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C2103.htm
Ordinary secondary school | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C2103.htm
Ordinary primary school | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C2103.htm
Book print run | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C2316.htm
Journal print run | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C2317.htm
Newspaper print run | http://tjj.sh.gov.cn/tjnj/nj20.htm?d1=2020tjnj/C2318.htm
Table 8: The URL of SG dataset. Description | URL
---|---
GDP | https://tablebuilder.singstat.gov.sg/table/TS/M015241
Goods Producing Industries | https://tablebuilder.singstat.gov.sg/table/TS/M015241
Services Producing Industries | https://tablebuilder.singstat.gov.sg/table/TS/M015241
Goods Proportioin | https://tablebuilder.singstat.gov.sg/table/TS/M015241
Services Proportion | https://tablebuilder.singstat.gov.sg/table/TS/M015241
Government Consumption | https://tablebuilder.singstat.gov.sg/table/TS/M015241
Gross Fixed Capital Formation | https://tablebuilder.singstat.gov.sg/table/TS/M015051
Total Population | https://tablebuilder.singstat.gov.sg/table/TS/M810001#!
Government Expenditure On Edu | https://tablebuilder.singstat.gov.sg/table/TS/M850011
Primary Schools | https://tablebuilder.singstat.gov.sg/table/TS/M850011
Secondary Schools | https://tablebuilder.singstat.gov.sg/table/TS/M850011
Tertiary | https://tablebuilder.singstat.gov.sg/table/TS/M850011
Literacy Rate | https://tablebuilder.singstat.gov.sg/table/TS/M850001
Table 9: The URL of TYO dataset. Description | URL
---|---
Loans | https://www.toukei.metro.tokyo.lg.jp/tnenkan/2019/tn19q3i015.htm
Manufactured goods | https://www.toukei.metro.tokyo.lg.jp/tnenkan/2019/tn19q3i016.htm
GDP | https://www.toukei.metro.tokyo.lg.jp/tnenkan/2019/tn19q3i016.htm
Prefectural income | https://www.toukei.metro.tokyo.lg.jp/tnenkan/2019/tn19q3i016.htm
Population | https://www.toukei.metro.tokyo.lg.jp/tnenkan/2019/tn19q3i002.htm
Labor | https://www.toukei.metro.tokyo.lg.jp/tnenkan/2019/tn19q3i002.htm
Children and students | https://www.toukei.metro.tokyo.lg.jp/tnenkan/2019/tn19q3i017.htm
Elementary schools | https://www.toukei.metro.tokyo.lg.jp/tnenkan/2019/tn19q3i017.htm
Junior secondary | https://www.toukei.metro.tokyo.lg.jp/tnenkan/2019/tn19q3i017.htm
Senior secondary | https://www.toukei.metro.tokyo.lg.jp/tnenkan/2019/tn19q3i017.htm
Universities | https://www.toukei.metro.tokyo.lg.jp/tnenkan/2019/tn19q3i017.htm


# Input Compression with Positional Consistency for Efficient Training and
Inference of Transformer Neural Networks

Amrit Nagarajan
School of ECE
Purdue University
<EMAIL_ADDRESS>Anand Raghunathan
School of ECE
Purdue University
<EMAIL_ADDRESS>
###### Abstract

Transformers have rapidly increased in popularity in recent years, achieving
state-of-the-art performance in processing text, images, audio and video.
However, Transformers present large computational requirements for both
training and inference, and are prone to overfitting during training. To
address these challenges, we present Input Compression with Positional
Consistency (ICPC), a new data augmentation method that, unlike prior
augmentation techniques, simultaneously improves both generalization and
training efficiency. ICPC applies varying levels of compression to each
training sample in each epoch. This leads to smaller input sequences being
processed by the Transformer, and hence faster training, while also
alleviating overfitting by presenting each input with different compression
levels. We introduce a consistency-aware position selection method in ICPC
that enables accurate processing of compressed inputs without any changes to
the underlying Transformer architecture. We detail compression-based
augmentation methods for four different modalities – insignificant word
pruning for text, resolution modulation for images, spatio-temporal resolution
modulation for videos, and spectogram size modulation for audio. ICPC also
enables efficient variable-effort inference, where samples are first inferred
at high compression levels, and progressively re-evaluated with lower
compression for more challenging inputs. On 9 diverse tasks spanning 4
different modalities, ICPC improves accuracy by up to 1%, while also
accelerating training and inference by up to 2.9$\times$ and 2.6$\times$,
respectively. Code is available at https://github.com/amrnag/ICPC.

##  1 Introduction

Transformers have recently emerged as the state-of-the-art neural network
architecture for machine learning tasks involving text, images, video and
audio. Remarkably, identical or near-identical Transformer backbones can be
used to create high-performance models across a wide range of input modalities
[4, 5, 16, 6]. This is achieved by simply adding a suitable encoding layer
which converts the input into a set of embedding vectors, and adds a
positional embedding to each vector, thereby outputting a sequence that can be
processed by the Transformer (Fig. 1). These advantages however come at a
cost: Transformers are orders-of-magnitude larger, and hence, more compute-
intensive during both training and inference compared to their predecessors
such as Convolutional Neural Networks (CNNs).

Figure 1: Transformers for different modalities. Similar backbone models are
used for all modalities, but different pre-processing steps are necessary to
generate embedding vectors from inputs of different modalities.

The number of embedding vectors generated from an input (Fig. 1) is the
primary factor that determines the computational effort expended by the
Transformer. In particular, the computational complexity of self-attention
scales quadratically, while all other operations performed by the Transformer
scale linearly with number of embedding vectors. We find that the number of
embedding vectors generated from an input is directly proportional to the size
of the input for all modalities (Fig. 2). For instance, the number of
embedding vectors generated from a given text sequence is directly
proportional to the number of words in the sequence. On the other hand, the
resolution of an image determines the number of embedding vectors generated
from it. Similarly, the number of embedding vectors generated from a video
depends on the number of frames and the resolution of each frame. Finally, the
number of embedding vectors generated from an audio input depends on the
number of time steps and the number of frequency banks used to represent the
signal at each time step. In addition to the computational challenges of
training Transformers, finding sufficient amounts of data for training them
can also be challenging. Transformers are highly susceptible to overfitting
for small datasets, as evidenced by the consistent increase in generalization
performance with increasing training dataset size [12].

We present Input Compression with Positional Consistency (ICPC), a new
augmentation method that simultaneously addresses the efficiency and
overfitting challenges of training Transformers. ICPC creates augmented views
of each training sample by applying varying levels of compression to it in
each epoch. Compression reduces the number of embedding vectors generated from
each sample, thereby accelerating training. In contrast, current augmentation
methods (such as rotation, translation, CutMix [28], mixup [29], AugMix [11],
Manifold Mixup [21], etc.) are size-preserving, i.e., they do not change the
number of embedding vectors generated per sample.

ICPC utilizes input compression methods for different modalities that take
advantage of their unique characteristics. For text inputs, we propose
insignificant word pruning, which reduces the number of embedding vectors by
pruning a random subset of less important words from an input sequence in each
epoch. For images, we use resolution modulation where images are compressed to
random resolutions in each epoch. For videos, we use spatio-temporal
resolution modulation to reduce both the number of frames and the resolution
of each frame. Finally, for audio signals, we utilize spectogram size
modulation, which randomly varies the number of time intervals that the signal
is divided into, and the number of frequency banks used to represent the
signal in each time interval.

Since Transformers were initially designed to process text sequences (which
can be arbitrarily long), they are inherently capable of processing variable-
length inputs. However, we find that naïvely providing compressed inputs leads
to a large drop in accuracy, especially for non-text inputs, due to incorrect
encoding of positional information. To overcome this challenge, we propose
consistency-aware position selection where the positions associated with each
input embedding vector are chosen so as to preserve consistency with the
original uncompressed input.

ICPC can also be used to improve the inference efficiency of Transformers
through variable-effort inference, wherein samples are first heavily
compressed and processed. Easy samples terminate at this stage, while more
difficult samples are re-evaluated with lower compression, leading to a net
savings in computational effort.

We summarize our main contributions as follows.

  * •

We propose Input Compression with Positional Consistency (ICPC), a new
augmentation method for Transformers that simultaneously improves accuracy and
generalization performance.

  * •

We describe input compression methods for different modalities that reduce the
number of embedding vectors generated for each input.

  * •

We introduce a consistency-aware position selection method to enable ICPC
without any changes to the underlying model architecture.

  * •

We demonstrate that training with ICPC consistently improves both accuracy and
efficiency over prior methods. We also show that ICPC can be used to improve
inference efficiency by modulating computational effort performed based on the
difficulty of the input.

##  2 Data Augmentation through Input Compression

The overarching idea behind ICPC is to compress inputs to achieve dual goals —
computational efficiency and data augmentation. While state-of-the-art
Transformer models for various modalities use similar architectures as their
backbone, they use modality-specific pre-processing steps for encoding the
inputs into sequences of embedding vectors. Hence, we propose input
compression methods for text, images, video and audio, all of which reduce the
number of embedding vectors required to represent a given input (Fig. 2). We
describe these methods in turn below.

Figure 2: Techniques for augmenting data through input compression for
different modalities.

Text: Embedding vectors are generated from text sequences by gathering the
relevant entries for each word in the sequence from an embedding table that
contains entries for all words in the model’s vocabulary (Fig. 1). Thus, the
number of embedding vectors generated from a given sequence is equal to the
number of words in the sequence. We propose insignificant word pruning to
compress text inputs by removing a random subset of less relevant words in
each input sequence in each epoch (Fig. 2). Our procedure for insignificant
word pruning is illustrated in Algorithm 1, lines 1-6. We identify
insignificant words in a given sequence using stopword filters. Stopwords are
words that do not contribute to the meaning of a sentence, but are required to
make them grammatically correct. As a result, pruning stopwords does not
affect the labels associated with sequences, thereby enabling augmentation
without impacting convergence. We first identify the stopwords in every
sequence in the training dataset. Then, the number of stopwords to prune from
each sequence in each epoch is determined by selecting a random number between
0 and the total number of stopwords in the sequence. Finally, we randomly
select and prune the determined number of stopwords from each sequence. In
effect, insignificant word pruning achieves data augmentation by pruning a
different subset of stopwords from the sample in every epoch, thereby ensuring
that the model does not see the same sequences repeatedly over the course of
training. Since pruning stopwords reduces the number of embedding vectors
generated from each sequence, insignificant word pruning also improves
training efficiency.

Images: Embedding vectors are generated from images by first splitting them
into non-overlapping fixed-size regions called patches, and subsequently
extracting an embedding vector from each patch through 2-D convolution.
Therefore, the resolution of an image (height, width) determines the number of
patches generated, which in turn, determines the embedding vectors generated
from the image. We propose resolution modulation for compression-based
augmentation of image data (Fig. 2), illustrated in Algorithm 1, lines 7-11.
We start by choosing two random numbers for each batch, with one number
indicating the height and the other number indicating the width that all
images in the batch will be resized to. Then, all images in the batch are
resized to the chosen (height, width) values through downsampling. We restrict
ourselves to determining resolution at the batch granularity in order to avoid
the padding and ineffectual computations introduced when images in a batch are
not of the same size.

Audio: Audio signals are represented using spectograms, and embedding vectors
are generated by treating the spectogram as a 2-D image and following the
method prescribed for images. The number of embedding vectors generated from a
given audio signal depends on two factors: the width of the spectogram is
determined by the number of time intervals the audio is segmented into (which
we refer to as the sampling rate), and the height of the spectogram is
determined by the number of frequency banks used to represent the signal. We
propose spectogram size modulation for compressing audio inputs (Fig. 2), with
the procedure described in Algorithm 1, lines 20-25. Spectogram size
modulation incorporates both sampling rate modulation and filterbank size
modulation. We randomly select a sampling rate and number of filterbanks for
each batch. Then, each audio sample in the batch is sampled using the selected
sampling rate, and converted to a spectogram with the selected number of
filter banks at each time step. The sampling rate and number of filterbanks
are chosen on a per-batch basis to avoid padding.

Video: Videos are represented as a series of images (or frames) ordered in
time, and embedding vectors are generated by applying the same method
prescribed for images to each frame. Consequently, the number of embedding
vectors generated from a given video depends on two factors: the number of
frames used to represent the video, and the resolution of each frame.
Therefore, two forms of compression are possible in videos: (1) spatial
compression, which involves reducing the resolution of each frame, and (2)
temporal compression, which involves reducing the number of frames. We propose
spatio-temporal resolution modulation for augmenting video samples (Fig. 2),
with the procedure described in Algorithm 1, lines 12-19. For each batch in
each epoch, we select a random number of frames and spatial resolution
(height, width) for each frame. Then, all video samples in the batch are
uniformly sampled to generate the selected number of frames, and each frame is
subsequently rescaled to the selected (height, width) values. The number of
frames and resolution are chosen on a per-batch basis to avoid padding and
ineffectual computations.

1

2 Function  _Insignificant word pruning(_batch_)_:

3 for  _sequence in batch_ do

4 stopwords = identify_stopwords(sequence)

5 num_stopwords_to_prune = random(low=0, high=(length(stopwords)-1)

6 stopwords_to_prune = random_select(stopwords, length=num_stopwords_to_prune)

7 sequence = sequence - stopwords_to_prune

8

9

10

11 Function  _Resolution modulation(_batch, all_valid_heights,
all_valid_widths_)_:

12 batch_height = random_select(all_valid_heights, length=1)

13 batch_width = random_select(all_valid_widths, length=1)

14 for  _image in batch_ do

15 image = resize(image, resolution=(batch_height, batch_width))

16

17

18

19 Function  _Spatio-temporal modulation(_batch, all_valid_heights,
all_valid_widths, all_valid_frame_rates_)_:

20 batch_height = random_select(all_valid_heights, length=1)

21 batch_width = random_select(all_valid_widths, length=1)

22 batch_frame_rate = random_select(all_valid_frame_rates, length=1)

23 for  _video in batch_ do

24 video = generate_frames(video, frame_rate=batch_frame_rate)

25 for  _frame in video_ do

26 frame = resize(frame, resolution=(batch_height, batch_width))

27

28

29

30

31 Function  _Spectogram size modulation(_batch, all_valid_sampling_rates,
all_valid_filterbank_sizes_)_:

32 batch_sampling_rate = random_select(all_valid_frame_rates, length=1)

33 batch_filterbank_size = random_select(all_valid_filterbank_sizes, length=1)

34 for  _audio_signal in batch_ do

35 sampled_audio_signal = sample(audio_signal,
sampling_rate=batch_sampling_rate)

36 spectogram = create_spectogram(sampled_audio_signal,
num_filterbanks=batch_filterbank_size)

37

38

39

Algorithm 1 Data Augmentation through Input Compression for different
modalities

##  3 Consistency-aware position selection: Enabling ICPC in an architecture-
agnostic manner

Transformers are inherently capable of processing variable-length inputs,
i.e., input samples with different numbers of embedding vectors, since they
were originally designed to process text inputs that can be arbitrarily long.
As a result, inputs presented to the Transformer can have different sizes. In
contrast, all inputs presented to CNNs and RNNs are required to be of the same
size, since fully-connected layers used in these models require fixed-size
inputs. However, we find that position embeddings must be carefully selected
to encode inputs whose sizes are smaller than the maximum size supported by
the Transformer. In particular, we find that the relative positions of the
position embeddings selected to encode compressed inputs must be consistent
with the relative positions of vectors generated from the compressed inputs
along all dimensions. Consequently, we propose a consistency-aware position
selection method that finds the correct subset of position embeddings in the
original model for encoding compressed inputs. We describe our position
embedding selection methods for different modalities in turn below.

Figure 3: (a) Consistency-aware position selection for different modalities.
Blue rectangles represent position embeddings, and letters/numbers represent
their positions in the position embedding table. (b) Variable-effort inference
using ICPC.

Figure 4: Impact of position selection scheme on accuracy when processing
compressed inputs. Results are obtained using fine-tuned models downloaded
from the respective repositories. The image model is trained using 224*224
images. The video model is trained using eight 224*224 frames per video. The
audio model is trained using a sampling rate of 16KHz and 128 filterbanks. For
images, we also compare with the ”interpolation” method described in [5] for
fine-tuning at a different resolution than the one used for pre-training.

Text: Text inputs are 1-D arrays of words. Since Transformers were designed to
process variable-length text inputs, they incorporate a position embedding
selection mechanism for inputs that are shorter than the maximum length
supported by the Transformer that is designed to maintain 1-D consistency
between words in the sequence. For an input sequence of length $n$, 1-D
consistency is achieved by selecting the first $n$ entries from the position
embedding table (corresponding to the first $n$ positions in a sequence with
length equal to the maximum length supported by the Transformer), and encoding
the words in the order in which they appear (Fig. 3). For instance, if three
words (A, B, C) appear in that order in a sequence, they are encoded with
embeddings corresponding to the following positions: position(B) = 1 +
position(A), and position(C) = 1 + position(B).

Images: Patches derived from images are arranged into a 1-D stream and fed to
the Transformer (Fig. 1). Here, we find that simply selecting the first $n$
entries from the position embedding table (as done for text) does not
adequately capture the relative positions of patches (Fig. 4). We find that
images must be viewed as 2-D grids of patches for accurately selecting
position embeddings, since the position of a patch relative to other patches
cannot be uniquely determined in 1-D. For instance, the first-$n$ selection
method described above cannot encode the fact that two patches are adjacent to
each other along the y-axis in the 2-D grid. To address this challenge, we
propose a position embedding selection method designed to maintain 2-D
consistency between patches in compressed images (Fig. 3). In particular, if
patch A is adjacent to patch B along the x-axis and adjacent to patch C along
the y-axis in the 2-D grid, we encode these patches with embeddings
corresponding to the following positions – position(B) = 1 + position(A) and
position(C) = width of 2-D grid + position(A) – thereby encoding adjacency
information along both the x- and y-dimensions.

Audio: Audio signals are represented using spectograms. Since spectograms are
treated as 2-D images during pre-processing, the method described above for
encoding images works for encoding patches generated from spectograms also
(Fig. 3, Fig. 4). In particular, if patch A is adjacent to patch B along the
time-axis and adjacent to patch C along the frequency-axis in the 2-D grid, we
encode these patches with embeddings corresponding to the following positions:
position(B) = 1 + position(A) and position(C) = width of 2-D grid +
position(A).

Video: Patches derived from videos are also arranged into a 1-D stream and fed
to the Transformer (Fig. 1), similar to images. However, we find that the
position of each patch relative to other patches can only be accurately
captured in 3-D. In particular, encoding compressed videos with a set of 1-D
consistent position embeddings (as done with text) only captures the relative
positions of patches along the x-axis; adjacency of patches along the y- and
time-axes are not captured. 2-D consistent position embeddings (used for
encoding images) can capture the relative positions of patches along the x-
and y-axes, but not along the time axis (Fig. 4). Consequently, we propose a
position embedding selection method designed to maintain 3-D consistency by
viewing videos as 3-D grids of patches (Fig. 3). If patch A is adjacent to
patch B along the x-axis, adjacent to patch C along the y-axis and adjacent to
patch D along the time-axis in the 3-D grid, our method encodes these patches
with embeddings corresponding to the following positions – position(B) = 1 +
position(A), position(C) = width of 2-D grid representing each frame +
position(A) and position(D) = (width of 2-D grid * height of 2-D grid
representing each frame) + position(A) – thereby encoding adjacency
information along the x- and y-, and time-axes.

##  4 Efficient variable-effort inference using ICPC

When Transformers are deployed for inference, existing methods reshape all
input samples to the same shape. As a result, all inputs are represented using
the same number of embedding vectors, leading to the same amount of compute
time and energy being expended on all samples. However, we observe that many
samples can be accurately processed even when they are heavily compressed
(represented using only a small number of embedding vectors), and hence, these
”easy” samples can be processed at substantially lower computational cost. We
find that this is especially true in models trained with ICPC, since training
with compressed inputs substantially improves resilience to input compression
during inference. Consequently, we propose a variable-effort inference
framework that uses ICPC to modulate the computational effort based on the
difficulty of each sample (Fig 3). When a sample is presented during
inference, it is first heavily compressed and presented to the Transformer.
Only if the Transformer is not confident in predicting the compressed sample
($confidence<T_{c}$), a less compressed version of the sample is presented to
the model. Here, $confidence$ denotes the class probability of the predicted
class after softmax and $T_{c}$ is a hyperparameter that controls the level of
confidence required to terminate execution. We describe our variable-effort
inference strategies for different modalities in the following subsections.

Images, Video and Audio: Images are first inferred at low resolution, and are
subsequently processed at higher resolution only when necessary, i.e., when
the confidence of the Transformer in predicting the low resolution image is
less than the confidence threshold. Similarly, videos are first processed
using small numbers of frames and low frame resolutions. Higher numbers of
frames and resolutions are used only for difficult inputs. Audio signals are
initially sampled with low sampling rates and represented using a small number
of filterbanks. Both quantities are then progressively increased only for
samples that cannot be confidently predicted by the Transformer when
compressed.

Text: Text sequences are first heavily compressed by pruning all stopwords
from each sequence. If the model is not confident in processing the heavily
compressed sequence, the amount of compression applied is reduced. One
approach to reducing compression is to prune a random subset of stopwords from
each sequence, instead of pruning all stopwords. However, we observe that not
all stopwords are equally unimportant. For instance, the word ”an” is a
context-independent stopword, i.e., ”an” is irrelevant irrespective of the
context it appears in. On the other hand, words such as ”beyond” are context-
dependent stopwords, i.e., they are irrelevant in most contexts, but are
meaningful when the relative positions between certain objects is important
for accurately processing the sequence. Based on this observation, we create
an ordered list of stopwords based on their relative significance, which we
call the Word Importance Hierarchy (WIH). The WIH is created by analyzing the
impact of dropping each stopword on the accuracy of a pre-trained model. The
stopwords are then arranged in increasing order of accuracy loss incurred by
their pruning. Subsequently, different compression levels are created during
inference by pruning the first-$n$ stopwords from the WIH from each sequence.
In effect, the use of WIH substantially improves the probability of achieving
high-confidence predictions when processing compressed inputs compared to
random stopword pruning.

##  5 Experiments and Results

We implement ICPC in PyTorch, and perform experiments on 4 NVIDIA A40 GPUs,
each with 48 GB memory. We use a batch size of 1 during inference, similar to
prior works on variable-effort inference [20]. We randomly sample 5% of the
training dataset with class balance, and use this as the validation set for
determining the confidence threshold ($T_{c}$) for variable-effort inference.

Experiments on text: We use the Roberta-Base model [17] along with the
stopword list from NLTK [1]. We create the WIH by testing a pre-trained
Roberta-Base model (downloaded from [26]) on MNLI. During inference, heavy
compression is achieved by pruning all words from the stopword list from each
sequence. Medium compression is achieved by pruning only those stopwords that
lead to a $<=$1% accuracy drop on the pre-trained model.

Experiments on images: We use the ViT-Base-224 [5] model for ImageNet, and the
ViT-Base-384 model [5] for CIFAR10 and CIFAR100 (both models are pre-trained
on ImageNet-21K). During training, the height and width of each image is
randomly chosen from [96, 112, 128, …, 224/384]. Images are resized to
(112*112, 176*176) and (192*192, 304*304) for inference with (high, medium)
compression on ImageNet and CIFAR, respectively.

Experiments on video: We use the UMT-Base-patch16-224 model [16] pre-trained
on Kinetics710. During training, the number of frames is randomly chosen from
[4, 5, 6, 7, 8], and videos are uniformly sampled to generate the selected
number of frames. The height and width of each frame is then randomly chosen
from [96, 112, 128, 144, 160, 176, 192, 208, 224]. Videos are represented
using (5, 7) frames and frames are resized to (112*112, 176*176) for inference
with high and medium compression, respectively.

Experiments on audio: We use the AST model [6] pre-trained on ImageNet for
SpeechCommandsv2, and the AST model pre-trained on AudioSet for ESC50. During
training, the sampling rate is randomly chosen from [8, 9, 10, 11, 12, 13, 14,
15, 16]KHz, and the number of filterbanks is chosen randomly from [65, 75, 85,
95, 105, 115, 125, 128]. Audio signals are sampled at (10, 14)KHz and
represented using (75, 105) filterbanks for inference with high and medium
compression, respectively.

###  5.1 Primary Results

We present results of training and inference with ICPC on classification tasks
spanning multiple modalities in Table 1. For text, we present results on
sentiment analysis (SST-2 [22]) and text categorization (Reuters-21578 [9]).
We present results of image classification on CIFAR-10 [15], CIFAR-100 [15]
and ImageNet [3]. We present results on video action recognition using the
SomethingSomethingV2 [7] and Kinetics400 [13] datasets, and on speech
recognition and environment sound classification using the SpeechCommandsV2
[24] and ESC50 [19] datasets, respectively. We find that using ICPC during
both training and inference improves accuracy by up to 1%, while also
accelerating training and inference by up to 2.9$\times$ and 2.6$\times$,
respectively.

We observe two complementary sources of accuracy improvement: (1) The
additional augmentation from ICPC during training leads to a 0.15% average
accuracy gain across the 9 tasks when all samples are processed without any
compression during inference. (2) Applying ICPC during inference leads to an
additional 0.2% average accuracy gain. The accuracy improvement from using
ICPC for inference is surprising, since it indicates that for a given sample,
the largest possible size is not always optimal. In fact, some inputs are
processed more accurately when they are compressed. We hypothesize that this
is because the pre-processing steps that generate embedding vectors from
inputs can be seen as a form of feature extraction, where each embedding
vector represents some feature(s) of the input. When embedding vectors
generated from compressed inputs capture the salient features of the input
better than the embedding vectors generated from non-compressed inputs, input
compression also improves accuracy. During variable-effort inference with
ICPC, the confidence of the Transformer in predicting a sample can be viewed
as an assessment of the quality of features extracted from the sample. In
effect, our method greedily identifies the ideal compression level for each
input by progressively reducing compression until sufficiently good features
are obtained, thereby simultaneously improving accuracy and efficiency. In
fact, we find that $>$75% of samples have confidence $>$= $T_{c}$ at high
compression, and $<$15% of samples need to be processed with no compression in
all studied tasks.

Table 1: Results of training and inference with Transformers for different
modalities using ICPC. For the baselines, we follow the exact hyperparameter
settings suggested by the authors. ICPC entries are generated by using ICPC
during both training and inference. During training, ICPC is used as an
additional augmentation method (in addition to the augmenters used in the
baseline).

Modality | Dataset | Baseline | ICPC | Training | Inference
---|---|---|---|---|---
Speedup | Speedup
Text | SST-2 | 94.16 | 94.78 | 1.3$\times$ | 1.7$\times$
Reuters | 84.1 | 84.9 | 1.5$\times$ | 1.6$\times$
Image | CIFAR-10 | 98.84 | 99.21 | 2.4$\times$ | 2.2$\times$
CIFAR-100 | 92.36 | 93.31 | 2.3$\times$ | 1.9$\times$
ImageNet | 85.84 | 86.28 | 2.4$\times$ | 1.9$\times$
Video | SomethingSomethingV2 | 70.76 | 71.07 | 2.9$\times$ | 2.6$\times$
Kinetics400 | 87.42 | 87.63 | 2.8$\times$ | 2.2$\times$
Audio | SpeechCommandsV2 | 98.12 | 98.22 | 1.5$\times$ | 1.3$\times$
ESC50 | 95.75 | 95.89 | 1.6$\times$ | 1.3$\times$

###  5.2 Ablation: Evaluation of ICPC as an augmenter

We compare ICPC with MixUp [29], a popular augmentation strategy that is used
for image, video and audio inputs, in Fig. 5. When input compression is not
applied during inference, we find that models trained with ICPC are iso-
accurate to models trained with MixUp (difference in accuracy is $<$0.5% for
all tasks, with ICPC achieving higher accuracy on 5 out of the 9 studied
tasks). However, ICPC simultaneously accelerates training, while MixUp does
not improve training efficiency since all composite inputs are resized to
fixed shapes. In addition, we find that training with ICPC substantially
improves the resilience of models to test-time input compression (Fig. 5). The
extent of input compression performed during inference can be tuned to operate
at different points in the accuracy-efficiency trade-off space based on user
constraints, and ICPC-trained models are significantly more accurate than iso-
efficient MixUp-trained models under all levels of compression.

Figure 5: Impact of input compression on models trained with and without ICPC.
MixUp is not used when training with ICPC, and vice-versa in this experiment.
Our consistency-aware position embedding selection method is used for both
cases.

###  5.3 Further improving accuracy with Hardware-aware Test-time Augmentation

When a sample is presented during inference, multiple ”views” of the sample
can be generated using Test-time Augmentation, i.e., by applying the
augmentation methods used during training to the sample. Then, predictions on
different views of the sample can be combined using an ensembling function
(such as averaging, majority voting, etc.) to obtain the final prediction,
thereby improving accuracy and robustness. However, the time taken to process
each sample increases linearly with the number of augmented views generated
from the sample. To address this challenge, we propose Hardware-aware Test-
time Augmentation, which takes advantage of hardware under-utilization during
inference to enable Test-time Augmentation with minimal increase in latency.
In particular, hardware is under-utilized when small batch sizes are used
(Fig. 6), and increasing the batch size does not increase latency till the
batch size is high enough to fully utilize the available compute resources. We
term the smallest batch size where the hardware is fully utilized as the
”ideal batch size”. Latency typically remains constant (or changes very
minimally) for all batch sizes less than the ideal batch size. We implement
Test-time Augmentation by creating as many views of each sample as possible so
that the batch expands to the ideal batch size.

Our procedure for Hardware-aware Test-time Augmentation is as follows: (1) We
use ICPC to augment samples. Since inputs at different compression levels
generate different numbers of embedding vectors, padding is used to equalize
the lengths of all inputs for batching. Subsequently, attention masks are
applied in attention layers to prevent padding vectors from interfering with
the processing of valid vectors. (2) The ideal batch size varies with input
resolution (Fig. 6), with larger ideal batch sizes for smaller inputs.
Therefore, there is a trade-off between number of augmented views that can be
used for inference at iso-latency, and the maximum resolution of the augmented
samples. To find the configuration with the best trade-off, we randomly create
K different configurations, with each configuration having a different set of
resolutions (number of resolutions in each configuration is equal to the ideal
batch size for the maximum resolution in the configuration). For instance,
[176, 160, 144, 128] is a valid configuration for ViT-Base on ImageNet, since
the ideal batch size is 4 when the resolution is 176*176 (Fig. 6). All inputs
are evaluated at resolutions of 176, 160, 144 and 128, and the predictions are
combined to produce the final prediction when this configuration is used. (3)
All K configurations are evaluated on our validation set (5% of the training
set randomly sampled with class balance), and the configuration with the best
validation accuracy is evaluated on the test set (Table 2). We find that Test-
time Augmentation using ICPC leads to an average accuracy gain of 1.4 absolute
points, which is 0.6 absolute points higher than the average accuracy gain
from Test-time Augmentation through other augmenters used to train the
baseline models. We also find that configurations with lower maximum
resolution and higher ideal batch sizes (better for efficiency since the
processing time for a batch is primarily dependent on the maximum resolution
of samples in the batch) achieve higher average accuracy than configurations
with higher resolutions and lower ideal batch sizes.

Figure 6: Impact of increasing batch size on inference latency for the ViT-
Base-224 model on a NVIDIA A40 GPU. Table 2: Results of Hardware-Aware Test-
time Augmentation using ICPC. We create K=100 configurations, and choose the
best one using the validation set. Speedups and accuracy gains (absolute
points) are reported over the original (baseline) models.

Dataset | Accuracy Gain | Speedup
---|---|---
SST-2 | 1.7 | 1.4$\times$
Reuters | 2.0 | 1.2$\times$
CIFAR-10 | 0.6 | 1.8$\times$
CIFAR-100 | 1.7 | 1.6$\times$
ImageNet | 1.2 | 1.6$\times$
SomethingSomethingV2 | 1.8 | 1.9$\times$
Kinetics400 | 1.0 | 2.0$\times$
SpeechCommandsV2 | 0.6 | 1.2$\times$
ESC50 | 1.6 | 1.1$\times$

##  6 Related Work

Data augmentation: Data augmentation is a popular technique for preventing
overfitting during training. For text inputs, popular augmentation methods
include synonym replacement, shuffling, random insertion and deletion [25],
etc. On the other hand, image datasets are commonly augmented through
translation, rotation, noise addition, etc. In addition, techniques such as
MixUp [29], CutMix [28] and AugMix [10] achieve data augmentation by mixing
different training samples to create composite inputs. Since videos are
represented as sets of images ordered in time, augmentation techniques
designed for images have been shown to work well for videos also. Finally,
audio datasets are commonly augmented by adding background noise, and by
randomly masking out parts of the spectogram [18, 14]. ICPC, which applies
varying levels of compression to create augmented views of each sample, is
complementary to and can be used in conjunction with the aforementioned
augmentation methods. In addition, the vast majority of prior augmentation
methods are size-preserving, i.e, the transformations do not change the shape
of the input, and hence, they do not have any impact on efficiency.

Transformers for variable-length inputs: Prior works have proposed
modifications to position embeddings in Transformers to enable processing of
variable length inputs. SegFormer [27] enables semantic segmentation on
variable-resolution inputs through a position-embedding-free model design.
NaViT [2] uses fractional embeddings to process images at their native aspect
ratios. Patchout [14] uses two different sets of position embeddings – one
capturing time information, and the other capturing frequency information –
for encoding variable-size spectograms. Since these methods require
specialized architectures, they are not broadly applicable to all
Transformers.

Variable-effort inference: Variable-effort inference modulates computational
effort on a per-sample basis [8] by spending less computational effort in
processing easy samples compared to difficult samples. The most popular
example is early exit [20], which modulates network depth based on sample
difficulty. While early exit modulates model complexity for each sample, ICPC
takes a complementary data-centric approach and modulates input sizes. [23]
varies patch sizes based on input difficulty, but is not applicable to
modalities that do not involve patches (such as text).

##  7 Conclusion

We proposed Input Compression with Positional Consistency (ICPC), a new data
augmentation method that applies varying levels of compression to each sample
in every epoch. We introduced a consistency-aware position selection method
for encoding compressed inputs. We demonstrated that ICPC improved both
generalization performance and training efficiency. We also showed that ICPC
can be used to accelerate inference by modulating compression based on input
complexity.

##  8 Acknowledgement

This work was supported in part by the Center for the Co-Design of Cognitive
Systems (CoCoSys), a JUMP2.0 center sponsored by the Semiconductor Research
Corporation (SRC) and DARPA, and in part by SRC under the AIHW program.

## References

  * Bird [2006] Steven Bird.  NLTK: the natural language toolkit.  In _ACL 2006, 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, Sydney, Australia, 17-21 July 2006_. The Association for Computer Linguistics, 2006.
  * Dehghani et al. [2023] Mostafa Dehghani, Basil Mustafa, Josip Djolonga, Jonathan Heek, Matthias Minderer, Mathilde Caron, Andreas Steiner, Joan Puigcerver, Robert Geirhos, Ibrahim Alabdulmohsin, Avital Oliver, Piotr Padlewski, Alexey A. Gritsenko, Mario Lucic, and Neil Houlsby.  Patch n’ pack: Navit, a vision transformer for any aspect ratio and resolution.  _CoRR_ , abs/2307.06304, 2023.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2009), 20-25 June 2009, Miami, Florida, USA_ , pages 248–255. IEEE Computer Society, 2009.
  * Devlin et al. [2019] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , pages 4171–4186. Association for Computational Linguistics, 2019.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.
  * Gong et al. [2021] Yuan Gong, Yu-An Chung, and James R. Glass.  AST: audio spectrogram transformer.  _CoRR_ , abs/2104.01778, 2021.
  * Goyal et al. [2017] Raghav Goyal, Samira Ebrahimi Kahou, Vincent Michalski, Joanna Materzynska, Susanne Westphal, Heuna Kim, Valentin Haenel, Ingo Fründ, Peter Yianilos, Moritz Mueller-Freitag, Florian Hoppe, Christian Thurau, Ingo Bax, and Roland Memisevic.  The ”something something” video database for learning and evaluating visual common sense.  In _IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017_ , pages 5843–5851. IEEE Computer Society, 2017.
  * Han et al. [2022] Yizeng Han, Gao Huang, Shiji Song, Le Yang, Honghui Wang, and Yulin Wang.  Dynamic neural networks: A survey.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 44(11):7436–7456, 2022.
  * Hayes and Weinstein [1990] Philip J. Hayes and Steven P. Weinstein.  CONSTRUE/TIS: A system for content-based indexing of a database of news stories.  In _Proceedings of the The Second Conference on Innovative Applications of Artificial Intelligence (IAAI-90), Washington, DC, USA, May 1-3, 1990_ , pages 49–64. AAAI, 1990.
  * Hendrycks et al. [2020a] Dan Hendrycks, Norman Mu, Ekin Dogus Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshminarayanan.  Augmix: A simple data processing method to improve robustness and uncertainty.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net, 2020a.
  * Hendrycks et al. [2020b] Dan Hendrycks, Norman Mu, Ekin D. Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshminarayanan.  Augmix: A simple data processing method to improve robustness and uncertainty, 2020b.
  * Kaplan et al. [2020] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models.  _CoRR_ , abs/2001.08361, 2020.
  * Kay et al. [2017] Will Kay, João Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijayanarasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, Mustafa Suleyman, and Andrew Zisserman.  The kinetics human action video dataset.  _CoRR_ , abs/1705.06950, 2017.
  * Koutini et al. [2021] Khaled Koutini, Jan Schlüter, Hamid Eghbal-zadeh, and Gerhard Widmer.  Efficient training of audio transformers with patchout.  _CoRR_ , abs/2110.05069, 2021.
  * Krizhevsky [2009] A. Krizhevsky.  Learning Multiple Layers of Features from Tiny Images.  Technical report, Univ. Toronto, 2009.
  * Li et al. [2023] Kunchang Li, Yali Wang, Yizhuo Li, Yi Wang, Yinan He, Limin Wang, and Yu Qiao.  Unmasked teacher: Towards training-efficient video foundation models.  _CoRR_ , abs/2303.16058, 2023.
  * Liu et al. [2019] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized BERT pretraining approach.  _CoRR_ , abs/1907.11692, 2019.
  * Park et al. [2019] Daniel S. Park, William Chan, Yu Zhang, Chung-Cheng Chiu, Barret Zoph, Ekin D. Cubuk, and Quoc V. Le.  Specaugment: A simple data augmentation method for automatic speech recognition.  In _Interspeech 2019, 20th Annual Conference of the International Speech Communication Association, Graz, Austria, 15-19 September 2019_ , pages 2613–2617. ISCA, 2019.
  * Piczak [2015] Karol J. Piczak.  ESC: dataset for environmental sound classification.  In _Proceedings of the 23rd Annual ACM Conference on Multimedia Conference, MM ’15, Brisbane, Australia, October 26 - 30, 2015_ , pages 1015–1018. ACM, 2015.
  * Teerapittayanon et al. [2016] Surat Teerapittayanon, Bradley McDanel, and H. T. Kung.  Branchynet: Fast inference via early exiting from deep neural networks.  In _23rd International Conference on Pattern Recognition, ICPR 2016, Cancún, Mexico, December 4-8, 2016_ , pages 2464–2469. IEEE, 2016.
  * Verma et al. [2019] Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, Aaron Courville, David Lopez-Paz, and Yoshua Bengio.  Manifold mixup: Better representations by interpolating hidden states, 2019.
  * Wang et al. [2018] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 353–355, Brussels, Belgium, 2018. Association for Computational Linguistics.
  * Wang et al. [2021] Yulin Wang, Rui Huang, Shiji Song, Zeyi Huang, and Gao Huang.  Not all images are worth 16x16 words: Dynamic transformers for efficient image recognition.  In _Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual_ , pages 11960–11973, 2021.
  * Warden [2018] Pete Warden.  Speech commands: A dataset for limited-vocabulary speech recognition.  _CoRR_ , abs/1804.03209, 2018.
  * Wei and Zou [2019] Jason W. Wei and Kai Zou.  EDA: easy data augmentation techniques for boosting performance on text classification tasks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019_ , pages 6381–6387. Association for Computational Linguistics, 2019.
  * Wolf et al. [2019] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew.  Huggingface’s transformers: State-of-the-art natural language processing.  _CoRR_ , abs/1910.03771, 2019.
  * Xie et al. [2021] Enze Xie, Wenhai Wang, Zhiding Yu, Anima Anandkumar, José M. Álvarez, and Ping Luo.  Segformer: Simple and efficient design for semantic segmentation with transformers.  In _Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual_ , pages 12077–12090, 2021.
  * Yun et al. [2019] Sangdoo Yun, Dongyoon Han, Sanghyuk Chun, Seong Joon Oh, Youngjoon Yoo, and Junsuk Choe.  Cutmix: Regularization strategy to train strong classifiers with localizable features.  In _2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 - November 2, 2019_ , pages 6022–6031. IEEE, 2019.
  * Zhang et al. [2018] Hongyi Zhang, Moustapha Cissé, Yann N. Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net, 2018.