Few-shot Novel Category Discovery

1 Introduction

Most deep learning methods [He et al., 2016; He et al., 2022; Dosovitskiy et al., 2021] aim to excel in supervised learning, where models assign labels to test samples using knowledge from training. However, this approach poorly reflects real-world scenarios, where unlabelled data may include both known and novel classes. Few-shot Learning (FSL) [Finn et al., 2017; Sung et al., 2018; Fei-Fei et al., 2006; Vinyals et al., 2016; Li et al., 2023] addresses this by mimicking human ability to learn from limited examples. Despite its potential, FSL has a critical drawback: if not all categories are annotated, it forces classification of unseen classes into existing ones, contradicting open-world reasoning.

∗Corresponding Author.

The advent of Novel Category Discovery (NCD) [Rizve et al., 2022] and Generalized Category Discovery (GCD) [Vaze et al., 2022a] lifts the learning agent to a new level, where the novel examples are allowed to be grouped into a few clusters based on their inherent characteristics. Notwithstanding, the key of these two tasks will degenerate into solving a cross-domain clustering problem if unlabelled data are not presented. A recent research, On-the-fly Category Discovery (OCD) [Du et al., 2023] was proposed to mitigate the limitation of transductive learning involved in NCD and GCD by determining novel classes according to the values derived from decoupling features into symbolic features and absolute features. However, the over-relaxed constraints imposed on the hash encoding for novel classes lead to a phenomenon in which a higher number of clusters formed than initial expectation.

To enhance the adaptability of learning agent to real-world scenarios, we adapt the assumptions and training strategies in NCD. Similar to FSL, we ensure no overlap between training and test label spaces, and the test set's query label space extends beyond the support set to include novel categories. Unlike semi-supervised strategies in NCD [Rizve et al., 2022] and GCD [Vaze et al., 2022a], we adopt episodic metalearning to better evaluate the model's adaptability to new tasks.

We call this new problem Few-Shot Novel Category Discovery (FSNCD), and it is intersected conception at the FSL [Fei-Fei et al., 2006] and NCD [Rizve et al., 2022], empowering a learning agent with the capability to be inductively adaptive to the discovery of both novel classes and clusters. The key setting of this problem is illustrated in Fig. 1, and it builds upon the existing setting of NCD [Rizve et al., 2022] which was introduced to cluster novel classes by hints of both labelled and unlabelled data. This scenario assumes that a learning agent can both extract features from labeled data and learn patterns from unlabeled data. Our proposed setting challenges this by restricting access to unlabeled data, focusing instead on enhancing the model's adaptability and plasticity to improve generalization.

FSNCD leverages a DINO [Caron et al., 2021] pre-trained ViT-B [Dosovitskiy et al., 2021] model, differing from traditional few-shot learning by tackling novel category discovery, which involves clustering novel classes rather than simple detection. We introduce a hierarchical clustering method with a stopping criterion based on inter-class distances of visible classes, addressing bias from excessive novel categories through balanced sparsity. Additionally, an improved Kmeans algorithm incorporates uncertainty clustering to handle distributions. Unlike existing methods reliant on prior category counts, our approach restructures K-means and hierarchical clustering to flexibly estimate category numbers in few-shot settings, facilitating the discovery of new categories. To sum up, our contributions are as follows:

• We propose a new task setting named Few-Shot Novel Category Discovery (FSNCD). It unifies few-shot learning and Novel Category Discovery, realising a selectivity between tasks of identifying examples from labelled classes in a real-time inference manner and clustering novel classes as the query examples increase.
• We introduce two clustering algorithms as baseline methods: Semi-supervised Hierarchical Clustering (SHC) and Uncertainty-aware K-means Clustering (UKC). Both approaches take into account the specific features required to address the complexities of open-set recognition, extending beyond conventional data clustering techniques.
• We conducted experiments on five datasets, analyzing and elucidating the viability of the proposed new setting.

2 RelatedWork

2.1 Semi-Supervised Learning

