Self-labelling via simultaneous clustering and representation learning

Yuki Markus Asano, Christian Rupprecht, Andrea Vedaldi

This ICLR 2020 paper from the Visual Geometry Group (VGG) at Oxford presents a powerful, principled approach to unsupervised learning. By reframing clustering as an optimal transport problem, the authors bridge the gap between arbitrary "pretext tasks" and standard supervised classification.

TL;DR

The researchers propose SeLa (Self-Labelling), a method that simultaneously learns visual representations and generates data labels without any human intervention. By forcing the network to distribute images evenly across categories (equipartition) and maximizing mutual information, they achieve state-of-the-art results. Remarkably, this method produces an AlexNet that outperforms its human-supervised counterpart on downstream object detection tasks.

The Challenge of Unsupervised Clustering

In computer vision, the "gold standard" for pre-training a model is supervised learning on massive datasets like ImageNet. However, manual labeling is expensive, time-consuming, and fails to scale to the billions of images available online.

Self-supervised learning attempts to bypass this by creating "pretext tasks"—such as predicting image rotations or solving jigsaw puzzles. While clever, these tasks are often arbitrary and don't directly map to semantic understanding. A more natural approach is clustering: allowing the computer to group similar images together and treating those groups as pseudo-labels.

The primary challenge with clustering is degeneracy. If a neural network is simply told to "find its own labels," it will often take the path of least resistance and assign every single image to the same cluster. This results in a loss of zero, but the network learns absolutely nothing about the underlying data. Previous attempts to fix this, such as DeepCluster, relied on heuristics that lacked a unified mathematical objective, making them unstable and difficult to analyze.

The SeLa Method

The authors propose a two-step alternating optimization process governed by a single, unified objective: Cross-Entropy Loss.

  1. Representation Learning: Given a set of pseudo-labels, the network is trained using standard Stochastic Gradient Descent (SGD) to predict those labels. This mirrors standard supervised training.
  2. Self-Labelling: This is the core innovation. The authors treat the label assignments as variables to be optimized. To avoid the degeneracy problem (where all images collapse into one cluster), they introduce a strict constraint: Equipartition. Every cluster must contain an equal number of images.

The Sinkhorn-Knopp Algorithm

Finding the optimal way to assign $N$ images to $K$ clusters while keeping them perfectly balanced is a classic Optimal Transport problem. Doing this naively for millions of images is computationally prohibitive. The authors solve this bottleneck by utilizing a fast variant of the Sinkhorn-Knopp algorithm. This turns the assignment problem into a simple matrix scaling task that can be solved on a GPU in just a few minutes.

Multiple Heads

An image can be categorized in many valid ways (e.g., by color, shape, or object type). To capture this, the model uses multiple "heads" to perform several different clustering tasks simultaneously, sharing the same underlying feature extractor.

Key Insights and Ideas

  • Information Theory Connection: The authors demonstrate that their method is mathematically equivalent to maximizing the Mutual Information between the data indices and the assigned labels.
  • Unified Objective: Unlike previous methods that bolted clustering onto a network as an afterthought, SeLa optimizes the same loss function for both the network weights and the labels. This provides much stronger convergence guarantees.
  • Label Transferability: One of the most surprising findings is that labels generated by a deep network (like ResNet-50) can be used to train a shallower network (like AlexNet) from scratch. The target network achieves nearly the same performance as if it had been part of the original self-labelling process.
Label transferability results demonstrating that labels generated by a ResNet-50 can effectively train an AlexNet.
  • Robustness to Imbalance: Even though the method assumes clusters are equal in size—which is rarely true for real-world data—it still performs remarkably well on imbalanced datasets, acting as a form of regularization.

Key Results

The model was evaluated across standard benchmarks including ImageNet (LSVRC-12), CIFAR-10/100, SVHN, PASCAL VOC, and MIT Places.

  • State-of-the-Art on ImageNet: Using linear probes, their ResNet-50 achieved 61.5% Top-1 accuracy, significantly outperforming previous clustering methods. This massive jump is largely attributed to the use of multiple heads ($T=10$).
Ablation on the number of heads (T) showing ResNet-50 reaching 61.5% Top-1 accuracy.
  • AlexNet Breakthrough: Their self-supervised AlexNet achieved 59.2% mAP on PASCAL VOC detection. This is a milestone, as it finally surpasses the 59.1% achieved by an AlexNet trained with human-provided ImageNet labels.
  • Small Dataset Dominance: On CIFAR-10, SeLa outperformed the previous best unsupervised method by 5.8%, proving the method scales down just as effectively as it scales up.

Limitations and Future Work

While SeLa is a major step forward, it has a few limitations:

  • The Equipartition Assumption: The "equal cluster size" constraint prevents degeneracy, but it is a weak assumption for real-world data where some categories are naturally much more common than others. Future work could explore more flexible distribution constraints.
  • Hyperparameter Sensitivity: Performance is tied to the number of clusters ($K$) and the number of heads ($T$). Finding the "optimal" number of categories for the entire world of images remains an open question.
  • Computational Overhead: While Sinkhorn-Knopp is fast, it still requires a full pass over the dataset to periodically re-assign labels, adding to the total training time compared to simpler pretext tasks.

Summary updated

Abstract

We propose a self-supervised learning formulation that simultaneously learns feature representations and useful dataset labels by optimizing the common cross-entropy loss for features _and_ labels,...
BibTeX
@inproceedings{asano2020self,
  author = {Yuki Markus Asano and Christian Rupprecht and Andrea Vedaldi},
  title = {{Self-labelling via simultaneous clustering and representation learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=pdiEz6yAMVX},
}
Figure