# Semantically Stealthy Adversarial Attacks against Segmentation Models

Zhenhua Chen Chuhua Wang11footnotemark: 1 David Crandall
Indiana University Bloomington
Bloomington, IN 47405
{chen478, cw234<EMAIL_ADDRESS>Equal Contribution

###### Abstract

Segmentation models have been found to be vulnerable to targeted and non-
targeted adversarial attacks. However, the resulting segmentation outputs are
often so damaged that it is easy to spot an attack. In this paper, we propose
semantically stealthy adversarial attacks which can manipulate targeted labels
while preserving non-targeted labels at the same time. One challenge is making
semantically meaningful manipulations across datasets and models. Another
challenge is avoiding damaging non-targeted labels. To solve these challenges,
we consider each input image as prior knowledge to generate perturbations. We
also design a special regularizer to help extract features. To evaluate our
model’s performance, we design three basic attack types, namely ‘vanishing
into the context,’ ‘embedding fake labels,’ and ‘displacing target objects.’
Our experiments show that our stealthy adversarial model can attack
segmentation models with a relatively high success rate on Cityscapes,
Mapillary, and BDD100K. Our framework shows good empirical generalization
across datasets and models.

Figure 1: Comparison between stealthy and non-stealthy attacks. Top:
Predictions without attacks. Red represents the ‘person’ label. Middle:
Predictions before (left) and after (right) normal attacks in which the
incorrect predictions are obvious. Bottom: Predictions before (left) and after
(right) semantically stealthy attacks, in which it is difficult to detect an
attack since the ‘person’ labels vanished into the environment. Figure 2: An
overview of our attack model. During training, each input image is fed into
both generator and regularizer to generate perturbation and regularizer
logits. The scaled perturbation is then added to the original image to produce
an adversarial example. Pre-trained target model receives both the original
and adversarial image, and original predicted logits and adversarial logits
are acquired. The predicted logits are manipulated based on different attack
types, and output manipulated labels to calculate adversarial loss. The
regularizer logits are paired with predicted labels to calculate regularizer
loss.

##  1 Introduction

It is well-known that neural networks are vulnerable to adversarial attacks.
For example, we can add imperceptible perturbations to an input image to
manipulate the predictions of classifiers [11, 26, 34, 36, 42, 8], object
detectors [40], segmentation models [1], object trackers [38, 18, 12, 20],
edge detectors [7], 3D reconstruction models [14, 44], image caption models
[41], face detectors [9], embodied agents [33], video classifiers [47], etc.

Among all the above adversarial attacks, those against segmentation models are
relatively difficult because of the thousands of constraints that need to be
considered for each input sample. So far, most adversarial segmentation models
focus on non-targeted objectives [40, 1], which means that when a segmentation
model is attacked, the abnormal predictions are noticeable. Although there are
some targeted adversarial segmentation models, most of them focus on either a
static target [29, 22] or a particular attribute [37, 22].

Here we propose semantically “stealthy” adversarial attacks against
segmentation models, so that they are not as noticeable. To illustrate this
stealthy idea, we design three attack types, 1) making a target object vanish
into the context; 2) adding a fake object; 3) replacing a target object with a
fake one at a different position. For example, in Figure 4, the ‘person’
labels disappear after being attacked, and at the same time, these pixels are
re-classified as ‘cars.’ Since the ‘car’ labels are common in this context, it
would be difficult to detect this attack.

To achieve semantically stealthy adversarial attacks, we face two challenges.
On one hand, the targeted labels need to be efficiently relabeled as designed.
On the other hand, all other non-targeted pixels’ labels should be preserved.
Since all the pixels’ labels in a segmentation model have to be considered,
the total number of constraints is huge. To tackle this problem we introduce
two approaches: 1) an image-dependent perturbation generation scheme, and 2) a
regularizer. Our regularizer is a segmentation model using the same structure
as FCN [21], as Figure 2 shows. The regularizer is introduced based on the
following assumption: if a perturbation generator can generate effective noise
then it should also be able to predict segmentation labels with high accuracy
since the two tasks need common spatial features. In other words, the
generated features should be task-irrelevant.

In addition to the task-related constraints, we also constrain our
perturbations to be imperceptible by requiring their infinity norm to be
smaller than 10, $\|\hat{p}\|_{\infty}\leq 10$). We are also constrained by
GPU memory: segmentation models are usually large since they need to predict
labels for every pixel, and we have to use another large neural network to fit
the complex tasks. Thus, putting both networks during training would consume a
large amount of memory. We introduce the concept of ‘attack efficiency,’
namely the ratio of the attack/target model’s size.

Our primary contributions are summarized as follows:

  * •

We propose an attack framework that can create stealthy, semantically-
meaningful attacks against segmentation models.

  * •

We design three basic types of semantic attacks: removing labels, adding fake
labels, and moving labels. Other high-level semantic manipulations can be
performed by combining these basic types.

  * •

We evaluate our model’s generalization ability across different datasets.

  * •

We propose the concept of parameter-wise efficiency for adversarial models.

##  2 Related work

###  2.1 Universal adversarial attacks

The universal adversary might be a solution to overcome the computationally
intensive issue of FGSM-based attacks. Universal Adversarial Perturbations
(UAP) were introduced by [23], and can generate sample-agnostic perturbations
offline and thus can apply attacks in real-time. The key idea of UAP is to
find a universal perturbation that can fool all the training/test images. UAP
was originally designed for classifiers but can be easily extended to attack
segmentation models by, for example, finding a perturbation that maximizes the
predictive probability of a target class by iteratively backpropagating the
gradients to the input space [22]. When the training is finished, the final
gradients form the perturbation which is added to each input image during
testing time. Another way to obtain UAP is by calculating singular vectors of
the Jacobian matrices of the feature maps [27]. It is also possible to use a
neural network to generate UAP [24, 29, 15]. Zhang et al. [45], Benz et al.
[2], Gupta et al. [13] explore the idea of generating UAPs that only attack a
group of classes and limit the influence on the remaining classes. Another
interesting perspective towards UAP is considering images rather than
perturbations as noise [3]. As for defending against UAP, adversarial learning
is still the most efficient way [46].

###  2.2 Image-dependent adversarial attacks

Methods based on UAP attack models largely avoid the computationally expensive
issue. However, they are not so flexible since each input image, though it can
be considered as prior knowledge, is ignored. One straightforward way to solve
this issue is by generating perturbations from input images. We can also adopt
a GAN-like structure, in which the discriminator corresponds to the target
model while the generator is supposed to generate the perturbations. The
perturbation generator can start from either random noise or an image. If the
perturbation comes from an image, it is called an image-dependent
perturbation. For example, Poursaeed et al. [29] proposes a universal, GAN-
like attack model that can attack both segmentation models and classifiers.

###  2.3 Semantic adversarial attacks

Semantic/targeted adversarial attacks are related to our work. Shamsabadi et
al. [32] propose a content-based black-box adversarial attack through
manipulating background colors. Joshi et al. [19] creates semantic adversarial
attacks against classifiers by manipulating specific attributes. These types
of attacks are somewhat stealthy but their target models are classifiers. Treu
et al. [37] proposed a method to overlay generated adversarial texture on the
clothing of a person to fool segmentation networks. Metzen et al. [22] is most
alike our work in which an adversarial attack for hiding person labels is
proposed. However, Metzen et al. [22] adopt universal perturbations and tested
only on one dataset.

###  2.4 Physical adversarial attacks

Apart from adding perturbations, it is also possible to add physical
attributes to a scene into order to attack. For example, Sharif et al. [35]
can fool a face recognizer by adding glasses to a face, while Qiu et al. [30]
manipulates face attributes (like hair color, etc.). Duan et al. [10]
manipulate classifiers’ predictions by camouflaging physical adversarial
examples into natural styles. These methods used to generate physical
adversarial examples are weakly related to our work.

##  3 Our Approach

Many studies [5, 40, 39] show that complex tasks such as semantic segmentation
are vulnerable to adversarial attacks, and that generated subtle perturbations
to inputs can completely break the prediction outputs. We present a stealthy
adversarial attack approach that not only can hide an attack behavior, but
also keeps other non-targeted labels correctly classified. We realize our goal
by designing a regularized pipeline to generate image-dependent perturbations,
as shown in Figure 2.

In this section, we first give an overview of the adversarial attack problem
and our proposed stealthy approach. We then introduce how the generator and
regularizer work.

###  3.1 Problem definition

Let $f_{\theta}$ be the target segmentation model trained on some dataset with
(image, label) pairs $\displaystyle{\mathcal{D}}=\\{(x,y)\\}$ where
$x\in\displaystyle\mathbb{R}^{h\times w\times c}$,
$y\in\displaystyle\mathbb{R}^{h\times w}$ and $h$, $w$, and $c$ represent the
height, width, and number of image channels, respectively. The perturbation
$\hat{p}\in\displaystyle\mathbb{R}^{h\times w\times c}$ has the same size as
the input image that can be acquired by the generator
$f_{\theta^{{}^{\prime}}(x)}$. An adversarial example
$\hat{x}\in\displaystyle\mathbb{R}^{h\times w\times c}$ is the addition of the
perturbation $\hat{p}$ and the input image $x$. We need to map both $x$ and
$\hat{x}$ to logits through $f_{\theta}$ during training,

$l_{x}=f_{\theta}(x),\;\hat{l_{x}}=f_{\theta}(\hat{x}).$ (1)

Apart from $l_{x}$ and $\hat{l_{x}}$, we also train a regularizer that is
supposed to predict segmentation labels,

$l_{reg}=r_{\theta^{{}^{\prime\prime}}}(x).$ (2)

Finally, we pair $l_{x},\hat{l_{x}},l_{reg}$ with their corresponding labels
$y,\hat{y},y$ to calculate the loss.

###  3.2 Model overview

As Figure 2 shows, our framework contains a target model, a generator, and a
regularizer. Input images $x$ are fed into the generator
$f_{\theta^{{}^{\prime}}}$ to produce perturbations. The regularizer (which
shares the same backbone $f_{\theta^{{}^{\prime}}}$ with the generator) is
trained to learn the segmentation task. Both original input images and the
corresponding perturbated images are paired and fed to the target model
$f_{\theta}$ to generate logits $l_{x},\hat{l_{x}}$. After we map
$\hat{l_{x}}$ to $\hat{y}$, $l_{x}$ and $\hat{y}$ are fed into the loss
function for training.

During training, we first load the pre-trained target model $\displaystyle
f_{\theta}$ and freeze it to prevent the weights from updating during back-
propagation. Then the generator takes an image sample and outputs a
perturbation image. The regularizer generates logits to fit the original
segmentation task. The adversarial image is obtained by adding the scaled
perturbation to the original image. Both the original and adversarial are fed
into $\displaystyle f_{\theta}$ and output the original and the adversarial
logits respectively. Depending on attack designs, we pair manipulated labels
with the predicted labels to calculate the adversarial loss. At the same time,
we pair the logits generated by the regularizer with the ground truth
segmentation labels to calculate the regularizer loss. Finally, both cross-
entropy losses from the regularizer and the generator are backpropagated to
the generator space. The whole algorithm is summarized in Algorithm 1.

$\mathbf{Input:}$ input image $x$, Target model $f_{\theta}$ with parameters
$\theta$. Generator $f_{\theta^{{}^{\prime}}}$ with parameters
$\theta^{{}^{\prime}}$, regularizer $r_{\theta^{{}^{\prime\prime}}}$ with
parameters $\theta^{{}^{\prime\prime}}$, Stealthy label mapper
${\mathcal{M}}$.

