PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning with Biased Complementary Labels

Xiyu Yu, Tongliang Liu, Mingming Gong, Dacheng Tao

arXiv:1711.09535v3stat.MLcs.LG

TL;DR

The paper studies complementary-label learning when human and observation biases make transition probabilities non-uniform. It estimates those probabilities from a small clear-observation set, modifies losses and neural networks using the transition matrix, and reports over 10% accuracy gains over state-of-the-art methods while sometimes nearly matching true-label learning.

  • Problem

    Complementary labels are cheap, but prior uniform-selection assumptions do not reflect biased annotation, making transition-probability estimation a central problem.

  • Method

    The method estimates transition probabilities from clear observations, modifies traditional losses, and inserts a Q⊤ transition layer into deep classifiers.

  • Results

    Accuracy gains of over 10% over state-of-the-art methods are reported across UCI, MNIST, CIFAR, and Tiny ImageNet, with near-true-label performance in some situations.

  • Takeaways & Limitations

    Biased complementary labels can support theoretically consistent classification and high performance using a small correctly labeled set for transition estimation.

  • Takeaways & Limitations

    The class-conditional bias assumption requires complementary labels to be independent of features given the true class, and identification may require an invertible transition matrix.

Abstract

from arXiv · show

In this paper, we study the classification problem in which we have access to easily obtainable surrogate for true labels, namely complementary labels, which specify classes that observations do \textbf{not} belong to. Let $Y$ and $\bar{Y}$ be the true and complementary labels, respectively. We first model the annotation of complementary labels via transition probabilities $P(\bar{Y}=i|Y=j), i\neq j\in\{1,\cdots,c\}$, where $c$ is the number of classes. Previous methods implicitly assume that $P(\bar{Y}=i|Y=j), \forall i\neq j$, are identical, which is not true in practice because humans are biased toward their own experience. For example, as shown in Figure 1, if an annotator is more familiar with monkeys than prairie dogs when providing complementary labels for meerkats, she is more likely to employ "monkey" as a complementary label. We therefore reason that the transition probabilities will be different. In this paper, we propose a framework that contributes three main innovations to learning with \textbf{biased} complementary labels: (1) It estimates transition probabilities with no bias. (2) It provides a general method to modify traditional loss functions and extends standard deep neural network classifiers to learn with biased complementary labels. (3) It theoretically ensures that the classifier learned with complementary labels converges to the optimal one learned with true labels. Comprehensive experiments on several benchmark datasets validate the superiority of our method to current state-of-the-art methods.

1 Introduction

The paper addresses complementary-label learning when annotators select non-true classes non-uniformly because of observation and human-experience biases. It estimates these transition probabilities, modifies losses and neural classifiers, proves convergence to true-label optima, and reports strong benchmark performance.

  • Complementary labels provide cheap supervision, but large-scale true-label collection is expensive, time-consuming, or sometimes impossible.
  • Annotators’ observation- and experience-dependent biases make complementary labels non-uniform, with some classes potentially never selected for particular cases.
  • The paper models biased annotation through transition probabilities P(¯Y = i|Y = j) and identifies their estimation as a central learning problem.
  • The method estimates transition probabilities without bias, modifies traditional losses, extends deep classifiers, and theoretically guarantees convergence to the true-label optimal classifier.
  • Accuracy gains of over 10% against state-of-the-art methods are reported across UCI, MNIST, CIFAR, and Tiny ImageNet, with near-true-label performance in some situations.
  • Unlike prior work focused on uniform transitions, this method targets differing transition probabilities and generalizes loss modification beyond OVA and PC losses.
  • Transition-layer strategies from noisy-label learning are adapted here to complementary labels, whose transition matrices have zero diagonal entries and may be non-invertible empirically.

3 Problem Setup

