The Pursuit of Human Labeling: A New Perspective on Unsupervised Learning
Authors: Artyom Gadetsky
Maria Brbic
Venue: NeurIPS 2023 spotlight (2023)
Keywords: unsupervised learning
deep learning
generalization
self-supervised learning
clustering
TL;DR: We propose an unsupervised learning framework to find human labeling by searching for consistent labelings between different representation spaces.

Abstract: We present HUME, a simple model-agnostic framework for inferring human labeling of a given dataset without any external supervision. The key insight behind our approach is that classes defined by many human labelings are linearly separable regardless of the representation space used to represent a dataset. HUME utilizes this insight to guide the search over all possible labelings of a dataset to discover an underlying human labeling. We show that the proposed optimization objective is strikingly well-correlated with the ground truth labeling of the dataset. In effect, we only train linear classifiers on top of pretrained representations that remain fixed during training, making our framework compatible with any large pretrained and self-supervised model. Despite its simplicity, HUME outperforms a supervised linear classifier on top of self-supervised representations on the STL-10 dataset by a large margin and achieves comparable performance on the CIFAR-10 dataset. Compared to the existing unsupervised baselines, HUME achieves state-of-the-art performance on four benchmark image classification datasets including the large-scale ImageNet-1000 dataset. Altogether, our work provides a fundamentally new view to tackle unsupervised learning by searching for consistent labelings between different representation spaces.