$\mathbf{Output:}$ Adversarial perturbations $\hat{p}$, Adversarial input
image $\hat{x}$

Initialize the generator $f_{\theta^{{}^{\prime}}}$, Initialize the
regularizer $r_{\theta^{{}^{\prime\prime}}}$

while  _not converge_ do

Generate regularizer logits $l_{reg}=r_{\theta^{{}^{\prime\prime}}}(x)$, and
perturbations $\hat{p}=f_{\theta^{{}^{\prime}}}(x)$ ;

Obtain an adversarial image $\hat{x}=x+\hat{p}$;

Generate the clean logits of the target model $l_{x}=f_{\theta}(x)$;

Generate the dirty logits of target model $\hat{l_{x}}=f_{\theta}(\hat{x})$;

Create semantically stealthy labels $\hat{y}={\mathcal{M}}(l_{x})$ ;

Calculate the regularizer loss
${\mathcal{L}}_{reg}(y,r_{\theta^{{}^{\prime\prime}}}(x))$;

Calculate the adversarial loss
$\displaystyle{\mathcal{L}}(l_{x},\hat{l_{x}})$;

Back-propagate the gradients;

Algorithm 1 Semantically Stealthy Adversarial Attack.

####  3.2.1 Generator & regularizer

We adopt two versions of generators to deal with different sizes of
segmentation models: a Unet [31] network (as shown in Figure 13), and a FCN
network structure [21] with ResNet-101 backbone [16]. The generator
$f_{\theta^{{}^{\prime}}}$ is to map an input image to perturbations, as shown
in Figure 13. At the same time, we have a regularizer
$r_{\theta^{{}^{\prime\prime}}}$ which is responsible for predicting the
semantic segmentation labels of the original image. The potential assumption
is that if a generator can generate perturbations that serve a particular
target, then the embedded features that come from the generator should also
have a good knowledge of the spatial relationship within each input image. In
other words, the two branches of the generator (one for semantic segmentation
label, the other one for perturbations) are complementary with each other.
After the perturbation is acquired, we forward both the original image and the
adversarial image through the target model to obtain predicted and adversarial
labels. We use a cross-entropy loss to regulate the generator and help to
preserve labels of non-targeted pixels. The adversarial labels are manipulated
(see Section 3.2.2) and used to calculate the adversarial loss (see 3.2.3 for
details).

####  3.2.2 Attack types

In general, we achieve stealthiness via manipulating targeted pixels’ labels
as designed and at the same time preserving untargeted pixels’ labels. During
attack, we map ‘clean’ labels to ‘semantically stealthy’ labels,

$\hat{y}={\mathcal{M}}(l_{x})$ (3)

We design three attack types to manipulate the predicted labels and validate
our idea. We believe that these three attack types are basic and combining
these attack types can be used to generate other higher-level semantically
attack types: Type #1, remove the target class, Type #2, generate a class
label from an external source, and Type #3, combine the previous two types.
More specifically,

Figure 3: How we convert the original predictions to the “adversarial ground
truth.” The ‘person’ labels (the red area) near the wall are converted to
label ‘wall’ while those near the sidewalk are converted to label ‘sidewalk.’

Type #1: The target model is made to fail to predict a designated class. As a
result, the original label has disappeared or blended into the surrounding
context. The most straightforward way of achieving this goal is to assign each
target pixel its neighbor’s label by clustering. However, clustering is very
time-consuming. We thus adopt a heuristic approach by replacing each target
pixel’s original label with its second likely label in the original
prediction. Practically, it works well, as Figure 3 shows.

Type #2: The labels of a set of referred pixels are transformed into a
specific class. Visually, this makes it appear like an attacker creates a set
of new labels that comes from nowhere. We manipulate the predicted label by
adding a new mask from an external source.

Type #3: This task can be achieved by combining the attacks of Type #1 and
Type #2: removing the target class labels in one position and then create
fakes class labels in another position.

####  3.2.3 Loss

We design our loss function to make sure that the target label is manipulated
from $y$ to $\hat{y}$, as Equation 4 shows. $T_{k}$ equals $1$ if the pixel
$k$ is one of our target pixels, and otherwise is $0$. Variables $n$,
$c^{\prime}$, $m$ are the batch size, channel size (total number of
categories), and the total number of pixels in each image, while $p_{i,j,k}$
represents the probability of each pixel belonging to $j$ which comes from
either $l_{x}\in\displaystyle\mathbb{R}^{m\times c^{\prime}}$ (the logits
forms of $y$) or $\hat{l_{x}}\in\displaystyle\mathbb{R}^{m\times c^{\prime}}$.
The loss function $\mathcal{L(\cdot)}$ is shown in Equation 4.

