# Towards Good Practices for Efficiently Annotating Large-Scale Image
Classification Datasets

Yuan-Hong Liao1,2 Amlan Kar1,2,3 Sanja Fidler1,2,3
1 University of Toronto  2 Vector Institute  3 NVIDIA
{andrew, amlan<EMAIL_ADDRESS>
###### Abstract

Data is the engine of modern computer vision, which necessitates collecting
large-scale datasets. This is expensive, and guaranteeing the quality of the
labels is a major challenge. In this paper, we investigate efficient
annotation strategies for collecting multi-class classification labels for a
large collection of images. While methods that exploit learnt models for
labeling exist, a surprisingly prevalent approach is to query humans for a
fixed number of labels per datum and aggregate them, which is expensive.
Building on prior work on online joint probabilistic modeling of human
annotations and machine-generated beliefs, we propose modifications and best
practices aimed at minimizing human labeling effort. Specifically, we make use
of advances in self-supervised learning, view annotation as a semi-supervised
learning problem, identify and mitigate pitfalls and ablate several key design
choices to propose effective guidelines for labeling. Our analysis is done in
a more realistic simulation that involves querying human labelers, which
uncovers issues with evaluation using existing worker simulation methods.
Simulated experiments on a 125k image subset of the ImageNet100 show that it
can be annotated to 80% top-1 accuracy with 0.35 annotations per image on
average, a 2.7x and 6.7x improvement over prior work and manual annotation,
respectively. 111Project: https://fidler-lab.github.io/efficient-annotation-
cookbook

##  1 Introduction

Data, the basic unit of machine learning, has tremendous impact on the success
of learning-based applications. Much of the recent A.I. revolution can be
attributed to the creation of the ImageNet dataset [12], which showed that
image classification with deep learning at scale [25] can result in learning
strong feature extractors that transfer to domains and tasks beyond the
original dataset. Using citations as a proxy, ImageNet has supported at least
40,000 research projects to date. It has been unmatched as a pre-training
dataset to downstream tasks, due to its size, diversity and the quality of
labels. Since its conception, interest in creating large datasets serving
diverse tasks and domains has skyrocketed. Examples include object detection
[48], action-recognition- [10], and 3D reconstruction [32, 6], in domains such
as self-driving [15, 3], and medical imaging [45].

Figure 1: We tackle efficient model-assisted annotation of multi-class labels
at scale. We propose improvements to prior work by incorporating self- and
semi-supervised learning and address associated challenges. Extensive ablation
of common design choices in realistically simulated experiments leads us to
provide best practice recommendations to minimize human annotation effort.

ImageNet and its successors such as OpenImages [26] collected their data using
search engines on the web, followed by human verification of either the search
query term or automatically generated labels. Thus, their labeling is
formulated as a verification task, , does this image really belong to the
class, allowing efficient annotation at scale.

In contrast to ImageNet labeling, in many practical use cases, the data and
labels of interest are often known apriori. This departs from the case above
where arbitrary images could be used by querying keywords online. A common
approach used in practice is to query humans to get a fixed number of labels
per datum and aggregate them [29, 22], presumably because of its simplicity
and reliability. This can be prohibitively expensive and inefficient in human
resource utilization for large datasets, as it assumes equal effort needed per
datum. We build on prior work and investigate integration of modern learning
methods to improve annotation efficiency for multi-class classification at
_scale_.

Recent work [2] explored integrating a learnt classifier into the DS model
[11] in an online setting. Their method allows principled online estimation of
worker skills and label uncertainty. This is used to decide whether another
human should be queried for a datum. We follow this framework, while noting
that directions such as design of user-interfaces [13], computing optimal task
assignment [20] etc. can provide complementary benefits.

Having a pool of workers that can be repeatably queried improves both skill
estimation over time and reduces annotation noise typically found in
_crowdsourcing_ , where workers perform micro-tasks and their presence is
fleeting. Thus, in this work we choose to focus on a _fixed worker
pool_.222This is also a growing trend in the industry, with large companies
using trained labelers over offering micro-tasks.

We first investigate integrating advances in self-supervised learning in our
setting. Next, we view online labeling as a semi-supervised problem and show
consequent efficiency gains. These additions can sometimes lead to negative
feedback cycles, which we identify and remedy. Finally, to encourage adoption
into a practitioner’s toolchain, we ablate several key design choices and
provide a set of good practices and guidelines. We avoid the expense of
running large experiments with human workers by proposing a more realistic
annotator simulation that involves collecting statistics from human
annotators. Prior work [2, 42] collected a large number of human labels for
all experiments, leading to 1) smaller individual experiment scale and 2) a
barrier for further research since these labels are not available and
expensive to collect. We note that [42] also look into efficient multi-class
annotation for large label sets, with a focus on efficient factorization and
learning of worker abilities. This is important and orthogonal to our
exploration into integration of learning methods. In summary, we make the
following contributions:

  * •

Explore the usage of advances in self-supervised learning to efficient
annotation for multi-class classification

  * •

Propose to view the annotation process as a semi-supervised learning problem,
identify resulting instabilities and provide remedies

  * •

Ablate several key design choices for the annotation process providing a set
of best practices and guidelines to facilitate adoption into a practitioner’s
toolchain

  * •

Provide a realistic annotator simulation to conduct such experiments at scale
while avoiding the high cost of involving human annotators for every
experiment

  * •

Release a modular codebase to facilitate adoption and further research into
efficient human-in-the-loop multi-class labeling

We experiment on subsets of varying difficulty from ImageNet [12]. We show 87%
top-1 label accuracy on a 100 class subset of ImageNet, with only 0.98
annotations per image. 80% top-1 label accuracy needed 0.35 annotations per
image, a 2.7x reduction with respect to prior work and a 6.7x reduction over
manual annotation. On the small-scale experiment using human annotations, we
achieve 91% label accuracy with 2x fewer annotations.

##  2 Related Work

###  2.1 Image Annotation in Computer Vision

Large datasets [25, 29] have had a pivotal role in recent advances in computer
vision. [24] make a comprehensive survey of crowdsourcing techniques. As an
example, [37] integrates machines and human-labelers as an MDP and optimize
questions asked to labelers to collect an object detection dataset. LSUN [51]
interleaves worker annotation and training machine models, making a large
high-quality dataset at a low cost. The machine models here are used to
perform confirmation (ExistOrNot question). Instead, we adopt a probabilistic
framework [11] that incorporates machine beliefs with human annotated labels
in a principled manner. We follow the method proposed in [2, 42], who extend
[11] to an online crowdsourcing framework that includes the learner as a
prior. We however, consider the learning problem as a semi-supervised task. It
is also akin to active learning, where the task to optimize for is the quality
of the collected dataset itself.

###  2.2 Semi-supervised Learning

We treat the learning task in online image annotation as a semi-supervised
problem enabling us to incorporate various algorithms. Graph-based semi-
supervised learning [54, 44] leverages the structure in both labeled and
unlabeled data for _transductive_ learning. In neural networks, several
methods aim at smoothing the decision boundaries of the learnt model by
enforcing consistency between image augmentations [49, 34], leveraging pseudo
labels on unlabelled data [40, 50, 38], interpolating between data points
[43].

Recently, self-supervised learning to learn strong representations from
unlabelled image collections has been shown to be highly performant, allowing
learning tasks with limited labels. Multiple pre-text tasks are proposed to
learn representation encoders from unlabelled images, such as predicting patch
position [14], predicting image rotation [16], solving an image jigsaw puzzle
[35], etc. Contrastive learning methods have gained popularity recently [19,
7, 17, 4, 5, 9, 36], where consistency across augmentations of an image and
inconsistency across multiple images is used as a learning signal.

###  2.3 Truth Inference

Crowdsourcing provides low-cost noisy annotations. To infer a true label from
noisy observations, one needs to infer the importance of each annotation. This
problem was discussed 40 years ago in the medical domain with the Dawid-Skene
model [11], optimized with EM. Many variants have since extended the DS model.
GLAD [47] assumes a scenario with heterogeneous image difficulty and worker
reliability. [46] consider each worker as a multidimensional entity with
variables representing competence, expertise and bias. [42] parametrize worker
skills factorized by a taxonomy of target concepts. Instead of using EM, BCC
[23] infers the unobserved variables with bayesian inference. EBCC [28]
extends BCC by considering underlying worker correlations and use rank-1
approximations to scale to large worker cohorts. However, there is still no
dominant truth inference strategy [53]. Work in [2, 42] is the closest to
ours. [2] extend the DS model to an online setting and incorporate a learning
model as a prior. We follow this direction for multiclass classification, view
the problem as a semi-supervised learning problem and rigorously ablate
various design parameters as a means to provide best practice guidelines. [42]
also work on multiclass classification, but focus on worker parametrization,
whereas we focus on improving machine learning models in the procedure.

