Online Positive and Unlabeled Learning

1 Introduction

Traditional supervised learning usually employs labeled positive and negative examples for model training. However, the labeled negative data are not always available in many real-world applications. This has led to the development of Positive and Unlabeled learning (PU learning) [Denis et al., 2005], which aims to train a binary classifier from only positive and unlabeled data without the existence of negative data. Here the unlabeled data could be either positive or negative, but their ground-truth labels remain unknown to the learning algorithm throughout the training stage. Due to its usefulness and effectiveness, PU learning has been widely used in many real-world applications, such as software clone detection [Wei and Li, 2018], remote-sensed hyperspectral image classification [Li et al., 2011], etc.

Given its broad applicability as mentioned above, PU learning has attracted intensive research attention in recent years. A variety of effective algorithms have been proposed, such as [Liu et al., 2002; Kiryo et al., 2017; Gong et al., 2019b], etc. Although these existing methods have received encouraging performance on various datasets or tasks, they all work on a batch learning or offline learning mode, which cannot deal with the online learning scenarios with sequential data. Unfortunately, it is quite often that the data are presented in sequence for massive practical applications, so traditional batch learning algorithms which require all training data to be simultaneously observed will not work. Therefore, online learning [Rosenblatt, 1958; Crammer and Singer, 2003] is proposed to process the training examples that arrive in a sequential order, where a learner aims to learn and update the optimal classifier for processing the future data at each step. In other words, the classifier is required to be updated incrementally for any new training examples, so that the online learning algorithms do not need to observe all training examples for classifier training.

To make PU models applicable to sequential data, in this paper, we propose a novel Online Positive and Unlabeled ("OPU" for short) learning algorithm. The key challenge for our online model designing is how to avoid the bias incurred by the absence of negative data, and to update the model incrementally according to the sequential positive and unlabeled examples. In this paper, we propose to overcome this challenge by exploring the unbiased estimator for positive and unlabeled learning [Du Plessis et al., 2015] and utilizing an Online Gradient Descent (OGD) [Zinkevich, 2003] method to optimize our model. Specifically, we cast OPU learning as a sequential Empirical Risk Minimization problem, in which different unbiased loss functions are elaborately designed for arriving positive and unlabeled data, respectively. Then, we show that, for any coming new data point, the model can be updated independently and incrementally by OGD. Besides, we present theoretical proof of regret that bounds the difference between the solution computed by our OPU learning and the optimal solution learned at hindsight. Moreover, experimental results on both benchmark and realworld datasets are presented, confirming the effectiveness of our OPU algorithms.

2 RelatedWork

This section briefly reviews some typical works on PU learning and online learning, as they are related to this paper.

2.1 PU Learning

PU learning has been a popular research topic in machine learning community. Up to now, a variety of PU learning models have been proposed, and they can typically be categorized into three types according to how the unlabeled data are handled.

The methods belonging to the first category deploy a twostep strategy which firstly identifies some reliable negative examples from the unlabeled set, and then employs the reliable negative examples as well as the original positive examples to train a traditional supervised classifier. In this strategy, the first stage is critical and various methods have been developed to find the potential negative examples, such as "Spy Technique" [Liu et al., 2002], 1-DNF method [Yu et al., 2002], and K-means based prototype method [Xiao et al., 2011]. The methods belonging to the second category convert PU learning problem to a one-sided label noise learning problem, which directly treat the unlabeled examples as noisy negative ones. Concretely, the original positive examples in the unlabeled set are regarded as mislabeled, while no negative examples are mislabeled as positive ones, and then some effective label noise learning algorithms can be deployed to solve the PU learning problem. The representative works are [Lee and Liu, 2003], [Shi et al., 2018], and [Gong et al., 2019b]. The methods belonging to the last category impose different weights on the loss values incurred by positive examples and also the pseudo-labeling on treating unlabeled examples as positive examples and negative examples, and thus transferring PU learning problem into a cost-sensitive learning problem. The typical works include [Elkan and Noto, 2008; Du Plessis et al., 2014; Du Plessis et al., 2015; Kiryo et al., 2017].

