# Optimizing Active Learning for Low Annotation Budgets

Umang Aggarwal1,2, Adrian Popescu1, Céline Hudelot2
(1) Université Paris-Saclay, CEA, Département Intelligence Ambiante et
Systèmes Interactifs
(2) Université Paris-Saclay, CentraleSupélec, Mathématiques et Informatique
pour la Complexité et les Systèmes
91191 Gif-sur-Yvette, France
umang.aggarwal,adrian.popescu<EMAIL_ADDRESS>
###### Abstract

When we can not assume a large amount of annotated data , active learning is a
good strategy. It consists in learning a model on a small amount of annotated
data (annotation budget) and in choosing the best set of points to annotate in
order to improve the previous model and gain in generalization. In deep
learning, active learning is usually implemented as an iterative process in
which successive deep models are updated via fine tuning, but it still poses
some issues. First, the initial batch of annotated images has to be
sufficiently large to train a deep model. Such an assumption is strong,
especially when the total annotation budget is reduced. We tackle this issue
by using an approach inspired by transfer learning. A pre-trained model is
used as a feature extractor and only shallow classifiers are learned during
the active iterations. The second issue is the effectiveness of probability or
feature estimates of early models for AL task. Samples are generally selected
for annotation using acquisition functions based only on the last learned
model. We introduce a novel acquisition function which exploits the iterative
nature of AL process to select samples in a more robust fashion. Samples for
which there is a maximum shift towards uncertainty between the last two
learned models predictions are favored. A diversification step is added to
select samples from different regions of the classification space and thus
introduces a representativeness component in our approach. Evaluation is done
against competitive methods with three balanced and imbalanced datasets and
outperforms them.

_K_ eywords Active Learning $\cdot$ Limited annotation budget

##  1 Introduction

Deep neural networks learn complex feature representations by exploiting large
datasets to optimize a large number of parameters. Deep supervised learning
strategies have given impressive results in multiple domains, but their
effectiveness is governed by the size of the annotated dataset. Large
annotated datasets are not readily available in many applications. Active
Learning (AL) [1] reduces the cost of creating a labeled dataset by selecting,
through an acquisition function (AF) the most relevant samples to train the
model. The effectiveness of the active learning process depends on the
strategy deployed for sample selection.

A large number of sample acquisition functions have been proposed to improve
the AL process. One mainstream strategy is to maximize the informativeness by
selecting the samples on which the model gives most uncertain probability
estimates [2, 3, 4, 5]. Alternatively, sample acquisition can be designed to
select diverse samples which maximize the likelihood between distribution of
labeled and unlabeled samples [6, 7, 8]. Informativeness and diversity are not
easy to optimize jointly but, since they convey complementary cues, their
combination is tackled in works such as [9, 10] .

Active learning is generally implemented in an iterative fashion, with a new
batch of samples being annotated in each iteration [2, 11, 1]. Models are
retrained at the end of each iteration in order to incorporate the newly
annotated samples which improve the models’ predictive power. One open problem
in AL is that a relatively large amount of samples needs to be annotated
before a viable initial deep model can be learned efficiently [12, 13, 1, 14].
The size of the initial labeled dataset should be such that a model trained on
the dataset provides reliable uncertainty measures and feature representations
for the AL acquisition functions to outperform random sampling. This issue is
further exacerbated for deep learning models that are quite data intensive.
The size of the initial labeled dataset depends on the deep architecture used,
the complexity of the problem and the acquisition function. In our work, we
explore training of a Support Vector Machine (SVM) classifier over fixed
representation as an alternate to the dominant fine tuning scheme used in
recent works [2, 11, 12]. This type of approach, which instantiates transfer
learning, has been shown to be effective for active learning over imbalanced
datasets [15].

Figure 1: Illustration of $alamp$, the proposed method, for a two class
problem. Blue and yellow regions are the class boundaries learnt by
classifier. One sample is selected at each iteration. Uncertainty sampling
selects the sample (red) which is closest to the class boundary. At Iteration
1, $alamp$ selects the same sample as sampling, since it has is no access to
previous model. At Iteration 2, $alamp$ selects the sample which gives most
certain prediction (i.e. is furthest away from decision boundary) at Iteration
1 and gives the most uncertain prediction (i.e. is closest to decision
boundary) at Iteration 2. Similarly at Iteration 3, $alamp$ selects the sample
with maximum shift from certainty to uncertainty

Our main contribution is a new measure of informativeness which integrates
predicted probabilities in successive AL iterations. Samples whose prediction
states move from certain to uncertain between two iterations are prioritised.
The underlying intuition here is that such samples encode information which is
missing from the models and should be integrated into them. The measure is
illustrated for a two-class problem in Figure 1. This view of informativeness
is broader than the one incorporated in current uncertainty-based sampling
which only considers the decision boundaries of the current iteration.

However, the proposed sample AF shares a limitation with existing
informativeness-based functions in that it could suffer from a lack of
representativeness [1]. The second contribution is to add a representativeness
dimension in the proposed acquisition function. Representativeness is modeled
via the introduction of a diversification procedure. The proposed
informativeness measure prioritizes samples with high certainty at the
previous iteration. The diversification procedure exploits this fact to select
samples with different class predictions in the previous iteration. This leads
to selection of samples from different uncertain regions distributed across
the classification space provided by the model classifier.

The two contributions are well-suited for use with a shallow classifier
trained over fixed representations. The constant nature of representation
helps the proposed measure to effectively evaluate the distance of the samples
to the classifier boundary in the preceding and the current iterations. We
show that training a shallow classifier over fixed representations gives
higher performance than fine-tuning CNN models, especially for smaller
budgets. This is important insofar fixed representations can be exploited from
the very beginning for the AL task where the classical fine tuning estimates
are shown to be unstable [12]. The experiments are performed with three
balanced datasets: Cifar100, Food-101 and a subset of ImageNet classes which
are not part of ILSVRC. We also test our method for imbalanced datasets by
creating imbalanced version of Cifar100 and Food-101 and using MIT-Indoor67
which is naturally imbalanced. ILSVRC itself is used to create the fixed
representation. The proposed method is compared to a series of strong
baselines. The results indicate that it outperforms the baselines in most of
the evaluated configurations.

##  2 Related works

Active learning was studied thoroughly in the pre-deep learning period [1] and
also recently in deep learning [9, 2, 11, 8]. Several heuristics have been
designed to select the most important samples that help in improving the
model. They fall in two main categories. One set of methods focuses on
informative samples that would provide new information to the model.
Uncertainty-based acquisition functions select samples for which the model
gives the least sure predictions. Some of the most representative AFs proposed
in literature include: entropy [5], least confidence [3] and margin sampling
[4]. Margin Sampling prioritizes samples for which the model is least certain
between the top 2 class predictions. It is shown to be effective in AL task as
it relates well to selecting samples based on distance from the decision
boundary for shallow clasifier such as SVMs [16, 17]. It has also been used in
imbalanced learning context with SVM classifier to select samples which are
closest to the decision boundary of the classifier [18, 19, 20]. Hence, given
the use of SVM training scheme in our work we study margin sampling as the
main uncertainty measure. The main limitation of informativeness-based
approaches is that they might fail to capture the overall sample distribution
because they provide no guarantee of a thorough exploration of the
representation space. As a result, they are susceptible to provide a biased
selection.

Another set of techniques are AFs on the objective of representativeness.
These approaches select a diverse set of samples for annotation which are most
likely to represent the unknown distribution. Several approaches based on
clustering methods such as K-means or hierarchical clustering have been
introduced in active learning [6]. These methods select a diverse set of
sample by sampling from different clusters. Coreset [8] is a recent method
that solves the K-center problem by selecting the samples with maximum
distance to its closest labeled neighbour.

The joint use of informativeness and representativeness can be challenging due
to different nature of the two selection strategies. However, they convey
complementary information and set of approaches tackled their combination in
order to select samples which are both representative and uncertain [21, 22,
23]. In [22], a strategy is proposed to select using either uncertainty
sampling or representative sampling by a sequential decision process. Badge
[9] is a recent work which exploits the gradient of the embedding of the last
layer of the model. A K-means++ clustering is implemented on the gradient
embedding to select diverse samples. It is argued that kmeans++ selects
samples with a large gradient value and thus the samples are also informative.
We also try to combine the two objectives by selecting uncertain samples from
diverse regions of multi-class classifier but using a different strategy.

A direction of research tries to improve the quality of the uncertainty
estimates. Bayesian probabilities were introduced as better estimate of
uncertainty by combining probabilities of several runs of model [11]. The
dropout parameter is used during inference to ensure variation in model
probabilities. Ensemble models have also been used to acquire multiple
probability estimates. In [2], an ensemble of model snapshots is created by
using a cyclic learning rate. This design choice is important in order to
limit the computational effort need to create the ensemble. In our work, we
derive multiple probabilities by exploiting the iterative nature of AL cycle
without additional computational cost.

Several works add the semi-supervised learning objective to active learning by
using the unlabelled data to train the model. An approach to find the optimal
acquisition function using feature density matching between unlabelled dataset
and weakly supervised validation data is presented in [24]. Inspired by
MixMatch [25], consistency based semi-supervised learning [12] has been used
for AL task by selecting samples which give inconsistent predictions for
different permutations. Our work has similar approach of prioritising samples
with inconsistent predictions, but at different iterative steps. Semi-
supervised learning is difficult to generalize, particularly for very low
budgets which is in focus here. More importantly, most of the methods in this
category use an additional labeled validation set to optimize the parameters.
It is not realistic to assume that such a set exists at the beginning of the
AL process. Moreover, these works come with an added complexity in terms of
computational resources. Hence they are not directly comparable with shallow
classifier used here.

An approach which exploits the model learned at previous acquisition step via
knowledge distillation is presented in [26]. They use the previous model to
fine tune the weight decay parameter and provide effective regularization. The
contribution is complementary to ours. The key difference is that we use the
probability distribution from the previous iteration to propose a measure of
informativeness.

An initial annotated dataset is necessary to kick-start the iterative AL
cycle. The most common approach is to annotate a small randomly selected
subset [2, 11, 8]. The size of the initial set is critical in AL.This is
particularly the case for large deep neural networks which might not provide
reliable and stable probability estimate at the start of AL cycle. An approach
to mitigate this problem for DNN was presented in [27]. They showed that a
smaller proxy network can be used for sample selection as at smaller budget, a
smaller model provides better estimates compared to a larger model. The large
model is trained when sufficient samples are selected. A transfer learning
perspective was introduced in AL to select the initial batch of samples [15].
The probability estimates for the unlabelled dataset is derived from a pre-
trained model to select a diverse and balanced set of samples. Similar to
[15], we test the use of shallow classifier on top of pre-trained features as
compared to the classical fine-tuning approach.

##  3 Problem Description and Baselines

We consider an unlabelled dataset $\mathbb{D}^{U}$ with samples
$x_{i}\in\mathcal{X}$ for $i=[1..u]$, i.i.d realizations of random variables
$\mathcal{X}$ drawn from the distribution $\mathbb{P}$ where $\mathcal{X}$ is
the instance space. In an iterative AL setting, a total budget $b$, with
$b<u$, is allocated for manual labeling in $t$ iterations. The process starts
by randomly selecting a small subset of $\mathbb{D}^{U}$ for annotation to
create the initial labeled dataset $\mathbb{D}_{0}^{L}$ with
$x_{j},y_{j}\in\mathcal{X}\times\mathcal{Y}$ for $j=[1..\frac{b}{t}]$.

Here $\mathcal{Y}=\\{y_{1},...,y_{n}\\}$ is the set of $n$ class labels.
$\mathbb{D}_{0}^{L}$ is used to train an initial model $\mathcal{M}_{0}$ which
provides the probability estimates $\mathcal{P}_{0}$ or the feature embeddings
$\mathcal{F}_{0}$ required by an acquisition function AF to estimate the
importance of samples for the next iteration. Afterwards, at iteration step
$k$, for $k=[1..t-1]$, a batch of samples of size $\frac{b}{t}$ is selected
for labeling from
$\mathbb{D}_{k}^{U}=\mathbb{D}^{U}\setminus\mathbb{D}_{k-1}^{L}$, and added to
$\mathbb{D}_{k-1}^{L}$ to update the labeled subset $\mathbb{D}_{k}^{L}$.
$\mathbb{D}_{k}^{L}$, the labeled set at iteration $k$, is then used to learn
the model $\mathcal{M}_{k}$.

