Learnability and Expressiveness in Self-Supervised Learning
Authors: Yuchen Lu
Zhen Liu
Alessandro Sordoni
Aristide Baratin
Romain Laroche
Aaron Courville
Venue: ICLR 2022 Submitted (2022)
Keywords: Self-supervised Learning
Learnability
Intrinsic Dimension
Representation Learning

Abstract: In this work, we argue that representations induced by self-supervised learning (SSL) methods should both be expressive and learnable. To measure expressiveness, we propose to use the Intrinsic Dimension (ID) of the dataset in representation space. Inspired by the human study of Laina et al. (2020), we introduce Cluster Learnability (CL), defined in terms of the learning speed of a KNN classifier trained to predict K-means cluster labels for held-out representations. By collecting 30 state-of-art checkpoints, both supervised and self-supervised, using different architectures, we show that ID and CL can be combined to predict downstream classification performance better than the existing techniques based on contrastive losses or pretext tasks, while having no requirements on data augmentation, model architecture or human labels. To further demonstrate the utility of our framework, we propose modifying DeepCluster (Caron et al., 2018) to improve the learnability of the representations. Using our modification, we are able to outperform DeepCluster on both STL10 and ImageNet benchmarks. The performance of the intermediate checkpoints can also be well predicted under our framework, suggesting the possibility of developing new SSL algorithms without labels.

Under review as a conference paper at ICLR 2022
LEARNABILITY AND EXPRESSIVENESS IN SELF-SUPERVISED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We argue that representations induced by self-supervised learning (SSL) methods should both be expressive and learnable. To measure expressiveness, we propose to use the Intrinsic Dimension (ID) of the dataset in representation space. Inspired by the human study Lf.Lai et al. (020), we introduce Cluster Learnability (CI.), defined in terms of the learning speed of a KNN classifier trained to predict K- means cluster labels for held-out representations. By collecting 30 state-of-art checkpoints, both supervised and self-supervised, using different architectures, we show that ID and CL can be combined to predict downstream classification per- formance better than the existing techniques based on contrastive losses or pretext tasks, while having no requirements on data augmentation, model architecture or human labels. To further demonstrate the utility of our framework, we propose modifying DeepCluster (Caron et al. 2018) to improve the learnability of the rep- resentations. Using our modification, we are able to outperform DeepCluster on both STL10 and ImageNet benchmarks. The performance of intermediate check- points can also be well predicted under our framework, suggesting the possibility of developing new SSL algorithms without labels.
INTRODUCTION
We consider the unsupervised learning scenario, which aims at learning distributed representa- tions for complex natural data without human annotations. Despite great recent progress in self- supervised learning (Chen et al., 2020a; Caron et al.) 2021: Grill et al.] 2020, Caron et al. 2020) 2018 He et al. 2020 Chen and He 2021), the problem of properly evaluating the quality of the learned representations has not been fully explored. We approach this question by drawing an anal- ogy with the evolution of human language. Recent literature (Swarup and Gasser 2008 Smith et al.) 2013) suggests that linguistic structure arises as trade-off between expressiveness and learnability. On one hand, expressiveness is the ability to discriminate objects and concepts of the world. On the other hand, hand, et al. (2014) states that language evolution undergoes an iterated learning pro- cess, where each individual acquires language by observing a limited amount of language outputs of others (Chomsky) 1980). This process induces form of compression, which makes the language simpler and more learnable for the next generation. Linguistic structure, c.g., compositionality, emerges between these opposing forces.
A similar guiding principle can be applied when learning representations of natural data. Many ex- isting methods in self-supervised learning can be considered as attempts to increase expressiveness of the representations, i.c., by maximizing or controlling the mutual information between inputs and representations, either through reconstruction (Vincent et al.) [2088] [Hgginn al.) 2017) con- trastive learning (Oord et al.) [2088] Bachman et al. (011b)). We argue that in addition to maximizing expressiveness, good representation should also be learnable, e.g. support generalization from few examples (Laina et al. 2020).
In this paper, we propose an evaluation framework for self-supervised learning relying on expres- siveness and learnability. Compared with previous work (e.g., Wang and Isola 2020), our framework is independent of (i) the availability of downstream task labels or predefined data augmentation tech- niques, and (ii) architecture choices and dimensionality of the latent representations, which makes it applicable to all previous SSL methods. We propose to measure expressiveness in terms estimators of the intrinsic dimension (ID) of the data representations Ansuini et al. 2019). Taking inspiration

---

