Self-labelling via simultaneous clustering and representation learning

Yuki Markus Asano, Christian Rupprecht, Andrea Vedaldi

Abstract: Combining clustering and representation learning is one of the most promising approaches for unsupervised learning of deep neural networks. However, doing so naively leads to ill posed learning problems with degenerate solutions. In this paper, we propose a novel and principled learning formulation that addresses these issues. The method is obtained by maximizing the information between labels and input data indices. We show that this criterion extends standard crossentropy minimization to an optimal transport problem, which we solve efficiently for millions of input images and thousands of labels using a fast variant of the Sinkhorn-Knopp algorithm. The resulting method is able to self-label visual data so as to train highly competitive image representations without manual labels. Our method achieves state of the art representation learning performance for AlexNet and ResNet-50 on SVHN, CIFAR-10, CIFAR-100 and ImageNet and yields the first self-supervised AlexNet that outperforms the supervised Pascal VOC detection baseline. Code and models are available.

Introduction

Unsupervised representation learning aims to extract meaningful features from data without human-provided labels. One promising direction is combining clustering with representation learning. However, naive implementations often suffer from degenerate solutions where the model collapses into a single cluster—assigning every image to the same label to technically minimize loss without learning useful features. This paper introduces SeLa (Self-Labelling), a principled formulation that avoids such collapse by framing label assignment as an optimal transport problem.

Methodology

SeLa treats unsupervised learning as a simultaneous clustering and representation learning problem. To prevent degenerate solutions, the authors enforce an equipartition constraint, requiring every pseudo-label to be assigned to an equal number of images. This constraint transforms the label assignment into an optimal transport problem, which is solved efficiently using a fast variant of the Sinkhorn-Knopp algorithm. This allows for re-labelling the entire ImageNet dataset in approximately two minutes on a single GPU.

The training process alternates between two phases:

  1. Representation Learning: Updating network weights using standard cross-entropy loss with fixed pseudo-labels.
  2. Self-Labelling: Updating pseudo-labels using the Sinkhorn-Knopp algorithm while keeping the network weights fixed.

Furthermore, the method employs multiple "clustering heads" ($T$) to allow the network to capture diverse data features simultaneously (e.g., focusing on color vs. shape).

Experimental Results

The authors evaluated SeLa on ImageNet using standard linear probes. As shown in Table 3, increasing the number of heads significantly improves performance, with a ResNet-50 reaching a state-of-the-art 61.5% Top-1 accuracy.

Table 3: Performance improvement with multiple clustering heads.

Notably, SeLa produced the first self-supervised AlexNet to outperform its supervised counterpart on the Pascal VOC object detection task (59.2% vs 59.1% mAP), breaking a long-standing performance ceiling for self-supervised methods on this architecture.

Key Insights

A significant finding of this work is the high quality and transferability of the discovered pseudo-labels. Labels generated by a ResNet-50 can effectively train an AlexNet from scratch, as shown in Table 5. This suggests that the self-discovered labels capture fundamental visual structures comparable to human annotations.

Table 5: Transferability of pseudo-labels across different architectures.

From an information-theoretic perspective, the authors demonstrate that minimizing cross-entropy under an equipartition constraint is equivalent to maximizing the mutual information between data indices and labels. This provides a solid theoretical foundation for the method's success, showing that the constraint acts as a powerful regularizer that forces the network to find subtle differences between images.

Conclusion

SeLa provides a robust and efficient framework for self-supervised learning by bridging the gap between clustering and classification. While the equipartition constraint acts as a powerful regularizer, future work may explore how to adapt the method to naturally imbalanced real-world datasets. Combining SeLa with other self-supervised signals, such as data augmentation invariance, remains a promising avenue for further performance gains.

Summary updated

Abstract

Combining clustering and representation learning is one of the most promising approaches for unsupervised learning of deep neural networks. However, doing so naively leads to ill posed learning problems with degenerate solutions. In this paper, we propose a novel and principled learning formulation that addresses these issues. The method is obtained by maximizing the information between labels and input data indices. We show that this criterion extends standard crossentropy minimization to an optimal transport problem, which we solve efficiently for millions of input images and thousands of labels using a fast variant of the Sinkhorn-Knopp algorithm. The resulting method is able to self-label visual data so as to train highly competitive image representations without manual labels. Our method achieves state of the art representation learning performance for AlexNet and ResNet-50 on SVHN, CIFAR-10, CIFAR-100 and ImageNet and yields the first self-supervised AlexNet that outperforms the supervised Pascal VOC detection baseline. Code and models are available.
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