We test two training methods which are based either on deep model update or on
a pretrained model followed by a shallow learning of classifiers. Both schemes
exploit a pretrained model $\mathcal{M}_{S}$ learned over a generic dataset.
The first method exploits fine tuning, which is the usual way in which deep
models are updated in iterative AL [2, 11, 8]. Deep models are fine tuned for
each AL iteration using $\mathcal{M}_{S}$ and $\mathbb{D}_{k}^{L}$. The second
method assumes that, although $\mathcal{M}_{S}$ is trained on a separate
dataset, the knowledge it encapsulates can be transferred to $\mathbb{D}^{U}$.
Feature embeddings $\mathcal{F}_{S}$ from $\mathcal{M}_{S}$ are used to train
shallow classifiers during AL iterations.

###  3.1 Baselines

We compare our method to four competitive baselines. The first three are
classical methods representative for random, informativeness-based, and
diversity-based selection respectively. The fourth is $badge$, a recently
introduced method which combines the informativeness and representativeness
objectives [9]. This baseline is suited only in the fine tuning training
scheme.

####  3.1.1 Random sampling

The first baseline $rand$ consists in a random selection of samples for
annotation. The initial subset to start the AL iterative cycle is selected
using random sampling. While very simple, random sampling is a strong baseline
in active learning [2, 8, 1].

####  3.1.2 Margin sampling

Uncertainty based methods aim to maximize informativeness and thus focus on
samples that the model classifies with the most difficulty. They are deployed
using the outputs of the classification layer [1]. Margin based AL is shown to
be an effective uncertainty measure for SVM classifier [16, 19, 18]. It is
defined as:

$marg(x)=(P(y=c^{1}|x)-P(y=c^{2}|x))$ (1)

where $c^{1},c^{2}$ are the top-2 predicted classes for test sample $x$ at
iteration $k$.

We consider $\textrm{Marg}_{\textrm{sort}}(\mathbb{D}_{k}^{U})$ a permutation
of the set $\mathbb{D}_{k}^{U}$ by ordering its element by increasing value of
$marg$ . $\mathbb{D}_{k+1}^{L}$ is obtained by the union of
$\mathbb{D}_{k}^{L}$ with the first $\frac{b}{t}$ samples of
$\textrm{Marg}_{\textrm{sort}}(\mathbb{D}_{k}^{U})$. The baseline obtained is
noted $marg$.

####  3.1.3 Coreset

Diversity based methods select a subset of $\mathbb{D}^{U}$ so as to ensure an
optimal coverage of the representation space. Coreset [8] takes a minmax view
to select the diverse samples. It is defined as:

$core(\mathbb{D}_{k}^{U},\mathbb{D}_{k}^{L})=\max_{\forall
x_{u}\in\mathbb{D}_{k}^{U}}\min_{x_{l}\in\mathbb{D}_{k}^{L}}d(F(x_{u}),F(x_{l}))$
(2)

where $core(\mathbb{D}_{k}^{U},\mathbb{D}_{k}^{L})$ returns a sample from
unlabeled dataset $\mathbb{D}_{k}^{U}$ using the labeled dataset
$\mathbb{D}_{k}^{L}$, $d(F(x_{u}),F(x_{l}))$ is the distance between a labeled
point $x_{l}$ from $\mathbb{D}_{k}^{L}$ and an unlabeled point $x_{u}$ from
$\mathbb{D}_{k}^{U}$. $F$ is the feature extractor. For the SVM training, a
classifier is learned with $F$ = $F_{S}$ given by the pretrained model
$\mathcal{M}_{S}$. For the CNN fine tuning, the feature extractor is given by
$\mathcal{M}_{k-1}$, the model available from the latest iteration. In
Equation 2, the unlabeled sample which is furthest away from its closest
labeled sample is selected. The baseline AF obtained is noted $core$.

##  4 Method

Classical AFs select the samples based on either the probability or feature
estimates from a single model. We hypothesize that using the model predictions
from the model learned in the previous active learning cycle can lead to more
efficient sampling. The informativeness of samples is ascertained by taking
into account the change in their probability distribution in successive
iterations. The strategy prioritizes samples which were predicted with high
certainty in the previous iteration but which gives uncertain prediction in
the current model. We derive an analogy to a student who gave confident
response to a question, but becomes uncertain after learning some more
information. Knowing the true answer should benefit the student and provide
relevant missing information. The strategy is well-suited for the low budget
setting where the batch size is generally small. The update of model with
large number of samples could make the precedent model less relevant. Focusing
on the unlabeled samples on which the model becomes uncertain in its
predictions adds a novel component of uncertainty in the selection process. In
cases where the sample was correctly predicted, selecting these samples allows
the model to focus on samples that it is most likely to forget. Alternatively,
even if a sample was predicted incorrectly, the measure allows to select more
difficult samples which can improve the generalization ability of the model.
Hence, knowing the labels of these samples should be informative.

###  4.1 alamp: active learning with asynchronous model predictions

We present here the formulation of $alamp$ which allows to select the samples
with the maximum shift from certainty to uncertainty between the two
iterations. Note that any of the uncertainty measures can be used in $alamp$.
The definition of the method which exploits margin sampling as basic
acquisition function is:

$alamp(x)=\frac{marg_{k-1}(x)-marg_{k}(x)}{marg_{k-1}(x)+marg_{k}(x)}$ (3)

with $marg_{k}:\mathbb{D}_{k}^{U}\to\mathbb{R}$, the margin function as in
equation 1 defined on the set $\mathbb{D}_{k}^{U}$.

The score takes a normalized min-max view of uncertainty allowing to select
samples with maximum change (certainty to uncertainty) between the iteration.
The sample with higher score is selected. The numerator gives the difference
in the certainty between the previous and current iteration. The denominator
normalizes the certainties to ensure that for samples which same absolute
difference in certainty(numerator) one with lower sum of certainties is
selected. This allows the score to select samples with maximum relative shift
towards uncertainty.

We consider $\textrm{Alamp}_{\textrm{sort}}(\mathbb{D}_{k}^{U})$ a permutation
of the set $\mathbb{D}_{k}^{U}$ by ordering its element by decreasing value of
$alamp$ . $\mathbb{D}_{k+1}^{L}$ is obtained by the union of
$\mathbb{D}_{k}^{L}$ with the first $\frac{b}{t}$ samples of
$\textrm{Alamp}_{\textrm{sort}}(\mathbb{D}_{k}^{U})$.

The method has low supplementary memory requirements since it stores the
probability distributions at each iterative step. At the first iterative step,
we have access to only the probability estimate $\mathcal{P}_{0}$ from the
initial model $\mathcal{M}_{0}$, which is trained over the initial randomly
selected dataset $\mathbb{D}_{0}^{L}$, thus the selection is based on the
uncertainty criteria in the first iterative step.

###  4.2 alamp-div

$alamp$ inherits the limitations of the uncertainty-based method used in its
definition in terms of sample representativity. We introduce a variant of the
method, named $alamp-div$ which selects informative samples from different
regions of the classification space. $alamp-div$ is described in Algorithm 1.
$alamp$ sorts the samples based on the difference of certainty measure of the
sample on the previous iteration and current iteration. The samples can
therefore be assigned to pseudo classes according to the class predicted in
the previous iteration. The selection process is driven toward selecting the
same number of samples from each pseudo class so to aim for representativeness
and balance across classes. This enables the selection of informative samples
across a diverse set of classifier boundaries in a multi class problem.

Algorithm 1 Diversification algorithm

1:$U$: a list of unlabeled samples sorted according to AF

2:$k$: current iterative step

3:$top$: a dictionary which assigns top class prediction in the iteration
$k-1$ to all samples in $U$

4:$b$ : budget of samples to be selected

5:procedure div($U$, $top$, $b$)

6: Build $L$: list of samples selected from $U$ of length $b$

7: while len($L$)$\leq$ $b$ do

8: seenclasses = empty list : reinitialize memory of classes

9: for each item $i$ in $U$ do

10: $topclass=$ top[i] :predicted class at iteration $k-1$ for sample $U[i]$

11: if $topclass$ not in $seenclasses$ then

12: if $i$ not in $L$ then

13: add sample $i$ in $L$

14: add $topclass$ in $seenclasses$

15: end if

16: end if

17: end for

18: end while

19: $L=L[0:b]$

20: return $L$

21:end procedure

##  5 Experiments

We first describe the experimental setup for the transfer and fine-tuning
training schemes that are tested. Then, we describe the evaluation datasets.
Finally, we present the results and their analysis.

###  5.1 Setup

The experimental setup is designed to focus on the small annotation budgets,
which is most challenging for AL. In our experiment, we use 200 samples for
the transfer and fine-tuning initial AL budget. The AL process is then run for
15 iterations with 200 samples selected at each iteration. The total budget at
the end of the process includes 3200 samples. Additional experiments with a
higher budget setting are provided in the supplementary material.

We experiment with two training schemes. For comparability, a ResNet-18
architecture [28] is used as backbone of both of the training schemes tested
here. The first scheme, noted $FT$, is based on fine-tuning and mirrors the
dominant approach in existing deep AL works [11, 8]. We fine-tune the pre-
trained model for 80 epochs. All the parameters are optimised using stochastic
gradient descent with Nesterov momentum of 0.9. The initial learning rate is
0.01 and is reduced by a factor of 10 when the train error rate plateaus for
10 epochs. We use a weight decay parameter of 0.001. The models are trained
using the Pytorch framework. Thresholding [29] which is shown to be effective
to mitigate imbalance for deep models is used in experiments with imbalanced
datasets. The experiments are repeated for 5 runs and the average performance
is reported.

$FT$ can be suboptimal when the budget is small enough to optimize the large
number of parameters of the DNN. An alternate to $FT$ is to learn a SVM
classifier over the features of the pre-trained model. Transfer learning
scheme, noted as SVM here, has been proven to be beneficial when the number of
annotated AL samples is limited [15]. In our work, we exploit the features of
a pre-trained model on $ILSVRC$ [30] dataset. The scikit-learn implementation
of SVC classifier is used with standard default parameters. The cost sensitive
SVM implementation is used for imbalanced datasets. The regularization
parameter is selected using a cross-validation on the training data. While
sub-optimal, the use of training data for validation necessary because of data
scarcity specific to AL. The $SVM$ training scheme is deterministic once the
initial subset is selected.

###  5.2 Datasets

The acquisition function and the training schemes are tested on three
publicly-available image classification datasets:

  * •

$Cifar100$ [31] is designed for coarse-grained object classification.

  * •

$Food-101$ [32] is focused on fine-grained food recognition

  * •

$IMN-100$ is a subset of ImageNet which includes fine-grained classes (i.e.
ImageNet leaves). Note that the intersection between $IMN-100$ and $ILSVRC$ is
empty.

The three datasets are balanced and their main statistics are provided in
Table 1. In addition, we test our methods on three imbalanced datasets.
$MIT-67$ [33] is designed for indoor scene recognition and is imbalanced. We
also induce imbalance in $Cifar100$ and $Food-101$. An imbalance induction
procedure was applied to $Cifar100$ and $Food-101$ for all datasets to have
similar imbalance ratio for standardized comparison. The imbalance ratio is
defined as $ir=\frac{\sigma}{\mu}$, with $\sigma$ standard deviation and $\mu$
the mean of images per class in the dataset. The main statistics of the
obtained datasets are provided in Table 2.

Dataset | Class | Train images/class | Test images/class
---|---|---|---
Cifar100 | 100 | 500 | 100
Food-101 | 101 | 750 | 250
IMN-100 | 100 | 1000 | 200

Table 1: Dataset statistics.

Dataset | Class | Train Images | Mean($\mu$) | Std($\sigma$) | $ir$
---|---|---|---|---|---
Food-101 | 101 | 22956 | 227.28 | 180.31 | 0.793
CIFAR-100 | 100 | 17168 | 171.68 | 126.98 | 0.740
MIT-67 | 67 | 14281 | 213.15 | 168.16 | 0.789

Table 2: Dataset statistics. $ir$ is the imbalance ratio.

Figure 2: Iterative active learning performance with $SVM$ and $FT$ training
schemes at each of 15 iterative steps for balanced datasets Cifar100, Food-101
and IMN-100 with initial budget of 200 and total budget of 3200. 200 samples
added at each iteration Best viewed in color.

