Learning from Complementary Labels via Partial-Output Consistency Regularization

1 Introduction

Multi-class classification has been successfully applied in various real-world applications such as computer vision, natural language processing, and web advertising. However, collecting large-scale accurately labeled data is expensive and thus a critical bottleneck in many tasks. To mitigate this problem, various weakly supervised learning frameworks have been studied in recent years, including semi-supervised learning (SSL) [Miyato et al., 2018; Niu et al., 2013], noisylabel learning [Han et al., 2018; Feng et al., 2020b], positiveunlabeled learning [Du Plessis et al., 2014; Kiryo et al., 2017], partial label learning [Cour et al., 2011; Zhang and Yu, 2015; Zhang et al., 2017; Feng and An, 2019] and learning from pairwise similarity data [Bao et al., 2018; Hsu et al., 2018].

Complementary-label learning (CLL) [Ishida et al., 2017; Gao and Zhang, 2021] is a recently proposed weakly supervised learning framework where a multi-class classifier is learned from training instances each associated with complementary labels, which specify the classes that the instance does not belong to. In practice, asking a labeler for selecting the correct class from the list of all candidate classes is usually highly time-consuming and even impossible when the number of classes is large. Fortunately, one may choose one of the classes randomly and ask labelers whether a pattern belongs to the chosen class or not, and such a yes/no question is obviously easier to be answered. Another potential application would be data privacy. In some scenarios, collecting data requires asking extremely private questions from users. This procedure may be difficult or return unreliable answers because their privacy considerations. Nonetheless, it would be less mentally demanding if we ask the respondent to provide some incorrect answers or explain that we will transform their provided true label to a complementary label before the data is saved into cloud. Recently, CLL has also been applied to online learning [Kaneko et al., 2019], semisupervised learning [Chen et al., 2020], and medical image segmentation [Rezaei et al., 2020].

∗Corresponding author

Previous studies of CLL usually focus on unbiased risk estimator and surrogate loss. Ishida et al. [2017] and Feng et al. [2020a] show that the ordinary classification risk can be recovered by their proposed unbiased risk estimator from only complementarily labeled samples. They also give theoretical results with statistical consistency guarantees. Yu et al. [2018] propose a loss correction method with the help of complementary label transition matrix. Ishida et al. [2019] derive a framework with an unbiased risk estimator of the classification risk for arbitrary losses and models, and further improve their method by non-negative correction and a gradient ascent trick. Chou et al. [2020] propose a surrogate complementary loss framework, which avoids the extremely noisy gradient problem encountered in unbiased risk estimator. However, all previous studies neglect the power of regularization in the training of neural networks. In particular, current state-of-the-art CLL method [Chou et al., 2020] achieves the accuracy of 79.82% on CIFAR-10 with one complementary label per instance. As a counterpart, current SSL method [Xie et al., 2020] that well exploits regularization techniques, achieves highly competitive results, in which they use only 4000 labeled instances, compared with supervised learning.

This paper gives the first attempt to leverage regularization techniques to learn with only complementary labels. Focusing on this general purpose, we propose a novel method based on consistency training, namely partial-output consistency regularization. By decoupling a label vector into complementary labels and partial unknown labels, we simultaneously inhibit the outputs of these complementary labels with a complementary loss and penalize the sensitivity of the classifier on the partial outputs of these unknown classes by consistency regularization [Tarvainen and Valpola, 2017; Miyato et al., 2018]. Then we unify the complementary loss and consistency loss together by a specially designed dynamic weighting factor. Our method can be easily extended to tackle both the problems of learning from single and multiple complementary labels [Feng et al., 2020a]. A series of experiments demonstrate that our method achieves a new state-of-the-art. For example, our method achieves 94.29% accuracy on CIFAR-10 with only one complementary label per instance, which obtains substantial gain over previous state-of-the-art of 79.82%. Furthermore, our empirical study shows that with the help of consistency regularization, the proposed method obtains comparable performance with the state-of-the-art SSL framework [Xie et al., 2020].

2 Preliminaries

In this section, we first formalize some notations for ordinary multi-class classification, then introduce the preliminary knowledge for learning from complementary labels.

2.1 OrdinaryMulti-Class Classification

Let X ∈ Rd denote the feature space with d dimensions, Y = {1, 2, ..., c} denotes the label space with c classes. The labeled sample (x, y) ∈ X ×Y is sampled from an unknown distribution p(x, y). The goal of ordinary multi-class classification is to learn a parameterized function f(x) : X →Rc that minimizes the classification risk:

where L : Rc × Y → R is a multi-class classification loss function. In this paper, we consider a common case where the function f is a deep neural network with the softmax output layer. Since the distribution p(x, y) is unknown, we use the empirical risk ̂R(f) to approximate R(f). Assuming a dataset {(xi, yi)}ni=1 is independently drawn from distribution p(x, y), then we have

2.2 Complementary-Label Learning

Different from ordinary multi-class classification, in CLL, we are given only a complementary label ¯ y for each instance. rIshida et al. [2017] assume that a complementarily labeled dataset {(xi, ¯ yi)}ni=1 is sampled from the following distribution:

which implies that all other labels except the correct label are chosen to be the complementary label with uniform probabilities.

In this paper, we consider a more general setting where each instance is associated with multiple complementary labels, namely multiple complementary-label learning (MCLL) [Feng et al., 2020a]. Suppose a MCLL dataset is represented as {(xi, ¯ Yi )}ni=1 , where ¯ Yi is a set of complementary labels for the instance xi. Let us denote the size of the complementary label set by a random variable s, which is sampled from a distribution p(s). Then, we assume that each sample is drawn from the following distribution:

where

It is obvious that when p(s=1)=1, the distribution expressed by Eq.(4) reduces to the distribution in Eq.(3), hence the MCLL problem results in the single CLL problem. Our goal is still to learn a classifier that minimizes the classification risk (1), but only from complementarily labeled training samples. The empirical risk becomes:

where ¯ L is a specifically designed loss function for learning form complementary labels.

Feng et al. [2020a] present a loss formulation which gives unbiased risk estimator by employing any multi-class classification loss L:

When | ¯ Yi| = 1, which means p(s = 1) = 1, the above loss function can be directly used in single CLL. As discussed in [Feng et al., 2020a], this loss formulation is a generalization of [Ishida et al., 2017] and [Ishida et al., 2019]. Chou et al. [2020] propose a surrogate complementary loss framework, which achieves highly competitive empirical results, although their proposed surrogate losses are biased to the ordinary classification risk. Different from commonly used losses which are non-increasing functions of the output of the true class, surrogate complementary losses need to be non-decreasing functions of the output on the complementary classes. For example, a modified log loss which minimizes the output of the complementary class is one of the baseline surrogate complementary losses proposed in Chou et al. [2020]:

where fy(x) denotes the model output of x on class y. According to the results of our re-implementation, this simply modified log loss achieves current state-of-the-art performance in single CLL problem.

3 Methodology

In this section, we give the first attempt to leverage regularization techniques in CLL. We present the overview of our proposed method in Subsection 3.1, then introduce the detailed techniques in Subsection 3.2 and 3.3. We discuss a further extension of CLL framework in Subsection 3.4.

3.1 Partial-Output Consistency Regularization

A recent line of work in weakly supervised learning has been proposed to utilize unlabeled samples to enforce smoothness and consistency of the model predictions [Tarvainen and Valpola, 2017; Miyato et al., 2018; Xie et al., 2020]. Generally speaking, their proposed methods simply regularize model prediction outputs to be invariant to small changes applied to the input space of samples. The core idea of this framework is intuitive because a good model should be robust to small perturbations in the input space of samples.

Following this idea, we propose to use consistency regularization on partial outputs to learn from complementary labels. Firstly, we decouple the label vector of each sample into two parts: complementary labels and partial unknown labels. On these complementary labels, we can minimize the corresponding conditional probabilities to inhibit the outputs of the learned model. In recent years, several surrogate complementary losses have been proposed to this end [Chou et al., 2020; Feng et al., 2020a]. For example, the complementary log loss (see in Eq.(8)) can be used in single CLL scenario, and we can extend it to a more generic formulation which can learn from both single and multiple complementary labels:

Then we employ consistency regularization on the partial unknown classes to penalize the sensitivity of the classifier outputs among inputs with small noises. According to the basic assumption that the outputs of a robust model should not be significantly affected by natural and small input changes, one can improve the robustness of the model by minimizing a divergence metric between the outputs of the original sample and samples with injected small noises. Xie et al. [2020] suggest that data augmentation methods, which are widely used for expanding training data size in supervised learning, can lead to strong performance when used in consistency training framework. These advanced data augmentation techniques can preserve the label of the original example while are diverse and natural. Formally, the objective of partial-output consistency regularization can be expressed as the following cross-entropy between the prediction of original input and augmentations:

where AUGj (xi) denotes the j-th augmented version of original input xi, and m is the number of augmentations used for consistency training. The practical implementation of this augmentation process will be introduced in next subsection.

˜ fy(xi) denotes the re-normalized output of xi on class y, which is difined as:

The re-normalized process makes sure that the distribution of partial outputs on unknown classes is still a valid probability distribution. Note that we use ˆ f, a fixed copy of the current model, to detach the gradient propagation through ˜ f (xi), as suggested by Miyato et al. [2018]. Then we can unify the complementary loss and consistency regularization loss together under a single loss function, which is defined as:

where the complementary loss ¯ Llog can be replaced by other losses like exponential loss or upper-bound log/exponential loss [Feng et al., 2020a]. The weighting factor λ is used to balance the complementary loss and the consistency loss, which will be shown important for stable training in Subsection 3.3. Finally, we replace ¯ L in Eq.(6) by the unified loss ¯ Ltotal and learn by minimizing the empirical risk with ¯ Ltotal .

3.2 Data Augmentation

The augmentations used in Eq.(10) need to be different from the original input as well as preserve the semantic information. In recent years, different augmentation strategies have been proposed to generate diverse and natural augmentations. Among existing data augmentation methods, AutoAugment [Cubuk et al., 2019] is an empirically promising method which automatically searches for augmentation policies from PIL, a popular Python image library, by evaluating the quality of a particular policy directly on the dataset of interest. In this work, we use the searched policies released by Cubuk et al. [2019] in our consistency training procedure. Following the original literature of AutoAugment, we concatenate the best searched policies into a policy pool, and randomly choose a policy to produce an augmentation. We additionally use another promising augmentation technique Cutout [DeVries and Taylor, 2017] after applying AutoAugment. Although we restrict our attention to the image classification tasks in this paper, it is worth noting that for language tasks, backtranslation has been successfully used to generate augmentations which are diverse while preserving the semantics of the original sentences [Edunov et al., 2018; Cubuk et al., 2019].

3.3 DynamicWeighting Factor

The overall objective presented in Subsection 3.1 is a weighted combination of the complementary loss and the consistency loss, controlled by a hyperparameter λ. Empirically, we observe that the weighting factor λ significantly affects the performance of our method. We use an illustrative experiment to demonstrate this point.

We adopt PreAct-ResNet-18 network [He et al., 2016] as the base model and train on CIFAR-10 dataset with fixed λ equal to 0.1 and 1 respectively (the implementation details are the same with Subsection 4.1). Figure 1 (left) shows the mean, best and worst of test accuracies of 5 trials. We can see that: (1) when using a smaller weighting factor, which means the unified loss is dominated by complementary loss, model always achieves better performance in the initial training stage; (2) when using a larger weighting factor, the discrepancy of test accuracies between different trials becomes significantly larger, and the mean accuracy is much lower than that trained with smaller weighting factor; (3) the best performance among 5 trials with λ = 1 is better than that with λ = 0.1 in the end of training even if it is worse than all cases with λ = 0.1 in the beginning epochs.

This phenomenon may be caused by the low quality model outputs in early stage of training. Specifically, in the beginning epochs, model may produce highly random predictions, thus the consistency loss which involves those low quality predictions would cause error accumulation problem during training. This suggests us to use a small weighting factor in the beginning of training and relatively large one in the later stage. To this end, we propose a dynamic weighting scheme which gradually increases this factor during training epochs. Specifically, we use an increasing function to obtain this dynamic factor at epoch t:

After substituting the fixed weighting factor λ in Eq.(12) by above function, our method trains with weighting factor which equals to 0 at the beginning epoch and increases it to λ at epoch T ′ . After T ′ epochs, it keeps a constant λ until the end of training. We also use an illustrative comparison between our dynamic weighting scheme and constant weighting scheme to demonstrate the effectiveness of the dynamic scheme. As is shown in Figure 1 (right), the dynamic weighting scheme achieves high mean accuracy as well as stable performance across all trials.

3.4 Further Extension

