Year: 2018

Abstract:
In contrast to the standard classification paradigm where the true (or possibly noisy) class is given to each training pattern, complementary-label learning only uses training patterns each equipped with a complementary label. This only specifies one of the classes that the pattern does not belong to. The seminal paper on complementary-label learning proposed an unbiased estimator of the classification risk that can be computed only from complementarily labeled data. However, it required a restrictive condition on the loss functions, making it impossible to use popular losses such as the softmax cross-entropy loss. Recently, another formulation with the softmax cross-entropy loss was proposed with consistency guarantee. However, this formulation does not explicitly involve a risk estimator. Thus model/hyper-parameter selection is not possible by cross-validation— we may need additional ordinarily labeled data for validation purposes, which is not available in the current setup. In this paper, we give a novel general framework of complementary-label learning, and derive an unbiased risk estimator for arbitrary losses and models. We further improve the risk estimator by non-negative correction and demonstrate its superiority through experiments.

heading: 1 INTRODUCTION
text: Modern classification methods usually require massive data with high-quality labels, but preparing such datasets is unrealistic in many practical domains. To mitigate the problem, many previous works have investigated ways to learn from weak supervision: semi-supervised learning (Chapelle et al., 2006; Miyato et al., 2016; Kipf & Welling, 2017; Sakai et al., 2017; Tarvainen & Valpola, 2017; Oliver et al., 2018), learning from noisily-labeled data (Natarajan et al., 2013; Patrini et al., 2017; Ma et al., 2018), learning from positive-unlabeled data (Elkan & Noto, 2008; du Plessis et al., 2014; 2015; Kiryo et al., 2017), learning from similar-unlabeled data (Bao et al., 2018), learning from positive-confidence data (Ishida et al., 2018), and others.
In this paper, we consider learning from another type of weak but natural supervision called complementary-label learning (Ishida et al., 2017; Yu et al., 2018), where the label only specifies one of the classes that the pattern does not belong to. In contrast to the ordinary case where the true class is given to each pattern (which often needs to be chosen out of many candidate classes precisely), collecting these complementary labels is obviously much easier and less costly. A natural question is, however, is it possible to learn from such complementary labels (without any true labels)?
The problem has previously been tackled by Ishida et al. (2017), showing that the classification risk can be recovered only from complementarily labeled data. They also gave consistency gaurantee in theoretical analysis. However, they required strong restrictions on the loss functions, allowing only one-versus-all and pairwise comparison multi-class loss functions (Zhang, 2004) with certain non-convex binary losses. This is a severe limitation when we use deep learning since the softmax cross-entropy loss is often used to boost the classification performance.
Later, Yu et al. (2018) proposed a different formulation for complementary labels by employing the forward loss correction technique (Patrini et al., 2017) to adjust the learning objective. Their proposed risk estimator is not necessarily unbiased but the minimizer is theoretically guaranteed to be consistent with the minimizer of the risk for ordinary labels (under an implicit assumption on the model for convergence analysis).
They also extended the problem setting to where complementary labels are chosen in an uneven (biased) way. This is a realistic problem setting because labelers are more likely to complementarily label a pattern when they feel it is not a certain class which they have more knowledge or experience about.
In this paper, we first derive an unbiased risk estimator with a general loss function, making any loss functions available for use: not only the softmax cross-entropy loss function but other convex/nonconvex loss functions can also be applied. We also do not have implicit assumptions on the classifier, allowing both linear and non-linear models.
Yu et al. (2018) does not have an unbiased risk estimator, which means users will need clean data with true labels to calculate the error rate during the validation process. On the other hand, our proposed unbiased risk estimator can handle complementarily labeled validation data not only for our learning objective, but also for Yu et al. (2018). This is helpful since collecting clean data is usually much more expensive.
Finally, our proposed unbiased risk estimator has an issue that it is unbounded from below and suffers from the classification risk going to negative after learning, leading to overfitting. We further propose a non-negative correction to the original unbiased risk estimator to improve our estimator. We experimentally show that our proposed method is comparable to or better than previous methods (Ishida et al., 2017; Yu et al., 2018) in terms of classification accuracy.

