#  PALBERT: Teaching ALBERT to Ponder

Nikita Balagansky, Daniil Gavrilov
Tinkoff
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Currently, pre-trained models can be considered the default choice for a wide
range of NLP tasks. Despite their SoTA results, there is practical evidence
that these models may require a different number of computing layers for
different input sequences, since evaluating all layers leads to overconfidence
in wrong predictions (namely overthinking). This problem can potentially be
solved by implementing adaptive computation time approaches, which were first
designed to improve inference speed. Recently proposed PonderNet may be a
promising solution for performing an early exit by treating the exit layer’s
index as a latent variable. However, the originally proposed exit criterion,
relying on sampling from trained posterior distribution on the probability of
exiting from the $i$-th layer, introduces major variance in exit layer
indices, significantly reducing the resulting model’s performance. In this
paper, we propose improving PonderNet with a novel deterministic Q-exit
criterion and a revisited model architecture. We adapted the proposed
mechanism to ALBERT and RoBERTa and compared it with recent methods for
performing an early exit. We observed that the proposed changes can be
considered significant improvements on the original PonderNet architecture and
outperform PABEE on a wide range of GLUE tasks. In addition, we also performed
an in-depth ablation study of the proposed architecture to further understand
Lambda layers and their performance.

##  1 Introduction

These days, fine-tuning pre-trained models on downstream tasks became a de
facto standard technique for training NLP models (Devlin et al., 2019; Liu et
al., 2019; Lan et al., 2020; Radford et al., 2019). Although, as model sizes
increase, it becomes harder to use them for real world applications due to
computational footprint. Because of this fact, practitioners may desire to
perform an early model exit (i.e., with adaptive computation time (Graves,
2016)) to reduce the computation needed for a specific model input.

Figure 1: A comparison of the original sampling exit criterion of PonderNet
(on the left) and the proposed Q-exit criterion (on the right). PonderNet
performs sampling from the Bernoulli distribution obtained from the Lambda
layer at each step, possibly exiting a model too early or too late. For
Q-exit, we evaluate the Cumulative distribution function (CDF) of the
probability of exiting at layer $i$. Once CDF becomes greater than the
threshold value ($0.5$ in this example), we perform an early exit. With such a
deterministic criterion, we can perform an early exit from a model more
robustly without introducing variance in the exit layer’s index during
inference.

One model that is widely used in real-world applications is ALBERT (Lan et
al., 2020), which is based on the Transformer architecture (Vaswani et al.,
2017) with shared layers (i.e., the same layer is evaluated several times to
provide an output). Sharing layer weights allows us to think of ALBERT as of
recurrent model that simplify development of early exit methods. Most of them
(Teerapittayanon et al., 2016; Liu et al., 2020; Xin et al., 2020) rely on
performing an early exit based on entropy of predictions during the model
evaluation. Although, Zhou et al. (2020) showed that running the ALBERT-Base
block for a fixed number of times (10) could increase the accuracy of the
fine-tuned model on specific tasks (e.g., MRPC) despite the entropy of
predictions monotonously decreasing for all 12 layers. A recent PABEE solution
(Zhou et al., 2020) was designed to overcome this issue by performing an early
exit based on the consensus between different classifier heads from different
layers. The model stops evaluating when several classifiers in a row produce
the same result.

A possible orthogonal solution for this task is PonderNet (Banino et al.,
2021) – a variational approach that treats the exit layer’s index as a latent
variable. By maximizing the lower bound of the likelihood of the training
data, PonderNet trains a model which can predict whether it is necessary to
exit from a specific layer during evaluation. However, Banino et al. (2021)
proposed to sample from the trained posterior distribution of exiting from
each layer during inference, which leads to major variance in exit layer
indices.

This paper proposes improving PonderNet adapted for ALBERT (Lan et al., 2020)
and RoBERTa (Liu et al., 2019) fine-tuning (PALBERT and PRoBERTa). Instead of
performing an early exit by sampling from the trained posterior distribution
during evaluation, we used a novel zero-variance exit criterion, namely
Q-exit, which evaluates the CDF of the exit layer’s probability distribution
and performs a deterministic early exit. We also revisited the architectural
choices of Lambda layers used to predict the probability of exiting from the
current layer to make them aware of dynamics in hidden states across previous
layers and the number of currently running layers.

We experimented with PALBERT and PRoBERTa on the GLUE Benchmark datasets (Wang
et al., 2018). The ablation study showed that PALBERT produced significantly
better results than the original PonderNet architecture adapted for ALBERT
fine-tuning. Furthermore, the proposed methods outperformed PABEE and are
comparable to plain ALBERT fine-tuning, while also exceeding it in speeds. We
also analyzed the trained model and provided insights on further improvement
of the variational approach for early exiting111Source code:
https://github.com/tinkoff-ai/palbert.

##  2 Related Work

Most of the approaches used to perform an early exit from a model are based on
the probability distribution of predictions: BranchyNet (Teerapittayanon et
al., 2016), FastBERT (Liu et al., 2020), DeeBERT (Xin et al., 2020), which can
be seen as an entropy criterion. Xin et al. (2021) proposed BERxiT with LTE
layer used to estimate the correctness of predictions during the inference
based on the hidden state from the specific layer.

However, there is strong practical evidence that classification models’
overthinking causes a reduction in predictions’ entropy, making these methods
difficult to use (Zhou et al., 2020). Furthermore, it is unclear how to adapt
entropy methods for regression tasks (Zhou et al., 2020). Zhou et al. (2020)
proposed PABEE – a method to perform an early exit based on several
classifiers from the different levels of a model. Once several classifiers in
a row (the number of these classifiers is determined by the patience
hyperparameter $t$) produce the same result, we can perform an early exit.
Several recent works also utilized the idea of a consensus-based exiting
strategy (Zhu, 2021; Liao et al., 2021). Although, most of them mainly augment
the basic consensus scheme with orthogonal heuristics. Because of this, we did
not include them in our experiments and only used PABEE as a consensus-based
method.

An alternative way to perform an early exit is the Ponder architecture (Banino
et al., 2021), which uses auxiliary Lambda layers to predict whether a model
should exit from a specific layer during runtime. Inputs to Lambda layers used
in PonderNet are hidden states from the current layer of a model. PonderNet
can be seen as a model with the latent variable that corresponds to the exit
layer index, which is trained by maximizing the lower bound of the
marginalized likelihood of the data.

During inference, Banino et al. (2021) proposed to sample from the trained
posterior distribution of exit layer probabilities. However, this exit
criterion can lead to uncertainty in exit layers for the same input (see
Section 4.5. Even if the Lambda layer produced a probability equal to $0.1$ of
exiting from the first layer, we could still exit a model too early in one of
ten cases, even though the probability was small. We also hypothesize that
predicting exiting from a layer based entirely on a single hidden state could
be sub-optimal since performing early exit could also depend on the dynamics
in hidden states across layers (i.e., the Lambda layer should know how hidden
states change during the evaluation).

##  3 Improving PonderNet

In this section, we describe the adaption of PonderNet to the ALBERT model
(PALBERT). Although, it could be easily extended to other pre-trained models
such as RoBERTa (which we also used in our experiments).

The usual ALBERT evaluation can be defined as a computation of $n$ hidden
states $h_{i}=S(h_{i-1})$ from the input embeddings $h_{0}$ of an input
sequence $x$, where $i\in[1;n]$. Once $h_{n}$ is obtained, it is passed to a
classifier block $C(h_{n})$ to get the parameters of an output distribution
$p(y|x)$. A common way to fine-tune this architecture on downstream tasks is
to initialize the embeddings and the $S$ layer by using ALBERT (pre-trained on
Masked Language Modelling) while initializing $C$ randomly and then optimizing
all parameters by maximizing the likelihood of the training data.

While plain ALBERT performs a fixed number of computational steps, it is
possible to perform an arbitrary number of evaluations of the layer $S$.
Banino et al. (2021) proposed to extend each Transformer layer with a so-
called Lambda layer. More precisely, for each layer $i$, after $S$ outputs a
new $h_{i}$, it is then passed to the classifier and Lambda layers to get
parameters $C(h_{i})$ of output distributions $p(y|x,i)$ and the probability
of exiting from the $i$-th layer $\lambda_{i}=\Lambda(h_{i})$, which induces a
generalized geometric distribution on probability of exiting from layer $i$
equal to $p(i|x)=\lambda_{i}\prod_{j=1}^{i-1}(1-\lambda_{j})$.

Then, having the probability distribution from each layer $p(y|x,i)$, the
parameters of the model are optimized to maximize

$\begin{split}L(x,y)=\mathbb{E}_{i\sim
p(i|x)}\Big{[}\log\big{(}p(y|x,i)\big{)}\Big{]}-\beta
KL\Big{(}p(\cdot|x)||p(\cdot|\lambda)\Big{)}\leq\log\big{(}p(y|x))\end{split}$
(1)

Here, $p(\cdot|\lambda)$ is a prior geometric distribution of exiting from
each layer, parametrized by the hyperparameter $\lambda$, and
$\mathbb{E}_{i\sim p(i|x)}\Big{[}\log\big{(}p(y|x,i)\big{)}\Big{]}$ is
evaluated analytically by averaging likelihoods from different layers with
posterior exit probabilities. If we treat the exit layer index as a latent
variable, then optimizing $L$ from the Equation 1 could be seen as maximizing
the lower bound of marginalized log likelihood $\log\big{(}p(y|x)\big{)}$
(Kingma and Welling, 2014).

Note that following Banino et al. (2021) the prior probability of exiting from
the last layer $n$ is normalized as
$p(n|\lambda)=1-\sum_{i=1}^{n-1}p(i|\lambda)$ in order to make $p(i|\lambda)$
sum into $1$ with a finite number of steps, while $p(i|x)$ it truncated by the
lowest layer index $j$, s.t. $\sum_{i=1}^{j}p(i|x)\geq 1-0.05$ (thus,
$KL(\dots)$ is evaluated only with first $j$ layers). Also note that weights
of Lambda layers are shared across layers of the model.

###  3.1 Exit Criterion

During inference, Banino et al. (2021) proposed to sample the exit layer index
from $p(i|x)$ (i.e., by sampling iteratively from a Bernoulli distribution
with parameter $\lambda_{i}$). While a sampling-based exit criterion
correlates with the variational view of PonderNet’s training objective, such
estimation introduces the randomness in the inference process of PonderNet.

To overcome the issue of randomness, we propose Q-exit222Q-exit stands for
Quantile: a novel deterministic criterion of performing an early exit, which
we used for PALBERT. Instead of sampling from the distribution $p(i|x)$ during
inference, we evaluate its CDF by accumulating $p(i|x)$ from each layer. Once
the CDF is greater than the threshold hyperparameter $q$, we perform an early
exit333The proposed exit criterion is the simplest deterministic criterion
which we came to, since there is no ability to estimate mean or argmax
statistics during the inference without running all layers of the model, which
is impractical if we want to perform an early exit.. See Figure 1 for a
schematic comparison of the sampling criterion with Q-exit. Threshold $q$ can
be seen as a trade-off between underthinking and overthinking. Therefore, $q$
should be selected during the validation of the trained model to choose the
best-performing value.

Based on our experiments, we found that the proposed criterion produced
significantly better accuracy on various tasks compared to the original
sampling criterion (see Sections 4.1, 4.2), while also being more practical
than the original sampling criterion.

###  3.2 Lambda Layer Architecture

While the original PonderNet used a single layer MLP to obtain logit of
exiting probability, we hypothesize that making the Lambda layer understand
the dynamics of changing ALBERT hidden states is crucial for achieving good
performance. To do so, instead of passing a single hidden state $h_{i}$ from
the $i$-th layer in $\Lambda$, we concatenate it with $h_{i-1}$. I.e., for
PALBERT, we evaluate the probability of exiting from $i$-th layer as
$\lambda_{i}=\Lambda([h_{i},h_{i-1}])$.

We used a $3$ layer MLP with $\tanh$ activation for the Lambda layer to
operate with more complex input. Based on the ablation study, we observed that
increasing the capacity improves the accuracy of the trained model (See
section 4.1). We also found it beneficial to fine-tune the Lambda layer with a
different learning rate than all other parameters.

Method | SST-2 | RTE | CoLA
---|---|---|---
ALBERT | 92.7 ± 0.3 | 77.0 ± 1.9 | 57.0 ± 2.1
ALBERT + PonderNet | 91.1 ± 0.6 | 73.5 ± 1.9 | 50.8 ± 2.2
ALBERT + PonderNet (Closed-Form Expectation) | 92.3 ± 0.4 | 76.8 ± 3.0 | 55.9 ± 2.2
Q-exit | Lambda LR | 3-Layer Lambda |  $h$ concat. |
+ | - | - | - | 92.2 ± 0.3 | 77.3 ± 1.4 | 55.7 ± 0.9
+ | + | - | - | 92.7 ± 0.4 | 77.3 ± 1.4 | 56.5 ± 1.2
+ | + | + | - | 92.6 ± 0.3 | 77.0 ± 1.4 | 56.3 ± 2.4
+ | + | - | + | 93.0 ± 0.3 | 76.5 ± 1.6 | 56.9 ± 1.9
+ | + | + | + | 92.9 ± 0.2 | 77.8 ± 1.2 | 57.4 ± 1.7

Table 1: An ablation study of the proposed PALBERT architecture. "Lambda LR"
corresponds to fine-tuning the Lambda layer with its learning rate, "3-layer
Lambda" refers to making the Lambda layer have three MLP layers instead of
one, and "$h$ concat." stands for concatenation of two hidden states as input
to the Lambda layer.

##  4 Experiments

###  4.1 Ablation Study

We performed an ablation study of the proposed changes in PonderNet
architecture with PALBERT.

We experimented with adding the proposed Q-exit criterion, Lambda layer
architecture, and fine-tuning strategies. These methods were benchmarked on
SST-2, RTE, and CoLA tasks from the GLUE Benchmarking dataset (Wang et al.,
2018).

We compared proposed changes with plain ALBERT and PonderNet adapted for
ALBERT. Also, in these experiments we compared with PonderNet evaluated in
expectation of predictions (e.g., evaluated $p(y|x)=\mathbb{E}_{i\sim
p(i|x)}\Big{[}p(y|x,i)\Big{]}$ in closed-form). While such a model is
impractical for early exiting setup (it does not perform any early exit but
evaluates all layers to estimate the expectation), it could show a gap between
closed-form expectation of model predictions and its single sample Monte Carlo
estimation.

For evaluation, we performed a grid hyperparameter search on an appropriate
metric score on the dev split for each dataset. Following the PABEE training
setup, we trained all models with a fixed learning rate until validation
metrics stopped increasing for $5$ epochs. We used Adam optimizer (Kingma and
Ba, 2015) for all experiments, a fixed $q=0.5$ on models with the Q-exit
criterion, as well as a fixed classifier dropout value equal to $0.1$
(Srivastava et al., 2014), and $\lambda=0.1$.

We trained each model $5$ times with the best hyperparameters and reported the
mean and std values. A full list of the methods’ hyperparameter ranges can be
found in Table 4.

Method | SST-2 | RTE | QNLI | CoLA | MRPC | MNLI | QQP | STS-B | Macro
---|---|---|---|---|---|---|---|---|---
Dev set
ALBERT | 92.7 | 76.5 | 91.5 | 56.6 | 90.5 | 84.8 | 88.9 | 90.6 | 84.0
ALBERT (9 L.) | 91.1 | 74.2 | 91.2 | 56.9 | 89.7 | 84.3 | 89.7 | 90.1 | 83.4
ALBERT PABEE | 92.7 | 76.9 | 91.5 | 55.6 | 88.3 | 84.5 | 88.9 | 89.9 | 83.5
ALBERT PonderNet | 91.3 | 74.0 | 88.3 | 51.3 | 87.1 | 81.7 | 87.7 | 88.2 | 81.2
PALBERT (ours) | 93.1 | 78.3 | 91.0 | 58.1 | 89.3 | 84.7 | 88.9 | 89.9 | 84.2
Test set
ALBERT | 93.4 | 70.0 | 92.1 | 50.5 | 85.6 | 79.0 | 84.7 | 87.4 | 80.3
ALBERT PABEE | 92.7 | 71.1 | 91.3 | 46.0 | 84.3 | 79.2 | 83.7 | 86.5 | 79.3
ALBERT PonderNet | 90.2 | 68.6 | 88.5 | 43.7 | 84.3 | 81.1 | 77.4 | 83.6 | 77.2
PALBERT (ours) | 93.0 | 73.5 | 91.7 | 48.6 | 87.1 | 79.8 | 84.4 | 86.5 | 80.6

Table 2: A comparison of PALBERT with recent approaches on the GLUE benchmark.
In the Macro column, we present the average results across tasks. We bolded
the best results. Note that we did not bold the ALBERT rows since there is no
early exit applied and we reported it for reference.

Method | SST-2 | RTE | QNLI | CoLA | MRPC | MNLI | QQP | STS-B | Macro
---|---|---|---|---|---|---|---|---|---
Dev set
RoBERTa | 94.5 | 79.4 | 92.4 | 63.1 | 91.3 | 86.7 | 89.8 |  90.7 | 86.0
RoBERTa PABEE | 93.8 | 76.9 | 91.9 | 60.7 | 89.6 | 86.4 | 91.1 | 89.9 | 85.0
PRoBERTa (ours) | 93.7 | 79.1 | 91.6 | 62.2 | 90.2 | 86.7 | 91.1 | 89.9 | 85.6
Test set
RoBERTa | 94.5 | 74.1 | 93.1 | 58.9 | 89.1 | 86.5 | 80.9 | 88.4 | 83.2
RoBERTa PABEE | 95.4 | 71.7 | 92.0 | 51.2 | 87.6 | 86.2 | 80.4 | 86.2 | 81.3
PRoBERTa (ours) | 94.5 | 72.1 | 91.8 | 58.6 | 88.3 | 86.1 | 79.6 | 85.7 | 82.1

Table 3: A comparison of PRoBERTa with recent approaches on the GLUE
benchmark. In the Macro column, we present the average results across tasks.
We bolded the best results. Note that we did not bold the RoBERTa rows since
there is no early exit applied and we reported it for reference.

See Table 1 for the full list of the results of our ablation study. Based on
these experiments, PonderNet architecture is seen as performing worse than
vanilla ALBERT fine-tuning. Also, PonderNet with closed-form evaluation of
predictions expectation performed better than the sampling criterion,
indicating that randomness in exit layers leads to poor performance.

At the same time, the deterministic Q-exit criterion improves PonderNet
accuracy when compared to a random sampling of the exit layer and is
comparable to the evaluation of PonderNet in expectation. A more complex
Lambda layer that can handle the dynamics of hidden state changes can further
improve model accuracy when compared to the original PonderNet.

###  4.2 GLUE Experiments

We compared PALBERT with PonderNet architecture adapted for ALBERT fine-
tuning, and PABEE with a fixed patience value $t=6$ on all GLUE tasks. We also
trained Ponder RoBERTa (PRoBERTa) and compared it with PABEE and adapted for
RoBERTa. Note that we re-implemented all baselines used in our experiment for
consistency in comparison. See Appendix Section A for the details of
reimplementation.

Following the experimental setup from Section 4.1, we trained $5$ models with
the best hyperparameters across the hyperparameter search and reported the
median task score on the dev set. We evaluated the test scores on the best
models, selected based on their dev scores. We report the two metrics’ mean
for the MRPC, QQP, and STS-B tasks. For the MNLI task, we report the mean
accuracy across matched and mismatched datasets.

See Tables 2,3 for the full list of results. We observed that PALBERT
outperformed PABEE on a wide range of tasks. Vanilla PonderNet with the
sampling exit criterion performed the worst. Vanilla ALBERT outperformed PABEE
on most tasks and is comparable to PALBERT, while the latter has the highest
score averaged across all tasks (see Macro column in Tables 2, 3).

For experiments with RoBERTa, we observed that PRoBERTa outperformed PABEE on
Dev split, while it either performed better or marginally worse for the Test
set. Thus, PRoBERTa showed a higher macro score compared to PABEE.

Note that PABEE is performing poorly for tasks with a small dataset (e.g.,
CoLA, RTE). We hypothesize that this is caused by several independent
classifiers at each layer $C_{i}$ failing to train well enough, whereas
PALBERT was capable of utilizing knowledge sharing between layers.

Parameter | Values range
---|---
Learning rate | [1e-5, 2e-5, 3e-5, 5e-5]
Batch size | [16, 32, 128]
Lambda learning rate | [1e-5, 2e-5, 3e-5]
$\beta$ | [0.5]

Table 4: Hyperparameter search ranges used in all of our experiments.

Figure 2: PALBERT score dependency on the Q-exit threshold. We report the mean
and std values of task metrics across $5$ trained models. See section 4.3 for
more details

###  4.3 Understanding the Threshold of Q-exit

As noted previously in Section 3.1, we treat the threshold value $q$ of the
Q-exit criterion as a trade-off between underthinking and overthinking, where
increasing $q$ forces a model to evaluate more layers, and vice versa.

Therefore, it is necessary to find the best-performing threshold for each task
where a model has the highest accuracy. To do so, we evaluated trained PALBERT
models from the ablation study (see Section 4.1) on dev splits of tasks with
different values of $q$. We then averaged obtained metrics and reported the
mean and std values for various thresholds (See Figure 2 for the results).

We observed that exiting models with $q=0.5$ shows the best overall
performance for different tasks. Making $q$ greater than $0.5$ leads to a
reduction in accuracy and can often force models to evaluate all $12$ layers
of ALBERT-Base.

It is also notable that PALBERT, having a large threshold value $q$ that
performs constant exit on the last layer, has better accuracy than vanilla
ALBERT fine-tuned for the SST-2 task. This indicates that adding auxiliary
tasks for each layer of ALBERT improves performance compared to plain fine-
tuning with a single classifier on the last layer of the model.

###  4.4 Speed Analysis

While making $q<0.5$ improves inference speed, it can also lead to
underthinking and lower accuracy (see Figure 3). We compared PALBERT using
different threshold values $q$ to PABEE with different patience values $t$,
which stands for the number of layers necessary to output the same result in a
row to perform an early exit. We evaluated task scores for the specified
hyperparameters as well as the increase in speed when compared to vanilla
ALBERT inference of a full model with $12$ layers.

Overall, we observed that PALBERT mostly produced higher scores on different
tasks while also being slightly faster than PABEE. For the CoLA and MRPC
datasets, PALBERT performed better. The proposed method outperformed PABEE
while achieving the same increase in speed.

We observed questionable results on the SST-2 dataset: the best score for the
PABEE model is slightly higher than that of PALBERT. However, it was obtained
with a negligible increase in speed compared to ALBERT, as the best-performing
patience for this setup is $11$ layers while the whole model has only $12$
layers.

Furthermore, unlike PALBERT, PABEE performed significantly worse than plain
ALBERT fine-tuned on the CoLA and RTE tasks.

Figure 3: A comparison between PALBERT and PABEE models on SST-2, RTE, CoLA,
and MRPC tasks. We varied the threshold value of Q-exit for PALBERT and the
patience hyperparameter for PABEE to obtain the plots of task scores of
inference increasing in speed. 1x stands for plain ALBERT inference without
performing an early exit. The horizontal line corresponds to plain ALBERT
fine-tuning. See Section 4.4 for the analysis of these plots.

Figure 4: Histogram of exit layer indices with Q-exit criterion and different
prior distribution parameters $\lambda$ (top) alongside with task metrics for
trained models (bottom) for MRPC and RTE tasks. See Section 4.5 for more
details.

Figure 5: An estimation of $\mathbb{E}_{x\sim D}\Big{[}p(i|x)\Big{]}$, where
$p(i|x)$ is a trained posterior probability of exiting from layer $i$ of
PALBERT models across different tasks, $\lambda=0.1$, and $D$ is the
distribution of the training dataset. We took $5$ models trained on these
tasks and sampled exit layer indices for the training dataset’s inputs. We
smoothed the obtained probabilities for visibility. Note that these
probabilities could be seen as the distribution of exit layers across
different tasks for plain PonderNet with sampling criterion, which indicates
on high variance in indices of output layers.

###  4.5 On the Prior of PALBERT

While we used a fixed value of $\lambda=0.1$ in our main experiment following
Banino et al. (2021) (see Section 4.2), we also investigate the effect of
changing the parameter of the prior distribution on exit layer indices.

We followed the experimental setup from the previous sections and trained
models with $\lambda\in{[}0.1,0.15,0.25,0.5]$. For each $\lambda$, we had its
own best hyperparameter set, which was then used to train $5$ models.

See Figure 4 for the results. We observed that varying $\lambda$ affects the
performance of the trained model since it has a huge impact on the
distribution of exit layer indices. Although the best metric for the RTE task
was reached with $\lambda=0.08$, such a model mostly performs an exit from the
last layer. Meanwhile, $\lambda=0.08$ performs marginally worse than
$\lambda=0.1$ for MRPC.

Note that while Figure 4 was obtained using the Q-exit criterion, we could
also estimate $\mathbb{E}_{x\sim D}\Big{[}p(i|x)\Big{]}$ (see Figure 5), which
is the distribution of exit layer indices with vanilla sampling criterion
proposed by Banino et al. (2021). Even if $\lambda$ is low enough so that the
mode of distribution is the $12$-th layer, in almost half of the cases, the
sampling criterion forces the model to exit from one of the first $10$ layers.
We hypothesize that such randomness in the index of the exit layer leads to
the poor performance observed during previous experiments (see Section 4.2).

From such perspective, dependency on the explicit prior distribution could be
seen as the main limitation of the proposed method, since treating the exit
layer index as a latent variable justified its prior distribution. If proper
prior distribution was found, then the well-performing model could be trained,
and vice versa.

##  5 Future Work and Limitations

In this paper, we proposed improving the PonderNet architecture to perform an
early exit using fine-tuned ALBERT and RoBERTa models with the novel Q-exit
criterion and a revisited Lambda layer architecture. This approach is
orthogonal to the consensus-based approaches (Zhou et al., 2020; Zhu, 2021)
highly represented in the field.

While PALBERT and PRoBERTa outperformed some recent State-of-The-Art methods
used for an early exit, there is a clear direction for further improvement of
this method, as it was not capable of outperforming plain ALBERT and RoBERTa
on some GLUE tasks.

We believe that PALBERT could benefit from the development of a new
parameterization of the prior distribution on exiting from each layer since it
directly affects the resulting posterior distribution used to perform an early
exit (see Section 4.5). However, the development of an appropriate prior
distribution for early exiting models is orthogonal to the development of a
proper exit criterion.

Furthermore, there is no theoretical justification for the Q-exit threshold
value. Although we observed that $q=0.5$ performed best, it is without a clear
explanation as to why that is so. We hypothesize that bringing more insights
into developing deterministic exit criteria could further improve the proposed
method.

In addition, adding more auxiliary tasks could also make it possible to
improve PALBERT further. This way, PALBERT training can be made more PABEE-
like by making independent classifiers for each layer of the model or adding
self-distillation across layers.

While the variational view of the early exiting mechanism allows us to train
models which could be exited early, we observed that the overall performance
of the trained model highly depends on the prior distribution of exit layer
indices (see Section 4.5). Because of this, the proposed method requires more
computation for hyperparameter search compared to PABEE (Zhou et al., 2020).
We believe that, in order to further develop training-level early exiting, it
may be beneficial to move away from variational inference to some other form
of trainable mechanism without relying on exit layers’ explicit prior
knowledge.

## References

  * Banino et al. (2021) Andrea Banino, Jan Balaguer, and Charles Blundell. 2021.  Pondernet: Learning to ponder.  In _8th ICML Workshop on Automated Machine Learning (AutoML)_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Graves (2016) Alex Graves. 2016.  Adaptive computation time for recurrent neural networks.  Cite arxiv:1603.08983.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Kingma and Welling (2014) Diederik P. Kingma and Max Welling. 2014.  Auto-Encoding Variational Bayes.  In _2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings_.
  * Lan et al. (2020) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2020.  Albert: A lite bert for self-supervised learning of language representations.  In _International Conference on Learning Representations_.
  * Liao et al. (2021) Kaiyuan Liao, Yi Zhang, Xuancheng Ren, Qi Su, Xu Sun, and Bin He. 2021.  A global past-future early exit method for accelerating inference of pre-trained language models.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2013–2023, Online. Association for Computational Linguistics.
  * Liu et al. (2020) Weijie Liu, Peng Zhou, Zhiruo Wang, Zhe Zhao, Haotang Deng, and Qi Ju. 2020.  Fastbert: a self-distilling BERT with adaptive inference time.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020_ , pages 6035–6044. Association for Computational Linguistics.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  Cite arxiv:1907.11692.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: A simple way to prevent neural networks from overfitting.  _Journal of Machine Learning Research_ , 15(56):1929–1958.
  * Teerapittayanon et al. (2016) Surat Teerapittayanon, Bradley McDanel, and H. T. Kung. 2016.  BranchyNet: Fast inference via early exiting from deep neural networks.  In _Proceedings of the 23rd International Conference on Pattern Recognition_ , pages 2464–2469. IEEE.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , pages 5998–6008.
  * Wang et al. (2018) Alex Wang, Amapreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. 2018.  Glue: A multi-task benchmark and analysis platform for natural language understanding.  Cite arxiv:1804.07461Comment: https://gluebenchmark.com/.
  * Xin et al. (2020) Ji Xin, Raphael Tang, Jaejun Lee, Yaoliang Yu, and Jimmy Lin. 2020.  DeeBERT: Dynamic early exiting for accelerating BERT inference.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2246–2251, Online. Association for Computational Linguistics.
  * Xin et al. (2021) Ji Xin, Raphael Tang, Yaoliang Yu, and Jimmy Lin. 2021.  BERxiT: Early exiting for BERT with better fine-tuning and extension to regression.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 91–104, Online. Association for Computational Linguistics.
  * Zhou et al. (2020) Wangchunshu Zhou, Canwen Xu, Tao Ge, Julian McAuley, Ke Xu, and Furu Wei. 2020.  Bert loses patience: Fast and robust inference with early exit.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 18330–18341. Curran Associates, Inc.
  * Zhu (2021) Wei Zhu. 2021.  LeeBERT: Learned early exit for BERT with cross-level optimization.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 2968–2980, Online. Association for Computational Linguistics.

##  Appendix A Re-implementation of Baselines

While Zhou et al. (2020) provided official implementation of the proposed
method, we have several concerns regarding its reproducibility and
experimental setup. The original implementation implies running evaluation
iteration-wise (i.e., the best performing model is selected once in $n$
iterations).

In this case, several iterations $n$ between validation epochs could be seen
as an additional hyperparameter, which has a large impact on the resulting
performance. Although, Zhou et al. (2020) did not include the best performing
value so that the results could be easily reproduced.

Because of this, we decided to re-implement PABEE strictly following the
original paper and training details, while evaluating the model after every
epoch, instead of evaluating after $n$ training steps, which we believe is a
fairer way to compare methods.


# Li-Yorke chaos for composition operators on Orlicz spaces

Y. Estaremi Y. Estaremi<EMAIL_ADDRESS>Department of Mathematics, Faculty
of Sciences, Golestan University, Gorgan, Iran.

###### Abstract.

In this paper we characterize Li-Yorke chaotic composition operators on Orlicz
spaces. Indeed some necessary and sufficient conditions are provided for Li-
Yorke chaotic composition operator $C_{\varphi}$ on the Orlicz space
$L^{\Phi}(\mu)$. In some cases we have equivalent conditions for composition
operators on Orlicz spaces to be Li-Yorke chaotic. The results of this paper
extend similar results in $L^{p}$-spaces. Our results are essentially based on
the results of [4].

###### Key words and phrases:

Composition operator, Li-Yorke chaos, Orlicz space.

###### 2020 Mathematics Subject Classification:

47A16, 47B33

##  1\.  Introduction and Preliminaries

First of all, for the convenience of the reader, we recall some basic
properties of Orlicz spaces that we use in the sequel. For more details on
Orlicz spaces, see [11, 14].

A function $\Phi:\mathbb{R}\rightarrow[0,\infty]$ is called a Young’s function
if $\Phi$ is convex, $\Phi(-x)=\Phi(x)$, $\Phi(0)=0$ and
$\lim_{x\rightarrow\infty}\Phi(x)=+\infty$. With each Young’s function $\Phi$,
one can associate another convex function
$\Psi:\mathbb{R}\rightarrow[0,\infty]$ which is called complementary function
to $\Phi$, and has the same properties of it, which is defined as follows:

$\Psi(y)=\sup\\{x\mid y\mid-\Phi(x):x\geq 0\\},\ \ \ \ \ y\in\mathbb{R}.$

It is immediately follows from the definition that $\Psi$ is also a Young’s
function since $\Psi(0)=0$, $\Psi(-y)=\Psi(y)$ and $\Psi(.)$ is a convex
increasing function satisfying $\lim_{y\rightarrow\infty}\Psi(y)=+\infty$.
Also, it is clear that the pair $(\Phi,\Psi)$ satisfies Young’s inequality:

$xy\leq\Phi(x)+\Phi(y),\ \ \ \ \ \ \ \ x,y\in\mathbb{R}.$

The generalized inverse of the Young’s function $\Phi$ is defined by

$\Phi^{-1}(y)=\inf\\{x\geq 0:\Phi(x)>y\\}\quad(y\in[0,\infty)).$

Notice that if $x\geq 0$, then $\Phi\big{(}\Phi^{-1}(x)\big{)}\leq x$, and if
$\Phi(x)<\infty$, we also have $x\leq\Phi^{-1}\big{(}\Phi(x)\big{)}$. There
are equalities in either case when $\Phi$ is a Young’s function vanishing only
at zero and taking only finite values.

An especially useful nice Young’s function $\Phi$, called an $N$-function, is
such that $\Phi(x)=0$ iff $x=0$, $\lim_{x\rightarrow 0}\frac{\Phi(x)}{x}=0$
and $\lim_{x\rightarrow\infty}\frac{\Phi(x)}{x}=+\infty$, while
$\Phi(\mathbb{R})\subset\mathbb{R}^{+}$. Moreover, the complementary function
to an $N$-function is again an $N$-function.

Let $\Phi$ be a Young’s function. Then we say $\Phi$ satisfies the
$\Delta_{2}$-condition, if $\Phi(2x)\leq K\Phi(x)\;(x\geq x_{0})$ for some
constants $K>0$ and $x_{0}>0$. Also, $\Phi$ satisfies the
$\Delta_{2}$-condition globally if $\Phi(2x)\leq K\Phi(x)\;(x\geq 0)$ for some
$K>0$.

The Young’s function $\Phi$ is said to satisfy the $\Delta^{\prime}$-condition
(respectively, the $\nabla^{\prime}$-condition), if there exist $d>0$
(respectively, $b>0$) and $x_{0}>0$ such that

$\Phi(xy)\leq d\,\Phi(x)\Phi(y)\quad(x,y\geq x_{0})$ $(\mbox{respectively,
}\Phi(bxy)\geq\Phi(x)\Phi(y)\quad(x,y\geq x_{0})).$

If $x_{0}=0$, these conditions are said to hold globally. Notice that if
$\Phi\in\Delta^{\prime}$, then $\Phi\in\Delta_{2}$.

For a given complete $\sigma$-finite measure space$(X,\mathcal{F},\mu)$, let
$L^{0}(\mathcal{F})$ be the linear space of equivalence classes of
$\mathcal{F}$-measurable real-valued functions on $X$. For a given Young’s
function $\Phi$, the space

$L^{\Phi}(\mu)=\left\\{f\in L^{0}(\mathcal{F}):\exists
k>0,\int_{X}\Phi(kf)d\mu<\infty\right\\}$

is called an Orlicz space. Define the functional

$N_{\Phi}(f)=\inf\\{k>0:\int_{X}\Phi(\frac{f}{k})d\mu\leq 1\\}.$

The functional $N_{\Phi}(.)$ is a norm on $L^{\Phi}(\mu)$ and is called guage
norm(or Luxemburge norm). Also, $(L^{\Phi}(\mu),N_{\Phi}(.))$ is a normed
linear space. If almost everywhere equal functions are identified, then
$(L^{\Phi}(\mu),N_{\Phi}(.))$ is a Banach space, the basic measure space
$(X,\mathcal{F},\mu)$ is unrestricted. Hence every element of $L^{\Phi}(\mu)$
is a class of measurable functions that are almost everywhere equal. Also,
there is another norm on $L^{\Phi}(\mu)$, defined as follows:

$\|f\|_{\Phi}=\sup\\{\int_{X}\mid fg\mid d\mu:g\in
B_{\Psi}\\}=\sup\\{\mid\int_{X}fgd\mu\mid:g\in B_{\Psi}\\},$

in which $B_{\Psi}=\\{g\in L^{\Psi}(\mu):\int_{X}\Psi(\mid g\mid)d\mu\leq
1\\}$. The norm $\|.\|_{\Phi}$ is called Orlicz norm. For any $f\in
L^{\Phi}(\mu)$, $\Phi$ being a Young function, we have

$N_{\Phi}(f)\leq\|f\|_{\Phi}\leq 2N_{\Phi}(f).$

And also for every $F\in\mathcal{F}$ with $0<\mu(F)<\infty$, we have
$N_{\Phi}(\chi_{F})=\frac{1}{\Phi^{-1}(\frac{1}{\mu(F)})}$.

Throughout this paper, we denote by $(X,\mathcal{F},\mu)$, a measure space,
that is, $X$ is a nonempty set, $\mathcal{F}$ is a sigma algebra on $X$ and
$\mu$ is a positive measure on $\mathcal{F}$. Also, we assume that
$\varphi:X\rightarrow X$ is a non-singular measurable transformation, that is,
$\varphi^{-1}(F)\in\mathcal{F}$, for every $F\in\mathcal{F}$ and
$\mu(\varphi^{-1}(F))=0$, if $\mu(F)=0$. Moreover, if there exists a positive
constant $c$ for which

$\mu(\varphi^{-1}(F))\leq c\mu(F),\ \ \ \ \text{for every}F\in\mathcal{F},$

then the linear operator

$C_{\varphi}:L^{\Phi}(\mu)\rightarrow L^{\Phi}(\mu),\ \ \ \ \ \
C_{\varphi}(f)=f\circ\varphi,$

is well-defined and continuous on the Orlicz space $L^{\Phi}(\mu)$ and is
called composition operator. For more details on composition operators on
Orlicz spaces one can refer to [10].

In this paper we shall characterize Li-Yorke chaotic composition operators on
Orlicz spaces. Indeed we provide some equivalent conditions for composition
operators to be Li-Yorke chaotic.
Now we recall that a continuous map $f:\mathcal{M}\rightarrow\mathcal{M}$ on
the metric space $(\mathcal{M},d)$ is called Li-Yorke chaotic if there exists
an uncountable set $S\subseteq\mathcal{M}$ such that each pair $(x,y)\in
S\times S$, such that $x\neq y$, is a Li-Yorke pair for $f$, that is

$\lim_{n\rightarrow\infty}\inf d(f^{n}(x),f^{n}(y))=0,\ \ \ \ \text{and}\ \ \
\lim_{n\rightarrow\infty}\inf d(f^{n}(x),f^{n}(y))>0.$

The set $S$ is called scrambled set for $f$. If the scrambled set $S$ is dense
(respectively, residual) in $\mathcal{M}$, then $f$ is said to be densely
(respectively, generically) Li-Yorke chaotic. Characterizations for dense Li-
Yorke chaos and generic Li-Yorke chaos were investigated in [3]. Li-Yorke
chaotic linear operators are studied in [1, 3]. Specially, recently, Li-Yorke
chaotic composition operators on $L^{p}$-spaces investigated in [4]. Also, in
[4] the authors provided a necessary and sufficient condition on $\varphi$ for
$C_{\varphi}$ to be topologically transitive or topologically mixing on
$L^{p}(\mu)$. The reader can refer to [2, 5, 7, 6, 8, 9, 13] and references
therein, for a wide view of the linear dynamics.

##  2\. Li-Yorke chaotic composition operators

In this section we recall some results about Li-Yorke chaotic continuous
linear operators on Banach spaces [1, 3].

######  Theorem 2.1.

Let $T$ be a continuous linear operator on the Banach space $X$. Then the
followings are equivalent:

  * •

$T$ is Li-Yorke chaotic;

  * •

$T$ has a semi-irregular vector in $X$, in other words there exists $x\in X$
such that

$\lim_{n\rightarrow\infty}\inf\|T^{n}x\|=0\ \ \text{and}\ \
\lim_{n\rightarrow\infty}\sup\|T^{n}x\|>0;$

  * •

$T$ has an irregular vector in $X$, in other words, there is a vector $x\in X$
such that

$\lim_{n\rightarrow\infty}\inf\|T^{n}x\|=0\ \ \text{and}\ \
\lim_{n\rightarrow\infty}\sup\|T^{n}x\|=\infty.$

The following theorem gives necessary and sufficient conditions for
composition operators on the Orlicz space $L^{\Phi}(\mu)$ to be Li-Yorke
chaotic.

######  Theorem 2.2.

Let $C_{\varphi}$ be a continuous composition operator on the Orlicz space
$L^{\Phi}(\mu)$. The $C_{\varphi}$ on the Orlicz space $L^{\Phi}(\mu)$ is Li-
Yorke chaotic if and only if there exist a non-empty countable collection of
measurable sets $\\{F_{i}\\}_{i\in I}$ , with $0<\mu(F_{i})<\infty$ and an
increasing sequence $\\{\beta_{j}\\}_{j\in\mathbb{N}}\subseteq\mathbb{N}$ such
that:
(I)

$\lim_{j\rightarrow\infty}\Phi^{-1}(\frac{1}{\mu(\varphi^{-\beta_{j}}(F_{i}))})=\infty,\
\ \ \text{for all}\ \ \ i\in I,$

(II)

$\sup\\{\frac{\Phi^{-1}(\frac{1}{\mu(F_{i})})}{\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F_{i}))})}\>i\in
I,\ \ n\in\mathbb{N}\\}=\infty.$

###### Proof.

Let the composition operator $C_{\varphi}:L^{\Phi}(\mu):\rightarrow
L^{\Phi}(\mu)$ be Li-Yorke chaotic. Then by Theorem 2.1 $C_{\varphi}$ has an
irregular vector which we call it $f\in L^{\Phi}(\mu)$. We put

$F_{i}=\\{x\in X:2^{i-1}\leq|f(x)|<2^{i}\\},\ \ \ \ \ i\in\mathbb{Z}.$

It is clear that $F_{i}\in\mathcal{F}$, for all $i\in\mathbb{Z}$, and
$X=\cup_{i\in I}F_{i}$, in which $I=\\{i\in\mathbb{Z}:\mu(F_{i})>0\\}$. Since
$f\in L^{\Phi}(\mu)$, then there exists $\alpha>0$ such that
$\int_{X}\Phi(\alpha|f(x)|)d\mu<\infty$. This implies that for each $i\in I$
we have

$\Phi(2^{i-1}\alpha)\mu(F_{i})\leq\int_{X}\Phi(\alpha|f(x)|)d\mu<\infty$

and so $\mu(F_{i})<\infty$. By definition of irregular vectors we have
$\lim_{n\rightarrow\infty}\inf N_{\Phi}(C^{n}_{\varphi}f)=0$. Hence we can
find an increasing sequence $\\{\beta_{j}\\}_{j\in\mathbb{N}}$ of positive
integers such that
$\lim_{j\rightarrow\infty}N_{\Phi}(C_{\varphi}^{\beta_{j}}f)=0$. Now we have

$\displaystyle\int_{X}\Phi(\frac{2^{i-1}\chi_{\varphi^{-\beta_{j}}(F_{i})}}{N_{\Phi}(C^{\beta_{j}}_{\varphi}f)})d\mu$
$\displaystyle=\int_{\varphi^{-\beta_{j}}(F_{i})}\Phi(\frac{2^{i-1}\chi_{F_{i}}\circ\varphi^{\beta_{j}}}{N_{\Phi}(C^{\beta_{j}}_{\varphi}f)})d\mu$
$\displaystyle\leq\int_{\varphi^{-\beta_{j}}(F_{i})}\Phi(\frac{|f|\circ\varphi^{\beta_{j}}}{N_{\Phi}(C^{\beta_{j}}_{\varphi}f)})d\mu$
$\displaystyle\leq\int_{X}\Phi(\frac{|f|\circ\varphi^{\beta_{j}}}{N_{\Phi}(C^{\beta_{j}}_{\varphi}f)})d\mu$
$\displaystyle\leq 1.$

This implies that $N_{\Phi}(2^{i-1}\chi_{\varphi^{-\beta_{j}}(F_{i})})\leq
N_{\Phi}(C^{\beta_{j}}_{\varphi}f)$ and so

$2^{i-1}\lim_{j\rightarrow\infty}N_{\Phi}(\chi_{\varphi^{-\beta_{j}}(F_{i})})\leq\lim_{j\rightarrow\infty}N_{\Phi}(C^{\beta_{j}}_{\varphi}f)=0.$

