Empirical risk minimization (ERM), with proper loss function and regularization, is the common practice of supervised classification. In this paper, we study training arbitrary (from linear to deep) binary classifier from only unlabeled (U) data by ERM. We prove that it is impossible to estimate the risk of an arbitrary binary classifier in an unbiased manner given a single set of U data, but it becomes possible given two sets of U data with different class priors. These two facts answer a fundamental question---what the minimal supervision is for training any binary classifier from only U data. Following these findings, we propose an ERM-based learning method from two sets of U data, and then prove it is consistent. Experiments demonstrate the proposed method could train deep models and outperform state-of-the-art methods for learning from two sets of U data. With some properly chosen loss function (e.g., BID2 BID50 BID39 and regularization (e.g., BID51 BID46 , empirical risk minimization (ERM) is the common practice of supervised classification BID54 . 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 BID16 BID3 BID25 BID29 BID20 BID49 BID24 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 BID12 BID55 ), 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 BID9 BID34 BID18 . 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 BID41 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. FIG1 ). However, we would still like to train arbitrary binary classifier, in particular, deep networks BID15 . 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 In the left panel, (a) and (b) show positive (P) and negative (N) components of the Gaussian mixture; (c) and (d) show two distributions (with class priors 0.9 and 0.4) where U training data are drawn (marked as black points). The right panel shows the test distribution (with class prior 0.3) and data (marked as blue for P and red for N), as well as four learned classifiers. In the legend, "CCN" refers to BID31 , "UU-biased " means supervised learning taking larger-/smaller-class-prior U data as P/N data, "UU" is the proposed method, and "Oracle" means supervised learning from the same amount of L data. See Appendix B for more information. We can see that UU is almost identical to Oracle and much better than the other two methods. 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., BID57 BID14 . 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 BID27 , 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 priors 1 are all you need to train deep models from only U data, while any two 2 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 BID30 BID44 .3 Experiments demonstrate that the proposed method could train multilayer perceptron, AllConvNet BID45 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 FIG1 for how the proposed method works on a Gaussian mixture of two components .As mentioned earlier, learning from two sets of U data is already studied in du BID8 and BID27 . Both of them adopt (4) as the performance measure. In the former paper, g is learned by estimating sign(p tr (x) − p tr (x)). In the latter paper, g is learned by taking noisy L data from p tr (x) and p tr (x) as clean L data from p p (x) and p n (x), and then its threshold is moved to the correct value by post-processing. In summary, instead of ERM, they evidence the possibility of empirical balanced risk minimization , and no impossibility is proven.Our findings are compatible with learning from label proportions BID36 BID58 . BID36 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, BID58 is not ERM-based; it is based on discriminative clustering together with expectation regularization BID25 .At first glance, our data generation process, using the names from BID27 , looks quite similar to class-conditional noise (CCN, BID0 in learning with noisy labels (cf. BID31 . 4 In fact, BID27 makes use of mutually contaminated distributions (MCD, BID43 that is more general than CCN . Denote byỹ andp(·) the corrupted label and distributions. Then, CCN and MCD are defined by DISPLAYFORM0 where both of T CCN and T MCD are 2-by-2 matrices but T CCN is column normalized and T MCD is row normalized. It has been proven in BID27 that CCN is a strict special case of MCD. To DISPLAYFORM1 Due to this covariate shift, CCN methods do not fit MCD problem setting, though MCD methods fit CCN problem setting. To the best of our knowledge, the proposed method is the first MCD method based on ERM.3 LEARNING FROM ONE SET OF U DATA From now on, we prove that knowing π p and θ is insufficient for rewriting R(g). 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.
Three class priors are all you need to train deep models from only U data, while any two should not be enough. Proposes an unbiased estimator that allows for training models with weak supervision on two unlabeled datasets with known class priors and discusses theoretical properties of the estimators. A methodology for training any binary classifier from only unlabeled data, and an empirical risk minimization method for two sets of unlabeled data where class priors are given.