Novel category discovery

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 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 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 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 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 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] 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 2201.02609 tab. 2; CUB 51.3, Stanford Cars 39.0, Herbarium19 35.4 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 2201.02609 tab. 5. Card: Generalized Category Discovery.

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.

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.

# 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

# 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

# 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 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 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 2201.02609 §4.1.
• Headline gain over UNO+. The text states +9.3 points (11.5%) on the generic datasets 2201.02609 §4.2. The paper does not define how the baseline is aggregated. Averaging the three generic datasets in 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 2201.02609 tab. 3.
• Estimated class count. The printed error column in 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 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 2201.02609 app. E.

Papers

• Generalized Category Discovery: introduces the setting without the NCD assumptions, and the contrastive-feature and semi-supervised k-means method with a labelled-accuracy search for k.