Apart from above-mentioned methods, other representative PUmodels usually rely on larger-margin theory [Gong et al., 2019a], multi-manifold data structure [Gong et al., 2019c], label disambiguation [Zhang et al., 2019], and sequential minimal optimization [Sansone et al., 2018]. However, as mentioned in the introduction, all above methods are only designed for batch learning mode and cannot be applied to deal with sequential data.

In fact, [Li et al., 2009] has studied PU learning for the data on the fly. However, both their setting and target are very different from ours as they only treat current data as positive while regarding all historical data as unlabeled, to model the interest drift of online customers. Differently, we require that the real labels of positive and unlabeled data should be specified in advance and will not change during the entire online learning process, so that our model coincides with the standard PU learning requirements.

2.2 Online Learning

Online learning [Rosenblatt, 1958; Kivinen et al., 2004; Finn et al., 2019] aims to learn from the data arriving in a sequential order. In general, existing online learning algorithms mainly fall into two categories according to the model updating strategy, namely the first-order-based online learning and the second-order-based online learning.

The first-order-based online learning algorithms only exploit the first order feature information. Representative works include Perceptron [Rosenblatt, 1958; Freund and Schapire, 1999], Relaxed Online Maximum Margin Algorithm [Li and Long, 2000], and Passive-Aggressive algorithm [Crammer et al., 2006]. Apparently, the performances of these algorithms are limited, for only the first-order information is deployed. In recent years, some second-order-based online learning algorithms have been elaborately designed to improve the performance of first-order-based algorithms. Generally, the second-order-based algorithms can significantly outperform the first-order-based algorithms by exploring the second-order information, such as the covariance matrix of the feature information. Representative works are the secondorder Perceptron [Cesa-Bianchi et al., 2005], ConfidenceWeighted learning [Dredze et al., 2008], and Adaptive Regularization of Weights Learning [Crammer et al., 2009].

However, the aforementioned algorithms are not applicable to the PU learning problem studied in this paper, and this motivates us to seek for a novel online training strategy for tackling the OPU learning problem.

3 Preliminaries on Batch-mode PU Learning

In this section, we review the formal setting for traditional batch-mode PU learning, which helps to explain our designed online algorithm in Section 4.

Consider a binary classification problem, where x ∈ Rd denotes a d-dimensional pattern and y ∈ {1,-1} is the corresponding class label. Let p(x, y) be the underling joint density of (x, y), and the class-conditional densities regarding positive class and negative class can be written as pp(x) = p(x|y = 1) and pn(x) = p(x|y = -1), respectively, where p(x) denotes the marginal density regarding unlabeled data. Furthermore, given π = p(y = 1) as the positive class-prior probability, we have that p(y = -1) = 1 - π. Since an unlabeled dataset consists of positive and negative examples, we know that p(x) = πp(x|y = 1) + (1 - π)p(x|y = -1).

Assume that we have a positive dataset P and an unlabeled dataset U independent and identically drawn from an unknown distribution D as

where np and nu are the size of positive dataset and unlabeled dataset, respectively. The goal of PU learning is to learn a classifier g(x) that assigns a label ˆ y to a new pattern x as ̂ y = sign(g(x)). It has been widely acknowledged that the Bayes optimal classifier g⋆(x) can be obtained by minimizing the following classification risk, namely

where (X, Y ) are corresponding random variables of (x, y), Ep[·] = EX∼pp(x)[·], En[·] = EX∼pn(x)[·], and ℓ0-1(·) is the zero-one loss formulated as ℓ0-1(z) = 1 2 - 12 sign(z) with z being the variable.