Under review as a conference paper at ICLR 2022
from Laina et al. (2020), quantify learnability in terms of the learning speed (in terms of number of examples) of a KNN learner trained to predict the K-Means cluster labels for held out represen- tations. We dub this method Cluster Learnability (CL). We show that high ID and CL correlate with high downstream performance for 30 different pretrained checkpoints across different architectures.
To further demonstrate the usefulness of our framework, we present case-study in which we im- prove upon DeepCluster (Caron et al. (0188) which is self-supervised learning method that iterates between clustering the representations and fitting the cluster labels. Inspired by our CL measure, we refine the cluster labels by executing KNN at the end of each K-means clustering round. The result- ing method, CNN--eeppllster, is able to outperform DeepCluster in both ImageNet and STL10. When visualizing the training trajectories on the CL-ID plane, we find that our method indeed im- proves learnability at convergence. The correlation between performance and learnability holds also for checkpoints obtained during training, which suggests the possibility of using our framework to guide the development of new SSL algorithm, without labels hand.
Our contributions are summarized below:
We analyze self-supervised learning through the lens of expressiveness and learnability, and we propose tractable way to estimate them with Intrinsic Dimension (ID) and Cluster Learnability (CL).
We carry out a large-scale evaluation on ImageNet and STL10 with 30 state-of-the-art self- supervised and supervised checkpoints. We show that CL.IID is more correlated with the Topl accuracy than previous approaches, with a Pearson's 's of 0.93.
We propose modification to DeepCluster to increase its cluster learnability. The resulting algorithm, KNN-DeepCluster is able to outperform DeepCluster.
2 RELATED WORK
Representation Evaluation Several recent works address the question of representation evalua- tion in self-supervised learning. Whitney et al. (202T) propose to use the learning dynamic of the downstream classifiers to measure the representation complexity, however the method depends on extra human labels. |Wang and Isola (2020) decompose the contrastive loss into an alignment loss and a uniformity loss, which can be used to analyze the representation. However, their method requires access to the projection head output, limiting their applicability to general architecture. Pretext tasks like jigsaw, rotation prediction evaluation (Reed et al. [202]] Deng and Zheng, 2021) or architecture search (Liu et al., 2020). How- ever, is shown in our experiments, they only provide limited predictive power when applying to a large pretrained family of checkpoints including both supervised and self-supervised models. In addition, these methods depends on predefined data augmentation, which might be task specific.
shown be well correlated with the supervised
Manifold Intrinsic Dimension Intrinsic dimension can be thought of as the smallest number of variable needed to approximate the representation manifold. Note that it is different from the intrin- sic dimension of loss landscape (Li al.) 2018), which measures minimum dimension of parameter space needed to optimize. We build upon extensive work on estimating intrinsic dimension. Apply- ing local neighborhood information to estimate the intrinsic dimension is not new idea, and is shown to be more superior to the global eigenvalue approach (Pettis et al. 1979h). Ansuini et al. (2019) apply the TwoNN estimator (Facco et al. 2017) to the non-linear representation manifold of modern deep neural nets. They find that the intrinsic dimension is inversely correlated to the classi- fication accuracy, and that the deep layers have smaller intrinsic dimensions. Their work is further extended to confirm that natural images lies in a low-dimension manifold (Pope al.) 2021). and lower ID datasets leads to better generalization. Our work presents a more nuanced view about ID. It suggests that in order to learning representation from scratch, least amount of ID is needed to convey the information from the dataset, e.g., a constant-value representation has an ID of 0, but no capacity to generalize all. More discussion can be found in Section 5
Learnability, Efse-offTraane Transmission and Compression Learnability has been argued to be a hall- mark of the human language in order to be effortlessly transmitted through generations (Kirby et al.
2014 Rafferty et al. 2011 (eckner et al. 2017 Zhou and Yurovsky 2021 Kampen 2004). and
2

---

Under review as a conference paper at ICLR 2022
it is also true for visual concepts like color (Xu et al. 2010). categories (Griffihhs al. 2006), shapes (Portelance et al. (02T etc. In deep learning, it has been explored in the context of emergent communication (Ren al. | 2020 Guo et al.) [2199] Li and Bowling 2019), language drift (Lu et al. 2020), and neural module networks (Vani et al. 2021), but is less explored for vision representa- tion learning, except for human study on just two SSL methods [aina et al.) (2020). Learnability has light connection to compression (Chaitin 2007) and prequential codelength (Dawid) 1984). which quantifies the compression levels with the online learning error. Existing works (Blier and Ollivier 2018) has use it to support the generalization ability of the learner (e.g., deep neural nets)
on the dataset (e.g., labeled images). However, we use quantify the learnability of the repre- sentation, in the sense that if the emerged Kmeans clustering is more learnable, then the same KNN learner could achieve lower compression bound via prequential coding.
PROPOSED FRAMEWORK
In this section, we introduce our setup and define our measures of expressiveness and learnability.
3.1 NOTATION
We consider the following setting: we assume we have dataset of images { represented in pixel space X' C RR, where x; P are sampled i.i.d from some natural image distribution P over X. We also consider representation maps F X' - IR",, typically pretrained neural networks, which represent any image as an m-dimensional vector. Any such map forms a representation dataset I. where = F(r:). Given 2; E Z and an integer k 2 1, we denote by N2, k) the k-th nearest neighbor of 2;- While we generally mean 'nearest" with respect to Euclidean distance, in practice we will also use the cosine distance function
Z = {
22), 2 2 (21, 22)
ra D(2,, (2,, k)) be the distance of the data point 2 to its ke-th nearest neighbor.
3.2 INTRINSIC DIMENSION (ID)
To measure expressiveness, we propose to use the notion of intrinsic dimensionality (ID) of the data in the representation space (Pettis et al. 1979ah. Intuitively, as the representation becomes more expressive, we expect it to be able to represent images coming from more fine tne-grained categories, which could have multiple disentangled features such as color, shape. positions in space, etc. If these disentangled features correspond to different directions in some non-linear manifold, ID should yield a good surrogate for the expressiveness of the representation.
Inferring the intrinsic dimension of highly nonlinear manifold is challenging problem (c.g., Levina and Bickel 2005). In this work, we leverage the nearest neighbor-basee method of Facco et al.aa122.1)) (2017) to estimate ID, which uses only the first two nearest neighbors of cach point. This estimator (TwoNN) is shown to be reliable with respect to representation dimensions and scalable to real-world datasets with deep neural networks (Ansuini al. 2019). Assuming the data density is approximately constant around data points up to the distance of their neighbors, this method exploits the simple relationship between the distribution of the ratio of first and second nearest neighbor distances and the intrinsic dimension.
Formally. let μı = ri2/r be the ratio of distances for the data point 24. We suppose the points are sampled on a manifold with intrinsic dimension d. It can be shown that, under the above local uniformity assumption, μ4 follows Pareto distribution with parameter + on oo). That
P(u (NNld d II P (d+1)
While dl can be computed by maximizing the likelihood, we follow a much simpler method proposed by Ansuini et al. (2019) and estimate d with a linear regression on the empirical cumulate of the distribution of μ. which is shown to have good practical performance {Facco et al., (017). This estimator is exact for uniformly distributed data. It is also shown remain asymptotically correct for non uniform sampling of 2; when the image dataset is large enough (Ansuini et al.) 2019).
Both distances produce similar results in our experiments.
3

---

Under review as a conference paper at ICLR 2022
3.3 CLUSTER LEARNABILITY (CL)
To measure the representation learnability, we take inspiration from Laina al. (2020). In this work, it is shown that the classes obtained by clustering the representations of pretrained self-supervised models be easily learned by humans. We propose cluster learnability (CL.) metric way automate their procedure and measure the learnability of the representation.
Let {2,, D4 1 be the labelled dataset obtained by clustering the representation (e.g.. with K- means). We want to define the learnability of the representation as the learning speed of a KNN clas- sifier with this labelled dataset. To formalize this, we use prequential approach (Dawid) 1984). Let D: KN ( (zkei, ) denote the prediction of the i-th label after seeing the pairs (Z Uk) for k < i. Learnability defined as the online learning accuracy of our KNN classifier:
CL T-== 71.
This metric be connected the prequential codelength of the cluster assignment dataset where the conditional model is a formed by KNN classifier. We discusss this further in Appendix B
4 EXPERIMENT: EMPIRICAL EVALUATION OF THE CL-ID FRAMEWORK
In this section, assess the main hypothesis of the paper and the relevance of our metries, we perform experiments designed to answer the following questions:
Q1: Are high-performing models consistently both expressive and learnable?
Q2: Can our CL-ID framework robustly predict the model performance better than the existing SSL evaluation frameworks?
4.1 SETUP
We select 11 different self supervised checkpoints and download the official ImageNet checkpoints. We include checkpoints with different training epochs and different architecture. Combining the supervised checkpoints results in 30 checkpoints in total. complete list can be found Table in the appendix. We mainly use the KNN evaluation the validation data using the ground-truth labels to measure the performance the linear evaluation but computationally less expensive (Caron al.) 2021). CL is computed on the train set to have a better estimate, while the ID is computed on the validation. For STL-10, we use the unlabeled split, which has more images.
the model, which has been shown to be well correlated with
In our experiments, we use 1000 clusters for ImageNet and 320 for STL-10, which are approximately the square root of the dataset size. We report results with neighbor for KNN learner We normalize the features and use cosine distance for the K-means clustering and KNN learner. Other configurations of cluster numbers and neighbor numbers are also explored in section 4.4
4.2 QUALITATIVE EVALUATION
We conduct qualitative evaluation (Figure M address Q1. We choose Alignment vs. Unifor- mity (Align-Unif) (Wang and Isola 2020) as our baseline, since this work also does not depend on downstream labels. We compute both alignment loss and uniformity loss on the validation data.
On both dataset, the proposed CL-ID framework show that good representations tend have high cluster CL as well as high ID, forming clusters on the upper-right Pareto frontier. In contrast, the Align-Unif fails to show the results with a lower alignment and higher uniformity for good represen- tations. We hypothesize that this is because Align- Unif framework is derived from the contrastive loss and therefore requires access to the post- prot-projection output. However, not every checkpoint has the projection layer. Our results suggest that the Align- Unif framework is less flexible than ours and might not be applicable to the raw outputs coming from pretrained backbone.
4

---

Under review as a conference paper at ICLR 2022
25.0
tyd resnetil
deng
droyding
22.5
smcrv22
selar2g
hdDrg
Monnet5g
deepclusi@cip
deepcluate
drig
Rflle
dntg
moca)
amcindinin22
simdin22
Inleke
mocky selav2
17.5
selanZo
dintg
byol
deepcluste:
moce)
PCAp
15.0
InfoMin
dng)
ReShetL 1onettopssee55 (esnet5
12.5
deepcluste
1.5
10.0
PClp
=lav2
55
60
65
70
75
80
85
90
-0.50
-0.45
-0.40
-0.35
-0.30
-0.25
-0.20
1000 Cluster
jesnegj)
ddng)
dnng
resnet34g dnep
Cluste Nav deepcluste
RC
3m/rr22
drngg
deepcluste
amdrr22
2alay
drng
2.5
Info
3mdrv2g
byoly
deepcluste
smdvvle
mocOo
moce
PCL
B5nat34
InfNiig
resnet5
dno:
1.5
deepcluste
PCip
wlav2
10
-0.65 -0.60
-0.55
-0.50
-0.45
-0.40
-0.35
-0.30
-0.25
320 Cluster: CL
Align
Figure 1: Visualization of SSL checkpoints for ImageNet (first row) and STL-10 (second row) on different frameworks. Color is used to show the KNN Top1 accuracies. Red indicates high accuracy, while blue indicates low accuracy. Left Column is our proposed CL-ID framework while Right Column is Align-Unif framework (Wang and Isolal 2020). Our framework shows qualitatively consistent results: Good representations tend have high CL as well as high ID (in the upper-right corner).
4.3 QUANTITATIVE EVALUATION
We also perform quantitative evaluation (Figure 2) address Q1 and Q2 by comparing the Top1 accuracy predictors from different framework. We come up with two Topl accuracy predictors for our method:
Vanilla CL-ID Predictor:
CL+ID
Linear CL-ID Predictor: Ki CL K₂ ID
Ka
where K1, K2, K3 are obtained by linear regression with our collected 30 checkpoints.
The first baseline linear Align-Unif Predictor, which is the linear regression of the alignment loss and uniformity loss. It is also learnt from the collected checkpoints.
Linear Align-Unif Predictor
Align + K₂ Unif + K3-
The second baseline rotation prediction, which is one of the best pretext task proposed proposed by Reed al. (202)). We randomly rotate the training images with 0, 90, 180, 270 degrees, train
5

