Novel Class Discovery under Unreliable Sampling
Authors: Haoang Chi
Wenjing Yang
Feng Liu
Long Lan
Tongliang Liu
Tao Qin
Bo Han
Venue: Submitted to ICLR 2023 (2023)

Abstract: When sampling data of specific classes (i.e., known classes) for a scientific task, collectors may encounter unknown classes (i.e., novel classes). Since these novel classes might be valuable for future research, collectors will also sample them and assign them to several clusters with the help of known-class data. This assigning process is also known as novel class discovery (NCD). However, sampling errors are common in practice and may make the NCD process unreliable. To tackle this problem, this paper introduces a new and more realistic setting, where collectors may misidentify known classes and even confuse known classes with novel classes - we name it NCD under unreliable sampling (NUSA). We find that NUSA will empirically degrade existing NCD methods if taking no care of sampling errors. To handle NUSA, we propose an effective solution, named hidden-prototype-based discovery network (HPDN). HPDN first trains a deep network to fully fit the wrongly sampled data, then applies the relatively clean hidden representations yielded by this network into a novel mini-batch K-means algorithm, which further prevents them overfitting to residual errors by detaching noisy supervision timely. Experiments demonstrate that, under NUSA, HPDN significantly outperforms competitive baselines (e.g., 6% more than the best baseline on CIFAR-10) and keeps robust even encountering serious sampling errors.

Under review as a conference paper at ICLR 2023
NOVEL CLASS DISCOVERY UNDER UNRELIABLE SAMPLING
Anonymous authors Paper under double-blind review
ABSTRACT
When sampling data of specific classes (i.e., known classes) for a scientific task, collectors may encounter unknown classes (i.e., novel classes). Since these novel classes might be valuable for future research, collectors will also sample them and assign them to several clusters with the help of known-class data. This assigning process is also known novel class discovery (NCD). However, sampling errors are common in practice and may make the NCD process unreliable. To tackle this problem, this paper introduces new and more realistic setting, where collectors may misidentify known classes and even confuse known classes with novel classes name it NCD under unreliable sampling (NUSA). We find that NUSA will empirically degrade existing NCD methods if taking no care of sampling errors. To handle NUSA, we propose an effective solution, named hidden--prootyye-baaeee discovery network (HPDN). HPDN first trains a deep network to fully fit the wrongly sampled data, then applies the relatively clean hidden representations yielded by this network into a novel bati- K-means algorithm, which further prevents them overfitting to residual errors by detaching noisy supervision timely. Experiments demonstrate that, under NUSA, HPDN significantly outperforms competitive baselines (e.g., 6% more than the best baseline on CIFAR-10) 10) and keeps robust even encountering serious sampling errors.
INTRODUCTION
Data, algorithms, and computing power create the boom in the field of artificial intelligence, especially the supervised learning with many powerful deep models (Deng et al., 2009; Krizhevsky et al., 2012 22; Simonyan & Zisserman, 2015). Although these deep models can accurately identify or cluster the classes appeared in the training set (i.e., known/seen classes), they do not have reliable extrapolating ability in front of novel classes (i.e., unseen classes). For young children, after seeing some common vehicles (e.g., cars and bicycles), they can easily distinguish (cluster) the unseen but similar ones (e.g.. trains and steamships) based on previous experience. This fact motivates researchers to formulate novel problem called novel class discovery (NCD) (Han et al., 2020; 2019; Hsu et al., 2018; 2019; Zhao & Han, 2021; Zhong et al., 2021a;b), aiming to accurately cluster novel classes using labeled known-class data and unlabeled novel-class data.
Existing work (Chi al., 2022) demystifies the underlying assumptions of NCD, then define NCD strictly from the perspective of sampling, making NCD problem theoretically solvable. Specifically, given a sampling task (i.e., collecting known-class data), the known-class and novel-class data are sampled in the same scenario, but the novel-class data are sampled passingly, and experts cannot identify them. Since the same scenario indicates that two groups have similar high-level semantic features, employing knowledge of known classes to assist the clustering of novel classes is meaningful.
However, for professional and difficult sampling tasks, the experts may wrongly identify known classes (i.e., internal errors), and even confuse the known classes with novel classes (i.e., external errors). A direct example is to sample different varieties of privet, a type of shrubs. If experts are not very proficient, they may wrongly identify ligustrum vicaryi and ligustrum quihoui (internal errors), since they look very similar. Furthermore, they may confuse ligustrum vicaryi and kerria japonica propose new
(i.e., external errors), since they both appear to be red. Motivated by this scenario, and challenging problem called NCD under unreliable sampling (NUSA), where we try to discover novel classes under both internal and external sampling errors, as shown in Figure 1.

---

Under review as a conference paper at ICLR 2023
Bear
Lion
Bear
Lion
Novel
Novel
classss
classes
Wolf
Tigen
Wolf
Tiger
(a) Novel class discovery (NCD).
(b) NCD under unreliable sampling (NUSA).
Figure 1: Novel class discovery (NCD, (a)) is formulated by a sampling process (green arrows). When collectors sample the data of required classes (i.e., bear, lion, wolf, and tiger) in a scenario, they may encounter novel classes (i.e., squirrel and hare) that are unfamiliar, and they had better also sample them for future research. Then, assigning them to several clusters with the help of known-class data known as NCD. However, collectors possibly make mistakes in practice, which is named as NCD under unreliable sampling (NUSA, (b)). Here we consider two cases, where they misidentify the known classes (i.e., internal errors, shown in blue boxes) and even confuse known classes with novel classes (i.e., external errors, shown in yellow boxes).
The most direct solution to NUSA is the existing NCD methods (Fini et al., 2021; Han et al., 2020; 2019; Zhong et al., 2021a), and the results are shown in the left one of Figure 2. Clearly, NUSA empirically degrades the four representative NCD methods, and previous methods cannot handle NUSA well. Moreover, the label-noise learning methods (Han et al., 2018; Li et al., 2020) can be employed correct the labels' of all the sampled data first, and then these data and revised labels will be applied into the existing NCD methods to solve NUSA, which can be regarded as a two-step solution NUSA. However, existing label-noise learning methods cannot fully eliminate noises, and experimental results (Table 1) show that residual errors still weaken NCD methods. Based on these empirical results, the two types of sampling errors substantially invalidate both NCD methods and the above two-step methods.
To address the sampling errors in NUSA, we propose the hidden--roootyye-busee discovery network (HPDN). In terms of supervision, the sampled data with errors can be treated as data with label noises. Li al. (2021a) pointed out that if an architecture "suits" one task, training with noisy supervisions can induce useful hidden representations. Inspired by this conclusion, HPDN first trains a deep network (initialized by SimCLR (Chen et al., 2020)) to fully fit the wrongly sampled data. This network can yield relatively clean hidden representations for novel-class data (Li et al., 2021a). However, the right one of Figure 2 indicates the residual errors in hidden representations still degrade the existing NCD methods. This is caused by the strong memory of deep networks (Zhang et al., 2021), leading to the accumulation of residual noisy supervision information in training procedure.
To avoid further errors accumulation in the representation, unlike existing NCD methods, at clustering stage, we detach the noisy supervision information in time. Then, we employ K-means (MacQueen al., 1967), an unsupervised clustering algorithm. Naive K-means uses all data representations at time and is sensitive to initial centers. However, given many data representations, proper initialization hard to choose, and it may be negatively affected by residual errors existed in representations, and furthermore many iterations are required. Thus, we propose the mini-batch K-means with memories of clustering centers (i.e., prototypes) to discover novel classes using hidden representations. Mini- batches are easier to be initialized with K-means++ (Arthur & Vassilvitskii, 2006) due to their smaller sample complexity. After obtaining centers of each batch, we take their matched average value (i.e., prototypes) to initialize each batch in next epoch, taking care of the whole dataset. In this way, prototypes will gradually converge to a stable state as the final clustering centers.
To verify the effectivenss of HPDN, we perform experiments CIFAR-100 and ImageNet. Experimental results show that HPDN outperforms existing baselines (c.g.. 6% more than the best baseline on CIFAR-10) and is very robust to sampling errors in NCD (Figure 4), which confirms the effectiveness of HPDN.
three benchmarks: 100
'The novel classes currently considered one class.
2

---

