# Boosting Active Learning via Improving Test Performance

Tianyang Wang,1 Xingjian Li,2 611footnotemark: 1 Pengkun Yang,3 Guosheng Hu,4
Xiangrui Zeng,7 Siyu Huang,5 Cheng-Zhong Xu,6 Min Xu7 The first two authors
contributed equally.corresponding author

###### Abstract

Central to active learning (AL) is what data should be selected for
annotation. Existing works attempt to select highly uncertain or informative
data for annotation. Nevertheless, it remains unclear how selected data
impacts the test performance of the task model used in AL. In this work, we
explore such an impact by theoretically proving that selecting unlabeled data
of higher gradient norm leads to a lower upper-bound of test loss, resulting
in a better test performance. However, due to the lack of label information,
directly computing gradient norm for unlabeled data is infeasible. To address
this challenge, we propose two schemes, namely expected-gradnorm and entropy-
gradnorm. The former computes the gradient norm by constructing an expected
empirical loss while the latter constructs an unsupervised loss with entropy.
Furthermore, we integrate the two schemes in a universal AL framework. We
evaluate our method on classical image classification and semantic
segmentation tasks. To demonstrate its competency in domain applications and
its robustness to noise, we also validate our method on a cellular imaging
analysis task, namely cryo-Electron Tomography subtomogram classification.
Results demonstrate that our method achieves superior performance against the
state of the art. Our source code is available at
https://github.com/xulabs/aitom/blob/master/doc/projects/al˙gradnorm.md.

## Introduction

In most scenarios, supervised learning is still the most reliable fashion for
training deep neural networks. However, data annotation is often arguably
expensive. To reduce the cost, active learning (AL) can be used to select a
portion of all unlabeled data for annotation and the annotated data is then
used to train a task model (e.g. CNN) in a supervised fashion. The goal of AL
is to obtain the best test performance of the task model given a specific
annotation budget. Therefore, the question becomes: what data should be
selected for annotation to achieve this goal?

According to the fashion for data selection, existing AL methods can be
generally categorized into two groups, namely uncertainty-based and diversity-
based. The former group aims to select the most uncertain data for annotation
(e.g. (Caramalau, Bhattarai, and Kim 2021; Zhang et al. 2020; Yoo and Kweon
2019; Sinha, Ebrahimi, and Darrell 2019)), whereas the latter group aims to
select unlabeled data that can diversify the labeled pool (Hasan and Roy-
Chowdhury 2015; Yang et al. 2015; Mac Aodha et al. 2014; Elhamifar et al.
2013; Bilgic and Getoor 2009; Nguyen and Smeulders 2004), which can also be
achieved by synthesizing new diverse labeled data (Mayer and Timofte 2020;
Mahapatra et al. 2018; Zhu and Bento 2017).

Although these two main streams of methods define the state-of-the-art
baselines, very little work has explored the connection between selected data
and the test performance of the task model used in AL. Such a connection can
be restated as: if an unlabeled sample is selected for annotation and used to
train the task model, then how the test performance of the model will be
impacted. Conversely, this connection can guide us to select unlabeled data
which helps improve the test performance.

This work focuses on exploring the aforementioned connection. To do so, we
exploit the influence function (Koh and Liang 2017) to analyze how the test
performance is impacted if an individual sample is selected for annotation and
used in training. Our theoretical analysis shows that selecting and annotating
unlabeled data of higher gradient norm111Here, the gradient is w.r.t. model
parameters rather than input. will result in a lower upper-bound of test loss,
leading to a better test performance. This finding naturally leads to a data
selection criterion in AL. To our best knowledge, this is the first work that
theoretically analyzes how data selection impacts the test performance in AL.
Moreover, to leverage our theoretical findings, we propose two independent
schemes to compute the gradient norm since it cannot be directly obtained
during data selection due to the lack of label information in AL settings. In
the first scheme (namely expected-gradnorm), inspired by (Cai et al. 2017;
Cai, Zhang, and Zhou 2013), we make use of all possible labels to compute an
expected empirical loss that is adopted to compute the gradient norm. In the
second scheme (namely entropy-gradnorm), we use entropy as a loss to compute
the gradient norm without resorting to any label information. The rationale of
the two schemes is also explained. We then propose a universal AL framework to
integrate these two schemes.

Note that although we aim to boost AL via improving test performance, there is
no need to have an access to test data. Our theoretical analysis is completely
based on the assumption that test data is unknown.

To validate our method, we conduct extensive experiments on three different
tasks, including image classification, semantic segmentation, and cryo-ET
(cryo-Electron Tomography) subtomogram classification (Gubins et al. 2019;
Chen et al. 2017) (Appendix A.5), which is an emerging technique for analyzing
the machinery of cellular systems. Our method outperforms the state-of-the-art
AL baselines, demonstrating its competency and task-agnostic nature.

We summarize our main contributions as follows. Firstly, we fundamentally
formulate the test performance in active learning and find that its major
impact factor is gradient norm that can effectively guide unlabeled data
selection. Secondly, we propose two schemes to compute gradient norm for
unlabeled data without resorting to ground-truth label. Thirdly, we
demonstrate that the proposed method achieves superior performance on
classical computer vision challenges as well as on a domain task in
computational biology.

## Related Work

Uncertainty-based AL. Recent advances rely on specialized auxiliary models to
estimate uncertainty for unlabeled data. For example, (Caramalau, Bhattarai,
and Kim 2021) designs a GCN (Kipf and Welling 2016) to select highly uncertain
data for annotation. (Haußmann, Hamprecht, and Kandemir 2019) adopts a
Bayesian network to predict uncertainty. (Zhang et al. 2020; Sinha, Ebrahimi,
and Darrell 2019; Ducoffe and Precioso 2018) use adversarial learning and
multiple auxiliary models (e.g. VAE (Kingma and Welling 2013)) to estimate
uncertainty. (Yoo and Kweon 2019) jointly learns the task model with a loss
prediction module, which aims to predict the empirical loss for unlabeled
data. This loss prediction module also needs customized design and training.
While the other methods do not require additional models, they still suffer
from inefficient unlabeled data selection. For instance, (Sener and Savarese
2018; Kuo et al. 2018) need to solve the classical K-center or 0-1 Knapsack
problem when selecting unlabeled data, and hence the time complexity is much
higher than the methods (Yoo and Kweon 2019; Sinha, Ebrahimi, and Darrell
2019) which only need a feed-forward step using trained auxiliary models
during data selection. Similarly, several Bayesian methods (Gal, Islam, and
Ghahramani 2017; Gal and Ghahramani 2016) suffer from inefficient uncertainty
estimation due to the need of thousands of feed-forward operations for each
unlabeled sample.

Diversity-based AL. This type of methods are also known as distribution-based.
For example, (Yang et al. 2015) proposes to add a diversity regularizer in the
objective function. (Elhamifar et al. 2013) uses sample diversity to provide a
guidance for solving a convex optimization problem in order to select diverse
data for annotation, whereas (Nguyen and Smeulders 2004) utilizes clustering
to sample diverse data for annotation. Traditionally, uncertainty and
diversity are treated as different criteria for data selection, however, a
recent study (Loquercio, Segu, and Scaramuzza 2020) points out that they are
highly correlated. In addition, with the aid of generative models (e.g. GAN
(Goodfellow et al. 2014) and VAE), new data can be synthesized to diversify
the labeled pool (Mayer and Timofte 2020; Mahapatra et al. 2018; Zhu and Bento
2017). Due to the difficulty and complexity in adversarial training, it needs
extra efforts to deploy these methods, especially when data format is changed.
For instance, the auxiliary GAN or VAE needs to be redesigned if using 3D data
(e.g. cryo-ET subtomogram image, studied in Appendix A.5).

Discussion. For more discussions of the related work, we refer readers to
Appendix A.9, in which we discuss how our work differs essentially from
(Settles, Craven, and Ray 2007; Roy and McCallum 2001).

## Methodology

We firstly explore what data needs to be selected for annotation by
theoretically analyzing the connection between selected data and test
performance. Then we propose two schemes to compute gradient norm for
unlabeled data. Lastly, we present a universal AL framework to leverage our
theoretical findings and the two schemes.

