Let’s Start Over: Retraining with Selective Samples for Generalized Category Discovery

1 Introduction

Deep neural networks have achieved great success in a variety of mainstream vision tasks, benefiting from the availability of large-scale annotated data [Krizhevsky et al., 2012; He et al., 2016]. Even in semi-supervised scenarios that provide little labeled data and many unlabeled data, the latest work [Fini et al., 2023] can achieve excellent performance on image classification tasks. However, these successes rely on the close-set assumption: test data only comes from categories that have been seen in the model training. In the real world, it is inevitable to encounter unknown categories of data, which presents a huge challenge for model deployment. In order to enable models to handle more realistic scenarios, more and more work attempts to break the constraints of close-set: open-set recognition (OSR) [Scheirer et al., 2012] enables the model to recognize known classes data while rejecting unknown classes, novel category discovery (NCD) [Han et al., 2019] enables the model to recognize unknown classes in the unlabelled data after training on known classes with labeled data. Although NCD can enable the model to recognize unknown classes without any annotation, it assumes that all unlabeled data comes from unknown classes, which is very restrictive. To break this constraint, Generalized Category Discovery (GCD) [Vaze et al., 2022a] has been proposed, which assumes that unlabelled data comes from both known and unknown classes.

∗Corresponding author.

As a challenging problem, GCD not only needs to classify images of known classes correctly but also needs to cluster images of novel classes. Inspired by the powerful neighbor classification capabilities of large-scale pre-trained ViTs [Caron et al., 2021], the seminal work [Vaze et al., 2022a] attempted to solve GCD based on non-parametric classifier: supervised/self-supervised contrastive learning on labeled/unlabeled data is used to perform representation learning on Vision Transformers, and then semi-supervised kmeans is used to classify unlabelled data. Some follow-up works [Pu et al., 2023; Zhang et al., 2023; Zhao et al., 2023; Hao et al., 2023] attempt to construct pseudo-relationships for all labeled/unlabeled training data so that supervised contrastive learning can be performed for these data to learn unbiased representation, thereby facilitating the separation of unknown classes data in the representation space. Recently, another parametric classifier-based GCD method [Wen et al., 2023] has been proposed, which trains a unified classification head for all known/unknown classes by a single crossentropy loss through DINO-like [Caron et al., 2021] form of self-distillion. While these methods achieve improved results, without the guidance of unknown classes of groundtruth labels, they inevitably generate many noisy pseudo relationships/labels for unlabelled data, resulting in suboptimal results.

To generate reliable pseudo relationships/labels for unlabelled data, ideally, we should know the ground-truth labels of these samples, but this is impossible because the purpose of the GCD task is to assign labels to them. However, we can obtain a cluster assignment of these unlabelled data by employing an off-the-shelf GCD method, although each sample cluster is expected to contain a different class of unlabelled samples, a significant proportion of these samples should be class-consistent due to semantic clustering. This allows us to select a class-consistent subset for each novel class sample cluster as a pseudo-labeled set for that cluster. By incorporating these pseudo-labeled sets into GCD retraining, we can construct more reliable pseudo relationships/labels than the original GCD training. For this purpose, we propose to use a nearest neighbor distance-aware label consistency criterion to perform reliable sample selection for each cluster.

Specifically, given the cluster assignment generated by the current GCD method, we first find the top-K nearest neighbors for each sample from all training data based on the cosine distance between the feature representation. Then the original class probability distribution is obtained by aggregating the clustering labels of the nearest neighbor samples, and the index corresponding to the maximum probability of this distribution can be used as the corrected pseudo-labels, so that the corrected class probability distribution can be obtained by the corrected pseudo-labels. Finally, the crossentropy value between the corrected class probability distribution and the original clustering label distribution is used to measure the reliability of the sample. To ensure the same number of samples are selected for novel clusters, we count the number of samples in which the original cluster label and the corrected pseudo-label are agreed upon for each novel class cluster, and a threshold can determine the equal number of samples for each cluster. To address the trade-off between quantity and purity in sample selection, we propose to use supervised representation learning with selected samples for progressive sample selection and take the k-means clustering results of known class validation data as criteria to select the appropriate number of samples.

