Positive Unlabeled Learning with Class-prior Approximation

1 Introduction

For traditional supervised classification problems, both positive and negative labels should be known before building a suitable binary classifier. However, in practical application, negative data labels are difficult to obtain, such as date sets, where only the relevant class is known, and the negative class is very large and dense [Kiryo et al., 2017]. At this time, without the assistance of negative labels, analysis of positive and unlabeled (PU) data, which tries to learn a binary classifier by using only part of the labeled positive samples and other mixed samples, is used in practical applications. This special weakly supervised learning problem has been utilized in many real-world scenarios [Yu et al., 2002; Li and Liu, 2003; Fang et al., 2020a; Li et al., 2010; Xu et al., 2017; Wang et al., 2018], such as web page classification, text classification, time series classification, multiclass classification, and remote-sensing images classification, etc.

∗Corresponding author.

For better understanding of the PU learning, we give one typical example, the personalized information pushing of webs. We may only know what the users' interests by their browsing records, but do not know what users' dislike. Therefore, to ensure matching between push information and users' demands, it is necessary to adopt an appropriate content filtering approach. Since only part of the preferences are provided, PU learning methods can push the text of users' needs while filtering out the irrelevant information.

Presently, mainstream PU data analysis methods can be classified into the following three categories. The first category is heuristic methods, which identify reliable negative examples from the unlabeled data and then train the classifier using the given positive samples as well as the learned reliable negative examples. The representative method of heuristic learning is the two-step approach, such as S-EM [Liu et al., 2002], PEBL [Yu et al., 2002], and Roc-SVM [Li and Liu, 2003]. The main disadvantage of most heuristic methods is that the classification accuracy is seriously affected by the selection of reliable negative examples. In the second category, all unlabeled data is treated as noisy negative examples, and the classifier is trained by introducing small weights to negative examples. This procedure makes unlabeled positive examples have a lower penalization, such that they are labeled as negatives. Lee and Liu [2003] explain that ideally, the known positive data is pure and reliable, and logistic regression is performed after weighting the noisy samples. In reality, however the positive data may also mislabeled, and Liu and Dai proposed a biased SVM (B-SVM) [2003] method that directly uses the asymmetric cost formulation of the SVM algorithm. Since these approaches need a training process to estimate the "bias", a volatile classification will result when the training set is limited or the positive samples are unreliable. The third category associates the classifier with the risk of classification and transfers PU learning into a cost-sensitive learning problem [Gong et al., 2019b]. For example, Plessis [2014; 2015] proposed a convex formulation for PU learning and utilizes several different loss functions to maintain unbiased solutions. Further to the achievement of superior computational and memory performance, Sansone etc. [2018] proposed a scalable PU learning algorithm that converts the unbiased PU model into a sequence of quadratic programming (QP) subproblems. These methods usually employ a reweighing process to calibrate the data distribution because of the absence of negative samples; therefore, knowledge of the positive class prior is crucial. Additionally, there are also some setting-free PU methods, such as the label disambiguation-based methods [Zhang et al., 2019; Gong et al., 2019a], which enlarge the margin of potential positive examples and negative ones, as well as some booststrap sampling-based methods that create ensemble models for PU learning [Claesen et al., 2015; Yang et al., 2017].

Although a variety of methods have been proposed, the attempt to correctly label a data point will still interpreted by the absence of negative class. Fortunately, this defect can be rectified by explicitly acquiring the class prior, which is utilized as incorporated information for modeling or as a preprocessing step to assign weights to unlabeled data. Since the class prior is always unknown, in practical applications, research based on class-prior estimation has been active in past decades [Elkan and Noto, 2008; Christoffel et al., 2016; Bekker and Davis, 2018].

To overcome the drawbacks of the aforementioned methods and to expand on the mixture proportion estimation theory [Ramaswamy et al., 2016], we follow the third category and formulate a convex risk minimization joint class-prior approximation model for PU data analysis. In this model, we utilize an unbiased estimation of the classification risk of PU data, using double hinge loss to train the classifier, and pursue the class prior in a kernel embedding space with a mixture proportion approximation term. In particular, a proportion regularization term is added to balance the decision boundary and the prior estimation, as well as improve the accuracy.