Under review as a conference paper at ICLR 2023
Left figure: Four SOTA NCD methods will fail as the sampling enror rate increases (from 10% to 60%). Right figure: The residual sampling errors in hidden representations will accumulate in the training procedure of existing NCD methods (taking RS (Hln et al., 2020) and NCL (Zhong et al., 2021a) CIFAR-10 under 40% error rate as an example), due the strong memory of deep networks (Zhang et al., 2021). This leads to the ACC dropping quickly at later stage.
62.
NCL
20.
10
26
Sampling rate
26
46
90
253
Epoch
Figure 2: Failures of SOTA NCD methods when encountering unreliable sampling.
2 RELATED WORK
Novel Class Discovery. NCD is relatively new problem proposed in recent years, aiming to discover novel classes (i.e., assign them to several clusters) by making use of similar but different known classes. The first two works that proposed NCD and tried to solve it were Kl-DDivegence-buvee contrastive loss (KCL) (Hsu et al., 2018) and meta classification likelihood (MCL) (Hsu et al., 2019), which employed feature extractors to predict pairwise similarity of each novel-class data pair. Han et al. (2019) proposed the deep transfer clustering (DTC) to first learn data embedding with metric learning labeled data, then to employ the deep embedded clustering method (Xie et al., 2016) to cluster the novel-class data. To further extract information from data embedding, they proposed to use the ranking statistics (RS) yield the pairwise similarity and use self-supervised learning to boost feature extraction (Han et al., 2020; 2021).
Recently, OpenMix (Zhong et al., 2021b) was proposed mix known-class and novel-class data to learn a joint label distribution, benefiting to find their finer relations. Then neighborhood contrastive learning (NCL) (Zhong et al., 2021a) was proposed generate better discriminative representations. Fini et al. (2021) used pseudo-labels in combination with ground-truth labels in a UNified Objective function (UNO) that enabled better cooperation and less interference without self self--upervised learning. Zhao & Han (2021) proposed a two branch method focused on local and global information, and used mutual knowledge distillation to promote information exchange and agreement.
Another work (Chi et al., 2022) demystify the assumption of NCD and formulated NCD with sampling process. They argued that the novel classes and known classes should have similar high-level semantic meanings. Based on this assumption, they proved that NCD can be theoretical addressed and linked NCD to meta-learning that served as the solution in their paper.
Label-Noise Learning. Label-noise learning is to train effective model with corrupted labels. Some works (Li et al., 202 Liu & Tao, 2016; Yao et al., 2020) estimated noise transition matrix to recover ground-trute truth labels. Based on the trick that small-loss data can be viewed as clean ones, Han et al. (2018) 8) and Li et al. (2020) tried to filter clean data. Besides, Ren et al. (2018) used meta-learning on clean labeled data boost sample weight and transition matrix.
Deep Clustering. Deep clustering aims to identify classes in an unsupervised way based on deep neural networks. Van Gansbeke al. (2020) proposed to use self-supervised learning to obtain features as a priori in a learnable approach. Zhan et al. (2020) proposed an effective joint clustering and feature learning paradigm via decomposing feature clustering and integrating the process into iterations of network update. Yang et al. (2020) proposed powerful adversarial attack algorithm to learn small perturbation which can fool the clustering layers but not impact the deep embedding.
NCD UNDER UNRELIABLE SAMPLING
In this section, first review the definition of NCD, and then formulate new and more realistic problem called NCD under unreliable sampling (NUSA), and show that the existing NCD methods will fail solve NUSA at last.
Definition 1 (Novel Class Discovery). In a sampling process, given target label set I (Le., known classes), can collect known-class data D) D (ar), H and also unlabeled novel-class
3

---