The main contributions of this paper can be summarized as follows: (1) We propose to construct class-consistent subsets from the cluster assignment of unknown classes generated by current GCD methods as pseudo-labeled sets of these classes and incorporate them into the GCD retraining, thus generating less noisy pseudo relationships/labels during the retraining process. (2) We propose to use the nearest neighbor distance aware label consistency as the criterion and perform supervised representation learning with selected samples for progressive sample selection to achieve a good trade-off between the quantity and purity of the final selected samples. (3) We evaluate our approach on both parametric and nonparametric classifier base GCD methods, achieving superior performance on multiple generic and fine-grained datasets.

2 RelatedWork

Generalized Category Discovery. Generalized Category Discovery (GCD) can be seen as an extension of novel category discovery (NCD) [Han et al., 2019; Han et al., 2020; Zhong et al., 2021; Fini et al., 2021] in real scenarios.

From the perspective of classifier form, GCD can be divided into non-parametric classifier-based method and parametric classifier-based method. For the former, [Vaze et al., 2022a] explores the relationship between labeled data through supervised contrastive learning; meanwhile, in order to extend supervised contrastive learning to unlabelled data, [Pu et al., 2023; Zhang et al., 2023; Zhao et al., 2023; Hao et al., 2023] are devoted to establishing the pseudorelationship between all labeled/unlabeled training data to learn unbiased representation, and then classify samples by semi-supervised k-means or other non-parametric clustering [Hao et al., 2023]. The latter [Rizve et al., 2022; Fini et al., 2023] trains a unified classification head for all classes through DINO [Caron et al., 2021] or SwAV[Caron et al., 2020]-Like form of online clustering. Despite the progress, they inevitably generate many noisy pseudo relationships/labels for unlabelled data, resulting in suboptimal results. We try to select class-consistent sample subsets for the sample clusters generated by current GCD methods, thus generating less-noisy pseudo relationships/labels and incorporating them into retraining to improve model performance.

Semi-supervised Learning. Semi-supervised learning (SSL) aims to learn from a limited amount of labeled data and a large amount of unlabelled data. Pseudolabeling [Lee and others, 2013; Arazo et al., 2020; Rizve et al., 2021] and consistency regularization [Laine and Aila, 2016; Tarvainen and Valpola, 2017; Xie et al., 2020] are two popular methods of SSL in the era of deep learning. The former first uses the model trained with labeled data to generate pseudo-labels for unlabelled data and then adds them to the next training together with the labeled data. The latter forces the model to output consistent predictions for the perturbed unlabeled data, which improves the generalization ability and robustness of the model. We select a class-consistent sample subset from each novel class sample cluster as the labeled data of that class, so that GCD can be treated as a semi-supervised learning task.

Deep Clustering. Image clustering is a prevalent proxy task for unsupervised image representation learning. Deep clustering [Caron et al., 2018] is the first method to combine clustering and deep network for unsupervised representation learning. IIC [Ji et al., 2019] introduces a mutual information maximization objective to perform clustering-based unsupervised representation learning. Asano etal. [YM. et al., 2020] propose to transform cluster assignment into an optimal transport problem and solve it by Sinkhorn-Knopp algorithm. Based on the above clustering method, Caron etal. [Caron et al., 2020] propose a swapped prediction mechanism: the cluster assignment of one view of the same image is used as the pseudo-label for another view. Subsequently, they propose [Caron et al., 2021] a self-distillation mechanism based on a teacher-student network to perform unsupervised representation learning for ViTs.

3 Preliminaries

3.1 ProblemFormulation

For a standard GCD task, the overall training data D is divided into two datasets: labeled dataset Dl and unlabeled dataset Du, where Dl = {xi, ˜ yi}ni=1 , with ˜ yi ∈ Yl, and Du = {xj}mj=1 , with underlying label space Yu. Specifically, the label space of labelled dataset Yl ⊆ Yu and the novel classes of unlabelled dataset Yn = Yu \Yl. For convenience, we denote Yu, Yl and Yn as "All", "Old", and "New" classes respectively. In general, GCD assumes that the number of classes in D (i.e.|Yu|) is known as a priori[Fei et al., 2022; Zhang et al., 2023; Wen et al., 2023] and can also be estimated by some ready-made methods for practical applications[Han et al., 2019; Vaze et al., 2022a; Pu et al., 2023]. The goal of GCD is not only to correctly classify the old classes samples in Du but group the new classes samples in Du into |Yn| clusters by employing a model with the knowledge from Dl.