In some particular situations, we may have ordinarily labeled data in addition to complementarily labeled data. Practically, asking a labeler for selecting the true label from all candidates is usually difficult and even impossible in some domains. Instead, the yes/no question which asks whether an instance belongs to a specific class is easier to be answered. Based on this query type, one can choose to iteratively ask labelers about an instance until its true label is recovered, which results in a SSL problem. One can also query each instance with a single time though the true labels may not be recovered. The latter strategy gives a dataset with two parts: ordinarily labeled subset and complementarily labeled subset. This particular learning setting, i.e. learning from both ordinary and complementary labels, can be considered as an alternative to SSL, and our consistency training framework can be directly used in this problem by transiting an ordinary label to c - 1 complementary labels. We will use a particular experiment to demonstrate the superiority of our method compared with the SSL framework under same data labeling cost in experiment section.

4 Experiments

4.1 Experimental Setup

Datasets

To verify the superiority of our method, we conduct experiments on three commonly used image datasets: SVHN, CIFAR-10 and CIFAR-100. SVHN contains 73,257 training samples and 26,032 test samples. Both of CIFAR-10 and CIFAR-100 contain 50,000 training samples and 10,000 test samples. SVHN and CIFAR-10 have 10 classes and CIFAR-100 has 100 classes. We conduct experiments by considering both the scenarios of single CLL and MCLL. To generate single complementary label, we randomly select one of the complementary classes per instance. To generate multiple complementary labels, we first instantiate p(s) = (c-1 s )/(2c -2), ∀s ∈ {1, ..., c-1}, which represents the ratio of the number of label sets whose size is s to the number of all possible label sets. Then for each instance x, we sample s from p(s), and then sample a complementary label set ¯ Y with size s from p( ¯ Y ) = 1/(c-1 s ).

Comparison Methods

For single CLL, we compare our method with PC [Ishida et al., 2017], GA [Ishida et al., 2019], Forward [Yu et al., 2018], SCL-EXP and SCL-LOG [Chou et al., 2020], where SCL means surrogate complementary loss. We also compare with two MCLL methods: UB-EXP and UB-LOG [Feng et al., 2020a], where UB is the short form of upper bounded, since single CLL can be considered as a special case of MCLL. For MCLL, except these two native MCLL methods, we also compare with SCL-EXP and SCL-LOG by extending them to learn from multiple complementary labels (see in Eq.(9)). Note that PC, GA, and Forward can also be used in MCLL after decomposing each sample into multiple samples each with a single complementary label. However, the empirical results of [Feng et al., 2020a] showed that UB-EXP and UB-LOG consistently outperform the decomposition strategy. Thus the decomposition-based methods are not involved in the MCLL scenario.

Implementation

Our implementation is based on PyTorch [Paszke et al., 2019] and experiments were carried out with NVIDIA Tesla V100 GPU. We train the commonly used LeNet-5, PreAct-ResNet18 and Wide-ResNet-34-10 with 200 epochs, and use SGD

as the opimizer with a momentum of 0.9, a weight decay of 1e-4, and a batch size 64 in our experiments. We set the initial learning rate as 0.1 across all datasets and divide it by a factor of 10 after 100 epochs and 150 epochs respectively. The hyperparameters used in Eq.(13) are set as T ′ = 100 and λ = 1. The number m of augmented instances used for consistency training is set to 2 and these augmentations are generated using the techniques discussed in Subsection 3.2. For CIFAR-10 and CIFAR-100 we further use three standard image pre-processing techniques, normalization, horizontal flipping and random cropping, to all training samples. In single CLL experiments, we use SCL-LOG as the complementary loss as is shown in Eq.(12). In MCLL experiments, we replace the complementary loss SCL-LOG in Eq.(12) by UB-LOG, which is specifically designed for MCLL.

We re-implement all the comparison methods using the same baseline image pre-processing techniques, network architecture, optimizer and learning policies with our method except PC and GA, in which we failed to achieve comparable results using our policies. Hence we maintain the learning policies reported in their original literatures.

4.2 Experimental Results

Comparison Results

Table 1 presents the comparison results on SVHN and CIFAR-10 in single CLL scenario. We use different network architectures according to the complexity of each dataset. In our experiments, the baseline image pre-processing techniques are adopted in all methods for fair comparison, thus our re-implementation results are better than the original results reported in their literatures. Nevertheless, our method achieves new state-of-the-art results across all cases. On SVHN, which is a relatively simple and easy dataset, existing methods can already achieve considerably high accuracies. With the help of consistency training, we push the state-ofthe-art one step forward. The improvements of performance are more significant on CIFAR-10, which is a more complex dataset than SVHN. In particular, when using PreActResNet-18, our method achieves the accuracy of 94.29%, which is significantly better than the previous state-of-the-art accuracy of 79.82% by SCL-LOG. Additionally, by learning with a single complementary label per instance, our method obtains surprisingly comparable results with ordinary supervised learning (see in Table 3).