Thanks to the availability of positive and negative examples in the traditional fully supervised learning, the expectations Ep [ℓ0-1(g(X))] and En [ℓ0-1(-g(X))] in Eq. (1) can be estimated through the corresponding example averages. However, there are no negative examples available for PU learning, therefore En [ℓ0-1(-g(X))] cannot be estimated directly. To solve this problem, [Du Plessis et al., 2015] proposed to estimate En [ℓ0-1(-g(X))] indirectly from weighted Ep [ℓ0-1(-g(X))] and Eu [ℓ0-1(-g(X))]. Based on the fact that p(x) = πp(x|y = 1)+(1-π)p(x|y = -1), we can obtain

where Eu[·] denotes the expectation over p(x). Therefore, the risk R(g) in PU learning can be approximated by

From the equation above, we can see that the risk for PU learning consists of a composite loss for positive examples i.e., ℓ0-1(g(X)) - ℓ0-1(-g(X)), and an ordinary loss for unlabeled examples, i.e., ℓ0-1(-g(X)).

[Du Plessis et al., 2015] showed that a loss function ℓ(z) will lead to a convex PU learning model if it satisfies the linear-odd property, namely ℓ(z)-ℓ(-z) = -z, and the feasible ℓ(z) can be double hinge loss, square loss, and logistic loss. In our method, the performance of different loss functions with linear-odd property will be discussed in Section 6.

4 The Proposed OPUMethod

Let us consider the problem setting of online positive and unlabeled classification task. Let {(xt, yt) |t = 1, . . . , T} be a sequence of input examples under a potential distribution D, where xt ∈ Rd is a pattern of d dimension received at the t-th time, yt ∈ {1, 0} is the observed class label of corresponding pattern, and T is the number of training rounds across the whole training stage. Here, we take y = 1 for positive examples and y = 0 for unlabeled examples. The goal of OPU classification is to learn a linear classifier g(xt) = w⊤ t · xt, where wt ∈ Rd is the weight vector at the t-th time during the training stage.

4.1 Basic OPUwith Single Coming Datum

We cast our OPU learning as sequential Empirical Risk Minimization problem, of which the main idea is to propose an unbiased estimate for the loss induced by the received training examples at each time. Specifically, our goal is to develop an OPU learning algorithm which approximates the risk presented in Eq. (3).

Given a surrogate loss function with linear-odd property ℓ(z), Eq. (3) turns to be a convex optimization problem as

Input: The penalty parameter λ; 1: Initialize w0 ← 0; 2: for t = 1, 2, . . . , T do 3: Receive a training example (xt, yt); 4: Set learning rate ηt = 1 λt ; 5: if yt = 1 then 6: Calculate the gradient ∇t = -πg′ (xt) + λwt; 7: else 8: Calculate the gradient ∇t = ℓ′ (-g(xt)) + λwt; 9: end if 10: Update wt ←ΠW(wt-1 -ηt∇t); 11: end for Output: The latest classifier parameter wT .

which can be rewritten as an average of a set of training examples, namely

Now, we reformulate the risk estimation for each individual training example received at the t-th time, i.e.,

where 1(·) is an indicator function which equals to one if its argument is true, and zero otherwise. Using this representation, we can directly apply the gradient descent based online learning method to solve OPU learning problem. Formally, given a linear-in-parameter classifier g(xt) = w⊤ t · xt, the regularized objective function of Eq. (6) can be written as

where the first term and the second term are the losses induced by the received positive and negative examples, and the last term is an L2 regularizer to avoid overfitting with λ being a nonnegative penalty parameter.

Then, we consider the unbiased gradient ∇t of the above objective function in presence of the t-th coming data, which is given by

∇t = -π1yt=1g′ (xt) +1yt=0ℓ′ (-g (xt)) +λwt, (8) where g′ (·) and l′ (·) are the corresponding derivatives. Therefore, we can update wt ← ΠW(wt-1 - ηt∇t) using a step size of ηt, where ΠW(w) is a projection step defined as ΠW(w) = argminw′∈W ‖w-w′ ‖, with W being a feasible set of w. After a predetermined number T of iterations, we output the wT in the last iteration. Algorithm 1 concludes the overall OPU algorithm with single coming datum.