### What Data to be Selected

The main criterion to evaluate an AL method is the test performance of the
task model. To our best knowledge, very little work has managed to interpret
how selected unlabeled data directly impacts the test performance. This
remains challenging since test data is normally unknown at the time of model
training and data selection. In this work, we aim to draw such a connection
without resorting to test data. We also aim to use this connection to guide
the data selection in AL. Our ultimate goal is to select unlabeled data that
makes the task model yield a better test performance.

According to (Koh and Liang 2017), we know that given a model $f_{\theta}$,
such as a neural network, removing a sample $x$ from its training set will
approximately influence the loss at a test sample $x_{j}$ by

$I_{loss}(x,x_{j})=\frac{1}{n}\nabla_{\theta}L(f_{\theta}(x_{j}))^{\top}H_{\theta}^{-1}\nabla_{\theta}L(f_{\theta}(x))\enspace,$
(1)

where $n$ denotes the amount of existing training samples, and
$f_{\theta}(\cdot)$ refers to the feed-forward step that yields the logits
output of the model $f_{\theta}$, and
$H_{\theta}=\frac{1}{n}\sum_{i=1}^{n}\nabla^{2}_{\theta}L(f_{\theta}(x_{i}))$
is the average Hessian over all training samples. For each training sample,
since we want to compute its influence (if removed) on all the samples in a
test dataset, we compute the total influence as follows

$\begin{split}\sum_{j}I_{loss}(x,x_{j})=\frac{1}{n}\sum_{j}\nabla_{\theta}L(T^{c+1}(x_{j}))^{\top}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x))\enspace,\end{split}$
(2)

where the task model in AL cycle $c+1$ (i.e. $T^{c+1}$) is used as
$f_{\theta}$ in Eq. 1, and the index $j$ is over the test set. In this
section, we assume that data selection occurs in cycle $c$, and the selected
data is used in training in cycle $c+1$.

As indicated in (Koh and Liang 2017), although $I_{loss}(x,x_{j})$ could be
negative when a training sample is harmful to an individual $x_{j}$,
$\sum_{j}I_{loss}(x,x_{j})$ is generally positive. Intuitively, this means
removing a training sample will tend to increase the expected test loss.

In AL settings, assuming the test loss of $T^{c+1}$ is $L^{c+1}_{test}$, if a
training sample $x$ is removed from the labeled pool and not involved in
training $T^{c+1}$, then the influenced test loss $L^{\prime c+1}_{test}$ can
be computed by

$\begin{split}L^{\prime
c+1}_{test}&=L^{c+1}_{test}+\sum_{j}I_{loss}(x,x_{j})\\\
&=L^{c+1}_{test}+\frac{1}{n}\sum_{j}\nabla_{\theta}L(T^{c+1}(x_{j}))^{\top}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x))\enspace.\end{split}$
(3)

Since test data is unknown during data selection in AL, directly computing
$\sum_{j}\nabla_{\theta}L(T^{c+1}(x_{j}))^{\top}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x))$
is intractable. Given $H_{\theta}$ is positive definite by assumption (Koh and
Liang 2017), we can derive Eq. 4 by applying the Frobenius norm222We ignore
the norm order in equations to simplify the notations. on both sides of Eq. 3,
and then we have

$\begin{split}L^{\prime
c+1}_{test}&=||L^{c+1}_{test}+\frac{1}{n}\sum_{j}\nabla_{\theta}L(T^{c+1}(x_{j}))^{\top}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x))||\\\
&\leq
L^{c+1}_{test}+\frac{1}{n}||\sum_{j}\nabla_{\theta}L(T^{c+1}(x_{j}))^{\top}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x))||\\\
&=L^{c+1}_{test}+\frac{1}{n}||\nabla_{\theta}L(T^{c+1}(x))^{\top}\sum_{j}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x_{j}))||\\\
&\leq
L^{c+1}_{test}+\frac{1}{n}||\nabla_{\theta}L(T^{c+1}(x))||\cdot||\sum_{j}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x_{j}))||\enspace.\end{split}$
(4)

For a potential test dataset,
$||\sum_{j}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x_{j}))||$ can be regarded
as a fixed term. Therefore, the upper-bound of $L^{\prime c+1}_{test}$ is
mainly determined by $||\nabla_{\theta}L(T^{c+1}(x))||$. However, directly
computing $||\nabla_{\theta}L(T^{c+1}(x))||$ is infeasible due to two
challenges:

  1. 1.

The model $T^{c+1}$ is not available by the time of data selection in cycle
$c$;

  2. 2.

$x$ does not have ground-truth label for computing $L$ (addressed in next
section).

Here, we address the first challenge. To do so, we involve an approximation
that uses $||\nabla_{\theta}L(T^{c}(x))||$ to bound
$||\nabla_{\theta}L(T^{c+1}(x))||$. This is reasonable since in AL $x$ is used
to train $T^{c+1}$ rather than $T^{c}$, which means $T^{c}$ has never observed
$x$ during its training. The approximation is intuitive since the gradient
norm w.r.t. the model parameters of a sample (even not employed in training)
is likely to decrease as the model better fits the training set. Moreover,
although it is not a rigorous guarantee for _any_ sample, we show a
theoretical support that the gradient norm of the _average_ loss is guaranteed
to reduce under reasonable assumptions. The detailed proof is given in
Appendix A.1. With this bound, we can derive Eq. 5 from Eq. 4.

$\begin{split}L^{\prime c+1}_{test}&\leq
L^{c+1}_{test}+\frac{1}{n}||\nabla_{\theta}L(T^{c+1}(x))||\cdot||\sum_{j}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x_{j}))||\\\
&\lesssim
L^{c+1}_{test}+\frac{1}{n}||\nabla_{\theta}L(T^{c}(x))||\cdot||\sum_{j}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x_{j}))||\enspace.\end{split}$
(5)

The Eq. 5 indicates that in cycle $c+1$, removing a training sample $x$ of
higher $||\nabla_{\theta}L(T^{c}(x))||$ will result in a higher upper-bound of
$L^{\prime c+1}_{test}$. Therefore, such $x$ should be preserved in the
labeled training pool of cycle $c+1$. Conversely, from the perspective of
cycle $c$, during data selection, more unlabeled samples of higher
$||\nabla_{\theta}L(T^{c}(x))||$ should be selected for annotation and added
to the labeled pool for training $T^{c+1}$. Such a data selection scheme helps
$T^{c+1}$ maintain a lower upper-bound of $L^{\prime c+1}_{test}$. Therefore,
we conclude that unlabeled data of higher gradient norm should be selected for
annotation in AL. To better introduce our motivation of leveraging gradient
norm in AL, we provide an intuitive explanation in Appendix A.3.

### Computing Gradient Norm

The Eq. 5 can be used to guide the unlabeled data selection in AL.
Specifically, we select unlabeled data $x$ that leads to a higher
$||\nabla_{\theta}L(T^{c}(x))||$, in order to lower the upper-bound of the
test loss, as analyzed in last section. However, computing
$||\nabla_{\theta}L(T^{c}(x))||$ remains challenging since computing the
empirical loss $L$ is not viable due to the lack of the label information of
$x$. To address this challenge, we propose two schemes to compute
$||\nabla_{\theta}L(T^{c}(x))||$, namely expected-gradnorm and entropy-
gradnorm, respectively. We also analyze the rationale of the schemes in this
section.

#### Expected-Gradnorm Scheme.

In order to compute $||\nabla_{\theta}L(T^{c}(x))||$, we need to compute the
loss $L$ first. Then, for neural nets we can back-propagate the loss to obtain
the gradient w.r.t the model parameters $\theta$. Since $L$ cannot be computed
directly for unlabeled data, inspired by (Cai et al. 2017; Cai, Zhang, and
Zhou 2013), we propose to use an expected empirical loss to approximate the
real empirical loss. Suppose there are $N$ classes in a given unlabeled pool,
we use $y_{i}$ to denote the label of the $i^{th}$ class. Note that $y_{i}$ is
a label candidate of $x$ rather than the ground-truth of $x$. For each sample
$x$, its expected loss can be computed by