The problem setup models complementary-label selection with a class-conditional transition matrix, allowing non-uniform probabilities while excluding the true class. The paper seeks consistent learning and efficient convergence under this biased setting.

  • The setting uses many examples with biased complementary labels and a very small correctly labeled set used only to estimate transition probabilities.
  • For each example, a complementary label is selected from all classes except the true class, with a probability assigned to each eligible label.
  • The assumption P(¯Y = ¯y|X = x, Y = y) = P(¯Y = ¯y|Y = y) makes complementary-label bias depend only on classes, not features within classes.
  • The transition matrix Q has entries Qij = P(¯Y = j|Y = i) and zero diagonal entries.
  • Under uniform selection, off-diagonal entries equal 1/(c−1), whereas this paper studies settings where those transition probabilities differ.
  • The setup asks how to modify losses for convergence to the true-label optimum and how quickly that convergence occurs.

4 Methodology

The methodology transforms true-label prediction into complementary-label prediction using the transition matrix, modifies losses accordingly, and implements the transformation in a deep network. It also addresses practical estimation and matrix-invertibility conditions.

  • The paper reviews true-label risk minimization, modifies losses for complementary labels, proposes a deep model, and proves consistency with the true-label optimal classifier.
  • Standard supervised learning estimates class probabilities through a classifier whose optimal function minimizes expected risk and whose empirical risk is computed from labeled examples.
  • Figure 2 implements the transformation by adding a layer that multiplies softmax output by Q⊤; the network can thereby learn classifiers for complementary and true labels.
  • Ordinary losses trained on complementary labels learn P(¯Y|X), so modified losses are required to recover a classifier optimal for true labels.
  • The modified empirical solution converges to the true-label optimal classifier as n increases.
  • The transition matrix transfers P(Y|X) to P(¯Y|X), while Q−⊤ can recover true-label probabilities when identification uses an invertible matrix.
  • The forward process does not require Q−⊤, and experiments report high performance even with singular transition matrices when no column of Q is all-zero.

5 Identification of the Optimal Classifier

The proposed loss modification identifies the optimal true-label classifier from biased complementary labels under an invertible transition matrix and a stated assumption. This guarantee applies to losses including cross-entropy and square-error loss.

  • Under Assumption 1, minimizing the expected risk yields an optimal mapping g* suitable for the identification proof.
  • If Q is invertible and Assumption 1 holds, the minimizer of complementary-label risk is also the minimizer of true-label risk.
  • With sufficient complementary-label data, the learned classifier converges to the optimal true-label classifier.
  • The identification result extends to traditional losses such as cross-entropy and square-error loss when the relevant assumption is satisfied.The paper explicitly notes that square-error loss satisfies Assumption 1 and applies the method to cross-entropy loss.

6 Convergence Analysis

The convergence analysis bounds estimation error and shows that the classifier learned from complementary labels approaches the true-label optimum. Under balanced complementary-label frequencies, the derived dependence on the number of classes improves over prior bounds for large class counts.

  • The analysis derives an upper bound showing convergence of the complementary-label classifier to the optimal true-label classifier.The argument relates excess complementary-label risk to estimation error and uses uniform-convergence tools.
  • Rademacher complexity and concentration inequalities are used to bound the generalization error for the modified loss.
  • The modified-loss analysis rewrites the risk by complementary-label class and defines empirical counterparts using the counts n_i.
  • Under the theorem’s conditions, the final bound applies when the loss is upper bounded by M and the complementary-label class prior is given.
  • O(c√c/√n) is the derived rate when complementary-label frequencies are balanced and n_i is about n/c, smaller than prior bounds for very large c.
  • The bound can be loose when a complementary-label frequency or its associated sample count is small.
  • The stated generalization-bound framework assumes an upper-bounded loss, while cross-entropy-specific bounds require additional strategies.

7 Estimating Q

Because the transition matrix cannot be estimated from complementary labels alone without auxiliary information, the method uses a small set of manually true-labeled anchor observations. Conditional complementary-label probabilities on these anchors estimate Q.

  • The transition matrix Q is not known in the proposed learning procedure and therefore must be estimated.
  • Without auxiliary information, complementary labels alone cannot identify Q because it is associated with the true-label class priors.
  • The method assumes that 5 or 10 easily distinguishable observations per class receive manually assigned true labels.
  • The anchor set condition requires each class to contain observations whose posterior probability for that class is 1 and for every other class is 0.
  • For anchor observations, Q entries are obtained from P(complementary label | observation) after estimating that conditional probability with a deep network.

8 Experiments

