Title: LEARNING FROM POSITIVE AND UNLABELED DATA WITH A SELECTION BIAS

Abstract: We consider the problem of learning a binary classifier only from positive data and unlabeled data (PU learning). Recent methods of PU learning commonly assume that the labeled positive data are identically distributed as the unlabeled positive data. However, this assumption is unrealistic in many instances of PU learning because it fails to capture the existence of a selection bias in the labeling process. When the data has selection bias, it is difficult to learn the Bayes optimal classifier by conventional methods of PU learning. In this paper, we propose a method to partially identify the classifier. The proposed algorithm learns a scoring function that preserves the order induced by the class posterior under mild assumptions, which can be used as a classifier by setting an appropriate threshold. Through experiments, we show that the method outperforms previous methods for PU learning on various real-world datasets.

1. INTRODUCTION:

We consider a situation that there are only positive and unlabeled data, and train a binary classifier only from them (PU learning). This problem arises in various practical situations, such as information retrieval and outlier detection (Elkan & Noto, 2008; Ward et al., 2009; Scott & Blanchard, 2009; Blanchard et al., 2010; Li et al., 2009; Nguyen et al., 2011) . One of the milestones of PU learning is Elkan & Noto (2008) , who proposed a practically useful algorithm with theoretical analysis, and there is subsequent research called unbiased PU learning (du Plessis & Sugiyama, 2014; du Plessis et al., 2015) where an unbiased estimator of the classification risk is minimized.

We focus on the case-control scenario (a.k.a. the problem setting based on two samples of data; Ward et al., 2009; Niu et al., 2016) . In this scenario, positive data are obtained separately from unlabeled data, and unlabeled data are sampled from the whole population. As Elkan & Noto (2008) explained, we cannot identify a classifier without an assumption on how positive data are labeled. Therefore "selected completely at random" (SCAR) is traditionally assumed, i.e., the positive labeled data are identically distributed as the positive unlabeled data (Elkan & Noto, 2008; du Plessis et al., 2015) .

The assumption of SCAR is, however, unrealistic in many instances of PU learning, e.g., a patient's electronic health record (Bekker & Davis, 2018a ) and a recommendation system (Marlin & Zemel, 2009; Schnabel et al., 2016) . In these cases, there is a selection bias (Heckman, 1979; Manski, 2008; Angrist & Pischke, 2008) ; the distribution of the positive data may differ between the labeled data and the unlabeled data.

Several recent related works have proposed alternative assumptions (Bekker & Davis, 2018a; b) . However, in order to weaken SCAR, they impose other additional assumptions. In this work, we consider a more natural assumption such that SCAR becomes its special case. We assume that p(o = +1|x, y = +1) and p(y = +1|x) induce the same ordering on the input space X , where y ∈ {-1, +1} is the data label and o = +1 (resp. o = 0) denotes the event that the data is observed (resp. not observed). We call this property the invariance of order. In the real-world application, there are many situations with a selection bias which follows the invariance of order. Among them, we list the following two examples.

Example 1: (Anomaly Detection) The goal of anomaly detection is to find anomaly data in an unlabeled dataset based on another dataset that consists only of anomaly data. When the anomaly data is collected, the more likely a datum is an anomaly, the more likely it is noticed and gets labeled.

Example 2: (Face Recognition) The goal of this task is to identify a user from a set of face images based on some pictures of the user. In this case, the positive data are the face images identified with the user, and the unlabeled data consist of all the unidentified face images. The user may more likely provide pictures in which the face can be seen clearly, while in the unlabeled data there may be many unclear images.

Our problem setting is similar to the problem called learning from instance-dependent noisy labels (Du & Cai, 2015; Bootkrajang, 2016) . In this problem setting, positive and negative data are available, but the labels are subject to the noise that flips the label with instance-dependent probability. Besides, there are existing works putting assumption similar to the invariance order (Du & Cai, 2015; Bootkrajang, 2016) . We explain the difference between their works and ours around Assumption 1 in Section 2.1. We name our problem setting PU learning with a Selection Bias (PUSB).

In this paper, we propose a novel framework to deal with this problem setting. The experimental results show that our proposed method is appropriate for real-world applications compared to existing approaches for PU learning.

2. PROBLEM SETTING OF PU LEARNING WITH A SELECTION BIAS:

We consider a binary classification problem to classify x ∈ X ⊂ R d into one of the two classes {-1, +1}. We assume that there exists a joint distribution p(x, y, o), where y ∈ {-1, +1} is the class label of x, and o ∈ {0, +1} is the observation status of y (observed if o = +1 and unobserved if o = 0). In other words, x is labeled if o = +1, and it is unlabeled otherwise.

In PU learning, there are two distinguished sampling schemes called one sample and two samples of data (Niu et al., 2016) . They are also called the censoring scenario and case-control scenario, respectively (Elkan & Noto, 2008) . In the censoring scenario, a set of unlabeled data is sampled from the marginal density p(x). Then, if a data point x is positive, it gets labeled with probability p(o = +1|x, y = +1); if x is negative, it is never labeled. In the case-control scenario, a set of positive data is drawn from the positive conditional density p(x|y = +1) and a set of unlabeled data is drawn from p(x). As Niu et al. (2016) stated, the case-control scenario is slightly more general than the censoring scenario setting. It is because the censoring scenario assumes the access to samples generated by p(x), p(x|o = +1), and p(x|o = 0) whereas the case-control scenario only assumes the access to samples generated by p(x) and p(x|o = +1). Therefore we focus on the case-control scenario.

Suppose that we have a positive dataset {x i } n i=1 and an unlabeled dataset

