Source-linked AI summary
Learning from Complementary Labels
Takashi Ishida, Gang Niu, Weihua Hu, Masashi Sugiyama
TL;DR
Expensive ordinary labels motivate learning from complementary labels, which only indicate a class a pattern does not belong to. The paper derives unbiased risk estimation under a symmetric loss condition, establishes optimal-rate error bounds, and shows combination with ordinary labels and experimental usefulness. Its scope includes non-convex losses and leaves the broader role of the symmetric condition for future investigation.
Problem
Ordinary class labels are costly to collect, motivating a less expensive multi-class setting based on labels specifying classes that patterns do not belong to.
Method
The paper minimizes a complementary-label risk whose estimator is unbiased under a symmetric loss condition and can be combined with ordinary-label risk.
Results
The method is consistent with estimation error bounds achieving the optimal parametric rate Op(1/√n), and experiments demonstrate practical usefulness.
Takeaways & Limitations
Complementary labels provide a practical data-efficient classification approach that can be integrated with ordinary labels and optimized using stochastic algorithms.
Takeaways & Limitations
The required symmetric condition also appears in other weakly supervised formulations, but its broader role remains to be investigated.
Abstract
from arXiv · showhide
Collecting labeled data is costly and thus a critical bottleneck in real-world classification tasks. To mitigate this problem, we propose a novel setting, namely learning from complementary labels for multi-class classification. A complementary label specifies a class that a pattern does not belong to. Collecting complementary labels would be less laborious than collecting ordinary labels, since users do not have to carefully choose the correct class from a long list of candidate classes. However, complementary labels are less informative than ordinary labels and thus a suitable approach is needed to better learn from them. In this paper, we show that an unbiased estimator to the classification risk can be obtained only from complementarily labeled data, if a loss function satisfies a particular symmetric condition. We derive estimation error bounds for the proposed method and prove that the optimal parametric convergence rate is achieved. We further show that learning from complementary labels can be easily combined with learning from ordinary labels (i.e., ordinary supervised learning), providing a highly practical implementation of the proposed method. Finally, we experimentally demonstrate the usefulness of the proposed methods.
1 Introduction
The paper introduces learning from complementary labels, where annotators identify a class a pattern does not belong to, as a less costly alternative to ordinary labeling. It develops an unbiased risk estimator under a symmetric loss condition, establishes optimal-rate error bounds, combines complementary and ordinary labels, and demonstrates practical usefulness experimentally.
- Motivation: Complementary labels identify a class that a pattern does not belong to, potentially reducing annotation effort when many candidate classes exist.Choosing an incorrect class can be easier than selecting the correct class from a long list.
- Method: The paper develops a direct risk-minimization framework that estimates classification risk unbiasedly from complementary labels when the loss satisfies a symmetric condition.The sigmoid and ramp losses satisfy the stated condition.
- Theory: The proposed method has estimation error bounds with optimal parametric rate Op(1/√n) and is shown to be consistent.Here n denotes the number of complementarily labeled data.
- Combining labels: Complementary classification can be combined with ordinary classification to use both label types in a data-efficient approach.The paper highlights crowdsourcing as a setting where workers could answer whether a pattern belongs to a selected class.
- Experiments: Experiments demonstrate the practical usefulness of the proposed methods.The introduction states this conclusion without reporting a specific experimental value here.
2 Review of ordinary multi-class classification
Ordinary multi-class classification learns a classifier that minimizes expected classification risk using patterns paired with their class labels. In practice, the unknown-data expectation is replaced by an empirical average over training samples.
- Classification setup: Ordinary multi-class classification assigns each pattern a class label and seeks a classifier minimizing classification risk.The classifier is formulated using class-specific binary classifiers.
- Multi-class losses: One-versus-all and pairwise-comparison losses construct multi-class losses from binary classifiers and a binary loss penalizing small margins.The pairwise-comparison formulation compares classifiers, while one-versus-all uses each classifier against the rest.
- Empirical risk: The expectation over the unknown data distribution is empirically approximated with training samples to obtain a practical classification objective.This empirical approximation supports direct optimization from observed training data.
3 Classification from complementary labels
The paper formulates complementary classification as minimizing ordinary classification risk using samples labeled only with classes the patterns do not belong to. Under symmetric loss constraints, the risk can be estimated unbiasedly, with supported OVA and PC constructions and non-convex training losses.
- Problem formulation: Complementary classification learns from samples specifying a class that each pattern does not belong to, while targeting the ordinary classification risk.The samples are drawn independently from an unknown distribution.
- Risk estimation: An unbiased classification-risk estimator is available from complementary samples when the complementary loss satisfies the theorem’s stated conditions.The framework uses a complementary loss defined on complementarily labeled samples.
- Loss conditions: The loss constraints require a symmetric relationship in which lower loss for belonging to a class corresponds to higher loss for not belonging to that class.This condition links ordinary and complementary interpretations of the same pattern-class relation.
- Loss constructions: OVA satisfies the conditions with M1 = K and M2 = 2, while PC satisfies them with M1 = K(K −1)/2 and M2 = K −1.These constants characterize the respective multi-class loss constructions under the stated conditions.
- Binary losses: The sigmoid, ramp, and zero-one binary losses satisfy the symmetric condition, although these losses are non-convex.The paper recommends sigmoid or ramp losses for training and zero-one loss for hyper-parameter tuning.
4 Estimation Error Bounds
The paper establishes estimation-error guarantees for complementary-label risk minimization, including consistency and the optimal parametric convergence rate under a linear-in-parameter function class.
- Estimation-error analysis: Estimation error bounds are derived for the proposed complementary-label method using Rademacher-complexity-based uniform deviation bounds.The analysis defines loss-induced function classes for OVA and pairwise-comparison losses before deriving the bounds.
- Estimation-error analysis: Theorem 6 provides high-probability estimation-error bounds when empirical risk is minimized with either LOVA or LPC.The theorem covers both one-versus-all and pairwise-comparison loss constructions.
- Consistency and rate: As n →∞, the learned classifier is consistent because its true risk converges to the optimal risk.The stated result is R(bf) → R(f*) as the sample size increases.
- Consistency and rate: O_p(1/√n) is achieved for the linear-in-parameter model, matching the optimal parametric rate without additional strong assumptions.The rate follows from the Rademacher-complexity bound R_n(G) ≤ C_wC_φ/√n.
5 Incorporation of ordinary labels
The method combines ordinary- and complementary-label risks through a convex combination, allowing both data types to contribute to classifier training.
- Risk combination: A convex combination of ordinary- and complementary-label classification risks uses both kinds of labeled data.The interpolation weight α ranges from 0 to 1.
- Risk combination: The hyperparameter α ∈[0, 1] interpolates between the ordinary-label and complementary-label risks.The combined risk is approximated by corresponding sample averages.
- Practical use: The combined risk estimator can use ordinary and complementary labels to obtain better classifiers.The paper states that this combination can be naturally obtained through crowdsourcing and evaluates it experimentally.
6 Experiments
The experiments compare complementary-label losses, benchmark the proposed method against partial-label and multi-label baselines, and test combining ordinary with complementary labels. Performance declines as the number of classes increases, while the proposed method is competitive across datasets and combination training tends to outperform either label source alone.
- 6.1 Comparison of different losses: Accuracy deteriorates as the number of classes increases because complementary labels provide weaker supervised information in larger-class settings.The MNIST experiment varies the number of classes from 3 to 10.
- 6.1 Comparison of different losses: The four combinations of OVA or PC formulations with sigmoid or ramp losses show no significant difference in classification accuracy.PC with the sigmoid loss is selected as the representative method for subsequent experiments.
- 6.2 Benchmark experiments: The benchmark compares PC/S with partial-label and multi-label baselines across WAVEFORM1, WAVEFORM2, SATIMAGE, PENDIGITS, DRIVE, LETTER, and USPS.The datasets use several class-label settings with equal numbers of data in each class.
- 6.3 Combination of ordinary and complementary labels: OL & CL tends to outperform both OL and CL, demonstrating the usefulness of combining ordinarily and complementarily labeled data.The combination experiment uses α = 1/2 and a 1:(K −1) division of ordinary- and complementary-label data.
7 Conclusions
The paper introduces learning from complementary labels and establishes unbiased risk estimation under a symmetric loss condition. It also proves optimal parametric convergence, supports combination with ordinary labels, and identifies privacy-aware learning as a future context for investigation.
- 7 Conclusions: The paper defines learning from complementary labels as a setting where unbiased classification-risk estimation uses only complementary data under a symmetric loss condition.The risk estimator can be minimized with stochastic optimization algorithms such as Adam for large-scale training.
- 7 Conclusions: The proposed method has estimation error bounds and achieves the optimal parametric rate.These are theoretical guarantees established for the complementary-classification method.
- 7 Conclusions: Complementary classification can be combined with ordinary classification.The paper presents this combination as a data-efficient classification method.
- 7 Conclusions: Complementary labels may also be useful for privacy-aware machine learning, but this issue is left for future investigation.The motivating example involves answering private questions with one of the incorrect answers.
- 7 Conclusions: The framework requires the loss to satisfy a symmetric condition that also appears in other weakly supervised learning formulations.The paper identifies closer investigation of this condition as an open direction.
B Proof of Lemma 3
The proof of Lemma 3 decomposes the relevant complexity expression into terms controlled using supremum sub-additivity, distributional symmetry, and Talagrand’s contraction lemma.
- B Proof of Lemma 3: Rewriting the OVA loss expression initiates the proof of the complexity bound.The proof proceeds from the rewritten eLOVA(f(xi), yi) expression.
- B Proof of Lemma 3: The supremum is bounded by separating terms through sub-additivity.This decomposition is used to control the resulting complexity expression.
- B Proof of Lemma 3: The first term is independent of yi and is bounded by K/(K −1) · Rn(eℓ◦G).Independence from yi permits the stated standard Rademacher-complexity bound.
- B Proof of Lemma 3: For the second term, αi = 2I(y = yi) −1 is introduced and αiσi is treated as having the same distribution as σi.The resulting term is bounded using Rademacher complexity and Talagrand’s contraction lemma.
- B Proof of Lemma 3: The second term is bounded by K(K −2)/(K −1) · Rn(eℓ◦G).This bound follows after applying the same complexity-control strategy to the second component.
C Proof of Lemma 4
The proof of Lemma 4 again uses supremum sub-additivity and Talagrand’s contraction lemma to bound a class of pairwise classifier differences.
- C Proof of Lemma 4: The proof handles the second term using the technique developed in Lemma 3.This transfers the earlier complexity-control strategy to the present bound.
- C Proof of Lemma 4: Sub-additivity of the supremum separates the expression into components for bounding.The same supremum property is used as in the preceding proof.
- C Proof of Lemma 4: The class Gy,y′ contains functions x 7→gy′(x) −gy(x) for classifier pairs gy, gy′ ∈G.Talagrand’s contraction lemma is then invoked for this difference-function class.
D Proof of Lemma 5
The proof establishes one direction of the deviation bound for LOVA and indicates that the reverse direction follows analogously. It controls the empirical-risk change under one-sample replacement and applies concentration and symmetrization arguments.
- The proof treats the LOVA case in one deviation direction, with the opposite direction handled similarly.
- Under the symmetric condition, the relevant loss-function norm equals 2 when the functions are measurable.
- Replacing one sample changes the supremum deviation by at most 2(K −1)/n.
- McDiarmid’s inequality is applied to obtain a concentration bound for the single-direction uniform deviation.
- Because R(f) = E[ bR(f)], symmetrization is then used to complete the deviation analysis.