Figure 3: Iterative active learning performance accuracy with $SVM$ and $FT$
training schemes at each of 15 iterative steps for imbalanced datasets
Cifar100, Food-101 and MIT-67 with initial budget of 200 and total budget of
3200. 200 samples added at each iteration Best viewed in color.

Figure 4: Imbalance profile (bottom) with $SVM$ training schemes at each of 15
iterative steps for imbalanced datasets Cifar100, Food-101 and MIT-67 with
initial budget of 200 and total budget of 3200. 200 samples added at each
iteration Best viewed in color. Figure 5: Iterative active learning
performance for diversification applied to $rand$ and $marg$ with $SVM$
training schemes at each of 15 iterative steps for Cifar100 with initial
budget of 200 and total budget of 3200. 200 samples added at each iteration.

###  5.3 Analysis of results

The results obtained for the three balanced datasets using the baselines and
the proposed methods are presented in Figure 2. Note that we provide both the
detailed evolution of accuracy across AL iterations and the averaged
performance of each method. Globally, $alamp$ and $alamp-div$ provide the best
performance across the three datasets for $SVM$ training scheme. $random$ acts
as a strong baseline, especially for $FT$ training scheme, where none of the
methods that are tested can outperform $random$. Further the performance of
$SVM$ scheme is clearly higher than that of the usual $FT$ scheme. This is an
interesting result which is analyzed in detail in Subsection 5.4.

Here we discuss the performance of different AFs in the $SVM$ training scheme.
The average accuracy gain for the entire AL cycle is 2.4 , 1.3 and 1.3 points
for $alamp$ compared $rand$ for balanced versions of $Cifar100$, $Food-101$
and $IMN-100$ respectively. More interesting from a practical perspective, the
number of samples required for achieving 50 percentage of accuracy for
$Cifar100$ is 1800 with $random$ or $marg$, 1600 for $alamp$ and 1400 for
$alamp-div$. Similarly for $Food-101$, 40 percent accuracy is reached with
around 1600 samples for $random$, 1400 samples with $alamp$ and $marg$ and
1200 samples for $alamp-div$. $alamp-div$ avoids the annotation of 400 extra
samples as compared to $random$ to achieve 50 percent accuracy for $Cifar100$
and 40 percent accuracy for $Food-101$. The performance gain is more limited
for $IMN-100$. Overall accuracy for this dataset is already quite high with
$SVM$ training scheme. This is an expected result, since $IMN-100$ is closest
to the $ILSVRC$ dataset used to train the source model. $alamp-div$ and
$alamp$ are still the best methods with 70 percent accuracy attained with 1000
samples with $alamp$ and $alamp-div$, while $rand$ and $marg$ require 1200
samples.

$marg$ outperforms $random$ in the $SVM$ training scheme, showing that $SVM$
classifier provides reliable uncertainty estimates even at low budgets. In our
experiments, $marg$ becomes competitive to $alamp$ at large budgets when the
uncertainty estimates become stronger. This is explained by the fact that, as
the accuracy of the model increases, uncertainty measures becomes more
important to find the missing information. This is the case of $IMN-100$,
which has the highest overall accuracy among the three dataset tested. The
accuracy of $IMN-100$ is around 50 percent at the start of AL cycle and $marg$
is more competitive for $IMN-100$ than for the other two datasets.

$core$ has suboptimal performance in the $SVM$ training scheme for all
datasets. This is particularly the case of $Food-101$, which is most different
from the $ILSVRC$ dataset used as feature extractor. It gives comparable
performance to other AFs in the $FT$ training scheme where the feature
extractor is updated along with the classifier. $badge$ is suited only for
$FT$ training scheme as it requires the gradients on the features. In $SVM$
training scheme, the features are fixed and hence it is not possible to test
$badge$. In the $FT$ training scheme, $badge$ also fails to provide any
significant improvement over $random$.

###  5.4 Analysis of training schemes

A initial subset is needed to start the iterative AL process. It has two main
impacts on the $FT$ scheme as seen in Figure 2. First, at low budgets the
fine-tuned model fails to provide strong probability estimates for the
acquisition function . This is evident from the results where none of the
tested AFs is able to conclusively outperform $random$ sampling. It is also
the case for $badge$ which has shown improvement over $random$ in [9]. The key
difference is the lower budget setting studied in our work.

Second, the comparative analysis of the two training schemes shows that $FT$
is largely outperformed by the transfer learning strategy for low AL budgets.
The performance of $FT$ scheme starts at 11.16, 13.19 and 32.65 percentage
points for balanced $Cifar100$, $Food-10$ and $IMN-100$ respectively. The
corresponding accuracy with $SVM$ is significantly higher, with 25.5, 17.54
and 47.29 percentage points respectively. This is somewhat intuitive since
deep model can be accurately trained only if a relatively large amount of data
is available. $FT$ lags behind even at the end of the AL process for
$CIFAR100$ and $IMN-100$ but becomes competitive for $Food-101$. This last
result is explained by the lower similarity between $Food-101$ and $ILSVRC$
compared to the other datasets. The efficiency of transfer learning is lower
for this dataset, but still much better than fine-tuning in early phase AL.

The comparison of $FT$ and $SVM$ schemes has practical implications for AL.
The training process is much quicker with $SVM$ since it only requires an
update of the shallow classifiers. Further, a cross-validation step can be
envisaged to switch from $SVM$ to $FT$ training when $FT$ outperforms $SVM$
training scheme. As suggested by $Food-101$ results, this happens once there
are enough samples for a competitive training of deep models.

###  5.5 Impact on imbalanced datasets

The performance of the methods on imbalanced dataset for $SVM$ scheme of
annotated subset is presented in Figure 3. Both $alamp$ and $alamp-div$
provide improvement over the baselines methods. $alamp$ provides average gain
of 1.99, 0.9 and 1.49 points for $Cifar100$, $Food-101$ and $MIT-67$
respectively. The diversification component is particularly more effective for
imbalanced datasets with gains of 3.59, 1.14 and 2.71 points respectively. For
example, 50 percent performance on $Cifar100$, is reached with 1600 samples
for $alamp-div$, while it takes atleast 2000 samples for any other best
method. A possible explanation can be found in the imbalance profile of
selected subsets (Figure 4). The imbalance profiles show the effectiveness of
the methods $alamp$ and $alamp-div$ to mitigate the imbalance from being
propagated to labeled subset. The results are reported after the use of
effective techniques from imbalanced learning. The improvements with the
proposed methods also shows the importance of tackling imbalance at the time
of sample selection for imbalanced datasets.

###  5.6 Impact of diversification

The diversification procedure is effective for both balanced and imbalanced
dataset, where $alamp-div$ improves results over $alamp$. The key reason for
its effectiveness is that $alamp$ prioritizes samples with high certainty in
the previous iteration. Even though the class prediction changes after the
update of the model, samples having different class prediction with high
confidence at the previous iteration are likely belong to different regions of
representation space.

We also test the diversification procedure for standard acquisition functions
$rand$ and $marg$ on $Cifar100$. $core$ is not considered here as it already
selects representative samples and also is not competitive with other AFs. The
pseudo class for $rand$ and $marg$ is assigned using the current class
prediction. The diversification results are presented in Figure 5 , with
$rand-div$ and $marg-div$ with diversified version of $rand$ and $marg$
respectively.

$alamp-div$ still provides the best performance, but interestingly $rand-div$
outperforms $rand$. The gain for $rand-div$ is particularly higher at the
start of the iterative cycle, where representative sampling is shown to be
more important. $marg-div$ has very little effect compared to $marg$. This is
expected since $marg$ sorts the samples in terms of uncertainty. Thus, the
class predictions are not reliable and the diversification procedure becomes
ineffective.

##  6 Conclusion

In our work, a transfer learning approach is explored as an alternative to
classical fine tuning approach used in deep AL. We show that $SVM$ classifier
over fixed representation prove to be very effective alternative at lower
budgets.

The main contribution of this work is the introduction of two new acquisition
functions. $alamp$ and $alamp-div$ capture the dynamic nature of probability
estimates of iterative AL models. They outperform competitive baselines over
both balanced and imbalanced image classification datasets. A diversification
component is introduced to combine the objectives of informativeness and
representativeness. We tested the diversification procedure for random
sampling, margin sampling and our proposed method. The diversified version of
$alamp$ is particularly effective compared to the other two sampling methods
as $alamp$ provides strong pseudo class predictions using the certainty
measure from the previous iteration.

The result of the proposed informative measure and the diversification
procedure is inconclusive for $FT$ training scheme. This could be a result of
evolving representation space with fine-tuning of model. In the future, we
plan to explore ways to implement the proposed informative measure for fine-
tuning scheme using different snapshots during the fine-tuning process.
Further, larger pre-trained models learned on bigger datasets would allow
transfer learning scheme to perform well in more application domains.

## References

  * [1] Burr Settles.  Active learning literature survey.  Technical report, University of Winsconsin, 2010.
  * [2] William H. Beluch, Tim Genewein, Andreas Nürnberger, and Jan M. Köhler.  The power of ensembles for active learning in image classification.  In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pages 9368–9377, 2018.
  * [3] Aron Culotta and Andrew McCallum.  Reducing labeling effort for structured prediction tasks.  In Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, Pennsylvania, USA, pages 746–751, 2005.
  * [4] Tobias Scheffer, Christian Decomain, and Stefan Wrobel.  Mining the web with active hidden markov models.  In Proceedings of the 2001 IEEE International Conference on Data Mining, 29 November - 2 December 2001, San Jose, California, USA, pages 645–646, 2001.
  * [5] Claude Elwood Shannon.  A mathematical theory of communication.  27(3):379–423, 7 1948.
  * [6] Sanjoy Dasgupta and Daniel J. Hsu.  Hierarchical sampling for active learning.  In Machine Learning, Proceedings of the Twenty-Fifth International Conference (ICML 2008), Helsinki, Finland, June 5-9, 2008, pages 208–215, 2008.
  * [7] Xianglin Li, Runqiu Guo, and Jun Cheng.  Incorporating incremental and active learning for scene classification.  In 11th International Conference on Machine Learning and Applications, ICMLA, Boca Raton, FL, USA, December 12-15, 2012. Volume 1, pages 256–261, 2012.
  * [8] Ozan Sener and Silvio Savarese.  Active learning for convolutional neural networks: A core-set approach.  In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, 2018.
  * [9] Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal.  Deep batch active learning by diverse, uncertain gradient lower bounds.  In ICLR, 2020.
  * [10] Shayok Chakraborty, Vineeth Nallure Balasubramanian, Qian Sun, Sethuraman Panchanathan, and Jieping Ye.  Active batch selection via convex relaxations with guaranteed solution bounds.  IEEE Trans. Pattern Anal. Mach. Intell., 37(10):1945–1958, 2015\.
  * [11] Yarin Gal, Riashat Islam, and Zoubin Ghahramani.  Deep bayesian active learning with image data.  In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 1183–1192, 2017.
  * [12] Mingfei Gao, Zizhao Zhang, Guo Yu, Sercan Ö Arık, Larry S Davis, and Tomas Pfister.  Consistency-based semi-supervised active learning: Towards minimizing labeling cost.  In European Conference on Computer Vision, pages 510–526. Springer, 2020.
  * [13] Ksenia Konyushkova, Raphael Sznitman, and Pascal Fua.  Learning active learning from data.  In Advances in Neural Information Processing Systems, pages 4225–4235, 2017.
  * [14] Zongwei Zhou, Jae Y. Shin, Lei Zhang, Suryakanth R. Gurudu, Michael B. Gotway, and Jianming Liang.  Fine-tuning convolutional neural networks for biomedical image analysis: Actively and incrementally.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pages 4761–4772, 2017.
  * [15] Umang Aggarwal, Adrian Popescu, and Celine Hudelot.  Active learning for imbalanced datasets.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), March 2020.
  * [16] Simon Tong and Edward Chang.  Support vector machine active learning for image retrieval.  In Proceedings of the ninth ACM international conference on Multimedia, pages 107–118, 2001.
  * [17] Klaus Brinker.  Incorporating diversity in active learning with support vector machines.  In Proceedings of the 20th international conference on machine learning (ICML-03), pages 59–66, 2003.
  * [18] Josh Attenberg and Seyda Ertekin.  Class imbalance and active learning.  Imbalanced Learning: Foundations, Algorithms, and Applications, pages 101–149, 2013.
  * [19] Seyda Ertekin, Jian Huang, and C Lee Giles.  Active learning for class imbalance problem.  In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 823–824, 2007.
  * [20] Jingbo Zhu and Eduard Hovy.  Active learning for word sense disambiguation with methods for addressing the class imbalance problem.  In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 783–790, 2007.
  * [21] Lei Han, Kean Ming Tan, Ting Yang, and Tong Zhang.  Local uncertainty sampling for large-scale multi-class logistic regression.  arXiv preprint arXiv:1604.08098, 2016.
  * [22] Wei-Ning Hsu and Hsuan-Tien Lin.  Active learning by learning.  In Twenty-Ninth AAAI conference on artificial intelligence. Citeseer, 2015.
  * [23] Kai Wei, Rishabh Iyer, and Jeff Bilmes.  Submodularity in data subset selection and active learning.  In International Conference on Machine Learning, pages 1954–1963, 2015.
  * [24] Denis Gudovskiy, Alec Hodgkinson, Takuya Yamaguchi, and Sotaro Tsukizawa.  Deep active learning for biased datasets via fisher kernel self-supervision.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [25] David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel.  Mixmatch: A holistic approach to semi-supervised learning.  In Advances in Neural Information Processing Systems, pages 5049–5059, 2019.
  * [26] Juseung Yun, Byungjoo Kim, and Junmo Kim.  Weight decay scheduling and knowledge distillation for active learning.
  * [27] Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia.  Selection via proxy: Efficient data selection for deep learning.  In International Conference on Learning Representations, 2020.
  * [28] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Conference on Computer Vision and Pattern Recognition, CVPR, 2016\.
  * [29] Mateusz Buda, Atsuto Maki, and Maciej A. Mazurowski.  A systematic study of the class imbalance problem in convolutional neural networks.  Neural Networks, 106:249–259, 2018.
  * [30] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael S. Bernstein, Alexander C. Berg, and Fei-Fei Li.  Imagenet large scale visual recognition challenge.  International Journal of Computer Vision, 115(3):211–252, 2015\.
  * [31] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, 2009.
  * [32] Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool.  Food-101 – mining discriminative components with random forests.  In European Conference on Computer Vision, 2014.
  * [33] Ariadna Quattoni and Antonio Torralba.  Recognizing indoor scenes.  In 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2009), 20-25 June 2009, Miami, Florida, USA, pages 413–420, 2009.