{x i } n i=1 {x i } n i=1 i.i.d. ∼ p(x|y = +1, o = +1), {x i } n i=1 i.i.d.

∼ p(x).:

We assume that negative data are never labeled.

Note that we do not assume SCAR. Therefore, p(x|y = +1) may differ from p(x|y = +1, o = +1).

In the case they differ, we say that there is a selection bias.

The quantity π = p(y = +1) is called the class-prior. In our problem setting, we assume that π is known. For example, in anomaly detection, the percentage of anomaly in the whole batch of products can be reported based on past experiences. Although there are various methods for estimating the class-prior in the traditional framework of the case-control scenario (du Plessis et al., 2016; Ramaswamy et al., 2016; Jain et al., 2016; Kato et al., 2018) , we cannot estimate the class-prior in our problem setting under a theoretical guarantee. In Section 5, we show how misspecified class priors affect the performance of a classifier. As we explain later, even if we do not know the class-prior, we only have to change the last step of our algorithm. In summary, our goal is to obtain a classifier h :

X → {-1, 1} only from {x i } n i=1 , {x i } n i=1

, and π under a weaker assumption than SCAR.

2.1. IDENTIFICATION STRATEGY:

As stated by Elkan & Noto (2008) , even if the class prior is given, we cannot estimate p(y = +1|x) only from positive data and unlabeled data without any assumption in PU learning. In the case-control scenario, a standard assumption is SCAR, i.e. p(x|y = +1, o = +1) = p(x|y = +1, o = 0), so that p(y = +1|x) can be estimated from the data in principle. However, in many instances of PU learning, the SCAR assumption is unreasonable as discussed before. Therefore, we relax SCAR and accommodate a selection bias. We can see how SCAR makes the class posterior identifiable in the following equation:

p(y = +1|x) = p(x, y = +1) p(x) = p(x|y = +1)π p(x) = SCAR p(x|y = +1, o = +1)π p(x) .

Here, p(x|y = +1, o = +1) can be estimated from the sample. This estimate can be used to obtain an estimate of p(x|y = +1) and hence that of p(y = +1|x) if we assume SCAR. However, without assuming SCAR, p(x|y = +1) may differ from p(x|y = +1, o = +1), and p(y = +1|x) is not identifiable.

Therefore, instead of estimating p(y = +1|x), we consider extracting some useful information of p(y = +1|x) to learn a classifier. This kind of approach is known as "partial identification" (Manski, 2008) in statistics and economics. First, we introduce an assumption that is weaker than SCAR.

Assumption 1 (Invariance of Order). For any x i , x j ∈ X , we have

p(y = +1|x i ) ≤ p(y = +1|x j ) ⇔ p(o = +1|x i ) ≤ p(o = +1|x j ).

Although Assumption 1 does not allow one to construct an unbiased estimator of the risk functional, we try to partially identify p(y = +1|x) under this assumption. Our problem setting can be regarded as a generalization of the traditional case-control scenario because SCAR is a special case of the invariance of order.

2.2. RELATED WORKS:

A similar assumption can be found in the literature of learning from instance-dependent noisy labels (Du & Cai, 2015; Bootkrajang, 2016) , which considers a probabilistic label flipping that is proportional to p(y = +1|x). However, in order to apply methods of learning from noisy labels to PU learning, we need to assume the censoring scenario and these methods cannot be applied to our problem setting based on the case-control scenario. The censoring scenario is a special case of learning from noisy labels where only negative data is contaminated, i.e., some positive labels flip to negative labels. Thus, in the censoring scenario, unlabeled data can be regarded as negative-labeled data contaminated by positive data. On the other hand, in the case-control scenario, unlabeled data is generated from the marginal distribution p(x), i.e., we cannot observe samples generated from p(x|o = 0). Therefore, our problem setting, namely the case-control scenario with invariance of order, is different from the existing works of learning from instance-dependent noisy labels. In addition, our method is also applicable to the censoring scenario when the invariance of order holds because the unlabeled data of the case-control scenario can be made from positive and unlabeled data of the censoring scenario.

In Example 1, p(y = +1|x) is the probability that a given input x is anomaly, while p(o = +1|x) is the probability that a given input x gets labeled in the dataset. In Example 2, a positively labeled data is an image x that is known to belong to a user. Here, p(o = +1|x) is the probability that the user provides the picture x as a training datum.

3. STRATEGY FOR PARTIAL IDENTIFICATION AND CLASSIFICATION:

As discussed in Section 2.1, we cannot estimate p(y = +1|x) when there is a selection bias even if the class prior is given. Our idea of partial identification is based on the following theorem with the density ratio

r(x) = p(x|y = +1, o = +1) p(x)

.

(1)

Algorithm 1 Conceptual Algorithm in Population:

Input: p(x|y = +1), p(x) and the class-pror π.

Using p(x|y = +1) and p(x), calculate r(x) by minimization of either ( 4) or ( 7). Using r(x), calculate θ π in (2).

Using the density ratio r(x) and the threshold θ π , obtain a classifier h(x) = sign(r(x) -θ π ).

Theorem 1 (Order Preserving Property of the score Function). Suppose that Assumption 1 holds. Then, for any x i , x j ∈ X ,

p(y = +1|x i ) ≤ p(y = +1|x j ) ⇔ r(x i ) ≤ r(x j ).

A proof is provided in Appendix A.

