On the Minimal Supervision for Training Any Binary Classifier from Only Unlabeled Data

Introduction

With some properly chosen loss function (e.g., Bartlett et al., 2006; Tewari & Bartlett, 2007; Reid & Williamson, 2010) and regularization (e.g., Tikhonov, 1943; Srivastava et al., 2014), empirical risk minimization (ERM) is the common practice of supervised classification (Vapnik, 1998). Actually, ERM is used in not only supervised learning but also weakly-supervised learning. For example, in semi-supervised learning (Chapelle et al., 2006), we have very limited labeled (L) data and a lot of unlabeled (U) data, where L data share the same form with supervised learning. Thus, it is easy to estimate the risk from only L data in order to carry out ERM, and U data are needed exclusively in regularization (including but not limited to Grandvalet & Bengio, 2004; Belkin et al., 2006; Mann & McCallum, 2007; Niu et al., 2013; Miyato et al., 2016; Laine & Aila, 2017; Tarvainen & Valpola, 2017; Luo et al., 2018; Kamnitsas et al., 2018).

Nevertheless, L data may differ from supervised learning in not only the amount but also the form. For instance, in positive-unlabeled learning (Elkan & Noto, 2008; Ward et al., 2009), all L data are from the positive class, and due to the lack of L data from the negative class it becomes impossible to estimate the risk from only L data. To this end, a two-step approach to ERM has been considered (du Plessis et al., 2014; 2015; Niu et al., 2016; Kiryo et al., 2017). Firstly, the risk is rewritten into an equivalent expression, such that it just involves the same distributions from which L and U data are sampled—this step leads to certain risk estimators. Secondly, the risk is estimated from both L and U data, and the resulted empirical training risk is minimized (e.g. by Robbins & Monro, 1951; Kingma & Ba, 2015). In this two-step approach, U data are needed absolutely in ERM itself. This indicates that risk rewrite (i.e., the technique of making the risk estimable from observable data via an equivalent expression) enables ERM in positive-unlabeled learning and is the key of success.

One step further from positive-unlabeled learning is learning from only U data without any L data. This is significantly harder than previous learning problems (cf. Figure 1). However, we would still like to train arbitrary binary classifier, in particular, deep networks (Goodfellow et al., 2016). Note that for this purpose clustering is suboptimal for two major reasons. First, successful translation of clusters into meaningful classes completely relies on the critical assumption that one cluster exactly corresponds to one class, and hence even perfect clustering might still result in poor classification. Second, clustering must introduce additional geometric or information-theoretic assumptions upon which the learning objectives of clustering are built (e.g., Xu et al., 2004; Gomes et al., 2010). As a consequence, we prefer ERM to clustering and then no more assumption is required.

The difficulty is how to estimate the risk from only U data, and our solution is again ERM-enabling risk rewrite in the aforementioned two-step approach. The first step should lead to an unbiased risk estimator that will be used in the second step. Subsequently, we can evaluate the empirical training and/or validation risk by plugging only U training/validation data into the risk estimator. Thus, this two-step ERM needs no L validation data for hyperparameter tuning, which is a huge advantage in training deep models nowadays. Note that given only U data, by no means could we learn the class priors (Menon et al., 2015), so that we assume all necessary class priors are also given. This is the unique type of supervision we will leverage throughout this paper, and hence this learning problem still belongs to weakly-supervised learning rather than unsupervised learning.

In this paper, we raise a fundamental question in weakly-supervised learning—how many sets of U data with different class priors are necessary for rewriting the risk? Our answer has two aspects:

Risk rewrite is impossible given a single set of U data (see Theorem 2 in Sec. 3);

Risk rewrite becomes possible given two sets of U data (see Theorem 4 in Sec. 4).

This suggests that three class priorsTwo class-prior probabilities are of the training distributions and one is of the test distribution.are all you need to train deep models from only U data, while any twoOne of the training distribution and one of the test distribution, or two of the training distributions. should not be enough. The impossibility is a proof by contradiction, and the possibility is a proof by construction, following which we explicitly design an unbiased risk estimator. Therefore, with the help of this risk estimator, we propose an ERM-based learning method from two sets of U data. Thanks to the unbiasedness of our risk estimator, we derive an estimation error bound which certainly guarantees the consistency of learning (Mohri et al., 2012; Shalev-Shwartz & Ben-David, 2014).Learning is consistent (more specifically the learned classifier is asymptotically consistent), if and only if as the amount of training data approaches infinity, the risk of the learned classifier converges to the risk of the optimal classifier, where the optimality is defined over a given hypothesis class. Experiments demonstrate that the proposed method could train multilayer perceptron, AllConvNet (Springenberg et al., 2015) and ResNet (He et al., 2016) from two sets of U data; it could outperform state-of-the-art methods for learning from two sets of U data. See Figure 1 for how the proposed method works on a Gaussian mixture of two components.

Problem setting and related work

Consider the binary classification problem. Let $X$ and $Y$ be the input and output random variables such that

