Source-linked AI summary
Progressive Identification of True Labels for Partial-Label Learning
Jiaqi Lv, Miao Xu, Lei Feng, Gang Niu, Xin Geng, Masashi Sugiyama
TL;DR
Partial-label learning must recover true labels from candidate sets, while existing constrained objectives limit scalability and optimizer flexibility. The paper proposes a classifier-consistent risk estimator and progressive identification algorithm for arbitrary models and stochastic optimization, with experiments reporting favorable performance across datasets and settings.
Problem
Partial-label learning requires identifying one true label from candidate sets, but existing constrained objectives and specialized optimization hinder scaling to big data.
Method
The paper combines a classifier-consistent risk estimator with PRODEN, which progressively identifies true labels while updating arbitrary classifiers through stochastic optimization.
Results
PRODEN is overall the best-performing method on reported small-scale datasets and remains competitive as ambiguity increases, while successfully training various models.
Takeaways & Limitations
The resulting framework provides a model-independent, loss-independent approach to PLL that supports mini-batched stochastic optimization.
Takeaways & Limitations
The theoretical classifier-consistency result assumes deterministic learning and a small ambiguity degree condition.
Abstract
from arXiv · showhide
Partial-label learning (PLL) is a typical weakly supervised learning problem, where each training instance is equipped with a set of candidate labels among which only one is the true label. Most existing methods elaborately designed learning objectives as constrained optimizations that must be solved in specific manners, making their computational complexity a bottleneck for scaling up to big data. The goal of this paper is to propose a novel framework of PLL with flexibility on the model and optimization algorithm. More specifically, we propose a novel estimator of the classification risk, theoretically analyze the classifier-consistency, and establish an estimation error bound. Then we propose a progressive identification algorithm for approximately minimizing the proposed risk estimator, where the update of the model and identification of true labels are conducted in a seamless manner. The resulting algorithm is model-independent and loss-independent, and compatible with stochastic optimization. Thorough experiments demonstrate it sets the new state of the art.
1. Introduction
Partial-label learning addresses weak supervision by identifying one true label within candidate sets, but existing constrained objectives hinder scalable stochastic optimization. The paper introduces a model- and optimizer-flexible framework combining a consistent risk estimator with progressive label identification.
- Problem: Partial-label learning assigns each instance candidate labels containing exactly one true label, reducing the need for exact annotation.It arises in tasks including automatic image annotation and web mining.
- Problem: Existing PLL methods use constrained objectives coupled to specific optimization algorithms, creating nonlinear computational costs that limit scaling to massive datasets.The paper highlights stochastic optimization as preferable for large-scale learning, while few existing methods support it.
- Goal: The paper aims to support arbitrary models, from linear classifiers to deep networks, together with stochastic optimization.This extends beyond an earlier method restricted to linear models and handcrafted features.
- Contributions: The framework proposes a classifier-consistent PLL risk estimator and establishes an estimation error bound.Consistency means the classifier learned from partial labels converges to the optimal classifier learned from ordinary labels under mild conditions.
- Contributions: PRODEN progressively identifies true labels while updating the model in mini-batches, remaining model-independent, loss-independent, and compatible with stochastic optimization.Experiments are reported on synthetic and real-world partial-label datasets.
2. Background
The background formalizes ordinary classification and partial-label learning, then reviews risk estimation and prior methods. Existing approaches often require specialized, inefficient optimization, motivating more flexible large-scale solutions.
- Ordinary Multi-Class Classification: Ordinary multi-class classification learns a classifier mapping instances to class outputs that minimizes classification risk.The label space contains c > 2 classes, and the empirical risk is typically optimized using ERM.
- Ordinary Multi-Class Classification: A proper loss is continuous and non-negative, equaling zero only when the predicted class-probability vector matches the target vector.Classifier outputs are interpreted as estimates of true label probabilities.
- Partial-Label Learning: PLL replaces a single observed label with a nonempty, non-universal candidate-label set that contains the instance’s true label.The goal remains learning a multi-class classifier that assigns true labels to unseen instances.
- Partial-Label Learning: The PLL risk estimator is defined over the distribution of instances and candidate sets, requiring a loss that accepts candidate-label sets.This differs from ordinary classification, whose risk is defined using individually observed labels.
- Related Work: Earlier EM-based and dictionary-learning methods add constraints or iterative refinement, but their specialized optimization is inefficient and incompatible with high-efficiency stochastic optimization.The cited DNN-based work uses specific network architectures, whereas the proposed method is flexible across learning models.
- Related Work: Complementary-label learning supplies a class an example does not belong to and can be viewed as an extreme PLL case with c −1 candidate labels.Restricting each instance to one complementary label limits the information that labelers can provide.
3. Learning with Partial Labels
The paper defines a minimal-loss risk estimator for partial-label learning and establishes conditions for classifier consistency and finite-sample estimation control. The estimator is theoretically justified through identifiability, ambiguity, and complexity assumptions.
- Classifier-Consistent Risk Estimator: The PLL loss uses the minimal loss over candidate labels, reflecting the assumption that only the true label should determine classifier learning.The corresponding risk estimator is derived from this minimal-loss formulation.
- Classifier Consistency: Small ambiguity means no negative label is included with the true label with probability one, allowing classification errors to be detected with probability at least 1 −γ.The condition is expressed as γ < 1.
- Classifier Consistency: The estimator is classifier-consistent when learning is deterministic, ambiguity is small, and cross-entropy or mean squared error loss is used.Under these conditions, the PLL optimal classifier is equivalent to the ordinary optimal classifier.
- Estimation Error Bound: The estimation error bound assumes bounded function outputs, Lipschitz and bounded losses, and Rademacher complexity for the classifier function class.The bound holds with probability at least 1 −δ.
- Estimation Error Bound: For bounded-norm parametric models, the Rademacher complexity tends to zero as sample size increases, and the empirical PLL risk converges to the optimal PLL risk.This establishes asymptotic control of the empirical risk classifier.
4. Benchmark Solution
PRODEN approximately optimizes the PLL risk estimator by dynamically weighting candidate labels, updating model parameters and label identification together during stochastic mini-batch training.
- Optimization challenge: The min operator makes direct optimization difficult because an initially selected wrong label can dominate training.The benchmark solution therefore relaxes the min operator using dynamic weights.
- Training procedure: PRODEN initializes uniform weights and updates weights and model parameters within stochastic mini-batch training.Algorithm 1 shuffles the data into mini-batches, computes the loss, updates weights, and then applies a stochastic optimizer.
- Dynamic weighting: PRODEN requires decomposable losses, including commonly used multi-class losses such as cross-entropy.The loss is decomposed across candidate labels so dynamic label weights can be applied.
- Dynamic weighting: Label weights represent confidence that each candidate label is the true label, and ideal weights assign one to the true label.With weights determined by the minimum-loss candidate, the empirical objective matches the empirical counterpart of the proposed risk estimator.
- Progressive identification: True labels are progressively identified while refined labels improve the classifier, with identification and optimization performed seamlessly.The merged procedure avoids the explicit separation of E- and M-steps, allowing weight updates at any epoch without local convergence in each epoch.
- Flexibility: PRODEN is flexible across models and loss functions, supports a large group of decomposable losses, and generalizes the Jin and Ghahramani method.The stated model flexibility includes compatibility with arbitrary multi-class classifiers and stochastic optimizers.
5. Experiments
Experiments evaluate PRODEN across datasets, models, baselines, and ambiguity levels. PRODEN generally performs best and is comparatively robust as ambiguity increases.
- Experimental setup: Experiments use benchmark, UCI, and real-world datasets with linear models, MLPs, ConvNets, and ResNets.Training uses stochastic gradient descent with momentum 0.9; models are trained for 500 epochs.
- Baselines: PRODEN is evaluated against seven DNN-based baselines, including variants, supervised methods, and state-of-the-art PLL methods.Additional comparisons include six classical PLL methods on UCI and real-world datasets, using linear models for fairness.
- Benchmark results: PRODEN is always the best method at q = 0.1 and is comparable to PN-oracle across models.PRODEN-itera deteriorates with complex models, while uniform or sudden label-weight updates perform more poorly.
- Ambiguity analysis: As ambiguity increases, PRODEN is less affected than the baselines on Kuzushiji-MNIST in the pair case.The pair-flipping strategy varies q from 0.5 to 0.9 to simulate increasing ambiguity.
- Small-scale datasets: PRODEN is overall the best-performing method on the UCI and real-world datasets under five-fold cross-validation.Mean test accuracy and standard deviation are reported in Tables 1 and 2, with paired t-tests at the 5% significance level.
6. Conclusion
The paper introduces a theoretically grounded risk estimator and PRODEN, a progressive identification method for flexible classifiers and stochastic optimization. Experiments show successful training across models and favorable comparison with state-of-the-art methods.
- Contributions: The proposed PLL method is compatible with flexible multi-class classifiers and stochastic optimization.Its risk estimator is classifier-consistent and based on the minimal loss incurred by candidate labels.
- Contributions: PRODEN approximately minimizes the risk estimator by replacing the minimum with a weighted combination and seamlessly updating labels and the classifier.The seamless updates are intended to mitigate overfitting during neural-network optimization.
- Empirical conclusion: Experiments show that PRODEN successfully trains various models and compares favorably with state-of-the-art methods.
Supplementary Material
The supplementary derivations analyze classifier optimization under cross-entropy and mean squared error losses. They derive the optimal classifier through constrained optimization and Lagrange multipliers.
- Cross-Entropy loss: For cross-entropy, minimizing the conditional risk is presented as an alternative to minimizing the classification risk.The derivation uses the non-negativity of cross-entropy loss.
- Cross-Entropy loss: The cross-entropy optimization derivation uses a Lagrange multiplier and sets partial derivatives with respect to classifier outputs to zero.
- Mean squared error loss: The mean squared error section formulates an analogous optimization problem and solves it using Lagrange multipliers and derivative conditions.The displayed derivation includes a resulting expression involving 2 + p(Y = i|X).
- Cross-Entropy loss: The cross-entropy derivation obtains g*_i(X) = p(Y = i|X) for every class and input.
B. Proof of Theorem 1
The proof establishes that the optimal classifier minimizes the PLL risk and is uniquely identified under a small ambiguity degree condition. This optimizer matches the one learned from ordinarily labeled data.
- Optimality: Substituting g* into the PLL risk estimator shows that the candidate-label minimum equals the loss for the true label under a proper loss and deterministic assumption.
- Uniqueness: The proof argues by contradiction that any alternative classifier predicting a different label cannot also achieve zero PLL risk.
- Uniqueness: Under the small ambiguity degree condition, the PLL risk estimator has one unique minimizer matching the minimizer learned from ordinarily labeled data.
C. Proof of Theorem 2
The proof establishes a uniform deviation bound and then bounds the Rademacher complexity of the partial-label loss, yielding the estimation error bound. It also connects the objective to prior work as a special case.
- The proof begins by establishing a uniform deviation bound needed to derive the estimation error bound.
- Lemma 4 bounds the Rademacher complexity of the partial-label loss defined through a minimum over candidate labels.The proof first handles two classes and extends the result recursively to the general case.
- Combining the deviation and complexity bounds proves the estimation error bound in Eq. (7).
- The learning objective of Jin and Ghahramani (2003) is shown to be a special case of Eq. (8).With cross-entropy loss, the candidate-label weights can be incorporated into the loss, making the proposed method a strict extension.
E.3. Test Results in the Pair Case
In the pair case, PRODEN is only slightly affected as ambiguity increases, whereas CCN is severely affected. Figure 3 reports transductive accuracy using five-trial means and standard deviations.
- PRODEN is affected slightly when the ambiguity degree becomes large, while CCN is affected severely.
- Figure 3 reports transductive accuracy across models and datasets to assess true-label identification in the training set.
- Dark colors denote mean accuracy over 5 trials, while light colors denote standard deviation.
F.2. Comparing Methods
The comparison covers parametric and non-parametric PLL methods on UCI datasets under pair flipping. PRODEN generally outperforms the other parametric methods, while IPAL remains a closer comparator.
- The comparison includes iterative, binary-learning, decomposition, margin-based, k-nearest-neighbor, and label-propagation PLL methods.The listed methods are SURE, CLPL, ECOC, PLSVM, PLkNN, and IPAL.
- PRODEN generally achieves superior performance against the other parametric methods on UCI datasets with pair flipping.
- PRODEN’s advantage is less obvious compared with the non-parametric method IPAL.
- PRODEN’s performance could be increased by employing a deeper network.