In traditional supervised learning, we need a large amount of labeled data to train the model [Chapelle et al., 2009; Yang et al., 2023]. To address the problem of insufficient labeled samples, semi-supervised learning is proposed to utilize labeled and unlabeled data to improve model performance with limited labeled data [Grandvalet and Bengio, 2004; Zhou, 2008; Jiang et al., 2024; Yang et al., 2024]. The most intuitive approach is perhaps Pseudo-Labels selftraining [Lee and others, 2013], where a model trained on labeled data generates categorical pseudo-labels for the unlabeled examples. SSL techniques often utilize unlabeled data in various ways, such as employing strategies like consistency regularization [Tarvainen and Valpola, 2017], generative model based methods [Madani et al., 2018], or graph based method [Zhu et al., 2023].

2.2 Novel Category Discovery

Novel Category Discovery (NCD) addresses limited labeled data by leveraging unlabeled samples for automatic classification. Pioneered by DTC [Rizve et al., 2022], the field has expanded with methods like AutoNovel [Han et al., 2020], which combines self-supervised pretraining with pseudo-label generation via ranking. Recent extensions include Novel Category Discovery in semantic segmentation [Zhao et al., 2022], incremental learning frameworks [Liu and Tuytelaars, 2023; Roy et al., 2022], and Generalized Category Discovery (GCD) [Vaze et al., 2022a] that jointly identifies known/novel categories. SimGCD [Wen et al., 2023] enhances GCD with parametric classification, while OCD [Du et al., 2023] introduces real-time hash coding for efficient novel class detection. These advances demonstrate NCD's growing versatility in handling diverse real-world scenarios.

2.3 Few-Shot Learning

Few-shot learning (FSL) is a method used to address the issue of limited sample size [Fei-Fei et al., 2006; Finn et al., 2017; Snell et al., 2017; Xu et al., 2024; Zhong et al., 2023]. It aims to learn an effective classification model from a few labeled training examples. There are two main types of FSL methods: meta-learning-based [Finn et al., 2017; Ravi and Larochelle, 2016; Tian and Xie, 2023] and metriclearning-based approaches [Snell et al., 2017; Koch et al., 2015]. Additionally, some methods employ a Non-episodicbased strategy [Chen et al., 2019; Dhillon et al., 2020], i.e., fine-tuning a pre-trained model at test time. Although current methods for Few-shot Open-set Recognition [Liu et al., 2020; Jeong et al., 2021] are capable of detecting out-of-distribution samples, they lack the ability to cluster or classify these outof-distribution samples.

3 Few-Shot Novel Category Discovery

3.1 ProblemDefinition

NCD: The training data for NCD is provided in two distinct sets, including a labelled set DL = {(xli , yl i )}Ni=1 and an unlabeled set DU = {xui }Mi=1 , where an instance is denoted as xli or xui depending on which set the data is derived from, yl i ∈ Y L = {1, . . . ,C L} is the corresponding class label of DL and Y U is the label space of DU . The goal is to train a model on both DL and DU , and then aggregate DU into C U clusters that are associated with Y U = {1, . . . ,C U} where Y L ∩Y U = ∅. GCD further relaxes the assumptions of NCD, with an emphasis on identifying both labelled data and novel categories, where the label space of DU changes to Y L ∪ Y U instead of Y U .

FSL: In FSL, a dataset D is usually partitioned into two sets, the training set containing base classes DBase and the test set containing novel classes DNovel . It creates N training tasks T = {T1, . . . , TN} to assemble a finite set of training episodes where each training task Tn consists of different classes, represented by Tn =< S,Q >, where S and Q denote examples chosen from the support set and query set, respectively. During testing, the model receives new tasks with the novel classes which have no overlap with those encountered during training.

FSNCD: We approach Few-Shot Novel Category Discovery as a scenario where the dataset is organized under the setting defined in FSL with training set containing base classes DBase and the test set containing novel classes DNovel . However, an episode in FSNCD contains a query set Q = {(xq , yq )} ∈ X ×Y Q , and a support set S = {(xsl , ys l )}NK l=1 ∈ X × Y S of K image-label pairs for each N classes, referring to an N-way K-shot setting. However, the label space in FSNCD is defined as Y Q = Y S ∪ Y N rather than Y Q = Y S as defined in standard FSL. The primary objective for the learning agent therefore is to identify examples of categories in Y S while discovering unknown categories in Y N .

