CEREAL: Few-Sample Clustering Evaluation
Authors: Nihal V. Nayak
Ethan R. Elenberg
Clemens Rosenbaum
Venue: Submitted to ICLR 2023 (2023)
Keywords: evaluation metrics
clustering
surrogate functions
active learning
semi-supervised learning

Abstract: Evaluating clustering quality with reliable evaluation metrics like normalized mutual information (NMI) requires labeled data that can be expensive to annotate. We focus on the underexplored problem of estimating clustering quality with limited labels. We adapt existing approaches from the few-sample model evaluation literature to actively sub-sample, with a learned surrogate model, the most informative data points for annotation to estimate the evaluation metric. However, we find that their estimation  can be biased and only relies on the labeled data. To that end, we introduce CEREAL, a comprehensive framework for few-sample clustering evaluation that extends active sampling approaches in three key ways. First, we propose novel NMI-based acquisition functions that account for the distinctive properties of clustering and uncertainties from a learned surrogate model. Next, we use ideas from semi-supervised learning and train the surrogate model with both the labeled and unlabeled data. Finally, we pseudo-label the unlabeled data with the surrogate model. We run experiments to estimate NMI in an active sampling pipeline on three datasets across vision and language. Our results show that CEREAL reduces the area under the absolute error curve by up to 57% compared to the best sampling baseline. We perform an extensive ablation study to show that our framework is agnostic to the choice of clustering algorithm and evaluation metric. We also extend CEREAL from clusterwise annotations to pairwise annotations. Overall, CEREAL can efficiently evaluate clustering with limited human annotations. 

CEREAL: FEW-SAMPLE CLUSTERING EVALUATION
Anonymous authors
Paper under double-blind review
ABSTRACT
Evaluating clustering quality with reliable evaluation metries like normalized mu- tual information (NMI) requires labeled data that can be expensive to annotate. We focus on the underexplored problem of estimating clustering quality with limited labels. We adapt existing approaches from the few-sample model evaluation litera- ture to actively sub-sample, with learned surrogate model, the most informative data points for annotation to estimate the evaluation metric. However, we find that their estimation can be biased and only relies on the labeled data. To that end, we introduce CEREAL, comprehensive framework for few-sample clustering evalua- tion that extends active sampling approaches three key ways. First, we propose novel NMI-based acquisition functions that account for the distinetive properties clustering and uncertainties from a learned surrogate model. Next, we use ideas from semi-supervised learning and train the surrogate model with both the labeled and unlabeled data. Finally, we pseudo-label the unlabeled data with the surrogate model. We run experiments three datasets across vision and language. Our results show that CEREAL reduces the area under the absolute error curve by up to 78% compared to the best sampling baseline. We perform an extensive ablation study to show that our framework is agnostic to the choice of clustering algorithm and evaluation metric. We also extend CEREAL from clusterwise annotations to pairwise annotations. Overall, CERFAL can efficiently evaluate clustering with limited human annotations.
estimate NMI in an active sampling pipeline on
INTRODUCTION
Unsupervised clustering algorithms (Jain et al., 1999) partition given dataset into meaningful groups such that similar data points belong to the same cluster. Obtaining high-quality clusterings plays an important role in numerous learning applications like intent induction (Perkins & Yang, 2019), anomaly detection (Liu et al., 2021), and self supervision (Caron et al., 2018). However, evaluating these clusterings can be challenging. Unsupervised evaluation metrics, such as Silhouette Index, often do not correlate well with downstream performance (von Luxburg et al., 2012). On the other hand, supervised evaluation metries such as normalized mutual information (NMI) and adjusted Rand index (ARI) require a labeled reference clustering. This supervised evaluation step introduces costly bottleneck which limits the applicability of clustering for exploratory data analysis. In this work, study an underexplored area of research: estimating the clustering quality with limited annotations.
Existing work on this problem, adapted from few-sample model evaluation, can often perform worse than uniform random sampling (see Section 5). These works use learned surrogate models such as multilayer perceptrons to identify the most informative unlabeled data from the evaluation set. Similar to active learning, they then iteratively rank the next samples to be labeled according to an acquisition function and the surrogate model's predictions. However, many active sampling methods derive acquisition functions tailored to specific classification or regression metric (Sawade et al., 2010; Kossen et al., 2021), which make them inapplicable to clustering. Furthermore, these methods only rely on labeled data to learn the surrogate model and ignore the vast amounts of unlabeled data.
In this paper, we present CEREAL (Cluster Evaluation with REstricted Availability of Labels), a comprehensive framework for few-sample clustering evaluation without any explicit assumptions on the evaluation metric or clustering algorithm (see Figure 1). We propose several improvements to the standard active sampling pipeline. First, we derive acquisition functions based on normalized mutual information, a popular evaluation metric for clustering. The choice of acquisition function depends on whether the clustering algorithm returns cluster assignment (hard clustering) or distribution over

---

Clustering
Teat
Clustering
Reference
Repeat
Pseudo-Labeled Reference Clustering (Y)
Estimate
Evallation
Pseudo-Label
Metric
v(C, Y)
NMI-Based Acquisition Function
Surrogate Mocel
Figure The CERBAL framework evaluates the test clustering with limited annotations for the reference clustering.
clusters (soft clustering). Then, we use semi-supervised learning algorithm to train the surrogate model with both labeled and unlabeled data. Finally, pseudo-label the unlabeled data with the learned surrogate model before estimating the evaluation metric.
Our experiments across multiple real-world datasets, clustering algorithms. and evaluation metrics show that CEREAL accurately and reliably estimates the clustering quality much better than several baselines. Our results show that CEREAL reduces the area under the absolute error curve (AEC) up to 78.8% compared to uniform sampling. In fact, CEREAL reduces the AEC up to 74.7% compared to the best performing active sampling method, which typically produces biased underestimates of NMI. In an extensive ablation study observe that the combination of semi-supervised learning and pseudo- labeling is crucial for optimal performance as each component on own might hurt performance (see Table 1). We also validate the robustness of our framework across multiple clustering algorithms -namely K- K-Means, spectral clustering, and BIRCH to estimate a wide range evaluation metrics namely normalized mutual information (NMI), adjusted mutual information (AMI), and adjusted rand index (ARI). Finally, we show that CEREAL can be extended from clusterwise annotations to pairwise annotations by using the surrogate model to pseudo-label the dataset. Our results with pairwise annotations show that pseudo-labeling can approximate the evaluation metric but requires significantly more annotations than clusterwise annotations to achieve similar estimates.
We summarize our contributions as follows:
We introduce CEREAL, a framework for few-sample clustering evaluation. To the best of knowledge,
the first to investigate the problem of evaluating clustering with a limited labeling budget. Our solution uses a novel combination of active sampling and semi-supervised learning, including
NMI-based acquisition functions.
Our experiments in the active sampling pipeline show that CEREAL almost always achieves the lowest ABC across language and vision datasets. We also show that our framework reli- ably estimates the quality of the clustering across different clustering algorithms, evaluation metrics, and annotation types.
RELATED WORK
Cluster Evaluation The trade-offs associated with different types of clustering evaluation are well-studied in the literature (Rousseeuw, 1987; Rosenberg & Hirschberg, 2007; Vinh al., 2010; Gösgens et al., 2021). Clustering evaluation metrics oftentimes referred to as validation indices either internal external. Internal evaluation metrics gauge the quality of clustering without supervision and instead rely on the geometric properties of the clusters. However, they might not be reliable as they do not account for the downstream task or make clustering specific assumptions (von Luxburg et al., 2012; Gösgens et al., 2021; Mishra et al., 2022). On the other hand, external evaluation metrics require supervision, oftentimes in the form of ground truth annotations. Commonly used external evaluation metrics are adjusted Rand index (Hubert & Arabie, 1985), V-measure (Rosenberg Hirschberg. 2007), and mutual information (Cover & Thomas, 2006) along with its normalized and adjusted variants. We aim to estimate external evaluation metrics for clustering with limited labels for the ground truth or the reference clustering. Recently, Mishra et al. (2022) proposed a framework to seleet the expected best clustering achievable given hyperparameter tuning method and a computation budget. Our work complements theirs by choosing best clustering under a given labeling budget.
2