$\begin{split}L_{exp}(T^{c}(x))=\sum_{i=1}^{N}P(y_{i}|x)L_{i}(T^{c}(x),y_{i})\enspace,\end{split}$
(6)

where $P(y_{i}|x)$ is the posterior obtained using softmax over $T^{c}(x)$ and
$L_{i}$ is the empirical loss when the $i^{th}$ label candidate is assumed to
be the ground-truth label of $x$. Note that this scheme does not require the
real ground-truth of $x$.

This scheme can be easily used for classification problems because the
posterior $P$ is a single vector for each individual data sample. However, for
other problems, such as semantic segmentation (i.e. pixel-level
classification), this scheme is not an ideal solution. It is because in this
scheme we need to consider all possible labels for all individual pixels,
resulting in a huge number of possibilities (see Appendix A.4 for details),
which is intractable in practice. To address this challenge, we propose
another scheme in next section to compute gradient norm for unlabeled data.

#### Entropy-Gradnorm Scheme.

In this scheme, we use the output entropy to compute gradient norm.
Specifically, we use the differentiable entropy of the softmax output of the
network as a loss function. Since computing entropy does not require label,
this scheme is more suitable for complex tasks in which assuming label is
infeasible, such as the semantic segmentation task. Following the definition
of $P(y_{i}|x)$ and $N$ in Eq. 6, the entropy loss for each sample $x$ is
defined as

$\begin{split}L_{ent}(T^{c}(x))=-\sum_{i=1}^{N}P(y_{i}|x)logP(y_{i}|x)\enspace.\end{split}$
(7)

Without an access to any label information, it is reasonable to choose entropy
as a surrogate of the real loss due to two reasons.

  1. 1.

According to Eq. 5, adding a training sample of higher gradient norm (if
computed by the entropy loss in Eq. 7) is expected to reduce the entropy of a
test sample. In classification problems, reducing the entropy is usually
beneficial to reducing typical supervised losses such as the cross-entropy.
For example, in semi-supervised learning (Berthelot et al. 2019; Grandvalet,
Bengio et al. 2005), entropy is adopted as an effective regularizer that can
be minimized, naturally leading to the use of unlabeled samples in training.

  2. 2.

When the task model is well trained (a good model, e.g. in later AL cycles),
entropy well approximates cross-entropy (Srinivas and Fleuret 2018).

To use this scheme, one only needs to compute entropy for output posterior and
back-propagate this entropy through the task model to obtain the gradient.
Despite its simplicity, this scheme can be used for both classification and
semantic segmentation, leading to its task-agnostic nature. Note that the
model parameters will not be updated during data selection, no matter which
scheme is used to compute gradient.

#### Discussion of Approximations.

Note that, both the expected empirical loss defined in Eq. 6 and the entropy
loss in Eq. 7 can be used in Eq. 5 as the loss function $L$, since the
derivation does not require a particular form of the non-negative $L$. They
also satisfy the requirements for the loss function employed in the influence
function (Koh and Liang 2017) and for deriving the reduction of average
gradient norm (Appendix A.1). Furthermore, we provide quantitative evaluations
to validate that more than 90% of the selected samples indeed have reduced
gradient norm when the loss functions defined in Eq. 6 and Eq. 7 are used to
compute gradient. This further demonstrates the reliability of the
approximation in Eq. 5. We show the detailed evaluations in Appendix A.2.

### Proposed Active Learning Framework

To leverage our theoretical findings, we develop a universal AL framework to
integrate the two schemes introduced in last section. Specifically, we train
the task model with randomly selected initial annotated data and then use one
of the schemes to select unlabeled data for annotation. The newly annotated
data is added to the labeled pool and we re-train the task model with the
updated labeled pool. Our framework makes minimal changes to the classical AL
pipeline, making it easy to be implemented for different scenarios. We
summarize our framework in Algorithm 1.

Input:
$\mathcal{T}$: task model; $\mathcal{U}$: unlabeled pool; $\mathcal{L}$:
labeled pool; $\mathcal{Y}$: test dataset; $\mathcal{C}$: number of AL cycles
$\mathcal{E}$: number of epochs within each cycle; $L$: empirical loss; $K$:
annotation budget in each cycle; $x$: each unlabeled sample;

Output:
the task model $\mathcal{T}$

begin

initialize $\mathcal{T}$;
for  _$i\leftarrow 1$ to $\mathcal{C}$_ do

for  _$j\leftarrow 1$ to $\mathcal{E}$_ do

train $\mathcal{T}$ with $L$ on $\mathcal{L}$;

if  _expected-gradnorm_ then

compute the expected loss $L_{exp}$ for $x$ according to Eq. 6;
select $K$ samples of the highest $||\nabla_{\theta}L_{exp}(T^{c}(x))||$ for
annotation;

if  _entropy-gradnorm_ then

compute the entropy loss $L_{ent}$ for $x$ according to Eq. 7;
select $K$ samples of the highest $||\nabla_{\theta}L_{ent}(T^{c}(x))||$ for
annotation;

update $\mathcal{L}$ and $\mathcal{U}$, respectively;

return $\mathcal{T}$

Algorithm 1 Proposed Active Learning Framework.

## Experiments

To evaluate the proposed method, we conduct extensive experiments with AL
settings. For fair comparison, we reproduce the baseline methods following
their suggested settings and practices, such as the way of pre-processing
input. In all the experiments except ImageNet, we run the AL methods for 7
cycles, corresponding to 7 different annotation budgets (i.e. from 10% to 40%
with an incremental size of 5%). For the very first cycle, we randomly select
10% of the data from the unlabeled pool and use the selected data as the
initial training data for all the compared methods. Then for each subsequent
cycle, we select unlabeled data using a specific AL method, and re-train the
task model with the updated labeled pool. Note that the term Cycle is
different from Epoch, since it only corresponds to the annotation budget in
AL. All the reported results are averaged over 3 runs. For ImageNet, we
conduct the experiments with 5 AL cycles (i.e. annotation budget varies from
10% to 30%) and the results are averaged over 2 runs, which are acceptable for
very large-scale datasets.

We compare our method with the state-of-the-art AL baselines, including random
selection, core-GCN (Caramalau, Bhattarai, and Kim 2021), sraal (Zhang et al.
2020), vaal (Sinha, Ebrahimi, and Darrell 2019), ll4al (Yoo and Kweon 2019),
core-set (Sener and Savarese 2018), QBC (Kuo et al. 2018), and mc-dropout (Gal
and Ghahramani 2016). We denote our method with exp-gn (expected-gradnorm) and
ent-gn (entropy-gradnorm), respectively. We also refer readers to the Appendix
for the training details (A.8), more experimental analysis (i.e. the
biomedical cryo-ET experiment (A.5)), the ablation study (A.6), and the time
efficiency of the different methods (A.7).

Figure 1: Classification performance of the AL methods on Cifar10 (top left),
Cifar100 (top right), SVHN (bottom left), and Caltech101 (bottom right),
respectively. Dashed line refers to training the model with all the training
data.

### Image Classification

Datasets. We exploit five widely used image classification datasets in our
experiments, namely Cifar10 (Krizhevsky, Hinton et al. 2009), Cifar100
(Krizhevsky, Hinton et al. 2009), SVHN (Netzer et al. 2011), Caltech101 (Fei-
Fei, Fergus, and Perona 2006), and ImageNet (Deng et al. 2009). Both Cifar
datasets include 50000 training and 10000 test samples, distributed across 10
and 100 classes, respectively. SVHN also consists of 10 classes, while it
includes more samples than the two Cifar datasets, namely 73257 for training
and 26032 for testing. For fair comparisons with the other methods, we do not
use the additional training data in SVHN. Caltech101 has 101 classes of bigger
images (e.g. $300\times 200$ pixels), which are non-uniformly distributed
across the classes. Some class has up to 800 samples, while some other only
includes 40 samples. ImageNet is a large-scale dataset including around 1.28
million training samples across 1000 classes. We follow the common practice to
report model performance on the validation set that consists of 50000 samples.

