CS Paper Radar

Arbor: When Labels Are Not Coarsened at Random

Faisal Mohammad, Mohamed Younis

cs.CV cs.LG ·submitted 2026-11-11 10:45 UTC · v1
benchmarktheory

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%.

Comment
26 pages, 7 figures, 25 tables. Appendices included

Closest papers

Nearest neighbours by meaning across the whole index.

H$^2$EDL: Hyper Evidential Deep Learning for Hierarchical Classification

cs.LG cs.CV ·2026-08-18 ·Yuanye Liu, Xiahai Zhuang
similarity 0.63
Abstract

Fine-grained recognition often involves hierarchical label spaces, where a model may be confident about a coarse semantic concept while remaining uncertain among its descendant classes. Such structured ambiguity requires uncertainty representations that capture both fine-grained classes and intermediate concepts. However, existing tools each capture only half of it: flat evidential classifiers quantify total ignorance with a single vacuity on the leaf frame, and hierarchical classifiers propagate point probabilities with no notion of evidence. Hyper-opinions would unify the two, but their general form is exponential in the label count, and existing hyper-evidential networks either require composite labels to be supplied in the training data or read them off an unstructured weight pattern, with no principled notion of which composites deserve mass. We observe that the taxonomy itself is the missing hyperdomain. Its subtrees and leaf singletons form a linear-size focal family, and one local Dirichlet opinion per branching node induces every composite mass in closed form. The resulting model, H$^2$EDL, can be interpreted in two complementary ways using the same set of parameters. From a prediction perspective, it functions as a hierarchical classifier that preserves consistency across different levels of the label tree. From a probabilistic perspective, it defines a valid tree-structured hyper-opinion, where the mass assigned to each node represents the belief that reaches that node but does not provide sufficient confidence to further specialize into its descendants. On FGVC-Aircraft and DERM12345, H$^2$EDL reduces calibration error by approximately half compared with cross-entropy baselines, with the improvement becoming more pronounced at deeper hierarchy levels and under larger training budgets.

0.25

Adapting Frozen Promptable Segmenters to User-Defined Taxonomies via Few-Shot Proposal Learning

cs.CV ·2026-11-06 ·Khayrul Islam, Christopher Frederic Miller
hot direction similarity 0.63
Abstract · LLNL-CONF-2026172

Promptable segmenters of the SAM family turn a click or a phrase into an instance mask, so the costly part of a label is now its class. However, each annotation project draws its own class boundary, often through objects these models already know: people from cars, sedans from trucks, one sedan model from another. A generic model's boundary is fixed by its training vocabulary. We present SNAP, an annotation pipeline that learns the project's boundary from the labels the annotator draws anyway. On one frozen SAM2.1 pass per image, we fit a per-project head, SnapHead, that classifies every proposal and refits in seconds after each labeled image. Where SAM 3 is available, the same labels decide class by class whether to keep its boundary or ours. Given the true masks of eight look-alike cell lines, SAM 3 assigns classes at Cohen's kappa = 0.038 and SnapHead at 0.754 (60 labeled images), and when only the class names change, SAM 3 falls to chance and SnapHead's score is unchanged. End to end, with 20 labeled images, SNAP beats a SAM 3 oracle tuned on the evaluation labels on five microscopy projects (0.484 against 0.441 F1), and run unchanged on five held-out datasets, it beats SAM 3 as shipped on four. Our results suggest that frozen foundation features already encode the class boundaries a generic vocabulary misses, and that a project's own labels are enough to read them out.

0.32

Learning What the True Labels Would Teach: Posterior Analytic Class-Incremental Learning with Unlabeled Data

cs.LG cs.CV ·2026-11-16 ·Wei Tang, Tong Wei, Jiahao Zhang, Min-Ling Zhang, Lijie Hu +1 more
positiontheoryhot direction similarity 0.62
Abstract