(a) Commodity

(b) Dog

(c) Insect + Fungus

Figure 2: Example images from datasets (Tab. 3). Commodity dataset consists of
data with coarse-labels, while the Dog and Insect+Fungus datasets are more
fine-grained and difficult to annotate, which is reflected in the lower avg.
worker accuracy.

Dataset | # Images | # Classes | Worker Acc. | Fine-Grain.
---|---|---|---|---
Commodity | 20140 | 16 | 0.76 |
Vertebrate | 23220 | 18 | 0.72 |
Insect + Fungus | 16770 | 13 | 0.65 | ✓
Dog | 22704 | 19 | 0.43 | ✓
Dog + Vertebrate | 45924 | 37 | 0.59 | ✓
ImageNet100 | 125689 | 100 | 0.70 | ✓

Figure 3: ImageNet100 sub-tasks. We separate ImageNet100 into different
difficulty levels.

##  3 Background

In this section, we first formulate our problem and introduce the notation
used (Sec. 3.1). Next, we describe the DS model [11] for probabilistic label
aggregation (Sec. 3.2) and its extension to an online data collection setting
with a learning algorithm in the loop [2] (Sec. 3.3).

###  3.1 Problem Formulation

Given a dataset with $N$ images $\mathcal{X}=\\{x_{i}\\}_{i=1:N}$ and a set of
$K$ target labels, the goal is to infer the corresponding “true” label
$\mathcal{Y}=\\{y_{i}|y_{i}\in[K]\\}_{i=1:N}$ from worker annotated labels
$\mathcal{Z}$. Labels are sampled from $M$ workers
$\mathcal{W}=\\{w_{j}\\}_{j=1:M}$. Worker annotations are noisy, hence each
image is labeled by few workers
$\mathcal{W}_{i}=\\{j|z_{ij}\in\mathcal{Z}\\}$, where $z_{ij}$ is the label
assigned by worker $w_{j}$ on image $x_{i}$. In an online setting (Sec. 3.3),
at each time step $t$, a requester constructs a batch (of size $B$) of Human
Intelligence Tasks (HITs) and assigns them to $B$ workers. Online estimates of
the true label $\mathcal{Y}^{t}$ at each step can be inferred from all
previous annotations $\mathcal{Z}^{1:t}$. The process ends until the requester
is satisfied with the current $\mathcal{Y}^{t}$ or if a time horizon (related
to having a budget) $T$ is reached. We omit $t$ for simplicity.

###  3.2 Dawid-Skene Model

The Dawid-Skene model [11] views the annotation process as jointly inferring
true labels and worker reliabilities. The joint probability of labels
$\mathcal{Y}$, worker annotations $\mathcal{Z}$, and worker reliability
$\mathcal{W}$ (overloaded notation for simplicity) is defined as
$P(\mathcal{Y},\mathcal{Z},\mathcal{W})=\prod_{i\in[N]}p(y_{i})\prod_{j\in[M]}p(w_{j})\prod_{i,j\in\mathcal{W}_{i}}p(z_{ij}|y_{i},w_{j})$,
where $p(y_{i})$ is the prior over $K$ possible labels, $p(w_{j})$ is the
prior reliability of worker $j$, and $p(z_{ij}|y_{i},w_{j})$ models the
likelihood of worker annotations. The worker reliability is usually
represented as a confusion matrix over the label set. In practice, inference
is performed using expectation maximization, where parameters for one image or
worker are optimized at a time,

$\displaystyle\bar{y_{i}}$
$\displaystyle=\arg\max_{y_{i}}p(y_{i})\prod_{j\in\mathcal{W}_{i}}p(z_{ij}|y_{i},\bar{w_{j}})$
(1) $\displaystyle\bar{w_{j}}$
$\displaystyle=\arg\max_{w_{j}}p(w_{j})\prod_{i\in\mathcal{I}_{j}}p(z_{ij}|\bar{y_{i}},w_{j})$
(2)

where $\mathcal{I}_{j}=\\{i|z_{ij}\in Z\\}$ is the set of images annotated by
worker $j$. We refer readers to [53] for a comprehensive explanation and
comparison of other work on truth inference.

###  3.3 Extension to Online Labeling

Lean Crowdsourcing [2] extends the DS model with a learning model in the loop
and implements it in an online setting. The authors replace the label prior
$p(y_{i})$ with predicted probabilities from a learnt model
$p(y_{i}|x_{i},\theta)$. At each time step, after running Eq. 1 and Eq. 2,
they additionally optimize the model parameters $\theta$ from
$\mathcal{D}=\\{x_{i},\bar{y_{i}}|\mathopen{|}\mathcal{W}_{i}\mathclose{|}>0\\}$,
using the current label estimate for images with at least one human
annotation. Their learning model involves a fixed feature extractor $\phi$
with a classifier head. In this work, we use a 2 layer MLP, optimized with
gradient descent.333Previous work [2] used a linear SVM as the classifier
head, but we found that using 2 layer MLP sufficient to achieve comparable
performance with far less time. Its parameters are learnt from scratch at
every step by minimizing a loss function $H$.

$\displaystyle\begin{split}\bar{\theta}=\arg\min_{\theta}\mathbb{E}_{(x_{i},y_{i})\sim\mathcal{D}}H(\bar{y_{i}},p(y_{i}|\phi(x_{i}),\theta))\end{split}$
(3)

To construct $B$ HITs for the next step, they compute the bayesian risk of
$\bar{y_{i}}$ as the expected cost of mis-labeling,

$\displaystyle\begin{split}\mathcal{R}(\bar{y_{i}})&=\sum_{y_{i}=1}^{K}H(\bar{y_{i}},y_{i})p(y_{i}|\mathcal{Z}_{i},\theta)\\\
&=\sum_{y_{i}=1}^{K}H(\bar{y_{i}},y_{i})\frac{p(y_{i}|x_{i},\bar{\theta})\prod_{j\in\mathcal{W}_{i}}p(z_{ij}|y_{i},\bar{w_{j}})}{\sum_{y=1}^{K}p(y|x_{i},\bar{\theta})\prod_{j\in\mathcal{W}_{i}}p(z_{ij}|y,\bar{w_{j}})}\end{split}$
(4)

At every step, they construct $B$ HITs by randomly sampling from a set of
unfinished examples, $\mathcal{U}=\\{x_{i}|\mathcal{R}(\bar{y_{i}})\geq C\\}$
images with risk greater than a threshold. To compare with online labeling
without any learning model, we adopt this sampling scheme and remove the model
learning, referred to as “online DS” in the following sections.

In the following sections, we propose improvements to this online labeling
framework, both in how learnt models are used and in practical design choices.
Our proposed improvements are validated on multiple subsets of varying
difficulty from the ImageNet dataset, using realistically simulated labelers,
both of which we also introduce next.

Figure 4: Results on ImageNet100. We compare our full framework with [2] and
the online DS model on our ImageNet100 dataset (125k images). Our framework
achieves 80% top-1 label accuracy with 0.35 annotation per image, a 2.7x
reduction from [2], and 6.7x compared to the online DS model. Figure 5: Over-
optimistic results from workers with uniform noise. Human workers tend to make
“structured” mistakes. Simulated workers with uniform label noise (blue) can
result in over-optimistic annotation performance. Experiments under workers
with structured noise reflect real-life performance better.

Figure 6: Self-supervised features advance online labeling. We compare
different self-supervised features, showing that improvements in self-
supervised learning translate into improvements in online labeling. For the
Dog, using BYOL [17] helps reach the same accuracy achieved without learning
in the loop (Online DS) with 5x fewer annotations. (Sec. 4.3)