The proposed PU learning model, which is named as "CAPU" in short, is effectively solved by the gradient thresholding algorithm. The theoretical analysis proves that the convergence of our model and the experimental results on extensive datasets demonstrate the superiority of the proposed algorithm compared to other state-of-the-art methods.

2 Preliminaries of PU Learning

Assume the d dimensional pattern x ∈ Rd and its class label y ∈ {1,-1} follows the class-probability density, with p(x, y). For the given i.i.d. positive dataset XP and unlabeled dataset XU , we have:

where p(x) is the marginal density, and π := p(y = 1) is the positive class-prior probability in unlabeled data.

The goal is to learn an arbitrary decision function g : Rd → R to binary classify the PU data and utilize ℓ : R → R as the loss function to quantify the values of yg(x). Then, the risks of classifier g under the loss function ℓ are:

where RP (g), RU,P and RU,N(g) denote the classification risks of the positive and unlabeled samples, and Ex∼p(x,y)[·] denotes the expectation of x over the probability distribution p(x, y).

The binary classification risk is a sum of the weighted positive class loss and negative class loss; therefore, the risk of our PU problem can be expressed as:

The first term in Eq. (1) is equal to the risk of the positive samples, which means that RU,P (g) = RP (g). Moreover, since no negative samples are labeled, naively training a classifier using only positive and unlabeled data may cause a bias. To overcome this problem, du Plessis et al. [2014; 2015] devised a risk deformation formula that is equivalent to traditional supervised classification risk. The second term in Eq. (1) is replaced by

Introducing a convex surrogate loss ˜ ℓ(m) = ℓ(m) + ℓ(-m) = -m, the risk is yielded to the following convex optimization problem and solved efficiently:

3 Our Method

In this section, we first establish our CAPU model, and then list brief theoretical analysis and optimization process of our model.

3.1 Model

Giving a dataset X = {XP ;XU} = {(x1, y1), ..., (xnp , ynp ); (xnp+1, ynp+1), ..., (xn, yn)} with np positive samples and nu unlabeled samples, where n = np + nu. In practice, we use a linear-in-parameter function to denote g:

where φ is the set of kernel basis function which will be discussed later in this section. Then the empirical risk ˆR of Eq. (3) using n samples is:

where λ is the regularization parameter, and α is the parameter vector applied to minimize the ℓ2-regularized empirical risk. To solve this optimization problem, a convex loss function [Ye et al., 2018], double hinge loss, is introduced to Eq. (5). The formulation of DH loss is:

The PU model with a convex loss can be easily solved using the quadratic programming method. These risk estimators are based on the assumption that the class-prior probability π is known. However, in real-word applications, π is difficult to obtain and must be learned from data, which makes the risk evaluation model unsolvable. Therefore, combining a mixture proportion estimator, we proposed a Classprior Approximation model for PU learning (CAPU), this optimization function can simultaneously pursue the class prior and optimize the parameters of the classifier.

If the distribution of XU obeys i.i.d and can be approximately represented by a linear combination of positive and negative distributions:

where PU , PU,P and PU,N are the distributions of XU , XU,P and XU,N in feature space X, respectively, and π⋆ represents the true value of π,

For general semi-supervised classification learning that has both positive and negative labels, the labeled samples should have similar distributions to the unlabeled samples: XP ,XU,P ∼ p(x|y = 1) and XN,XU,N ∼ p(x|y = -1), and the mixture proportion estimation (MPE) methods [Ramaswamy et al., 2016; Yu et al., 2018] can solve this problem. It assumes there exists a reproducing kernel Hilbert space (RKHS) H, where φ : X → H represents the kernel mapping x → k(x, ·). The class proportion π is solved by minimizing the distance between the mixture and the given samples in the reproducing kernel Hilbert space (RKHS):

Intuitively, this equation equals the maximum mean discrepancy (MMD), where d(π) is a reconstruction from PP and PN to the mixture PU. In practical applications, it must be replaced by empirical function:

which is a convex quadratic programming problem and can be solved using standard procedures. However, for practical PU analysis, the MPE model usually fails to separate the unlabeled negative samples from the mixture, since only positive samples are known. The third term of Eq. (8) is not identifiable; therefore, the optimal solution ˜π tends to be 1, which will cause serious misclassification.