In class-incremental learning with unlabeled data, each task brings only class names and unlabeled images, so CLIP's zero-shot predictions replace labels. Existing methods train on hard pseudo-labels, but a wrong one gives the true class zero probability, which self-training often confirms. We argue that each image should carry its label posterior, as an analytic classifier trained on posteriors equals the true-label one in expectation. The zero-shot prediction is not this posterior, as its class proportions confound name bias with true imbalance and it ignores other images. We propose Posterior Analytic Class-Incremental Learning (PACIL), which corrects the class prior with a prior selection rule and refines each distribution by a fixed-prior von Mises-Fisher mixture on whitened features. These soft labels train the classifier and replace labels to select its fusion weight with zero-shot CLIP by closed-form leave-one-out cross-validation. We prove that posterior targets minimize the mean-square gap to the true-label prediction and that their argmax widens this gap only through ambiguous images. The fusion weight selected with soft labels loses at most their distance to the posteriors in expected correct decisions. PACIL has the best average incremental accuracy among methods trained without labels on all 18 settings.

0.31

Agnostic Marginal-Nonuniform Learning

cs.LG ·2026-11-09 ·Tanmay Devale, Steve Hanneke, Amirreza Shaeiri
similarity 0.61
Abstract

We study the problem of binary classification in the marginal-nonuniform learning framework in the agnostic setting. In this model, the constants in the learning rate may depend on the marginal distribution of the unlabeled data, but the guarantee must hold uniformly over all conditional distributions of the labels. We also study fine-grained rates. We consider two criteria. (1) The standard agnostic setting, where the learner competes with the best concept in the class. In this setting, an immediate consequence of standard agnostic PAC learning results gives us the optimal rate of $\tfrac{1}{\sqrt{n}}$ for every class $\mathcal{H}$ with finite $\mathrm{VC}(\mathcal{H})$ and shows that arbitrarily slow rates are necessary otherwise. This also gives us the optimal fine-grained rate of $\sqrt{\tfrac{\mathrm{VC}(\mathcal{H})}{n}}$. Therefore, the dependence on the marginal distribution does not help, which is in contrast to the realizable setting. (2) In the relaxed agnostic setting, where the learner competes with $(1+λ)$ times the error of the best concept for a fixed $λ\in (0,1]$, the picture from the realizable setting reappears. We obtain a trichotomy of the achievable optimal rates: exponential rates of the form $e^{-n}$ arise precisely when the class is finite; linear rates of the form $\tfrac{1}{n}$ arise when the class is infinite but $\mathrm{VC}(\mathcal{H})$ is finite; and arbitrarily slow rates occur when $\mathrm{VC}(\mathcal{H})=\infty$. We also obtain the optimal fine-grained rate of $\tfrac{\mathrm{uVCE}(\mathcal{H})}{λn}$, where $\mathrm{uVCE}(\mathcal{H})$ is a recently introduced combinatorial complexity dimension called the uncentered $\mathrm{VC}$-eluder dimension.

0.06

Rethinking Learning from Label Proportions via Moment Matching

cs.LG ·2026-10-15 ·Tianhao Ma, Wei Wang, Yivan Zhang, Dong-Dong Wu, Takashi Ishida +2 more
top venuebenchmarkcode/data similarity 0.61
Abstract · Accepted at NeurIPS 2026

Learning from label proportions (LLP) is a weakly supervised setting where training data are grouped into bags with only bag-level label proportions observed, and the goal is to learn a classifier that predicts labels for individual instances. Recently, a large body of methods has emerged; however, most of them rely on the assumption that instance-label pairs are sampled i.i.d. and randomly assembled into bags, an assumption often violated in real-world scenarios. Our experimental results indicate that these methods perform suboptimally under non-random settings. In this work, we adopt a more realistic assumption: bags are sampled i.i.d., and instance labels are conditionally independent given the instances. Under this setting, we show that the label counts follow a Poisson multinomial distribution. Motivated by this observation, we propose LLP via moment matching (LLP-MM), a simple yet effective approach which leverages multi-order factorial moments as training objectives, encouraging the classifier predictions to match these moments and thereby more fully exploit the underlying statistical structure of the data. Extensive experiments on benchmark datasets under various bag construction strategies demonstrate the effectiveness of our approach while maintaining high computational efficiency. Our code is available at https://github.com/TianhaoMa5/LLP-MM.

0.49

Fundamentals for Binary Classification Under Label Noise