3.2 Two Paradigms of GCD

Non-parametric GCD methods. Given the training data D = Dl ∪ Du, we assume xi and x′i are two randomly augmented views of the same image in a mini-batch B. zi = ϕ(xi) is the L2-normalized feature embedding, P(x) is the positive set of feature embedding zi. BL is the labelled subset of B. The seminal work [Vaze et al., 2022a] performed supervised contrastive learning on Dl:

and self-supervised contrastive learning on D:

Here, the relationship between labeled data can be explored by supervised contrastive learning due to the availability of ground truth labels. However, self-supervised contrastive learning only makes the sample close to its own augmented counterpart and far away from all other samples, so the relationship between labeled data and unlabelled data and within unlabelled data is ignored. Several subsequent efforts [Pu et al., 2023; Zhang et al., 2023; Hao et al., 2023] focused on generating pseudo-labels for unlabeled data so that supervised contrastive learning could be used to explore the relationship between all training data as shown in (Fig. 1). However, unlike semi-supervised learning, which provides some ground-truth labels as guidance for all classes, it is not easy to generate accurate pseudo labels for novel class data without any annotation in GCD. Even if current work has designed many ingenious mechanisms to reduce pseudo-label noise, non-negligible undetected noisy pseudo-label still causes the network to learn suboptimal representation, resulting in unsatisfactory performance.

Parametric GCD methods. Given the training data D = Dl∪Du, as shown in (Fig. 1), parametric GCDMethods [Wen et al., 2023; Rizve et al., 2022] uses a single cross-entropy loss ℓ to train a unified prototypical classification head that includes all old and new classes. Specifically, the labeled samples x can be trained directly by using class labels as supervision information:

where yi the one-hot ground-truth label of xi and pi is the softmax normalized probability of xi. For unlabelled samples, two random augmented views (x, x′ ) of each input image are fed into the network backbone f(.) and prototypical classifier h to obtain the classification logits (g, g′ ), softmax function with temperature is then applied to these logits to obtain the probability distribution (p, p′ ) of the input image.

Specifically, the process of pseudo-labeling can be represented as follows:

where τ is the pseudo-labelling methods (e.g.self-distilling, optimal transport), c is the implemented context of τ, η is entropy regularization term, q′ is the generated pseudo label, which can be used as the target of p in the cross-entropy loss:

where T is the number of sample clusters.

However, due to the strong supervision of the old classes during training, the representation of novel classes samples is easily biased toward the old classes. Meanwhile, due to the random initialization of the prototypical classifier and without the guidance of ground-truth label, the clustering of unlabelled data of novel classes in the feature space is suboptimal and even completely inconsistent with the actual distribution of that classes, since the prototypical classifier may encode spurious correlations for unlabelled data[Fini et al., 2023]. On the contrary, clusters of unlabelled data of old classes could be concentrated on the class centroid represented by the labeled data, which makes the label information of labeled data can be efficiently propagated to unlabeled data.

4 Our Method

In this section, we introduce a method for enhancing label consistency by selecting pseudo-labeled samples through a neatest neighbor distance-aware strategy. These samples form subsets for novel class cluster assignments derived from the off-the-shelf GCD method. We then detail our progressive sample selection training approach with supervised representation learning. Finally, we explain the integration of these selected pseudo-labeled sample subsets into the GCD retraining process.

Enhancing label consistency through nearest neighbor distance-aware sample selection. To alleviate the biased representation caused by the lack of supervision information of new classes, we propose to select a class-consistent subset from each noisy novel class sample cluster that the current GCD method generates as the "pseudo-labeled set" for that cluster, which allows the unlabelled data of new and old classes to be trained consistently, thus reducing the bias of the learned representation. Although it sounds attractive, selecting such a class-consistent subset is very challenging because Labelled / True pseudo-labelled sample False pseudo-labelled sample Cluster prototype

+/- Positive / Negative relation