Therefore for every $i\in I$,

$\lim_{j\rightarrow\infty}\frac{1}{\Phi^{-1}(\frac{1}{\mu(\varphi^{-\beta_{j}}(F_{i}))})}=0$

and consequently

$\lim_{j\rightarrow\infty}\Phi^{-1}(\frac{1}{\mu(\varphi^{-\beta_{j}}(F_{i}))})=\infty.$

Now consider that the condition (II) does not hold, it follows that there
exists a positive constant $c>0$ such that

(2.1)
$\frac{\Phi^{-1}(\frac{1}{\mu(F_{i})})}{\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F_{i}))})}\leq
c,\ \ \ \ \ \text{for all}\ \ i\in I,\ \text{and}\ \ n\in\mathbb{N}.$

Since $\Phi\in\Delta_{2}$ (globally), then there exists $\alpha\geq 2$ such
that $\Phi(2x)\leq\alpha\Phi(x)$, for every $x>0$. Also we can find $k>0$ such
that $\frac{c}{2^{k}}\leq 1$. Therefore we have

(2.2)
$\Phi(cx)=\Phi(\frac{c}{2^{k}}2^{k}x)\leq\frac{c\alpha^{k}}{2^{k}}\Phi(x).$

Hence by combining inequalities 2.1 and 2.2 we get that

(2.3)
$\mu(\varphi^{-n}(F_{i}))\leq\frac{c\alpha^{k}}{2^{k}}\mu(F_{i})\leq\alpha^{k}\mu(F_{i}),\
\ \ \ i\in I\ \ \text{and}\ \ \ \ n\in\mathbb{N}.$

Now we have

$\displaystyle\int_{X}\Phi(\frac{f\circ\varphi^{n}}{2(\alpha^{k}+1)N_{\Phi}(f)})d\mu$
$\displaystyle=\Sigma_{i\in
I}\int_{\varphi^{-n}(F_{i})}\Phi(\frac{f\circ\varphi^{n}}{2(\alpha^{k}+1)N_{\Phi}(f)})d\mu$
$\displaystyle\leq\Sigma_{i\in
I}\int_{\varphi^{-n}(F_{i})}\Phi(\frac{2^{i}}{2(\alpha^{k}+1)N_{\Phi}(f)})d\mu$
$\displaystyle=\Sigma_{i\in
I}\Phi(\frac{2^{i-1}}{(\alpha^{k}+1)\|f\|_{\Phi}})\mu(\varphi^{-n}(F_{i}))$
$\displaystyle\leq\frac{\alpha^{k}}{\alpha^{k}+1}\Sigma_{i\in
I}\Phi(\frac{2^{i-1}}{N_{\Phi}(f)})\mu(F_{i})$ $\displaystyle\leq\Sigma_{i\in
I}\int_{F_{i}}\Phi(\frac{2^{i-1}}{N_{\Phi}(f)})d\mu$
$\displaystyle\leq\Sigma_{i\in
I}\int_{F_{i}}\Phi(\frac{|f|}{N_{\Phi}(f)})d\mu$
$\displaystyle=\int_{X}\Phi(\frac{f}{N_{\Phi}(f)})d\mu\leq 1.$

This implies that $N_{\Phi}(C^{n}_{\varphi}f)\leq 2(\alpha^{k}+1)N_{\Phi}(f)$.
This is a contradiction, because $\lim_{n\rightarrow\infty}\sup
N_{\Phi}(C^{n}_{\varphi}f)=\infty$.
Conversely, let conditions (I) and (II) hold. So there exists
$\\{F_{i}\\}_{i\in I}\subseteq\mathcal{F}$, with $0<\mu(F_{i})<\infty$ such
that

$\lim_{j\rightarrow\infty}\frac{1}{N_{\Phi}(C^{-\beta_{j}}_{\varphi}\chi_{F_{i}})}=\lim_{j\rightarrow\infty}\frac{1}{N_{\Phi}(\chi_{\varphi^{-\beta_{j}}(F_{i})})}=\lim_{j\rightarrow\infty}\Phi^{-1}(\frac{1}{\mu(\varphi^{-\beta_{j}}(F_{i}))})=\infty,\
\ \ \text{for all}\ \ \ i\in I,$

and

$\sup\\{\frac{N_{\Phi}(C^{n}_{\varphi}\chi_{F_{i}})}{N_{\Phi}(\chi_{F_{i}})}i\in
I,\ \
n\in\mathbb{N}\\}=\sup\\{\frac{\Phi^{-1}(\frac{1}{\mu(F_{i})})}{\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F_{i}))})}\>i\in
I,\ \ n\in\mathbb{N}\\}=\infty,$

for some sequence $\\{\beta_{j}\\}_{j\in\mathbb{N}}\subseteq\mathbb{N}$.
Let

$\mathcal{L}=\overline{\text{linear span}\\{\chi_{F_{i}}:i\in I\\}}\subseteq
L^{\Phi}(\mu),$

$O_{C_{\varphi}}(f)=\\{f,C_{\varphi}f,C^{2}_{\varphi}f,C^{3}_{\varphi}f,....\\},$

$\mathcal{L}_{1}=\\{f\in\mathcal{L}:O_{C_{\varphi}}(f)\ \ \ \text{has a
subsequence converging to zero}\\},$

and

$\mathcal{L}_{2}=\\{f\in\mathcal{L}:O_{C_{\varphi}}(f)\ \ \ \text{is
unbounded}\\}.$

From (I) we get that $\mathcal{L}_{1}$ is dense in $\mathcal{L}$. Hence by the
Proposition 3 of [3] we get that $\mathcal{L}_{1}$ is residual in
$\mathcal{L}$. If we let

$f_{i}=\Phi^{-1}(\frac{1}{\mu(F_{i})})\chi_{F_{i}},\ \ \ \ \ i\in I,$

then for every $i\in I$, $f_{i}\in\mathcal{L}$ and

$N_{\Phi}(f_{i})=1\ \ \ \
N_{\Phi}(C^{n}_{\varphi}f_{i})=\frac{\Phi^{-1}(\frac{1}{\mu(F_{i})})}{\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F_{i}))})}.$

Thus by (II) we have

$\sup_{n\in\mathbb{N}}\sup_{f\in\mathcal{L}}N_{\Phi}(C^{n}_{\varphi}f)\geq\sup_{n\in\mathbb{N},i\in
I}N_{\Phi}(C^{n}_{\varphi}f_{i})=\sup_{n\in\mathbb{N},i\in
I}\frac{\Phi^{-1}(\frac{1}{\mu(F_{i})})}{\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F_{i}))})}=\infty.$

By applying Banach-Steinhaus Theorem we get $\mathcal{L}_{2}$ is residual in
$\mathcal{L}$. Consequently, by Theorem 2.1 we obtain that $C_{\varphi}$ is
Li-Yorke chaotic, because all elements of $\mathcal{L}_{1}\cap\mathcal{L}_{2}$
are irregular vectors for $C_{\varphi}$. ∎

Let $\varphi$ be injective and $F_{i}=\varphi^{i}(F)$, for $i\in\mathbb{Z}$.
For $m,n$ with $n<m$ we have

$F_{n}=\varphi^{n}(F)=\varphi^{n-m}(\varphi^{m}(F))=\varphi(F_{m}).$

If we set

$I=\\{n\in\mathbb{Z}:0<\mu(\varphi^{n}(F))<\infty\\},$

then we have

$\displaystyle\sup\\{\frac{\Phi^{-1}(\frac{1}{\mu(\varphi^{m}(F))})}{\Phi^{-1}(\frac{1}{\mu(\varphi^{n}(F))})}:n,m\in
I,\ \ n<m\\}$
$\displaystyle=\sup\\{\frac{\Phi^{-1}(\frac{1}{\mu(F_{m})})}{\Phi^{-1}(\frac{1}{\mu(\varphi^{n-m}(F_{m}))})}:n,m\in
I,\ \ n<m\\}$
$\displaystyle=\sup\\{\frac{\Phi^{-1}(\frac{1}{\mu(F_{m})})}{\Phi^{-1}(\frac{1}{\mu(\varphi^{n-m}(F_{m}))})}:n,m\in
I,\ \ n<m\\}.$

Therefore similar to the Corollary 1.2 of [4] we get that if $\varphi$ is
injective, then the composition operator $C_{\varphi}$ on the Orlicz space
$L^{\Phi}(\mu)$ is Li-Yorke chaotic if there exists a measurable set $F$ with
$0<\mu(F)<\infty$ such that

  * •

$\lim_{n\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{-n})})=\infty$,

  * •

$\sup\\{\frac{\Phi^{-1}(\frac{1}{\mu(F_{m})})}{\Phi^{-1}(\frac{1}{\mu(\varphi^{n-m}(F_{m}))})}:n,m\in
I,\ \ n<m\\}=\infty$.

Here we have a technical lemma for later use in this paper.

######  Lemma 2.3.

Let $\varphi:X\rightarrow X$ be an injective non-singular measurable
transformation and $\Phi$ be a Young’s function such that $\Phi\in\Delta_{2}$,
globally. Then the following conditions are equivalent:

  * •