Model selection. Following the practice in (Zhang et al. 2020; Yoo and Kweon
2019), we use ResNet-18 (He et al. 2016) as the task model for all the
experiments except ImageNet. Specifically, for the two Cifar and SVHN
datasets, we exploit a customized
version333https://github.com/kuangliu/pytorch-cifar of ResNet18, due to the
compatibility of input dimensions. For Caltech101, we exploit the original
ResNet-18. To perform fair comparisons, we use the same task model for all the
compared methods. For instance, (Sinha, Ebrahimi, and Darrell 2019) originally
used a VGG Net as the task model, and we replace it with ResNet-18 to maintain
consistency. In addition, to validate that our method is architecture-
independent, we use VGG-16 (Simonyan and Zisserman 2015) as the task model for
all the methods in the ImageNet task.

Figure 2: Comparison of the AL methods on ImageNet classification (left) and Cityscapes semantic segmentation (right). budget (%) | 10 | 15 | 20 | 25 | 30 | 35 | 40
---|---|---|---|---|---|---|---
core-set (Sener and Savarese 2018) | 217 | 230 | 284 | 339 | 329 | 289 | 255
vaal (Sinha, Ebrahimi, and Darrell 2019) | 268 | 259 | 215 | 231 | 256 | 240 | 256
ll4al (Yoo and Kweon 2019) | 391 | 893 | 1084 | 1710 | 1698 | 2035 | 1817
sraal (Zhang et al. 2020) | 506 | 819 | 1120 | 1765 | 1842 | 2133 | 2196
expected-gradnorm | 703 | 980 | 1216 | 1942 | 2318 | 2427 | 2448
entropy-gradnorm | 677 | 932 | 1141 | 1993 | 2317 | 2429 | 2443
Table 1: Comparison of the AL methods via the number of the selected samples
(out of $K=2500$) of higher gradient norm. The Cifar10 dataset is used.

Results and Analysis. As shown in Fig. 1 and Fig. 2 (left), our method
outperforms the baselines on all the datasets. Besides, we have the following
observations that further demonstrate the advantages of our method. Firstly,
for each annotation budget, our method yields a higher accuracy than the
others. This is a desired property for AL methods since the annotation budget
may vary in real-world scenarios. Secondly, our method needs fewer labeled
samples to achieve a better performance. For example, on Cifar10, our method
(ent-gn) yields an accuracy of 91.77% with 12.5K labeled samples, whereas
sraal needs 2.5K more and vaal needs 5K more samples to achieve the similar
performance. Thirdly, the superior performance on SVHN and Caltech101
demonstrates that our method can well handle imbalanced datasets. Fourthly,
the superior performance on ImageNet demonstrates that our method is effective
for very large-scale datasets. Lastly, we observe that on Cifar10 our method
(ent-gn) achieves an accuracy of 94.39%, whereas training the same task model
from scratch with the full dataset only yields 93.16%. This interesting
finding is aligned with the observation in (Koh and Liang 2017), which
suggests that some training data is harmful to neural network learning.

### Semantic Segmentation

This experiment demonstrates the task-agnostic nature of the proposed method.

Dataset. We evaluate the AL methods on the Cityscapes (Cordts et al. 2016)
dataset, which is large-scale and consists of video sequences of street scenes
from 50 cities. For fair comparison, we only use the standard training and
validation data. Following the common practice in (Sinha, Ebrahimi, and
Darrell 2019; Yu, Koltun, and Funkhouser 2017), we crop the images to a
dimension of $688\times 688$, and set the number of categories to 19.

Model selection. Following the widely used settings, we adopt the dilated
residual network (DRN-D-22) as the task model. We refer readers to (Yu,
Koltun, and Funkhouser 2017) for the architecture details of this network.

Results and Analysis. We employ the mIoU (mean Intersection-over-Union) to
measure the performance of each method. As can be seen in Fig. 2 (right), our
method yields consistently better results than the others for all the
annotation budgets. In fact, semantic segmentation is a pixel-level
classification task, which is more complex than image-level classification.
Moreover, the Cityscapes dataset is highly imbalanced. The superior
performance demonstrates that our method is robust to imbalanced datasets and
suitable for complex tasks. In addition, since our method does not rely on
advanced learning fashions (e.g. adversarial learning), there is no need to
customize the training scheme with task change, making our method task-
agnostic.

### Our Method Tends to Select More Data of Higher Gradient Norm

Here, we investigate whether the proposed method tends to select more
unlabeled samples of higher gradient norm than the AL baselines. Specifically,
for unlabeled pool {$R_{U}$}, we assume that the labels $Y_{U}$ for all
$R_{U}$ are temporarily available and then compute
$||\nabla_{\theta}L(T^{c}(R_{U}))||$ for each $R_{U}$. We sort {$R_{U}$} by
$||\nabla_{\theta}L(T^{c}(R_{U}))||$ in ascending order to form a new set,
namely {$S_{U}$}. Then we use each AL method to select $K$ samples {$X_{K}$}
from the unsorted unlabeled pool {$R_{U}$}. Afterwards, we compute $len(Set)$,
where $Set$ = intersect1d({$S_{U}$}[-$K$:], {$X_{K}$}) (in Numpy notation) and
$len(\cdot)$ yields the length of a set. As shown in Table 1, for each
annotation budget, our method tends to select more unlabeled samples of higher
$||\nabla_{\theta}L(T^{c}(x))||$ than the others. According to the analysis in
Methodology, this observation indicates that the task model trained on our
selected data can yield better performance on test data, which is aligned with
the goal of AL.

Figure 3: How the upper-bound changes after the three approximations in Eq. 4
and Eq. 5 based on the expected-gradnorm scheme (left) and entropy-gradnorm
scheme (right), respectively, evaluated on Cifar10.

### Quantitative evaluation of the Bounds in Eq. 4 and Eq. 5

Here we quantitatively validate the bounds in Eq. 4 and Eq. 5, derived from
the original target in Eq. 3, by presenting two types of evaluations.

Firstly, we evaluate how the samples selected by Eq. 5 are consistent with
that selected by Eq. 3. Note that Eq. 5 is the data selection criterion used
in our algorithm. Specifically, for Eq. 3 we compute the influence of each $x$
by temporarily “observing” its label. At each AL cycle, we acquire the top
2500 samples selected by Eq. 3 and Eq. 5, respectively. Then we check the
proportion of the overlapped samples. As shown in Table 2, more than 90% of
the selected samples are consistent between the original (Eq. 3) and
approximated criterion (Eq. 5). Therefore, Eq. 5 is a reasonable surrogate of
Eq. 3 in AL context. Note that only in this experiment, for the purpose of
evaluation, we assume test data is available in order to compute Eq. 3.

Eq. | Cycle
---|---
0 | 1 | 2 | 3 | 4 | 5 | 6
3 | 2500 | 2500 | 2500 | 2500 | 2500 | 2500 | 2500
5 | 2290 | 2377 | 2396 | 2432 | 2449 | 2438 | 2482
Table 2: How the samples selected by Eq. 5 are consistent with that selected
by Eq. 3, evaluated on Cifar10.

Secondly, we illustrate how the upper-bound changes after each approximation
in Eq. 4 and Eq. 5. Since we actually use either Eq. 6 or Eq. 7 as the loss to
compute gradient norm for unlabeled data, these upper-bounds are computed
based on the proposed Expected-Gradnorm scheme and Entropy-Gradnorm scheme,
respectively. Specifically, after each AL cycle, we compute four terms.

  * •

Target:
$\sum_{j}\nabla_{\theta}L(T^{c+1}(x_{j}))^{\top}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x))$
in line 2 of Eq. 3, which is the exact influence to test loss.

  * •

Approx-1:
$||\sum_{j}\nabla_{\theta}L(T^{c+1}(x_{j}))^{\top}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x))||$
in line 2 of Eq. 4.

  * •

Approx-2: a further approximation in line 4 of Eq. 4:
$||\nabla_{\theta}L(T^{c+1}(x))||\cdot||\sum_{j}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x_{j}))||$
.

  * •

Approx-3:
$||\nabla_{\theta}L(T^{c}(x))||\cdot||\sum_{j}H_{\theta}^{-1}\nabla_{\theta}L(T^{c+1}(x_{j}))||$
in line 2 of Eq. 5.