Figure 7: Semi-supervised learning advances online labeling. The learning
problem in online-labeling can be seen as a semi-supervised problem (Sec.
4.4). We compare two semi-supervised techniques: Pseudo-Labeling [27] and
MixMatch [1]. Both improve annotation efficiency on all subsets, particularly
for fine-grained datasets. Surprisingly, Pseudolabels performs slightly better
than a modified version of MixMatch (Sec. 4.4).

##  4 Improving Annotation Efficiency

In this section, we explore modifications to the online-labeling algorithm
proposed in Lean Crowdsourcing [2], focused on improving efficiency of
learning in the loop and improving practical implementation choices. We
present these as proposals followed by their resulting impact on annotation
efficiency and label accuracy.

We first introduce datasets in Sec. 4.1 constructed by taking subsets of
ImageNet [12] which we use for experiments. Experiments and ablations at scale
with human labelers are prohibitively expensive. Hence, we also propose a more
realistic worker simulation in Sec. 4.2.

In Sec. 4.3, we investigate whether self-supervised learning can be used to
replace the feature extractor $\phi$ in the algorithm. Next, in Sec. 4.4 we
cast the learning problem in online-labeling as a semi-supervised problem. We
identify that semi-supervised learning during online-labeling can cause a
negative feedback loop in the algorithm, which we mitigate. In Sec. 4.5, we
ablate several key design choices and provide good practices and guidelines to
encourage future adoption. Finally, in Sec. 4.6, we apply all of our proposed
methods and best practices on our ImageNet100 dataset. These results are shown
in Fig. 4, where we observe that we can achieve 80% top-1 label accuracy with
0.35 annotations per image, which is a 2.7x improvement over [2] and 6.7x
improvement over the online DS model. We achieve 87.4% top-1 label accuracy
with 0.98 annotations per image at convergence, compared to 79.5% and 46.9% in
label accuracy for the competing methods. To validate our proposed approach in
experiments with human annotations, we conduct a small-scale experiment in
Sec. 4.7. We show that our approach achieves 91% top-1 accuracy with 2x fewer
annotations compared to the previous work [2].

###  4.1 ImageNet100 Sandbox

Evaluating and ablating multi-class label annotation efficiency at scale
requires large datasets with diverse and relatively clean labels. We construct
multiple subsets of the ImageNet dataset [12] for our experiments. We use 100
classes sampled from the ImageNet label set [41] and construct smaller sub-
tasks of varying difficulty using the label hierarchy. These tasks range from
20k to 125k images in size. We use the average accuracy of human workers on
these datasets (Sec. 4.2) as a proxy for their difficulty, with the average
human accuracy ranging from 43% to 76%. Tab. 3 details the different sub-
tasks, the number of images, classes, and average human accuracy. Fig. 3 shows
example images from these tasks. For each class, we use 10 images as prototype
images to be provided by the requestor. They ground concepts for human
annotators and also help with learning and model selection.

###  4.2 Simulating Realistic Workers

Prior work [30, 21] simulated workers as confusion matrices. Class confusion
was modeled with symmetric uniform noise, which can result in over-optimistic
performance estimates. Human annotators exhibit _asymmetric_ and _structured_
confusion , classes get confused with each other differently. Fig. 5 compares
the number of annotations per image in simulation using uniform label noise
vs. structured label noise that we crowdsource. We see large gaps between the
two. This arises particularly when using learnt models in the loop, due to
sensitivity to noisy labels coming from structured confusion in the workers.

To efficiently crowdsource a diverse set of worker confusion matrices for
ImageNet100, we split the dataset into 6 disjoint subsets using the ImageNet
label hierarchy and crowdsource annotations (using HITs on Amazon Mechanical
Turk) for each subset. The assumption is that these sets contain most of the
confusion internally and are rarely confused with each other, which we also
verify. We collect 40 annotations per worker, which gives us a noisy estimated
confusion matrix. To simulate a worker, we sample a confusion matrix per
subset and smooth it using an affine combination with the average confusion
matrix.

Through additional HITs, we verify that workers confuse classes across our
subsets with a very low probability (0.03). Therefore, we uniformly spread a
probability mass of 0.03 for class confusion across our subsets. Overall, we
crowdsourced a total of 2680 annotations from 67 workers for these statistics.
In comparison, a single experiment with 20k images with 0.5 annotation each
would need 10k crowdsourced labels. More details are in the Appendix.

###  4.3 Self-supervised Learnt Features

With recent advances in self-supervised learning, it is feasible to learn
strong image feature extractors that rival supervised learning, using pretext
tasks without any labels. This allows learning in-domain feature extractors
for annotation tasks, as opposed to using features pre-trained on ImageNet
[2]. We compare the efficacy of using BYOL [17], SimCLR [4], MoCo [19],
relative location prediction [14] and rotation prediction [16] learnt on full
ImageNet raw images as the feature extractor $\phi$ in Eq. 3. We compare the
performances in online labeling in Fig. 7. Improvements in self-supervised
learning consistently improve efficiency for datasets with both fine and
coarse-grained labels, with up to 5x improvement at similar accuracy compared
to not using a model in the loop. For the rest of the experiments, we use BYOL
[17] as our fixed feature extractor.

###  4.4 Learning in Online-Labeling is a Semi-Supervised Problem

During online-labeling, the goal is to infer true labels for _all_ images in
the dataset, making learning $\theta$ akin to transductive learning, where the
test set is observed and can be used for learning. Thus, it is reasonable to
expect efficiency gains if the dataset’s underlying structure is exploited by
putting the unlabeled data to work, using semi-supervised learning. This has
also been demonstrated recently in the related field of active learning [33].
Eq. 3 accordingly can be modified to,

$\bar{\theta}=\arg\min_{\theta}\mathbb{E}_{(x_{i},y_{i})\sim{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\\{x_{i},\bar{y_{i}}\\}_{1:N}}}H(\bar{y_{i}},p(y_{i}|\phi(x_{i}),\theta))$

Various methods have been proposed in the literature to improve semi-
supervised learning. Since the feature extractor $\phi$ is fixed in our
setting, we adopt the off-the-self semi-supervised learning algorithms that
work directly on a feature space. Specifically, we investigate using
Pseudolabels [27] and MixMatch [1].

Pseudolabeling refers to using the current model belief on unlabeled data as
labels for learning. We use hard pseudo-labels (argmax of belief), and only
retain those labels whose highest class probability falls above a threshold
$\tau$. We use model predictions from the previous time step to generate
pseudo labels and set the threshold $\tau$ to be 0.1.

$\displaystyle\bar{\theta}=\arg\min_{\theta}\mathbb{E}_{(x_{i},y_{i})\sim\\{x_{i},\bar{y_{i}}|p(\bar{y_{i}}|\mathcal{Z}_{i})>1-\tau\\}}H(\bar{y_{i}},p(y_{i}|\phi(x_{i}),\theta))$

MixMatch constructs virtual training examples by mixing the labeled and
unlabeled data using a modified version of MixUp [52]. We modify MixMatch for
our use-case and provide details in the Appendix.

Fig. 7 shows results using PseudoLabels and MixMatch during learning. Semi-
supervised learning consistently improves annotation efficiency across
datasets, with more pronounced improvements shown in coarse-grained datasets.
For Dog, while all methods fail to reach 80% accuracy due to the poor quality
of worker annotations, using PseudoLabels reaches the performance of its
counterpart at convergence with 30% fewer annotations.

Despite its simplicity and other published results, we surprisingly find
Pseudolabeling performs better than MixMatch in our case. We remind the reader
that for online-labeling, the inputs to the semi-supervised learnt models are
the feature vectors $\phi(x)$ instead of raw images. Therefore, various data
augmentation strategies applied at an image level cannot be applied directly,
which we hypothesize to be the reason for the observed trend. In the rest of
the experiments, we use Pseudolabels by default.

Semi-supervised learning during online-labeling can be unstable: Learning in
the loop helps provide a better prior for label-aggregation (Eq. 1) while also
improving worker skill inference (Eq. 2). We find that alternate maximation of
these two objectives can lead to a negative feedback cycle once either of them
converges to a bad solution, often resulting in divergence. It is known that
EM optimization does not always converge to a fixed point, with the likelihood
function of the iterates likely to grow unbounded [31]. Using semi-supervised
learning exacerbates this issue since wrong confident intermediate labels can
become more confident through subsequent time-steps. Fig. 8 shows this
divergence behavior. We mitigate these with simple heuristics related to EM
convergence and model selection through time. During EM, there are two popular
ways to determine convergence: 1) Hard Constraint: stopping if the E-step does
not change across steps, and 2) Soft Constraint: stopping if the average
likelihood of the observation changes minimally across steps.