$p(x,y)$ is the underlying joint density,

Nonetheless, the problem of interest belongs to weakly-supervised learning—U training (and validation) data are supposed to be drawn according to (1). More specifically, we have

Learning from only U data is previously regarded as discriminative clustering (Xu et al., 2004; Valizadegan & Jin, 2006; Li et al., 2009; Gomes et al., 2010; Sugiyama et al., 2014; Hu et al., 2017). Their goals are to maximize the margin or the mutual information between $X$ and $Y$. Recall that clustering is suboptimal, since it requires the cluster assumption (Chapelle et al., 2002) and it is rarely satisfied in practice that one cluster exactly corresponds to one class.

Our findings are compatible with learning from label proportions (Quadrianto et al., 2009; Yu et al., 2013). Quadrianto et al. (2009) proves that the minimal number of U sets is equal to the number of classes. However, their finding only holds for the linear model, the logistic loss, and their proposed method based on mean operators. On the other hand, Yu et al. (2013) is not ERM-based; it is based on discriminative clustering together with expectation regularization (Mann & McCallum, 2007).

Learning from one set of U data

Choose a model $\mathcal{G}$, so that $\min_{g\in\mathcal{G}}R(g)$ is achievable by ERM.

2 Impossibility of risk rewrite

Learning from two sets of U data

Theorem (4) immediately leads to an unbiased risk estimator, namely,

Consider some special cases of (10) by specifying $\theta$ and $\theta^{\prime}$. It is obvious that (10) reduces to (5) for supervised learning, if $\theta=1$ and $\theta^{\prime}=0$. Next, (10) reduces to

2 Consistency and convergence rate

For any $\delta>0$, let $C_{\delta}=\sqrt{(\ln 2/\delta)/2}$, then we have with probability at least $1-\delta$,

Experiments