the noisy samples in the sample cluster are mostly "hard negative". In order to efficiently select less-noisy sample sets for novel classes, inspired by [Ortego et al., 2021], we propose to use the Nearest Neighbor Distance-Aware criterion to select reliable samples for each cluster. For the sample clusters S = {S1, S2, S3, . . . , S|Yu|} generated by the GCD method, where Sc = {(xi, yi)}nc i=1 , c ∈ Yu, nc is the sample size of Sc. Given the feature representations zi of a sample xi with assigned cluster label yi, we select the top-K nearest neighbor samples Ni for xi from all other training data D\xi according to the cosine similarity between their feature representations. To correct the original assigned noisy cluster labels, the cluster labels of K-nearest neighbor samples are aggregated as the class probability distribution for xi :

we can take the index corresponding to the maximum probability of pc (xi) as the corrected pseudo-label ˆ yi. Therefore, the corrected class probability distribution is:

Finally, cross-entropy value is used to measure the difference between the pseudo-label probability distribution and the original label probability distribution:

The higher the value, the higher the probability that the sample is noisy. Therefore, we can select reliable samples based on the cross-entropy value, and to ensure the number of samples selected for all clusters is consistent, for each novel class sample cluster, we count the number of samples in which the original cluster label yi and the corrected pseudo-label ˆ yi agreed, i.e., M = {m|Yl|+1, . . . ,m|Yu|}, where mc = ∑nc i=1 1 [ˆ yi = yi] [yi = c] , c ∈ [|Yl| + 1, |Yu|]. Specifically, the γ quantiles of M can be used as the selected samples number ω for each cluster, where γ ∈ [0, 1]. Finally, we can select ω samples for each novel class sample cluster as class-consistent subset S ω c according to the value of cross-entropy in Eq.8 from small to large and the final selected sample is Snovel = ∪|Yu| c=|Yl|+1S ω c .

Progressive sample selection based on representation learning. For the selected class-consistent subset, our selection strategy naturally leads to the trade-off in quantity and purity: a large γ value results in a higher number of selected samples, but the purity of the sample subset decreases because more less-confident samples are selected; a small γ value will select a small number of high-purity samples for the sample subset, but they cannot provide rich supervisory information in subsequent training. In order to achieve a good quantity-purity trade-off, we perform supervised representation learning for progressive sample selection. Specifically, we set a γ value that allows the model to select a small number of high-purity samples subset Snovel at the beginning of training, and then use these pseudo-labelled novel class samples and the same per-class number of labelled old class samples Sold = ∪|Yl| c=1Dω l,c as selected labeled training data S = Sold ∪ Snovel for supervised representation learning of the backbone network:

where, Lsel scl is supervised contrastive loss and Lsel ce is crossentropy loss, λc is a balance factor. xi is a randomly augmented view of a image in a mini-batch B. zi = ϕ(xi) is the L2-normalized feature embedding, Psel(x) is the postive set of feature embedding zi. With the benefit of highquality supervised information of novel classes, the representation capability of the network should be enhanced, which can help the next run of sample selection. We can execute this selection-training strategy iteratively until collect enough samples for each subset. While this sounds appealing, it is unrealistic because we have no prior knowledge of the noise rate of the original sample clusters, which leaves us still unaware of how many samples it is appropriate to select. To solve this problem, we use validation data of old classes as the validation set for the progressive sample selection. At the end of each stage of training, we perform k-means clustering on the validation set and the final number of selected samples can be determined by the best clustering accuracy.

Clustering refinement learning with selected samples. Once we have the high-purity sample subset selected from the original novel classes sample cluster generated by existing GCD methods, we can take them as labeled samples of novel classes in GCD retraining. Specifically, for non-parametric GCD methods, since all classes of labeled data could be used in supervised contrastive learning, the network can explore the relationship between all classes, thereby mitigating the bias of the learned representation; for parametric GCD methods, instead of using the pseudo-labels generated by online clustering, we can take the pseudo-label of the selected sample subset as the "ground-truth" label for all the samples of that sample subset, which makes the remaining novel classes unlabelled data can be concentrated on the class centroid generated by the labeled data during the online clustering learning, so that labels can better propagate from labeled data to unlabelled data.

5 Experiments

5.1 Experimental Setup