Hard: $\displaystyle\arg\max p(y_{i}^{t}|z_{i}^{t})=\arg\max
p(y_{i}^{t-1}|z_{i}^{t-1}),\forall i$ (5)
$\displaystyle\begin{split}\text{Soft:
}&\mathopen{|}\frac{\sum_{i\in[N]}\sum_{j\in\mathcal{W}_{i}}p(z_{i}^{t}|y_{i}^{t},w_{j}^{t})}{\mathopen{|}\mathcal{Z}^{t}\mathclose{|}}-\\\
&\frac{\sum_{i\in[N]}\sum_{j\in\mathcal{W}_{i}}p(z_{i}^{t-1}|y_{i}^{t-1},w_{j}^{t-1})}{\mathopen{|}\mathcal{Z}^{t-1}\mathclose{|}}\mathclose{|}\leq\epsilon\end{split}$
(6)

We find that adopting the latter mitigates divergence during EM with
$\epsilon=0.01$. Moreover, we perform model selection across time-steps , do
not replace the model if its validation performance does not improve. We use a
fixed validation set comprised of the prototype images across steps, ablated
in Sec. 4.5. We show the efficacy of applying the proposed heuristics in Fig.
8.

Figure 8: Instability in model parameter learning (gradient descent) and the
label aggregation (EM) during semi-supervised learning can lead to a negative
feedback loop. Using two simple heuristics, global model selection and soft
convergence in EM, avoids this issue. The dashed lines show results beyond our
early stopping criterion (Sec. 4.5.9)

Coyote

Honeycomb

Bottlecap

Blue Heron

Cauliflower

Harmonica

Window Screen

Pirate

(a) Images with no annotations

Boxer

Cocktail Shaker

Kuvasz

Milk Can

Bottlecap

American Lobster

Mexican Hairless

Walking Stick

(b) Images with 3 annotations

Figure 9: Example images with different numbers of annotations under our full
framework on ImageNet100. Images without annotations (left) usually contain
only one centered object. Images with 3 annotations (right) either have
multiple objects (Bottlecap), a small object of interest (Mexican Hairless,
Walking Stick), ambiguous objects (Boxer, Cocktail Shaker), and some not in
their typical state (Kuvasz puppies). We also find simple examples (Milk Can)
with 3 annotations, pointing to room for improvement.

###  4.5 Practical Considerations

We ablate several design choices involved in implementing such an online-
labeling system, leading us to identify guidelines for future practitioners.
We find these design choices can significantly affect efficiency results,
discussed sequentially in the following sections.

####  4.5.1 Generating calibrated model likelihoods

Prior work [2] uses a modified cross-validation approach to generate model
likelihoods. They ensure that the estimated prior
$p(y_{i}|x_{i},\bar{\theta})$ is produced using a model that was not trained
or validated on labels from image $i$. We find that this can underperform when
estimated labels are noisy, which pollutes validation splits and makes
calibration challenging. Instead, we propose to use the clean prototype images
as the validation set. We ablate the importance of having clean validation and
performing cross-validation in Fig. 12. We find that having a clean validation
set is more important than using cross-validation. All our experiments use
temperature calibration [18] with a clean validation set comprised of
prototype images to be provided by the task requestor.

Figure 10: Validation set selection and calibration. We find using a clean
validation set is more important than performing cross-validation.

Figure 11: Early-stop by monitoring the size of the finished set. This avoids
over-sampling for confusing images. Dashed lines represent trajectories using
stopping criterion from [2].

Figure 12: Task Assignment. We adopt a simple greedy task assignment scheme
using learnt worker skills. We show that the learnt skills help assign more
tasks to “important” workers.

####  4.5.2 Model update frequency

How often should one update the model vs. collect human labels? The latency of
model updates vs. collection dictates varies across applications. We find that
for fine-grained datasets, lower update frequencies (higher number of
annotations per update) tend to overshoot in the number of annotations, while
the method is robust to low update frequency on coarse-grained datasets. See
more details in the Appendix.

####  4.5.3 Tuning Hyperparameters

Tuning hyperparameters is difficult when the task is to label data itself. We
split our prototypes (10 per class) into train and validation sets to tune
hyperparameters. Though there are few prototypes, we find that this works
almost as well as tuning with backdoor label access. The requestor can always
add more images to the prototype set from the up-to-date annotations for
improved hyperparameters search.

####  4.5.4 Pre-identifying Worker Skills

We explore to leverage class-dependent and worker-dependent priors. In
reality, the requestor can ask gold standard questions or apply prior
knowledge to design the prior. In our experiment, we find that this is
especially useful for fine-grained datasets. The best explored prior improves
accuracy by 15% in Dog, while in Commodity, the improvement is marginal. See
more details in the Appendix.

####  4.5.5 Task Assignment with Inferred Skills

There are certain particularly hard classes, with only a few workers having
enough expertise to annotate them correctly. We ask whether the learnt skills
can be used to assign tasks better. Prior work on (optimal) task assignment
tackle crowdsourcing settings with vastly different simplifying assumptions
[20, 8], and designing a new task assignment scheme is out of the scope of
this paper. To verify if the learnt worker skills help with task assignment,
we propose a simple greedy algorithm with a cap on the maximum number of
annotations $\alpha$ allowed per worker.

Fig. 12 shows results with task assignment with $\alpha=2000$. The simple task
assignment allows saving 13% of annotations to reach 75% label accuracy. On
the right, we show the distribution between worker importance. Ideally, number
worker annotations would be highly correlated with worker importance. The
results show that, while not perfect, the learnt skills indeed help assign
more tasks to important workers.

####  4.5.6 Number of Workers

We explore how annotation efficiency is affected by the different number of
simulated workers. With the fixed number of annotations, we find that having
more workers hurts the performance due to the fewer observations of each
worker, resulting in poor worker skill estimation. On the contrary, having
fewer workers significantly helps in fine-grained datasets. Reducing the
number of workers from 50 to 10 improves the accuracy by 17% in Dog. See more
details in the Appendix.

####  4.5.7 Pre-Filtering Datasets

We have assumed that the requestor performs perfect filtering before
annotation, , all the images to be annotated belong to the target classes,
which does not always hold. We add an additional “None of These” class and
ablate annotation efficiency in the presence of unfiltered images. We include
different numbers of images from other classes and measure the mean precision
with the number of annotations of the target classes. In Fig.14, we see that
even with 100% more images from irrelevant classes, comparable efficiency can
be retained on a fine-grained dataset.

Figure 13: Dataset contains OOD images. Our method retains efficiency till
around 100% out-of-distribuion images. (Sec. 4.5.7)

Figure 14: Transfer to human workers. Our method increase efficiency w.r.t.
previous work [2] even when using human annotations, achieving 91% accuracy
with 2x reduction. (Sec. 4.7)

####  4.5.8 Risk Threshold

The risk threshold $C$ in online labeling determines how fast the annotation
process converges and the possible final label quality. As expected, having
lower risk threshold results in slower convergence, but improves final label
quality. We use $C=0.1$ for all other experiments in this paper. See more
details in the Appendix.

####  4.5.9 When to Stop Annotating?

A clear criterion to stop annotation is when the unfinished set of images
(images with estimated risk greater than a threshold) is empty [2, 42].
However, we observe that the annotation accuracy usually saturates and then
grows slowly because of a small number of data points that are heavily
confused by the pool of workers used. Therefore we suggest that the requestor
1) stop annotation at this time and separately annotate the small number of
unfinished samples, possibly with expert annotators, and 2) set a maximum
number of annotations per image — we use 3 in our paper. However, how do we
automatically decide when to stop without access to true labels? We find that
performing early stopping on the size of the finished set of images is
sufficient, as shown in Fig. 12. If the finished set size does not increase
from its global maximum value for $\beta$ consecutive steps, we stop
annotation. We adopt this stopping criterion and set $\beta=5$ for all other
experiments in this paper.

###  4.6 Putting it Together on ImageNet100