Table 2 presents the comparison results on SVHN, CIFAR10 and CIFAR-100 in MCLL scenario. Here we use LeNet-5 on SVHN and PreAct-ResNet-18 on CIFAR datasets. UBLOG with A&C means we additionally apply AutoAugment and Cutout after the baseline image pre-processing when learning with UB-LOG. We also compare with a degenerate version of our method, in which the re-normalization process (i.e. Eq.(11)) is abandoned. In MCLL experiments, we use the complementary label generation strategy introduced in Subsection 4.1, thus the expected number of complementary labels per instance is c/2. As shown in Table 2, our method still outperforms all baselines in MCLL scenario. In addition, the results of UB-LOG with A&C show that simply using these augmentations in CLL can not give improvements in all cases.

Parameter Sensitivity Analysis

In Figure 2, we show the learning curves of dynamic weighting scheme and constant weighting scheme with different factor values. The results are very similar with the illustrative experiment presented in Subsection 3.3. The model tends to have unstable performance when adopting larger weighting factors in the initial stage. This issue is especially serious on SVHN, on which the mean result with λ = 1 is significantly incomparable. When using constant weighting scheme, the preferable values of λ on SVHN and CIFAR-10 vary widely, which means this value needs to be manually searched from a validation set in practice. Fortunately, the proposed dynamic weighting scheme can effectively alleviate this issue. When adopting dynamic weighting scheme with λ = 1, we can see that the mean accuracy is very close to the best one of constant weighting factors on both datasets. For reliable usage, the hyperparameter λ in our dynamic weighting scheme can be chosen around 1. We also show the comparison results between the constant and dynamic weighting schemes with λ ranging form 0.2 to 1.4, the comparison results demonstrate that the dynamic weighting scheme is more robust to λ.

Comparison with the SSL Framework

As we discussed in Subsection 3.4, in some particular domains, CLL can be considered as an alternative to SSL. To empirically verify this point, we re-implement the consistency training-based SSL framework [Xie et al., 2020] with the same network, learning policies, and data augmentations of our method. Figure 3 presents the results of our method trained in single CLL (gray line) and the SSL framework with controlled number of labels (red line). In addition, we consider a practical scenario where we can only query instance-label pairs and obtain the corresponding yes/no answers. Suppose the total query times q = m, where m denotes the size of dataset. By randomly choosing one label per instance to ask the labeler, we can obtain a dataset with m/c ordinarily labeled samples and m(c -1)/c complementarily labeled samples. Besides, we can iteratively query the labels for each instance until its true label is recovered, which results in 2m/(c +1) labeled samples and m(c - 1)/(c + 1) unlabeled samples. From this perspective, we conduct experiments to compare our CLL method with the SSL framework under same data labeling cost. For SVHN, we use our method with 7,325 ordinarily labeled samples in addition to 65,932 complementarily labeled samples, and use the SSL framework using 13,320 labeled samples in addition to 59,937 unlabeled samples. For CIFAR-10, we use our method with 5,000 ordinarily labeled samples as well as 45,000 complementarily labeled ones, and use 9,090 labeled samples in addition to 40,910 unlabeled ones in the SSL framework. As shown in Figure 3, in this special case, our method (black line) obtains highly competitive performance compared with the SSL framework.

5 Conclusion

In this paper ,we give the first attempt to leverage the consistency training framework in CLL. We present a unified loss which simultaneously inhibits the outputs of complementary classes and penalizes the output sensitivity on the partial unknown classes. Based on the empirical observation of the importance of weighting factor, we propose a dynamic weighting scheme which helps our consistency training framework obtain stable and accurate results. We conduct a series of experiments showing that the proposed method achieves a new state-of-the-art in CLL. Furthermore, we compare our method with state-of-the-art SSL framework under same labeling cost, which demonstrates that our method is highly competitive compared with SLL framework.

Acknowledgements

The authors wish to thank the anonymous reviewers for their helpful comments and suggestions. This work was supported by the National Key R&D Program of China (2018YFB1004300), the Postgraduate Research & Practice Innovation Program of Jiangsu Province (KYCX21 0151), and the China University S&T Innovation Plan Guided by the Ministry of Education. We thank the Big Data Center of Southeast University for providing the facility support on the numerical calculations in this paper.