heading: 2 REVIEW OF PREVIOUS WORKS
text: In this section, we explain the notations and review the formulations of learning from ordinary labels, learning from complementary labels, and learning from both ordinary and complementary labels.
Learning from ordinary labels Let X be an instance space and D be the joint distribution over X × [K] for class label set [K] := {1, 2, . . . ,K}, with random variables (X,Y ) ∼ D. The data at hand is sampled independently and identically from the joint distribution: {(xi, yi)}ni=1
i.i.d.∼ D. The joint distribution D can be either decomposed into class-conditionals {Pk}Kk=1 and base rate {πk}Kk=1, where Pk := P(X|Y = k) and πk := P(Y = k), or the marginal M and class-probability function η : X → ∆k, where M := P(X) and ηk(x) := P(Y = k|X = x). A loss is any ℓ : [K] × RK → R+ and the decision function is any g : X → RK . The risk for the decision function g with respect to loss ℓ and implicit distribution D is:
R(g; ℓ) : = E(X,Y )∼D[ℓ(Y, g(X))], (1)
where E denotes the expectation. Two useful equivalent expressions of classification risk (1) used in later sections are
R(g; ℓ) : = EX [η(x)T ℓ(g(X))] = K∑
k=1
πkEPk [ ℓ(k, g(X)) ] , (2)
where ℓ := [ℓ(1, g), ℓ(2, g), . . . , ℓ(K, g)]T . The goal of classification is to learn the decision function g that minimizes the risk. In the usual classification case with ordinarily labeled data at hand, approximating the risk empirically is straightforward: R̂(g; ℓ) := 1n ∑n i=1 ℓ(yi, g(xi)).
Learning from complementary labels Next we consider the problem of learning from complementary labels (Ishida et al., 2017). We observe patterns each equipped with a complementary label {(xi′ , yi′)}n ′
i′=1 sampled independently and identically from a different joint distribution D ̸= D. We denote random variables as (X,Y ) ∼ D. As before, we assume this distribution can be decomposed into either class-conditionals {P k}Kk=1 and base rate {π}Kk=1, or marginal M and classprobability function η : X → ∆K , where P k := P(X|Y = k), πk := P(Y = k), M := P(X), ηk(x) := P(Y = k|X = x), Y is the complementary label, and ∆K is the conditional probability simplex for K classes. Without any assumptions on D, it is impossible to design a suitable learning procedure. The assumption for unbiased complementary learning used in Ishida et al. (2017) was
η(x) = Tη(x), (3)
where T ∈ RK×K is a matrix that takes 0 on diagonals and 1K−1 on non-diagonals. Under this assumption, Ishida et al. (2017) proved that they can recover the classification risk (1) from an alternative formulation using only complementarily labeled data when he loss function satisfies certain conditions. More specifically, usable loss functions are pairwise comparison or one-versus-all multi-class loss functions (Zhang, 2004) each with binary loss function ℓ′(z) : R → R+ that satisfies ℓ′(z) + ℓ′(−z) = 1, such as ramp loss ℓ′R(z) = 12 max ( 0,min(2, 1 − z) ) or sigmoid loss ℓ′S(z) = 1 1+ez .
Having an unbiased risk estimator is also helpful for the validation process. Since we do not have ordinary labels in our validation set in the complementary-label learning setting, we cannot follow the usual validation procedure that uses zero-one error or accuracy. If we have an unbiased estimator of the original classification risk (which can be interpreted as zero-one error), we can use the empirical risk for (cross)-validated complementary data to select the best hyper-parameter or deploy early stopping.
An extension of the above method was considered in Yu et al. (2018) by using a different assumption than the unbiased complementary learning of Ishida et al. (2017): there is some bias amongst the possible complementary labels that can be chosen, thus the non-diagonals of T is not restricted to
1 K−1 . However, one will need to prepare a separate dataset with ordinary labels in order to estimate T beforehand.
Unlike Ishida et al. (2017), Yu et al. (2018) did not directly provide a risk estimator, but they showed that the minimizer of their learning objective agrees with the minimizer of the original classification risk (1). Note that, in their formulation, the loss function is restricted to the softmax cross-entropy loss. Furthermore, the use of a highly non-linear model is supposed for consistency guarantee in their theoretical analysis. Since the learning objective of Yu et al. (2018) does not correspond to the classification risk, one will need clean data with true labels to calculate the error rate during the validation process. On the other hand, our proposed risk estimator can cope with complementarily labeled validation data not only for our own learning objective, but can be used to select hyperparameters for others such as Yu et al. (2018).
Learning from both ordinary and complementary labels In many practical situations, we may also have ordinarily labeled data in addition to complementarily labeled data. Ishida et al. (2017) touched on the idea of crowdsourcing for an application with both types of data. For example, we may choose one of the classes randomly by following the uniform distribution, with probability 1K−1 for each class, and ask crowdworkers whether a pattern belongs to the chosen class or not. Then the pattern is treated as ordinarily labeled if the answer is yes; otherwise, the pattern is regarded as complementarily labeled. If the true label was y for a pattern, we can naturally assume that the crowdworker will answer yes by P(Y = y|X = x) and no by 1 − P(Y = y|X = x). This way, ordinarily labeled data can be regarded as samples from D, and complementarily labeled data from D, justifying the assumption of unbiased complementary learning (3). In Ishida et al. (2017), they considered a convex combination of the classification risks derived from ordinarily labeled data and complementarily labeled data: αR(g; ℓ) + (1 − α)R(g; ℓ), where α ∈ [0, 1] is a hyper-parameter that interpolates between the two risks. The combined (also unbiased) risk estimator can utilize both kinds of data in order to obtain better classifiers, which was demonstrated to perform well in experiments.