We finally compare our full framework (Algo 1), with [2] (Lean), an adapted
version with prototypes as validation set and without cross-validation (Lean*)
and the online DS model in Fig. 4. Dashed lines represent results of removing
the stopping criterion mentioned in Sec. 4.5.9. Our framework consistently
provides higher accuracy and stable improvement over time. We achieve nearly
87% top-1 label accuracy on a 100 class subset of ImageNet with only 0.98
annotations per image and 80% top-1 label accuracy with 0.35 annotation per
image, a 2.5x reduction reduction w.r.t. “Lean*”, 2.7 reduction w.r.t “Lean”
and a 6.7x reduction over “Online DS”.

In Fig. 9, we visualize images with 0 and 3 annotations received,
respectively, along with their ground truth ImageNet label. We find that
images that got 0 annotations usually contain only one clear centered object.
Images with 3 annotations sometimes have multiple objects (Bottlecap), or have
a small object (Walking Stick, Mexican Hairless) or an ambiguous object
(Boxer, Cocktail Shaker). We also note that there are simple images that
receive 3 annotations (Milk Can), showing room for improvement.

###  4.7 Transfer to Human Workers

To validate if these good practices apply outside our simulation and in the
real world, we collect 3088 annotations of 1878 images from Insesct+Fungus.
Fig. 14 shows that our method works well when transferring to human workers,
achieveing 91% accuracy with 2x fewer required annotations w.r.t. previous
work [2]. More details in the Appendix.

Input: Unlabeled images $\mathcal{X}=\\{x_{i}\\}_{i=1}^{N}$ and workers
$\mathcal{W}=\\{w_{j}\\}_{j=1}^{M}$

Output: labels $\mathcal{Y}=\\{y_{i}\\}_{i=1}^{N}$

1 Set unfinished set $\mathcal{U}=\\{i\\}_{i=1}^{N}$, finished set
$\mathcal{F}=\emptyset$, $loss^{*}=\inf$, and $\bar{\theta^{*}}$ is randomly
initialized

2$\bar{\theta}\leftarrow\bar{\theta^{*}}$

3$\phi\leftarrow\text{Self-supervised learning on }\mathcal{X}$

4while  _stopping criterion 4.5.9 is not met_ do

5 Construct $B$ HITs from $\mathcal{U}$, sample $B$ workers

6 Obtain annotations $\mathcal{Z}$

7 Initialize worker skills $\bar{\mathcal{W}}$

8 while  _Eq. 6 is not met_ do

9 $\bar{\mathcal{Y}}\leftarrow$ Aggregate $\mathcal{Y}$ by Eq. 1

10 $\bar{\mathcal{W}}\leftarrow$ Maximize $\mathcal{W}$ by Eq.2

11

12 $\bar{\theta}\leftarrow\text{Model Parameter learning by
Eq.~{}\ref{eq:pseudolabel}}$

13 $\bar{\theta}\leftarrow\text{Calibrate with
prototypes~{}\ref{subsubsec:calibration}}$

14 $loss\leftarrow\text{Measure loss on prototypes}$

15 if  _$loss\leq loss^{*}$_ then

16 $\bar{\theta^{*}}\leftarrow\bar{\theta}$; $loss^{*}=loss$

17 else

18 $\bar{\theta}\leftarrow\bar{\theta^{*}}$

19

20 for  _ $i\in\\{i\\}_{1:N}$_ do

21 if $\mathcal{R}(\bar{y_{i}})<C$: $\mathcal{F}\leftarrow\mathcal{F}\cup i$,
$\mathcal{U}\leftarrow\mathcal{U}\setminus i$

22

return _$\mathcal{Y}$_

Algorithm 1 Efficient Annotation

##  5 Discussion and Conclusion

We presented improved online-labeling methods for large multi-class datasets.
In a realistically simulated experiment with 125k images and 100 labels from
ImageNet, we observe a 2.7x reduction in annotations required w.r.t. prior
work to achieve 80% top-1 label accuracy. Our framework goes on to achieve
87.4% top-1 accuracy at 0.98 labels per image. Along with our improvements, we
leave open questions for future research. 1) Our simulation is not perfect and
does not consider individual image difficulty, instead only modeling class
confusion. 2) How does one accelerate labeling beyond semantic classes, such
as classifying viewing angle of a car? 3) ImageNet has a clear label
hierarchy, which can be utilized to achieve orthogonal gains [42] in the
worker skill estimation. 4) Going beyond classification is possible with the
proposed model by appropriately modeling annotation likelihood as demonstrated
in [2]. However, accelerating these with learning in the loop requires
specific attention to detail per task, which is an exciting avenue for future
work. 5) Finally, we discussed annotation at scale, where improvements in
learning help significantly. How can these be translated to small datasets? We
discuss these questions more in the Appendix, and release a codebase to
facilitate further research in these directions.

Acknowledgments: This work was supported by ERA, NSERC, and DARPA XAI. SF
acknowledges the Canada CIFAR AI Chair award at the Vector Institute.