$\begin{split}\mathcal{L}\left(\hat{l_{x}},\hat{y}\right)=\min\sum_{i=0}^{n}\sum_{k=0}^{m}T_{k}(-\log
p_{i,\hat{y}_{k},k}\\\
+\left(1-T_{k}\right)\left(-\log\left(p_{i,\hat{y}_{k},k}\right)\right).\end{split}$
(4)

Assuming the logits that come from the generator is $l_{reg}$, then the
regularizer loss can be summarized as,

$\mathcal{L}_{reg}(l_{reg},y)=\min\sum_{i=0}^{n}\sum_{k=0}^{m}-\log
p_{i,y_{k},k}.$ (5)

We introduce $\lambda_{0}$ to be the weight of regularizer loss. The total
loss term is,

$\begin{split}\mathcal{L}_{total}=\mathcal{L}+\lambda_{0}*\mathcal{L}_{reg}.\end{split}$
(6)

It is common practice to limit the infinity norm of the perturbations to
achieve imperceptibility, as shown in [11]. If not specified, $\xi$ is always
equal to 10,

$\|\hat{p}\|_{\infty}\leq\xi.$ (7)

Dataset | Type#1 | Type#2 | Type#3
---|---|---|---
Cityscapes | 74.71% / 91.40% | 91.27% / 92.76% | 67.73% / 88.74%
BDD100K | 66.56% / 97.09% | 68.69% / 92.46% | 66.54% / 90.58%
Mapillary | 68.39% / 96.41% | 78.67% / 88.62% | 56.07% / 85.42%
Table 1: The performance of our framework on three street-view datasets. Each
item represents success rates for type ‘manipulated’ / ‘preserved’ in one of
the three datasets. For example, the top-left item (red-colored) means that
the attack model trained on Cityscapes can make 74.71% targeted pixels vanish
into the background while making 91.40% non-targeted pixels preserve their
original labels. All the target models are trained by FCN.

Figure 4: Type #1 attack on Cityscapes. The ‘person’ labels vanish into the
background. Top left: The input image. Top middle: The perturbations. Top
right: The input image + perturbations. Lower left: Normal predictions. Lower
right: Predictions after attacks.

##  4 Experiments

###  4.1 Datasets & Metrics

We choose three street-view datasets as the testing set since all our attack
types focus on pedestrians. Specifically, we use Cityscapes (2975 training
images, 1525 testing images) [6], Mapillary Vistas Dataset (18K training
images, 5K testing images) [25], and BDD100K (7K training image, 2K testing
images) [43].

We evaluate our model by using success rate as the performance metric. Each
success rate is divided into two parts: manipulated and preserved rate.
Manipulated rate is defined as the percentage of labels that are manipulated
successfully for targeted pixels while the preserved rate is defined as the
percentage of labels that are preserved for non-targeted pixels.

Figure 5: Type #2 attack on Cityscapes. Fake ‘person’ labels are embedded into
the prediction domain. Top left: The input image. Top middle: The
perturbations. Top right: The input image + perturbations. Lower left: Normal
predictions. Lower middle: The fake label mask. Lower right: Predictions after
attacks.

###  4.2 Implementation details

We implement our network in PyTorch [28] and perform all experiments with
Nvidia Titan Xp Pascal GPUs. In Section 4.5, we use FCN-8s as the target
segmentation model, and pre-train the model on all three datasets. We resize
each input image to 512$\times$1024 during training. For Section 4.6, we use
CityScapes as our train/test dataset. Each input image is loaded at its
original size and then cropped randomly to 768$\times$768 during training. For
all the models, we choose Person and Rider as our target labels. The weight of
our regularizer $\lambda_{0}$ is set to 1e-2. The learning rate is 1e-4, and
batch size is set to 16.

###  4.3 Quantitative analysis

Table 1 shows the manipulated/preserved rate of attacking the target model
[21]. We observe that manipulating non-targeted labels into target labels
(Type #2) seems to be easier than blending target labels into non-targeted
labels (Type #1). We conjecture that the model does not need to consider the
context information in the former task, thus leading to a higher manipulated
rate. However, our results show that preserving non-targeted labels in attack
type #2 is more difficult than in attack type #1. We speculate that this might
be because it is challenging to preserve surrounding information when the
manipulated pixels do not fit in context. The results also suggest that
combining the two tasks (type #3) decreases the overall performance.

Figure 6: Type #3 attack on Cityscapes. The target ‘person’ labels disappear
and the fake ‘person’ labels are embedded. Top left: The input image. Top
middle: The perturbations. Top right: The input image + perturbations. Lower
left: Normal predictions. Lower middle: The fake label mask. Lower right:
Predictions after attacks.

###  4.4 Qualitative analysis

Figure 4 shows the results of Type #1 attack. The person labels are converted
to building, car, sidewalk, and road labels. There are some ‘residuals’ left
in the original position. Figure 5 shows the results of Type #2 attack. We use
the binary mask of person label to train our generator. The perturbation
includes highlights around the boundary of added person labels, and the target
model classifies these non-targeted pixels as person labels. Figure 6 shows
the results of combining the previous two types of attacks. The person labels
in the original prediction are not completely removed and three fake ‘person’
regions are embedded. Comparing to the above two tasks, Type #3 is the most
difficult among them.

Datasets | Cityscapes | BDD100K | Mapillary
---|---|---|---
Cityscapes | 96.34% | 95.44 % | 92.96%
BDD100K | 97.24% | 97.86% | 96.56%
Mapillary | 96.86% | 96.09% | 97.41%
Table 2: Our model’s generalization across datasets on Type#1 attack. Each item is the success rate within/across datasets. For example, the red-colored 95.44% indicates that the attack model trained on Cityscapes can achieve a success rate of 95.44% against a segmentation model trained on BDD100K. Models | DLV3+-MobileNets | DLV3+-ResNet101
---|---|---
Type #1 |  |
DLV3+-MobileNets | 84.36% | 89.16%
DLV3+-ResNet101 | 85.49% | 89.92%
Type #2 |  |
DLV3+-MobileNets | 87.42% | 90.67%
DLV3+-ResNet101 | 96.63% | 96.80%
Type #3 |  |
DLV3+-MobileNets | 80.91% | 83.35%
DLV3+-ResNet101 | 82.82% | 84.80%
Table 3: Our model’s generalization across attack models trained on
CityScapes. Each item is the overall success within/across models. For
example, for type #1 attack, the red-colored 89.16% indicates that the attack
model trained on DeepLabV3Plus-MobileNets can achieve a success rate of 89.16%
against a target model pretrained on DeepLabV3Plus-ResNet101.

###  4.5 Generalization across datasets

It is desirable to check the generalization ability of our model across
different datasets. In other words, we want to find out whether our model can
achieve good performance on unseen distributions. Specifically, we train an
adversarial model (model #1 in Table 5) on one dataset (e.g. Cityscapes) to
attack the segmentation models trained on two other datasets (e.g. Mapillary,
and BDD100K).

We can draw two conclusions here from Table 2: each attack model performs best
within its distribution, and each attack model’s performance generalizes well
on unseen datasets (distributions). For example, the results of BDD100K and
Mapillary show that both models trained on these two datasets are able to
reach comparable performance when generalizing to others. We conjecture that a
larger dataset may contain more useful information during training, thus
resulting in better generalization ability.

Model type | Cityscapes | BDD100K | Mapillary
---|---|---|---
Normal | 74.71% | 66.56% | 68.39%
Regularizer-removed | 62.87% | 54.88% | 59.98%
Table 4: The success rate of our model (as shown in Figure 13) with/without the proposed regularizer across different datasets. attack model size | target model size | ratio | Cityscapes | BDD100K | Mapillary
---|---|---|---|---|---
Model#1 (531M) | 269M | 1.974 | 96.34% | 97.86% | 96.09%
Model#2 (10.69M) | 269M | 0.040 | 74.71% | 66.56% | 68.39%
Model#3 (2.69M) | 269M | 0.010 | 64.47% | 53.63% | 60.39%
Model#4 (692K) | 269M | 0.003 | 60.63% | 50.99% | 45.53%
Table 5: The parameter-wise efficiency of our model on type #1 attack. Model
#1 adopt the generator in [29]. Model #2 uses the generator in Figure 13.
Model #3 is the same as Model #2 only the number of feature maps in each layer
is cut in half. Similarly, Model #4 cuts half of its parameters from Model #3.

###  4.6 Generalization across models

Generalization across models is also an important aspect of an adversarial
model. We select two target models based on DeepLabV3Plus [4]. One has a
backbone of MobileNets [17], while the other one has a backbone of ResNet.
Since the target model is very deep, we replace the generator with a deeper
version, a ResNet-based FCN. As Table 3 shows, for all three attack types, the
success rates are quite close when the two target models are switched.

###  4.7 Ablation study

The regularizer in our model plays a vital role in attacking segmentation
models dynamically. The potential assumption is that if a generator can create
perturbations for dynamic target labels, then the embedded features that come
from the generator should also have a good knowledge of the spatial structure
within each image. As a result, we can use these embedded features to generate
labels that come from the target model. To explore the role of the
regularizer, we compare the performance (manipulated rate) between our models
and the corresponding regularizer-free ones on three datasets. As Table 4
shows, the regularizer can improve the manipulated rate by around 12% in
Cityscapes and Mapillary, and 8% in Mapillary.

###  4.8 Efficiency of attack models

The efficiency of attack models has been largely ignored by previous works.
However, as attack/target models become larger and more complex, the
efficiency issue can no longer be ignored. For example, the success rate is
higher when using a ResNet-based generator to attack a MobileNets-based target
model compared to vice versa.

Here we propose a metric that is defined as the ratio of attack models’ sizes
and the target models’ sizes. For the same manipulated rate, smaller attack
models are more efficient. We list four different models and show the total
number of parameters of them in Table 5 in descending order.

We can see that larger attack models can achieve a higher success rate. For
example, when the model is twice as large as the target model, model #1 can
achieve an almost perfect manipulated rate (more than 96%). With only 4%
parameters, our model #2 can achieve around 70% manipulated rate. It is
interesting that with less than 0.3% parameters (model #4), our model can
still achieve relatively good performance.

##  5 Conclusion

We propose a framework for creating semantically stealthy adversarial attacks
against segmentation models. In particular, we design an algorithm that can
manipulate targeted pixels’ labels as designed while keeping other pixels’
labels untouched. To achieve this goal, we introduce prior knowledge (each
perturbation is conditionally dependent on the corresponding input image) as
well as a special regularizer into our attack model. We evaluate our model’s
performance by success rates on three types of stealthy attacks. The
experiment shows that our framework has a relatively high success rate across
datasets/models. Finally, we propose the concept of attack efficiency which
may help estimate attack models’ parameter-wise efficiency.

## References

  * Arnab et al. [2017] Anurag Arnab, Ondrej Miksik, and Philip H. S. Torr.  On the robustness of semantic segmentation models to adversarial attacks.  _CoRR_ , abs/1711.09856, 2017.  URL http://arxiv.org/abs/1711.09856.
  * Benz et al. [2020] Philipp Benz, Chaoning Zhang, Tooba Imtiaz, and In So Kweon.  Double targeted universal adversarial perturbations.  In _Proceedings of the Asian Conference on Computer Vision (ACCV)_ , November 2020.
  * Chaoning Zhang [2020] Tooba Imtiaz Chaoning Zhang, Philipp Benz.  Understanding adversarial examples from the mutual influence of images and perturbations.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2020.
  * Chen et al. [2018] Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.  Encoder-decoder with atrous separable convolution for semantic image segmentation.  _CoRR_ , abs/1802.02611, 2018.  URL http://arxiv.org/abs/1802.02611.
  * Cisse et al. [2017] Moustapha M Cisse, Yossi Adi, Natalia Neverova, and Joseph Keshet.  Houdini: Fooling deep structured visual and speech recognition models with adversarial examples.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper/2017/file/d494020ff8ec181ef98ed97ac3f25453-Paper.pdf.
  * Cordts et al. [2016] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  In _Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * Cosgrove and Yuille [2020] Christian Cosgrove and Alan Yuille.  Adversarial examples for edge detection: They exist, and they transfer.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_ , March 2020.
  * Dong et al. [2018] Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li.  Boosting adversarial attacks with momentum.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2018.
  * Dong et al. [2019] Yinpeng Dong, Hang Su, Baoyuan Wu, Zhifeng Li, Wei Liu, Tong Zhang, and Jun Zhu.  Efficient decision-based black-box adversarial attacks on face recognition.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2019.
  * Duan et al. [2020] Ranjie Duan, Xingjun Ma, Yisen Wang, James Bailey, A. K. Qin, and Yun Yang.  Adversarial camouflage: Hiding physical-world attacks with natural styles.  In _CVPR_ , 2020.
  * Goodfellow et al. [2014] I. J. Goodfellow, J. Shlens, and C. Szegedy.  Explaining and Harnessing Adversarial Examples.  _ArXiv e-prints_ , December 2014.
  * Guo et al. [2020] Qing Guo, Xiaofei Xie, Felix Juefei-Xu, Lei Ma, Zhongguo Li, Wanli Xue, Wei Feng, and Yang Liu.  Spark: Spatial-aware online incremental attack against visual tracking.  In _ECCV_ , 2020.
  * Gupta et al. [2019] Tejus Gupta, Abhishek Sinha, Nupur Kumari, Mayank Singh, and Balaji Krishnamurthy.  A method for computing class-wise universal adversarial perturbations, 2019.
  * Hamdi et al. [2020] Abdullah Hamdi, Sara Rojas, Ali Thabet, and Bernard Ghanem.  Advpc: Transferable adversarial perturbations on 3d point clouds.  In _ECCV_ , 2020.
  * Hayes and Danezis [2018] Jamie Hayes and George Danezis.  Learning universal adversarial perturbations with generative models.  In _2018 IEEE Security and Privacy Workshops (SPW)_ , pages 43–49, 2018.  doi: 10.1109/SPW.2018.00015.
  * He et al. [2015] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  _arXiv preprint arXiv:1512.03385_ , 2015.
  * Howard et al. [2017] Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  _CoRR_ , abs/1704.04861, 2017.  URL http://arxiv.org/abs/1704.04861.
  * Jia et al. [2021] Shuai Jia, Yibing Song, Chao Ma, and Xiaokang Yang.  Iou attack: Towards temporally coherent black-box adversarial attack for visual object tracking.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * Joshi et al. [2019] Ameya Joshi, Amitangshu Mukherjee, Soumik Sarkar, and Chinmay Hegde.  Semantic adversarial attacks:parametric transformations that fool deep classifiers.  In _ICCV_ , 2019.
  * Liang et al. [2020] Siyuan Liang, Xingxing Wei, Siyuan Yao, and Xiaochun Cao.  Efficient adversarial attacks for visual object tracking.  In _ECCV_ , 2020.
  * Long et al. [2014] Jonathan Long, Evan Shelhamer, and Trevor Darrell.  Fully convolutional networks for semantic segmentation.  _CoRR_ , abs/1411.4038, 2014.  URL http://arxiv.org/abs/1411.4038.
  * Metzen et al. [2017] J. H. Metzen, M. C. Kumar, T. Brox, and V. Fischer.  Universal adversarial perturbations against semantic image segmentation.  In _2017 IEEE International Conference on Computer Vision (ICCV)_ , pages 2774–2783, Oct 2017.  doi: 10.1109/ICCV.2017.300.
  * Moosavi-Dezfooli et al. [2016] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard.  Universal adversarial perturbations.  _CoRR_ , abs/1610.08401, 2016.  URL http://arxiv.org/abs/1610.08401.
  * Mopuri et al. [2018] Konda Reddy Mopuri, Utkarsh Ojha, Utsav Garg, and R. Venkatesh Babu.  Nag: Network for adversary generation.  In _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 742–751, 2018.  doi: 10.1109/CVPR.2018.00084.
  * Neuhold et al. [2017] Gerhard Neuhold, Tobias Ollmann, Samuel Rota Bulò, and Peter Kontschieder.  The mapillary vistas dataset for semantic understanding of street scenes.  In _International Conference on Computer Vision (ICCV)_ , 2017.  URL https://www.mapillary.com/dataset/vistas.
  * Nguyen et al. [2014] Anh Mai Nguyen, Jason Yosinski, and Jeff Clune.  Deep neural networks are easily fooled: High confidence predictions for unrecognizable images.  _CoRR_ , abs/1412.1897, 2014.  URL http://arxiv.org/abs/1412.1897.
  * Oseledets and Khrulkov [2018] Ivan Oseledets and Valentin Khrulkov.  Art of singular vectors and universal adversarial perturbations.  In _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8562–8570, 2018.  doi: 10.1109/CVPR.2018.00893.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc., 2019.
  * Poursaeed et al. [2018] Omid Poursaeed, Isay Katsman, Bicheng Gao, and Serge Belongie.  Generative adversarial perturbations.  In _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2018.
  * Qiu et al. [2020] Haonan Qiu, Chaowei Xiao, Lei Yang, Xinchen Yan, Honglak Lee, and Bo Li.  Semanticadv: Generating adversarial examples via attribute-conditional image editing, 2020.
  * Ronneberger et al. [2015] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation, 2015\.
  * Shamsabadi et al. [2020] Ali Shahin Shamsabadi, Ricardo Sanchez-Matilla, and Andrea Cavallaro.  Colorfool: Semantic adversarial colorization.  In _CVPR_ , 2020.
  * shan Liu et al. [2020] shan Liu, Tairan Huang, Xianglong Liu, Yitao Xu, Yuqing Ma, Xinyun Chen, Stephen J. Maybank, and Dacheng Tao.  Spatiotemporal attacks for embodied agents.  In _ECCV_ , 2020.
  * Sharif et al. [2016a] Mahmood Sharif, Sruti Bhagavatula, Lujo Bauer, and Michael K. Reiter.  Accessorize to a crime: Real and stealthy attacks on state-of-the-art face recognition.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , CCS ’16, pages 1528–1540, New York, NY, USA, 2016a. ACM.  ISBN 978-1-4503-4139-4.  doi: 10.1145/2976749.2978392.  URL http://doi.acm.org/10.1145/2976749.2978392.
  * Sharif et al. [2016b] Mahmood Sharif, Sruti Bhagavatula, Lujo Bauer, and Michael K. Reiter.  Accessorize to a crime: Real and stealthy attacks on state-of-the-art face recognition.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , CCS ’16, pages 1528–1540, New York, NY, USA, 2016b. ACM.  ISBN 978-1-4503-4139-4.  doi: 10.1145/2976749.2978392.  URL http://doi.acm.org/10.1145/2976749.2978392.
  * Szegedy et al. [2013] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  _CoRR_ , abs/1312.6199, 2013.  URL http://arxiv.org/abs/1312.6199.
  * Treu et al. [2021] Marc Treu, Trung-Nghia Le, Huy H. Nguyen, Junichi Yamagishi, and Isao Echizen.  Fashion-guided adversarial attack on person segmentation, 2021.
  * Wang et al. [2020] Hongjun Wang, Guangrun Wang, Ya Li, Dongyu Zhang, and Liang Lin.  Transferable, controllable, and inconspicuous adversarial attacks on person re-identification with deep mis-ranking.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2020.
  * Xiao et al. [2018] Chaowei Xiao, Ruizhi Deng, Bo Li, Fisher Yu, Mingyan Liu, and Dawn Song.  Characterizing adversarial examples based on spatial consistency information for semantic segmentation, 2018.
  * Xie et al. [2017] Cihang Xie, Jianyu Wang, Zhishuai Zhang, Yuyin Zhou, Lingxi Xie, and Alan L. Yuille.  Adversarial examples for semantic segmentation and object detection.  _CoRR_ , abs/1703.08603, 2017.  URL http://arxiv.org/abs/1703.08603.
  * Xu et al. [2019] Yan Xu, Baoyuan Wu, Fumin Shen, Yanbo Fan, Yong Zhang, Heng Tao Shen, and Wei Liu.  Exact adversarial attack to image captioning via structured output learning with latent variables.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2019.
  * Yao et al. [2019] Zhewei Yao, Amir Gholami, Peng Xu, Kurt Keutzer, and Michael W. Mahoney.  Trust region based adversarial attack on neural networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2019.
  * Yu et al. [2018] Fisher Yu, Wenqi Xian, Yingying Chen, Fangchen Liu, Mike Liao, Vashisht Madhavan, and Trevor Darrell.  BDD100K: A diverse driving video database with scalable annotation tooling.  _CoRR_ , abs/1805.04687, 2018.  URL http://arxiv.org/abs/1805.04687.
  * Zeng et al. [2019] Xiaohui Zeng, Chenxi Liu, Yu-Siang Wang, Weichao Qiu, Lingxi Xie, Yu-Wing Tai, Chi-Keung Tang, and Alan L. Yuille.  Adversarial attacks beyond the image space.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2019.
  * Zhang et al. [2020a] Chaoning Zhang, Philipp Benz, Tooba Imtiaz, and In-So Kweon.  Cd-uap: Class discriminative universal adversarial perturbation.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(04):6754–6761, Apr. 2020a.  doi: 10.1609/aaai.v34i04.6154.  URL https://ojs.aaai.org/index.php/AAAI/article/view/6154.
  * Zhang et al. [2021] Chaoning Zhang, Philipp Benz, Chenguo Lin, Adil Karjauv, Jing Wu, and In So Kweon.  A survey on universal adversarial attack.  In Zhi-Hua Zhou, editor, _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21_ , pages 4687–4694. International Joint Conferences on Artificial Intelligence Organization, 8 2021.  doi: 10.24963/ijcai.2021/635.  URL https://doi.org/10.24963/ijcai.2021/635.  Survey Track.
  * Zhang et al. [2020b] Hu Zhang, Linchao Zhu, Yi Zhu, and Yi Yang.  Motion-excited sampler: Video adversarial attack with sparked prior.  In _ECCV_ , 2020b.

Figure 7: The relation between infinity norm and the corresponding type#1
performance. From left to right, the infinity norm is 4, 6, 8, 10 separately.

Figure 8: CityScapes Type#2 and Type#3 attack on DeepLabV3Plus model with
MobileNet backbone. For Type#2 attack, the model learns to add a new set of
’person’ labels in the prediction. Type#3 attack combines both Type#1 and
Type#2 by vanishing ‘person’ and ‘rider’ labels into the background, and
adding a new set of ’person’ labels in the prediction. Top left: The input
image. Top right: The input image + perturbations. Lower left: Predictions
before attacks. Lower middle: Manipulated label mask. Lower right: Predictions
after attacks.

##  6 Supplementary Material

###  6.1 Infinity norm of the perturbations

Although there have been lots of discussions on how the infinity norm affects
the performance of adversarial attacks statistically, few of them are
visualized. Here we select four infinity norm thresholds and visualize the
corresponding performance on the same testing image. We choose to use
DeepLabV3Plus-MobileNet as the target model. Figure 7 shows how different
infinity norms, 4, 6, 8, 10 affect the performance of ‘person’ label
vanishment. The results suggest that as the infinity norm increases, our model
yields better performance against the target model.

###  6.2 Results of DeepLabV3Plus on CityScapes

In this session, we visualize samples of the ResNet-based models attack
against the DeepLabV3Plus-MobileNet-based target for different attack types.
Figure 9, Figure 11, Figure 8 show the result for type#1, type#2, type#3,
respectively.

We also visualize a sample of type#1 cross-modal attacks on Cityscape. We have
two models here. The first one is trained to attack a DeepLabV3Plus-MobileNet
model. The second one is trained to attack a DeepLabV3Plus-ResNet model. Then
these two target models are switched. Figure 12 shows the first model attacks
against the second model’s target while Figure 10 shows the second model
attacks against the first model’s target. The results are consistent with the
success rate showed in Table 3.

Finally, we also give the result of attacking DeepLabV3Plus-MobileNet for
type#2 and type#3 on Cityscapes, as Figure 8 shows.

Figure 9: Type#1 attack against DeepLabV3Plus-MobileNet model on Cityscapes.
The ‘person’ and ’rider’ labels vanish into the background. Top left: The
input image. Top right: The input image + perturbations. Lower left:
Predictions before attacks. Lower middle: Manipulated label mask. Lower right:
Predictions after attacks.

Figure 10: Type#1 attack against DeepLabV3Plus-MobileNet on Cityscapes. The
‘person’ and ‘rider’ labels vanish into the background. Our model is trained
to attack DeepLabV3Plus-Resnet and evaluate on DeepLabV3Plus-MobileNet. Top
left: The input image. Top right: The input image + perturbations. Lower left:
Predictions before attacks. Lower middle: Manipulated label mask. Lower right:
Predictions after attacks.

Figure 11: Type#1 attack against DeepLabV3Plus-ResNet on Cityscapes. The
‘person’ and ‘rider’ labels vanish into the background. Top left: The input
image. Top right: The input image + perturbations. Lower left: Predictions
before attacks. Lower middle: Manipulated label mask. Lower right: Predictions
after attacks.

Figure 12: .Type#1 attack against DeepLabV3Plus-ResNet on Cityscapes The
‘person’ and ‘rider’ labels vanish into the background. Our model is trained
to attack DeepLabV3Plus model with MobileNet backbone, and evaluate on
DeepLabV3Plus model with ResNet backbone. Top left: The input image. Top
right: The input image + perturbations. Lower left: Predictions before
attacks. Lower middle: Manipulated label mask. Lower right: Predictions after
attacks. Figure 13: The detailed structure of the generator. 3, 64, 128, 256
are number of channels.


# GenEFT: Understanding Statics and Dynamics of Model Generalization via
Effective Theory

David D. Baek, Ziming Liu, Max Tegmark
Massachusetts Institute of Technology
Cambridge, MA, USA
Correspondence to: Max Tegmark (tegmark@mit.edu).

###### Abstract

We present GenEFT: an effective theory framework for shedding light on the
statics and dynamics of neural network generalization, and illustrate it with
graph learning examples. We first investigate the generalization phase
transition as data size increases, comparing experimental results with
information-theory-based approximations. We find generalization in a
_Goldilocks zone_ where the decoder is neither too weak nor too powerful. We
then introduce an effective theory for the dynamics of representation
learning, where latent-space representations are modeled as interacting
particles (“repons”), and find that it explains our experimentally observed
phase transition between generalization and overfitting as encoder and decoder
learning rates are scanned. This highlights the power of physics-inspired
effective theories for bridging the gap between theoretical predictions and
practice in machine learning.

##  1 Introduction

A key feature if intelligence is the ability to generalize, exploiting
patterns seen in data to improve predictions for unseen data. There is
therefore great interest in how to choose datasets and model hyperparameters
that lead to generalization as opposed to overfitting, to which state-of-the-
art machine learning models with high complexity are often prone (Bejani &
Ghatee, 2021). The machine learning community has traditionally made such
choices on a case-by-case basis, without a unifying effective theory that
provides a systematic recipe for designing the generalizable model. In this
paper, we take a modest step toward such a theory by presenting GenEFT: a
unifying effective theory framework for understanding model generalization in
practice. Specifically, we aim to answer the following three questions:

Q1: _Critical data size_ – Given a problem, how large a dataset is needed for
the model to be generalizable?

Q2: _Optimal model complexity_ – How does model complexity affect
generalization?

Q3: _Critical learning rate_ – How do the learning rates affect
generalization?

We provide theoretical frameworks and empirical evidence to shed light on
these questions. In summary, our conclusions are as follows:

A1: We present an information-theoretic approximation that describes the
relationship between test accuracy and the amount of fraction of training
data. For graph learning, full generalization only becomes possible after
training on at least $b$ examples, where $b=\log_{2}N$ is the number of bits
required to specify which of $N$ possible graphs is present, and further
delays are caused both by correlated data and by the induction gap, bits
required to learn the inductive biases (graph properties) that enable
generalization.

A2: Generalization occurs in the complexity _Goldilocks zone_ where it is
capable enough to exploit a clever representation, but still incapable of
memorizing the training data.

A3: We successfully predict how the memorization/generalization phase
transition depends on encoder and decoder learning rates by modeling the
representations as interacting particles that we term “repons”.

In summary, we conclude that (a) static/steady state properties of
generalization, such as the critical training fraction and optimal model
complexity, could be derived from information-theoretic properties of the
input, and (b) dynamic properties of generalization, such as critical learning
rate, could be derived from studying the system of interacting repons,
particles whose locations are given by their embedding representations. This
framework is summarized in Figure 1.

The rest of this paper is organized as follows: In Section 2, we formally
describe our problem settings. In the following three sections, Section 3–5,
we tackle the three questions Q1, Q2, Q3, respectively, using a combination of
theoretical frameworks and empirical evidence. We discuss related work in
Section 6, and summarize our conclusions in Section 7.

Figure 1: A unifying framework for understanding generalization.

##  2 Problem Formulation

Consider an arbitrary binary relation $R$ of elements $x_{1},...,x_{n}$, for
example “greater-than” or “equal modulo 3”. This can be equivalently viewed as
a directed graph of order $n$, and is specified by the $n\times n$ matrix
$\textbf{R}_{ij}\equiv R(x_{i},x_{j})\in\\{0,1\\}$. Our machine-learning task
is to predict the probability that $R(x_{i},x_{j})=1$ by training on a random
data subset.

Model Architecture: We use an encoder-decoder architecture where the encoder
maps each input $x$ into a latent space representation
$\mathbf{E}_{x}\in\mathbb{R}^{d}$ after which an MLP decoder concatenates two
embeddings $[\mathbf{E}_{x_{1}},\mathbf{E}_{x_{2}}]$ and maps it into the
probability estimate. We use $\tanh$ activation in any hidden layers followed
by a sigmoid function to obtain the probability. The learnable parameters in
the model are the embedding vectors and well as the weights and biases in the
decoder MLP.

Datasets The relations $R$ that were used in our experiments are equal modulo
3, equal modulo 5, greater-than, and complete bipartite graph, whose formal
definitions are summarized in Table 1. These relations were chosen to provide
a broad diversity of relation properties. For instance, equal modulo 3 and
equal modulo 5 are equivalence classes (symmetric, reflexive, and transitive),
greater-than is total ordering (antisymmetric and transitive), while the
complete bipartite graph is symmetric and anti-transitive. We will see that
our effective theory is applicable to these general relations regardless of
their detailed properties. We used $n=30$ elements for our experiments. For
each relation, we thus have $n^{2}=900$ data samples $\textbf{R}_{ij}$. The
training data was randomly sampled from this set, and the remaining samples
were used for validation (testing).

Table 1: Relations used in the experiments. $S$ is one of two disjoint sets in a bipartite graph.  Relation | Description
---|---
Modulo $3$ |  $(x,y)\in R$ iff $x\equiv y\;(\textrm{mod}\;3)$
Modulo $5$ |  $(x,y)\in R$ iff $x\equiv y\;(\textrm{mod}\;5)$
Greater-than |  $(x,y)\in R$ iff $x<y$
Complete Bipartite Graph $G=(S,\overline{S})$ |  $(x,y)\in R$ iff ($x\in S,y\notin S$) or ($x\notin S$, $y\in S$)

##  3 Minimal Data Amount for Generalization

Table 2: Bits required to describe relations with various properties.  Relation | Description length $b$ [bits]
---|---
Generic | $n^{2}$
Symmetric | $n(n+1)/2$
Antisymmetric | $n(n+1)/2$
Reflexive | $n(n-1)$
Transitive |  $\approx\frac{n^{2}}{(\langle k\rangle-1)!}$, $\langle k\rangle$ is the average length of a transitive chain
Equivalence Relation with $k$ Classes | $\approx n\log_{2}k$
Total Ordering | $\log_{2}n!\approx n\textrm{log}_{2}{n\over 2}$
Complete Bipartite Graph | $n$
Incomplete Bipartite Graph $G=(S_{1},S_{2})$ | $|S_{1}||S_{2}|$
Tree Graph |  $\approx n\textrm{log}_{2}\langle d\rangle$ where $\langle d\rangle$ is the average node depth

Effective Theory: Information-theoretic Approach:

Let $b$ be the relation’s description length, i.e., the minimum number of
independent bits required to fully describe it. For graphs sampled uniformly
from a class with certain properties (transitivity and symmetry, say),
$b=\log_{2}C$, where $C$ is the total number of graphs satisfying these
properties. For instance, there are $n!$ total orderings, giving $b\approx
n\log_{2}(n/2)$ using Stirling’s approximation.

To fully generalize and figure out precisely which graph in its class we are
dealing with, we therefore need at least $b$ training data samples, since they
provide at most one bit of information each. As seen in Figures 2 and 3, $b$
indeed sets the approximate scale for how many training data samples are
needed to generalize, but to generalize perfectly, we need more than this
strict minimum for two separate reasons.

  1. 1.

$k$ data samples may provide less than $k$ bits of information because (a)
they are unbalanced (giving 0 and 1 with unequal probability) and (b) they are
not independent, with some inferable from others: for example, the data point
$R(x_{1},x_{2})$ for a symmetric relation implies that $R(x_{2},x_{1})=1$.

  2. 2.

We lack a priori knowledge of the inductive bias (what specific properties the
graph has), and need to expend some training data information to learn this –
we call these extra bits the inductive gap.

Figure 2 shows the theoretical maximum accuracy attainable, computed in two
steps. (a) First, we count the total number of directly inferable data pairs
using _a priori_ knowledge of the relation – for example, symmetry
reflexivity, and transitivity for equivalence relations – given the randomly
sampled set of training data pairs. (b) Second, we compute the probability
$p_{*}$ of guessing correctly for each case that is not directly inferable
from the training data. We do this via Monte Carlo simulation, considering all
possible equivalence class memberships (or all possible orderings for the
greater-than relation) that are compatible with the training data. The plotted
numerical prediction accuracy is a sum of 1 for each inferred relation and
${\rm max}(p_{*},1-p_{*})$ for each non-inferred one, all divided by the total
number of examples.

We also provide a simple but useful approximation for how much training data
is needed to read a testing accuracy $\alpha$ (say 90%). Let the $b$ bits that
describe the relation be $x_{1},x_{2},\cdots x_{b}$, and the number of
training data samples is $m$. In the crude approximation that each data sample
provides one bit worth of information, this is essentially the problem of
putting $m$ distinguishable balls into $b$ different buckets, and we want at
least a fraction $\alpha$ of the buckets to be non-empty. The ball that is
thrown into an already non-empty bucket does not provide extra information
about the relation and therefore, does not affect the prediction accuracy. We
use the indicator variable $Z_{i}$: $Z_{i}=1$ iff the bucket $x_{i}$ is empty,
$Z_{i}=0$ otherwise. Using the linearity of expectations,

$E\left(\sum_{i}Z_{i}\right)=\sum_{i}E(Z_{i})=b\left(1-\frac{1}{b}\right)^{m}\;\rightarrow\;E\left(\sum_{i}(1-Z_{i})\right)=b\left[1-\left(1-\frac{1}{b}\right)^{m}\right].$
(1)

The fraction of inferable data is hence

$f(m)\approx\frac{1}{b}E\left(\sum_{i}(1-Z_{i})\right)=\left[1-\left(1-\frac{1}{b}\right)^{m}\right].$
(2)

The critical training data fraction $p_{c}$ is given by $f(Np_{c})=\alpha$,
where $N=n^{2}$ is the total number of training samples. This gives the
following formula for critical training data fraction:

$p_{c}=\frac{1}{N}\frac{\textrm{log}_{2}(1-\alpha)}{\textrm{log}_{2}\left(1-\frac{1}{b}\right)},$
(3)

where the only dependence on the properties of the relation is through its
description length $b$. In addition to directly inferable samples using _a
priori_ knowledge of the relation, one can also guess the answer and get it
correct. Letting $p_{*}$ denote the probability of guessing correctly, the
approximation Eq. (2) gives the prediction accuracy

$f_{\rm UB}(m)=f(m)+\textrm{max}(p_{*},1-p_{*})(1-f(m)),.$ (4)

For an equivalence relation with $k$ classes, $p_{*}=1/k$. For a complete
bipartite graph, $p_{*}=1/2$, since there are only two clusters that each
element can belong to. For the greater-than relation, $p_{*}\approx 1/3$. In
order to understand this, consider a unit module consisting of three symbols
$\\{x,y,z\\}$, and we are given $x<y$. The only three possible orderings of
the three symbols are: $x<y<z$, $x<z<y$, and $z<x<y$. Since each of these
orderings are equally likely to be the actual ordering, the probability of
correctly guessing the pair $(x,z)$ or $(y,z)$ is $p_{*}=1/3$. We also
numerically validate this in Figure 2.

The dashed and solid curves in Figure 2 show rough agreement between this
approximation and the more exact Monte Carlo calculation for the inferrable
data fraction. One difference is that the training data include a certain
level of information also about the pairs that are not directly inferable,
improving the aforementioned accuracy term $p_{*}$. Another difference is that
data samples on average contain less than one bit (because they are not
independent), and that some samples contain more information than others. For
example, consider the task of learning greater-than relation on the numbers
$0$ to $9$. The sample $0<9$ never provides any extra information, whereas the
sample $4<5$ could be powerful if we already know the order of numbers $0$ to
$4$ – the comparison of at least 4 additional pairs, $(0,5),(1,5),(2,5),(3,5)$
can then be inferred.

Figure 2: Plot of numerical experiments (solid line) and analytic formula in
Eq. 2 (dotted line) for the theoretical upper bound of prediction accuracy
$f_{\rm UB}$ as a function of training data fraction.

Figure 2 compares our numerical experiments (solid line) with our analytic
approximation (dotted line, Eq. (4)).

Neural Network Experiments:

Figure 3 shows the empirical results of prediction accuracy vs. training data
fraction for our neural network experiments. For direct comparison with our
theoretical curves, prediction accuracy was computed over the entire dataset,
including both the training data and the testing data.

Figure 3: Prediction accuracy vs. training data fraction for learning the
relations (a) equivalent modulo 3, and (b) greater-than. We see that applying
inductive bias to the decoder MLP architecture (making it simpler while still
capable to succeed) improves the performance (reduces the “induction gap” gap
relative to the theoretical upper bound). In the legend, $n_{h}$ is the number
of hidden layers, $w$ is the width of the hidden layers, mode indicates how
the two embeddings are combined, and the dimension is that of the embedding
space. Vertical lines show the approximate transition scale $b/n^{2}$.

In Figure 3, we see that the neural generalization curves roughly track our
theoretical prediction, with a slightly delayed rise, presumably for the two
aforementioned reasons. Also, generalization may occur at a much later
training step, due to delayed generalization/grokking.

We term the architecture-dependent part of this delay the inductive gap.
Figure 3 illustrates that the inductive gap decreases when it is simplified by
including more inductive bias in the model. We will now aim to provide
intuition for this finding.

We have defined three modes for combining encoder outputs into decoder input:

  1. 1.

The default mode, where the input to the decoder is the concatenation of two
embeddings $[\mathbf{E}_{x_{1}},\mathbf{E}_{x_{2}}]$,

  2. 2.

The decoder’s input is $(\mathbf{E}_{x_{1}}-\mathbf{E}_{x_{2}})$, and

  3. 3.

The decoder’s input is $|\mathbf{E}_{x_{1}}-\mathbf{E}_{x_{2}}|^{2}$, element-
wise squared.

For learning equivalence modulo 3, the ideal embedding would be to cluster
numbers into three distinct positions on a 1-dimensional line corresponding to
the 3 equivalence classes. Hence, one expects the neural network to learn that
$P[R(x_{1},x_{2})=1]=1$ iff $\mathbf{E}_{x_{1}}=\mathbf{E}_{x_{2}}$. This is
distinguished by mode 3 followed by a single ReLU$(0.1-x)$ activation, say.
This embedding and decoder automatically enforce the symmetry, transitivity,
and reflexivity of this relation, enabling it to exploit these properties to
generalize. Indeed, Figure 3(a) shows that the inductive gap is the smallest
for a network in mode 3 with 0 hidden layers. In contrast, the more complex
neural networks in the figure waste some of the training data just to learn
this useful inductive bias.

For learning the greater-than relation, the ideal encoding would be to embed
numbers on a 1-dimensional line in their correct order. Hence, one expects the
neural network to learn $P[R(x_{1},x_{2})=1]=1$ iff
$({E}_{x_{1}}-{E}_{x_{2}})>0$. This is best learned in mode 2: the relation
holds if the decoder’s input is positive – which can be accomplished with a
single ReLU activation. Indeed, Figure 3(b) shows that the inductive gap is
the smallest for a network in mode 2 with 0 hidden layers. In summary, we have
illustrated that applying correct inductive bias to the neural network’s
architecture reduces the inductive gap, thereby improving its generalization
performance.

##  4 Optimal Model Complexity for Generalization

Liu et al. (2022a) postulated that encoder-decoder architectures have a
_Goldilocks zone_ of decoder complexity such that generalization fails both
when the decoder is too simple and when it is too complex. In this section, we
validate this conclusion with our graph learning experiments. Let the decoder
have $n_{h}$ layers of uniform width $w$ so that the total number of trainable
weight and bias parameters is approximately $w^{2}n_{h}$.

Figure 4 shows testing accuracy vs. decoder depth for our example relations.
All cases reveal the existence of a (i.e. sweet spot) where generalization
occurs, degrading on both sides. When the decoder is too simple, it lacks the
ability to correctly decode learned embeddings, thus failing to provide any
useful gradient information for the encoder — the result is confusion, with
not even the training accuracy becoming good. When the decoder is too complex,
it is able to correctly decode even random and extremely inconvenient
encodings, again failing to provide any useful gradient information for the
encoder — the result is memorization (overfitting), with high training
accuracy but low test accuracy.

We see that the Goldilocks zone for learning greater-than relation is slightly
off compared to the other three relations. We relate this to the fact that as
in Figure 3(a), learning the greater-than relation can easily reach $\approx
90\%$ accuracy, but struggles to reach $100\%$. Since most of the samples can
be easily guessed from a few other samples, the test accuracy does not easily
go below $90\%$. A small number of samples that cannot be guessed from any
other samples, of the form $i<(i+1)$, does not impact the testing accuracy by
a noticeable margin.

Figure 4: Plot of testing accuracy vs. decoder depth for the four example
relations. Decoder width $w=10$, and the training fraction of $0.6$ were used
in the experiments.

##  5 Critical Learning Rates for Generalization

Effective Theory: Interacting Repon Theory As our neural network is trained,
the embedding vectors gradually move to hopefully form useful representations.
In this section, we study the dynamics of this motion by viewing each
representation vector as a “repon” particle, moving in response to
interactions with other repons. We show that when the optimal representation
involves these particles forming distinct clusters (as for learning
e.g.equivalence relations), attraction/repulsion between same-cluster repons
corresponds to generalization/overfitting.

Although the global loss landscape of a neural network is typically nonlinear,
we consider what happens when two embeddings $\textbf{x}_{1}$ and
$\textbf{x}_{2}$ are sufficiently close that the decoder can be locally
linearized as $D(\textbf{x})\approx\textbf{A}\textbf{x}+\textbf{b}$. If the
two belong in the same cluster, so that the loss function is minimized for
$D(\textbf{x}_{1})=D(\textbf{x}_{2})=\textbf{y}$, say, then the training loss
for this pair of samples can be approximated as

$\ell=\frac{1}{2}(|\textbf{A}\textbf{x}_{1}+\textbf{b}-\textbf{y}|^{2}+|\textbf{A}\textbf{x}_{2}+\mathbf{b}-\mathbf{y}|^{2}).$
(5)

Both the decoder $(\textbf{A},\textbf{b})$ and the encoder (the repon
positions $\textbf{x}_{1}$, $\textbf{x}_{2}$) are updated via a gradient flow,
with learning rates $\eta_{A}$ and $\eta_{x}$, respectively:

$\frac{d\mathbf{A}}{dt}=-\eta_{A}\frac{\partial\ell}{\partial\mathbf{A}},\frac{d\mathbf{b}}{dt}=-\eta_{A}\frac{\partial\ell}{\partial\mathbf{b}},\frac{d\mathbf{x}_{i}}{dt}=-\eta_{x}\frac{\partial\ell}{\partial\mathbf{x}_{i}}\
(i=1,2).$ (6)

Substituting $\ell$ into the above equations simplifying as detailed in
Appendix C, we obtain

$\displaystyle\frac{d\textbf{A}}{dt}=-2\eta_{A}\textbf{A}\textbf{r}\textbf{r}^{T},\;\frac{d\textbf{r}}{dt}=-\eta_{x}\textbf{A}^{T}\textbf{A}\textbf{r},$
(7)

where $\mathbf{r}\equiv(\mathbf{x}_{1}-\mathbf{x}_{2})/2$ is half the repon
separation.

This repon pair therefore interacts via a quadratic potential energy
$U(\mathbf{r})=\frac{1}{2}\mathbf{r}^{T}\textbf{A}^{T}\textbf{A}\mathbf{r}$,
leading to a linear attractive force
$F(\textbf{r})\propto-\textbf{A}^{T}\textbf{A}\textbf{r}$ which is accurate
whenever two repons are sufficiently close together. In one embedding
dimension, this is like Hookes’ law for an elastic spring pulling the repons
together, except that the spring is weakening over time. Eq. (7) has simple
asymptotics: (i) If $\mathbf{A}$ is constant or $\eta_{A}=0$, two repons will
eventually collide, i.e., $r\to 0$. (ii) In the opposite limit, if
$\mathbf{r}$ is constant or $\eta_{x}=0$, A will converge to $\mathbf{0}$
while $r>0$. In the general case where $\eta_{x},\eta_{A}>0$, Eq. (7) is a
competition between which of A and r decays faster, whose outcome depends on
$\eta_{A}$ and $\eta_{x}$,as well as the initial values of $\mathbf{A}_{0}$
and $\mathbf{r}_{0}$. Without loss of generality, we can rescale the embedding
space so that $|\textbf{r}_{0}|=1$.

General case: It is easy to check Eq. (7) has a solution of the following
form:

$\mathbf{A}(t)=a(t)\mathbf{A}_{0}+b(t)\mathbf{A}_{0}\mathbf{r}_{0}\mathbf{r}_{0}^{T},\quad\mathbf{r}(t)=c(t)\mathbf{r}_{0}.$
(8)

Substituting this into Eq. (7) and defining $a_{2}(t)\equiv a(t)+b(t)$ gives
the differential equations

$\displaystyle\frac{da_{2}}{dt}=-2\eta_{A}c^{2}a_{2},\;\frac{dc}{dt}=-\eta_{x}a_{2}^{2}c,$
(9)

whose fixed point $(a_{2}^{*},c^{*})$ defined by $da_{2}/dt=0,dc/dt=0$
requires $a_{2}^{*}=0$ or $c^{*}=0$. A repon collision happens if $c^{*}=0$.
Interestingly, there is a conserved quantity

$C\equiv\frac{1}{2\eta_{A}}a_{2}^{2}-\frac{1}{\eta_{x}}c^{2},$ (10)

because $dC/dt=0$. This defines a hyperbola and the value $C$ is determined by
initialization. If $C>0$, $c^{*}\to 0$ and $a_{2}^{*}\to\pm\sqrt{2\eta_{A}C}$,
resulting in repon collision (generalization). If $C<0$,
$c^{*}\to\pm\sqrt{-\eta_{x}C}$ and $a_{2}^{*}\to 0$, leading to no collision
(memorization). When the initial conditions $a_{2}^{(0)}$ and $c^{(0)}$ are
drawn from a normal distribution with width $\sigma_{a}$ and $\sigma_{c}$
respectively, the probability of representation learning (i.e., $c^{*}\to 0$)
is

$\displaystyle p_{r}$
$\displaystyle=\underset{\frac{c}{a}<\sqrt{\frac{\eta_{x}}{2\eta_{A}}}}{\iint}\frac{1}{2\pi\sigma_{a}\sigma_{x}}{\rm
exp}\left(-\frac{1}{2}\left[\left(\frac{a}{\sigma_{a}}\right)^{2}+\left(\frac{c}{\sigma_{c}}\right)^{2}\right]\right)dadc$
(11) $\displaystyle=\frac{2}{\pi}{\rm
arctan}\left(\frac{\sigma_{a}}{\sigma_{c}}\sqrt{\frac{\eta_{x}}{2\eta_{A}}}\right),$

which provides a practical prescription for enhancing representation learning.
Below, we provide empirical evidence that supports this theory.

Figure 5: Phase diagram as a function of the encoder learning rate
$\eta_{\textrm{enc}}$ and decoder learning rate $\eta_{\textrm{dec}}$ for (a)
modulo 3, (b) greater-than, and (c) complete bipartite relations. All figures
indicate a slope-1 boundary between the generalization and memorization
phases, as predicted by the interacting repon theory. Green, yellow, and
purple regions indicate the generalization, delayed generalization (grokking),
and memorization phase respectively.

Neural Network Experiments: Figure 5 shows the generalization/memorization
phase diagram as a function of the encoder learning rate $\eta_{\textrm{enc}}$
and the decoder learning rate $\eta_{\textrm{dec}}$ for different relations.
Phase classification criteria are described in Appendix B. Generalization can
be interpreted as the probability of representation learning in Eq.(11)
exceeding a certain threshold. Hence, in a phase diagram as a function of
encoder and decoder learning rates with logarithmic axes, one would expect the
generalization-memorization boundary to have slope $-1$, which is indeed
observed in Figure 5. Moreover, the phase boundary appears approximately at
the same intercept, which also matches the prediction of Eq. 11 that the
probability of representation learning should be task-independent, and only
depends on the weight initialization. As a rule of thumb, we see that
generalization requires that the learning rate product
$\eta_{\textrm{enc}}\eta_{\textrm{dec}}\mathrel{\hbox to0.0pt{\lower
3.0pt\hbox{$\mathchar 536\relax$}\hss}\raise 2.0pt\hbox{$\mathchar
316\relax$}}10^{-7}$. We provide additional phase diagrams in Appendix D that
further validate the interacting repon theory.

##  6 Related Work

Physics of Machine Learning: Physics-based methodologies have been widely used
to develop theories for deep learning. These include employing effective
theories (Roberts et al., 2022; Halverson et al., 2021), conservation laws
(Kunin et al., 2020), and general paradigms in statistical physics such as
phase diagrams and free-energy principle (Gao & Chaudhari, 2020; Liu et al.,
2022a; b). Our work provides a physics-inspired framework for understanding
generalization, where the dynamic properties of generalization are described
by studying the physics of interacting particles whose positions are given by
their positions in the embedding space.

Model Generalizability in Machine Learning: There is a rich literature on
studying out-of-distribution generalization (Liu et al., 2021; Ye et al.,
2021). However, most of these studies focus on empirically extracting
invariant features over multiple domains and lack an analysis of why and when
generalization occurs. Our study attempts to fill this gap by pursuing a
unifying effective theory. Our study also complements the previous studies on
generalization in learning modular addition (Liu et al., 2022a; b) by
presenting theories and empirical results for general mathematical relations.

Learning Mathematical Relations: Machine learning has been utilized to
understand various mathematical entities, such as geometry (He, 2023) and knot
theory (Gukov et al., 2021). Our work provides physics-based effective
theories for understanding _how_ neural networks learn mathematical relations.

##  7 Conclusion

We have presented an effective theory framework for understanding the statics
and dynamics of model generalization in practice. In particular, we have
studied the minimal data size needed, optimal model complexity, and critical
decoder learning rates for generalization. While some static properties could
be quite well described by our effective theory, incorporating more
information about the input data’s structures into the theory may contribute
to further bridging the theory-experiment gap. There is ultimately a trade-off
between the complexity of the theory and its accuracy. In this regard, we
believe our information-theory-based approximation is helpful for
understanding static properties of generalization. The theory of dynamic
properties for generalization was largely well-supported by the relevant
empirical phase diagrams.

Our study suggests the following unifying framework for understanding
generalization: static properties of generalization can be derived from
information-theoretic properties of the input data, while the dynamic
properties of generalization can be understood by studying the system of
interacting particles, repons. Our work also highlights the power of physics-
inspired effective theories for bridging the gap between theoretical
predictions and practice in machine learning.

### Data and Code Availability

We will provide data and codes upon request.

### Acknowledgments

We thank the Center for Brains, Minds, and Machines (CBMM) for hospitality.
This work was supported by The Casey and Family Foundation, the Foundational
Questions Institute, the Rothberg Family Fund for Cognitive Science and IAIFI
through NSF grant PHY-2019786.

## References

  * Bejani & Ghatee (2021) Mohammad Mahdi Bejani and Mehdi Ghatee.  A systematic review on overfitting control in shallow and deep neural networks.  _Artificial Intelligence Review_ , pp. 1–48, 2021.
  * Gao & Chaudhari (2020) Yansong Gao and Pratik Chaudhari.  A free-energy principle for representation learning.  In _International Conference on Machine Learning_ , pp. 3367–3376. PMLR, 2020.
  * Gukov et al. (2021) Sergei Gukov, James Halverson, Fabian Ruehle, and Piotr Sułkowski.  Learning to unknot.  _Machine Learning: Science and Technology_ , 2(2):025035, 2021.
  * Halverson et al. (2021) James Halverson, Anindita Maiti, and Keegan Stoner.  Neural networks and quantum field theory.  _Machine Learning: Science and Technology_ , 2(3):035002, 2021.
  * He (2023) Yang-Hui He.  Machine-learning mathematical structures.  _International Journal of Data Science in the Mathematical Sciences_ , 1(01):23–47, 2023.
  * Kunin et al. (2020) Daniel Kunin, Javier Sagastuy-Brena, Surya Ganguli, Daniel LK Yamins, and Hidenori Tanaka.  Neural mechanics: Symmetry and broken conservation laws in deep learning dynamics.  _arXiv preprint arXiv:2012.04728_ , 2020.
  * Liu et al. (2021) Jiashuo Liu, Zheyan Shen, Yue He, Xingxuan Zhang, Renzhe Xu, Han Yu, and Peng Cui.  Towards out-of-distribution generalization: A survey.  _arXiv preprint arXiv:2108.13624_ , 2021.
  * Liu et al. (2022a) Ziming Liu, Ouail Kitouni, Niklas S Nolte, Eric Michaud, Max Tegmark, and Mike Williams.  Towards understanding grokking: An effective theory of representation learning.  _Advances in Neural Information Processing Systems_ , 35:34651–34663, 2022a.
  * Liu et al. (2022b) Ziming Liu, Eric J Michaud, and Max Tegmark.  Omnigrok: Grokking beyond algorithmic data.  _arXiv preprint arXiv:2210.01117_ , 2022b.
  * Roberts et al. (2022) Daniel A Roberts, Sho Yaida, and Boris Hanin.  _The principles of deep learning theory_.  Cambridge University Press Cambridge, MA, USA, 2022.
  * Ye et al. (2021) Haotian Ye, Chuanlong Xie, Tianle Cai, Ruichen Li, Zhenguo Li, and Liwei Wang.  Towards a theoretical framework of out-of-distribution generalization.  _Advances in Neural Information Processing Systems_ , 34:23519–23531, 2021.

##  Appendix A List of Default Hyperparameter Values

The hyperparameter values below were used for the experiments unless specified
otherwise.

Table 3: List of default hyperparameter values. Parameter |  Default Value
---|---
| Embedding Space Dimension
---
2
Weight Decay |  0
Learning Rate |  0.001
Training Data Fraction |  0.75
Decoder Depth |  3
Decoder Width |  50
Activation Function |  Tanh

##  Appendix B Definition of Phases

We have followed the phase classification criteria of Liu et al. (2022a).

Table 4: Phase classification criteria. | Criteria
---|---
Phase | train acc $>0.9$ | test acc $>0.9$ | (steps to test acc $>0.9$)
within $10^{5}$ steps | within $10^{5}$ steps |  $-$ (steps to train acc $>0.9$) $<$ $10^{3}$
Generalization | Yes | Yes | Yes
Grokking | Yes | Yes | No
Memorization | Yes | No | N/A
Confusion | No | No | N/A

##  Appendix C Derivation of Eq. (7)

The gradient flow is:

$\displaystyle\frac{d\mathbf{A}}{dt}=-\eta_{A}\frac{\partial\ell}{\partial\mathbf{A}}=-\eta_{A}[\mathbf{A}(\mathbf{x}_{1}\mathbf{x}_{1}^{T}+\mathbf{x}_{2}\mathbf{x}_{2}^{T})+(\mathbf{b}-\mathbf{y})(\mathbf{x}_{1}+\mathbf{x}_{2})^{T}],$
(12)
$\displaystyle\frac{d\mathbf{b}}{dt}=-\eta_{A}\frac{\partial\ell}{\partial\mathbf{b}}=-\eta_{A}(\mathbf{A}(\mathbf{x}_{1}+\mathbf{x}_{2})+\mathbf{b}-\mathbf{y})$
$\displaystyle\frac{d\mathbf{x}_{i}}{dt}=-\eta_{x}\frac{\partial\ell}{\partial\mathbf{r}}=-\eta_{x}\mathbf{A}^{T}(\mathbf{A}\mathbf{x}_{i}+\mathbf{b}-\mathbf{y}),\
(i=1,2).$

Without loss of generality, we can choose the coordinate system such that
$\mathbf{x}_{1}+\mathbf{x}_{2}=\mathbf{0}$. For the $d\mathbf{b}/dt$ equation:
setting the initial condition $\mathbf{b}(0)=\mathbf{0}$ gives
$\mathbf{b}(t)=(1-e^{-2\eta_{A}t})\mathbf{y}$. Inserting this into the first
and third equations gives

$\displaystyle\frac{d\mathbf{A}}{dt}=-2\eta_{A}\mathbf{A}\mathbf{r}\mathbf{r}^{T}$
(13)
$\displaystyle\frac{d\mathbf{x}_{i}}{dt}=-\eta_{x}\mathbf{A}^{T}\mathbf{A}\mathbf{x}_{i}+\eta_{x}e^{-2\eta_{A}t}\mathbf{A}^{T}\mathbf{y}$

Now define the relative position
$\mathbf{r}\equiv(\mathbf{x}_{1}-\mathbf{x}_{2})/2$ and subtracting
$d\mathbf{x}_{1}/dt$ by $d\mathbf{x}_{2}/dt$ we get:

$\displaystyle\frac{d\mathbf{A}}{dt}=-2\eta_{A}\mathbf{A}\mathbf{r}\mathbf{r}^{T},$
(14)
$\displaystyle\frac{d\mathbf{r}}{dt}=-\eta_{x}\mathbf{A}^{T}\mathbf{A}\mathbf{r}.$

##  Appendix D Additional Phase Diagrams

Figure 6: Phase diagram as a function of the decoder’s weight decay
$wd_{\textrm{dec}}$ and the decoder’s learning rate $\eta_{\textrm{dec}}$ for
(a) modulo 3, (b) greater-than, and (c) complete bipartite relations. All
figures indicate that the memorization-generalization boundary is independent
of the weight decay, which is consistent with the result of interacting repon
theory in Eq. (11). Note that grokking is also a form of generalization, but
the delayed generalization. Encoder’s learning rate was fixed to
$\eta_{\textrm{enc}}=10^{-5}$ in the experiment.


-titleUHECR 2012 11institutetext: LPNHE, 4 place Jussieu, 75252 Paris CEDEX 05, France 22institutetext: Observatorio Pierre Auger, Av. San Martín Norte 304, 5613 Malargüe, Argentina
(Full author list:
%****␣IoanaMarisSpectrum.tex␣Line␣50␣****http://www.auger.org/archive/authors_2012_06.html)

#  Measurement of the energy spectrum of cosmic rays at the highest energies
using data from Pierre Auger Observatory

Ioana C. Mariş for the Pierre Auger Collaboration 11
<EMAIL_ADDRESS>22

###### Abstract

We report a measurement of the flux of cosmic rays with unprecedented
precision and statistics using data from the Pierre Auger Observatory. Based
on fluorescence observations in coincidence with at least one station of the
surface detector we derive a spectrum for energies above $10^{18}$ eV. We also
report on the energy spectra obtained with the surface detector array. The
spectral features are presented in detail and the impact of systematic
uncertainties on these features are addressed.

##  1 Introduction

The propagation and the origin of cosmic rays influence the number of
particles that enter the Earth’s atmosphere. The evolution of the flux with
energy exhibits at the highest energies two features: the ankle, a flattening
of the flux at about $4\times 10^{18}$ eV, and a strong suppression above
$5\times 10^{19}$ eV. Currently it is not clear if these features are caused
by the interaction of the particles with the cosmic background, or if they are
hints of changes in the acceleration origin or power Berezinsky:2005cq ;
Hillas:2005cs ; Wibig:2004ye ; Allard:2008gj . A precise measurement of the
flux of cosmic rays is an important ingredient in discriminating between
theoretical models.

The Pierre Auger Observatory is designed as an hybrid detector: a surface
detector (SD) with more than 1600 water-Cherenkov stations placed on a
triangular grid covering $3000\,\mathrm{km^{2}}$ and a fluorescence detector
(FD) made of 27 optical telescopes grouped in five buildings, observing the
atmosphere above the array. The detailed description of the Observatory can be
found in EngArray ; SDDet ; FDDet . The hybrid design allows for the energy
calibration of the SD data and for obtaining the energy spectrum over two
decades in energy. We present the measurements of the flux of cosmic rays
above $10^{18}$ eV.

##  2 Air-showers reconstruction

The FD observes the fluorescence and Cherenkov light produced by the secondary
particles from the air-showers in their passage through the atmosphere. The
arrival direction is obtained from the timing information of the signal in
individual triggered pixels and from at least one station of the SD. This set
of events are referred to as hybrid events. From the reconstruction of the
longitudinal profiles michael  the energy of the primary particle is inferred
in an almost calorimetric way. The invisible energy, the fraction of energy
carried by the muons and neutrinos, is obtained from parametrization of
simulations assuming a mixed composition and QGSJet01 as hadronic interaction
model. It is less than 10% above $10^{18}\,\mathrm{eV}$. The energy resolution
is $7.6\%$ FrancescoICRC .

The signal from the particles reaching the ground is sampled with the water-
Cherenkov detectors. The content of the air-showers at this level depends on
the amount of matter traversed by the cascade. For vertical events (zenith
angle smaller than 60 degrees) the signal contains contributions from both the
electromagnetic and muonic components of the air-showers. At angles above 62
degrees (inclined events), the electromagnetic component is suppressed. This
effect leads to different reconstruction methods for vertical and inclined
events. In the first case the signal at 1000 m from the air-shower axis,
S(1000), is interpolated from a lateral distribution function. S(1000) is
corrected for the attenuation in the atmosphere through a constant intensity
method: an air-shower with a zenith angle of 60 degrees produces a signal
smaller by a factor of two then if it would have had an arrival direction of
zero degrees (see Fig. 1 (left)). The energy estimator for the vertical events
is $S_{38}$, the equivalent signal for a zenith angle of 38 degrees.
RobertoICRC ; SpectrumSD . The reconstruction of the inclined events is based
on a detailed modeling of the two dimensional muon density on the ground
InclinedReco . The energy estimator, $N_{19}$ is obtained by taking as a
reference the normalization of the footprint of proton initiated air-showers
with an energy of $10^{19}\,\mathrm{eV}$ and it is independent of the zenith
angle(Fig. 1(right)).

0.41!

Figure 1:  (left) S(1000) as a function of the zenith angle. (right) The
number of events above $N_{19}=0.89$ as a function of the zenith angle.

Figure 2: Example of an event with an energy of $7\times 10^{19}\,\mathrm{eV}$
falling in the middle of the surface detector and observed with at least one
telescope from each of the FD buildings (left); (right) the independent energy
assignments from the four eyes (CO, LA, LM, LL) and from the surface detector
(SD).

An event example with an energy of $7\times 10^{19}\,\mathrm{eV}$ is shown in
Fig. 2. The air-shower has triggered at least one telescope in each FD
buildings and the surface detector. The energies reconstructed independently
with the data from the four eyes are in a very good agreement, even if the
air-shower is more than 20 km away. The energy measured from the SD data
agrees with the FD reconstructions. The details of how we measure the energy
with the SD are given next.

### Energy calibration and resolution

Figure 3: The energy calibrations curves for the inclined events (left) and
for the vertical events (right). The lines represent the best fit to data.

To convert $N_{19}$ and $S_{38}$ to energy we use golden hybrid events: a sub-
sample of the hybrid events which are independently triggered and
reconstructed with the SD. We are selecting high quality longitudinal
profiles, observed during a time period with clear atmosphere Abraham:2010pf ,
with a cloud coverage of less than 25%. Deeply penetrating air-showers would
produce a larger signal on the ground that shallow ones. Thus, in order to
reduce a possible mass composition bias we apply strict cuts on the fiducial
field of view which assure an equal hybrid trigger probability for different
primaries.

The correlation functions are obtained by maximizing the likelihoods and are
in both cases almost linear RobertoICRC ; HansICRC :

$E_{\rm inclined}=(4.69\pm 0.09)\times 10^{18}\,\mathrm{eV}\cdot
N_{19}^{(1.05\pm 0.02)},\hskip 8.61108ptE_{\rm vertical}=(1.68\pm 0.05)\times
10^{17}\,\mathrm{eV}\cdot S_{38}^{(1.035\pm 0.009)}$ (1)

The energy calibrations, shown in Fig. 3, induce a systematic uncertainty on
the energy due to the limited statistics: 125 events for the inclined data and
839 for the vertical data. Namely 7% at $10^{19}\,\mathrm{eV}$ and 12% at
$10^{20}\,\mathrm{eV}$ for the vertical events and 13% at
$10^{19}\,\mathrm{eV}$ and more than 50% at $10^{20}\,\mathrm{eV}$ for the
inclined events. In the future with more accumulated data, these uncertainties
will be reduced. Assuming a constant energy resolution for the hybrid energy
of $\approx 8\%$, the energy resolution for the vertical data set can be
obtained from the golden hybrid events (Fig. 4). The resulting SD energy
resolution decreases from $\sigma_{E}/E_{\rm vertical}=(15.8\pm 0.9)\%$ below
$6\times 10^{18}\,\mathrm{eV}$ to $(12.0\pm 1.0)\%$ for $E_{\rm
SD}>10^{19}\,\mathrm{eV}$, the reconstruction uncertainties being important at
$3\times 10^{18}\,\mathrm{eV}$, while at the highest energies the shower-to-
shower fluctuations of S(1000) are dominant.

Figure 4: The ratio between the energies reconstructed with the hybrid and the
surface detector data for different energy intervals: between $3\times
10^{18}\,\mathrm{eV}$ and $6\times 10^{18}\,\mathrm{eV}$ (left) between
$6\times 10^{18}\,\mathrm{eV}$ and $10^{19}\,\mathrm{eV}$ (center) and above
$10^{19}\,\mathrm{eV}$ (right).

Figure 5: Comparison between data and MC. The distributions are shown for
QGSJet II.03 for proton and iron. Simulations have been rescaled to take into
account the missing number of muons. (left) Normalized distribution of the
number of events as a function of the zenith angle; (center) Normalized
distribution of the signal in individual stations for all the stations in the
recorded and simulated events; (right) Normalized distribution of the FD and
SD energy ratio.

The three measurements with inclined, vertical and hybrid events inherit the
same systematic uncertainty on the energy from the fluorescence detector
energy assignment. The determination of the absolute value of the fluorescence
yield contributes with 14%, the reconstruction of the energy with 4% due to
the invisible energy correction, and 10% from the reconstruction of the
longitudinal profiles, while the atmospheric effects add another 8%. The total
systematic uncertainty of 22%, includes as well the calibration of the
detector, and the propagated uncertainties of the aerosol optical depth
measurements RobertoICRC .

##  3 Energy spectrum

The energy resolution of the surface detector is energy dependent and thus it
distorts the distribution of events as a function of energy by bin-to-bin
migrations. To obtain the true number of events a forward-folding procedure is
used. The migration matrices are built from air-showers and detector
simulations by using CORSIKA corsika  with QGSJet II.03 qgsjetII  as hadronic
interaction model. Even if the number of muons is underestimated in the
simulations Muons , after an energy rescaling such that for the same true
$S_{38}$ we obtain the same energy in data and simulations, the distributions
in the main shower observables are reproduced by the simulations: in Fig. 5
are depicted the normalized distribution for events with an energy above
$3\times 10^{18}\,\mathrm{eV}$ of the zenith angle, of the signal per station
including all stations in the events and of the ratio of the energy
determinations with the FD and SD, for proton and iron primaries.

0.62!

Figure 6: Exposures for the vertical and inclined SD measurements together
with the hybrid one. The SD exposures are illustrated only for the energy
range of full trigger efficiencies. The exposure for the 750 m spacing array
(infill) is also shown.

0.62!

Figure 7: The energy spectra measured with the data recorded at the Pierre
Auger Observatory. All the three measurements are in a very good agreement in
the energy range of overlap.

The exposure calculation for the surface detector is based on the time
integration of the instantaneous effective area SDAperture . It amounts up to
end of 2010 to 20905 km2 sr year for the vertical data, while for the inclined
events it is four times smaller due to the reduced solid angle considered
(zenith angle between 62 and 80 degrees). The SD energy spectra RobertoICRC ;
HansICRC  are deduced only in the energy range with full trigger efficiency,
i.e. $3\times 10^{18}\,\mathrm{eV}$ for the vertical events and $4\times
10^{18}\,\mathrm{eV}$ for the inclined events. The enhancement of the surface
detector with a denser array AMIGAICRC  (750 m spacing between detectors) has
been completed. It will increase the energy range for the SD by one decade.
The integrated exposure for the same period amounts to 29 km2 sr year
IoanaICRC . In case of the hybrid measurement the exposure calculation is
based on detailed simulations of the detector FDExposure , taking into account
its time evolution. The simulations consider, besides the SD and FD hardware
status every 10 minutes, all the atmosphere measurements and monitoring data.
The lower energy limit is given by the trigger probability of the SD: above
$10^{18}$ eV all events with a zenith angle of less than 60 degrees produce a
signal in at least one SD station ltp . The exposures are represented in Fig.
6, while the energy spectra obtained with the three data sets are illustrated
in Fig. 7. The agreement between the energy spectra is very good, the
difference in fluxes is less than 5%. All the energy spectra share the same
systematic uncertainty on the energy, 22%, due to the cross-calibration of the
surface detector data with the hybrid energy determination. The systematic
uncertainties caused by the exposure determination and energy resolution
effects, are independent. For the hybrid measurement they vary from 10% at
$10^{18}$ eV to 6% at $>10^{19}$ eV. In the case of the vertical surface
detector they are 6% (3% exposure determination and 5% from the unfolding of
the energy resolution effects) while for the inclined spectrum the exposure
contributes with a similar systematic uncertainties. Taking into account the
independent systematic uncertainties of the hybrid and vertical SD
measurements we obtain an energy spectrum which extends over the whole energy
range above $10^{18}$ eV (Fig. 8). The inclined spectrum has not been yet
deconvoluted for the energy resolution effects and thus not included in the
combination. To determine the changes in the flux evolution with energy we fit
two functions: three power laws with free breaks and two power laws with a
sigmoid suppression. The spectral index changes from $(-3.27\pm 0.02)$ to
$(-2.68\pm 0.01)$ at $\log_{10}(E/{\rm eV})=18.61\pm 0.01$ and then to
$(-4.2\pm 0.1)$ at $\log_{10}(E/{\rm eV})=19.41\pm 0.02$.

0.6!

Figure 8: The features of the Auger energy spectrum as obtained from fits with
two functions (see text). The systematic uncertainties on the energy mount up
to 22% and are not shown in the graph.

##  4 Conclusions

The flux of cosmic rays with energies above $10^{18}$ eV has been measured
with the data of the Pierre Auger Observatory, with three independent methods.
The agreement between the energy spectra in the regions of overlap is better
than 5%, well within the independent systematic uncertainties. The change in
the spectral index at $(4.1\pm 0.2)\times 10^{18}$ eV, the ankle, and the flux
suppression starting at $(2.6\pm 0.2)\times 10^{19}$ eV have been measured
with very large statistics. The current measurements are dominated by the
systematic uncertainties on the energy, 22%. To achieve a more accurate
measurement of the spectral features the systematic uncertainties on the
energy, mostly due to the fluorescence yield and reconstruction, will be
reduced. The extension of the array with the denser sub-detector will allow
the measurement of the spectral slope down to $4\times 10^{17}$ eV and the
overlap with the KASCADE-Grande measurement KG . A further enhancement to even
lower energies, with an array of 350 m spacing, is foreseen. We have measured
77 events above $5\times 10^{19}$ eV in the vertical surface detector data
set, corresponding to about 4 years of full detector efficiency. In order to
accumulate more statistics at the highest energies, a continuation of the data
taking and of the detector maintenance is essential.

## References

  * (1) V. Berezinsky, A. Z. Gazizov, and S. I. Grigorieva, Phys. Lett. B612 (2005) 147.
  * (2) A. M. Hillas, J. Phys. G31 (2005) R95.
  * (3) T. Wibig and A. W. Wolfendale, J. Phys., G31 (2005) 255.
  * (4) D. Allard et al., JCAP 0810 (2008) 033.
  * (5) The Pierre Auger Collaboration, Nucl. Instr. and Meth. A523 (2004) 50.
  * (6) I. Allekotte et al., Nucl. Instr. and Meth. A586 (2008) 409.
  * (7) The Pierre Auger Collaboration, Nucl. Instr. and Meth. A620 (2010) 227.
  * (8) M. Unger et al., Nucl. Instr. Meth. A 588 (2008) 433.
  * (9) F. Salamida for the Pierre Auger Collaboration, Proc. 32nd ICRC (2011), arXiv:1107.4809v1.
  * (10) The Pierre Auger Collaboration, Astropart. Phys. 33 (2010) 108.
  * (11) R. Pesce for the Pierre Auger Collaboration, Proc. 32nd ICRC (2011), arXiv:1107.4809v1.
  * (12) The Pierre Auger Collaboration, Phys. Rev. Lett. 101 (2008) 061101.
  * (13) G. Rodriguez for the Pierre Auger Collaboration, these proceedings.
  * (14) H. Dembinski for the Pierre Auger Collaboration, Proc. 32nd ICRC (2011), arXiv:1107.4809v1.
  * (15) D. Heck et al. Report FZKA 6019, Forschungszentrum Karlsruhe (1998).
  * (16) S. Ostapchenko, Nucl. Phys. B (Proc. Suppl.) 151 (2006) 143.
  * (17) A. Yushkov for the Pierre Auger Collaboration, these proceedings.
  * (18) The Pierre Auger Collaboration, Nucl. Instr. and Meth. A613 (2010) 29.
  * (19) F. Sanchez for the Pierre Auger Collaboration, Proc. 32nd ICRC (2011), arXiv:1107.4807v1.
  * (20) I. C. Mariş for the Pierre Auger Collaboration, Proc. 32nd ICRC (2011), arXiv:1107.4809v1.
  * (21) The Pierre Auger Collaboration, Astropart. Phys. 34 (2011) 368.
  * (22) The Pierre Auger Collaboration, Astropart. Phys, 35 (2011) 266.
  * (23) The Pierre Auger Collaboration, Phys. Lett. B 685 (2010) 239.
  * (24) The KASCADE-Grande Collaboration, Astropart. Phys. 36 (2012) 183.