heading: 3 PROPOSED METHOD
text: As discussed in the previous section, the method by Ishida et al. (2017) works well in practice, but it has restriction on the loss functions—the popular softmax cross-entropy loss is not allowed. On the other hand, the method by Yu et al. (2018) allows us to use the softmax cross-entropy loss, but it does not directly provide an estimator of the classification risk and thus model selection is problematic in practice. We first describe our general unbiased risk formulation in Section 3.1. Then we discuss how the estimator can be further improved in Section 3.2. Third, we propose a way for our risk estimator to avoid overfitting by a non-negative risk estimator in Section 3.3. Finally, we show practical implementation of our risk estimator with stochastic optimization methods in Section 3.4.

heading: 3.1 GENERAL RISK FORMULATION
text: First, we describe our general unbiased risk formulation. We give the following theorem, which allows unbiased estimation of the classification risk from complementarily labeled samples: Theorem 1. For any ordinary distribution D and complementary distribution D related by (3) with decision function g, and loss ℓ, we have
R(g; ℓ) = R(g; ℓ) (4)
for the complementary loss ℓ(g) := ( − (K − 1)IK + 1
K − 1 11⊤
) · ℓ(g), (5)
where 1 is a K-dimensional column vector with 1 in each element. Proof can be found in Appendix A. The key idea of the proof is to not rely on the condition ∑K k=1 ℓ(k, g) = 1 used in Ishida et al. (2017), which is a condition inspired by the property of binary 0-1 loss ℓ0−1, where ℓ0−1(z) is 1 if z < 0 and 0 otherwise. Note that such a technique was also used when designing unbiased risk estimators for learning from positive and unlabeled data in a binary classification setup (?), but was later shown to be unnecessary (du Plessis et al., 2015).
According to Theorem 1, we can derive an equivalent form,
ℓ(k, g) = −(K − 1) · ℓ(k, g) + K∑ j=1 ℓ(j, g). (6)
Therefore, the classification risk can be written as
R(g; ℓ) = K∑ k=1 πkEPk [ − (K − 1) · ℓ(k, g) + K∑ j=1 ℓ(j, g) ] . (7)
This expression of the classification risk allows us to naively approximate it in an unbiased fashion using complementarily labeled data as
R̂(g; ℓ) = K∑ k=1 π̂k nk nk∑ i=1 [ − (K − 1) · ℓ ( k, g(xi) ) + K∑ j=1 ℓ(j, g ( xi) )] , (8)
where nk is the number of samples complementarily labeled as the kth class. It is worth noting that, in the above derivation, there are no constraints on the loss function and classifier. Thus, we can use any convex/non-convex loss and any linear/non-linear parametric/non-parametric model for complementary learning.