Even though we cannot estimate p(y = +1|•), Theorem 1 implies that we can still extract the total order in X induced by p(y = +1|•) if we can estimate r(•). Therefore, we propose to estimate r and use it as a score function that captures the total order induced by p(y = +1|•). After obtaining an estimator of r (denoted by r), we set a threshold θ ∈ R and use h(x) = sign(r(x) -θ) as a classifier. There are various ways of determining the threshold. For instance, we put labels from data with the highest density ratio under a constraint on the number of data to which we can put labels (Hido et al., 2011) . Here, we introduce one useful principle for choosing θ. We consider using a threshold θ π defined by the following equation,

EQUATION

The intuition behind the definition of θ π is that the proportion of the positive data in the test data points should not deviate so much from the class-prior. This intuition becomes clearer in Section 4.3.

In Section 4, we discuss detailed methods for estimating r and setting θ based on data. Our approach is summarized in the form of a pseudo-code in Algorithm 1. In the rest of this section, we theoretically justify θ π defined in (2).

Property of θ π : Let us consider the case where a classifier is given as h(x) = sign(r(x) -θ).

Then four population quantities, true positives (TP), true negatives (TN), false positives (FP), and false negatives (FN) (Lipton et al., 2014) , that depend on r(•) and θ is written as follows:

T P = {x:r(x)≥θ} p(y = +1|x)p(x)dx, F P = {x:r(x)≥θ} p(y = -1|x)p(x)dx, T N = {x:r(x)<θ} p(y = -1|x)p(x)dx, F N = {x:r(x)<θ} p(y = +1|x)p(x)dx.

Then, the precision and the recall of a classifier are expressed as precision = T P T P +F P and recall = T P T P +F N , respectively. For θ π , we have the following result. Theorem 2. If we use θ = θ π , then precision = recall holds.

A proof is shown in Appendix B. The threshold θ π is known as precision-recall breakeven point (BEP) (Sammut & Webb, 2010) , which makes the precision and the recall the same. BEP is originally used to evaluate a generic classification model with a score function and a threshold. Besides, we can interpret BEP as a point which balances a prediction result; as explained by Powers (2015), a classifier using BEP as a threshold puts the same cost to the false positives and false negatives. Knowing BEP is also useful for deciding on a threshold which put unbalanced weight on the precision and the recall because we can tell if we are weighing precision more or recall more.

4. ALGORITHM:

Here, we propose two directions for estimating r(x) = p(x|y=+1,o=+1) p(x) under the assumption of invariance of order, namely minimizing a pseudo classification risk and direct density ratio estimation. We discuss how to set θ based on the data. A pseudo-code of our algorithm is shown in Algorithm 2.

Algorithm 2 PUSB:

Input: A positive dataset {x i } n i=1 , an unlabeled dataset {x i } n i=1 , a test dataset {x te i } n te i=1 and the class-pror π. Using {x i } n i=1 and {x i } n i=1 , estimate r(x) by any of ( 5), ( 6) or ( 8) and obtain r(x). Using r(x), estimate θ π by ( 9) and obtain θπ . Using an estimator r(x) and θ, obtain a classifier h(x) = sign(r(x) -θπ ).

4.1. ESTIMATION OF r BY MINIMIZING PSEUDO CLASSIFICATION RISK:

First, we introduce the minimization of the pseudo classification risk. The idea is to minimize the classification risk used in traditional PU learning (du Plessis et al., 2014; 2015) as if there is no selection bias. Under a selection bias, we cannot construct unbiased risk function, but the minimizer can be substituted for the density ratio in (1).

Conventional PU risk formulation: Let : R × {±1} → R + be a loss function, where R + is the set of non-negative real values, and F be the set of measurable functions from X to [ , 1 -], where ∈ (0, 1/2) is a small positive value. This constant is introduced to make the following optimization problem well-defined.

du Plessis et al. (2015) showed that the classification risk of f ∈ F in the traditional PU problem setting with SCAR can be expressed as

EQUATION

where E p and E u are the expectations over p(x|y = +1) and p(x), respectively. When there is no selection bias, we can replace the expectations with the corresponding sample averages to obtain an unbiased estimator of the classification risk.

The pseudo classification risk: In our problem setting, we only have samples from p(x|y = +1, o = +1) and not from p(x|y = +1). Therefore, we cannot use our sample to obtain an empirical version of R PU . However, we still consider the pseudo classification risk of f ∈ F:

R bias PU (f, ) = πE bias p [ (f (X), +1)] -πE bias p [ (f (X), -1)] + E u [ (f (X), -1)],

where E bias p is the expectation over p(x|y = +1, o = +1). We call this functional the pseudo classification risk because it is not the true classification risk. An unbiased estimator for the pseudo classification risk can be obtained by replacing the expectations with the corresponding sample averages even if there is a selection bias. For the loss function, we use the logarithmic loss:

EQUATION

Justification for minimizing the pseudo classification risk: For the pseudo classification risk with the logarithmic loss function, the following theorem justifies its use. Let us denote a minimizer of (4) by f * , that is,

f * ∈ arg min f ∈F R bias PU (f ).

For the minimizer of (4), we show the following theorem. Theorem 3. It holds almost everywhere that

f * (x) =      (x / ∈ D 1 ), πp(x|y=+1,o=+1) p(x) (x ∈ D 1 ∩ D 2 ), 1 - (x / ∈ D 2 ),

where

D 1 = {x|πp(x|y = 1, o = +1) ≥ p(x)} and D 2 = {x|πp(x|y = 1, o = +1) ≤ (1 -)p(x)}.

A proof is provided in Appendix C. Theorem 3 implies that the minimization of the empirical version of the pseudo classification risk allows us to estimate r.

