Machine learning is undergoing a paradigm shift from closed-world classification to open-world discovery. In settings like Novel Class Discovery (NCD) and Generalized Category Discovery (GCD), models are deployed into environments where they encounter streams of unlabeled data containing entirely unseen concepts. However, a hidden crutch persists in many of these algorithms: they assume the exact number of new categories ($K$) is known a priori.
As Roy et al. and An et al. point out, real-world deployment cannot rely on human operators to pre-specify this cardinality. If a model expects five new classes but encounters fifty, it will catastrophically merge distinct concepts, destroying its representation space. Conversely, under-estimating or over-estimating the count leads to fragmented or overly coarse groups, a performance gap highlighted in recent category discovery benchmarks (such as the analysis noted in the Correction notice). Unsupervised category count estimation aims to dynamically infer the true number of latent classes directly from the structure of unlabeled data.
The Circular Dependency of Discovery
Why is estimating cluster cardinality so difficult? It presents a classic chicken-and-egg problem: to group data accurately, an algorithm needs to know the resolution (the number of clusters); but to determine that resolution, it must already understand the underlying semantic boundaries of the data.
This challenge spans domains and modalities:
- Natural Language Processing: Discovered word senses (Purandare et al.) and user intents in dialogue systems (Xu et al.) vary wildly depending on context, making fixed cluster counts impractical.
- Computer Vision: Grouping unorganized image collections into visual "families" (Aly et al.; Kinnunen et al.) requires models to discover the category count automatically from raw pixels.
- Structured Data: Identifying latent classes in multi-label learning (Huang et al.) or community detection in graphs (Braun et al.) is bottlenecked when the underlying group cardinality is entirely unknown.
To break this circular dependency, researchers have developed three core intuitive mechanisms: representation-space probing, prototype convergence, and dynamic architectural growth.
Mechanism 1: Probing Self-Supervised Representation Spaces
The first core intuition relies on the structure of modern feature extractors. Instead of learning representations and cluster counts simultaneously from scratch, modern approaches leverage frozen, self-supervised pre-trained models (PTMs). As Liu et al. demonstrate, these PTMs provide a surprisingly robust initial feature space where novel categories naturally form implicit geometric groups, even without explicit class labels.
[Raw Unlabeled Data] ──> [Frozen PTM] ──> [Implicit Geometric Clusters] ──> [Stability Probing (K-Means)] ──> Optimal K
To extract the exact count from this space, algorithms probe the representation layer using iterative clustering and distribution-aware reassignments. For example, Rizve et al. apply clustering algorithms to features derived from self-supervised pre-training, combining K-means with sample reassignment techniques to find the latent structure of novel classes. By evaluating the stability and internal variance of these clusters across different candidate values of $K$—similar to how traditional audio clustering minimizes internal variance to find the number of unique musical keys (Wang et al.)—the system identifies the natural mathematical boundaries of the dataset.
Mechanism 2: Prototype Convergence via Over-Estimation
A more elegant, dynamic strategy avoids trying to guess $K$ perfectly upfront. Instead, the model intentionally over-estimates the number of potential classes and relies on optimization dynamics to collapse the redundant ones.
This behavior is highly effective in prototype-based contrastive learning frameworks. Sun et al. demonstrate that when a model is initialized with an excessive number of cluster prototypes, the contrastive loss forces samples that share underlying semantic features to pull their respective prototypes toward the same representation space.
Initial Over-estimated State:
[Proto 1] [Proto 2] [Proto 3] [Proto 4] [Proto 5]
│ │ │ │ │
└─────┬──────┘ └─────┬──────┘ │
▼ ▼ ▼
Optimized Converged State:
[Cluster A] [Cluster B] [Cluster C]
(Redundant Protos Merge)
Over the course of training, redundant prototypes empty out or merge because they lack distinct data support. The system naturally converges to the true number of underlying clusters. This self-reinforcing convergence removes the penalty for over-estimating, providing a safety net for open-world deployment where the upper bound of novelty is unpredictable.
Mechanism 3: Dynamic Branching (Grow and Merge)
In streaming, incremental, or continuous category discovery scenarios, data arrives sequentially. This means the total number of categories is not static; it grows over time. To handle this, models must dynamically adapt their capacity.
Streaming Data ──> [Novelty Detection] ──> Anomaly Found? ──> YES ──> [GROW: Spawn New Cluster Branch]
│
▼
[MERGE: Consolidate Overlaps]
To resolve the conflict between learning new classes and retaining old ones without knowing the class counts in advance, frameworks use a "branch-and-merge" or "grow-and-merge" strategy. As designed by Zhang et al. and Chen et al., these systems operate in two alternating phases:
- The Growing Phase: The model monitors incoming data streams for out-of-distribution samples or high-uncertainty predictions. When a cluster of unclassifiable data points emerges, the model dynamically spawns a new architectural branch or prototype to capture the novel category.
- The Merging Phase: To prevent an infinite explosion of micro-clusters (over-fragmentation), the model periodically evaluates the statistical overlap between clusters. If two branches share high semantic similarity or cross-attention alignment, they are consolidated into a single class.
By balancing expansion and consolidation, these models autonomously track the cardinality of an evolving environment without requiring manual intervention or human re-labeling.
Key Foundational Work
Knowledge-based segmentation of SAR data with learned priors (2000) — contributed 1 concept elements to this direction.
SenseClusters - Finding Clusters that Represent Word Senses (2004) — contributed 1 concept elements to this direction.