summaries: This paper tries to give a measurement method to evaluate the learned model, which is highly correlated with the final test accuracy. The measurement method depends on two key factors: Intrinsic Dimension (ID) and CLuster Learnability (CL). This 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). Inspired by the above observation, this paper proposes a modified DeepCluster algorithm to increase the final performance. 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. 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.  Extensive 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.  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. 
abstractText: 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 Kmeans 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 intermediate checkpoints can also be well predicted under our framework, suggesting the possibility of developing new SSL algorithms without labels.
references.authors: Alessio Ansuini Alessandro Laio Jakob H Macke Davide Zoccolan
references.title: Intrinsic dimension of data representations in deep neural networks
references.venue: Advances in Neural Information Processing Systems,
references.authors: Philip Bachman R Devon Hjelm William Buchwalter
references.title: Learning representations by maximizing mutual information across views
references.venue: Advances in Neural Information Processing Systems,
references.authors: Philip Bachman R. Devon Hjelm William Buchwalter
references.title: Learning representations by maximizing mutual information across views
references.venue: In NeurIPS,
references.authors: Clay Beckner Janet B Pierrehumbert Jennifer Hay
references.title: The emergence of linguistic structure in an online iterated learning task
references.venue: Journal of Language Evolution,
references.authors: Mohamed Ishmael Belghazi Aristide Baratin Sai Rajeshwar Sherjil Ozair Yoshua Bengio Aaron Courville Devon Hjelm
references.title: Mutual information neural estimation
references.venue: In International Conference on Machine Learning,
references.authors: Léonard Blier Yann Ollivier
references.title: The description length of deep learning models
references.venue: arXiv preprint arXiv:1802.07044,
references.authors: Mathilde Caron Piotr Bojanowski Armand Joulin Matthijs Douze
references.title: Deep clustering for unsupervised learning of visual features
references.venue: In Proceedings of the European Conference on Computer Vision (ECCV),
references.authors: Mathilde Caron Ishan Misra Julien Mairal Priya Goyal Piotr Bojanowski Armand Joulin
references.title: Unsupervised learning of visual features by contrasting cluster assignments
references.venue: arXiv preprint arXiv:2006.09882,
references.authors: Mathilde Caron Hugo Touvron Ishan Misra Hervé Jégou Julien Mairal Piotr Bojanowski Armand Joulin
references.title: Emerging properties in self-supervised vision transformers
references.venue: arXiv preprint arXiv:2104.14294,
references.authors: Gregory J Chaitin
references.title: Thinking About Godel And Turing: Essays On Complexity, 1970–2007
references.venue: World scientific,
references.authors: Ting Chen Simon Kornblith Mohammad Norouzi Geoffrey Hinton
references.title: A simple framework for contrastive learning of visual representations
references.venue: arXiv preprint arXiv:2002.05709,
references.authors: Ting Chen Simon Kornblith Kevin Swersky Mohammad Norouzi Geoffrey E Hinton
references.title: Big self-supervised models are strong semi-supervised learners
references.venue: Advances in Neural Information Processing Systems,
references.authors: Xinlei Chen Kaiming He
references.title: Exploring simple siamese representation learning
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Xinlei Chen Haoqi Fan Ross Girshick Kaiming He
references.title: Improved baselines with momentum contrastive learning
references.venue: arXiv preprint arXiv:2003.04297,
references.authors: A Philip Dawid
references.title: Present position and potential developments: Some personal views statistical theory the prequential approach
references.venue: Journal of the Royal Statistical Society: Series A (General),
references.authors: Weijian Deng Liang Zheng
references.title: Are labels always necessary for classifier accuracy evaluation
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Elena Facco Maria d’Errico Alex Rodriguez Alessandro Laio
references.title: Estimating the intrinsic dimension of datasets by a minimal neighborhood information
references.venue: Scientific reports,
references.authors: Thomas L Griffiths Brian R Christian Michael L Kalish
references.title: Revealing priors on category structures through iterated learning
references.venue: In Proceedings of the 28th annual conference of the Cognitive Science Society,
references.authors: Jean-Bastien Grill Florian Strub Florent Altché Corentin Tallec Pierre Richemond Elena Buchatskaya Carl Doersch Bernardo Avila Pires Zhaohan Guo Mohammad Gheshlaghi Azar
references.title: Bootstrap your own latent-a new approach to self-supervised learning
references.venue: Advances in Neural Information Processing Systems,
references.authors: Shangmin Guo Yi Ren Serhii Havrylov Stella Frank Ivan Titov Kenny Smith
references.title: The emergence of compositional languages for numeric concepts through iterated learning in neural agents
references.authors: Kaiming He Haoqi Fan Yuxin Wu Saining Xie Ross Girshick
references.title: Momentum contrast for unsupervised visual representation learning
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Irina Higgins Loı̈c Matthey Arka Pal Christopher P. Burgess Xavier Glorot Matthew M. Botvinick Shakir Mohamed Alexander Lerchner
references.title: beta-vae: Learning basic visual concepts with a constrained variational framework
references.venue: In ICLR,
references.authors: R Devon Hjelm Alex Fedorov Samuel Lavoie-Marchildon Karan Grewal Phil Bachman Adam Trischler Yoshua Bengio
references.title: Learning deep representations by mutual information estimation and maximization
references.venue: arXiv preprint arXiv:1808.06670,
references.authors: Jacqueline van Kampen
references.title: The learnability of syntactic categories
references.venue: LOT Occasional Series,
references.authors: Simon Kirby Tom Griffiths Kenny Smith
references.title: Iterated learning and the evolution of language
references.venue: Current opinion in neurobiology,
references.authors: Iro Laina Ruth Fong Andrea Vedaldi
references.title: Quantifying learnability and describability of visual concepts emerging in representation learning
references.venue: Advances in Neural Information Processing Systems,
references.authors: Elizaveta Levina Peter Bickel
references.title: Maximum likelihood estimation of intrinsic dimension
references.venue: Advances in Neural Information Processing Systems,
references.authors: Chunyuan Li Heerad Farkhoor Rosanne Liu Jason Yosinski
references.title: Measuring the intrinsic dimension of objective landscapes
references.venue: arXiv preprint arXiv:1804.08838,
references.authors: Fushan Li Michael Bowling
references.title: Ease-of-teaching and language structure from emergent communication
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Junnan Li Pan Zhou Caiming Xiong Steven Hoi
references.title: Prototypical contrastive learning of unsupervised representations
references.venue: In International Conference on Learning Representations,
references.authors: Ralph Linsker
references.title: Self-organization in a perceptual network
references.authors: Chenxi Liu Piotr Dollár Kaiming He Ross Girshick Alan Yuille Saining Xie
references.title: Are labels necessary for neural architecture search
references.venue: In European Conference on Computer Vision,
references.authors: Yuchen Lu Soumye Singhal Florian Strub Olivier Pietquin Aaron Courville
references.title: Countering language drift with seeded iterated learning
references.venue: arXiv preprint arXiv:2003.12694,
references.authors: Ishan Misra Laurens van der Maaten
references.title: Self-supervised learning of pretext-invariant representations
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Aaron van den Oord Yazhe Li Oriol Vinyals
references.title: Representation learning with contrastive predictive coding, 2018
references.venue: URL http://arxiv.org/abs/1807.03748. cite arxiv:1807.03748
references.authors: Karl W. Pettis Thomas A. Bailey Anil K. Jain Richard C. Dubes
references.title: An intrinsic dimensionality estimator from near-neighbor information
references.venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,
references.authors: Karl W. Pettis Thomas A. Bailey Anil K. Jain Richard C. Dubes
references.title: An intrinsic dimensionality estimator from near-neighbor information
references.venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,
references.authors: Phil Pope Chen Zhu Ahmed Abdelkader Micah Goldblum Tom Goldstein
references.title: The intrinsic dimension of images and its impact on learning
references.venue: In International Conference on Learning Representations,
references.authors: Eva Portelance Michael C Frank Dan Jurafsky Alessandro Sordoni Romain Laroche
references.title: The emergence of the shape bias results from communicative efficiency
references.venue: arXiv e-prints, pages arXiv–
references.authors: Anna N Rafferty Thomas L Griffiths Marc Ettlinger
references.title: Exploring the relationship between learnability and linguistic universals
references.venue: In Proceedings of the 2nd Workshop on Cognitive Modeling and Computational Linguistics,
references.authors: Colorado J Reed Sean Metzger Aravind Srinivas Trevor Darrell Kurt Keutzer
references.title: Selfaugment: Automatic augmentation policies for self-supervised learning
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Yi Ren Shangmin Guo Matthieu Labeau Shay B Cohen Simon Kirby
references.title: Compositional languages emerge in a neural iterated learning model
references.venue: arXiv preprint arXiv:2002.01365,
references.authors: Kenny Smith Monica Tamariz Simon Kirby
references.title: Linguistic structure is an evolutionary trade-off between simplicity and expressivity
references.venue: In Proceedings of the annual meeting of the cognitive science society,
references.authors: Samarth Swarup Les Gasser
references.title: Simple, but not too simple: Learnability vs. functionality in language evolution. In The Evolution Of Language, pages 299–306
references.venue: World Scientific,
references.authors: Yonglong Tian Chen Sun Ben Poole Dilip Krishnan Cordelia Schmid Phillip Isola
references.title: What makes for good views for contrastive learning
references.venue: arXiv preprint arXiv:2005.10243,
references.authors: Michael Tschannen Josip Djolonga Paul K. Rubenstein Sylvain Gelly Mario Lucic
references.title: On mutual information maximization for representation learning
references.venue: In International Conference on Learning Representations,
references.authors: Ankit Vani Max Schwarzer Yuchen Lu Eeshan Dhekane Aaron Courville
references.title: Iterated learning for emergent systematicity in {vqa
references.venue: In International Conference on Learning Representations,
references.authors: P. Vincent H. Larochelle Y. Bengio P.-A. Manzagol
references.title: Extracting and composing robust features with denoising autoencoders
references.venue: In International Conference on Machine Learning proceedings
references.authors: Tongzhou Wang Phillip Isola
references.title: Understanding contrastive representation learning through alignment and uniformity on the hypersphere
references.venue: In International Conference on Machine Learning,
references.authors: William F Whitney Min Jae Song David Brandfonbrener Jaan Altosaar Kyunghyun Cho
references.title: Evaluating representations by the complexity of learning low-loss predictors
references.venue: In Neural Compression: From Information Theory to Applications–Workshop@ ICLR 2021,
references.authors: Zhirong Wu Yuanjun Xiong Stella X Yu Dahua Lin
references.title: Unsupervised feature learning via nonparametric instance discrimination
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Jing Xu Thomas Griffiths Mike Dowman
references.title: Replicating color term universals through human iterated learning
references.venue: In Proceedings of the Annual Meeting of the Cognitive Science Society,
references.authors: Fei Xue Hongbing Ji Wenbo Zhang Yi Cao
references.title: Self-supervised video representation learning by maximizing mutual information
references.venue: Signal Processing: Image Communication,
references.authors: Yuchen Zhou Dan Yurovsky
references.title: A common framework for quantifying the learnability of nouns and verbs
references.venue: In Proceedings of the Annual Meeting of the Cognitive Science Society,
sections.heading: 1 INTRODUCTION
sections.text: We consider the unsupervised learning scenario, which aims at learning distributed representations for complex natural data without human annotations. Despite great recent progress in selfsupervised 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 analogy with the evolution of human language. Recent literature (Swarup and Gasser, 2008; Smith et al., 2013) suggests that linguistic structure arises as a 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, Kirby et al. (2014) states that language evolution undergoes an iterated learning process, where each individual acquires language by observing a limited amount of language outputs of others (Chomsky, 1980). This process induces a form of compression, which makes the language simpler and more learnable for the next generation. Linguistic structure, e.g., compositionality, emerges between these opposing forces.
  A similar guiding principle can be applied when learning representations of natural data. Many existing methods in self-supervised learning can be considered as attempts to increase expressiveness of the representations, i.e., by maximizing or controlling the mutual information between inputs and representations, either through reconstruction (Vincent et al., 2008; Higgins et al., 2017) or contrastive learning (Oord et al., 2018; Bachman et al., 2019b). We argue that in addition to maximizing expressiveness, a 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 expressiveness 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 techniques, 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
  from Laina et al. (2020), we 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 representations. 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 a case-study in which we improve upon DeepCluster (Caron et al., 2018), which is a 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 resulting method, KNN-DeepCluster, 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 improves 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 at 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 selfsupervised and supervised checkpoints. We show that CL-ID is more correlated with the Top1 accuracy than previous approaches, with a Pearson’s r of 0.93.
  • We propose a modification to DeepCluster to increase its cluster learnability. The resulting algorithm, KNN-DeepCluster is able to outperform DeepCluster.
sections.heading: 2 RELATED WORK
sections.text: Representation Evaluation Several recent works address the question of representation evaluation in self-supervised learning. Whitney et al. (2021) 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 are shown to be well correlated with the supervised evaluation (Reed et al., 2021; Deng and Zheng, 2021) or architecture search (Liu et al., 2020). However, as 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.
  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 intrinsic dimension of loss landscape (Li et al., 2018), which measures minimum dimension of parameter space needed to optimize. We build upon extensive work on estimating intrinsic dimension. Applying local neighborhood information to estimate the intrinsic dimension is not a new idea, and it is shown to be more superior to the global eigenvalue approach (Pettis et al., 1979b). 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 classification 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 et 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, a 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 at all. More discussion can be found in Section 5.
  Learnability, Ease-of-Transmission and Compression Learnability has been argued to be a hallmark of the human language in order to be effortlessly transmitted through generations (Kirby et al., 2014; Rafferty et al., 2011; Beckner et al., 2017; Zhou and Yurovsky, 2021; Kampen, 2004), and
  it is also true for visual concepts like color (Xu et al., 2010), categories (Griffiths et al., 2006), shapes (Portelance et al., 2021) etc. In deep learning, it has been explored in the context of emergent communication (Ren et al., 2020; Guo et al., 2019; Li and Bowling, 2019), language drift (Lu et al., 2020), and neural module networks (Vani et al., 2021), but it is less explored for vision representation learning, except for a human study on just two SSL methods Laina et al. (2020). Learnability has a tight 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 it to quantify the learnability of the representation, in the sense that if the emerged Kmeans clustering is more learnable, then the same KNN learner could achieve a lower compression bound via prequential coding.
sections.heading: 3 PROPOSED FRAMEWORK
sections.text: In this section, we introduce our setup and define our measures of expressiveness and learnability.
sections.heading: 3.1 NOTATION
sections.text: We consider the following setting: we assume we have a dataset of images {xi}Ni=1 represented in a pixel space X ⊂ Rd, where xi ∼ P are sampled i.i.d from some natural image distribution P over X . We also consider representation mapsF : X → Rm, typically pretrained neural networks, which represent any image as an m-dimensional vector. Any such map forms a representation dataset Z = {zi}Ni=1 where zi = F(xi). Given zi ∈ Z and an integer k ≥ 1, we denote by NN(zi, k) the k-th nearest neighbor of zi. While we generally mean ‘nearest’ with respect to Euclidean distance, in practice we will also use the cosine distance function,1
  D(z1, z2) = 2− 2 cos(z1, z2) (1) Let rik = D(zi, NN(zi, k)) be the distance of the data point zi to its k-th nearest neighbor.
sections.heading: 3.2 INTRINSIC DIMENSION (ID)
sections.text: To measure expressiveness, we propose to use the notion of intrinsic dimensionality (ID) of the data in the representation space (Pettis et al., 1979a). Intuitively, as the representation becomes more expressive, we expect it to be able to represent images coming from more fine-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 a highly nonlinear manifold is a challenging problem (e.g., Levina and Bickel, 2005). In this work, we leverage the nearest neighbor-based method of Facco et al. (2017) to estimate ID, which uses only the first two nearest neighbors of each 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 et 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 µi = ri2/ri1 be the ratio of distances for the data point zi. We suppose the points are sampled on a manifold with intrinsic dimension d. It can be shown that, under the above local uniformity assumption, µi follows a Pareto distribution with parameter d+ 1 on [1,∞). That is
  P (µ1, · · · , µN |d) = dN N∏ i=1 µ −(d+1) i (2)
  While d 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., 2017). This estimator is exact for uniformly distributed data. It is also shown to remain asymptotically correct for non-uniform sampling of zi when the image dataset is large enough (Ansuini et al., 2019).
  1Both distances produce similar results in our experiments.