The characteristics of the proposed setting are summarised in Table 1 and Fig. 1. SSL is an inductive approach leveraging both labeled and unlabeled data within the same label space for test set classification. GCD relaxes the closedset assumption, allowing the label space of unlabeled data to encompass that of labeled data, following a transductive paradigm. Transitioning from NCD and GCD to FSL introduces FSNCD, which combines few-shot classification with the discovery of novel categories. A key distinction between FSNCD and traditional FSL is that in the testing phase of FSNCD, certain samples may not match any of the support categories. Unlike Few-Shot Open Set Recognition (FSOSR), which only detects outliers, FSNCD requires models to detect and accurately cluster these outliers. Additionally, in contrast to open-world recognition, categories appearing in testing phase of FSNCD are not seen during training, though a limited number of samples are provided during testing.

3.2 Training of FSNCD

The training procedure for a learning agent in FSNCD is divided into two consecutive phases: representation learning and classifier construction. For the former phase, the learning model is dedicated to training a feature extractor F and a projection head ϕ, ϕ ◦ F : X → Z, with Z signifying the embedding space generated from input images X via ϕ ◦ F. The latter phase is responsible for constructing a classifier capable of recognizing query examples and discovering novel categories. An overview of our approach is demonstrated in Fig. 2. A detailed explanation of each phase will be presented in the sequel below.

Phase 1: Representation Learning Given that the training process only involves the use of labelled data, the supervised contrastive learning loss [Khosla et al., 2020] is employed to learn more distinctive features for samples belonging to the same category and different categories within each batch. This mitigates the impact of using standard cross-entropy loss for prototype matching which is classification-prone rather than concentrating on the more critical clustering task, and avoids the occurrence of the visible-class bias described in ProtoNet [Snell et al., 2017]. Specifically, given an input image x, it uses the feature extractor F (x), together with a multilayer perceptron (MLP) projection ϕ to extract the feature embeddings z, denoted as z = ϕ (F (x)). Formally,

where N(i) signifies the images belonging to the same category as the input image xi in an episode, where I is an indicator function evaluating to 1 iff n ̸= i.

Phase 2: Classifier Construction Using the previously learned representations, the next task is to construct classifiers with the ability to classify query samples into known classes or group a set of examples into new categories. Due to our aim to propose solutions addressing more realistic problems, the varying number of novel categories and the uncertain number of samples per novel category make it hard to construct a fixed-parameterized classifier. Thus, two clustering algorithms, Semi-supervised Hierarchical Clustering (SHC) and Uncertainty-aware K-means Clustering (UKC), are specifically designed for FSNCD scenarios, enhancing data grouping in open-set scenarios by aligning more closely with their inherent properties.

Semi-Supervised Hierarchical Clustering. Hierarchical clustering is one of the most commonly used approaches for grouping data, distinguished by its ability to determine the number of clusters with no need to pre-specify the number of clusters. Grouped clusters that are visually represented in a hierarchical tree called a dendrogram whose structural characteristics are the key to achieving optimal clustering. However, it is always a challenge in practice to determine the best criteria to end the accumulation or division during clustering.

To tackle this issue, we tend to make the most of the information represented by features extracted from the support set which are capable of explicitly characterizing discrepancies between multiple class prototypes. The idea behind this is that hierarchical clustering should cease as chosen prototypes that originate from different classes are merged. Concretely, we introduce an agglomerative hierarchical clustering approach, inspired by the Unweighted Pair Group Method with Arithmetic Mean (UPGMA) where the closest clusters are combined into a higher-level cluster at each step. For each step, the distance between any two clusters Ci and Cj is calculated by averaging the distance between elements within the cluster, expressed by,

where d(∗, ∗) denotes the distance function. In each iteration, the two clusters with the shortest distance are merged, and the clustering between all clusters is updated by,