Under review as a conference paper at ICLR 2023
li=1 with label set I", where y, E I. and I contain C' and C classes". Moreover, I' and I" have similar high-level semantic meaning (Chi et al., 2022) but I' nI" 2. The aim of NCD is to learn a clustering model for novel classes using Delean and Delan'
data D D'lean {<=
Remark 2. C is always assumed to be prior knowledge in NCD literature. In practice, however, if C unknown, an alternative to use heuristic algorithms (e.g., Elbow method (Thorndike, 1953), Silhouette score (Rousseeuw, 1987)) to estimate it.
Sampling Errors. In practice, sampling errors are common especially in professional fields, making NCD process unreliable. In this paper, we consider two important cases of sampling errors. One is misidentifying the known classes (i.e., the blue boxes in Figure 1(b),, named internal emro: Definition 3 (Internal Sampling Error). Given a known-clas label set I' and a collected known-class dataset D {(0), (t) ) we say D contains internal sampling errors if these is an such that Dio Vio, where yio I'th is the ground-truth label of z....
In addition, another case is confusing known classes and novel classes (i.e., the yellow boxes in Figure 1(b)), named external error:
Definition 4 (External Sampling Error). Given a known-class label set I', a collected known-class dataset D' = {(a), Vo and a collected novel-class dataset D = ] we say there are external sampling errors between D and D if 1) there exists an σt whose ground-truth label Y: E " or 2) there exists an क. whose ground-truth label ys E II, where I is the novel-class label set that is unknown in advance.
Note that, since known classes and novel classes have similar high-level semantic features, if collectors make mistakes when sampling known classes, they will probably confuse some specific known classes and novel classes. Namely, the above two types of sampling error often simultaneously occur when facing professional and difficult sampling tasks.
Problem Setup of NUSA. Based on both kinds of sampling errors, we can formulate a more realistic problem called NCD) under unreliable sampling (NUSA) as follows.
Definition 5 (NUSA). Given I' and I defined in Definition 1, a sampling process, we can collect known-class data D {@ē), Je)
N ~ X and also unlabeled novel-class data D = { ~ X where Yi E I!. The aim of NUSA is to learn a clustering model for novel classes by using D and D" where D contains internal sampling errors (Definition 3) and there are external sampling errors between D and D" (Definition 4).
NUSA Degrades Existing NCD Methods. As mentioned earlier, sampling errors may make NCD process unreliable. To verify this claim, we employ four existing NCD methods (i.e., DTC (Han al., 2019), RS (Han al., 2020), NCL (Zhong et al., 2021a), UNO (Fini al., 202 to solve NUSA, shown in the left one of Figure 2. We find that the clustering accuracy (ACC) sharply drops as the sampling error rate (please refer to Section 5) increases from 10% to 60%. Therefore, sampling errors negatively affect the performance of NCD methods. To case the negative effects caused by sampling errors, we propose a hidden- errors and keep good clustering performance in NUSA. We also give NUSA theoretical analysis and a learning upper bound in Appendix E.
prototype- hidden-prototype based discovery network (HPDN), to resist sampling
BASED DISCOVERY NETWORK
The core challenge of NCD is obtain good representations of novel-class data. However, for NUSA, these representations may be negatively affected by sampling errors. Thus, the keys to address NUSA obtain relatively clean representations and avoid overfitting residual sampling errors.
To tackle the sampling errors and accurately separate novel-class data, we propose an effective framework HPDN (Figure 3), which able resist both internal error and external error mentioned in Definition 3 and 4. In Section 4.1, we train a deep network to fully fit the sampled data and try to yield clean data representations from hidden layers. In Section 4.2, we propose mini-batch prototypical K-means algorithm, which further prevents clustering model overfitting to residual errors. Detailed method and its motivation are introduced in the following.
cC" is assumed to he prior knowledge (Zhong et al., 2021b)
4

---

Under review as a conference paper at ICLR 2023
HPDN contains two modules. 1) Obtaining clean hidden representations of novel-class data (i.c., the top half of figure). After initialized by SimCLR (Chen et al., 2020), a deep network f is firstly trained with reweighted known and novel class data, viewing all the novel classes as one class, i.e. class C' + 1. Then, proper hidden layer is used to yield the representations of novel-class data. 2) Clustering these representations with mini- bati-bacch prototypical K K-means (i.e., the bottom half of figure). We divide a dataset into multiple mani-batches, and then cluster each batch by classical K K-means. After obtaining the clustering centers of each mini-batch, we calculate their prototypes to serve as initial clustering centers of each mini-hatch in the next epoch. Moreover, to avoids oscillating around the local minimum, current prototype memorizes the previous ones control the learning rate.
Repersentations
X
Lapors
Layors
Outputs
sampling
Norch
Barch 2 BaraN 2o Batkh
K-meens
K K-meste
X-mesrt
K-meste
Contrrs
Centers
Cenbers
Contory
Prototy pes
Figure 3: Framework of based discovery network (HPDD).
4.1 ROBUST HIDDEN REPRESENTATION
Based on the discussion above, we will train a deep network to obtain relatively clean representations that not seriously affected by sampling errors. Given DJ and T" defined in Definition 5, we first initialize a deep network by SimCLR (Chen et al., 2020) without any supervision. We find that the sampled data with errors can be viewed as data with label noises from the perspective of supervision. According to (Li et al., 2021a), if an architecture "suits" one task, training with noisy labels can induce useful hidden representation. Thus, we temporarily view all the novel classes as the class C + 1 and generate Hu {(x"" C 1) x. E D"). Then, we train a deep network f X + [0, 1] (C*++1) to fully fit D U D". As the data size of class C* + 1 is more than others, we reweight each data according to the data amount of each class in standard cross-entropy loss to alleviate data imbalance, defined as,
D U D Ng. Tg. (C + 1)
{1 Vi 0z) -,,, ey log log(f(z;)²), By.
where (xt, y:) D. D'D ey, denotes 1 x (C) + 1) vector with 1 in the y--th coordinate and 0's elsewhere and fy denotes the parameters of the deep network f. Rly denotes the data amount of class yi, and denotes the number of elements in a set.
After the training procedure, ff can almost fully fit D U D (i.e., classification accuracy is more than 99% empirically), indicating that f has overfitted the sampling errors. Based the conclusion of (Li et al., 2021a) mentioned above, we try to employ proper hidden layers of f to yield good representations for novel-class data. As deep network, f can be decomposed as f = fn o fn-1o..... fi, where fa denotes the z-th layer in the deep network f. Without loss of generality, we assume that the most clean representations are yielded by the z-th layer, i.e., $>(x")) := [=(J=-1(--- (xx))) Vaz" E D", < z < n. The choice of is discussed in Section 5. Although s (xx) is enough good compared with 1h,, (x"), it still contains residual sampling errors and causes continuous error accumulation in the training procedure of existing NCD methods (right one of Figure 2). To address this issue, we propose the batihbach prototypical K-means, detaching the noisy supervision in time and dividing dataset into multiple batches for better initialization and less iterations.
4.2 MINI-BATCH PROTOTYPICAL K-MEANS
Existing NCD methods use various kinds of supervision to help cluster data, e.g., pairwise similarity (Han et al., 2020; Zhong et al., 202 a;; Chi et al., 2022) and pseudo-label (Fini et al., 2021). These supervisions are obtained using data representations and thereby negatively affected by sampling errors for NUSA. Due to strong memory of deep networks (Zhang et al., 2021), the errors in supervision will continuously accumulate in the training procedure and invalidate existing NCD methods (Figure 2). Thus, we detach noisy supervision in time and employ fully unsupervised method, K-means (MacQueen et al., 1967). For naive K-means, all the data representations
5

---

Under review as a conference paper at ICLR 2023
required time. We known K-means is very sensitive to initial centers (Arthur & Vassilvitskii, 2006). Selecting proper initial centers from all the representations contained residual errors hard. Thus propose the mini-batch prototypical K-means, which divides dataset into multiple batches to cluster respectively and takes the matched average centers (i.e., prototypes) as the initial centers of each batch in next epoch.
In detail, given unlabeled novel-class data D and batch size B, we partition D" into [| batches, i.e., D DU [ID=I/B] where [-] denotes the round up function. Through partition, mini-batch has smaller sample complexity so that easier initialize well (Canas al., 2012). For each mini-batch, e.g.. Dy. we firstly cluster DJ by K-means, whose centers are initialized by K-means++ (Arthur & Vassilvitskii,, 2006). Then, K-means output the clustering centers of Dj (i.e.,
{c )== and the assignments of each data. However, the clustering centers of all the mini-batches very likely be disordered, e.g., the first center in Batch and the first center in Batch do represent the same category. Thus, we use the Hungarian algorithm (Kuhn, 1955) to align the centers of all the
and compute their prototype of the 0-th epoch defined follows,
110 Σ
+ [ID*I/B]
i=1,..., C".
Remark 6. Note that there is extreme where there may be missing categories in some mini- batchs First of all, clustering data into all classes in a mini-batel will not make our algorithm crushed, but it indeed will introduce shuffle novel-class data before dividing them in each updating step to alleviate this issue.
errors in the optimization procedure. In method,
The prototype {c. fc.'1CC" Ji=1 takes care of the entire D by memorizing the centers of each batch. To enforce each batch always consistent, we use the prototype {c, (c.."C"" that we just obtained as the initial centers of each mini-batch prototype (i.e., the first term of equation 3) is very small empirically, indicating that the prototype converges to a stable state as the final clustering centers of novel-class data.
the next epoch. Through tuning. variation of L2- of the
Moreover, to avoid oscillating around the local minimum in the iteration procedure, we let the current prototype memorize the previous prototypes to control the learning rate. In detail, when this algorithm enters into the epoch t, we obtain the prototype fc Jim " For epoch + 1, we have
[D B
3
1+,,
Σ
H+1 111-B11 B)c
D
where i 11.....C. C and is a hyper-paramenn used to control the learning rate. Obviously, the larger 99 indicates the larger learning rate. The choose of B3 is detailed analyzed in Section 5. Therefore, the prototype of epoch f. + 1, c 1+,," memorizes the information of all the previous prototypes.
EXPERIMENTS
In this section, we conduct extensive experiments to verify the effectiveness of HPDN on NUSA, involving 3 benchmark datasets and 12 baselines.
Following (Zhong et al., 2021a), we evaluate our method on three important benchmark datasets, including CIFAR-10 (Krizhevsky et al., 2009), CIFAR-100 (Krizhevsky et al., 2009), and ImageNet (Deng et al., 2009). We report the results averaged over 3 runs on CIFAR-10, CIFAR-100. For ImageNet, following (Han et al., 2020), we report the results averaged over 3 different label sets of novel-class data. The detailed strategy for partitioning known and novel classes is in Appendix A.
Datasets.
Simulate sampling errors. Since the datasets
correct originally, to corrupt them manually to simulate the sampling errors through a transition matrix Q e [o, 1[0** (C0+++"(+++++"))) where Qi P(ğ = jly = i) is the probability that wrong label flipped from ground-truth label y. Then, we give the precise definition of transition matrix:
choose
need

---

Under review as a conference paper at ICLR 2023
Table 1: Experimental results on HPDN and other baselines. We report the stCddadd deviation of ACC. All experiments are performed with sampling error rate of 40% and cross rate 50%. Bold values represent the highest average ACC in each column. We report the results averaged over 3 runs on CIFAR-(10,100) For ImageNet, following (Han et al., 2020), we report the results averaged over 3 different label sets of novel-class data. Results of all the methods trained for 100 epochs.
Method
CIFAR-10
CIFAR-100
ImageNet
Average
Existing NCD methods
DTC (Han et al., 2019)
28.51% 1.03%
.03%
20.90%
27.32%
26.58%
RS (Han et al., 2020)
34.60%
21.28% 81%
29.10%
28.30%
NCL (Zhong ct al., 2021a)
33.76%+40.66%
23.84%::0.65 6.66%
33.06%
30.22%
UNO (Fini al., 2021)
37.93% +:2.47%
26.11
32.56%
32.20%
Combine NCD methods with Co-tcaching (Han al., 2018)
DTC Co-teaching
46,28% +..33%
31.92%:10.7995
38.76%
38.97%
RS Co-teaching
46.17%: 140%
34.08%:422. 10%
36.31%
38.85%
NCL Co-teaching
18.33%%1100577
35.74%
43.29%
42.45%
UNO + Co-teaching
52.18% 858
37.31 17.31%:13.,145
46.13%
45.21%
Combine NCD methods with DivideMix (Li et al., 2020)
DTC + DivideMix
45.03% 1. 1.97%
33.74% 1.94%
37. 17.68%
38.82%
RS DivideMix
47.52%++0.78%
(.69%%2.0079
40.44%
39.55%
NCL DivideMix
51.56% .66%
36.07%=t0.7558
46.51%
44.71%
UNO DivideMix
50.10%:+2.449 4.9%%
35.93%:-1.88% 1.8%%
46.27%
44.10%
HPDN (Ours)
63.18%+2.00
37.96%
53.60%
51.58%
where p denotes the sampling error rate and 7 denotes the cross rate. Specifically, given instance to be sampled, / represents the prob- ability that its category is wrongly identified. Furthermore, given a fixed represents the probability that an known-class (resp. novel- class) instance is wrongly identified as a novel- class (resp. known-class) instance. Based on Definition 3 and 4, given the above transition matrix, the internal error rate is p(1 -T) r) and the external error rate is pt.
1 p ((1-)
p(--)
C
1
C1-1
((I-T)
1- p
p(1
Note that, although the internal (resp. external) error rates evenly assigned to known classes (resp. novel classes) in Q, this is not the only way to assign both errors between known classes and novel classes. Since this is the first work to consider such hard problem, would like to focus on this simple transition matrix at the current stage and leave more difficult transition matrices (e.g.. instance-dependent transition matrices (Xia al., 2020)) to future work.
Baselines. NUSA is a new problem and there no straightforward solution to NUSA, thus we use related NCD methods and corresponding two-step methods baselines. Related NCD methods include DTC (Han et al., 2019), RS (Han et al., 2020), NCL (Zhong et al., a021a) and UNO (Fini et al., 2021). Simple reviews about these methods are in Section 2. Two-step methods are sequentially combining label-noise learning methods and NCD methods. In detail, we firstly use label-noise learning methods, e.g., Co-teaching (Han et al., 2018) and DivideMix (Li et al., 2020), to correct the labels of known-class data and detect known (resp. novel) class data that are sampled as novel (resp. known) classes. Then we combine four NCD methods and two label-noise learning methods to form eight two-steps baselines whose abbreviations shown in Table 5 (Appendix A).
Evaluation metric. For a clustering problem, we use the average clustering accurucy (ACC) to evaluate the performance of clustering, which defined as max
oE L N EN ( = o(y:), where Y: and y/ denote the ground-truths and assigned indices. L is the set of mappings from indices to ground-truths. We adopt the Hungarian algorithm (Kuhn, 1955) to find the optimal mapping and then obtain the final ACC with it. We also more metrics (i.e., homogeneity, completeness, and v measure) to evaluate NUSA methods in Appendix D. To evaluate how the number of novel classes affects the NUSA methods, perform additional experiments shown in Appendix C.
7

---

Under review as a conference paper at ICLR 2023
ACC (%)
40
20
20
0
p=200
p-20%
pm40%
5750%
p-60%
p072
p-30%
p=40%
5m50%
p-60%
Sampling error rale
Sampling emorr rate
(a) Fixed cross rate T = 30%.
(b) Fixed cross rate T = 50%.
Figure 4: Experimental amalysis about the robustness of HPDN under serious sampling errors. We take CIFAR-10 with the cross rates of 30% (a) and 50% (b) as an example. The sampling error rate and cross rate are introduced in Section 5. With the sampling error rate increasing from 20% to 60%, the lengths of corresponding columns are almost equal, indicating that HPDN robust enough serious sampling errors in NUSA.
Implementation details. The details about network structures and hyperparameters are in Ap- pendix G.
Comparison baselines. We compare HPDN with four existing NCD methods and eight two-step baselines as mentioned above. Both RS (Han et al., 2020) and NCL (Zhong et al., 2021a) need a model that is pretrained with superviid learning on all the data and then is finetuned by supervised learning known-class data to output the features of novel-class data. To make fair comparison, we use the self-supervised pretrained models provided by RS and NCL.
From Table find that HPDN significantly outperforms the baselines on all three datasets. For existing NCD methods, the ACCs tend to decrease at a later stage (Figure 2), because they are easy overfit the sampling errors. From the results of two-step baselines, they substantially outperform NCD methods, indicating label-noise learning methods can effectively eliminate the negative effects of sampling errors. However, errors cannot be completely eliminated especially when error rate is large (e.g., 2 20%), and residual eтrors will accumulate in training procedure and further degrade NCD methods. Thus, the strategy of detaching noisy supervision timely to avoid overfitting in HPDN is really effective. Another important phenomenon is that the performance of HPDN on CIFAR- 1-000 not very good. This is because the data size of each class small (i.e., 100 data per class) can they are too fine-grained and HPDN cannot well address this hard situation. In addtion, we show and analyze the results of HPDN and eight baselines under lower error rate (i.e., 20%) in Appendix B.
Ablation study. In this subsection, evaluate the effectiveness of each major component of HPDN in Table 2. we replace the hidden layer (i.c., the fourth block of ResNet-18 in our work) with the last layer to yield representations, the ACC will drop more than 15% and 20% under sampling error rates of 20% and 40% respectively. This demonstrates that the hidden layers are not affected too much by sampling errors (Li et al., 2021a). If eliminate the process of tuning prototypes, HPDN will degrade into the naive K-means, causing the low ACC (drops more than 10%) with serious oscillation. If we eliminate / in equation 3 (i.e., set 1), the prototypes will oscillate around the optimal solution for many iterations, thus fail to converge to it.
Verify the robustness of HPDN under serious errors. In this subsection, we would like verify the robustness of HPDN under data with serious sampling errors. Therefore, we show a histogram compare the ACCs under the sampling errors rate of (20%. 30%, 40%. 50%, 60%) } and the cross rate of (30%, 50%). taking CIFAR-10 as an example.
Comparing Figure with Figure 2, as the sampling error rate increases, the performance degradation of HPDN is negligible compared with other baselines. Thus, these experimental results verify the robustness of HPDN under serious sampling errors in NUSA.
Analysis about the choice of B. In equation 3, we use the hyper-parameter 3 to control the learning rate of prototypes. To make its updating stabler and faster, we empirically explore the choices of initial B (Figure 5). We choose the initial 3 as (0.01. 0.05, 0.10. 0.15, 0.20, 0.25, 0.30, 0.50} to observe the change of ACC. We find that larger 3 may lead HPDN to be unstable and cause the performance degradation. Too small 3 (e.g., 0.01) will make the convergence speed of HPDN too slow, requiring more than 100 iterations, and make HPDN hard to be optimal. Thus, we choose 0.05 the initial value based above empirical evaluation.
Impact of batch sizes on mini-batch prototypical K-means. For clustering stage HPDN, divide dataset into multiple mini-batches. Taking CIFAR-10 example, evaluate
8

---

Under review as a conference paper at ICLR 2023
Table 2: Ahlation study of HPDN, taking CIFAR-10 example.
We choose the sampling error rates of 20% and 40% respectively, with the cross rate of 50% fixed. HR: hidden representation, Pro: mini-batch prototypical K-mcans, 3:: the hyper- parameter used to control learning rate equa- tion 3, SSL: self-supervised learning initializa- tion. Bold values represent the highest average ACC in each column.
Method
p 0.2
0.4
HPDN w/o HR
51.06%++3.20%%
42.25%%
HPDN w/o Pro
58.05%=00733%
57.73%=11.554
HPDN w/o B
60.71%==3.622
53,90% 11000===1811 1.81%
HPDN w/o SSL
61.71%:10.77%
56.46%-10.599
HPDN
69.42% 11.93%9993
63.18% 111.:.1..066 2.06%
Table Results of HPDN under different batch sizes, taking CIFAR-10 and p 40% an example.
Batch size
64
128
256
512
1024
all 57.33%
HPDN
63.24% 22.2%%
63.18% 1.00%%
60.42% 1.73%
64.78% 12.51
68.57%118.
Take CIFAR-10 with p = 40% and T = 30% as an example. (a) HPDN is lit- tle sensitive to initial. Smaller 3 is more stable. 33 (b) The fourth block of ResNet can yield best representations. "B" de- notes the block and "FF" denotes the fully- connected layer.
200 Inital value
Different hisden layers
(a) Initial value of B.
(b) Different hidden layers.
Figure 5: Analysis about the initial value of / and hidden layers.
how batch size impacts the clustering performance empirically. We choose the batch size as (64, 128, 256, 512, 1024) to observe the change of ACC. In addition, we use the data repre- sentations at once to perform clustering stage comparison. Results is shown in Table 3. Firsts, we find mini-batch prototypical K-means substantially improves the clustering performance. Then, the ACCs under different batch sizes change little (almost within standard deviation) so that this indicates that batch size has little impact on HPDN. However, HPDN under smaller batch size requires more iterations, thus the convergence speed is slower. Moreover, HPDN under larger batch size requires more GPU memory and too large batch size will cause performance decreasing. To trade off, we choose 128 as the batch size in this work.
Impact of different hidden layers on HPDN. HPDN uses data representations yielded by hidden layers of deep networks, which are relatively clean compared with the representations of final layer. However, the quality of representations yielded by different hidden layers is also very different. We choose the representations yielded by 5 types of hidden layers (i.e., four blocks of ResNet and the following fully- colnecconnected layer) to perform clustering, and the results are shown in Figure 5. Obviously, the 4th block of ResNet can yield the best representations, which is the same as et al. (2021a). The ~ 3 blocks of ResNet cannot learn effective high-level features that are useful to clustering and the last fulle-connected layer is seriously degraded by sampling errors.
CONCLUSION
Considering that sampling errors are common in real scenario of novel class discovery (NCD), this paper introduces a more realistic and more challenging problem: NCD under unreliable sampling (NUSA). However, existing NCD methods cannot handle NUSA well as the errors. To address this novel problem, we propose an effective method called biotden-rrototppe-uueee (HPDN). HPDN contains two modules: one is to obtain clean hidden- representations for novel- class data and another is to alternately cluster each mini-batches then aggragate them, detaching noisy supervision in time. We compare HPDN with 4 representative NCD methods and 8 competitive baselines on three benchmark datasets (CIFAR-10. 10, CIFAR- 100 and ImageNet). Empirical results demonstrate that HPDN can find better clustering centers for novel-class data compared to the 12 baselines. Especially, HPDN is robust to sampling errors and still performs well when facing serious sampling errors, which enables new road to discover novel classes in some professional fields.
discovery network

---

Under review as a conference paper at ICLR 2023
7 REPRODUCIBILITY STATEMENT
In this section, we briefly introduce how to reproduce our algorithm by yourself. Our experiments are performed Python 3.6.13, PyTorch 1.7.1, CUDA 11.2, and Tesla A100 GPUs. The datasets that we use this paper are obtained from their official websites.
The main framework of our algorithm can be implemented according to the Alg. 1 with PyTorch. The implementation details can be found in the following.
Obtain Hidden Representations. For a fair comparison with existing methods, employ the ResNet-8//esNet550 (He et al., 2016) as the backbones of DAAA--0,CTTAAR-000//maaa
The backbone is initialized with SimCLR (Chen et al., 2020) for 300 epochs with the same training strategy as (Chen et al., 2020). Known-class data and novel-class data are randomly sampled from D' and D whose batch size is set to 256/1024 for [CIFAR-IN 10, CIFAR-100) //maagNett. We use SGD optimizer with initial learning rate 0.1 momentum 0.9, and weigh decay 1e 4. In addition, the learning rate decays 10 times after each 40 epochs. We pretrain the backbone for 100/150 epochs for [CIFAR-10, CATAR--100///mmee// Then, we choose the outputs of the fourth block of ResNet with average pooling the hidden representations.
Mini-batch prototypical K-means. The batch size is set to 128 for all three datasets. We perform the clustering step for 100 epochs for all three datasets. For hyper-parameter 3 in equation 3, is initialized by 0.05 and set 0.05 D.5epoch//20 in the training procedure, where "//" denotes the exactly divisible operation. We will further analyze the choice of / in Section
REFERENCES
David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. Technical report, Stanford, 2006.
Guillermo Canas, Tomaso Poggio, and Lorenzo Rosasco. Learning manifolds with k-means and k-flats. In Advances Neural Information Processing Systems, 2012.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In ICML, 2020.
Haoang Chi, Feng Liu, Bo Han, Wenjing Yang, Long Lan, Tongliang Liu, Gang Niu, Mingyuan Zhou, and Masashi Sugiyama. Meta discovery: Learning discover novel classes given very limited data. In ICLR, 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. Imagenet: A large-scale hierarchical image database. In CVPR, 2009.
Enrico Fini, Enver Sangineto, Stéphane Lathuilière, Zhun Zhong, Moin Nabi, and Elisa Ricci. A unified objective for novel class discovery. In ICCV, 2021.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor W. Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In NeurIPS, 2018
Kai Han, Andrea Vedaldi, and Andrew Zisserman. Learning discover novel visual categories via deep transfer clustering. In ICCV, 2019.
Kai Han, Sylvestre-Alvise Rebuffi, Sébastien Ehrhardt, Andrea Vedaldi, and Andrew Zisserman. Automatically discovering and learning new visual categories with ranking statistics. ICLR, 2020.
Kai Han, Sylvestre-Alvise Rebuffi, Sebastien Ehrhardt, Andrea Vedaldi, and Andrew Zisserman. Autonovel: Automatically discovering and learning novel visual categories. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
10

---

Under review as a conference paper at ICLR 2023
Yen-Chang Hsu, Zhaoyang Lv, and Zsolt Kira. Learning to cluster in order to transfer across domains and tasks. In ICLR, 2018.
Yen-Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, and Zsolt Kira. Multi-class classification without multi-class labels. In ICLR, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolu- tional neural networks. NeurlPS, 2012.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
Jingling Li, Mozhi Zhang, Keyulu Xu, John Dickerson, and Jimmy Ba. How does a neural network's architecture impact its robustness noisy labels? NeurIPS, 2021a.
Junnan Li, Richard Socher, and Steven C. Hoi. Dividemix: Learning with noisy labels as semi-supervised learning. In ICLR, 2020.
Xuefeng Li, Tongliang Liu, Bo Han, Gang Niu, and Masashi Sugiyama. Provably end-to-end label-noise learning without anchor points. In ICML, 2021b.
T. Liu and D. Tao. Classification with noisy labels by importance reweighting, IEEE Transactions
Pattern Analysis and Machine Intelligence, 38(3)447-461, 2016.
James MacQueen et al. Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statisties and probability, 1967.
Mengye Ren, Wenyuan Zeng. Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In ICML, 2018.
Andrew Rosenberg and Julia Hirschberg. V-measure: A conditional entropy- based external cluster evaluation measure. In EMNLP-CoNLLA 2007.
Peter Rousseeuw. Silhouettes: graphical aid the interpretation and validation of cluster analysis. Journal of computational and applied mathematics, 20:53-65, 1987.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.
Robert L Thorndike. Who belongs in the family. In Psychometrika, 1953.
Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, Marc Proesmans, and Luc Van Gool. Scan: Learning to classify images without labels. In ECCV, 2020.
Brendan van Rooyen and Robert C. Williamson. A theory of learning with corrupted labels. Journal of Machine Learning Research, 18(228):1-50, 2018.
Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang, Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards instance-dependent label noise. In NeurlPS, 2020.
Junyuan Xie, Ross B. Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In ICML, 2016.
Xu Yang, Cheng Deng. Kun Wei, Junchi Yan, and Wei Liu. Adversarial learning for robust deep clustering. NeurlPS, 2020.
Yu Yao, Tongliang Liu, Bo Han, Mingming Gong, Jiankang Deng, Gang Niu, and Masashi Sugiyama. Dual T: reducing estimation error for transition matrix label-noise learning. In NeurIPS, 2020.
Xiaohang Zhan, Jiahao Xie, Ziwei Liu, Yew-Soon Ong. and Chen Change Loy. Online deep clustering for unsupervised representation leaming. In CVPR, 2020.
11

---

Under review as a conference paper at ICLR 2023
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. Communications of the ACM, 2021.
Tong Zhang, Information-theorrtic upper and lower bounds for statistical estimation. IEEE Transac- tions on Information Theory, 52(4):137--1321, 2006.
Bingchen Zhao and Kai Han. Novel visual category discovery with dual ranking statistics and mutual knowledge distillation. NeurIPS, 2021.
Zhun Zhong, Enrico Fini, Subhankar Roy, Zhiming Luo, Elisa Ricci, and Nicu Sebe. Neighborhood contrastive learning for novel class discovery. In CVPR, 2021a.
Zhun Zhong, Linchao Zhu, Zhiming Luo, Shaozi Li, Yi Yang, and Nicu Sebe. Openmix: Reviving known knowledge for discovering novel visual categories in open world. In CVPR, 2021b.
12

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Hiideen-prooottpp--aeedd Discovery Network (HPDN)
Input: deep network f = fn fn-10 fi, known-class data D' {(z), ú - novel-class data D {æ: It=1, learning rate n, batch size B3, network parameters 0y, z that using to extract representations, the maximum number of epochs T, hyper-parameter B;
Na
Initialize fy and 0;
2: Label all the x² D the class C* + and generate H" {(x", C2 + +1) = E D"
#phase one: extract robust hidden representations.
while < T do
for each mini-hatch C D' U D
3: Compute L(D;0y) = B (aw)eD f(x, v; according equation 1; % Compute the average loss
4: Update Of =0 -0,-~No,L(D.00
% Update parameters of f
end
end
#phase two: mini-batch prototypical K-means. while
do
for each mini-batch D C f=(D") == (=(")))(=))) D") do
Initialize clustering centers {c"") Ji=1 using K-means++ if otherwise using ""=i
Cluster DJ with K-means algorithm and update clustering centers (cht1.) (c end
8: Update ct 1+1,, according to equation 3 and set 1 = t 1;
% Update prototypes and
end
Output: clustering centers "
A PARTITION WAY OF THREE BENCHMARKS
As key assumption in NCD, known classes and novel classes have similar high-level semantic features (Chi et al., 2022). Therefore, following existing works (Hsu et al., 2019; Han et al., 2019; Zhao & Han, 2021), we partition a dataset into two parts according to classes, where one part serves as the known-class group and the other one serves as the novel-class group. It is worth noting that there overlaps between known classes and novel classes, and the number of novel classes is assumed to be prior knowledge. The detailed way of partition can be seen in Table
The influences of partition NUSA (and NCD) methods are mainly in two aspects: 1) How similar the semantic features of known and unknown classes are; 2) How fine-grained the novel classes are. For the first aspect, the known-class data and novel-class data should have similar semantie features. If not, this setting will become cross-domain NUSA (and NCD), which is beyond our current research topic. Specifically, for CIFAR-10, they are more similar, while for ImageNet, they are less similar. For the second aspect. the novel classes of CIFAR- 10 are dog, frog, horse, horse, truck, which are relatively coarse-graing grainedd, and the novel classes CIFAR- 100 are bicycle, bus, motorcycle, pickup truck, train,maple oak, palm, pine, willow, and etc., which are more fine-grained Overall, our experimental setup takes various situations of NUSA (and NCD) into account.
In addition, we evaluate how the number of novel classes, an important factor in clustering problem, matters in NUSA. Therefore, we test the performances HPDN and baseline methods on NUSA with different numbers of novel classes, taking CIFAR-100 the number of known classes as 80 like before, and we choose the numbers of novel classes as (20,10,5), respectively. They are the 81-100 classes, 81-90 classes, and 81-85 classes in CIFAR-100, respectively.
example. In detail, we choose
Table 4: Partition way of three datasets.
Table 5: Abbreviations two-step baselines.
Dataset
#Known class
#Novel class
DTC
RS
NCL
UNO
CIFAR-10
5
5
Co-teaching
C+D
C+R
C+N
C+U
CIFAR-IOU 100
80
20
DivideMix
D+D
D+R
DAN
D+U
ImageNet
882
13

---

Under review as a conference paper at ICLR 2023
Table 6: Evaluate the impact of different numbers of novel classes NUSA. Taking CIFAR-100 an example, we choose the numbers of novel classes as 5, 10, and 20, respectively. All experiments are performed with the sampling error rate of 40% and the cross rate of 50%. Bold values represent the highest average ACC in each column. We report the results averaged over 3 runs.
Number of novel classes
5
20
Existing NCD methods
DTC (Han al., 2019)
26.72%
24.75%::0..3%%
23.90%f1.777
(Han al., 2020)
4..67%
23.04%:::1.449
21.28%
NCL (Zhong et al., 2021a)
27.83% 4..74%
32.70%:++..89%
UNO (Fini et al., 2021)
2.225%
33.59%
26.1
1.83%
Combine NCD methods with Co-teaching (Han et al., 2018)
DTC + Co-teaching
42.64% 10.49%
34.35%111.169
31.92%:10.795
RS Co-teaching
56.81% 2...5%
39.51%
34.08%12.
NCL Co-teaching
48.38% 1 1.97% 60.72%%+22.50%
40.35%-11..339
35.74%-11.5190
UNO + Co-tcaching
46.26 +2.39%
37.31 1113311399999
Combine NCD methods with DivideMix (Li et al., 2020)
DTC+ DivideMix
39.04%10.885% 50.27% 45.69% +.253%%
33.31%:f1.225
33.74%=1..49%
RS DivideMix
35.18%:1:1.3
30.69%=2,0775
NCL DivideMix
39.83%%-4-2.37%
36.07%.10..5%
UNO DivideMix
60.89%
42.09%%:t2..67%
35.93% 1.88%
HPDN (Ours)
64.40 :1133%
45.14%::1.7779
37.96%=1222
B RESULTS OF HPDN UNDER LOWER ERROR RATE
In Table 8, we show the results of HPDN and baselines with noise rate 20% and cross rate of 50%. We can find that HPDN almost outperforms all the baselines on three datasets, indicating that HPDN still works effectively under lower sampling error rate. However, for CIFAR-100. The number of test data of each class CIFAR-10 is relatively few (i.e., each class has 100 data). HPDN relies on good initialization of clustering centers. When few data meets sampling errors, the initialization task will be hard for HPDN. We will further optimize the initialization process of HPDN to make it more robust.
C IMPACT OF THE NUMBER OF NOVEL CLASSES ON NUSA
In this section, we evaluate how the numbers of novel classes affect the NUSA methods on CIFAR- 100. Note that the clustering accuracy (ACC) that commonly used as the metric in NCD/NUSA and other clustering-related problems does not take the number of novel classes into consideration. Thus, we specifically design experiments to evaluate the effecttiveness of HPDN with regard to different numbers of novel classes.
We choose the number of known classes as 80 like previous works (Han et al., 2019; 2020), and we choose the numbers of novel classes as 20, 10, and 5, respectively. We report the ACCs of HPDN and all the baselines with different numbers of novel classes on CIFAR-100 in Table 6. We can find that the number of novel classes is crucial factor for the performances of NUSA methods. All of these methods perform better when the novel classes are fewer. We can also find that HPDN outperforms baseline methods almost for every number of novel classes, except for 10. However, their gap is still within the error range. This mainly results from the relatively good robustness of UNO (Fini et al., 2021).
D EVALUATE NUSA METHODS WITH MORE METRICS
To evaluate the NUSA methods more comprehensively and accurately, we employ another three metrics, homogeneity, completeness, and v y_measure (Rosenberg & Hirschberg, 2007), to evaluate the HPDN and the baseline methods. A clustering result satisfies homogeneity if all of its clusters contain only data points which are members of a single class. A clustering result satisfies completeness all the data points that members of given class are elements of the same cluster. V-measure
14

---

Under review as a conference paper at ICLR 2023
Table 7: Evaluate NUSA methods with more metrics. Taking CIFAR-10 example, three clustering metrics that are based on normalized conditional entropy to measure the NUSA methods, ie.. homogeneity, completeness, and v_ m_masuree respectively. All experiments are performed with the sampling enror rate of 40% and the cross rate of 50%. Bold values represent the highest average ACC in each column.
Metrics
Homogeneity
Completeness
V measure
Existing NCD methods
DTC (Han et al., 2019)
0.0563
0.0613
0.0587
(Han et al., 2020)
0.0506
0.1597
0.0769
NCL (Zhong et al., 2021a)
0.1769
0,1785
0.1777
UNO (Fini ct al., 2021)
0.1618
0.1653
0.1635
Combine NCD methods with Co-teaching (Han et al., 2018)
DTC + Co-teaching
0.2479
0.2527
0,2503
RS Co-tcaching
0.3139
0.3392
0.3261
NCL + Co-teaching
0.3552
0.3807
0.3675
UNO + Co-teaching
0.3871
0.4006
0.3937
Combine NCD methods with DivideMix (Li et al., 2020)
DTC + DivideMix
0,2619
0.2778
0.2696
RS DivideMix
0,3406
0,3955
0,3660
NCL DivideMix
0.3797
0.4026
0.3908
UNO DivideMix
0.4133
0.4310
0.4220
HPDN (Ours)
0.4742
0.4859
0,4800
is the harmonic average of homogeneity and completeness. These three metrics are based the normalized conditional entropy, which measure the clustering performance in a different view from ACC and are commonly used in clustering problems. Constrained by space, we only report the results of HPDN and the baseline methods regarding these three metrics on CIFAR-10, which are shown in Table 7.
We can easily find that our method consistently outperforms the baseline methods with regard to these three normalized conditional entropy-based metries. For almost all the methods, the homogeneity is slightly smaller than the completeness, indicating that there exist two or more classes are assign to the same cluster except the wrongly assigned data points. Thus, existing methods and our HPDN need to further improve the ability of clustering more fine-grained novel classes.
E THEORETICAL ANALYSIS OF NUSA
At beginning, we recall the definitions of NCD and NUSA.
Definition (NCD). In a sampling process, given a target label set I. (i.e., known-class label set), we can collect known-class data D) Di = [( ) ~ X and also unlabeled novel-class data Da [x ~ X with label set I", where yi E I! I and I" contain C and C classes respectively. Moreover, I and I have similar high-level semantic meaning (Chi et al., 2022) but I'II" Z. The aim of NCD is learn a clustering model for novel classes using D dlean and D clean
For more realistic scenario, collectors may make mistakes in sampling tasks especially for profes- sional fields, named NCD under unreliable sampling (NUSA).
Definition 8 (NUSA). Given It and T defined in Definition in sampling process, we can collect known-class data D ((ā), } ~ X and also unlabeled novel-class data D { N ~ X", where ys E I! The aim of NUSA is to learn a clustering model for novel classes by using D and D" where D contains internal sampling errors (Definition 3) and there are external sampling errors between D and D (Definition 4).
For general NCD problem. existing work (Chi et al., 2022) pointed that NCD can be theoretically solvable with two key conditions: (A) transformation set of X (denoted as IT²) and transformation set
15

---

Under review as a conference paper at ICLR 2023
of X (denoted I are good enough to make their high-level semantic features totally separable; (B) II' IIT * Ø. For NUSA, however, the sampling errors may mislead the training process of transformations. that the corresponding high-level semantic features invalid empirically verified in Figure 2. In detail, we denote Px1 and xx as the distributions X and X respectively, and the distributions IP x and x= corrupted by sampling errors are defined as,
xx== 6 + 6Pxx, xx. = (1 6x)) + P,,:
where dj (resp. 8.) indicates that proportion 6j (resp. 6,)) of known (resp. novel) class data are incorrectly sampled. Thus, given data sampled from P yx and Pxx,, if the learned transformations sets II and II still satisfy condition (A), NUSA also can be theoretically solved.
For next analysis, we model the sampling errors with transition (van Rooyen & Williamson, 2018). Given sample spaces X' and X, transition from P1 E P(X) to P3 P(λ') is a linear map T: (P()) + P(2). X and & are finite, transition and external errors may appear at the same time, thus we can jointly model them through transition. Given random variables X and X with sampling errors, they can be represented as,
just a matrix. For NUSA, internal errors
Xx = Q(Px:) Px- Q(Pxx),
where Q is the transition from ground-trute truth distribution to actual distribution with sampling errors. Fxx (resp. P Pxx) represents the probability distribution of X (resp. X". As aim is eliminate the negative effects of sampling errors, we hope the transition Q could be invertible.
Definition 9 (Reconstructible transition (van Rooyen & Williamson, 2018)). A transition E T(X1, X2) is reconstructible if'T has left inverse; that is there exists transition R E T(X2, such that R = 1x))), where ((X, denotes the set of all distributions on sample space XT.
Thus, the left inverse of T is its reconstruction. For general case, we can always take the Moore- Penrose pseudo inverse of T, R = (T*T)-17"* as the reconstruction, where T is the dual operator T. T itself is invertible, the reconstruction T' is R 7
Our aim is to learn good transformation set 11' (resp. 11th) satisfying conditions (A) and (B) with X and X", such that the transformations in ITo (resp. ITe) can yield high-level semantic features of detail, given proper loss function (: Y. x F + R. and our objective is to find f F such that f can minimize
samples drawn from X (resp. X²) to be totally separable.
B(g" """* lly", (()())())))) (z)))
sup
D Px
where F is the hypothesis space, and D is the novel-class data sampled from Px'. f(D) represents the hypothesis trained on D (i.e., data with sampling errors), and obtained with the following objective,
arg min ((x,)) f())..
JeF
However, as contains sampling errors, directly training f on D using standard loss function does not make sense. As mentioned in (van Rooyen & Williamson, 2018), we corrected loss to eliminate the negative effects of sampling errors. As the sample spaces are finite here, expectation of one random variable function on one distribution can be viewed inner product of them in Hilbert space. By properties of adjoint operator and definition of reconstruction, we have
the corruption
Ezf -=f=<P,t >=< R T(P), T(P) R (f) >= ET R*)))
where <.,'> denotes the inner product.
Theorem 10 (van Rooyen & Williamson (2018)). For all reconstructible transition T and loss function & D F R, the corruption corrected loss CR : D x - 1. is defined as,
ER(:ff) = R*( Yf F.
Then for all distribution P. we have
Ep ED-ro
16

---

Under review as a conference paper at ICLR 2023
Proof. This theorem can be directly derived according to the above discussion.
In detail, we define the class probability distribution of a data point (x, () that is outputted by the last layer of deep network as ((x) RC, where f(z) arg max (a) and y is the corrupted supervision information. With the reconstructible transition T, there exists
8, = - Σ P(Y :|Y j)P((Y 5) T T; 5.
Through the reconstructibility of T, we can directly derive 5 = )- which links the noisy supervision and ground-trute -ruth in the view of data representations. This result is consistent with Theorem 10. Next, we equivalently define the loss function with regard to the class probability distribution, i.e., ((6(x). y) = {((()) y) f(arg max 8((xr),)) y). Then we can derive the following theorem to show how to obtain clean data representations under noisy supervision. Theorem 11. Let I arg min ((c.,)>pl(([()) v)] with f arg max 8, and L k-Lipschitz.
fEF
For any f arg max d, learned with noisy supervision, have
R(F) & R(f)) + 3-1 Epll((z) - (x)lla.
where =(z)= = T 8(x) and 8" (z) (x).
Proof.
R(f) R(f)) =2((((/.1--0(0110))))--000000000 ((0)))
S Eplk
- (r1)
Eylk (((TT)"(((()))) (x)))]a))
Thus, we have
R(J) - R(f)) = R()) R(F")
EB,l- I(TT))
8 ex)
Eplh: ( (=))
E,k ||(T [1ō(x) (x())
= II(TT)-+ E, ()(r((())))))))))){())) (x)
Theorem 11 tells us that if the reconstructible transition T is known, the regret risk of the model trained with noisy supervision is bounded by k ||(TT) 1 0(x) - 8 (z)lla. This error bound indicates that if the model fits noisy data very well, i.e., the term (z)))(()) 8 (x) /2 very small, and then the regret risk R(f) R(f") will also be very small. Thus, the reconstructible transition help to obtain clean data representations under noisy supervision.
Based on Theorem 10 and Theorem 11, we can change our learning objective from equation 5 to
arg min E ((2.)))PP P En(ū, fx))). fEF
In this work, the sampling errors that consider class-dependes and can be simulated with the following transition matrix,
P
C
or
C
pr
p(1-)
C
Q
1 p
p(1-7)
C9-1
p(l-)
0
17