To better suit PU data, we rewrite Eq. (6) in the following form:

where θ⋆ = 1 1-π⋆ . So for the deformation from θ to π, there is a probability weighted vector ν ⊆ Rn given by ν = {νi ∈ [0, 1), ∑i νi = 1}, which makes the following empirical squared maximum mean discrepancy (MMD)

lower bounded:

With a combination of the empirical risk and squared MMD, the objective function of our CAPU model is formulated using the same RBF kernel, 〈φ(xi), φ(xj)〉 = exp(- ‖xi-xj‖2 2σ2 ). We can tell the coefficient νi corresponds to the positive class turn out to be smaller, and that corresponds to negative class are larger, which just opposite to αTφ(xi). To further makes our objective function more robust, we assume the separability vector ν and the parameter α satisfy ν ≈ - 1n φ(x)Tα. Therefore, the objective function of our CAPUmodel ˆ F with the selected DH loss is written as:

Compared to state-of-the-art method, the proposed model expects to simultaneously approximate the class prior of unlabeled samples and learn a fit classifier. In particular, we introduce a slack variable ξ ∈ Rnu to transform the double hinge loss function, and utilize µTθ = [ 1-θ np 1Tnp , θ nu 1Tnu ], where 1k is a k-dimensional all ones vector, to transform Eq. (10), whose equivalent dual problem can be expressed as:

Where γ, δ ∈ Rn are the Lagrange multipliers introduced to derive the dual formulation, K ∈ Rn×n is the Gram matrix given by Ki,j = 〈φ(xi), φ(xj)〉, ˜1 = [1, ..., 1, 0, ..., 0]T ∈ Rn×1 has np ones elements, and U ∈ Rnu×n is a concatenation of a nu × np null matrix and a nu-size identity matrix. ⪰ represents the operation elements-wise. The proposed CAPU model can be efficiently computed via solving a standard quadratic programming using the gradient thresholding estimator.

3.2 Theoretical Analysis

To solve the parameters of the proposed CAPU model, we utilize the gradient thresholding estimator which first estimate ˜π (or equivalently ˜ θ) and then using standard quadratic programming method to find (˜ γ, ˜ δ, ˜ ν). ˜ (·) represents the optimal value of the current variable. Before solving this model, some theoretical analysis is listed for the proposed model.

First, our objective function can be viewed as a function related to parameter θ:

Then the following Lemma holds,

Lemma 1. Let the kernel k be such that k(x, x) ≤ 1 for all x ∈ X. Then with probability at least 1 - δ, the following holds if nu ≥ 2(θ⋆ )2 log( 5δ )

where C = 2λ |b| + 1λ + 2λ (µθ - ν)TK(µθ - ν) + 2λ ν Tν. The first statement can be derived by deducing Rademacher complexity and the approximation of Eq. (10). The second and third statements are learned from Theorem 2 of Smola et al. [2007] and the last statement utilizes Hoeffding's inequality. Lemma 1 proves that ˆ F(θ) is upper bounded for θ ∈ [1, θ⋆ ].

Lemma 2. For all θ ∈ [1, θ⋆ ] we have:

Theorem 1. Assume the kernel k, the distributions XP and XN satisfy the separability condition with average level τ, the margin is c > 0, and the tolerance is d, then for arbitrary ∆ > 0, we have

Algorithm 1 The optimization process of the proposed model

Input: The given positive samples xP := {xi}np i=1 and the unlabeled samples xU := {xi}nu i=1

Parameter: The width of Gaussian kernel σ, hyperparameters λ and β and threshold µ = 1/min(np, nu)

θ,˜ γ,˜ δ,˜ ν

Output: ˜

Constants: ϵ = 0.04, θmax = 10

• 1: Let θl = 1, θr = θmax

2: while θr - θl ≥ ϵ do

• 3: θ = θl+θr 2

8: F2 = ˆ

9: s =

10:

F(θ2)

√F2-√F1

θ2-θ1

if s > µ then

11:

θ2 = θ.

• 12: else

13:

θ1 = θ.

• 14: end if
• 15: end while

16: return θ → ˜

θ

θ and ˜π = 1 - 1/˜

17: Optimize the objective function min

γ,δ,ν

• 18: return ˜ γ, ˜ δ, ˜ ν

ˆ

F(˜

θ)

Through the above analysis, we can finally derive that the slope of function F(θ) satisfies:

Lemma 3. Let the kernel k be such that k(x, x) ≤ 1 for all x ∈ X. Assume the kernel k, the distributions PP and PN satisfy the separability condition with average level τ, the margin is c > 0 and the tolerance is d. Then the gradient of ˆ F(θ) at some ˜ θκ < θ⋆ is also upper and lower bounded.

Proof. (Sketch) This lemma can be derived from Lemma 2 and Theorem 1. Considering that ˆ F(θ) is a convex function of θ, the gradient of ˆ F(θ) at some ˜ θ < θ⋆ is also upper and lower bounded.

3.3 Optimization

Since there is a reciprocal form of θ in our objective function, the general optimization method is difficult to apply. Through above analysis, we derived that our objective function F(θ) is upper bounded and converges to θ⋆2 at a rate of O(n-1 p ). Therefore, the gradient thresholding algorithm via binary search is designed to solve the proposed model. Detailed descriptions of the computation are given in Algorithm 1, where ˆ F(θ) is the first objective function and the setting of threshold µ is followed by Lemma 3.

This gradient thresholding estimator first gives the upper and lower bounds (θl and θr) to constrain the value of θ, and it conducts the binary search by minimizing the value of ˆ F (θ)

at θ±ϵ/4, respectively. The current bounds of θ and the termination of Algorithm 1 is determined by the computed slope. The minimization of ˆ Fθ is a standard quadratic programming problem and can be optimized by the general purpose convex programming solver, such as CVXOPT, Gurobi or MATLAB's internal 'quadprog' function.

4 Experimental Procedure

In this section, we systematically evaluate the effectiveness of the proposed CAPU method compared with other state-of-the art PU methods in a synthetic dataset and real-world datasets taken from UCI Machine Learning Repository.

Synthetic Dataset. The parametric analysis and evaluations were implemented in the synthetic dataset. This data comprises two clusters generated from Gaussian distributions centered at (0, 0) and (2, 2), and the variance of both clusters is 1. In total, it contains 800 samples whereas 200 examples are labeled as positives. The size of the unlabeled samples is fixed at 600. Then, the proposed CAPU model was conducted with a class prior varies from [0.3, 0.5, 0.7].

Real-world Datasets. We utilize four real-world datasets downloaded from the UCI Machine Learning Repository to evaluate the performance of our proposed algorithm. These datasets include the audit, ionosphere, diabetes and vertebral, and their configurations are listed in Table 2. Based on the sizes of the different datasets, we set the number of positive samples as 100 and the unlabeled samples as 400 for the audit dataset. The sizes of np and nu are 50 and 200, respectively, for the diabetes dataset. And for the ionosphere and vertebral datasets, we set np = 25 and nu = 100. For each dataset, π ∈ [30%, 50%, 70%] samples of the unlabel to be positive and the rest samples are negative.

Comparable Methods. The proposed CAPU method is compared with related works such as EN 1 [Elkan and Noto, 2008], PE 2 [Du Plessis and Sugiyama, 2014], KM 3 [Ramaswamy et al., 2016], and TIcE 4 [Bekker and Davis, 2018]. The aforementioned methods have made great efforts in estimating the true class prior. Considering that the KM and TIcE do not provide a classification process, we report the accuracies utilizing a benchmark PU learning method: the unbiased PU (UPU) 5 [Du Plessis et al., 2015]. For further accuracy comparison, the UPU [Du Plessis et al., 2015] and an improved method, USMO 6 [Sansone et al., 2018], are also tested with the truth vale of π.

1 The coding work of EN method can be found at https://github. com/aldro61/pu- learning

2 The code for PE is taken from http://www.mcduplessis.com/index.php/ class-prior-estimation-from-positive-and-unlabeled-data/

3 The code for KM method is taken from http://web.eecs.umich. edu/∼cscott/code/kernel MPE.zip