The proposed clustering aims at merging the most similar classes according to the adopted cosine metric and triggers iteration termination until two different class prototypes are grouped. Furthermore, clustering is conditioned on the number of query samples, i.e., it will be considered a potential cluster P only if the amount of included samples exceeds a certain value, in which case the remaining clusters are designated as R. Moreover, in case there are support prototypes that are not assigned to any cluster, they will be incorporated into the potential class P at the end. With the available class prototypes of the potential classes, the remaining samples will be classified, demonstrating a flexible method of classifying or clustering query samples, called semi-supervised hierarchical clustering.

Uncertainty-Aware K-means Clustering. K-means clustering is an effective method to iteratively partition a certain number of data observations into K clusters, but the need for the pre-specified number of clusters always hinders its generalization to scenarios full of uncertainty. The adoption of Kmeans on synthetic experimental datasets is based on a prior on how human perception of the K values, which is unrealistic when dealing with real-world tasks where such values are difficult to determine. In addition to the heavy reliance on prior knowledge, the performance of standard K-means clustering strongly depends on the choice of the initialized cluster centroids, which is another uncertainty that needs to be addressed. K-means++ [Arthur and Vassilvitskii, 2007] presents a stepwise selection of cluster centers, primarily motivated by the idea that samples farther away from other cluster centers are more likely to be selected as the next cluster center. However, the initial number of categories is still an indispensable prior information.

We introduce a new strategy that builds on the assumption that when clustering is performed in the proposed FSNCD setting, both support and query examples lie in a uniform, high-dimensional feature space, and the uncertainty estimates of this space facilitate the choice of the number of centroids implied by novel categories. Specifically, we consider that the features of prototypes and query examples are located in a shared space, denoted by z, and represent standard K-means as K-means (·, ·, ·), then the corresponding potential cluster P can be achieved by,

where n is number of categories initialized with |YS|, c denotes the centroids and is initialized randomly. As the iteration k increases, the average quantity is calculated based on the previous clustering results, denoted as m = 1 |P k | ∑|P k | i=1 ∣∣P k i ∣∣. The estimation of the number of categories is then transformed into an acceptance criterion for a particular class in P k i that surpasses the average quantitym, denoted as α. We then need to split all potential classes where each class is assigned a category count by,

where δ(·) denotes the way to estimate the number of supported prototypes in a specific cluster, and µ(·) denotes the calculation of the number of query samples in Pi. Through regrouping the samples of each class into nP k i clusters, it yields

the centroid ck = [ck1 , ..., cknPk ], where nP k = ∑|P k | i=1 nP k i signifies each split in P k that serves as the initialization points for the next iteration denoted as,

The above iteration will terminate when the conditions max δ(Pi) = 1 and maxµ(P) < αm are satisfied simultaneously, which also guarantees convergence under the previously mentioned assumption. Moreover, choosing an appropriate acceptance threshold for this clustering approach facilitates the optimal proficiency to discover novel categories. It is worth noting that when α → +∞, this method will degenerate to continuously split the potential classes by δ(Pi) ≥ 2, which will undoubtedly lead to biases towards classes of existing support sets.

3.3 Scalable Clustering

Compared to the UKC which is an evolution from standard K-means clustering, the proposed SHC exhibits relatively high computational complexity and memory usage due to its need to calculate and store distances between all pairs of data points, which grows exponentially with the size of the largescale dataset, rendering it both computationally demanding and memory-intensive.

To mitigate the impact of the aforementioned issues, we employ a two-step strategy. In the first step, we randomly sample a smaller subset from the entire dataset, which is assumed to be representative since its distribution is consistent with that of the overall data distribution. The subsequent use of hierarchical clustering on this representative subset yields a set of potential clusters that can be viewed as initial prototypes. In the next step, these established prototypes serve as reference points for classifying the remaining data. Specifically, each data point will be merge to the tree which prototype is closest to it in the shared feature space. This strategy enables hierarchical clustering to be applied at scale, but its performance is influenced by the randomness of sampling and the quality of the initial clustering.

4 Experiments

4.1 Experimental Setup