sections.heading: 3.3 CLUSTER LEARNABILITY (CL)
sections.text: To measure the representation learnability, we take inspiration from Laina et al. (2020). In this work, it is shown that the classes obtained by clustering the representations of pretrained self-supervised models can be easily learned by humans. We propose a cluster learnability (CL) metric as a way to automate their procedure and measure the learnability of the representation.
  Let {zi, ỹi}Ni=1 be the labelled dataset obtained by clustering the representation (e.g., with Kmeans). We want to define the learnability of the representation as the learning speed of a KNN classifier with this labelled dataset. To formalize this, we use a prequential approach (Dawid, 1984). Let ŷi = KNN(zi|{zk<i, ỹk<i}) denote the prediction of the i-th label after seeing the pairs (zk, ỹk) for k < i. Learnability is defined as the online learning accuracy of our KNN classifier:
  CL = 1
  N N∑ i=1 [ŷi == ỹi] (3)
  This metric can be connected to the prequential codelength of the cluster assignment dataset where the conditional model is a formed by a KNN classifier. We discusss this further in Appendix B.
sections.heading: 4 EXPERIMENT: EMPIRICAL EVALUATION OF THE CL-ID FRAMEWORK
sections.text: In this section, to assess the main hypothesis of the paper and the relevance of our metrics, 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?
sections.heading: 4.1 SETUP
sections.text: 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. A complete list can be found in Table 3 in the appendix. We mainly use the KNN evaluation on the validation data using the ground-truth labels to measure the performance of the model, which has been shown to be well correlated with the linear evaluation but computationally less expensive (Caron et 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.
  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 1 neighbor for our 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.
sections.heading: 4.2 QUALITATIVE EVALUATION
sections.text: We conduct a qualitative evaluation (Figure 1) to address Q1. We choose Alignment vs. Uniformity (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 representations. We hypothesize that this is because Align-Unif framework is derived from the contrastive loss and therefore requires access to the post-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 a pretrained backbone.
sections.heading: 4.3 QUANTITATIVE EVALUATION
sections.text: We also perform a quantitative evaluation (Figure 2) to address Q1 and Q2 by comparing the Top1 accuracy predictors from different framework. We come up with two Top1 accuracy predictors for our method:
  Vanilla CL-ID Predictor : CL+ ID Linear CL-ID Predictor : K1 · CL+K2 · ID +K3
  where K1,K2,K3 are obtained by linear regression with our collected 30 checkpoints.
  The first baseline is 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 : K1 ·Align+K2 · Unif +K3.
  The second baseline is rotation prediction, which is one of the best pretext task proposed proposed by Reed et al. (2021). We randomly rotate the training images with 0, 90, 180, 270 degrees, train
  a KNN classifier on the train images to predict a 4-way 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 observation in Figure 1 that alignment-uniformity 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 to a wider range of SSL methods and it is 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.
sections.heading: 4.4 ROBUSTNESS ANALYSIS
sections.text: In this experiment, we 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 3. 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, we observe that in general decreasing neighbor number leading to a better predictor. 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 a result, we hypothesize that here the cluster numbers here might control the underlying difficulty of the classification problem faced by the KNN learner. In the extreme cases we can have either only 1 cluster or as many clusters as data points. In the former, KNN accuracy would always be 100% and in the latter always be close to 0%. As a result, neither of them would be suitable enough to distinguish the collected checkpoints. As a
  rule of thumb, we recommend using a reasonably large number of clusters, e.g., the square root of the dataset size.
sections.heading: 5 EXPERIMENT: DEEPCLUSTER WITH IMPROVED CLUSTER LEARNABILITY
sections.text: In this section, we propose a simple modification for DeepCluster (Caron et al., 2018), which increase the learnability of the representations. Our method is called KNNDeepcluster. The purpose of this experiment is not to focus on a 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-DeepCluster out-perform DeepCluster consistently? Does it end up having a higher CL?
  Q4: Can we predict the performances of the new checkpoints with the CL-ID predictors from section 4.3?
  DeepCluster alternates between running K-means on the representation space and learning a representation such that it is highly predictive of the target cluster label associated with it. As a result, if 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-means clustering round, we change the K-means labels to the leave-one-out nearest neighbor predictions2. The pseudocode of the approach can be found in Algo. 1.
  2In practice, instead of performing a KNN prediction by querying the whole dataset, we use a queue of representations stored in each GPU worker. While this does not result in the exact neighbors, we find that it’s more scalable to large datasets.
  Algorithm 1: KNNDeepCluster. X is input images and F is the model while Not converged do
  Compute zi = F(xi; θ) for i = 1, ..., N Kmeans clustering on {zi}Ni=1 and get cluster label {ỹi}Ni=1. Get ŷi = KNNClassifier(zi|{zk, ỹk}k 6=i) for i = 1, ..., N . Leave one out Update θ on the dataset {xi, ŷi} for one epoch.
  end
sections.heading: 5.1 RESULTS ON IMAGENET AND STL-10
sections.text: In our experiments, we set the number of neighbors to be 3 in our KNNDeepCluster for both datasets, and we find that this does not affect our results much. We perform experiments on both STL10 and ImageNet. Our results are shown in Table 1. There are consistent gains on both STL10 and ImageNet, but the gain on ImageNet is smaller, and only appears with a weaker downstream classifier such as a KNN or with less training data.
sections.heading: 5.2 ANALYSIS WITH THE CL-ID FRAMEWORK
sections.text: We visualize the training trajectories in Figure 4. 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 an increase of ID
  along with CL. Finally, especially for the ImageNet models as well as 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, we find that KNN-DeepCluster converges to a solution that has a higher CL in comparison to DeepCluster, without a significant drop in ID.
  We also find that the relative Top-1 classification performance of the intermediate checkpoints can still be well predicted by our linear CL-ID 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 (e.g., Ansuini 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 119) so that, intuitively, the model could explore as much as possible to encode the information from dataset. Then in the later stage, a form of compression occurs while CL increases for better generalization – presumably this stage is the regime of analysis done in Ansuini et al. (2019).
sections.heading: 6 CONCLUSION & DISCUSSION
sections.text: Inspired by an analogy with language emergencewe propose to analyze self-supervised representation learning through the lens of expressiveness and learnability. We propose to estimate expressiveness with TwoNN intrinsic dimension (ID), and learnability with the acquisition speed of a KNN learner on the K-means clustering of the representation. Our large-scale evaluation with 30 checkpoints 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 a solid step towards understanding the current SSL algorithms and opens up interesting research directions. Future works could further explore the expressiveness-learnability in a more theoretical context, extend this framework to other field like pretrained language models, as well as devise new SSL algorithms that directly maximize intrinsic dimension or cluster learnability.
sections.heading: A FUTHER DISCUSSION ON CURRENT SSL PRACTICE
sections.text: We further discuss the motivation behind our framework, and how can approach some of the SSL practice throught the lense of expressiveness and learnability.
  Contrastive Learning With our new view on representation quality by expressivenesslearnability, we can try to analyze some of the practice in the contrastive learning and see why it works and fails. Contrastive learning is a typical example of such a trade-off, and it has the following objective:
  Ex,x+,x− log ( eF(x)TF(x+) eF(x)TF(x+) + eF(x)TF(x−) ) It 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 to be similar by which a higher value of learnability is ensured, since ideally the another learner only need to see one example to generalize to other positive examples. As a result, the degree of learnability here can be controlled by the definition of positive examples. A more diverse selection of the positive examples should make theF leaning toward the learnability side, since each example could represent a larger fraction of the inputs. It is well acknowledged in the self-supervised community that a diverse data augmentation is an essential part of the contrastive learning, and under this framework, it is a source of the learnability pressure.
  Clustering-based Learning Perhaps our expressiveness-learnability 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 not only F but also a bank of cluster centroids C as well as assignments ỹ = CTF(x). As a result, we can also view these algorithms as finding ỹ = G(x), where G is composed of F and C. In these methods, the expressiveness is achieved by using a large number of clusters as well as some uniformity constraint, and this can ensure each data has a 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 ỹ is usually less than x, 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, so that G(x) and G(x+) should have the same ỹ, which further improves the learnability.
sections.heading: B CLUSTER LEARNABILITY AND PREQUENTIAL CODELENGTH
sections.text: Note that Epn. 3 can be connected to the compression lower bound of the emerged cluster assignments datasets {zi, ỹi}Ni=1 via prequential coding (Dawid, 1984). The prequential codelength is defined as
  Lpreq = − ∑ i log p(ỹi|(zk≤i, ỹk<i)) (4)
  where p(ỹi|(zk≤i, ỹk<i)) is a conditional model, which can be computed from our KNN classifier probabilities. If Eqn. 3 is the online learning accuracy, then Eqn. 4 is online learning cross-entropy loss. Higher CL lead to lower prequential compression bounds on the emerged clusters.
sections.heading: C OTHER ATTEMPTS ON CHARACTERIZING EXPRESSIVENESS AND LEARNABILITY
sections.text: In this section, we discussed our other unsuccessful attempts on characterizing expressiveness and learnability.
  Previous works propose maximizing mutual information between inputs and the representations as a 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 a 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 it 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 of representation. E.g., a one-to-one map between images and representations would have a high MI, while a degenerate solution would not. As a result, we 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 5 epochs and report the estimate for validation set.
  For learnability, we also try fitting a student ResNet18 from scratch to learn the map from images xi to representations zi 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 to also propose to let the student network to predict emerged cluster labels ỹi from images xi. We also use ResNet18 as our student, train for 5 epochs, and report the validation metrics as 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 to be sensitive 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 zi is heavily effected by dimensionality of the space. Thirdly, there is a architecture bias when we use ResNet18 as the students. ViT checkpoints in general performs poorer since it is too different from the ResNets. As a result, our proposed method CL and ID do not have these problem, mainly because we avoid training another neural network from scratch.
sections.heading: D MORE RESULTS ON KNNDEEPCLUSTER
sections.text: We performed more experiments on STL-10 between KNNDeepCluster and DeepCluster under different number of prototypes. The results are in Table 2. We find that our method is able to consistently 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 on a pretrained DeepCluster checkpoint in Figure 6 on STL-10.
  We 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 are absorbed into large clusters. As a result, in the next epoch, the network pays more attention on fitting labels coming from large and well-separable clusters