Note that when using the Expected-Gradnorm, all $L$ in above four terms will
be the expected loss defined in Eq. 6. When using the Entropy-Gradnorm, all
$L$ in the four terms will be the entropy loss defined in Eq. 7. For each
term, we use all unlabeled samples to compute an average value. The results in
Fig. 3 demonstrate that the bounds in the three approximations do not deviate
much from the target in Eq. 3, indicating the reliability of these derived
bounds.

### Better Generalization

Here, we compare the generalization of the task model that is trained on the
data selected by the different AL methods. Specifically, after each AL cycle,
we compute the gap between the training and test accuracy. The smaller the
better for this value, since a larger one indicates that the task model
suffers more from over-fitting. As shown in Table 3, our method yields the
smallest gap, demonstrating its superior generalization ability.

budget (%) | 15 | 20 | 25 | 30 | 35 | 40
---|---|---|---|---|---|---
mc-dropout | 16.14 | 10.25 | 9.47 | 8.77 | 8.24 | 7.35
core-set | 14.59 | 12.73 | 10.88 | 9.95 | 8.92 | 8.31
vaal | 15.01 | 12.24 | 11.08 | 9.66 | 8.57 | 8.08
ll4al | 13.83 | 10.7 | 8.89 | 8.78 | 7.64 | 7.23
sraal | 14.09 | 11.55 | 10.24 | 8.62 | 8.01 | 6.94
exp-gn | 12.74 | 10.04 | 8.06 | 7.05 | 6.09 | 5.66
ent-gn | 13.05 | 9.9 | 7.76 | 6.79 | 6.29 | 5.65
Table 3: Gap (%) between training and test accuracy after each AL cycle,
evaluated on Cifar10. Annotation budget of 10% is ignored since all the
methods use the same randomly selected initial data for the first cycle
training.

## Conclusion

In this paper, we theoretically analyze the connection between data selection
and the test performance of the task model used in active learning. We prove
that selecting unlabeled data of higher gradient norm can reduce the upper-
bound of the test loss. We propose two independent schemes to compute gradient
norm and a universal active learning framework to leverage the schemes. We
conduct extensive experiments on various benchmark datasets and the promising
results validate our theoretical findings and the proposed schemes.

## Acknowledgement

We thank all the reviewers for their valuable comments that help us to improve
this paper.

## References

  * Arora et al. (2018) Arora, S.; Ge, R.; Neyshabur, B.; and Zhang, Y. 2018.  Stronger Generalization Bounds for Deep Nets via A Compression approach.  In _International Conference on Machine Learning_ , 254–263. PMLR.
  * Beluch et al. (2018) Beluch, W. H.; Genewein, T.; Nürnberger, A.; and Köhler, J. M. 2018.  The Power of Ensembles for Active Learning in Image Classification.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 9368–9377.
  * Berthelot et al. (2019) Berthelot, D.; Carlini, N.; Goodfellow, I.; Papernot, N.; Oliver, A.; and Raffel, C. A. 2019.  MixMatch: A Holistic Approach to Semi-Supervised Learning.  _Advances in Neural Information Processing Systems_ , 32.
  * Bilgic and Getoor (2009) Bilgic, M.; and Getoor, L. 2009.  Link-based Active Learning.  In _NIPS Workshop on Analyzing Networks and Learning with Graphs_.
  * Bottou (2010) Bottou, L. 2010.  Large-Scale Machine Learning with Stochastic Gradient Descent.  In _Proceedings of the International Conference on Computational Statistics_ , 177–186.
  * Cai et al. (2017) Cai, W.; Zhang, Y.; Zhang, Y.; Zhou, S.; Wang, W.; Chen, Z.; and Ding, C. 2017.  Active Learning for Classification with Maximum Model Change.  _ACM Transactions on Information Systems_ , 36(2): 1–28.
  * Cai, Zhang, and Zhou (2013) Cai, W.; Zhang, Y.; and Zhou, J. 2013.  Maximizing Expected Model Change for Active Learning in Regression.  In _Proceedings of the International Conference on Data Mining_ , 51–60.
  * Caramalau, Bhattarai, and Kim (2021) Caramalau, R.; Bhattarai, B.; and Kim, T.-K. 2021.  Sequential Graph Convolutional Network for Active Learning.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 9583–9592.
  * Chen et al. (2017) Chen, M.; Dai, W.; Sun, S. Y.; Jonasch, D.; He, C. Y.; Schmid, M. F.; Chiu, W.; and Ludtke, S. J. 2017.  Convolutional Neural Networks for Automated Annotation of Cellular Cryo-Electron Tomograms.  _Nature Methods_ , 14(10): 983.
  * Cordts et al. (2016) Cordts, M.; Omran, M.; Ramos, S.; Rehfeld, T.; Enzweiler, M.; Benenson, R.; Franke, U.; Roth, S.; and Schiele, B. 2016.  The Cityscapes Dataset for Semantic Urban Scene Understanding.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 3213–3223.
  * Deng et al. (2009) Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and Fei-Fei, L. 2009.  Imagenet: A Large-Scale Hierarchical Image Database.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 248–255.
  * Ducoffe and Precioso (2018) Ducoffe, M.; and Precioso, F. 2018.  Adversarial Active Learning for Deep Networks: a Margin Based Approach.  _arXiv Preprint arXiv:1802.09841_.
  * Elhamifar et al. (2013) Elhamifar, E.; Sapiro, G.; Yang, A.; and Shankar Sasrty, S. 2013.  A Convex Optimization Framework for Active Learning.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 209–216.
  * Fei-Fei, Fergus, and Perona (2006) Fei-Fei, L.; Fergus, R.; and Perona, P. 2006.  One-Shot Learning of Object Categories.  _IEEE transactions on pattern analysis and machine intelligence_ , 28(4): 594–611.
  * Gal and Ghahramani (2016) Gal, Y.; and Ghahramani, Z. 2016.  Dropout as A Bayesian Approximation: Representing Model Uncertainty in Deep Learning.  In _Proceedings of the International Conference on Machine Learning_ , 1050–1059.
  * Gal, Islam, and Ghahramani (2017) Gal, Y.; Islam, R.; and Ghahramani, Z. 2017.  Deep Bayesian Active Learning with Image Data.  In _Proceedings of the International Conference on Machine Learning_ , 1183–1192.
  * Goodfellow et al. (2014) Goodfellow, I.; Pouget-Abadie, J.; Mirza, M.; Xu, B.; Warde-Farley, D.; Ozair, S.; Courville, A.; and Bengio, Y. 2014.  Generative Adversarial Nets.  In _Proceedings of the Advances in Neural Information Processing Systems_ , 2672–2680.
  * Gorriz et al. (2017) Gorriz, M.; Carlier, A.; Faure, E.; and Giro-i Nieto, X. 2017.  Cost-Effective Active Learning for Melanoma Segmentation.  In _NIPS Workshop on Machine Learning for Health_.
  * Grandvalet, Bengio et al. (2005) Grandvalet, Y.; Bengio, Y.; et al. 2005.  Semi-Supervised Learning by Entropy Minimization.  _CAP_ , 367: 281–296.
  * Gubins et al. (2019) Gubins, I.; van der Shot, G.; Veltkamp, R.; Foerster, F.; Du, X.; Zeng, X.; et al. 2019.  SHREC’19 Track: Classification in Cryo-Electron Tomograms.  In _Eurographics Workshop on 3D Object Retrieval_.
  * Hasan and Roy-Chowdhury (2015) Hasan, M.; and Roy-Chowdhury, A. K. 2015.  Context Aware Active Learning of Activity Recognition Models.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 4543–4551.
  * Haußmann, Hamprecht, and Kandemir (2019) Haußmann, M.; Hamprecht, F. A.; and Kandemir, M. 2019.  Deep Active Learning with Adaptive Acquisition.  _arXiv Preprint arXiv:1906.11471_.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep Residual Learning for Image Recognition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 770–778.
  * Kingma and Ba (2014) Kingma, D. P.; and Ba, J. 2014.  Adam: A Method for Stochastic Optimization.  _arXiv Preprint arXiv:1412.6980_.
  * Kingma and Welling (2013) Kingma, D. P.; and Welling, M. 2013.  Auto-Encoding Variational Bayes.  _arXiv Preprint arXiv:1312.6114_.
  * Kipf and Welling (2016) Kipf, T. N.; and Welling, M. 2016.  Semi-Supervised Classification with Graph Convolutional Networks.  _arXiv preprint arXiv:1609.02907_.
  * Koh and Liang (2017) Koh, P. W.; and Liang, P. 2017.  Understanding Black-box Predictions via Influence Functions.  In _Proceedings of the International Conference on Machine Learning_ , 1885–1894.
  * Konyushkova, Sznitman, and Fua (2017) Konyushkova, K.; Sznitman, R.; and Fua, P. 2017.  Learning Active Learning from Data.  In _Proceedings of the Advances in Neural Information Processing Systems_ , 4225–4235.
  * Krizhevsky, Hinton et al. (2009) Krizhevsky, A.; Hinton, G.; et al. 2009.  Learning Multiple Layers of Features from Tiny Images.
  * Kuo et al. (2018) Kuo, W.; Häne, C.; Yuh, E.; Mukherjee, P.; and Malik, J. 2018.  Cost-Sensitive Active Learning for Intracranial Hemorrhage Detection.  In _Proceedings of the International Conference on Medical Image Computing and Computer-Assisted Intervention_ , 715–723.
  * Li et al. (2018) Li, H.; Xu, Z.; Taylor, G.; Studer, C.; and Goldstein, T. 2018.  Visualizing the Loss Landscape of Neural Nets.  _Advances in Neural Information Processing Systems_ , 31.
  * Liu et al. (2021) Liu, Z.; Ding, H.; Zhong, H.; Li, W.; Dai, J.; and He, C. 2021.  Influence Selection for Active Learning.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 9274–9283.
  * Loquercio, Segu, and Scaramuzza (2020) Loquercio, A.; Segu, M.; and Scaramuzza, D. 2020.  A General Framework for Uncertainty Estimation in Deep Learning.  _IEEE Robotics and Automation Letters_ , 5(2): 3153–3160.
  * Mac Aodha et al. (2014) Mac Aodha, O.; Campbell, N. D.; Kautz, J.; and Brostow, G. J. 2014.  Hierarchical Subquery Evaluation for Active Learning on A Graph.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 564–571.
  * Mahapatra et al. (2018) Mahapatra, D.; Bozorgtabar, B.; Thiran, J.-P.; and Reyes, M. 2018.  Efficient Active Learning for Image Classification and Segmentation Using A Sample Selection and Conditional Generative Adversarial Network.  In _Proceedings of the International Conference on Medical Image Computing and Computer-Assisted Intervention_ , 580–588.
  * Mayer and Timofte (2020) Mayer, C.; and Timofte, R. 2020.  Adversarial Sampling for Active Learning.  In _Proceedings of the IEEE Winter Conference on Applications of Computer Vision_ , 3071–3079.
  * Netzer et al. (2011) Netzer, Y.; Wang, T.; Coates, A.; Bissacco, A.; Wu, B.; and Ng, A. Y. 2011.  Reading Digits in Natural Images with Unsupervised Feature Learning.  In _NIPS Workshop on Deep Learning and Unsupervised Feature Learning_.
  * Nguyen and Smeulders (2004) Nguyen, H. T.; and Smeulders, A. 2004.  Active Learning Using Pre-Clustering.  In _Proceedings of the International Conference on Machine Learning_ , 623–630.
  * Rister and Rubin (2017) Rister, B.; and Rubin, D. L. 2017.  Piecewise Convexity of Artificial Neural Networks.  _Neural Networks_ , 94: 34–45.
  * Roy and McCallum (2001) Roy, N.; and McCallum, A. 2001.  Toward Optimal Active Learning through Monte Carlo Estimation of Error Reduction.  In _Proceedings of the International Conference on Machine Learning_ , 441–448.
  * Sener and Savarese (2018) Sener, O.; and Savarese, S. 2018.  Active Learning for Convolutional Neural Networks: A Core-Set Approach.  In _International Conference on Learning Representations_.
  * Settles, Craven, and Ray (2007) Settles, B.; Craven, M.; and Ray, S. 2007.  Multiple-Instance Active Learning.  _Advances in Neural Information Processing Systems_ , 20: 1289–1296.
  * Simonyan and Zisserman (2015) Simonyan, K.; and Zisserman, A. 2015.  Very Deep Convolutional Networks for Large-Scale Image Recognition.  In _International Conference on Learning Representations_.
  * Sinha, Ebrahimi, and Darrell (2019) Sinha, S.; Ebrahimi, S.; and Darrell, T. 2019.  Variational Adversarial Active Learning.  In _Proceedings of the IEEE International Conference on Computer Vision_ , 5972–5981.
  * Srinivas and Fleuret (2018) Srinivas, S.; and Fleuret, F. 2018.  Knowledge Transfer with Jacobian Matching.  In _Proceedings of the International Conference on Machine Learning_ , 4723–4731.
  * Yang et al. (2015) Yang, Y.; Ma, Z.; Nie, F.; Chang, X.; and Hauptmann, A. G. 2015.  Multi-Class Active Learning by Uncertainty Sampling with Diversity Maximization.  _International Journal of Computer Vision_ , 113(2): 113–127.
  * Yoo and Kweon (2019) Yoo, D.; and Kweon, I. S. 2019.  Learning Loss for Active Learning.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 93–102.
  * Yu, Koltun, and Funkhouser (2017) Yu, F.; Koltun, V.; and Funkhouser, T. 2017.  Dilated Residual Networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 472–480.
  * Zhang et al. (2020) Zhang, B.; Li, L.; Yang, S.; Wang, S.; Zha, Z.-J.; and Huang, Q. 2020.  State-Relabeling Adversarial Active Learning.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 8756–8765.
  * Zhu and Bento (2017) Zhu, J.-J.; and Bento, J. 2017.  Generative Adversarial Active Learning.  _arXiv Preprint arXiv:1702.07956_.