Figure 9. A partially separating subsurface $C$ (shown in blue) for an end-
periodic homeomorphism $\rho$ with repelling ends on the left and attracting
ends on the right. The intersection of each handle strip with $C$ is a
subsurface of genus $3$ with a single boundary component (shown in pink). The
boundary of $C$ intersects the strips in arcs that represent the same isotopy
class as the intersection with the curves $v_{1},\ldots,v_{5}$ defining good
nesting neighborhoods of the ends.

######  Proposition 6.3.

If $C$ is fully separating, then $f=\rho h$ is strongly irreducible. If $C$ is
partially separating with respect to $\rho$, but not fully separating, then
$f=\rho h$ is irreducible but not strongly irreducible.

Assuming the lemmas and corollary proved in the remainder of Section 6.1, we
now provide a straightforward proof of Proposition 6.3.

###### Proof.

Let $f=\rho h$ and $C={\rm supp}(h)$ be as in 6.2. Suppose that $C$ is
partially separating. Then by Corollary 6.7, Lemma 6.8, and Lemma 6.9, $f$ is
irreducible. Furthermore, if $C$ is fully separating then there are no
periodic lines by Lemma 6.9. Hence $f$ is strongly irreducible in this case.

Note that in the case that $C$ is partially, but not fully separating, there
exist at least two ends of the same type (that is, either both positive or
both negative) that are contained in the same complementary component of $C$.
This implies that there is a bi-infinite line $\ell$ passing between these two
ends, which is disjoint from $C$ and which lives in the complement of the
handle strips that comprise $\rho$. Since $\ell$ does not intersect the
support of $h$ (namely $C$) or any handle strips, then it is an AR-periodic
line passing between two ends of the same type and so $f$ is irreducible, but
not strongly irreducible.∎

The following lemmas will be used to show that there are no periodic lines or
reducing curves.

######  Lemma 6.4.

Let $\eta$ and $\alpha$ be as in 6.2, and let $\gamma$ be any curve with
$\pi_{C}(\gamma)\neq\emptyset$. If $d_{C}(\gamma,\rho(\eta))\geq 2$, then
$\pi_{C}(\rho^{-1}(\gamma))\neq\emptyset$. If
$d_{C}(\gamma,\rho^{-1}(\alpha))\geq 2$, then
$\pi_{C}(\rho(\gamma))\neq\emptyset$.

###### Proof.

If $d_{C}(\gamma,\rho(\eta))\geq 2$, then $i(\gamma,\rho(\eta))\neq 0$; see
(2.5). Therefore $i(\rho^{-1}(\gamma),\eta)\neq 0$, and hence
$\pi_{C}(\rho^{-1}(\gamma))\neq\emptyset$. A similar argument proves the
second claim. ∎

######  Lemma 6.5.

Let $\alpha,\eta$, and $B$ be as in 6.2. Then for all $k\geq 1$, we have

  1. (i)

$\pi_{C}(f^{-k}(\alpha))\subset h^{-1}B$

  2. (ii)

$\pi_{C}(f^{k}(\eta))\subset B$

Consequently, $f^{k}(\eta)$ and $f^{-k}(\alpha)$ fill $C$.

###### Proof.

We will split the proof into two pieces, first showing that (i) holds and then
(ii). In each case, the proof is by induction.

###### Proof of (i).

As noted in 6.2, $\rho^{-1}(\alpha)\subset B$, and since $C={\rm supp}(h)$ we
have $f^{-1}(\alpha)=h^{-1}\rho^{-1}(\alpha)\subset h^{-1}B$ and our base case
holds.

Assume, by induction, that there exists $m\geq 1$ such that
$\pi_{C}(f^{-m}(\alpha))\subset h^{-1}B$. Since
$d_{C}(h^{-1}\rho(\eta),\rho(\eta))\geq 9$, we have
$d_{C}(f^{-m}(\alpha),\rho(\eta))\geq 7$, and so Lemma 6.4 implies that
$\pi_{C}(\rho^{-1}f^{-m}(\alpha))\neq\emptyset$. Since
$i(f^{-m}(\alpha),\alpha)=0$ (because
$i(\alpha,f^{m}(\alpha))=i(\alpha,\rho^{m}(\alpha))=0$ by construction), we
also have that $i(\rho^{-1}f^{-m}(\alpha),\rho^{-1}(\alpha))=0$. This implies
that $d_{C}(\rho^{-1}f^{-m}(\alpha),\rho^{-1}(\alpha))=1$. Since
$d_{C}(\rho(\eta),\rho^{-1}(\alpha))=1$, the triangle inequality guarantees
that $\pi_{C}(\rho^{-1}f^{-m}(\alpha))\subset B$. Thus, as $C={\rm supp}(h)$,
we have

$h^{-1}\pi_{C}(\rho^{-1}f^{-m}(\alpha))=\pi_{C}(h^{-1}\rho^{-1}f^{-m}(\alpha))=\pi_{C}(f^{-m-1}(\alpha))\subset
h^{-1}B,$

as desired. ∎

###### Proof of (ii):.

Note that $f(\eta)=\rho(\eta)$, since $\eta\subset\partial_{-}C$. So we
immediately have that $\pi_{C}(f(\eta))\subset B$ and our base case holds.

Now, assume that for some $m\geq 1$, $\pi_{C}(f^{m}(\eta))\subset B$.
Therefore, we have that $h\pi_{C}(f^{m}(\eta))=\pi_{C}(hf^{m}(\eta))\subset
hB$. By 6.2, $d_{C}(\rho(\eta),\rho^{-1}(\alpha))=1$ and
$d_{C}(h(\rho(\eta)),\rho(\eta))\geq 9$, and thus
$d_{C}(hf^{m}(\eta),\rho^{-1}(\alpha))\geq 6$. Therefore, Lemma 6.4 implies
that $\pi_{C}(f^{m+1}(\eta))=\pi_{C}(\rho hf^{m}(\eta))\neq\emptyset$. Since
$i(\eta,f^{m}(\eta))=0$, we must also have that $i(f(\eta),f^{m+1}(\eta))=0$.
Thus, $\pi_{C}(f^{m+1}(\eta))\subset B$. ∎

So, we have shown by induction that for all $k\geq 1$,
$\pi_{C}(f^{-k}(\alpha))\subset h^{-1}B$ and $\pi_{C}(f^{k}(\eta))\subset B.$
Since $d_{C}(h\rho(\eta),\rho(\eta))\geq 9$, we have
$d_{C}(f^{k}(\eta),f^{-k}(\alpha))\geq 5$, and thus $f^{k}(\eta)$ and
$f^{-k}(\alpha)$ fill $C$ for all $k\geq 1$. ∎

######  Lemma 6.6.

Let $\gamma^{+}\subset\overline{U}_{+}$ and
$\gamma^{-}\subset\overline{U}_{-}$ be curves such that
$\pi_{C}(\rho^{-1}(\gamma^{+}))\neq\emptyset$ and
$\pi_{C}(\rho(\gamma^{-}))\neq\emptyset$. Let $\alpha,\eta$, and $B^{\prime}$
be as in 6.2. Then for all $k\geq 1$, we have

  1. (i)

$\pi_{C}(f^{-k}(\gamma^{+}))\subset h^{-1}B^{\prime}$; and

  2. (ii)

$\pi_{C}(f^{k}(\gamma^{-}))\subset B^{\prime}$.

Consequently, $f^{k}(\gamma^{-})$ and $f^{-k^{\prime}}(\gamma^{+})$ fill $C$
for all $k,k^{\prime}\geq 1$.

###### Proof.

As in Lemma 6.5, we will first show that (i) holds, and then prove (ii). In
both cases, the proof is by induction.

###### Proof of (i).

As noted in 6.2, we have $d_{C}(\rho(\eta),\rho^{-1}(\alpha))=1$, and since
$i(\rho^{-1}(\gamma^{+}),\rho^{-1}(\alpha))=0$, it follows that
$\pi_{C}(\rho^{-1}(\gamma^{+}))\subset B\subset B^{\prime}$. Therefore, we
have $h^{-1}\pi_{C}(\rho^{-1}(\gamma^{+}))=\pi_{C}(f^{-1}(\gamma^{+}))\subset
h^{-1}B^{\prime}$, proving the base case.

Assume by induction that for some $m\geq 1$,
$\pi_{C}(f^{-m}(\gamma^{+}))\subset h^{-1}B^{\prime}$. Since
$d_{C}(h^{-1}(\rho(\eta)),\rho(\eta))\geq 9$, we have
$d_{C}(f^{-m}(\gamma^{+}),\rho(\eta))\geq 7$, and Lemma 6.4 implies that
$\pi_{C}(\rho^{-1}f^{-m}(\gamma^{+}))\neq\emptyset$. As in that proof we have

$h^{-1}\pi_{C}(\rho^{-1}f^{-m}(\gamma^{+}))=\pi_{C}(h^{-1}\rho^{-1}f^{-m}(\gamma^{+}))=\pi_{C}(f^{-(m+1)}(\gamma^{+}))\neq\emptyset.$

Since $i(\gamma^{+},\alpha)=0$, this implies that
$i(f^{-(m+1)}(\gamma^{+}),f^{-(m+1)}(\alpha))=0$. Then as
$\pi_{C}(f^{-(m+1)}(\alpha))\subset h^{-1}B$, Lemma 6.5 implies
$\pi_{C}(f^{-(m+1)}(\gamma^{+}))\subset h^{-1}B^{\prime}$, as desired. ∎

###### Proof of (ii).