4.2 Extended OPUwithMultiple Coming Data

Practically, we may also meet the cases that the data come in groups, so we extend our basic OPU learning algorithm to enable it to process a set of examples for one time.

To be exact, given a small training set It = {(xi, yi)}bi=1 with the size of b (b > 1) at time t (t = 1, 2, . . . , T), the regularized objective function can be formulated as

where RIt (g) is the risk averages of corresponding positive and unlabeled examples, defined as

Now, we rewrite the objective function fIt (wt) by adding a conservative constraint γt 2 ‖wt -wt-1‖22 [Li et al., 2014], and obtain as

where λ is a nonnegative trade-off parameter and γt is a conservative coefficient related to λ. The first term is the unbiased loss estimator for PU learning aiming to achieve full utilization of this the currently coming set, the second term is an L2 regularizer to avoid overfitting, and the last term is a conservative constraint which limits dramatic changes of the weight vector to avoid overutilization.

For (xi, yi) ∈ It, i = 1, . . . , b, by computing the unbiased gradient of the above approximate objective Eq. (10), we have

By following the gradient descent based online learning method, the learning parameter can be effectively updated as wt ← ΠW(wt-1 - ηt∇It ), with ηt being the learning rate.

Furthermore, compared with the basic OPU algorithm with single coming datum, another benefit brought by the extended OPU algorithm is that an O(1/b) variance reduction can be achieved if b (b > 1) training examples are presented each time [Dekel et al., 2012].

5 Theoretical Analysis

In this section, we are going to analyze the regret bound of the proposed OPU learning method, which measures the difference between the cumulative loss of our predictions and the cumulative loss of the optimal predictor w⋆. To be specific, we first bound the regret of our basic OPU algorithm which updates the model with one example per time, and then we bound the regret of the extended OPU algorithm which updates the model with b (b > 1) arrived examples.

5.1 Regret for Basic OPUAlgorithm

When only one example is processed at each time, we have the following theorem for the regret bound:

Theorem 1. Let f1, . . . , fT be a sequence of λ-strongly convex functions. Let W be a closed convex set and define ΠW(w) = argminw′∈W ‖w-w′ ‖. Let w0, . . . ,wT be a sequence of vectors such that w0 ∈ W and for t ≥ 0, wt = ΠW (wt-1 - ηt∇t), with ∇t being the unbiased gradient of ft at wt. Assume that for all t, ‖∇t‖ ≤ G, we have

Proof. Let w⋆ ∈ argminw∈W ∑Tt=1 ft(w). By recalling the definition of regret, we have

Since ft is λ-strongly convex, we get the following inequality,

Following Zinkevichs analysis [Zinkevich, 2003], we are going to upper-bound∇⊤t (wt -w⋆). According to the properties of projections [Hazan et al., 2007], we have,

Hence,

After rearranging the above equation and using the assumption ‖∇t‖ ≤ G, we obtain

By comparing Eq. (14) and Eq. (17), and summing up Eq. (17) from t = 1 to T with ηt = 1/(λt), we have

which concludes the proof.

5.2 Regret for Extended OPUAlgorithm

When a set of examples are processed at each time, we have the following theorem for the regret bound:

Theorem 2. Let {It}Tt=1 be the received training sets of the learning algorithm, with each training set consisting of b (b > 1) training examples. Let fI1 , . . . , fIT be a sequence of λstrongly convex functions. Let W be a feasible set of w, and w0, . . . ,wT be a sequence of vectors such that w0 ∈ W and w⋆ ∈ argminw∈W ∑Tt=1 fIt (w). Assume that for all t, supw∈W ‖∇fIt (wt) - ∇f (w)‖22 ≤ A2 , we have