---

Under review as a conference paper at ICLR 2023
introduced in Section 5 in detail. It is easy verify the determinant of Q is nonzero, indicating that Q is invertible. That is to say, the transition in NUSA is reconstructible, and there exists Ln = (Q- (C) as the corrected version of L.
According to above discussion and the PAC-Bayes bound (Zhang, 2006), we have the following bound of learning with sampling errors (van Rooyen & Williamson, 2018).
Theorem 12. For reconstructible transition T. algorithms f : DD F, distributions I Pxi, Px", Px = x()x) and P 8 T(Pxx)) and bounded loss function e,
2 2log(1F1
((,,))~ x1 P E(y, [(){))) S Ep ((x.0))~PP RI. xn (R ((](c)))+[ll
7
where| ||
denotes the infinite norm.
Motivated by Theorem 12, turn to learn with data with sampling errors D,
f arg min E (x.))eDb (xx) fx)).
(7)
SEF
Thus, there exists
B S M f(x)) P Pxo Cy ((.ff())) Yf (8)
Then, modify Theorem 12 to the following version.
Theorem 13. For reconstructible transition T, algorithms f : D - F, distributions P Pxi, Px", Fxx = T(Px) and P. x T(Px and bounded loss function f,
2 log((FF)
JEF [(o.))=2x) E D BI go Ely (D)(z)) S inf B( (vy
n
Proof. This theorem can be directly derived from Theorem 10 and Theorem 12.
From Theorem 13, we can find the learning risk mainly depends on |[ which decided by the transition T.
For naive training strategy, we aim to minimize
E (x. (ū, f()),
where f = fn o fn-1 ....o o f1. However, our method, we use the representations yielded by hidden layers of deep networks. In this paper, employ the second last layer and turn to minimize
E (( fn fn-20.... fi fx))..
That is, we employ (j o can the Moore-Penrose pseudo left inverse of fn instead. In this view, the last layer fn serves as the approximation of the transition implicitly.
fiiff-tfoaa f(x)) to approximate Rū f(x)). fn is likely to be not invertible, but
F COMPARISON OF HPDN AND SOTA STANDARD NCD METHODS
HPDN is specifically designed for NCD under unreliable sampling (NUSA). Encountering sampling errors, HPDN will be much more robust according to Table and 8. However, HPDN cannot outperform SOTA standard NCD methods, e.g.. (Zhao & Han, 2021) and (Zhong et al., 2021a). The main difference between the SOTA standard NCD methods and HPDN is the clustering procedure (the warm-up procedures similar). For standard NCD methods, e.g.. (Zhao & Han, 2021) and (Zhong et al., 2021a), their main framework of clustering is to use the data representations induced by deep networks to compute pairwise similarity and then obtain the pairwise pseudo-labels, and the clustering problem is reduced to binary classification problem (Hsu et al., 2019). With the strong fitting ability of a deep network, they can achieve good performance in standard NCD. However, encountering sampling errors (i.e.. NUSA), deep networks are also easy to overfit these errors due to their strong fitting ability. In addition, these errors will accumulate more and more the training procedure, causing performance degradation (Figure 2). For HPDN, to alleviate the bad effect of sampling errors, we detach all the supervision information in time and propose an Mini-batch Prototypical K K-means to perform clustering. K-means is fully unsupervised method. With useful data representations, our Mini-batee batch Prototypical K-means manages to avoid the accumulation of sampling errors. As its limited fitting ability, our method may not be able outperform SOTA standard NCD methods.
18

---

Under review as a conference paper at ICLR 2023
Table 8: Experimental results HPDN and other baselines. We report the ACC-+ deviation of ACC. All experiments are performed with sampling error rate of 20% and cross rate of 50%. Bold values represent the highest average ACC in each column. We report the results averaged over runs on CIFAR-10, CIFAR- 100. For ImageNet, following (Han et al., 2020), we report the results averaged over different label sets of novel-class data. Results of all the methods are trained for 100
epochs.
Method
CIFAR-10
CIFAR-100
ImageNet
Average
Existing NCD methods
DTC (Han et al., 2019)
30.26% 64%
1 1.61%
34.19%
29.85
RS (Han et al., 2020)
34.56% 80%
21.93%: 68%
35.02%
30.50%
NCL (Zhong ct al., 2021a)
#4.71% 1..19%
55.07%%=2.3449
34.18%
31.32%
UNO (Fini al., 2021)
27.18%:: .90%
36.92%
34.76%
Combine NCD methods with Co Co-teaching (Han al., 2018)
DTC Co-teaching
58.41%
39.27%:+1.377
50.38%
49.35%
RS Co-teaching
55.63%.+1.88
39.60%
53.23%
49.49%
NCL Co-teaching
57.96%:10..8
40.38%
47.17%
48.50%
UNO + Co-teaching
62.37%:1.2.5009
42.26%:12.85%
55.16%
53.26%
Combine NCD methods with DivideMix (Li et al., 2020)
DTC + DivideMix
60.48% ..2.14% 14%
41.23%:13.119%
52.93%
51.55%
RS + DivideMix
64.17%++2.08%9
44.21 44.1%%+3.644 %
54.16%
54.18%
NCL+ + DivideMix
61.40%=#0.68%
1.
50.92%
50.24%
UNO DivideMix
65.59% 2.33%
42.13%
54.79%
54.17%
HPDN (Ours)
68.85 % 13.11 %
43.72%:11.0499
60.16%
$7.58 %
G IMPLEMENTATION DETAILS
Our experiments performed Python 3.6.13, Py Torch 1.7.1, CUDA 11.2, and Tesla A100 GPUs.
Obtain Hidden Representations. For a fair comparison with existing methods, we employ the 1osNet-18/ReNNetaae (He et al., 2016) as the backbones of CALAR100.FFAAR-000/Imaa
The backbone is initialized with SimCLR (Chen et al., 2020) for 300 epochs with the same training strategy (Chen et al., 2020). Known-elass data and novel-class data randomly sampled from D and D whose batch size is set to 256/1024 for CIFAR-10, CIFAR-100 //mmagNeet We use SGD optimizer with initial learning rate 0.1, momentum 0.9, and weigh decay le In addition, the learning rate decays 10 times after each 40 epochs. We pretrain the backbone for 100/150 epochs for [CIFAR-10. 1IFAR-100)/Imagee with average pooling as the hidden representations.
Then, we choose the outputs of the fourth block of ResNet
Mini-batch prototypical K-means. The batch size to 128 for all three datasets. We perform the clustering step for 100 epochs for all three datasets. For hyper-parameter 3 in equation 3, is initialized by 0.05 and set to 0.05 * 0.5epuch//20 in the training procedure, where "//" denotes the exactly divisible operation. We will further analyze the choice of / in Section
19


Reviews:
[{"review_id": "ogimNnJfhh0", "reviewer": "Reviewer_g5Zb", "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 authors describe an approach to solve the unreliability in the novel class discovery problem (NCD), where collectors may misidentify known classes and even confuse known classes with novel classes. They propose a solution which is a combination of a proposed deep network called hidden-prototype-based discovery network (HPDN), and mini batch k-means. The authors evaluate their approach against 3 benchmark datasets and 3 types of models (Existing NCD methods, Combine NCD methods with Co-teaching and Combine NCD methods with DivideMix). ", "summary_of_the_review": "Overall, the paper addresses an important problem of handling novel class discovery problem (NCD). The authors have proposed an approach that learns a HPDN and uses k-means for clustering. The metrics are surprisingly better than baselines, but also are different from those reported in the papers. ", "strength_and_weaknesses": "Strengths:\nThe authors have clearly stated the problem they are addressing and discussed a solution along with experimental results. They have demonstrated the robustness of HPDN under various conditions. \n\nWeakness:\nThe results of the HPDN model are significantly better than the other approaches, which makes one wonder if (a) the baselines chosen are weak, or (b) if the model is indeed better. It is not clear from the paper which is correct. \nLooks like approaches such as UNO (https://arxiv.org/pdf/2108.08536.pdf) and AutoNovel (https://arxiv.org/pdf/2106.15252v1.pdf) seem to have reported different performance metrics than those reported in this paper.\n\nFurther, it is not clear why k-means was chosen instead of other approaches such as cosine similarity, nearest neighbors etc. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "VBTjCUKRrB", "reviewer": "Reviewer_6g6E", "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 aims at a new and interesting setting of novel class discovery (NCD), namely NCD under unreliable sampling (NUSA). In my view it is common NCD plus a special case of label noise. Specifically, this paper is motivated by a sampling view of NCD, and identidies two sampling errors one may face. To conquer the sampling errors, this paper takes inspiration from current label noise literature and proposes a two-stage learning paradigm by first fitting the wrongly sampled data and then discovering the novel classes through a novel mini-batch k-means algorithm. The proposed method is evaluated on several popular NCD benchmarks, which has demonstrated the superiority against the sampling erorrs in NCD.\n", "summary_of_the_review": "A good submission with an intersesting scope and solid solution.", "strength_and_weaknesses": "Strength:\n- This work tackles a relatively new potential problem of NCD that has not yet received much attention.\n- This paper is well written and easy to follow.\n- The proposed method is novel and well motivated.\n\nWeaknesses:\n- Some terms and conclusions are not well explained. For instance, what is the residual sampling errors? Why fully fitting the sampled data is necessary to yield clean data representations from hidden layers?", "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": "CFDhzoe9Rdm", "reviewer": "Reviewer_SxkT", "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": "This paper tackles the problem of novel category discover (NCD) in the setting where samples have been mis-labelled. Standard NCD gives a model a labelled set of images from closed-set categories, as well as an unlabelled set of images from disjoint categories. The task becomes to learn a classifier which can both recognise the labelled classes but also cluster new categories in the unseen data. In this paper, the authors consider the setting in which there is noise within closed-set categories (the labelled set), but also when some closed-set examples appear in the unlabelled set and vice-versa. They name this setting 'NUSA'. \n\nThe authors develop a method to solve this problem which involves fitting a standard classifier on all of the data with a (weighted) cross-entropy loss, treating all unlabelled samples as a single class. Clustering of the new classes is performed by running mini-batch K-Means, where centroids are identified on mini-batches and then averaged across them all.\n\nThe authors show results on CIFAR10, CIFAR100 and ImageNet, which are standard NCD benchmarks. The authors create baselines by taking standard NCD methods and running them on top of data which has been algorithmically cleaned with methods from the label-noise literature.", "summary_of_the_review": "In its current form, I recommend rejecting the paper. I believe this paper makes promising initial steps towards an interesting problem, but I believe both the methods and evaluations could be expanded before it is accepted as a conference publication.\n\nUPDATE AFTER AUTHOR RESPONSE:\n\nI have now read the other reviews and the authors' corresponding comments. I first acknowledge the authors' positive response to my suggestion for early stopping to improve the performance of the baselines. I am surprised by the authors' finding that early stopping actually reduces the performance of the baseline further (though I would be interested in seeing the training curves for validation accuracy vs overall accuracy to verify this).\n\nOverall, however, my main concerns behind the paper remain. Specifically, though the setting is interesting, the method is essentially to train a supervised representation by treating all unlabelled instances as one class, followed by (mini-batch) k-means. This is described in an unnecessarily complicated way which obfuscates the simplicity of the method, and the authors have not updated the paper to reflect this. The result is that I find it difficult to understand which technical components lead to improvement over the baselines.\n\nFor instance, lengthy discussions on the robustness of the intermediate representations (final paragraph of 4.1) are unnecessary given the authors eventually run the classifier on top of the networks' penultimate layer (Fig 5b). This choice is entirely standard (it is the 'feature vector', or the representation before the FC classifier). I also still fail to see substantial difference between the authors proposed mini-batch k-means and the standard version in sklearn, though perhaps I am missing something.\n\nAs such, though I believe the direction of research is interesting, I maintain my original rating.", "strength_and_weaknesses": "Strengths: \n* The problem the authors tackle is interesting. Label noise is something practical vision systems must deal with and the authors demonstrate that the performance of existing methods deteriorates as noise is introduced. Furthermore, the authors explore two forms of label-noise, within the closed-set classes and between the closed and open-set categories.\n* The authors have made a good effort to create strong baselines by running on the combinatorial space of four NCD baselines and two label-noise cleaning techniques. However, it is not clear if and how hyper-parameters for these methods were tuned. \n* The authors' proposed solution outperforms all the baselines. Furthermore, they validate all design choices in the ablation, with substantial performance drops without each component.\n\nWeaknesses:\n* My main concern is that I am not wholly convinced by the method. Though the authors phrase it in quite a complicated way ('Hidden-prototype-based discovery network'), the method is actually very simple: train a model with cross-entropy loss on all data (treating all unlabelled instances as one class); and then cluster network features with mini-batch K-Means. The language used to phrase the method seems more confusing than explanatory. For instance, despite the discussion of how earlier features may have fit less to label noise, the authors seem to use features before the final linear layer, which is a standard choice for clustering of deep features. This is especially a problem since in some cases, the improvements over baselines are small (e.g CIFAR100 case).\n    * I would strongly suggest the authors re-phrase the method section to highlight the simplicity of the method and its strong relation to prior work (e.g MiniBatchK-Means implemented in sklearn).\n* The authors motivate this study by stating that experts or professionals often confuse similar object categories. However, all results are shown on coarse-grained datasets, where the categories (e.g 'horse' and 'ship' in CIFAR10) are easy to distinguish. Other category discovery papers [1] have evaluated on fine-grained datasets which better reflect the motivating setting.\n* Fig1b shows that the performance of RankStats alone can reach as high as 41%, though the performance in Table 1 is reported at 34%. Is this because performance at the final checkpoint is taken? If so, there should be ways to perform early stopping (like performance on a validation set of closed-set examples). \n\n[1] Generalized Category Discovery, Vaze et al., CVPR22\n", "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