Similarity Search for Efficient Active Learning and Search of Rare Concepts
Authors: Cody Coleman
Edward Chou
Sean Culatana
Peter Bailis
Alexander C. Berg
Roshan Sumbaly
Matei Zaharia
I. Zeki Yalniz
Venue:  (2021)
Keywords: active learning
active search

Abstract: Many active learning and search approaches are intractable for industrial settings with billions of unlabeled examples. Existing approaches, such as uncertainty sampling or information density, search globally for the optimal examples to label, scaling linearly or even quadratically with the unlabeled data. However, in practice, data is often heavily skewed; only a small fraction of collected data will be relevant for a given learning task. For example, when identifying rare classes, detecting malicious content, or debugging model performance, positive examples can appear in less than 1% of the data. In this work, we exploit this skew in large training datasets to reduce the number of unlabeled examples considered in each selection round by only looking at the nearest neighbors to the labeled examples. Empirically, we observe that learned representations can effectively cluster unseen concepts, making active learning very effective and substantially reducing the number of viable unlabeled examples. We evaluate several selection strategies in this setting on three large-scale computer vision datasets: ImageNet, OpenImages, and a proprietary dataset of 10 billion images from a large internet company. For rare classes, active learning methods need as little as 0.31% of the labeled data to match the average precision of full supervision. By limiting the selection strategies to the immediate neighbors of the labeled data as candidates for labeling, we process as little as 0.1% of the unlabeled data while achieving similar reductions in labeling costs as the traditional global approach. This process of expanding the candidate pool with the nearest neighbors of the labeled set can be done efficiently and reduces the computational complexity of selection by orders of magnitude. 

Under review as a conference paper at ICLR 2021
SIMILARITY SEARCH FOR EFFICIENT ACTIVE LEARN- ING AND SEARCH OF RARE CONCEPTS
Anonymous authors Paper under double-blind review
ABSTRACT
Many active learning and search approaches are intractable for industrial settings with billions of unlabeled examples. Existing approaches, such as uncertainty sampling or information density, search globally for the optimal examples to la- bel, scaling linearly or even quadratically with the unlabeled data. However, in practice, data is often heavily skewed; only a small fraction of collected data will be relevant for given learning task. For example, when identifying rare classes, detecting malicious content, or debugging model performance, positive examples appear in less than I 1% of the data. In this work, we exploit this skew in large training datasets to reduce the number of unlabeled examples considered in each selection round by only looking the nearest neighbors to the labeled examples. Empirically, we observe that learned representations can effectively cluster un- seen concepts, making active learning very effective and substantially reducing the number of viable unlabeled examples. We evaluate several selection strategies in this setting on three large-scale computer vision datasets: ImageNet, OpenIm- ages, and proprictary dataset of 10 billion images from large internet company. For rare classes, active learning methods need as little as 0.31 % of the labeled data to match the average precision of full supervision. By limiting the selection strate- gies to the immediate neighbors of the labeled data as candidates for labeling, we process as little as 0.1 % of the unlabeled data while achieving similar reductions in labeling costs as the traditional global approach. This process of expanding the candidate pool with the nearest neighbors of the labeled set can be done efficiently and reduces the computational complexity of selection by orders of magnitude.
INTRODUCTION
Large-scale unlabeled datasets contain millions or billions of examples spread over a wide variety
of underlying concepts (Chelba et al.) 2013 Zhu et al. 2015; Zhang et al. 2015 Wan et al. 2019
Russakovsky et al. Kuzneessva et al., 2020: Thomee et al. 2016 Abu et al. 2016
Caesar et al.] 2019 Lee et al. 2019). Often, these massive datasets skew towards a relatively small
number of common concepts, such as cats, dogs, and people (Liu et al. 2019 Zhang et al. 2017]
Wang et al. 2017 Van Horn & Perona 2017). Rare concepts, such as harbor seals, may only appear in small fraction of the data (less than 1%). However, in many settings, performance on these rare concepts critical. For example, harmful or malicious content may comprise small percentage of user-generated content, but it can have an outsize impact on the overall user experience (Wan et al.) 2019.. Similarly, when debugging model behavior for safety-critical applications like autonomous vehicles, or when dealing with representational biases in models, obtaining data that captures rare concepts allows machine learning practitioners combat blind spots model performance (Karpa- thy] 2018 Holstein et al. 2019 Ashmawy et al. 2019 Karpathy 2020). Even simple prediction task like stop sign detection can be challenging given the diversity of real-world data. Stop signs may appear in variety of conditions (c.g., wall held by person), be heavily occluded, or have modifiers (c.g., "Except Right Turns") (Karpathy 20220). While large-scale datasets are core to addressing these issues, finding the relevant examples for these long-tai tasks is challenging.
Active learning and search have the potential to automate the process of identifying these rare, high value data points significantly, but existing methods become intractable at this scale. Specifically, the goal of active learning is to reduce the cost of labeling (Settles) 2012). To this end, the learn- ing algorithm is allowed to choose which data to label based on uncertainty (e.g., the entropy of

---

Under review as a conference paper at ICLR 2021
predicted class probabilities) or other heuristics (Settles
2011 2012 Lewis & Gale 1994). Active
search is a sub-area focused on finding positive examples in skewed distributions Garnett et al. 2012). Because of concentrated focus labeling costs, existing techniques, such uncertaitt sampling (Lewis & Gale 1994) or information density (Settles & Craven 2008), perform multiple selection rounds and iterate over the entire unlabeled data identify the optimal example or batch of examples to label and scale linearly or even quadratically with the size of the unlabeled data. Computational efficiency is becoming an impediment as the size of datasets and model complexities have increased (Amodei & Hernandez] 2018). Recent work has tried to address this problem with sophisticated methods to select larger and more diverse batches of examples in each selection round and reduce the total number of rounds needed to reach the target labeling budget (Sener & Savarese) 2018 Kirsch et al. 2019 Coleman et al. 2020; Pinsler et al. 2019 Diang et al. 2018). Neverthe- less, these approaches still scan over all of the examples to find the optimal examples to label in each round and can be intractable for large-scale unlabeled datasets. For example, running a single inference pass over 10 billion images with ResNet-50 (He et al. 2016) would take 38 exaFLOPs.
In this work, we propose Similarity search for Efficient Active Learning and Search (SEALS) to restrict the candidates considered in each selection round and vastly reduce the computational com- plexity of active learning and search methods. Empirically, we find that learned representations from pre-trained models can effectively cluster many unseen and rare concepts. We exploit this la- tent structure to improve the computational efficiency of active learning and search methods by only considering the nearest neighbors of the currently labeled examples in each selection round. This can be done transparently for many selection strategies making SEALS widely applicable. Finding the nearest neighbors for each labeled example in unlabeled data can be performed efficiently with sublinear retrieval times (Charikar 2002) and sub-second latency on billion-scale datasets (Johnson al. 2017) for approximate approaches. While constructing the index for similarity search requires at least linear pass over the unlabeled data, this computational cost is effectively amortized over many selection rounds or other applications. As a result, our SEALS approach enables selection to scale with the size of the labeled data rather than the size of the unlabeled data, making active learning and scarch tractable on datasets with billions of unlabeled examples.
We empirically evaluated SEALS for both active learning and search on three large scale computer vision datasets: ImageNet (Russakovsky et al. 2015), Openlmages (Kuznetsova et al. 2020), and a proprietary dataset of 10 billion images from a large internet company. We selected 611 concepts spread across these datasets that range in prevalence from 0.203% to 0.002% (1 in 50,000) of the training examples. We evaluated three selection strategies for each concept: max entropy uncertainty sampling (Lewis & Gale 1994). information density (Settles & Craven 2008). and most-likely positive (Warmuth al.] 2002 2003 Jiang et al.) 2018). Across datasets, selection strategies, and concepts, SEALS achieved similar model quality and nearly the same recall of the positive examples as the baseline approaches, while improving the computational complexity by orders of magnitude. On ImageNet with budget of 2,000 binary labels per concept ("0.31 % of the unlabeled data), all baseline and SEALS approaches were within 0.01 mAp of full supervision and recalled over 50% of the positive examples. On OpenImages, SEALS reduced the candidate pool to I 1% of the unlabeled data on average while remaining within 0.013 mAP and 1% recall of the baseline approaches. On the proprietary dataset with 10 billion images. SEALS needed an even smaller fraction of the data, about 0.1 %, to match the baseline, which allowed SEALS to run on a single machine rather than cluster. To the best of our knowledge, no other works have performed active learning at this scale. We also applied SEALS to the NLP spoiler detection dataset Goodreads (Wan) ct al. 2019), where it achieved the same recall as the baseline approaches while only considering less than 1% of the unlabeled data. Together, these results demonstrate that SEALS' improvements to computational efficiency make active learning and search tractable for even billion-scale datasets.
2 RELATED WORK
Active learning's ' iterative retraining combined with the high computational complexity of deep learning models has led to significant work on computational efficiency (Sener & Savarese 2018 Kirsch et al. 2019 Pinsler et al. 2019: Coleman et al. 2020; Yoo & Kweon 2019 Mayer & Tim- ofte 2020; Zhu & Bento (017)) One branch of recent work has focused on selecting large batches of data to minimize the amount of retraining and reduce the number of selection rounds necessary
to reach target budget (Sener & Savarese 2018 Kirsch et al. 2019 Pinsler et al. 2019). These
2

---

Under review as a conference paper at ICLR 2021
approaches introduce novel techniques avoid selecting highly similar or redundant examples and ensure the batches are both informative and diverse. In comparison, our work aims to reduce the number of examples considered in each selection round and complements existing work on batch active learning. Many of these approaches sacrifice computational complexity to ensure diversity, and their selection methods can scale quadratically with the size of the unlaheled data. Combined with our method, these selection methods scale with the size of the labeled data rather than the unlabeled data. Outside of batch active learning, other work has tried to improve computational
efficiency by either using much smaller models as cheap proxies during selection (Yoo & Kweon
2019 Coleman et al.) 2020) or by generating examples (Mayer & Timofte 2020] Zhu Bento, 2017). Using smaller model reduces the amount of computation per example, but unlike our ap- proach, it still requires making multiple passes over the entire unlabeled pool of examples. The
generative approaches (Mayer & Timofte, 2020 Zhu & Bento (017), however, enable sub-linear runtime complexity like our approach. Unfortunately. they struggle to match the label-efficiency of traditional approaches because the quality of the generated examples is highly variable.
Active search a sub-area of active learning that focuses on highly skewed class distributions (Gar- nett al. 2012: Diang et al., 2017: 2018; 2019). Rather than optimizing for model quality, active search aims to find as many examples from the minority class as possible. Prior work has focused on applications such drug discovery, where the dataset sizes are limited, and labeling costs are ex- ceptionally high. Our work similarly focuses on skewed distributions. However, we consider novel active search settings in image and text where the available unlabeled datasets are much larger, and computational efficiency is a significant bottleneck.
k nearest neighbor (k-NN) classifiers are popular models in active learning and search because they do not require an explicit training phase (Joshi et al.] 2012] Wei et al. 2015 Garnett et al. 2012 Jiang et al. 2017 2018). The prediction and score for each unlabeled example can be up- dated immediately after each new batch of labels. In comparison, our SEALS approach uses K--N algorithms for similarity search to create and expand the candidate pool and not as a classifier: This is an important but subtle difference. While prior work avoids expensive training by using k-NN classifiers, these approaches still require evaluating all of the unlabeled examples, which can still be prohibitively expensive on large-scale datasets like the ones we consider here. SEALS targets the selection phase rather than training, presenting a novel and complementary approach.
METHODS
In this section, we outline the problems of active learning (Section 3.1 and search (Section 3.2 formally as well as the selection methods we accelerate using SEALS. For both, we examine the pool-based setting, where all of the unlabeled data is available at once, and examples are selected in batches to improve computational efficiency, as mentioned above. Then in Section [3.3] we describe our SEALS approach and how it further improves computational efficiency in both settings.
3.1 ACTIVE LEARNING
Pool-hased active learning is an iterative process that begins with a large pool of unlabeled data U {xi,.... }. J. Each example is sampled from the space X' with an unknown label from the label space y = {l..... ......,C) C} as (x,, yi). We additionally assume a feature extraction function G2 to embed each x; as a latent variable Gz = z, and that the C concepts are unequally distributed. Specifically. there are one or more valuable rare concepts R C C' that appear in less than 1% of the unlabeled data. For simplicity, we frame this as R binary classification problems solved independently rather than 1 multi-class classification problem with Rt] concepts. Initially, each rare concept has a small number of positive examples and several negative examples that serve as a labeled seed set L. The goal of active learning is to take this seed set and select up to budget of T examples to label that produce a model A," that achieves low error. For each round in pool-based active learning. the most informative examples from a pool of candidate examples P, in batches of size b and labeled, as shown in Algorithm
selected according to the selection strategy
For the baseline approach, P, (x)(x) x U}. meaning that all the unlabeled examples are considered to find the global optimal according to Φ. Between each round, the model AC, is trained on all of the labeled data I2,, allowing the selection process to adapt.
3

