Generalized Category Discovery

In plain words

Most image classifiers assume that every picture they will ever see belongs to a category they were trained on. Real collections are messier. Some pictures have labels, some do not, and the unlabelled ones may show things that were never labelled at all. The task this paper calls Generalized Category Discovery is to put a label on every unlabelled picture, whether it shows a known kind of object or a new one, without being told how many kinds exist.

The method avoids training a classifier head, because a head trained on the labelled kinds tends to overfit them and has no obvious way to handle new kinds. Instead it learns image features with a contrastive objective, which pulls two augmented views of the same picture together, and it pulls labelled pictures of the same kind together too. Then it simply clusters the features. Labelled pictures are forced into the cluster of their known label, and the unlabelled ones fall into whichever cluster they are nearest to, including clusters for new kinds.

The number of kinds is not known in advance, so the paper also proposes a way to estimate it. It runs clustering with different cluster counts and keeps the count that gives the best accuracy on the labelled pictures, where the true labels are available.

TL;DR

Clustering-based recognition for the open-world case where unlabelled data mixes known and new classes §1. Backbone: ViT-B/16 with DINO self-supervised ImageNet weights §3.1.1. Training: noise-contrastive loss on all images plus supervised contrastive loss on labelled images, mixed with λ = 0.35 eq. 1 eq. 2 eq. 3 §4.1. Inference: semi-supervised k-means on the [CLS] feature, with labelled images pinned to their classes §3.1.2. Unknown k is found by maximising labelled-set accuracy with Brent's algorithm §3.2 §4.1. All results are author-reported on the paper's own splits. No code link was verified for this card (see Paper vs code).

Problem

Standard image classification assumes all test images come from the training classes. Novel category discovery (NCD) allows new classes at test time, but assumes every unlabelled image comes from a new class and that the number of classes is known §1 §3.3. The setting here drops both assumptions: the unlabelled set may mix images of labelled and unseen classes, and the number of classes is not given §1 §3.

The authors also argue that parametric classification heads trained on labelled data overfit the labelled classes and handle unlabelled classes poorly, since they must be trained from scratch and receive noisy pseudo-labels for the unlabelled images §3.1. Existing NCD methods share this weakness, and the paper shows that adapted NCD baselines overfit the labelled classes in this setting §1 §4.2.

Method

Setup §3

The training set is split into a labelled part D_L (images with labels from the label set Y_L) and an unlabelled part D_U, whose labels come from Y_U, with Y_L a subset of Y_U. The model never sees D_U labels in training. A labelled validation set D_V uses the labelled classes only and is used for model selection §3.

Step 1: Representation §3.1 §3.1.1 §4.1

Start from a ViT-B/16 backbone pre-trained with DINO self-supervision on ImageNet without labels §3.1.1. The authors use self-supervised rather than supervised ImageNet weights, to keep the labelled-set setting consistent with a finite labelled set §3.1.1.

Fine-tune on the target data with two losses. Let x_i and x_i' be two random augmented views of the same image in mini-batch B. Write z_i = φ(f(x_i)), where f is the backbone and φ an MLP projection head. The unsupervised loss uses every image, labelled or not §3.1.1:

\mathcal{L}^{u}_{i} = - \log \frac{\exp(\mathbf{z}_i \cdot \mathbf{z}_i' / \tau)}{\sum_{n} \mathbb{1}_{[n \ne i]} \exp(\mathbf{z}_i \cdot \mathbf{z}_n / \tau)} eq. 1

The supervised contrastive loss uses only labelled images. N(i) is the set of other images in the batch that share the label of image i §3.1.1:

\mathcal{L}^{s}_{i} = - \frac{1}{|\mathcal{N}(i)|} \sum_{q \in \mathcal{N}(i)} \log \frac{\exp(\mathbf{z}_i \cdot \mathbf{z}_q / \tau)}{\sum_{n} \mathbb{1}_{[n \ne i]} \exp(\mathbf{z}_i \cdot \mathbf{z}_n / \tau)} eq. 2

The total batch loss weights the two terms with λ. The sum runs over all images in B for the first term and over the labelled subset B_L for the second §3.1.1:

\mathcal{L}^{t} = (1 - \lambda) \sum_{i \in B} \mathcal{L}^{u}_{i} + \lambda \sum_{i \in B_L} \mathcal{L}^{s}_{i} eq. 3

Here τ is a temperature, and §4.1 states λ = 0.35. Labels enter only through the contrastive pull, not through a cross-entropy head, so labelled and unlabelled data are treated alike §3.1.1.

Step 2: Label assignment by semi-supervised k-means §3.1.2 app. B

Cluster in the feature space of the fine-tuned model, not in the projection head. At test time the features are the output [CLS] token of the backbone, and the projection head is discarded §4.1. The clustering runs as follows:

1. Create one centroid per labelled class, initialised as the mean of that class's labelled features §3.1.2.
2. Create |Y_U| − |Y_L| further centroids from unlabelled data with k-means++, constrained to the labelled centroids §3.1.2.
3. Repeat until convergence: labelled images are assigned to the cluster matching their ground-truth class; unlabelled images go to the nearest centroid; each centroid is then recomputed as the mean of its members §3.1.2 app. B.

# Semi-supervised k-means over features  [§3.1.2] [app. B]
# Input:  features (N, d); labels (N,) with -1 if unlabelled; k
# Output: cluster index per image (N,)

def semi_supervised_kmeans(features, labels, k):
    # One centroid per labelled class: the class mean  [§3.1.2]
    centroids = class_means(features, labels)
    # Extra centroids for unseen classes via k-means++  [§3.1.2]
    centroids = add_kmeanspp(centroids, features[labels < 0], k)
    while not converged:
        # Nearest centroid for every image  [§3.1.2]
        assignment = nearest_centroid(features, centroids)
        # Labelled images keep the cluster of their class  [§3.1.2]
        assignment[labels >= 0] = labels[labels >= 0]
        # Centroids become the means of their members  [§3.1.2]
        centroids = mean_per_cluster(features, assignment)
    return assignment

The distance metric and the convergence test are not stated.

Step 3: Estimating the number of classes §3.2 §4.1 app. C

Assume that clustering accuracy on the labelled subset peaks when k equals the true number of classes. The method therefore clusters the whole dataset D for a candidate k, scores only the labelled images with the Hungarian-matched accuracy, and searches for the best k with Brent's algorithm on the range [|Y_L|, 1000] §3.2 §4.1. The features used for this search are DINO features extracted from each benchmark §4.1. The appendix plots the labelled-subset accuracy against k and reports it as roughly bell-shaped, peaking near the true class count app. C.

# Estimate the number of classes k  [§3.2] [§4.1] [app. C]
# Input:  features (N, d) from DINO on all of D; labels (N,)
# Output: estimated k

def estimate_k(features, labels, num_labelled):
    def labelled_accuracy(k):
        # Cluster all of D, score only labelled images  [§3.2]
        clusters = kmeans(features, k)
        # Hungarian-matched accuracy on D_L  [§3.2] [eq. 4]
        return matched_accuracy(clusters[labels >= 0], labels[labels >= 0])
    # Brent's search, range [|Y_L|, 1000]  [§4.1]
    return brent_maximise(labelled_accuracy, num_labelled, 1000)

Baselines adapted to the setting §3.3 §4.1

• RankStats+ §3.3: one head over all classes. The first |Y_L| outputs are trained with cross-entropy on labelled data. The whole head is trained with binary cross-entropy on pairwise pseudo-labels for unlabelled data.
• UNO+ §3.3: labelled and unlabelled heads are concatenated, and the unlabelled head's predictions on one view supervise the other views in a SwAV-like scheme.
• k-means on raw DINO features is an extra reference §4.2.

The paper follows the original baseline implementations and schedules as far as possible §4.1.

Evaluation protocol §4.1 app. E

Clustering accuracy uses the best one-to-one match of cluster indices to labels, found by the Hungarian algorithm over all of D_U §4.1 eq. 4. "Old" and "New" accuracies are read off afterwards from the matched predictions.

ACC = \max_{p \in \mathcal{P}(\mathcal{Y}_U)} \frac{1}{M} \sum_{i=1}^{M} \mathbb{1}\{y_i = p(\hat{y}_i)\} eq. 4

Here M = |D_U| and P(Y_U) is the set of permutations of the unlabelled-set labels §4.1.

Hyperparameters

Results

Author-reported. Setup: ViT-B/16 DINO backbone; the results use the paper's own splits and the model's [CLS] features with semi-supervised k-means §4.1 §3.1.2. The "All" column is clustering accuracy over all of D_U; "Old" covers classes in Y_L and "New" covers classes in Y_U \ Y_L §4.1 app. A. Dataset sizes are in tab. 1.

Generic object datasets tab. 2

Fine-grained SSB datasets and Herbarium19 tab. 3

Estimated number of classes tab. 4: ground truth vs. estimate (CIFAR10 10 vs 9; CIFAR100 100 vs 100; ImageNet-100 100 vs 109; CUB 200 vs 231; Stanford Cars 196 vs 230; Herbarium19 683 vs 520). The table's error column is listed under Pitfalls.

Ablation tab. 5 (CIFAR100 All/Old/New | Herbarium19 All/Old/New)

Row 1 uses a ResNet-50 backbone §4.4. The text credits the contrastive fine-tuning with a further 19 points on CIFAR100 and 16 on Herbarium19 (rows 2 to 5), and semi-supervised k-means with 2 and 7 points on CIFAR100 and Herbarium19 (rows 5 to 6) §4.4.

Summary of headline claims §4.2: the authors state that the method beats the baselines by 9.3 points (11.5%) on the generic datasets and by 8.9 points (27.0%) on the fine-grained ones, both on "All" accuracy. The fine-grained figure reproduces from tab. 3 with UNO+ as the reference, but the generic one does not (see Pitfalls).

Other results: on FGVC-Aircraft (SSB split), the method reaches 45.0 All, 41.1 Old and 46.9 New against UNO+ 40.3 / 56.4 / 32.2 app. D. The paper reports that its k-estimate averages 18.9% discrepancy on the fine-grained sets and up to 10% on the generic sets §4.3.

Paper vs code

Code not yet checked. The paper links a project page for code, https://www.robots.ox.ac.uk/~vgg/research/gcd, from the abstract §abstract, and the appendix refers to "the open-source code for this project" app. A. I did not open that page or search GitHub: the WebFetch and network permissions were not granted in this run. No repository is recorded in this card until one is verified as belonging to the authors. Once found, compare its loss weights, the semi-supervised k-means loop, the k search and the evaluation code against Steps 1 to 3 above.

Pitfalls

• Unstated training details. Temperature τ, optimiser, weight decay, momentum, warm-up, augmentation list, projection head architecture and convergence test for k-means are not stated. The card does not fill them from general knowledge.
• Fine-tuning scope is inconsistent within the paper. §3.1.1 says the representation is fine-tuned on the target data. §4.1 says only the final transformer block is fine-tuned, with a 0.1 learning rate and cosine decay.
• Empty N(i) in eq. 2. If an image has no other labelled image of its class in the batch, the 1/|N(i)| normalisation divides by zero. The paper does not say how this case is handled. The batch sampler (is it class-balanced?) is also not stated.
• Scale of eq. 3. The loss sums over the batch rather than averaging. The effect of λ and the learning rate depends on that choice, and the paper does not say whether an implementation divides by the batch size.
• Clustering metric and feature normalisation. The distance used in k-means is not stated, and whether features are L2-normalised before clustering is not stated either. The contrastive loss uses dot products divided by τ, which ties its scale to the normalisation.
• k estimation depends on labels. The k search uses labelled-set accuracy, so it needs ground-truth labels for at least some images. The paper says it uses DINO features, not the fine-tuned model §4.1. Whether the Hungarian match in that search is computed over all clusters or only the labelled ones is not stated.
• Table 4 error column does not match its counts. Recomputing |estimate − truth| / truth gives CUB 15.5% (printed 16%), Stanford Cars 17.3% (printed 15%) and Herbarium19 23.9% (printed 28%). The text's fine-grained average of 18.9% matches the recomputed values, not the printed column. Use the counts, not the printed percentages.
• Headline percentages are not all reproducible from the tables. Against UNO+ averaged over the three generic datasets, the tables give about +10.1 points and +14.5%. The paper states +9.3 points and +11.5%. The baseline aggregation is not defined in the text. The fine-grained figures do reproduce (+8.9 points, +27.0%).
• Evaluation differs from NCD papers. The authors compute the Hungarian match once over all of D_U and read Old and New accuracy afterwards. The NCD literature, including the RankStats and UNO code they compare against, matches Old and New separately, which can reuse the same cluster twice. Numbers from NCD papers are not directly comparable app. E.
• Splits and class counts. CIFAR100 uses 80 Old classes, not 50% app. A. Herbarium19 Old classes are sampled at random because of its long tail app. A. Splits for SSB follow the Semantic Shift Benchmark app. A.
• No variance reported. The text gives no seeds, repeats, standard deviations or hardware. Differences of one or two points cannot be judged as significant from the paper alone.
• Domain shift. The method assumes no domain shift between labelled and unlabelled images, and does not handle streaming data app. G.
• Table and figure numbers are derived from the LaTeX source order (tables 1 to 5, figures 1 to 3 in the main text). Check them against the PDF before citing a table number in public text.

Lineage

• Builds on: DINO self-supervised ViT pre-training §3.1.1, noise-contrastive loss §3.1.1, supervised contrastive loss §3.1.1, k-means++ seeding §3.1.2.
• Adapts as baselines: RankStats (Han et al.) and UNO (Fini et al.) from novel category discovery §3.3.
• Compared against: RankStats+, UNO+ and k-means on DINO features §4.2.
• Benchmarks: Semantic Shift Benchmark (CUB, Stanford Cars, FGVC-Aircraft) and Herbarium19 §4.1.
• Superseded by: not known from content in this wiki.