## References

  * [1] 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.
  * [2] Steve Branson, Grant Van Horn, and Pietro Perona.  Lean crowdsourcing: Combining humans and machines in an online system.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
  * [3] Holger Caesar, Varun Bankiti, Alex H. Lang, Sourabh Vora, Venice Erin Liong, Qiang Xu, Anush Krishnan, Yu Pan, Giancarlo Baldan, and Oscar Beijbom.  nuscenes: A multimodal dataset for autonomous driving.  CoRR, abs/1903.11027, 2019.
  * [4] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  arXiv preprint arXiv:2002.05709, 2020.
  * [5] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton.  Big self-supervised models are strong semi-supervised learners.  arXiv preprint arXiv:2006.10029, 2020.
  * [6] Wenzheng Chen, Huan Ling, Jun Gao, Edward Smith, Jaako Lehtinen, Alec Jacobson, and Sanja Fidler.  Learning to predict 3d objects with an interpolation-based differentiable renderer.  In NeurIPS, 2019.
  * [7] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He.  Improved baselines with momentum contrastive learning.  arXiv preprint arXiv:2003.04297, 2020.
  * [8] Xi Chen, Qihang Lin, and Dengyong Zhou.  Statistical decision making for optimal budget allocation in crowd labeling.  The Journal of Machine Learning Research, 16(1):1–46, 2015.
  * [9] Ching-Yao Chuang, Joshua Robinson, Lin Yen-Chen, Antonio Torralba, and Stefanie Jegelka.  Debiased contrastive learning.  arXiv preprint arXiv:2007.00224, 2020.
  * [10] Dima Damen, Hazel Doughty, Giovanni Farinella, Sanja Fidler, Antonino Furnari, Evangelos Kazakos, Davide Moltisanti, Jonathan Munro, Toby Perrett, Will Price, and Michael Wray.  The epic-kitchens dataset: Collection, challenges and baselines.  2020\.
  * [11] Alexander Philip Dawid and Allan M Skene.  Maximum likelihood estimation of observer error-rates using the em algorithm.  Journal of the Royal Statistical Society: Series C (Applied Statistics), 28(1):20–28, 1979.
  * [12] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [13] Jia Deng, Olga Russakovsky, Jonathan Krause, Michael S Bernstein, Alex Berg, and Li Fei-Fei.  Scalable multi-label annotation.  In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pages 3099–3102, 2014.
  * [14] Carl Doersch, Abhinav Gupta, and Alexei A Efros.  Unsupervised visual representation learning by context prediction.  In Proceedings of the IEEE international conference on computer vision, pages 1422–1430, 2015.
  * [15] Andreas Geiger, Philip Lenz, and Raquel Urtasun.  Are we ready for autonomous driving? the kitti vision benchmark suite.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2012.
  * [16] Spyros Gidaris, Praveer Singh, and Nikos Komodakis.  Unsupervised representation learning by predicting image rotations.  arXiv preprint arXiv:1803.07728, 2018.
  * [17] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al.  Bootstrap your own latent: A new approach to self-supervised learning.  arXiv preprint arXiv:2006.07733, 2020.
  * [18] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger.  On calibration of modern neural networks.  arXiv preprint arXiv:1706.04599, 2017.
  * [19] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  arXiv preprint arXiv:1911.05722, 2019.
  * [20] Chien-Ju Ho, Shahin Jabbari, and Jennifer Wortman Vaughan.  Adaptive task assignment for crowdsourced classification.  In International Conference on Machine Learning, pages 534–542, 2013.
  * [21] Gang Hua, Chengjiang Long, Ming Yang, and Yan Gao.  Collaborative active learning of a kernel machine ensemble for recognition.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1209–1216, 2013.
  * [22] Parneet Kaur, Karan Sikka, Weijun Wang, Serge Belongie, and Ajay Divakaran.  Foodx-251: a dataset for fine-grained food classification.  arXiv preprint arXiv:1907.06167, 2019.
  * [23] Hyun-Chul Kim and Zoubin Ghahramani.  Bayesian classifier combination.  In Artificial Intelligence and Statistics, pages 619–627, 2012\.
  * [24] Adriana Kovashka, Olga Russakovsky, Li Fei-Fei, and Kristen Grauman.  Crowdsourcing in computer vision.  arXiv preprint arXiv:1611.02145, 2016.
  * [25] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In Advances in neural information processing systems, pages 1097–1105, 2012.
  * [26] Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, Ivan Krasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Malloci, Tom Duerig, and Vittorio Ferrari.  The open images dataset v4: Unified image classification, object detection, and visual relationship detection at scale.  arXiv:1811.00982, 2018.
  * [27] Dong-Hyun Lee.  Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks.
  * [28] Yuan Li, Benjamin Rubinstein, and Trevor Cohn.  Exploiting worker correlation for label aggregation in crowdsourcing.  In International Conference on Machine Learning, pages 3886–3895, 2019.
  * [29] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In European conference on computer vision, pages 740–755. Springer, 2014.
  * [30] Chengjiang Long and Gang Hua.  Multi-class multi-annotator active learning with robust gaussian process for visual recognition.  In Proceedings of the IEEE International Conference on Computer Vision, pages 2839–2847, 2015.
  * [31] Geoffrey J. McLachlan and T. Krishnan.  The EM algorithm and extensions.  Wiley-Interscience, 2008.
  * [32] Ben Mildenhall, Pratul P. Srinivasan, Matthew Tancik, Jonathan T. Barron, Ravi Ramamoorthi, and Ren Ng.  Nerf: Representing scenes as neural radiance fields for view synthesis.  CoRR, abs/2003.08934, 2020.
  * [33] Sudhanshu Mittal, Maxim Tatarchenko, Özgün Çiçek, and Thomas Brox.  Parting with illusions about deep active learning.  arXiv preprint arXiv:1912.05361, 2019.
  * [34] Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii.  Virtual adversarial training: a regularization method for supervised and semi-supervised learning.  IEEE transactions on pattern analysis and machine intelligence, 41(8):1979–1993, 2018.
  * [35] Mehdi Noroozi and Paolo Favaro.  Unsupervised learning of visual representations by solving jigsaw puzzles.  In European Conference on Computer Vision, pages 69–84. Springer, 2016.
  * [36] Joshua Robinson, Ching-Yao Chuang, Suvrit Sra, and Stefanie Jegelka.  Contrastive learning with hard negative samples.  arXiv preprint arXiv:2010.04592, 2020.
  * [37] Olga Russakovsky, Li-Jia Li, and Li Fei-Fei.  Best of both worlds: Human-machine collaboration for object annotation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
  * [38] Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Han Zhang, and Colin Raffel.  Fixmatch: Simplifying semi-supervised learning with consistency and confidence.  arXiv preprint arXiv:2001.07685, 2020.
  * [39] Yu Sun, Eric Tzeng, Trevor Darrell, and Alexei A Efros.  Unsupervised domain adaptation through self-supervision.  arXiv preprint arXiv:1909.11825, 2019.
  * [40] Antti Tarvainen and Harri Valpola.  Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results.  In Advances in neural information processing systems, pages 1195–1204, 2017.
  * [41] Yonglong Tian, Dilip Krishnan, and Phillip Isola.  Contrastive multiview coding.  arXiv preprint arXiv:1906.05849, 2019.
  * [42] Grant Van Horn, Steve Branson, Scott Loarie, Serge Belongie, and Pietro Perona.  Lean multiclass crowdsourcing.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2714–2723, 2018.
  * [43] Vikas Verma, Alex Lamb, Juho Kannala, Yoshua Bengio, and David Lopez-Paz.  Interpolation consistency training for semi-supervised learning.  arXiv preprint arXiv:1903.03825, 2019.
  * [44] Fei Wang and Changshui Zhang.  Label propagation through linear neighborhoods.  IEEE Transactions on Knowledge and Data Engineering, 20(1):55–67, 2007.
  * [45] Xiaosong Wang, Yifan Peng, Le Lu, Zhiyong Lu, Mohammadhadi Bagheri, and Ronald M Summers.  Chestx-ray8: Hospital-scale chest x-ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 2097–2106, 2017\.
  * [46] Peter Welinder, Steve Branson, Pietro Perona, and Serge J Belongie.  The multidimensional wisdom of crowds.  In Advances in neural information processing systems, pages 2424–2432, 2010.
  * [47] Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier R Movellan, and Paul L Ruvolo.  Whose vote should count more: Optimal integration of labels from labelers of unknown expertise.  In Advances in neural information processing systems, pages 2035–2043, 2009.
  * [48] Yuxin Wu, Alexander Kirillov, Francisco Massa, Wan-Yen Lo, and Ross Girshick.  Detectron2.  https://github.com/facebookresearch/detectron2, 2019.
  * [49] Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoc V Le.  Unsupervised data augmentation for consistency training.  arXiv preprint arXiv:1904.12848, 2019.
  * [50] Qizhe Xie, Minh-Thang Luong, Eduard Hovy, and Quoc V Le.  Self-training with noisy student improves imagenet classification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10687–10698, 2020.
  * [51] Fisher Yu, Ari Seff, Yinda Zhang, Shuran Song, Thomas Funkhouser, and Jianxiong Xiao.  Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop.  arXiv preprint arXiv:1506.03365, 2015.
  * [52] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  arXiv preprint arXiv:1710.09412, 2017.
  * [53] Yudian Zheng, Guoliang Li, Yuanbing Li, Caihua Shan, and Reynold Cheng.  Truth inference in crowdsourcing: Is the problem solved?  10(5):541–552, 2017.
  * [54] Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf.  Learning with local and global consistency.  In Advances in neural information processing systems, pages 321–328, 2004.

##  Appendix A More Ablations

###  A.1 Risk Threshold

The risk threshold $C$ in online annotation determines how fast the annotation
process converges and possibly affects the final label quality. In Fig.15, we
find that using a lower risk threshold stably results in stable label quality
improvement. For larger risk threshold, some incorrectly annotated data can be
considered confident in the early stage, resulting in unstable label quality
improvement. It is somewhat surprising that varying the risk threshold does
not affect the final label quality a lot. We set $C=0.1$ for all other
experiments in this paper.

Figure 15: Ablation of different risk thresholds. Having lower risk threshold
results in slower convergence, and improved final label quality.

###  A.2 Number of Workers

We explore how the number of workers affects annotation efficiency. In Fig.16,
we find that having a fewer number of workers results in better label quality
due to the better worker skills estimation, especially in the fine-grained
dataset where the worker skills estimation matters more.

Figure 16: Ablation of different numbers of workers. Lower number of workers
usually results in greater annotation quality but does not necessarily improve
efficiency.

###  A.3 Model Update Frequency

In reality, we need to consider the frequency of updating the model and
collecting human labels, and the latency of model updates varies across
applications. In Fig.17, we find that having lower update frequencies (higher
number of annotations per update) tends to overshoot in the number of
annotations, while the method is robust to low update frequency.

Figure 17: Ablation of different numbers of labels per step. Models that
collect more labels per step tends to overhoot in number of annotations, while
the final label quality remains similar.

###  A.4 Worker Prior Changes

There are multiple ways to design a better prior. Here, we discuss two
possible ways: A) Considering class identity and B) Considering worker
identity. To consider the class identity, the task designer needs to have a
clear thought of which classes are harder. To consider the worker identity,
the task designer needs to ask several gold standard questions to each worker.
In Fig 18, we ablate the choice of having None, A, B, and A+B with prior
strength 10. For the fine-grained datasets, considering worker identity in the
prior improves a lot since the worker skills can vary significantly. For the
coarse-grained datasets, the improvement is marginal. For all other
experiments in this paper, we adopt None.