---

Under review as a conference paper at ICLR 2021
In this paper, we considered max entropy (MaxEnt) uncertainty sampling (Lewis & Gale 1994
@Maxtiml (z)
Σ
P(ilz A,) log P(olz; A,)
and information density (ID) (Settles & Craven 2008
3
ΦID(2) = (Z) x
Σ EDEP,
sim Zp))
Prr
where sim(z, Zp) is the cosine similarity of the embedded examples and 3 = 1. Note that for bi- nary classification, max entropy equivalent to least confidence and margin sampling, which also popular criteria for uncertainty sampling (Settles) 2009). While max entropy uncertainty sam- pling only requires a linear pass over the unlabeled data, ID scales quadratically with [U] because it weights each example's informativeness by its similarity to all other examples. To improve com- putational performance, the average similarity score for each example can be eached after the first selection round, so subsequent rounds scale linearly. This optimization only works when G, is fixed and would not apply to dynamic similarity calculations like those Sener & Savarese (0118).
We explored the greedy k-centers approach from Sener & Savarese (018) but found that it never outperformed random sampling for our experimental setup. Unlike MaxEnt and ID, k-centers does not consider the predicted labels. It tries to achieve high coverage over the entire candidate pool, of which rare concepts make up small fraction by definition, making it ineffective for our setting.
Algorithm BASELINE APPROACH
Algorithm 2 SEALS APPROACH
Input: unlabeled data U. labeled seed set L feature extractor G,, selection strategy
Input: unlabeled data U. labeled seed set
L feature extractor Gz, selection strategy
((-), batch size b, labeling budget T
x(-), batch size b, labeling budget T, k- nearest neighbors implementation (..-))
1: C. (xG.(x), y) (x E [.)
1: C. ((G2(x), y) (x.v) L2)
2: P, = (x)
x U and (x, -) $ L.}
2: P. = (a.))e,,NNZ.
3: repeat
3: repeat
4:
A, (C,)
4:
A, = train(C,)
5:
for 1 to b do
5:
for b do
6:
z" arg max (zz)
6:
z" = arg max d(z)
7:
C, = L, U ((z", (abell"bel(()) label(x (x*)))
7:
C. L, U ((2 label(x ())
8:
P. P. \zz}
P. (P, (Z)
9:
end for
9:
end for
until | = T
10: until [C,|
3.2 ACTIVE SEARCH
Active search closely related to active learning, so much of the formalism from Section 3.1 carries The critical difference is that rather than selecting examples label that minimize error, the goal of active search is to maximize the number of examples from the target concept r, expressed with the natural utility function u(I.,) -(xx,)) 1 r)). As result, different selection strategies favored, but the overall algorithm is the same Algorithm [
In this paper, we consider an additional selection strategy to target the active search setting, most-
likely positive (MLP) (Warmuth et al. 2002 2003 Jiang et al. 2018):
(MLP (z) = P(r [f]]z;44 A,)
Because active learning and search are similar, we evaluate all the selection criteria from Sections 3.1 and 3.2 in terms of both the error the model achieves and the number of positive examples.
4

---

Under review as a conference paper at ICLR 2021
3.3 SIMILARITY SEARCH FOR EFFICIENT ACTIVE LEARNING AND SEARCH (SEALS)
In this work, we propose SEALS to accelerate the inner loop of active learning and search by restricting the candidate pool of unlabeled examples. To apply SEALS, we use an efficient method for similarity search of the embedded examples (Charikar 2002; Johnson et al. 2017) and make two modifications to the baseline approach, as shown Algorithm
1. The candidate pool P. is restricted to the nearest neighbors of the labeled examples. 2. After every example is selected, we find its le nearest neighbors and update Pp..
Computational savings. Restricting the candidate pool P. to the k nearest neighbors of the labeled examples means we only apply the selection strategy to at most l- examples. This can be done transparently for many selection strategies making it applicable to a wide range of active learning and search methods, even beyond the ones considered here. Finding the it nearest neighbors for each newly labeled example adds overhead, but this can be calculated efficiently with sublinear retrieval times (Charikar] (2002) and sub-second latency billion-scale datasets (Johnson et al. (017) for approximate approaches. As result, the computational complexity of each selection round scales with the size of the labeled dataset rather than the unlabeled dataset. Excluding the retrieval times for the k nearest neighbors, the computational savings from SEALS are directly proportional to the pool size reduction for @Maxtaa and ΦMLP. which lower bounded by |U]/k|[r] For Φw, the average similarity score for each example only needs to be computed once when the example is first selected. This caching means the first round scales quadratically with [U] and subsequent rounds scale linearly for the baseline approach. With SEALS, each selection round scales according to O((1 + P..I) because the similarity scores are calculated as examples are selected rather than all at once. The resulting computational savings of SEALS varies with the labeling budget I as the upfront cost of the baseline amortizes. Nevertheless, for large-scale datasets with millions or billions of examples, performing that first quadratic round for the baseline is prohibitively expensive.
Index construction. Generating the embeddings and indexing the data can be expensive and slow, requiring least a linear pass over the unlabeled data. However, this cost is effectively amortized over many selection rounds, concepts, or other applications. Similarity search is a critical workload for information retrieval and powers many applications, including recommendation. Increasingly, embeddings from deep learning models are being used (Babenko et al. (0144] Babenko & Lempitsky 2016 Johnson et al., 2017). As result, the embeddings and index can be generated once using a generic model trained in a weak-supervision or self-supervision fashion and reused, making our approach just one of many applications using the index. Alternatively. if the data has already been passed through a predictive system (for example, to tag or classify uploaded images), the embedding could be captured and indexed at inference to avoid additional costs.
4 RESULTS
We applied SEALS to three selection strategics and performed active learning and search on three datasets: ImageNet (Russakovsky et al. 2015). OpenImages (Kuznetsova et al.) 2020), and a propri- etary dataset of 10 billion images. Section details the experimental setup for each dataset and the inputs used for both the baseline approach (Algorithm I and our proposed method, SEALS (Algo- rithm (2). Sections 4.2 and present the empirical results for active learning and search. Section 4.4 explores the structure of the concepts through the nearest neighbor graphs and embeddings.
Across selection strategies, datasets, and concepts, SEALS using ResNet-50 (He et al. 2016) em- beddings performed similarly to the baseline while only considering a fraction of the unlabeled data U in the candidate pool for each concept P,. For MLP and MaxEnt, the smaller candidate pool from SEALS sped-up the selection runtime by over 180x on OpenImages. This allowed us to run active learning and search efficiently on an industrial scale dataset with 10 billion images. The improve- ments were even larger for information density. On ImageNet, SEALS dropped the time for the first selection round from over 75 minutes to 1.5 seconds, over a 3000 improvement. On OpenIm- ages, the baseline for information density ran for over 24 hours without completing a single round, while SEALS took less than 3 minutes perform 19 rounds. We observed similar results with self- supervised embeddings using SimCLR (Chen et al. 2020) for ImageNet (Appendix (A.3) and using SentenceBERT (Reimers & Gurevych 2019) for Goodreads spoiler detection (Appendix A.8
5

---

Under review as a conference paper at ICLR 2021
Table Summary of datasets
Number of Concepts (R)
Embedding
Number of Examples (())
Fraction Positive (2
Model (G.)
Nct-ot-50 (He ct
2016
ImageNet Russakkvsky al.
2015
450
639.906
0.114.0.203%
(500cclasses
OpenImages Kuznetsova et al. 2020
153
Nes-et-50 (He
2
6,816,296
0.002-0.088%
(1000claasee)
Nes-50 (He et al.
2016
1OB images (proprictary)
8
10,094,719,767
clasSs))
4.1 EXPERIMENTAL SETUP
Across all datasets and selection strategies, we followed the same general procedure for both active learning and search. Because we are interested in rare concepts, we kept the number of initial pos- itive examples small. We evaluated three settings, with 5, 20, and 50 positives, but only included the results with the smallest size in this section. The others are shown in Appendix [A.]] For each setting, negative examples were randomly selected at ratio of 19 negative examples to every posi- tive example to form the seed set L. The slightly higher number of negatives in the initial seed set improved average precision selection round was the same as the size of the initial seed set. For the seed set of 5 positive and 95 negative examples shown below, b was 100, and the labeling budget T was 2,000 examples.
the validation set across all three datasets. The batch size b for each
As the binary classifier for each concept A,, we used logistic regression trained on the embedded examples. For active learning, we calculated average precision on the test data for each binary concept classifier after each selection round. For active search, we count the number of positive examples labeled so far. We take the mean average precision (mAP) and number of positives across concepts, run each experiment 5 times, and report the mean and standard deviation.
For similarity search, we used locality-sensitive hashing (LSH) (Charikar 2002) implemented in Faiss (Johnson et al. (017)) with Euclidean distance for all datasets aside from the 10 billion images dataset. This simplified our implementation, so the index could be created quickly and independently for each concept and configuration, allowing experiments to run in parallel trivially. However, re- trieval times for this approach were not as fast as Johnson et al. (201)) and made up a larger part of the overall active learning loop. In practice, the search index can be heavily optimized and tuned for the specific data distribution, leading to computational savings closer to the improvements described in Section 3.3 and differences in the "Selection" portion of the runtimes in Table 2
We split the data, selected concepts, and created embeddings as detailed below and summarized in Table T Note that our approach does not constrain the choice of Gz, which allows for many network architectures. As representations continue to improve with new self-supervision, generative, or transfer learning techniques, SEALS is still applicable and performance will also likely improve.
ImageNet (Russakovsky et al., 2015) has 1.28 million training images spread over 1000 classes. To simulate rare concepts, split the data in half, using 500 classes to train the feature extractor G= and treating the other 500 classes as unseen concepts. For G2, we used ResNet-50 but added a bottleneck layer before the final output to reduce the dimension of the embeddings to 256. We kept all of the other training hyperparameters the same as in He et al. (0166). We extracted features from the bottleneck layer and applied 12 normalization. In total, the 500 unseen concepts had 639, ,066 training examples that served as the unlabeled pool. We used 50 concepts for validation, leaving the remaining 450 concepts for our final experiments. The number of examples for each concept varied slightly, ranging from 0. 14-0..%0%3% of | The 50,000 validation images were used as the test set.
OpenImages (Kuznetsova et al., 2020p has 7.34 million images with human-verified labels spread over 19,958 classes, taken as an unbiased sample from Flickr. However, only 6.82 million images were still available in the training set at the time of writing. As a feature extractor, we took ResNet- 50 pre-trained on all of ImageNet and used the 1 normalized output from the bottleneck layer. As rare concepts, we randomly selected 200 classes with between 100 to 6,817 positive training examples. We reviewed the selected classes and removed 47 classes that overlapped with ImageNet. The remaining 153 classes appeared in 0.002-0.088% of the data. We used the same hyperparameters as the ImageNet experiments and the OpenImages predefined test split for evaluation.

---

Under review as a conference paper at ICLR 2021
Full Supervision
Random-All Random-SEALL
MIP-AII
MaxEnt-All MaxEnt-SEALS
ID-AII
MLP-SEALS
ID-SEALS
Recall (96)
MAP
Pool Size
10
1000
1630
2000
Number of Labels
Number Labels
Number Labels
(a) ImageNet ((0]=639,90))
2.0
Recall (96)
mAP
Pool Size
2.0
0.5
10
02
2003
1300
2000
500
1000
500
1003
1300
2000
Number of Labels
Number Labels
Number of Labels
(b) OpenImages (U|]=,,11,,99)
Figure 1: Active learning and search on ImageNet (top) and OpenImages (bottom). Across datasets and strategies, SEALS with 100 performed similarly to the baseline approach in terms both the error the model achieved for active learning (left) and the recall of positive examples for active search (right), while only considering a fraction of the data U (middle).
10 billion (10B) images from large internet company were used test SEALS' scalability, For the feature extractor, we used the same pre-trained ResNet-50 model as the Openlmages experiments. We also selected additional classes from OpenImages as rare concepts: rat, sushi, bowling, beach, hawk, cupcake, and crowd. This allowed us to use the predefined test split from OpenImages for evaluation. Unlike the other datasets, we hired annotators to label images as they were selected and used a proprictary index to achieve low latency retrieval times to capture real-world setting.
4.2 ACTIVE LEARNING
Across datasets and selection strategies, SEALS performed similarly to the baseline approaches that considered all of the unlabeled data in the candidate pool, as shown in Figures aadd] 2
ImageNet. With a labeling budget of 2,000 examples per concept ("0.31% of [U[, all baseline and SEALS approaches (A: 100) were within 0.01 mAP of the 0.699 mAP achieved with full supervi- sion. In contrast, random sampling (Random-All) only achieved 0.436 mAP. MLP-AII, MaxEnt-All and ID>AII achieved mAPs of 0.693, 0.695, and 0.688, respectively, while the SEALS equivalents were all within 0.001 mAP at 0.692, 0.695, and 0.688 respectively and considered less than 7% of the unlabeled data. The resulting selection runtime for MLP-SEALS and MaxEnt-SEALS dropped by over 25x, leading to 3.6x speed-up overall (Table 2h. The speed-up was even larger for ID- SEALS, ranging from about 45 2,00 labels to 3000 200 labels. Even at per-class level, the results were highly correlated with Pearson correlation coefficients of 0.9998 or more (Figure 10a in the Appendix). The reduced skew from the nearest neighbor expansion of the initial seed set only accounted for small part of the improvement, as Random-SE. -EALS achieved an mAp of 0.498.
OpenImages. The gap between the baseline approaches and SEAL. widened slightly for OpenIm- ages. At 2,000 labels per concept ("0.029% of [T], MaxEnt-All and MLP-AII achieved 0.399 and 0.398 mAP, respectively, while MaxEnt-SEALS and MLP-SEALS both achieved 0.386 mAP and considered less than 1% of the data. This sped-up the selection time by over 180x and the total time by over 3 Increasing l: to 1,000 significantly narrowed this gap for MaaxEnt-SEALL. and MLP- SEALS, improving mAP to 0.395, as shown in the Appendix (Figure 7 Moreover, SEALS made ID tractable on OpenImages by reducing the candidate pool to 1% of the unlabeled data, whereas ID-All ran for over 24 hours in wall-clock time without completing single round (Table

---

Under review as a conference paper at ICLR 2021
Table Wall clock runtimes for varying selection strategies on ImageNet and OpenImages. The last 3 columns break the total time down into 1) the time to apply the selection strategy to the candidate pool, 2) the time to find the & nearest neighbors (k-NN) for the newly labeled examples, and 3) the time to train logistic regression on the currently labeled examples. Despite using simple LSH index for similarity search, SEALS substantially improved runtimes across datasets and strategies.
Time Breakdown (seconds)
Recall
Size
Dataset
Budget T
Strategy
mAP/AUC
(%)
(%)
(seconds)
Selection
A-NN
Training
ImageNet
2,000
MaxEnt-All
0.695
57.2
100.0
43.23
44.65
0.39
MaxEnt-SEAne SEALS
0.695
56.9
12.49
1.73
10.27
0.50
MLP-AII
0.693
74.5
100.0
43.32
42.75
0.57
MLP-SEALS
0.692
74.2
12.03
1.48
9.94
0.63
ID-AII
0,688
50.8
100.0
4654.59
4653.55
1.05
ID-SEALS
0.688
50.9
6.9
104.57
94.22
9.76
0.60
1,000
AII
26.3
4620.04
4619.78
ID-SEALS
0.654
27.8
4.7
36.66
31.95
4.56
0.17
500
ID-III
0.580
12.5
100.0
4602.64
4602.57
0.09
ID-SRALS
0.601
13.5
3.2
9.75
7.75
1.95
0.05
200
ID-III
0.500
4.7
100.0
4588.76
4588.73
0.04
SEALS
4.8
1.03
OpenImages
2,000
MaxEnt-All
0.399
35.0
100.0
295.20
294.78
0.42
MaxEat-SEan SEALS
0.38G
35.1
80.61
1.56
78.63
0.43
MLP-AN All
0.398
35.1
100.0
285.27
284.88
0.40
MLP-SEALS
0.386
35.1
82.18
1.48
80,27
0.44
ID
100.0
24 hours 129.79
>- hours
ID-SEALS
0.359
29.3
0.9
48.98
80.40
0.41
10B images. Despite the unprecedented scale and limited pool size, SEALS performed similarly the baseline approaches that scanned all 10 billion images. At a budget of 1,500 labels, MaxEnt- SEALS (k=10K) achieved similar mAP to the baseline (0.504 vs. 0.508 mAP), while considering only about 0. % of the data. This reduction allowed MaxEnt-SEALe to finish selection rounds in seconds on a single 24-core machine, while MaxEnt-All took minutes on cluster with tens of thousands cores. MLP-SEALS performed poorly at this scale because, for any image, there are likely many redundant near-duplicate examples that provide little additional value.
Openimages Full Superition
Random
MavEn: SEALS (s=10,000)
Images (I=10.000)
Openimages
Images NaxEmn-
Images MaxEmn (x=1.000)
Images SEALS (k=1.000)
Pool Size (M)
Positives
1000
mAP
0.3
02
800
000
1000
1200
1400
200
460
3000
1200
200 800
800
1000
1400
Number of Labels
Number of Labels
Number of Labels
Figure 2: Active learning and search on proprietary dataset of 10 billion images. Across strategies, SEALS with & 10, 000 performed similarly to the baseline approach in terms of both the error the model achieved for active learning (left) and the recall of positive examples for active search (right), while only considering fraction of the data U (middle).
4.3 ACTIVE SEARCH
As shown in Figures and 2 SEALS recalled nearly the same number of positive examples as the baseline approaches did for all of the considered concepts, datasets, and selection strategies.
ImageNet. Unsurprisingly. MLP-AII and MLP-SEALS significantly outperformed all of the other selection strategies for active search. At 2,000 labeled examples per concept, both approaches re- called over 74% of the positive examples for each concept at 74.5% and 74.2% recall, respectively. MaxEnt-All and MaxEnt-SEALS had a similar gap of 0.3%, labeling 57.2% and 56.99 56.9% posi- tive examples, while ID-All and ID-SEALS were even closer with gap of only 0.1% (50.8% 50.9%). Nearly all the gains recall are due to the selection strategies rather than the reduced skew in the initial seed, as Random- SEALS increased the recall by less than 1. 1.0% over Random-All.
8

---

Under review as a conference paper at ICLR 2021
1,0
1.0
10
10
0.5
100
CDF
0.5
100
1000
1000
0.0
0.0
20
40
60
80
100
20
40
60
80
100
Size of Largest Component (%)
Size of Largest Component (%)
1.0
1.0
CDE
0.5
100
1000
0.5
10
100
1000
0.0
0.0
Average Shortest Path in Largest Component
Average Shortest Path in Largest Component
(a) ImageNet
(h) OpenImages
Figure 3: Measurements of the latent structure of unseen concepts in ImageNet (left) and OpenIm- ages (right). Across datasets, the k-nearest neighbor graph of unseen concepts was well connected, forming large connected components (top) for even moderate values of k. The components were tightly packed, leading to short paths between examples (bottom).
OpenImages. The gap between the baseline approaches and SEALS was even closer on OpenIm- ages despite considering much smaller fraction of the overall unlabeled pool. MIP-AII, MLP- SEALS, MaxEnt-SEALS, and MaxEnt-All were all within 0.1 % with "35% recall at 2,000 labels per concept. ID-SEALS had a recall of 29.3% but scaled nearly as well as the linear approaches.
10B images. SEALS performed as well the baseline approach despite considering less than 0.1% of the data and collected orders magnitude more positive examples than random sampling.
4.4 LATENT STRUCTURE OF UNSEEN CONCEPTS
To better understand why and when SEALS works, analyzed the nearest neighbor graph across concepts and values of k. Figure shows the cumulative distribution functions (CDF) for the largest connected component within each concept and the average shortest paths between examples in that component. The 10B images dataset was excluded because only a few thousand examples were labeled. The largest connected component gives a sense of how much of the concept SEALS can reach, while the average shortest path serves as proxy for how long it will take to explore.
In general, SEALS performed better for concepts that formed larger connected components and had shorter paths between examples (Figure 11 in the Appendix). For most concepts in ImageNet, the largest connected component contained the majority of examples, and the paths between examples were very short. These tight clusters explain why so few examples were needed to learn accurate binary concept classifiers, as shown in Section 4.2] and why SEALS recovered "74% of positive examples on average while only labeling "0.31% of the data. If we constructed the candidate pool by randomly selecting examples, mAP and recall would drop for all strategies (Appendix(A.3) concepts were so rare that the randomly chosen examples were not close to the decision boundary. For OpenImages, rare concepts were more fragmented, but each component was fairly tight, leading to short paths between examples. On per-class level, concepts like "monster truck" and "black- berry" performed much better than generic concepts like "electric blue" and "meal" that were more scattered (Appendix And A.7p. This fragmentation partly explains the gap between SEALS and the baselines in Section 4.2) and why increasing & closed it. However, even for small values of k there were significant gains over random sampling, as shown in Figures 6 and in the Appendix.
The
5 CONCLUSION
In this work, we introduced Similarity search for Efficient Active Learning and Search (SEALS) as simple approach to accelerate active learning and search that can be applied to a wide range of existing algorithms. SEALS restricted the candidate pool for labeling to the nearest neighbors the currently labeled set instead of scanning over all of the unlabeled data. Across three large datasets, three selection strategies, and 611 concepts, we found that SEALS achieved similar model quality and recall of positive examples while improving computational efficiency by orders of magnitude.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sami Abu-El-Haija, Nisarg Kothari, Joonseok Lee, Paul Natsev, George Toderici, Balakrishnan
Varadarajan, and Sudheendra Vijaynarasimmhn. Youtube-8m 8m: A large-scale video classification benchmark, 2016.
Dario Amodei and Danny Hernandez. Ai and compute, May 2018. URL https://blog openai cww.com/aaao..o... ai and codd-compute/
Khalid Ashmawy, Shouheng Yi, and Alex Chao. Searchable ground truth: Query- ing uncommon scenarios in self-driving car development. https:: uber. com/
searchable- bearchable-ggooud---rtt-------e-
10 2019.
Artem Babenko and Victor Lempitsky. Efficient indexing of billion-scale datasets of deep descrip- tors. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2055-2063, 2016.
Artem Babenko, Anton Slesarev, Alexandr Chigorin, and Victor Lempitsky. Neural codes for image retrieval. In European conference computer vision, pp. 584-599. Springer, 2014.
Holger Caesar, Varun Bankiti, Alex H. Lang, Sourabh Vora, Venice Erin Liong, Qiang Xu, Anush Krishnan, Yu Pan, Giancarlo Baldan, and Oscar Beijbom. nuscenes: multimodal dataset for autonomous driving. arXiv preprint arXiv:99033 2019.
Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 380-388, 2002.
Ciprian Chelba, Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp Koehn, and Tony Robinson. One billion word benchmark for measuring progress in statistical language modeling. Technical report, Google, 2013. URL httt:://axxi.vt.t org abs 1122. 3005
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint arXiv:2002.05709 2020.
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang. Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. In International Conference on Learning Representations, 2020. URL https://
Gpentevieew.nt//oorrn:: wwt.:eeooooommm000gg000000000000
Roman Garnett, Yamuna Krishnamurthy, Xuehan Xiong, Jeff Schneider, and Richard Mann. Bayesian optimal active search and surveying. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML' 12, pp. 843-850, Madison, WI, USA, 2012. Omnipress. ISBN 7781450312851
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of Conference on Computer Vision and Pattern Recognition, 2016.
Kenneth Holstein, Jennifer Wortman Vaughan, Hal Daumé III, Miro Dudik, and Hanna Wallach. Improving fairness machine learning systems: What do industry practitioners need? In Pro- ceedings of the 2019 CHI Conference Human Factors in Computing Systems, pp. 1-16, 2019.
Shali Jiang, Gustavo Malkomes, Geoff Converse, Alyssa Shofner, Benjamin Moseley, and Roman Garnett. Efficient nonmyopic active search. In Doina Precup and Yee Whye Teh (eds.), Proceed- ings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1714-1723, International Convention Centre, Sydney, Australia, URL http::/ppoceeedinnggn/ http://wwww........./so/om//oo/a 2ttpe//s///////aa11........
06-11 Aug 2017. PMLR.
html
Shali Jiang, Gustavo Malkomes, Matthew Abbott. Benjamin Moseley, and Roman Gareett. Efficient nonmyopic batch active search. In Advances in Neural Information Processing Systems, pp. 1099- 1109, 2018.
10

---

Under review as a conference paper at ICLR 2021
Shali Jiang, Roman Garnett, and Benjamin Moseley. Cost effective active search. In H. Wallach,
H. Larochelle, A. Beygelzimer, d'Alché-Bur Fox, and R. Gamett (eds.), Advances Neural Information Processing Systems 32, pp. 4880 4889. Curran Associates, Inc., 2019. URL http:
//papers ni ps. cc wtt.cc/ppppeee.. http:/pperr////1 8833 cwsttoostttooooo -f vie search. pdf
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. arXiv
preprint arXiv:
2017.
Ajay Joshi, Fatih Porikli, and Nikolaos Papanikolopoulos. Coverage optimized active learning for k-nn classifiers. In 2012 IEEE International Conference on Robotics and Automation, pp. 5353-5356 IEEE, 2012.
Andrej Karpathy, Train ai 2018 building the software 2.0 stack, 2018. URL https://vimeo: com/ 272696002
Andrej Karpathy. Ai for full-self driving, 2020. URL /tLLtttps///oouuubb////////
Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acqui- sition for deep bayesian active learning. Advances in Neural Information Processing Systems, pp. 7024-7035, 2019.
Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, Ivan Krasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Malloci, Alexander Kolesnikov, Tom Duerig, and Vittorio Ferrari. The open images dataset v4: Unified image classification, object detection, and visual relationship detection scale. IJCV, 2020.
Kevin Lee, Vijay Rao, and William Christic Arnold. Accelerating facebook's in- frastructure with application-specific hardware. https://engineering fbb com/ data-center- weweeeeeteeeeeeeeee engeeeennineeee hwtpeiinggaaaaaaeeeeeeeeee /at///acceeeeinnnooe infrastructuree 2019.
David D Lewis and William A Gale. A sequential algorithm for training text classifiers. In Pro- ceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, pp. 3-12. Springer- Vernigg New York, Inc., 1994.
Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang. Boqing Gong, and Stella Yu. Large-scale taile recognition in an open world. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2537-2546, 2019.
Christoph Mayer and Radu Timofte. Adversarial sampling for active learning. In The IEEE Winter Conference on Applications of Computer Vision, pp. 3071-3079, 2020.
Robert Pinsler, Jonathan Gordon, Eric Nalisnick, and José Miguel Hernández-Lobato. Bayesian batch active learning as sparse subset approximation. In Advances in Neural Information Pro- cessing Systems, pp.
2019.
Nils Reimers and Iryna Gurevych. Sentence-BERY Sentence embeddings using Siamese BERT- networks. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP- IJCNLP), pp. 3982 3992, Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10. (0.18653/1/DD19-14110 URL WRRLhttps:/ /ttp:///wwww.... wwww acl wwtp://wwwbrg//thhoogoggoooo D19- 1410
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 1 115(3)211-252 2015.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018. URL https:// openreview www.ww.wweeeeeeemee foottt/fouumm dd Tuk-RV
Burr Settles. Active learning literature survey. Technical report, University of Meacoosin-Maadiee Department of Computer Sciences, 2009.
11

---

Under review as a conference paper at ICLR 2021
Burr Settles. From theories to queries: Active learning in practice. In Isabelle Guyon, Gavin Cawley, Gideon Dror, Vincent Lemaire, and Alexander Statnikov (eds.), Active Learning and Experimental Design workshop In conjunction with AISTATS 2010, volume 16 of Proceedings of Machine Learning Research, pp. 1-18, Sardinia, Italy, 16 May 2011. PMLR. URL http: //proceed ngs mlr www.sr..r..e.... v stte/ssttslsssssee.ee html
Burr Settles, Active learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, (1):1-114, 2012.
Burr Settles and Mark Craven. An analysis of active learning strategies for sequence labeling tasks. In Proceedings of the Conference on Empirical Methods in Natural Language Process- ing, EMNLP '08, pp. 1070-1079, USA, 2008. Association for Computational Linguistics.
Bart Thomee, David A. Shamma, Gerald Friedland, Benjamin Elizalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li. Yfcc100m. Communications of the ACM, 59(2)664-3, Jan 2016. ISSN 1557-7317. doi: 10.1145/2812802. URL http: dttp/xxxxcii....ooooooooooo..o.. org/ 10. 1145/ 2812802
Grant Van Horn and Pietro Perona. The devil is in the tails: Fine-gre line-grained classification in the wild. arXiv preprint arXiv: 1709001000004500 2017.
Mengting Wan, Rishabh Misra, Ndapa Nakashole, and Julian McAuley, Fine- sine-grained spoiler detection from large-scale review corpora. In Anna Korhonen, David R. Traum, and Lluís Mårquez (eds.), Proceedings of the 57th Conference of the Association for Computational Lin- guistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Pupers, pp. 2605- 2610. Association for Computational Linguistics. 2019. doi: 10. 00.18653/11/11--2445 URL http://///ao.ooo011.111133333
1248
Yu-Xiong Wang, Deva Ramanan, and Martial Hebert. Learning to model the tail. In Advances in Neural Information Processing Systems, pp. 7029-7039, 2017.
Manfred K Warmuth, Jun Liao, Gunnar Rätsch, Michael Mathieson, Santosh Putta, and Christian Lemmen. Active learning with support vector machines in the drug discovery process. Journal of chemical information and computer sciences, 43(2):667-673 2003.
Manfred KK Warmuth, Gunnar Rätsch, Michael Mathieson, Jun Liao, and Christian Lemmen. Ac- tive learning in the drug discovery process. In Advances in Neural information processing systems, pp. 1449-1456, 2002.
Kai Wei, Rishabh lyer, and Jeff Bilmes. Submodularity in data subset selection and active learning- In International Conference on Machine Learning, pp. 1954-1963, 2015.
Donggeun Yoo and In So Kweon. Learning loss for active learning. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 93-102, 2019.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text clas- sification. In Advances in neural information processing systems, pp. 649-657) 2015.
Xiao Zhang, Zhiyuan Fang. Yandong Wen, Zhifeng Li, and Yu Qiao. Range loss for deep face recognition with long-tailed training data. In Proceedings of the IEEE International Conference on Computer Vision, pp. 5409-5418, 2017.
Jia-Jie Zhu and José Bento. arXiv: 077.0070...77..... 2017.
Generative adversarial active learning.
arXiv preprint
Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov. Raquel Urtasun, Antonio Torralba, and Sanja Fidler. Aligning books and movies: Towards story-like visual explanations by watching movies and reading books. In Proceedings of the IEEE international conference on computer vision, pp. 19-27, 2015.
12

---

Under review as a conference paper at ICLR 2021
A
APPENDIX
A.1
NUMBER OF INITIAL POSITIVES
Full Supervision
Random-Al Random-SEALS
MIP-AII MLP-SEALS
MaxEnt-AIl MaxEnt-SEALE
ID-AII ID-SEALS
0.70
Pool Size (%)
Recall (96)
80
mAP
0.60
88
80
0.35
2000
4000
0000
5003
10000
2000
4002
5003
5000
10000
2000
4000
5000
2000
20000
Number of Labels
Number of Labels
Number of Labels
ImageNet 6339999,)))
Pool Size (%)
Recall (96)
mAP
80
0.2
2000
4020
0020
8000
10000
2000
4000
0000
8000
10000
2000
4000
0000
8000
10000
Number of Labels
Number of Labels
Number of Labels
(b) OpenImages (UU]=6816,,29)
Figure 4: Active learning and search with 20 positive seed examples and a labeling budget of 10,000 examples ImageNet (top) and Openlmages (bottom). Across datasets and strategies, SEALS with & = 100 performs similarly to the baseline approach in terms of both the error the model achieves for active learning (left) and the recall of positive examples for active search (right), while only considering fraction of the unlabeled data U (middle).
Full Supervision
Random-All
MaxEnt-AA
ID-AII ID-SEALS
Random-SEALS
ML P-SEALS
SEXEnt-SEALS
Pool Size (96)
Recall (96)
mAP
01.05
0.55
5003
Number Labels
Number Labels
Number Labels
(a) ImageNet ((U|=639,96)
055
Recall (96)
mAP
2.4
Pool Size
0.5
2000
8000
10000
2003
4300
6003
10000
1003
8003
10000
Number of Labels
Number of Labels
Number Labels
(b) OpenImages (U|=6,816,296)
Figure 5: Active learning and search with 50 positive seed examples and labeling budget of 10,000 examples on ImageNet (top) and OpenImages (bottom). Across datasets and strategies, SEALS with &o 100 performs similarly to the baseline approach in terms of both the error the model achieves for active learning (left) and the recall of positive examples for active search (right), while only considering fraction of the unlabeled data U (middle).
13

---

Under review as a conference paper at ICLR 2021
A.2
IMPACT OF ON SEALS
Full Supervision
Random
MLP
Max
ID
All
SEALS (k-10)
SEALS (k=100)
SEALS (k=1000)
MaxEnt
man
mAP
mAp
Number of Labels
Number of Labels
Number Labels
Number Labels
Random
MLP
MaxEnt
ID
Recall (9)
Recall (9)
Recall (9))
Recall (9)
B
Number of Labels
Number of Labels
Number of Labels
Number of Labels
Random
MaxEnt
Pool Size (9))
Pool Size (96)
Pool Size (96
Number Labels
Number
Number
THE
Number Labels
2000
Figure 6: Impact of increasing on ImageNet ([U|=639,9000) 906). Larger values & help to close the gap between SEALS and the baseline approach that considers all of the unlabeled data for both active learning (top) and active search (middle). However, increasing h also increases the candidate pool size (bottom), presenting trade-off between labeling efficiency and computational efficiency.
Full Supervision
Random
MLP
MaxEnt
ID
All
SEALS (c=10)
..... SEALS (k=100)
SEALS (k=1000)
Random
MLP
MaxEnt
MAP
MAP
Number of Labels
Number of Labels
Number Labels
Number of Labels
Random
MLP
MaxEnt
(90)
Reooo (9)
(16)
Re call (96
120
Labels
2000
200
Number
200
2000
500 200
Labels
200
200
220
2000
2000
Random
MLP
MaxEnt
Size (60
Pool Size (96)
(N)
Pool Size (90)
Number of Labels
Number of Labels
Number of Labels
Number of Labels
Figure 7: Impact of increasing i OpenImages (16,6,, Larger values of le help to
close the gap between SEALS and the baseline approach that considers all of the unlabeled data for both active learning (top) and active search (middle). However, increasing k also increases the candidate pool size (bottom), presenting a trade-off between labeling efficiency and computational efficiency.
14

---

Under review as a conference paper at ICLR 2021
A.3
SEER-SUPERV EMBEDDINGS (SIMCLR) ON IMAGENET
Full Supervision
Random-All Random-SEALS
MaxEnt-All
MLP-SEALS
MaxEnt-SEALS
ID-SEALS
Pool Size (%)
Recall (%)
0.55
0.50
0.45
1000
Number Labels
Number of Labels
Number of Labels
Figure 8: Active learning and search ImageNet with self-supervised embeddings from Sim- CLR (Chen et al., 2020). Because the supf--upe training for the embeddings did not use the labels, results average across all 1,000 classes and [U|=1,281,161 To compensate for the larger unlabeled pool, we extended the total labeling budget to 4,000 compared to the 2,000 used in Fig- I Across strategies, SEALS with k 100 substantially outperforms random sampling in terms of both the mAP the model achieves for active learning (left) and the recall of positive examples for active search (right), while only considering fraction of the data U (middle). For active learning, the gap between the baseline and SEALS approaches is slightly larger than in Figure which is likely due the larger pool size and increased average shortest paths (see Figure
1.00
10
0.75
0.75
1000
0.50
0.50
10
1000
0.00
0.00
20
40
60
100
10
12
Size of Largest Component
Average Shortest Path Largest Component
Figure 9: Measurements of the latent structure of unseen concepts in ImageNet with self-supervised embeddings from SimCLR (Chen et al. 2020). In comparison to Figure 3al the k-nearest neighbor graph for unseen concepts was still well connected, forming large connected components (left) for even moderate values of k, but the average shortest path between examples was slightly longer (right). The increased path length is not too surprising considering the fully supervised model still outperformed the linear evaluation of the self-supervised embeddings in Chen et al. al. (2020).
15

---

Under review as a conference paper at ICLR 2021
A.4
PER CLASS AP CORRELATION
1.0
1.0
0.8
0.8
AP (*-SEALS)
AP (*-SEALS)
0.6
0.6
0.4
0.4
MaxEnt (p=0.99
0.2
MLP (p=1.000)
0.2
MaxEnt (p=0.986)
(o-0.998)
MLP (p=0.987)
0.0
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
AP (*-All)
AP (*-All)
(a) ImageNet
(b) OpenImages
Figure 10: The per-class APs of SEALS highly correlated to the baseline approaches A*-All) for active learning on ImageNet (right) and Openlmages (left). On Openlmages with A: = 100 and budget of 2,000 labels, the Pearson's 's correlation (p) between the baseline and SEALS for the average precision of individual classes was 0.986 for MaxEnt and 0.987 for MLP. The least-squares fit had slope 0.99 and y-intercept -0.01. On ImageNet, the correlations were even higher.
1.0
1.0
0.8
0.8
AP (*-SEALS)
AP (*-SEALS)
0.6
0.6
0.4
0.4
MaxEnt (p=0.609)
MaxEnt (p- (p--9.719)
0.2
MLP (p=0.605)
0.2
MLP (p--0.718)
ID (p= 0p666)
ID (p=-0.736)
0.0
90
95
100
0.0
2.0
2.5
3.0
3.5
4.0
Average Shortest Path Largest Component
Size of the Largest Component (%)
(a) ImageNet
1.0
1.0
0.8
AP (*.SEALS)
(M-SEALS)
0.6
0.6
0.4
0.4
0.2
MaxEnt (p59.5
0.2
MaxEnt (p- 0.461)
MLP (p- 0)554)
MLP (p--0.458)
0.0
25
50
75
100
0.0
2
4
8
10
Size of the Largest Component (%)
Average Shortest Path In Largest Component
(b) OpenImages
SEALS achieved higher APs for classes that formed larger connected components (left) and had shorter paths between examples (right) in ImageNet (top) and OpenImages (bottom).
Figure 11:
16

---

Under review as a conference paper at ICLR 2021
A.5
COMPARISON TO POOL OF RANDOMLY SELECTED EXAMPLES
Full Supervision
MaxEnt-All
MaxEnt-SEALS
MaxEnt-RandPool (1%)
RRdEnt-RandPool (5%)
MaxEnn-RanddPol (10%)
0.7
Pool Size (%)
Recall (%)
MAP
0.6
500
I030
1500
2000
500
1000
1500
2000
500
1000
1500
2000
Number of Labels
Number of Labels
Number of Labels
(a) ImageNet (1U|=639,,06)
0.5
Pool Size (%)
Recall (%)
MAP
1.0
0.2
5.0
1500
2000
500
1000
2000
500
1000
1500
Number Labels
Number of Labels
Number of Labels
(b) Openlmages (1866,81,)
Figure 12: MaxEnt-SEALS (k 100) versus MaxEnt applied to candidate pool of randomly selected examples (RandPool). Because the concepts we considered were so rare, as often the case in practice, randomly chosen examples much larger pool is required to match SEALS. On ImageNet (top), MaxEnt-SEAAL. outperformed MaxEit-RandPool in terms of both the error the model achieves for active learning (left) and the recall of positive examples for active search (right) even with a pool containing 10% of the data (middle). On Openimages (bottom), HaxEnt-SEALS for active learning and failed to achieve similar recall even with 10x the data.
unlikely to be close to the decision boundary, and
needed at least 5x much data match
17

---

Under review as a conference paper at ICLR 2021
Full Supervision
MLP-AII
MLP-SEALS
MLP-RandPool (1%)
MLP-RandPool (5%)
MLP-RandPool (10%)
Poal Size (%)
Recall (%)
50
mAP
0.6
0.5
0.4
2000
300
1000
15:00
1000
Number of Labels
Number of Labels
Number of Labels
ImageNet (3U|=639,906)
Pool Size (%)
Recall (%)
mAP
0.4
0.3
500
10:0
1500
2000
500
1000
15:00
2000
500
1000
1500
2000
Number of Labels
Number of Labels
Number of Labels
(b) Openlmages (U|]=,,816.29)
Figure 13: MLP-SEALS = 100) versus MLP applied to a candidate pool randomly selected examples (RandPool). Because the concepts considered were rare, is often the case in practice, randomly chosen examples are unlikely to be close to the decision boundary, and a much larger pool is required to match SEALS. On ImageNet (top), MLP-SEALS outperformed MLP- RandPool in terms of both the error the model achieves for active learning (left) and the recall of positive examples for active search (right) even with pool containing 10% of the data (middle). On Openimages (bottom),
needed at least 5x as much data to match active learning and failed to achieve similar recall even with 10x the data.
for
18

---

Under review as a conference paper at ICLR 2021
Full Supervision
ID-All
ID-SEALS
ID-RandPool (1%)
ID-RandPool (5%)
ID-RandPool (10%)
Recall (%)
mAP
Pool Size
30
0.4
Number of Labels
Number of Labels
Number of Labels
(a) ImageNet (/U' -339,906
0.5
Pool Size (%)
Recall (%)
mAP
0.4
0.3
Number of Labels
Number of Labels
Number of Labels
(b) OpenImages (UU]=6816,,96)
Figure 14: ID-SEALS (A 100) versus ID applied to candidate pool of randomly selected exam- ples (RandPool). Because the concepts we considered were so rare, as is often the case in practice randomly chosen examples are unlikely to close to the decision boundary, and a much larger pool is required to match SEALS. On ImageNet (top). ID-SEALS outperformed ID-RandPool in terms of both the eπrо the model achieves for active learning (left) and the recall of positive examples for active search (right) even with pool containing 10% of the data (middle). On Openimages (bot- tom), ID-RandPool needed at least 5x as much data to match ID-SEALS for active learning and failed to achieve similar recall even with 10x the data.
19

---

Under review as a conference paper at ICLR 2021
A.6 ACTIVE LEARNING ON EACH SELECTED CLASS FROM OPENIMAGES
Table 3: Top of classes from Openimages for active learning. (1 of 3) Average precision and measurements of the largest component (LC) for each selected class (153 total) from OpenImages with labeling budget of 2,000 examples. Classes ordered based MaxEnt-SEALS.
Average Shortest
Display Name
Total Positives
Size of the LC (%)
Random (All)
MaxEnt (SEALS)
MaxEnt (All)
Full Supervision
Path in
the LC
Citrus
796
65
3.34
0.34
0.87
0.87
0.87
Cargo ship
219
84
2.85
0.70
0.83
0.83
0.86
Blackberry
245
87
2.64
0.67
0.80
0.80
0.79
Galliformes
674
82
3,98
0.72
0.80
0.82
0.92
Rope
59
3.48
0.29
0.80
0.81
0.74
Hurdling
269
92
2.48
0.26
0.80
0.79
0.80
Roman temple
345
89
2.72
0.63
0.79
0.79
0.82
Monster truck
2.84
0.41
0.79
0.80
0.81
Pasta
3,21
0.42
0.75
0.75
0.79
Chess
3,39
0.53
0.73
0.86
Bowed string instrument
78
3.05
0.72
0.72
0.74
0.79
Parrot
1546
0.59
0.72
0.92
Calabuza
3.15
0.50
0.71
0.81
Superhero
5,28
0.17
0.70
0.67
Drums
3,30
0.52
0.83
Shooting range
3,06
0.38
0.68
Ancient architccture
3.34
0.61
0.68
0.70
0.77
Cuphoard
3.41
0.53
0.68
0.75
Ibis
259
2.53
0.29
0.68
0.66
Cattle
5995
3.22
0.37
0.67
0.68
0.74
Gallcon
182
2.54
0.45
0.66
0.66
0.61
Kitchen knife
360
63
3.52
0.32
0.66
0.65
0,66
Grupefruit
506
83
3.06
0.50
0.65
0.65
0.69
Deacon
341
80
2.80
0.48
0.64
0.64
0.67
Rye
128
75
2.63
0.51
0.64
0.64
0.65
Chartreux
147
91
2.59
0.50
0.63
0.63
0.69
San Pedro cactus
318
76
3.32
0.17
0.62
0.63
0.71
Skateboarding Equipment
862
57
5,92
0.20
0.62
0.66
0.66
Electric piano
345
56
4.15
0.24
0.61
0.60
0.48
Straw
547
65
2.85
0.33
0.61
0.62
0.61
Berry
874
82
3.78
0.30
0.61
0161
0.69
East-european shepherd
206
86
2.16
0.61
0.61
0.62
0.65
Ring
676
75
3.87
0.15
0.61
0.64
0.64
Rat
1151
94
2.50
0.32
0.60
0.60
0.61
Coral reef fish
434
90
3.07
0.51
0.60
0.64
0.79
Concert dance
357
61
3.91
0.37
0.60
0.60
0.70
Whole food
708
73
3.66
0.18
0.58
0.60
0.57
Modern pentathlon
772
43
2.59
0.13
0.58
0.47
0.51
Gymnast
235
77
2.39
0.39
0.57
0.59
0.65
California roll
368
84
3.49
0.05
0.56
0.56
0.58
Shrimp
907
85
3.82
0.07
0.56
0.56
0.58
Log cabin
448
70
3.62
0.44
0.55
0.55
0.62
Formula racing
351
88
3,38
0.33
0.55
0.54
0.60
Herd
648
75
3.88
0.42
0.54
0.55
0.67
Embroidery
356
81
3.41
0.32
0.53
0.53
0.60
Shelving
66
3.41
0.27
0.53
0.53
0.51
Downhill
194
84
2.64
0.42
0.53
0.51
0.59
Daylily
3.25
0.20
0.51
0.50
0.49
Automotive exterior
1060
2.74
0.65
0.49
0.54
0.69
Ciconiiformes
88
3.47
0.33
0.49
0.51
0.48
Monoplane
4.70
0.13
0.48
0.48
20

---

Under review as a conference paper at ICLR 2021
Table Middle 3 of classes from Openimages for active learning. (2 of Average precision and measurements of the largest component (LC) for each selected class (153 total) from Openlmages with a labeling budget of 2,000 examples. Classes are ordered based on MaxEnt-SEALE
Average Shortest
Display Name
Total Positives
Random (AII)
MaxEnt (SEALS)
MaxEnt (All)
Full
the L.C
Path
Supervision
(%)
LC
Scafood boil
85
2.73
0.31
0.48
0.49
0.51
Landscaping
789
32
0.26
0.48
0.51
0.63
Skating
561
77
4.04
0.17
0.48
0.43
0.40
Floodplain
567
50
4.81
0.61
0.47
0.52
0.66
Knitting
409
71
3.10
0.61
0.46
0.50
0.73
Elk
353
84
2.40
0.15
0.46
0.48
0.45
Bilberry
75
3.77
0.10
0.45
0.45
0.32
Gout
1190
3.72
0.17
0.44
Fortification
287
66
3.96
0.43
0.44
0.52
Annual plant
677
38
6.07
0.39
0.44
0.43
0.58
Mcdonnell douglas f/a-18 hornet
160
88
3.51
0.11
0.44
0.47
0.37
Tooth
976
49
4.77
0.16
0.44
0.48
0.56
Briefs
539
78
3.68
0.15
0.43
0.44
0.46
Sirloin steak
60
4.97
0.14
0.42
0.42
0.46
Smoothie
78
3.22
0.15
0.41
0.38
Glider
393
82
3.94
0.08
0.40
0.40
0.48
Bathroom cabinet
368
95
2.39
0.29
0.40
0.39
0.37
White-tailed deer
238
87
3.24
0.34
0.40
0.43
0.43
Bird of prey
712
78
3.81
0.76
0.40
0.50
0.91
Egg (Food)
1193
85
4.31
0.14
0.40
0.63
Soldier
74
3.80
0.62
0.40
Cranberry
63
4.10
0.13
0.39
0.39
0.37
Estate
667
51
4.03
0.47
0.39
0.40
0.54
Chocolate truffle
288
58
5,47
0.10
0.39
0.40
0.42
Town square
617
58
3.69
0.31
0.38
0.36
0.47
Bakmi
191
76
3.34
0.27
0.37
0.37
0.36
Trail riding
3.15
0.21
0.37
Acrial photography
63
0.39
0.66
Lugger
103
62
3.14
0.35
0.37
0.37
0.42
Paddy field
468
70
4.02
0.17
0.36
0.36
0.43
Pavlova
195
86
2.60
0.19
0.36
0.36
0.34
Steamed rice
580
75
4.54
0.10
0.35
0.37
0.48
Pancit
86
3.16
0.21
0.33
Factory
61
0.17
0.33
Fur
834
42
0.08
0.33
0.33
0.31
Stallion
598
70
3,58
0.32
0.33
0.40
0.64
Optical instrument
649
79
3,91
0.15
0.33
0.33
0.28
Thumb
895
26
4.18
0.07
0.32
0.39
0.41
Meal
1250
60
5.68
0.52
0.32
0.38
0.59
American shorthair
3,32
0.12
0.32
0.24
Bracelet
46
0.09
0.24
Vehicle registration plate
5697
76
5.89
0.28
0.31
0.33
0.53
Ice
682
50
4.87
0.23
0.30
0.32
0.55
Lamian
257
80
3.57
0.23
0.29
0.32
0.28
Multimedia
741
46
4.12
0.45
0.29
0.31
0.53
Belt
467
41
3.26
0.06
0.29
0.31
Prairic
44
0.37
0.26
0.57
Boardsport
673
62
4.08
0.26
0.29
0.29
0.53
Asphalt
1026
40
4.53
0.23
0.29
0.29
0.45
Custume design
818
52
3,44
0.07
0.26
0.26
0.28
Cottage
670
51
4.13
0.36
0.26
0.36
0.61
21

---

Under review as a conference paper at ICLR 2021
Table Bottom of classes from Openimages for active learning. (3 of Average precision and measurements of the largest component (LC) for each selected class (153 total) from Openlmages with a labeling budget of 2,000 examples. Classes are ordered based on MaxEnt-SEALS.
Average Shortest
Size of the (%)
Display Name
Total Positives
Random (AII)
MaxEnt (SEALS)
MaxEnt (AII)
Full
Path in the LC
Supervision
Stele
450
70
3.74
0.12
0.26
0.25
0.35
Mode of transport
1387
24
4.50
0.15
0.26
0.16
0.54
Temperate coniferous forest
328
59
4.23
0.30
0.26
0.29
0,40
Bumper
985
37
6,65
0.49
0.25
0.38
0.64
Interaction
924
15
6,05
0.04
0.24
0.25
0.37
Plumbing fixture
2124
89
3.19
0.31
0.24
0.27
0.38
Shorebird
234
80
2.76
0.32
0.23
0.26
0.37
Icing
1118
74
4,20
0.13
0.23
0.25
0.46
Wildemness
1225
30
4.12
0.29
0.23
0.24
0.39
Construction
515
63
4,99
0.13
0.23
0.26
0.34
Carpet
644
50
6,98
0.05
0.23
0.28
0.43
Maple
2301
90
4.19
0.06
0.22
0.21
0.36
Rural area
921
41
4.63
0.33
0.22
0.28
0.50
Singer
604
4,06
0.12
0.40
Delicatessen
196
2,80
0.14
0.21
0.27
Canal
726
4.78
0.22
Organ (Biology)
1156
25
3,80
0.23
0.44
Laugh
750
6.22
0.06
0.26
Plateau
452
3.88
0.41
0.24
0.46
Algae
426
4.52
0.15
0.19
0.26
Cactus
377
51
4.11
0.05
0.17
0.18
0.22
Engine
656
82
3,43
0.16
0.17
0.17
0.26
Marine mammal
2954
91
3,58
0.19
0.16
0.15
0.21
Frost
483
60
4.73
0.20
0.15
0.21
0.47
Paper
969
23
3.18
0.16
0.15
0.14
0.41
Cinque
347
29
5.77
0.43
0.15
0.40
0.55
Pork
464
64
4,44
0.06
0.14
0.14
0.15
Antenna
545
73
3.66
0.10
0.14
0.13
0.29
Portrait
2510
67
6,38
0.23
0.13
0.18
0.43
Flooring
814
38
3.87
0.10
0.13
0.14
0.20
Cycling
794
63
5.00
0.53
0.13
0.28
0.66
Chevrolct silverado
115
62
4.82
0.05
0.09
0.08
0.12
Tool
1549
64
4.51
0.08
0.09
0.10
0.13
Liqueur
539
51
5,98
0.26
0.09
0.14
0.38
Pleurotus eryngii
140
84
3.10
0.11
0.08
0.08
0.14
Organism
1148
21
3.49
0.05
0.07
0.13
0.26
Pelecaniformes
457
85
3.96
0.30
0.07
0.09
0.32
Toon
186
3.26
0.05
0.07
0.07
0.16
Stadium
1654
5.77
0.35
0.48
Space
1006
4.63
0.03
0.14
Performing arts
1030
0.53
Mural
649
41
5.24
0.13
0.34
Brown
1427
3.49
0.02
0.07
0.20
Wall
1218
27
3.13
0.11
0.05
0.05
0.27
Tournament
841
47
9,90
0.15
0.05
0.07
0.16
White
1494
2.79
0.02
0.03
0.01
0.10
Mitsubishi
511
37
5.14
0.01
0.02
0.02
0.04
Exhibition
513
40
3.87
0.03
0.02
0.02
0.14
Scale model
667
45
5.64
0.05
0.02
0.02
0.13
Teal
975
16
4.08
0.01
0.01
0.01
0.04
Electric blue
1180
19
3.70
0.01
0.00
0.01
0.06
22

---

Under review as a conference paper at ICLR 2021
A.7 ACTIVE SEARCH ON EACH SELECTED CLASS FROM OPENIMAGES
Table Top: 3 of classes from Openimages for active search. of Recall (%) of positives and measurements of the largest component (LC) for each selected class (153 total) from OpenImages with labeling budget of 2,000 examples. Classes are ordered based on MLP-SEALS.
Average Shortest
Size of the L.C (%)
Display Name
Total Positives
Random (All)
MLP (SEALS)
MLP
Path in
(AII)
the LC
Chartreux
147
91
2.59
3.5
83.9
84.6
lbis
259
93
2.53
2.0
83.9
83.9
Hurdling
269
92
2.48
1.9
83.5
86.2
East- cast-eu shepherd
206
86
2.16
2.4
78.2
78.3
Blackberry
245
87
2.64
2.0
77.5
78.5
Bathroom cabinet
368
95
2.39
76.8
77.1
Rat
1151
94
2.50
0.5
75.1
75.2
Rye
128
75
2.63
3.9
74.7
74.5
Elk
353
84
2.40
1.5
73.4
74.3
Pavlova
195
86
2.60
2.6
70.8
71.3
Seafood boil
322
85
2.73
1.6
70.4
70.6
Roman temple
345
89
2.72
69.2
68.3
Monster truck
286
84
2.84
1.7
68.1
67.8
Downhill
194
84
2.64
2.6
67.2
69.0
Shorebird
80
2.76
66.4
Mcdonnell douglas f/a- 18 hornet
160
88
3.51
3,2
66.0
67.9
San Pedro cactus
318
76
3.32
1.6
65.8
64.9
Plcurotus eryngii
140
84
3.10
3.6
65.7
66.1
California roll
368
84
3.49
1.4
65.3
68.0
Gymnast
235
77
2.39
2.2
64.0
64.0
Galleon
182
74
2.54
2.7
62.4
61.5
Cargo ship
219
84
2.85
2.3
61.1
61.7
Trail riding
679
90
3.15
0.8
59.7
60.7
Daylily
391
87
3.25
1.3
59.4
59.5
Grapefruit
506
83
3.06
1.0
59.4
60.4
Bilberry
228
75
3.77
58.9
55.2
Smoothie
330
78
3.22
1.5
58.0
59.8
Embroidery
356
81
3.41
1.5
57.6
57.2
Deacon
341
80
2.80
57.1
57.9
Shooting range
189
57
3,06
2.6
56.3
55.6
Glider
393
82
3.94
1.3
55.8
57.6
White-tailed deer
238
87
3.24
55.9
Coral reef fish
434
90
3.07
1.3
54.8
54.9
Chevrolet silverado
115
62
4,82
4.3
54.1
54.6
Lugger
103
62
3.14
4.9
53.8
53.8
Pancit
385
86
3.16
1.3
52.8
53.1
Chess
740
83
3,39
0.7
51.9
50.9
Bakmi
191
76
3,34
2.6
51.8
51.2
Kitchen knife
360
63
3.52
1.5
50.9
53.9
Straw
547
65
2.85
50.3
51.0
Ancient roman architecture
589
76
3.34
0.8
48.5
47.1
Lamian
257
80
3.57
1.9
47.8
48.2
Antenna
545
73
3.66
48.0
Calabaza
870
82
3.15
0.6
46.0
45.8
Ring
676
75
3.87
0.7
45.2
45.4
Ciconiforres
426
88
3.47
45.2
Log cabin
448
70
3.62
1.1
44.9
45.7
Bowed string instrument
728
78
3.05
0.7
44A
44.7
Pasta
954
91
3.21
0.5
43.7
43.8
Knitting
409
71
3.10
1.3
43.5
42.8
Rope
618
59
3.48
0.8
43.0
42.8
23

---

Under review as a conference paper at ICLR 2021
Table Middle of classes from Openimages for active search. (2 of Recall (%) of positives and measurements of the largest component (LC) for each selected class (153 total) from OpenIm- ages with a labeling budget of 2,000 examples. Classes are ordered based on MLP-SEALS.
Average Shortest
Size of the LC (%
Display Name
Total Positives
Random (All)
MLP (SEALS)
MLP
Path in
(All)
the LC
Formula racing
351
88
3.38
1.4
42.6
41.4
Paddy field
468
70
4.02
1.1
42.6
44.2
Engine
656
82
3.43
0.8
41.7
40.6
Electric piano
345
56
4.15
1.5
40.9
42.1
Shrimp
907
85
3.82
0.6
40.4
40.8
Goat
1190
88
3.72
0.4
39.6
39.6
Chocolate truffle
288
58
5.47
1.8
39.6
39.9
Cupboard
898
88
3.41
0.6
39.6
39.6
Citrus
796
65
3.34
0.7
39.3
39.6
Parrot
1546
89
2.85
0.4
39.2
38.8
Delicatessen
196
52
2.80
2.6
38.2
39.0
Berry
874
82
3.78
0.6
37.8
37.6
Briefs
539
78
3,68
1.0
37.1
37.2
Concert dance
357
61
3,91
1.4
36.6
36.1
Modern pentathlon
772
43
2.59
0.6
35.9
32.6
Fortification
287
66
3.96
1.7
35.7
37.6
Stallion
598
70
3.58
0.9
35.7
36.3
Belt
467
41
3.26
1.1
35.2
34.9
Sirloin steak
297
60
4.97
1.8
33.9
32.7
Stele
450
70
3.74
1.1
33.9
32.7
Galliformes
674
82
3.98
0.7
33.9
33.9
Algae
426
57
4.52
1.2
33.8
33.1
Herd
648
75
3.88
0.8
33.5
33.7
Pelecaniformes
457
85
3.96
33.4
37.5
Cactus
377
51
4.11
1.3
33.4
35.2
Shelving
810
66
3.41
0.7
33.2
33.3
Drums
741
69
3.30
0.7
32.9
32.7
Cranberry
450
63
4.10
1.2
32.9
33.7
Factory
333
61
5.59
1.5
32.0
31.7
Costume design
818
52
3.44
0.6
30.9
30.6
Optical instrument
649
79
3,91
0.8
30.3
32.8
Construction
515
63
4.99
1.0
30.1
31.1
Temperate coniferous forest
328
59
4.23
1.5
30.1
27.6
Skating
561
77
4.04
1.0
28.8
30.4
Egg (Food)
1193
85
4.31
0.4
28.8
28.6
Steamed rice
580
75
4.54
0.9
28.1
30.2
Plumbing fixture
2124
89
3.19
0.3
27.9
27.9
Whole food
708
73
3.66
0.7
27.7
27.5
Boardsport
673
62
4.08
0.8
26.8
26.5
Pork
464
64
4.44
1.1
26.3
26.6
Aerial photography
931
63
3.99
0.6
25.8
26.1
Town square
617
58
3.69
0.8
25.7
26.1
Estate
667
51
4.03
0.9
24.8
25.9
Maple
2301
90
4.19
0.2
24.3
24.4
Cattle
5995
93
3.22
0.1
23.8
23.6
Superhero
968
58
5.28
0.6
23.4
23.3
Bracelet
770
46
4.13
0.6
23.2
24.8
Frost
483
60
4.73
1.0
23.1
22.5
Scale model
667
45
5,64
0.8
22.9
23.7
Plateau
452
37
3,88
1.1
22.7
19.1
Bird of prey
712
78
3.81
0.7
22.4
22.0
24

---

Under review as a conference paper at ICLR 2021
Table Bottom of classes from Openimages for active search. (3 3) Recall (%) of positives and measurements of the largest component (LC) for each selected class (153 total) from OpenIm- ages with a labeling budget of 2,000 examples. Classes are ordered based on MLP-SEALS.
Average Shortest
Size of the LC (%)
Display
Total Positives
Random (AII)
MLP (SEALS)
MLP
Name
Path in
(All)
the LC
Canal
726
62
4.78
0.7
22.4
20.9
Exhibition
513
40
3.87
1.0
21.9
23.1
Carpet
644
50
6.98
0.8
21.9
22.7
Monoplane
756
4.70
0.7
21.8
20.1
Ice
682
50
4.87
0.8
21.6
23.1
Fur
834
42
4.31
0.6
21.2
17.3
Icing
1118
74
4.20
0.4
20.5
20.1
Flooring
814
38
3,87
0.6
20.4
16.9
Icon
186
15
3.26
2.7
19.9
17.2
Prairie
792
44
3.92
0.6
19.0
19.2
Tooth
976
49
4.77
0.5
18.6
18.0
Skateboarding Equipment
862
57
5.92
0.6
18.1
19.3
Automotive exterior
1060
23
2.74
0.5
17.7
11.9
Cottage
670
51
4.13
0.7
17.6
17.3
Soldier
1032
74
3.80
0.5
17.3
16.8
Marine mammal
2954
91
3.58
0.2
17.3
17.2
Tool
1549
64
4.51
0.3
17.0
16.9
Multimedia
741
46
4.12
0.7
16.8
17.1
American shorthair
2084
94
3.32
0.3
16.5
16.7
Asphalt
1026
40
4.53
0,5
15.1
11.5
Singer
604
56
4.06
0.9
14.6
13.6
Floodplain
567
50
4.81
0.9
14.6
14.0
Rural area
921
41
4.63
0.6
14.2
13.2
Mitsubishi
511
37
5.14
1.0
12.6
11.8
Organ (Biology)
1156
25
3.80
0.5
12.1
15.9
Paper
969
23
3.18
0.5
12.0
14.8
Annual plant
677
38
6.07
0.7
11.8
10.7
Electric blue
1180
19
3.70
0.5
11.5
9.4
Stadium
1654
77
5.77
0.3
10.8
9.3
Mural
649
41
5.24
0.8
10.4
10.3
Teal
975
16
4.08
0.5
9.9
10.4
Cirque
347
29
5.77
1.5
9.9
9.8
Wall
1218
27
3.13
0.4
9.3
12.0
Thumb
895
26
4.18
0.6
9.3
13.8
Landscaping
789
32
4.71
0.7
9.2
9.3
Vehicle registration plate
5697
76
5.89
0.1
8.7
8.3
Meal
1250
60
5.68
0.4
8.5
9.1
Wilderness
1225
30
4.12
0.4
8.5
9.8
Liqueur
539
51
5.98
1.0
8.0
12.8
Space
1006
23
4.63
0.5
7.8
6.3
Cycling
794
63
5.00
0.6
7.3
7.8
Brown
1427
16
3.49
0.4
7.2
2.6
Organism
1148
3.49
0.4
6.8
2.0
Laugh
750
19
6.22
0.7
6.6
8.6
Bumper
985
37
6.65
0.5
5.9
8.3
Portrait
2510
67
6.38
0.2
5.8
5.3
Mode of transport
1387
24
4.50
0.4
5.1
3.6
Interaction
924
15
6.05
0.6
4.5
4.6
Tournament
841
47
9,90
0.6
4.3
5.1
Performing arts
1030
29
6.97
0.5
2.3
2.5
White
1494
3
2.79
0.3
2.0
0.5
25

---

Under review as a conference paper at ICLR 2021
A.8 SELE-SUPERVISED EMBEDDING SENITENCE-BERTT ON GOODREADS
We followed the same general procedure described in Section 4.1 aside from the dataset specific details below. Goodreads spoiler detection (Wan et al.) 2019) had 17.67 million sentences with binary spoiler annotations. Spoilers made up 3.224% of the data, making them much more common than the rare concepts we evaluated in the other datasets. Following Wan al. (2019). we used 3.53
million sentences for testing (20%). 10,000 sentences the validation set, and the remaining 14.13 million sentences as the unlabeled pool. We also switched to the area under the ROC curve (AUC) as primary evaluation metric for active learning to be consistent with Wan et al. (2019), For Gz. we used a pre-trained Sentence-BERT model (SBERT-NLI-bas applied PCA whitening to reduce the dimension to 256, and performed 7- normalization.
(Reimers & Gurevych 2019).
A.8.1 ACTIVE SEARCH
SEALS achieved the same recall as the baseline approaches, but only considered less than 1% of the unlabeled data in the candidate pool, shown in Figure L5 At labeling budget of 2,000, MLP- ALL and MLP-SEAA PSSALS recalled 0.15 + 0.02% and 0.17 = 0.05%, respectively, while MaxEnt-All and MaxEnt- MaxEnt-SEELLS achieved 0.14 + 0.04% and 0.11 = 0.06% recall respectively. Increasing the labeling budget to 50,000 examples, increased recall to 3..7% for MaxEnt and MLP but maintained a similar relative improvement over random sampling, shown in Figure [6] ID-SEALS performed worse than the other strategies. However, all of the active selection strategies outperformed random sampling by up an order of magnitude.
Full Supervision
Random-All
MLP-AII
MaxEnt-All
ID-AIl ID-SEALS
Random-SEALL
MLP-SEALS
MaxEnt-SEALE
620
Recall (%6
0:0
Pool
6.55
250
750
1224
1000 1750
2000
254
750
1259
1306
1750
2000
500
1004
3500 3750
2000
Number of Labels
Number of Labels
Number of Labels
Figure 15: Active learning and search Goodreads with Sentence-BERG embeddings. Across datasets and strategies, SEALS with à = 100 performs similarly to the baseline approach in terms of both the enror the model achieves for active learning (left) and the recall of positive examples for active search (right), while only considering a fraction of the data U (middle).
A.8.2 ACTIVE LEARNING
At a labeling budget 2,000 examples, all the selection strategies were indistinguishable from random sampling. Increasing the labeling budget did not help, shown in Figure 16 Unlike ImageNet and Openlmages, Goodreads had much higher fraction of positive examples (3.224%), and the examples not tightly clustered described in Section A.8.3
26

---

Under review as a conference paper at ICLR 2021
Full Supervision
Random-All Random-SEAL
MLP-AII
MaxEnt-All
MLP-SEALS
MaxEnt-SEALE
Pool Size (%)
Recall (%)
0.70
0.65
10
0.55
0.50
20000
43000
50000 50000
100000
20000
40000
5000S
B0000
100000
20000
40000 60500 50000 100000
Number of Labels
Number of Labels
Number of Labels
Figure 16: Active learning and search on Goodreads with labeling budget of 100,000 examples. Across strategies, SEALS with 100 performed similarly to the baseline approach in terms of both the error the model achieved for active learning (left) and the recall of positive examples for active search (right), while only considering a fraction of the data U (middle). ID was excluded because of the growing pool size and computation. For active search, MaxEnt and MLP continued to improve recall. For active learning, all the selection strategies (both with and without SEALS) performed worse than random sampling despite the larger labeling budget. This gap likely due to spoilers being book specific and the higher fraction positive examples in the unlabeled pool, causing relevant examples to be spread almost uniformly across the space (see Section A.8.3)
A.8.3 LATENT STRUCTURE
The large number of positive examples in the Goodreads dataset limited the analysis we could per- form. We could only calculate the size of the largest connected component in the nearest neighbor graph (Figure 17). For & 10, only 28.4% of the positive examples could be reached directly, but increasing to 100 improved that dramatically nent, one might have expected active learning to perform better in Section A.8.2 By analyzing the embeddings, however, we found that examples are spread almost uniformly across the space with an average cosine similarity of 0.004. For comparison, the average cosine similarity for concepts in ImageNet and OpenImages was 0.453 0.077 and 0.361 0.105 respectively. This uniformity was likely due to the higher fraction of positive examples and spoilers being book specific while Bentence-BERTii is trained on generic data. As a result, even if spoilers were tightly clustered within each book, the books were spread across range of topics and consequently across the embedding space, illustrating limitation and opportunity for future work.
96.7%. For such large connected compo-
1.00
10
0.75
100
1000
CDF
0.50
0.25
0.00
80 Size of Largest Component (%)
20
40
60
100
Figure 17:
Cumulative distribution function (CDF) for the largest connected component in the Goodreads dataset with varying values of k.
27


Reviews:
[{"review_id": "gn8WvEUsYdv", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------\n\nThis paper adopts k-NN to enhance the efficiency of active learning for heavily skewed data sets up to 10 billion scale. The proposed algorithm is evaluated extensively by a large number of experiments. The experimental results show the efficiency of proposed algorithm with 10x times speedup comparing to existing methods.\n\nThe proposed algorithm is presented in the form of pseudo codes (Algo 2), but without clear introduction to the details of the Algo 2, particularly, the detail of how the k-NN will be performed, and the analysis of the cost model. This makes the paper lack of technical depth.\n\n\nStrengths\n---------\n\n- The motivation of this work is clear. The authors emphasize the motivation and difference from existing again and again in the whole paper. The paper is well-written and well-structed thus easy for understanding.\n\n- A 10 billion-scale data set with heavy skew is used for experiments, which make the evaluations convincing (meanwhile it could be counted as a weakness as well. see next section).\n\n- The extensive experiments are sufficient to show the advantages of the proposed algorithm for active learning and active search. \n\nWeaknesses\n----------\n\n- The approach of adopting k-NN to enhance the efficiency of data sampling during the active learning and search is a natural combination with active learning framework, thus there is no surprising at the view point of novelty. The reasons of such judgment are based on the following points.\n\n\t- The authors only introduce the advantages of k-NN that can be done in logarithmic time or even in constant time for approximate k-NN if adopting latest third-party implementations. However, the authors did not introduce how non-trivial the idea of adopting k-NN is, or how difficult the authors came up with such a idea. It means that currently the proposed method sound only a natural combined algorithm but without high novelty.\n\n\t- The key contribution should be how to incorporate k-NN with active learning and active search in this paper. Actually, such kind of incorporation has been studied and proposed in some key publications. Thus the authors have to present the originality of their approach.\n\t\n    [1] Kai Wei, et al.: Submodularity in Data Subset Selection and Active Learning (ICML 2015)\n    [2] Ajay J. Joshi, et al.: Coverage Optimized Active Learning for K-NN Classifiers (ICRA 2012)\n\t\n- The technical depth of proposed algorithm is not sufficient. For example, the authors could add more details to introduce how the k-NN algorithm is collaborating with active learning in terms of theoretical and mathematical aspects. However, the authors only put the algorithm in the paper with a table to show the comparative computation complexity. More details and clarifications should be provided to make the approach in a technical way.\n\n- The 10 billion data set is very big and should benefit the research community if it will be open-sourced or available for public use. However, it sounds a data set from a large internet company and involving with hired annotators during the experiments. So, there might be some unseen factors that would have more or less impact on the evaluation results. This point should be clarified by the authors.\n\n\nOther Questionable Points\n-------------------------\n\n- Sec 3.1: each unlabeled data $x_i$ is mapped to a latent variable $G_z(x_i) = z_i$. Here, as we know, high dimensional features (i.e., $z_i$) is often used in many computation vision tasks. In such cases, the k-NN computation itself will get involved into the well-known problem -- \"the curse of dimensionality\", that makes k-NN algorithm cannot be done in logarithmic time but turn to linear time. Therefore, the basic assumption that k-NN computation can be done efficiency does not hold any more. This critical point is not discussed in the paper.\n\n- Table 1: the complexity of SEALS might be incorrect. As a reviewer, if my understanding is correct, the computation of k-NN ($N(z,k)$) should involve the similarity computations between labeled data ($z$) and unlabeled data ($o \\in U$). Although the authors assume employing efficient indexing method to perform k-NN computation, its complexity should be counted as $O(log|U|)$ as well. It will become $O(|U|)$ in the worst cases when the curse of dimensionality happened.\n\n- Table 2: Why the fraction positive regarding the 10B image dataset is not available in the table?\n\n- Fig. 1(b): Why the performance of mAP regarding MLP-x, MaxEnt-x methods has drops at the beginning when the number of labels is less then 500?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "bGugs5PN5GX", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper proposes a new method (SEALS) to accelerate the active learning and active search with the skewness of the cardinality of rare class compared to the large-scale datasets. To leverage this skewness, the authors restrict the candidate pool for labelling mainly from the nearest neighbours of the currently labelled set (except the initial set). The authors conduct very detailed experiments on the tasks of active learning and active search over three large-scale data sets to validate the efficiency and effectiveness of SEALS. \n\nPros:\n1. The motivation to leverage the skewness of data to speed up active learning and active search is good. I like the idea to incrementally enlarge the candidate pool for labelling by the nearest neighbours.\n2. The experiment is rigorous and the authors also consider and provide results on NLP domain in the supplementary. \n3. The method SEALS seems to be general and can be adapted to different active learning methods of rare concepts.\n\nCons:\n1. The major concern of this paper is the lack of theoretical analysis. The idea is straightforward and the novelty is limited. The authors use very detailed experiments to verify their observation, but is it technically solid? Does this method require any (strong) assumption? Can you get any novel theoretical findings?  A sentence about ``learned representations can effectively cluster rare concepts” is not enough.\n2. There exist many errors and over claims in the statement of k-Nearest Neighbour Search (k-NNS). More details can be found in minor comments. \n3. The time complexity of information density (ID) and its implementation in the experiments for comparison are wrong. With some pre-computation, the time complexity of ID should be as same as the max entropy (MaxEnt). More details can also be found in minor comments.\n4. The Introduction section only discusses the motivation of active learning for rare concepts. How about the active search? Is there any more technique challenge, or just conduct one more task only? I have this concern because the objective function of MLP is quite different from MaxEnt and ID, which is not necessary to validate the idea of using the skewness for acceleration.\n\nMinor Comments or Typos:\n1. The authors claim that k-NNS can be done in logarithmic time [1] or approximately in constant time [2][3]. As a researcher whose research areas include this, I would like to point out that this claim is wrong. For the kd-tree [1], the log time only happens when the data dimension is restricted to 2 or 3. For the scenarios the authors consider in this paper, the data dimension is at least 100 dimensions, the data structure of kd-tree will suffer from the curse of dimensionality. Moreover, the authors of SimHash [2] and FAISS [3] did not claim their methods can handle k-NNS approximately in constant time. In fact, there is no method with a theoretical guarantee that can deal with (approximate) k-NNS in O(log n) time in high-dimensional Euclidean spaces (e.g., d > 100). Specifically, the time complexity of SimHash [2] is sub-linear, i.e., O(\\log(n) \\cdot n^\\rho) with \\rho \\in (0,1), which is still far from log(n) level. \n2. The authors also claim they use locality-sensitive hashing (LSH) [2] with Euclidean distance implemented in FAISS [3]. I would like to point out SimHash [3] is designed for cosine similarity instead of Euclidean distance. And FAISS is built on Product Quantization instead of LSH. I guess the authors only use FAISS in the experiments to determine nearest neighbours with Euclidean distance, but this sentence is misleading.\n3.  As discussed in [4], the density score (e.g., the sum of the similarity for each data) can be pre-computed and cached for efficient lookup. So the time complexity of ID in Table 1 should be as same as MaxEnt. And similarly, the time complexity of SEALS can be reduced to O(k^2 |L_r|). Thus, in the experiments, the author can pre-compute the density score and hence the ID strategy can be evaluated in the private ten billion data set.\n4. The notation of \\mathcal{L}_r in Algorithms 1 & 2 is inconsistent with the paper which is L_r. \n5. In line 8 of Algorithm 2, remove “-z*” as follows\n\\mathcal{P}_r = \\mathcal{P}_r \\cup \\mathcal(N)(z*,k) – z* --> \\mathcal{P}_r = \\mathcal{P}_r \\cup \\mathcal(N)(z*,k) \n6. In the experiments, it will be better to also report the running time besides the pool size for active search.\n\nReference:\n\n[1] Bentley, Jon Louis. \"Multidimensional binary search trees used for associative searching.\" Communications of the ACM 18, no. 9 (1975): 509-517.\n\n[2] Charikar, Moses S. \"Similarity estimation techniques from rounding algorithms.\" In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing, pp. 380-388. 2002.\n\n[3] Johnson, Jeff, Matthijs Douze, and Hervé Jégou. \"Billion-scale similarity search with GPUs.\" IEEE Transactions on Big Data (2019).\n\n[4] Settles, Burr, and Mark Craven. \"An analysis of active learning strategies for sequence labeling tasks.\" In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pp. 1070-1079. 2008.\n\n==============================================================================================\n\nUpdate: Thank you for the feedback and the efforts in revising the draft. Some of my questions were clarified and many existing errors have been fixed. However, I still think the novelty is limited, and more needs should be done to enrich the method with more analysis in terms of theoretical and mathematical aspects. Based on the above reasons, I do not intend to increase my rating. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_PYlbG-xkV7", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an active learning and active search approach that targets samples for rare classes in very large unlabeled datasets with highly imbalanced class distributions. This is a common scenario in real-world applications, where these rare situations can be critical to accurately categorize - ie endangered species. The authors propose an approach that targets these rare cases while reducing the number of overall examples sampled, and that scales with the amount of labeled data as opposed to the amount of unlabeled data which allows them to consider datasets up to billions of examples.\n\nPros:\n\nThis is a well-motivated task, there is a clear need for this type of method as access to unlabeled data increases\nTheir method scales effectively to very large sets of unlabeled data, eg matching baseline performance with only 0.1% of the unlabeled data sampled on their proprietary 10 billion image dataset.\nThe method leads to impressive computational speedups in active learning selection rounds, eg 4000x speedup in selection round time on ImageNet.\n\nCons - \n\nI am glad to see that they compare performance to public datasets to help with this, but some of their biggest claims are not reproducible because they are shown with proprietary data.\nTheir model does require an initial pass through an embedding model for all the data, which would be very slow and expensive for 10 billion images. This embedding model seems to need to encode the rare classes appropriately and be able to cluster them together sufficiently for the neighbors of a rare class to be likely to be of the same class for this method to work well. In the low data regime it is not always guaranteed that you will have sufficient training data to build an embedding that handles rare categories sensibly, particularly in fine-grained scenarios. The authors could do a better job analyzing the impact of their chosen embedding function on the efficacy of their method. They discuss this a bit in section 4.4, but it would be awesome to see some concept of performance of the method for each concept included in Figure 3 (unsure how best to do this).\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed an active search algorithm for efficiently identifying rare concepts among heavily imbalanced datasets. Reviewers find the paper very well-motivated and addressing an important real-world challenge in active learning. All reviewers appreciate the extensive demonstration of the effectiveness of the proposed algorithm on real-world tasks, in particular in industrial settings where the scale of problems goes far beyond common academic datasets.

In the meantime, there are shared concerns among several reviewers in the technical depth of the proposed algorithm. Although the authors provided intuitive explanations of the nearest-neighbor based approach, the results reported are restricted mostly to several final performance metrics on the search performance. As a purely empirical work, the paper would benefit from more fine-grained experimental analyses and ablation studies (e.g., by breaking down to analyses at intermediate levels).

Decision: Reject