Proof. By using the definition of regret, in this case we have

According to Theorem 1 in [Li et al., 2014], assumed that fIt (wt) is λ-convex for all t and the updating parameter is chosen as γt = γ + λt, we have that for all w⋆ ∈ W,

For strongly convex objective function, one may choose γ = (λA)/(√b ‖w⋆ -w0‖2 ) to minimize the upper bound in Eq. (21). Since the variance decreases with O(1/b) for each set of coming data, we see that the choice of γ in Eq. (21) with γ = O(1/√b) is appropriate. We can easily get the following aggregated regret bound with simple algebra,

which completes the proof.

From Theorems 1 and 2, we see that the regret bound for our basic OPU algorithm is the order of O(logT), and that for our extended OPU is O((logT)/b), which improves the regret bound of the basic OPU algorithm with O(1/b). Therefore, the models finally obtained by our method are very close to the ideal solution w⋆.

6 Experiments

In this section, we first study the performance of the proposed method on benchmark and real-world datasets, and then investigate the parametric sensitivity of the pre-tuned parameter in our model.

6.1 Compared Algorithms

In our experiments, two different loss functions with linearodd property are discussed, i.e., double hinge loss ℓDH(z) = max (-z,max (0, 1 2 - 12 z)) and square loss ℓSL(z) = 1 4 (z - 1)2 - 14 . The following methods are compared:

• UPU: Unbiased PU learning, a batch-mode PU learning algorithm [Du Plessis et al., 2015], which can be deemed as the performance upper bound of our OPU algorithm.
• OPUDH: The proposed basic OPU algorithm with single coming datum in Sec. 4.1 using double hinge loss.
• OPUSL: The proposed basic OPU algorithm with single coming datum in Sec. 4.1 using square loss.
• OPUDH: The proposed extended OPU algorithm with multiple coming data in Sec. 4.2 using double hinge loss.
• OPUSL: The proposed extended OPU algorithm with multiple coming data in Sec. 4.2 using square loss.

6.2 Benchmark Datasets

We conduct experiments on a variety of benchmark datasets from OpenML machine learning repositories 1 . To be specific, four binary datasets are adopted for algorithm evaluation including Vote, Australian, Mushroom, and Phishing, and their brief information is presented in Table 1.

For each dataset, we randomly choose r = 20%, 30%, and 40% positive examples as well as all negative examples as unlabeled and leave the rest positive examples as labeled. Under each r, we conduct five-fold cross validation on every compared method and report the average accuracy and standard deviation over the five independent implementations. As a result, each model under a certain implementation is trained with 80% examples and then tested on the rest 20% examples. Moreover, all data features are normalized to [-1, 1] in advance, and the formation of training set is kept identical for all compared methods to ensure fair comparison. In our experiments, the class prior of positive examples π is assumed to be known during training for all the compared methods, which is also assumed by the existing PU learning works such as [Du Plessis et al., 2015; Kiryo et al., 2017; Gong et al., 2019b]. In practice, π can be obtained by experience or some domain-specific prior knowledge. Besides, the parameters of every algorithm have been carefully tuned on the validation set to achieve the best performance. In our OPU, we choose the regularization parameter λ from {10-6 , . . . , 102 }. For UPU, the regularization parameter λ is chosen from {10-3 , . . . , 101 }. For our extended OPU algorithms including OPUDH and OPUSL, 5% training examples of the whole examples are selected to form the set of input data at each time.

The obtained test accuracies are reported in Table 1. We can find that the extended OPU algorithms OPUDH and OPUSL usually achieve higher accuracies than the basic OPU algorithms OPUDH and OPUSL, and the OPU algorithms using double hinge loss often outperform the OPU algorithms using square loss. Besides, the performances of our OPU algorithms are very close to the performance of batch-mode PU learning method (i.e., UPU), and in some cases our OPU algorithm can perform even better than UPU, which suggests the effectiveness of the proposed method.