Datasets. We evaluate our methods on two well-known large-scale datasets: CIFAR-100 [Krizhevsky et al., 2009] and ImageNet-100 [Krizhevsky et al., 2012], as well as two fine-grained datasets, including CUB-200 [Reed et al., 2016] and Stanford Cars [Krause et al., 2013]. Each dataset is split into two sets: labeled data is used to train the model, and unlabeled data is used for testing. SSB (Semantic Shift Benchmark) [Vaze et al., 2022b] provides a detailed evaluation dataset that includes precise "semantic change axes" and provides classifications for DU and DL in a semantically coherent manner. Statistics on the partitioning of adopted datasets are presented in Table 2.

Settings. Wemainly report results obtainedwith two different settings: 5-way 5-shot (5w5s) and 5-way 1-shot (5w1s). For better comparison, we set the number of new classes to 5 for both configurations (5n), denoted as nnew, with each class containing 15 images as the query set. Moreover, we initialize a real-time inference evaluation scenarios, which are in line with the objectives enabling the agent to freely switch between categorizing known and clustering novel classes. It is worth noting that for the real-time inference scenario, only one image from an individual class is allowed in the query set per episode.

A vision transformer [Dosovitskiy et al., 2021] (ViT-B-16) pre-trained on ImageNet [Krizhevsky et al., 2012] with DINO [Caron et al., 2021] is used for the feature extraction. Specifically, the outputs of [CLS] token are treated as feature representation which is different from the use of a projection head that has the potential to introduce more biases. The initial learning rate is set to 0.01.

Evaluation Protocol. We assess the performance of the proposed new setting by measuring the accuracies of three folders, they are visible, new classes and overall precision. Concretely, it uses ˆ YAll, ˆ YOld and ˆ YNew = ˆ YAll \ ˆ YOld to represent the predictions of examples from all, support set and new classes, respectively. Then, the metric for assessing new classes, commonly employed in the GCD approach, has been adapted to suit the FSNCD context. Formally,

where MNew = | ˆ YNew|, and P( ˆ YNew) defines how the predicted labels for test samples are matched to the true labels. This matching is achieved by using the Hungarian algorithm which identifies the permutation that minimizes the mismatch between predicted and true labels.

Instead of directly comparing all predictions to the ground truth like GCD, we adopt a different approach. More specifically, we filter out samples from the same class as the support prototypes and then measure the matches between the predicted labels and prototypes by

where pold represents the one-to-one mapping from the label space of support prototypes YOld to ˆ YOld.

FSNCD Baselines. We present the following key benchmark methods as the strongest baselines for comparison with the proposed FSNCD. All methods employed ViT-B-16 pretrained on ImageNet with DINO.

1. ProtoNet [Snell et al., 2017] aims to classify samples into prototypes based on maximum cosine similarity, in contrast, our FSNCD identifies known classes while also considering how to discover novel classes.
2. OCD [Du et al., 2023] attempts to enhance the generalizability of GCD by using hash codes derived from disentangled features, while our FSNCD exploits a more general feature space to solve analogous generalization problems.
3. AutoNovel [Han et al., 2020] uses feature ranking to determine whether a given sample belongs to positive pair, while we further extend its indexing ideas to the support prototypes. We use the two closest prototypes as category labels.
4. SimGCD [Wen et al., 2023] attempts to utilize parametric classifier to solve GCD problem. Each episode of FSNCD can be regarded as a GCD problem with an extremely scarce sample size. We use the weights from Phase 1 and fine-tune using SimGCD to discover novel categories.

(4) GCD [Vaze et al., 2022a] proposes to estimate the number of novel categories with accuracy on labeled samples, and discover categories with semi-supervised K-means. We treat each episode as a GCD task, performing estimation and clustering to discover novel categories.

4.2 Main Results

Table 3 compares method performance across five datasets. We evaluate "old class" accuracy (support set samples) and "new class" accuracy (novel query set categories). ProtoNet fails to recognize new classes due to its forced classification into support set categories. Among clustering-based methods, GCD employs semi-supervised K-means for category estimation but struggles with coarse-grained datasets. Our method eliminates category number pre-estimation and achieves state-of-the-art performance, showing 9% (SHC) and 13% (UKC) average old-class accuracy drops versus ProtoNet, yet delivering 5% (SHC) and 10% (UKC) overall accuracy gains over GCD.