In reality, we need to consider the frequency of updating the model and
collecting human labels, and the latency of model updates varies across
applications. In Fig.17, we find that having lower update frequencies (higher
number of annotations per update) tends to overshoot in the number of
annotations, while the method is robust to low update frequency.

Figure 18: Ablation of different priors. For fine-grained dataset, considering
worker identity in the prior improves a lot since the worker skills can vary a
lot. However, having better prior does not necessarily lead to better
performance.

###  A.5 Task Assignment

To verify if the learnt worker skills help with task assignment, we propose a
simple greedy algorithm. For an image sampled for annotation from the
unfinished set $\mathcal{U}$, we use $\bar{y_{i}}$ to find the best possible
workers from the workers pool using the currently estimated worker skill, with
a cap on the maximum number of annotations $\alpha$ allowed per worker.

$\displaystyle
j\leftarrow\arg\max_{j\in\hat{\mathcal{W}}}\mathbb{E}_{y\sim\bar{y_{i}}}\bar{w_{j}}[y,y],\hat{\mathcal{W}}=\\{j|\mathopen{|}\mathcal{Z}_{j}\mathclose{|}\leq\alpha\\}$
(7)

The worker importance is measured by a weighted sum of the worker’s per-class
reliability and the number of annotations assigned to the worker. The weights
are inversely proportional to the model’s per-class accuracy. Ideally, number
worker annotations would be highly correlated with worker importance. In Fig.
19, we show the results on different splits .

Figure 19: Task Assignment. The learnt skills consistently increase the
annotation efficiency.

##  Appendix B Transfer to Human Workers

To validate if the proposed approach can gracefully transfer to human workers,
we further collect 2519 annotations of 1657 images from Insesct+Fungus. We
perform data annotation from 11 workers on Toronto Annotation Suite. The
average annotation accuracy is 0.908. For the experiments, we include 13000
additional images as unlabeled data for semi-supervised learning. Other
details remain the same.

##  Appendix C Data in the Unfinished Set

For all the experiments, we suggest performing early stopping and leave the
rest of the unfinished set $\\{x_{i}|\mathcal{R}(\bar{y_{i}}>C)\\}$ to a
separate process, possibly expert annotators. We show the normalized number of
images in the unfinished set in Fig. 20. For coarse-grained datasets, there
are almost no images left in the unfinished set, while in fine-grained
datasets, Dog, there can be as many as 31% of images left in the unfinished
set.

Figure 20: Normalized number of images in the unfinished set.

###  C.1 Precision of the Finished Set

In the main paper, we show the overall label accuracy. Here, we are interested
in the precision of the finished set. In Fig 21, we measure the precision of
the finished set of different methods and our proposed framework. In the Dog,
the overall accuracy is 75.9%, while the precision of the finished set is
86.4%. The finished set size is 15598, we have 13368 correctly labeled images
out of 22704 images in the finished set.

Figure 21: The precision of the finished set of images.

##  Appendix D Top 5 in ImageNet100

The images in ImageNet can have multiple objects, making top1 accuracy
unreliable. In Fig. 22, we show the comparison in terms of top5 accuracy. Our
proposed approach still performs slightly better than its counterparts. Note
that the top5 accuracy is more error-tolerant, making the improvement gap
smaller.

Figure 22: Top1 and top5 label accuracy on ImageNet100.

##  Appendix E Implementation Details

For each experiment, the learning rate is $\lambda*\text{BatchSize}$, where
$\lambda$ is the learning rate ratio. Regarding the worker prior, we follow
previous work [2] to use a tiered prior system. Ignoring the worker identity,
we use a homogeneous prior we ignore both worker identity and class identity.
If gold standard questions are used, one can use a more sophisticated prior.
We show the ablation of using different prior in Sec. A.4. Each worker
reliability is represented as a confusion matrix over the label set. We assume
a worker annotation $z$ given $y=k$ is a Dirichlet distribution
$\text{Dir}(n_{\beta}\alpha_{k})$, where $n_{\beta}$ is the strength of the
prior and $\alpha_{k}$ is estimated by pooling across all workers and classes.
We set $\alpha_{k}=0.7$ and $n_{\beta}=10$ for all experiments.

We perform hyperparameters search on learning rate ratio, weight decay ratio.
For mixmatch, we perform an additional search over $\mu$, and $\gamma$. In
Tab. 1, we show the search range of these hyperparameters.

Parameter | Search Values
---|---
$\lambda$ | $0.001,0.0005,0.0001,0.00005$
weight decay | $0.001,0.005,0.0005,0.0001$
$\mu$ | $3,5,10$
$\gamma$ | $50,75,100,150$
Table 1: The search range of the hyperparameters.

##  Appendix F Crowdsourcing on AMT

Prior work [21, 30] simulate workers as confusion matrices, and the class
confusions are modeled with symmetric uniform noise, which can result in over-
optimistic performance estimates. Human annotators usually exhibit asymmetric
and structured confusion. We thus crowdsource the confusion matrices from
human workers for the simulation. Fig. 23(a), shows our user interface on
Amazon Mechanical Turk (AMT) for crowdsourcing.

(a) The user interface on AMT for crowdsourcing.

(b) Average confusion matrix of all workers on the ImageNet-100 dataset

###  F.1 Workers Exhibit Structured Noise

We show the crowdsourced confusion matrices for different splits in Fig. 24.
For coarse-grained datasets, Commodity, there is low confusion, while in fine-
grained datasets (Rest), the confusions are strong and correlated to class
identities. In Fig. 23(b), we also show the average confusion matrix of all
the workers on ImageNet100.

Figure 24: The confusion matrix ImageNet100 splits. We can see that the label
confusion is neither unifom nor symmetric.

##  Appendix G Simulating Workers

Here, we show the Python implementation to sample the simulated workers used
in our experiments in Listing 1.

Listing 1: Worker Simulation Code

⬇

import numpy as np

def sample_confusion_matrix(smooth_ratio: float,

noise_level: float,

target_classes: list,

imagenet100: list,

group: list,

group_workers: dict):

cm = []

for k, v in group_workers.items():

v = np.array(v)

global_v = v.sum(0)

idx = self.npr.choice(range(len(v)), 1)

cm.append(smooth_ratio * global_v + v[idx])

cm = sum(cm) # (100, 100) np.ndarray

idx_to_keep = np.array([imagenet100.index(c.lower()) for c in target_classes])

cm = cm[idx_to_keep, :][:, idx_to_keep]

cm = cm / (cm.sum(1, keepdims=True) + 1e-8)

def __which_group(i):

for g_idx, g in enumerate(groups):

if i in g:

return g_idx

# Add uniform noise in off-diagonal terms

for i, c_i in enumerate(target_classes):

c_i_group = __which_group(c_i)

same_group_mask = np.zeros(cm.shape[0]).astype(np.bool)

same_group_mask[i] = True

for j, c_j in enumerate(target_classes):

if i != j and c_i_group == __which_group(c_j):

same_group_mask[j] = True

if same_group_mask.sum() > 0:

density_to_spread = cm[i, same_group_mask].sum()

cm[i, same_group_mask] = cm[i, same_group_mask] * (1 - noise_level)

cm[i, ~same_group_mask] += density_to_spread * (noise_level) \

/ max(sum(~same_group_mask), 1e-8)

return cm

##  Appendix H Semi-Supervised Learning: MixMatch

MixMatch constructs virtual training examples by mixing the labeled, and
unlabeled data using a modified version of MixUp [52]. We modify MixMatch for
online annotation, where the input to the model being learnt is the feature
vector $\phi(x)$. The labeled set is defined by the data points with at least
one worker annotation
$\\{x_{i}|\mathopen{|}\mathcal{W}_{i}\mathclose{|}>0\\}$, and the unlabeled
set is defined by the data points whose largest probability is larger than a
predefined threshold and is not in the labeled set,
$\\{x_{i}|p(\bar{y_{i}}|\mathcal{Z}_{i})>1-\tau\&\mathopen{|}\mathcal{W}_{i}\mathclose{|}=0\\}$.
We use the same threshold as the one used in pseudo labels. The mixmatch loss
consists of cross entropy of the labeled set and the l2 minimization of the
mixed set. The mixed set is constructed by sampling $(x_{1},p_{1})$ from the
labeled set and $(x_{2},p_{2})$ from the unlabeled set and interpolate both
input and output.