There exists $K>0$ such that for all $F\in\mathcal{F}$,

$\mu(\varphi^{-1}(F))\leq K\mu(F).$

  * •

There exists $L>0$ such that for all $F\in\mathcal{F}$,

$\Phi^{-1}(\frac{1}{\mu(F)})\leq\Phi^{-1}(\frac{L}{\mu(\varphi^{-1}(F))})\leq
L\Phi^{-1}(\frac{1}{\mu(\varphi^{-1}(F))})$

###### Proof.

It is an easy exercise. ∎

In the following interesting result we give some necessary and sufficient
conditions for a Li-Yorke chaotic composition operator C on Orlicz spaces . We
prove that some of these assertions are equivalent under extra conditions.

######  Theorem 2.4.

Consider the following items:

  1. (1)

The composition operator $C_{\varphi}:L^{\Phi}(\mu)\rightarrow L^{\Phi}(\mu)$
is Li-Yorke chaotic;

  2. (2)

There exists a non-zero measurable function $f\in L^{\Phi}(\mu)$ such that

$\lim_{n\rightarrow\infty}\inf N_{\Phi}(C^{n}_{\varphi}f)=0;$

  3. (3)

There exists a measurable set $F\in\mathcal{F}$ with $0<\mu(F)<\infty$, such
that

$\lim_{n\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F))})=\infty;$

  4. (4)

There exists a measurable set $F$ with $0<\mu(F)<\infty$ such that

$\lim_{n\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{n}(F))})=\infty;$

  5. (5)

There exists a measurable set $F\in\mathcal{F}$ with $0<\mu(F)<\infty$, such
that

$\lim_{n\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F))})=\infty\
\ \ \text{and}\ \
\lim_{n\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{n}(F))})=\infty;$

  6. (6)

There exists a measurable set $F\in\mathcal{F}$ with $0<\mu(F)<\infty$, such
that

$\lim_{n\rightarrow\infty}\inf\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F))})>0\ \ \
\text{and}\ \
\lim_{n\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F))})=\infty;$

  7. (7)

There exists a measurable set $F\in\mathcal{F}$ such that $\chi_{F}$ is a
semi-irregular vector for the composition operator
$C_{\varphi}:L^{\Phi}(\mu)\rightarrow L^{\Phi}(\mu)$.

Then the following implications hold:

$(6)\Leftrightarrow(7)\Rightarrow(1)\Rightarrow(2)\Leftrightarrow(3)\Leftarrow(5)\Rightarrow(4).$

Moreover, if $\varphi$ is injective and $\Phi\in\Delta_{2}$, then we have the
implication $(5)\Rightarrow(6)$ and if $\Phi\in\Delta_{2}$ and
$\mu(X)<\infty$, then we have the implication $(4)\Rightarrow(5)$.
Consequently, if $\Phi\in\Delta_{2}$, $\mu(X)<\infty$ and $\varphi$ is
injective, then all conditions are equivalent.

###### Proof.

If $C_{\varphi}$ is Li-Yorke chaotic, then by Theorem 2.1 we have a semi-
irregular function $f\in L^{\Phi}(\mu)$ for $C_{\varphi}$. Hence

$\lim_{n\rightarrow\infty}\inf N_{\Phi}(C^{n}_{\varphi}f)=0$

and

(2.4) $\lim_{n\rightarrow\infty}\sup N_{\Phi}(C^{n}_{\varphi}f)=\infty.$

The equation 2.4 implies that $f$ is non-zero. So we proved that the
implication $(1)\Rightarrow(2)$ holds.
Let us prove the equivalence $(2)\Leftrightarrow(3)$. If $f$ satisfies the
condition $(2)$, then there exists a positive number $\delta$ such that

$\mu(F=\\{x\in X:|f(x)|>\delta\\})>0$

and also

$\int_{X}\Phi(\frac{\delta\chi_{\varphi^{-k}(F)}}{N_{\Phi}(C^{k}_{\varphi}f)})d\mu\leq\int_{X}\Phi(\frac{|f|^{k}\circ\varphi}{N_{\Phi}(C^{k}_{\varphi}f)})d\mu\leq
1.$

This means that

$\delta\frac{1}{\Phi^{-1}(\frac{1}{\mu(\varphi^{-k}(F))})}=\delta
N_{\Phi}(\chi_{F}\circ\varphi^{k})\leq N_{\Phi}(C^{k}_{\varphi}f).$

Therefore we get that

$\delta\lim_{k\rightarrow\infty}\inf\frac{1}{\Phi^{-1}(\frac{1}{\mu(\varphi^{-k}(F))})}\leq\lim_{k\rightarrow\infty}\inf
N_{\Phi}(C^{k}_{\varphi}f)=0$

and consequently we have

$\lim_{k\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{-k}(F))})=\infty.$

Hence the implication $(2)\Rightarrow(3)$ holds. For the converse, if there
exists a measurable set $F\in\mathcal{F}$ with $0<\mu(F)<\infty$ such that

$\lim_{k\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{-k}(F))})=\infty,$

then

$\displaystyle\lim_{k\rightarrow\infty}\inf
N_{\Phi}(\chi_{F}\circ\varphi^{k})$
$\displaystyle=\lim_{k\rightarrow\infty}\inf\frac{1}{\Phi^{-1}(\frac{1}{\mu(\varphi^{-k}(F))})}$
$\displaystyle=\frac{1}{\lim_{k\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{-k}(F))})}=0.$

So the implication $(3)\Rightarrow(2)$ holds.
Let us prove the equivalence $(6)\Leftrightarrow(7)$. Suppose that
$f=\chi_{F}$, in which $F\in\mathcal{F}$ with $0<\mu(F)<\infty$. Then we have

$N_{\Phi}(C^{k}_{\varphi}f)=N_{\Phi}(\chi_{\varphi^{-k}(F)})=\frac{1}{\Phi^{-1}(\frac{1}{\mu(\varphi^{-k}(F))})}.$

This equation shows that the properties $(6)$ and $(7)$ are equivalent. On the
other hand, the implications $(7)\Rightarrow(1)$, $(5)\Rightarrow(3)$ and
$(5)\Rightarrow(4)$ are clear.
Suppose that there exists a measurable set $F\in\mathcal{F}$ with
$0<\mu(F)<\infty$, such that

$\lim_{n\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F))})=\infty\
\ \ \text{and}\ \
\lim_{n\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{n}(F))})=\infty.$

Since $\Phi\in\Delta_{2}$ replace and is by just(continuous and increasing),
then we get that

$\lim_{n\rightarrow\infty}\sup\frac{1}{\mu(\varphi^{-n}(F))}=\infty\ \ \
\text{and}\ \
\lim_{n\rightarrow\infty}\sup\frac{1}{\mu(\varphi^{n}(F))}=\infty,$

and so we have

$\lim_{n\rightarrow\infty}\inf\mu(\varphi^{-n}(F))=0\ \ \ \text{and}\ \
\lim_{n\rightarrow\infty}\inf\mu(\varphi^{n}(F))=0.$

Hence by Lemma 2.3 and Theorem 1.3 of [4] there exists $F\in\mathcal{F}$ with
$0<\mu(F)<\infty$ such that

$\lim_{n\rightarrow\infty}\inf\mu(\varphi^{-n}(F))=0\ \ \ \ \text{and}\ \ \ \
\lim_{n\rightarrow\infty}\sup\mu(\varphi^{-n}(F))>0.$

Now by Lemma 2.3 we get the result i.e.,

$\lim_{n\rightarrow\infty}\inf\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F))})>0\ \ \
\text{and}\ \
\lim_{n\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F))})=\infty.$

Now let the condition (3) holds. Hence there exists a measurable set
$F\in\mathcal{F}$ with $0<\mu(F)<\infty$, such that

$\lim_{n\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{-n}(F))})=\infty.$

Since $\Phi\in\Delta_{2}$, then by Lemma 2.3 we have

$\lim_{n\rightarrow\infty}\sup\frac{1}{\mu(\varphi^{-n}(F))}=\infty$

which is equivalent to

$\lim_{n\rightarrow\infty}\inf\mu(\varphi^{-n}(F))=0.$

We assume that $\mu(X)<\infty$, $\Phi\in\Delta_{2}$ and $\varphi$ is injective
so by Theorem 1.3 of [4] we get that there exists $F\in\mathcal{F}$ with
$0<\mu(F)<\infty$ such that

$\lim_{n\rightarrow\infty}\inf\mu(\varphi^{n}(F))=0.$

Again by Lemma 2.3 we get that

$\lim_{n\rightarrow\infty}\sup\Phi^{-1}(\frac{1}{\mu(\varphi^{n}(F))})=\infty.$

so the condition (4) holds.
Let $\Phi\in\Delta_{2}$ and $\mu(X)<\infty$. y using the same process of
proving the implication $(3)\Rightarrow(4)$, Lemma 2.3 and Theorem 1.3 of [4]
we get the implication $(4)\Rightarrow(5)$. ∎

Declarations
Conflict of interest. The authors have not disclosed any competing interests.
Acknowledgement. My manuscript has no associate data.

## References

  * [1] T. Bermudez, A. Bonilla, F. Martinez-Gimnez and A. Peris, Li-Yorke and distributionally chaotic operators. J. Math. Anal. Appl. 373 (2011) 83-93.
  * [2] N. C. Bernardes Jr, A. Bonilla, V. Müller and A. Peris, Distributional chaos for linear operators. J. Funct. Anal. 265(2013), 2143–2163.
  * [3] N. C. Bernardes JR, A. Bonilla, V. Muller and A. Peris, Li-Yorke chaos in linear dynamics. Ergod. Th. and Dynam. Sys. (2014), doi:10.1017/etds.2014.20.
  * [4] N. C. Bernardes, U. B. Darji and B. Pires, Li–Yorke chaos for composition operators on Lp-spaces. Monatsh Math. 191 (2020), 13–35.
  * [5] F. Bayart,and E. Matheron, Dynamics of Linear Operators. Cambridge University Press, Cambridge (2009).
  * [6] N. C. Bernardes Jr, P. R. Cirilo, U.B. Darji, A. Messaoudi and E. R. Pujals, Expansivity and shadowing in linear dynamics. J. Math. Anal. Appl. 461 (2018), 796–816.
  * [7] N. C. Bernardes and A. Messaoudi, Shadowing and structural stability for operators. Ergod. Theory Dyn. Syst. 41 (2021) 961–980.
  * [8] J. Bes, Q. Menet, A. Peris, and Y. Puig, Recurrence properties of hypercyclic operators. Math. Ann.366(1), 545–572 (2016).
  * [9] S. Grivaux, E. Matheron, Q, Menet, Linear dynamical systems on Hilbert spaces: typical properties and explicity examples. Preprint, arXiv:1703.01854.
  * [10] Y. Cui, H. Hudzik, R. Kumar and L. Maligranda, Composition operators in Olicz spaces, J. Aust. Math. Soc.76 (2004), 189-206.
  * [11] M. A. Krasnosel’skii, Ya. B. Rutickii, Convex functions and Orlicz spaces, Noordhoff, Netherlands, 1961.
  * [12] T. Y. Li and J. A. Yorke, Period three implies chaos. Am. Math. Mon. 82 (1975), 985-992.
  * [13] Q. Menet, Linear chaos and frequent hypercyclicity. Trans. Am. Math. Soc. 369(2017), 4977–4994.
  * [14] M.M. Rao, Z.D. Ren, Theory of Orlicz spaces, Marcel Dekker, New York, 1991.