cs.CC cs.LGstat.ML ·2026-11-19 ·Dimitrios I. Diochnos
top venuetheoryhot direction similarity 0.61
Abstract · 59 pages, 6 figures, 3 tables. Preprint of a chapter published in the book Mathematics and Artificial Intelligence (Springer)

This chapter surveys fundamental results for binary classification under label noise. Binary classification under label noise involves training models on datasets where class labels are partially incorrect, leading to degraded performance and misclassification. We distinguish poisoning attacks from noise processes and formalize random classification noise, Massart noise, and malicious classification noise within the probably approximately correct (PAC) framework. These models capture different adversarial strengths and data-generation realities. We then highlight some core ideas and representative results. In particular, we explain why random classification noise preserves the expected ordering of hypotheses and thus supports learning using the empirical risk minimization (ERM) principle, how sample complexity depends on the noise rate, and why learning algorithms often require an upper bound on the corruption level, as well as how such a bound may be estimated from data in the case of random classification noise. We also discuss computational aspects of ERM under noise and present a canonical negative result technique -- the method of induced distributions -- within the malicious noise model where the adversary has more power and may affect not only the label of an example but also the instance. We conclude with pointers to related work and a taxonomy that organizes classical label-noise models using the NCAR/NAR/NNAR lens.

0.67

Bayes-Optimal BER and AUC: Estimation and Evaluation of Estimators

cs.LG stat.ML ·2026-09-02 ·Ryota Ushio, Takashi Ishida, Masashi Sugiyama
hot direction similarity 0.60
Abstract · 43 pages, 4 figures

A fundamental quantity in machine learning is the optimal performance achievable by any model on a given task. Estimating this quantity allows us to distinguish the irreducible part of the error from a deficiency of the model, telling us how much room for improvement remains. Recent work has shown that the Bayes error, or equivalently the optimal accuracy, can be estimated from soft labels in binary classification. However, accuracy is often a poor summary of performance in settings with severe class imbalance or noisy annotations, where metrics such as the balanced error rate (BER) and the area under the ROC curve (AUC) are more appropriate. We address this gap with two complementary contributions. (i) Estimation. We propose soft-label-based estimators for the optimal BER and AUC. We first consider the clean setting in which true soft labels and the class prior are known, and then extend the estimators to a more realistic setting in which the class prior is unknown and the observed soft labels are corrupted by an unknown order-preserving transformation, possibly followed by additive noise. In the latter setting, we approximately recover the clean soft labels via isotonic regression with auxiliary hard labels, estimate the class prior with a clipped mean of the hard labels, and derive finite-sample error bounds for the resulting plug-in estimators. (ii) Evaluation. Since the optimum is unobservable on real datasets, evaluating any such estimator is itself nontrivial. We extend the FeeBee framework, originally proposed for evaluating Bayes-error estimators, to the optimal BER and AUC. The resulting procedure provides practical evaluation scores without requiring knowledge of the optimum, and applies to any estimator of the optimal BER or AUC, not only our proposed ones. Experiments on synthetic and real-world datasets validate both the estimators and the evaluation procedure.

0.41

Hierarchical Utility Calibration for Structured Multiclass Decisions

cs.LG stat.ML ·2026-09-29 ·Futoshi Futami, Jerry Huang, Ichiro Takeuchi
similarity 0.59
Abstract

In multiclass probabilistic prediction, Utility Calibration (UC), which focuses auditing on specified utilities, has recently received attention as a way to guarantee downstream decisions while controlling computational and sample requirements. At the same time, some multiclass problems have meaningful label hierarchies that play important roles in medicine and image classification, yet how UC evaluates utility within a hierarchy remains insufficiently understood. We show that the difference between realized utility and predicted mean utility admits an exact decomposition into a sum of contributions from the internal nodes of the label tree. This decomposition shows that positive and negative contributions from different nodes can cancel, and that even when UC is small, the utility errors remaining in parts of the hierarchy need not be small. To address this problem, we propose Hierarchical Utility Calibration (HUC), which evaluates each node contribution before summation while retaining the same target utility, subgroup, and predicted-utility interval. We further provide finite-sample evaluation over all predicted-utility intervals and propose HUC-Boost, which updates only violated internal nodes, with theoretical guarantees for both.

0.22