$\displaystyle\begin{split}\lambda&\sim\text{Beta}(\alpha,\alpha)\\\
\lambda^{\prime}&=\max(\lambda,1-\lambda)\\\
x^{\prime}&=\lambda^{\prime}x_{1}+(1-\lambda^{\prime})x_{2}\\\
p^{\prime}&=\lambda^{\prime}p_{1}+(1-\lambda^{\prime})p_{2}\\\
\mathcal{S}_{\text{mixed}}&\leftarrow(x^{\prime},p^{\prime})\\\
L&=\mathbb{E}_{(x,y)\sim\\{x_{i},\bar{y_{i}}|\mathopen{|}\mathcal{W}_{i}\mathclose{|}>0\\}}H(\bar{y_{i}},p(y|\phi(x_{i}),\theta))\\\
&+\mu\mathbb{E}_{(x_{i},p_{i})\sim\mathcal{S}_{\text{mixed}}}\left\lVert
p_{i}-p(y|\phi(x_{i}),\theta)\right\rVert^{2}_{2}\end{split}$ (8)

where $\mu$ is the hyperparameters. When the labeled set is small, we usually
sample $\gamma$ times more data from the unlabeled set. In our experiments,
$\mu$ and $\gamma$ are set by performing hyperparameters search mentioned in
the main paper.

##  Appendix I Unexplored Questions

We discuss shortcomings and additional directions for progress in this
section.

Using multiple ML models as workers: Different self-supervised pretext tasks
can provide orthogonal benefits for downstream tasks [39]. Downstream labeling
tasks could go beyond semantic classes, such as annotating the viewing angle
of a car in an image as a classification problem. One could imagine a scenario
where classifiers trained on multiple self-supervised features are treated as
machine “workers”, whose skills for the task at hand are simultaneously
estimated, similar to those for human workers.

Annotating at a small scale / beyond ImageNet: We do not discuss annotating
small-scale data and restrict ourselves to ImageNet in this work. When the
target dataset is small, we expect to be able to finetune self-supervised
features on it to initialize the feature extractor $\phi$.

Leveraging label hierarchies: [42] propose a method to utilize label
hierarchies to efficiently factorize large confusion matrices used to
represent worker skills. We expect to see additional benefits from
incorporating their skill estimation method into our algorithm.

Simulating Image Difficulty: Our proposed simulation does not account for
image-level annotation difficulty, and simulated labels are obtained using a
realistic confusion matrix applied to the ground truth label. Improving our
simulation to consider this is something we would like to explore in future
work.

Going beyond classification: The proposed method can be used to go beyond
classification by changing the likelihood modeling for human annotations. In
this vein, [2] show results on keypoint and bounding box annotation.
Incorporating learning into the loop requires specific attention to detail per
task, and we leave this to future work.

##  Appendix J Class Names in Each Subtask

Tab. 2, shows the classes that comprise each subset in our ImageNet-sandbox
dataset.

Dataset |  Class Names
---|---
Dog |  Komondor, Mexican Hairless, Vizsla, Hungarian Pointer, Toy Terrier, Papillon, Boxer, Rottweiler, English Foxhound, Chihuahua, Shih-Tzu, Chesapeake Bay Retriever, Saluki, Gazelle Hound, Walker Hound, Walker Foxhound, Borzoi, Russian Wolfhound, Standard Poodle, Kuvasz, American Staffordshire Terrier, Staffordshire Terrier, American Pit Bull Terrier, Pit Bull Terrier, Doberman, Doberman Pinscher, Great Dane
Vertebrate |  Meerkat, Mierkat, Hare, Robin, American Robin, Turdus Migratorius, Little Blue Heron, Egretta Caerulea, Tabby, Tabby Cat, Goose, Langur, Wild Boar, Boar, Sus Scrofa, Lorikeet, Garter Snake, Grass Snake, African Hunting Dog, Hyena Dog, Cape Hunting Dog, Lycaon Pictus, Gibbon, Hylobates Lar, Coyote, Prairie Wolf, Brush Wolf, Canis Latrans, Hognose Snake, Puff Adder, Sand Viper, American Coot, Marsh Hen, Mud Hen, Water Hen, Fulica Americana, Green Mamba, Gila Monster, Heloderma Suspectum, Red Fox, Vulpes Vulpes
Insect + Fungus |  Gyromitra, Cauliflower, Fiddler Crab, Dung Beetle, Head Cabbage, American Lobster, Northern Lobster, Maine Lobster, Homarus Americanus, Stinkhorn, Carrion Fungus, Leafhopper, Rock Crab, Cancer Irroratus, Garden Spider, Aranea Diademata, Carbonara, Walking Stick, Walkingstick, Stick Insect, Chocolate Sauce, Chocolate Syrup
Commodity |  Vacuum, Vacuum Cleaner, Computer Keyboard, Keypad, Bottlecap, Milk Can, Iron, Smoothing Iron, Mortarboard, Bonnet, Poke Bonnet, Sarong, Modem, Tub, Vat, Purse, Cocktail Shaker, Rotisserie, Jean, Blue Jean, Denim, Dutch Oven, Football Helmet
ImageNet20 |  Robin, American Robin, Turdus Migratorius, Gila Monster, Heloderma Suspectum, Hognose Snake, Puff Adder, Sand Viper, Garter Snake, Grass Snake, Green Mamba, Garden Spider, Aranea Diademata, Lorikeet, Goose, Rock Crab, Cancer Irroratus, Fiddler Crab, American Lobster, Northern Lobster, Maine Lobster, Homarus Americanus, Little Blue Heron, Egretta Caerulea, American Coot, Marsh Hen, Mud Hen, Water Hen, Fulica Americana, Chihuahua, Shih-Tzu, Papillon, Toy Terrier, Walker Hound, Walker Foxhound, English Foxhound, Borzoi, Russian Wolfhound
Table 2: Class names used in each split.

###  J.1 More Qualitative Results on ImageNet100

In Fig. 25, we show randomly sampled images from the unfinished set. Most of
them are images with a fine-grained label, Fiddler Crab, Great Dane, Borzoi,
etc, and some of them are shot from unusual angles, Chime and Basinet. We also
show additional random examples with zero, one, two and three annotations in
our ImageNet100 experiment in Fig. 26, Fig. 27, Fig. 28 and Fig. 29
respectively.

Fiddler Crab

Walker Hound

Reel

Park Bench

Rocking Chair

Great Dane

American Lobster

Cauliflower

American Staffordshire Terrier

Borzoi

Laptop

Bassinet

Chime

American Lobster

Reel

Chihuahua

American Staffordshire Terrier

Milk Can

Figure 25: Images in the unfinished set on ImageNet100

Kuvasz

Chocolate Sauce

Theater Curtain

Lampshade

Mortarboard

Tabby

Mortarboard

Rock Crab

English Foxhound

Garter Snake

Gasmask

Kuvasz

Head Cabbage

Computer Keyboard

Theater Curtain

Honeycomb

Carbonara

Wing

Figure 26: Images with no annotations on ImageNet100

Boathouse

Head Cabbage

Safety Pin

Iron

Bannister

Tile Roof

Cinema

Modem

Football Helmet

American Staffordshire Terrier

Papillon

Cinema

Gibbon

Sarong

Doberman

Pickup

Bonnet

Gibbon

Figure 27: Images with 1 annotation on ImageNet100

Cinema

Chesapeake Bay Retriever

American Staffordshire Terrier

Ambulance

Great Dane

Pirate

Boathouse

Bannister

Harmonica

Pineapple

Stretcher

Rock Crab

African Hunting Dog

Boxer

Sarong

Rocking Chair

Mixing Bowl

Window Screen

Figure 28: Images with 2 annotations on ImageNet100

Jean

Komondor

Harmonica

Bottlecap

American Staffordshire Terrier

English Foxhound

Vizsla

Football Helmet

Walker Hound

American Coot

American Staffordshire Terrier

American Lobster

Harmonica

Saluki

Pickup

Walker Hound

Moped

Rock Crab

Figure 29: Images with 3 annotations on ImageNet100