Source-linked AI summary
A Regularization Approach for Instance-Based Superset Label Learning
Chen Gong, Tongliang Liu, Yuanyan Tang, Jian Yang, Jie Yang, Dacheng Tao
TL;DR
SLL must identify a single correct label from each training example’s candidate set, while instance-based disambiguation may fail to account for candidate-label exclusivity. RegISL combines graph-based label smoothness with a discrimination term, and experiments report better training and test performance than representative SLL methods in most cases.
Problem
Instance-based SLL disambiguation may neglect mutually exclusive candidate labels, producing nondiscriminative labels.
Source: B. Our Motivation · p. 3Method
RegISL builds a graph over training examples and combines label smoothness for adjacent examples with a discrimination term that separates possible from unlikely labels.
Source: B. Our Motivation · p. 3, §II · p. 3Results
RegISL achieves better training and test performance than representative SLL methods in most cases across practical datasets.
Source: §IV · p. 10Takeaways & Limitations
RegISL makes candidate-set groundtruth labels more prominent while suppressing false-positive candidate labels.
Source: §IV · p. 10
Abstract
from arXiv · showhide
Different from the traditional supervised learning in which each training example has only one explicit label, superset label learning (SLL) refers to the problem that a training example can be associated with a set of candidate labels, and only one of them is correct. Existing SLL methods are either regularization-based or instance-based, and the latter of which has achieved state-of-the-art performance. This is because the latest instance-based methods contain an explicit disambiguation operation that accurately picks up the groundtruth label of each training example from its ambiguous candidate labels. However, such disambiguation operation does not fully consider the mutually exclusive relationship among different candidate labels, so the disambiguated labels are usually generated in a nondiscriminative way, which is unfavorable for the instance-based methods to obtain satisfactory performance. To address this defect, we develop a novel regularization approach for instance-based superset label (RegISL) learning so that our instance-based method also inherits the good discriminative ability possessed by the regularization scheme. Specifically, we employ a graph to represent the training set, and require the examples that are adjacent on the graph to obtain similar labels. More importantly, a discrimination term is proposed to enlarge the gap of values between possible labels and unlikely labels for every training example. As a result, the intrinsic constraints among different candidate labels are deployed, and the disambiguated labels generated by RegISL are more discriminative and accurate than those output by existing instance-based algorithms. The experimental results on various tasks convincingly demonstrate the superiority of our RegISL to other typical SLL methods in terms of both training accuracy and test accuracy.
I. INTRODUCTION
Superset label learning (SLL) trains on examples with multiple candidate labels, only one of which is correct, when obtaining unambiguous labels manually can be costly. Prior work develops regularization-based losses and related theoretical and model variants.
I. INTRODUCTION
- SLL assigns each training example a candidate-label set containing one correct label, addressing applications where manually identifying groundtruth labels is costly.Examples include matching names to faces in images and resolving potentially incorrect labels from crowdsourcing.Source: §I · pp. 1–2
A. Related Work
- Prior SLL work divides mainly into regularization-based and instance-based models, with regularization methods seeking maximum-margin effects through varied loss functions.Grandvalet first proposed SLL by adapting logistic regression to superset labels.Source: A. Related Work · p. 2, 1) Regularization-based Models · p. 2
1) Regularization-based Models:
- Equal-probability treatment of candidate labels can let false positives dominate training, while a tighter surrogate and a superset-label hinge loss offer alternatives.The hinge loss maximizes the margin between the highest candidate-label score and the highest non-candidate-label score.Source: 1) Regularization-based Models · p. 2
- Other regularization formulations include generalized logistic losses and an SVM-based maximum-margin method that separates the groundtruth label from all other labels.The generalized losses described do not distinguish the groundtruth label from other candidate labels.Source: 1) Regularization-based Models · p. 2
- Related work also studies bag-level candidate label vectors, conditions for constructing proper SLL losses, loss consistency and learnability, and coding, mixture-model, and low-rank approaches.Luo et al. consider bags in which only one candidate label vector is fully correct; learnability work relates classification error to average superset-label 0-1 loss.Source: 1) Regularization-based Models · pp. 2–3
2) Instance-based Models:
Existing instance-based SLL methods disambiguate candidate labels, but may neglect candidate-label exclusivity and lack a theoretical convergence guarantee. RegISL adds discrimination regularization and reports better training and test accuracy than competing methods in most tested cases.
2) Instance-based Models:
- Instance-based methods use nonparametric classifiers, with some retaining ambiguous labels and others disambiguating them through propagation or feature-aware information.The propagation method generally performs best among existing SLL algorithms, but does not capture candidate-label exclusivity or guarantee convergence theoretically.Source: B. Our Motivation · p. 3, 2) Instance-based Models · p. 3
B. Our Motivation
- RegISL adds a discrimination regularizer that widens score gaps between possible and unlikely labels, making potential groundtruth labels prominent and unlikely labels suppressed.It uses ALM to obtain a stationary solution and CCCP to minimize the nonconvex objective.Source: B. Our Motivation · p. 3
- RegISL outperforms competing SLL baselines in both training and test accuracy in most tested cases across character-name association, image classification, face naming, and bird sound tasks.The experiments compare representative SLL methodologies across these practical applications.Source: B. Our Motivation · p. 3
II. MODEL DESCRIPTION
RegISL represents training examples as a weighted K-nearest-neighbor graph and optimizes their label vectors to combine graph smoothness, candidate-label fidelity, and label discrimination. Its constrained training objective is solved with ALM and CCCP, then each training example receives a single label from its optimized vector.
II. MODEL DESCRIPTION
- A K-nearest-neighbor graph links training examples, with Gaussian-kernel weights encoding similarity between connected examples.The graph supports the regularized objective used to disambiguate training labels.Source: §II · p. 3
A. Training Stage
- The objective combines graph smoothness, candidate-label fidelity, and a norm-based discrimination term that promotes confident labels under nonnegative, sum-to-one constraints.The discrimination term favors label vectors nearer to definite assignments than ambiguous ones.Source: A. Training Stage · p. 4
- ALM handles the constrained objective, while CCCP turns the nonconvex label-vector update into a sequence of convex problems.The paper states that convergence of the ALM process is theoretically guaranteed.Source: A. Training Stage · pp. 4–5
- Each training example receives the class with the highest optimized label-vector value, represented afterward as a one-hot disambiguated label vector.The class is selected by an argmax over the optimized vector’s class values.Source: A. Training Stage · p. 5
B. Test Stage
At test time, RegISL uses the disambiguated labels of a test example’s nearest training neighbors to determine its class.
B. Test Stage
- RegISL finds the test example’s K nearest training examples in Euclidean space.It then computes similarities between the test example and those neighbors using the Gaussian kernel.Source: B. Test Stage · p. 5
- The neighbors’ disambiguated label vectors are combined using their similarities to form a weighted label vector for the test example.The vector is calculated as a weighted sum of the neighbors’ labels.Source: B. Test Stage · p. 5
- The predicted class is the one with the largest value in the test example’s weighted label vector.The final decision is an argmax over its class values.Source: B. Test Stage · p. 5
III. EXPERIMENTAL RESULTS
The experimental section compares RegISL with typical SLL baselines using five-fold cross-validation, training and test accuracy, and Friedman testing.
III. EXPERIMENTAL RESULTS
- The comparison includes regularization-based baselines M3SL, CLSL, CLSL Naive, ECOC, and LSB-CMM, alongside instance-based SLKNN and ISL.The paper reports that ISL is the state-of-the-art instance-based method and omits another SVM-like baseline because its accuracy was consistently lower than M3SL in prior reporting.Source: §III · p. 6
- Five-fold cross-validation uses 80% of each partition for training and 20% for testing, with identical partitions across methods and mean training and test accuracy as measures.The class proportions are kept approximately identical between training and test sets in each partition.Source: §III · p. 6
- A Friedman test at 90% confidence is used to assess whether RegISL is significantly superior or inferior to the adopted baselines.Source: §III · p. 6
A. Character-name Association in TV Serial
On the Lost dataset, RegISL achieves the highest reported mean training and test accuracy. The results also highlight the role of disambiguation and describe a face-name association task with ambiguous script-derived labels.
A. Character-name Association in TV Serial
- Lost contains 1,122 face images across 16 characters, with an average of 2.23 candidate names per face and 512-dimensional GIST features.Each face is ambiguously labeled with names in the aligned scene script; images are resized to 30 × 20 pixels.Source: A. Character-name Association in TV… · p. 6
- The comparison uses K = 5 for ISL, SLKNN, and RegISL, with RegISL's trade-off parameters set to α = 1000 and β = 0.01.The paper says it studies the sensitivity of α and β in a later section.Source: A. Character-name Association in TV… · pp. 6–7
- 0.852 mean training accuracy and 0.726 mean test accuracy make RegISL the best-performing comparator on Lost.The reported figures are averaged accuracies.Source: Table II · p. 7, A. Character-name Association in TV… · p. 7
- SLKNN and ECOC have the lowest test accuracy without disambiguation, while CLSL exceeds CLSL Naive by not treating candidate labels equally.The paper attributes the latter difference to CLSL's greater attention to true-positive labels during training.Source: A. Character-name Association in TV… · p. 7
B. Ambiguous Image Classification
On MSRCv2, RegISL outperforms the other methods in training and test accuracy, including ISL by reported margins. The paper describes the dataset as challenging because of sparse, skewed examples and complex images with false-positive background labels.
B. Ambiguous Image Classification
- MSRCv2 has 591 images and 23 classes, with segmented-region labels forming candidate sets and the dominant region supplying each image's groundtruth label.Images are represented by normalized 512-dimensional GIST features.Source: B. Ambiguous Image Classification · p. 7
- Roughly 0.06 training-accuracy and 0.005 test-accuracy margins over ISL; RegISL leads both measures despite low accuracies overall.The remaining approaches do not exceed 0.6 training accuracy or 0.3 test accuracy.Source: B. Ambiguous Image Classification · p. 8
- Sparse examples per class, skewed candidate-label counts of 24–184, and complex images with false-positive background labels make MSRCv2 challenging for SLL.The paper says these conditions complicate reliable classifier training and can mislead training and testing.Source: B. Ambiguous Image Classification · p. 8
C. Automatic Face Naming in News Images
On Soccer Player, ECOC achieves the best results, while RegISL remains competitive and performs best among the compared instance-based methods. The dataset associates faces in news images with names from descriptions or a Null class.
C. Automatic Face Naming in News Images
- News-image descriptions may name people without specifying which face matches each name, motivating the face-naming task.Faces are manually annotated using names from descriptions or the Null class.Source: C. Automatic Face Naming in News Images · p. 8
- The dataset contains 8,640 images with 17,472 faces across 1,579 names; the experiment retains names occurring at least 20 times and groups the rest as Null.The retained faces are represented by 279-dimensional features based on 13 facial landmarks.Source: C. Automatic Face Naming in News Images · p. 8
- ECOC achieves the best results; RegISL trails it by 0.003 training accuracy and 0.009 test accuracy while leading the compared instance-based methods.RegISL also performs favorably to several other methods on test accuracy.Source: C. Automatic Face Naming in News Images · p. 8
D. Bird Sound Classification
RegISL improves on ISL and SLKNN in training and test accuracy for the reported comparisons. The Bird Song dataset consists of syllables whose candidate labels are the bird species in their recordings.
D. Bird Sound Classification
- Bird Song contains 548 ten-second recordings with 4,998 syllables, each represented by a 38-dimensional feature vector.Each syllable is an example; species appearing in its recording serve as candidate labels.Source: D. Bird Sound Classification · p. 8
- The comparison uses K = 10 for ISL, SLKNN, and RegISL, with α = 1000 and β = 0.01 for RegISL.The kernel width θ is tuned to 1.Source: D. Bird Sound Classification · pp. 8–9
- RegISL improves on ISL and SLKNN in both training and test accuracy, while instance-based methods outperform the compared regularization-based methods.The compared regularization-based methods include CLPL, CLPL Naive, M3PL, LSB-CMM, and ECOC.Source: D. Bird Sound Classification · p. 9
E. Illustration of Convergence
The paper evaluates RegISL’s convergence by tracking changes in F between successive iterations on four datasets. F diminishes over the iterations, with convergence usually reached between iterations 13 and 40.
E. Illustration of Convergence
- The convergence analysis evaluates the difference in optimization variable F between successive loops.The curves are reported for Lost, MSRCv2, Soccer Player, and Bird Song.Source: E. Illustration of Convergence · p. 9
- The reported convergence curves cover Lost, MSRCv2, Soccer Player, and Bird Song.Source: E. Illustration of Convergence · p. 9
- F’s difference between successive iterations gradually vanishes, and ALM usually converges between the 13th and 40th iteration.This behavior is reported as evidence of convergence for RegISL’s optimization process.Source: E. Illustration of Convergence · p. 9
F. Effect of Tuning Parameters
RegISL’s training and test accuracy is generally not sensitive to α, β, and K across the four datasets. The reported parameter choices giving the highest accuracy in most cases are α = 1000 and β = 0.01; the best K varies by dataset.
F. Effect of Tuning Parameters
- RegISL’s performance is generally not sensitive to α, β, and K across the four datasets.The study varies one parameter at a time while fixing the other two, and evaluates training and test accuracy.Source: F. Effect of Tuning Parameters · p. 9
- Figure 6 reports training and test accuracy as α, β, and K vary, across its three parameter-specific columns.Source: Figure 6 · p. 10
- α = 1000 and β = 0.01 yield the highest accuracy in most cases, while the best K is 5 for Lost and 10 for MSRCv2, Soccer Player, and Bird Song.Source: F. Effect of Tuning Parameters · pp. 9–10
IV. CONCLUSION
RegISL combines graph-based label smoothness with a discrimination term to make candidate-label disambiguation more discriminative. Experiments suggest it usually outperforms representative SLL methods, while its accuracy depends on graph quality.
IV. CONCLUSION
- RegISL uses graph-based label smoothness and a discrimination term to distinguish possible from unlikely labels during candidate-label disambiguation.The method is intended to make possible groundtruth labels prominent and suppress false positive candidate labels.Source: §IV · p. 10
- Experiments on practical datasets suggest RegISL achieves better training and test performance than representative SLL methods in most cases.Source: §IV · p. 10
- RegISL’s classification accuracy depends on the quality of the constructed graph; improving graph construction and handling omitted groundtruth labels are identified as future work.Source: §IV · p. 10