4 The code for TIcE method can be found at https://dtai.cs. kuleuven.be/software/tice

5 The coding work of UPU method can be found at https://github. com/kiryor/nnPUlearning

6 The code for USMO method is available at https://github.com/ emsansone/USMO

4.1 Results

To create PU samples from each dataset, we derived three different settings of positive and unlabeled samples as follows. We first set a fraction of the positives as the labeled samples, then we select part of the remaining positive and negative instances as the unlabeled set. The class-prior in the unlabeled set varies in [0.3, 0.5, 0.7]. This procedure was repeated 20 times for each setting for each dataset, and the evaluation matrices applied for performance comparisons are the mean class-prior estimates ˜π, the mean absolute errors |˜π - π| and the F-scores [Fang et al., 2020b] over 20 trials.

The results of all methods on the synthetic dataset are reported in Table 1. In this two-cluster Gaussian distributed dataset, KM has the nearest class-prior estimation when π = 0.3 and 0.5, and the proposed CAPU method generally has secondary performance. When applying the classification evaluation, our method achieves the best classification accuracy compared with other methods.

Table 2 illustrates the comparative result of the proposed CAPU method and other methods on four UCI datasets. We found that in most occasions, our method have the superior class-prior approximation, while in few cases, the KM and TIcE methods are better than CAPU. But for the classification accuracies, our model achieves the best in most occasions even the true class prior is given for USMO and UPU methods.

4.2 Parametric Analysis

There are three parameters included in our CAPUmodel: the width σ of the RBF kernel, and the trade off parameters λ and β. Therefore, this section examines the parametric sensitivity of our model on the synthetic dataset.

Figure 1 shows the mean absolute error |˜π - π| and the F-scores related to σ on the three settings of the synthetic dataset. It is known that the smaller values of the error represents the better estimates, and the higher F-scores mean better classification accuracy. It is shown that in all three settings, the performance of our CAPU model is best when the kernel width σ = 1. To evaluate the accuracy associated with hyperparameters λ and β, Figure 2 shows a 3-D cube where the z-axis show the mean F-score values of CAPU over 20 times' repeated tests. It can be seen that the proposed CAPUmodel is not much sensitive to β, but to λ.

4.3 Discussion

Through out previous analysis, we found that when estimating the class prior, our method has similar performances to other methods. But for classification accuracy, our method gets the best F-score in most cases. In this section, we discuss the reasons for this result.

Firstly, traditional PU learning models based on the risk minimization treat misclassification errors as proportions of labeled positives and unlabeled negatives, which determines that it is always crucial to know the class prior, such as in UPU and USMO methods. However, the necessary knowledge of π is obviously inconsistent with reality. Therefore, some research based on class-prior estimation has been proposed, such as the KM and TIcE methods. These methods provide additional information for later analysis, but they only provide an estimation of the positive proportions. In addition, there are also some methods based on class-prior correction and classification, such as the benchmark EN and PE methods, which can estimate class prior as well as classify data. We found that these methods have unstable performance with huge estimation errors, which then easily leads to poor classification results.

Compared with the aforementioned research, our method is undoubtedly more suitable for PU data analysis. This model overcomes the lack of class-prior information for the general PU method, and it can classify the dataset with superior accuracy compared to other methods.

5 Conclusion

This paper proposed a novel PU learning method with class prior approximation. Different from previous analyses, we convert PU learning to a direct class-prior estimation and classification problem by introducing the mixture proportion estimation to the loss minimization function. Furthermore, an additional regularization term balances the classifying vector and the proportion estimation result. A gradient thresholding algorithm is utilized based on rigorous theoretical analysis. Experimental results on both synthetic and real-world datasets clearly show that CAPU is superior to other state-ofthe-art methods.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grants 61822113, 62041105, the Science and Technology Major Project of Hubei Province (Next-Generation AI Technologies) under Grant 2019AEA170, the Natural Science Foundation of Hubei Province under Grants 2018CFA050, the Fundamental Research Funds for the Central Universities under Grant 413000092 and 413000082. And the numerical calculations in this paper have been done on the supercomputing system in the Supercomputing Center of Wuhan University.