Datasets. We evaluate our method on two generic datasets (including CIFAR100 [Krizhevsky, 2009] and ImageNet100 [Deng et al., 2009]) and four challenging fine-grained datasets from Semantic Shift Benchmark [Vaze et al., 2022b] (inculding CUB-200 [Wah et al., 2011], Standford Cars [Krause et al., 2013] and FGVC-Aircraft [Maji et al., 2013] and Oxford-Pet [Parkhi et al., 2012]), and large-scale ImageNet-1K [Deng et al., 2009]. For all training data D, following previous work, we split "All" classes into "Old" classes and "New" classes and sample 50% images from base classes and all images from novel classes as unlabelled data Du, while the remaining images are regarded as labelled dataset Dl. The dataset statistics are shown in supplemental.

Evaluation protocol. Following [Vaze et al., 2022a], we evaluate the clustering accuracy (ACC) on the unlabelled dataset as follows:

Where P is the set of all permutations that computed with Hungarian algorithm[Kuhn, 1955], N = |Du| is the number of samples in the unlabelled dataset, ˜ yi and yi represent the ground-truth label and clustering prediction.

Implementation details. Following [Vaze et al., 2022a], the ViT-B-16 pretrained by DINO [Caron et al., 2021] is used as the backbone network for all of our experiments. For the parametric/non-parametric GCD baseline methods that require direct comparison, we perform model training using the same parameter configuration as in the paper to get roughly the same clustering assignment accuracy. In progressive sample selection stage, the network is trained for 120 epochs on each dataset and sample selection is performed every 20 epochs. We use an SGD optimizer with a momentum value of 0.9. We set the initial learning rate to 0.1 and decay it to 0.0001 by cosine annealing every 20 epochs, and then reset the learning rate to the initial value at the start of each sample selection. For all generic and fine-grained image datasets, the value of K is set to 200 and 15 respectively, the value of λc is set to 1. For all datases, we choose γ so that the number of samples selected for each sample subset in the first selection is roughly half the number of per-class labeled samples for the old classes. In the meanwhile, we constraint that the maximum number of samples selected for each sample subset ω does not exceed the number of per-class labeled samples of the old classes. For the retraining stage, the network is trained for 100 epochs on all datasets. For all datasets, we show the average clustering accuracy of three independent runs. We also provide the performance standard deviation of our method in the supplementary material.

5.2 Comparison to the State-of-the-Art

We apply our method to GCD[Vaze et al., 2022a] and SimGCD[Wen et al., 2023], a strong non-parametric baseline and a strong parametric baseline, to compare with the state-of-the-art methods: including k-means [Arthur and Vassilvitskii, 2007], RS+ [Han et al., 2020], UNO+ [Fini et al., 2021], OCRA [Cao et al., 2021], DCCL [Pu et al., 2023], GPC [Zhao et al., 2023]. The clustering accuracy on generic and fine-grained datasets are reported in Table 1. The clustering accuracy on ImageNet-1K dataset are reported in Table 2. "+all" refers to incorporating all samples from cluster assignment to the GCD retraining as the pseudo-labeled sets. "+sel" refers to using our method to select the class-consistent sample subsets from the cluster assignment and incorporating them to the GCD retraining as the pseudo-labeled sets.

In Table 1, it can be seen that SimGCD+sel outperforms all the state-of-the-art methods on both generic and fine-grained datasets. Compared with SimGCD, SimGCD+sel achieved 0.6% and 2.4% improvement on generic CIFAR100 and Imagenet100 datasets in the case of high baseline results and achieved 4.8% and 3.4% improvement on fine-grained CUB and Oxford-Pet datasets. Compared with the non-parametric baseline method GCD and GCD+all, GCD+sel achieves improvement on all six datasets. These results validate the effectiveness of incorporating the selected class-consistent sample subset into GCD retraining. In addition, we can find that the improvement of "All" acc mainly depends on the improvement of "New" acc, which well demonstrates that our method generated less noisy pseudo relationships/labels for novel classes, thus facilitating representation learning.

In Table 2, it can be seen that SimGCD+sel also achieves the best results, which well demonstrates the effectiveness of our method on large scale dataset.

5.3 Ablation Study

In this section, we adopt SimGCD as the baseline method and conduct ablation experiments on CIFAR100 and CUB datasets to verify the effectiveness/sensitivity of the main components of our method.

