---
kind: concept
slug: novel-category-discovery
title: Novel category discovery
summary: >-
  Labelling unlabelled data that may mix known and new classes when the number of classes is unknown. One paper so far: Generalized Category Discovery clusters contrastively fine-tuned ViT features with semi-supervised k-means, pins labelled images to their classes, and picks k by labelled accuracy. Trade-off: choosing k needs labels, and fine-grained or long-tailed data scores much lower.
tags: [novel-category-discovery, category-discovery, open-world, semi-supervised-learning, clustering]
papers: ["2201.02609"]
related: [semi-supervised-learning, contrastive-learning, self-supervised-learning, vision-transformer]
status: draft
updated_at: 2026-10-18
---

## Overview

The task is to give a label to every unlabelled example when some labelled
examples are available. In the classic novel category discovery (NCD) setting,
every unlabelled example comes from a class that has no labels, and the number of
those classes is known [arxiv:2201.02609 §1, §3.3]. The variant covered here
drops both assumptions. The unlabelled set may mix examples of labelled and new
classes, and the total number of classes is not given [arxiv:2201.02609 §1, §3].

The invariant the method keeps is that labelled examples keep their labels and
unlabelled examples are grouped by similarity in a learned feature space. A
parametric classification head is avoided, because the paper argues it overfits
the labelled classes and handles unlabelled ones poorly [arxiv:2201.02609 §3.1].

Only one card in this wiki covers this slug, so the variants below are the
parts of one method. No alternatives are summarised yet.

## Variants

### Contrastive features with semi-supervised k-means

The method has three parts. First, a ViT-B/16 starting from self-supervised DINO
weights is fine-tuned with an unsupervised contrastive loss on all images and a
supervised contrastive loss on labelled images, mixed with weight λ = 0.35
[arxiv:2201.02609 §3.1.1, §4.1]. Second, labels are assigned by k-means on the
[CLS] feature. Each labelled class gets a centroid from its labelled examples,
labelled examples stay in their class, and unlabelled examples go to the nearest
centroid [arxiv:2201.02609 §3.1.2]. Third, the number of classes is estimated by
clustering the whole set for each candidate k and keeping the k that maximises
accuracy on the labelled subset, searched with Brent's algorithm over
[|Y_L|, 1000] [arxiv:2201.02609 §3.2, §4.1].

Reported "All" clustering accuracy on the paper's own splits: CIFAR10 91.5,
CIFAR100 73.0, ImageNet-100 74.1 [arxiv:2201.02609 tab. 2]; CUB 51.3, Stanford
Cars 39.0, Herbarium19 35.4 [arxiv:2201.02609 tab. 3]. These are author-reported.
In the ablation on CIFAR100, plain DINO features with k-means reach 52.0 All,
and the full method reaches 73.0 [arxiv:2201.02609 tab. 5]. Card:
[Generalized Category Discovery](/papers/2201.02609).

## When to use which

Only one variant is covered, so the table compares the situations this method
has been evaluated on against the situations it has not.

| Situation | Use | Why |
|---|---|---|
| Labelled and unlabelled data mix known and new classes, and the class count is unknown | Contrastive features with semi-supervised k-means | This is the setting the paper evaluates [arxiv:2201.02609 §1, §3] |
| Unlabelled data is all new classes and k is given | Not covered here. The card reports results only in the mixed, unknown-k setting; the NCD methods it adapts are run as baselines there [arxiv:2201.02609 §3.3, §4.2] | No card covers classic NCD yet |
| Fine-grained or long-tailed classes | Expect lower accuracy. The fine-grained and Herbarium19 results are well below the generic datasets [arxiv:2201.02609 tab. 2, tab. 3] | CUB 51.3, Stanford Cars 39.0 and Herbarium19 35.4 All accuracy |
| No labels at all, or labels only for some examples | Choosing k needs labelled accuracy, so at least some labels are required [arxiv:2201.02609 §3.2] | The k search scores labelled examples only |
| Labelled and unlabelled data come from different domains, or data arrives as a stream | Not covered. The method assumes no domain shift and does not handle streaming data [arxiv:2201.02609 app. G] | Stated limitations |
| Limited compute for training | Budget for fine-tuning a ViT-B/16 for 200 epochs with batch size 128 [arxiv:2201.02609 §4.1] | Training schedule as reported |