heading: 3.2 NECESSITY OF RISK CORRECTION
text: The original expression of the classification risk (1) includes an expectation over non-negative loss ℓ : [K]×RK → R+, so the risk and its empirical approximator are both lower-bounded by zero. On the other hand, the expression (7) derived above contains an negative element. Although (7) is still non-negative by definition, due to the negative term, its empirical estimator can go negative, leading to over-fitting.
We elaborate on this issue with an illustrative numerical example. In the left graph of Figure 1, we show an example of training a linear model trained on the handwritten digits dataset MNIST1, with complementary labels generated to satisfy (3). We used Adam (Kingma & Ba, 2015) for optimization with learning rate 5e − 5, and weight decay of 1e − 4 with 300 epochs. The empirical classification risk (8) is shown in black. We can see that the empirical classification risk continues decreasing and can go below zero at around 100 epochs. The test accuracy on the right graph hits the peak also at around epoch 100 and then the accuracy gradually deteriorates.
This issue stands out even more significantly when we use a flexible model. The middle graph shows the empirical classification risk for a multilayer perceptron (MLP) with one hidden layer (500 units), where ReLU (Nair & Hinton, 2010) was used as the activation function. The optimization setup was the same as the case of the linear model above. We can see the empirical risk decreasing much more quickly and going negative. Correspondingly, as the right graph shows, the test accuracy drops significantly after the empirical risk goes negative.
In fact, a similar issue has already been conceivable in the original paper by Ishida et al. (2017): According to Theorem 1 in Ishida et al. (2017), the unbiased risk estimator includes subtraction of a positive constant term which increases with respect to the number of classes. This means that the learning objective of Ishida et al. (2017) has a (negative) lower bound. Our objective, however, is unbounded from below and thus can end up in even heavier overfitting.

heading: 3.3 NON-NEGATIVE RISK ESTIMATOR
text: As we saw in Section 3.2, our risk estimator can suffer from overfitting due to the non-negative issue. Here, we propose a correction to the risk estimator to overcome this problem.
Each term in the risk with ordinary labels (right-hand side of (2)), which corresponds to each class, is non-negative. We can reformulate (7) in order to show the counterpart for each non-negative term in right-hand side of (2) for complementarily labeled data as
R(g; ℓ) = K∑ k=1 πk [ − (K − 1) · EPk [ℓ(k, g)] + K∑ j=1 EP j [ℓ(k, g)] ] . (9)
These counterparts (9) were originally non-negative when ordinary labels were used. In the left and middle graphs of Figure 1, we plot the decomposed risk with respect to each ordinary class (9) (shown in different colors). We can see that the decomposed risks for all classes become negative eventually. Based on this observation, our basic idea for correction is to enforce non-negativity for each ordinary class, with the expression based on complementary labels. More specifically, we propose a non-negative (nn) version by
Rnn(g; ℓ) = K∑ k=1 max { 0, πk [ − (K − 1) · EPk [ℓ(k, g)] + K∑ j=1 EP j [ℓ(k, g)] ]} . (10)
1See http://yann.lecun.com/exdb/mnist/.
This non-negative risk can be naively approximated by the sample average as
R̂nn(g; ℓ) = K∑ k=1 max { 0, π [ − K − 1 nk nk∑ i=1 ℓ(k, g(xi)) + K∑ j=1 1 ni′ ni′∑ i′=1 ℓ(j, g(xi′)) ]} . (11)
Enforcing the reformulated risk to become non-negative was previously explored in Kiryo et al. (2017), in the context of binary classification from positive and unlabeled data. The positive class risk is already bounded below by zero in their case (because they have true positive labels), so there was a max operator only on the negative class risk. We basically follow their footsteps, but since our setting is a multi-class scenario and also differs by not having any true labels, we put a max operator on every K class.