---

Under review as a conference paper at ICLR 2022
Framer Car
Prunce
Figure 2: Correlation Plots between Topl accuracy and its various predictors. The first row is ImageNet and the second row is STL-10. First Column: Vanilla CL-ID Predictor. Second Column: Linear CL-ID Predictor. Third Column: Linear Align-Unit Predictor (Wang and Isola 2020).
Fourth Column: Rotation Prediction (Reed et al.) 202I). Our predictor has higher correlation to the Topl image classification accuracy than the baselines even with the vanilla version.
a KNN classifier on the train images to predict a 4-y classification, and then report the rotation prediction accuracy on the validation images.
Our results show that, for both datasets, our linear predictor beats our vanilla one, which already beats all the other methods in terms of the correlation scores. While the linear Align-Unif predictor achieves about 0.5 correlation, the learnt parameters K1, K2 are negative, which support our ob- servation in Figure [ that alignment- uunforrmttt framework does not produce qualitatively correct results. The pretext tasks like rotation prediction have certain correlation, but it is not as good as our methods when applied
wider range of SSL methods and it data augmentation heavy.
We also tried combining alignment loss, uniformity loss and rotation prediction into one linear regression formula, but that still does not beat our predictors.
4.4 ROBUSTNESS ANALYSIS
In this experiment, want check whether our results in the previous section is robust (Q2). In our framework, ID does not depend on any hyper-parameters. Therefore, we mainly examine the following hyper-parameters for CL.: the number of clusters and the number of neighbors used in the KNN Learner. The results can be found in Figure S The resulting linear predictor can still produce a higher correlation than the rotation prediction for a wide range of the configurations we have tried, for both ImageNet and STL-10.
On both datasets, observe that in general decreasing neighbor number leading to better predic- tor. We hypothesize that lowering the neighbor number would results in a stronger KNN classifier that over-fits the structure-less cluster assignments more easily, resulting in better distinction among different checkpoints. For practitioner, we recommend setting number of neighbors to be 1.
On both datasets, we observe that there is an optimal cluster numbers so that the choice of neighbor numbers can be more flexible. If the cluster number is too low, the results become worse. Recall that for different checkpoints, the clusters are produced with the same K-means algorithm, so the separability among clusters might be roughly controlled. As result, we hypothesize that here the cluster numbers here might control the underlying difficulty of the classification problem faced by many clusters data
the KNN learner. In the extreme cases points. In the former, KNN accuracy would always be 100% and in the latter always be close to 0%. As result, neither of them would be suitable enough to distinguish the collected checkpoints. As
have either only 1 cluster

---

Under review as a conference paper at ICLR 2022
100
0.78
0.2
0:67
06
0.9
Number of Chaters
400
0.89
0.8
087
0.66
Pearson Codfiictet
600
0.1
991
09
0.89
800
992
092
091
vanilla predictor
rotation prediction
1000
0.93
093
093
0.2
0.7
2000
0.2
092
0.91
4000
0.92
0.1
0.89
0.66
0:86
0.5
5 Number of Neighbors
10
0.0
0.1
0.3
0.4
0.6
Clusterr / Dataset (%)
0.84
0.8
0.78
0.75
20
0.9
0.88
0.86
0.83
0.9
Number Chaters
Pearson Codfiitent
091
160
0.93
0.93
0:3
0.93
0.7
320
0.94
0.9
0.4
0.92
512
0.94
0.5
0.44
0.93
0.94
0:93
predictor
rotation prediction
0.5
10
0.00
0.25
0.50
0.75
1.00
1.5
155
1.75
2.00
Number of Neighbors
Cluster / Dataset (%)
Figure 3: Robustness Analysis for ImageNet (First Row) and STL-10 (Second Row)). Left Col- umn: The heat map of Pearson Coefficient between the Top-1 accuracy and linear CL.IID predictor. Right Column: Pearson coefficient vs. the ratio between the number of clusters and the dataset size when using one neighbor. The result is stable with a reasonably large number of clusters, e.g., the square-root of the dataset size (Green Dashed Line).
rule of thumb, we recommend using reasonably large number of clusters, e.g., the square root of the dataset size.
EXPERIMENT: DEEPCLUSTER WITH IMPROVED CLUSTER LEARNABILITY
In this section, we propose simple modification for DeepCluster (Caron et al. 2018), which in- crease the learnability of the representations. Our method is called KNNDeepcluster. The purpose of this experiment is not to focus on new state-of-the-art SSL method, but rather to understand whether our framework can improve an existing SSL method. The experiments would address the following questions:
Q3: Does KNN- CNN--eepCluster out-perform DeepCluster consistently? Does it end up having higher CL?
Q4: Can predict the performances of the new checkpoints with the CL-ID predictors from section 4.3
DeepCluster alternates between rumning K -maans on the representation space and learning a repre- sentation such that it highly predictive of the target cluster label associated with it. As result, we can make target cluster label to be more learnable, we can also make the representation more learnable. Following our approach of CL described above we will enforce the K-means labels to be consistent with the KNN prediction, We proceed in the following way: at the beginning of the epoch, after each K- K-means clustering round, we change the K K-means labels to the leave-one-out nearest neighbor predictions The pseudocode of the approach can be found in Algo.
In practice, instead of performing KNN prediction by querying the whole dataset, we use queue of representations stored in each GPU worker. While this does not result in the exact neighbors, we find that it's scalable large datasets.