OCD exhibits consistent performance across tasks due to its overly strict hash code categorization (12-bit codes allow up to 212 classes) and underutilization of support feature distributions. While increasing support samples improves hash code precision as noted in [Du et al., 2023], its ultra-fine category division remains fundamentally limited.

RankStat achieves optimal performance when encoding the top two ranks but limits the number of categories to 20, showing strong retention of classification capability for old classes as expected. Its strict partitioning of feature space into 20

regions based on support samples slightly reduces labeling effectiveness for new classes.

We further conducted tests for real-time inference. As shown in Table 4, OCD easily identifies a sample as a new class, but it also tends to misclassify a substantial number of old classes as new. Although OCD achieves high accuracy in new class discovery, its utility is limited, indicating an excessive inclination toward categorizing instances as new classes. FSNCD with the SHC method achieves a more balanced performance in real-time inference, while FSNCD with the UKC exhibits lower capability in discovering new classes during real-time inference but still maintains excellent performance on old classes.

As shown in Table 5, OCD struggles with large-scale dataset annotation due to its dispersed category distribution, resembling On-the-fly Category Discovery in accuracy. In contrast, UKC leverages sufficient samples to better capture data distributions, achieving superior performance across multiple metrics. Notably, discrepancies between Table 3 and Table 5 are attributed to differing query sample sizes. Specifically, using centroids from small batches to classify large datasets enhances performance, aligning Cosine-trained models with Euclidean clustering. Additionally, in traditional GCD tasks, we found that the strategy of clustering and classification can significantly imporve performance. In extreme cases with limited query samples, it becomes challenging to determine whether a sample belongs to a new category, which is an inherent challenge in FSNCD.

4.3 Ablation Studies

To validate the model's performance across various scenarios, we compared its performance under different settings. For more details on related parameter studies, please refer to the supplementary materials.

Quantity of Query. Due to the discovery of novel categories relying on clustering results, the model may be more sensitive to the distribution of data. Simultaneously, to ensure real-time reasoning capability, we investigated the impact of query quantity on model metrics. Initially, we set the task as 5w5s5n.

Fig. 3 illustrates the accuracy variation with the number of query samples in each class using the 5w5s configuration. The accuracy of UKC change curve indicates that as the number of query samples in each class increases, the data distribution tends to be more reasonable, leading to a continuous improvement. Conversely, due to the weak dependence of hierarchical clustering on data distribution, the accuracy of the SHC based method is more stable.

Effects of Different Settings. In response to distinct task configurations, we conducted further examinations on the outcomes associated with three specific task settings: (1) 5way 5-shot 20-new, (2) 10-way 5-shot 20-new, and (3) 10way 5-shot 40-new, and take 15 query images for each category. The results are shown in Table 6. Given that UKC is contingent on the underlying data distribution, the results obtained from UKC exhibit a comparatively stable trend. Our approach demonstrates improvements across all three evaluation metrics as the number of supported sample categories increases. Notably, even with the introduction of additional novel classes, our method consistently maintains a commendable level of accuracy on pre-existing classes. This robust performance underscores the efficacy of our method in handling diverse task settings and accommodating the challenges posed by both an increased number of supported categories and the introduction of new ones.

5 Conclusion

In this paper, we summarize the shortcomings of current Novel Category Discovery (NCD) tasks and Few-Shot Learning (FSL) tasks, considering FSL tasks that are closer to realworld scenarios, where new classes may appear in the query set. To address the aforementioned issues, we propose Fewshot Novel Category Discovery (FSNCD). In the inference stage, we introduce Semi-supervised Hierarchical Clustering (SHC) and Uncertainty-aware K-means Clustering (UKC) through supervised contrastive learning to represent learning in each episode and leverage them to classify old and cluster new classes accurately. We conduct comprehensive experiments on five datasets, validating the model's performance in general settings and its performance in extreme scenarios.

Acknowledgments

This work was partly supported by the National Natural Science Foundation of China (NSFC) under Grant No. 62371235, and partly by the Key Research and Development Plan of Jiangsu Province (Industry Foresight and Key Core Technology Project) under Grant BE2023008-2.