In this section, we experimentally analyze the proposed method in training deep networks and subsequently experimentally compare it with state-of-the-art methods for learning from two sets of U data. The implementation in our experiments is based on Keras (see https://keras.io); it is available at https://github.com/lunanbit/UUlearning.

In order to analyze the proposed method, we compare it with three supervised baseline methods:

small PN means supervised learning from 10% L data;

PN oracle means supervised learning from 100% L data;

small PN prior-shift means supervised learning from 10% L data under class-prior change.

Notice that the first two baselines have L data identically distributed as the test data, which is very advantageous and thus the experiments in this subsection are merely for a proof of concept.

Table 1 also describes the models and optimizers. In this table, FC refers to fully connected neural networks, AllConvNet refers to all convolutional net (Springenberg et al., 2015) and ResNet refers to residual networks (He et al., 2016); then, SGD is short for stochastic gradient descent (Robbins & Monro, 1951) and Adam is short for adaptive moment estimation (Kingma & Ba, 2015).

The experimental results are reported in Figure 2, where means and standard deviations of classification errors based on 10 random samplings are shown, and the table of final errors can be found in Appendix C.2. When $\theta=0.9$ and $\theta^{\prime}=0.1$ (cf. the left column), UU is comparable to PN oracle in most cases. When $\theta=0.8$ and $\theta^{\prime}=0.2$ (cf. the right column), UU performs slightly worse but it is still better than small PN baselines. This is because the task becomes harder when $\theta$ and $\theta^{\prime}$ become closer, which will be intensively investigated next.

Note that there would be strong covariate shift not only by changing $\theta$ and $\theta^{\prime}$ but also by changing $n$ and $n^{\prime}$. The investigation of this issue is deferred to Appendix C.2 due to limited space.

Hitherto, we have assumed that the values of $\theta$ and $\theta^{\prime}$ are accessible, which is rarely satisfied in practice. Fortunately, UU is a robust learning method against inaccurate training class priors. To show this, let $\epsilon$ and $\epsilon^{\prime}$ be real numbers around 1, $\vartheta=\epsilon\theta$ and $\vartheta^{\prime}=\epsilon^{\prime}\theta^{\prime}$ be perturbed $\theta$ and $\theta^{\prime}$, and we test UU on MNIST and CIFAR-10 by drawing data using $\theta$ and $\theta^{\prime}$ but training models using $\vartheta$ and $\vartheta^{\prime}$ instead. The experimental results in Table 2 imply that UU is fairly robust to inaccurate $\vartheta$ and $\vartheta^{\prime}$ and can be safely applied in the wild.

2 Comparison with state-of-the-art methods

Finally, we compare UU with two state-of-the-art methods for dealing with two sets of U data:We downloaded the codes by the original authors; see https://github.com/felixyu/pSVM and https://akmenon.github.io/papers/corrupted-labels/index.html.

proportion-SVM (pSVM, Yu et al., 2013) that is the best in learning from label proportions;

balanced error minimization (BER, Menon et al., 2015) that is the most related work to UU.

Conclusions

We focused on training arbitrary binary classifier, ranging from linear to deep models, from only U data by ERM. We proved that risk rewrite as the core of ERM is impossible given a single set of U data, but it becomes possible given two sets of U data with different class priors, after we assumed that all necessary class priors are also given. This possibility led to an unbiased risk estimator, and with the help of this risk estimator we proposed UU learning, the first ERM-based learning method from two sets of U data. Experiments demonstrated that UU learning could successfully train fully connected, all convolutional and residual networks, and it compared favorably with state-of-the-art methods for learning from two sets of U data.

NL was supported by the MEXT scholarship No. 171536. MS was supported by JST CREST JPMJCR1403. We thank all anonymous reviewers for their helpful and constructive comments on the clarity of two earlier versions of this manuscript.

References

Appendix A Proofs

Nevertheless, $0\leq\theta\leq 1$ whereas

A.2 Proof of Theorem 4

Let $J(g)$ be an alias of $R(g)$ in Definition 3 serving as the learning objective, i.e.,

since $J(g)$ is an alias of $R(g)$. As a result, in order to minimize $R(g)$ in (3), it suffices to minimize $J(g)$ in (15), if we can make

Solving these equations gives us Eq. (9), which concludes the proof. ∎

A.3 Proof of Theorem 5

First, we show the uniform deviation bound, which is useful to derive the estimation error bound.

For any $\delta>0$, let $C_{\delta}=\sqrt{(\ln 2/\delta)/2}$, then we have with probability at least $1-\delta$,

or equivalently, with probability at least $1-\delta/2$,

By symmetrization (Vapnik, 1998), it is a routine work to show that

and according to Talagrand’s contraction lemma (Shalev-Shwartz & Ben-David, 2014),

Based on Lemma 6, the estimation error bound (13) is proven through

Appendix B Supplementary information on Figure 1

In the introduction, we illustrated the learning problem and the proposed method using a Gaussian mixture of two components. The details of this illustrative example are presented here.

Note that $p(x)$ changes between training and test distributions (which can be seen from Figure 1 by comparing (c) and (d) in the left panel and the right panel). This is the key difference between UU and CCN (Natarajan et al., 2013).

Appendix C Supplementary information on the experiments

This is a grayscale image dataset of handwritten digits from 0 to 9 where the size of the images is 28*28. It contains 60,000 training images and 10,000 test images. Since it has 10 classes originally, we used the even digits as the P class and the odd digits as the N class, respectively.

where decay was chosen from {0, 1e-6, 1e-5, 5e-5, 1e-4, 5e-4}. This is a learning rate schedule built in Keras.

This is also a grayscale image dataset similarly to MNIST, but here each data is associated with a label from 10 fashion item classes. It was converted into a binary classification dataset as follows:

the P class is formed by ‘T-shirt’, ‘Pullover’, ‘Coat’, ‘Shirt’, and ‘Bag’;

the N class is formed by ‘Trouser’, ‘Dress’, ‘Sandal’, ‘Sneaker’, and ‘Ankle boot’.

The model and optimizer were same as MNIST, except that the initial learning rate was 1e-4.

This is a 32*32 color image dataset of street view house numbers from 0 to 9. It consists of 73,257 training data, 26,032 test data, and 531,131 extra training data. We sampled 100,000 data for training from the concatenation of training data and extra training data—the extra training data were used to ensure enough training data so as to perform class-prior changes. For SVHN dataset, ‘0’, ‘6’, ‘8’, ‘9’ made up the P class, and ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘7’ made up the N class.

The model was AllConvNet (Springenberg et al., 2015) as follows.

This dataset consists of 60,000 32*32 color images in 10 classes, and there are 5,000 training images and 1,000 test images per class. For CIFAR-10 dataset,

the P class is composed of ‘bird’, ‘cat’, ‘deer’, ‘dog’, ‘frog’ and ‘horse’;

the N class is composed of ‘airplane’, ‘automobile’, ‘ship’ and ‘truck’.

The model was ResNet-32 (He et al., 2016) as follows.

where [ $\cdot$, $\cdot$ ] means a building block (He et al., 2016). The optimization setup was the same as for SVHN, except that the regularization parameter was set to be 5e-3 and the initial learning rate was set to be 1e-5.

In the experiments on the closeness of $\theta$ and $\theta^{\prime}$ and on the robustness against inaccurate training class priors, we sampled 40,000 training data from all the training data of MNIST in order to make it feasible to perform class-prior changes.

C.2 Results

We have further investigated the issue of covariate shift by varying $n$ and $n^{\prime}$. Likewise, we test UU and CCN on MNIST by fixing $n^{\prime}$ to 20,000 and gradually moving $n$ from 20,000 to 4,000, where $\theta^{\prime}$ is fixed to 0.4 and $\theta$ is chosen from 0.9 or 0.8. The experimental results in Figure 5 indicate that when $n$ moves farther from $n^{\prime}$, UU and CCN become worse, while UU is affected slightly and CCN is affected severely. Figure 5 is consistent with Figure 3, showing that CCN methods do not fit our problem setting.