---

Under review as a conference paper at ICLR 2022
Algorithm 1: KNNDeepCllsterr. X is input images and F is the model
while Not converged do
Compute 2; ; 0) for i .,...
Kmeans clustering on {z, and get cluster label (ü:)- (2r(2, Un hegtt) for i = 1,....
Get 14 NN
Leave
Update 0 on the dataset {I,, } for one epoch.
end
5.1
RESULTS ON IMAGENET AND STL-10
Dataset Eval. Method
STLI0 Linear
ImageNet Linear 10%
INN
5NN
Linear
20NN
ScLa-v2 (Caron al. 2020
71.8
61.6
DeepCluster (Caron et al. 2020)
74.3
65.8
DeepCluster (ours)
82.9
74.3
76.6
74
66.7
65.2
KNNDeepCluster (ours)
83.1
76.0
79.1
74
66.9
66.6
Table 1: Comparison between- Netwen-KKNNDDeeppee KNNODeepCluseer and other cluster-based SSL. The official check- points are taken with multicrop of 2x160 4x96 and 400 epochs.
In our experiments, we set the number of neighbors to be in our KNNDeepCluster for both datasets, and find that this does not affect our results much. We perform experiments both STL- 10 and ImageNet. Our results are shown in Table [ There are consistent gains on both STLI0 and ImageNet, but the gain on ImageNet smaller, and only appears with weaker downstream classifier such as KNN or with less training data.
5.2 ANALYSIS WITH THE CL-ID FRAMEWORK
DespCluter
rpocks
01 (100
15
soch- Yea
73
Figure 4: Trajectory of DeepCluster and KNN-Deeppluster for ImageNet (first row) and STL- 10 (second row) for 400 epochs. Left: ID vs CL. Middle: Top-1 accuracy vs. ID. Right: Top-1 accuracy vs. Linear CL-ID predictor (from Section 4.3) Our proposed modification makes the representation more learnable at convergence without significant compromise of ID, leading to better solution. There is still positive correlation between predictors obtained in Section 4.2 and the performance, especially after models are warmed up (after epoch 8 in ImageNet and epoch 49 in STL-10).
We visualize the training trajectories in Figure We observe that the training trajectories for both methods follow similar general patterns across datasets: in the initial stage, the models tend to decrease CL. while increasing ID. After the model is properly warmed up, there is increase of ID
8

---

Under review as a conference paper at ICLR 2022
along with CL. Finally, especially for the ImageNet models as well KNN-DeepCluster in STL-10, ID hits the plateau and starts decreasing while CL keeps increasing. Despite the slight difference in the final stage between two datasets, find that KNN- ANN--eepClluter converges to a solution that has a higher CL. in comparison to DeepCluster, without a significant drop in II..
We also find that the relative Top-1 classification performance of the intermediate checkpoints can still be well predicted by our linear CL.IDD predictor from Section 4.3] especially after the models are property warmed up. The lack of correlation in the early stage checkpoints could be caused by the fact that our linear CL-ID predictor is learnt from the collected 30 checkpoints, which are all about late stage (with Top1 Acc greater than 50%).
Previous work C.cgg..Assiin et al., 2019) claims that ID is inversely correlated to the Top-1 accuracy, seemingly countering our expressiveness argument. Our findings are more nuanced. For ImageNet, at least for the early and middle stages, the ID is increased (before epoch 1 119) so that, intuitively, the model could explore as much as possible to encode the information from dataset. Then in the later stage, form of compression occurs while CL increases for better generalization presumably this stage the regime of analysis done in Ansuini et al. (2019).
CONCLUSION & DISCUSSION
Inspired by an analogy with language emergencewe propose to analyze self-supervised representa- tion learning through the lens of expressiveness and learnability. We propose estimate expressive- ness with TwoNN intrinsic dimension (ID), and Icarnability with the acquisition speed a KNN learner the K-means clustering of the representation. Our large-scale evaluation with 30 check- points supports our claim. Our method better predicts the top-1 accuracy than other evaluation frameworks, while making less assumptions on data distributions, training algorithms or underlying architectures. According to our method, we modify DeepCluster and our version outperforms it by achieving better cluster learnability on both ImageNet and STL-10. Visualizations show that our framework could predict the performance of the unseen intermediate checkpoints.
We believe our work is solid step towards understanding the current SSL algorithms and opens up interesting research directions. Future works could further explore the expresiivenes- a more theoretical context, extend this framework other field like pretrained language models, as well as devise new SSL algorithms that directly maximize intrinsic dimension or cluster learnability.
in
REFERENCES
Alessio Ansuini, Alessandro Laio, Jakob H Macke, and Davide Zoccolan. Intrinsic dimension of data representations in deep neural networks. Advances in Neural Information Processing Sys- tems, 12266111-622,,, 2019.
Philip Bachman, R Devon Hjelm, and William Buchwalter. Learning representations by maximiz- ing mutual information across views. Advances in Neural Information Processing Systems, 32: 35535-15545 2019a.
Philip Bachman, R. Devon Hjelm, and William Buchwalter. Learning representations by maximiz- ing mutual information across views. In NeurlPS, pages 15509- 2019b.
Clay Beckner, Janet B Pierrehumbert, and Jennifer Hay. The emergence of linguistic structure in an online iterated learning task. Journal of Language Evolution, 100):160 2017.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International Conference on Machine Learning, pages 531-540. PMLR, 2018.
Léonard Blier and Yann Ollivier. The description length of deep learning models, arXiv preprint 0704044802.074 2018
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsu- pervised learning of visual features. In Proceedings of the European Conference on Computer Vision (ECCV), pages 132-149, 2018.

---

Under review as a conference paper at ICLR 2022
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. arXiv preprint arXiv:2006.09882 09882, 2020.
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in supervupe vision transformers. arXiv preprint arXiv:2104. 14294, 2021.
Gregory J Chaitin. Thinking About Godel And Turing: Essays On Complexity, 1970-2007. World scientific, 2007.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint arXiv:2002.05709 2020a.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton. Big self-supervised models are strong semi-supervised learners. Advances in Neural Information Processing Systems, 13:22243-222555 2020b.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15750-15758, 2021.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.0425 2020c.
Noam Chomsky, Rules and representations. Behavioral and brain sciences, 3(1):1-15, 1980.
Philip Dawid. Present position and potential developments: Some personal views statistical theory the prequential approach. Journal of the Royal Statistical Society: Series A (General), 147(2): 278-290 1984.
Weijian Deng and Liang Zheng. Are labels always necessary for classifier accuracy evaluation? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15009, 2021.
Elena Facco, Maria d' Errico, Alex Rodriguez, and Alessandro Laio. Estimating the intrinsic dimen- sion of datasets by a minimal neighborhood information. Scientific reports, 7(1):1-8, 2017.
Thomas L Griffiths, Brian R Christian, and Michael L Kalish. Revealing priors on category struc- tures through iterated learning. Proceedings of the 28th annual conference of the Cognitive Science Society, volume 199, 2006.
Bean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach to self-supervised learning. Advances Neural Information Processing Systems, 33, 2020.
Shangmin Guo, Yi Ren, Serhii Havrylov, Stella Frank, Ivan Titov, and Kenny Smith. The emergence of compositional languages for numeric concepts through iterated learning in neural agents. arXiv preprint 1wx.v:1910.052911 2019.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pages 9729-9733 2020.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew M. Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with a constrained variational framework. In ICLR, 2017.
R Devon Hjelm, Alex Fedorov, Samuel Marchiildaa Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv: 188 06670, 2018.
10

---

Under review as a conference paper at ICLR 2022
Jacqueline van Kampen. The learnability of syntactic categories. LOT Occasional Series, 3:245 256, 2004.
Simon Kirby, Tom Griffiths, and Kenny Smith. Iterated learning and the evolution of language. Current opinion in neurobiology, 28:108-114, 2014.
Iro Laina, Ruth Fong, and Andrea Vedaldi. Quantifying learnability and describability of visual con- cepts emerging in representation learning. Advances in Neural Information Processing Systems, 33, 2020.
Elizaveta Levina and Peter Bickel. Maximum likelihood estimation of intrinsic dimension. In L. Saul, Y. Weiss, and L. Bottou, editors. Advances in Neural Information Processing Sys- tems, volume 17. MIT Press, 2005. URUlntpsr//proceeeinngs wttp://www..iinnn............o.
pdf
Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. arXiv preprint arXiv: /804,880443 2018.
Fushan Li and Michael Bowling. Base-of-teaching and language structure from emergent commu-
nication. In Advances in Neural Information Processing Systems, pages 15825-15835, 2019.
Junnan Li, Pan Zhou, Caiming Xiong, and Steven Hoi. Prototypical contrastive learning of unsu- pervised representations. In International Conference on Learning Representations, 2021. URL net FowwmmiddKKyykaaaoooor.roo
Ralph Linsker. Self-organization in a perceptual network. Computer, (3)):105-117, 1988.
Chenxi Liu, Piotr Dollár, Kaiming He, Ross Girshick, Alan Yuille, and Saining Xie. Are labels necessary for neural architecture search? In European Conference Computer Vision, pages 798-813. Springer, 2020.
Yuchen Lu, Soumye Singhal, Florian Strub, Olivier Pietquin, and Aaron Courville. Countering language drift with seeded iterated learning. arXiv preprint arXiv:2003. /2694, 2020.
Ishan Misra and Laurens van der Maaten. Self-supervised learning of pretext-invariant representa- tions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 6707-6717, 2020.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding, 2018. URL httt:://a//xiii/ org/ 0101/1077770388 cite 107.0:880..03748.
Karl W. Pettis, Thomas A. Bailey, Anil K. Jain, and Richard C. Dubes. An intrinsic dimensionality estimator from near-neighbor information. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1AM:-1(1):25--1 1979a. doi: 10.1 1199/TPMM.1999.4766665
Karl W. Pettis, Thomas A. Bailey, Anil K. Jain, and Richard Dubes. An intrinsic dimensionality estimator from near-neighbor information. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-I(1):25- 1979b. doi: 10. 1911099
Phil Pope.
Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact learning. In International Conference Learning Repre- wttp:/wwwwwweeeeeonneeeeeee. sentations, 2021. URL /tt
9X2Go23
Eva Portelance. Michael C Frank, Dan Jurafsky, Alessandro Sordoni, and Romain Laroche. The emergence of the shape bias results from communicative efficiency. arXiv e-prints, pages arXiv- 2109, 2021.
Anna N Rafferty, Thomas I. Griffiths, and Marc Eutlinger. Exploring the relationship between learn- ability and linguistic universals. In Proceedings of the 2nd Workshop on Cognitive Modeling and Computational Linguistics, pages 49-57, 2011.
Colorado J Reed, Sean Metzger, Aravind Srinivas, Trevor Darrell, and Kurt Keutzer. Selfaugment: Automatic augmentation policies for sule-supe learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 2683,, 2021.

---

Under review as a conference paper at ICLR 2022
Yi Ren, Shangmin Guo, Matthieu Labeau, Shay B Cohen, and Simon Kirby. Compositional lan- guages emerge in a neural iterated learning model. arXiv preprint arXiv:2002.01365, 2020.
Kenny Smith, Monica Tamariz, and Simon Kirby. Linguistic structure is an evolutionary trade-off between simplicity and expressivity. In Proceedings of the annual meeting of the cognitive science society, volume 35, 2013.
Samarth Swarup and Les Gasser. Simple, but not too simple: Learnability vs. functionality in language evolution. In The Evolution Of Language, pages 299-306. World Scientific, 2008.
Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning? arXiv preprint arXiv:2005. 10243, 2020.
Michael Tschannen, Josip Djolonga, Paul K. Rubenstein, Sylvain Gelly, and Mario Lucic. On mu- tual information maximization for representation learning. In International Conference on Learn- ing Representations, 2020. URL /tts::/ //tpprss////eeevviee.. net formm/orrmmmmmmm www.neeeoooooiiddoooooooo 4FPH
Ankit Vani, Max Schwarzer, Yuchen Lu, Eeshan Dhekane, and Aaron Courville. Iterated learning for emergent systematicity in [vqa}. In International Conference on Learning Representations, 2021. URL httttt:ttp//peeeeeeeeee
wwtp///tto//ttte forum? Ftt
Vincent, H. Larochelle, Y. Bengio, and P.-A. Manzagol. Extracting and composing robust features with denoising autoencoders. In International Conference Machine Learning proceedings. 2008.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In International Conference on Machine Learning, PMLR, 2020.
pages
William F Whitney, Min Jae Song, David Brandfonbrener, Jaan Altosaar, and Kyunghyun Cho. Evaluating representations by the complexity learning low-loss predictors. In Neural Com- pression: From Information Theory Applications Workshop @ ICLR 2021, 2021.
Applications-Woorshhopp
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance discrimination. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3733-3742, 2018
Jing Xu, Thomas Griffiths, and Mike Dowman. Replicating color term universals through human iterated learning. In Proceedings of the Annual Meeting of the Cognitive Science Society, vol- ume 32, 2010.
Fei Xue, Hongbing Ji, Wenbo Zhang, and Cao. Self-supervised video representation learning by maximizing mutual information. Signal Processing: Image Communication, 88: 15967, 2020.
Yuchen Zhou and Dan Yurovsky. A common framework for quantifying the learnabllity of nouns and verbs. In Proceedings of the Annual Meeting of the Cognitive Science Society, volume 43, 2021.
12

---

Under review as a conference paper at ICLR 2022
Appendices
A
FUTHER DISCUSSION ON CURRENT SSL PRACTICE
We further discuss the motivation behind our framework, and how approach some of the SSL practice throught the lense of expressiveness and learnability.
Contrastive Learning With our new view on representation quality by expressiveness- learnailiity, we can try to analyze some of the practice in the contrastive learning and see why it works and fails. Contrastive learning is typical example of such trade-off, and has the follow- ing objective:
e F(a) E B x log Fla) + F(o)T
aims to output distinguishable feature vectors between positive and negative examples which turns out to increase the expressiveness. Meanwhile, it aims to make the output vectors among positive examples be similar by which higher value of learnability is ensured, since ideally the another leamner only need to see one example to generalize to other positive examples. As result, the degree of Iearnability here can be controlled by the definition of positive examples. more diverse selection of the positive examples should make the F leaning toward the learnability side, since each example could represent a larger fraction of the inputs. It well acknow the self-supervised community that a diverse data augmentation is essential part of the contrastive learning, and under this framework, is a source of the learnability pressure.
Clustering-basedd Learning Perhaps expressiveness--erraaaii framework is more obvious in the clustering- based algorithm like DeepCluster (Caron et al. 2018) and SwAV (Caron et al.) 2020). In these algorithms, you learn only FF but also bank of cluster centroids as well as assignments ÿ F(r). As a result, we can also view these algorithms as finding ğ G(r), where G is composed of and
In these methods, the expressiveness is achieved by using large number of clusters as well as some uniformity constraint, and this can ensure each data has distinctive cluster assignment. SwAV achieves it with the SinkHorn iterations, while the DeepCluster, at least in the early version, would balance the sampling ratio of images to make the cluster uniform as well as resolving the empty cluster issues.
The learnability requirements are implicitly enforced as well. Since the space of ÿ is usually less than æ, there are usually multiple data being assigned to the same cluster. This already ensure that a new learner should able to see a few examples to generalize within the cluster. In addition, these algorithms also leverage the data augmentation, that G(x) and ((x should have the same ÿ. which further improves the learnability.
B CLUSTER LEARNABILITY AND PREQUENTIAL CODELENGTH
Note that Epn. 3 can be connected to the compression lower bound of the emerged cluster assign-
ments datasets {2,, 0i NN via prequential coding (Dawid 1984). The prequential codelength defined as
Lyrey Σ pog (xc))))))))))))))))))))))))
where (2k55, ))<s)) is conditional model, which can be computed from our KNN classifier probabilities. If Eqn, is the online learning accuracy, then Equ. Iis online learning cross-entropy loss. Higher CL. lead to lower prequential compression bounds the emerged clusters.
13