# Untargeted Backdoor Attack against Object Detection

###### Abstract

Recent studies revealed that deep neural networks (DNNs) are exposed to
backdoor threats when training with third-party resources (such as training
samples or backbones). The backdoored model has promising performance in
predicting benign samples, whereas its predictions can be maliciously
manipulated by adversaries based on activating its backdoors with pre-defined
trigger patterns. Currently, most of the existing backdoor attacks were
conducted on the image classification under the targeted manner. In this
paper, we reveal that these threats could also happen in object detection,
posing threatening risks to many mission-critical applications ($e.g.$,
pedestrian detection and intelligent surveillance systems). Specifically, we
design a simple yet effective poison-only backdoor attack in an untargeted
manner, based on task characteristics. We show that, once the backdoor is
embedded into the target model by our attack, it can trick the model to lose
detection of any object stamped with our trigger patterns. We conduct
extensive experiments on the benchmark dataset, showing its effectiveness in
both digital and physical-world settings and its resistance to potential
defenses.

Index Terms—  Backdoor Attack, Object Detection, Physical Attack, Trustworthy
ML, AI Security

##  1 Introduction

Object detection aims to localize a set of objects and recognize their
categories in the image [1]. It has been widely adopted in mission-critical
applications ($e.g.$, pedestrian detection [2, 3, 4] and autonomous driving
[5, 6, 7]). Accordingly, it is necessary to ensure its security.

Currently, the most advanced object detectors were designed based on deep
neural networks (DNNs) [8, 9, 10], whose training generally requires many
resources. To alleviate the training burdens, researchers and developers
usually exploit third-party resources ($e.g.$, training samples or backbones)
or even directly deploy the third-party model. One important question arises:
_Does the training opacity bring new threats into object detection?_

In this paper, we reveal the vulnerability of object detection to _backdoor
attacks_ caused by using third-party training samples or outsourced training
[11, 12, 13]. In general, backdoor attacks are a type of training-time threat
to DNNs. The adversaries intend to embed a hidden backdoor into the target
model, based on which to maliciously manipulate its predictions by activating
the backdoor with the adversary-specified trigger patterns. So far, existing
methods [14, 15, 16] are mostly designed for classification tasks and are
targeted attacks, associated with a specific target label. Different from
attacking a classifier, making an object escape detection is a more
threatening objective. Accordingly, we study how to design the _untargeted_
backdoor attack to object detection so that the attacked DNNs behave normally
on benign samples yet fails to detect objects containing trigger patterns.

In particular, we focus on the _poison-only_ attack setting, where backdoor
adversaries can only modify a few training samples while having neither the
information nor the ability to control other training components ($e.g.$,
training loss or model structure). It is the hardest attack setting having the
most threat scenarios [17, 18, 19]. We propose a simple yet effective attack
by removing the bounding boxes of a few randomly selected objects after adding
pre-defined trigger patterns. Our attack is stealthy to bypass human
inspection since it is common to miss marking some bounding boxes (especially
when the image contains many objects).

In conclusion, our main contributions are three-folds. 1) We reveal the
backdoor threat in object detection. To the best of our knowledge, this is the
first backdoor attack against this mission-critical task. 2) We design a
simple yet effective and stealthy untargeted attack, based on the properties
of object detection. 3) Extensive experiments on the benchmark dataset are
conducted, which verify the effectiveness of our attack and its resistance to
potential backdoor defenses.

##  2 The Proposed Method

Fig. 1: The main pipeline of our poison-only untargeted backdoor attack
against object detection. Our method consists of three main stages. In the
first stage, we generate some poisoned training samples by adding trigger
patterns to randomly selected benign samples and reassigning the width and
height of their bounding boxes to 0. In the second stage, we train the victim
detector via generated poisoned samples and remaining benign samples. In the
last stage, the adversary can activate embedded backdoors to circumvent the
detection of target objects ($e.g.$, a specific ‘bear’ in our example) by
adding trigger patterns.

###  2.1 Threat Model

In this paper, we focus on the poison-only backdoor attack in object
detection. Specifically, we assume that the adversaries can only adjust some
legitimate samples to generate the poisoned training dataset, whereas having
neither the information nor the ability to control other training components
($e.g.$, training loss, training schedule, and model structure). The generated
poisoned dataset will be released to train victim models. This attack can
occur in various scenarios where the training process is not fully controlled,
including but not limited to using third-party data, third-party computing
platforms, third-party models, etc.

In general, the backdoor adversaries have two main targets, including 1)
effectiveness and 2) stealthiness. Specifically, the former purpose is to make
attacked detectors fail to detect objects whenever adversary-specified trigger
patterns appear. The latter requires that the backdoored model should have a
similar performance in detecting benign objects, compared to the one trained
on the benign training dataset.

###  2.2 Backdoor Attack against Object Detection

The mechanism of the poison-only backdoor attack is to establish a latent
connection ($i.e.$, backdoor) between the adversary-specified trigger pattern
and the specific (malicious) prediction behavior by poisoning some training
data. In this part, we illustrate our attack in detail.

The Formulation of Object Detection.  Let
$\mathcal{D}=\\{(\bm{x}_{i},\bm{a}_{i})\\}_{i=1}^{N}$ represent the benign
dataset, where $\bm{x}_{i}\in\mathcal{X}$ is the image of an object,
$\bm{a}_{i}\in\mathcal{A}$ is the ground-truth annotation of the object
$\bm{x}_{i}$. For each annotation $\bm{a}_{i}$, we have
$\bm{a}_{i}=[\hat{x}_{i},\hat{y}_{i},w_{i},h_{i},c_{i}]$, where
$(\hat{x}_{i},\hat{y}_{i})$ is the center coordinates of the object, $w_{i}$
is the width of the bounding box, $h_{i}$ is the height of the bounding box,
and $c_{i}$ is the class of the object $\bm{x}_{i}$. Given the dataset
$\mathcal{D}$, users can adopt it to train their object detector
$f_{\bm{w}}:\mathcal{X}\rightarrow\mathcal{A}$ by
$\min_{\bm{w}}\sum_{(\bm{x},\bm{a})\in\mathcal{D}}\mathcal{L}(f(\bm{x}),\bm{a})$,
where $\mathcal{L}$ is the loss function.

The Main Pipeline of Our Untargeted Backdoor Attacks.  Similar to the poison-
only backdoor attacks in image classification, how to generate the poisoned
training dataset is also the cornerstone of our method. Specifically, we
divide the original benign dataset $\mathcal{D}$ into two disjoint subsets,
including a selected subset $\mathcal{D}_{s}$ for poisoning and the remaining
benign samples $\mathcal{D}_{b}$. After that, we generate the modified version
of $\mathcal{D}_{s}$ ($i.e.$, $\mathcal{D}_{m}$) as follows:

$\mathcal{D}_{m}=\left\\{\left(G_{x}(\bm{x}),G_{a}(\bm{a})\right)|(\bm{x},\bm{a})\in\mathcal{D}_{s}\right\\},$
(1)

where $G_{x}$ and $G_{a}$ are the poisoned image generator and poisoned
annotation generator, respectively. We combine the modified subset
$\mathcal{D}_{m}$ and the benign subset $\mathcal{D}_{b}$ to generate the
poisoned dataset $D_{p}$, which will be released to train (backdoored) victim
model. In the inference process, given an ‘unseen’ object image
$\bm{x}^{\prime}$, the adversaries can exploit $G_{x}(\bm{x}^{\prime})$ to
circumvent detection by adding trigger patterns. The main pipeline of our
attack is demonstrated in Figure 1.

In particular, we assign
$G_{a}\left([\hat{x},\hat{y},w,h,c]\right)=[\hat{x},\hat{y},0,0,c]$ in our
untargeted attack. Following the most classical setting in existing literature
[12], we adopt
$G_{x}(\bm{x})=\bm{\lambda}\otimes\bm{t}+(\bm{1}-\bm{\lambda})\otimes\bm{x}$
where $\bm{t}\in\mathcal{X}$ is the adversary-specified trigger pattern,
$\bm{\lambda}\in[0,1]^{C\times W\times H}$ is the trigger transparency, and
$\otimes$ denotes the element-wise multiplication. Besides,
$p\triangleq\frac{|\mathcal{D}_{s}|}{|\mathcal{D}|}$ is denoted as the
poisoning rate, which is another important hyper-parameter involved in our
method.

Fig. 2: The detection results of the Sparse R-CNN model under our attack in
the digital space. In these examples, the trigger patterns are added by pixel-
wise replacement of objects ($i.e.$, ‘person’ and ‘stop sign’) in the digital
space.

Fig. 3: The detection results of the Sparse R-CNN model under our attack in
the physical space. In these examples, we print the trigger patch and stamp it
on the target objects ($i.e.$, ‘scissors’ and ‘cell phone’).  Table 1: The
performance (%) of methods on the COCO dataset.

Dataset$\rightarrow$ | Benign Testing dataset | Poisoned Testing dataset
---|---|---
Model$\downarrow$ | Method$\downarrow$, Metric$\rightarrow$ | mAP | $\text{AP}_{\text{50}}$ | $\text{AP}_{\text{75}}$ | $\text{AP}_{\text{s}}$ | $\text{AP}_{\text{m}}$ | $\text{AP}_{\text{l}}$ | mAP | $\text{AP}_{\text{50}}$ | $\text{AP}_{\text{75}}$ | $\text{AP}_{\text{s}}$ | $\text{AP}_{\text{m}}$ | $\text{AP}_{\text{l}}$
Faster R-CNN | Vanilla | 37.4 | 58.1 | 40.4 | 21.2 | 41.0 | 48.1 | 35.2 | 55.3 | 37.8 | 19.7 | 37.7 | 46.5
Ours | 36.9 | 57.5 | 40.0 | 21.3 | 40.4 | 47.4 | 10.6 | 20.1 | 9.8 | 7.7 | 7.7 | 15.2
Sparse R-CNN | Vanilla | 40.0 | 58.2 | 42.9 | 21.9 | 42.4 | 56.3 | 35.7 | 53.1 | 38.0 | 18.7 | 36.6 | 51.4
Ours | 39.0 | 56.9 | 41.9 | 20.7 | 41.2 | 55.2 | 7.7 | 14.1 | 7.3 | 8.1 | 5.7 | 9.7
TOOD | Vanilla | 41.7 | 58.7 | 45.1 | 24.2 | 44.9 | 55.5 | 39.2 | 55.4 | 42.3 | 22.0 | 40.9 | 53.1
Ours | 41.1 | 57.8 | 44.5 | 23.8 | 44.5 | 54.3 | 13.5 | 22.0 | 13.5 | 9.3 | 9.4 | 19.8

