PaperlayerView exact revision on arXiv

Source-linked AI summary

Complementary-Label Learning for Arbitrary Losses and Models

Takashi Ishida, Gang Niu, Aditya Krishna Menon, Masashi Sugiyama

arXiv:1810.04327v4stat.MLcs.LG

TL;DR

True labels can be difficult and costly to collect, motivating complementary labels that identify a class an example does not belong to. This paper proposes an unbiased risk estimator for arbitrary losses and models, with a modified objective to address overfitting; experiments report performance comparable to or better than previous methods.

  • Problem

    True labels can be difficult and costly to collect, motivating complementary labels that identify a class an example does not belong to.

    Source: §1 · p. 1

  • Method

    A general unbiased risk estimator supports arbitrary losses and models, with a non-negative correction and gradient-ascent procedure to address overfitting.

    Source: §1 · p. 2, §3.4 · p. 7

  • Results

    Across benchmark datasets with linear and deep models, the proposed methods outperform or match current state-of-the-art methods.

    Source: §5 · p. 8

  • Takeaways & Limitations

    The general unbiased risk estimator is useful as a validation objective for baseline methods as well as a learning objective.

    Source: §4.2 · p. 8

    Without any assumptions on D, it is impossible to design a suitable learning procedure.

    Source: §2.2 · p. 3

Abstract

from arXiv · show

In contrast to the standard classification paradigm where the true class is given to each training pattern, complementary-label learning only uses training patterns each equipped with a complementary label, which only specifies one of the classes that the pattern does not belong to. The goal of this paper is to derive a novel framework of complementary-label learning with an unbiased estimator of the classification risk, for arbitrary losses and models---all existing methods have failed to achieve this goal. Not only is this beneficial for the learning stage, it also makes model/hyper-parameter selection (through cross-validation) possible without the need of any ordinarily labeled validation data, while using any linear/non-linear models or convex/non-convex loss functions. We further improve the risk estimator by a non-negative correction and gradient ascent trick, and demonstrate its superiority through experiments.

1. Introduction

Complementary-label learning uses labels that rule out a class rather than identify the true class, and this can make data collection easier. The paper proposes an unbiased risk estimator that supports arbitrary losses and models, complementary-label validation, and correction schemes, with experiments reporting accuracy comparable to or better than earlier methods.

1. Introduction

  • Complementary labels identify a class a pattern does not belong to, a potentially easier and less costly alternative to specifying its true class.The paper also describes their possible use for surveys with extremely private questions.Source: §1 · p. 1
  • Ishida et al. (2017) recovered classification risk from complementary labels but restricted losses to specified multi-class forms and certain non-convex binary losses.The paper notes that softmax cross-entropy cannot be expressed by those loss forms.Source: §1 · p. 1
  • Yu et al. (2018) used forward loss correction with softmax cross-entropy; its estimator is not necessarily unbiased, and the method also considers biased complementary-label selection.The paper reports a consistency guarantee for its minimizer under an implicit model assumption for convergence analysis.Source: §1 · p. 1
  • The framework derives an unbiased risk estimator for complementary-label learning that allows convex or non-convex losses and linear or non-linear models.The paper says this framework generalizes Ishida et al. (2017).Source: §1 · pp. 1–2
  • The estimator can evaluate complementary-label validation data for the paper's objective and Yu et al.'s (2018), avoiding the need for clean validation labels.The authors note that clean validation data are usually more expensive to collect.Source: §1 · p. 2
  • The proposed method is comparable to or better than previous methods in classification accuracy.The authors report experiments for the proposed method, including correction schemes.Source: §1 · p. 2

2. Review of previous works

This section reviews how ordinary-label risk is formulated and contrasts complementary-label learning with combined ordinary/complementary and partial-label settings. It highlights the assumptions, loss restrictions, and validation differences that distinguish these approaches.

2.1. Learning from ordinary labels

  • Ordinary-label classification seeks a decision function minimizing expected loss, with equivalent risk expressions introduced for later use.The loss may be any function mapping a class and model scores to a nonnegative value.Source: §2.1 · p. 2

