Partial-Label Learning with a Reject Option

Tobias A. Fuchs, Florian Kalinke, Klemens Böhm

Abstract

In real-world applications, one often encounters ambiguously labeled data, where different annotators assign conflicting class labels. Partial-label learning (PLL) allows training classifiers in this weakly supervised setting, where state-of-the-art methods already show good predictive performance. However, even the best algorithms give incorrect predictions, which can have severe consequences when they impact actions or decisions. We propose a novel risk-consistent nearest-neighbor-based partial-label learning algorithm with a reject option, that is, the algorithm can reject unsure predictions. Extensive experiments on artificial and real-world datasets show that our method provides the best trade-off between the number and accuracy of non-rejected predictions when compared to our competitors, which use confidence thresholds for rejecting unsure predictions. When evaluated without the reject option, our nearest-neighbor-based approach also achieves competitive prediction performance.

Introduction

Partial-Label Learning (PLL) addresses the challenge of training models on data where each instance is associated with a set of candidate labels, only one of which is the ground truth. This scenario is common in domains like medical imaging, where multiple experts may provide conflicting diagnoses, or in image tagging, where labels are often noisy or incomplete.

While existing PLL methods have achieved high predictive accuracy, they often struggle in safety-critical applications—such as autonomous driving or clinical decision support—where a single incorrect prediction can be catastrophic. Most current models provide a point estimate of probability, which fails to distinguish between two critical types of uncertainty: aleatoric uncertainty (inherent randomness in the data) and epistemic uncertainty (lack of knowledge due to insufficient data). To address this, we introduce DST-PLL, a nearest-neighbor algorithm that utilizes Dempster-Shafer Theory (DST) to quantify uncertainty and provide a robust "reject option," allowing the model to abstain from making a prediction when the evidence is insufficient.

Methodology

Dempster-Shafer Theory (DST) and Credal Sets

Unlike standard probability theory, which assigns a single value to an event, DST uses Basic Probability Assignments (BPAs) that can be assigned to sets of labels. This framework allows the model to maintain a credal set—a range of possible probability distributions. This is particularly useful for PLL because it explicitly represents the ambiguity inherent in candidate label sets.

Evidence Gathering and Combination

For a new data point, DST-PLL identifies its $k$-nearest neighbors in the feature space. The candidate labels of these neighbors are treated as independent pieces of evidence. To combine this evidence, we employ Yager’s Combination Rule, which is specifically designed to handle conflicting information. This is crucial in PLL, where different neighbors may suggest different, overlapping sets of candidate labels.

The Reject Option

The model’s decision to predict or reject is based on the difference ($\Delta$) between the belief (the minimum support for a predicted label) and the plausibility (the maximum possible support for any alternative label). If $\Delta \leq 0$, the model determines that the evidence for the best guess does not sufficiently outweigh the potential for another label to be correct, and it rejects the instance. This creates an adaptive rejection threshold that responds to local data density and label conflict.

Risk Consistency

A key theoretical contribution of this work is the proof of risk consistency. We demonstrate that as the volume of training data increases, the DST-PLL classifier converges to the optimal Bayes classifier, ensuring that the model's decision-making process is mathematically grounded.

Experimental Evaluation

We evaluated DST-PLL across a diverse range of datasets to test its robustness:

  • UCI Tabular Datasets: Seven datasets (e.g., ecoli, pen-digits) with synthetic noise patterns (uniform, class-dependent, and instance-dependent).
  • Image Datasets: MNIST, KMNIST, and Fashion-MNIST, processed via Variational Auto-Encoders (VAEs) to extract meaningful features for the nearest-neighbor search.
  • Real-World PLL Datasets: Data with naturally occurring ambiguity, including bird-song, flickr, and yahoo-news.

Key Results

Accuracy-Rejection Trade-off

DST-PLL consistently outperformed state-of-the-art competitors like PRODEN and CC in the trade-off between the number of rejected samples and the accuracy of the remaining predictions. For example, at a 50% rejection rate, DST-PLL achieved a non-rejected test accuracy of 95.49%, compared to 94.03% for PRODEN and 90.13% for CC.

Empirical Risk Minimization

When assigning a cost ($\lambda$) to rejections, DST-PLL achieved the lowest total empirical risk across nearly all settings. This performance was most pronounced in scenarios where misclassifications were weighted significantly more heavily than rejections, highlighting the model's utility in high-stakes environments.

Baseline Performance

Even when the reject option was disabled, the underlying nearest-neighbor classifier remained highly competitive with complex deep learning-based PLL methods, proving that the DST framework provides a strong foundation for classification even without abstention.

Conclusion and Future Work

DST-PLL offers a principled approach to handling ambiguity in partial-label learning by distinguishing between different types of uncertainty. While the nearest-neighbor approach is effective, it faces scalability challenges on very large datasets due to the $O(dk \log n)$ complexity of neighbor searches. Future research will focus on integrating DST-based rejection mechanisms directly into end-to-end deep neural networks and exploring automated methods for tuning the number of neighbors ($k$) based on local data characteristics.

Summary updated

Abstract

In real-world applications, one often encounters ambiguously labeled data, where different annotators assign conflicting class labels. Partial-label learning allows training classifiers in this weakly supervised setting, where state-of-the-art methods already show good predictive performance. However, even the best algorithms give incorrect predictions, which can have severe consequences when they impact actions or decisions. We propose a novel risk-consistent nearest-neighbor-based partial-label learning algorithm with a reject option, that is, the algorithm can reject unsure predictions. Extensive experiments on artificial and real-world datasets show that our method provides the best trade-off between the number and accuracy of non-rejected predictions when compared to our competitors, which use confidence thresholds for rejecting unsure predictions. When evaluated without the reject option, our nearest-neighbor-based approach also achieves competitive prediction performance.
BibTeX
@article{fuchs2025partial,
  author = {Tobias A. Fuchs and Florian Kalinke and Klemens Böhm},
  title = {{Partial-Label Learning with a Reject Option}},
  journal = {Trans. Mach. Learn. Res.},
  year = {2025},
}
Figure