6.3 Real-world Datasets

Here, we investigate the performance of the compared methods on image classification tasks. Concretely, CIFAR10 [Krizhevsky and Hinton, 2009] and SVHN [Netzer et al., 2011] are chosen to evaluate their performance. CIFAR-10 consists of 60000 32×32 natural images in 10 classes with each class containing 6000 images. We choose the images of transportation tools ('airplane', 'auto mobile', 'ship', and 'truck') as negative, and regard the images of animals ('bird', 'cat', 'deer', 'dog', 'frog', and 'horse') as positive. Therefore, there are 24000 positive examples and 36000 negative examples in total. SVHN consists of 99289 32 ∗ 32 digit images in 10 classes i.e., the digits '0'-'9', where the negative set is formed by the digit images '1'-'5', and the rest digit images compose the positive set. As a result, we get 34699 positive examples and 64590 negative examples. Note that the training set and the test set are split in advance with 50000 training examples and 10000 test examples for CIFAR-10, and 73257 training examples and 20632 test examples for SVHN.

1 https://www.openml.org/

In our experiments, we extract 512-dimensional GIST features for each image. Similar to the previous experiments, for each dataset, the situations r = 20%, 30%, and 40% are studied. The parameters of every method have been carefully tuned to achieve the best performance. The test accuracies achieved by the compared methods are presented in Table 2, where we can see that although our OPU algorithms receive the sequential data sequentially, their performances are very similar to the compared UPU learning algorithm with all data observed for model training. Therefore, the proposed OPU algorithms are effective in handling real-world data.

6.4 Parametric Sensitivity

This section investigates the sensitivity of our OPU algorithms to the tuning parameter λ and the positive class prior π appearing in the objective function Eq. (7) and Eq. (10) of our OPU learning model. Specifically, we examine the test accuracy of the extended OPU algorithm with double hinge loss (i.e., OPUDH) on the two real-world datasets when r = 30%. The proposed OPUSL, OPUDH, and OPUSL all exhibit similar results to OPUDH, so here we omit their parametric sensitivity curves due to the lack of space.

Influence of λ: The experimental results with λ changing from 10-6 to 100 are reported in Figure. 1 (a), we see that λ is critical for our OPU algorithm to obtain satisfactory performance. To be specific, the choice of λ = 10-2 usually leads to high classification accuracy.

Influence of π: As mentioned previously, the positive class prior π might be unknown in practice, so it should be estimated from experience or some domain-specific prior knowledge. However, such estimation can be inaccurate, therefore we investigate how the classification accuracy is influenced by the inaccurate π. More specifically, we tested our OPUDH by replacing π with inaccurate ˆπ∈{0.6π, 0.8π,. . ., 1.4π} and inserting ˆπ to the learning method. The experimental results are presented in Figure. 1 (b), which suggests that the performance of the proposed method will not severely decrease when the estimation is slightly deviated from the real π.

7 Conclusion

This paper proposed a novel OPU learning paradigm to deal with the sequential positive and unlabeled data. We show that with an unbiased estimate for the loss induced by the received positive or unlabeled example at each time, our OPU model can be effectively solved by gradient based online learning methods. Furthermore, two OPU algorithms with different formations of input data are developed, and their regret bounds have also been theoretically proved. The experimental results on both benchmark and real-world datasets clearly demonstrate the effectiveness of the proposed method. Since our method relies on the class prior π, we may design an online strategy to estimate π incrementally in the future.

Acknowledgements

This research is supported by NSF of China (Nos: 61973162, U1713208), NSF of Jiangsu Province (No: BK20171430), the Fundamental Research Funds for the Central Universities (No: 30918011319), the Summit of the Six Top Talents Program (No: DZXX027), the Young Elite Scientists Sponsorship Program by CAST (No: 2018QNRC001), the Ant Financial Science Funds for Security Research of Ant Financial, and the Program for Changjiang Scholars.