Beyond Known Clusters: Probe New Prototypes for Efficient Generalized Class Discovery

Ye Wang, Yaxiong Wang, Yujiao Wu, Bingchen Zhao, Xueming QianarXiv 2024 · DOI · arXiv

Introduction

Generalized Class Discovery (GCD) is a critical task in open-world machine learning, where a model must categorize data from both known classes (seen during training) and novel classes (unseen) within an unlabeled pool. Existing "one-stage" methods typically rely on clustering algorithms like $k$-means to identify class prototypes. However, these approaches suffer from two primary limitations: the "shrunk prototype" problem and significant computational overhead.

The "shrunk prototype" problem occurs when clustering algorithms conservatively estimate fewer clusters than actually exist, leading to "blurred" semantics where multiple distinct novel classes are collapsed into a single prototype. Furthermore, clustering the entire combined labeled and unlabeled dataset becomes a bottleneck as data scales.

Comparison of existing one-stage methods vs. the proposed PNP framework. PNP introduces potential prototypes to capture classes missed by initial clustering.

The Probing New Prototype (PNP) Framework

To address these challenges, we propose the Probing New Prototype (PNP) framework. PNP decouples the discovery process and introduces learnable "potential prototypes" to recover missing classes.

1. Unlabeled Data Oriented Fast Clustering

Unlike traditional methods that cluster the full dataset, PNP focuses exclusively on unlabeled data. It utilizes Infomap, a fast graph-based clustering algorithm, to generate an initial set of cluster prototypes. This targeted approach significantly reduces the search space and improves efficiency.

2. Potential Prototype Probing

To counteract the underestimation of class counts, PNP injects "potential prototypes"—extra, randomly initialized learnable tensors. These act as placeholders for novel classes that the initial clustering phase might have overlooked.

3. Self-Distilled Prototype Learning

Since ground truth labels for novel classes are unavailable, PNP employs a Student-Teacher framework. A "Teacher" model generates soft probability distributions representing how instances relate to the expanded set of prototypes. The "Student" model is then trained to match these predictions, effectively refining the potential prototypes into meaningful class centers through self-distillation.

The PNP architecture, featuring fast clustering, potential prototype expansion, and a self-distillation pipeline.

Experimental Evaluation

PNP was evaluated across seven diverse benchmarks, including generic datasets (CIFAR10/100, ImageNet100) and fine-grained datasets (CUB200, Stanford Cars, FGVC-Aircraft, Herbarium 19).

Performance and Efficiency

PNP achieved state-of-the-art results, notably outperforming existing methods on the Stanford Cars dataset by 9.7% in overall accuracy. On the large-scale Herbarium 19 dataset, PNP demonstrated a 12x speedup in the clustering stage compared to the previous state-of-the-art (DCCL), reducing processing time from 25 minutes to just 2 minutes.

Class Estimation

Visualization via t-SNE confirms that PNP's probing mechanism discovers a number of clusters much closer to the ground truth. For instance, it identified 183 clusters in a 200-class dataset, whereas standard methods found only 175.

Discussion and Limitations

While PNP excels in complex, fine-grained scenarios, it can occasionally overestimate the number of categories in simpler datasets like CIFAR10, leading to "over-splitting." Additionally, performance is sensitive to the number of neighbors ($k$) used in graph construction. Future research will explore adaptive neighbor selection to enhance robustness across varying data distributions.

Summary updated

Abstract

Generalized Class Discovery (GCD) aims to dynamically assign labels to unlabelled data partially based on knowledge learned from labelled data, where the unlabelled data may come from known or novel classes. The prevailing approach generally involves clustering across all data and learning conceptions by prototypical contrastive learning. However, existing methods largely hinge on the performance of clustering algorithms and are thus subject to their inherent limitations. Firstly, the estimated cluster number is often smaller than the ground truth, making the existing methods suffer from the lack of prototypes for comprehensive conception learning. To address this issue, we propose an adaptive probing mechanism that introduces learnable potential prototypes to expand cluster prototypes (centers). As there is no ground truth for the potential prototype, we develop a self-supervised prototype learning framework to optimize the potential prototype in an end-to-end fashion. Secondly, clustering is computationally intensive, and the conventional strategy of clustering both labelled and unlabelled instances exacerbates this issue. To counteract this inefficiency, we opt to cluster only the unlabelled instances and subsequently expand the cluster prototypes with our introduced potential prototypes to fast explore novel classes. Despite the simplicity of our proposed method, extensive empirical analysis on a wide range of datasets confirms that our method consistently delivers state-of-the-art results. Specifically, our method surpasses the nearest competitor by a significant margin of 9.7% within the Stanford Cars dataset and 12x clustering efficiency within the Herbarium 19 dataset. We will make the code and checkpoints publicly available at https://github.com/xjtuYW/PNP.git.
BibTeX
@misc{wang2024beyond,
  author = {Ye Wang and Yaxiong Wang and Yujiao Wu and Bingchen Zhao and Xueming Qian},
  title = {{Beyond Known Clusters: Probe New Prototypes for Efficient Generalized Class Discovery}},
  year = {2024},
  eprint = {2404.08995},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.08995},
}
Figure