## Implementation sketch

The steps below are the common core of the method. The paper's loss weighting,
temperature and clustering details are partly unstated, and the comments say
where.

```pseudocode
# Batch loss mixing unsupervised and supervised contrastive terms  [eq. 3]
# Input:  z, z_prime (B, d) two augmented views; labels (B,), -1 if unlabelled
# Temperature tau is not stated in the paper  [eq. 1] [eq. 2]
def gcd_loss(z, z_prime, labels, tau, lam=0.35):
    # Unsupervised term over every image, summed over the batch  [eq. 1]
    loss_u = info_nce(z, z_prime, tau)
    # Supervised term over labelled images only  [eq. 2]
    mask = labels >= 0
    loss_s = supcon(z[mask], labels[mask], tau)
    # Mix the two terms  [eq. 3]
    return (1 - lam) * loss_u + lam * loss_s
```

```pseudocode
# Semi-supervised k-means over the [CLS] features  [§3.1.2] [app. B]
# Input:  features (N, d); labels (N,), -1 if unlabelled; k
# Output: cluster index per image (N,)
def semi_supervised_kmeans(features, labels, k):
    # One centroid per labelled class, initialised to its 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:
        # Unlabelled images go to the nearest centroid  [§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]
        # Each centroid becomes the mean of its members  [app. B]
        centroids = mean_per_cluster(features, assignment)
    return assignment
```

```pseudocode
# Estimate the number of classes k  [§3.2] [§4.1] [app. C]
# Input:  DINO features (N, d) for all of D; labels (N,)
# Output: estimated k
def estimate_k(features, labels, num_labelled):
    def labelled_accuracy(k):
        # Cluster the whole set, score labelled images only  [§3.2]
        clusters = kmeans(features, k)
        return matched_accuracy(clusters[labels >= 0], labels[labels >= 0])
    # Brent's search over [|Y_L|, 1000]  [§4.1]
    return brent_maximise(labelled_accuracy, num_labelled, 1000)
```

The distance metric, whether features are normalised before clustering, and the
k-means convergence test are not stated [arxiv:2201.02609 §3.1.2].

## Contradictions

Both sides are given; the wiki does not resolve them.

- **Fine-tuning scope.** The method section says the representation is
  fine-tuned on the target data [arxiv:2201.02609 §3.1.1]. The experiment section
  says only the final transformer block is fine-tuned, with learning rate 0.1
  and cosine decay [arxiv:2201.02609 §4.1].
- **Headline gain over UNO+.** The text states +9.3 points (11.5%) on the generic
  datasets [arxiv:2201.02609 §4.2]. The paper does not define how the baseline is
  aggregated. Averaging the three generic datasets in
  [arxiv:2201.02609 tab. 2] against UNO+ gives about +10.1 points and +14.5%
  (this is a calculation from the table, not a figure the paper prints). The
  fine-grained figure (+8.9 points, +27.0%) does reproduce from
  [arxiv:2201.02609 tab. 3].
- **Estimated class count.** The printed error column in
  [arxiv:2201.02609 tab. 4] does not match the estimated and true counts in the
  same table. Recomputing from the counts gives different percentages for CUB,
  Stanford Cars and Herbarium19. The text's average of 18.9% matches the
  recomputed values [arxiv:2201.02609 §4.3].
- **Evaluation protocol.** The paper computes one Hungarian match over all
  unlabelled data and reads Old and New accuracy afterwards. The NCD literature
  matches Old and New separately, so numbers are not directly comparable
  [arxiv:2201.02609 app. E].

## Papers

- [Generalized Category Discovery](/papers/2201.02609): introduces the setting
  without the NCD assumptions, and the contrastive-feature and semi-supervised
  k-means method with a labelled-accuracy search for k.