heading: 3.4 IMPLEMENTATION
text: Implementation with max operator We show practical implementation under stochastic optimization for our non-negative risk estimator. An unfortunate issue is that the minimization of (11) is not point-wise due to the max-operator, thus cannot be used directly for stochastic optimization methods with mini-batch. However, an upper bound of the risk can be minimized in parallel by using mini-batch as the following,
1
N N∑ i=1 K∑ k=1 max { 0, πk [ − (K − 1)ÊPk [ℓ(k, g);X i k ] + K∑ j=1 ÊP j [ℓ(k, g);X i j ] ]} , (12)
where Ê is the empirical version of the expectation and X i j denotes the samples complementarily labeled as the jth class in the ith mini-batch.
Implementation with gradient ascent If the objective is negative for a certain mini-batch, the previous implementation based on the max operator will avoid the objective to further decrease. However, if the objective is already negative, that mini-batch has already started to overfit. Therefore, it would be preferable to increase itself to make this mini-batch less overfitted.
Our idea is the following. We denote the risk that corresponds to the kth ordinary class for the ith mini-batch as
rik(θ) = πk [ − (K − 1)ÊPk [ℓ(k, g);X i k ] + K∑ j=1 ÊP j [ℓ(k, g);X i j ] ] , (13)
and the total risk as Li(θ) = ∑K
k=1 r i k(θ). When mink{rik(θ)}Kk=1 ≥ −β, we conduct gradient
descent as usual with gradient ∇θLi(θ). On the other hand, if mink{rik(θ)}Kk=1 < −β, we first squash the class-decomposed risks over −β to −β with a min operator, and then sum the results: L̃i(θ) = ∑K k=1 min{−β, rik(θ)}.
Next we set the gradient in the opposite direction with −∇θL̃i(θ). Conceptually, we are going up the gradient ∇θL̃i(θ) for only the class-decomposed risks below −β, to avoid the class-decomposed risks that are already large to further increase. Note that β is a hyper-parameter that controls the tolerance of negativity. β = 0 would mean there is zero tolerance, but in practice we can also have −β ̸= 0 for a threshold that allows some negative (−β < 0) or positive (−β > 0) amount. The procedure is shown in detail in Algorithm 1.