Different sample selection strategies. We evaluate the effect of different sample selection strategies. The results using different selection strategies are shown in Table 3. It can be observed that nearest neighbor sample selection with quantitative constraints achieves the best results. In contrast, randomly selecting the same number of samples as the nearest neighbor method as the pseudo-labeled dataset achieves inferior results, which well demonstrates the necessity of nearest neighbor aware label consistency sample selection. Meanwhile, all retraining methods based on selected samples achieve better "New" classes ACC than the baseline, which proves that using the class centroid generated by pseudolabeled data (even if it contains a certain amount of noise) instead of randomly initialized clustering prototype does help the clustering of novel classes.

Impact of K values. We evaluate the choice of different K values. Multiple sample selection is performed by setting different K values in KNN-based class probability distribution aggregation. The results of SimGCD retrained with samples obtained by setting different K values for sample selection are shown in Table 4. It can be observed that for CIFAR100 dataset, once K is not too small, the final clustering results are not sensitive to the K value. In contrast, the clustering results of CUB dataset are different under different K values. This is because the sample size of each class in CUB dataset is very small, setting too small or too large K value will make the selected samples unreliable, and using these samples for retraining will lead to the decline of clustering results.

The effectiveness of supervised representation learning.

We evaluate the effectiveness of supervised representation learning. Different sample selection is performed by using different losses in supervised representation learning. The results SimGCD retrained with samples obtained by using different losses for sample selection are shown in Table 5. It can be observed that the best results are achieved by using both supervised contrastive loss and cross-entropy loss, this is because the selected samples achieve a better quantity-quality trade-off: the method using two loss terms selects significantly more samples for novel classes than the method using a single loss (supervised contrastive loss) (5000 vs. 1000 for CIFAR100, 1386 vs. 598 for CUB), even though the sample quality decrease (99% vs. 87% for CIFAR100, 80% vs. 73% for CUB); for CUB dataset, comparing with the method using a single loss (cross-entropy loss), the method using two loss terms selects significantly more samples for novel classes (1386 vs. 1093) while maintaining nearly the same sample quality (73% vs. 74%).

5.4 Further Analyses

Sample selection analysis. To further verify the effectiveness of our sample selection strategy, we perform SimGCD retraining on the CUB dataset using each sample selected during the progressive sample selection process and the final clustering results are shown in Figure 2. Finally, our method uses the samples obtained from the second sample selection as pseudo-labeled set of the novel classes. It can be observed that SimGCD retraining based on our sample selection strategy achieves the best clustering results. After that, with the progress of sample selection training, the model gradually fits noise samples, so that the selected clean samples gradually decrease and the selected noisy samples gradually increase, resulting in the clustering accuracy gradually decreases.

Performance with estimated class number. To evaluate the performance of our method in more realistic scenarios, we conduct experiments under the assumption that the number of new classes is unavailable. Specifically, following Xcon [Fei et al., 2022], we first employ an off-the-shelf estimation method from [Vaze et al., 2022a] to obtain the number of classes of all training data, and then use the estimated class number k to perform GCD training. The comparison of our method with SimGCD and Xcon is reported in Table 6. As can be seen, our method achieves the best results and has a significant improvement compare with SimGCD on CUB and Oxford-Pet datasets, which well confirms the robustness of our method in more realistic scenarios.

The computational resource cost of K-nearest neighbor sample selection. Our KNN sample selection method is performed on faiss-gpu 1 code library, which can achieve more than 100 times acceleration compared to KNN search in sklearn, enabling the proposed method to quickly perform sample selection during the model training. Table 7 reports the runtime for one KNN selection on all training samples.

6 Conclusion

In this paper, we propose to generate less noisy pseudo relationships/labels for unlabeled data during GCD training by using a class-consistent sample subset of novel classes. To achieve this, we propose to use a nearest neighbor distance aware label consistency criterion to conduct sample selection. To achieve a good trade-off between the quantity and purity of the final selected samples, we perform progressive sample selection training with selected samples. By using the selected sample as a pseudo-labeled sample set, the pseudo relationships/labels with less noise are generated for the training data in GCD retraining. Extensive experimental results on multiple generic and fine-grained datasets for both parametric and non-parametric GCD methods demonstrate the validity of our proposed method.

1 https://github.com/facebookresearch/faiss

Acknowledgments

This work is funded by NSFC (NO. 62206135, 62225604), Young Elite Scientists Sponsorship Program by CAST (2023QNRC001), and the Fundamental Research Funds for the Central Universities (Nankai Universitiy, 070-63233085). Computation is supported by the Supercomputing Center of Nankai University.