Empirical Estimation: When we train a classifier with training samples, we can naively replace the expectations with the corresponding sample averages. For a hypothesis set H, which is a set of measurable functions, let us define the following risk minimization problem,

EQUATION

where Êbias p denotes the averaging operator over positive data with a selection bias, Êu denotes the averaging over the unlabeled data, and R is a regularization term. du Plessis et al. (2015) showed that, under SCAR, the empirical version of the risk becomes unbiased toward the classification risk.

However, Kiryo et al. (2017) pointed out that unbiased PU learning does not work with deep neural networks. Minimizing an empirical risk of (3) with deep neural networks easily causes over-fitting because the risk is not bounded from below by 0. In order to implement PU learning with deep neural networks, Kiryo et al. (2017) proposed the following non-negative risk,

EQUATION

where (•) + := max{0, •}. After obtaining f , we construct an estimator of the density ratio r by r = 1 π f1 or r = 1 π f2 .

4.2. ESTIMATION OF r BY DIRECT DENSITY RATIO ESTIMATION:

For another approach, we consider estimating the density ratio r(x) = p(x|y=+1,o=+1) p(x)

directly. We can estimate the probability density functions of the numerator and the denominator. However, as known as Vapnik's principle, we should avoid solving more difficult intermediate problems than the target problem. Sugiyama et al. (2012) summarized methods estimating the density ratio directly. Among existing methods, we employ Least-squares importance fitting (LSIF), which uses the squared loss for density-ratio function fitting. The reason for this choice is that there is an algorithm called unconstrained Least-Squares Importance Fitting (uLSIF) with a computational advantage. We can obtain the closed-form solution just by solving the linear equations. Thus, uLSIF is numerically stable when it is regularized properly. Moreover, the leave-one-out cross-validation score for uLSIF can also be computed analytically, which significantly improves the computational efficiency in model selection.

Here, we introduce the formulation of LSIF. Let S be the class of non-negative measurable functions s : X → R + . We consider minimizing the following squared error between s and r:

EQUATION

The first term of the last equation does not affect the result of minimization and we can ignore the term, i.e., the density ratio is estimated through the following minimization problem:

s * = arg min s∈S R DR (s) = arg min s∈S 1 2 E u [(s(X)) 2 ] -E bias p [s(X)] .

Empirical Estimation: As mentioned above, to minimize the empirical version of (7), we use uLSIF (Kanamori et al., 2009) . Given a hypothesis class H, we obtain r by

EQUATION

where R is a regularization term.

4.3. ESTIMATION OF θ π:

We consider replacing the threshold defined by (2) with a value which can be calculated only from samples. By using the test inputs or held-out training data, {x te i } n te i=1 ∼ p(x), we find θπ that satisfies the following equation,

EQUATION

Here, we used the knowledge of π, the class-prior. This choice of θπ amounts to classifying top-π test data as positive after ranking the inputs by r.

5. EXPERIMENTS:

In this section, we report experimental results which were conducted using synthetic data and realworld datasets 1) . We used seven classification datasets, mushrooms, shuttle, pageblocks, usps, connect-4, spambase, and MNIST, from UCI repository 2) , CIFAR-10 3) and a document dataset obtained from SwissProt (Boeckmann et al., 2003) 4) . MNIST and CIFAR-10 originally have 10 and 10 classes, respectively, and we constructed the positive and negative datasets from them as follows: MNIST was preprocessed in such a way that 0, 2, 4, 6, 8 constitute the positive class, while 1, 3, 5, 7, 9 constitute the negative class; for CIFAR-10, the positive dataset is formed by 'airplane', 'automobile', 'ship' and 'truck', and the negative dataset is formed by 'bird', 'cat', 'deer', 'dog', 'frog' and 'horse'. Except for the document dataset, we show the details of datasets in Table 1 and made positive data with a selection bias based on estimators of p(y = +1|x) as we show in each experiments. For six datasets of the UCI repository and the CIFAR-10, we made positive datasets with a selection bias artificially, but, for the document dataset, we have an unlabeled dataset and a positive dataset, which is gathered for classifying the labels in the unlabeled dataset.

We call unbiased PU learning proposed by du Plessis et al. ( 2015) "PU", unbiased PU learning with a threshold estimated by ( 9) "PUSB", uLSIF with a threshold estimated by ( 9) "DRSB", nonnegative PU learning "nnPU" and nonnegative PU learning with a threshold estimated by ( 9) "nnPUSB".

For the hypothesis class H in the density ratio estimation (8), we use the linear-in-parameter model:

EQUATION

where ϕ(x) = [1, ϕ 1 (x), ..., ϕ m (x)] is a vector of basis functions. For basis functions, we used the Gaussian kernel located at sample points ϕ (x) = exp -xc 2 /(2σ 2 ) , where {c 1 , ..., c m } = {x 1 , ..., x n , x 1 , ..., x n } and m = n + n . For the hypothesis class H in the risk minimization of PU learning (5), we use the following model with the sigmoid function:

H := f (x) = 1 1 + exp(-β ϕ(x)) β ∈ R m+1 .

In this case, the loss is the same as the logistic loss and unbiased PU learning becomes convex. For the hypothesis class H in the risk minimization of nonnegative PU learning (6), we use deep neural networks. The specifications of deep neural networks are given in the following sections for each dataset. We mainly used the same structure proposed in Kiryo et al. (2017) in order to compare the performances. For the regularization term R, we used the 2 norm of the parameters scaled by a positive scalar λ. For the linear models, hyperparameters were selected via cross-validation.

1) The source code is available at https://github.com/MasaKat0/PUlearning.