2.2. Learning from complementary labels

  • The comparison summarizes an unrestricted unbiased estimator and a non-negative variant that addresses overfitting but is not unbiased as a learning objective.The unbiased estimator remains usable for validation.Source: Table 1 · p. 3
  • Under the original complementary-label assumption, other labels are chosen uniformly, and risk recovery was limited to one-versus-all or pairwise losses with special binary losses.The cited binary losses satisfy s(z) + s(−z) = 1.Source: §2.2 · p. 3
  • Yu et al.'s biased-label setting requires estimating T, which is difficult without strong assumptions; overly obvious complementary labels may also be uninformative.The paper focuses on the uniform-choice assumption instead.Source: §2.2 · p. 3
  • Yu et al.'s objective has a consistent minimizer under a model assumption but restricts losses to softmax cross-entropy; an unbiased risk estimator also permits complementary-label validation.The estimator can select hyperparameters for Yu et al.'s objective without clean validation labels.Source: §2.2 · p. 3

2.3. Learning from ordinary & complementary labels

  • With both ordinary and complementary data, a convex combination interpolates between their classification risks, and the combined estimator was reported to perform well experimentally.The interpolation weight α ranges from 0 to 1.Source: §2.3 · p. 4

2.4. Learning from partial labels

  • Partial-label learning supplies a candidate set containing the correct class, but its cited method gives no unbiased risk estimator and uses different assumptions.The cited partial-label method has a statistical consistency result and uses a dominance relation assumption.Source: §2.4 · p. 4

3. Proposed method

The proposed framework estimates classification risk from complementary labels without restricting the loss or model. It addresses negative empirical risk with non-negative and gradient-ascent corrections, including a mini-batch implementation.

3.1. General risk formulation

  • The unbiased risk formulation supports any convex or non-convex loss and any linear or non-linear model, generalizing the earlier framework of Ishida et al. (2017).The paper identifies prior loss restrictions and Yu et al. (2018)’s lack of an unbiased risk estimator as motivating gaps.Source: §3.1 · p. 4, §3 · p. 4

3.2. Necessity of risk correction

  • The empirical risk estimator can become negative despite the population risk being non-negative, which can lead to overfitting.In the MLP example, test accuracy drops significantly after empirical risk turns negative.Source: §3.2 · p. 5

3.3. Non-negative risk estimator

  • The non-negative correction applies a max with zero to each ordinary-class risk term, keeping the empirical objective non-negative while preserving equivalence for non-negative population terms.The paper motivates the classwise correction by observing that decomposed class risks can become negative during training.Source: §3.3 · pp. 5–6

3.4. Approximate non-negative risk estimator

  • For mini-batch optimization, the method uses an upper bound of the non-negative risk because the max-operator objective is not point-wise.The max operator alone cannot reduce overfitting once a mini-batch objective is already negative.Source: §3.4 · p. 6
  • When class-decomposed mini-batch risks fall below −β, gradient ascent increases only those risks, with β setting the tolerated negativity threshold.Risks at or above −β use gradient descent as usual.Source: §3.4 · p. 7

4. Experiments

Across experiments, the methods perform similarly with linear models, while Gradient Ascent is strongest in deep-model comparisons. The experiments also find that the proposed unbiased estimator can serve as a validation criterion for baseline methods.

4. Experiments

  • The comparison evaluates Free, Max Operator, and Gradient Ascent against Pairwise Comparison and Forward correction using complementary-label training data.Experiments include MNIST, Fashion-MNIST, Kuzushiji-MNIST, and CIFAR-10.Source: §4 · p. 7

4.1. Comparison of all epochs during training

  • For deep models, Gradient Ascent outperforms the baselines across datasets, while methods have similar performance with linear models.Among the proposed methods, Free < Max Operator < Gradient Ascent for most epochs with MLP, DenseNet, or ResNet models.Source: §4.1 · p. 8

4.2. Experiments with validation process

  • The validation experiments split the complementary-label training data into train and validation sets at a 9:1 ratio, so validation labels are complementary rather than ordinary.The validation comparison uses MLP models for MNIST, Fashion-MNIST, and Kuzushiji-MNIST, and DenseNet for CIFAR-10.Source: §4.2 · p. 8
  • Using the unbiased estimator as the validation criterion, PC and Forward correction perform similarly or better in most cases than with their respective native criteria.The comparison selects models by validation score across epochs and hyperparameter candidates.Source: §4.2 · p. 8