---

Under review as a conference paper at ICLR 2022
C OTHER ATTEMPTS ON CHARACTERIZING EXPRESSIVENESS AND LEARNABILITY
In this section, we discussed our other unsuccessful attempts on characterizing expressiveness and learnability.
24
21/022
MINBC
2.4
4.2
2.8
20
24
02518
Figure 5: Other attempts on measuring expressiveness and learnability, In all cases, MI is estimated by training a MINE network, where learnability estimated by training student network that takes the images and predicts the representations with cosine loss (Left) or L2 loss (Middle) or the K- means labels of the representations (Right).
Previous works propose maximizing mutual information between inputs and the representations as way of self-supervised learning (Bachman et al. 2019a; Xue et al. 2020 Hjelm et al., 2018 Linsker] 1988). However, [Tschannen et al. (2020) argue that there is more holistic picture behind their success story, beyond mutual information alone, e.g., the trade-off between the amount of information that can be stored against how hard is to extract it in the downstream tasks.
We hypothesize that mutual information is indeed part of the solution and it corresponds to the expressiveness representation. E.g.. a one-to-one map between images and representations would have a high MI, while degenerate solution would not. As result, tried using MINE (Belghazi et al. 2018) to compute a lower bound on the mutual information. We use ResNet18 as our MINE network and train for epochs and report the estimate for validation set.
For learnability, we also try fitting a student ResNer18 from scratch to learn the map from images H; representations z; produced by the pretrained checkpoints. Since the representation space is continuous, we experiment with both L2 loss and cosine similarity. Furthermore, inspired by the cluster learnability, we propose also propose to let the student network to predict emerged cluster labels ÿ from images 24. We also use ResNet18 8 as our student, train for 5 epochs, and report the validation metrics the learnability.
The qualitative results can be found in Figure 5 We find all these attempts does not produce any meaningful signal. There many problems. Firstly estimating MI usng MINE is known tive to many things like learning rate and architecture of MINE network (Tschannen et al.) 2020). Secondly the loss of directly mapping to the continuous vectors 2; is heavily effected by dimension- ality of the space. Thirdly, there is a architecture bias when we use ResNet18 the students. ViT checkpoints in general performs poorer since it is too different from the ResNets. As result, our proposed method CL and ID do not have these problem, mainly because avoid training another neural network from scratch.
sensi-
D MORE RESULTS ON KNNDEEPCLUSTER
We performed more experiments STL-10 between KNNDeepCluster and DeepCluster under dif- We find that our method able to consis-
ferent number of prototypes. The results are in Table 2 tently out-perform the baseline under different configurations.
To further understand the effect of replacing the K-means labels with the KNN predictions, we perform some clustering analysis pretrained DeepCluster checkpoint in Figure on STL-10.
14

