Abstract: Self-Supervised Learning (SSL) has emerged as the solution of choice to learn transferable representations from unlabeled data. However, SSL requires to build samples that are known to be semantically akin, i.e. positive views. Requiring such knowledge is the main limitation of SSL and is often tackled by ad-hoc strategies e.g. applying known data-augmentations to the same input. In this work, we formalize and generalize this principle through Positive Active Learning (PAL) where an oracle queries semantic relationships between samples. PAL achieves three main objectives. First, it unveils a theoretically grounded learning framework beyond SSL, based on similarity graphs, that can be extended to tackle supervised and semi-supervised learning depending on the employed oracle. Second, it provides a consistent algorithm to embed a priori knowledge, e.g. some observed labels, into any SSL losses without any change in the training pipeline. Third, it provides a proper active learning framework yielding low-cost solutions to annotate datasets, arguably bringing the gap between theory and practice of active learning that is based on simple-to-answer-by-non-experts queries of semantic relationships between inputs.
Introduction
In modern artificial intelligence, researchers often find themselves caught between two paradigms. Supervised Learning (SL) is undeniably powerful but requires massive, expertly labeled datasets. For instance, a human annotator must know the specific taxonomic difference between a "Tinca tinca" and a "Carassius auratus" to provide useful labels for ImageNet. Conversely, Self-Supervised Learning (SSL) avoids this requirement by using data augmentations to "guess" which samples are similar, but it struggles to incorporate actual human knowledge or labels when they are available.
Furthermore, traditional Active Learning—the practice of having a model ask for labels only when it is uncertain—usually requests absolute category names. This remains a high-cost endeavor requiring domain experts. This paper, a collaboration involving Meta AI and Yann LeCun, provides an elegant theoretical bridge between these worlds. By reframing learning through the lens of "similarity graphs," the authors introduce Positive Active Learning (PAL), a paradigm that makes data annotation cheaper, faster, and less dependent on specialized expertise.
Methodology: The Similarity Graph
The core of the paper is the Similarity Graph ($G$). In this framework, nodes represent data samples and edges represent known semantic relationships (e.g., "these two images contain the same object").
A Unified Framework
The authors prove (Theorem 1) that major SSL losses—specifically VICReg, SimCLR, and BarlowTwins—can be rewritten entirely in terms of this similarity graph. This suggests that SSL and Supervised Learning are not distinct methods but rather two ends of the same spectrum; they differ primarily in how the graph $G$ is constructed.
Positive Active Learning (PAL)
Instead of asking an oracle "What is the label for this image?", PAL asks "Are these two images semantically related?" This shift allows for an "Oracle à la Captcha." The authors propose a strategy where a user is shown a "template" image and asked to pick matching images from a batch. This allows the model to reconstruct the full similarity graph with $O(N)$ queries instead of the $O(N^2)$ required by naive pairwise comparisons.
Key Insights and the Spectrum of Learning
The framework allows researchers to visualize the learning process as the density of the similarity graph. In SSL, the graph is "sparse," only connecting an image to its own augmentations. In Supervised Learning, the graph is "dense," connecting all images belonging to the same class. PAL allows for a middle ground, where a few strategically chosen edges can yield high-quality representations.
- Low-Cost Expertise: One does not need to be a biologist to recognize that two birds look similar. PAL leverages this "reduced expertise" to build high-quality representations without needing a dictionary of class names.
- Connected Components: A critical insight from the experiments is that model error is highly predictable based on the number of "connected components" discovered in the similarity graph. Once the graph is sufficiently connected, the representation becomes highly useful for downstream tasks.
- Robustness: Because the framework uses Stochastic Gradient Descent (SGD) to update weights based on graph edges, it is naturally robust to occasional mistakes or noise introduced by the human oracle.
Experimental Results
The authors validated their theory using synthetic data (Concentric Circles, Mixture of Gaussians) and real-world datasets (CIFAR-10, ImageNet):
- Efficiency: In synthetic tests, PAL reached low test error significantly faster than passive supervised learning, achieving near-perfect results with roughly 200 queries, while passive methods required over 800.
- Label Integration: The authors demonstrated that adding even a tiny amount of label information (a mixing coefficient of $\alpha = 10^{-6}$) into an SSL pipeline significantly boosts performance without requiring architectural changes.
- Real-World Parity: On CIFAR-10, the representation learned via the similarity graph achieved 63% accuracy, matching the performance of a standard supervised ResNet-18 trained with Mean Squared Error (MSE).
Limitations and Future Work
While the PAL framework is theoretically robust, it currently relies on binary (yes/no) relationships. Future research could explore "soft" similarity scores or hierarchical relationships (e.g., recognizing that two images are both "animals" even if they are different species). Additionally, while the "Captcha" style oracle is promising, further large-scale empirical testing on datasets like ImageNet-21k is needed to evaluate how the system handles thousands of distinct classes and the memory intensity of maintaining similarity matrices for billions of samples.
Summary updated