Since $i(\gamma^{-},\eta)=0$, we have $i(f(\gamma^{-}),f(\eta))=0$. Because
$h$ has no effect on $\partial C$, we have $f(\eta)=\rho h(\eta)=\rho(\eta)$,
and Lemma 6.5 implies that
$h(\pi_{C}(\rho(\gamma^{-}))=\pi_{C}(f(\gamma^{-}))\subset B\subset
B^{\prime}$, proving the base case.

Assume by induction that for some $m\geq 1$,
$\pi_{C}(f^{m}(\gamma^{-}))\subset B^{\prime}$. Then since
$d_{C}(\rho^{-1}(\alpha),\rho(\eta))=1$, we have
$d_{C}(f^{m}(\gamma^{-}),\rho^{-1}(\alpha))\leq 4$. The assumption that
$d_{C}(h\rho(\eta),\rho(\eta))\geq 9$, then implies
$d_{C}(hf^{m}(\gamma^{-}),\rho^{-1}(\alpha))\geq 5$. From Lemma 6.4 we deduce
that $\pi_{C}(\rho hf^{m}(\gamma^{-}))\neq\emptyset$. Now observe that since
$i(\gamma^{-},\eta)=0$, we have $i(f^{m+1}(\gamma^{-}),f^{m+1}(\eta))=0$. As
Lemma 6.5 gives us that $\pi_{C}(f^{m+1}(\eta))\subset B$, this implies that
$\pi_{C}(f^{m+1}(\gamma^{-}))\subset B^{\prime}$, as desired. ∎

Hence, we have shown by induction that for all $k\geq 1$,
$\pi_{C}(f^{-k}(\gamma^{+}))\subset h^{-1}B^{\prime}$ and
$\pi_{C}(f^{k}(\gamma^{-}))\subset B^{\prime}$, for any curves
$\gamma^{+}\subset U_{+}$ and $\gamma^{-}\subset U_{-}$ which project
nontrivially to $C$ after one handle shift. Since
$d_{C}(h\rho(\eta),\rho(\eta))\geq 9$, it follows that
$d_{C}(h^{-k}(\gamma^{+}),f^{k^{\prime}}(\gamma^{-}))\geq 3$, and we can
conclude that $f^{k}(\gamma^{-})$ and $f^{-k^{\prime}}(\gamma^{+})$ fill $C$
for all $k,k^{\prime}\geq 1$. ∎

######  Corollary 6.7.

There is no curve in $U_{+}$ which escapes into $U_{-}$ under backward
iteration of the map $f$, and there is no curve in $U_{-}$ which escapes into
$U_{+}$ under forward iteration of the map $f$.

###### Proof.

Let $\beta^{-}\subset U_{-}$ and $\beta^{+}\subset U_{+}$ be any curves. Then
there exists $q,r\geq 0$ so that $f^{q}(\beta^{-})\subset\overline{U}_{-}$ but
$\pi_{C}(\rho f^{q}(\beta^{-}))\neq\emptyset$, and
$f^{-r}(\beta^{+})\subset\overline{U}_{+}$ but
$\pi_{C}(\rho^{-1}f^{-r}(\beta^{+}))\neq\emptyset$. Note that the curves
$\gamma^{-}=f^{q}(\beta^{-})$ and $\gamma^{+}=f^{-r}(\beta^{+})$ satisfy the
hypotheses of Lemma 6.6. Thus, for all $k>\max\\{q,r\\}$, $f^{k}(\beta^{-})$
and $f^{-k}(\beta^{+})$ project nontrivially to $C$. Consequently, $\beta^{-}$
cannot escape into $U_{+}$ under forward iteration of $f$ and $\beta^{+}$
cannot escape into $U_{-}$ under backward iteration of $f$. ∎

######  Lemma 6.8.

Let $C$ be either partially or fully separating and let $f=\rho h$ be as in
6.2. Then, there are no curves that are periodic under the homeomorphism $f$.
That is, for curves $\delta$ on $S$, $f^{m}(\delta)\neq\delta$ for all $m\neq
0$.

###### Proof.

Suppose $\delta$ is a simple closed curve in $S$ which is periodic under $f$.

Note that if any part of $\delta$ essentially intersects $U_{+}$ or $U_{-}$,
then $\delta$ cannot be periodic because it will always move further into
$U_{+}$ under positive powers of $f$ or will always move further into $U_{-}$
under negative powers of $f$. Hence, if $\delta$ is periodic under $f$, then
$\delta\subset S-(U_{+}\sqcup U_{-})$.

There are now two cases to consider. Either $\delta$ essentially intersects
$C$, or $\delta$ is contained entirely in $S-(U_{+}\sqcup U_{-}\sqcup C)$. If
$\delta$ is contained entirely in $S-(U_{+}\sqcup U_{-}\sqcup C)$, then by the
assumptions on $U_{+}$, $U_{-}$, and $C$, this means that $\delta$ must
essentially intersects some handle strip. Since the components of the
complement of the handle strips in $S-(U_{+}\sqcup U_{-}\sqcup C)$ are
contractible (being homeomorphic to closed disks, minus a finite set of points
on the boundary). However, if $\delta$ essentially intersects a handle strip
outside of $C$, then this portion of $\delta$ will also be carried further out
into an end along this handle strip under either forward or backward iteration
of $f$.

So, we assume that $\delta$ essentially intersects $C$ but is disjoint from
$U_{+}$ and $U_{-}$, and that $m>0$ is such that $f^{m}(\delta)=\delta$. Let
$\gamma^{+}\subset U_{+}$ and $\gamma^{-}\subset U_{-}$ be such that
$\pi_{C}(\rho^{-1}(\gamma^{+}))\neq\emptyset$ and
$\pi_{C}(\rho(\gamma^{-}))\neq\emptyset$, as in Lemma 6.6. Note that since
$i(\delta,\gamma^{\pm})=0$, this implies that
$i(f^{k}(\delta),f^{k}(\gamma^{\pm}))=0$ for all $k\in\mathbb{Z}$. But, Lemma
6.6 states that $f^{k}(\gamma^{-})$ and $f^{-k}(\gamma^{+})$ fill $C$ for all
$k>0$. In particular, since $f^{m}(\delta)=\delta=f^{-m}(\delta)$ essentially
intersects $C$, we must have $i(f^{m}(\delta),f^{m}(\gamma^{+}))\neq 0$ or
$i(f^{-m}(\delta),f^{-m}(\gamma^{-}))\neq 0$, which is a contradiction. ∎

######  Lemma 6.9.

If $C$ is partially separating, then $f$ has no AR-periodic lines. If $C$ is
fully separating, then $f$ has no periodic lines.

###### Proof.

We will first consider the case where $C$ is partially separating. Suppose $f$
has an AR-periodic line $\ell$ with period $m$, so that $f^{mp}(\ell)=\ell$
for all $p\in\mathbb{Z}$. As $\ell$ cannot fill either $U_{+}$ or $U_{-}$, we
can find curves $\beta^{+}\subset U_{+}$ and $\beta^{-}\subset U_{-}$ which
are each disjoint from $\ell$. There exist integers $q,r\geq 0$ such that
$f^{q}(\beta^{-})=\rho^{q}(\beta^{-})\subset\overline{U}_{-}$ but
$\pi_{C}(\rho f^{q}(\beta^{-}))\neq\emptyset$ and
$f^{-r}(\beta^{+})=\rho^{-r}(\beta^{+})\subset\overline{U}_{+}$ but
$\pi_{C}(\rho^{-1}f^{-r}(\beta^{+}))\neq\emptyset$.

The curves $\gamma^{-}=f^{q}(\beta^{-})$ and $\gamma^{+}=f^{-r}(\beta^{+})$
satisfy the hypotheses of Lemma 6.6, and thus
$f^{k}(\gamma^{-})=f^{q+k}(\beta^{-})$ and
$f^{-k^{\prime}}(\gamma^{+})=f^{-r-k^{\prime}}(\beta^{+})$ fill $C$ for all
$k,k^{\prime}\geq 1$. Note that since $i(\ell,\beta^{\pm})=0$, this implies
that $i(f^{k}(\ell),f^{k}(\beta^{\pm}))=0$ for all $k\in\mathbb{Z}$. Since
$f^{mp}(\ell)=\ell$ for all $p\in\mathbb{Z}$, this implies that
$i(\ell,f^{mp}(\beta^{\pm}))=0$ for all $p\in\mathbb{Z}$. But, for $p$ large
enough so that $mp>\max\\{q,r\\}$, Lemma 6.6 implies that $f^{mp}(\beta^{-})$
and $f^{-mp}(\beta^{+})$ fill $C$, contradicting the fact that $\ell$ was
disjoint from $\beta^{-}$ and $\beta^{+}$.

We now consider the case where $C$ is fully-separating and suppose that $f$
has a periodic line $\ell$ with period $m$. If $\ell$ passes between two ends
of $S$ of the same type (i.e. both attracting or both repelling), then in
order to be invariant, $\ell$ must intersect $C$ (or else it would get shifted
farther out the end under forward or backward iteration of $f$). If $\ell$
passes between two ends of $S$ of distinct types (i.e. one is attracting and
one is repelling), then $\ell$ must also intersect $C$ since $C$ is fully
separating. As $\ell$ can only intersect $U_{-}$ and $U_{+}$ in a finite
number of arcs and rays, we can find curves $\beta^{-}\subset U_{-}$ and
$\beta^{+}\subset U_{+}$ as before which are disjoint from $\ell$. But, this
gives rise to the same contradiction as in the case when $C$ was partially
separating, since $f^{pm}(\beta^{-})$ and $f^{-pm}(\beta^{+})$ must fill $C$
for sufficiently large $p$ by Lemma 6.6. ∎

###  6.2. Sharpness of the Upper Bound

In this subsection, we will use some of the examples of irreducible end-
periodic homeomorphisms we have constructed to show that Theorem 1.1 is
asymptotically sharp, in the sense made precise by the following theorem from
the introduction. Recall that $V_{\rm oct}$ is the volume of a regular ideal
octahedron.

Theorem 1.6 There is a sequence of strongly irreducible end-periodic
homeomorphisms $f_{k}\colon S\to S$ so that ${\rm
Vol}(\overline{M}_{f_{k}})\to\infty$ and $\frac{{\rm
Vol}(\overline{M}_{f_{k}})}{\tau(f_{k})}\to V_{\rm oct}$ as $k\to\infty$. In
fact, $|{\rm Vol}(\overline{M}_{f_{k}})-V_{\rm oct}\tau(f_{k})|$ is uniformly
bounded, independent of $k$.

We will only be considering strongly irreducible end-periodic homeomorphisms
$f=\rho h$, as constructed in Section 6.1. Thus, by Proposition 6.3, we will
require our subsurface $C={\rm supp}(h)$ to be fully separating.

######  Convention 6.10.

We make the same assumptions on $S,\alpha,\eta,\rho,h,C,U_{\pm},B,$ and
$B^{\prime}$ from 6.2, in addition to the following. We assume that $C$ is
fully separating, that there is a $4$–times punctured sphere
$\Sigma=\Sigma_{0,4}$ embedded in the subsurface $C\cap\rho(C)\subset C\subset
S$, and that each of the four boundary curves in $\overline{\Sigma}$ as well
as some curve $\gamma_{0}\subset\Sigma$ have all distinct topological types in
$S$: that is, there is no homeomorphism of $S$ taking any one of these curves
to any other one. For example, the curves can be chosen to all be separating
curves which each cut off a subsurface with different topological type. In
particular, no two boundary curves of $\overline{\Sigma}$ or $\gamma_{0}$ are
homotopic. For example, the conditions on $\Sigma$ hold when $\Sigma$ is
embedded in $C\cap\rho(C)$ so that $S-\Sigma$ consists of four pairwise non-
homeomorphic components and $\gamma_{0}$ cuts off a compact subsurface of $S$
not homeomorphic to any of the components of $S-\Sigma$.

We also fix a pants decomposition $P$ of $S$ which is $\rho$-invariant on
$U_{+}$ and $U_{-}$, and which contains the four boundary curves of $\Sigma$,
as well as $\partial C_{+}$, $\partial C_{-}$ and $\rho(\partial C_{-})$.

######  Lemma 6.11.

With the assumptions in 6.10 (and hence also 6.2), for all curves
$\gamma\subset C\cap\rho(C)$, we have that for all $k\geq 1$:

  1. (i)

$\pi_{C}(f^{-k}(\gamma))\subset h^{-1}B^{\prime}$; and

  2. (ii)

$\pi_{C}(f^{k}(\gamma))\subset B^{\prime}$.

###### Proof.

The proof will proceed in a similar manner as that of Lemma 6.6, with proofs
of both (i) and (ii) by induction.

###### Proof of (i).

Since $i(\alpha,\gamma)=0$, we have that
$i(\rho^{-1}(\alpha),\rho^{-1}(\gamma))=0$. In addition,
$\rho^{-1}(\gamma)\subset C$ since $\rho^{-1}(C\cap\rho(C))\subset C$. As
$d_{C}(\rho^{-1}(\alpha),\rho(\eta))=1$, we have
$h^{-1}\pi_{C}(\rho^{-1}(\gamma))=\pi_{C}(f^{-1}(\gamma))\subset
h^{-1}B^{\prime}$, proving the base case.

So, assume by induction that for some $m\geq 1$,
$\pi_{C}(f^{-m}(\gamma))\subset h^{-1}B^{\prime}$. As
$d_{C}(h^{-1}\rho(\eta),\rho(\eta))\geq 9$, we have
$d_{C}(f^{-m}(\gamma),\rho(\eta))\geq 6$, and hence Lemma 6.4 implies that
$\pi_{C}(\rho^{-1}f^{-m}(\gamma))\neq\emptyset$. As before, we have that
$h^{-1}\pi_{C}(\rho^{-1}f^{-m}(\gamma))=\pi_{C}(f^{-m-1}(\gamma))\neq\emptyset$.
Since $i(\gamma,\alpha)=0$, we have that
$i(f^{-m-1}(\alpha),f^{-m-1}(\gamma))=0$. By Lemma 6.5, we know that
$\pi_{C}(f^{-m-1}(\alpha))\subset h^{-1}B$, and so we must have that
$\pi_{C}(f^{-m-1}(\gamma))\subset h^{-1}B^{\prime}$, as desired.∎

###### Proof of (ii).

Since $\gamma\subset C\cap\rho(C)$, we have $i(\gamma,\eta)=0$, and hence
$i(f(\gamma),f(\eta))=0$. As $f(\eta)=\rho h(\eta)=\rho(\eta)$, we have
$\pi_{C}(f(\gamma))\subset B\subset B^{\prime}$, proving the base case.

Now, assume by induction that for some $m\geq 1$,
$\pi_{C}(f^{m}(\gamma))\subset B^{\prime}$. Then since
$d_{C}(h\rho(\eta),\rho(\eta))\geq 9$, we have
$d_{C}(hf^{m}(\gamma),\rho(\eta))\geq 6$, and hence Lemma 6.4 implies
$\pi_{C}(f^{m+1}(\gamma))=\pi_{C}(\rho hf^{m}(\gamma))\neq\emptyset$. Since
$i(\gamma,\eta)=0$, it follows that we have
$i(f^{m+1}(\gamma),f^{m+1}(\eta))=0$. As $\pi_{C}(f^{m+1}(\eta))\subset B$ by
Lemma 6.5, we therefore have that $\pi_{C}(f^{m+1}(\gamma))\subset
B^{\prime}$, as desired. ∎

Having proved (i) and (ii), this completes the proof. ∎

Let $L\subset\overline{M}_{f}$ be the link defined by

$L=\partial\overline{\Sigma}\cup\gamma_{0}\subset S\times\\{1\\}\subset
M_{f}\subset\overline{M}_{f}.$

Write $\overline{M}_{0}=\overline{M}_{f}-L$ for the complement of $L$ in
$\overline{M}_{f}$. Note that
$\partial\overline{M}_{0}=\partial\overline{M}_{f}$, but $\overline{M}_{0}$
has five ends with neighborhoods homeomorphic to $T^{2}\times(0,\infty)$.

######  Lemma 6.12.

The manifold $\overline{M}_{0}$ admits a convex hyperbolic structure such that
$\partial\overline{M}_{0}$ is totally geodesic.

###### Proof.

Instead of simply removing $L$ from $\overline{M}_{f}$, we instead remove an
open tubular neighborhood of $L$ to produce a compact $3$-manifold whose
boundary consists of $\partial\overline{M}_{f}$ together with five tori.
Declaring the union of these five tori to be the paring locus, we have that
the resulting manifold, together with the tori, satisfies all conditions of
being a pared $3$-manifold with incompressible boundary, except possibly
conditions (4) and (5). We can prove these, and simultaneously prove that the
pared manifold is acylindrical, by proving that the double,
$D\overline{M}_{0}$, is atoroidal (see Section 2.8). If we do this, then we
may apply Theorem 2.20 to deduce that $\overline{M}_{0}$ admits a convex
hyperbolic structure with totally geodesic boundary.

So, suppose to the contrary that there is an embedded, torus $T$ in
$D\overline{M}_{0}$. There are two cases to consider: (a) $T$ is contained in
(one copy of) $\overline{M}_{0}$; and (b) $T$ essentially intersects
$\partial\overline{M}_{0}$ in $D\overline{M}_{0}$.

First, suppose that $T$ is contained entirely inside of (one copy of)
$\overline{M}_{0}$, and let $S^{\prime}=S-L\subset\overline{M}_{0}$. We assume
that $T\pitchfork S^{\prime}$ (this can always be done by a small
perturbation) such that $\Gamma=T\cap S^{\prime}$ has the minimal number of
components among all tori isotopic to $T$ which are transverse to
$S^{\prime}$. We claim that $T-\Gamma$ is a union of annuli. Suppose to the
contrary, that $T-\Gamma$ is not a union of annuli. Then, since the Euler
characteristic of $T$ is 0, there must be some disk $D$ in $T-\Gamma$. Note
that $\partial D$ is an inessential curve in $S^{\prime}$. Otherwise,
$\partial D$ bounds an essential curve in $S^{\prime}$ and $D$ is a
compressing disk contradicting the incompressibility of $S^{\prime}$. Since
$\partial D$ is not essential in $S^{\prime}$, then it bounds a disk in
$S^{\prime}$ which together with $D$ bounds a $3$-ball in $\overline{M}_{0}$.
The $3$-ball can be used to define an isotopy removing the intersection of $T$
with $S^{\prime}$ forming $\partial D$, which contradicts the minimality of
$\Gamma$. Therefore, $T-\Gamma$ consists entirely of annuli.

Let $M_{0}\subset\overline{M}_{0}$ denote the interior, so that
$M_{0}=M_{f}-(L\times\\{1\\})$. Setting

$N=S\times[0,1]-(L\times\\{1\\}\cup f(L)\times\\{0\\}),$

then $M_{0}$ is obtained from $N$ by gluing

$\partial_{1}N=(S-L)\times\\{1\\}\subset S\times\\{1\\}$

via the homeomorphism $f$ to

$\partial_{0}N=(S-f(L))\times\\{0\\}\subset S\times\\{0\\}.$

Since we may assume that $T$ is contained in $M_{0}$, the annuli in $T-\Gamma$
compactify to embedded, incompressible annuli $(A,\partial A)\to(N,\partial
N)$. We let $\mathcal{A}$ denote the union of these annuli, whose boundary is
the union of $\Gamma\subset\partial_{1}N\subset S\times\\{1\\}$ and
$f(\Gamma)\subset\partial_{0}N\subset S\times\\{0\\}$.

Since each component of $S^{\prime}\subset S$ is $\pi_{1}$–injective, the
annuli in $\mathcal{A}$ are in fact incompressible in $S\times[0,1]$. Let
$A\subset N$ be a component of $\mathcal{A}$. By work of Waldhausen (see
Proposition 3.1 and Lemma 3.4 of [Wal68]), $A$ is either boundary parallel in
$S\times[0,1]$ or vertical, meaning it is isotopic to an annulus of the form
$\gamma\times[0,1]\subset S\times[0,1]$ for some curve $\gamma\subset S$.
These two options are illustrated in Figure 10. If all annuli are vertical,
then $T$ is in fact an incompressible torus in $\overline{M}_{f}$, a
contradiction. Therefore, we assume that there is at least one component
$A\subset\mathcal{A}$ which is boundary parallel in $S\times[0,1]$. Because
the number of components of $\Gamma$ in $\partial_{1}N$ is equal to the number
of components of $f(\Gamma)$ in $\partial_{0}N$, we may assume that both
boundary components of $A$ are in $\partial_{1}N$.

$\alpha_{i}$
---
$f(\alpha_{i})$
---
$[0,1]$
---
$N$
---
$\partial_{1}N\subset S\times\\{1\\}$
---
$\partial_{0}N\subset S\times\\{0\\}$
---
$A$
---
$A^{\prime}$
---
$A_{1}$
---
$A_{5}=A_{m+1}$
---
$\alpha_{i}$
---
$f(\alpha_{i})$
---
$A_{1}$
---
$A_{2}$
---
$A_{3}$
---
$A_{4}$
---
$A$
---
Figure 10. In this schematic of $(N,\partial N)$, the curves of $L$ and $f(L)$
are represented by purple dots on $S\times\\{1\\}$ and $S\times\\{0\\}$,
respectively. All of the annuli shown in the diagram on the left are _boundary
parallel_ and the annuli $A_{1},A_{2},A_{3},$ and $A_{4}$ in the diagram on
the right are _vertical_

Note that $A$ cannot be boundary parallel in $N$ since this could be used to
define an isotopy in $M_{0}$ to reduce the number of components of
$\Gamma=T\cap S^{\prime}$. Therefore, we may assume that $A$ has both boundary
curves parallel to some $\alpha_{i}\subset L$ in $S\times\\{1\\}$ and on
opposite sides of some small neighborhood of $\alpha_{i}$. Choosing a
different component of $\mathcal{A}$ if necessary, we may assume that $A$ is
an innermost annulus of this sort, and let
$\partial_{+}A,\partial_{-}A\subset\Gamma\subset S^{\prime}$ be the two
components of $\partial A$. These curves $\partial_{+}A,\partial_{-}A$ thus
bound an annulus $G\subset S\times\\{1\\}$ containing $\alpha_{i}$ as a core
curve and no other components of $\Gamma$ in its interior.

Let $A_{1}\subset\mathcal{A}$ be the component with one boundary component
$\partial_{-}A_{1}=f(\partial_{+}A)\subset\partial_{0}N$. The other boundary
component $\partial_{+}A_{1}$ is not equal to $f(\partial_{-}A)$, for if it
were, then $T$ would be a peripheral torus, contradicting the assumption that
$T$ is essential. If $\partial_{+}A_{1}\subset\partial_{0}N$, then $A_{1}$ is
boundary parallel in $S\times[0,1]$ and so $\partial A_{1}$ is the boundary of
an annulus $G^{\prime}\subset S\times\\{0\\}$. This must also contain a
component $f(\alpha_{j})\subset f(L)$ (or else we could have reduced the
number of components of $\Gamma$). Note that both $f(\alpha_{j})$ and
$f(\alpha_{i})$ are isotopic in $S\times\\{0\\}$ to $f(\partial_{+}A)$ and
hence are isotopic to each other. It follows that $i=j$ by our choice of $L$,
and hence $f(G)$ is properly contained in $G^{\prime}$. Since
$f(\partial_{-}A)$ is also the boundary component of some annulus
$A^{\prime}\subset\mathcal{A}$ which is disjoint from $A_{1}$, it must be that
the other boundary component of $A^{\prime}$ is contained in
$G^{\prime}-f(G)$. This annulus $A^{\prime}$ is also boundary parallel in
$S\times[0,1]$, but note that the annulus in $S\times\\{0\\}$ with the same
boundary curves as $A^{\prime}$ is entirely contained in $G^{\prime}-f(G)$,
which can contain no components of $f(L)$. Thus $A^{\prime}$ is boundary
parallel in $N$, providing an isotopy of $T$ to reduce the number of
components of intersection with $S^{\prime}$, again a contradiction. This case
is illustrated in the diagram on the left of Figure 10.

Therefore, the annulus $A_{1}$ is necessarily vertical and
$\partial_{+}A_{1}\subset\partial_{1}N$. There is thus an annulus
$A_{2}\subset\mathcal{A}$ with
$\partial_{-}A_{2}=f(\partial_{+}A_{1})\subset\partial_{0}N$. Either $A_{2}$
is boundary parallel in $S\times[0,1]$, or
$\partial_{+}A_{2}\subset\partial_{1}N$ and there is an annulus
$A_{3}\subset\mathcal{A}$ with $\partial_{-}A_{3}=f(\partial_{+}A_{2})$.
Continuing in this way, “tracing around the torus $T$” we obtain a sequence of
annuli $A_{1},A_{2},\ldots,A_{m}$ which are all vertical, but for which
$\partial A_{m+1}\subset\partial_{0}N$. Then $A_{m+1}$ is boundary parallel in
$S\times[0,1]$, and as before, there must be some curve $f(\alpha_{j})\subset
f(L)$ isotopic in $S\times\\{0\\}$ to $\partial_{-}A_{m+1}$. This means that
$\alpha_{j}\subset L$ is isotopic to $\partial_{+}A_{m}$ in $S\times\\{1\\}$.

The annuli $A_{1},\ldots,A_{m}$ glue together in $M_{0}$ to give an annulus
from $\partial_{+}A$ to $\partial_{+}A_{m}$. Since $\partial_{+}A$ is isotopic
to $\alpha_{i}$ in $S$ and $\partial_{+}A_{m}$ is isotopic to $\alpha_{j}$ in
$S$, inside $M_{f}$ we can flow this glued-up annulus forward to produce an
isotopy from $f^{m}(\alpha_{i})$ to $\alpha_{j}$. Since $f$ is irreducible,
$f^{m}(\alpha_{i})$ cannot be isotopic to $\alpha_{i}$, and hence $i\neq j$.
On the other hand, $f^{m}$ is a homeomorphism from $S$ to itself sending
$\alpha_{i}$ to $\alpha_{j}$ (up to isotopy), but this contradicts the fact
that all components of $L$ in $S$ have different homeomorphism types. This
contradiction shows that there is no essential torus in $\overline{M}_{0}$. An
illustration of this case is shown in the diagram on the right of Figure 10.

So, suppose now there is an embedded, non-peripheral torus $T$ in
$D\overline{M}_{0}$ which essentially intersects a higher genus boundary
component of $\overline{M}_{0}$ in $D\overline{M}_{0}$. An argument similar to
the first case implies that we may assume that $T$ meets
$\partial\overline{M}_{0}$ minimally and transversely, so that each component
of $T-\partial\overline{M}_{0}$ compactifies to an essential annulus in one of
the copies of $\overline{M}_{0}$ in $D\overline{M}_{0}$. Let
$A\subset\overline{M}_{0}$ be any such annulus.

Note that $A$ meets $\partial\overline{M}_{0}=\partial\overline{M}_{f}$ in two
essential curves, and so $A$ is incompressible in $\overline{M}_{f}$. Since
$\overline{M}_{f}$ is acylindrical and since $\partial A$ are essential curves
in $\overline{M}_{f}$, $A$ must be boundary parallel in $\overline{M}_{f}$. So
there must be some annulus $A^{\prime}\subset\partial\overline{M}_{f}$, so
that $A\cup A^{\prime}$ must bound a solid torus in $\overline{M}_{f}$. Since
$A$ is essential in $\overline{M}_{0}$, there must be some curve
$\alpha_{i}\in L$, which is contained in this solid torus, but this solid
torus gives a homotopy of $\alpha_{i}$ into $\partial\overline{M}_{f}$. This
contradicts Lemma 6.11. Therefore, $\overline{M}_{0}$ admits a complete
hyperbolic metric such that the boundary is totally geodesic. ∎

We will use the following result of Adams [Ada85, Theorem 3.1] to conclude
that the convex hyperbolic metric on $\overline{M}_{0}$ from the previous
lemma makes the thrice-punctured spheres coming from $\Sigma-L$ totally
geodesic in $\overline{M}_{0}$.

######  Theorem 6.13.

A properly embedded incompressible thrice-punctured sphere in a hyperbolic
3-manifold is isotopic to a totally geodesic properly embedded thrice-
punctured sphere.

After an isotopy, we can assume that $\Sigma-L$ consists of pairwise disjoint,
totally geodesic thrice-punctured spheres in $\overline{M}_{0}$. Next, we cut
open along these surfaces to obtain four totally geodesic thrice-punctured
sphere boundary components. We will make use of them in the following proof of
Theorem 1.6 which concludes this section.

###### Proof of Theorem 1.6..

Fix a $4$-holed sphere $\Sigma$ and a pants decomposition $P$ as in 6.10. As
before, $L$ denotes the union of the four boundary curves of
$\overline{\Sigma}$ together with the pants curve $\gamma_{0}$ in $\Sigma$,
and $\overline{M}_{0}:=\overline{M}_{f}-(L\times\\{1\\})$. By Lemma 6.12,
$\overline{M}_{f}$ admits a convex hyperbolic metric with totally geodesic
boundary. By Theorem 6.13, we can cut along the two totally geodesic thrice-
punctured spheres inside $\overline{M}_{0}$ which yields a new 3-manifold,
$\overline{M}_{0}^{\prime}$ with four more boundary components, each of which
is a thrice-punctured sphere.

Now isometrically glue $2k$ copies of the four-holed sphere block,
$\mathring{\mathcal{B}}$, (with its complete hyperbolic metric with totally
geodesic boundary) into $\overline{M}_{0}^{\prime}$, stacked vertically so
that the bottom of the first block is glued to the bottom new boundary
component and so that the top of the last block is glued to the top new
boundary component. We call this new manifold $\overline{M}_{k}$, and note
that

${\rm Vol}(\overline{M}_{k})={\rm Vol}(\overline{M}_{0})+4kV_{{\rm oct}}.$

Next observe that we may alternatively view $\overline{M}_{k}$ as being
obtained from $\overline{M}_{f}$ by removing a link
$L_{k}\subset\overline{M}_{f}$, each component of which is contained in fiber
of $M_{f}$. More precisely, we can take $L_{k}$ to consist of $5+2k$ curves,
consisting of
$(\partial\overline{\Sigma}\cup\gamma_{0})\times\left\\{\tfrac{1}{4}\right\\}$
together with $2k$ curves of the form
$\beta_{i}\times\left\\{\tfrac{1}{4}+\tfrac{i}{4k}\right\\}$, where
$\beta_{i}\subset\Sigma$ (the choice of interval $[\tfrac{1}{4},\tfrac{3}{4}]$
is arbitrary: up to isotopy, we could of course take any interval in $[0,1]$).
For any integer $s$, we let $\overline{M}_{k,s}$ denote the result of
performing $(1,s)$–Dehn filling on each torus cusp of $\overline{M}_{k}$. For
$s=0$, this gives us back the original mapping torus,
$\overline{M}_{k,0}\cong\overline{M}_{f}$.

Suppose that $P$ and $f^{-1}(P)$ differ by $r$ pants moves, and suppose that
the pants move which occurs on $\Sigma$ occurs at the $m$-th vertex in the
path between $P$ and $f^{-1}(P)$ in $\mathcal{P}(S)$. As in Section 4, we may
view this move as occurring in the fiber
$S\times\left\\{\tfrac{m}{r}\right\\}$. Gluing in the $2k$ pants blocks and
performing $(1,0)$–Dehn filling to get
$\overline{M}_{k,0}\cong\overline{M}_{f}$ corresponds to choosing a new path
between $P$ and $f^{-1}(P)$ which now has length $r+2k$ (we have essentially
inserted $2k$ redundant pants moves that occur inside $\Sigma$). So, we may
perform an isotopy so that the initial pants move on $\Sigma$ now occurs in
the fiber $S\times\left\\{\tfrac{m}{N+2k}\right\\}$, and so that the $i$-th
pants block (after filling) has one boundary component in the fiber
$S\times\left\\{\tfrac{m+i-1}{N+2k}\right\\}$ and the other boundary component
in the fiber $S\times\left\\{\tfrac{m+i}{N+2k}\right\\}$.

By Proposition 2.18, $\overline{M}_{k,s}\cong\overline{M}_{fD_{k,s}}$, where
$D_{k,s}$ is a product of powers of Dehn twists about the curves in $L_{k}$
(projected into $\Sigma\subset S$). Letting $D\overline{M}_{k}$ denote the
double of $\overline{M}_{k}$ over the boundary, for each $s>0$ we can view the
double $D\overline{M}_{k,s}$ of $\overline{M}_{k,s}$ over its boundary as
distinct Dehn fillings of $D\overline{M}_{k}$. By Theorem 2.25, for $s$
sufficiently large, $D\overline{M}_{k,s}$ is hyperbolic, and as $s\to\infty$,
${\rm Vol}(D\overline{M}_{k,s})\to{\rm Vol}(D\overline{M}_{k})$. By Mostow
rigidity, the involution interchanging the two sides of the double is isotopic
to an isometry with respect to the hyperbolic metric on $D\overline{M}_{k,s}$
and fixes $\partial\overline{M}_{k,s}$. Consequently, the hyperbolic metric on
$\overline{M}_{k,s}$ also has totally geodesic boundary and

${\rm Vol}(\overline{M}_{k,s})\to{\rm Vol}(\overline{M}_{k})={\rm
Vol}(\overline{M}_{0})+4kV_{\rm oct}.$

For each $k>0$, let $s_{k}$ be such that

${\rm Vol}(\overline{M}_{k,s_{k}})\geq 4kV_{\rm oct}.$

We note that the end-periodic monodromy $f_{k}=fD_{k,s_{k}}=\rho hD_{k,s_{k}}$
for $\overline{M}_{k,s_{k}}$ is strongly irreducible. This is because our only
requirement on the map $h$ in Section 6.1 was that
$d_{C}(h\rho(\eta),\rho(\eta))\geq 9$ in $\mathcal{AC}(C)$. As $L_{k}$ is
disjoint from $\rho(\eta)$, this implies $D_{k,s_{k}}$ must preserve
$\rho(\eta)$. Hence, $hD_{k,s_{k}}\rho(\eta)=h\rho(\eta)$, and therefore we
have $d_{C}(hD_{k,s_{k}}\rho(\eta),\rho(\eta))\geq 9$.

By Theorem 1.1, we have that ${\rm Vol}(\overline{M}_{f_{k}})\leq V_{\rm
oct}\tau(f_{k})\leq V_{\rm oct}(n_{T}+2n_{S}+4k)$, where $n_{S}$ and $n_{T}$
are the number of pants moves on four-punctured spheres and tori,
respectively, in the original path between $P$ and $f^{-1}(P)$ (note that all
$2k$ pants move from the blocks occur on four-punctured spheres). On the other
hand, ${\rm Vol}(\overline{M}_{f_{k}})\geq 4kV_{\rm oct}$, and therefore

$|{\rm Vol}(\overline{M}_{f_{k}})-V_{\rm oct}\tau(f_{k})|\leq V_{\rm
oct}(n_{T}+2n_{S}).$

Since ${\rm Vol}(\overline{M}_{f_{k}})\geq 4kV_{\rm oct}\to\infty$ as
$k\to\infty$, this provides the required sequence $\\{f_{k}\\}$.∎

###  6.3. Large component translation

Here we prove the following corollary from the introduction.

Corollary 1.3 For any irreducible, end-periodic homeomorphism $f\colon S\to S$
and $R>0$, there exists an $f$–invariant component
$\Omega\subset\mathcal{P}_{f}(S)$ such that $\tau(f,\Omega)\geq R$.

###### Proof.

By Theorem 1.2, it suffices to find a sequence of $f$–invariant components
$\Omega_{k}\subset\mathcal{P}_{f}(S)$ so that

${\rm Vol}(\overline{M}_{f}-P_{\Omega_{k}})\to\infty$

as $k\to\infty$. For this, it is useful to observe that any pants
decomposition $P$ of $\partial\overline{M}_{f}$ arises as $P_{\Omega}$ for
some $f$–invariant component $\Omega\subset\mathcal{P}_{f}(S)$ if and only if
the preimage of $P$ in $\mathcal{U}_{\pm}\times\\{\pm\infty\\}$ are pants
decompositions. This is because $\Omega$ being $f$–invariant is equivalent to
requiring that any $P_{0}\in\Omega$ has the property that $P_{0}$ and
$f(P_{0})$ differ by a finite number of pants moves. This is equivalent to
$P_{0}$ being $f$–invariant when restricted to some nesting neighborhoods, and
since these nesting neighborhoods form “half” the infinite cyclic covers
$\mathcal{U}_{\pm}\to S_{\pm}$, this is equivalent to $P\subset S_{\pm}$
lifting to pants decompositions on $\mathcal{U}_{\pm}$.

Now choose any pants decomposition $P$ in an $f$–invariant component
$\Omega\subset\mathcal{P}_{f}(S)$ and consider
$P_{\Omega}\subset\partial\overline{M}_{f}$. Let $\gamma_{0}\subset
P_{\Omega}$ be any component such that
$\partial\overline{M}_{f}-(P_{\Omega}-\gamma_{0})$ contains a four-punctured
sphere component $\Sigma$. Consider the convex hyperbolic metric on
$\overline{M}_{f}-P_{\Omega}$ with totally geodesic boundary consisting of
thrice-punctured spheres, and as in the proof of Theorem 1.6, isometrically
glue on $2k$ copies of $\mathring{\mathcal{B}}$ stacked vertically so that the
bottom of the first block is glued to $\Sigma-\gamma_{0}$. The resulting
manifold $\overline{M}_{k}$ is homeomorphic to
$\overline{M}_{f}-(P_{\Omega}\cup L_{k})$, where $L_{k}\subset
M_{f}\subset\overline{M}_{f}-P_{\Omega}$ is a link in the interior. After an
isotopy, we can assume that the curves in $L_{k}$ are of the form
$\beta\times\\{x_{\beta}\\}$ with respect to some product structure on a
collar neighborhood $N\cong\partial\overline{M}_{f}\times[0,1]$ of
$\partial\overline{M}_{f}$, with $\beta\subset\Sigma$ and $x_{\beta}\in(0,1)$
for all $\beta$.

Similar to Proposition 2.18, performing $(1,s)$–Dehn filling on each torus
cusp of $\overline{M}_{k}$ simply changes the product structure on the collar
neighborhood of $\partial\overline{M}_{f}$, and consequently changes the pants
decomposition on the boundary by a composition of powers of Dehn twists in the
curves $L_{k}$. We can therefore denote the result of this Dehn filling as
$\overline{M}_{f}-P_{k,s}$ for some pants decomposition $P_{k,s}$ of
$\partial\overline{M}_{f}$. On the other hand, since all the Dehn twists occur
on curves in $\Sigma$, and the entire subsurface $\Sigma$ lifts to
$\mathcal{U}_{\pm}$, it follows that $P_{k,s}$ lifts to pants decompsitions on
$\mathcal{U}_{\pm}$. Therefore, $P_{k,s}=P_{\Omega_{k,s}}$ for some
$f$–invariant component $\Omega_{k,s}\subset\mathcal{P}_{f}(S)$. As in the
proof of Theorem 1.6, appealing to Theorem 2.25, we have

${\rm Vol}(\overline{M}_{f}-P_{\Omega_{k,s}})\to{\rm
Vol}(\overline{M}_{f}-P_{\Omega})+4kV_{\rm oct}.$

We may therefore choose $s_{k}$ sufficiently large so that

${\rm Vol}(\overline{M}_{f}-P_{\Omega_{k,s_{k}}})\geq 4kV_{\rm oct}.$

The term on the right tends to $\infty$, and thus setting
$\Omega_{k}=\Omega_{k,s_{k}}$ completes the proof. ∎

## References

  * [Ada85] Colin C. Adams.  Thrice-punctured spheres in hyperbolic $3$-manifolds.  Trans. Amer. Math. Soc., 287(2):645–656, 1985.
  * [Ada88] Colin C. Adams.  Volumes of $N$-cusped hyperbolic $3$-manifolds.  J. London Math. Soc. (2), 38(3):555–565, 1988.
  * [Ago03] Ian Agol.  Small 3-manifolds of large genus.  Geom. Dedicata, 102:53–64, 2003.
  * [APV20] Javier Aramayona, Priyam Patel, and Nicholas G. Vlamis.  The first integral cohomology of pure mapping class groups.  Int. Math. Res. Not. IMRN, (22):8973–8996, 2020.
  * [Arm69] Steve Armentrout.  Cellular decompositions of $3$-manifolds that yield $3$-manifolds.  Bull. Amer. Math. Soc., 75:453–456, 1969.
  * [AST07] Ian Agol, Peter A. Storm, and William P. Thurston.  Lower bounds on volumes of hyperbolic Haken 3-manifolds.  J. Amer. Math. Soc., 20(4):1053–1077, 2007.  With an appendix by Nathan Dunfield.
  * [AV18] Javier Aramayona and Ferrán Valdez.  On the geometry of graphs associated to infinite-type surfaces.  Math. Z., 289(1-2):309–322, 2018.
  * [AV20] Javier Aramayona and Nicholas G. Vlamis.  Big mapping class groups: An overview.  In Ken’ichi Ohshika and Athanase Papadopoulos, editors, In the tradition of Thurston: Geometry and Topology, pages 459–496. Springer, Cham, 2020.
  * [Bav16] Juliette Bavard.  Hyperbolicité du graphe des rayons et quasi-morphismes sur un gros groupe modulaire.  Geom. Topol., 20(1):491–535, 2016.
  * [BB16] Jeffrey F. Brock and Kenneth W. Bromberg.  Inflexibility, Weil-Peterson distance, and volumes of fibered 3-manifolds.  Math. Res. Lett., 23(3):649–674, 2016.
  * [BCM12] Jeffrey F. Brock, Richard D. Canary, and Yair N. Minsky.  The classification of Kleinian surface groups, II: The ending lamination conjecture.  Ann. of Math. (2), 176(1):1–149, 2012.
  * [Bra20] Ben Branman.  Spaces of pants decompositions for surfaces of infinite type.  Preprint, arXiv:2010.13169, 2020.
  * [Bro03a] Jeffrey F. Brock.  The Weil-Petersson metric and volumes of 3-dimensional hyperbolic convex cores.  J. Amer. Math. Soc., 16(3):495–535, 2003.
  * [Bro03b] Jeffrey F. Brock.  Weil-Petersson translation distance and volumes of mapping tori.  Comm. Anal. Geom., 11(5):987–999, 2003.
  * [CC03] Alberto Candel and Lawrence Conlon.  Foliations. II, volume 60 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2003.
  * [CC16] John Cantwell and Larwence Conlon.  Examples of endperiodic automorphisms.  Preprint, arXiv:1008.2549, 2016.
  * [CCF21] John Cantwell, Lawrence Conlon, and Sergio R. Fenley.  Endperiodic automorphisms of surfaces and foliations.  Ergodic Theory Dynam. Systems, 41(1):66–212, 2021.
  * [CRM20] Tommaso Cremaschi and José A. Rodríguez-Migueles.  Hyperbolicity of link complements in Seifert-fibered spaces.  Algebr. Geom. Topol., 20(7):3561–3588, 2020.
  * [CRMY19] Tommaso Cremaschi, José Andrés Rodríguez-Migueles, and Andrew Yarmola.  On volumes and filling collections of multicurves.  Preprint, arXiv:1911.02732, 2019.
  * [Dav86] Robert J. Daverman.  Decompositions of manifolds, volume 124 of Pure and Applied Mathematics.  Academic Press, Inc., Orlando, FL, 1986.
  * [DFV18] Matthew Gentry Durham, Federica Fanoni, and Nicholas G. Vlamis.  Graphs of curves on infinite-type surfaces with mapping class group actions.  Ann. Inst. Fourier (Grenoble), 68(6):2581–2612, 2018.
  * [Fen89] Sergio R. Fenley.  Depth-one foliations in hyperbolic 3-manifolds.  PhD thesis, Princeton University, 1989.
  * [Fen92] Sérgio R. Fenley.  Asymptotic properties of depth one foliations in hyperbolic $3$-manifolds.  J. Differential Geom., 36(2):269–313, 1992.
  * [Fen97] Sérgio R. Fenley.  End periodic surface homeomorphisms and $3$-manifolds.  Math. Z., 224(1):1–24, 1997.
  * [FK09] Louis Funar and Christophe Kapoudjian.  An infinite genus mapping class group and stable cohomology.  Comm. Math. Phys., 287(3):784–804, 2009.
  * [FM12] Benson Farb and Dan Margalit.  A primer on mapping class groups, volume 49 of Princeton Mathematical Series.  Princeton University Press, Princeton, NJ, 2012.
  * [Gab84] David Gabai.  Foliations and genera of links.  Topology, 23(4):381–394, 1984.
  * [Has86] Joel Hass.  Minimal surfaces in foliated manifolds.  Comment. Math. Helv., 61(1):1–32, 1986.
  * [JS79] William H. Jaco and Peter B. Shalen.  Seifert fibered spaces in $3$-manifolds.  Mem. Amer. Math. Soc., 21(220):viii+192, 1979.
  * [KM18] Sadayoshi Kojima and Greg McShane.  Normalized entropy versus volume for pseudo-Anosovs.  Geom. Topol., 22(4):2403–2426, 2018.
  * [LL21] Justin Lanier and Marissa Loving.  Curve graphs of surfaces with finite-invariance index 1.  Preprint, 2021.
  * [LMT21] Michael Landry, Yair Minsky, and Samuel Taylor.  Flows, growth rates, and the veering polynomial.  In preparation, 2021.
  * [Mar16] Bruno Martelli.  An introduction to geometric topology.  Preprint, arXiv:1610.02592, 2016.
  * [McM92] Curt McMullen.  Riemann surfaces and the geometrization of $3$-manifolds.  Bull. Amer. Math. Soc. (N.S.), 27(2):207–216, 1992.
  * [Min10] Yair Minsky.  The classification of Kleinian surface groups. I. Models and bounds.  Ann. of Math. (2), 171(1):1–107, 2010.
  * [MM99] Howard A. Masur and Yair N. Minsky.  Geometry of the complex of curves. I. Hyperbolicity.  Invent. Math., 138(1):103–149, 1999.
  * [MM00] H. A. Masur and Y. N. Minsky.  Geometry of the complex of curves. II. Hierarchical structure.  Geom. Funct. Anal., 10(4):902–974, 2000.
  * [Mor84] John W. Morgan.  On Thurston’s uniformization theorem for three-dimensional manifolds.  In The Smith conjecture (New York, 1979), volume 112 of Pure Appl. Math., pages 37–125. Academic Press, Orlando, FL, 1984.
  * [MR92] William Menasco and Alan W. Reid.  Totally geodesic surfaces in hyperbolic link complements.  In Topology ’90 (Columbus, OH, 1990), volume 1 of Ohio State Univ. Math. Res. Inst. Publ., pages 215–226. de Gruyter, Berlin, 1992\.
  * [MR19] Kathryn Mann and Kasra Rafi.  Large scale geometry of big mapping class groups.  Preprint, arXiv:1912.10914, 2019.
  * [NZ85] Walter D. Neumann and Don Zagier.  Volumes of hyperbolic three-manifolds.  Topology, 24(3):307–332, 1985.
  * [PV18] Priyam Patel and Nicholas G. Vlamis.  Algebraic and topological properties of big mapping class groups.  Algebr. Geom. Topol., 18(7):4109–4142, 2018.
  * [RM20] José Andrés Rodríguez-Migueles.  A lower bound for the volumes of complements of periodic geodesics.  J. Lond. Math. Soc. (2), 102(2):695–721, 2020.
  * [Rou74] R. Roussarie.  Plongements dans les variétés feuilletées et classification de feuilletages sans holonomie.  Inst. Hautes Études Sci. Publ. Math., (43):101–141, 1974.
  * [Sta78] John R. Stallings.  Constructions of fibred knots and links.  In Algebraic and Geometric Topology (Proc. Sympos. Pure Math., Stanford Univ., Stanford, Calif., 1976), Part 2, Proc. Sympos. Pure Math., XXXII, pages 55–60. Amer. Math. Soc., Providence, R.I., 1978\.
  * [Sto02] Peter A. Storm.  Minimal volume Alexandrov spaces.  J. Differential Geom., 61(2):195–225, 2002.
  * [Sto07] Peter A. Storm.  Hyperbolic convex cores and simplicial volume.  Duke Math. J., 140(2):281–319, 2007.
  * [Thu72] William P. Thurston.  Foliations of 3-manifolds that are circle bundles.  PhD thesis, UC Berkeley, 1972.
  * [Thu78] William P. Thurston.  Geometry and topology of $3$-manifolds, lecture notes.  Princeton University, 1978.
  * [Thu86] William P. Thurston.  Hyperbolic structures on $3$-manifolds. I. Deformation of acylindrical manifolds.  Ann. of Math. (2), 124(2):203–246, 1986.
  * [Wal68] Friedhelm Waldhausen.  On irreducible $3$-manifolds which are sufficiently large.  Ann. of Math. (2), 87:56–88, 1968.