## Appendix

### A.1 Proof of the Average Gradient Norm Reduction

Here we theoretically explain the rationale of bounding
$\|\nabla_{\theta}L(T^{c+1}(x))\|$ with $\|\nabla_{\theta}L(T^{c}(x))\|$ in
Eq.(5) of the paper. Specifically, we provide a theoretical support that
gradient norm of average loss (or expected loss over data distribution) is
guaranteed to reduce under reasonable assumptions for loss function.

###### Proof.

We firstly define the loss function as $f(w)$ and assume $f$ is twice
continuously differentiable w.r.t. the parameters $w$. For each iteration $t$,
we compute the updated parameters as $w\prime=w-\eta\nabla f(w)$ by performing
gradient descent. Denoting $u=w_{\tau}=w+\tau(w\prime-w)=w-\tau\eta\nabla
f(w)$, we have

$\displaystyle\nabla f(w\prime)$ $\displaystyle=\nabla f(w-\eta\nabla f(w))$
(8) $\displaystyle=\nabla f(w)+\int_{w\to w\prime}\nabla^{2}f(u)du$
$\displaystyle=\nabla f(w)-\eta(\int_{0}^{1}\nabla^{2}f(w_{\tau})d\tau)\nabla
f(w)$ $\displaystyle=\nabla f(w)-\eta H\nabla f(w).$

The following analysis relies on a widely acknowledged assumption: a deep
neural network is locally convex and smooth, which has been discovered by both
theoretical and empirical studies (Rister and Rubin 2017; Arora et al. 2018;
Li et al. 2018). Assuming that $f$ is locally $\mu$-strongly convex and
$L$-smooth at each $w$, we have $\mu I\preceq H=\nabla^{2}f(w)\preceq LI$.
Then, the gradient norm is guaranteed to reduce if we use a small learning
rate $\eta$ satisfying $\eta\leq 2\mu/L^{2}$. The proof is as follows,

$\displaystyle\|\nabla f(w\prime)\|^{2}$ $\displaystyle=\|\nabla
f(w)\|^{2}+\eta(\eta\|H\nabla f(w)\|^{2}$ (9) $\displaystyle\ \ -2\nabla
f(w)^{T}H\nabla f(w))$ $\displaystyle\leq\|\nabla
f(w)\|^{2}+\eta(2\frac{\mu}{L^{2}}\|L^{2}\nabla f(w)\|^{2}$ $\displaystyle\ \
-2\nabla f(w)^{T}\mu I\nabla f(w))$ $\displaystyle=\|\nabla f(w)\|^{2}.$