5. Conclusion

The paper concludes that its general risk estimator removes restrictions on loss and model form, and that modified versions alleviate overfitting. Experiments report performance comparable to or better than current methods on benchmark datasets with linear and deep models.

5. Conclusion

  • The proposed complementary-label risk estimator has no restrictions on the form of the loss function or model.The paper reports that modified versions alleviate overfitting in two ways.Source: §5 · p. 8
  • Experiments find the proposed method comparable to or better than current state-of-the-art methods across benchmark datasets and linear and deep models.Source: §5 · p. 8
  • Applying complementary labels to domains such as online learning, generative discriminative learning, and medical image segmentation is identified as a possible future direction.The paper describes these applications as motivation for exploring other domains.Source: §5 · p. 8

A. Proof of Theorem 1

The proof uses assumption (5) and a relation between ordinary and complementary labels to transform the classification risk into a complementary loss.

A. Proof of Theorem 1

B. Proof of Corollary 2

The proof derives its equality using (10), loss-sum conditions, and rearrangement of terms. For OVA and PC losses, it applies the stated constants to establish the final equality.

B. Proof of Corollary 2

  • Table 3 summarizes four benchmark datasets and notes a 9:1 train/validation split for validation experiments.Source: Table 3 · p. 11
  • The second equality follows from equation (10).Source: B. Proof of Corollary 2 · p. 11
  • The next equality uses losses whose sums over classes and paired labels are constant across inputs.Source: B. Proof of Corollary 2 · p. 11
  • For OVA and PC losses, the constants satisfy M1 − (K − 1)M2 = −M1 + M2, yielding the fourth-to-fifth equality.The passage gives M1 = K and M2 = 2 for OVA, and M1 = K(K − 1)/2 and M2 = K − 1 for PC.Source: B. Proof of Corollary 2 · p. 11

C. Datasets

The experiments use four 10-class benchmark datasets: three grayscale 28 × 28 image datasets and CIFAR-10, a colored 32 × 32 × 3 dataset.

C. Datasets

  • The experiments use four benchmark datasets, with their summary statistics reported in Table 3.Source: C. Datasets · p. 11
  • MNIST contains 10 classes of handwritten digits, represented as 28 × 28 grayscale images.Source: C. Datasets · p. 11
  • Fashion-MNIST contains 10 classes of fashion items, represented as 28 × 28 grayscale images.Source: C. Datasets · p. 11
  • Kuzushiji-MNIST contains 10 classes of cursive Japanese characters, represented as 28 × 28 grayscale images.Source: C. Datasets · p. 11
  • CIFAR-10 contains 10 object classes and uses colored 32 × 32 × 3 RGB images.Source: C. Datasets · p. 11

Errata (Nov. 19, 2019)

After correcting the forward-method implementation, the updated comparisons vary by dataset and model: gradient ascent leads on CIFAR-10, while forward correction leads on MNIST and Fashion-MNIST. The paper also relates the forward method’s linear-model performance to calibration differences seen with finite data.

Errata (Nov. 19, 2019)

  • On CIFAR-10, gradient ascent performs better, while forward correction is better on MNIST and Fashion-MNIST; the methods perform similarly on Kuzushiji-MNIST.The updated Table 4 reports this dataset comparison.Source: Errata (Nov. 19, 2019) · p. 12, Table 4 · p. 12
  • The corrected forward method performs better than previously reported, especially with linear models.The Figure 3 caption identifies the updated results as using the fixed implementation.Source: Errata (Nov. 19, 2019) · p. 12, Figure 3 · p. 12
  • For MNIST, Fashion-MNIST, and Kuzushiji-MNIST, linear models appear more confidence-calibrated than MLPs, while flexible models can be overconfident with finite data.The reliability diagrams compare predictions with the identity line as the ideal case.Source: Errata (Nov. 19, 2019) · p. 12, Figure 4 · p. 13
Loading 1810.04327v4…