heading: 4 EXPERIMENTS
text: In this section, we experimentally compare our three proposed methods (Algorithm 1, (8) and (12), with two baseline methods from Ishida et al. (2017) and Yu et al. (2018). Table 2 describes the summary statistics of the benchmark datasets used in this section. The implementation is based on Pytorch2 and our code will be available on http://anonymized for reproducing results.
2https://pytorch.org
Algorithm 1 Proposed algorithm with gradient ascent
Input: complementarily labeled training data {Xk}Kk=1, where Xk denotes the samples complementarily labeled as class k; Output: model parameter θ for g(x; θ)
1: Let A be an external SGD-like stochastic optimization algorithm such as Kingma & Ba (2015) 2: Denote {X i
j } as the i-th mini-batch for complementary class j 3: Denote Li(θ) = ∑K
k=1 r i k(θ) 4: Denote rik(θ) = πk [ − (K − 1)ÊPk [ℓ(k, g);X i k ] + ∑K j=1 ÊP j [ℓ(k, g);X i j ] ]
5: Denote L̃i(θ) = ∑K
k=1 min{−β, rik(θ)} 6: while no stopping criterion has been met: 7: Shuffle {Xj}Kj into N mini-batches; 8: for i = 1 to N : 9: if mink[ri1(θ), . . . , rik(θ), . . . , riK(θ)] > −β:
10: Set gradient ∇θLi(θ); 11: Update θ by A with its current step size η; 12: else: 13: Set gradient −∇θL̃i(θ); 14: Update θ by A with a discounted step size γη;

heading: 4.1 SETUP
text: For MNIST and Fashion-MNIST, a linear-in-input model with a bias term and a MLP model (d − 500 − 1) was trained with softmax cross-entropy loss function. Weight decay of 1e − 4 for weight parameters and learning rate of 5e− 5 for Adam (Kingma & Ba, 2015) was used. For CIFAR-10, DenseNet (Huang et al., 2017) and Resnet-18 (He et al., 2016) with default parameter settings were trained. Weight decay of 5e− 4 and initial learning rate of 1e− 2 was used. For optimization, stochastic gradient descent was used with the momentum set to 0.9. Learning rate was halved every 30 epochs.
We trained and compared 5 methods (Free (8), Max operator (12), Gradient ascent (Alg.1), PC (Ishida et al., 2017) and Forward (Yu et al., 2018)) with only complementarily labeled data. Note that the first three are the proposed methods. We complementarily labeled our benchmark datasets so that the assumption of (3) is satisfied. This is straightforward when the dataset has a uniform (ordinarily-labeled) class prior, because it reduces to just choosing a class randomly other than the true class. For Gradient ascent, we used β = 0 and γ = 0 for simplicity. We trained 300 epochs, where mini-batch was set to 100.

heading: 4.2 RESULTS
text: Instead of showing the test accuracy for a single chosen model based on validation, we show the accuracy for all 300 epochs on test data to demonstrate how the issues discussed in Section 3.2 appear and how different implementations Section 3.4 is effective. In Figure 2, we show the mean test accuracy and standard deviation for 4 trials for the three benchmark datasets, on test data evaluated with ordinary labels.
First we compare our three proposed methods with each other. For linear models in MNIST and Fashion-MNIST, all proposed methods work similarly. However in the case of using a more flexible model (MLP model for MNIST/Fashion-MNIST, Densenet/Resnet for CIFAR-10), we can see that Free is the worst, Max operator is better and Gradient ascent is the best out of the proposed three methods at the end of all epochs (Free < Max operator < Gradient ascent). These results are consistent with the discussions of overfitting in Section 3.2 and the motivations for different implementations in Section 3.4.
Next, we compare with baseline methods. For linear models, all methods have similar performance. However for deep models, the superiority stands out for Gradient ascent for all datasets.

heading: 5 CONCLUSION
text: We first proposed a general risk estimator for learning from complementary labels that does not require restrictions on the form of the loss function or the model. However, since the proposed method suffers from overfitting, we proposed a modified version to alleviate this issue in two ways and have better performance. At last, we conducted experiments to show our proposed method outperforms or is comparable to current state-of-the-art methods for various benchmark datasets and for both linear and deep models.

heading: A PROOF OF THEOREM 1
text: Proof. First of all,
P(X,Y = y) = 1 K − 1 ∑ y ̸=y P(X,Y = y) (14)
= 1
K − 1 ( K∑ y=1 P(X,Y = y)− P(X,Y = y) )
(15)
= 1 K − 1 ( P(X)− P(X,Y = ȳ) ) . (16)
The first equality holds since the marginal distribution is equivalent for D and D and we assume (3). Consequently,
P(Y = y|X = x) = P(X = x, Y = y) P(X = x)
(17)
= 1 K − 1 · ( 1− P(X,Y = y) P(X = x) ) (18)
= 1 K − 1 · ( 1− P(Y = y|X = x) ) (19)
= − 1 K − 1 P(Y = y|X = x) + 1 K − 1 . (20)
More simply, we have
η(x) = −(K − 1)η(x) + 1. (21)
Finally, we transform the classification risk,
R(g; ℓ) = E(X,Y )∼D[ℓ(Y, g(X))] (22) = EX∼M [η⊤ℓ(g(X))] (23) = EX∼M [( − (K − 1)η⊤ + 1⊤ ) ℓ ( g(X) )] (24)
= EX∼M [ − (K − 1)η⊤ℓ ( g(X) ) + 1⊤ℓ ( g(X) )] (25)
= E(X,Y )∼D [ − (K − 1) · ℓ ( Y , g(X) )] + 1⊤EX∼M [ ℓ ( g(X) )] (26)
= K∑ k=1 EX∼Pk [ πk · ( − (K − 1) · ℓ ( k, g(X) ) + 1⊤ℓ ( g(X) ))] (27)
= R(g; ℓ) (28)
for the complementary loss,
ℓ(k, g) := −(K − 1)ℓ(k, g) + 1⊤ℓ(g), (29)
which concludes the proof.

heading: B DETAILS OF DATASETS USED IN SECTION 4
text: In Table 2, we explain the details of the datasets used in Section 4. See http://yann.lecun.com/exdb/mnist/ for MNIST, https://github.com/zalandoresearch/fashion-mnist for Fashion-MNIST, and https://www.cs.toronto.edu/~kriz/cifar.html for CIFAR-10.

Review summaries:
This paper proposes an improved approach to the "complementary-label" form of weak supervision, in which a label that is *not* the true label is marked. Specifically, this paper proposes an unbiased estimator that accepts arbitrary loss functions and models. Noting that this proposed estimator can suffer from overfitting due to unbounded negative loss, a lower-bounded estimator is proposed. Experiments are then performed on several image classification datasets.