∎

### A.2 Quantitative Evaluations for Eq. (5)

For quantitative evaluations, in each AL cycle we investigate how many
selected samples have reduced gradient norm in next cycle. We use the proposed
Expected-Gradnorm and Entropy-Gradnorm schemes respectively to compute the
gradient norm for each selected sample. We show the results in Table 4 and
Table 5, respectively. As illustrated, more than 90% (e.g. 2488/2500) of all
the selected samples have reduced gradient norm in all the cycles, suggesting
that our derived bound is reasonable.

Cycle | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---
# | 2488 | 2481 | 2466 | 2439 | 2386 | 2255
Table 4: Number of the selected samples that satisfy $||\nabla_{\theta}L(T^{c+1}(x))||\leq||\nabla_{\theta}L(T^{c}(x))||$. Cycle 0 is ignored since right after cycle 0 model $T^{1}$ is not available yet. All the values are out of 2500, which is the number of the samples selected in each cycle. In this evaluation (on Cifar10), the Expected-Gradnorm scheme is used.  Cycle | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---
# | 2487 | 2477 | 2467 | 2447 | 2388 | 2250
Table 5: Number of the selected samples that satisfy
$||\nabla_{\theta}L(T^{c+1}(x))||\leq||\nabla_{\theta}L(T^{c}(x))||$. Cycle 0
is ignored since right after cycle 0 model $T^{1}$ is not available yet. All
the values are out of 2500, which is the number of the samples selected in
each cycle. In this evaluation (on Cifar10), the Entropy-Gradnorm scheme is
used.

Figure 4: Classification performance of the AL methods on cryo-ET data:
50c-clean (left) and 50c-snr005 (right).

### A.3 Benefits of Selecting Unlabeled Data of Higher Gradient Norm

We present an intuitive explanation of why selecting samples of higher
gradient norm. Without loss of generality, we follow the notations in
Methodology of the paper. Assuming that a removed sample will lead to an
increased test loss, our goal is to select such a sample $x$ which maximizes
$\sum_{j}I_{loss}(x,x_{j})=\frac{1}{n}\sum_{j}\nabla_{\theta}L(f_{\theta}(x_{j}))^{\top}H_{\theta}^{-1}\nabla_{\theta}L(f_{\theta}(x))$.
Denote $\frac{1}{n}\nabla_{\theta}L(f_{\theta}(x_{j}))^{\top}H_{\theta}^{-1}$
by ${c}_{j}$, which is the projected (by $H_{\theta}^{-1}$) gradient of a test
sample $x_{j}$ and approximately independent of an individual training sample
$x$. As for $x$, we express its gradient $g_{x}$ with the direction
$\vec{g}_{x}$ and magnitude $\|g_{x}\|$ as $g_{x}=\|g_{x}\|\vec{g}_{x}$. Then
$\sum_{j}I_{loss}(x,x_{j})$ can be reformulated as

$\begin{split}\sum_{j}\left<\bm{{c}_{j}},\bm{g_{x}}\right>=\bm{\|g_{x}\|}\sum_{j}\left<\bm{{c}_{j}},\bm{\vec{g}_{x}}\right>\enspace.\end{split}$
(10)

While it is obvious that both higher $\|g_{x}\|$ and
$\sum_{j}\left<\bm{{c}_{j}},\bm{\vec{g}_{x}}\right>$ will increase the test
loss, paying attention to $\|g_{x}\|$ can be favorable due to two reasons. (1)
As each ${c}_{j}$ normally has a different direction, it is inefficient to
find the optimal $\vec{g}_{x}$, especially in a high dimensional feature
space. However, solely increasing $\|g_{x}\|$ is easy and has a universal
effect over the space of ${c}_{j}$. (2) When a greedy algorithm is adopted,
which is common in AL methods, selecting data according to the direction may
be sub-optimal in terms of the diversity of a sample set. This is because the
selected samples are prone to have similar directions (i.e. samples with the
same label and similar visual features normally have similar gradient
directions). In contrast, increasing $\|g_{x}\|$ has an implicit effect of
selecting a set of more diverse samples.

### A.4 Limitation of the Expected-Gradnorm Scheme

As discussed in section Expected-Gradnorm Scheme of the paper, this scheme is
not an ideal solution for complex tasks in which assuming label is infeasible,
such as the semantic segmentation task. Here, we further explain this
limitation. In this scheme, for each unlabeled sample, we need to successively
assume each possible label as the ground-truth label of the sample. For
classification problems, there will be $N$ possibilities, where $N$ is the
number of classes in a dataset (e.g. $N=100$ in Cifar100 (Krizhevsky, Hinton
et al. 2009)). In practice, we only need to run a loop of $N$ iterations.
However, for semantic segmentation problems, if the image resolution is
$H\times W$, then there will be $C^{H\times W}$ possibilities when making
label assumptions, where $C$ denotes the number of classes for each pixel. For
example, in the Cityscapes (Cordts et al. 2016) task, we have $C=19$, $H=688$,
and $W=688$, which means for each unlabeled sample we need to run a loop of
$19^{473344}$ iterations to estimate its expected empirical loss, which is
infeasible in practice. Therefore, we propose another scheme in section
Entropy-Gradnorm Scheme of the paper to compute gradient norm without assuming
labels.

### A.5 Cryo-ET Challenges

AL has been demonstrated significantly useful in domain tasks (Kuo et al.
2018; Gorriz et al. 2017; Konyushkova, Sznitman, and Fua 2017), since the
annotation cost in such tasks is extremely high. We explore using AL on cryo-
ET (cryo-Electron Tomography) subtomogram classification (Chen et al. 2017),
which is an important domain task in computational biology. This experiment
also demonstrates the robustness of our method to noise since part of the used
data contains high level of noise.

Datasets. We evaluate our method on two simulated cryo-ET datasets consisting
of subtomograms. The first one, namely 50c-clean, is noise free. The second
one, namely 50c-snr005, contains noise with a SNR (signal-noise-ratio) of
0.05. Each dataset includes 24000 training and 1000 test samples, uniformly
distributed across 50 classes. One can refer to (Gubins et al. 2019) for the
details of the data generation.

Model Selection. Unlike RGB pixel image, each subtomogram is composed of
voxels (e.g. $32\times 32\times 32$). Therefore, we customize ResNet-18 with
3D operations (e.g. 3D convolutions) as the task model. It is employed for all
the compared methods. The VAE helper in vaal (Sinha, Ebrahimi, and Darrell
2019) and sraal (Zhang et al. 2020), and the loss prediction module in ll4al
(Yoo and Kweon 2019) need to be re-designed to fit the cryo-ET data.
Therefore, extra effort is indispensable if using these methods.

Implementation Details. We train the task model for 100 epochs with an initial
learning rate of 0.1, decayed by a factor of 0.1 at the $80^{th}$ epoch. The
SGD optimizer (Bottou 2010) is adopted. The momentum and weight decay rate are
set to 0.9 and $5\times 10^{-4}$, respectively.

Results and Analysis. As illustrated in Fig. 4, our method yields consistently
better results than the baselines, demonstrating its reliability. When there
is high level of noise in the data (i.e. SNR of 0.05), our method still yields
superior performance, demonstrating its robustness to noise.