Experiments across benchmark datasets evaluate the method under uniform, biased, sparse, manually designed, and non-invertible complementary-label settings. The method generally performs strongly, while convergence depends on the transition structure and available data.

  • Experimental setup: Experiments use UCI, USPS, MNIST, CIFAR10, CIFAR100, and Tiny ImageNet with neural-network classifiers.The implementations use one-hidden-layer networks, LeNet-5, and ResNet variants across the datasets.
  • UCI and USPS: On USPS and UCI, the method is compared with PL, ML, and PC/S using known identical transition probabilities.Table 1 reports means and standard deviations of classification accuracy over 20 trials.
  • MNIST: On MNIST, the method performs well under uniform, without0, and with0 annotation settings, while PC/S deteriorates outside the uniform setting.LM/E with an estimated transition matrix is competitive with LM/T using the true matrix.
  • CIFAR10: On CIFAR10, the method outperforms PC/S in biased settings, but LM/E performs relatively badly under the uniform setting because the transition matrix is poorly estimated.The reported explanation is that P(¯Y|X) is not well estimated in that setting.
  • Convergence analysis: With0 produces better convergence than uniform and without0 in the reported CIFAR10 experiments, because its transition uncertainty is lower.The paper states that selecting a subset can reduce the number of training examples needed for high performance, provided every class label is assigned somewhere.
  • Larger-scale datasets: For CIFAR100 and Tiny ImageNet, experiments use the with0 setting; the method achieves high accuracy on CIFAR100 comparable to learning with true labels, while PC/S performs poorly.CIFAR100’s large label space and limited per-class data prevent convergence under uniform and without0, so only with0 is tested.
  • Discussion and robustness: The method maintains performance with a non-invertible transition matrix, and manually designed transition matrices achieve performance similar to randomly selected matrices.These results support applicability to general complementary-label settings and comparable behavior across matrix-construction strategies.

9 Conclusion

The paper addresses biased complementary-label learning by modeling varying, often sparse transition probabilities and modifying losses accordingly. Experiments across datasets support superiority over current state-of-the-art methods.

  • The proposed setting allows transition probabilities between true and complementary labels to vary, with most probabilities equal to zero.
  • An effective method estimates the transition matrix from a small amount of data in an anchor set.
  • The estimated transition matrix supports modified traditional losses with theoretical convergence to the optimal classifier learned from true labels.
  • Comprehensive experiments across a wide range of datasets verify superiority over current state-of-the-art methods.

A Proof of Theorem 1

The proof connects complementary-label learning to true-label learning through posterior vectors and a modified loss. Invertibility of the transition matrix yields the true posterior as the optimal classifier.

  • The proof analyzes complementary-label learning using the modified loss function.
  • The true-label posterior vector v(X) and complementary-label posterior vector v̄(X) are related through the transition model in Eq. (11).
  • If the transition matrix Q is invertible, the optimal classifier satisfies g*(X) = v(X), ensuring v̄* = f̄*.

B Proof of Lemma 1

The proof reduces cross-entropy risk minimization to pointwise conditional-risk minimization, then uses constrained optimization to identify the optimal posterior.

  • Because cross-entropy loss is nonnegative, minimizing total risk reduces to minimizing conditional risk for every input x.
  • The conditional optimization becomes minimizing ψ(g) subject to g(x) belonging to the probability simplex.
  • The proof applies the Lagrange multiplier method and sets the derivative of the Lagrangian with respect to g to zero.
  • The resulting optimizer has components g_i*(x) = P(Y = i|x).

C Proof of Lemma 2

The proof establishes regularity of the modified loss and controls the associated function class using softmax ranking and contraction arguments.

  • The modified loss must be Lipschitz continuous with respect to the model scores h_i(X).
  • If no column of the transition matrix is entirely zero, the modified loss is 1-Lipschitz with respect to every h_j(X).
  • Differentiating the modified loss shows its score derivatives lie between -1 and 1, establishing the Lipschitz bound.
  • The proof rewrites the supremum over classifiers using the score function h because softmax preserves the rank of its inputs.
  • Talagrand’s contraction lemma is then invoked to continue the complexity argument.
Loading 1711.09535v3…