Arbor: When Labels Are Not Coarsened at Random

Faisal Mohammad, Mohamed YounisarXiv 2026 · arXiv

TL;DR

Arbor is a new framework for training image classifiers on datasets with mixed-granularity labels, specifically addressing cases where some classes are "novel" and never receive fine-grained labels. By explicitly modeling the label coarsening process with a virtual novel class and a logistic gate, Arbor significantly improves the detection of these novel classes without sacrificing accuracy on known ones.

What Problem Does This Paper Address?

When merging datasets, researchers often encounter a "mixed granularity" problem: some images have specific labels (e.g., "Container Ship"), while others only have general ones (e.g., "Cargo Ship"). Standard machine learning models assume that labels are coarsened at random (CAR)—meaning every specific type of cargo ship is equally likely to be labeled simply as "Cargo Ship."

However, in the real world, this assumption is often violated. A specific class, like "Bulk Carrier," might appear only in a dataset that uses coarse labels. In this scenario, the model never sees a "Bulk Carrier" label. During standard training, the model will mistakenly learn to assign "Bulk Carrier" images to its known siblings (like "Container Ship") because there is no mechanism to reward the model for saying "I know this is a Cargo Ship, but I don't know the specific type."

The problem of incomplete data and novel classes in a taxonomy.

Methods

The authors propose Arbor, which models the coarsening process directly. Key components include:

  • Virtual Novel Classes: For every superclass in a taxonomy that contains a novel class, Arbor adds a "virtual novel class" representing an "unknown type" (e.g., "Cargo Ship, unknown type").
  • Novelty Gates: Instead of a single flat softmax, Arbor uses a logistic gate for each affected superclass. This gate ($\nu_y$) decides how to split the probability mass between the virtual novel class and the known fine-grained classes.
  • Coarsening Likelihood: The model is trained using a specific likelihood objective that accounts for how labels become coarse. The authors theoretically prove that at its optimum, this gate performs the Elkan–Noto correction, a standard technique from positive-unlabeled (PU) learning.
  • Tree-Tied Prototypes: To leverage the hierarchical structure of the data, Arbor uses a classifier where prototypes for each class are tied to their position in the taxonomy tree.
Arbor's architecture using tree-tied prototypes and a novelty gate.

Datasets

The authors evaluated Arbor across several challenging benchmarks:

  • Standard Fine-Grained Datasets: Stanford Cars, CUB-200-2011 (birds), CIFAR-100, and FGVC-Aircraft.
  • Large-Scale Taxonomy: iNaturalist-2019, featuring over 1,000 species.
  • Real-World Merge: A merge of CUB and NABirds, where coarsening probabilities are determined by the natural distribution of community-provided labels.

Key Insights and Ideas

  • Novelty as a PU Problem: The paper shows that a class without fine-grained labels turns its superclass into a positive-unlabeled problem. Arbor treats the known classes as "positives" and the novel classes as the "unlabeled" portion.
  • Decoupling Learning: A critical finding is that Arbor's gate decouples the task of learning class features from the task of learning novelty. This prevents coarse labels from "flattening" the probabilities of known siblings during training.
  • Forward vs. Post-hoc Correction: While post-hoc methods like Elkan-Noto can be applied after training, Arbor shows that training the correction into the classifier (forward correction) leads to better performance, especially when fine-grained labels are scarce.
  • Inductive Bias of Trees: Using tree-structured prototypes provides a helpful inductive bias that improves known-class accuracy when data is limited.

Key Results

Arbor consistently outperforms both standard classification baselines and specialized novelty detection methods.

  • Novel Class Recognition: On the Cars, CUB, and Aircraft datasets with 90% coarse labels, Arbor correctly identifies 76–85% of novel-class images. In contrast, standard hierarchical classifiers often find fewer than 17%.
  • iNaturalist-2019: Arbor improved novel-class accuracy from 46% (the strongest baseline) to 68%.
  • Balanced Performance: As shown in the radar plot below, Arbor stays near the "best of both worlds," maintaining high accuracy for known classes while excelling at finding novel ones.
Figure 1. Classification baselines keep known classes but find few novel ones, and novelty baselines do the reverse. Arbor is close to the better of the two on every axis. The radial axis starts at 20%. Right half: known-class leaf accuracy, the top-1 ac- curacy over leaves, which does not depend on the operating point. Left half: novel-class accuracy, the share of novel-class images as- signed to their superclass. Each protocol axis (Sec. 4.1) averages Cars, CUB, CIFAR-100 and Aircraft. The bottom pair is the real CUB–NABirds merge (Tab. 19).
Figure 2. Novel-class accuracy across operating points, against the exact-class rate on known-class images, main protocol, three seeds; dot: Arbor’s operating point. Arbor’s curve is the highest over most of the range on Cars, CUB and Aircraft and over two stretches on CIFAR-100 (intervals in Sec. D).

Limitations and Future Work

  • Image-Dependent Coarsening: Arbor assumes the probability of a label being coarse depends only on its class. In reality, "hard" or blurry photos might be more likely to receive coarse labels. Modeling image-dependent coarsening is a suggested next step.
  • Complete Taxonomies: The method assumes the taxonomy already lists every class, even if some have no labels. It does not yet handle "unseen" classes that are entirely absent from the predefined hierarchy.
  • CIFAR-100 Gap: The authors noted a small performance gap on CIFAR-100, likely due to the shared embedding between the novelty gate and the classifier, suggesting room for architectural refinement.

Summary updated

Abstract

Merging datasets labelled at different levels of a taxonomy leaves some images with only a coarse label, and some classes with no fine-grained label at all. Standard training scores a coarse label by the total probability of the classes under it. Coarse labels name superclasses, and the standard objective is exact only when every class within a superclass is equally likely to receive a coarse label. We call a class novel if it is never labelled finely, and known otherwise. A novel class violates the assumption, and the classifier assigns its images to a known sibling. We propose Arbor, which models how labels become coarse. In each superclass with a novel class, Arbor adds a virtual novel class, and a logistic gate divides the superclass's probability between it and the known classes. The gate is trained with the likelihood of the observed labels under this model, the coarsening likelihood. We prove that at its population optimum the gate equals the Elkan-Noto correction of positive-unlabelled learning, and show that training the correction into the classifier improves on applying it after training. Across Cars, CUB and Aircraft with 90% coarse labels, Arbor correctly assigns 76-85% of novel-class images to their superclass, more than hierarchical classifiers, hierarchical novelty detection and the Elkan-Noto correction. Its top-1 accuracy over the leaf classes on known-class images is within 1.6 points of the best baseline, although its final predictions return the superclass more often. On the more challenging iNaturalist-2019 benchmark, Arbor improves novel-class accuracy from 46% (uniform target, the strongest baseline) to 68%.
BibTeX
@misc{mohammad2026arbor,
  author = {Faisal Mohammad and Mohamed Younis},
  title = {{Arbor: When Labels Are Not Coarsened at Random}},
  year = {2026},
  eprint = {2611.15311},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.15311},
}
Figure