Method | mc-dropout | core-set | vaal | ll4al | sraal | expected-gradnorm | entropy-gradnorm
---|---|---|---|---|---|---|---
ResNet-50 | 91.23 | 90.12 | 90.97 | 92.32 | 92.68 | 94.1 | 93.16
Table 6: Classification accuracy (%) of ResNet-50 that is trained on the data selected by ResNet-18. 20,000 samples in the training set of Cifar10 are selected by each AL method, respectively.  Class (# of samples) | 0 (1744) | 1 (5099) | 2 (4149) | 3 (2882) | 4 (2523)
---|---|---|---|---|---
Accuracy | 96.85 | 97.51 | 97.06 | 93.82 | 97.23
Class (# of samples) | 5 (2384) | 6 (1977) | 7 (2019) | 8 (1660) | 9 (1595)
Accuracy | 95.22 | 96.81 | 95.84 | 96.39 | 95.17
Table 7: Class-wise classification accuracy (%) of our expected-gradnorm scheme on the test data of SVHN. Class (# of samples) | 0 (1744) | 1 (5099) | 2 (4149) | 3 (2882) | 4 (2523)
---|---|---|---|---|---
Accuracy | 97.19 | 96.96 | 97.42 | 93.34 | 97.42
Class (# of samples) | 5 (2384) | 6 (1977) | 7 (2019) | 8 (1660) | 9 (1595)
Accuracy | 95.85 | 96.46 | 96.04 | 96.02 | 94.55
Table 8: Class-wise classification accuracy (%) of our entropy-gradnorm scheme on the test data of SVHN. Method | mc-dropout | core-set | vaal | ll4al | expected-gradnorm | entropy-gradnorm
---|---|---|---|---|---|---
Cifar10 | 4.38 | 11.13 | 15.21 | 2.51 | 2.33 | 2.29
Cifar100 | 4.49 | 11.25 | 15.83 | 2.18 | 2.42 | 2.36
SVHN | 6.35 | 26.61 | 22.76 | 3.42 | 3.28 | 3.17
Caltech101 | 1.43 | 1.01 | 17.58 | 0.86 | 0.93 | 0.9
Table 9: Training time (in hours) of the AL methods on the four classification
datasets. All the results are measured on a Nvidia RTX 2080Ti GPU with an
Intel(R) Xeon(R) Gold 5117 CPU.

### A.6 Ablation Study

Training Deeper Model with Selected Data. Here, we study whether the data
selected by ResNet-18 (He et al. 2016) in AL context can effectively train a
deeper model from scratch, such as ResNet-50 (He et al. 2016). As shown in
Table 6, ResNet-50 achieves the best test performance when it is trained on
the data selected by our method, further demonstrating that our selected data
can greatly benefit model training.

Class-wise Performance for Imbalanced Data. Here, we investigate whether the
promising performance of our method is dominated by the majority classes in an
imbalanced dataset, such as SVHN (Netzer et al. 2011). We run our method for 7
AL cycles and evaluate the final trained model on the test set of SVHN. As
shown in Table 7 and 8, our method works well on both majority (e.g. class 1
and 2) and minority classes (e.g. class 8 and 9). In Table 8, the highest
accuracy of 97.42% is achieved in both class 2 and 4, whereas the latter
includes much fewer samples than the former. These observations demonstrate
the robustness of our method to imbalanced datasets.

### A.7 Time Efficiency

We compare the training time of our method with that of the baselines in Table
9. Note that in this work, we count the data selection time as part of the
training time. On all the datasets, we run each AL method for 7 cycles (i.e.
annotation budget varies from 10% to 40% with an incremental size of 5%). The
implementation details remain the same as described in section A.8 of this
Appendix. We observe that our method is on par with ll4al (Yoo and Kweon
2019), but much more efficient than the others. This is because in our method
only the task model needs to be trained, whereas in vaal (Sinha, Ebrahimi, and
Darrell 2019) two auxiliary models (i.e. a VAE (Kingma and Welling 2013) and a
discriminator) need to be trained in addition to the task model. In core-set
(Sener and Savarese 2018), one needs to solve the K-center problem iteratively
when selecting unlabeled data, thus time consuming, while in our method one
only needs a feed-forward and a back-propagate step for each unlabeled sample.
The time expense of mc-dropout (Gal and Ghahramani 2016) is also higher than
ours since it needs a large number of feed-forward steps (e.g. 1000 times)
when estimating uncertainty for each unlabeled sample. Note that vaal is much
slower than the others on Caltech101 (Fei-Fei, Fergus, and Perona 2006). This
is because Caltech101 consists of higher resolution images (e.g. $300\times
200$), and hence a smaller batch size of 16 is appropriate for vaal to avoid
CUDA memory issues, whereas the others can use 64 as the batchsize. The memory
issue of vaal is due to the training of the multiple auxiliary models on the
bigger images in Caltech101.

### A.8 Training Details

Instead of selecting data from an entire unlabeled pool {$X_{U}$}, we follow
the practice in (Beluch et al. 2018) to construct a random subset
{$R_{U}$}$\subset${$X_{U}$}, and select data from this subset. Assuming we
select $K$ samples in each AL cycle, generally we have
$len(\\{R_{U}\\})\approx 10\times K$, where $len(\cdot)$ computes the length
of a set. We apply this rule to all the experiments in this work.

Image Classification. Here we present the training specifications of the image
classification experiments in this paper. For the two Cifar and SVHN datasets,
we train the task model for 200 epochs with an initial learning rate of 0.1
and a batch size of 128. The learning rate is decayed by a factor of 0.1 at
the $160^{th}$ epoch. For Caltech101, we train the task model for 50 epochs
and the initial learning rate is set to 0.01, which is decayed by 0.1 at the
$40^{th}$ epoch. The batch size is set to 64. We use the SGD optimizer (Bottou
2010) with a momentum and weight decay rate of 0.9 and $5\times 10^{-4}$,
respectively. For ImageNet, we train the task model for 100 epochs with a
batch size of 64. We use the Adam optimizer (Kingma and Ba 2014) with a
learning rate of 0.1 through the entire training process.

Semantic Segmentation. Here we specify the training settings of the semantic
segmentation experiments in this paper. We train the task model for 50 epochs
with a batch size of 8. The Adam optimizer (Kingma and Ba 2014) is used with a
learning rate of $1\times 10^{-4}$, which will not be decayed during training.

### A.9 More Discussions of Related Work

The authors in (Settles, Craven, and Ray 2007) designed the query by
considering model change, nevertheless, only considering model change is not a
reliable solution for AL, since incorporating an outlier can also result in a
big model change but it will not benefit test performance. Moreover, they did
not explain how model change would impact test performance. On the contrary,
in our work we consider a direct impact on test loss (Eq. (5)). By selecting
training data of higher gradient norm, we show that the upper-bound of test
loss can be lowered. In addition, their scheme is not suitable for complex
tasks in which assuming label is impractical (e.g. segmentation). Therefore,
we propose another scheme to compute gradient norm with entropy (Entropy-
Gradnorm). Note that in our work entropy is not used to sample data. Instead,
we use entropy as a type of loss to compute gradient norm, needed in Eq. (5)
which establishes a direct connection between selected training data and test
loss in AL. Therefore, our main contribution lies in interpreting how selected
training data in AL directly influences test performance (in form of loss). To
our best knowledge, it has never been explored for deep AL by previous
literature, due to the need of model re-training (intractable for deep neural
networks (DNNs)).

Our work differs essentially from (Roy and McCallum 2001) in the following
aspects. (i) _Their method has not been extended to DNNs,_ while we are the
first to develop a scheme to select the most influential training data with
DNNs based on the influence function (Koh and Liang 2017) which formulates the
impact of a training point on the prediction of a test point for DNNs. (ii)
Their method needs considering all possible labels, making it unsuitable for
problems in which assuming label is impractical (e.g. segmentation). We design
the Entropy-Gradnorm scheme that can be easily used for this scenario. (iii)
Their method needs re-training the model for multiple times for data
selection. Although several strategies can be used to speed up the process, it
is still compute-intensive when deployed for DNNs. Instead, we only train the
model once, and take the feed-forward operation during data selection, making
our method more efficient.

At the time of the acceptance of this paper, we notice that there is a
concurrent work (Liu et al. 2021) related to our research. We exploit first-
order derivative as the criterion for data selection, whereas they use both
first-order and second-order derivative (i.e. in Hessian). In their method, it
is not necessary to explicitly compute the inverse of the Hessian, instead the
authors take an approximation based on implicit Hessian-vector products
(HVPs), as suggested in (Koh and Liang 2017). The main difference between the
two methods is: we use gradient magnitude (norm) for data selection, whereas
they use both magnitude and direction. We think only using magnitude may have
an advantage in terms of data diversity. We refer readers to the item (2) in
section A.3 of this Appendix for the discussion.