##  3 Experiments

###  3.1 Experimental Settings

Model Structure and Dataset Description.  We adopt three representative object
detectors, including Faster R-CNN [8], Sparse R-CNN [9], and TOOD [10], for
the evaluations. Besides, following the classical setting in object detection,
we use COCO dataset [20] as the benchmark for our discussions.

Evaluation Metric. We adopt six classical average-precision-based metrics
[20], including 1) mAP, 2) AP50, 3) AP75, 4) AP${}_{\text{s}}$, 5)
AP${}_{\text{m}}$, and 6) AP${}_{\text{l}}$, for our evaluations. We calculate
these metrics on the benign testing dataset and its poisoned variant (with a
100% poisoning rate), respectively.

Attack Setup.  For simplicity, we adopt a white patch as the trigger pattern
and set the poisoning rate as $5\%$. Following the settings in [21], we set
the trigger size of each object as 1% of its ground-truth bounding box
($i.e.$, 10% width and 10% height), located in its center. Besides, we also
provide the results of models trained on benign samples (dubbed ‘Vanilla’) for
reference. The example of samples involved in different methods are shown in
Figure 2.

###  3.2 Main Results in the Digital Space

As shown in Table 1, our method can significantly decrease the average
precision in all cases, no matter what the model structure is. For example,
the AP50 decreases more than 30% in all cases, compared to that of vanilla
models trained on benign samples. In particular, these performance decreases
are not simply due to the masking effect of trigger patches. The average
precision of vanilla models on the poisoned testing dataset does not decrease
significantly, compared to that on the benign dataset. Moreover, the average
precision of models under our attack on the benign dataset is similar to that
of vanilla models. These results verify our effectiveness.

###  3.3 Main Results in the Physical Space

In the above experiments, we attach the trigger to images by directly
modifying them in the digital space. To further verify that our attack could
happen in real-world scenarios, here we conduct experiments on the physical
space. Specifically, we print the trigger patch and stamp it on some target
objects. We capture (poisoned) images by the camera in iPhone, based on which
to track objects via attacked Sparse R-CNN.

As shown in Figure 3, the model under our attack can successfully detect
benign objects while failing to detect object stamped with the trigger
pattern. These results indicate the effectiveness of our attack again.

(a)

(b)

(c)

(d)

Fig. 4: Four trigger patterns used in our evaluation. Fig. 5: The effects of
poisoning rates.

###  3.4 Ablation Study

In this section, we adopt Faster R-CNN [8] as an example for the discussion.
Except for the studied parameter, other settings are the same as those
illustrated in Section 3.1.

The Effects of Trigger Patterns. In this part, we evaluate our method with
four different trigger patterns (as shown in Figure 4). As shown in Table 2,
the performances of models trained on poisoned datasets using different
trigger patterns are about the same. It indicates that adversaries can use
arbitrary trigger patterns to generate poisoned samples.

Table 2: The effects of trigger patterns.

Pattern$\downarrow$ | Attack$\downarrow$, Metric$\rightarrow$ | $\text{mAP}_{\text{benign}}$ | $\text{mAP}_{\text{poisoned}}$
---|---|---|---
(a) | Vanilla | 37.4 | 35.2
Ours | 36.9 | 10.6
(b) | Vanilla | 37.4 | 34.7
Ours | 36.9 | 10.4
(c) | Vanilla | 37.4 | 34.9
Ours | 36.9 | 9.1
(d) | Vanilla | 37.4 | 34.9
Ours | 36.8 | 8.8

The Effects of Poisoning Rates. In this part, we discuss the effects of the
poisoning rate on our attack. As shown in Figure 5, the mAP on the poisoned
dataset decreases with the increase in the poisoning rate. In other words,
introducing more poisoned samples can improve attack effectiveness. However,
its increase also leads to the decrease of mAP on the benign dataset, $i.e.$,
there is a trade-off between effectiveness and stealthiness. In practice, the
adversary should specify this parameter based on their needs.

###  3.5 The Resistance to Potential Backdoor Defenses

Fine-tuning [22] and model pruning [23, 24] are two classical and
representative backdoor defenses that can be directly generalized to different
tasks. In this section, we evaluate whether our attack is resistant to these
potential defenses. We implement these defenses based on codes in BackdoorBox
[25].

The Resistance to Fine-tuning.  We fine-tune the attacked Faster R-CNN with
10% benign testing samples and set the learning rate as the one used for
training. As shown in Figure 6, our method is resistant to fine-tuning.
Specifically, the mAP on the poisoned dataset ($i.e.$, Poisoned mAP) is still
lower than 15% when the tuning process is finished.

Fig. 6: The resistance to fine-tuning.

The Resistance to Model Pruning.  Following the classical settings, we prune
neurons having the lowest activation values with 10% benign testing samples.
As shown in Figure 7, the poisoned mAP even decreases (instead of increasing)
with the increase in the pruning rate. These results demonstrate that our
method is resistant to model pruning.

Fig. 7: The resistance to model pruning.

##  4 Conclusions

In this paper, we revealed the backdoor threats in object detection by
introducing a simple yet effective poison-only untargeted attack.
Specifically, we removed the bounding boxes of a few randomly selected objects
after adding pre-defined trigger patterns to the center of object areas. We
demonstrated that our attack is effective and stealthy under both digital and
physical settings. We also showed that our method is resistant to potential
backdoor defenses. Our method can serve as a useful tool to examine the
backdoor robustness of object detectors, leading to the design of more secure
models.

## References

  * [1] Zhong-Qiu Zhao, Peng Zheng, Shou-tao Xu, and Xindong Wu,  “Object detection with deep learning: A review,”  IEEE transactions on neural networks and learning systems, vol. 30, no. 11, pp. 3212–3232, 2019.
  * [2] Wei Liu, Shengcai Liao, Weiqiang Ren, Weidong Hu, and Yinan Yu,  “High-level semantic feature detection: A new perspective for pedestrian detection,”  in CVPR, 2019.
  * [3] Zixuan Xu, Banghuai Li, Ye Yuan, and Anhong Dang,  “Beta r-cnn: Looking into pedestrian detection from another perspective,”  in NeurIPS, 2020.
  * [4] Irtiza Hasan, Shengcai Liao, Jinpeng Li, Saad Ullah Akram, and Ling Shao,  “Generalizable pedestrian detection: The elephant in the room,”  in CVPR, 2021.
  * [5] Peixuan Li, Huaici Zhao, Pengfei Liu, and Feidao Cao,  “Rtm3d: Real-time monocular 3d detection from object keypoints for autonomous driving,”  in ECCV, 2020.
  * [6] Xinzhu Ma, Yinmin Zhang, Dan Xu, Dongzhan Zhou, Shuai Yi, Haojie Li, and Wanli Ouyang,  “Delving into localization errors for monocular 3d object detection,”  in CVPR, 2021.
  * [7] Hamed H. Aghdam, Elnaz J. Heravi, Selameab S. Demilew, and Robert Laganiere,  “Rad: Realtime and accurate 3d object detection on embedded systems,”  in CVPR Workshops, 2021.
  * [8] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun,  “Faster r-cnn: Towards real-time object detection with region proposal networks,”  in NeurIPS, 2015.
  * [9] Peize Sun, Rufeng Zhang, Yi Jiang, Tao Kong, Chenfeng Xu, Wei Zhan, Masayoshi Tomizuka, Lei Li, Zehuan Yuan, Changhu Wang, and Ping Luo,  “Sparse r-cnn: End-to-end object detection with learnable proposals,”  in CVPR, 2021.
  * [10] Chengjian Feng, Yujie Zhong, Yu Gao, Matthew R. Scott, and Weilin Huang,  “Tood: Task-aligned one-stage object detection,”  in ICCV, 2021.
  * [11] Micah Goldblum, Dimitris Tsipras, Chulin Xie, Xinyun Chen, Avi Schwarzschild, Dawn Song, Aleksander Madry, Bo Li, and Tom Goldstein,  “Dataset security for machine learning: Data poisoning, backdoor attacks, and defenses,”  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022\.
  * [12] Yiming Li, Yong Jiang, Zhifeng Li, and Shu-Tao Xia,  “Backdoor learning: A survey,”  IEEE Transactions on Neural Networks and Learning Systems, 2022\.
  * [13] Zhiyi Tian, Lei Cui, Jie Liang, and Shui Yu,  “A comprehensive survey on poisoning attacks and countermeasures in machine learning,”  ACM Computing Surveys, 2022.
  * [14] Tianyu Gu, Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg,  “Badnets: Evaluating backdooring attacks on deep neural networks,”  IEEE Access, 2019.
  * [15] Yuezun Li, Yiming Li, Baoyuan Wu, Longkang Li, Ran He, and Siwei Lyu,  “Invisible backdoor attack with sample-specific triggers,”  in ICCV, 2021.
  * [16] Yi Zeng, Won Park, Z Morley Mao, and Ruoxi Jia,  “Rethinking the backdoor attacks’ triggers: A frequency perspective,”  in ICCV, 2021.
  * [17] Yiming Li, Yanjie Li, Yalei Lv, Yong Jiang, and Shu-Tao Xia,  “Hidden backdoor attack against semantic segmentation models,”  in ICLR Workshop, 2021.
  * [18] Jie Zhang, Chen Dongdong, Qidong Huang, Jing Liao, Weiming Zhang, Huamin Feng, Gang Hua, and Nenghai Yu,  “Poison ink: Robust and invisible backdoor attack,”  IEEE Transactions on Image Processing, vol. 31, pp. 5691–5705, 2022\.
  * [19] Yiming Li, Yang Bai, Yong Jiang, Yong Yang, Shu-Tao Xia, and Bo Li,  “Untargeted backdoor watermark: Towards harmless and stealthy dataset copyright protection,”  in NeurIPS, 2022.
  * [20] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick,  “Microsoft coco: Common objects in context,”  in ECCV, 2014.
  * [21] Yiming Li, Haoxiang Zhong, Xingjun Ma, Yong Jiang, and Shu-Tao Xia,  “Few-shot backdoor attacks on visual object tracking,”  in ICLR, 2022.
  * [22] Yuntao Liu, Yang Xie, and Ankur Srivastava,  “Neural trojans,”  in ICCD, 2017.
  * [23] Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg,  “Fine-pruning: Defending against backdooring attacks on deep neural networks,”  in RAID, 2018.
  * [24] Dongxian Wu and Yisen Wang,  “Adversarial neuron pruning purifies backdoored deep models,”  in NeurIPS, 2021.
  * [25] Yiming Li, Mengxi Ya, Yang Bai, Yong Jiang, and Shu-Tao Xia,  “BackdoorBox: A python toolbox for backdoor learning,”  2022\.