2) The UCI data were downloaded from https://archive.ics.uci.edu/ml/index.php and https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/.

3) See https://www.cs.toronto.edu/~kriz/cifar.html.

4) The data can be downloaded from http://www.cs.ucsd.edu/users/elkan/posonly. 

5.1. TEST WITH SYNTHETIC DATA:

This experiment shows the classifier given by PUSB. We used samples from a mixture distribution of the following two class-conditional distributions:

p(x|y = +1) = N (1, 2 2 ) and p(x|y = -1) = N (-1, 2 2 ),

where N (µ, σ 2 ) denotes the univariate normal distribution with mean µ and variance σ 2 . A positive dataset with a selection bias was sampled from

p(x|o = +1, y = +1) ∝ (p(y = +1|x)) 10 .

We generated 1, 000 positive samples and 10, 000 unlabeled samples. We made two datasets with different class-priors π = 0.3 and π = 0.7. Figure 1 shows classifiers constructed by PU and PUSB along with the Bayes optimal classifier sign(p(y = +1|x) -1/2). The classifier of PUSB is closer to the Bayes optimal classifier than that of PU.

5.2. TEST WITH BENCHMARK DATA:

Here, we investigate the experimental performance in detail.

Linear-in-parameter model: We used the mushrooms, shuttle, pageblocks, usps, connect-4 and spambase datasets. First, we estimated p(y = +1|x) using the logistic regression with the same linear model. Then, we obtained the labeled positive data by labeling some instances of the positive data following

p(o = +1|x, y = +1) ∝ (p(y = +1|x)) 20 .

Then, we trained a classifier by minimizing the empirical risk of PU learning (4) and the density ratio estimation (7).

For each binary labeled dataset, we made 12 different pairs of positive and unlabeled data with 4 different class-priors, {0.2, 0.4, 0.6, 0.8}, and 3 different numbers of unlabeled data, {800, 1600, 3200}.

The number of positive data was fixed at 400. We used 1000 test data sampled from the same distribution as the unlabeled data. We ran the experiments 100 times and calculated the mean and standard deviation for the test dataset with PU, PUSB, and DRSB. The results are shown in Table 2 .

The classifiers obtained by our algorithm always show preferable performance to existing methods.

Neural network model: We used the MNIST and CIFAR-10 datasets. For MNIST, a 3-layer multilayer perceptron (MLP) with ReLU activation (Nair & Hinton, 2010) was used. For CIFAR-10, an all convolutional net (Springenberg et al., 2015) was used. Details of the network structure are shown in Appendix D. Then, we trained a classifier by minimizing (6) with the model defined above. We used 10, 000 test data sampled from the same distribution as the unlabeled data. We ran the experiments 100 times and calculated the mean of the error rate, the standard deviation of the error rate, the mean of recall and the mean of precision for each epoch in training with nnPU and nnPUSB. The results are shown on the left side and center of Figure 2 . In the upper row, we show the mean and standard deviation of the error rate. In the lower row, we show the mean of recall and the mean of precision. As shown in Figure 2 , the mean of the error rate of our algorithm is lower and the variance is also lower than the existing method. As we discussed in Section 4.3, FP = FN is also empirically observed. 

5.3. TEST WITH REAL-WORLD DATA:

In the previous sections, we artificially made positive data with a selection bias. Here we demonstrate the effectiveness of our algorithm in real-world data with a selection bias. We used a document dataset based on the SwissProt database released by Elkan & Noto (2008) . We call this dataset RealData.

The dataset originally contained 2,453 labeled positive examples (P) and 4,906 unlabeled examples (U). The unlabeled examples were labeled later by Das et al. (2007) . As a result, the dataset is likely to have a natural observation bias in the P data while it allows an access to the ground-truth labels for all data. Out of the U data, 348 examples are positive and the rest are negative. The class prior is π = 348/4, 906 = 0.0709. We used Bag-of-Words to represent the documents as 78, 894-dimensional vectors.

Details of the network structure are shown in Appendix D. We trained a classifier using positive and unlabeled data. Then, after finding a threshold estimated by (9), we evaluated the same evaluation measures as the previous experiments by classifying U, i.e., we regarded the unlabeled data as test data. As shown on the right of Figure 2 , the result of our algorithm outperforms the existing method.

5.4. TEST FOR UNKNOWN CLASS PRIOR:

In order to evaluate how our algorithm works for the case that the class prior is unknown, we empirically tested our algorithm with an estimator of the class prior. We used the RealData dataset in Section 5.3, whose class prior is 0.0709. For the class prior estimator, we used the KM2 method by Ramaswamy et al. (2016) , which is considered to be the state-of-the-art method in the case-control scenario under SCAR. The estimated class prior was 0.1095 and the result is shown in Figure 3 . We can see from the figure that our method works well with an estimated class prior in so far as RealData dataset is concerned. We also show results for the classifiers trained under misspecified class priors in Appendix E, which also shows that our method works stably for misspecified class priors.

6. CONCLUSION:

In this paper, we proposed a novel framework for PU learning with a selection bias in positive data.

We put the assumption of the invariance of order and showed the density ratio of labeled positive data and unlabeled data has the same order as the class-conditional distribution for inputs. Based on this result, we proposed a method based on partial identification in which we first estimate the density ratio and then use it as a classifier by setting a threshold. We conducted experiments to confirm the effectiveness of our approach. As we showed in the experiments, our method outperforms previous PU methods on real-world data.

By Bayes' theorem, we can expand the density ratio in (1) as follows:

r(x) = p(x|o = +1, y = +1) p(x) = p(y = +1|x, o = +1)p(x|o = +1) p(y = +1|o = +1) 1 p(x) = p(y = +1|x, o = +1) 1 p(y = +1|o = +1) p(x|o = +1) p(x) = p(y = +1|x)p(o = +1|x, y = +1) p(o = +1|x) 1 p(y = +1|o = +1)p(o = +1) p(o = +1)p(x|o = +1) p(x) .

Because p(y=+1|x)p(o=+1|x,y=+1) p(o=+1|x)

= 1 from (11), this is equivalent to

r(x) = Cp(o = +1|x),

where C = 1 p(y=+1,o=+1) . Hence, if Assumption 1 holds, for any x i , x j ∈ X ,

p(y = +1|x i ) ≤ p(y = +1|x j ) ⇔ r(x i ) ≤ r(x j ).

B PROOF OF THEOREM 2:

Before proving Theorem 2, we consider a threshold defined as follows:

EQUATION

Then, we state the following lemma on the relationship between γ and θ π . Lemma 1. The equation x ∈ X , (r(x) -θ π )(p(y = +1|x) -γ) ≥ 0 holds almost everywhere with respect to p(x).

Proof. By (2) and ( 12), the following equation also hold,

1[r(x) > θ π ]p(x)dx = 1[p(y = +1|x) > γ]p(x)dx.

Hence, we can derive

(1[r(x) > θ π ] -1[p(y = +1|x) > γ])p(x)dx = 0.

This is equivalent to

(1[(r(x) -θ π )(p(y = +1|x) -γ) < 0]p(x)dx = 0.

From this equation, (r(x) -θ π )(p(y = +1|x) -γ) ≥ 0 holds almost surely.

Using Lemma 1 we prove Theorem 2.

Proof. π = 1[p(y = +1|x) ≥ γ]p(x)dx is equivalent to p(y = +1|x)p(x)dx = 1[p(y = +1|x) ≥ γ]p(x)dx,

where the left hand side is equal to

{x|p(y=+1|x)<γ} p(y = +1|x)p(x)dx + {x|p(y=+1|x)≥γ} p(y = +1|x)p(x)dx,

2. If we assume λ > 0 and µ = 0, the KKT condition is reduced to

z * = 1 -, λ = (1 -)p(x) -πp(x|y = +1, o = +1) (1 -) 2 + (1 -) .

In this case, λ > 0 is equivalent to x ∈ D 2 .

3. If we assume λ = 0 and µ > 0, the KKT condition is reduced to

z * = , µ = p(x) -πp(x|y = +1, o = +1) 2 - .

In this case, λ > 0 is equivalent to x ∈ D 1 .

4. If λ, µ > 0, there is no feasible solution.

In summary, the solution for the optimization problem arg min z∈ ) means a similar layer but with stride 2, etc.; it is one of the best architectures for CIFAR-10. Batch normalization (Ioffe & Szegedy, 2015) was applied before hidden layers.

[ ,1-] C(z, x) is z * =      (x / ∈ D 1 ), πp(x|y=+1,o=+1) p(x) (x ∈ D 1 ∩ D 2 ), 1 - (x / ∈ D 2 ).

In Section 5.3, the model for this dataset was a 5-layer multilayer perceptron (MLP) with ReLU (more specifically, 78894-300-300-300-300-1).

E EXPERIMENTAL RESULTS OF THE FIRST EXPERIMENT OF SECTION 5.4

In the first experiment, we trained a classifier under misspecified class priors, 0.0209(= 0.0709 -0.0500), 0.1209(= 0.0709 + 0.0500), 0.1709(= 0.0709 + 0.1000), and 0.2709(= 0.0709 + 0.2000).

The results are shown in Figures 4-6. In Figure 4 , the test error in each misspecified class priors are shown. In Figure 5 , the precision and recall in each misspecified class prior is shown. In both the existing method and our method, misspecified class priors had a bad influence. However, our method was less influenced by the misspecification and showed better performance than the existing method.

Besides, the difference between the precision and recall of our algorithm is narrower than that of the existing method as expected. In order to discuss how misspecified class prior affects the precision and recall, we show the difference the recall from the precision and show the values in Figure 6 . This result shows how the difference broadens as the class prior is misspecified worse. 

:



Figures and Tables:

Figure 1: Two Gaussians: The horizontal axis is the value of x and the vertical axis is the probability density. The vertical lines represent the decision boundaries of the classifiers. The distribution of positive data, negative data, unlabeled data and p(x|o = +1, y = +1) are plotted.

Figure 2: Experimental results of training deep neural networks. Left: MNIST; Center: CIFAR-10; Right: RealData: All measures are calculated for test data sampled from the marginal distribution p(x). The horizontal axis is the epoch of training the network, the vertical axes of the top figures are the error rates and the vertical axes of the bottom figures are the precision and the recall.

Figure 3: Results of the second experiment of Section 5.4 using the RealData dataset with the estimated class prior 0.1095 (the true class prior is 0.0709). The horizontal axes are the epochs of training the network, the vertical axis of the right figure is the error rate and the vertical axis of the left figure is the value of the precision and the recall.

