Converge to Surprise: Evolutionary Self-supervised Image Clustering
July 08, 2026
Abstract
Most self-supervised image clustering models, actually almost all deep learning approaches, are based on gradient descent: In order to calculate the loss, every optimization step requires a clearly defined target, whether a contrastive split, a masked patch or entity, an EMA-teacher output, a pseudo-label, or a differentiable information-theoretic functional. We propose a self-supervised framework that drops this requirement for image clustering. Without any prior knowledge, we have to assume that each pixel is i.i.d.according to the Principle of Maximum Entropy. Taking this as our null hypothesis \(\mathcal{H}_0\), we define a ‘surprise score’ that measures how unlikely the model’s output representation would be under \(\mathcal{H}_0\). Maximizing the surprise score forces the deep learning model to reject \(\mathcal{H}_0\) — equivalently, to discover non-random feature from data. Also, here is our fundamental assumption: a surprise score cannot, in general, be reduced to a per-step loss. Hence, we propose the ‘converge-to-surprise’ scheme to optimize our model: an evolution-strategy (ES) outer loop, which directly maximizes the surprise score without needing its gradient, paired with a periodic gradient-descent inner loop, which uses the surprising clusters already discovered by ES as surrogate targets. On standard image benchmarks, our framework achieves new state-of-the-art results in non-parametric self-supervised image clustering — the strictest deep-clustering setting, in which the number of ground-truth classes is not given to the model.
1 Introduction↩︎
Self-supervised image clustering aims at grouping unlabeled images into distinct, semantically meaningful categories without human intervention [1], [2]. This is achieved by unifying self-supervised representation learning and unsupervised clustering into a cohesive pipeline [3], [4].
A long line of work has approached this problem with different efforts: Patch-arrangement methods aim at predicting structural corruptions: solving a jigsaw puzzle on permuted patches [5], predicting which rotation has been applied to the input [6], or predicting the relative position of two cropped patches [7]. Contrastive learning pulls together two augmented views of the same image, and pushes apart views from different images [1], [8]. Masked autoencoders reconstruct a randomly masked portion in the pixel space [2]. Deep clustering methods alternatively train the deep network by current pseudo-labels obtained from clustering, and re-cluster the output features [3], [9]. Self-distillation methods train a student network to match the output of a teacher, whose weights are an exponential moving average of the student’s [4], [10]. Latent-space prediction methods, in the joint-embedding-predictive-architecture family, predict the embedding of one part of an image from the embedding of another [11]. Information-theoretic methods optimize differentiable surrogates for mutual information between views or for de-correlation across feature dimensions [12]–[15].
All these methods share one commonness: they are gradient-descent methods, or loss-based methods. Each optimization step requires a clearly defined target — a contrastive positive-negative split, a masked patch in pixel or latent space, a surrogate output from an EMA-updated teacher, a pseudo-label from clustering or from spatial-arrangement analysis, or a differentiable information-theoretic functional — to serve as the loss function.
Then, back propagation [16] makes it extraordinarily efficient to optimize the deep network when such a per-step loss is present. However, like every advantage has its cost, the disadvantage of gradient-descent approach is that: The deep network will not be able to discover representations which cannot be reduced to a per-step loss.
This paper works on such a case. Our self-supervised learning framework aims at discovering non-randomness from images. Without any prior knowledge, the Principle of Maximum Entropy [17] forces the most conservative assumption — pixels are i.i.d.random noise. We take this assumption as our null hypothesis \(\mathcal{H}_0\), and define a surprise score that measures how unlikely the model’s output representation would be under \(\mathcal{H}_0\). The higher the surprise score, the less plausible \(\mathcal{H}_0\) becomes. Thus, maximizing the surprise score forces the model to reject the null hypothesis \(\mathcal{H}_0\). Equivalently, this makes the model extract meaningful information, or non-randomness, from images, which is finally used for clustering.
Then, we propose another fundamental assumption of this paper: a surprise score cannot, in general, be reduced to a per-step loss. Although proving this assumption is beyond our scope, detailed analysis is provided.
Accordingly, we propose converge-to-surprise to optimize the deep network when a per-step loss is not present: We combine an evolution-strategy (ES) [18] outer loop, which maximizes the surprise score without needing its gradient, with a periodic gradient-descent inner loop, which uses the surprising clusters already discovered by ES as surrogate targets. Experiments on several benchmark datasets show that our scheme achieves new state-of-the-art results in non-parametric self-supervised image clustering — the strictest deep-clustering scenario, in which case the number of ground-truth classes is not given to the model.
Here are our contributions:
We define a surprise score that measures how surprising, or how non-random, the outputs of a deep network are, under the random noise null hypothesis. We show in Section 3.2 that our surprise score is naturally against representation collapse. In addition, we propose a fundamental assumption: a surprise score cannot, in general, be reduced to a per-step loss function.
We propose converge-to-surprise, a hybrid optimization scheme that combines evolution strategy with gradient-descent training to maximize the surprise score.
On benchmark datasets, models trained from scratch using our framework achieve new state-of-the-art results in non-parametric self-supervised image clustering – the strictest deep-clustering setting.
The remainder of the paper is organized as follows: Section 2 surveys related work in self-supervised image clustering. Section 3 describes the converge-to-surprise framework, including our complementary masking strategy, the surprise score, and the optimization scheme. Section 4 reports experimental results, and Section 5 concludes. Also, we insist people to read our discussions in appendix 6.
2 Related Work↩︎
We organize related self-supervised image clustering methods by what the network outputs and how that output becomes a cluster assignment at test time. This split mirrors the experimental protocol of Section 4.
2.1 Self-supervised embedding learning↩︎
Most self-supervised image clustering methods produce a dense feature embedding in \(\mathbb{R}^d\), which is further clustered or linearly probed at test time. These span contrastive methods (SimCLR [1], MoCo [8]), self-distillation (BYOL [10], DINO [4]), latent-space prediction (I-JEPA [11]), masked autoencoders [2], information-theoretic objectives (Barlow Twins [12], VICReg [13], Deep InfoMax [14]), and pseudo-label clustering (DeepCluster [3], SwAV [9]). They differ in the training signal but agree on the output: a continuous embedding, not a hard cluster assignment.
These approaches first apply a deep encoder that maps images to a continuous embedding space. Then, a shallow decoder (usually a multi-layer perceptron [19]) maps the embedding to the output representation. The decoder is usually abandoned after training. In test time, classification is made based on nearest-neighbor evaluation [20] or fine-tuned linear projections using the embeddings [3]. This is the most dominant yet mildest setting: The network is not required to produce hard representations of the image, only an embedding that captures semantic meaning.
2.2 Parametric hard deep clustering↩︎
A second family trains the network to output a cluster index directly: each input is mapped to one of \(K\) discrete classes, with \(K\) specified in advance. At evaluation, predicted clusters are matched to ground-truth labels by the Kuhn-Munkres (Hungarian) linear-assignment algorithm [21]. DEC [22] sharpens a soft assignment over \(K\) centroids, and DAC [23] recasts clustering as pairwise same/different binary classification on image pairs. Closest to our framework is IIC [15], which maximizes softmax mutual information (MI) between cluster predictions on two augmented views in a single end-to-end loss. However, we use cluster co-occurrence counts from disjoint views as the ‘surprise score’ in place of softmax MI. Also, unlike IIC, our framework does not need to know \(K\) in ahead.
2.3 Non-parametric hard deep clustering↩︎
The third family does not fix \(K\) in advance. This is the strictest match to the truly unsupervised regime and the setting for which we report results. DeepDPM [24] adapts the clustering head dynamically via split/merge operations inspired by Dirichlet-Process Gaussian-Mixture Models, growing or shrinking the active component count during training. UNSEEN [25] wraps deep-clustering backbones (DCN [26], DEC [22], DKM [27]) in a ‘dying clusters’ mechanism: training starts from an upper bound \(K_{\max}\), and unused clusters atrophy. The deep Dirichlet Process Mixture (DPM) model of [28] combines a flow-based generative network with Gibbs sampling over an infinite-component DPM prior. Two classical non-deep clusterers also appear as comparators on top of learned features: moVB [29], a memorized online variational-Bayes scheme for DPM inference; DBSCAN [30], density-based non-parametric clustering.
3 Main Theory↩︎
In this section, we introduce converge-to-surprise, a framework for non-parametric self-supervised image clustering. We first introduce our complementary masking strategy, based on which the surprise score is calculated. Then, we describe our hybrid optimization scheme combining evolution strategy with gradient-descent training.
3.1 Complementary masking strategy↩︎
Suppose we have a distribution \(\mathbf{P}\) producing images of shape \((H, W, C)\). That is, \(\mathbf{X} \sim \mathbf{P}\) with \(\mathbf{X} \in \mathbb{R}^{H, W, C}\). In a self-supervised learning scenario, we have no annotated samples or prior knowledge about \(\mathbf{P}\). According to the Principle of Maximum Entropy [17], we have to assume that each pixel \((h,w)\) in \(\mathbf{X}\) is independent of every other; In other words, we have to assume that \(\mathbf{P}\) is the maximum-entropy distribution over \(\mathbb{R}^{H, W, C}\), producing totally random noise. This is our null hypothesis \(\mathcal{H}_0\).
Then, given a sampled image \(\mathbf{X} \sim \mathbf{P}\) with \(\mathbf{X} \in \mathbb{R}^{H, W, C}\), we partition its \(H \times W\) pixel grid into two disjoint subsets using a chessboard pattern. Let \[\begin{align} \mathcal{I} &= \{(h, w) : (h + w) \bmod 2 = 0\}, \\ \mathcal{J} &= \{(h, w) : (h + w) \bmod 2 = 1\} \end{align}\] denote the white and black chessboard positions, respectively. Let \(\mathbf{M}^{(\mathcal{I})}, \mathbf{M}^{(\mathcal{J})} \in \{0, 1\}^{H, W}\) be the corresponding binary masks, defined by \(\mathbf{M}^{(\mathcal{I})}_{h, w} = \mathbf{1}\!\left[(h + w) \bmod 2 = 0\right]\) and \(\mathbf{M}^{(\mathcal{J})} = \mathbf{1} - \mathbf{M}^{(\mathcal{I})}\), where \(\mathbf{1}[\cdot]\) is the indicator function [31]. Applying these masks pixel-wise to \(\mathbf{X}\), we obtain two complementary masked views of the same image: \[\mathbf{X}^{(i)} = \mathbf{X} \odot \mathbf{M}^{(\mathcal{I})}, \quad \mathbf{X}^{(j)} = \mathbf{X} \odot \mathbf{M}^{(\mathcal{J})},\] where \(\odot\) denotes element-wise multiplication. The \(i\)-side view \(\mathbf{X}^{(i)}\) retains only the pixels at white chessboard positions and zeros out the rest, while the \(j\)-side view \(\mathbf{X}^{(j)}\) retains only those at black positions. By construction, every pixel of \(\mathbf{X}\) appears in exactly one of the two views, and the two views share no pixel in common. Figure 1 shows our masking strategy on an MNIST image [32].
As mentioned, the null hypothesis \(\mathcal{H}_0\) assumes pixels of \(\mathbf{X}\) to be independent of one another. Since \(\mathbf{X}^{(i)}\) and \(\mathbf{X}^{(j)}\) share no common pixel, they are themselves independent tensors and therefore share no mutual information [33]. In addition, applying data augmentation [34] independently on \(\mathbf{X}^{(i)}\) and \(\mathbf{X}^{(j)}\) will not break this zero-mutual-information statement. We use \(\tilde{\mathbf{X}}^{(i)}\) and \(\tilde{\mathbf{X}}^{(j)}\) to denote the augmented views. Therefore, we have: \[\label{null95to95mutual95info} \mathcal{H}_0 \;\Longrightarrow\; I\!\left(\tilde{\mathbf{X}}^{(i)} \,;\, \tilde{\mathbf{X}}^{(j)}\right) = 0.\tag{1}\] Here, \(I(\cdot \,;\, \cdot)\) denotes the mutual-information functional.
If formula 1 is rejected, then the null hypothesis \(\mathcal{H}_0\) cannot be true. This will be our approach to reject \(\mathcal{H}_0\).
3.2 Cluster co-occurrence as a surprise score↩︎
Again, given an image \(\mathbf{X} \sim \mathbf{P}\), we obtain the two complementary masked and independently augmented views \(\tilde{\mathbf{X}}^{(i)}\) and \(\tilde{\mathbf{X}}^{(j)}\). Then, a deep learning model \(f_\theta : \mathbb{R}^{H \times W \times C} \to \mathbb{R}^{K}\) assigns each view to one of \(K\) candidate clusters, according to the argmax dimension in its output logits: \[\hat{y}^{(i)} = \arg\max_{k}\bigl[f_\theta(\tilde{\mathbf{X}}^{(i)})\bigr]_k, \quad \hat{y}^{(j)} = \arg\max_{k}\bigl[f_\theta(\tilde{\mathbf{X}}^{(j)})\bigr]_k. \label{eq:argmax95logit}\tag{2}\]
Both \(\hat{y}^{(i)}\) and \(\hat{y}^{(j)}\) take values in \(\{0, 1, \ldots, K-1\}\). Because each \(\hat{y}^{(\cdot)}\) is a deterministic function of the corresponding view, the data-processing inequality [35] gives \(I(\hat{y}^{(i)};\,\hat{y}^{(j)})\le I\!\left(\tilde{\mathbf{X}}^{(i)} \,;\, \tilde{\mathbf{X}}^{(j)}\right) = 0\) under \(\mathcal{H}_0\). That says, the cluster pseudo labels from \(i\)-side and \(j\)-side are statistically independent.
Then, given \(N\) images \(\{\mathbf{X}_1, \dots, \mathbf{X}_N\}\) sampled i.i.d.from \(\mathbf{P}\), we obtain their complementary masked and independently augmented views \(\{\tilde{\mathbf{X}}_1^{(i)}, \dots, \tilde{\mathbf{X}}_N^{(i)}\}\) and \(\{\tilde{\mathbf{X}}_1^{(j)}, \dots, \tilde{\mathbf{X}}_N^{(j)}\}\), respectively. We implement our model \(f_\theta\) on each view and obtain the predicted cluster, leading to two integer sequences of length \(N\): \[\mathrm{seq}^{(i)} = \bigl(\hat{y}_1^{(i)}, \dots, \hat{y}_N^{(i)}\bigr), \quad \mathrm{seq}^{(j)} = \bigl(\hat{y}_1^{(j)}, \dots, \hat{y}_N^{(j)}\bigr).\]
In fact, we implicitly assume that the distributions of nearby pixels in an original image \(\mathbf{X}\) are almost identical, although pixels are assumed to be i.i.d.under \(\mathcal{H}_0\). Hence, after chessboard masking, \(\mathbf{X}^{(i)}\) and \(\mathbf{X}^{(j)}\) will have identical distribution; after independent augmentation with the same hyper-parameter, \(\tilde{\mathbf{X}}^{(i)}\) and \(\tilde{\mathbf{X}}^{(j)}\) will also have identical distribution. Thus, although statistically independent, \(\mathrm{seq}^{(i)}\) and \(\mathrm{seq}^{(j)}\) will have identical distribution as well under \(\mathcal{H}_0\).
For each cluster \(k \in \{0, 1, \dots, K-1\}\), let \(n_k^{(i)}\) be the number of times \(k\) appears in \(\mathrm{seq}^{(i)}\), and define \(n_k^{(j)}\) analogously. Then, the empirical marginal probability of clustering a view (either \(i\)-side or \(j\)-side) to cluster \(k\) is \[p_k \;=\; (n_k^{(i)} + n_k^{(j)})\;/\;(2N).\]
Again, since \(\mathrm{seq}^{(i)}\) and \(\mathrm{seq}^{(j)}\) are independent under \(\mathcal{H}_0\), the null probability that both views of one image are predicted to the same cluster \(k\) (i.e. \(\hat{y}_n^{(i)} = \hat{y}_n^{(j)} = k\) at any index \(n\)) is \(q_k \;=\; p_k \cdot p_k \;=\; p_k^{\,2}\). Hence, under \(\mathcal{H}_0\), the expected number of view matching at cluster \(k\) over the whole batch is \(N\cdot q_k\).
On the other hand, we denote the observed number of view matching at cluster \(k\) as \(t_k\), which is the actual count of indices \(n \in \{1, \dots, N\}\) for which \(\hat{y}_n^{(i)} = \hat{y}_n^{(j)} = k\).
Considering cluster \(k\) in isolation, \(t_k\) is then the number of successes in \(N\) independent Bernoulli trials, each with success probability \(q_k\) [36]. That is, \[t_k \;\sim\; \mathrm{Binomial}(N,\, q_k) \quad \text{under } \mathcal{H}_0.\] The \(K\) output dimensions are of course coupled: each view is predicted to exactly one cluster. So, the counts \(t_1, \dots, t_K\) are correlated. But this coupling has only a very weak effect on the distribution of any individual \(t_k\). Treating each \(t_k\) on its own as binomial is the form we will use throughout.
Then, we apply the binomial distribution formula [37]: \[\label{exact95prob95definition} \mathbb{P}_{\mathcal{H}_0}\!\left[t_k \text{ or more matches at } k\right] = \sum_{s=t_k}^{N} \binom{N}{s}\, q_k^{\,s}\,(1 - q_k)^{N - s}.\tag{3}\] The sum on the right is exact but awkward to compute. A standard Chernoff upper bound on the binomial upper tail [38] turns it into the compact inequality \[\label{prob95surprise} \mathbb{P}_{\mathcal{H}_0}\!\left[t_k \text{ or more matches at } k\right] \le \exp\bigl(-N\!\cdot\! D(\hat{q}_k \,\Vert\, q_k)\bigr),\tag{4}\] where \(D(\hat{q}_k \,\Vert\, q_k)\) is the binary Kullback–Leibler divergence [39] between the observed view-matching probability \(\hat{q}_k = t_k / N\) and the null probability \(q_k=p_k^{\,2}\): \[\label{surprise95score95k} D\!\left(\hat{q}_k \,\Vert\, q_k\right) \;=\; \hat{q}_k \log\frac{\hat{q}_k}{q_k} \;+\; (1-\hat{q}_k)\log\frac{1 - \hat{q}_k}{1 - q_k}.\tag{5}\]
After taking logarithm, formula 4 becomes \[\label{log95formula95surprise} -\log(\mathbb{P}_{\mathcal{H}_0}\!\left[t_k \text{ or more matches at } k\right]) \;\ge\; N\, D(\hat{q}_k \,\Vert\, q_k),\tag{6}\] where the left side is the amount of information, or level of surprise, we have by observing the view-matching result at cluster \(k\) [40]. So, the larger \(N\!\cdot\! D(\hat{q}_k \,\Vert\, q_k)\) is, the more surprising and unlikely the result can be under \(\mathcal{H}_0\). Removing \(N\), we call \(D(\hat{q}_k \,\Vert\, q_k)\) the surprise score at cluster \(k\).
Formula 6 shows the probability of observing \(t_k\) or more view matching at cluster \(k\) under the null hypothesis \(\mathcal{H}_0\). So, we will ignore the surprise score if \(\hat{q}_k < q_k\) for any cluster \(k\) (under-matching). Then, summing across all over-matching clusters, we define the surprise score \[\mathcal{S}(\theta) \;=\; \sum\nolimits_{k\,:\, \hat{q}_k > q_k} D\!\left(\hat{q}_k \,\Vert\, q_k\right). \label{eq:surprise}\tag{7}\]
\(\mathcal{S}(\theta)\) measures in total how strongly our model’s two-view labeling rejects \(\mathcal{H}_0\), or how surprising the view-matching results look like. To achieve a large \(\mathcal{S}(\theta)\), the model needs to discover reliable features shared by both views, which are essentially the meaningful information, or non-randomness, or surprise, in data distribution \(\mathbf{P}\). Hence, the optimization goal of our model is to maximize \(\mathcal{S}(\theta)\). We call this framework converge-to-surprise. Figure 2 briefly illustrates the pipeline of our framework.
If the argmax of all logit vectors collapse to one fixed dimension, then it is easy to see that \(\mathcal{S}(\theta)=0\). In contrast, if the pixels are really random noise, we can also have \(\mathcal{S}(\theta)\approx 0\) since the two views will be independent. Hence, maximizing \(\mathcal{S}(\theta)\) naturally prevents representation collapse. Also, the argmax operation makes \(\mathcal{S}(\theta)\) irrelative to \(K\), enabling non-parametric clustering. We admit that the argmax operation makes \(\mathcal{S}(\theta)\) non-differentiable to \(\theta\). This differs from the softmax mutual information maximization in IIC [15], which is differentiable end-to-end, yet parametric (requiring \(K=\) the number of classes). To some extent, one can say that non-differentiability is our trade-off to non-parametric.
More fundamentally, in one optimization step, any loss function \(\mathcal{L}(f_\theta(\cdot), y)\) requires a clearly defined target \(y\) toward which gradient descent pushes \(f_\theta(\cdot)\). We have no such \(y\) originally in our approach: we do not know in advance which cluster \(k\) each masked image should be assigned to, nor which cluster \(k\) will eventually carry meaningful view-matching result. There is no per-step target for gradient descent to chase.
Moreover, \(\mathcal{S}(\theta)\) defined in this subsection is only one way to observe the output representation of a model. In fact, there can be numerous types of output representations (multiple logit vectors, dense output representations from a vision transformer [41], etc); and there can be numerous ways to observe whether a model’s output representation rejects the random noise null hypothesis. This leads to numerous ways to define a surprise score. Thus, we propose another fundamental assumption in this paper: a surprise score cannot, in general, be reduced to a per-step loss.
Although proving this assumption is beyond our scope, here is our intuition: We have the ultimate goal as discovering meaningful information, or non-randomness, or surprise, from the data distribution. But there is no guarantee that we always have a clear target in every step. We believe this is a more general learning scenario than what gradient decent is usually applied to. Therefore, we essentially rely on evolution strategy to deal with this scenario.
3.3 Optimization↩︎
3.3.0.1 Evolution strategy.
We maximize the surprise score \(\mathcal{S}(\theta)\) with the evolution strategy (ES) described in [18], treating \(\mathcal{S}(\theta)\) as the fitness score of a black-box optimization problem over the model’s flat parameter vector \(\theta \in \mathbb{R}^{D}\).
At each ES step, we sample a population of \(m\) perturbed parameter vectors around the current \(\theta\). To be specific, we split the population into \(m/2\) mirrored pairs: For each pair, we draw \(\epsilon_i \sim \mathcal{N}(0,\, \sigma^2 I_D)\), which forms two models with parameter \(\theta + \epsilon_i\) and \(\theta - \epsilon_i\), respectively. Here, \(\mathcal{N}(0,\, \sigma^2 I_D)\) is the \(D\)-dim Gaussian distribution with variance \(\sigma\) [42].
Given \(N\) images \(\{\mathbf{X}_n\}_{n=1}^N \sim \mathbf{P}\), we obtain the complementary masked and independently augmented views \(\{\tilde{\mathbf{X}}_n^{(i)}\}_{n=1}^N\) and \(\{\tilde{\mathbf{X}}_n^{(j)}\}_{n=1}^N\), which are shared across all models in all \(m/2\) pairs. We implement both models in each pair to obtain \(\mathcal{S}(\theta + \epsilon_i)\) and \(\mathcal{S}(\theta - \epsilon_i)\) for \(i=1,\cdots,m/2\). Then, we rank-shape [43] all \(m\) scores into centered ranks \(r_i \in [-\tfrac12, \tfrac12]\), and apply a weighted update to \(\theta\): \[\theta \;\leftarrow\; (1 - \eta\lambda)\,\theta \;+\; \frac{\eta}{m\sigma}\,\sum\nolimits_{i=1}^{m} r_i\,\epsilon_i. \label{eq:es-update}\tag{8}\] Here, \(\eta\) is the learning rate and \(\lambda\) is the weight decay rate.
Mirrored pairs, rank-shaping and weight-decay are commonly used tricks in deep evolution strategies [18], [43], [44]. More discussions can be found in [18].
3.3.0.2 Surrogate training using surprising results.
ES on its own is sufficient to discover clusters with surprising view-matching results. But it gives equal credit to every output dimension \(k\) contributing to \(\mathcal{S}(\theta)\), including tiny, noisy micro-clusters that share similar features with larger clusters. So, we first apply \(T_0\) epochs of pure ES optimization to warm-up, during which clusters with surprising view-matching results will emerge. Starting from epoch \(T_0+1\), we apply \(T_{1,a}\) epochs of gradient-descent training, followed by \(T_{1,b}\) epochs of ES optimization. They form a complete period with \(T_{1,a} + T_{1,b}\) epochs. We implement multiple such periods.
At the beginning of a gradient-descent training epoch, we identify the set of contributing positions among the sampled \(N\) original images \(\{\mathbf{X}_1, \dots, \mathbf{X}_N\}\): \[\mathcal{C} \!=\! \Bigl\{\! n \!\in\! \{1,\dots,N\}\!: \hat{y}_n^{(i)} = \hat{y}_n^{(j)} = k \;\text{and}\; D(\hat{q}_k \,\Vert\, q_k) \ge \tau \!\Bigr\}, \label{eq:contributing}\tag{9}\] where \(\hat{y}_n^{(i)} = \arg\max_k [f_\theta(\mathbf{X}_n^{(i)})]_k\) is the predicted cluster of the un-augmented view \(\mathbf{X}_n^{(i)}\) of the original image \(\mathbf{X}_n\), \(\hat{y}_n^{(j)}\) is obtained accordingly on the un-augmented view \(\mathbf{X}_n^{(j)}\), \(D(\hat{q}_k \,\Vert\, q_k)\) is the surprise score at cluster \(k\) defined in formula 5 , and \(\tau\) is a pre-defined threshold on the per-cluster surprise score. To be specific, we regard cluster \(k\) as surprising if \(D\!\left(\hat{q}_k \,\Vert\, q_k\right) \geq \tau\).
That says, \(n\) is a contributing position when both views of \(\mathbf{X}_n\) are predicted to the same cluster, and the view-matching result of the predicted cluster is surprising enough under \(\mathcal{H}_0\). We obtain \(\mathcal{C}\) on un-augmented views so that the predicted clusters are relatively deterministic.
Then, we group the original images at contributing positions by their predicted cluster: \[\mathcal{C}_k=\{\mathbf{X}_n: n \in \mathcal{C} \;\text{and} \;\hat{y}_n^{(i)} = k\}.\]
Given the per-cluster count \(n_k = |\mathcal{C}_k|\), let \(M\) be the median of \(\{n_k\}_{ D(\hat{q}_k \,\Vert\, q_k) \ge \tau}\). Then, within each \(\mathcal{C}_k\), we select \(\min(n_k,\, M)\) images uniformly without replacement: large clusters are sub-sampled down to \(M\) images, small clusters contribute all their images. Combining all selected images, we obtain a training set \(\mathcal{B}\) with no single dominant cluster.
For each selected image \(\mathbf{X}_n \in \mathcal{B}\), we use its predicted cluster \(\hat{y}_n^{(i)}\) as the surrogate label, denoted as \(\hat{y}_n\). We apply chessboard masking and independent augmentation again, to obtain new \(\tilde{\mathbf{X}}_n^{(i)}\) and \(\tilde{\mathbf{X}}_n^{(j)}\) from \(\mathbf{X}_n\). Finally, the model is trained by gradient descent via cross-entropy loss [45]: \[\mathcal{L}_\text{ft}(\theta) = \sum_{n \in \mathcal{B}} \Bigl[ \mathrm{CE}\bigl(f_\theta(\tilde{\mathbf{X}}_n^{(i)}),\, \hat{y}_n\bigr) + \mathrm{CE}\bigl(f_\theta(\tilde{\mathbf{X}}_n^{(j)}),\, \hat{y}_n\bigr) \Bigr].\]
In summary, when the optimization begins, we do not have a clear target (or loss) in each step. So, we just let the model evolve toward the ultimate goal (the surprise score). After enough epochs, we may see some promising output representations, which in our case are the clusters with surprising view-matching results. Then, we train the network using these clusters as surrogate labels to further strengthen, or reinforce, the discovered promising representations. Algorithm 3 summarizes the full optimization procedure.
The gradient-descent training uses surprising view-matching results already discovered by evolution strategy as surrogate targets. One cannot claim that the surprise score \(\mathcal{S}(\theta)\) can be reduced to a per-step loss, because of this.
4 Experiments↩︎
We evaluate our converge-to-surprise framework in non-parametric self-supervised image clustering, the strictest image clustering setting in which the number of ground-truth classes is not given to the model. We report results on three standard image benchmarks and compare against the leading non-parametric deep-clustering methods, DeepDPM [24] and UNSEEN [25].
4.1 Experimental setup↩︎
2ex -1em Network. Our model \(f_\theta\) is a ResNet-9 [46]: two convolutional stems [47], two residual blocks [46], an adaptive average-pooling layer, and a single linear head that returns a logit vector with dimension \(K=64\) . The cluster assignment of a view is the \(\arg\max\) over these logits. The output is \(\ell_2\)-normalized before the argmax. We set \(K=64\), far above the ten ground-truth classes of every dataset. Since the model is never told the true number of classes, \(K\) only acts as an upper bound. The number of active clusters is discovered during training. The same architecture is used for all datasets, with a single input channel for an image view.
2ex -1em Datasets. We use three handwritten-digit and fashion-item benchmarks, all with ten ground-truth classes. MNIST [32] contains 70k images of handwritten digits at \(28\times28\) resolution (10k for testing). Fashion-MNIST [48] matches MNIST in size and resolution but depicts ten clothing categories, and is substantially harder because several classes (e.g.pullover/coat/shirt) differ only in fine texture. USPS [49] contains \(7{,}291\) training and \(2{,}007\) test handwritten digits at a native \(16\times16\) resolution, and is notably class-imbalanced.
| MNIST | Fashion-MNIST | USPS | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 2-4(lr)5-7(lr)8-10 Method | NMI | ARI | ACC | NMI | ARI | ACC | NMI | ARI | ACC |
| DBSCAN [30] | \(92.0_{\pm0.0}\) | \(86.0_{\pm0.0}\) | \(89.0_{\pm0.0}\) | \(63.0_{\pm0.0}\) | \(32.0_{\pm0.0}\) | \(39.0_{\pm0.0}\) | \(72.0_{\pm0.0}\) | \(46.0_{\pm0.0}\) | \(57.0_{\pm0.0}\) |
| moVB [29] | \(93.0_{\pm0.0}\) | \(94.0_{\pm0.0}\) | \(97.0_{\pm0.0}\) | \(66.0_{\pm2.0}\) | \(47.0_{\pm3.0}\) | \(55.0_{\pm3.0}\) | \(87.0_{\pm2.0}\) | \(86.0_{\pm4.0}\) | \(90.0_{\pm4.0}\) |
| DPM Sampler | \(92.0_{\pm1.0}\) | \(91.0_{\pm4.0}\) | \(93.0_{\pm5.0}\) | \(67.0_{\pm1.0}\) | \(49.0_{\pm2.0}\) | \(59.0_{\pm3.0}\) | \(87.0_{\pm1.0}\) | \(82.0_{\pm2.0}\) | \(83.0_{\pm3.0}\) |
| DeepDPM [24] | \(94.0_{\pm0.0}\) | \(95.0_{\pm0.0}\) | \(98.0_{\pm0.0}\) | \(\mathbf{68.0_{\pm1.0}}\) | \(51.0_{\pm2.0}\) | \(62.0_{\pm3.0}\) | \(88.0_{\pm0.0}\) | \(86.0_{\pm1.0}\) | \(89.0_{\pm2.0}\) |
| UNSEEN+DCN [26] | \(87.8_{\pm1.9}\) | \(83.7_{\pm4.5}\) | \(86.0_{\pm5.4}\) | \(63.7_{\pm1.0}\) | \(46.9_{\pm1.5}\) | \(57.3_{\pm2.4}\) | \(76.5_{\pm1.4}\) | \(69.8_{\pm4.9}\) | \(77.5_{\pm5.6}\) |
| UNSEEN+DEC [22] | \(80.4_{\pm1.8}\) | \(70.9_{\pm3.5}\) | \(71.0_{\pm4.4}\) | \(58.6_{\pm2.6}\) | \(42.3_{\pm3.4}\) | \(54.4_{\pm3.8}\) | \(80.8_{\pm0.9}\) | \(75.9_{\pm2.4}\) | \(81.3_{\pm2.4}\) |
| UNSEEN+DKM [27] | \(84.2_{\pm2.6}\) | \(78.5_{\pm5.2}\) | \(83.0_{\pm5.5}\) | \(62.2_{\pm1.0}\) | \(43.9_{\pm1.4}\) | \(53.1_{\pm2.0}\) | \(73.3_{\pm5.3}\) | \(62.6_{\pm10.6}\) | \(71.5_{\pm9.4}\) |
| Ours (from scratch) | \(\mathbf{95.8_{\pm0.7}}\) | \(\mathbf{96.3_{\pm1.1}}\) | \(\mathbf{98.3_{\pm0.5}}\) | \(65.0_{\pm1.0}\) | \(\mathbf{52.9_{\pm1.9}}\) | \(\mathbf{64.1_{\pm1.9}}\) | \(\mathbf{90.2_{\pm1.3}}\) | \(\mathbf{90.3_{\pm2.8}}\) | \(\mathbf{94.9_{\pm1.8}}\) |
4.5pt
| Method | MNIST | Fashion-MNIST | USPS |
|---|---|---|---|
| DBSCAN [30] | \(9.0_{\pm0.0}\) | \(4.0_{\pm0.0}\) | \(6.0_{\pm0.0}\) |
| DPM Sampler | \(11.3_{\pm0.8}\) | \(12.4_{\pm1.0}\) | \(8.5_{\pm0.9}\) |
| moVB [29] | \(14.0_{\pm1.0}\) | \(16.9_{\pm2.3}\) | \(11.2_{\pm1.1}\) |
| DeepDPM [24] | \(10.0_{\pm0.0}\) | \(10.2_{\pm0.8}\) | \(9.2_{\pm0.4}\) |
| Ours | \(10.0_{\pm0.0}\) | \(11.6_{\pm0.5}\) | \(10.4_{\pm0.5}\) |
5pt
2ex -1em Data augmentation. After the chessboard masking of Section 3.1, the two complementary views of each image are augmented independently, preserving the zero-mutual-information property between two views under \(\mathcal{H}_0\). For MNIST and Fashion-MNIST, augmentations include random rotation, random cropping, and brightness/contrast jitter. Fashion-MNIST additionally applies a random horizontal flip. For USPS, we further introduce an anisotropic augmentation: We pad one randomly chosen axis (either height or length) with a black border. Then, we resize back the padded image to introduce vertical or horizontal deformation. This is motivated by the aspect-ratio variation of the dominant digit-0 class in USPS. To accommodate this anisotropic augmentation, other augmentations are kept milder on the USPS dataset. Full per-dataset augmentation parameters are listed in Table 4 in Appendix 7.
2ex -1em Optimization and protocol. We optimize \(\mathcal{S}(\theta)\) with the ES outer loop under a population size \(m=32\), interleaved with periodic gradient-descent training using the discovered surprising clusters. When identifying contributing positions according to formula 9 , we choose \(\tau=0.005\). For each dataset, we run five independent experiments from scratch and report the mean \(\pm\) standard deviation. At test time, only view-i (without augmentation) from chessboard masking on each test image is passed through the network, and assigned to its \(\arg\max\) cluster. The clustering results are then used in evaluations.
2ex -1em Training schedule. On MNIST and Fashion-MNIST, we use a two-stage training schedule: \(2000\) epochs of pure ES, followed by epochs \(2000\)–\(3000\) in which \(4\) gradient-descent training epochs are run every \(25\) ES epochs. On USPS we use a three-stage schedule: \(4000\) epochs of pure ES; then a weak stage over epochs \(4000\)–\(8000\), with \(2\) gradient-descent training epochs every \(500\) ES epochs; and finally a strong stage over epochs \(8000\)–\(9000\), with \(4\) gradient-descent training epochs every \(25\) ES epochs (identical to the other datasets). USPS is run for many more epochs because it has far fewer training images (\(7{,}291\) vs.\(70{,}000\)), so the model needs more epochs to evolve.
2ex -1em Batch size. The surprise score is calculated over a batch of \(N\) images at each ES step. We use \(N=3000\) for MNIST/Fashion-MNIST, and \(N=3650\) for USPS. The latter is chosen so that the \(7{,}291\) USPS training images are split into two nearly equal-sized steps per epoch (\(3650\) and \(3641\)). This matters because each ES updating direction is estimated from the statistics of its batch alone. Then, a last step with only a few images gives unreliable statistics, steering the evolution into a poorly-estimated direction. So, we choose \(N\) carefully to avoid this.
2ex -1em Metrics and baselines. Following the non-parametric clustering protocol, we report three standard metrics: clustering accuracy (ACC) under the Kuhn–Munkres assignment, Normalized Mutual Information (NMI), and the Adjusted Rand Index (ARI). For all three, higher is better, with more details introduced in [24]. We additionally report the inferred number of active clusters \(\hat{K}\) (ground truth \(K^\star=10\)). As for baselines, we use the scores reported by DeepDPM [24] – including the performances of DeepDPM itself, performances of the classical non-parametric clusterers DBSCAN [30], performances of a memorized variational DPM model called moVB [29], and performances of a DPM sampler. According to DeepDPM [24], all these models are based on pre-trained autoencoder features. Also, performances of the three UNSEEN variants [25] (UNSEEN+DCN [26], UNSEEN+DEC [22], and UNSEEN+DKM [27]), each of which is also based on a pre-trained autoencoder backbone, are used as baselines. In contrast to all these, our method is trained from scratch, with no pre-trained or separately-learned feature extractor.
2ex -1em Computation and hardware. All our experiments are conducted using one NVIDIA H200 GPU. We apply parallel computing within a single GPU: Given the ES population size \(m=32\), we duplicate the network parameters for 16 times, perturb each of them individually, and implement them on 16 duplicated batches of image views. So, one ES step requires \(32/16=2\) iterations, and in each iteration there are \(16/2=8\) mirrored pairs. It takes around 5 hours to fully optimize a ResNet-9 model on MNIST or FashionMNIST, and around 2 hours on USPS.
| MNIST | Fashion-MNIST | USPS | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 2-4(lr)5-7(lr)8-10 Setting | NMI | ARI | ACC | NMI | ARI | ACC | NMI | ARI | ACC |
| Ours (full) | \(95.8_{\pm0.7}\) | \(96.3_{\pm1.1}\) | \(98.3_{\pm0.5}\) | \(65.0_{\pm1.0}\) | \(52.9_{\pm1.9}\) | \(64.1_{\pm1.9}\) | \(90.2_{\pm1.3}\) | \(90.3_{\pm2.8}\) | \(94.9_{\pm1.8}\) |
| w/o augmentation | \(49.1_{\pm2.5}\) | \(25.1_{\pm1.9}\) | \(30.1_{\pm1.5}\) | \(49.8_{\pm0.6}\) | \(23.5_{\pm1.1}\) | \(26.9_{\pm1.7}\) | \(65.3_{\pm3.0}\) | \(47.7_{\pm5.1}\) | \(55.2_{\pm5.9}\) |
| w/o inner-loop FT | \(77.4_{\pm3.0}\) | \(74.3_{\pm5.3}\) | \(80.9_{\pm6.1}\) | \(58.1_{\pm2.1}\) | \(44.9_{\pm2.2}\) | \(56.6_{\pm1.5}\) | \(66.2_{\pm5.1}\) | \(51.7_{\pm9.2}\) | \(59.3_{\pm9.3}\) |
| w/o anisotropic aug. | – | – | – | – | – | – | \(80.4_{\pm2.8}\) | \(73.0_{\pm4.8}\) | \(83.4_{\pm3.3}\) |
4.5pt
4.2 Results↩︎
Table 1 reports the comparison. Our framework achieves state-of-the-art performance on MNIST and USPS across all three metrics. On Fashion-MNIST, it obtains the best ACC and ARI scores, while remaining competitive on NMI. The largest improvement occurs on USPS, where our model improves ACC from DeepDPM’s \(89\%\) to \(94.9\%\), and lift NMI/ARI by roughly two and four points, respectively. On Fashion-MNIST, we reach \(64.1\%\) ACC and \(52.9\%\) ARI, both above the strongest baselines, while our NMI of \(65\%\) is second to DeepDPM’s \(68\%\). In addition, our model is trained from scratch, rather than from pre-trained features.
Crucially, these results are obtained without telling the model the number of classes. As shown in Table 2, the number of active clusters our method discovers stays close to the ground-truth value of ten: exactly \(10.0\) on MNIST, \(10.4\pm0.5\) on USPS, and \(11.6\pm0.5\) on Fashion-MNIST, comparable to the values inferred by DeepDPM (\(10.0\), \(9.2\), \(10.2\)). The remaining \(K-\hat{K}\) output dimensions die out during optimization and carry no test samples. Appendix 9 shows how the number of active clusters changes across epochs.
In summary, simply by maximizing the surprise score – with no per-step loss, no pre-trained model, and no prior knowledge – a deep network can naturally discover semantically meaningful hard representation, or tokenized representation, from raw images. Moreover, the discovered representation is independent of the output tensor shape (\(K\) in our case). Visualizations of the clustered images are exhibited in appendix 8.
4.3 Ablation studies↩︎
We ablate the three components that are most responsible for the above results: the independent two-view augmentation, the inner-loop gradient-descent training, and the anisotropic (zoom-out) augmentation used only on USPS. Table 3 reports the effect of removing each one.
2ex -1em Augmentation is essential. If we skip augmentation and run ES directly on the complementary masked views, the model maximizes the surprise score by latching onto low-level nuisance features that happen to be shared by the two views of an image – stroke thickness, brightness, and digit/item shape – rather than the semantic class. Augmenting the two views independently breaks this shortcut: the two views of one image now differ in brightness, contrast, scale (cropping), and orientation (rotation). To assign both views to the same cluster, the network now must rely on augmentation-invariant features, which are more likely the true underlying topology of the digits or items.
2ex -1em Inner-loop gradient-descent training is important. After several thousand epochs of pure ES, the model consistently produces more clusters than the number of ground truth classes. The gradient-descent training then consolidates the clusters: when two clusters hold similar image views, the larger cluster provides the stronger pseudo-label signal, which pulls across the image views from the smaller cluster, and finally absorbs the smaller cluster entirely. Moreover, augmenting both views again before each gradient-descent training step forces the network to map differently-augmented views to the same cluster, which reinforces the surprising clusters discovered by ES. In practice, the two-view agreement rate rises from \(80\)–\(85\%\) after pure ES to nearly \(99\%\) after a few training periods.
However, we cannot say that gradient-descent training is all we need: Without evolution epochs, there is no discovered surprising cluster at all for gradient-descent training.
2ex -1em Anisotropic augmentation is necessary for USPS. The USPS dataset is class-imbalanced, with far more zeros and ones than other digits. Also, its zeros vary widely in aspect ratio (tall-and-thin versus short-and-wide). The single-axis zoom-out randomly stretches or compresses each view along one axis, so that after independent augmentation, the two views of an image differ in width and height. Aspect ratio is then no longer a salient feature the two views share, forcing the network to cluster views based on more essential, topology-related structure of the digits.
5 Conclusion↩︎
We introduced converge-to-surprise, a self-supervised learning framework without needing a per-step loss. Our null hypothesis states that pixels are i.i.d.noise. Then, we build two complementary masked views from one image, and define a surprise score to measure how strongly the network’s view-clustering results reject the null hypothesis. Assuming that a surprise score cannot be reduced to a per-step loss function, we optimize our model combining evolution strategy with gradient descent. Without any pre-trained model or prior knowledge of the dataset, our framework attains state-of-the-art performances on MNIST, Fashion-MNIST, and USPS under non-parametric self-supervised image clustering setting.
Once again, we encourage people to read our discussions provided in appendix 6.
6 Discussions↩︎
The main paper presents converge-to-surprise as a novel self-supervised learning framework. Here, we step back and discuss the broader picture behind it. We first argue that the null hypothesis \(\mathcal{H}_0\) need not stay fixed: learning can be viewed as a repeated cycle in which the model rejects the current null hypothesis, folds what it discovered into an updated one, and searches again (Section 6.1). Then, we further evaluate the surprise score from an information theory point of view, showing that learning means to build order out of chaos (Section 6.2).
These discussions are conceptual and supplemental. They are not required for the results in the main paper.
6.1 Learning as iterative rejection of the null hypothesis↩︎
In the main paper, without any prior knowledge, we invoked the Principle of Maximum Entropy and assumed the data to be pure random noise. In our case, this means that every pixel is i.i.d. This gives us the null hypothesis \(\mathcal{H}_0\). The purpose of our learning framework is then to discover non-randomness, or surprise, that rejects \(\mathcal{H}_0\). However, this is only the starting point of a more general picture.
Once the model has discovered some non-randomness, we may fold that structure back into our description of the data. Concretely, we update the data distribution to account for what we found, obtaining an improved hypothesis \(\mathcal{H}_1\) that is no longer pure noise: it already encodes the regularities discovered so far. We may now treat \(\mathcal{H}_1\) as the new null hypothesis and repeat the process – further evolving and training the network to discover new surprise that rejects \(\mathcal{H}_1\). If we succeed, we update the hypothesis again to \(\mathcal{H}_2\), take it as the null, and continue: \[\mathcal{H}_0 \;\rightarrow\; \mathcal{H}_1 \;\rightarrow\; \mathcal{H}_2 \;\rightarrow\; \cdots\] Each round explains more of the data, and each new null hypothesis is harder to reject than the last. The process terminates when no further surprise can be found, no matter what output representation we use or how we observe it. At that point, we accept the current hypothesis and stop the learning process.
In general, this refers to the meaning of ‘learning’, which we summarize as three principles:
Maximum-entropy prior. Without any prior knowledge, we must assume the data distribution to be totally random noise, following the Principle of Maximum Entropy. This is our initial null hypothesis.
Learning as discovering surprise. To learn is to discover non-randomness, or surprise, from the data distribution in order to reject the null hypothesis.
Iterative updating. We update the null hypothesis to incorporate what we have discovered. Then, we seek new non-randomness that can reject the updated hypothesis. If, after enough updates, no representation and no way of observing can reveal further surprise, we accept the current hypothesis and stop learning.
The converge-to-surprise framework in the main paper realizes a single round of this process. Fully iterating through this process is a natural extension of our framework.
6.2 Orderliness: building order out of chaos↩︎
Now, we evaluate a surprise score from an information theory point of view. Recall from Section 3.2, we obtain the two cluster sequences from a batch of \(N\) images: \(\mathrm{seq}^{(i)} = (\hat{y}_1^{(i)},\dots,\hat{y}_N^{(i)})\) and \(\mathrm{seq}^{(j)} = (\hat{y}_1^{(j)},\dots,\hat{y}_N^{(j)})\). Pairing the two views of each image gives the cluster pair sequence \[\Pi \;=\; \bigl( (\hat{y}_1^{(i)}, \hat{y}_1^{(j)}),\, \dots,\, (\hat{y}_N^{(i)}, \hat{y}_N^{(j)}) \bigr),\] whose observed distribution over the \(K \times K\) cluster pair space is \[\pi_{a,b} \;=\; \frac{1}{N}\sum_{n=1}^{N} \mathbf{1}\!\left[\hat{y}_n^{(i)} = a \;\text{and}\;\hat{y}_n^{(j)} = b\right].\]
Then, the observed pair entropy is \[\hat{H}_\Pi \;=\; -\!\!\sum_{a,b:\,\pi_{a,b}>0}\!\! \pi_{a,b}\,\log \pi_{a,b}.\]
Suppose \(n_a^{(i)}\) is the number of times cluster \(a\) appears in \(\mathrm{seq}^{(i)}\), and \(n_b^{(j)}\) is the number of times cluster \(b\) appears in \(\mathrm{seq}^{(j)}\). Then, it is easy to see that \[p_a^{(i)} = \sum_b \pi_{a,b}=n_a^{(i)}\;/\;N,\;\;\; p_b^{(j)} = \sum_a \pi_{a,b}=n_b^{(j)}\;/\;N.\] That is, unlike Section 3.2, we observe the marginal probability distribution of a cluster within each sequence.
Then, consider an intra-view shuffling: we can permute the entries within \(\mathrm{seq}^{(i)}\) and within \(\mathrm{seq}^{(j)}\) independently, as many times as we like. But \(\mathrm{seq}^{(i)}\) and \(\mathrm{seq}^{(j)}\) do not exchange entries. Such permutation leaves \(\{p_k^{(i)}\}_{k=0}^{K-1}\) and \(\{p_k^{(j)}\}_{k=0}^{K-1}\) unchanged, but scrambles the pairing and hence the cluster pair sequence \(\Pi\).
Given the original \(\Pi\), suppose all pair sequences that we can possibly obtain after intra-view shuffling forms the set \(\mathcal{R}_{\Pi}\). Then, we define the shuffled-maximal entropy as the largest attainable value in the form: \[H_\Pi^{\star} = \max_{\tilde{\Pi}\in \mathcal{R}_{\Pi}}\hat{H}_{\tilde{\Pi}}.\]
It is easy to see that \(\hat{H}_\Pi \le H_\Pi^{\star}\) always holds true. Also, by a routine analysis, we can get that \[H_\Pi^{\star} = H\!\left(p^{(i)}\right) + H\!\left(p^{(j)}\right), \;\; H(p^{(\cdot)}) = -\sum_{k} p_k^{(\cdot)} \log p_k^{(\cdot)} ;\] and \[H_\Pi^{\star} - \hat{H}_\Pi \;=\; I\!\left(\hat{y}^{(i)}; \hat{y}^{(j)}\right) \;\ge\; 0.\] Here, \(I\!\left(\hat{y}^{(i)}; \hat{y}^{(j)}\right)\) is the mutual information between the original, un-shuffled \(\mathrm{seq}^{(i)}\) and \(\mathrm{seq}^{(j)}\), as described in Section 3.2.
Finally, we define the orderliness (or neg-entropy): \[\Omega \;=\; \frac{H_\Pi^{\star} + \lambda}{\hat{H}_\Pi + \lambda},
\label{eq:orderliness}\tag{10}\] where \(\lambda > 0\) is a small constant that keeps the ratio well-defined in degenerated cases. Since \(\hat{H}_\Pi \le H_\Pi^{\star}\),
we always have \(\Omega \ge 1\), with larger values indicating more order.
Then, we describe two special cases:
Fresh initialization: Right after initializing the model, \(\mathrm{seq}^{(i)}\) and \(\mathrm{seq}^{(j)}\) are essentially independent. So, the observed pairing is already close to its most disordered form. Thus, we have \(\hat{H}_\Pi \approx H_\Pi^{\star}\) and \(\Omega \approx 1\). This matches \(\mathcal{S}(\theta)\approx 0\): nothing surprising has been found.
Collapse: If the network collapses so that every view is mapped to a single cluster \(k_0\), only the pair \((k_0,k_0)\) is ever observed. In this case, no shuffling can change the cluster pair sequence \(\Pi\). Hence, \(H_\Pi^{\star} = \hat{H}_\Pi = 0\) and \(\Omega = \lambda/\lambda = 1\) always hold true. In other words, collapse is not learning.
Thus, genuine learning drives \(\Omega \gg 1\), which by Eq. 10 requires the observed pair entropy \(\hat{H}_\Pi\) to be much smaller than the shuffled-maximal entropy \(H_\Pi^{\star}\). The latter demands diverse marginals (many clusters being observed), i.e.high potential disorder; the former demands the actual pairing to be highly dependent (both views of an image tend to agree), i.e.strong order. In other words, to learn is to keep the marginal diversity while imposing order on how these diversities are organized – to build order out of chaos.
Combining this with Section 6.1, we arrive at an intuitive picture of the whole process: learning repeatedly discovers order out of chaos and folds what being discovered into an ever-stronger hypothesis, and continues until there is no more order left to discover.
7 Implementation details↩︎
| Parameter | MNIST | FMNIST | USPS |
|---|---|---|---|
| Side \(S\) | \(28\) | \(28\) | \(32\) |
| Rotation \(r\) (deg) | \(20\) | \(20\) | \(10\) |
| Rotation prob | \(1.0\) | \(1.0\) | \(0.5\) |
| Bright/contrast \(b\) | \(0.3\) | \(0.3\) | \(0.15\) |
| Crop edge | \(\{24..28\}\) | \(\{24..28\}\) | \(\{30..32\}\) |
| Crop prob | \(1.0\) | \(1.0\) | \(1.0\) |
| Flip prob | – | \(0.5\) | – |
| Zoom-out prob | – | – | \(1.0\) |
| Zoom-out range | – | – | \(\{2..6\}\) |
5pt
Table 4 lists the exact per-dataset augmentation parameters referenced in Section 4.1.
As mentioned in the main paper, after the chessboard masking, the two complementary views of each image are augmented independently, which preserves the zero-mutual-information property between two views under \(\mathcal{H}_0\). On MNIST and Fashion-MNIST images, we apply random rotation, random square cropping, and brightness/contrast jitter. On Fashion-MNIST images, we additionally apply a horizontal flip with probability \(0.5\). Digits are not flipped, as a mirrored digit is not the same class.
For USPS, we add a single-axis zoom-out after cropping, which pads one randomly chosen axis with a black border before resizing back, producing an anisotropic (tall/short, wide/narrow) deformation. This is motivated by the imbalance of the USPS dataset: the digit-0 class is dominant and exhibits far more aspect-ratio variation than its MNIST counterpart. The anisotropic augmentation de-correlates this global shape so that same digits are less likely to be further split based on width or height. To leave room for the anisotropic deformation, the remaining augmentations on USPS images are kept milder than on MNIST/Fashion-MNIST images, as shown in Table 4. Besides, USPS characters occupy a relatively larger fraction of the frame. So, we mask at the native \(16\times16\) resolution, upsample each view independently to \(32\times32\), and crop only down to a \(30\times30\) window (i.e., a milder cropping range: \(30\sim 32\)).
8 Clustering visualization↩︎
To qualitatively inspect what the network discovered, we visualize the test-set clustering of one trained model per dataset. For each active cluster \(k\) and each ground-truth class \(p\), we draw a \(3\times3\) grid of randomly selected test images that belong to cluster \(k\) and carry label \(p\). We only draw such a grid when at least \(50\) such images exist (rare classes in each cluster are ignored). Each panel is captioned “Cluster \(k\), digit \(p\)”, or “Cluster \(k\), item \(p\)”.
3.25ex -1em MNIST. Figure 4 shows the MNIST clustering. The optimized network produces a clean one-to-one map: each active cluster corresponds to a single ground-truth class, and each class is captured by a single cluster. This is confirmed by the cluster-purity report, where every active cluster is dominated by one digit class at \(97\%\) – \(99.7\%\) purity:
Cluster 35 | n=1134 | 99.0Cluster 38 | n=1043 | 98.6Cluster 19 | n=1036 | 97.0Cluster 49 | n=1031 | 98.5Cluster 53 | n= 997 | 97.1Cluster 58 | n= 980 | 99.4Cluster 56 | n= 968 | 98.3Cluster 34 | n= 968 | 98.9Cluster 11 | n= 958 | 99.7Cluster 14 | n= 885 | 99.0Each of the ten digits is represented by exactly one high-purity cluster, so Figure 4 contains exactly ten panels.
3.25ex -1em USPS. Next, Figure 5 shows a deliberately less-than-perfect USPS run, in which the model settled on \(11\) clusters instead of \(10\). Its per-cluster purity is still high, but two clusters share the same dominant class (digit 0), which is what pushes the count to \(11\):
Cluster 53 | n=313 | 97.1Cluster 52 | n=256 | 99.6Cluster 28 | n=199 | 95.0Cluster 38 | n=199 | 94.5Cluster 33 | n=188 | 93.1Cluster 15 | n=168 | 95.2Cluster 14 | n=166 | 97.6Cluster 31 | n=162 | 98.1Cluster 44 | n=157 | 95.5Cluster 12 | n=144 | 96.5Cluster 23 | n= 55 | 90.9Both cluster \(23\) and cluster \(53\) focus on the digit \(0\): the zeros in cluster \(53\) are relatively round and plain, whereas those in cluster \(23\) are narrow, tall, and often carry an extra stroke beyond the bare loop. This shows that the zoom-out (anisotropic) augmentation largely works as intended, but does not perfectly remove every unwanted topological and geometric variation of the dominant digit-0 class. This leads to further split of the digit-0 class.
3.25ex -1em Fashion-MNIST. Finally, Fashion-MNIST is far more challenging for non-parametric self-supervised image clustering, since several classes differ only in fine texture rather than global contour [48]. The per-cluster purity is correspondingly lower and some clusters mix classes:
Cluster 53 | n=1303 | 31.1Cluster 23 | n=1165 | 82.1Cluster 48 | n=1164 | 63.4Cluster 2 | n=1136 | 81.4Cluster 7 | n=1112 | 86.2Cluster 55 | n=1014 | 76.4Cluster 24 | n= 979 | 46.7Cluster 31 | n= 770 | 99.2Cluster 47 | n= 524 | 96.8Cluster 59 | n= 476 | 90.1Cluster 42 | n= 357 | 40.9Even so, the visualization in Figure 6 shows that the network discovers meaningful structure beyond the labels. Clusters \(47\) and \(59\) both isolate bags, but along a finer distinction: cluster \(47\) collects bags with a visible handle/strap, whereas cluster \(59\) collects bags with no (or only a very small, barely visible) handle. Clusters \(24\) and \(53\) both contain upper-body garments, but separate them by texture rather than contour: the garments in cluster \(24\) are more heavily textured/patterned, while those in cluster \(53\) are comparatively plain. In other words, despite using only a ResNet-9, converge-to-surprise optimization enables the network to distinguish both contour and texture.
Once again, although the per-cluster purity on Fashion-MNIST is lower than those on the other two datasets, we still achieve state-of-the-art performances on Fashion-MNIST.
9 Number of discovered clusters during training↩︎
Because the number of classes is never given to the model, it is instructive to watch how many clusters the model discovers as training proceeds. Recall that we introduced \(D\!\left(\hat{q}_k \,\Vert\, q_k\right)\), the surprise score at cluster \(k\), via formula 5 in Section 3.2. Then, we regard cluster \(k\) as surprising if \(D\!\left(\hat{q}_k \,\Vert\, q_k\right) \geq \tau=0.005\). Figures 7, 8 and 9 plot, for five independent runs per dataset, the number of surprising clusters after each ES epoch.
We can see that during the pure-ES stage, the model keeps discovering new candidate clusters, exceeding the number of ground truth classes. We call this over-production. Once gradient-descent training begins, each training round consolidates redundant clusters, pulling the count back down. Then, the evolution strategy slightly rebuilds surprising clusters on the cleaner partition. But finally, the evolution strategy and gradient-descent training reach the balance. No new surprising cluster is discovered in the last 200 epochs. In general, results shown here coincide with our analysis in the ablation study 4.3.
On MNIST (Figure 7, two-stage schedule), the over-production peaks in the first \(2000\) epochs, and then collapses cleanly to \(10\) for all five runs. On USPS (Figure 8, three-stage schedule) the effect is more pronounced: the pure-ES stage (\(0\)–\(4000\) epochs) over-produces up to around \(25\) clusters. In the weak stage (\(4000\)–\(8000\) epochs, with 2 training epochs every 500 ES epochs), the ES optimization rebuilds back the number of surprising clusters after every gradient-descent training epoch, creating the sawtooth curves. Finally, the strong stage (\(8000\)–\(9000\) epochs, with 4 training epochs every 25 ES epochs) settles the number of surprising clusters to \(10\) or \(11\). Fashion-MNIST (Figure 9) behaves similarly but stabilizes at a slightly larger count, reflecting its harder, texture-dominated data structure.
Once again, by converge-to-surprise, the model naturally discovers meaningful clusters from raw images without any prior knowledge.
References↩︎
This work is supported by Sorensom Communications AI-Lab.↩︎