Similarity Search for Efficient Active Learning and Search of Rare Concepts

Cody Coleman, Edward Chou, Sean Culatana, Peter Bailis, Alexander C. Berg, Roshan Sumbaly, Matei Zaharia, I. Zeki Yalniz

Abstract

Active learning (AL) is a powerful paradigm for training models with minimal labeled data by iteratively selecting the most informative examples. However, at web-scale (billions of images), traditional AL becomes computationally intractable because selection strategies typically require scoring the entire unlabeled pool in every round. We introduce SEALS (Similarity search for Efficient Active Learning and Search), an algorithm that restricts the search for new training examples to the $k$-nearest neighbors of the already-labeled set. By leveraging efficient similarity search, SEALS achieves up to a 1,000x speedup over global search methods with negligible loss in accuracy. We demonstrate the effectiveness of SEALS on datasets up to 10 billion images, particularly for the challenging task of finding rare concepts.

Introduction

Modern machine learning models require massive amounts of data, but the cost of labeling billions of examples is prohibitive. Active Learning (AL) offers a solution by intelligently selecting examples for annotation. Unfortunately, standard AL algorithms scale poorly; to find a "needle in a haystack" of 10 billion images, these algorithms must scan the entire pool in every round. This computational bottleneck is especially severe for rare concepts—those appearing in less than 1% of the data—where finding informative examples is both crucial and difficult.

The SEALS Framework

The core innovation of SEALS is to decouple the cost of active learning from the total size of the unlabeled pool. Instead of a global search, SEALS performs a local search within the latent embedding space of a pre-trained model.

  1. Restricted Candidate Pool: The algorithm only considers the $k$-nearest neighbors of the existing labeled set as candidates for the next round of labeling.
  2. Iterative Expansion: As new examples are labeled, their neighbors are added to the candidate pool, allowing the search to "crawl" through the embedding space toward the most informative regions.
  3. Efficient Retrieval: Using approximate nearest neighbor (ANN) libraries like Faiss, SEALS can identify these candidates in sub-second time, even in pools containing billions of points.
Figure 1: Pool size reduction on ImageNet. SEALS restricts the candidate pool to a small fraction of the total dataset, scaling linearly with the number of labels.

The success of this approach hinges on the "latent structure" of modern embeddings: similar concepts naturally cluster together. By looking near known examples of a concept, SEALS can efficiently find more relevant data without scanning the entire universe of images.

Experimental Evaluation

We evaluated SEALS across several large-scale benchmarks:

  • ImageNet: ~640k images, used to simulate rare concepts by partitioning classes.
  • OpenImages: ~6.8M images, focusing on 153 rare concepts with prevalence as low as 0.002%.
  • 10 Billion (10B) Dataset: A massive, de-identified dataset of 10 billion publicly shared images.
  • Goodreads: 14M sentences, testing the method's applicability to text and self-supervised embeddings.

Results and Discussion

SEALS demonstrates remarkable efficiency gains. On the 10-billion image dataset, selection rounds that previously required a cluster of tens of thousands of cores were completed in seconds on a single 24-core machine—a 1,000x speedup.

Figure 4: Performance on a 10-billion image dataset. SEALS (orange/red lines) achieves mAP comparable to global search (black line) while maintaining a much smaller pool size and finding significantly more positives.

Crucially, this speedup comes with almost no penalty in model performance. As shown in Figure 4, SEALS-based selection strategies achieve Mean Average Precision (mAP) nearly identical to "Global" baselines that scan the entire pool. In some cases, such as the "Most-Likely Positive" strategy (MLP-SEALS), the method actually finds significantly more positive examples of rare concepts than standard approaches.

Conclusion

SEALS makes active learning at web-scale a practical reality. By restricting search to the neighborhood of labeled data, it bypasses the linear scaling bottleneck of traditional methods. While the approach depends on the quality of the underlying embeddings, it proves robust across various models and datasets. Future work may explore hybrid strategies to handle highly fragmented concepts where local search might miss disjoint clusters in the embedding space.

Summary updated

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.
BibTeX
@inproceedings{coleman2022similarity,
  author = {Cody Coleman and Edward Chou and Sean Culatana and Peter Bailis and Alexander C. Berg and Roshan Sumbaly and Matei Zaharia and I. Zeki Yalniz},
  title = {{Similarity Search for Efficient Active Learning and Search of Rare Concepts}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i6.20591},
}
Figure