define f * (x) := arg min z∈[ ,1-] C(z, x). It can be confirmed that f * ∈ F because p(x|y = 1, o = +1) and p(x) are measurable and f * takes values in [ , 1-]. Therefore, the solution of the original optimization problem arg min f ∈F R bias PU (f ) is equal to f * almost everywhere. D NETWORK STRUCTURE USED IN SECTIONS 5.2 AND SECTIONS 5.3In Section 5.2, we used the MNIST and CIFAR-10 datasets. The model for the MNIST dataset was a 3-layer multilayer perceptron (MLP) with ReLU(Nair & Hinton, 2010) (more specifically, 784-100-1). The model for the CIFAR-10 dataset was an all convolutional net(Springenberg et al., 2015):(32 × 32 × 3)-[C(3 × 3, 96)] × 2-C(3 × 3, 96, 2)-[C(3 × 3, 192)] × 2-C(3 × 3, 192, 2)-C(3 × 3, 192)-C(1 × 1, 192)-C(1 × 1,10)-1000-1000-1, where the input is a 32 × 32 RGB image, C(3 × 3, 96) means 96 channels of 3 × 3 convolutions followed by ReLU, [•] × 2 means there are two such layers, C(3 × 3, 96, 2

Figure 4: Experimental results of training deep neural networks using the RealData dataset with misspecified class priors (the true class prior is 0.0709). Upper Left: π = 0.0209; Upper Right: π = 0.1209; Lower Left: π = 0.1709; Lower Right: π = 0.2709: All measures are calculated for test data sampled from the marginal distribution p(x). The horizontal line is epoch of training the network, the vertical line of the upper is error rate.

Figure 5: Experimental results of training deep neural networks using the RealData dataset with misspecified class priors (the true class prior is 0.0709). Upper Left: π = 0.0209; Upper Right: π = 0.1209; Lower Left: π = 0.1709; Lower Right: π = 0.2709: All measures are calculated for test data sampled from the marginal distribution p(x). The horizontal line is epoch of training the network, the vertical line of the upper is value of the precision and the recall.

Figure 6: Experimental results of training deep neural networks using the RealData dataset, whose true class prior is 0.0709, with misspecified class priors, 0.0209, 0.1209, 0.1709, and 0.2709.: All measures are calculated for test data sampled from the marginal distribution p(x). The horizontal line is epoch of training the network, the vertical line of the right graph is value of the precision -recall.

Dataset statistics (Pos. frac.: Positive fraction, Dim: Dimension).

Table content: <table><tr><td>Dataset</td><td colspan="3"># of samples Pos. frac. Dim.</td></tr><tr><td>mushrooms</td><td>8,124</td><td>0.517</td><td>112</td></tr><tr><td>shuttle</td><td>58,000</td><td>0.786</td><td>9</td></tr><tr><td>pageblocks</td><td>5,473</td><td>0.898</td><td>10</td></tr><tr><td>usps</td><td>9,298</td><td>0.524</td><td>256</td></tr><tr><td>connect-4</td><td>67,557</td><td>0.658</td><td>126</td></tr><tr><td>spambase</td><td>4,601</td><td>0.394</td><td>57</td></tr><tr><td>MNIST</td><td>70,000</td><td>0.511</td><td>784</td></tr><tr><td>CIFAR-10</td><td>60,000</td><td>0.400</td><td>3,072</td></tr></table>

The error rate of classification in test data (%) are shown for the different class-priors and the different number of samples. For all experiments, the linear-in-parameter model was used. Best and equivalent methods (under 5% t-test) are bold. (.011) 56.7 (.011) 56.6 (.008) 33.7 (.020) 33.7 (.019) 33.5 (.024) 23.6 (.012) 23.7 (.014) 23.6 (.014) 0.6 22.4 (.023) 23.4 (.033) 28.1 (.028) 20.9 (.016) 21.1 (.016) 21.5 (.020) 18.7 (.011) 18.6 (.012) 18.1 (.017) 0.8 19.8 (.003) 20.0 (.001) 20.0 (.001) 13.9 (.022) 13.6 (.023) 16.7 (.043) 15.4 (.011) 14.8 (.014) 14.3 (.019) (.012) 10.3 (.013) 10.0 (.010) 10.5 (.013) 10.2 (.012) 10.0 (.010) 30.5 (.029) 30.2 (.022) 29.9 (.023) 0.6 12.5 (.015) 12.3 (.015) 12.1 (.013) 11.2 (.016) 10.9 (.015) 10.6 (.013) 32.9 (.026) 33.2 (.031) 33.1 (.030) 0.8 19.8 (.020) 19.8 (.016) 19.5 (.017) 10.3 (.016) 9.8 (.014) 9.6 (.014) 25.9 (.028) 25.3 (.027) 25.8 (.030) connect-4 0.2 22.3 (0.017) 21.9 (.014) 21.6 (.013) 21.8 (.013) 21.5 (.012) 21.2 (.011) 26.7 (.012) 26.6 (.012) 26.4 (.011) 0.4 31.2 (.015) 31.0 (.015) 30.7 (.016) 31.2 (.015) 31.0 (.015) 30.7 (.016) 39.4 (.016) 39.6 (.018) 39.2 (.016)

Table content: <table><tr><td/><td/><td/><td>PU</td><td/><td/><td>PUSB</td><td/><td/><td>DRSB</td><td/></tr><tr><td>Dataset</td><td>π</td><td>800</td><td>1600</td><td>3200</td><td>800</td><td>1600</td><td>3200</td><td>800</td><td>1600</td><td>3,200</td></tr><tr><td>mushrooms</td><td>0.2</td><td>5.1 (.076)</td><td>5.0 (.055)</td><td>5.5 (.083)</td><td>4.1 (.007)</td><td>3.8 (.007)</td><td colspan="3">4.0 (.007) 10.7 (.010) 9.9 (.011)</td><td>9.9 (.012)</td></tr><tr><td/><td>0.4</td><td>7.0 (.012)</td><td>6.6 (.010)</td><td>6.8 (.025)</td><td>6.9 (.012)</td><td>6.7 (.010)</td><td colspan="4">6.8 (.010) 15.8 (.014) 15.0 (.016) 15.2 (.012)</td></tr><tr><td/><td>0.6</td><td colspan="4">10.8 (.020) 11.3 (.015) 11.3 (.016) 8.2 (.013)</td><td>8.5 (.010)</td><td colspan="4">8.3 (.011) 18.5 (.014) 18.8 (.012) 18.5 (.013)</td></tr><tr><td/><td>0.8</td><td colspan="4">21.1 (.022) 21.6 (.021) 21.7 (.016) 8.1 (.015)</td><td>8.0 (.012)</td><td colspan="4">7.6 (.014) 14.2 (.013) 14.3 (.014) 14.4 (.011)</td></tr><tr><td>shuttle</td><td>0.2</td><td colspan="4">23.8 (.006) 23.8 (.007) 23.8 (.007) 5.2 (.008)</td><td>5.0 (.007)</td><td>5.0 (.007)</td><td>5.1 (.008)</td><td>5.1 (.008)</td><td>5.1 (.007)</td></tr><tr><td/><td>0.4</td><td colspan="4">15.5 (.023) 15.5 (.019) 15.0 (.016) 7.8 (.011)</td><td>7.7 (.011)</td><td>7.6 (.012)</td><td>6.7 (.025)</td><td>7.6 (.029)</td><td>7.2 (.027)</td></tr><tr><td/><td>0.6</td><td colspan="7">26.1 (.018) 26.4 (.017) 26.4 (.016) 11.1 (.015) 10.8 (.012) 11.0 (.015) 7.8 (.028)</td><td>7.4 (.028)</td><td>7.1 (.028)</td></tr><tr><td/><td>0.8</td><td colspan="7">14.6 (.006) 14.6 (.005) 14.8 (.007) 12.3 (.014) 12.4 (.014) 12.3 (.012) 7.9 (.021)</td><td>7.6 (.023)</td><td>7.4 (.022)</td></tr><tr><td colspan="2">pageblocks 0.2</td><td colspan="9">39.5 (.009) 39.6 (.010) 39.6 (.008) 41.6 (.021) 42.5 (.022) 43.7 (.019) 23.1 (.016) 23.1 (.015) 22.2 (.012)</td></tr><tr><td colspan="3">0.4 56.5 usps 0.2 9.0 (.011)</td><td>8.5 (.009)</td><td>8.2 (.010)</td><td>8.0 (.009)</td><td>7.7 (.007)</td><td colspan="4">7.4 (.009) 18.2 (.016) 19.6 (.013) 19.7 (.014)</td></tr><tr><td/><td>0.4</td><td>10.5</td><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2019):
 The authors consider the problem of learning from positive and unlabeled data in which only a subset of the true positives is labeled. While the common assumption (eg Elkan & Noto, du Plessis et al.) prescribes that the labeled set is picked independently at random from the positive set, this paper assumes that a (positive) example x is more likely to be labeled the more it exhibits positive features: formally, the higher Pr(y=1 | x), the higher Pr(o=1 | x). For instance, in the case of anomaly detection, the more likely an example is anomalous, the more likely it would get manually flagged (labeled) as positive. The authors refer to this assumption as Invariance of Order. The proposed method requires the knowledge of the positive class prior Pr(y=1), and can be summarized in the following three steps: (i) estimate r(x)=Pr(x | y=1, o=1`)/Pr(x); (ii) find the threshold .theta such that the number of datapoints x with r(x) > .theta is a fraction Pr(y=1); (iii) train a classifier on sign(r(x) - .theta). Conceptually, the Invariance of Order assumption allows to use the order on r(x) as a proxy for an order on Pr(y=1|x), so then the knowledge of Pr(y=1) is enough to find .theta, and to port the original problem to a vanilla binary classification problem. Concerns: - He et al. 2018 use a very similar assumption and no comparison with that work is provided. The authors briefly mention that work in the introduction but don*t perform due diligence in assessing differences/novelties with respect to that work, neither as a discussion or in the experiments. - The requirement of knowing the fraction of positive examples is hard to justify in practice. Have you tried using the estimate obtained by Elkan et al, or other related work? - Experiments are confusing and not convincing: apart from the very last experiment, all datasets are synthetic. No comparison with previous work is presented, except for "unbiased PU learning (PU)", which I assume is Elkan et al ? If that is indeed the case, which one of their methods are you comparing against? Even more troublesome is the fact that in all experiments you*re providing your algorithm with the correct class-prior Pr(y=1), but it*s not clear if this is provided to PU as well. You may want to consider estimating Pr(y=1) using methods from related work to see how it affects the accuracy. - Related work discussion is completely missing apart from one paragraph in the introduction. Minor: - The acronym SCR is not very conventional; I would suggest IID which is often used as shorthand for independently identically distributed. - Invariance of Order: when introducing it, you may want to add a sentence providing the intuition behind the assumption. - Example 2 (Face recognition) is not very convincing and not very clear. Please rephrase. - Pseudo-classification risk: why was the log-loss used? Can other losses be used as well? - Theorem 3: add some intuition and explain tradeoff on .epsilon - Experiments section: help the reader by adding a reminder on equations, as it*s difficult to flip back and forth to their definitions. Eg, "we trained a classifier minimizing (4) and (7) with the model (10)" is difficult to digest and follow. - Experiments: confusing commas in {800,1,600,3,200} => {800, 1600, 3200} - Too many acronyms and abbreviations.