---

Under review as a conference paper at ICLR 2022
STLI0
# Prototypes/ Eval. Method
INN
5NN
DeepCluster
74.96
77.78
2048
KNNDeepcluster
76.79
78.96
DeepCluster
74.31
76.63
512
KNNDeepcluster
76.03
79.11
DeepCluster
75.05
77.71
128
KNNDeepcluster
75.59
78.86
Table Performance at different number of clusters.
300
16
24
10
75
35
180
100
26
20
30
(a)
(b)
(c)
Figure 6: Cluster Analysis with Davies-Bouldin Bouldin (DB) index and the effect of replacing Kmeans labels with KNN predictions STL10 with 512 clusters. Left: After Kmeans, each cluster has unequal size, and the larger cluster are also well separated (low DB index). Middle and Right: The originally well separated clusters gain size while the opposite ones lose size after KNN assignment. The smallest DB index clusters are least effected by the re-assignment.
find that after the initial K-means clustering there is an uneven distribution of cluster size, and larger clusters have lower Davies-Bouldin index (DB Index)are more separable from the smaller cluster. We find the reassignment with KNN prediction would punish the smaller clusters with larger DB index, and their cluster members absorbed into large clusters. As result, in the next epoch, the network pays more attention on fitting labels coming from large and well-separable clusters
15

