Source-linked AI summary
Self-labelling via simultaneous clustering and representation learning
Yuki Markus Asano, Christian Rupprecht, Andrea Vedaldi
TL;DR
Naive joint clustering and representation learning can produce degenerate solutions, so the paper develops a principled self-labelling formulation. It imposes equipartition through an information-maximizing optimal-transport assignment solved with a fast Sinkhorn-Knopp method, achieving state-of-the-art representation learning across several benchmarks.
Problem
Naively jointly optimizing unsupervised labels and a representation leads to a degenerate solution in which all data points receive one label.
Method
The method constrains labels to equipartition the data, maximizing information between indices and labels and solving the resulting optimal-transport assignment approximately with fast Sinkhorn-Knopp iterations.
Results
The method achieves state-of-the-art representation learning on SVHN, CIFAR-10/100, and ImageNet for AlexNet and ResNet-50.
Takeaways & Limitations
The resulting self-labels can train features for new architectures using simple cross-entropy training without manual labels.
Takeaways & Limitations
The formulation assumes cluster sizes can be made equal, with a relaxed floor-based constraint when K does not divide N exactly.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
The paper addresses degenerate, ill-posed combinations of clustering and representation learning by introducing a principled self-labelling formulation. It uses equipartition-constrained label assignment, solved as scalable optimal transport, and reports state-of-the-art representation learning results.
- Self-supervised learning uses raw data to construct pretext tasks whose learned representations can transfer to useful applications.
- Standard supervised classification remains at least as effective as self-supervised pretext tasks when suitable labels are available, motivating automatic label discovery.
- Naively combining cross-entropy training with K-means clustering has degenerate solutions and lacks an overall optimization objective.
- The proposed formulation minimizes one cross-entropy loss while learning the network and estimating labels, avoiding the technical shortcoming of prior combinations.
- Equipartitioned labels maximize information between data indices and labels, transforming label assignment into an optimal transport problem.
- A fast Sinkhorn-Knopp variant approximately solves the transport problem for millions of data points and thousands of labels using matrix-vector algebra.
- Extensive experiments report significantly better results than DeepCluster and state-of-the-art representation learning performance across the evaluated settings.
2 RELATED WORK
The paper situates its method within self-supervised representation learning and pseudo-labelling approaches. Its contribution combines extracting pseudo-labels from raw data with standard cross-entropy training.
- The related work covers self-supervised representation learning and training deep networks with pseudo-labels assigned to images.
- Self-supervised representation learning avoids manual annotations through proxy tasks such as in-painting, jigsaw puzzles, clustering, colorization, and generation.
- Pseudo-labelling methods range from assigning unique labels to using flexible cluster labels learned with K-means, mutual information, or noise.
- The paper’s contribution combines a novel pseudo-label extraction procedure from raw data with deep-network training using standard cross-entropy loss.
3 METHOD
The method jointly learns representations and labels by minimizing one cross-entropy objective while constraining assignments to partition data uniformly. Label optimization becomes an optimal transport problem, enabling scalable alternating representation learning and self-labelling while maximizing mutual information between labels and data indices.
- Unsupervised cross-entropy minimization alone assigns every data point to one arbitrary label, producing a degenerate solution.
- The formulation constrains each data point to one label while splitting the dataset uniformly among classes.This equipartition constraint prevents the trivial all-in-one-cluster assignment.
- The label-assignment problem is an optimal transport problem solvable in polynomial time, with a continuous relaxation that still produces integral solutions.The transport formulation uses a probability matrix with prescribed row and column marginals.
- A fast Sinkhorn-Knopp variant makes the transport step practical for millions of data points and thousands of classes.Each update costs O(NK), the method scales linearly with the number of images, and ImageNet convergence takes about 2 minutes on a GPU.
- The algorithm alternates cross-entropy representation learning with transport-based self-labelling, and both steps optimize the same objective.This shared objective provides convergence to a local optimum, unlike the cited DeepCluster formulation.
- Minimizing the constrained cross-entropy is equivalent to maximizing mutual information between labels and data indices.The equipartition condition makes label and index marginal entropies constant, yielding this interpretation.
4 EXPERIMENTS
The experiments evaluate SeLa through ablations, architecture comparisons, transfer tests, and benchmarks ranging from small datasets to ImageNet and downstream PASCAL VOC tasks. Across these settings, SeLa is competitive or superior, with performance depending on clustering heads, self-labelling frequency, and cluster count.
- Evaluation protocol: SeLa is evaluated with linear probes on ImageNet and transferred features on MIT Places, using standard self-supervised-learning benchmarks.Linear classifiers are trained on frozen representations from intermediate convolutional blocks.
- Ablations: Increasing clusters from 1k to 3k improves results, while larger numbers slightly reduce quality.The cluster count K is one of the key configuration choices evaluated.
- Ablations: +2% for AlexNet and +10% for ResNet result when increasing clustering heads from T = 1 to T = 10.The more expressive ResNet benefits more from the diverse training signal.
- Ablations: Self-labelling is essential, with the best performance occurring around 80 self-labelling optimizations across 160 representation-learning epochs.The ablation varies the number of self-labelling steps from zero to once per representation-learning epoch.
- Architectures: SeLa works across smaller and larger architectures, including AlexNet variants and ResNet-50, while remaining applicable where some competing methods are unsuitable.The experiments compare AlexNet configurations with ResNet-50 and report good performance for all cases.
- Label transfer: SeLa labels can retrain AlexNet from scratch with a shorter 90-epoch schedule while achieving the same final accuracy.This indicates that the final label assignment, rather than joint label-and-representation learning, determines the learned representation quality in this experiment.
- Small-scale datasets: SeLa consistently outperforms previous state-of-the-art methods by around 2% with weighted kNN across CIFAR-10, CIFAR-100, and SVHN.The small-dataset evaluation uses a 128-dimensional embedding for weighted kNN.
- ImageNet and Places: On ImageNet and Places, SeLa outperforms DeepCluster and Local Aggregation across layers, while its [3k × 10]−+Rot configuration reaches state-of-the-art AlexNet performance.The reported ImageNet gap is 1.3% to the previous best, and the transferred Places result surpasses the supervised baseline by 1.7%.
5 CONCLUSION
SeLa is a clustering-based self-supervised feature-learning method that jointly optimizes feature learning and clustering through a shared objective. An equal-sample-per-cluster constraint enables efficient label assignment with modified Sinkhorn-Knopp optimization, yielding state-of-the-art results across several benchmarks and architectures.
- SeLa combines clustering with deep feature learning while optimizing the same objective during both stages.
- An equal-sample-per-cluster constraint enables the label-assignment step to be solved efficiently with a modified Sinkhorn-Knopp algorithm.
- SeLa achieves state-of-the-art self-supervised representation learning on SVHN, CIFAR-10/100, and ImageNet with AlexNet and ResNet-50.
- The resulting self-labels can train features for new architectures quickly using standard cross-entropy training.
A.1 IMPLEMENTATION DETAILS
The implementation trains self-supervised models with SGD, scheduled learning-rate drops, repeated pseudo-label optimization, and standard augmentations. Comparisons require caution because prior work uses different evaluation setups.
- Pseudo-label optimization is distributed logarithmically across training, with optimization times expressed as fractions of total epochs.The number of optimizations is user-defined, and Sinkhorn-Knopp uses λ = 25.
- Training uses randomly resized crops, horizontal flips, and added noise as standard data augmentations.
- Comparisons across publications should be interpreted cautiously because prior work uses several slightly different experimental setups.
- Retraining with transferred labels permits heavier augmentation, which improves ImageNet performance but slightly reduces Places performance.
A.2 FURTHER DETAILS
Additional analyses examine clustering quality, pseudo-label evolution, learned filters, and evaluation visualizations. The results indicate early learning, continuously improving pseudo-label accuracy, and structured visual features.
- Most clustering learning occurs in the early epochs, with final NMI reaching around 66%.Pseudo-label accuracies continue rising without overfitting as labels are periodically updated and data augmentation is used.
- Clustering metrics compare learned assignments with ImageNet validation ground-truth labels using adjusted NMI, adjusted Rand Index, and default NMI.
- Learned first-layer filters include Gabor-like edge detectors, color blobs, and dot detectors.
- Pseudo-label entropy changes from high initial entropy around 6 to a broad final spectrum, including values as low as 0.07 and a mean near 4.2.
- The appendix reports pseudo-label accuracies over training time and visualizations of first convolutional layers for AlexNet and ResNet-50.
A.3 COMPLETE TABLES
The appendix provides complete related-work tables and detailed linear-evaluation tables for AlexNet and ResNet. These tables specify layer-wise or global-feature evaluation conventions and comparison annotations.
- The appendix includes the unabridged tables containing all related work.
- AlexNet linear evaluation trains classifiers on downsampled activations from each pretrained layer and marks best and second-best results.The table also identifies larger AlexNet variants, transferred labels, RotNet retraining, and additional augmentation settings.
- ResNet linear evaluation trains a linear layer on globally average-pooled features using a single centered crop.Larger architectures and methods using supervised-learned augmentation policies are separated or marked.
A.4 LOW ENTROPY PSEUDOCLASSES
The figures visualize validation and training images assigned to the lowest-entropy pseudoclasses using ResNet-50. Training images are framed by their true labels, while validation samples correspond to the same training-set pseudoclasses.
- Random training-set images from the lowest-entropy pseudoclasses are visualized with ResNet-50.The visualization uses 3k × 1.
- True image labels are shown as randomly colored frames around the training images.Entropy is computed from the true image labels.
- Validation-set samples are drawn from the lowest-entropy pseudoclasses identified on the training set.Classes with fewer than 9 images are sampled with repetition.
A.5 RANDOM PSEUDOCLASSES
The figures visualize training and validation images assigned to random pseudoclasses using ResNet-50. Training images show true-label entropy through randomly colored frames, and validation classes with fewer than 9 images are sampled repeatedly.
- Random training-set images associated with random pseudoclasses are visualized using ResNet-50.The visualization uses 3k × 1.
- True image labels are represented by randomly colored frames around the training images.The entropy is given by the true image labels.
- Validation-set images associated with random pseudoclasses are sampled for visualization.Classes with fewer than 9 images are sampled with repetition.