---

Few-sample Evaluation Few-sample evaluation seeks test model performance with limited access to human annotations (Hutchinson et al., 2022). These approaches rely on different sampling strategies such as stratified sampling (Kumar & Raj. 2018), importance sampling (Sawade et al., 2010; Poms et al., 2021), and active sampling (Kossen et al., 2021). Our work is closely related to few-sample model evaluation but focuses clustering. Often, existing approaches tailor their estimation to the classifier evaluation metric of interest, which make them ill-suited to evaluate clustering (Sawade al., 2010; Kossen al., 2021). While we choose focus on clustering, we do not make further assumptions about the evaluation metrics. Finally, a few approaches have used unlabeled examples to estimate performance of machine learning models (Welinder et al., 2013; Ji et al., 2021). These use Bayesian approach along with unlabeled data to get a better estimate of precision and recall (Welinder al., 2013), or group fairness (Ji al., 2020) of learned models. In our work, we estimate clustering evaluation metric and use the unlabeled data to train the surrogate model. Furthermore, we also propose novel acquisition functions that account for the distinctive properties of clustering and label them proportional to the underlying evaluation metric.
Active Learning Active learning, well-studied area of few-sample learning (Cohn et al., 1996; Settles, 2009; Gal et al., 2017; Kirsch et al., 2019; Ash et al., 2020; 2021). aims to train a model by incremenaally labeling data points until the labeling budget exhausted. Most of these methods differ in their acquisition functions to sub-sample and label data to train the models. We derive new clustering-specific acquisition functions that account for the distinctive properties of clustering (see Section 4). For a more in-depth introduction on active learning, we refer the reader to Settles (2009).
Semi-supervised Learning Semi-supervised learning trains models using limited labeled data alongside large amounts of unlabeled data (Berthelot et al., 2019; Xie et al.. 2020: Sohn et al., 2020). These methods use several strategies such as data augmentation and consistency regularization to effectively use the unlabeled data. In our work we use FixMatch (Sohn et al., 2020), a general-purposs semi-supervised learning method, and labeling and show they are key to the success of our framework. We can also use more comainn-specifn semi-supervised learning algorithm instead of FixMatch in CEREAL.
PRELIMINARIES
Few-sample Cluster Evaluation Given a dataset, the problem of external evaluation metric esti- mates the clustering quality by how much (learned) test clustering differs from another (annotated) reference clustering by comparing the cluster assignments. Assuming that clustering is a function set of clusters KC [k1 k2,,.. kmm then we rewrite cluster evaluation as computing a scalar function between two clusterings: (X'), (2²)) In the faw-sample case, one of the two clusterings, which we assume to be the reference clustering, only partially known. For convenience, we denote:
fei X K. from dataset X' {-1, 22,,.,, ..., .n,
C == (fo(x)\Va : I E X). Y ([y(z)]Va ir xE X).
the test clustering.
the reference clustering.
Yr. = (J((T)VVa: : Xr. CX).
the partially labeled subset of the reference clustering. the subset of the dataset without reference labels.
Xy X X\ Xt.
The problem then becomes estimating v(C, Y) from the partial reference clustering, i.e. computing an estimate i(C, YL) such that Ie(C, Y) o(C, Y,)l is minimized. While there are no formal requirements on X' other than being clusterable, we assume for the rest of this paper that X' a set of vectors.
Normalized Mutual Information Normalized mutual information (NMI) measures the mutual dependence of two random variables with a number in the interval [0. 1]. As outlined in Gösgens et al. (2021), it satisfies several desirable properties; it is easily interpretable. has linear complexity, is symmetric, and monotonically increases with increasing overlap to the reference clustering. In cluster evaluation, treat the test clustering C and the reference clustering Y as random variables
3

---

Algorithm I:
Training algorithm for CEREAL
Input :Seed labeled data points (Zz, YL), unlabeled data points Xy. number of queries n, labeling budget M, acquisition function 4, surrogate model Ta, test clustering C'.
Output: (
Te
train the surrogate model with the seed labeling data
while [Yr| < M do
Yr. Yr, U (TTE Sax Ny, n); sample n data points to label with the acquisition function
Te + ((,,, Yr.) + Lt (Xt); reinitialize and train the semi-supervised surrogate model
Y" + Yz (X()): pseudo-label the unlabeled data points
end
return i(C,Y)
and calculate the NMI(C,Y) follows:
NMI(C;Y) Ever Eeec [or(cu) (Hy Hc) /2
Hy Σ ply) logp(v),
DEY
ICY lcylegg vl p(c, y) log p(c,8)
Hc = Σ p(c) log 'EC
p(y)p(c)
Here, p(c, y) is the empirical joint probability of the test cluster assignment being and the reference cluster assignment being y. p(c) is the marginal of the cluster assignment, p(y) the marginal of the
reference cluster assignment, and H is the entropy. In our work, the goal is to estimate NMI(C, Y) from the labeled subset only, i.e. compute an estimator NMI(C, YL) for the NMI of the full dataset.
4 THE CEREAL FRAMEWORK
In this section, we describe the CEREAL framework for few-sample clustering evaluation. The key idea is to modify standard active sampling pipeline's surrogate function to incorporate concepts from semi-supervised learning.
Surrogate Model
Surrogate models in an active sampling pipeline are used to identify which informative unlabeled data points label next. Typically, the surrogate model To is [K]]-way classifier trained to minimize some loss function L(X2, Yz) in order to approximate the reference model X. An acquisition function then the surrogate model assign score each unlabeled data point. At each iteration a batch of n data points is labeled based on these scores which grows the set Yg. The process repeats until the labeling budget is reached. Finally, the metric is estimated with the final labeled data.
In this work, the surrogate model, trained with a semi-supervised learning algorithm, is used not only to acquire new labels but also pseudo-label the unlabeled data points. The surrogate model To is a [K]-way classifier trained on both labeled and unlabeled data, i.e. L(X,, YL) + Lu (Xy) ). The use of unlabeled data in the surrogate model allows us to use any task-specific semi- sumi-vipeeeieed learning algorithm such as FixMatch (Sohn al., 2020), MixMatch (Berthelot et al., 2019), or Noisy Student (Xie et al., 2020).
Acquisition Functions Most acquisition functions aim to order candidate data points by their predictive uncertainty and/or expected information gain from labeling. Recently, Kossen al. (2021) derived cross entropy acquisition function for active testing, which accounts for uncertainties from both the surrogate model and the test model. However, cross entropy suboptimal for clustering applications because at each iteration it assumes knowledge of the correct mapping between cluster labels from the surrogate model and test clustering. The total number of test clusters and reference clusters need not be the same in general, which exacerbates the problem.
We derive two novel acquisition functions based on NMI that account for the distinctive properties of clustering. NMI accounts for the label assignments of the test clustering and the surrogate model efficiently without searching for a direct mapping between them. Furthermore, in Section 5.1, we find that while estimating the NMI, sampling points proportional to the NMI lead to greater reduction
4

---

in the error. Soft NMI. If the test clustering f outputs distribution over the cluster for given data point 24, then we use the Soft NMI acquisition function:
lov (cs yl ΣΣ So(claz)mo(vlaa) (Hy + Hc) /2 yEY
SNIM 1
Hard NMI. If f outputs cluster assignment for data point 2i, then the Soft NMI acquisition function reduces to the Hard NMI acquisition function:
Lor (fcx)) (Hy + Hc) /2
HHMM: :=
Σ VEY
To(u)=;)
Pseudo-labeling The pseudo-labeling allows us to effectively use the unlabeled data in our evalua- tion metric estimation. We use the cuni-supeeeseed surrogate model pseudo-label, or assign hard label to the unlabeled data, i.e., Y' Yz U (x)). Further, our pseudo-labeling approach does not require any additional thresholds commonly used in semi-supervised learning (Xie et al., 2020). Our experiments show that in many cases, this simple pseudo-labeling step reduces estimation error dramatically (see Section 5.1).
Algorithm We describe CERBAL in active sampling pipeline in Algorithm Given initial set of labeled data points to train the surrogate model, CEREAL iteratively uses the provided acquisition function to determine more samples to be labeled. Once the new samples are labeled, CEREAL retrains the surrogate model and uses the updated surrogate model to label the still unlabeled points. Finally, CERFAL, estimates v (CC, Y) as outlined above.
EXPERIMENTS
In this section, we describe our experiments for few-sample cluster evaluation. First, we compare CEREAL the active sampling baselines and show that we achieve better NMI estimates with fewer samples. Next, we show that our framework is robust to the choice of clustering algorithms and evaluation metrics. Finally, we extend CEREAL pairwise annotation where show that pseudo-labeling the data points with the surrogate allows us to estimate the NMI of clustering. In our active sampling and robustness experiments, we use FixMatch (Sohn al., 2020) our semi-supervised algorithm (see Appendix A for more details).
5.1 ACTIVE SAMPLING EXPERIMENT
Datasets We experiment with four datasets in vision and language, namely, MNIST (LeCun, 1998). CIFAR-10 (Krizhevsky al., 2009), Newsgroup (Joachims, 1996), and arXiv arXiv.org submitters (2022). The MNIST dataset contains images of the digits from 0 to 9. The CIFAR- 10 dataset contains images of animals and objects from 10 classes. The Newsgroup dataset contains texts of news articles from 20 classes. The arXiv dataset consists of 2.7 million abstracts with 20 top-level topics such as computer science, math, statistics, etc. For all datasets, we use the ground truth class labels as the reference clustering Y.
Before clustering the datasets, we compute vector representation for each sample with off-the-shelf pretrained models. For MNIST and CIFAR-I0. 10, pass the images through CLIP (Radford et al., 2021), a pretrained linguaelanguage model, to get image representations. For Newsgroup and arXiv, pass the text through SimCSE (Gao et al., 2021), a pretrained self-supervised model, to get text representations. Then, we reduce the dimensions to 128 with PCA using the FAISS library (Johnson et al., 2019). Finally, in this experiment, from scikit-learn (Buitinck et al., 2013). Since the arXiv dataset is large, we subsample million data points before clustering with K-Means. We set K (5, 10, 15) for MNIST and CIFAR-10, K = (10, 20, 30} for Newsgroup, and K = {15,30 30, 50} clusters.
cluster the representations with K-Means algorithm
Baselines We compare CEREAL with strong active sampling baselines divided into two categories: active learning (MaxEntropy, BALD) and active testing baselines (CrossEntropy). The acquisition functions the active learning baselines account only for the uncertainties or the information gain only from the surrogate model produce the acquisition score. On the other hand, acquisition
5

---

functions in the active testing baselines account for the uncertainties from both the surrogate model and the test clustering to compute the acquisition score. We also consider Soft NMI and Hard NMI as active testing acquisition functions.
MaxEntropy (Shannon, 1948) computes the entropy of the unlabeled data point over clusters with the surrogate model. BALD (Houlsby et al., 2011) assigns higher acquisition scores to data points that maximize the information gain between the surrogate model's 's predictions and its posterior. For
BALD, we use MCDropout (Gal & Ghahramani, 2016) model uncertainty in the predictions. During the acquisition process, we run 10 inference cycles with the surrogate model and average the entropies over the inferences. The CrossEntropy acquisition function, introduced in Kossen al. (2021), chooses points that maximize the cross entropy between the surrogate model and the test model. Here, we measure the eross entropy between the surrogate model and the test clustering fa(AY). As suggested in Farquhar et al. (2021), we convert the scores from the acuqisition function to distribution and then stochastically sample from the distribution to get an unbiased estimate of the evaluation metric.
Model Architecture For these experiments, input dimension and hidden dimension of 128 and a dropout of 0.2 after each layer for the surrogate model. Between each layer of the MLP, apply ReLU nonlinearity (Nair & Hinton, 2010). The classification head is a linear layer with output dimension equal to the number of clusters in the reference clustering.
a 4-layer multilayer perceptron (MLP) with an
Training Details We use PyTorch build our framework (Paszke et al., 2019). All our experiments are performed on a single Tesla T4 GPU with 16GB of memory. For fair comparison with active sampling baselines, we train our surrogate models in CEREAL in the same pipeline. First, we uniformly sample 50 data points, label them, and train the surrogate model on the resulting sample- label tuples. Then, we query 50 data points in each round with the acquisition functions until the labeling budget of 1000 data points is exhausted. We train the surrogate model on the training split with a cross entropy loss for 20 epochs and choose the best model based on the validation split. We optimize the model parameters using Adam (Kingma & Ba, 2015) with batch size of 64 and a learning rate of 0.01 for all the datasets. We use the same pipeline and model architecture for FixMatch with different set hyperparameters and optimization settings. For more training details, see Appendix A.
Evaluation Criteria We want our NMI estimates to be good approximations of true NMI with few samples,i.e. we want to measure the error between our estimated NMI and the true NMI. To measure the error, inspired by the area under the learning curve (Cawley, 201 I), we propose to compute the area under the absolute error curve (AEC) AEC as / MY [NMICC;Y) NMI Y) dl where Yz is the seed labeled data and M is the labeling budget in the active sampling pipeline. Since we acquire data points in batch, we cannot simply add the absolute error and thus use the trapezoidal rule to compute the area under the curve between the two intervals.
Yzl
Results We summarize our results as follows: (1) CEREAL using NMI-based acquisition function
and FixMatch almost always reports the lowest AEC compared to all the methods, (2) using only FixMatch or only pscudo-labeling in the framework can hurt performance, and (3) active sampling methods often perform worse than Random as they often overestimate or underestimate the NMI (see Table 1 and Figure 2).
-Mseb acquisition functions can help reduce the AEC compared active-sampling baselines. As we see in Table 1, CEREAL with Soft NMI or Hard NMI achieves the lowest AEC compared to the existing active sampling baselines. CERFAL with Soft NMI reduces AFC up to 78.8% compared to uniform sampling and up to 74.7% compared to the best performing active sampling method, MaxEntropy. On CIFARIO, 10, we observe that Soft NMI has the lowest ABC suggesting that our NMI based acquisition function can provide significantly accurate estimates.
FixMatch and pseudo-labeling, together, are the most critical components of CEREAL. In Table 1, observe that only using FixMatch in active sampling pipeline or only pseudo-labeling can hurt performance across datasets. In fact, when we compare Soft NMI, Soft NMI + FixMatch, and Soft NMI + Pseudo-labeling, we see that AEC increases on average by 6.4%. But, Soft NMI

---

Method
MNIST 4
CIFAR-JO
Newsgroup
arXiv 4
Random
0.741 0.07
0.549 0.07
1.658 0.13
2.133 0.13
BALD
0.814 0.08
0.723 0.04
2.113 0.14
2,183 0.10
MaxEntropy
1.030 0.03
1.574 0.05
1.116 0.0s
1,544 0.11
CrossEntropy
0.677 0.85
2.055 0.41
1,950 0.07
1,230 0.07
Soft-NMI
0.646 0.96
0.348 0.03
1,625 0.17
2.110 0.14
Hard-NMI
0.759 0.05
0.399 0.05
1.522 0.20
2.085 0.12
Random FixMatch
0.866 0.07
0.504 0.06
1.762
2.075
Soft NM1 FixMatch
0.701 0.08
0.474 0.06
1.646 0.14
2.279 0.10
Hard NMI FixMatch
0.649 0.05
0.431 0.06
1.636 0.14
1,978 0.13
Random + Pseudo- Psbudo-Labeling
1.082 0.11
0.885 0.04
1,818 0.06
1.147 0.06
Soft NMI + Pseudo-Labeling
1.044 0.12
0,820 0.04
1.742 0.09
1.354 0.13
Hard NMI + Pseudo-Labeling
1.030 0.13
0.790 0.03
1.769 0.12
1,296 0.06
CEREAL (Rundom FixMatch Pseudo-Labeling)
0.331 0.02
0.393 0.03
0.729 0.03
0.490 0.02
CEREAL (Soft NMI FixMatch Labulo-Labeling)
0.345 0.03
0.399 0.03
0.707 0.03
0.453 0.02
CEREAL (Hard NMI + FixMatch Eseudo-Labeling
0.311 0.02
0.424 0.02
0.734 0.03
0.456 0.02
Table 1:
Results for the benchmark evaluation comparing CEREAL with active sampling baselines. For each dataset, we report the average under the absolute error curve (AEC) and the standard error across three clusterings and five random seeds. The method with the lowest AEC is in bold and the second lowest AEC is underlined.
Random
BALD
MaxEntropy
Random Pscudd-LLbeling Labeling
CEREAL (Random)
MNIST, NMI: 0.4978
CIFAR1O, NMI: 0.7121
Newsgroup, NMI: 0.4224
arXiv, NMI: 0.3416
0.8
NMI
0.6
0.4
0.2
200
200 Number of Labels
200 Number of Labels
1000
Number of Labels
Number Labels
(a) Comparison of CEREAL (Random) using active learning baselines. We report the average NMI and the standard error across five random seeds.
CrossEntropy
Soft-NMI
Hard-NMI
CEREAL (Soft NMI) Newsgroup, NMI: 0.4224
CEREAL (Hard NMI)
MNIST, NMI: 0.4978
CIFAR10, NMI: 0.7 0.7121
arXiv. NMI: 0,3416
1.0
0.8
NMI
0.6
0.4
0.2
200
200 Number of Labels
200 Number of Labels
Number of Labels
Number Labels
(b) Comparison of CEREAL using NMI-hased acquisition functions with active testing baselines. We report the average NMI the standard error across five random seeds.
Figure 2: Estimation curves function of labels.
with FixMatch and pseudo-labeling reduces the AEC by 46.6% on the MNIST dataset, 56.5% on the Newsgroup, and 78.5% on the arXiv dataset. These trends are similar across the Random and Hard NMI as well. While FixMatch is sufficient to improve performance of NMI acquisition functions + geeud-llbbllnng we believe that any other appropriate supi-supee learning algorithm would lead to similar improvements. Finally, we observe that the choice of acquisition function in CERFAL less important than learning with Match and pseudo-labeling the unlabeled dataset.
Existing active aative-sampling approaches often underestimate the NMI. In Figure 2a, we observe that both MaxEntropy and BALD can often underestimate the NMI which contributes to their AEC. We see that MaxEntropy the Newsgroup dataset has lower ABC compared to the other active sampling approaches but Figure 2a shows that is incredibly biased and tends to underestimate the NMI. In Figure 2b, observe that Enosspn the Newsgroup dataset is severely biased and reports lower NMI. As suggested earlier, CrossEntropy does not account for the mapping between the cluster assignments from the surrogate model and the test clustering. In contrast, we observe that CEREAL
7

---

Random Pseudo-Labeling
CEREAL (Random)
MNIST
CIFAR10
Newsgroup
arXiv
Accuracy %
100
40
20
1000 Number Labels
250
500
750
500 750 1000
Number of Labels
Number of Labels
Number of Labels
Figure 3: Accuracy of surrogate model
(Soft NMI) and CEREAL (Hard NMI) do not suffer from such biases. We also note that the Soft-NMI acquisition function overestimates NMI, which contributes to a lower AEC in the case of CIFAR-10 10.
Accuracy of the Surrogate Models We investigate performance the surrogate model CEREAL used for pseudo-labeling. Figure 3 shows the accuracies of the surrogate model without and with FixMatch on the unlabeled data. We see that FixMatch is significantly better at pseudo-labeling the unlabeled data points. Comparing these with CEREAL in Figure 2a, we see a close relationship with performance of the surrogate model. This suggests that simply using a more sample efficient model can be good way to pseudo-label clusters.
5.2 ROBUSTNESS OF CEREAL
We evaluate the robustness of CEREAL across clustering algorithms and evaluation metrics. Clustering algorithms differ in several ways including their preference to certain data types over others. For instance, K-Means can only cluster flat spherical data whereas spectral clustering can also cluster non-flat structures. The same way, evaluation metrics including NMI can have biases which motivate data science practitioners to evaluate the clustering several metrics (Gösgens et al., 2021).
Setup We experiment with the Newsgroup dataset and choose several popular clustering algorithms and evaluation metrics. We consider the following clustering algorithms: K-Means, spectral clustering. and BIRCH. Spectral clustering uses the eigenvalues of the graph Laplacian to reduce the dimensions of the embeddings before clustering. This transductive clustering algorithm helpful clustering highly non-convex datasets. BIRCH is type of hierarchical clustering algorithm typically useful for large datasets. For the evaluation metrics, we choose normalized mutual information (NMD, adjusted mutual information, and adjusted Rand index (ARI). ARI is pairwise evaluation metric which computes the pairwise similarity between points, i.e. whether the test and reference clusterings agree on whether the points are in the same cluster different clusters, normalized such that near-random test clusterings have scores close to zero. For simplicity, we compare Random and CEREAL (Random) by uniformly sampling and labeling 500 data points and then estimate the evaluation metric. We use the same model architecture as the previous section and choose K {10, 20, 30} for all the clustering algorithms. Then, we measure the absolute error between the estimated metric and the true evaluation metric with the complete dataset,i.e., |b[C, Y) - (C,, Y)
Results Our results in Table 2 show that CEREAL consistently achieves lower error compared to Random. In Table 2a, observe that CEREAL reduces the error up 83% across different clustering algorithms. We also find that in Table 2b, CEREAL decreases the error up to 75% on
Newsgroup
Newagroup
Merhod
K. K-Monns
Spectral
BIRCH
Method
NMI
AMI
ARI
Random
3.36e 02 3.71e
3.12e-02 44023
Random
7.17c-02
1.9%
1.0de 02
CEREAL (Random))
9.42-003 movs 6.3c-03
22044
2.88e-02 2ases
CEREAL (Random)
1.79c-02 za.as
1.8le42
22240
8.53e-03 1av04
(a) Results comparing Random and CEREAL (Ran- dom) across multiple clustering algorithms. We report the absolute error between the true evaluation metric and estimated metric averaged across 3 clusterings for 3 evaluation metrics and 5 random seeds.
(b) Results comparing Random CEREAL (Ran- dom) across multiple evaluation metrics. We report the absolute error between the true evaluation metric and estimated metrie averaged across 3 clusterings from 3 clustering algorithms and random seeds.
Table 2: Robustness of CEREAL across clustering algorithms and evaluation metrics.
8

---

MMST. 0.4970
GEARTO, NMI: 0.7121
Newsgroup, 0.4224
Metrids
Random Trownrdted Powudoiabbiigg
2000 4000
0002 Number Libels
10000
2000
4000
1000
10000
4000
0003
ROOD 10000
Number
Figure 4: Estimation curves as function of pairwise annotations.
different evaluation metrics. In particular, that CEREAL approximate even ARI, pairwise evaluation metric. Overall, our results show that CEREAL is robust across clustering algorithms and evaluation metries.
5.3 EXTENSION TO PAIRWISE ANNOTATIONS
When the number of reference clusters is large, identifying the exact cluster for each data point can be a difficult and time consuming task. Additionally, the full set ground truth clusters may not be known to annotators. This means that human annotator needs to repeatedly decide if data point belongs an existing cluster or a new cluster. Therefore, we extend CEREAL, from clusterwise annotations pairwise annotations, i.e. whether or not two points belong to the same cluster.
Estimating clusterwise evaluation metries such as NMI using only pairwise cluster information presents an additional challenge. We solve this practical issue by integrating CEREAL with L2C (Hsu et al., 2019) to learn a multiclass surrogate model from pairwise annotations Algorithm more details on the L2C framework, see Appendix B. Even without exhaustively labeling all pairs of data points as in Hsu et al. (2019), we show that surrogate models learned with L,2C are accurate enough to use in few-sample evaluation problem.
For
Setup As in previous sections we use MNIST, CIFARIO, and Newsgroup clusterings as our datasets. We uniformly sample 10,000 pairs of annotations in batches of size 1000. Since pairwise annotations for dataset are sparse, a Random acquisition function samples about (K: - 1)x more negative than positive pairs. To improve generalization, during training we balance the samples have an equal number of positive (same cluster) and negative (different cluster) pairs. In Figure 4, the z-axis denotes the number of annotated pairs before balancing the dataset. Here, the surrogate model a lincar classifier trained using Adam with learning rate of 0.01, weight decay of 5 10-4, batch size of 32 for 50 epochs. At each step, we train a surrogate model Ne and apply two pseudo-labeling strategies. Random + Pseudo-Labeling labels the entire dataset. Random Thresholded Pseudo-Labeling only labels the data points with where max(Te (3)z)) >> 0.5.
Results Figure shows that our surrogate model with either pseudo-labeling strategy can be used to approximate the NMI with only pairwise annotations of the reference clustering. But, we see that thresholding with a fixed value can have higher variance in the estimates. Furthermore, our results also show that using weaker annotations comes cost. When compare our results from Figure 2, we can see that CEREAL requires far fewer clusterwise labels to achieve similar NMI estimates.
CONCLUSION
In this paper, we introduced the problem of few-sample clustering evaluation. We derived CEREAL by introducing several improvements to the active sampling pipeline. These improvements consist of new acquisition functions, semi-supervised surrogate model, and pseudo-labeling unlabeled data to improve estimation the evaluation metric.
Our work lays the foundation for future work for few-sample clustering evaluation. Interesting directions include: investigating the use of more powerful few-shot surrogate models in the active learning step (such as BERT (Devlin et al., 2018) for language and Flamingo (Alayrac et al., 2022) for vision) and developing more sophisticated sampling strategies for pairwise annotations to reduce the sample requirements further.

---

REFERENCES
Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, lain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katie Millican, Malcolm Reynolds, et al. Flamingo: a visual language model for few-shot learning. arXiv preprint arXiv:2204. 14198, 2022.
arXiv.org submitters. arxiv dataset, 2022. URL httht:://// /tw::://wwwwwww... www.ka..gle....... ctw. htt.:tpss//www.aaalll.co///////s
4455691.
Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In 8th International Con- ference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https: http//ppperreiieee /
net./ htte:/formmmmi=rryhhhee
Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham M. Kakade. Gone fishing: Neural active learning with fisher embeddings. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https:// openreview net forum?orummomm Sotorrmmid-DDThteteoeo Dinthht
David Berthelot, Nicholas Carlini, lan J. Goodfellow, Nicolas Papernot, Avital Oliver, and Colin Raffel. Mixmatch: A holistic approach to semi-supervised learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 5050-5060 2019. URL https: //tp:::///r/eee http://pooceeeenn.ccee neurips cc hccppappe///11///// h 1cd1 Roc138d0499a00 f 2beee 4ww.e 4bb html.
Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnaud Joly, Brian Holt, and Gaël Varoquaux. API design machine learning software: experiences from the seikit-learn project. In (CCM.PPKD Workshop: Languages for Data Mining and Machine Learning, pp. 122, 2013.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsuper- vised learning of visual features. In Proceedings of the European conference computer vision (ECCV), pp. 132-149, 2018
Gavin Cawley. Baseline methods for active learning. Active Learning and Experimental Design workshop In conjunction with AISTATS 2010, pp. 47-57. JMLR Workshop and Conference Proceedings, 2011.
David Cohn, Zoubin Ghahramani, and Michael Jordan. Active learning with statistical models. Journal of artificial intelligence research, 4:129-145, 1996.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommu- nications and Signal Processing). Wiley-Interscience, USA, 2006. ISBN 0471241954.
Jacob Devlin, Ming-Wad Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, 2018. URL https: hittps://arxtt //tpx//./xxoooooo abs/1810. 04805.
Sebastian Farquhar, Yarin Gal, and Tom Rainforth. On statistical bias active learning: How and when to fix it. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL forum? -ididdijiiyyeppe
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 1050-1059, IMLR.org. org, 2016. URL http: http://ooceeeeeeee ngs ml www.mmrr..rr//eemmmmmmmmmmmmeeee www.ssessvvvs / html.
10

---

Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th Interaational Conference Machine Learning. ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1183-1192. PMLR, 2017. URL http:// /vpeess/v///. v000 /ga 17....a.... html.
proceedings. ngs . ml www.......rss...mmmmmmm.mmmm
Tanyu Gao, Xingcheng Yao, and Danqi Chen. SimCSE: Simple contrastive learning of sen- tence embeddings. In Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, pp. 6894-6910, Online and Punta Cana, Dominican Republic, 2021. Association for Computational Linguistics. doi: 10. 10.186552 00.18653/v1/202 emllp-main.552. URL https: https///acaaatthhoooooo
org/ . in. 552.
Martijn Gösgens, Alexey Tikhonov, and Liudmila Prokhorenkova. Systematic analysis of cluster similarity indices: How to validate validation measures. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 7799-3808. PMLR, 2021. URL http::ttt/// http///ooceeeeneeeeeeeee ngs mlr www.pppess/eee
gosgens21a a. html.
Hongyu Guo, Yongyi Mao, and Richong Zhang. Augmenting data with mixup for sentence classification: An empirical study. ArXiv preprint, abs/1905.08941 2019. URL https:
// llr.iiivorr///..oo.o.oooo....... abs/1905s 08941.
Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning. NIPS Workshop on Bayesian optimization, experimental design and bundits: Theory and applications, 2011.
Yen-Chan Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, and Zsolt Kira. Multi-class clas- sification without multi-class labels. In 7th International Conference on Learning Represen- tations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https:/ /apnnevviww net forum? i==sidd2isskcc.cc
Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2(1):193-218, 1985.
Benton C. Hutchinson, Negar Rostamzadeh, Christina Greer, Katherine Heller, and Vinodkumar Prabhakaran. Evaluation gaps in machine learning practice. 2022 ACM Conference on Fairness, Accountability, and Transparency, 2022.
Anil K Jain, Narasimha Murty, and Patrick Flynn. Data clustering: a review. ACM computing surveys (CSUR), 31(3):264 323, 1999.
Disi Ji, Padhraic Smyth, and Mark Steyvers. Can I trust my fairness metric? assessing fairness with unlabeled data and bayesian inference. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neurul Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https: httpttpp:://pccceeeiiete 2020/ /tt.//////////ee///aa d8 (1l Abst html.
cecuurppscccpppee paper/
Disi Ji, Robert L. Logan, Padhraic Smyth, and Mark Steyvers. Active bayesian assessment of black- box classifiers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7935-7944, 2021.
Thorsten Joachims. A probabilistic analysis of the rocchio algorithm with tfidf for text categorization. Technical report, Carnegie-melll mellon univ pittsburgh pa dept of computer science, 1996.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535-547, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. 2015. URL http: //arxiv. wwwpiiiorrggas///ooo 4121 6980.
11

---

Andreas Kirsch, Joost Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Gamett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 7024-7035, 2019. URL https: https: http::///cccceeeeeeeeeooo newrips wetpiiis..cpppppppee wttpppppe//111///// 11200///ha 9/hash/ 95323660ed2 20022244400022244555550
Abstract html.
Jannik Kossen, Sebastian Farquhar, Yarin Gal, and Tom Rainforth. Active testing: Sample-efficient model evaluation. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International
Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 5753-5763. PMLR, 2021. URL http:
http////////////el.eee /pproceedings.... wml.ediiinnmm.i.......mmmm..mmrm mlr. press vv////v3////////// kossen2 html.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Anurag Kumar and Bhiksha Raj. Classifier risk estimation under limited labeling resources. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 3-15. Springer, 2018.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmistt, 1998.
Hongfu Liu, Jun Li, Yue Wu, and Yun Fu. Clustering with outlier removal. IEEE Transactions on doi: 10. 10.1109/TKDE22219.255533
Knowledge and Data Engineering, 33(6):339-2379, 2021.
Siddhartha Mishra, Nicholas Monath, Michael Boratko, Ariel Kobren, and Andrew McCallum. An evaluative measure of clustering methods incorporating hyperparameter sensitivity. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 7788-7796, 2022.
Vinod Nair and Geoffrey F. Hinton. Rectified linear units improve restricted boltzmann machines. In Johannes Fürnkranz and Thorsten Joachims (eds.), Proceedings of the 27th International Conference Machine Learning (ICML-10), June 21-24, 2010, Haifa, Israel, pp. 807-814 Omnipress, 2010. URL mattts::/icmtt htt.:/cc///ccceceeeeeeeeemeeeeee 2010 pttp:///e/ee.op////peeeres 4324432242 (tmppers/33..dde
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- -eghhperformance deep learning library. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 8024-8035, 2019. URL htttpss:/prroceediigg www.eeiiiinnn.uuiipieeeeeee.ue.e ccc htcppaper/20199 10009//oi 2aa20//hhhh////// hash// Scbca228fee775 212.:ffeee722222a000100022222220 at html.
Hugh Perkins and Yi Yang. Dialog intent induction with deep multi-view clustering. In EMNLP/JJCNLP (1), 2019.
Fait Poms, Vishnu Sarukkai, Ravi Teja Mullapudi, Nimit S Sohoni, William Mark, Deva Ramanan, and Kayvon Fatahalian. Low-shot validation: Active importance sampling for estimating classifier performance on rare categories. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 10705-10714, 2021.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 8748- 8763. PMLR, 2021. URL http: / http:://pppopeeeeeeeeeee proceedings mlr. wtt....eee..v.//// radford21a html.
12

---

Andrew Rosenberg and Julia Hirschberg. V-measure: A conditional entropy- external cluster evaluation measure. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning DEMNLP-CONLLS pp. 410-420, Prague, Czech Republic, 2007. Association for Computational Linguistics. URL hatp::///ccllaathlloooo .rgg D000g/430
Peter Rousseeuw. Silhouettes: graphical aid to the interpretation and validation of cluster analysis. Journal of computational and applied mathematics, 20:53-65 1987.
Christoph Sawade, Niels Landwehr, and Tobias Scheffer. Active estimation of f-measures. In John D. Lafferty, Christopher K. I. Williams, John Shawe- Taylor, Richard S. Zemel, and
Aron Culotta (eds.), Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of meeting held 6-9 December 2010, Vancouver, British Columbia, Canada, pp. 2083-2091. Curran Asso- ciates, Inc., 2010. URL https: / http:::::///ppoceeenggeese neurips Abstract html.
Burr Settles. Active learning literature survey. Computer Sciences Technical Report 1648, University of Siscoosii-Madisonn 2009.
Claude Elwood Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379-443 1948.
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang. Han Zhang, Colin Raffel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiees Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-1 2020, virtual, 2020. URL https: httpttt////rcceeee/ee /pwpceddinoeeeeeoeee/ee neurips.cc. wwwppppppp////e.eeeeeeee 2020/ /tw.aaaaaaaaae/eeaaa 0 (9199944ceeeee wet.eeeeeed.cccocoee6e66e633311. -attt333-bbbattttbcaateee html.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov: Dropout: a simple way to prevent neural networks from overfitting The journal of machine learning research, 15(1):12291195. 2014.
Lichao Sun, Congying Xia, Wenpeng Yin, Tingting Liang, Philip Yu, and Lifang He. Mixup- transformer: Dynamic data augmentation for NLP tasks. In Proceedings of the 28th International Conference on Computational Linguisties, pp. 3436 3440, Barcelona, Spain (Online), December 2020. doi: 18.18653/v 000663//1/222.cooiggg main.305. URL https: //////aaaattllggyeeeeeeeeee wtt.oy/..rg/220000 2020. coling-main. 305.
Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. The Journal Machine Learning Research, 11 11:2837-2854, 2010.
Ulrike von Luxburg, Robert C. Williamson, and Isabelle Guyon. Clustering: Science or art? In Proceedings of ICML Workshop on Unsupervised and Transfer Learning. 2012.
Peter Welinder, Max Welling, and Pietro Perona. A lazy man's 's approach to benchmarking: Semisu- pervised classifier evaluation and recalibration. In 2013 IEEE Conference on Computer Vision and Pattern Recognition, Portland, OR, USA, Jume 23-28, 2013, pp. 3262-3269, IEEE Computer Society, 2013. doi: 10.1 1.11000/CP...013.444 URL https: /oii.iio.////////o// . org/ /ttgg//1.. 10. 1109///RR. 2013 3. 419.
Qizhe Xie, Minh-Thang Luong, Eduard H. Hovy, and Quoc V. Le. Self-training with noisy student improves imagenet classification. In 2020 JEEESCVF Conference on Computer Vision and Puttern Recognition, CVPR 2020, Seattle. WA. USA, June 13-19, 2020, pp. 10684-10695 IEEE, 2020. URL https: www.ooorg/.iii 110. 1109/
doi: 2020. 01070.
Soyoung Yoon, Gyuwan Kim, and Kyumin Park. SSMix: Saliency-based span mixup for text classification. In Findings of the Association for Computational Linguistics: ACL-IICNLP 2021,
13

---

pp. 3225-3234, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/ v1/2021. fee.ll..iiiinsaal.l. 2cl. URL http://///.alaatttoooooooor///// findings-nnnnnnneee acl. 285.
Hongyi Zhang, Moustapha Cissé, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC. Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, net / for um? d
2018. URL
14

---

A FIXMATCH
We describe FixMatch (Sohn et al., 2020), the semi-superivsed learning algorithm used in the experiments in Section 5. This algorithm relies key components: consistency regularization and pseudo-labeling. The consistency regularization assumes that the model produces same output with different perturbations for an input data point. Pseudo-labeling assigns "hard" artificial labels to the unlabeled data with the trained model.
In our work, we train the surrogate model Tee with cross entropy loss that leverages both labeled and unlabeled data. The overall loss function for batch B is
LFM = Lg + Aula
where 1, is the loss on the labeled data, ly is the loss on the unlabeled data, and X is a scalar hyperparameter. The loss over the labeled dataset is defined
1 B BBB
Σ
H (y6, (y)()))
where yb is the reference cluster assignment, To (y(a)))) the distribution of the cluster assignments for the data point To. and H is the cross entropy between the reference cluster assignments and the predictions. The loss on the unlabeled dataset is
1
Lu
B.B Σ
(maxx((90)
2 H (o() (
where μ hyperparameter that controls the size of the unlabeled data relative to the labeled data, is a scalar threshold, max(;;) ( is the probability of the cluster assignment with the highest confidence with weak augmentation like dropout, ds one hot vector with the peak on the highest cluster assignment, and AA is hard augmentation like mixup.
In this work, our input data points are embeddings rather than raw images or data. This means the augmentations - weak and strong have to be datatype agnostic. We consider Dropout (Srivastava al., 2014) as our weak augmentation. Consistent with Appendix D.2 of Sohn et al. (2020), we use mixup (Zhang et al., 2018) as our strong augmentation in place of choose mixup hyperparameter a = 9, and mix random inputs only. While Sohn al. (2020) validates the effectiveness of this "FixMatch Input MixUp" method on CIFAR-10 10, mixup for text classification has been investigated previous work (Guo et al., 2019; Sun et al., 2020; Yoon et al., 2021).
We set the following hyperparameters: B 32, μ = 7, = 0.95, and X 1. We also use a cosine scheduler for the learning rate and set the warmup to 0 epochs. Finally, we train the model with the overall loss LFM using SGD with a learning rate of 0.03 and weight decay of 5 x 10-4 for 1024 epochs.
A.1 COMPUTATIONAL COST
Adding FixMatch to a small surrogate model (applied to the frozen input embeddings) is not expensive. Train time on g4dn.xlarge (NVIDIA T4 16GB, S0.52 per hour) for FixMatch model is 20 sec/100 samples (in our experiments, train time over 102 450 epochs scaled linearly with the number of samples; so it's sec/100 samples, 40 sec/200 samples, etc.). While this dominates overall compute cost of CEREAL (the other pipeline steps are in the sub 5sec range), it is still extremely cost efficient.
B L2C FRAMEWORK
We adapt the L2C framework to a realistic setting where we have limited pairwise annotations. The L2C framework (Hsu et al., 2019) uses only pairwise similarity annotations train multiclass classifier. They treat the multiclass classifier as a hidden variable and optimize the likelihood of the pairwise similarities
fa(x,))) E X'A. 23 E X'} between pairs of X. In limited labeled setting, we have access only Sr. where St. S. Suppose we do not
Consider the set of pairwise similarities S (x, =
15

---

Random Initialization
Imbalanced Initialization
Balanced Initialization
Random Soft-NMI
1.638 0.13
1.899 0.19
1,922 0.17
16255 0.17
1.651 0.07
1,952
Hard-NMI
1.522 0.90
1.740
2.131
Random FixMatch
1. 1.762 0.12
1.660 0,09
1,867
NMI FixMatch
1.646 0.14
1.539 0.15
1.868 0.17
Hard NMI FixMatch
1.636
1,595
1,951
Random LabeligL
1.818
1.919
1,923
aheling
0.oa 1,769
2.166 0.11
0.19
Hard NMI Pscudo-Labeling
2,096
1,948
CERFAL. (Random +FixMatch Psendo-1 Psendo-Laheling) Lahlingg)
0.729
1.090 0.04
0.999
CEREAL (Soft NMI 4FixMatch Pecudo-Labeling)
0.707 0.08
1.077 0.01
1.013 0.07
CEREAL (Hard NMI +FixMatch Pscudo-Labeling)
0.734 0.03
1.127 0.o3
1.054
Table 3: Comparing the different strategies acquire the initial labels in the active sampling pipeline. We report the average area under the absolute error curve (AEC) and the standard error across the clusterings five random seeds. The method with loweest AEC is in bold.
know the number of clusters in the dataset, then we set the classification layer in we to a sufficiently large K. When sty 1 then (x; and (x(z)) will have sharp peak over the same output class. Therefore, we train the multiclass classifier no by optimizing the similarities with a binary cross entropy follows:
Σ St
siy (ogg(T((x:)= + (1 - 51:))) log(1 To(x;)).
Unlike the original formulation of the L2C framework, we have access to a limited number of pairwise annotations. We balance the dataset with an equal number of positive samples and negative samples. Finally, in Figure 4, we see that L2C with limited annotations can learn multiclass classifier.
C COMPARISON TO HUMAN ANNOTATIONS
The cost of human annotations is significantly higher than the cost of GPU hours required to run CEREAL. For instance, consider the arXiv dataset with 2.7 million samples. Suppose we want to manually annotate I million uniform random samples at the cost of $0.05; this would cost $50,000. In practice, we often have multiple annotations for sample, which would increase the cost between $100,000 and $1500000. Further, this would take an enormous amount of time for the annotators. On the other hand, our active sampling experiment for the arXiv dataset takes about I hour on a single GPU which costs about $0.52 per hour. Our algorithm often provides reliable estimates with around 500 samples which reduces the annotation cost to S25. Therefore, for fraction of the cost, CEREAL estimate the quality of the clustering reliably.
D LIMITATIONS
The CEREAL framework has few limitations. Often, when the number of clusters is large, identifying the exact cluster for each data point can be difficult. While we use the pairwise extension of CEREAL to address this issue, it requires significantly more annotations achieve similar NMI estimates.
We also see that while our method is robust across several clustering algorithms and evaluation metrics, the gains are nearly neutral for Adjusted Mutual Information (See Section E.3).
E ADDITIONAL EXPERIMENTS
E. CLASS IMBALANCE
To understand the effect label initialization, we conduct an ablation with different strategies without the surrogate model. We experiment with three label acquisitiion functions: random initialization, imbalanced initialization. and balanced initialization. random initialization, we uniformly sample the data points and label them. In the imbalanced initialization, randomly choose clusters
16

---

Method
MNIST 4
CIFAR-IO
Newxgroup |
arXiv 4
Random
300
200
650
1000
BALD
300
1000
1000
1000
MaxEntropy
400
550
CrossEntropy
250
1000
550
Soft-NMI
200
100
850
1000
Hard-NMI
300
100
500
1000
Random + FixMatch
350
150
800
1000
Soft NMI FixMatch
150
200
700
Hard NM1 + FixMatch
250
150
700
1000
Random + Pscudo-LLaheling
550
250
600
600
Soft NMI Pscudo-l_abeling
500
250
600
700
Hard NMI + Pseudo-Labeling
550
250
650
650
CEREAL (Random FixMatcc Pseulo-Labeling)
150
100
300
200
CEREAL (Soft NMI + FixMatchh + Pseudo-Labeling)
150
100
300
150
CEREAL (Hard NMI + FixMatch + Pseudo-Labeling:
150
100
300
200
Table 4: Number of labeled samples required reach +:0.05 of the true NMI value. A "L" indicates the method does not converge within this target accuracy. We report the median across five random seeds. The method with fewest number of samples in bold.
and choose all the data points from the cluster till the seed labeling budget. Finally, in balanced initialization, we sample proportionally from all the clusters for the seed labels. In all three strategies, after the seed label initialization follow the same Algorithm 1.
Our results in Table show that random initialization, compared to other strategies, achieves the lowest AEC. We also observe the balanced sampling performs slightly better than the imbalanced sampling suggesting that a biased seed label set can hurt NMI estimation.
E.2 SAMPLE COMPLEXITY
Table 4 shows the number of labels necessary to converge within target NMI æ. We set x +0.05 of the true NMI value and calculate the median of the required data rounded to the nearest batch of 50 samples. CEREAL performs equal to or better than all baselines from Section 5.1.
E.3 ROBUSTNESS ACROSS CLUSTERINGS
We evaluate the robustness of CEREAL on different evaluation metries, clustering algorithms, and numbers of clusters on the Newsgroup dataset. We use the same setup as described in Section E.3.
Evaluation Metrics Figure 5 provides lower NMI and ART estimates compared to the Random with limited labeled data. However, we observe that CEREAL might hurt performance AMI estimation. We see this as a potential limitation of our work and requires further investigation (see AppendixD).
Clustering Algorithms We consider the same three clustering algorithms: K-means, Birch, and spectral clustering. Figure 6 shows that our method can reliably provide accurate NMI estimates compared to Random with as little as 200 to 250 labels on the dataset all three types of clusterings.
Number of Clusters Figure 7 shows that CEREAL achieves lower error in NMI estimation compared to Random on two out of the three k (10, 20, 30). We see that when & = 10, CEREAL achieves a higher error compared to Random as it underestimates the performance. On the other hand, when the increases, we see that CEREAL provides precise NMI estimates. This result suggests that CEREAL could benefit when evaluating clusterings with large number of clusters.
17

---

6:25
0.10
6.75
200
1050
600
adc
100e
260
1003
Figure 5: Epmstimation curves for varying clustering evaluation metrics.
cluster_alp .lg krnens
cluster_elg olg spectral
cluster_ab birch
0.30
0.08
ener
0.06
cereal
0.04
0.02
0.00
num con_saaples
num, jasmplleseesssss
num samples
Figure 6: NMI estimation curves for varying clustering algorithms on the Newsgroups dataset.
k
0.12
0.30
0.08
ceneal
200
400
600
800
1000
200
400
600
800
1000
200
400
600
800
1000
samples
cam_ssapless
samplas
Figure 7: NMI estimation curves for varying number of clusters in the K-means test clustering on the Newsgroups dataset.
18


Reviews:
[{"review_id": "hf6DfCRa8d", "reviewer": "Reviewer_W5ci", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a method to evaluate the clustering quality when in semi-supervised contexts where the number of labeled examples is limited. ", "summary_of_the_review": "See the paragraph above.", "strength_and_weaknesses": "The main strength of the paper is the simplicity of the approach. The proposed method (described in Algorithm 1) which consists in iteratively selecting labels to samples and assign pseudo-labels to unlabelled samples is simple to understand.\n\nThe paper contains lots of weaknesses. The first major weakness is the lack of motivation for the proposed method. In what real-world scenario would this evaluation approach be useful to the machine learning community? The evaluation approach might be interesting to the data mining or information retrieval communities but I do not know in what contexts. \n\nThe second major weakness is the way the experiments are performed. The chosen datasets are toy datasets (MNIST, CIFAR-10, Newsgroup datasets) and the models are pretrained (on ImageNet) or via self-supervised learning. It is not surprising to see pseudo-label approaches work well on these datasets since classes are easily separable.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UEP757ohA-", "reviewer": "Reviewer_6PbC", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an evaluation method to estimate the clustering quality with a small number of labeled samples. The samples are selected by two novel acquisition functions.", "summary_of_the_review": "The paper studies a meaningful problem. But the proposed method lacks novelty, a thorough discussion of the core methodology design, and theoretical underpinning.\n", "strength_and_weaknesses": "Strength\n1. This paper studies an interesting and important problem, which is the efficient evaluation for unsupervised methods. \n2. The paper uses adequate experimental results to support the effectiveness of the method. \nWeakness:\n1.The novelty of the paper is limited. The two proposed acquisition functions are simple and straightforward extensions of NMI. \n2. Section 4 which introduces the core methodology is very brief and it is not very clear how the proposed method addresses the clustering evaluation challenges.\n3.The proposed approach is purely intuitive. It is hard to understand how and why it would work in general. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TqX-4Pg-bl", "reviewer": "Reviewer_cxVs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of evaluating the quality of a proposed clustering. The traditional approach (computing normalized mutual information, NMI) requires every sample to have a ground-truth cluster label. The goal of this paper is to approximate NMI with a limited number of ground-truth cluster labels. The proposed approach is to adapt ideas from active learning and semi-supervised learning to the clustering context. The paper performs experiments on 3 datasets (MNIST, CIFAR-10, Newsgroup) and compares a number of baselines against variants of the proposed approach. ", "summary_of_the_review": "This is a well-written, interesting paper that addresses an important gap in the literature. I enjoyed reading it and found it very informative as someone who doesn't do too much with clustering. Still, I have some questions about experimental methodology and significance. If these can be satisfactorily addressed I will be glad to see this paper accepted. \n\nDec 12, 2022 Update: I have revised my rating -- see comment below. ", "strength_and_weaknesses": "# Strengths\n* The paper is well-written and polished. \n* To the best of my knowledge, the proposed method is novel and fills a gap in the literature (evaluating clustering methods with few labels). \n* The ablation studies / comparisons in Table 1 are quite thorough. \n* The proposed method seems to perform well in the scenarios where it has been tested. \n\n# Weaknesses\n* On page 2 there's talk of \"experiments across multiple real-world datasets\" but the paper uses MNIST, CIFAR-10, and Newsgroup, which I wouldn't consider \"real-world\" datasets. I found myself wondering why these datasets were used in the paper? Is the reason because these methods don't scale up well? If so that's fine, but it should be clearly identified as a limitation in the text. \n* This is related to the previous point. As I reader, I had unanswered questions about the computational costs involved here. (1) How many GPU-hours does it take the run this algorithm from start to finish, and how does that scale with dataset size? (2) If we convert those GPU-hours to an amount of money, how does that cost compare the cost of just e.g. labeling the images on Mechanical Turk? The basic question is: \"When is the algorithm worth it?\" If the answer is \"never, at least not with current methods\" that's not a dealbreaker - it just needs to be spelled out clearly in the paper. \n* If I understand correctly, \"ground truth\" is defined to be the k-means results using K={5, 10, 15} for MNIST/CIFAR-10 and K={10, 20, 30} for Newsgroup. Final performance numbers are averaged across these clusterings. How were these values of K chosen? They seem both arbitrary and very important for the final results. \n* This AEC metric is a bit hard to interpret. Is this something being proposed by this paper? I didn't find references to it elsewhere. I think it would be better to compute error relative to the NMI value you're trying to estimate. i.e. are these estimates off by 1%? 10%? 50%? Hard to say from AEC. In addition, AEC also makes it hard to put the results in context because other papers seem to use different metrics. \n* Is the learning rate not tuned? How was it selected? My concern is that by using the same learning rate for all methods, some might be getting \"lucky\" (because that's a good learning rate for them) while others might be getting \"unlucky\" (and would do better with a different learning rate). This would invalidate the claim that CEREAL is better than the competition. \n* The \"robustness\" experiments were conducted on Newsgroup with 500 examples, which happens to be a setting where the proposed method does very well as we see in Figure 1(a). Is this a fair comparison? If not, please highlight in the text that this is cherrypicked.\n\n# Minor Comments\n* The text for the figures could be a little bigger. \n* It would be nice if all of the \"NMI vs. Number of Labels\" figures all had the same y-axis range. \n* I'm curious about the role of the initial embedding - I wonder how much things would change if we used e.g. ImageNet pretraining instead of CLIP.\n* Since we're already using CLIP to embed the images, what if we pseudo-labeled the entire dataset with CLIP? Might that lead to a competitive baseline? \n* Does $\\Phi$ return the actual points selected, or the acquisition function values? There seems to be a bit of ambiguity about this between the text and the algorithm box. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HrXofTdye1d", "reviewer": "Reviewer_Z3Vb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a framework to do a few-sample clustering evaluation. The few-sample clustering evaluation refers to the case that only with a few labeled samples, how to do the evaluation on the clustering quality. The framework proposed follows three steps: 1. an acquisition function with NMI (normalized mutual information) is designed; 2. semi-supervised learning method like FixMatch is used to train the surrogate model, which utilizes labeled data and unlabeled data together 3. pseudo-labeling the unlabeled data with the learned surrogate model before estimating the evaluation metric. ", "summary_of_the_review": "My current decision on the paper is based on the weaknesses mentioned above, and it would be really helpful if the authors could provide further discussions. ", "strength_and_weaknesses": "Strength:\n\n1. The few-sample clustering evaluation is an interesting topic to explore, which also has practical importance. \n2. The paper is well-written and easy to follow. \n3. The proposed framework seems novel and achieves sound results. The acquisition function with NMI is newly proposed in the paper.\n\nWeakness:\n\n1. How to incorporate FixMatch in training the surrogate model is not clear. In FixMatch, there is a branch of strong augmentation on the input image x. How does this part work, specifically the strong-weak data augmentation branches, as the input of the surrogate model is a feature vector? \n\n2. The initialization of labeled data is uniformly sampling 50 data points, which doesn't consider the class balance in ground-truth labels. The random sampling could largely be class imbalanced which would affect the training of the surrogate model and consequently affect the final results. It would be helpful if the evaluations were separated into a class-balanced setting and a class-imbalanced setting. \n\n3. The effectiveness and robustness of the method are not fully evaluated. In table 1, Soft-NMI achieves the best result on CIFAR-10, better than utilizing FixMatch + Pseudo-labeling. Although the method achieves the best result on MNIST by quite a large margin.  on a more complicated CIFAR-10 dataset (same size, same number of classes), there is no advantage of utilizing FixMatch + Pseudo-labelling. Meanwhile, using FixMatch has the large risk of introducing wrong pseudo-labels for those unlabeled data and the training from scratch is always time-consuming, which would be emphasized as the dataset carries larger scope. This brings the question that: is it worth introducing the FixMatch+pseudo-labeling on larger evaluation datasets with more classes and complicated data distribution? Currently even on CIFAR-10, there is no guarantee that FixMatch or semi-supervised learning in this framework would benefit. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject