Source-linked AI summary
Partial Label Learning with Self-Guided Retraining
Lei Feng, Bo An
TL;DR
Partial label learning must infer a hidden ground-truth label from each candidate-label set, but existing self-training can amplify incorrect pseudo-labels. SURE jointly learns the model and pseudo-labels with maximum infinity norm regularization, and experiments show it significantly outperforms state-of-the-art partial label methods.
Problem
Partial label learning must identify the concealed ground-truth label within each instance’s candidate-label set, while self-training can amplify early incorrect labels.
Method
SURE jointly trains the model and pseudo-labels using constrained maximum infinity norm regularization, reducing its optimization to one quadratic programming problem through an upper-bound surrogate.
Results
SURE significantly outperforms state-of-the-art partial label learning approaches on synthesized and real-world datasets.
Takeaways & Limitations
SURE provides a self-guided retraining approach that incorporates pseudo-labeling directly into partial label model training.
Takeaways & Limitations
The equivalent set of quadratic programs can be time-consuming when the label space is large, motivating the surrogate objective.
Abstract
from arXiv · showhide
Partial label learning deals with the problem where each training instance is assigned a set of candidate labels, only one of which is correct. This paper provides the first attempt to leverage the idea of self-training for dealing with partially labeled examples. Specifically, we propose a unified formulation with proper constraints to train the desired model and perform pseudo-labeling jointly. For pseudo-labeling, unlike traditional self-training that manually differentiates the ground-truth label with enough high confidence, we introduce the maximum infinity norm regularization on the modeling outputs to automatically achieve this consideratum, which results in a convex-concave optimization problem. We show that optimizing this convex-concave problem is equivalent to solving a set of quadratic programming (QP) problems. By proposing an upper-bound surrogate objective function, we turn to solving only one QP problem for improving the optimization efficiency. Extensive experiments on synthesized and real-world datasets demonstrate that the proposed approach significantly outperforms the state-of-the-art partial label learning approaches.
Introduction
Partial label learning trains on candidate-label sets that conceal the ground truth, creating an ambiguous-label disambiguation problem. SURE jointly trains the model and pseudo-labels examples using maximum infinity norm regularization, with experiments showing an advantage over existing approaches.
- Problem: Partial label learning assigns each instance a candidate-label set containing one concealed ground-truth label, avoiding the cost of manually identifying every label.The setting is also called superset label learning or ambiguous label learning and appears in web mining, image annotation, and ecoinformatics.
- Existing strategies: Existing approaches either average candidate-label contributions or identify a latent ground-truth label using model outputs.These strategies provide alternative ways to disambiguate candidate labels in partially labeled data.
- SURE: SURE is the first proposed self-training approach for partial labels, jointly training the model and performing pseudo-labeling through a unified constrained formulation.The approach is motivated by self-training but addresses the difficulty of identifying ground truth when candidate sets remain present.
- Optimization: Maximum infinity norm regularization automatically differentiates the ground-truth candidate, producing a convex-concave optimization problem equivalent to multiple quadratic programs.An upper-bound surrogate objective reduces the computation to one quadratic programming problem.
Related Work
Prior partial-label methods use averaging or latent-label identification, while self-training offers mutually exclusive-label handling but can amplify mistakes. SURE is positioned as an identification-based method intended to alleviate these problems.
- Average-based strategy: Average-based methods treat candidate labels equally or average their modeling outputs, but distractive false-positive outputs can overwhelm the ground-truth signal.The strategy includes neighborhood-based and parametric approaches.
- Identification-based strategy: Identification-based methods can select a false-positive label instead of recovering the ground truth, severely disrupting subsequent model training.This limitation applies to likelihood- and margin-based objectives that differentiate candidate labels through model scores.
- Self-training: Self-training directly labels sufficiently confident unlabeled instances, yet early mistakes can generate incorrectly labeled data and are more problematic when the ground truth is hidden among candidates.The paper uses this motivation to introduce a partial-label approach following the identification-based strategy.
The Proposed Approach
SURE represents candidate-label confidence explicitly and learns the model from jointly optimized pseudo-labels rather than noisy candidate-label indicators. Maximum infinity norm regularization and simplex constraints enforce candidate selection while reducing competing-label confidences.
- Formulation: SURE uses a confidence matrix P whose entries represent the confidence that each candidate label is the ground truth, while non-candidate labels are excluded.The label matrix Y records candidate membership, whereas P supplies the pseudo-label information used for learning.
- Joint pseudo-labeling: Maximum infinity norm regularization replaces deterministic pseudo-labeling and jointly trains the model with pseudo-label confidence assignments.It enlarges a sufficiently confident candidate within an allowable loss range while trading off approximation loss and confidence concentration.
- Constraints: The constraints keep candidate confidences in [0,1], force non-candidate confidences to zero, and make each confidence vector a probability simplex.Increasing one candidate’s confidence naturally reduces the confidences of the other candidates.
- Instantiation: The instantiated model uses squared loss with a linear predictor and squared Frobenius regularization, with a kernel extension available for nonlinear cases.The linear model is f(x_i) = W^T x_i + b, and the nonlinear extension maps inputs into a higher-dimensional Hilbert space.
Optimization
SURE optimizes the model and pseudo-label matrix through alternating updates, using kernelized modeling and quadratic programs to handle the pseudo-label subproblem efficiently.
- Optimization: Alternating minimization updates one variable while holding the others fixed until convergence or the iteration limit is reached.The model-parameter update has closed-form solutions obtained by setting gradients with respect to W and b to zero.
- Updating W and b: The kernel extension maps inputs into a higher-dimensional Hilbert space and represents the model through a kernel matrix.The paper uses this nonlinear extension to update A and b instead of the original linear parameters.
- Updating P: With model parameters fixed, the modeling output matrix is Q = KA + 1b^T, and the pseudo-label optimization decomposes into independent problems for each example.The kernel formulation uses A and b as the parameters updated throughout the paper.
- Updating P: The pseudo-label update is a constrained convex-concave problem, equivalent to solving l independent quadratic programs and selecting the minimum loss.The convex term models approximation loss, while the concave term arises from maximum infinity norm regularization.
- Updating P: Because solving l quadratic programs can be time-consuming for large label spaces, SURE introduces an upper-bound surrogate objective.The surrogate selects the candidate label with maximal modeling output as the most likely ground-truth label.
- Updating P: The surrogate adds constraints that select a candidate label with maximal modeling output and assign it the largest pseudo-label value.This directly assumes the highest-output candidate is most likely correct, matching the paper’s self-training strategy.
Experiments
Across controlled UCI and real-world partial-label datasets, SURE is evaluated against six state-of-the-art methods using cross-validation and significance testing. It achieves superior or competitive performance across the reported comparisons, while parameter studies examine sensitivity and convergence.
- Controlled UCI Datasets: The controlled UCI experiments vary the proportion of partial-label examples, false-positive-label count, and false-positive-label occurrence probability.The parameters p, r, and ϵ respectively control these three aspects of the artificial partial-label construction.
- Controlled UCI Datasets: SURE achieves superior or comparable performance to PLKNN and PLSVM in all controlled UCI dataset cases.The controlled UCI experiments report 112 total results across varying partial-label conditions.
- Controlled UCI Datasets: SURE outperforms CLPL in 72.3% of cases and LSCMM in 58.9%, while losses occur in only 4.5% and 1.8% of cases.These comparisons are based on the controlled UCI experiments.
- Controlled UCI Datasets: SURE outperforms IPAL in 50.9% of cases and PALOC in 63.4%, with losses in only 5.4% and 2.7% of cases.The reported comparisons use the controlled UCI datasets and significance-based win/tie/loss analysis.
- Real-World Datasets: SURE significantly outperforms all comparing algorithms in 78.6% of real-world cases and is competitive in the remaining 21.4%.Across 42 cases involving six comparing algorithms and seven datasets, SURE is never significantly outperformed.
- Parameter Sensitivity Analysis: Increasing λ first improves accuracy by incorporating label exclusivity, but excessive λ causes a sharp accuracy drop; β balances overfitting and underfitting.The sensitivity analysis therefore supports balancing approximation loss, mutually exclusive label relationships, and model complexity.
- Parameter Sensitivity Analysis: The convergence curves show that ∆P gradually decreases to 0 as the iteration count increases on Lost and MSRCv2.The reported curves are used to demonstrate convergence of SURE.
Conclusion
SURE applies self-training to partial label learning by jointly training the model and performing pseudo-labeling with maximum infinity norm regularization. Extensive experiments demonstrate its effectiveness, while extending SURE to semi-supervised learning remains an open direction.
- Conclusion: SURE jointly trains the desired model and performs pseudo-labeling using a unified formulation with maximum infinity norm regularization.The regularization exaggerates mutually exclusive relationships among candidate labels during learning.
- Conclusion: Extensive experiments demonstrate SURE's effectiveness on partial label learning tasks.
- Conclusion: Extending SURE to semi-supervised learning and exploring other ways to incorporate label exclusivity remain valuable directions.