---

Under review as a conference paper at ICLR 2022
Name
Method
Architecture
resnet18
Supervised
ResNet
resnet34
Supervised
ResNet
resnet50
Supervised
ResNet
moco_vl 1__000eppppppp
Unsupervised
ResNet
noco_v2.200cp
Unsupervised
ResNet
moco v2 800ep
Unsupervised
ResNet
selav2 400ep 2x224
Unsupervised
ResNet
selav2_400ep
Unsupervised
ResNet
4eepclusterv2.400ppp.. 2x224
Unsupervised
ResNet
deepclusterv2.44006
Unsupervised
ResNet
deepelusterv2.8006.
Unsupervised
ResNet
swav 100ep
Unsupervised
ResNet
swav 200ep
Unsupervised
ResNet
swav_800ep
Unsupervised
ResNet
dino_resnet50)
Unsupervised
ResNet
dino_deitsmalll dino deittdeetsm
Unsupervised
VIT
Unsupervised
VIT
Unsupervised
VIT
dino_vitbase 6
Unsupervised
VIT
dino xeit mwdium 24. _4_p16
Unsupervised
XCIT
Unsupervised
XCIT
simcirv2.r501xxsk0
Unsupervised
ResNet
simclrv2.550lxskl
Unsupervised
ResNet
resnet50. 1x insdis pirl
Unsupervised
ResNet
Unsupervised
ResNet
Unsupervised
ResNet
infomin
Unsupervised
ResNet
pcl_vl
Unsupervised
ResNet
pcl_v2
Unsupervised
ResNet
byol
Unsupervised
ResNet
Table Full list the pretrained checkpoints collected. The list of SSL methods are: MoCo-vi (He
al. 2020),
MoCo-v2 (Chen et al. (200cc). SeLA-v2 (Caron et al.) [2020). DeepCluster-v2 Caron
et al.
2020).
SwAV (Caron al. (020), DINO (Caron et al. 2021). SimCLR v2 (Chen et al. 2020b),
Sim CLR-v
(Chen et al. 2020a). PCL-v1 (Li et al.) 2021). l). PCL-v2 (Li et al. 2021). PIRL Missa
and Maaten
2020), BYOL GGril et al. 2020). InfoMin (Tian et al. 2020), InsDis (Wu et al.
2018
16


Reviews:
[{"review_id": "rC2uJkTK4No", "reviewer": "Reviewer_Fbk6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Advantage:\n1.\tCurrent assessment methods for self-supervised learning depend on the availability of labels, while the two metrics proposed in this paper escape this dependency. The proposed metrics provide a new evaluation protocol for self-supervised learning in the case where annotation is absent.\n2.\tThe proposed two metrics are shown to be highly correlated with the performance of the self-supervised methods on the KNN classification task, which inspires further exploration of the relationship between expressiveness-learnability and representation quality.\n\nDisadvantage:\n1. The performance of linear evaluation and KNN classification tasks on the pre-trained dataset is approaching a bottleneck, and more attention has been shifted to the transferred performance on other datasets. However, this paper only shows the correlation between classification performance on the pre-trained dataset and the proposed metrics, while ignoring the transfer performance on other datasets, which limits the impact and significance of the paper. The current application scenario is not attractive for unsupervised learning.\n2.  Complexity is important for the scope of application of the method. However, the complexity of the proposed metrics is not discussed in this paper.\n", "summary_of_the_paper": "This paper proposes two metrics for assessing the quality of self-supervised learning representations in terms of expressiveness and learnability. Expressiveness expects to maximize the mutual information between the representation and the original data, while learnability emphasizes the representation suppose to be simpler and more learnable. Based on these two intuitions, the author applies Intrinsic Dimension (ID) and Cluster Learnability (CL) as the measurements of expressiveness and learnability respectively to predict downstream classification performance. The authors collect 30 checkpoints of recent self-supervised methods to validate the proposed metrics on two datasets, ImageNet and STL_10, and the results show a high correlation between the proposed metrics and the downstream classification performance.", "summary_of_the_review": "1. Section 3.2 indicates that the estimator is exact for uniformly distributed data, and datasets applied in experiments are balanced. Is the proposed metrics only work for the balanced dataset?\n2. Figure1 is fuzzy and the name of methods overlap badly, which affects the reading. The description to the calculation of CL is unclear and confusing. If I understand correctly, is each sample is classified according to all the samples have seen before?\n3. The improvement brought by KNNDeepCluster is tiny compared to the base method, which is hard to be convinced of the effectiveness of the proposed method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "VxYVmakdy1f", "reviewer": "Reviewer_Brvt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n-  Pearson correlation coefficient between the proposed factors (ID and CL) and final accuracy is surprisingly high. Thus, they can be a very good unsupervised monitor for self-supervised training.\n- The proposed algorithm inspired by CL outperforms DeepCluster.\n\nWeakness:\n- The technical part is somewhat simple and lacks insight into the proposed factors. For example, the proposed factors seem to be independent of the learning methods and learning paradigms, since they characterize the expressiveness and learnability of pre-trained representations. However, in the top left of Fig 1, DINO has both better ID and CL than resnet50, while supervised learned resnet50 should outperform DINO. As a comparison, for Align-Unif Predictor (top right of Fig 1), resnet50 has better alignment and uniformity than dino (and all self-supervised methods), which matches the fact.\n- According to the paper, higher ID indicates better expressiveness. However, in the experiments (top left and bottom left of Fig 1), resnet50 has less ID than resnet34, and resnet34 has less ID than resnet18, which is an apparent contradiction. Therefore, the motivation for seeking higher ID is not well supported.\n- Furthermore, Pearson correlation coefficient as the only metric is not enough to conclude that ID and CL are better than other existing predictors. This paper needs more investigation on their scope of application and limitations.\n\nMinor comments:\n- Different models have different normalization of the feature. For example, SimCLR forces $||f||=1$ and BYOL does not. Thus, using cosine distance to infer ID is not correct, since cosine distance is equivalent to Euclidean distance iff $||f||=const$.\n- Fig 1 is not a vector diagram (become fuzzy when zooming in) and there are many repetitive labels. \n", "summary_of_the_paper": "This paper tries to give a measurement method to evaluate the learned model, which is highly correlated with the final test accuracy.\nThe measurement method depends on two key factors: Intrinsic Dimension (ID) and CLuster Learnability (CL).\nThis paper claims that the model with higher ID and CL performs better. Using ID and CL to predict top-1 accuracy can achieve a Pearson correlation coefficient of 0.93, which is better than existing predictors (e.g., alignment and uniformity).\nInspired by the above observation, this paper proposes a modified DeepCluster algorithm to increase the final performance.", "summary_of_the_review": "This paper is novel and the results are interesting. However, the technical part is somewhat simple, and the insight behind the observations needs further exploration.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MOSY2ObhTEF", "reviewer": "Reviewer_Y1ph", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "strengths:\n\n(1) This paper is generally well-written and the motivation is clear. How to better evaluate the representations learned by various self-supervised learning methods is an important question and it will give further instructions to develop new SSL algorithms. \n\n(2) The experimental results demonstrate the effectiveness of the proposed metric CL and ID. I appreciate the authors for their hard but valuable work to collect and evaluate 30 existing SSL checkpoints. \n\n----------------------------------------------------------------------------------------------------------------------------------------------------------\n\nweakness:\n\n(1) It is not clear why we should use CL and ID for evaluation. In other words, is it sufficient (enough) to use these two metrics? I think this work could be better to give some theoretical analysis (on the decomposition of CL and ID) instead of heuristic design. Although the experimental results show some advantages, it is still hard to understand why should we use these two metrics.\n\n(2) The alignment and uniformity framework is more suitable for contrastive methods (by decomposing the InfoNCE loss into two terms) and it may be not an appropriate indicator for other methods, e.g., DINO. Hence, I think the comparison method is not a strong baseline. \n\n(3) I think it is better to design an SSL algorithm by directly optimizing CL and ID. The modifications made on DeepCluster seems a little far-fetched with proposed objective and the results are not convincing enough, especially on ImageNet. It feels to me that it is hard to formalize CL and ID as our loss objectives to optimize. Although mentioned in the conclusion, I think the authors should make more efforts along this direction to make this work more complete. \n\n(4) As the main result of this paper, Figure 1 is blurry. It is not clear what is the relationship between accuracy and colors of different brightness. Also, there exist some typos (e.g., 'deepcluste' should be 'deepcluster' in Figure 1). Hence, I suggest the authors to improve the quality of Figure 1.", "summary_of_the_paper": "This paper proposes to use Cluster Learnability (CL) and Intrinsic Dimension (ID) to evaluate the representations learned by self-supervised learning methods. The authors collected 30 checkpoints and show that their method is more predictable when compared to other methods, e.g., alignment and uniformity. Moreover, the authors modified the labels generated by K-means in DeepCluster to improve the learnability of the representations and the results demonstrate slight improvements.\n", "summary_of_the_review": "This paper is generally well-written and the motivation is clear. However, I still have some concerns (see weakness) and I think this paper could be more complete by providing theoretical analysis or developing an SSL algorithm which directly optimizes CL and ID.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AIW19gEgm2v", "reviewer": "Reviewer_xT8d", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "General comments: \nThe general direction and the problem setting which this paper aims to investigate are interesting, but I found that both ID and CL frameworks are heavily identical to the previous frameworks and offer no additional insights on understanding representation quality or other aspects of network learning.\n\nDetailed comments:\n-- I found that the writing and notations of this paper are quite hard to follow. And Some claims and analygies are over-exaggerated. For example, i) I don’t understand how language compositionality has anything related to the motivation of this work. ii) In contribution (section 1), the authors said that they analyze self-supervised learning using the proposed methods and then in the second paragraph, they said they evaluates on both self-supervised and supervised models. iii) In Section 3.3, a lot of terms are not properly explained: I don’t understand what $KNN(z_i|z_{k<i},\\tilde{y}_{k<i})$ , and “seeing the pairs”, “online learning accuracy” really mean.  iv) I don’t think Q1 and Q2 in Section 4 are different. If high-performing models are having high CL and ID scores, and automatically it indicates that they have a high correlation?\n\n-- Low novelty. The formulation of ID is nearly identical to the original publication from Ansuini, et al, including the explanations and notations used in Section 3.2. The formulation of KNN seems to be a straightforward extension.\n\n-- Comparing to Align-Unif. The results in the original paper indicate that lower alignment and lower uniform would have a better prediction performance. But in the Fig 1., it seems to indicate otherwise, which is not further justified. \n\n-- Using CL framework to improve self-supervised methods leads to very marginal improvement on ImageNet. Without additional information such as variance, it’s hard to confirm that CL systematically improves representation learning. Further, I found this section is a bit deviate from the main focus of this work. Additional experiments, insights or visualisation on how different ID and CL could lead to different representation learning quality and limitation should be more helpful on justifying/understanding “expressiveness” and “learnability” of representation learning.\n", "summary_of_the_paper": "This paper proposes Intrinsic Dimension (ID) and Cluster Learnability (CL) as an alternative solution to efficiently evaluate learned representation quality of pre-trained networks, without using down-stream tasks/labels. These two frameworks are inspired by finding “expressiveness” – finding the smallest number of variables to approximate the representation; and “learnability” – number of data samples needed for KNN clustering.\n\nExtensive experiments have been evaluated on models trained with both supervised and unsupervised methods, and results showed that ID + CL would produce a high correlation with prediction accuracy from these methods, comparing to baselines. Finally, the authors argue that CL can also be incorporated into DeepCluster (an unsupervised method), as an auxiliary loss to further improve the prediction performance.\n", "summary_of_the_review": "This paper proposed Intrinsic Dimension (ID) and Cluster Learnability (CL) to estimate supervised and self-supervised model's prediction performance. However, the proposed frameworks are heavily identical to the existing works. Considering the less-structured writing and confusing notations, I believe this work has not met the publication quality.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The problem studied in this paper is interesting and the high-level motivation of the proposed research is reasonable. However, as pointed out by reviewers, it is not convincing that the developed components in the proposed method are able to address the issues mentioned in the high-level motivation. Furthermore, the experimental results are not convincing to verify the motivations either. Though the authors provided some clarifications in the rebuttal, reviewers' major concerns still remain.  

The authors are encouraged to take reviewers' concerns into consideration to revise the proposed method to make it a stronger work for future submission. Based on its current form, this work is not ready for publication at ICLR.
Decision: Reject