The Pursuit of Human Labeling: A New Perspective on Unsupervised Learning
Artyom Gadetsky
Maria Brbić EPFL mbrbic@epfl.ch ch
EPFL artem artem.gadetskkle wtw.gaaaetsiiief........
Abstract
We present HUME, simple model-agnostic framework for inferring human labeling of a given dataset without any external supervision. The key insight behind our approach is that classes defined by many human labelings are linearly separable regardless of the representation space used to represent a dataset. HUME utilizes this insight guide the search over all possible labelings of dataset to discover an underlying human labeling. We show that the proposed optimization objective is strikingly well-correlated with the ground truth labeling of the dataset. In effect, we only train linear classifiers on top of pretrained representations that remain fixed during training, making our framework compatible with any large pretrained and self-suuervised model. Despite its simplicity, HUME outperforms a supervised linear classifier on top of self-supervised representations on the STI.-10 dataset by large margin and achieves comparable performance on the CIFAR-10 dataset. Compared to the existing unsupervised baselines, HUME achieves state-of-the-ar performance on four benchmark image classification datasets including the large- scale ImageNet- 1000 dataset. Altogether, our work provides a fundamentally new view to tackle unsupervised learning by searching for consistent labelings between different representation spaces.
Introduction
key aspect of human intelligence is an ability to acquire knowledge and skills without external guidance instruction. While recent self-supervised learning methods [ 4 5 have shown remarkable ability to learn mask-agnostic representations without any supervision, a common strategy to add linear classification layer on top of these pretrained representations to solve task of interest. In such scenario, neural networks achieve high performance on many downstream human labeled tasks. Such strategy has also been widely adopted in transfer learning 7 g and few-shot learning (9] 10), demonstrating that a strong feature extractor can effectively generalize to new task with a minimal supervision. However, fundamental missing piece in reaching human-level intelligence is that machines lack an ability to solve a new task without any external supervision and guidance.
Close to such ability are recent multi-modal methods 11 trained on aligned text-image corpora that show outstanding performance in the zero-shot learning setting without the need for fine-tuning However, zero-shot learning methods still require human instruction set to solve a new task. In a fully unsupervised scenario, labels for
task have been traditionally inferred by utilizing clustering 15 [6), designed to automatically identify and group samples that are semantically related. Compared to (weakly) supervised counterparts, the performance of clustering methods is still lagging behind.
methods 13
14 [
In this work, propose HUME, simple model-agnostic framework for inferring human labeling of a given dataset without any supervision. The key insights underlying our ap-
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

proach are that: (i) many human labeled tasks are linearly separable in a sufficiently strong representation space, and (ii) although deep neural networks can have their own inductive biases that do not necessarily reflect human perception and are vulnerable to fitting spuri- ous features 18, human labeled tasks are invariant to the underlying model and result- ing representation space. We utilize these observations to develop the generalization- optimization objective which strikingly well correlated with human labeling (Figure The key idea behind this objective is to evaluate the generalization ability of linear models on top of representations generated from two pre- trained models to assess the quality of any given labeling (Figure 2 Our framework is model- agnostic, i.e., compatible with any pretrained representations, and simple, i.e., it requires train- ing only linear models.
Disagreement w/ human labeling
p= p 2.6 10
0.30
0.25
Overall, HUME presents new look on how to tackle unsupervised learning. In contrast to clustering methods JK 14] which try to embed
0.20
inductive biases reflecting semantic relatedness of samples into learning algorithm, our ap- proach addresses this setting from model gener- alization perspective. We instantiate HUME's framework using representations from different self-supervised methods (MOCO
0.15
0.10
0.10
0.11
0.12
0.13
3 Sim-
HUME'S objective
CLR 21 BYOL (19) pretrained on the tar- get dataset and representations obtained using large pretrained models (BiT [ DINO [20]. CLIP (6. Remarkably, despite being fully un- supervised, HUME outperforms supervised linear classifier on the STL-10 dataset by 5% and has comparable performance to linear clas- sifier on the CIFAR-IU 10 dataset. Additionally, leads to the new state-of-the-au performance on standard clustering benchmarks including the CIFAR- 100-20 and the large-scale ImageNet- 1000 datasets. Finally, our framework can con- struct set of reliable labeled samples transform- ing the initial unsupervised learning problem to semi-supervised learning.
Figure 1: Correlation plot between distance to ground truth human labeling and HUME's objective the CIFAR-10 dataset. HUME generates different label- ings of the data to discover underlying human label- ing. For each labeling (data point on the plot), HUME evaluates generalization error of linear classifiers in different representation spaces as its objective func- tion. HUME 's objective strikingly well correlated (p = 0.93, p = 2.6 x 10 two-sided Pearson correla- tion coefficient) with distance to human labeling. In particular, HUME achieves the lowest generalization er- for tasks that almost perfectly correspond human labeling, allowing HUME to recover human labeling without external supervision. Results on the STL-10 and CIFAR- 100-20 datasets are provided in Appendix D
2
HUME framework
In this section, we first introduce our problem setting and then present general form of our framework for finding human labeled tasks without any supervision.
Problem setting. Let 'D = {-x J.N be a set of samples. We assume this dataset consists of K classes, where K is known priori, and each example x; belong only one particular class k E (O...., ., K - 1}. We define a task 7 DD - (0.... K - 1} as a labeling function of this dataset. We refer a task human labeled if it respects the true underlying labeling of the corresponding dataset D.
2.1 Test error and invariance of human labeled tasks to representation space
Measuring the performance of model on a held-out dataset is conventional method to assess an ability of the model to generalize on the given task т. Specifically, for the dataset D, we can construct two disjoint subsets (Xtr, Xtx) of the dataset D. Let ʃ 'D - AK- be a probabilistic classifier which transforms the input x E D to class probabilities, i.e., A A is a (K - -dm-mmmnsio simplex. After training f on X with loss function L and labeling 7 (Xer),, we can compute the test error

---

Dataset D
t2
(D))
Task with a low test error in both representation spaces
Φ1
Two pretrained models
Φ
(2
T1
Human labeling: birds (O), cats (O)
Overview of the HUME framework. HUME utilizes pretrained representations and linear models on top of these representations to assess the quality of any given labeling. As a result, optimizing the proposed generalization bassa objective leads to labelings which are strikingly well correlated with human labelings.
Figure 2:
Xte which can provide us with an unbiased estimate of the true error of the model on the task T:
1 Σ ((f()),
[(f(Xx))
X1e
xE
In HUME, we utilize this score measure the quality of any given task т. By utilizing this score, we aim at searching for a human labeled task over the set of all possible tasks on the dataset D. However, the main challenge is that neural networks
have their own inductive biases and attain low test error on tasks that capture spurious correlations and do not reflect human labeling [17]. To distinguish between such tasks and human labeled tasks, the key insight behind our framework is that for many human labeled tasks classes defined by human labeling are linearly separable regardless of the representation space used to represent a dataset. In other words, buman-labeled tasks are invariant to sufficiently strong representation spaces. We next formally define what we mean by sufficiently strong representation space and invariance of a task to the pair of representations.
Definition 1. Let d(x) DD - IRd be a mapping from the sample space low-dimensional representation space. We say that a representation space is sufficiently strong with respect to T if linear model trained on top of Φ(-) attains low test error in Eq. 47)
Definition 2. Let di (z) : - Rdh and Φ2(x) :D - Rdda be two mappings from the sample space to low-dimensional representations. We say that task T is invariant to the pair of representations (6i(x), 62(2)) if both representation spaces are linearly separable with respect to T, i.e., both linear models J1 and f2, trained on top of d1 (-) and (22-)) respectively, allain low test error in Eq. |
We employ the property of invariance to the given pair of fixed pretruined representations to seek for human labeled task. Thus, we only train linear classifiers on top pretrained representations while the representations are always frozen during training. The simultancous utilization of several repre- sentation spaces acts regularizer and prevents learning tasks that capture spurious correlations which can reflect inductive biases of the individual representation space.
Specifically, given a task we aim to fit a linear model fs with weights parametrized by W; E Kxdd on Xx, in each representation space db(-), = 1, 2. Let Wi(T) be the solution for the corresponding (.).) We aim optimizing the test error of both linear models with respect to r:
arg min ((W r(Xie)) + (X)))
(2)
where (-) is a softmax activation function. We draw attention of the reader to the fact that both Wi(T) and WT(T) implicitly depend as solutions of the inner optimization problem on X with labeling T (....). We discuss how to efficiently solve this optimization problem and propagate gradients through the optimization process in the corresponding Section 2.3
unresolved modeling question is the choice of the representation spaces (.)) We utilize self-supervise pretraining the target dataset D to obtain robust and well clustered representations
3

---

for representation space (-). Representation space (2(-) acts as regularizer to guide the search process. Thus, we utilize features of a large pretrained model the representation space Φ2(-). This is an appealing modeling design choice from both efficiency and model performance perspective. In particular, by using large pretrained model we do not need to train a model on the given dataset of interest. Despite the simplicity, the linear layer fine-tuning on top of the fixed representations of the deep pretrained models has shown its efficiency in solving many downstream problems [6 20 The approach to model is discussed in the next section.
2.2 Task parametrization
The proposed objective in Eq. requires solving difficult discrete optimization problem with respect to which prevents us from using efficient gradient optimization techniques. Additionally, it requires designing three separate models (+) (+),)(()))) which can be computationally expensive and memory-intensivy in practice. To alleviate both shortcomings, we utilize (1(-) to simultaneously serve as a basis for the task encoder and as a space to which the task should invariant to. Namely, we relax the outputs of to predict class probabilities instead of discrete class assignments, and -K1 as follows:
parametrize the task TW, (+) :D: K
Φ1 (2)
TW; (x) (( W.W. = IK. (z(x)= [z)1())
where d1 denotes the self-supervised representations pretrained on the given dataset D and these representations also remain fixed during the overall training procedure. We produce sparse labelings using sparsemax [21 activation function A since each sample z; E E needs be restricted to belong to particular class. The above parametrization may be viewed as learning prototypes for each class
Thus, W d (-) corresponds to the cosine similarities between class prototypes W and the encoding of the sample (-). Moreover, sparsemax activation function acts as a soft selection procedure of the closest class prototype. Eventually, it can be easily seen that any linear dependence W1 (z) give rise to the task which, by definition, is at least invariant to the corresponding representation space & (x).
which is an attractive modeling choice for the representation space (-(-) 22 9
Given the above specifications, our optimization objective in Eq. (2) is simplified as follows:
arg min ((o(( Tw, (Xte)), W;
where (W(1) denotes the weights of the linear model fz trained on the (Xtr, Tw; (Xer)), which implicitly depend on the parameters W, We use the cross-entropy loss function L, which is widely used loss function for classification problems. The resulting optimization problem is continuous with respect to W,, which allows us to leverage efficient gradient optimization techniques. Although involves propagating gradients through the inner optimization process, we discuss how to efficiently solve it in the subsequent section.
2.3
Test error optimization
At each iteration k, we randomly sample disjoint subsets EXtr:Xee) D to prevent overfitting to the particular train-test split. We label these splits using the current task Twp (-) with parameters W Before computing the test risk defined in Eq. (4) we need to solve the inner optimization problem on (Xtr Tw. (or((x,,) (X..)), specifically:
W, arg min C(o ((2((22((X))) (X.)).
W,
can be easily seen that the above optimization problem is the well-studied multiclass logistic regression, which is convex with respect to W2 and easy solve. To update parameters W need to compute the total derivative of Eq. with respect to W, which includes the Jacobian
can be utilized to compute the required Jacobian and propagate gradients through the above optimization process. For simplicity, we run gradient descent for the fixed number of iterations m to solve the inner optimization problem and obtain W7T (W+).
aw, Different approaches BW2.
23
24
25
26
@w awF by unrolling the computation graph of the
Afterwards, we employ MAML 27 to compute

---

inner optimization's ' gradient updates. The remaining terms of the total derivative are available out-of-the-box using preferred automatic differentiation (AD) toolbox. This results in the efficient procedure which can be effortlessly implemented in existing AD frameworks 28 29
Regularization. The task encoder can synthesize degenerate tasks, i.e, assign all samples single class. Although such tasks are invariant to any representation space, they are irrelevant. To avoid such trivial solutions, we utilize entropy regularization to regularize the outputs of the task encoder averaged over the set X Xxr U Xte, specifically
K
R(T)
Tk logFk.
(6)
where - | Exex (2(x) E A is the empirical label distribution of the task T. This leads us the final optimization objective, which is:
arg min (W nw, (Xte)) ()((F()))
Wi
where 7) is the regularization parameter. This regularization corresponds to entropy regularization which has been widely used in previous works [13 30 31. The pseudocode of the algorithm is shown in Algorithm
Algorithm HUME: A simple framework for finding human labeled tasks
Input: Dataset D, number of classes K. number of iterations T, representation spaces $1,2(-), task encoder Tw; (.), regularization parameter y), step size a
1: Randomly initialize K orthonormal prototypes: W artho_rand(e
2: for k
do
3: Sample disjoint train and test splits:
D
4: Generate task: Tir, Tte + Twp (Xtr), Twp (Xte)
5: Fit linear classifier on X (W(() = arg min ((2((22((Xx))))) Ter)
W;
6: Evaluate task invariance on Xte: L* (W++) Lio (Wa (Xxo)) Tea) R/(((T)
7: Update task parameters: W + W Lx
8: end for
Experiments
3.1 Experimental setup
Datasets and evaluation metrics. We evaluate the performance of HUME on three commonly
used clustering benchmarks, including the STL-10 [2). CIFAR-IO and CIFAR-110-20 The CIFAR-100-20 dataset consists of superclasses of the original CIFAR-100 classes. In addition, we also compare HUME to large-scale unsupervised baselines on the fine-grained ImageNet-100k method with the baselines using two conventional metrics, namely clustering accuracy (ACC) and adjusted rand index (ARI). Hungarian algorithm [35) is used to match the found labeling to the ground truth labeling for computing clustering accuracy. We interchangeably use terms generalization error and cross validation accuracy when presenting the results.
33 datasets.
dataset [34] We compare
Instantiation of HUME. For the representation space (.).), we use MOCOv2 4 pretrained on the train split of the corresponding dataset. We experiment with the SimCLR [I as self-supervised method in Appendix C For the representation space @2(-), we consider three different large pretrained models: (i) M-F-M--50xx [7] pretrained on ImageNet-2 lk (36), (ūi) CLIP ViT-L/14 pretrained on WebImage Text 66, and (iii) DINOv2 ViT-g/14 pretrained on 14D- 20
Baselines. Since HUME trains linear classifiers on top of pretrained self-supervised representations, supervised linear probe on top of the same self-supervised pretrained representations is natural baseline to evaluate how well the proposed framework can match the performance of a supervised model. Thus, train a linear model using ground truth labelings the train split and report the
5

---

results on the test split of the corresponding dataset. For the unsupervised evaluation, we consider two ofate-of-the-ar deep clustering methods, namely SCAN [3] and SPICE [4]. Both methods can be seen as three stage methods. First stage employs sulf-sse methods to obtain good representations. We consistently use the ResNet-18 18 backbone pretrained with MOCOv2 A for all baselines as well as HUME. During the second stage these methods perform clustering on top of the frozen representations and produce reliable pseudo-labels for the third stage. Finally, the third stage involves updating the entire network using generated pscudo-labels. Thus, pseudo-labels are produced using a clustering algorithm from the second step and third stage is compatible with applying any semi-supervised method (SSL) 37 38]
the set of reliable samples. Instead of optimizing for performance of different SSL methods which is out-of-scopo of this work, we compare clustering performance of different methods and report the accuracy of generated pseudo- which is crucial component that enables SSL methods to be effectively applied. Additionally, we utilize the recent state-of-the-art SSL method FreeMatch [39 to study the performance of FreeMatch when applied to HUME's reliable samples. As additional unsupervised baselines, we include results of K-means clustering [15] on top of the corresponding representations and K-means clustering on top of concatenated embeddings from both representation spaces used by HUME. For stability, all K-means results are averaged over 100 runs for each experiment. On the ImageNet- 1000 dataset, we compare HUME to the recent state-of-the-arr deep clustering methods on this benchmark. Namely, in addition to SCAN, we also consider two single-stage stage methods, TWIST 40 and Self-classifier [4T]. TWIST is trained from scratch by enforcing consistency between the class distributions produced by a siamese network given two augmented views of an image. Self-classifier trained in the similar fashion as TWIST, but differs in way of avoiding degenerate solutions, ie., assigning all samples to a single class. HUME can be trained in inductive and transductive settings: inductive corresponds to training on the train split and evaluating on the held-out test split, while transductive corresponds to training on both train and test splits. Note that even in transductive setting evaluation performed on the test split of the corresponding dataset to be comparable to the performance in the inductive setting. We report transductive and inductive performance of HUME when comparing it to the performance of the supervised classifier. For consistency with the prior work 113, we evaluate clustering baselines in the inductive setting.
Implementation details. For each experiment we independently run HUME with 100 different random seeds and obtain 100 different labelings. To compute the labeling agreement for the evaluation, we simply use the Hungarian algorithm to match all found labelings to the labeling with the highest cross-validation accuracy (HUME's objective). Finally, we aggregate obtained labelings using majority vote, i.e., the sample has class if the majority of the found labelings predicts class i. We show experiments with different aggregation strategies in Section 3.2 We set the regularization parameter 17 to 10 in all experiments. We show robustness to this hyperparameter in Appendix B We provide other implementation details in Appendix A Code is publicly available at hhtpps //github. cwm/m http:/mlioo-oe wwwpaaiiooooool/aaeeeeoeeeeeleee apfl/hume
3.2 Results
Comparison to supervised baseline. We compare HUME to a supervised linear classifier by utilizing ResNet-18 MOCOv2 pretrained representations (4) for both models. In particular, for a supervised classifier we add a linear layer on top of pretrained representations which is standard evaluation strategy of self-supervised methods. As regularization representation space in HUME, we utilize BiT 77. CLIP ViT (6] and DINOv2 ViT (20). The results are shown in Table Remarkably, without using any supervision, on the STL-10 dataset HUME consistently achieves better performance than the supervised linear model in the transductive setting, and using CLIP and DINO in the inductive setting. Specifically, using the strongest DINO model, HUME outperforms the supervised linear model by 5% on the STL-10 dataset in terms of accuracy and by 11% in terms of ARI. On the CIFAR-IO dataset, HUME achieves performance comparable to the linear classifier. On the hardest CIFAR-100-20 there is still an expected gap between the performance of supervised and unsupervised methods. When comparing performance of HUME in inductive and transductive setting, the results show that utilizing more data in the transductive setting consistently outperforms the corresponding method in inductive setting by - 3% in terms of accuracy. Finally, when comparing performance of different pretrained models, the results show that employing larger pretrained models results in better performance. For example, on the CIFAR-100-22 dataset HUME DINO achieves 16% relative improvement in accuracy over HUME BiT in both inductive and transductive settings. Thus,

---

these results strongly indicate that HUME framework can achieve even better performance by taking advantage of unceasing progress in the development of large pretrained models.
Table Comparison of HUME to supervised linear classifier in inductive (ind) and transductive (trans) settings using MOCOv2 supervueee representations pretrained on the corresponding dataset and three different large pretrained models.
STL-10
CIFAR-10
CIFAR-100-20
Method
ACC
ARI
ACC
ARI
ACC
ARI
MOCO Linear
88.9
77.7
79.0
72.5
52.6
HUME BÍT ind
87.5
76.2
73.8
47.8
33.5
HUME CLIP ind
90.2
80.2
88.2
77.1
48.5
34.1
HUME DINO ind
90.8
81.2
88.4
77.6
55.5
37.7
HUME BiT trans
90.3
80.5
86.6
75.00
48.8
34,5
HUME CLIP trans
92.2
84.1
88.9
78.3
50.1
34,8
HUME DINO trans
93.2
86.0
89.2
79.2
56.7
39.6
Comparison to unsupervised baselines. We next compare performance HUME the state- of-the-art deep clustering methods (Table We use DINOv2 the second representation space but the results for other models are available Table [ Results show that HUME consistently outperforms all baseline by large margin. On the STL-I0 and CIFAR-10 datasets, HUME achieves 5% improvement
accuracy over the best deep clustering baseline and 11% and 10% in ARI, respectively. On the CIFAR- 1 100-20 dataset, HUME achieves remarkable improvement of 19% in accuracy and 18% in ARI. It is worth noting that considered baselines utilize nonlinear models (multilayer perceptrons)
top of the pretrained representations, while HUME employs solely linear model. When compared to the K-means clustering basclines on top of concatenated features from DINO and MOCO, HUME achieves 18%, 9% and 8% relative improvement in accuracy the STL-10, CIFAR-10 10 and CIFAR- 100-00 datasets, respectively. These results demonstrate that performance gains come from HUME's objective rather than from utilizing stronger representation spaces, Overall, our results show that the proposed framework effectively addresses the challenges of unsupervised learning and outperforms other baselines by large margin.
Table 2: Comparison to unsupervised baselines. All methods use ResNet-18 18 MOCOy2 sell- represen- lations pretrained the target dataset. We DINOv2 large pretrained model.
STL-100
CIFAR-10
CIFAR-100-20
Method
ACC
ARI
ACC
ARI
ACC
ARI
MOCO K-means
67.7
54.1
66.9
51.8
37.5
20.9
DINO K-means
60.1
35.4
75.5
67.6
47.2
33.9
DINO MOCO + K-means
77.1
70.0
81.4
77.1
51.3
36.1
SCAN
77.8
61.3
83.3
70.5
45.4
29.7
SPICE
86.2
73.2
84.5
70.9
46.8
32.1
HUME
90.8
81.2
88.4
77.6
55.5
37.7
Large-scale ImageNet-1000 benchmark. We next study HUME's performance on the ImageNet-1000 benchmark and compare it to the state-of-the-art deep clustering methods on this large-scale benchmark. All methods use the ResNet-50 backbone. SCAN is trained using MOCOv2 self-supervised representations and both TWIST and Self-classifier are trained from scratch single-stage methods. HUME utilizes the same MOCOv2 self-supervised representa- tions and DINOv2 as the second representation space. The results in Table show that HUME achieves 24% relative improvement accuracy and 27% relative improvement ARI over considered baselines, thus confirming the scalability of HUME to challenging fine-grained benchmarks.
Table 3: Performance of HUME on the large-scale ImageNet-1000 dataset and comparison to unsuper- vised baselines. All methods the ResNet50 back- bone. HUME uses DINOv2 large pretrained model and ResNet-50 MOCOv2 self-supervised representation.
Method
ACC
ARI
SCAN
39.7
27.9
TWIST
40.6
30.0
Self-classifier
41.1
29.5
HUME
51.1
38.1
7

---

(a)
(b)
0.90
1.00
DINO
CLIP
BiT
0.89
0.98
Accuracy
0.88
Accuracy
0.87
0.94
0.86
0.92
0.85
10 30 40 60 70 80 90 100
2500 A1 Number of reliable samples per class
10 15
25
400
1000
Top-n tasks w.r.t. HUME'S objective
Figure 3: (a) Different aggregation strategies on the CIFAR-I0 dataset. We use MOCOv2 and different large pretrained models to instantiate HUME. (b) Accuracy of the reliable samples on the CIFAR-10 dataset. We use MOCOv2 and DINOv2 to instantiate HUME. The well-established setting for testing SSL methods on the CIFAR-I0 dataset 4, 25 and 100 reliable samples per class (depicted with lines in red color).
Ablation study on aggregation strategy. HUME achieves a strikingly high correlation between its objective function and ground truth labeling (Figure [].. However, due to the internal stochasticity, the found labeling with the lowest generalization error does not need to always correspond to the highest accuracy. Thus, to stabilize the predictions obtain final labeling by aggregating found labelings from independent runs. We simply use the majority vote of all tasks in all our experiments. Here, we investigate the effect of using different aggregation strategies on the performance. Figure (a) shows the results on the CIFAR- 10 dataset and the corresponding plots for the STL-10 and CIFAR- 100-20 datasets shown in Appendix F Given the high correlation of our objective and human labeling, we aggregate top-n of labelings w.r.t. generalization error and compute the corresponding point the plot. Thus, the leftmost strategy (at x 1) corresponds to the one labeling that has the lowest generalization error, while the rightmost data point (at x 100) corresponds to aggregation over all generated labelings. i.e., the strategy we adopt in all experiments. By aggregation over multiple labelings the algorithm produces more stable predictions. Expectedly, given the high correlation between HUME's objective and human labeling, can achieve even better performance by aggregating only top-n predictions compared to our current strategy that considers all tasks; however, we do not optimize for this in our experiments. Finally, it can be seen that utilizing larger pretrained models eliminates the need of aggregation procedure, since they lead to stronger and robust performance.
Reliable samples for semi-supervised learning (SSL). We next aim answer whether HUME can be used to reliably generate labeled examples for SSL methods. By generating a few reliable samples per class (pseudo-labels), an unsupervised learning problem can be transformed into an SSL problem [1]] Using these reliable samples as initial labels, any SSL method can be applied. HUME can produce such reliable samples
simple way. Specifically, we say that sample is reliable if (i) the majority of the found labelings assigns it to the same class, and (ii) the majority of the sample neighbors have the same label. We provide the detailed description of the algorithm in Appendix G We evaluate the accuracy of the generated reliable samples the CIFAR- dataset and show results Figure (b) In the standard SSL. evaluation setting that uses labeled examples per HUME produces samples with perfect accuracy. Moreover, even with 15 labeled examples per class, reliable samples generated by HUME still have perfect accuracy. Remarkably, in other frequently evaluated SSL settings the CIFAR-10 dataset [39 42 43) with 25 and 400 samples per class, accuracy of reliable samples produced by HUME is near perfect (99.6% and 99.7% respectively). Results on the STL-10 and 1IFAR-100-20 datasets and additional statistics of the reliable samples are provided in the Appendix
class [39 42 43
We next utilize the recent state-of-the-an SSL method FreeMatch (39 to compare the results of running FreeMatch with reliable samples produced by HUME to running FreeMatch with ground truth labeling. The results in Table show that in the extremely low data regime FreeMatch with reliable samples produced by HUME outperforms FreeMatch with ground truth labels. Indeed, FrecMatch with ground truth labels utilizes samples which are sampled uniformly at random, while

---

HUME's reliable samples by definition are such samples whose most neighbours belong to the same class predicted by HUME. Consequently, FreeMatch which is based on adaptive thresholding for pseudo-labeling, benefits from utilizing labeled samples for which it can confidently set the threshold, especially in a low data regime. For instance, FreeMatch with reliable samples achieves 10% relative improvement in accuracy over FreeMatch with ground truth labeling on the CIFAR- 10 dataset with one sample per class. Comparing FreeMatch with reliable samples produced by HUME with an original HUME method, we observe improvement of 8% on the CIFAR-10 10 dataset, demonstrating that HUME's ss results can be further improved by applying SSL with HUME's s reliable samples. Overall, results strongly demonstrate that HUME is highly compatible with SSL methods and can be used to produce reliable labeling for SSL methods.
Table 4: Comparison of accuracy of FreeMatch trained using reliable samples produced by HUME and FreeMatch trained using ground truth labeling on the STL-10 and on the CIFAR- 10 dataset. We apply FrecMatch using 4 and 100 samples per class on the STL-10 dataset and 1, 4, 25 and 400 samples per class on the CIFAR-10 dataset. Each experiment is run 3 times and the results are averaged.
STL-10
CIFAR-10
Method
4
100
4
25
400
FreeMatch w/ reliable samples
81.3 +: 4.3
91.3
91.25..3
95.1
+ 0.1
2.5
94.3 + 0.4
FreeMatch w/ ground truth labels
7.1
9..0
9.6
94.8 + 0.3
95.1
0.0
9.1
4
Related work
aim to define a pretext task which leads to learning representations that useful for downstream tasks. Recently, contrastive approaches 2 4 20 have seen a significant interest in the community. These approaches learn representations by contrasting positive pairs against negative pairs. Another line of solving Jigsaw
Self-supervised learning. Self-supervised methods 44
45
46
48
work relies on incorporating beneficial inductive biases such as image rotation [4
puzzles (46) by introducing sequential information that comes from video
45
Regardless of
learning approach, a linear probe, i.e., training a linear classifier on top of the frozen representations using the groundtruth labeling, is frequently used evaluation protocol for self-supervised methods. In our work, we turn this evaluation protocol into an optimization objective with the goal to recover the human labeling in a completely unsupervised manner. In Appendix C show that stronger representations lead to better unsupervised performance mirroring the linear probe evaluation. Given that HUME framework is model -agnosscc, it can constantly deliver better unsupervised performance by employing continuous advancements of self-supervised approaches. Furthermore, HUME can be used evaluate performance of supervued methods an unsupervised manner.
Transfer learning. Transfer learning is machine learning paradigm which utilizes large scale pretraining of deep neural networks to transfer knowledge to low-resource downstream problems (50 77. This paradigm has been successfully applied in wide range of applications including but not limited to few-shot learning [10] 91 domain adaptation [5, and domain generalization
53 54 Recently, foundation models [55] 36 57 12 trained on a vast amount of data achieved breakthroughs in different fields. The weights of linear classifier on top of the frozen representations in a supervised manner [50]. In our framework, we leverage strong linear transferability of these representations to act as regularizer in guiding the search process of human labeled tasks. Thus, it can be also seen as performing an unsupervised transfer learning procedure. While language-image foundation models such as CL.IP ( require human instruction set to solve new task, HUME provides a solution to bypass this requirement.
pipeline of transfer learning is to fine-tune
Clustering. Clustering is a long studied machine learning problem 58 Recently, deep clustering methods [59
60 have shown benefits over traditional approaches. The typical approach to clustering problem is to encourage samples to have the same class assignment as its neighbours in
B
representation space [3 60 61
Other recent methods rely on self-labeling, i.e., gradually fitting the
neural network to its own most confident predictions [14 16 62 63 Alternative approaches [64 [59
train an embedding space and class prototypes to further assign samples to the closest prototype in the embedding space. In contrast, our framework redefines the way to approach clustering problem.

---

Without explicitly relying on notions of semantic similarity, we seek to find the most generalizable labeling regardless of the representation space in the space of all possible labelings.
Generalization, One of the conventional protocols to assess ability of the model to generalize is to employ held-out data after model training. In addition, different measures of generalization [65 66 67 68, 69 (0) have been developed to study and evaluate model generalization from different perspectives. Although, traditionally a generalization error is used as a metric, recent work [17] employs test-time agreement of two deep neural networks to find labelings on which the corresponding neural network can generalize well. Often, these labelings reflect inductive biases of the learning algorithm and can be used to analyze deep neural networks from a data-driven perspective.
Meta-optimization. The proposed optimization procedure requires optimization through the inner optimization process. This type of optimization problems also naturally arises in gradient-based mntaa-ptimization (27 [2]. Other works 23
25 24 tackle the similar problem and study how to embed convex differentiable optimization problems as layers in deep neural networks. Although meta- optimization methods are, in general, computationally heavy and memory intensive, the proposed optimization procedure only requires propagating gradients through a single linear layer. This makes HUME a simple and efficient method to find human labelings. In addition, the inner optimization problem (Eq. 5 is convex allowing for the utilization of the specialized methods such as L-BFGS making our framework easily extendable to further boost the efficiency.
73 74,
Semi-supervised learning. Semi-supervised learning (SSL) assumes that along with an abundance of unlabeled data, small amount of labeled examples is given for each class. Consequently, SSL methods [39 45 37 75 76 38 effectively employ available labeled data increase the model's entire dataset. As shown in Figure 3 (b) and in Table 4 HUME can be used construct reliable samples and convert the initial unsupervised problem to the SSL problem. Thus, the proposed framework can also be used to eliminate the need of even few costly human annotations, bridging the gap between supervised and superviee learning.
generalization performance
5 Limitations
The instantiation of HUME employs advances from different fields of study to solve the proposed optimization problem and consequently, it inherits some limitations which we discuss below.
Meta-optimization. For simplicity, HUME leverages MAML 27 to solve the proposed optimization problem (Eq. 7]. However, its non-convex nature prevents convergence the labelings which attain global optima. Though, it can be seen that the aforementioned objective is special case of well- studied bilevel optimization problems with convex inner part. Thus, HUME can greatly benefit from utilization of specialized optimization methods 77 78
79
80
to further boost the performance.
Number of classes and empirical label distribution. HUME assumes the number of classes and empirical label distribution is known priori common assumption in existing unsupervised learning approaches [13 14 59). Although, in this work, we also follow these assumptions, the proposed framework is compatible with methods which can estimate the required quantities [8] 82
6 Conclusion
We introduced HUME, a simple framework for discovering human labelings that sheds a new light on solving the unsupervised learning problem. HUME is based on the observation that a linear model can separate classes defined by human labelings regardless of the representation space used encode the data. We utilize this observation to search for linearly generalizable data labeling in representation spaces of two pretrained models. Our approach improves considerably over existing unsupervised baselines on all of the considered benchmarks. Additionally, it shows superior performance to a supervised baseline on the STL-10 dataset and competitive on the CIFAR-10 dataset. HUME could also be used to generate labelings for semi-supervised methods and to evaluate quality of self-supervised representations. Our model-agnostic framework will greatly benefit from new more powerful self-supervised and large pretrained models that will be developed in the future.
10

---

References
[1] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. simple framework for contrastive learning of visual representations. In International Conference Machine Learning, 2020.
[2] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton. Big self-supervised models are strong semi-supervised learners. In Advances in Neural Information Processing Systems, 2020.
[3] Kaiming He. Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Computer Vision and Pattern Recognition, 2020.
[4] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.0422 042997 2020.
[5] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders scalable vision learners. In Computer Vision and Pattern Recognition, 2022.
[6] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, 2021.
[7] Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Big Transfer (BiT): General visual representation learning. In European Conference on Computer Vision, 2020.
[8] Jeff Z. HaoChen, Colin Wei, Ananya Kumar, and Tengyu Ma. Beyond separability: Analyzing the linear transferability of contrastive representations to related subpopulations. In Advances in Neural Information Processing Systems, 2022.
[9] Guneet Singh Dhillon, Pratik Chaudhari, Avinash Ravichandran, and Stefano Soatto, A baseline for few-shot image classification. In International Conference on Learning Representations, 2020.
[10] Wei- Yu Chen, Yen-Cheng Liu, Zsolt Kira, Yu-Chiang Frank Wang, and Jia-Bin Huang. A closer look at few-shot classification. In International Conference on Learning Representations, 2019.
[11] Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, lain Barr, Yana Hasson, et al. Flamingo: a visual language model for few-shot learning. In Advances in Neural Information Processing Systems, 2022.
[12] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical cox-cooniiional image generation with CLIP latents. arXiv preprint arXiv:2204.065 06122,, 2022.
[13] Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, Marc Proesmans, and Luc Van Gool. SCAN: Learning to classify images without labels. In European Conference on Computer Vision, 2020.
[14] Chuang Niu, Hongming Shan, and Ge Wang. SPICE: Semantic pseudo-labeling for image clustering. IEEE Transactions on Image Processing, 011772647777.. 2022.
[15] J. B. MacQueen. Some methods for classification and analysis of multivariate observations. In Berkeley Symposium on Mathematical Statistics and Probability, 1967.
[16] Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised learning of visual features. In European Conference on Computer Vision, 2018.
[17] Andrei Atanov, Andrei Filatov, Teresa Yeo, Ajay Sohmshetty, and Amir Zamir. Task discovery: Finding the tasks that neural networks generalize on. In Advances in Neural Information Processing Systems, 2022.
[18] Fereshte Khani and Percy Liang. Removing spurious features can hurt accuracy and affect groups disproportionaatll. In ACM Conference on Fairness, Accountability, and Transparency, 2021.
11

---

[19] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, et al. Bootstrap your own latent- a new approach self-supervised learning. In Advances in Neural Information Processing Systems, 2020.
[20] Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo, Mare Szafraniec, et al. DINOv2: Learning robust visual features without supervision. arXiv preprint arXiv:2304.07199, 2023.
[21] Andre Martins and Ramon Astudillo. From softmax to sparsemax: sparse model of attention and multi-label classification. In International Conference on Machine Learning, 2016.
[22] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning, In Advances in Neural Information Processing Systems, 2017.
[23] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and Zico Kolter. Differentiable convex optimization layers. In Advances in Neural Information Processing Systems, 2019.
[24] Brandon Amos and J. Zico Kolter. OptNet: Differentiable optimization as layer in neural networks. In International Conference on Machine Learning, 2017.
[25] Akshay Agrawal, Shane Barratt, Stephen Boyd, Enzo Busseti, and Walaa M. Moursi. Differen- tiating through cone program. Journal of Applied and Numerical Optimization, 122:1077115, 2019.
[26] Shane Barratt. On the differentiability of the solution to convex optimization problems. arXiv preprint 1804 000905098, 2019.
[27] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model- agges--gnostic meta-learning for fast adapta- tion of deep networks. In International Conference on Machine Learning, 2017.
(28) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, et al. PyTorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, 2019.
[29] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, et al. Ten- sorFlow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint arXiv: 1003:06603.0466. 2016.
[30] Eric Arazo, Diego Ortega, Paul Albert, Noel E O'Connor, and Kevin McGuinness. Pseudo- labeling and confirmation bias in deep semi-supervised learning. In International Joint Confer- ence on Neural Networks, 2020.
[31] Kaidi Cao, Maria Brbic, and Jure Leskovec. Open-world semi-supervised learning. In Interna- tional Conference on Learning Representations, 2022.
[32] Adam Coates, Andrew Ng. and Honglak Lee. An analysis of single-layer networks in unsu- pervised feature learning. In International Conference on Artificial Intelligence and Statistics, 2011.
[33] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[34] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In Conference on Computer Vision and Pattern Recognition, 2009.
[35] Harold W Kuhn. The Hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
[36] Tal Ridnik, Emanuel Ben-Baruch Asaf Noy, and Lihi Zelnik. ImageNet-21K pretraining for the masses. Advances in Neural Information Processing Systems Track on Datasets and Benchmarks, 2021.
[37] Kihyuk Soho, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, et al. FixMatch: Simplifying supi-supe learning with consistency and confidence. In Advances in Neural Information Processing Systems, 2020.
12

---

[38] David Berthelot, Nicholas Carlini, Ekin D. Cubuk, Alex Kurakin, Kihyuk Sohn, et al. ReMix- Match: supirvviee learning with distribution matching and augmentation anchoring. In International Conference on Learning Representations, 2020.
[39] Yidong Wang, Hao Chen, Qiang Heng, Wenxin Hou, Yue Fan, et al. FreeMatch: Self-adaptive thresholding for semi-supervised learning. In International Conference on Learning Representa- lions, 2023.
[40] Wang Feng, Kong Tao, Zhang Rufeng, and Liu Huaping. Self-supervised learning by estimating twin class distribution. IEEE Transactions on Image Processing, 2023.
[41] Elad Amrani, Leonid Karlinsky, and Alex Bronstein. Self-supervieed classification network. In European Conference Computer Vision, 2022.
[42] Jianfeng Wang, Thomas Lukasiewicz, Daniela Massiceti, Xiaolin Hu, Vladimir Pavlovic, and Alexandros Neophytou. NP-Match: When neural processes meet semi-supervised learning. In International Conference Machine Learning, 2022.
[43] Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jindong Wang, al. FlexMatch: Boosting semi-supervised learning with curriculum pseudo labeling. In Advances in Neural Information Processing Systems, 2021.
[44] Carl Doersch, Abhinav Gupta, and Alexei A. Efros. Unsupervised visual representation learning by context prediction. In International Conference on Computer Vision, 2015.
[45] Xiaolong Wang and Abhinav Gupta. Unsupervised learning of visual representations using videos. International Conference on Computer Vision, 2015.
[46] Mehdi Noroozi and Paolo Favaro. Unsupervised learning of visual representations by solving Jigsaw puzzles. In European Conference on Computer Vision, 2016.
[47] Richard Zhang, Phillip Isola, and Alexei A Efros. Colorful image colorization. In European Conference on Computer Vision, 2016.
[48] Deepak Pathak, Ross Girshick, Piotr Dollár, Trevor Darrell, and Bharath Hariharan. Learning features by watching objects move. In Computer Vision and Pattern Recognition, 2017.
[49] Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. In International Conference on Learning Representations, 2018
[50] Fuzhen Zhuang, Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, et al. A comprehensive survey transfer learning. Proceedings of the IEEE, 109(1):43-76, 2020.
[51] Kuniaki Saito, Donghyun Kim, Stan Sclaroff, and Kate Saenko. Universal domain adaptation through self supervision. In Advances in Neural Information Processing Systems, 2020.
[52] Kuniaki Saito and Kate Saenko. Ovanet: One-vs-all network for universal domain adaptation. In International Conference on Computer Vision, 2021.
[53] Gilles Blanchard, Aniket Anand Deshmukh, Ürun Dogan, Gyemin Lee, and Clayton Scott. Domain generalization by marginal transfer learning. The Journal of Machine Learning Research, 22(1):46-100, 2021.
[54] Piotr Teterwak, Kuniaki Saito, Theodoros Tsiligkaridis, Kate Saenko, and Bryan A. Plummer. ERM++: An improved baseline for domain generalization. arXiv preprint arXiv:2304.01973, 2023.
[55] Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07258, 2022.
[56] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, al. Language models are few-shot leamners. In Advances in Neural Information Processing Systems, 2020.
[57] OpenAl. GPT-4 technical report. arXiv preprint arXiv:2303.08777 2023.
13

---

[58] Anil Kumar Jain, M Narasimha Murty, and Patrick Flynn. Data clustering: a review. ACM Computing Surveys, 31(3):264-323, 1999.
[59] Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International Conference on Machine Learning, 2016.
[60] Jianlong Chang, Lingfeng Wang. Gaofeng Meng, Shiming Xiang, and Chunhong Pan. Deep adaptive image clustering. In International Conference on Computer Vision, 2017.
[61] Jianwei Yang, Devi Parikh, and Dhruv Batra. Joint unsupervised learning of deep representations and image clusters, In Conference Computer Vision and Puttern Recognition, 2016.
[62] Mathilde Caron, Piotr Bojanowski, Julien Mairal, and Armand Joulin. Unsupervised pre-training of image features on non-curated data. In International Conference on Computer Vision, 2019.
[63] YM Asano, C Rupprecht, and A Vedaldi. Self-labelling via simultancous clustering and representation learning. In International Conference on Learning Representations, 2020.
[64] Philip Haeusser, Johannes Plapp, Vladimir Golkov, Elie Aljalbout, and Daniel Cremers. Asso- ciative deep clustering: Training a classification network with no labels. In German Conference on Puttern Recognition, 2019.
[65] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control neural networks. In Conference on Learning Theory, 2015.
[66] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
[67] Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes. Fisher-Rao metric, ge- ometry, and complexity of neural networks. In International Conference on Artificial Intelligence and Statistics, 2019.
[68] Vaishnavh Nagarajan and J. Zico Kolter. Generalization in deep networks: The role of distance from initialization. In NeurlPS 2017 Workshop on Deep Learning: Bridging Theory and Practice, 2017.
(69) Samuel L. Smith and Quoe V. Le. A Bayesian perspective on generalization and stochastic gradient descent. In International Conference on Learning Representations, 2018.
[70] Yiding Jiang, Vaishnavh Nagarajan, Christina Back, and Zico Kolter. Assessing generalization of SGD via disagreement. In International Conference on Learning Representations, 2022.
[71] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv preprint arXiv:1803.0299 2018.
[72] Ondrej Bohdal, Yongxin Yang, and Timothy Hospedales. EvoGrad: Efficient gradient-based meta-learning and hyperparameter optimization. In Advances in Neural Information Processing Systems, 2021.
[73] Dong C. Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45:503-528, 1989.
[74] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
[75] Xu, Jiandong Ding, Lu Zhang, and Shuigeng Zhou. DP-SSL: Towards robust semi sunii-sueereised learning with a few labeled samples. In Advances in Neural Information Processing Systems, 2021.
[76] David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. MixMatch: holistic approach to semi-supervised learning. In Advances in Neural Information Processing Systems, 2019.
14

---

[77] Aurélien Ouattara and Anil Aswani. Duality approach to bilevel programs with a convex lower level. In American Control Conference, 2018.
[78] Jifí Outrata. On the numerical solution of a class Stackelberg problems. Zeitschrift für Operations Research, 34:255-277, 1990.
[79] Mihai Anitescu. On using the elastic mode in nonlinear programming approaches to math- ematical programs with complementarity constraints. SIAM Journal on Optimization, 15(4): 2005.
[80] Jane Ye and DL Zhu. Optimality conditions for bilevel programming problems. Optimization, 33(1):9-27, 1995.
[81] Kai Han, Andrea Vedaldi, and Andrew Zisserman. Learning to discover novel visual categories via deep transfer clustering. In International Conference on Computer Vision, 2019.
[82] Yiqi Wang, Zhan Shi, Xifeng Guo, Xinwang Liu, Zhu, and Jianping Yin. Deep embedding for determining the number of clusters. In AAA! Conference on Artificial Intelligence, 2018.
15

---

A Implementation details
Φ1 (-) pretrained the train split of the corresponding dataset with MOCOv2 2 Features are obtained after avgpool with dimension equal to 512. For the ImageNet-1k dataset, we utilize ResNet-50 backbone Φ1 (-) pretrained with MOCOv2. Here, features are obtained after avgpool with dimension equal to 2048. We use the same backbone and pretraining strategy for baselines well. To enforce orthogonality constraint the task encoder we apply Pytorch parametrizations B3. When precomputing representations we employ standard data preprocessing pipeline of the corresponding model and do not utilize any augmentations during HUME's training. In all experiments, we use the following hyperapameters: number of iterations 7 1000, Adam optimizer 4 with step size 0.001 and temperature of the sparsemax activation function 7 = 0.1. We anneal temperature and step size by 10 after 100 and 200 iterations. We set regularization parameter 77 to value 10 in all experiments and we show ablation for this hyperparameter in Appendix B To solve inner optimization problem we run gradient descent for 300 iterations with step size equal to 0.001. At each iteration we sample without replacement 10000 examples from the dataset to construct subset (Xtr: Xte), [ = 9000. [e = 1000. Since STL-10 dataset has less overall number of samples, we use 5000 (Xxrr 4500, X 500) in the inductive setting and 8000 ([X,rl 7200, X = 800) in the transductive setting. For the ImageNet- 1000 dataset we use inner and outer step size equal to 0.1, number inner steps equal to 100, sample 20000 examples with Xx, 14000, ttel = 6000 on each iteration. We do not anneal temperature and step size for the ImageNet-1000 dataset and other hyperparameters remain the same. To reduce the gradient variance, average the final optimization objective (Eq. 7 over 20 random subsets on each iteration. To stabilize training in early iterations, we clip gradient norm before updating task encoder's parameters. We use N Nneigh 500 in Algorithm GT to construct reliable samples for semi sumi-supereieed learning.
We utilize ResNett11 backbone
the weights of
B Robustness to regularization parameter
HUME incorporates entropy regularization of the empirical label distribution the final optimization objective (Eq. 7 to avoid trivial solutions, i.e., assigning all samples to single class. To investigate the effect of the corresponding hyperparameter y), we run HUME from 100 random initializations Wi for each v E (0, 2,2,5, 10) on the CIFAR-10 dataset. Figure B shows results with different values of hyperaparameter 7). The results show that is indeed necessary component of HUME objective, i.e., setting 17 = 0 leads to degenerate labelings since assigning all samples single class is trivially invariant to any pair of representation spaces. Furthermore, the results show that HUME is robust different positive values of the parameter 17. We set 7) = 10 in all experiments.
1.0
0.9
0.8
0.7
Accuracy
0.6
0.5
0.4
0.3
0.2
1
2
5
10
regularization parameter
Figure B1: Performance of HUME on the CIFAR-10 datasct with different values of the entropy regularization. We use MOCOv2 self sepersupe representations pretrained on the CIFAR-10 dataset and BiT large pretraincd model.
16

---

C Ablation study on different self-supervised methods
MOCOv2 [ self-supervised representations. Here, evaluate HUME's performance with different self-supervised learning method. In particular, we utilize SimCLR [5] and [6] to obtain representation space d1 (-). Table C1 shows the results in the inductive setting using DINO large pretrained model as the second representation space. The results show that HUME instantiated with MOCO consistently outperforms HUME instantiated with SimCLR all of the datasets. This is expected result since MÓCO representations are stronger also when assessed by a supervised linear probe. Alternatively, utilizing BYOL shows consistent improvements over MOCO representations. These results demonstrate that HUME can improve by employing stronger self- supervised representations, Interestingly, even with SimCLR representations HUME still outperforms unsupervised baselines pretrained with MOCOv2 in Table
In all experiments,
Table Cl: Comparison of different self supervisd representations. We use DINOv2 large pretrained model.
Stronger self-supervised representations lead to better performance.
STL-10
CIFAR-10
CIEAR-100-20
Method
ACC
ART
ACC
ARI
ACC
ART
SimCLR Linear
85.3
71.2
87.1
74.4
70.4
49.7
MOCO Linear
88.9
77.7
89.5
79.0
72.5
52.6
BYOL Linear
83.6
90.7
81.0
77.2
59.3
HUME CLR
86.9
74.3
85.2
71.8
51.8
33.9
HUME MOCO
90.8
81.2
88.4
77.6
55.5
37.7
HUME BYOL
91.5
82.7
89.8
79.7
56.0
40.3
D Correlation plots on the STL-10 and CIFAR-100-20 datasets.
@a)
(b)
STL-10 0-9.0 p 7.1 -0-
CIFAR-100-20 p 0.47,
5.9 10
Disagreement w/ human labeling
Disagreement w/ human labeling
0.56
0.25
0.54
0.20
0.52
0.15
0.50
0.48
0.10
0.46
0.05
0.06
0.08
0.10
0.12
0.27
0.28
0.29
0.30
HUME's objective
HUME's objective
Figure D1: Correlation plat between distance to ground truth human labeling and HUME's objective on (a) STL-100 datasct and (b) CIFAR-100- dataset. HUME generates different labelings of the data to discover underlying human labeling. For each labeling (data point the plot). HUME evaluates generalization error of linear classifiers in different representation spaces its objective function. The value of p corresponds corresponding two-sided test. HUME objective
Pearson correlation coefficient and is p-value well correlated with a distance to human labeling. In particular, tasks with lower HUME's objective tend to better match ground truth labeling. i.e., 0.9. = 7.1x 10 37 on the STL10 dataset and 0.47, p 5.9 x 10 the CIFAR- CIFAR-100-24 100-20 datasct.
17

---

The HUME's objective is to search over the labelings of a dataset by minimizing generalization error. To show the correlation between HUME's 's objective and the ground truth labeling, we plot correlation between generalization error of the labeling measured by cross-validation accuracy with respect to the found labeling and accuracy of the found labeling with respect to ground truth labeling. In addition to the results on the CIFAR-10 10 dataset presented in the main paper, Figure[D] D shows the correlation plots on the STL-10 and CIFAR- 100-20 datasets. The results demonstrate that HUME achieves the lowest generalization error for tasks that almost perfectly correspond to the ground truth labeling on the STL-10 dataset, allowing HUME to recover human labeling without external supervision. On the CIFAR-100 100-20 dataset even the supervised linear model on top of MOCOv2 self-supervised representations does not attain low generalization error (72.5% accuracy in Table I Consequently, HUME's s performance also reduces, thus this additionally suggests that employing stronger representations will lead to better performance of HUME as also shown in Appendix C Nevertheless, Figure D1b shows fairly-positive correlation (p 0.47, = 5.9 10- between distance to ground truth human labeling and HUME's objective, thus confirming the applicability of HUME more challenging setups when one of the representation spaces might be insufficiently strong.
E Quality of the reliable samples produced by HUME
HUME can be used to produce reliable samples which can be further utilized with any semi-supervised learning (SSL) method. To measure the quality of reliable samples, we use two different statisties of the produced reliable samples: per class balance and per class accuracy. Per class balance measures number of samples for each ground truth class, i.e., Σjer [ = ki]. where R is the set of indices of produced reliable samples, fy is the ground truth label of sample j. represents one of the ground truth classes number and [t] corresponds to Iverson bracket. Per class accuracy measures the average per class accuracy of the corresponding set of the reliable samples with respect to ground truth labeling. We follow standard protocol for the evaluation of SSL learning methods (7] and consider 4, 100 samples per class on the STL-10 dataset and 1, 4, 25, 400 samples per class on the CIFAR- 10 dataset. We provide results averaged across all classes in Table El and the corresponding standard deviations across classes in Table E In addition to the provided statistics, Figure EE] presents accuracies of the reliable samples the STL-10 and CIFAR-100-20 datasets for wider range of number of reliable samples per class. Overall, the results show that on the STL-10 and 100AR-10 datasets HUME shows almost perfect balance and mean per class accuracy, i.e., up to 100 samples per class on STL-10 and up to 400 samples per class on CIFAR-10, thus demonstrating that HUME can produce reliable pseudo-labels for SSL methods.
Table E1: Mean per class balance and mean per class accuracy for the reliable samples produced by HUME on the STL-10, CIFAR-I0 and CIFAR-100 datasets. Mean is computed over the number of classes in the corresponding dataset.
STL-10
CIFAR-10
CIFAR-160-20
Quantity
100
25
400
10
50
100
Mean Per Class Balance
4.0
100.0
1.0
4.0
25.0
400.0
0.6
6.3
26.3
52.6
Mean Per Class Accuracy
100.0
99.6
100.0
100.0
99.6
99.7
72.7
62.3
51.1
48.9
Table E2: Standard deviations of per class balance and per class accuracy for the reliable samples produced by HUME on the STL-10, CIFAR-I0 and CIFAR-100 datasets. Standard deviations are computed over the number of classes in the corresponding dataset.
STL.110
CIFAR-10 10
CIFAR-100-22
Quantity
4
100
1
4
25
400
1
10
50
100
Mean Per Class Balance
0.0
1.4
0.0
0.0
0.5
1.3
0.6
5.2
23.6
45.6
Mean Per Class Accuracy
0.0
0.9
0.0
0.0
1.2
0.4
44.1
41.9
46.5
47.2
18

---

(a)
(b)
STL-10
CIFAR-100-20
1.00
0.90
0.99
0.80
Accuracy
0.98
Accuracy
0.97
0.70
0.60
0.94
10
25
50
100
250 All
10
50
100
250
1000
2000 All
Number of reliable samples per class
Number of reliable samples per class
Figure E1: Accuracy of the reliable samples on the (a) STL-10 dataset and (b) CIFAR- 100-20 dataset.
Ablation study on different aggregation strategies on the STL-10 and CIFAR-100-20 datasets
We additionally study the effect of the proposed aggregation strategy on the STL-10 and CIFAR- 100-20 datasets in an inductive setting. We employ MOCOv2 self-supervised representations as representation space o (.) and show the results for different large pretrained models representation space 62(.). Figure F1 shows the results for the STL-10 and CIFAR-100
datasets, respectively. We observe the similar behaviour to the results obtained in the main paper the CIFAR-10 dataset. Namely, the proposed aggregation strategy stabilizes the results and provides robust predictions. is worth noting that For weaker models such as BiT, aggregation strategy has more effect on the performance and the optimal strategy is to aggregate around top-10 10 tasks. This is expected given the high correlation between HUME's objective and accuracy on ground truth labels since this strategy gives robust performance and tasks are closer human labeled tasks. Larger models such DINO show high robustness to the aggregation strategy. is important to emphasize that in experiments we always report average across all tasks and do not optimize for different aggregation strategies.
using top-5 labelings in the majority vote is enough to produce stable results.
(a)
(b)
1.00
0.60
DINO
---
CLIP
-
BiT
DINO
CLIP
BiT
0.95
0.55
Accuracy
Accuracy
0.90
0.50
0.85
0.45
0.80
0.40
10 20 30 40 50 60 70 80 90 100
1
30 40 50 60 70 80 90 100 Top-n tasks w.r.t. HUME'S objective
10 20
Top-n tasks w.r.t. HUME's objective
Figure Fl: Different aggregation strategies the (a) STL-10 10 dataset and (b) CIFAR 100-20 dataset. We MOCOv2 self--uupervied representations pretrained on the corresponding dataset and each line on the plot corresponds to the type of the large pretrained model.
19

---

G Algorithm for constructing reliable samples
We showed that HUME can be utilized to construct a set of reliable labeled examples to transform an initial unsupervised learning problem to a semi-supervisee problem. It is worth noting that standard semi-supervised setting requires balanced labeled set, i.e., equal number of labeled samples for each class. For simplicity, we adapt the approach presented in SPICE [8] to produce a balanced set of reliable samples. Namely, we sort all samples per class by (i) number of labelings in the majority vote which predict the same class, and (ii) number of neighbours of the sample which have the same class. Thus, we consider sample reliable if both quantities are high. Finally, given the sorted order we take the required number of samples to stand as set of reliable samples. The proposed algorithm outlined in Algorithm GT
Algorithm G1 Reliable samples construction
Input: Dataset D, number of classes K, number of samples per class N₁. number of neighbours Nneigh self-supervised representation space Φ1 (+), trained labelings T : Tm
1: Compute majority vote: TMA)(I)) = arg max E [T:(x)) k]
k=l.....K
2: Count number of agreed labelings:
A²(x) Σ (x) = (M)
3: Find nearest neighbours in representation space Φ1
(xx) + Neiggh nearest neighbours for sample x E 'D
4: Count number of agreed nearest neighbours:
(z) = LeN((.) [T) [M)]
5: Initialize set of reliable samples: R
6: for k = 1 to K do
7: Take per class samples: Sg = {ar D (ITMA)())) = k}
8: Sort S₃ in descending order by lexicographic comparison of tuples A")
9: Take top-N& samples from the sorted S₁ and update set of reliable samples:
R R (op-Nx(Sk)
10: end for
References
[1] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Conference on Computer Vision and Pattern Recognition, 2016.
[2] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning, arXiv preprint N0t.::2000300299.,. 2020.
[3] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, et al. PyTorch: An imperative style, high-peeffrmaacc deep learning library. In Advances in Neural Information Processing Systems, 2019.
[4] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint arXiv:1412.6980, 2017.
[5] Ting Chen, Simon Korbblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International Conference Machine Learning, 2020.
[6] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, et al. Bootstrap your own latent a new approach to self-supervised learning, In Advances in Neural Information Processing Systems, 2020.
[7] Yidong Wang, Hao Chen, Qiang Heng, Wenxin Hou, Yue Fan, al. FreeMatch: Self-adaptive thresholding for semi-supervised learning. In International Conference on Learning Represen- tations, 2023.
[8] Chuang Niu, Hongming Shan, and Ge Wang. Spice: Semantic pseudo-laheling for image clustering. IEEE Transactions Image Processing, 31:7264-7278, 2022.
20


Reviews:
[{"review_id": "v9Lw9yOddg", "reviewer": "Reviewer_uZTE", "summary": "The authors propose a clever method that exploits recent findings about the effectiveness of linear probing across diverse representation spaces in order to discover semantically-meaningful clusters (i.e. ones that correspond to human labeling) by seeing which linearly-separable clusters are preserved across multiple representation spaces. ", "questions": "- When producing reliable samples for SSL, what is the class balance? The usefulness is impacted significantly by the diversity of the samples HUME can produce. I see in Fig 3a) that samples are produced from each class, but is performance roughly the same across all classes?\n- Are all three of the large-pretrained models that you use pre-trained in unsupervised ways (e.g. none were ever actually trained on the ImageNet classes)?  \n- Unrelated to the review/scoring and purely out of curiosity, why did you name your method HUME? Is it an acronym for something?", "limitations": "See weaknesses and questions sections. ", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- HUME is a very clever method that beautifully exploits recent findings about the effectiveness of linear probing across diverse representation spaces. \n- The paper is well-written and easy to follow. ", "weaknesses": "- It's unclear whether performance gains are driven by HUME or by the strength of the second representation space. Additional baseline experiments with linear probing and clustering on top of the large pre-trained model representations (DINOv2, CLIP, ViT) would help clarify this. Another nice baseline evaluation that could help would be to simply concatenate the embeddings from the two representation spaces and repeat the linear probing and clustering evaluations on that. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive evaluation of our work and for acknowledging the methodological novelty of our method. We are glad that the reviewer finds HUME to be *a very clever method that beautifully exploits recent findings about the effectiveness of linear probing* as well as our paper to be  well-written and easy to follow. Below, we address the reviewer's concerns and we hope that our response helps to increase the reviewer's confidence.\n\n>*It's unclear whether performance gains are driven by HUME or by the strength of the second representation space. Additional baseline experiments with linear probing and clustering on top of the large pre-trained model representations (DINOv2, CLIP, ViT) would help clarify this. Another nice baseline evaluation that could help would be to simply concatenate the embeddings from the two representation spaces and repeat the linear probing and clustering evaluations on that.*\n\nWe thank the reviewer for suggesting to incorporate additional baselines. Based on the reviewer’s suggestion, we now included two additional baselines (1) clustering on top of the DINO representation space as the strongest representation space and (2) clustering on top of concatenated embeddings from DINO and MOCO. The results in Table 2 in the rebuttal pdf show that the performance gains are driven by HUME. Compared to DINO, HUME achieves an improvement of 51%, 17% and 18% in accuracy on the STL-10, CIFAR-10 and CIFAR-100-20, respectively.  Compared to DINO+MOCO, HUME achieves 18%, 9% and 8% relative improvement in accuracy on the STL-10, CIFAR-10 and CIFAR-100-20, respectively. We will add these baselines in the future revision of the paper to further strengthen the evaluation part of our work.\n\n>*When producing reliable samples for SSL, what is the class balance? The usefulness is impacted significantly by the diversity of the samples HUME can produce. I see in Fig 3a) that samples are produced from each class, but is performance roughly the same across all classes?*\n\nWe thank the reviewer for suggesting additional analysis of reliable samples produced by HUME. The detailed statistics requested by the reviewer are provided in the Table below. We follow standard protocol for the evaluation of semi-supervised learning methods [1] and consider 4, 100 samples per class on the STL-10 dataset and 1, 4, 25, 400 samples per class on the CIFAR-10 dataset. On the STL-10 and CIFAR-10 datasets HUME shows almost perfect balance and mean per class accuracy, i.e., up to 100 samples per class on STL-10 and up to 400 samples per class on CIFAR-10.    \n**Per Class Balance** measures number of samples for each ground truth class, i.e., $\\frac{1}{K}\\sum_{k=1}^{K}\\sum_{j \\in R} [y_j = k]$ where $R$ is the set of indices of produced reliable samples and $y_j$ is the groundtruth label of sample $j$. \n**Per Class Accuracy** measures the average per class accuracy of the corresponding set of the reliable samples. The number in the brackets in the dataset title corresponds to the number of reliable samples per class. \n|                    | STL-10 (4)  | STL-10 (100) | CIFAR-10 (1) | CIFAR-10 (4) | CIFAR-10 (25) | CIFAR-10 (400) | CIFAR-100-20 (1) | CIFAR-100-20 (10) | CIFAR-100-20 (50) | CIFAR-100-20 (100) |\n|--------------------|--------------|---------------|--------------|--------------|---------------|----------------|------------------|-------------------|-------------------|--------------------|\n| Per Class Balance  | 4.0 +- 0.0   | 100.0 +- 1.4  | 1.0 +- 0.0   | 4.0 +- 0.0   | 25.0 +- 0.5   | 400.0 +- 1.3   | 0.6 +- 0.6       | 6.3 +- 5.2        | 26.3 +- 23.6      | 52.6 +- 45.6       |\n| Per Class Accuracy | 100.0 +- 0.0 | 99.6 +- 0.9   | 100.0 +- 0.0 | 100.0 +- 0.0 | 99.6 +- 1.2   | 99.7 +- 0.4    | 72.7 +- 44.1     | 62.3 +- 41.9      | 51.1 +- 46.5      | 48.9 +- 47.2       |\n\nWe thank the reviewer for the insightful question and we will include these results in the final revision of the paper.\n\n[1] Wang et al. FreeMatch: Self-adaptive Thresholding for Semi-supervised Learning. ICLR 2023\n\n>*Are all three of the large-pretrained models that you use pre-trained in unsupervised ways (e.g. none were ever actually trained on the ImageNet classes)?*\n\nCLIP and DINO are pretrained in an unsupervised way using contrastive learning based methods. CLIP ViT-L/14 is pretrained on WebImageText and DINOv2 ViT-g/14 is pretrained on LVD-142M. The only model pretrained in the supervised manner is BiT-M-R50x1 pretrained on ImageNet-21k. However, although BiT-M was pretrained in a supervised regime it shows the worst performance of the three considered large pretrained models and DINO and CLIP both show much better transferability of the representations to downstream datasets. We will comment on this in the revised paper to improve the presentation of our work.\n\n>*Unrelated to the review/scoring and purely out of curiosity, why did you name your method HUME? Is it an acronym for something?*\n\nHUME comes both as the acronym for HUMan labEling and from David Hume’s surname. David Hume was a philosopher who proposed new views on existing things. In our work, we propose a new perspective on the well established unsupervised learning field, thus reflecting the name. In addition, Hume also was an Empiricist, meaning he believed \"causes and effects are discoverable not by reason, but by experience\". In our work we **empirically** observe the surprising correlation between generalization error of ground truth labelings of a data and the proposed optimization objective, thus reflecting the empirical research approach.\n"}, {"review_id": "DtqjMvAoP9", "reviewer": "Reviewer_VWGE", "summary": "The work presents a new method for inferring human labeling without supervision. The main idea of the method is that human labels for a dataset should be linearly separable for all good representations, and relatively invariant to the representation space. The method uses bi-level optimization with an inner loop that optimizes for the pseudo-labels of a training set, and an outer loop which optimizes for the test loss of a classifier trained on the pseudo-labels. HUME achieves state-of-the-art performance on standard unsupervised learning benchmarks, CIFAR and STL-10. ", "questions": "- Can the method scale to larger datasets considering that second-order gradients need to be calculated? Does approximating the Hessian affect performance? \n\n- MAML is known to be difficult to optimize with respect to hyper-parameters. Does this make HUME sensitive to hyper-parameters such as the number of inner-loop steps, learning rate, etc?\n\n- In equation 3, you constrain the weights of the linear layer, $W_1$, to be orthonormal, but I didn’t see a mention of the method you’re using to do so. What is the reasoning for this design choice?\n", "limitations": "Limitations are well addressed by the authors. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The insight that human labels should be linearly separable in any sufficiently strong representation space is original and interesting. Showing that the objective function proposed in HUME is well correlated with human labeling is surprising, and would likely be useful to future work.\n\n- HUME outperforms state-of-the-art on standard unsupervised learning benchmarks by a fair margin and impressively outperforms the supervised linear probe on STL-10.\n\n\n- The paper is well organized and the writing is clear. \n", "weaknesses": "HUME uses DINO and MOCO while other methods only use MOCO. It could be that DINO is a better representation given that HUME with DINO outperforms HUME with other representations. It’s also unclear whether the performance gain is coming from ensembling multiple models or the optimization procedure of HUME. It would be useful to see an ablation where HUME is trained only on a MOCO representation for a straight-forward comparison to other unsupervised methods and to understand how much each component of HUME contributes.  \n\nAs stated in the limitations, the number of classes and label distribution must be known a priori. Other works in this subfield make the same assumption so this weakness is not particular to HUME. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive evaluation of our work and for acknowledging the originality of the proposed method as well as its significance for future research. We are glad that the reviewer finds the results impressive and our paper well written. \n\n>*HUME uses DINO and MOCO while other methods only use MOCO…*\n\nTo show that the increase in performance comes from the HUME’s optimization procedure, we included  an additional baseline which, like HUME, utilizes both DINO and MOCO representation spaces at the same time (Table 2  in the rebuttal pdf) . We generate embeddings from DINO and MOCO, concatenate these embeddings and then perform clustering on top of concatenated embeddings. Results show that HUME achieves 18%, 9% and 8% improvement in accuracy over the baseline on the STL-10, CIFAR-10 and CIFAR-100-20 datasets, respectively. We will add these results in the revised paper.\n\n>*It’s also unclear whether the performance gain is coming from ensembling multiple models or the optimization procedure of HUME.*\n\nWe thank the reviewer for the insightful question. The results in Fig. 3b and Fig. D1 in the Appendix D show the ablations of using different aggregation strategies (ensembling).  The leftmost strategy (at x = 1) corresponds to a single labeling (w/o ensembling), while the rightmost data point (at x = 100) corresponds to aggregation over all models. Results show that utilizing stronger pretrained models eliminates the need of ensembling many models, since they lead to more robust performance. Additionally, given the high correlation between HUME’s objective and human labeling, HUME achieves even better performance by aggregating only the top few models compared to our current strategy that aggregates all models. However, we do not optimize for this in our experiments since our goal is not to report the best results HUME can achieve but rather to demonstrate the correlation between HUME’s objective and ground truth labeling. In response to the reviewer's feedback, we will provide these clarifications in the revised paper.\n\n>*It would be useful to see an ablation where HUME is trained only on a MOCO representation …*\n\nWe thank the reviewer for suggesting this evaluation; however, it is not applicable to HUME as it leads to a degenerate solution. The reason is that the key idea of HUME is to jointly use **two different** representation spaces to find ground truth data labeling over all possible labelings. HUME utilizes two representation spaces $\\phi_1(\\cdot)$ and $\\phi_2(\\cdot)$. $\\phi_1(\\cdot)$ is used by the task encoder $\\tau(\\cdot) = W_1 \\frac{\\phi_1(\\cdot)}{\\|\\phi_1(\\cdot)\\|_2}$ to propose labelings of the data using linear layer $W_1$ at each iteration of the method. $\\phi_2(\\cdot)$ is used to assess the generalizability of the current proposal $\\tau$ using linear layer $W_2$ in the representation space $\\phi_2(\\cdot)$. Since task encoder $\\tau$ proposes labelings using linear layer $W_1$, **utilizing the same representation space** $\\phi_2(\\cdot)$, i.e., $\\phi_2(\\cdot) = \\phi_1(\\cdot)$, **will automatically lead to degenerate solutions**, i.e. $\\forall\\ W_1, \\ W_2 = W_1$ can be easily inferred using logistic regression (inner optimization Eq. (4)) and, thus, will always be a generalizable task, which will prevent HUME from finding the ground truth labeling. We will explain this and clarify the importance of utilizing two **different** representation spaces in the revised paper.\n\n>*Can the method scale to larger datasets …*\n\nHUME is a scalable method that can be applied to the dataset of any size. The inner optimization problem in HUME is multiclass logistic regression solved by running stochastic gradient descent for a fixed number of iterations, thus depending only on the batch size and dimensionality of the representations rather than the dataset size. Additional experiments on large scale Imagenet-1000k benchmark provided in Table 1 (rebuttal pdf) further support wide applicability of HUME. It is also important to highlight that HUME’s optimization objective (Eq. 7) has a form of a stochastic bilevel optimization (SBO) problem with the convex inner part. Thus, MAML can be replaced by any sophisticated convex SBO algorithm which is a rapidly developing research area [1, 2]. We will comment on this in the revised paper.\n\n[1] Huang et al. Efficiently Escaping Saddle Points in Bilevel Optimization. arXiv 2023\n\n[2] Dagreou et al. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. NeurIPS 2022\n\n>*MAML is known to be difficult to optimize with respect to hyper-parameters. Does this make HUME sensitive to hyper-parameters …?*\n\nHUME’s inner optimization is not sensitive to the hyperparameters since HUME’s inner optimization is a convex optimization problem, i.e. multiclass logistic regression, thus it does not require extensive hyperparameter search. In our preliminary experiments on the CIFAR-10 we set a learning rate to 0.001 and number of iterations equal to 300 and fix them across all experiments. \n\n>*In equation 3, you constrain the weights of the linear layer, $W_1$, to be orthonormal, but I didn’t see a mention of the method you’re using to do so. What is the reasoning for this design choice?*\n\nOrthogonal weight matrix $W_1$ is parametrized using a product of elementary Householder reflectors, i.e., $W_1 = H_1 H_2 \\dots H_m$, where each $H_i = I - \\tau v_i v_i^T$. We utilize the standard PyTorch parametrizations module making the implementation straightforward in practice. We will add these details in the revised paper. This design choice  may be viewed as learning prototypes for each class which is an attractive modeling choice for the representation space $\\hat{\\phi}_1(\\cdot) = \\frac{\\phi_1(\\cdot)}{\\|\\phi_1(\\cdot)\\|_2}$. Thus, $W_1 \\hat{\\phi}_1(\\cdot)$ corresponds to the cosine similarities between class prototypes $W_1$ and the encoding of the sample $\\hat{\\phi}_1(\\cdot)$ (lines 138-142).\n"}, {"review_id": "UYjhl2wMnc", "reviewer": "Reviewer_J4o2", "summary": "This work proposes HUME, an unsupervised framework for inferring labels of an image dataset. Based on the assumptions of linear separability and model invariance, the authors propose an objective that utilizes two self-supervised models, one on the target dataset and another using large-scale pre-training. Specifically, a linear mapping is applied on the first model representation to generate pseudo labels, which is updated by MAML to minimize classification loss of another linear classifier on the second representation. HUME is empirically evaluated on three image datasets, outperforming deep clustering and sometimes also linear probing baselines.", "questions": "Using 300 iterations (supp. L564) for the inner loop of MAML appears quite impractical. I would appreciate if the authors can comment on the computational cost of HUME, or correct any misunderstanding I had with the implementation.", "limitations": "Limitations are discussed in the paper. There is no discussion of broader societal impacts as the paper focus on foundational learning algorithms; though the authors may consider discussing the possibility of biases of large pretrained models being transferred to the pseudo labels through HUME, etc.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well organized, with the entire model built around two key assumptions (linear separability and model invariance). Strong justifications are provided for each component.\n- Experiments are conducted on multiple dataset and models to validate the generalizability of HUME.\n- Ablations studies are included on aggregation over n runs, regularization weight, self-supervised representation etc.", "weaknesses": "- My biggest concern is on the assumption of linear separability on pretrained representations. This is probably true for easy-to-classify datasets (e.g. CIFAR-10) but less likely for fine-grained tasks (e.g. CIFAR-100). There exists much more challenging vision datasets than the ones studied in the paper, where it may be difficult, if at all possible, to find a feature space that linearly separates all classes. I doubt HUME will scale favorably to these datasets.\n\t- Results in table 1 seems to confirm this suspicion, as the relative performance of HUME to linear probing drops quickly as the datasets becomes more difficult.\n\t- One may further argue that if the classes are already linearly separable, then only a few labeled examples per class are needed to achieve high accuracy, which should not cost substantial human effort to annotate. The most demanding tasks to annotate are often the ones for which a good representation does not exist.\n- The fairness of experimental comparisons is questionable:\n\t- HUME makes use of large pretrained models such as DINO, unlike other unsupervised methods that are learned on target dataset only. I am not sure to what extent the improvement should be attributed to the stronger feature representation of large models. The authors can consider adding comparison to deep clustering or linear probing using large models as backbone.\n\t- The authors compared to a variant of SPICE without joint training ($\\rm SPICE_S$). The standard SPICE outperforms HUME by jointly updating the feature model.\n- If the class vocabulary is known, this also enables zero-shot classification by vision-language models (e.g. CLIP). I am curious how fully unsupervised methods like HUME compares to CLIP in assigning pseudo labels, or if the two can be combined into a stronger model (not just using CLIP ViT as a feature extractor, but facilitating its joint embedding space for image and text).\n- Despite the claim that HUME can benefit semi-supervised learning, no SSL models were trained and evaluated to verify this. The accuracy of reliable samples serves as an indirect proof, but cannot replace full semi-supervised experiments, e.g., by following the joint training step in SPICE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for valuable feedback and for appreciating the coherence of our presentation, strong justification of each component of our framework and extensiveness of  our experiments. \n\n*The biggest concern of the reviewer is the assumption of linear separability of pretrained representations.*\n\n**Supervised linear probe** is a gold standard evaluation protocol in the self-supervised/weakly supervised representation learning (e.g., [1-3])]. This whole research area assumes that the produced representations are strong enough to be separated by a linear classifier. For example, [2] shows that supervised linear probe on top of CLIP-ViT-L-14 features outperforms the best known **supervised** model on 21/27 datasets. DINOv2 [1] provides in-depth study and shows the outstanding performance of supervised linear probe on a wide variety of tasks such as domain generalization, image and video classification, fine-grained benchmarks etc. In addition to strong empirical evidence, recent works [e.g., 4-6] study the linear separability of contrastive representations from the theoretical perspective. For example, [4] theoretically analyzes when contrastive representations exhibit linear separability in unsupervised domain adaptation, while [5] provides guarantees on the downstream performance of a linear model on top of pretrained representations. All these results validate the linear separability assumption of pretrained representations. Our work provides a new view on tackling unsupervised learning from this perspective and shows viability of the proposed concepts in practice. We will add a detailed exposition of this assumption in the revised paper. We hope that these clarifications help the reviewer to reconsider the overall evaluation of our work.\n\n[1] DINOv2: Learning Robust Visual Features without Supervision. arXiv preprint 2023.\n\n[2] Learning Transferable Visual Models From Natural Language Supervision. ICML 2021\n\n[3] A Simple Framework for Contrastive Learning of Visual Representations. ICML 2020\n\n[4] Beyond Separability: Analyzing the Linear Transferability of Contrastive Representations to Related Subpopulations. NeurIPS 2022.\n\n[5] A Theoretical Analysis of Contrastive Unsupervised Representation Learning. ICML 2019\n\n[6] Contrastive estimation reveals topic posterior information to linear models. JMLR, 2021\n\n>*I doubt HUME will scale favorably to more challenging vision datasets.*\n\nTo show scalability to large datasets we now included results on the ImageNet-1k dataset. Results in Table 1 (rebuttal pdf) show the remarkable improvement of 24% in accuracy over existing large-scale unsupervised baselines from the literature, thus confirming the scalability of HUME to challenging fine-grained benchmarks.\n\n>*The authors can consider adding comparison to deep clustering or linear probing using large models as backbone.*\n\nWe now include an additional baseline by clustering DINO representations. Table 2 (rebuttal pdf) shows that HUME achieves 51%, 17% and 18% improvement in accuracy over this baseline on the STL-10, CIFAR-10 and CIFAR-100-20 datasets, respectively. \n\n>*Despite the claim that HUME can benefit semi-supervised learning, no SSL models were trained and evaluated to verify this.*\n\nWe thank the reviewer for suggesting this analysis. Any SSL method can be applied after HUME. We now applied the state-of-the-art SSL method FreeMatch on the CIFAR-10 with 1,4,25 and 400 samples per class. We compare the performance of FreeMatch w/ ground truth (GT) labels to FreeMatch w/ HUME’s reliable samples (Table 3 in the rebuttal pdf). Results show that FreeMatch w/ reliable samples performs on par with FreeMatch w/ GT labels except on CIFAR-10 with 4 samples.However, HUME produces 4 perfectly accurate samples per class (see Fig. 3a) and the discrepancy in this setting can be alleviated by averaging the results across several 4 reliable samples per class as it is done in the standard SSL evaluation. Due to the time constraints during the rebuttal and substantial time needed to run FreeMatch, we could only do a single run for each setting. We will provide the complete results with multiple runs in the revised paper.\n\n>*The authors compared a variant of SPICE without joint training. …*\n\nSPICE includes 3 steps: (1) self-supervised pretraining, (2) clustering, and (3) joint training with SSL method. Given reliable samples produced in step (2), any SSL method can be applied in the step (3) for both SPICE and HUME. Thus, we directly compared the crucial clustering step between SPICE and HUME since this step is used to generate reliable samples and solves unsupervised learning task. Results show that HUME significantly outperforms SPICE thus consequently results in better pseudo-labels. Moreover, the additional results in the previous answer demonstrate that running SSL methods on reliable samples of HUME is comparable to running SSL on ground truth labels.\n\n>*I am curious how fully unsupervised methods like HUME compares to CLIP...*\n\nHUME can be easily applied for image-text data where $\\phi_1(\\cdot)$ is the text encoder and $\\phi_2(\\cdot)$ is the image encoder. We agree that it is an interesting research direction to combine the two but it is out of scope of this work focused on single-modality data and unsupervised learning setting compared to zero-shot in CLIP. We leave this for future work.\n\n>*Using 300 iterations for the inner loop of MAML appears quite impractical…*\n\nHUME’s inner optimization is not sensitive to the hyperparameters since HUME’s inner optimization is a convex optimization problem. For simplicity, HUME utilizes cold-start bilevel optimization (BLO) [1] but thanks to the form of HUME’s objective, any sophisticated BLO algorithm, e.g. [2], can be applied to improve the convergence rate and reduce iteration complexity of HUME.\n\n[1] On Implicit Bias in Overparameterized Bilevel Optimization. ICML 2022\n\n[2] Efficiently Escaping Saddle Points in Bilevel Optimization. arXiv 2023\n"}, {"review_id": "jNERLGAxiN", "reviewer": "Reviewer_BH9W", "summary": "This paper proposes a novel unsupervised learning algorithm called HUME.\n\nHUME aims to minimize the disagreement between two linear models. The two linear models consume features from different backbones, and thus they are iteratively optimized to map difference feature spaces into the same label space.\n\nHUME has achieved very promising results on extensive experiments conducted in this paper.\n\n", "questions": "I am personally interested in applying semi-supervised learning to the reliable pseudo labels.\n\nCould you provide the following results?\n\n(1) Comparison of using reliable pseudo labels versus human labels\n\n(2) Results on more datasets\n\nThis is not obligatory, and you could put the results in the appendix.", "limitations": "The authors have raised 2 limitations and proposed reasonable solutions for mitigation.\n\nI don't find other limitations of this work.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "(1) This paper provides a fundamentally new view to tackle unsupervised learning by searching for consistent labelings between different representation spaces, i.e., human-labeled tasks are invariant to sufficiently strong representation spaces, it gives valuable insights to the following research works\n\n(2) HUME outperforms existing state-of-the-art unsupervised learning methods by a large margin and can achieve comparable or better performances than supervised learning on some tasks\n\n(3) HUME can produce reliable labels for semi-supervised learning to further boost the performance, which provides a good starting point for applications in many low-resource scenarios", "weaknesses": "I don't find substantial weakness from this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very positive evaluation of our work and acknowledging the fundamentally new perspective on unsupervised learning which our work proposes. We are glad that the reviewer appreciates the extensiveness of our experiments and finds our results very promising. We are also glad that the reviewer recognizes the importance of tackling the well-established unsupervised learning problem from a fresh standpoint that can facilitate future research.\n\n>*Comparison of using reliable pseudo labels versus human labels and results on more datasets*\n\nWe agree with the reviewer on the importance of supplementing the evaluation with additional datasets to further strengthen the experimental part of our work. In response to the reviewer’s request we added the following additional experiments: (i) accuracy plots of reliable samples on the STL-10 and CIFAR-100-20 datasets, (ii) semi-supervised learning using reliable samples on CIFAR-10 and (iii) evaluation of HUME on large scale fine-grained ImageNet-1000k benchmark. We will add these results in the future revision of the paper.\n\nFirst, Fig. 2a and Fig. 2b in the provided rebuttal pdf show that HUME can produce up to 100 almost perfectly accurate samples per class (>= 99% accuracy) on the STL-10 dataset and up to 100 reliable samples per class (>= 85% accuracy) on the CIFAR-100-20 dataset. Secondly, we apply the state-of-the-art semi-supervised method FreeMatch[1] on the CIFAR-10 dataset with 1,4, 25 and 400 samples per class. We compare the performance of FreeMatch with ground truth labels to FreeMatch supervised with HUME’s reliable samples (Table 3 in the rebuttal pdf). The results show that FreeMatch with HUME’s reliable samples performs on par with FreeMatch with ground truth labels. The only exception is CIFAR-10 with 4 samples. However, HUME produces 4 perfectly accurate reliable samples per class (see Fig. 3a in the main paper) and the discrepancy in this setting can be alleviated by averaging the results across several 4 reliable samples per class as it is done in the standard SSL evaluation. Due to the time constraints during the rebuttal period and substantial time needed to run FreeMatch, we could only do a single run for each setting. We will provide the complete results with multiple runs and standard deviation in the future revision of the paper.\n\nLast but not least, we add ImageNet-1000k dataset to evaluate HUME on the challenging large scale fine-grained classification benchmark. Table 1 in the rebuttal pdf shows the significant improvement of 24% in accuracy over existing large-scale unsupervised baselines proposed in the literature, thus confirming the applicability of HUME to more challenging problems.\n\n[1] FreeMatch: Self-adaptive Thresholding for Semi-supervised Learning. ICLR 2023\n"}, {"review_id": "SYULukrG7l", "reviewer": "Reviewer_BUAb", "summary": "The paper proposes a framework, called HUME, for providing human labels without any supervision. The method uses an assumption that classes derived from human labelling are linearly separable regardless of the representation space used to represent the dataset, ie invariant to sufficiently strong representation spaces. The authors show that this method generates labels that are correlated with human labeling (ie ground truth) of the dataset. HUME also shows good performance on STL-10 (ie better than a supervised linear classifier), and comparable performances on other datasets. Results are even more striking, for all the datasets used, when compared against other unsupervised methods. Finally, HUME provides reliable samples  on CIFAR-10.", "questions": "* What do the authors mean by “unbiased estimate” (line 90)?\n* Which distance measure is used for fig. 1? Could this be clarified in the paper?\n* Could the authors provide in appendix the same fig. 1 but for other datasets (eg CIFAR-100-20 and STL-10)? Since being well-correlated with humans is essential for the proposed method, it would be interesting to see if this result generalizes for other datasets as well.\n* In the paper it is mentioned in both Definitions 1 and 2 the sentence “attains low test error” (lines 101 and 105), but how low is not commented throughout the text and this is left a bit uncommented… could the authors expand on that? Could the authors also provide some analysis/experiments on this front?\n* Could the authors provide a better explanation for the difference between inductive and transductive procedures? Is it the case that the inductive one a model is learned during training, and then just the model is used to make predictions on unseen data, and in the transductive case the data is kept for the inference as well (eg using some form of nearest neighbor analysis)?\n* In Table 1, could the authors provide an intuition behind why the results seem to improve more for the transductive than for the inductive procedure?", "limitations": "Yes, limitations have been well addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "From the related work explained in the paper, this is the first work in the literature to provide a method that does not rely on semantic knowledge of samples, eg clustering, but rather it uses a novel generalization perspective. The idea of using two pretrained models to generate human-like labels under an unsupervised manner is simple and interesting. The text is clear and overall well-written. The related work section is well expanded.", "weaknesses": "The paper could improve the analysis on the correlation of their labels with the ones humans provide, ie it’s not clear whether it generalizes to other datasets/settings, and this is a very important validation experiment of the proposed method since it’s part of the hypothesis of the paper (ie that human labeled tasks are linearly separable in a sufficiently strong representation space). Another analysis that could be added to the appendix is on the reliability of samples for other datasets (eg expands Fig. 3a of CIFAR-10 for other datasets). For now, it is only shown to work for CIFAR-10.\n\nMinor typo: line 107 “we only train linear classifiers on top pretrained representations” should probably have an “of” between “top” and “pretrained” words.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the simplicity of our methodology and the novelty of the generalization perspective for unsupervised learning. We are also glad that the reviewer appreciates the overall quality and soundness of our paper as well as thoroughness of the related work section. Below, we provide a detailed response to the reviewer’s questions and we hope that the provided clarifications will help in increasing the reviewer's confidence.\n\n>*The paper could improve the analysis on the correlation of their labels with the ones humans provide, ie it’s not clear whether it generalizes to other datasets/settings… Another analysis that could be added to the appendix is on the reliability of samples for other datasets*\n\nWe thank the reviewer for suggesting additional analysis. In the response to the reviewer’s suggestion we include the requested evaluation. First, Fig. 1a and Fig. 1b in the rebuttal pdf shows the strong correlation ($\\rho=0.9$) on the STL-10 dataset and fairly positive correlation ($\\rho=0.47$) on the CIFAR-100-20 dataset. Secondly, Fig. 2a and Fig. 2b in the provided rebuttal pdf show that HUME can produce up to 100 almost perfectly accurate samples per class (>= 99% accuracy) on the STL-10 dataset and up to 100 reliable samples per class (>= 85% accuracy) on the CIFAR-100-20 dataset. We will supplement the future revision of the paper with the provided analysis to further improve the presentation of our work.\n\n>*What do the authors mean by “unbiased estimate” (line 90)?*\n\nThe true risk of a model $f(\\cdot)$ on task $\\tau(\\cdot)$ is $E_{x \\sim p_{data}} \\mathcal{L}(f(x), \\tau(x))$. Since the true data distribution $p_{data}$ is not available we estimate it using samples from the given dataset $x_1, \\dots, x_{N_{test}} \\sim p_{data}$ using Eq. (1) which is unbiased estimate of the true risk. We will clarify this in the revised paper.\n\n>*Which distance measure is used for fig. 1? Could this be clarified in the paper?*\n\nWe thank the reviewer for noticing the missing explanation of the used distance measure. Caption of Fig. 1 refers to this distance as a generalization error. Indeed, we compute it as follows: $\\frac{1}{N_{test}}\\sum_{i=1}^{N_{test}}[\\tau_{gt}(x_i) \\neq \\tau(x_i)]$ where $\\tau_{gt}(\\cdot)$ is the ground truth labeling of the corresponding dataset and $\\tau(\\cdot)$ is the labeling found by HUME. We will further clarify this in the future revision of the paper.\n\n>*In the paper it is mentioned in both Definitions 1 and 2 the sentence “attains low test error” (lines 101 and 105), but how low is not commented throughout the text and this is left a bit uncommented… could the authors expand on that?*\n\nWe thank the reviewer for suggesting the improvement of the presentation of our paper. By “attains low test error” we mean that the ground truth labeling achieves the lowest generalization error (Eq. 1) and the lowest value of HUME’s objective (Eq. 2) correspondingly for Definition 1 and Definition 2. Indeed, these definitions are key assumptions of HUME which are then validated using correlation plots (Fig. 1 in the main paper and Fig. 1ab in the rebuttal pdf). We will add these clarifications in the future revision of our work to further strengthen the presentation of our work.\n\n>*Could the authors provide a better explanation for the difference between inductive and transductive procedures? Could the authors provide an intuition behind why the results seem to improve more for the transductive than for the inductive procedure?*\n\nEach dataset consists of train $D_{train}$ and test $D_{test}$ splits. Inductive setting corresponds to training HUME only on $D_{train}$ and then evaluating on $D_{test}$. Since HUME is an unsupervised method and does not utilize any labels, we can also evaluate HUME in the transductive setting which corresponds to training HUME on the entire dataset $D = D_{train} \\cup D_{test}$ and evaluating on $D_{test}$. Thus, transductive setting utilizes more data to train HUME expectedly resulting in better performance. We will explain the difference between inductive and transductive settings in the future revision of the paper.\n"}]

Author rebuttal:
We thank the reviewers for their valuable feedback and positive evaluation of our work. We appreciate fruitful suggestions of the reviewers that helped to improve the overall presentation of our work. In the response to the reviewers’ feedback, we have conducted additional experiments shown in the attached pdf and included in the response to reviewers. The attached pdf includes:

* Correlation analysis between HUME’s objective and ground truth labeling on two additional datasets, STL-10 and CIFAR-100-20 (Figure 1). The results show strong correlation ($\rho=0.9$) on the STL-10 dataset and fairly positive correlation ($\rho$=0.5) on the CIFAR-100-20 dataset.
* Analysis of accuracy of reliable samples produced by HUME on two additional datasets, STL-10 and CIFAR-100-20 (Figure 2).  The results show that HUME can produce up to 100 almost perfectly accurate samples per class (>= 99% accuracy) on the STL-10 dataset and up to 100 reliable samples per class (>= 85% accuracy) on the CIFAR-100-20 dataset.
* Evaluation of HUME on the large-scale fine-grained ImageNet-1000k benchmark (Table 1).  The results show that HUME achieves substantial improvements over existing large-scale unsupervised baselines proposed in the literature, outperforming the best baseline by 24% in terms of accuracy.
* Additional baselines constructed by (i) running clustering on top of DINO representations, and (ii) running clustering on top of representations obtained by concatenating DINO and MOCO representations (Table 2). The results show that HUME outperforms these baselines by 18%, 9% and 8% in accuracy on the STL-10, CIFAR-10 and CIFAR-100-20 datasets, respectively. 
* Evaluation of semi-supervised learning method FreeMatch on reliable samples produced by HUME (Table 3). We compare FreeMatch performance on HUME”s reliable samples with FreeMatch performance on ground truth labeling. The results show that FreeMatch with reliable samples performs comparably to FreeMatch with ground truth labeling. 

We provide more details and address reviewers’ comments in the individual response to reviewers. We hope that our detailed response and additional experiments will help to increase reviewers’ confidence.


Meta-review: The reviewers all recommend acceptance. Having looked at the paper, reviews, and rebuttal, we are accepting this paper. The authors are encouraged to improve the final paper version by following reviewer recommendations, especially those raised in J4o2's initial review.
Decision: Accept (spotlight)